Почему происходит сбой программы, созданной Brainfuck при сборке компилятора?

Я пишу компилятор Brainfuck для NASM в Haskell. Он может компилировать небольшие программы, но не может делать это правильно с большими.

Рассмотрим следующий код Brainfuck:

++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.>---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++.

У меня это представлено как:

BfSource [Add 8,LoopL 0,GoRight 1,Add 4,LoopL 1,GoRight 1,Add 2,GoRight 1,Add 3,GoRight 1,Add 3,GoRight 1,Add 1,GoLeft 4,Sub 1,LoopR 1,GoRight 1,Add 1,GoRight 1,Add 1,GoRight 1,Sub 1,GoRight 2,Add 1,LoopL 2,GoLeft 1,LoopR 2,GoLeft 1,Sub 1,LoopR 0,GoRight 2,WriteChar,GoRight 1,Sub 3,WriteChar,Add 7,WriteChar,WriteChar,Add 3,WriteChar,GoRight 2,WriteChar,GoLeft 1,Sub 1,WriteChar,GoLeft 1,WriteChar,Add 3,WriteChar,Sub 6,WriteChar,Sub 8,WriteChar,GoRight 2,Add 1,WriteChar,GoRight 1,Add 2,WriteChar]

Который переводится в следующую сборку:

section .bss
    memory resb 30000
section .text
    global _start
_printChar:
    mov rdx, 1
    mov rbx, 1
    mov rax, 4
    int 80h
    ret
_start:
    mov rcx, memory
    mov al, [rcx]
    add al, 8
    mov [rcx], al
_L0:
    inc rcx
    mov al, [rcx]
    add al, 4
    mov [rcx], al
_L1:
    inc rcx
    mov al, [rcx]
    add al, 2
    mov [rcx], al
    inc rcx
    mov al, [rcx]
    add al, 3
    mov [rcx], al
    inc rcx
    mov al, [rcx]
    add al, 3
    mov [rcx], al
    inc rcx
    mov al, [rcx]
    inc al
    mov [rcx], al
    sub rcx, 4
    mov al, [rcx]
    dec al
    mov [rcx], al
    mov al, [rcx]
    test al, al
    jnz _L1
    inc rcx
    mov al, [rcx]
    inc al
    mov [rcx], al
    inc rcx
    mov al, [rcx]
    inc al
    mov [rcx], al
    inc rcx
    mov al, [rcx]
    dec al
    mov [rcx], al
    add rcx, 2
    mov al, [rcx]
    inc al
    mov [rcx], al
_L2:
    dec rcx
    mov al, [rcx]
    test al, al
    jnz _L2
    dec rcx
    mov al, [rcx]
    dec al
    mov [rcx], al
    mov al, [rcx]
    test al, al
    jnz _L0
    add rcx, 2
    call _printChar
    inc rcx
    mov al, [rcx]
    sub al, 3
    mov [rcx], al
    call _printChar
    mov al, [rcx]
    add al, 7
    mov [rcx], al
    call _printChar
    call _printChar
    mov al, [rcx]
    add al, 3
    mov [rcx], al
    call _printChar
    add rcx, 2
    call _printChar
    dec rcx
    mov al, [rcx]
    dec al
    mov [rcx], al
    call _printChar
    dec rcx
    call _printChar
    mov al, [rcx]
    add al, 3
    mov [rcx], al
    call _printChar
    mov al, [rcx]
    sub al, 6
    mov [rcx], al
    call _printChar
    mov al, [rcx]
    sub al, 8
    mov [rcx], al
    call _printChar
    add rcx, 2
    mov al, [rcx]
    inc al
    mov [rcx], al
    call _printChar
    inc rcx
    mov al, [rcx]
    add al, 2
    mov [rcx], al
    call _printChar
    mov rax, 1
    xor rbx, rbx
    int 80h

И вот как это ведет себя:

$ runghc Main.hs hello.bf
$ nasm -f elf64 hello.nasm
$ ld -m elf_x86_64 hello.o -o hello
$ ./hello
Hello World!

Работает как надо. Но при попытке скомпилировать большую программу (в данном случае это фрактальный генератор Мандельброта) возникает ошибка. Я на 100% уверен, что этот код работает, потому что я проверил его в онлайн-интерпретаторе Brainfuck.

$ runghc Main.hs mandelbrot.bf
$ nasm -f elf64 mandelbrot.nasm
$ ld -m elf_x86_64 mandelbrot.o -o mandelbrot
$ ./mandelbrot
Segmentation fault

С помощью pwndbg Я нашел место, где происходит segfault:

────────────────────[ REGISTERS ]────────────────────
 RAX  0x1
 RBX  0x0
 RCX  0x404fff ◂— add    byte ptr [rax], al
 // ... All other registers are 0x0
 RSP  0x7fffffffe0f0 ◂— 0x1
 RIP  0x4014b6 (_L43+33) ◂— mov    byte ptr [rcx], al
──────────────────────[ DISASM ]─────────────────────
 ► 0x4014b6 <_L43+33>    mov    byte ptr [rcx], al
   0x4014b8 <_L43+35>    add    rcx, 8
   0x4014bc <_L43+39>    mov    al, byte ptr [rcx]
   0x4014be <_L43+41>    test   al, al
   0x4014c0 <_L43+43>    jne    _L33 <0x4013a6>

   0x4014c6 <_L43+49>    sub    rcx, 9
   0x4014ca <_L44>       inc    rcx
   0x4014cd <_L44+3>     xor    al, al
   0x4014cf <_L44+5>     mov    byte ptr [rcx], al
   0x4014d1 <_L44+7>     dec    rcx
   0x4014d4 <_L44+10>    mov    al, byte ptr [rcx]

я Ctrl+Fсделал бы это _L33 в текстовом редакторе и что я нашел похожий, но другой код (все метки, сгенерированные моим компилятором, уникальны, поэтому он должен быть в одном месте).

    mov [rcx], al
    add rcx, 8
    mov al, [rcx]
    test al, al
    jnz _L33
    sub rcx, 9
_L44:
    inc rcx
    xor al, al
    mov [rcx], al
    dec rcx
    mov al, [rcx]

и так, что здесь происходит? NASM генерирует иную сборку, чем в исходном файле? Или, может быть pwndbg разобрали это неправильно? Я бы сказал, что что-то не так с моим компилятором, но я не знаю что.

РЕДАКТИРОВАТЬ: Я думаю, вырезать и вставить две ~100 строк файлов кода не очень хорошая идея, учитывая, что этот пост уже слишком длинный.

Я загрузил исходный код в репозиторий GitHub, пожалуйста, посмотрите на него.

Источник

2 ответа

Решение

Ваш генератор кода неправильно компилирует циклы:

bf2asm handle (LoopL x) =
    hPutStrLn handle $ "_L" ++ show x ++ ":"
bf2asm handle (LoopR x) =
    mapM_ (hPutStrLn handle)
        [ "    mov al, [rcx]"
        , "    test al, al"
        , "    jnz _L" ++ show x
        ]

Как вы можете видеть, он помещает тест текущего байта в конец цикла, создавая эквивалент цикла do-while:

do {  // [
    ...
} while (*ecx);  // ]

Но семантика [] В Brainfuck, что тест цикла выполняется в первую очередь, как это:

while (*ecx) {  // [
    ...
}  // ]

Вы должны изменить свой компилятор так, чтобы он выглядел так:

_LS42:
    mov al, [rcx]
    test al, al
    jz _LE42
...
    jmp _LS42
_LE42:
Источник

Ничего не происходит - инструкции идентичны. Особенно, jne а также jnz просто псевдонимы для той же инструкции. (А также byte ptr это просто дополнительное многословие для того, что в этом случае может быть выведено только из размера операнда регистра)

NASM собрал его правильно, pwndbg правильно его разобрал, ... и ваш компилятор где-то скрывается.:)

Источник
Другие вопросы по тегам