A brainfuck interpreter written in x86_64 assembly for linux.

brainfuck.asm

; this file is licensed under the MIT license, copyright 2024 Jenna Fligor,
; see the bottom of the file for the full text.
;
; build instructions:
; nasm -felf64 brainfuck.asm
; ld brainfuck.o -o brainfuck

bits 64
global _start
extern end

SYS_read   equ 0
SYS_write  equ 1
SYS_open   equ 2
SYS_close  equ 3
SYS_fstat  equ 5
SYS_mmap   equ 9
SYS_brk    equ 12
SYS_exit   equ 60

FD_STDIN  equ 0
FD_STDOUT equ 1
FD_STDERR equ 2

fstat_sizeof_stat equ 144
fstat_size_off    equ 48

%macro error 2
    mov eax, SYS_write
    mov edi, FD_STDERR
    lea rsi, [%1]
    mov rdx, %2
    syscall
%endmacro

%macro exit 1
    mov edi, %1
    mov eax, SYS_exit
    syscall
%endmacro

section .bss
prgm_start resq 1
prgm_size resq 1
prgm_end resq 1
tape_start resq 1
tape_end resq 1

section .rodata
usage_msg      db "usage:", 10, "brainfuck program.bf", 10
usage_len      equ $ - usage_msg
fail_open_msg  db "Error: failed to open program file", 10
fail_open_len  equ $ - fail_open_msg
fail_stat_msg  db "Error: failed to stat program file", 10
fail_stat_len  equ $ - fail_stat_msg
fail_mmap_msg  db "Error: failed to mmap program file", 10
fail_mmap_len  equ $ - fail_mmap_msg
fail_close_msg db "Warn: failed to close program file", 10
fail_close_len equ $ - fail_close_msg
fail_brk_msg   db "Error: unable to expand memory tape", 10
fail_brk_len   equ $ - fail_brk_msg

mem_overflow_msg   db "Error: attempted to shift past end of memory tape", 10
mem_overflow_len   equ $ - mem_overflow_msg
mem_underflow_msg  db "Error: attempted to shift before begining of memory tape", 10
mem_underflow_len  equ $ - mem_underflow_msg
prgm_overflow_msg  db "Error: encounted right end of program tape looking for matching ']'", 10
prgm_overflow_len  equ $ - prgm_overflow_msg
prgm_underflow_msg db "Error: encounted left end of program tape looking for matching '['", 10
prgm_underflow_len equ $ - prgm_underflow_msg

section .text
grow_tape:
    mov rdi, [tape_end]
    add rdi, 0x8000
    mov [tape_end], rdi
    mov eax, SYS_brk
    syscall
    cmp rax, [tape_end]
    jne .fail
    ret

.fail:
    error fail_brk_msg, fail_brk_len
    exit 3

_start:
    ; check if argc is exactly two, if it is, jump down to .open_file,
    ; else print usage string and exit with error-code 1
    mov rax, [rsp]
    cmp rax, 2
    je .open_file
    error usage_msg, usage_len
    exit 1

.open_file:
    mov eax, SYS_open
    mov rdi, [rsp+16] ; rsp hasn't moved yet so rsp+16 == argv[1]
    xor esi, esi      ; open read-only
    xor edx, edx      ; mode ignored for ro
    syscall
    mov r15, rax      ; store program fd in r15
    test rax, rax     ; set sign flag if fd is negative
    jns .stat_file    ; continue if positive, else throw error and exit
    error fail_open_msg, fail_open_len
    exit 2
    ; NOTE: r15 is now reserved for the program fd until it's closed

.stat_file:
    mov eax, SYS_fstat
    sub rsp, fstat_sizeof_stat ; reserve sizeof(struct stat) on stack
    mov rdi, r15               ; load program fd from r15
    mov rsi, rsp               ; set reserved stack space as buffer pointer
    syscall
    cmp rax, -1                ; print error an exit on -1
    jne .stat_success          ; (syscall defined error value)
    error fail_stat_msg, fail_stat_len
    exit 2
.stat_success:
    mov rsi, qword [rsp+fstat_size_off] ; load stat.st_size from stat buffer
    mov [prgm_size], rsi                ; store stat.st_size int prgm_size
    add rsp, fstat_sizeof_stat          ; free reserved stack space
    ; NOTE: rsi implicitly falls through with the size of the file, this *is*
    ; used by the next block when calling mmap

.map_file:
    mov eax, SYS_mmap
    xor edi, edi ; NULL (don't care where file is mapped)
    mov rdx, 1   ; protections: PROT_READ
    mov r10, 2   ; flags:       MAP_PRIVATE
    mov r8, r15  ; program fd
    xor r9, r9   ; no offset
    syscall
    mov [prgm_start], rax
    cmp rax, -1
    jne .close_file
    error fail_mmap_msg, fail_mmap_len
    exit 2

.close_file:
    mov eax, SYS_close
    mov rdi, r15                         ; program fd (r15 no longer reserved)
    syscall
    cmp rax, -1
    jne .setup                           ; on failure to close print warning
    error fail_close_msg, fail_close_len ; but don't exit since it's non-fatal

.setup:
    mov rax, [prgm_start] ; compute end of program tape from prgm_start plus
    add rax, [prgm_size]  ; prgm_size and store in prgm_end
    mov [prgm_end], rax

    mov rax, SYS_brk
    xor edi, edi
    syscall
    mov [tape_start], rax
    mov [tape_end], rax
    call grow_tape

    ; the brainfuck interpreter keeps two main peices of internal state:
    ; r15 is the pointer to the program tape and
    ; r14 is the pointer to the memory tape
    mov r15, [prgm_start]
    mov r14, [tape_start]

program_loop:
    cmp r15, [prgm_end] ; reaching the end of the program tape is the
    jge success         ; successful exit condition, so we check for that on
                        ; each iteration

    mov al, byte [r15]  ; we now read a byte from the program tape, increment
    inc r15             ; the program pointer, and then branch to the handler
    cmp al, '>'         ; for each operator, if it's not one of the eight valid
    je op_right         ; operations, we simply ignore the character and loop
    cmp al, '<'         ; again
    je op_left
    cmp al, '+'
    je op_inc
    cmp al, '-'
    je op_dec
    cmp al, '.'
    je op_out
    cmp al, ','
    je op_in
    cmp al, '['
    je op_open
    cmp al, ']'
    je op_close
    jmp program_loop

op_right:
    inc r14             ; shift the memory tape one to the right, then check to
    cmp r14, [tape_end] ; ensure we haven't overrun the tape and return to the
    jl program_loop     ; program loop, else error and exit
    call grow_tape
    jmp program_loop

op_left:
    dec r14               ; shift the memory tape one to the left, then check
    cmp r14, [tape_start] ; to ensure we haven't overrun the tape and return to
    jge program_loop      ; the program loop, else error and exit
    error mem_underflow_msg, mem_underflow_len
    exit 3

op_inc:
    inc byte [r14]   ; increment the current cell in the memory tape by one,
    jmp program_loop ; overflow is considered defined behavior

op_dec:
    dec byte [r14]   ; decrement the current cell in the memory tape by one,
    jmp program_loop ; underflow is considered defined behavior

op_out:
    mov eax, SYS_write ; write one byte from the current position of the
    mov edi, FD_STDOUT ; memory tape to stdout
    mov rsi, r14
    mov edx, 1
    syscall
    jmp program_loop

op_in:
    mov rax, SYS_read ; read one byte from stdin into the current position of
    mov rdi, FD_STDIN ; the memory tape
    mov rsi, r14
    mov rdx, 1
    syscall
    jmp program_loop

op_open:
    cmp byte [r14], 0 ; assuming the current memory tape value isn't zero we
    je .ff_start      ; can just increment the brace depth and return otherwise
    inc r13           ; we move to the matching ']'
    jmp program_loop

.ff_start:
    xor eax, eax        ; rax is the brace depth accumulator
.ff:
    cmp byte [r15], '[' ; here we iterate to the right in a loop, if we
    je .ff_inc          ; encounter another '[' we increment our brace depth
    cmp byte [r15], ']' ; since we'll need to find another ']' before we exit
    je .ff_dec          ; when we reach a ']' and our brace depth is zero
.ff_continue:           ; we're done and can exit the loop
    inc r15
    cmp r15, [prgm_end] ; sanity check to make sure a malformed program doesn't
    jl .ff              ; overflow the program tape and segfault
    error prgm_overflow_msg, prgm_overflow_len
    exit 3

.ff_inc:
    inc rax ; increment brace depth
    jmp .ff_continue

.ff_dec:
    test rax, rax  ; if brace depth already zero, we're done and can exit,
    jz .ff_done    ; otherwise simply decrement the brace depth and return
    dec rax        ; to the loop
    jmp .ff_continue

.ff_done:
    inc r15          ; shift program pointer to the byte *after* the ']'
    jmp program_loop ; technically this isn't necessary since on the next loop
                     ; call the current memory cell should still be zero so the
                     ; ']' would just continue without looping, but that's too
                     ; much implicit flow control for my taste

op_close:
    cmp byte [r14], 0 ; if the current memory cell is zero we don't loop back
    je program_loop   ; so we just return to program loop

    xor eax, eax      ; rax is the brace depth accumulator
    sub r15, 2        ; subtract two from r15 to move it from one after the ']'
                      ; to one before
.rewind:
    cmp byte [r15], ']' ; similar but reverse of op_open, on ']' we increment
    je .rewind_inc      ; the brace depth while on '[' we check if the brace
    cmp byte [r15], '[' ; depth is zero and then break if it is otherwise just
    je .rewind_dec      ; decrement it
.rewind_continue:
    dec r15
    cmp r15, [prgm_start] ; sanity check to make sure a malformed program
    jge .rewind           ; doesn't underflow the program tape and segfault
    error prgm_underflow_msg, prgm_underflow_len
    exit 3

.rewind_inc:
    inc rax ; increment brace depth
    jmp .rewind_continue

.rewind_dec:
    test rax, rax   ; if brace depth is zero exit the loop otherwise just
    jz .rewind_done ; decrements the brace depth by one
    dec rax
    jmp .rewind_continue

.rewind_done:
    inc r15 ; shift program pointer to byte *after* the '['
    jmp program_loop

success:
    exit 0

; MIT License
;
; Copyright 2024 Jenna Fligor
;
; Permission is hereby granted, free of charge, to any person obtaining a copy
; of this software and associated documentation files (the “Software”), to deal
; in the Software without restriction, including without limitation the rights
; to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
; copies of the Software, and to permit persons to whom the Software is
; furnished to do so, subject to the following conditions:
;
; The above copyright notice and this permission notice shall be included in all
; copies or substantial portions of the Software.
;
; THE SOFTWARE IS PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
; IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
; FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
; AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
; LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
; OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
; SOFTWARE.