Bootloader Golf: Brainf ***

20

Erstellen Sie einen Bootloader, der ein bestimmtes Brainfuck-Programm ausführt. Das ist , also gewinnt das Programm mit den wenigsten Bytes. Als Bootloader wird die Größe des Programms im kompilierten Code in Bytes ungleich Null gezählt.

Brainfuck

30000 überlaufende 8-Bit-Zellen. Zeiger springt über.

Einige Anmerkungen zu Operationen:

  • Die Eingabe muss so gelesen werden, dass alle druckbaren ASCII-Zeichen korrekt unterstützt werden. Andere Tastenanschläge können entweder ein beliebiges Zeichen einfügen oder gar nichts bewirken.
  • Das Lesen von Benutzereingaben muss zeichen- und nicht zeilenweise erfolgen.
  • Das Lesen von Benutzereingaben muss das eingegebene Zeichen wiedergeben.
  • Die Ausgabe muss entweder der Codepage 437 oder der Standard-Codepage Ihres integrierten VGA-Adapters folgen .

Bootloader

Dies ist ein x86-Bootloader. Ein Bootloader endet mit der traditionellen 55 AAReihenfolge. Ihr Code muss entweder auf VirtualBox, Qemu oder einem anderen bekannten x86-Emulator ausgeführt werden.

Platte

Die ausführbare Datei "Brainfuck" befindet sich im zweiten Festplattensektor direkt nach Ihrem Bootloader. Dieser befindet sich wie gewöhnlich im MBR-Abschnitt, dem ersten Sektor auf der Festplatte. Zusätzlicher Code (jeder Code über 510 Byte) kann sich in anderen Plattensektoren befinden. Ihr Speichergerät muss entweder eine Festplatte oder eine Diskette sein.

STDIO

Natürlich kann ein Bootloader nicht auf die IO-Funktionen des Betriebssystems zugreifen. Daher werden stattdessen BIOS-Funktionen zum Drucken von Text und Lesen von Benutzereingaben verwendet.

Vorlage

Hier ist eine einfache Vorlage, die in der Nasm-Assembly (Intel-Syntax) geschrieben wurde:

[BITS 16]
[ORG 0x7c00]

; first sector:

boot:
    ; initialize segment registers
    xor ax, ax
    mov ds, ax
    mov es, ax
    mov ss, ax

    ; initialize stack
    mov sp, 0x7bfe

    ; load brainfuck code into 0x8000
    ; no error checking is used
    mov ah, 2       ; read
    mov al, 1       ; one sector
    mov ch, 0       ; cylinder & 0xff
    mov cl, 2       ; sector | ((cylinder >> 2) & 0xc0)
    mov dh, 0       ; head
                    ; dl is already the drive number
    mov bx, 0x8000  ; read buffer (es:bx)
    int 0x13        ; read sectors


; fill sector
times (0x200 - 2)-($-$$) db 0

; boot signature
db 0x55, 0xaa

; second sector:

db 'brainfuck code here'

times 0x400-($-$$) db 0

Dies zu kompilieren ist ziemlich einfach:

nasm file.asm -f bin -o boot.raw

Und die laufen davon. Zum Beispiel mit Qemu:

qemu-system-i386 -fda boot.raw

Weitere Informationen: OsDev-Wiki , Wikipedia

Hannes Karppila
quelle
21
Input must be redIch bin mir ziemlich sicher, dass die meisten Bootloader von Haus aus keine Farben unterstützen.
Fund Monica's Lawsuit
4
Man sollte jüngeren Entwicklern erklären, was eine Diskette ist!
Bobbel
1
@bobbel Beginnen wir mit dem Bootloader
Bálint
5
Nicht, dass ich diesen Titel beleidigend finde, aber wie ist das möglich? Laut Meta ist es unmöglich, "Brainfuck" in den Titel zu setzen.
DJMcMayhem
Können wir mehr als 30k Zellen verwenden?
CalculatorFeline

Antworten:

13

171 Bytes 1

Wooohoooo! Es hat den halben Tag gedauert, aber es hat Spaß gemacht ...

Hier ist es also. Ich denke, es entspricht den Spezifikationen (Umlauf des Zellenzeigers, Echo der Zeichen bei der Eingabe, Lesen von Zeichen für Zeichen, Echo der Eingabezeichen, ...), und es scheint tatsächlich zu funktionieren (naja, ich habe nicht viele Programme ausprobiert Aber angesichts der Einfachheit der Sprache ist die Berichterstattung meiner Meinung nach nicht so schlecht.

Einschränkungen

Eine wichtige Sache: Wenn Ihr Brainfuck-Programm andere Zeichen als die 8 Brainfuck-Anweisungen enthält oder wenn die []nicht ausgewogen sind, stürzt es auf Sie ab, mouhahahaha!

Außerdem darf das Brainfuck-Programm 512 Byte (einen Sektor) nicht überschreiten. Dies scheint jedoch konform zu sein, da Sie sagen, "ausführbares Brainfuck befindet sich im zweiten Plattensektor" .

Letztes Detail: Ich habe die Zellen nicht explizit auf Null initialisiert. Qemu scheint es für mich zu tun, und ich verlasse mich darauf, aber ich weiß nicht, ob es ein echtes BIOS auf einem echten Computer tun würde (die Initialisierung würde sowieso nur ein paar Bytes länger dauern).

Der Code

(basierend auf Ihrer Vorlage und übrigens, danke dafür, ich hätte es nie ohne versucht):

[BITS 16]
[ORG 0x7C00]

%define cellcount 30000 ; you can't actually increase this value much beyond this point...

; first sector:

boot:
    ; initialize segment registers
    xor ax, ax
    mov ss, ax
    mov ds, ax
    mov es, ax
    jmp 0x0000:$+5

    ; initialize stack
    mov sp, 0x7bfe

    ; load brainfuck code into 0x8000
    ; no error checking is used
    mov ah, 2       ; read
    mov al, 1       ; one sector
    mov ch, 0       ; cylinder & 0xff
    mov cl, 2       ; sector | ((cylinder >> 2) & 0xc0)
    mov dh, 0       ; head
                    ; dl is already the drive number
    mov bx, 0x8000  ; read buffer (es:bx)
    int 0x13        ; read sectors

    ; initialize SI (instruction pointer)
    mov si, bx ; 0x8000
    ; initialize DI (data pointer)
    mov bh, 0x82
    mov di, bx ; 0x8200

decode:
    lodsb ; fetch brainfuck instruction character
.theend:
    test al, al ; endless loop on 0x00
    jz .theend
    and ax, 0x0013 ; otherwise, bit shuffling to get opcode id
    shl ax, 4
    shl al, 2
    shr ax, 1
    add ax, getchar ; and compute instruction implementation address
    jmp ax

align 32, db 0

getchar:
    xor ah, ah
    int 0x16
    cmp al, 13
    jne .normal
    mov al, 10 ; "enter" key translated to newline
.normal:
    mov byte [di], al
    push di
    jmp echochar

align 32, db 0

decrementdata:
    dec byte [di]
    jmp decode

align 32, db 0

putchar:
    push di
    mov al, byte [di]
echochar:
    mov ah, 0x0E
    xor bx, bx
    cmp al, 10 ; newline needs additional carriage return
    jne .normal
    mov al, 13
    int 0x10
    mov al, 10
.normal:
    int 0x10
    pop di
    jmp decode

align 32, db 0

incrementdata:
    inc byte [di]
    jmp decode

align 32, db 0

decrementptr:
    dec di
    cmp di, 0x8200 ; pointer wraparound check (really, was that necessary?)
    jge decode
    add di, cellcount
    jmp decode

align 32, db 0

jumpback:
    pop si
    jmp jumpforward

align 32, db 0

incrementptr:
    inc di
    cmp di, 0x8200+cellcount  ; pointer wraparound check
    jl decode
    sub di, cellcount
    jmp decode

align 32, db 0

jumpforward:
    cmp byte [di], 0
    jz .skip
    push si
    jmp decode
.skip:
    xor bx, bx ; bx contains the count of [ ] imbrication
.loop:
    lodsb
    cmp al, '['
    je .inc
    cmp al, ']'
    jne .loop
    test bx, bx
    jz decode
    dec bx
    jmp .loop
.inc:
    inc bx
    jmp .loop

; fill sector
times (0x1FE)-($-$$) db 0

; boot signature
db 0x55, 0xAA

; second sector contains the actual brainfuck program
; currently: "Hello world" followed by a stdin->stdout cat loop

db '++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.,[.,]'

times 0x400-($-$$) db 0

Tricks verwendet

Ok, ich habe ein bisschen geschummelt. Da Sie sagten, "ein Bootloader zu sein, wird die Größe des Programms im kompilierten Code in Bytes ungleich Null gezählt" , habe ich den Code verkleinert, indem ich "Löcher" zwischen der Implementierung der acht Brainfuck-Opcodes zugelassen habe. Auf diese Weise brauche ich keine große Sequenz von Tests, keine Sprungtabelle oder irgendetwas anderes: Ich springe einfach zu der Brainfuck-Opcode-ID (von 0 bis 8) multipliziert mit 32, um den Brainfuck-Befehl auszuführen (das ist es wert, darauf hingewiesen zu werden Dies bedeutet, dass die Implementierung der Anweisungen nicht mehr als 32 Byte dauern kann.

Um diese "Opcode-ID" aus dem Brainfuck-Programm-Zeichen zu erhalten, bemerkte ich außerdem, dass nur ein bisschen Mischen notwendig war. Betrachten wir nur die Bits 0, 1 und 4 des Opcode-Zeichens, ergeben sich die 8 eindeutigen Kombinationen:

   X  XX
00101100 0x2C , Accept one byte of input, storing its value in the byte at the pointer.
00101101 0x2D - Decrement (decrease by one) the byte at the pointer.
00101110 0x2E . Output the value of the byte at the pointer.
00101011 0x2B + Increment (increase by one) the byte at the pointer.
00111100 0x3C < Decrement the pointer (to point to the next cell to the left).
01011101 0x5D ] Jump back after the corresp [ if data at pointer is nonzero.
00111110 0x3E > Increment the pointer (to point to the next cell to the right).
01011011 0x5B [ Jump forward after the corresp ] if data at pointer is zero.

Und zum Glück gibt es tatsächlich einen Opcode, für dessen Implementierung mehr als 32 Bytes erforderlich sind, aber es ist der letzte (Sprung nach vorne [). Da nachher mehr Platz ist, ist alles in Ordnung.

Anderer Trick: Ich weiß nicht , wie ein typischer Gehirnfick Interpreter funktioniert, aber, um die Dinge viel kleiner, habe ich nicht tatsächlich umsetzen ]als „nach dem entsprechenden Sprung zurück , [wenn Daten auf Zeiger nicht Null sind“ . Stattdessen gehe ich immer auf die entsprechende zurück [und wende von hier aus die typische [Implementierung erneut an (die dann ]gegebenenfalls nach der erneuten erneuten Implementierung fortgesetzt wird). Aus diesem Grund [setze ich jedes Mal , wenn ich auf a stoße , den aktuellen "Brainfuck-Anweisungszeiger" auf den Stapel, bevor ich die inneren Anweisungen ausführe, und wenn ich auf a stoße]Ich stelle den Befehlszeiger zurück. Ziemlich so, als wäre es ein Aufruf einer Funktion. Sie könnten daher theoretisch den Stapel überlaufen lassen, indem Sie viele unregelmäßige Schleifen bilden, aber nicht mit der aktuellen 512-Byte-Beschränkung des Brainfuck-Codes.


1. Einschließlich der Null-Bytes, die Teil des Codes selbst waren, aber nicht derjenigen, die Teil einer Auffüllung waren

trübe
quelle