18
\$\begingroup\$

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 <fcntl.h> #include <libgen.h> #include <stddef.h> #include <stdio.h> #include <stdlib.h> #include <sys/stat.h> #include <unistd.h> 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 < 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 > 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, &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 < p.end) { ptrdiff_t i = ip - p.begin; switch (*ip) { case '<': if (--ptr < mem) return i + 1; break; case '>': if (++ptr >= 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 <= 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 > 0) { fprintf(stderr, "Error at offset %d\n", error_offset); } free_program(prog); }
\$\endgroup\$

3 Answers 3

Reset to default
9
\$\begingroup\$

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 <, >, -, +, ., ,, [ 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 '<': if (__builtin_expect(--ptr < mem, false)) { return i + 1; } break; case '>': if (__builtin_expect(++ptr >= 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 :)

\$\endgroup\$
5
\$\begingroup\$

Your code seems pretty good. @Morwenn's answer already covers the main things, however, I'll dare mentioning the minor nitpickings that were left out ;)

  • Your functions take a program by value. Not a performance concern in this case, I'm sure, since it consists of just 3 pointers, and it might even be good for cache locality. However, many C coding guidelines discourage taking structs by value, so this is something that might be looked down by some. I guess the one advantage I can see for always taking structs by pointer (or const pointer) is that if an initially small structure, such as your current program, gets expanded in the future, to the point where some copy overhead could be introduced, then it wouldn't be necessary to change any code.

  • You have one static function in the source file, though since no functions are exported to other source files, all but main could be static. Conversely, neither one really needs to be static, since it is a single source file program.

  • This buffer is quite large for a stack variable:

    unsigned char mem[30000] = { 0 };

    I would personally not take chances and dynamically allocate it. execute_program() is only called once, so you don't have to worry with allocation overhead or heap fragmentation. Another option would be making it static, though that introduces globally shared state...

  • One possible optimization that comes to mind would be making use of restrict on non-aliasing pointers. I think at least text/begin and jump are from different blocks, so it could apply. This is a good article about it if you are not very familiar with strict-aliasing. Though to make the most out of this compiler hint, you'd probably have to carefully check the assembly output.

\$\endgroup\$
3
\$\begingroup\$

I'm pretty sure this line

 p.jumps[i] = NULL; // In case no matching ']' is ever found

has no effect and will be removed by the optimizer. build_jump_table() only calls build_jump_table() and it doesn't read from p.jumps[] so there's no point in setting it here when it will be set by the return of the next line.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.