12
\$\begingroup\$

This is my bare-bones Brainfuck interpreter in C using lots of unixisms. What improvements can I make (with respect to the clarity of code, or obvious features to add)?

#include <assert.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/mman.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>

void error(char *msg) {
    fprintf(stderr, "Error: %s\n", msg);
}

enum { MEMSIZE = 30000 };

//unsigned char *mem;
unsigned char mem[MEMSIZE];
unsigned char *ptr;
unsigned char *prog;
size_t progsize;

int init(char *progname) {
    int f,r;
    struct stat fs;
    ptr = mem;// = calloc(MEMSIZE, 1);
    f = open(progname, O_RDONLY);
    assert(f != -1);
    r = fstat(f, &fs);
    assert(r == 0);
    prog = mmap(NULL, progsize = fs.st_size, PROT_READ, MAP_PRIVATE, f, 0);
    assert(prog != NULL);
    return 0;
}

/* As requested, a little more commentary on this, admittedly bizarre, function.
findmatch receives the current instruction-pointer and a bracket character 
for which the "match" is desired. It returns a new instruction-pointer.
*/
int findmatch(int ip, char src){
    char *q, *p="[]";
    int i, defer, dir[]= { 1, -1 };
    i = strchr(p,src)-p;  // at this point, if(src=='[') i=0; else if(src==']') i=1;
    ip+=dir[i];           // ie. if(src=='[') ++ip else if(src==']') --ip
                          // so dir[i] tells us which direction we're going
    // next, we reuse the same idiom to check each character as we scan.
    // defer counts up or down as we encounter [ and ] and finally reaches 0
    // when the match is found.
    for (defer=dir[i]; defer!=0; ip+=dir[i]) {
        if (ip<0||ip>=progsize) error("mismatch");   // check exceeded bounds
        if (q = strchr(p,prog[ip])) {   // if the char is a bracket
            int j = q-p;                // j is 0 or 1
            defer+=dir[j];              // adjust the 'defer' level
        }
    }
    return ip - dir[i];  // return new ip value (one past the matched bracket)
}

int run() {
    int ip;
    for(ip = 0; ip>=0 && ip<progsize; ip++)
        switch(prog[ip]){
        case '>': ++ptr; break;
        case '<': --ptr; break;
        case '+': ++*ptr; break;
        case '-': --*ptr; break;
        case '.': putchar(*ptr); break;
        case ',': *ptr=getchar(); break;
        case '[': /*while(*ptr){*/
                  if (!*ptr)
                      ip=findmatch(ip,'[')-1; // modified because run does ip++ 
                  break;
        case ']': /*}*/
                  if (*ptr)
                      ip=findmatch(ip,']')-1;
                  break;
        }

    return 0;
}

int cleanup() {
    //free(mem);
    ptr = NULL;
    return 0;
}

int main(int argc, char *argv[]) {
    init(argc > 1? argv[1]: NULL);
    run();
    cleanup();
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Ehrm.. init has some issues. It's kinda stupid to arrange to pass a NULL pointer if there's no filename, and then pass that NULL pointer to open and try to assert afterwords. I suppose readability might be improved by putting main at the top so you can just glance at it and scratch it off straightaway. It would also put it next to init which immediately follows in the calling sequence. ... On the otherhand, experienced C readers will naturally scan the whole file to find main. ... \$\endgroup\$ – luser droog Jul 29 '13 at 6:05
3
\$\begingroup\$

Braces

First of all, curses to you for omitting the braces for the loop in run(). I wasted a lot of time debugging a problem after I added some instrumentation code before the switch.

Error handling

Your assertions are inappropriate. Assertions are a way to redundantly state what the programmer knows must be true due to reasoning. They are not an error-handling mechanism. If the program is compiled with assertions disabled, then all of your "error handling" goes out the window.

A better idiom for error handling would be putting every call that might fail in an if condition, and bailing out if it fails.

int init(const char *progname) {   // const would be good
    int f, r;
    struct stat fs;
    ptr = mem;// = calloc(MEMSIZE, 1);
    if (!(f = open(progname, O_RDONLY))) {
        return -1;
    }
    if (0 != (r = fstat(f, &fs))) {
        return -1;
    }
    if (!(prog = mmap(NULL, progsize = fs.st_size, PROT_READ, MAP_PRIVATE, f, 0))) {
        return -1;
    }
    …

To follow through, you should handle the error in main():

int main(int argc, char *argv[]) {
    if (-1 == init(argc > 1 ? argv[1] : NULL)) {
        perror(NULL);
        return EXIT_FAILURE;
    }
    int err = run();
    cleanup();
    return (err == 0) ? EXIT_SUCCESS : EXIT_FAILURE;
}

Looping

Your findmatch() is not only hard to read, it's also inefficient. You can improve both issues by scanning the program just once to build a jump table.

int *jumps;

static int matchbrackets(int offset) {
    for (; offset < progsize; offset++) {
        int close;
        switch (prog[offset]) {
        case ']':
            return offset;
        case '[':
            close = matchbrackets(offset + 1);
            if (close < 0) {
                return close;   // mismatch
            }
            jumps[offset] = close;
            jumps[close] = offset;
            offset = close;
        }
    }
    return -1;
}

Add the initialization code to init() (and the corresponding deallocation in cleanup()):

if (!(jumps = malloc(progsize))) {
    return -1;
}
memset(jumps, -1, progsize);  // Mark all jumps as illegal
matchbrackets(0);             // Find legal jumps

Then the run() loop looks like:

int run() {
    for (int ip = 0; ip < progsize; ip++) {  // <-- better style
        switch (prog[ip]) {
        …
        case '[': if (!*ptr) ip = jumps[ip]; break;
        case ']': if ( *ptr) ip = jumps[ip]; break;
        }
        if (ip < 0) {
            error("mismatch");
            return -1;
        }
    }
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ That's awesome. Thank you. I can even see how to add further optimizations, like collapsing runs of + or -. \$\endgroup\$ – luser droog Apr 20 '15 at 8:11
  • \$\begingroup\$ You're right, it is bad practice in any programming language besides C to omit the braces in a for loop. The reader of the code won't be able to see where the loop ends. But, the statement "curses to you" is kinda mean, so I don't think you should use that. The OP does have a lot of bad practices in his/her program, so I applaud you for addressing that. \$\endgroup\$ – Obinna Nwakwue Mar 21 '16 at 22:50
8
\$\begingroup\$

My biggest complaint on readability would be your findmatch() function. There are too many non-descriptive variables (i.e. i, j, p, etc). Changing the names to be more descriptive, or adding some comments to elaborate on what you're trying to do would help a lot.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.