2

I made a Brainfuck interpreter in assembly (AT&T syntax, GCC). It works on most stuff. All the desired actions work (+ - > <). I made sure to take care of nested loops as well (pushing the address on the stack and after exiting the loop popping it off). And I used syscalls for writing and reading.

Using this code:

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

It prints Hello World! without an issue, notice how it pretty much has everything you need: Nested loops, all the commands you can do (except ,). And it still works perfectly fine.

However when using this code (The expected output is also Hello World! just like the first code):

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

It prints "n| 1f14 {g" (without any seg fault or illegal instruction). I'm scratching my head on why this code doesn't work while the other one works perfectly fine. I thought I took care of every possible instruction and some exceptions which have to be hard coded (nested loops). Is there some other caveat I should keep in mind when writing a Brainfuck interpreter? Nested loops seemed like the only caveat and those work perfectly fine. I've tried debugging but it didn't help me either.

This is my code:

.global main

format_str: .asciz "--<-<<+[+[<+>--->->->-<<<]>]<<--.<++++++.<<-..<<.<+.>>.>>.<<<.+++.>>.>>-.<<<+."

main:
    pushq %rbp
    movq %rsp, %rbp

    movq $format_str, %rdi
    call brainfuck

    movq $0, %rdi
    popq %rbp
    call exit
    
brainfuck:
    pushq %rbp
    movq %rsp, %rbp
    pushq %rbx
    movq $1, %r15       # use as loop counter
    
    movq %rdi, %rbx     # move the pointer to the first char in the string to %rbx
    movq $100000, %rdi  # allocate 100000 bytes in the heap
    call malloc         # call the actual malloc function
    movq %rax, %r12     # move the data pointer to the allocated bytes to r12
    addq $50000, %r12   # add 50000 to the location so we start in the middle. So when starting you can also go to "negative" cells
    sub $1, %rbx

.back:
    add $1, %rbx        # iterate one char over the string we have
.findVal:
    movzbl (%rbx),%eax  # move (%rbx) into %eax, only accesses memory once, speeding up the tests.
    cmp  $0,(%rbx)      # test for end of string
    je   .end
    cmp  $'+', %al      # test for plus
    je   .plus
    cmp  $'-', %al      # test for minus
    je   .minus
    cmp  $'>', %al      # test for right
    je   .right
    cmp  $'<', %al      # test for left
    je   .left
    cmp  $'[', %al      # test for opening bracket
    je   .openloop 
    cmp  $']', %al      # test for closing bracket
    je   .closeloop
    cmp  $'.', %al      # test for dot
    je   .dprint
    cmp  $',', %al      # test for comma
    je   .cinput
    jmp  .back          # if none match then it is an unsupported command, so iterate once over the string and jump back
    
    
.plus:
    add $1,(%r12)       # add 1 to the cell the data pointer (r12) is pointing at
    jmp .back
    
.minus:
    sub $1,(%r12)       # subtract 1 of the cell the data pointer (r12) is pointing at
    jmp .back
    
.right:
    add $1,%r12         # add 1 to the memory location of the data pointers, (hence moving up 1 cell)
    jmp .back
    
.left:
    sub $1,%r12         # subtract 1 to the memory location of the data pointers, (hence moving down 1 cell)
    jmp .back
    
.openloop:
    cmpb $0,(%r12)      # if the current cell we are pointing at is 0, jump to closing bracket
    je .jumpclose
    pushq %rbx          # save the opening bracket location on the stack (to deal with nested loops)
    jmp .back
    
.closeloop:
    cmpb $0,(%r12)      # if the current cell we are pointing at is 0, exit the loop
    je .endloop
    movq (%rsp), %rbx   # if it's not 0, move the top of the stack to the rbx, so we start back at the last pushed opening bracket
    jmp .back    
.endloop:
    addq $8,%rsp        # if it is the end of a loop (the cell at (%r12) is 0), then we add 8 to the stack pointer, so that the next jumping position (if there is one) is at (%r12)
    jmp .back

.inc_r15:    
    add $1, %r15        # increase nested loop counter
.jumpclose:             # finds the corresponding closing bracket
    add $1, %rbx        # go to next char
    movzbl (%rbx),%eax  # move rbx to eax so we access memory less often
    cmp  $']', %al      # check for closing loop
    je .closeloopfound
    cmp  $'[', %al      # check for opening loop
    je .inc_r15         # if there is another nested loop increase the loop counter
    jmp .jumpclose      # if none of those then simply jump back to iterate to the next char
.closeloopfound:
    sub  $1, %r15       # when encountering a closing loop, subtract 1 from the loop counter
    cmpq $0, %r15       # r15 is intiated with 1 since when we enter a loop we also have 1 opening bracket, if its equal to 0 after the last subtraction that means we found the correct bracket
    jne  .jumpclose     # if it's not 0, then jump back to jumpclose to continue finding the correct bracket
    mov  $1, %r15       # move 1 back into r15 to take care of the next time we have to skip a loop
    jmp  .back          # jump back
    
    
.dprint:
    movq    $1, %rax                     # perform syscall 1 which is sys_write
    movq    $1, %rdi                     # write to stdout
    movq    %r12, %rsi                   # use the char that %r12 is pointing to, which is stored as ascii
    movq    $1, %rdx                     # write 1 byte (amount of byte)
    syscall                              # perform the system_write (print) with syscall

    jmp .back
    
.cinput:
    movq    $0, %rax                     # sys_read call number 
    movq    $1, %rdi                     # read from stdin
    movq    %r12, %rsi                   # print the ascii value of whatever %r12 is pointing to
    movq    $1, %rdx                     # write 1 char
    syscall                              # perform the system_read with syscall
    
    jmp .back
    
.end:                                    # exiting the function 
    popq %rbx                            # restore %rbx
    popq %rbp                            # restore %rbp
    ret                                  # return to the proper return adress

I added some comments for clarity. I am just completely lost where the code goes wrong, I am using an online compiler which never failed me before. So I don't think that's the issue.

EDIT: After some more searching I found out a "caveat" I missed. I am not checking for 0 when entering a loop, I am merely checking for 0 when exiting a loop, like a true dumb ass. I've updated my code and added this functionality, luckily some programs do work now (Like Sierpinski from Daniel Cristofani). But some programs still fail sadly (the program above still fails). Now I really have no idea what to do anymore.

Improve this question
13
  • What is the expected output for the second example? Commented Dec 8, 2019 at 15:54
  • Oh sorry I forgot to add that, it is another Hello World! program, should print exactly the same as the first one. It's just a shorter variant. I'll edit the post Commented Dec 8, 2019 at 16:19
  • Unrelated: You could optimize by putting .back: just above the dispatch code. Special-case the first iteration by jumping over it or doing dec %rbx to cancel out the add, instead of having an extra jmp on every iteration. IDK what your bug might be; you did try single-stepping this in a debugger, right? Look for something that goes wrong earlier than the final result. Commented Dec 8, 2019 at 16:36
  • 1
    Brainfuck interpreter written in C on codereview might give some ideas. Your use of the stack to handle nested loops is probably a good idea. Commented Dec 8, 2019 at 16:38
  • 1
    subq $1,(%r12) is an 8-byte sub; your cells are 1 byte so you're allowing carry-out to propagate between cells. That's a bug, IDK if it's the cause of the problem you're asking about. Also related Brainfreeze: A Brainfuck compiler in C on CodeReview talks some about x86 asm sequences that implement BF "instructions". JITing vs. dispatch with a chain of branches isn't a big difference as far as what the blocks need to be. (And BTW, for performance you might want to dispatch via a jmp *table(%rax) after a movzx load.) Commented Dec 8, 2019 at 16:44

1 Answer 1

Reset to default
1

I have fixed the error after hours of searching. In the plus and minus section I was doing 

add $1, (%r12)

The error was that I should have done:

addb $1, (%r12)

Which makes sense if I think about it, however I didnt expect the whole code to not function because of something like this. And ontop of that some codes did function, like mandelbrot (one of the most complex codes). I looked at the wrong place the whole time.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

That makes no sense. addb is 8-bit operand size and isn't compatible with a 64-bit register like RBX. This won't even assemble and is not the problem; add $1, %rbx or inc %rbx is correct for incrementing a pointer.
Did you maybe mean add $1,(%r12) needed to be addb, like I commented on the question when you were still using addq? Apparently that defaults to dword operand size (assemble + disassemble with objdump -d or GDB to see). I thought GAS used to detect that as an error with ambiguous operand-size but the current version unfortunately accepts the ambiguity!
Yes whoops, I meant the code that was in the plus and minus section like I said in the post. Accidentally remembered wrong which registers I used for what. I guess I was just really happy I finally solved it after like 5+ hours of debugging this whole code. Oh and thanks for the help!
It's not a matter of how much you're adding, it's a matter of how big the operand is, and thus where carry-propagation stops. (And also how flags get set, i.e. which bit is the MSB for setting SF, and whether all bits of the result are zero -> set ZF). With RAX=0x000...1001, subb $2, %al` leaves AL=0xFF, the rest of RAX unchanged. subq $2, %rax leaves RAX=0x00...0FFF` (and doesn't set CF because borrow only propagates up to that higher set bit, not out the top of the 8-byte register). Same goes for memory. BTW, writing a 32-bit register zero-extends to the full 64-bit reg, unlike 8/16
Also, addb $1, (last_byte_of_page) won't fault, but addq $1, (last_byte_of_page) will cross into the next page (loading/storing 7 bytes there), and will segfault if that next page is unmapped. That might help to understand memory operand-size.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.