为什么Brainfuck为汇编编译器创建的程序会崩溃？

Question

我正在为Haskell中的NASM编译器编写Brainfuck .它可以编译小程序,但不能正确地使用大程序.

考虑以下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!

它的工作原理应该如此.但是当试图编译更大的程序(在这种情况下是mandelbrot分形生成器)时会发生段错误.我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我找到了发生段错误的地方:

????????????????????[ 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存储库,请看一下.

Answer 1

您的代码生成器错误编译循环:

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: