Bootloader golf: Brainf ***

20

Buat bootloader yang mengeksekusi program Brainfuck yang diberikan. Ini adalah , sehingga program dengan byte paling sedikit menang. Menjadi bootloader, ukuran program dihitung dalam byte bukan nol dalam kode yang dikompilasi.

Brainfuck

30000 sel meluap 8-bit. Pointer membungkus.

Beberapa catatan tentang operasi:

  • Input harus dibaca dengan cara semua karakter ASCII yang dapat dicetak didukung dengan benar. Penekanan tombol lainnya dapat menyisipkan karakter sewenang-wenang atau tidak melakukan apa pun.
  • Input yang dibaca pengguna harus buffer karakter, bukan buffer garis.
  • Membaca input pengguna harus menggemakan karakter yang dimasukkan
  • Output harus mengikuti halaman kode 437 atau codepage default adapter VGA bawaan Anda.

Bootloader

Ini adalah bootloader x86. Bootloader diakhiri dengan 55 AAurutan tradisional . Kode Anda harus dijalankan di VirtualBox, Qemu atau emulator x86 terkenal lainnya.

Disk

Executable Brainfuck terletak di sektor disk kedua, tepat setelah bootloader Anda, yang ditempatkan, seperti biasanya, di bagian MBR, sektor pertama pada disk. Kode tambahan (kode apa saja lebih dari 510 byte) dapat ditemukan di sektor disk lain. Perangkat penyimpanan Anda harus berupa hard drive atau floppy disk.

STDIO

Tentu saja, bootloader tidak dapat memiliki akses ke kemampuan IO sistem operasi. Oleh karena itu fungsi BIOS digunakan untuk mencetak teks dan membaca input pengguna.

Templat

Untuk memulai, berikut adalah templat sederhana yang ditulis dalam susunan Nasm (intel sintaks):

[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

Kompilasi ini cukup mudah:

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

Dan jalankan itu. Misalnya, dengan Qemu:

qemu-system-i386 -fda boot.raw

Informasi tambahan: wiki OsDev , Wikipedia

Hannes Karppila
sumber
21
Input must be redSaya cukup yakin sebagian besar bootloader tidak mendukung warna.
Dana Gugatan Monica
4
Orang harus menjelaskan kepada pengembang yang lebih muda apa floppy disk itu!
bobbel
1
@ Bobob Mari kita mulai dengan bootloader
Bálint
5
Bukannya saya menganggap judul ini ofensif, tetapi bagaimana mungkin? Menurut meta , tidak mungkin untuk memasukkan "brainfuck" dalam judul.
DJMcMayhem
Bisakah kita menggunakan lebih dari 30rb sel?
CalculatorFeline

Jawaban:

13

171 byte 1

Wooohoooo! Butuh setengah hari, tapi itu menyenangkan ...

Jadi begini. Saya pikir itu sesuai dengan spesifikasi (sampul pointer sel, gema karakter pada input, membaca char oleh char, gema input chars, ...), dan tampaknya benar-benar berfungsi (well, saya tidak mencoba banyak program , tapi mengingat kesederhanaan bahasanya, cakupannya tidak terlalu buruk, saya pikir).

Keterbatasan

Satu hal penting: jika program brainfuck Anda berisi karakter selain 8 instruksi brainfuck, atau jika []tidak seimbang, itu akan menimpa Anda, mouhahahaha!

Selain itu, program brainfuck tidak dapat melebihi 512 byte (satu sektor). Tapi ini sepertinya sesuai karena Anda mengatakan "executable Brainfuck terletak di sektor disk kedua" .

Detail terakhir: Saya tidak secara eksplisit menginisialisasi sel menjadi nol. Qemu tampaknya melakukannya untuk saya, dan saya mengandalkan ini, tetapi saya tidak tahu apakah BIOS yang sebenarnya pada komputer yang sebenarnya akan melakukannya (inisialisasi hanya akan mengambil beberapa byte lebih banyak).

Kode

(berdasarkan pada templat Anda, dan omong-omong, terima kasih untuk ini, saya tidak akan pernah mencoba tanpanya):

[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

Trik digunakan

Ok, saya sedikit curang. Karena Anda mengatakan "menjadi bootloader, ukuran program dihitung dalam byte yang bukan nol dalam kode yang dikompilasi" , saya membuat kode lebih kecil dengan memungkinkan "lubang" antara penerapan delapan opcode brainfuck. Dengan cara ini, saya tidak perlu urutan besar tes, tabel lompatan, atau apa pun: Saya hanya melompat ke "opcode id" brainfuck (dari 0 hingga 8) dikalikan dengan 32 untuk menjalankan instruksi brainfuck (perlu dicatat bahwa itu berarti implementasi instruksi tidak boleh lebih dari 32 byte).

Selain itu, untuk mendapatkan "id opcode" ini dari karakter program brainfuck yang diambil, saya perhatikan hanya sedikit pengocokan yang diperlukan. Memang, jika kita hanya mempertimbangkan bit 0, 1 dan 4 karakter opcode, kita berakhir dengan 8 kombinasi unik:

   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.

Dan, beruntung saya, sebenarnya ada satu opcode yang membutuhkan lebih dari 32 byte untuk diimplementasikan, tetapi ini adalah yang terakhir (melompat ke depan [). Karena ada lebih banyak ruang setelah, semuanya baik-baik saja.

Trik lain: Saya tidak tahu cara kerja juru bahasa khas Brainfuck, tetapi, untuk membuat segalanya jauh lebih kecil, saya tidak benar-benar menerapkan ]sebagai "Langsung kembali setelah sesuai [jika data pada pointer bukan nol" . Sebaliknya, saya selalu kembali ke yang sesuai [, dan, dari sini, menerapkan kembali [implementasi khas (yang kemudian, pada akhirnya, maju ke depan ]lagi jika diperlukan). Untuk ini, setiap kali saya encouter a [, saya meletakkan "pointer instruksi brainfuck" saat ini di tumpukan sebelum menjalankan instruksi dalam, dan ketika saya menemukan], Saya mengembalikan pointer instruksi. Sepertinya itu adalah panggilan ke suatu fungsi. Oleh karena itu, Anda secara teoritis dapat meluap tumpukan dengan membuat banyak loop imbricated, tetapi tidak dengan batasan 512-byte saat ini dari kode brainfuck.


1. Termasuk byte nol yang merupakan bagian dari kode itu sendiri, tetapi bukan byte yang merupakan bagian dari beberapa padding

redup
sumber