Golfe do carregador de inicialização: Brainf ***

20

Crie um gerenciador de inicialização que execute o programa Brainfuck fornecido. Isso é , então o programa com menos bytes vence. Sendo um carregador de inicialização, o tamanho do programa é contado em bytes diferentes de zero no código compilado.

Brainfuck

30000 células transbordando de 8 bits. O ponteiro se aproxima.

Algumas notas sobre operações:

  • A entrada deve ser lida de forma que todos os caracteres ASCII imprimíveis sejam suportados corretamente. Outros pressionamentos de tecla podem inserir um caractere arbitrário ou não fazer absolutamente nada.
  • A leitura da entrada do usuário deve ter um buffer de caracteres, não um buffer de linha.
  • A leitura da entrada do usuário deve fazer eco do caractere inserido.
  • A saída deve seguir a página de código 437 ou a página de código padrão dos adaptadores VGA internos.

Carregador de inicialização

Este é um carregador de inicialização x86. Um gerenciador de inicialização termina com o tradicional55 AA sequência . Seu código deve ser executado no VirtualBox, Qemu ou outro emulador x86 conhecido.

Disco

O Brainfuck executável está localizado no segundo setor de disco, logo após o carregador de inicialização, que é colocado, como normalmente, na seção MBR, o primeiro setor em disco. Código adicional (qualquer código acima de 510 bytes) pode ser localizado em outros setores do disco. Seu dispositivo de armazenamento deve ser um disco rígido ou um disquete.

STDIO

Obviamente, um carregador de inicialização não pode ter acesso aos recursos de E / S do sistema operacional. Portanto, as funções do BIOS são usadas para imprimir texto e ler a entrada do usuário.

Modelo

Para começar, aqui está um modelo simples escrito no assembly Nasm (sintaxe da 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 isso é bem fácil:

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

E a correr. Por exemplo, com o Qemu:

qemu-system-i386 -fda boot.raw

Informação adicional: wiki OsDev , Wikipedia

Hannes Karppila
fonte
21
Input must be redTenho certeza de que a maioria dos gerenciadores de inicialização não suporta nativamente cores.
Fund Monica's Lawsuit
4
Deve-se explicar aos desenvolvedores mais jovens o que é um disquete!
bobbel
1
@bobbel Vamos começar com o gerenciador de inicialização
Bálint
5
Não que eu ache esse título ofensivo, mas como é possível? Segundo a meta , é impossível colocar "brainfuck" no título.
DJMcMayhem
Podemos usar mais de 30 mil células?
CalculatorFeline

Respostas:

13

171 bytes 1

Wooohoooo! Demorou metade do dia, mas foi divertido ...

Então aqui está. Eu acho que está de acordo com as especificações (envolvente do ponteiro da célula, eco dos caracteres na entrada, leitura char por caractere, eco dos caracteres de entrada, ...), e parece realmente funcionar (bem, eu não tentei muitos programas , mas dada a simplicidade do idioma, acho que a cobertura não é tão ruim).

Limitações

Uma coisa importante: se o seu programa brainfuck contiver outros caracteres além das instruções do 8 brainfuck, ou se []não estiverem bem equilibrados, ele trará em você, mouhahahaha!

Além disso, o programa brainfuck não pode exceder 512 bytes (um setor). Mas isso parece estar em conformidade, pois você diz que "o executável Brainfuck está localizado no segundo setor de disco" .

Último detalhe: não iniciei explicitamente as células para zero. O Qemu parece fazer isso por mim, e estou contando com isso, mas não sei se um BIOS real em um computador real faria isso (a inicialização levaria apenas alguns bytes a mais).

O código

(com base no seu modelo e, a propósito, obrigado por isso, eu nunca teria tentado sem ele):

[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

Truques usados

Ok, eu trapacei um pouco. Como você disse que "sendo um carregador de inicialização, o tamanho do programa é contado em bytes diferentes de zero no código compilado" , reduzi o código ao permitir "buracos" entre a implementação dos oito códigos opcionais do cérebro. Dessa forma, não preciso de uma grande sequência de testes, de uma tabela de salto ou de qualquer coisa: apenas pulo para o id do opcode id (de 0 a 8), multiplicado por 32, para executar a instrução de mindfuck (vale a pena notar que isso significa que a implementação das instruções não pode demorar mais de 32 bytes).

Além disso, para obter esse "opcode id" do personagem do programa brainfuck buscado, notei que era necessário um pouco de embaralhamento. De fato, se considerarmos os bits 0, 1 e 4 do caractere opcode, terminamos com as 8 combinações ú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.

E, para minha sorte, existe realmente um código de operação que requer mais de 32 bytes para ser implementado, mas é o último (pule para a frente [). Como há mais espaço depois, está tudo bem.

Outro truque: não sei como funciona um intérprete típico do cérebro, mas, para tornar as coisas muito menores, na verdade não implementei ]como "Volte atrás do correspondente [se os dados no ponteiro forem diferentes de zero" . Em vez disso, sempre volto ao correspondente [e, a partir daqui, aplico novamente a [implementação típica (que, eventualmente, avança após o processo ]novamente, se necessário). Para isso, toda vez que encontro um [, coloco o "ponteiro de instruções de fôlego cerebral" atual na pilha antes de executar as instruções internas e, quando encontro um]Retorno o ponteiro de instruções. Praticamente como se fosse uma chamada para uma função. Portanto, teoricamente, você poderia sobrecarregar a pilha criando muitos loops imbricados, mas não com a atual limitação de 512 bytes do código do cérebro.


1. Incluindo os zero bytes que faziam parte do próprio código, mas não aqueles que faziam parte de algum preenchimento

escuro
fonte