I decided to try and write a [Brainfuck][1] 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 implmentation in Brainfuck][2]:
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);
}
[1]: https://en.wikipedia.org/wiki/Brainfuck
[2]: http://www.hevanet.com/cristofd/brainfuck/rot13.b