8
\$\begingroup\$

A little over a week ago I posted my basic Brainfuck interpreter here. I have since improved the interpreter on all suggested points except two minor details. (reporting the position of parsing error, which should be obvious from just the error, in Brainfuck; and a problem that would only occur in a program with at least 2GB of just [).

I'm now looking for any mistakes still left (possibly created while 'improving' the code), cases of bad style, etc. Recommendations for extra features are welcome too, of course, but my priority is the quality of the provided code.

I also host a version of it here, but I keep that one updated.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <sysexits.h>

#define MEMSIZE 30000 // max size of memory-space
#define INSSIZE 30000 // max size of instruction-space

enum {
    BF_UNDEFINED = 0, // in `instructions`, not initialized is undefined
    BF_INC,        BF_DEC,
    BF_GET,        BF_PUT,
    BF_NEXT,       BF_PREV,
    BF_LOOP_START, BF_LOOP_END,
};


int bf_instruction(char c)
{
    switch(c){
    case '+':
        return BF_INC;
    case '-':
        return BF_DEC;
    case ',':
        return BF_GET;
    case '.':
        return BF_PUT;
    case '>':
        return BF_NEXT;
    case '<':
        return BF_PREV;
    case '[':
        return BF_LOOP_START;
    case ']':
        return BF_LOOP_END;
    default:
        return BF_UNDEFINED;
    }
}


typedef struct brainfuck_data {
    int * instructions;
    size_t memsize;
    size_t inssize;
} bf_data_t;

void bf_data_init (bf_data_t * bf_data, size_t memsize, size_t inssize)
{
    bf_data->instructions = calloc(memsize,sizeof(int));
    bf_data->memsize = memsize;
    bf_data->inssize = inssize;
}

void bf_data_from_file (bf_data_t * bf_data, FILE *file)
{
    char c;
    int i = 0;
    int balance = 0; // Keeps track of BF_LOOP_START and BF_LOOP_END balance
    int instruction;
    while ((c = fgetc(file)) != EOF && i < bf_data->inssize){
        if((instruction = bf_instruction(c)) != BF_UNDEFINED){
            bf_data->instructions[i] = instruction;
            i++;
            if (instruction == BF_LOOP_START)
                balance++;
            else if (instruction == BF_LOOP_END)
                balance--;
            // Error if order of BF_LOOP_END and BF_LOOP_START tags is wrong
            if (balance < 0){
                fputs("Encountered BF_LOOP_END before matching BF_LOOP_START\n",stderr);
                exit(EX_SOFTWARE);
            }
        }
    }

    // Error if amount of instructions is more than permitted
    if (c != EOF && i >= bf_data->inssize){
        fprintf(stderr,"Cannot read more than %d instructions\n",bf_data->inssize);
        exit(EX_SOFTWARE);
    }

    // Error if BF_LOOP_START and BF_LOOP_END aren't balanced
    if (balance != 0){
        fputs("BF_LOOP_START and BF_LOOP_END were not balanced\n",stderr);
        exit(EX_SOFTWARE);
    }
}

void bf_data_run (bf_data_t *bf_data)
{
    size_t insptr = 0;
    size_t memptr = 0;

    int *memory = calloc(bf_data->memsize,sizeof(int));

    while(insptr < bf_data->inssize && bf_data->instructions[insptr] != BF_UNDEFINED){
        switch(bf_data->instructions[insptr]){
        case BF_INC:
            memory[memptr]++;
            break;
        case BF_DEC:
            memory[memptr]--;
            break;
        case BF_NEXT:
            if (memptr < bf_data->memsize - 1)
                memptr++;
            else
                memptr = 0;
            break;
        case BF_PREV:
            if (memptr > 0)
                memptr--;
            else
                memptr = bf_data->memsize - 1;
            break;
        case BF_LOOP_START:
            if (memory[memptr] == 0){
                // seek `]` forward
                int counter = 0;
                while(bf_data->instructions[insptr] != BF_LOOP_END || counter != 0){
                    if (bf_data->instructions[insptr] == BF_LOOP_END)
                        counter--;
                    insptr++;
                    if(bf_data->instructions[insptr] == BF_LOOP_START)
                        counter++;
                }
            }
            break;
        case BF_LOOP_END:
            if (memory[memptr] != 0){
                // seek `[` backward
                int counter = 0;
                while(bf_data->instructions[insptr] != BF_LOOP_START || counter != 0){
                    if (bf_data->instructions[insptr] == BF_LOOP_START)
                        counter--;
                    insptr--;
                    if(bf_data->instructions[insptr] == BF_LOOP_END)
                        counter++;
                }
            }
            break;
        case BF_PUT:
            putchar(memory[memptr]);
            break;
        case BF_GET:
            memory[memptr] = getchar();
            break;
        }
        insptr++;
    }
}

int main(int argc, char *argv[])
{
    if (argc != 2) {
        fputs("Invalid number of arguments, please provide input file as the only argument\n", stderr);
        exit(EX_USAGE);
    }

    // Create empty bf_data and initialize
    bf_data_t bf_data;
    bf_data_init (&bf_data, MEMSIZE, INSSIZE);

    // Open input file
    FILE *file = fopen(argv[1], "r");
    if (file == NULL){
        perror("Could not read input file");
        exit(EX_NOINPUT);
    }

    // Read all instructions from input
    bf_data_from_file (&bf_data,file);

    // Close input file
    fclose(file);

    // Run the program
    bf_data_run (&bf_data);
}
\$\endgroup\$
5
+50
\$\begingroup\$

Here are some observations that may help you improve your program.

Check return values and handle errors

The code calls calloc and but never checks for error return values. This is a serious problem that must be addressed. Note too, that even fclose can fail.

Don't leak memory

This code calls calloc in a few places but never free. This means that the routines are leaking memory. It would be much better to get into the habit of using free for each call to malloc or calloc and then assuring that you don't leak memory. In particular, the bf_data_run function should end with a free(memory) call.

Prefer const variables to #define

For both MEMSIZE and INSSIZE, their values could be declared as:

const size_t MEMSIZE = 30000; // max size of memory-space
const size_t INSSIZE = 30000; // max size of instruction-space

The difference is that when they are declared this way, they have a bit of additional type safety.

Be careful with size assumptions

The code currently includes this line:

fprintf(stderr,"Cannot read more than %d instructions\n",bf_data->inssize);

The problem here is that inssize is declared as type size_t but %d expects an int and they might not be the same size (and may be different signedness). Better would be to use %zd which is a modifier that is specifically for a size_t type.

Return an error code

The bf_data_from_file function can detect errors, but summarily exits the entire program rather than returning an error code that would allow the calling function to decide how to handle the error. A more robust design that might allow the code to be reused would return an error code. That way, the calling program could figure out what to do.

Here's how it might work for this program. First, define some error codes:

// Error codes
enum {
    BF_OK,
    BF_ERR_UNBALANCED_LOOP,
    BF_PROGRAM_TOO_LARGE,
    BF_LOOP_END_BEFORE_START 
};

Then change bf_data_from_file to return an int and end it with return BF_OK; and replace each instance of printing an error code and calling exit with the appropriate return instead. Calling the routine from within main might look like this:

// Read all instructions from input
switch (bf_data_from_file (&bf_data,file))  {
    case BF_ERR_UNBALANCED_LOOP:
        fputs("BF_LOOP_START and BF_LOOP_END were not balanced\n",stderr);
        exit(EX_DATAERR);
        break;
    case BF_PROGRAM_TOO_LARGE:    
        fprintf(stderr,"Cannot read more than %zd instructions\n",bf_data.inssize);
        exit(EX_DATAERR);
        break;
    case BF_LOOP_END_BEFORE_START:
        fputs("Encountered BF_LOOP_END before matching BF_LOOP_START\n",stderr);
        exit(EX_DATAERR);
        break;
    case BF_OK:
        // do nothing, all is well.
        break;
    default:
        fprintf(stderr, "Unknown error parsing input file %s\n", argv[1]);
        exit(EX_SOFTWARE);
}

Use the right error code

The EX_SOFTWARE exit code is for internal program errors, but I think that where it's used here, it's not really the fault of the program but the data that it has been fed. For that reason, I'd recommend using EX_DATAERR instead.

Be careful with signed vs. unsigned

The memory index i is declared as int but it's compared to inssize which is size_t which is unsigned on some platforms. It's probably better to declare i as size_t as well to be more portable.

\$\endgroup\$
  • \$\begingroup\$ In your opinion, what would be the correct way to propagate the error from the input? Of course return it, but what should be the default return value (I've seen 0 = nothing wrong, but also 1 = True ~ Correct) And what would be the proper statement in the main() function to read the error? It also feels kinda wrong to have something which is just maint to do operations and nothing else be anything but a void but I guess in C that's just the way it is? \$\endgroup\$ – Wysaard Aug 16 '16 at 19:29
  • \$\begingroup\$ I have updated my answer to address these questions. For error codes, it's almost always the case that there is only one way that can work, but a lot of ways to fail. For that reason, we tend to use 0 to indicate success and non-zero (and sometimes negative numbers) to indicated failure. \$\endgroup\$ – Edward Aug 16 '16 at 20:37
2
\$\begingroup\$

Code organization improvement: I suggest not polluting bf_data_from_file with EXIT's, but have it return error codes, and then exit in the main function. This makes it easier to unit test that function.

Invalid characters: the case for BF_UNDEFINED is now silently ignored, both in the reading function, as well as in the running function (where, e.g., you could add a "default" branch in the switch statement to cover that). Instead, I recommend returning some error codes for such cases, in both functions, and then bail out the program in main.

New feature: maximum size of memory and instruction could be parameters of the program, with possible fall-back to the now hard-coded values.

Unit tests: in the repo, there is currently only one example/test. I recommend adding more tests for valid and invalid usages as well. In particular, I suggest testing bf_data_run with such invalid cases, that would be caught by the parser, i.e. they would never get to the interpreter. The purpose is to make sure that this function is also robust, independently of the parser.

\$\endgroup\$
  • 1
    \$\begingroup\$ Ignoring BF_UNDEFINED is probably intentional; the language is specified to simply ignore all tokens not a part of its language. See en.wikipedia.org/wiki/Brainfuck#Hello_World.21 \$\endgroup\$ – Edward Aug 16 '16 at 20:42
  • \$\begingroup\$ @Edward I only put those instructions in memory that are actual valid instructions. Once a BF_UNDEFINED is reached, we have arrived at the space after all the instructions and the program should terminate. I guess I could do some tricks to actually make it such that the size of the instruction array is exactly as big as needed and at that point BF_UNDEFINED should never actually occur \$\endgroup\$ – Wysaard Aug 16 '16 at 22:50
2
\$\begingroup\$

Organization and readability

Position of int main()

Robert Martin's Clean Code suggests the idea of "The Newspaper Metaphor", which says that well-written code can be analogous to a well-written newspaper in that you read it vertically, with the first parts giving a synopsis of the whole story. Specificity and detail increases as you move down the page.

With this concept in mind, main() is our headline. Shifting main() to be the first function improves readability by immediately showing the reader a roadmap of program flow.

Minor nitpicks

In your struct declaration:

typedef struct brainfuck_data {
    int * instructions;
    size_t memsize;
    size_t inssize;
} bf_data_t;

Since you're using a typedef, you can omit brainfuck_data as it serves no purpose.

typedef struct {
    int * instructions;
    size_t memsize;
    size_t inssize;
} bf_data_t;

Note that if you have a self referential structure (e.g., a linked list), you can't omit the struct name as previously mentioned (Further explanation here ):

typedef struct node {
    int data;
    struct node *next; /* can't use just "node *next" here */
} node;

Additionally, you've defined this struct seemingly before it's first use in bf_data_init(). There's no clear rule against this (some larger projects will declare them in this manner). In this case, I would have expected to find it near the top, below your enum definition. Since you don't have any local headers included, and struct bf_data_t is used throughout your program (rather than a one-off single function), putting it at the top more clearly shows the reader that this is the data structure used throughout the program.

\$\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.