Verbose Brainfuck Interpreter in C

Question

I decided to try and write a Brainfuck interpreter in C as an exercise. This could have been written in one file, but I decided to split it up into a State "class" and an some interpreter methods.

An example test-run with a ROT13 implementation in Brainfuck:

const char* source_buffer = // Code in above link. Read from file in my test.
interpret_with_std_io(source_buffer);

// In the console

Hello World!
Uryyb Jbeyq!

I'd like suggestions on anything, but specifically:

• I'm fairly new to C. I'd like to know if I'm still making any newbie mistakes.

• A few parts of my interpreter/state separation feel clumsy. 99% of the state code requires no knowledge of the source code. [ unfortunately has the potential to jump forwards, so unless I pre-compute all the possible jumps, I need access to the source so I can search for its matching ]. I originally had the two hande_loop_ functions in the state code, then moved it to the interpreter, then back to the state. As a consequences though, my interpreter function dispatch_command now requires access to the source, solely for [.

• I needed a variable-sized stack to store the jump points, and decided on a linked list. It seems perfect here. Am I handling it OK?

• The mismatched-brace handling logic is frustrating. The handle_loop_ functions return false when they detect a mismatched brace. I need to manually feed this result all the way back to the main interpret_with_state function, just so I know whether an error happened. Exceptions would be perfect here, but obviously they aren't an option. Is there a better way of handling this?

It's broken up into 3 files: helpers.c (for safe allocation helpers), state.c and interpreter.c.

---

---

Helpers

#ifndef HELPERS_H
#define HELPERS_H

#include <stdlib.h>

// Prints an error message to stderr if ptr is NULL
// Message is in the form "Could not allocate space for %s.".
void ensure_allocation(const void* ptr, const char* allocation_reason);

// Attempts to allocate the requested amount of memory and asserts the validity of the
//  returned pointer using ensure_allocation before returning
void* terminating_malloc(size_t bytes, const char* allocation_reason);

#endif

---

#include <stdio.h>

#include "helpers.h"

void ensure_allocation(const void* ptr, const char* allocation_reason) {
    if (!ptr) {
        fprintf(stderr, "Could not allocate space for %s.", allocation_reason);
        exit(EXIT_FAILURE);
    }
}

void* terminating_malloc(size_t bytes, const char* allocation_reason) {
    void* const ptr = malloc(bytes);

    ensure_allocation(ptr, allocation_reason);

    return ptr;
}

---

---

State

#ifndef STATE_H
#define STATE_H

#include <stdlib.h>
#include <stdbool.h>

#define STANDARD_CELL_BUFFER_LENGTH 30000

typedef unsigned char Cell_Type;

typedef struct Jump_Node {
    size_t jump_position;
    struct Jump_Node* next;

} Jump_Node;

typedef struct {
    size_t instruction_pointer;
    size_t cell_pointer;

    Cell_Type* cell_buffer;
    size_t buffer_length;

    Jump_Node* jump_nodes_head;

} State;

void init_state(State*, size_t buffer_length);

// Initializes it with a buffer with the length of STANDARD_CELL_BUFFER_LENGTH
void init_standard_state(State*);


void advance_instruction_pointer(State*);


void increment_current_cell(State*); // +
void decrement_current_cell(State*); // -


// bool returns indicate whether or not the new cell pointer is "inbounds"
bool move_cell_pointer_left(State*); // <
bool move_cell_pointer_right(State*); // >

Cell_Type get_current_cell(State*); // .
void set_current_cell(State*, Cell_Type new_cell_contents); // ,


// Return false and have no effect if a matching brace isn't found, and it was required for operation
// Return true otherwise
bool handle_loop_start(State*, const char* source); // [
bool handle_loop_end(State*); // ]



// Frees the cell_buffer and the jump nodes; not the State pointer
void free_state(const State*);

#endif

---

#include <stdlib.h>
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

#include "helpers.h"
#include "state.h"

// ----- Jump Nodes -----

static void init_jump_node(Jump_Node* node, size_t position, Jump_Node* next_node) {
    node->jump_position = position;
    node->next = next_node;
}

static void free_jump_nodes(const Jump_Node* head) {
    const Jump_Node* current = head;

    while (current) {
        Jump_Node* next = current->next;
        free((Jump_Node*)current);

        current = next;
    }
}

// ----- State -----

void init_state(State* state, size_t buffer_length) {
    size_t const buffer_size = sizeof(Cell_Type) * buffer_length;
    Cell_Type* const cell_buffer = terminating_malloc(buffer_size, "cell buffer");
    memset(cell_buffer, 0, buffer_size);

    state->instruction_pointer = 0;
    state->cell_pointer = 0;

    state->cell_buffer = cell_buffer;
    state->buffer_length = buffer_length;

    state->jump_nodes_head = NULL;
}

void init_standard_state(State* state) {
    init_state(state, STANDARD_CELL_BUFFER_LENGTH);
}

void advance_instruction_pointer(State* state) {
    state->instruction_pointer++;
}

static void add_to_current_cell(State* state, Cell_Type n_to_add) {
    size_t const cell_ptr = state->cell_pointer;

    state->cell_buffer[cell_ptr] += n_to_add;
}

void increment_current_cell(State* state) {
    add_to_current_cell(state, 1);
}

void decrement_current_cell(State* state) {
    add_to_current_cell(state, -1);
}

static bool move_cell_pointer_by(State* state, int move_by) {
    state->cell_pointer += move_by;

    size_t const c_ptr = state->cell_pointer;
    return c_ptr > 0 && c_ptr < state->buffer_length;
}

bool move_cell_pointer_left(State* state) {
    return move_cell_pointer_by(state, -1);
}

bool move_cell_pointer_right(State* state) {
    return move_cell_pointer_by(state, 1);
}

Cell_Type get_current_cell(State* state) {
    const size_t cell_ptr = state->cell_pointer;

    return state->cell_buffer[cell_ptr];
}

static bool current_cell_is_zero(State* state) {
    return get_current_cell(state) == 0;
}

void set_current_cell(State* state, Cell_Type new_cell_contents) {
    const size_t cell_ptr = state->cell_pointer;

    state->cell_buffer[cell_ptr] = new_cell_contents;
}

// Returns the index in the source of the brace matching the opening brace at the given position.
// Returns -1 if a matching brace isn't found.
static int matching_brace_position(size_t opening_brace_position, const char* source) {
    int depth = 1;

    for (int i = opening_brace_position + 1; ; i++) {
        const char command = source[i];

        if (command == '\0') {
            return -1;

        } else if (command == '[') {
            depth += 1;

        } else if (command == ']') {
            depth -= 1;

            if (depth == 0) {
                return i;
            }
        }
    }
}

bool handle_loop_start(State* state, const char* source) {
    if (current_cell_is_zero(state)) { // Skip the loop
        const int pos = matching_brace_position(state->instruction_pointer, source);

        if (pos == -1) {
            return false;

        } else {
            state->instruction_pointer = pos;
        }

    } else { // Set a jump back point
        Jump_Node* const node = terminating_malloc(sizeof(Jump_Node), "jump node");
        init_jump_node(node, state->instruction_pointer, state->jump_nodes_head);

        state->jump_nodes_head = node;
    }

    return true;
}

bool handle_loop_end(State* state) {
    const Jump_Node* const popped_jump = state->jump_nodes_head;

    if (popped_jump) {
        if (current_cell_is_zero(state)) {
            state->jump_nodes_head = popped_jump->next;
            free((Jump_Node*)popped_jump);

        } else {
            size_t const recorded_position = popped_jump->jump_position;
            state->instruction_pointer = recorded_position;
        }

        return true;

    } else {
        return false;
    }
}

void free_state(const State* state) {
    free(state->cell_buffer);
    free_jump_nodes(state->jump_nodes_head);
}

static void dbg_set_cell(State* state, size_t cell_ptr, Cell_Type contents) {
    state->cell_buffer[cell_ptr] = contents;
}

---

---

Interpreter

#ifndef INTERPRETER_H
#define INTERPRETER_H

#include <stdio.h>

// Interpret the supplied code either using the standard io streams, or the supplied ones.
void interpret(const char* code, FILE* in_stream, FILE* out_stream);
void interpret_with_std_io(const char* code);

#endif

---

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

#include "state.h"
#include "interpreter.h"
#include "helpers.h"

// Returns a wrapped cell_pointer in the range 0 <= cell_pointer < buffer_size
// Requires that cell_pointer isn't more than buffer_size out of bounds.
static size_t wrap_cell_pointer(int signed_cell_pointer, size_t buffer_size) {
    int const scp = signed_cell_pointer;

    if (scp < 0) {
        return buffer_size + scp;

    } else if (scp >= (int)buffer_size) {
        return scp - buffer_size;

    } else {
        return scp;
    }
}

static void wrap_state_cell_pointer(State* state) {
    state->cell_pointer = wrap_cell_pointer(state->cell_pointer, state->buffer_length);
}

// Gets input from the supplied stream
// Returns a falsey null character if the input was out of range
// RELIES ON UCHAR_MAX!!! If Cell_Type is altered from an unsigned char,
//  this must be changed accordingly!
static Cell_Type read_input_from_stream(FILE* in_stream) {
    int const input = getc(in_stream);

    return (input > UCHAR_MAX || input < 0) ? '\0' : input;
}

// This must also be changed if Cell_Type is changed!
static void print_to_stream(FILE* out_stream, Cell_Type output) {
    fprintf(out_stream, "%c", output);
    fflush(out_stream);
}

static bool dispatch_command(State* state, char command, const char* source, FILE* in_stream, FILE* out_stream) {
    switch (command) {
        case '+':
            increment_current_cell(state);
            break;

        case '-':
            decrement_current_cell(state);
            break;

        case '<':
            move_cell_pointer_left(state);
            wrap_state_cell_pointer(state);
            break;

        case '>':
            move_cell_pointer_right(state);
            wrap_state_cell_pointer(state);
            break;

        case '[': {
            const bool matching = handle_loop_start(state, source);

            if (!matching) {
                puts("Unmatched [ found.\n");
                return false;
            }

            break;
        }

        case ']': {
            bool const matching = handle_loop_end(state);

            if (!matching) {
                puts("Unmatched ] found.\n");
                return false;
            }

            break;
        } 

        case ',': {
            Cell_Type const input = read_input_from_stream(in_stream);
            if (input) {
                set_current_cell(state, input);
            }

            break;
        }

        case '.': {
            Cell_Type const output = get_current_cell(state);
            print_to_stream(out_stream, output);

            break;
        }
    }

    return true;
}

static void interpret_with_state(State* state, const char* source, FILE* in_stream, FILE* out_stream) {
    while (true) {
        char const command = source[state->instruction_pointer];

        if (command == '\0') {
            break;

        } else {
            bool const evald_ok = dispatch_command(state, command, source, in_stream, out_stream);

            if (!evald_ok) {
                return;
            }

            advance_instruction_pointer(state);
        }
    }
}

void interpret(const char* code, FILE* in_stream, FILE* out_stream) {
    State state;
    init_standard_state(&state);

    interpret_with_state(&state, code, in_stream, out_stream);

    free_state(&state);
}

void interpret_with_std_io(const char* code) {
    interpret(code, stdin, stdout);
}

Answer 1

• matching_brace_position does not return -1 as advertised (if the matching brace is not found). If the matching brace is indeed not found, it returns nothing (in fact, it would access source out of bound). This is UB.

• handle_loop_end assumes a well-formed BF program. With an ill-formed one (having a stray ]) it would try to free something which wasn't previously allocated.

  As a side note, the cast (Jump_Node*)popped_jump is not necessary, and could even be harmful.

  As another side note, the final else is not necessary. Just return false.

• As the interpreter runs, the list of jump nodes is created and destroyed over and over again. I strongly recommend to create it once (rejecting the ill-formed programs in the process). BF is notoriously easy to compile after all.

  BTW, compiling (into a byte code at least) is an answer to your last bullet. If you insist on strictly interpreting, consider setjmp/longjmp.