5
\$\begingroup\$

I have written a small Brainfuck interpreter in C. More recent version hosted here.

I have found it very hard to test my interpreter because writing a program in Brainfuck is somewhat hard (or at least very tedious) and many snippets I found online either don't give output or do so very cryptically, so I don't know 100% sure if everything works as intended.

I have tested a few programs on it though, and that which I tested works.

Any criticism/advice would be very nice.

#include <stdio.h>

#define MEMSIZE 30000

int memory[MEMSIZE];
int instructions[MEMSIZE];

int memptr = 0;
int insptr = 0;

int isInstruction(char);
void runInstruction(char);

int main(int argc, char *argv[]) {
    // Open input file
    FILE *file = fopen(argv[1], "r");
    if (file == 0){
        printf("Error: Could not open source file\n");
        return 0;
    }

    // Read all instructions from input
    char c;
    int i = 0;
    int balance = 0; // Keeps track of `[` and `]` balance
    while ((c = fgetc(file)) != EOF && i < MEMSIZE){
        if(isInstruction(c)){
            instructions[i] = c;
            i++;
            if (c == '[')
                balance++;
            if (c == ']')
                balance--;
        }
    }

    // Close input file
    fclose(file);

    // Error if amount of instructions is more than permitted
    if (c != EOF && i >= MEMSIZE){
        printf("Error: cannot read more than 30000 instructions\n");
        return 0;
    }

    // Error if `[` and `]` aren't balanced
    if (balance != 0){
        printf("Error: `[` and `]` were not balanced\n");
        return 0;
    }

    // Run the program
    while(insptr < MEMSIZE && instructions[insptr] != 0){
        runInstruction(instructions[insptr]);
        insptr++;
    }
}

int isInstruction(char c) {
    if(c == '+' || c == '-' || c == '>' || c == '<' || c == '[' || c == ']' ||
       c == '.' || c == ','){
        return 1;
    } else {
        return 0;
    }
}

void runInstruction(char c) {
    switch(c){
    case '+':
        memory[memptr]++;
        break;
    case '-':
        memory[memptr]--;
        break;
    case '>':
        if (memptr < MEMSIZE - 1)
            memptr++;
        else
            memptr = 0;
        break;
    case '<':
        if (memptr > 0)
            memptr--;
        else
            memptr = MEMSIZE - 1;
        break;
    case '[':
        if (memory[memptr] == 0)
            // seek `]` forward
            while(instructions[insptr] != ']'){
                insptr++;
            }
        break;
    case ']':
        if (memory[memptr] != 0)
            // seek `[` backward
            while(instructions[insptr] != '['){
                insptr--;
            }
        break;
    case '.':
        putchar(memory[memptr]);
        break;
    case ',':
        memory[memptr] = getchar();
        break;
    default:
        printf("Error: Encountered unknown instruction `%c`\n",c);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ Side question: "...it very hard to test my interpreter because writing a program in Brainfuck is somewhat hard...so I don't know 100% sure if everything works as intended". Hmmmm why you write an interpreter for a language before you master the language itself? \$\endgroup\$ – Adriano Repetti Jul 11 '16 at 9:42
  • \$\begingroup\$ @AdrianoRepetti: I don't think that's necessary if you run a few (automated) test cases through your interpreter. I'm sure you can find a few known-good Brainfuck programs and either 1) their expected output or 2) a known-good Brainfuck interpreter to generate the expected output. \$\endgroup\$ – David Foerster Jul 11 '16 at 11:00
  • 1
    \$\begingroup\$ Please do not edit your question in a way that invalidates answers. I suggest that you wait a little while longer to see if you get more answers, then you can post a follow-up question if you want another review. \$\endgroup\$ – Simon Forsberg Jul 11 '16 at 11:46
  • 1
    \$\begingroup\$ By the way, have you tested your program on FizzBuzz ? \$\endgroup\$ – Simon Forsberg Jul 11 '16 at 11:47
  • 1
    \$\begingroup\$ @SimonForsberg I tested it on FizzBuzz just now, and I'm relieved to say that it works (on a version in which I fixed some of the bugs that were pointed out in the answers) \$\endgroup\$ – Wysaard Jul 11 '16 at 12:10
9
\$\begingroup\$

Use NULL for null pointers

NULL conveys your intention to use a pointer better than 0:

if (file == NULL) { ... }

As a bonus, in C the macro NULL typically expands to something like (void*)0; if you have warnings for potentially unsafe type conversions enabled (-Wconversion for GCC), the compiler will notify you, if you try to assign 0 to a pointer or NULL to an integer, which helps to find potential errors.

Use puts when you don't use string formatting

printf("Error: Could not open source file\n");

could just as well be

puts("Error: Could not open source file");

While printf is great for formatted output, the look for formatting specifiers carries a computational overhead that puts doesn't have. Some compilers (like GCC) will perform that optimization automatically for you, if you use a format string literal without format specifiers.

Checking whether a characters is in a set of characters

In isInstruction(char), instead of using a series of disjoint (joint with the || operator) equality comparisons, you could much better express your intent and the source character set with strchr:

return strchr("+-><[].,", c) != NULL;

A possible improvements might be:

const static char brainfuck_alphabet[] = {'+', '-', '>', '<', '[', ']', '.', ','};
return memchr(brainfuck_alphabet, c, sizeof(brainfuck_alphabet));

The improvements lies in the fact that the algorithm of memchr can make an assumption about the size of the memory region to check while strchr cannot. This could lead to a performance improvement.

Use bool for boolean values

The header <stdbool.h> declares boolean-like types. You can use them to express your intention for a boolean return value of isInstruction():

bool isInstruction(char c) { ... }

Don't repeat yourself

While you generally did will to adhere to that principle, I want to point out one small spot that could use improvement:

printf("Error: cannot read more than 30000 instructions\n");

could be

printf("Error: cannot read more than %d instructions\n", MEMSIZE);

That way the error message would reflect the actual buffer size in case MEMSIZE was redefined. Since the argument list of printf is variadic and doesn't carry type information, it would be better yet to not make assumptions on the width of the integer type of MEMSIZE. What if someone defined MEMSIZE to be larger than MAX_INT? The best course of action would be to force MEMSIZE into the type size_t (more about that later).

printf("Error: cannot read more than %zu instructions\n", (size_t)(MEMSIZE));

Data types

  1. You only ever store chars in instructions, so its type could just as well be:

    char instructions[…];
    

    On all 32- and 64-bit platforms you just saved 3*MEMSIZE bytes (which you could use to increase MEMSIZE again if that is a concern).

  2. memptr, insptr and i are indexes of plain arrays. Therefore they should have type size_t, which is the type meant to reflect the size or position of things in memory.

Make the code flow of branches based on mutually exclusive conditions mutually exclusive

In the above code the conditions c == '[' and c == ']' cannot both be true since c isn't altered between them. To make this obvious to the reader and the compiler (though a good one should find that optimization itself), you should use mutually exclusive if … else if … statements:

        if (c == '[')
            balance++;
        else if (c == ']')
            balance--;

Exit with an error status in case of an error

Programs may convey information in their exit status. By convention the status 0 means “no error, everything performed according to your instructions”. Every other status value usually refers to an error condition but there is no general convention on what each value means. One attempt to conventionalize them can be found in the sysexits.h header. You could use it like this in your program:

if (file == NULL) {
    // ...
    return EX_NOINPUT;
}

if (balance < 0) {
    // ...
    return EX_DATAERR;
}

if (c != EOF && i >= MEMSIZE) {
    // ...
    return EX_SOFTWARE;
}

In a similar fashion you could return an error from runInstruction(), but we already know that we didn't accept any illegal instructions.

Print error messages on stderr

printf and puts write their data to stdout, the standard output stream, but you're also writing program output to stdout via putchar. To avoid mixing program output and error messages, you should write the latter to stderr instead:

fprintf(stderr, ...);
fputs(..., stderr);

Be aware that fputs doesn't append a new-line character like puts.

Print operating system error messages to provide hints to the user

Like many library functions relying on system calls, fopen sets the global errno variable to report the type of error. You can use functions like strerror or perror to decode the value of errno into a human-readable, localized(!) error message:

if (file == NULL) {
    perror("Could not open source file");
    // ...
}

Respect the principle of locality, avoid global variables

Global variables clutter the name space and make it more difficult to follow the flow of the program. They also prevent a method or set of methods from being reentrant, a property that allows them to be executed concurrently. (This matters not just for multi-threaded programs, but also if you wanted to, say, interpret multiple Brainfuck programs one instructions at a time in a round-robin fashion to see which program terminates first.)

One way to achieve this is to move more data and logic into the method:

int main(int argc, char *argv[])
{
    // ...
    char instructions[MEMSIZE];
    // ...
    runInstructions(instructions, i);

    return EX_OK;
}

void runInstructions(const char *const instructions, size_t instruction_count)
{
    size_t memptr = 0;
    size_t insptr = 0;
    int memory[MEMSIZE];

    while (insptr < instruction_count) {
        switch(instructions[insptr]) {
            // ...
        }
    }
}

You could also use an instruction pointer instead of an instruction index:

void runInstructions(const char *const instructions, size_t instruction_count)
{
    size_t memptr = 0;
    const char *insptr = instructions;
    const char *const instructions_end = instructions + instruction_count;
    int memory[MEMSIZE];

    while (insptr < instructions_end) {
        switch(*insptr) {
        // ...
        case '[':
            if (memory[memptr] == 0)
                // seek `]` forward
                while (*insptr != ']')
                    insptr++;
            break;

        case ']':
            if (memory[memptr] != 0)
                    // seek `[` backward
                    while(*insptr != '[')
                        insptr--;
            break;
        // ...
        }
    }
}

Use library functions where possible

Library functions unburden you from writing your own code. They're (usually) less likely to contain errors than hand-rolled solutions and the library authors may have included arcane, platform-specific performance optimizations in them.

  1. To find the next closing bracket instruction you could write:

        case '[':
            if (memory[memptr] == 0) {
                // seek `]` forward
                insptr = memchr(insptr + 1, ']', (size_t)(instructions_end - insptr - 1));
            }
            break;
    
  2. To find the last opening bracket you could write:

        case ']':
            if (memory[memptr] != 0) {
                // seek `[` backward
                insptr = memrchr(instructions, '[', (size_t)(insptr - instructions - 1));
            }
            break;
    

Avoid undefined behaviour

  1. You can't be sure that argv[1] is defined. If it isn't its value may have NULL or garbage content. Check the value of argc first and print an appropriate error message if it's too small:

    if (argc < 2) {
        fputs("Error: No source file specified.\n", stderr);
        return EX_USAGE;
    }
    
  2. If the Brainfuck program happens to have a branch depth greater than INT_MAX, the balance variable would overflow. It typically overflows to the value -1, which would be caught with a subsequent balance < 0 check, but in C signed integer overflow results in undefined behaviour. That means the compiler may assume that overflow never happens and optimize the negative balance check to always be false, which would leave your program in a weird state.

    If you decide to care about that (INT_MAX+1 is 2^31 which would require a program of at least 2 GiB, all [, to trigger the bug on modern architectures after all), there are basically two approaches:

    • Use ssize_t instead of int. ssize_t covers a branching depth of almost (half) as many levels as the address space has bytes. It's quasi-impossible to generate and load a program of that size into the memory of your interpreter anyway, so you could consider your bases covered.

    • Check for overflow before increasing balance:

          if (c == '[') {
              if (balance == INT_MAX) {
                  fprintf(stderr, "Error: Cannot handle branches deeper than %d levels.\n", INT_MAX);
                  return EX_DATAERR;
              }
              balance++;
          }
      

Provide some debugging info to the programmer using your interpreter

It might be helpful for the user to know where in the program a parser error occurred, so you should keep track of the amount of bytes read so far:

size_t i = 0;
while (i < MEMSIZE && (c = fgetc(file)) != EOF) {
    read++;
    if(isInstruction(c)) { ... }
}

You can now report that value in parser error messages like so:

fprintf(stderr, "Error:%zu: Cannot handle branches deeper than %d levels.\n", read, INT_MAX);
fprintf(stderr, "Error:%zu: Encountered `]` before matching `[`\n", read);
fprintf(stderr, "Error:%zu: cannot read more than %zu instructions\n", (size_t)(MEMSIZE), read + 1);
\$\endgroup\$
  • \$\begingroup\$ Why read from file at all, if You could just mmap()? \$\endgroup\$ – Kamiccolo Jul 11 '16 at 10:17
  • 1
    \$\begingroup\$ @Kamiccolo: Because mmap is very platform-dependant, requires more programming effort and only works on regular files? Otherwise I agree that it's a possible improvement, but specialized I/O types don't seem to be the point of this exercise. \$\endgroup\$ – David Foerster Jul 11 '16 at 10:53
  • \$\begingroup\$ Thank you very much, I'm now going to try and fix everything in Zeta's post, then this one. I have one question though. The pointers are basically just indexes of the arrays. Wouldn't 0 be more adequate to show that? In some sense they aren't 'really' pointers \$\endgroup\$ – Wysaard Jul 11 '16 at 11:27
  • 2
    \$\begingroup\$ @Darklightus: I think David means the single NULL comparison with FILE*. \$\endgroup\$ – Zeta Jul 11 '16 at 11:30
  • \$\begingroup\$ @Zeta oops, of course \$\endgroup\$ – Wysaard Jul 11 '16 at 11:43
8
\$\begingroup\$

Bugs

Your program doesn't work with nested loops. If you have

+   jump into the loop
[   this is the first loop
  [ this is the second loop                                 (1)
  - decrease current value to get out of loop
  ]
  + we increment our current value to get back to the start
]   whoops, we go to (1)

You need to remember the position of the encountered [. A stack will come in handy.

Also, the balance is calculated incorrectly. The program ][ gets parsed, since balance == 0, but it shouldn't.

Write errors to stderr

Use fprintf(stderr,…) instead of printf if you want to print an error.

Show exclusive branches with else

If two if are exclusive to each other, make sure to use else if:

if (c == '[')
    balance++;
else if (c == ']')
    balance--;


// add the balance check, see bugs above
if (balance < 0){
    ...
}

Avoid global variables if possible for testing

Next, whenever possible avoid global variables. This will help you to test your function. For example, if you group your Brainfuck data in a struct, you'll be able to check whether it parses code correctly:

typedef struct brainfuck_data {
    int * memory;
    int * instructions;
    size_t memsize;

    int memptr;
    int insptr;
} bf_data_t;

int brainfuck_data_init(bf_data_t * data, size_t memsize) {
    data.memory = calloc(memsize, sizeof(int));
    if(!data.memory) {
        return -1;
    }
    data.instructions = calloc(memsize, sizeof(int));
    if(!data.instructions) {
        free(data.memory);
        return -2;
    }
    data.memsize = memsize;
    data.memptr  = 0;
    data.insptr  = 0;
}

// and so on for brainfuck_data_deinit

Now, if you have brainfuck_data_file(bf_data_t * data, FILE * fp) or brainfuck_data_parse(bf_data_t *, const char*), you can check whether your parser ignores non-brainfuck tokens correctly:

brainfuck_data_parse(&bf1, "[,.]");
brainfuck_data_parse(&bf2, "a simple echo program: [,.]");

int instructionsDiffer = 0;
for(i = 0; i < bf1.memsize && i < bf2.memsize && …; ++i){
   if(bf1.instructions[i] != bf2.instructions[i]) {
     instructionsDiffer = 1;
     break;
   }
   if(bf1.instructions[i] == 0)
     break;
}

Non-global state makes testing your programs a lot easier.

Note that the magic numbers -1 and -2 in the code above should be documented somewhere and replaced by a define, e.g.

#define BF_E_ALLOC_MEMORY -1
#define BF_E_ALLOC_INSTR  -2
#define BF_E_OK            0

Split functionality

At the moment, parsing is done in your main. Split it into its own function. An inspiration was given above.

Parse into a small set of values

Currently, all of your instructions are kept as characters. Instead, you could use an enum:

typedef enum {
   BF_INC,        BF_DEC,
   BF_GET,        BF_PUT
   BF_NEXT,       BF_PREV
   BF_LOOP_START, BF_LOOP_END       
} brainfuck_instruction_t;

That way, if you use

typedef struct brainfuck_data {
    brainfuck_instruction_t * instructions;
    ...
} bf_data_t;

you already know that there will be only valid instructions, unless someone tampered with them beforehand. The nice side-effect is that you can parse almost all Brainfuck-like languages into the same set of instructions and still run them. See this Q&A for an inspiration.

Conclusion

Test your program with non-trivial loops, split its functionality into small functions which are easier to test, make your code less error prone by using enums and less global variables.

For a program that uses loops, try calculating the nth Fibonacci number (for small n, though, since addition in BF takes ages).

\$\endgroup\$
  • \$\begingroup\$ The program ][ results in an error as expected because the parser first encounters the closing bracket, decreases the balance counter from its initial value 0 and discovers that the balance is now negative, all before even considering the second bracket. \$\endgroup\$ – David Foerster Jul 11 '16 at 11:05
  • \$\begingroup\$ @DavidFoerster: It doesn't. Not in the current version of the code. Unless you see another loop where the code gets parsed into the instruction, there's only while ((c = fgetc(file)) != EOF && i < MEMSIZE), and that does not check for negative balance. \$\endgroup\$ – Zeta Jul 11 '16 at 11:14
  • \$\begingroup\$ Thank you very much for the review, I'm now going to try fixing all this :D \$\endgroup\$ – Wysaard Jul 11 '16 at 11:25
  • \$\begingroup\$ @Darklightus: You're welcome. Keep in mind that you should not change your code significantly. If you want a review on revised code, post a new question. \$\endgroup\$ – Zeta Jul 11 '16 at 11:32
  • \$\begingroup\$ @Zeta: You're right. I was working with the version on GitHub (so I can look at it more easily while writing my answer), which does have a negative balance check. \$\endgroup\$ – David Foerster Jul 11 '16 at 12:00

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.