Brainfuck interpreter (with emphasis on robustness) While writing a review of @MotokoKusanagi's Brainfuck interpreter, I decided to write my own implementation to illustrate a few points.  In particular, I'd like it to be robust to malformed programs, and reasonably efficient (short of JITting the Brainfuck code).

Please point out any deficiencies you might find in this implementation.

#include &lt;fcntl.h&gt;
#include &lt;libgen.h&gt;
#include &lt;stddef.h&gt;
#include &lt;stdio.h&gt;
#include &lt;stdlib.h&gt;
#include &lt;sys/stat.h&gt;
#include &lt;unistd.h&gt;

typedef struct {
    char *begin,            // Pointer to beginning of program
         *end,              // Pointer just beyond the end of the program
         **jumps;           // Pointer to jump table
} program;

/**
 * Fills in p.jumps, the jump table.  For each '[' or ']' character
 * in the code, the pointer at the corresponding offset in p.jumps
 * is set to the matching ']' or '[' (or NULL if it is mismatched).
 * This function calls itself recursively to handle nesting.
 */
static char *build_jump_table(program p, char *begin) {
    char *c = begin;
    while (c &lt; p.end) {
        ptrdiff_t i = c - p.begin;
        switch (*c) {
          case '[':
            p.jumps[i] = NULL;      // In case no matching ']' is ever found
            p.jumps[i] = c = build_jump_table(p, c + 1);
            if (!c) return NULL;    // Error: no closing bracket
            break;
          case ']':
            p.jumps[i] = (begin &gt; p.begin) ?
                begin - 1 :         // Normal case
                NULL;               // Error: no opening bracket
            return c;
        }
        c++;
    }
    return NULL;
}

/**
 * Loads the program from the specified path.  On failure, all members of
 * the returned program will be NULL, and errno is set.
 */
program load_program(const char *path) {
    const program FAILURE = { .begin = NULL, .end = NULL, .jumps = NULL };
    int fd;
    struct stat stat_buf;
    if ( -1 == (fd = open(path, O_RDONLY)) ||
         -1 == fstat(fd, &amp;stat_buf) ) {
        return FAILURE;
    }
    int size = stat_buf.st_size;
    char *text = malloc(size);
    if ( (text == NULL) || (size != read(fd, text, size)) ) {
        free(text);
        close(fd);
        return FAILURE;
    }
    close(fd);
    program p = { .begin = text, .end = text + size, .jumps = malloc(size) };
    if (p.jumps == NULL) {
        free(text);
        return FAILURE;
    }
    build_jump_table(p, p.begin);
    return p;
}

void free_program(program p) {
    free(p.jumps);
    free(p.begin);
}

int execute_program(program p) {
    unsigned char mem[30000] = { 0 };
    unsigned char *ptr = mem;
    char *ip = p.begin;
    while (ip &lt; p.end) {
        ptrdiff_t i = ip - p.begin;
        switch (*ip) {
            case '&lt;': if (--ptr &lt; mem) return i + 1;                    break;
            case '&gt;': if (++ptr &gt;= mem + sizeof mem) return i + 1;      break;
            case '-': (*ptr)--;                                         break;
            case '+': (*ptr)++;                                         break;
            case '.': putchar(*ptr); fflush(stdout);                    break;
            case ',': *ptr = getchar();                                 break;
            case '[': if (!*ptr) ip = p.jumps[i];                       break;
            case ']': if ( *ptr) ip = p.jumps[i];                       break;
        }
        if (!ip++) {
            return i + 1;
        }
    }
    return 0;
}

void usage(FILE *f, char *argv[]) {
    fprintf(f, "Usage: %s PROGRAM.bf\n", basename(argv[0]));
}

int main(int argc, char *argv[]) {
    if (argc &lt;= 1) {
        usage(stderr, argv);
        return 1;
    }
    program prog = load_program(argv[1]);
    if (!prog.begin) {
        perror("Error: Could not load program");
        return 2;
    }
    int error_offset = execute_program(prog);
    if (error_offset &gt; 0) {
        fprintf(stderr, "Error at offset %d\n", error_offset);
    }
    free_program(prog);
}
Deficiencies? I don't really see any. Improvements? Maybe :)


You don't handle at all the return values of putchar, getchar and fflush. The Wikipedia article has some hints about how different implementations handle an EOF from the user input. Yours works as well, but is this really what you want?
In build_jump_table, the switch used to check whether *c is a [ or a ] seems a bit overkill. It would probably be easier to get away with a simple if .. else statement.
That's highly speculative, but I guess that if you replace the characters &lt;, &gt;, -, +, ., ,, [ and ] by values ranging from 0 to 7, or at least by contiguous values during the program load, it might help your compiler to generate a better jump table for your switch, which might help increasing the speed of the programs.

The assumption here is that your care more about the speed during the execution and that a little slowdown during the program load isn't a problem if it can otherwise improve performance.
I guess that you want your programs to be fast while they run and that a small slowdown when it terminates isn't one of your concerns if you can otherwise speed your program up. Therefore, if your compiler supports it (I guess it does), you could use __builtin_expect to influence branch prediction while the program runs:

switch (*ip) {
    case '&lt;':
        if (__builtin_expect(--ptr &lt; mem, false)) {
            return i + 1;
        }
        break;
    case '&gt;':
        if (__builtin_expect(++ptr &gt;= mem + sizeof mem, false)) {
            return i + 1;
        }
        break;
    // ...
}


It would however be a bad idea to influence branch prediction for the conditions in the cases of [ and ]. The results are too prone to change to risk a pessimization.


I would have some other small remarks but I will keep them for myself since they would be considered a matter of style and you know what you're doing anyway :)