Brainfuck JIT compiler

bff.c

/**
 * BFF - jit compiled bf
 * @author Patrick Kage
 */

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

#define MEMORY_SIZE 30000

// JIT symbols
enum {
    S_PROGEND,
    S_MOVELEFT,
    S_MOVERIGHT,
    S_INCREMENT,
    S_DECREMENT,
    S_INPUT,
    S_OUTPUT,
    S_LOOPSTART,
    S_LOOPEND
};

/* JIT symbols are packed into a buffer initialized to the 2x the length of the input file
 * Some symbols have an input value, packed next to the symbol.
 *
 * JIT symbols:
 * 
 *  S_MOVELEFT (cells)
 *      Move left (cells) cells
 *  S_MOVERIGHT
 *      Move right (cells) cells
 *  S_INCREMENT (val)
 *      Incrememnt cell (val) times
 *  S_DECREMENT (val)
 *      Decrement cell (val) times
 *  S_INPUT
 *      Input into the cell from STDIN. dummy arg for alignment
 *  S_OUTPUT
 *      Output the cell into STDOUT. dummy arg for alignment
 *  S_LOOPSTART (index)
 *      Start a loop. Arg is corresponding S_LOOPEND
 *  S_LOOPEND (index)
 *      End a loop. Arg is corresponding S_LOOPSTART
 *  S_PROGEND
 *      End the program.
 */


/**
 * Current program state
 */
typedef struct bf_state {
    unsigned int* exec_buf;     // instruction buffer (symbols)
    unsigned int exec_size;     // instruction buffer size
    unsigned int exec_ptr;      // current instruction

    int* mem_buf;               // memory buffer
    unsigned int mem_size;      // memory size
    unsigned int mem_ptr;       // memory pointer
} bf_state;

// prototypes
bf_state init_interpreter(char* filename);
bool compile_program(char* filebuf, unsigned int filelen, unsigned int* execbuf, unsigned int execlen);
unsigned int find_loop_forward(unsigned int* execbuf, unsigned int execlen, unsigned int start);
unsigned int find_loop_backward(unsigned int* execbuf, unsigned int start);
void free_interpreter(bf_state* state);
bool tick_interpreter(bf_state* state);


/**
 * Initialize interpreter
 * @param filename
 * @return a filled bf_state struct
 */
bf_state init_interpreter(char* filename) {
    bf_state state;

    // open the file
    FILE *fp = fopen(filename, "r");
    if (!fp) {
        fprintf(stderr, "file %s does not exist!\n", filename);
        exit(1);
    }

    // get length of file
    fseek(fp, 0, SEEK_END);
    unsigned int filesize = (unsigned int)ftell(fp);
    rewind(fp);

    // copy the entire file into memory
    char* contents = (char*)malloc((size_t)state.exec_size);
    fread(contents, state.exec_size, 1, fp);
    fclose(fp);

    // init the compilation buffer (double the execution buffer size plus two)
    state.exec_size = 2 + (2 * filesize);
    state.exec_buf = (unsigned int*)calloc(sizeof(unsigned int), (size_t)state.exec_size);
    state.exec_ptr = 0;

    // compile the buffer
    if (!compile_program(contents, filesize, state.exec_buf, state.exec_size)) {
        fprintf(stderr, "file %s is malformed!\n", filename);
        exit(1);
    }

    // free the file contents
    free(contents);


    // initialize the memory
    state.mem_buf = (int*)calloc(sizeof(int), MEMORY_SIZE);
    state.mem_ptr = 0;
    state.mem_size = MEMORY_SIZE;

    return state;
}

unsigned int find_loop_forward(unsigned int* execbuf, unsigned int execlen, unsigned int start) {
    unsigned int index = start;
    int depth = 1;

    // scan through the rest of the file, looking for a matching ]
    while (depth != 0) {
        index += 2;

        if (index >= execlen) {
            fprintf(stderr, "Unmatched '[' at position %d\n!", start);
            exit(1);
        }

        if (execbuf[index] == S_LOOPSTART) {
            depth++;
        } else if (execbuf[index] == S_LOOPEND) {
            depth--;
        }
    }

    return index;
    
}

unsigned int find_loop_backward(unsigned int* execbuf, unsigned int start) {
    unsigned int index = start;
    int depth = 1;

    // scan backwards through the file, looking for a matching [
    while (depth != 0) {
        index -= 2;

        if (execbuf[index] == S_LOOPSTART) {
            depth--;
        } else if (execbuf[index] == S_LOOPEND) {
            depth++;
        }

        if (index <= 0) {
            fprintf(stderr, "Unmatched ']' at position %d\n!", start);
            exit(1);
        }
    }

    return index;
}

unsigned int find_repeats(char* filebuf, unsigned int filelen, unsigned int start) {
    unsigned int count;
    char target = filebuf[start];
    for (count = 0; target == filebuf[start + count] && start + count < filelen; count++) {}
    return count;
}

/**
 * Compile into the JIT buffer
 */
bool compile_program(char* filebuf, unsigned int filelen, unsigned int* execbuf, unsigned int execlen) {
    unsigned int write_pos = 0;
    // first pass -- convert to instructions, ignoring loop refs
    for (unsigned int idx = 0; idx < filelen; idx++) {
        switch (filebuf[idx]) {
            case '<':
                execbuf[write_pos++] = S_MOVELEFT;
                execbuf[write_pos++] = find_repeats(filebuf, filelen, idx);
                idx += execbuf[write_pos - 1] - 1;
                break;
            case '>':
                execbuf[write_pos++] = S_MOVERIGHT;
                execbuf[write_pos++] = find_repeats(filebuf, filelen, idx);
                idx += execbuf[write_pos - 1] - 1;
                break;
            case '+':
                execbuf[write_pos++] = S_INCREMENT;
                execbuf[write_pos++] = find_repeats(filebuf, filelen, idx);
                idx += execbuf[write_pos - 1] - 1;
                break;
            case '-':
                execbuf[write_pos++] = S_DECREMENT;
                execbuf[write_pos++] = find_repeats(filebuf, filelen, idx);
                idx += execbuf[write_pos - 1] - 1;
                break;
            case ',':
                execbuf[write_pos++] = S_INPUT;
                execbuf[write_pos++] = 0; // dummy
                break;
            case '.':
                execbuf[write_pos++] = S_OUTPUT;
                execbuf[write_pos++] = 0; // dummy
                break;
            case '[':
                execbuf[write_pos++] = S_LOOPSTART;
                execbuf[write_pos++] = 0; // temporary
                break;
            case ']':
                execbuf[write_pos++] = S_LOOPEND;
                execbuf[write_pos++] = 0; // ignored
                break;
            default:
                break;
        }
    }

    // second pass -- resolve loop references
    for (unsigned int idx = 0; idx < execlen; idx += 2) {
        switch (execbuf[idx]) {
            case S_LOOPSTART:
                execbuf[idx + 1] = find_loop_forward(execbuf, execlen, idx);
                break;
            case S_LOOPEND:
                execbuf[idx + 1] = find_loop_backward(execbuf, idx);
                break;
            default:
                break;
        }
    }


    return true;
}

/**
 * Free the interpreter
 * @param state bf state
 */
void free_interpreter(bf_state* state) {
    free(state->exec_buf);
    free(state->mem_buf);
}


/**
 * tick the interpreter
 * @param state program state
 * @return false if done
 */
bool tick_interpreter(bf_state* state) {
    unsigned int cmd = state->exec_buf[state->exec_ptr];
    unsigned int arg = state->exec_buf[state->exec_ptr + 1];

    switch (cmd) {
        case S_MOVELEFT:
            state->mem_ptr -= arg;
            //printf("executing moveleft x%d", arg);
            break;
        case S_MOVERIGHT:
            state->mem_ptr += arg;
            //printf("executing moveright x%d", arg);
            break;
        case S_INCREMENT:
            state->mem_buf[state->mem_ptr] += arg;
            //printf("executing increment +%d", arg);
            break;
        case S_DECREMENT:
            state->mem_buf[state->mem_ptr] -= arg;
            //printf("executing decrement -%d", arg);
            break;
        case S_OUTPUT:
            //printf("executing output");
            putchar(state->mem_buf[state->mem_ptr]);
            break;
        case S_INPUT:
            //printf("executing input");
            state->mem_buf[state->mem_ptr] = getchar();
            fflush(stdout);
            break;
        case S_LOOPSTART:
            //printf("executing loop start, no jump");
            if (state->mem_buf[state->mem_ptr] != 0) break;
            //printf("\rexecuting loop start, jump to %d", arg);
            state->exec_ptr = arg;
            break;
        case S_LOOPEND:
            //printf("executing loop end, no jump");
            if (state->mem_buf[state->mem_ptr] == 0) break;
            //printf("\rexecuting loop end, jump to %d", arg);
            state->exec_ptr = arg;
            break;
        case S_PROGEND:
        default:
            return false;
    }
    //printf("\n");

    state->exec_ptr += 2;
    return true;
}

#ifdef DEBUG
void show_instruction(unsigned int cmd, unsigned int arg) {
        switch (cmd) {
            case S_MOVELEFT:
                printf("LEFT %d", arg);
                break;
            case S_MOVERIGHT:
                printf("RIGHT %d", arg);
                break;
            case S_INCREMENT:
                printf("INC %d", arg);
                break;
            case S_DECREMENT:
                printf("DEC %d", arg);
                break;
            case S_INPUT:
                printf("INPUT");
                break;
            case S_OUTPUT:
                printf("OUTPUT");
                break;
            case S_LOOPSTART:
                printf("LOOPSTART %d", arg / 2);
                break;
            case S_LOOPEND:
                printf("LOOPEND %d", arg / 2);
                break;
            case S_PROGEND:
                printf("PROGRAM END");
                break;
            default:
                printf("UNKNOWN");
                break;
        }
}
void show_program(bf_state *state) {
    unsigned int cmd, arg, read = 0;

    do {
        cmd = state->exec_buf[read];
        arg = state->exec_buf[read + 1];
        printf("%03d: ", read / 2);
        show_instruction(cmd, arg);
        printf("\n");
        read += 2;
    } while (cmd != S_PROGEND);
}
void show_memory(bf_state *state) {
    printf("[");
    for (int c = 0; c < 10; c++) {
        printf("%d", state->mem_buf[c]);
        if (c + 1 < 10) printf(" ");
    }
    printf("][%d]\t%04d -> ", state->mem_ptr, state->exec_ptr);

    unsigned int cmd = state->exec_buf[state->exec_ptr];
    unsigned int arg = state->exec_buf[state->exec_ptr + 1];
    show_instruction(cmd, arg);
    printf("\n");
}
#include <unistd.h>
#endif

// here we go!
int main(int argc, char** argv) {
	// get the filename
	if (argc != 2) {
		fprintf(stderr, "usage: %s filename\n", argv[0]);
		return 1;
	}

	// initialize bf interpreter with the file
	bf_state state = init_interpreter(argv[1]);

#ifdef DEBUG
    show_program(&state);
    usleep(1000000);
#endif


	while (tick_interpreter(&state)) {
#ifdef DEBUG
        show_memory(&state);
        usleep(1000);
#endif
    }

	free_interpreter(&state);
}