brainfuck_interpreter.c

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

#define MEMORY_SIZE 25
#define MAX_LOOPS 5000
#define MAX_INSTRUCTIONS 10000
#define MAX_INPUT 256
#define MAX_EXECUTION_STEPS 100000

struct loopMap {
    int count;
    int loops[MAX_LOOPS][2];
};

struct loopMap scanLoop(int instructionCount, char instructions[MAX_INSTRUCTIONS]) {
    int loopStack[MAX_LOOPS] = {0};
    int loopStackPtr = 0;
    
    struct loopMap res;
    res.count = 0;
    for (int i = 0; i < instructionCount; i++) {
        //printf("%c", instructions[i]);
        if (instructions[i] == '[') {
            loopStack[loopStackPtr] = i;
            loopStackPtr++;
        }
        if (instructions[i] == ']') {
            res.loops[res.count][0] = loopStack[loopStackPtr-1];
            res.loops[res.count][1] = i;
            loopStack[loopStackPtr-1] = 0;
            loopStackPtr--;
            res.count++;
        }
    }
    return res;
}

int getTwinLoopPosition(struct loopMap *map, int position) {
    for (int i = 0; i < map->count; i++) {
        if (map->loops[i][0] == position) {
            return map->loops[i][1];
        }
        if (map->loops[i][1] == position) {
            return map->loops[i][0];
        }
    }
    return -1;
}

void dumpMemory(int mp, int memory[MEMORY_SIZE]) {
    printf("\nMemory dump:\n");

    for (int i = 0; i < MEMORY_SIZE; i++) {
        printf("%d ", memory[i]);
    }
    printf("\n");
    for (int i = 0; i < MEMORY_SIZE; i++) {
        if (i == mp) {
            printf("^");
        } else {
            char str[MAX_INPUT];
            sprintf(str, "%d", memory[i]);
            for (int j = 0; j < strlen(str)+1; j++) {
                printf(" ");
            }
        }
    }
    printf("\n");
}

int main(int argc, char** argv) {
    if (argc != 2) {
        printf("Err: invalid usage");
        return 1;
    }

    // read the file
    const char* fileName = argv[1];
    FILE *fp = fopen(fileName, "r");
    if (fp == NULL) {
        printf("Error opening the file");
        return 1;
    }

    char ch;
    char instructions[MAX_INSTRUCTIONS] = {0};

    int instructionCount = 0;
    while ((ch = fgetc(fp)) != EOF) {
        instructions[instructionCount] = ch;
        instructionCount++;
    }
    instructionCount++;
    fclose(fp);
    
    // parse loops
    int loopCount = 0;
    struct loopMap loops = scanLoop(instructionCount, instructions);

    // execute the program
    int executed = 0;
    int memory[MEMORY_SIZE] = {0};
    int mp = 0;
    int ip = 0;
    while (ip < instructionCount) {
        char ins = instructions[ip];

        if (ins == '+') memory[mp] += 1;
        if (ins == '-') memory[mp] -= 1;
        if (ins == '@') dumpMemory(mp, memory);
        if (ins == '[' && memory[mp] == 0) {
            // jump after the next matching ]
            ip = getTwinLoopPosition(&loops, ip);
        }
        if (ins == ']') {
            // jump to the matching [
            ip = getTwinLoopPosition(&loops, ip)-1;
        }
        if (ins == '>') {
            mp++;
            if (mp >= instructionCount) {
                printf("Err: memory pointer overflow");
                return 1;
            }
        }
        if (ins == '<') {
            mp--;
            if (mp < 0) {
                printf("Err: memory pointer underflow");
                return 1;
            }
        }
        if (ins == '.') {
            printf("%c", memory[mp]);
        }
        if (ins == ',') {
            // get data from stdin
            int inp = (int) getchar();
            memory[mp] = inp;
        }
        ip++;
        executed++;
        if (executed > MAX_EXECUTION_STEPS) {
            printf("Err: Max execution allowed\n");
            return 1;
        }
    }
    printf("\n");
    return 0;
}