BrainFuck Interpreter in C

brainfuck.c

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

/**
 * BrainFuck Interpreter in C [1-2]
 * Wang Yihang <wangyihanger@gmail.com>
 * 
 * == Run
 * gcc -o bf bf.c
 * ./bf ./test.bf
 * 
 * == References
 * [1]: https://github.com/brain-lang/brainfuck/blob/master/brainfuck.md
 * [2]: https://www.wikiwand.com/en/Brainfuck
 */

#define u32 unsigned int
#define byte unsigned char
#define GREEN "\x1B[32m"
#define RESET "\x1B[0m"

struct BrainFuck {
    // Memory Tape
    u32 head;
    u32 max_memory_size;
    byte* memory;
    // Program
    u32 pc;
    u32 max_program_size;
    byte* program;
    // Stack
    u32 max_stack_size;
    // Jump Table
    u32* jump_table;
    // Output
    u32 oc;
    u32 max_output_size;
    byte* output;
};

struct BrainFuck* create(u32 max_memory_size, u32 max_program_size, u32 max_stack_size, u32 max_output_size) {
    struct BrainFuck* bf = (struct BrainFuck*) malloc(sizeof(struct BrainFuck));
    // Init Memory
    bf->head = 0;
    bf->max_memory_size = max_memory_size;
    bf->memory = (byte*) malloc(bf->max_memory_size + 1);
    // Init Program
    bf->pc = 0;
    bf->max_program_size = max_program_size;
    bf->program = (byte*) malloc(bf->max_program_size + 1);
    // Init Stack Size
    bf->max_stack_size = max_stack_size;
    // Init Jump Table
    bf->max_program_size = max_program_size;
    bf->jump_table = (u32*) malloc((sizeof(u32)) * (bf->max_program_size + 1));
    // Init output buffer
    bf->oc = 0;
    bf->max_output_size = max_output_size;
    bf->output = (byte*) malloc(bf->max_output_size + 1);
    return bf;
}

int checkIsValidProgramCounter(struct BrainFuck* bf) {
    return 0 <= bf->pc < bf->max_program_size;
}

int checkIsValidMemoryAddress(struct BrainFuck* bf) {
    return 0 <= bf->head < bf->max_memory_size;
}

int load(struct BrainFuck* bf, char* program) {
    u32 pc = 0;
    u32 sp = 0;
    u32* stack = (u32*) malloc(sizeof(u32) * bf->max_stack_size);
    // Clean Memory/Program/Jump Table
    memset(bf->memory, 0, bf->max_memory_size + 1);
    memset(bf->program, 0, bf->max_program_size + 1);
    memset(bf->jump_table, 0, (sizeof(u32)) * (bf->max_program_size + 1));
    memset(bf->output, 0, bf->max_output_size + 1);
    // Load Program
    while (program[pc] != 0 && pc < bf->max_program_size) {
        bf->program[pc] = program[pc];
        if (program[pc] == '[') {
            if (sp < bf->max_stack_size) { stack[sp++] = pc; }
            else { return -1; }
        }
        if (program[pc] == ']') {
            if (sp > 0) { 
                u32 jump_to = stack[--sp];
                bf->jump_table[jump_to] = pc;
                bf->jump_table[pc] = jump_to;
            }
            else { return -1; }
        }
        pc++;
    }
    free(stack);
    return sp == 0;
}

int debug(struct BrainFuck* bf, u32 steps, u32 delay_ms) {
    printf("============ %d steps ============\n", steps);
    printf("Program:\n");
    for (u32 i = 0; i < bf->max_program_size; i++) {
        if (i == bf->pc) {
            printf("%s%c%s", GREEN, bf->program[i], RESET);
        } else {
            printf("%c", bf->program[i]);
        }
    }
    printf("\n");

    printf("Memory:\n");
    for (u32 i = 0; i < bf->max_memory_size; i++) {
        if (i == bf->head) {
            printf("%s%02x%s", GREEN, bf->memory[i], RESET);
        } else {
            printf("%02x", bf->memory[i]);
        }
    }
    printf("\n");

    printf("Output:\n");
    for (u32 i = 0; i < bf->max_output_size; i++) {
        if (i == bf->oc) {
            printf("%s%c%s", GREEN, bf->output[i], RESET);
        } else {
            printf("%c", bf->output[i]);
        }
    }
    printf("\n");
    usleep(delay_ms * 1000);
}

int execute(struct BrainFuck* bf) {
    u32 steps = 0;
    u32 delay_ms = 0x10;
    while (1) {
        debug(bf, ++steps, delay_ms);
        if (!checkIsValidProgramCounter(bf)) { return -1; };
        if (!checkIsValidMemoryAddress(bf)) { return -1; };
        byte instruction = bf->program[bf->pc];
        if (!instruction) { break; }
        switch(instruction) {
            case '+': bf->memory[bf->head]++; break;
            case '-': bf->memory[bf->head]--; break;
            case '>': bf->head++; break;
            case '<': bf->head--; break;
            case '.': bf->output[bf->oc++] = bf->memory[bf->head]; putchar(bf->memory[bf->head]); break;
            case ',': bf->memory[bf->head] = getchar(); break;
            case '[':
                if (bf->memory[bf->head] == 0) {
                    bf->pc = bf->jump_table[bf->pc];
                }
                break;
            case ']':
                if (bf->memory[bf->head] != 0) {
                    bf->pc = bf->jump_table[bf->pc];
                }
                break;
            default:
                break;
        }
        bf->pc++;
    }
    return 0;
}

int destroy(struct BrainFuck* bf) {
    free(bf->memory);
    free(bf->program);
    free(bf->jump_table);
    free(bf->output);
    free(bf);
}

int main(int argc, char* argv[]) {
    u32 max_memory_size = 0x80;
    u32 max_program_size = 0x400;
    u32 max_stack_size = 0x40;
    u32 max_output_size = 0x80;
    
    // Read brainfuck code
    FILE* fp = fopen(argv[1], "r");
    byte* code = (byte*) malloc(sizeof(byte) * (max_program_size + 1));
    fread(code, sizeof(byte), max_program_size, fp);
    fclose(fp);

    // Create execution context
    struct BrainFuck* bf = create(max_memory_size, max_program_size, max_stack_size, max_output_size);
    if (!load(bf, code)) { exit(-1); }
    if (!execute(bf)) { exit(-1); }
    destroy(bf);
}

test.bf

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