11
\$\begingroup\$

I posted a question on Stack Overflow regarding this program. I ended up pretty much rewriting everything to get what is posted here. This turned into a two-day long project. I've been using Python for so long; I've been spoiled. Anyhow, here is a BrainF*** interpreter. It takes in a file or reads from stdin. I've tested it with:

... so I am fairly confident this is an accurate implementation of the language specs; except for bounds checking. I don't have bounds checking. If you find a bug I'd like to hear about it! Moreover I'd like to read some feedback regarding the quality of the code itself. There's a doubly-linked list I never really implement aside from the input text. I should really just switch out all that for a static array; or maybe switch out the program's memory array for a dynamic array. I can't decide.

bf.h

// list.c
typedef struct list list;
struct node {
    struct node *prev;
    int val;
    struct node *jump;
    struct node *next;
};
typedef struct node node;
node *newnode();
node *append(node *n);
node *prepend(node *n);
void erase(node *n);
int pop(node *n);
// op.c
void doop(node *n);
node *link(node *n);

list.c

#include <stdlib.h>
#include "bf.h"

// allocates a new node and sets all the things to zero
node *newnode() {
    node *n = malloc(sizeof(node));
    n->prev = n->next = 0;
    n->jump = n->val = 0;
    return n;
}

// appends a node to a given node. assumes it is an end node
node *append(node *n) {
    n->next = newnode();
    n->next->prev = n;
    return n->next;
}

// prepend node to list. assumes it is the first node
node *prepend(node *n) {
    n->prev = newnode();
    n->prev->next = n;
    return n->prev;
}

// navigates to first node, then frees all the nodes, iterating to the end
void erase(node *n) {
    node *m;
    while (n->prev)
        n = n->prev;
    while (n->next) {
        m = n->next;
        free(n);
        n = m;
    }
}

// pops any node and links any connected nodes to each other
// returns value of erased node
int pop(node *n) {
    int ret;
    if (n->prev)
        n->prev->next = n->next;
    if (n->next)
        n->next->prev = n->prev;
    ret = n->val;
    free(n);
    return ret;
}

op.c

#include <stdio.h>
#include "bf.h"

// bf tokens. all other are ignored
#define LSEEK       '<'
#define RSEEK       '>'
#define INCREMENT   '+'
#define DECREMENT   '-'
#define STDOUT      '.'
#define STDIN       ','
#define LBRACKET    '['
#define RBRACKET    ']'

// memory used by bf program. is this really turing-compliant?
char mem[30000] = { 0 };
// pointer used by bf program
char *ptr = mem;

// do operation beginning with given node
void doop(node *n) {
    // copy node pointer in case we need the head of the list later
    node *m = n;
    // loop while node pointer is a valid one; e.g. stop at EOF
    while (m) {
        switch (m->val) {
            // most of these are pretty self-explanatory
            case LSEEK:
                ptr--;
                break;
            case RSEEK:
                ptr++;
                break;
            case INCREMENT:
                (*ptr)++;
                break;
            case DECREMENT:
                (*ptr)--;
                break;
            case STDOUT:
                printf("%c", *ptr);
                fflush(stdout);
                break;
            case STDIN:
                *ptr = getchar();
                break;
            case LBRACKET:
                // jump to closing bracket if value at pointer is false
                if (!*ptr)
                    m = m->jump;
                break;
            case RBRACKET:
                // jump back to opening bracket if value at pointer is true
                if (*ptr)
                    m = m->jump;
                break;
        }
        // proceed to next instruction
        m = m->next;
    }
}

// finds and references each bracket instruction to its corresponding bracket
node *link(node *n) {
    // make a copy of the list head
    node *m = n;
    // make a temporary list to contain bracket links
    node *links = newnode();
    // while a valid node
    while (m) {
        // switch to bracket type
        switch (m->val) {
            case LBRACKET:
                // this is an opening bracket, so we temporarily store it's
                // location, and append the list as it grows
                if (links->jump)
                    links = append(links);
                links->jump = m;
                break;
            case RBRACKET:
                // this is the closing bracket, so we save the temporarily
                // stored link address to the closing bracket node, and
                // connect the opening bracket node to the closing also;
                // popping the list as we no longer need the data
                m->jump = links->jump;
                links->jump->jump = m;
                if (links->prev) {
                    links = links->prev;
                    pop(links->next);
                }
                break;
        }
        // increment to next character
        m = m->next;
    }
    // erase all the nodes in the temporary linked list
    erase(links);
    // return the head of the list
    return n;
}

main.c

#include <stdio.h>
#include <stdlib.h>
#include <signal.h>
#include "bf.h"

// press ctrl-c then enter to quit if not running from a file
int run = 1;
void quit(int val) {
    run = 0;
}

int main(int argc, char** argv) {
    // catch crtl-c
    signal(SIGINT, quit);
    int c;
    // our text structure is a linked list
    node *text, *text_start;
    if (argc > 1) {
        // print the file name
        printf("%s\n", argv[1]);
        // open the file and read it to the linked list
        FILE *f = fopen(argv[1], "r");
        if (f == NULL) return 1;
        text = text_start = newnode();
        while ((c = fgetc(f)) != EOF) {
            if (text->val)
                text = append(text);
            text->val = c;
        }
        fclose(f);
        // link all the loops/ gotos, then process all instructions
        doop(link(text_start));
        // free all linked list nodes
        erase(text_start);
        // we just ran a file, so no interpreter
        run = 0;
    }
    // repeatedly read and execute only one line until interrupted
    while (run) {
        // linked list generated for each line of input
        text = text_start = newnode();
        // read stdin buffer to list
        while ((c = getchar()) != '\n') {
            if (text->val)
                text = append(text);
            text->val = c;
        }
        // link all the loops/ gotos, then process the
        // instructions for the line
        doop(link(text_start));
        // free all linked list nodes
        erase(text_start);
    }
    return 0;
}
\$\endgroup\$
12
+50
\$\begingroup\$

This looks really good over all. I have pretty much no knowledege of brainfuck, but it was still easy to understand the code, and nothing jumps out at me as glaringly wrong. There are however a few (mostly) minor issues.

run flag and compiler optimizations

volatile is a widely misused variable modifier, but you acutally have one of the text book examples of when to use it. In particular, int run should be volatile. This is because the value can change in a way that the compiler is not particularly aware of. Imagine the while (run) loop from a compiler's perspective: nothing executed in that loop ever modifies run. This means that the compiler is technically allowed to assume the value of run does not change there and optimize that loop into if (run) { while (1) {} }. Marking run volatile tells the compiler that no, it really has to load it every time it looks at it, and it can't just assume from its own analysis that it never changes.

Function names

The node-related functions could be named a bit clearer. For example, I would prefix all of them with node_: node_new, node_append, node_prepend, etc. I like to go one step farther and prefix things with a fairly unique token (maybe bf_node_ instead of just node_), but that's overkill unless you plan on actually distributing a library version of this or it growing into a large project.

The names of some of your functions could be a lot clearer. doop could be evaluate_node, and link could be link_brackets, for example.

List interface

Your list interface seems a bit off to me. It should either be focused on values and have methods like int append(node* n, int value), or it should only do one thing like void append(node* n, node* next); In its current state, it's a strange middle ground where you actually have the list in a non-valid state for a bit until the user sets a value on the node. This is a bit strange, and I think it's prone to user error. I'd prefer to see an interface that operates around values instead of nodes whenever possible.

It would also be nice to have a list type that encapsulates a sequence of nodes. I don't really like how erase and pop traverse from whatever node you give them. This is both confusing and inefficient. Having certain functions be able to operate on a list instead of a node would be very convenient.

Global variables

Your interpretter currently depends on global state. This means that you can't have two independent brainfuck instances at the same time. This might be an acceptable limitation (for now...), but it still makes programs harder to reason about, and it can make certain types of bugs very hard to track down. It would be better if you had a data structure to encapsulate this global state, and then instead of operating on globals, your functions would just acccept this struct brainfuck or struct brainfuck_interpretter or whatever.

malloc result

You should check the return value of malloc. Currently you'll (probably) just get a segfault in newnode if allocation fails.

Code consolidation

The case where a file name is provided and the case where stdin is used look very similar to me. You can probably pull that into a consume_stream function that takes a FILE*, and it will make your main a lot more manageable and get rid of code duplication. Depending on how you want to handle the line-based approach compared to file based, this might be a problem though.

NULL vs 0

node *newnode() {
    node *n = malloc(sizeof(node));
    n->prev = n->next = 0;
    n->jump = n->val = 0;
    return n;
}

NULL conveys semantic meaning whereas 0 doesn't. For this reason, 0 as a null pointer should be avoided in favor of NULL.

Variable delcarations

You seem to be using C99 or newer, so you should be declaring your variables as closely as possible to use instead of at at the beginning of function scopes.

#define vs enum

I would put all of the tokens in an enum: enum brainfuck_token { LSEEK = '<', RSEEK = '>', ... }. An example where this could be nice is giving your list a brainfuck_token val; member instead of an int. enums also can't be re#defined which is nice, and debuggers can more easily find names for them instead of the literal you're likely to see for a #define.

In other words, unless you need a #define for some reason or other (they can be incredibly useful if you either have to use one because of limitations on other options or if you want to be able to change something at compile time without editing source code), it's typically better to go with either a constant or an enum.

Memory leak

From a quick run through valgrind, it looks like your application has a memory leak. This is quite interesting since at a (quick) glance, it appears that the proper memory management code is all there. It makes me a bit suspicious that there might be a bug hiding somewhere (of course, it could just be some incorrect memory management).

corbin@lmxe ~/review $ valgrind --leak-check=full ./bf fib.bf 
==2965== Memcheck, a memory error detector
==2965== Copyright (C) 2002-2013, and GNU GPL'd, by Julian Seward et al.
==2965== Using Valgrind-3.10.0.SVN and LibVEX; rerun with -h for copyright info
==2965== Command: ./bf fib.bf
==2965== 
fib.bf
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89==2965== 
==2965== HEAP SUMMARY:
==2965==     in use at exit: 64 bytes in 2 blocks
==2965==   total heap usage: 556 allocs, 554 frees, 18,328 bytes allocated
==2965== 
==2965== 32 bytes in 1 blocks are definitely lost in loss record 1 of 2
==2965==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2965==    by 0x4007C6: newnode (list.c:6)
==2965==    by 0x400820: append (list.c:14)
==2965==    by 0x400A6A: main (main.c:27)
==2965== 
==2965== 32 bytes in 1 blocks are definitely lost in loss record 2 of 2
==2965==    at 0x4C2AB80: malloc (in /usr/lib/valgrind/vgpreload_memcheck-amd64-linux.so)
==2965==    by 0x4007C6: newnode (list.c:6)
==2965==    by 0x400D3A: link (op.c:67)
==2965==    by 0x400A92: main (main.c:32)
==2965== 
==2965== LEAK SUMMARY:
==2965==    definitely lost: 64 bytes in 2 blocks
==2965==    indirectly lost: 0 bytes in 0 blocks
==2965==      possibly lost: 0 bytes in 0 blocks
==2965==    still reachable: 0 bytes in 0 blocks
==2965==         suppressed: 0 bytes in 0 blocks
==2965== 
==2965== For counts of detected and suppressed errors, rerun with: -v
==2965== ERROR SUMMARY: 2 errors from 2 contexts (suppressed: 0 from 0)
\$\endgroup\$
  • 1
    \$\begingroup\$ The last node wasn't being freed. In erase(), while (n->next); should be while (n); \$\endgroup\$ – motoku Mar 8 '15 at 2:03
3
\$\begingroup\$

REPL mode

When was the last time you live-coded a Brainfuck program in a read-eval-print loop? Is the REPL useful enough to justify writing two copies of the code in main()? Bear in mind that the , operation also reads from standard input, which gets rather confusing when your program is also being fed through standard input.

Your SIGINT handler doesn't really work. It makes it so that Ctrl C will not interrupt a program run from a file, since the run flag will only be checked after the program naturally terminates anyway. As for REPL mode, you only check the run flag after a newline character, so the effect is that you need to type Ctrl C Enter to quit. You would be better off with the default SIGINT handler.

In all cases, the program's exit code is 0. I would expect it to be non-zero if it terminates prematurely for any reason.

Security

You do not enforce that the memory pointer stays within the 30000-byte tape. That memory is in the stack, so it would be trivially easy to trigger a stack-based buffer overflow. Since the whole point of the Brainfuck interpreter is to let the program manipulate memory in any arbitrary way, it would also be easy to craft a malicious Brainfuck program to write some shellcode to be executed on buffer overflow.

A program with mismatched brackets, such as +], should cause an error. In your case, it triggers a segmentation fault.

Type mismatch

The compiler should have warned you:

list.c:8:13: warning: incompatible integer to pointer conversion assigning to
      'struct node *' from 'int' [-Wint-conversion]
    n->jump = n->val = 0;
            ^ ~~~~~~~~~~
1 warning generated.

What would make more sense is

node *newnode() {
    node *n = malloc(sizeof(node));
    n->prev = n->next = n->jump = NULL;
    n->val = 0;
    return n;
}

Or, better yet,

node *newnode() {
    return calloc(sizeof(node), 1);
}

Header organization

Your bf.h header contains comments // list.c and // op.c. That to me is an indication that you should have split up the header file into a list.h and op.h.

Linked list appropriateness

Linked lists are useful for data where access is mostly sequential, and where you need to frequently insert and remove some elements in the middle of the list. They aren't good for much else — which is to say, they are rarely useful.

On my 64-bit system, sizeof(node) is 32 — eight bytes per member field, including alignment. That is, you use 32 bytes of memory for each byte of source code, plus some more for the malloc() bookkeeping. Even if memory is plentiful, wasting it reduces the memory cache hit rate.

You used your linked list in two ways:

  • To store the code, one node per character of the program, and
  • As a stack while building the jump table.

Both of those applications would have been better implemented with something other than a linked list. The code should just be a byte array that directly reflects the file contents. For building the jump table, instead of using an explicit stack, you could use recursion and take advantage of the C call stack for a "free" stack implementation.

Linked list usage

If you are using a linked list, then a doubly-linked list is overkill, since a singly-linked list would have sufficed. You also have some awkward special cases for the first inserted node.

The linked list implementation could be simplified to this:

node *newnode() {
    return calloc(sizeof(node), 1);
}

node *prepend(node *head) {
    node *n = newnode();
    n->next = head;
    return n;
}

node *append(node *tail) {
    return tail->next = newnode();
}

node *pop(node *head) {
    node *n = head->next;
    free(head);
    return n;
}

void erase(node *head) {
    while (head) {
        head = pop(head);
    }
}

Then, in link(), you should manipulate the stack by working on the head of the list, not the tail:

node *link(node *n) {
    node *links = NULL;

    for (node *m = n; m; m = m->next) {
        switch (m->val) {
            case LBRACKET:
                (links = prepend(links))->jump = m;
                break;
            case RBRACKET:
                if (!links) {
                    break;  // Error: not enough '[' brackets
                }
                m->jump = links->jump;
                links->jump->jump = m;
                links = pop(links);
                break;
        } 
    }   
    // Free nodes in case there are too few ']' brackets
    erase(links);
    return n;
}

In main(), the code to populate list has an awkward special case. I'd write it this way instead:

text = text_start = newnode();
while ((c = fgetc(f)) != EOF) {
    text = append(text);
    text->val = c;
}
text_start = pop(text_start);

Suggested solution

I've posted an alternative implementation that rectifies the main problems I've mentioned above.

\$\endgroup\$
1
\$\begingroup\$

I think that the data structure and the organization of the code is far from optimal. You are making an interpreter with some sort of precompilation (the link function which searches for brackets). The data structure used to store the "compiled" code is bloated. You have a doubly-linked list for something that will never dynamically change. The prev pointer is never used. The jump pointer is rarely used.

What I suggest:

  1. use a bytecode to store your compiled code. The only thing you need is to replace the brackets with some sort of jump_if statement. No need for linked list... just a buffer of bytes.

  2. write a function to compile BrainF*** into your bytecode. Just copy the source code and put the current address on a stack whenever you find an open bracket. Write the jump_if statements when you find the corresponding closed bracket.

  3. define a data structure for the state of your virtual machine: data pointer, program pointer... and that's all.

  4. write the interpreter as a function accepting the virtual machine.

Other issues:

  • I don't understand why you are going to intercept the SIGINT signal, since you are replicating the standard behavior... I would remove that code

  • in the line

    n->jump = n->val = 0;

you are assigning an int to a pointer... A double assignment is not appropriate in this case.

  • in the main function you are repeating yourself when you distinguish the execution from a file and from stdin. Factor them out in a single function.
\$\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.