11
\$\begingroup\$

I wrote this BrainFuck interpreter in ANSI C89:

/*
 *  Copyright © 2019 James Larrowe
 *
 *  This file is part of bf.
 *
 *  bf is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  bf is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with bf.  If not, see <https://www.gnu.org/licenses/>.
 */

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

#define DEF_MEM_SIZE 32768

#define ezs(x) (x)
#define exit_if_true(x, y) if(x) exit_perr(y)

void bf_interp(unsigned char *, const unsigned char *, size_t, size_t);
void exit_perr(const char *);
unsigned char *read_file(const char *, size_t *);

int main(int argc, char **argv)
{
    size_t file_size,
           mem_size = DEF_MEM_SIZE;
    unsigned char *file, *mem;

    if(argc != 2)
    {
        fprintf(stderr, "Error: Incorrect number of arguments\n"
                        "  Usage: %s [file] (args...)\n", argv[0]);
        return 1;
    }

    file = read_file(argv[1], &file_size);
    mem = calloc(sizeof(*mem), mem_size);
    exit_if_true(mem == NULL, "calloc()");

    bf_interp(mem, file, mem_size, file_size);

    free(mem);
    free(file);

    return 0;
}

void bf_interp(unsigned char *sp, const unsigned char *ip, size_t sp_size, size_t ip_size)
{
    long spc = 0, ipc = 0;

    while(ezs(size_t)ipc < ip_size)
    {
        /* I would put this inside the switch
         * but clang warns about "unreachable code".
         */
        int nest;
        switch(ip[ipc])
        {
            case '>':
            {
                spc++;
                if(ezs(size_t)spc >= sp_size)
                {
                    unsigned char *tmp;

                    tmp = realloc(sp, sp_size + DEF_MEM_SIZE);
                    exit_if_true(tmp == NULL, "realloc()");

                    memset(tmp+sp_size, 0, DEF_MEM_SIZE);
                    memcpy(tmp, sp, sp_size);

                    sp_size += DEF_MEM_SIZE;

                    free(sp);
                    sp = tmp;
                }
                break;
            }
            case '<':
            {
                spc--;
                if(spc < 0)
                {
                    fputs("Error: spc < 0\n", stderr);
                    exit(1);
                }
                break;
            }
            case '+':
            {
                sp[spc]++;
                break;
            }
            case '-':
            {
                sp[spc]--;
                break;
            }
            case '.':
            {
                putchar(sp[spc]);
                break;
            }
            case ',':
            {
                int c = getchar();
                if(c != EOF)
                    sp[spc] = ezs(unsigned char)c;
                break;
            }
            case '[':
            {
                if(sp[spc] == 0)
                {
                    for( nest = 1; nest; )
                    {
                        ipc++;
                        if(ezs(size_t)ipc >= ip_size)
                        {
                            fputs("Error: ipc >= ip_size\n", stderr);
                            exit(1);
                        }
                        nest += (ip[ipc] == '[');
                        nest -= (ip[ipc] == ']');
                    }
                }
                break;
            }
            case ']':
            {
                if(sp[spc])
                {
                    for( nest = 1; nest; )
                    {
                        ipc--;
                        if(ipc < 0)
                        {
                            fputs("Error: ipc < 0\n", stderr);
                            exit(1);
                        }
                        nest -= (ip[ipc] == '[');
                        nest += (ip[ipc] == ']');
                    }
                }
                break;
            }
            default:
                break;
        }
        ipc++;
    }
}

unsigned char *read_file(const char *argv1, size_t *size)
{
    unsigned char *file;
    size_t was_read, sz;
    FILE *fp;

    fp = fopen(argv1, "r");
    exit_if_true(fp == NULL, "fopen()");

    exit_if_true(fseek(fp, 0L, SEEK_END) == -1, "fseek()");

    sz = ezs(size_t)ftell(fp);
    exit_if_true(sz == ezs(size_t)-1, "ftell()");

    *size = sz;

    file = malloc(sz);
    exit_if_true(file == NULL, "malloc()");

    exit_if_true(fseek(fp, 0L, SEEK_SET) == -1, "fseek()");

    was_read = fread(file, 1, sz, fp);
    if(was_read != sz)
    {
        fprintf(stderr, "Unable to read file.\n"
                        "Read %zu bytes when %zu bytes were expected\n",
                        was_read, sz);
        exit(1);
    }

    exit_if_true(fclose(fp) == EOF, "fclose()");

    return file;
}

void exit_perr(const char *str)
{
    perror(str);
    exit(1);
}

It's been tested and it works properly, but there are some design issues I'm worried about. In particular:

  • Have I split the code up into functions enough?

  • Do I have variable names that describe the code well?

  • How can I make it more efficient around the nesting code (case '[': and case ']':)?

  • Is it portable?

  • Are there any issues with it that I may have overlooked?

This runs and produces results identical to many other BrainFuck interpreters that I've tried.

This is available under the GPLv3 in my GitHub repository here.

\$\endgroup\$
  • 2
    \$\begingroup\$ Uff, this is horribly complicated code (hard to maintain, hard to find a bug). Keep it simple. Take a look at this one :) \$\endgroup\$ – DaBler Oct 11 at 17:24
7
+200
\$\begingroup\$

Okay, what's the deal with #define ezs(x) (x)? Is it some kind of trick to either hide C-style casts, or make them more greppable? If the latter, why such a short name? How about #define CAST_TO(x) (x)?


Other naming comments:

  • was_read sounds like a boolean. I think you mean bytes_read or even num_bytes_read.

  • Your function names are all tersified according to different conventions. You've got interpret_brainfuck (verb-noun), perror_and_exit (verb-and-verb), and read_file (verb-noun) — but you've tersified them as bf_interp (noun-abbrverb), exit_perr (reversed the order of the verbs for some reason), and... okay, read_file is a good name. :)


#define exit_if_true(x, y) if(x) exit_perr(y)

(A) Why is this not a (static) inline function? I don't think the macro is buying you anything.

(B) Consider:

if (cond1)
    exit_if_true(cond2, "message");
else
    puts("cond1 was false");  // LIES!

Always, always, always use proper macro hygiene in C and C++! It costs nothing, and it shows the reader that you know what you're doing, and every so often it avoids a really sneaky bug. What you should have written was:

#define exit_if_true(x, y) do { if (x) exit_perr(y); } while (0)

or, even better,

static inline void exit_if_true(bool b, const char *message) {
    if (b) {
        exit_perr(message);
    }
}

size_t file_size,
       mem_size = DEF_MEM_SIZE;
unsigned char *file, *mem;

Please, for the sake of your readers, write each declaration on its own line. I mean, it costs literally one more line of source code to write

size_t file_size;
size_t mem_size = DEF_MEM_SIZE;
unsigned char *file;
unsigned char *mem;

This also calls attention to the fact that you failed to initialize three of these variables. That smells like a bug. Let's see...

file = read_file(argv[1], &file_size);
mem = calloc(sizeof(*mem), mem_size);

Ah. So it actually would have saved you several lines of code to write simply

if (argc != 2) {
    fprintf(stderr, "Error: Incorrect number of arguments\n"
                    "  Usage: %s [file] (args...)\n", argv[0]);
    return 1;
}
size_t file_size;
unsigned char *file = read_file(argv[1], &file_size);

size_t mem_size = DEF_MEM_SIZE;
unsigned char *mem = calloc(mem_size, 1);
exit_if_true(mem == NULL, "calloc()");

I notice in passing that return 1; is quite natural and correct and POSIX-compliant — it's a really good idea to specify exactly what integral value your process returns on error — but technically it's not "ANSI C" to do that. ANSI C wants you to use return EXIT_FAILURE;, which returns an implementation-defined "failure" result.

More importantly, you accidentally swapped the arguments to calloc. They go nmemb, size. And yes, I had to look it up. I know that I always have to look it up. This, IMVHO, is a reason never to use calloc — I'd use malloc and then do an explicit memset if for some reason I needed zero-initialization.

Notice that sizeof(char) is 1 by definition.


long spc = 0, ipc = 0;

Again, I strongly recommend one declaration per line.

What's weird here is that you're carefully defining these variables as long... but then casting them to size_t everywhere they're used! Why not just define them as size_t?

I also personally dislike seeing long because its size varies from platform to platform. "Everyone knows" that on common desktop systems int is 32 bits and long long is 64, but the size of long might be one or the other, depending on architecture and operating system. Using long is like saying, "I want to have portability problems a year from now."


free(mem);

This is a double-free and crash bug. bf_interp will have freed the original value of mem the very first time it does a realloc. Either

  • pass mem by address to bf_interp so that bf_interp can modify it, or
  • transfer the responsibility for freeing mem into bf_interp — turn bf_interp into a "sink."

Since bf_interp uses mem as scratch space, trashing its semantic contents as well as its physical pointer value, I think the second option above makes quite a bit of sense.

The one thing that might change my mind is if you could demonstrate that bf_interp does not "trash" mem's contents, but rather updates them in a meaningful way. For example, if bf_interp took a parameter num_steps, and ran the program for that many steps, and then returned, so that you could "resume" the interpretation later — well, then it would make sense that bf_interp needs a way to pass mem back out to its caller. (But then bf_interp would also need a way to pass the rest of its state — ipc and spc. And now you're halfway to inventing object-oriented programming.)


Oh hey — your entire use of realloc is wrong!

                tmp = realloc(sp, sp_size + DEF_MEM_SIZE);
                exit_if_true(tmp == NULL, "realloc()");

                memset(tmp+sp_size, 0, DEF_MEM_SIZE);
                memcpy(tmp, sp, sp_size);

                sp_size += DEF_MEM_SIZE;

                free(sp);
                sp = tmp;

This should be simply

                sp = realloc(sp, sp_size + DEF_MEM_SIZE);
                exit_if_true(sp == NULL, "realloc()");

                memset(sp + sp_size, 0, DEF_MEM_SIZE);
                sp_size += DEF_MEM_SIZE;

Your version would become correct (but still inefficient) if you replaced realloc with simply malloc. The point of realloc is that it does the re-allocation for you; you don't have to manually free the old buffer or copy over the data.

If you used something like gcov to look at your code coverage, you'd see that your test cases (you have test cases, right?) never hit this codepath. That's why you didn't find the bug. If you had hit this codepath, the program definitely would have crashed.


    /* I would put this inside the switch
     * but clang warns about "unreachable code".
     */
    int nest;

The declaration of this variable should go at the variable's point of use. Like this:

                for (int nest = 1; nest != 0; )

Your usage message says:

Usage: ./a.out [file] (args...)

This isn't right, is it? I mean, file is not optional, and there is no such thing as args....

\$\endgroup\$
  • \$\begingroup\$ Your point about defining the variables after the if is invalid. Note the title, which says "in ANSI C". \$\endgroup\$ – JL2210 Oct 11 at 18:14
  • \$\begingroup\$ Same for the inline functions. \$\endgroup\$ – JL2210 Oct 11 at 18:15
  • 1
    \$\begingroup\$ @JL2210: As far as I know, ANSI C tracks ISO C, so the current standard is 2018. Admittedly my close knowledge of C stops circa 1999 (20 years ago), but if you're saying that you can't use inline functions because you're stuck on 19*89* (30 years ago)... and without GNU C extensions... well, I don't think you have any valid engineering reason for that. \$\endgroup\$ – Quuxplusone Oct 11 at 19:32
  • 1
    \$\begingroup\$ You can definitely test the spc-realloc bug with a short test case. Use nested loops. \$\endgroup\$ – Quuxplusone Oct 11 at 19:33
  • 1
    \$\begingroup\$ If you're asking whether Windows (MSVC) supports for (int i=0; i < n; ++i), the answer is "yes, since sometime in the '90s." \$\endgroup\$ – Quuxplusone Oct 13 at 16:35

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.