为什么 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 fractal generator），会发生段错误。我 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 行代码文件不是一个好主意，考虑到 post 已经太长了。

我已经把源码上传到a GitHub repository，请看一下

Answer 1

没有任何进展 - 说明是相同的。特别是，jne 和 jnz 只是同一指令的别名。（并且 byte ptr 只是额外的冗长，因为在这种情况下可以仅从寄存器操作数的大小推断出什么）

NASM 正确组装它，pwndbg 正确反汇编它，...并且您的编译器某处潜伏着一些错误。 :)

Answer 2

您的代码生成器miscompiles loops:

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:

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

Why does a program created by a Brainfuck into assembly compiler crash?

assembly

x86

segmentation-fault

brainfuck