Bootloader golf: Brainf ***

20

Cree un gestor de arranque que ejecute el programa Brainfuck dado. Este es el , por lo que gana el programa con menos bytes. Al ser un gestor de arranque, el tamaño del programa se cuenta en bytes distintos de cero en el código compilado.

Brainfuck

30000 celdas desbordantes de 8 bits. El puntero se envuelve.

Algunas notas sobre operaciones:

  • La entrada debe leerse de manera que todos los caracteres ASCII imprimibles sean compatibles correctamente. Otras pulsaciones de teclas pueden insertar un carácter arbitrario o no hacer nada en absoluto.
  • La lectura de la entrada del usuario debe tener un buffer de caracteres, no un buffer de línea.
  • La lectura de la entrada del usuario debe hacer eco del carácter insertado.
  • La salida debe seguir la página de códigos 437 o la página de códigos predeterminada de sus adaptadores VGA incorporados.

Cargador de arranque

Este es un gestor de arranque x86. Un gestor de arranque termina con la 55 AAsecuencia tradicional . Su código debe ejecutarse en VirtualBox, Qemu u otro emulador x86 conocido.

Disco

Brainfuck ejecutable se encuentra en el segundo sector del disco, justo después de su gestor de arranque, que se coloca, como generalmente, en la sección MBR, el primer sector en el disco. El código adicional (cualquier código de más de 510 bytes) se puede ubicar en otros sectores del disco. Su dispositivo de almacenamiento debe ser un disco duro o un disquete.

STDIO

Por supuesto, un gestor de arranque no puede tener acceso a las capacidades de E / S del sistema operativo. Por lo tanto, las funciones del BIOS se utilizan en su lugar para imprimir texto y leer la entrada del usuario.

Modelo

Para comenzar, aquí hay una plantilla simple escrita en ensamblaje Nasm (sintaxis de 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

Compilar esto es bastante fácil:

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

Y la corren. Por ejemplo, con Qemu:

qemu-system-i386 -fda boot.raw

Información adicional: OsDev wiki , Wikipedia

Hannes Karppila
fuente
21
Input must be redEstoy bastante seguro de que la mayoría de los gestores de arranque no admiten el color de forma nativa.
Fondo de la demanda de Mónica
44
¡Uno debería explicar a los desarrolladores más jóvenes qué es un disquete!
bobbel
1
@bobbel Comencemos con el gestor de arranque
Bálint
55
No es que este título me parezca ofensivo, pero ¿cómo es posible? Según el meta , es imposible poner "brainfuck" en el título.
DJMcMayhem
¿Podemos usar más de 30k células?
CalculatorFeline

Respuestas:

13

171 bytes 1

Wooohoooo! Me llevó medio día, pero fue divertido ...

Asi que aqui esta. Creo que se ajusta a las especificaciones (envolvente del puntero de la celda, eco de caracteres en la entrada, lectura de char por char, eco de caracteres de entrada, ...), y parece que realmente funciona (bueno, no probé muchos programas , pero dada la simplicidad del lenguaje, la cobertura no es tan mala, creo).

Limitaciones

Una cosa importante: si su programa Brainfuck contiene otros caracteres que no sean las 8 instrucciones Brainfuck, o si []no están bien equilibrados, ¡ se bloqueará en usted, mouhahahaha!

Además, el programa brainfuck no puede superar los 512 bytes (un sector). Pero esto parece conforme, ya que dice "Brainfuck ejecutable se encuentra en el segundo sector del disco" .

Último detalle: no inicialicé explícitamente las celdas a cero. Qemu parece hacerlo por mí, y estoy confiando en esto, pero no sé si un BIOS real en una computadora real lo haría (la inicialización solo tomaría unos pocos bytes más, de todos modos).

El código

(basado en su plantilla, y por cierto, gracias por esto, nunca lo habría intentado sin él):

[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

Trucos usados

Ok, hice trampa un poco. Como dijiste "al ser un gestor de arranque, el tamaño del programa se cuenta en bytes distintos de cero en el código compilado" , reduje el código al permitir "agujeros" entre la implementación de los ocho opcodes brainfuck. De esta manera, no necesito una gran secuencia de pruebas, una tabla de salto, ni nada: simplemente salto al "idcode op" de brainfuck (de 0 a 8) multiplicado por 32 para ejecutar la instrucción de brainfuck (vale la pena señalar que significa que la implementación de las instrucciones no puede tomar más de 32 bytes).

Por otra parte, para obtener esta "identificación de código de operación" del personaje del programa Brainfuck obtenido, noté que era necesario un poco de barajado. De hecho, si solo consideramos los bits 0, 1 y 4 del carácter del código de operación, terminamos con las 8 combinaciones únicas:

   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.

Y, por suerte, en realidad hay un código de operación que requiere más de 32 bytes para implementarse, pero es el último (saltar hacia adelante [). Como hay más espacio después, todo está bien.

Otro truco: no sé cómo funciona un intérprete típico de brainfuck, pero, para hacer las cosas mucho más pequeñas, en realidad no lo implementé ]como "Volver atrás después del correspondiente [si los datos en el puntero no son cero" . En cambio, siempre vuelvo a la correspondiente [y, a partir de aquí, vuelvo a aplicar la [implementación típica (que luego, eventualmente, avanza después de la ]otra si es necesario). Para esto, cada vez que me encuentro con un [, pongo el "puntero de instrucción de brainfuck" actual en la pila antes de ejecutar las instrucciones internas, y cuando encuentro un], Hago retroceder el puntero de instrucciones. Casi como si fuera una llamada a una función. Por lo tanto, en teoría, podría desbordar la pila haciendo muchos bucles imbricados, pero de todos modos no con la limitación actual de 512 bytes del código brainfuck.


1. Incluyendo los bytes cero que formaban parte del código en sí, pero no los que formaban parte de algún relleno

oscuro
fuente