Créez un chargeur de démarrage qui exécute le programme Brainfuck donné. C'est du code-golf , donc le programme avec le moins d'octets gagne. Étant un chargeur de démarrage, la taille du programme est comptée en octets non nuls dans le code compilé.

Brainfuck

30000 cellules débordantes 8 bits. Le pointeur s'enroule.

Quelques notes sur les opérations:

• L'entrée doit être lue de manière à ce que tous les caractères ASCII imprimables soient correctement pris en charge. D'autres frappes peuvent soit insérer un caractère arbitraire, soit ne rien faire du tout.
• La lecture des entrées utilisateur doit être mise en mémoire tampon de caractères, pas mise en mémoire tampon de ligne.
• La lecture de l'entrée utilisateur doit faire écho au caractère inséré.
• La sortie doit suivre la page de codes 437 ou la page de codes par défaut de vos adaptateurs VGA intégrés.

Bootloader

Il s'agit d'un chargeur de démarrage x86. Un chargeur de démarrage se termine par la 55 AAséquence traditionnelle . Votre code doit être exécuté sur VirtualBox, Qemu ou tout autre émulateur x86 bien connu.

Disque

L'exécutable Brainfuck est situé au deuxième secteur de disque, juste après votre chargeur de démarrage, qui est placé, comme d'habitude, dans la section MBR, le premier secteur sur le disque. Du code supplémentaire (tout code de plus de 510 octets) peut être localisé sur d'autres secteurs de disque. Votre périphérique de stockage doit être un disque dur ou une disquette.

STDIO

Bien sûr, un chargeur de démarrage ne peut pas avoir accès aux capacités d'E / S du système d'exploitation. Par conséquent, les fonctions du BIOS sont utilisées à la place pour imprimer du texte et lire les entrées utilisateur.

Modèle

Pour commencer, voici un modèle simple écrit en assembleur Nasm (syntaxe intel):

[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

La compilation est assez simple:

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

Et le courir. Par exemple, avec Qemu:

qemu-system-i386 -fda boot.raw

Informations supplémentaires: wiki OsDev , Wikipedia

171 octets ¹

Wooohoooo! Ça a pris la moitié de la journée, mais c'était amusant ...

Alors voilà. Je pense qu'il est conforme aux spécifications (enveloppement du pointeur de cellule, écho des caractères en entrée, lecture char par char, écho des caractères d'entrée, ...), et il semble fonctionner réellement (enfin, je n'ai pas essayé beaucoup de programmes , mais étant donné la simplicité de la langue, la couverture n'est pas si mauvaise, je pense).

Limites

Une chose importante: si votre programme brainfuck contient d'autres caractères que les 8 instructions brainfuck, ou si []elles ne sont pas bien équilibrées, il va planter sur vous, mouhahahaha!

De plus, le programme brainfuck ne peut pas dépasser 512 octets (un secteur). Mais cela semble conforme puisque vous dites que "l'exécutable Brainfuck est situé au deuxième secteur du disque" .

Dernier détail: je n'ai pas explicitement initialisé les cellules à zéro. Qemu semble le faire pour moi, et je compte sur cela, mais je ne sais pas si un vrai BIOS sur un vrai ordinateur le ferait (l'initialisation ne prendrait que quelques octets de plus, de toute façon).

Le code

^{(basé sur votre modèle, et d'ailleurs, merci pour cela, je n'aurais jamais essayé sans):}

[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

Astuces utilisées

Ok, j'ai un peu triché. Puisque vous avez dit "étant un chargeur de démarrage, la taille du programme est comptée en octets non nuls dans le code compilé" , j'ai rendu le code plus petit en permettant des "trous" entre l'implémentation des huit opcodes brainfuck. De cette façon, je n'ai pas besoin d'une grande séquence de tests, d'une table de sauts ou de quoi que ce soit: je saute juste à "id de code d'opération" brainfuck (de 0 à 8) multiplié par 32 pour exécuter l'instruction brainfuck (vaut la peine de noter que cela signifie que la mise en œuvre des instructions ne peut pas prendre plus de 32 octets).

De plus, pour obtenir cet "identifiant d'opcode" à partir du caractère du programme brainfuck récupéré, j'ai remarqué qu'un peu de mélange était nécessaire. En effet, si nous considérons uniquement les bits 0, 1 et 4 du caractère opcode, nous nous retrouvons avec les 8 combinaisons uniques:

   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.

Et, heureusement, il y a en fait un opcode qui nécessite plus de 32 octets pour être implémenté, mais c'est le dernier (aller de l'avant [). Comme il y a plus de place après, tout va bien.

Autre astuce: je ne sais pas comment fonctionne un interpréteur de brainfuck typique, mais, pour rendre les choses beaucoup plus petites, je n'ai pas réellement implémenté ]comme "Revenir en arrière après les [données si le pointeur correspondant n'est pas nul" . Au lieu de cela, je reviens toujours à la correspondante [et, à partir d'ici, réappliquons l' [implémentation typique (qui ensuite, éventuellement, se poursuit après la ]si nécessaire). Pour cela, chaque fois que je rencontre un [, je mets le "pointeur d'instruction brainfuck" actuel sur la pile avant d'exécuter les instructions internes, et quand je rencontre un], Je ramène le pointeur d'instruction. Un peu comme si c'était un appel à une fonction. Vous pourriez donc théoriquement déborder la pile en faisant de nombreuses boucles imbriquées, mais pas avec la limitation actuelle de 512 octets du code brainfuck, de toute façon.

^{1. Y compris les octets zéro qui faisaient partie du code lui-même, mais pas ceux qui faisaient partie d'un remplissage}