Bootloader golf: Brainf***

20

5

Create a bootloader that executes given Brainfuck program. This is , so the program with least bytes wins. Being a bootloader, the size of the program is counted in non-zero bytes in the compiled code.

Brainfuck

30000 8-bit overflowing cells. Pointer wraps over.

Some notes about operations:

  • Input must be read in a way that all printable ASCII characters are correctly supported. Other keystrokes may either insert an arbitrary character or do nothing at all.
  • Reading user input must be character buffered, not line buffered.
  • Reading user input must echo inserted character.
  • Output must follow either the code page 437 or your built-in VGA adapters default codepage.

Bootloader

This is a x86 bootloader. A bootloader ends with the traditional 55 AA sequence. Your code must run either on VirtualBox, Qemu or other well-known x86 emulator.

Disk

Executable Brainfuck is located at second disk sector, right after your bootloader, which is placed, as usually, in MBR section, the first sector on disk. Additional code (any code over 510 bytes) can be located at other disk sectors. Your storage device must be either a hard drive or a floppy disk.

STDIO

Of course, a bootloader cannot have an access to the operating system's IO capabilities. Therefore BIOS functions are used instead for printing text and reading user input.

Template

To get started, here is a simple template written in Nasm (intel syntax) assembly:

[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

Compiling this is pretty easy:

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

And the run it. For example, with Qemu:

qemu-system-i386 -fda boot.raw

Addtional information: OsDev wiki, Wikipedia

Hannes Karppila

Posted 2016-05-12T18:16:51.997

Reputation: 3 090

21Input must be red I'm pretty sure most bootloaders don't natively support color. – Fund Monica's Lawsuit – 2016-05-12T18:30:52.063

4One should explain to younger developers what a floppy disk is! – bobbel – 2016-05-12T20:53:53.353

1@bobbel Let's start with bootloader – Bálint – 2016-05-12T21:59:43.467

5

Not that I find this title offensive, but how is it possible? According to meta, it's impossible to put "brainfuck" in the title.

– James – 2016-05-13T00:32:05.797

Can we use more than 30k cells? – CalculatorFeline – 2016-11-28T17:35:21.087

Answers

13

171 bytes1

Wooohoooo! It took half the day, but it was fun...

So, here it is. I think it conforms to the specs (wraparound of cell pointer, echo of characters on input, reading char by char, echo of input chars, ...), and it seems to actually work (well, I didn't try many programs, but given the simplicity of the language, the coverage isn't that bad, I think).

Limitations

One important thing: if your brainfuck program contains other chars than the 8 brainfuck instructions, or if the [] are not well-balanced, it will crash on you, mouhahahaha!

Also, the brainfuck program can't exceed 512 bytes (a sector). But this seems conforming since you say "executable Brainfuck is located at second disk sector".

Last detail: I didn't explicitly initialized the cells to zero. Qemu seem to do it for me, and I'm relying on this, but I don't know whether a real BIOS on a real computer would do it (initialization would just take a few bytes more, anyway).

The code

(based on your template, and by the way, thanks for this, I would never have tried without it):

[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 used

Ok, I cheated a bit. Since you said "being a bootloader, the size of the program is counted in non-zero bytes in the compiled code", I made the code smaller by allowing "holes" between the implementation of the eight brainfuck opcodes. This way, I don't need a big sequence of tests, a jump table, or anything: I just jump to the brainfuck "opcode id" (from 0 to 8) multiplied by 32 to execute the brainfuck instruction (worth to note that it means the implementation of the instructions can't take more than 32 bytes).

Moreover, to get this "opcode id" from the brainfuck program character fetched, I noticed just a bit of bit shuffling was necessary. Indeed, if we just consider bits 0, 1 and 4 of the opcode character, we end up with the 8 unique combinations:

   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.

And, lucky me, there is actually one opcode that requires more than 32 bytes to implement, but it's the last one (jump forward [). As there is more room after, everything is fine.

Other trick: I don't know how a typical brainfuck interpreter works, but, to make things much smaller, I did not actually implement ] as "Jump back after the corresponding [ if data at pointer is nonzero". Instead, I always go back to the corresponding [, and, from here, re-apply the typical [ implementation (which then, eventually, goes forward after the ] again if needed). For this, each time I encouter a [, I put the current "brainfuck instruction pointer" on the stack before executing the inner instructions, and when I encounter a ], I pop back the instruction pointer. Pretty much as if it was a call to a function. You could therefore theoretically overflow the stack by making many many imbricated loops, but not with the current 512-bytes limitation of the brainfuck code, anyway.


1. Including the zero bytes that were part of the code itself, but not those that were part of some padding

dim lost faith in SE

Posted 2016-05-12T18:16:51.997

Reputation: 7 018