15
\$\begingroup\$

This compiler, implemented in C++, takes brainfuck code and produces a valid (but still obfuscated) C program, which in turn can be compiled to a native binary.

Expected usage is as follows:

  1. Build the compiler

    $ c++ -o bfc bfc.cpp
    
  2. Compile a brainfuck program (example) to C

    $ ./bfc ascii.bf
    
  3. Compile the resulting C program to an executable.

    $ cc -g -O0 -o ascii ascii.bf.c
    
  4. Run the executable natively.

    $ ./ascii
    

    Or, you can also run it in a debugger. As long as you compiled with debugging symbols included and without optimizations, you should be able to step through the brainfuck source code line by line.

    $ gdb ascii
    [...]
    (gdb) break ascii.bf:1
    Breakpoint 1 at 0x1000010fc: file ascii.bf, line 1.
    (gdb) run
    [...]
    Breakpoint 1, main (argc=1, argv=0x7fff5fbffbd0) at ascii2.bf:1
    1   [-][
    (gdb) break ascii.bf:66
    Breakpoint 2 at 0x1000031c3: file ascii.bf, line 66.
    (gdb) cont
    Continuing.
    
    Breakpoint 2, main (argc=1, argv=0x7fff5fbffbd0) at ascii.bf:66
    66      >>>>> >>>>> >>> .                   (c_ascii)
    (gdb) display m.ptr
    1: m.ptr = 4
    Current language:  auto; currently minimal
    (gdb) display /d m.mem[0] @ 32
    2: /d m.mem[0] @ 32 = {0, 58, 32, 10, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 58, 48, 1, 0, 0, 0, 58, 48, 1, 0, 0, 0, 58, 48, 0, 0}
    (gdb) display /d m.mem[m.ptr]
    3: /d m.mem[m.ptr] = 0
    

I'd like to know:

  1. How well does this technique work for debuggers other than GDB?
  2. Is there anything I should do to make either the compiler source code or the generated output more readable?
  3. How should I improve the error handling?
  4. Are there any other improvements you might suggest?

#include <cctype>
#include <fstream>
#include <iostream>
#include <string>

static const char BOILERPLATE_HEAD[] = "\
#include <stdio.h>\n\
#include <stdlib.h>\n\
#include <strings.h>\n\
\n\
typedef unsigned char bf_mem_t;\n\
\n\
struct machine_state {\n\
    int ptr;\n\
    int size;\n\
    bf_mem_t *mem;\n\
};\n\
\n\
void error(int line, struct machine_state *m) __attribute__((noreturn));\n\
void error(int line, struct machine_state *m) {\n\
    abort();\n\
}\n\
\n\
int init_machine(struct machine_state *m) {\n\
    m->ptr = 0;\n\
    m->size = 8;\n\
    m->mem = calloc(m->size, sizeof(bf_mem_t));\n\
    return 0 != m->mem;\n\
}\n\
\n\
int realloc_machine(int line, struct machine_state *m, int min_size) {\n\
    int new_size = m->size;\n\
    do {\n\
        new_size <<= 1;\n\
    } while (new_size < min_size);\n\
    if (NULL == (m->mem = realloc(m->mem, new_size))) {\n\
        return 0;\n\
    }\n\
    bzero(m->mem + m->size, new_size - m->size);\n\
    m->size = new_size;\n\
    return 1;\n\
}\n\
\n\
void advance(int line, struct machine_state *m, int change) {\n\
    m->ptr += change;\n\
}\n\
\n\
int ensure(int line, struct machine_state *m) {\n\
    if (m->ptr < 0) {\n\
        return 0;\n\
    }\n\
    if (m->ptr >= m->size && !realloc_machine(line, m, m->ptr)) {\n\
        return 0;\n\
    }\n\
    return 1;\n\
}\n\
\n\
int incr(int line, struct machine_state *m, int change) {\n\
    if (!ensure(line, m)) {\n\
        return 0;\n\
    }\n\
    m->mem[m->ptr] += change;\n\
    return 1;\n\
}\n\
\n\
bf_mem_t mem(int line, struct machine_state *m) {\n\
    if (m->ptr < 0) {\n\
        error(line, m);\n\
    } else if (m->ptr >= m->size) {\n\
        return 0;\n\
    } else {\n\
        return m->mem[m->ptr];\n\
    }\n\
}\n\
\n\
/* Only useful as a possible debugging breakpoint */\n\
struct machine_state *beginwhile(struct machine_state *m) {\n\
    return m;\n\
}\n\
\n\
/* Only useful as a possible debugging breakpoint */\n\
struct machine_state *endwhile(struct machine_state *m) {\n\
    return m;\n\
}\n\
\n\
int input(int line, struct machine_state *m) {\n\
    if (!ensure(line, m)) {\n\
        return 0;\n\
    }\n\
    int c = getchar();\n\
    if (-1 == c) {\n\
        return 0;\n\
    } else {\n\
        m->mem[m->ptr] = c;\n\
        return 1;\n\
    }\n\
}\n\
\n\
void output(int line, struct machine_state *m) {\n\
    putchar(mem(line, m));\n\
}\n\
void comment(int line, struct machine_state *m, const char *comment) {\n\
    return;\n\
    fprintf(stderr, \"%d %s\", line, comment);\n\
}\n\
\n\
#define L       advance(__LINE__, &m, -1);\n\
#define R       advance(__LINE__, &m, +1);\n\
#define M       if (!incr(__LINE__, &m, -1)) error(__LINE__, &m);\n\
#define P       if (!incr(__LINE__, &m, +1)) error(__LINE__, &m);\n\
#define W       while(mem(__LINE__, beginwhile(&m)))\n\
#define E       endwhile(&m);\n\
#define I       if (!input(__LINE__, &m)) error(__LINE__, &m);\n\
#define O       output(__LINE__, &m);\n\
#define C(x)    comment(__LINE__, &m, (x));\n\
\n\
\n\
int main(int argc, char *argv[]) {\n\
    struct machine_state m;\n\
    init_machine(&m);\n"
"#line 1 ";

static const char BOILERPLATE_TAIL[] = "}\n";

struct ParserState {
    std::string comment;
};

std::string &c_escape_string(std::string &comment) {
    std::string::size_type i = 0;
    while (std::string::npos != (i = comment.find_first_of("\\\a\b\f\n\r\t\v\"", i))) {
        switch (comment[i]) {
            case '\\':  comment.replace(i, 0, "\\"); break;
            case '\a':  comment.replace(i, 1, "\\a"); break;
            case '\b':  comment.replace(i, 1, "\\b"); break;
            case '\f':  comment.replace(i, 1, "\\f"); break;
            case '\n':  comment.replace(i, 1, "\\n"); break;
            case '\r':  comment.replace(i, 1, "\\r"); break;
            case '\t':  comment.replace(i, 1, "\\t"); break;
            case '\v':  comment.replace(i, 1, "\\v"); break;
            default:    comment.replace(i, 0, "\\");
        }
        i += 2;
    }
    return comment.insert(0, "\"").append("\"");
}

std::ostream &emit_boilerplate_head(std::ostream &out, const std::string &filename) {
    out << BOILERPLATE_HEAD;
    if (!filename.empty()) {
        std::string fn(filename);
        out << c_escape_string(fn);
    }
    return out << std::endl;
}

std::ostream &emit_boilerplate_tail(std::ostream &out) {
    return out << BOILERPLATE_TAIL;
}

std::ostream &emit_comment(ParserState &state, std::ostream &out) {
    std::string leading_whitespace, trailing_whitespace;
    std::string::size_type pos;
    if (std::string::npos != (pos = state.comment.find_first_not_of(" \f\n\r\t\v"))) {
        leading_whitespace = state.comment.substr(0, pos);
        state.comment = state.comment.substr(pos);
    }
    if (std::string::npos != (pos = state.comment.find_last_not_of(" \f\n\r\t\v"))) {
        trailing_whitespace = state.comment.substr(pos + 1);
        state.comment.resize(pos + 1);
    }
    out << leading_whitespace;
    if (!state.comment.empty()) {
        out << "C(" << c_escape_string(state.comment) << ")";
        state.comment.clear();
    }
    out << trailing_whitespace;
    return out;
}

std::ostream &emit_instruction(ParserState &state, std::ostream &out, char instruction) {
    emit_comment(state, out);
    if ('W' == instruction) {
        out << "W{";    // Exception for readability
    } else if ('E' == instruction) {
        out << "E}";    // Exception for readability
    } else {
        out << instruction << ' ';
    }
    return out;
}

/* Try hard to preserve whitespace, especially line breaks, so that debuggers
   can deduce the right line numbers. */
std::ostream &emit_whitespace(ParserState &state, std::ostream &out, char c) {
    if (state.comment.empty()) {
        out << c;
    } else {
        state.comment += c;
    }
    if (c == '\n' || c == '\r') {
        emit_comment(state, out);
    }
    return out;
}

std::ostream &compile(std::istream &in, std::ostream &out) {
    ParserState state;
    char c;
    while (in.get(c)) {
        if (isspace(c)) {
            emit_whitespace(state, out, c);
        } else switch (c) {
            // Operations and their mnemonics
            case '<':   emit_instruction(state, out, 'L'); break;   // Left
            case '>':   emit_instruction(state, out, 'R'); break;   // Right
            case '-':   emit_instruction(state, out, 'M'); break;   // Minus
            case '+':   emit_instruction(state, out, 'P'); break;   // Plus
            case '[':   emit_instruction(state, out, 'W'); break;   // While
            case ']':   emit_instruction(state, out, 'E'); break;   // End
            case ',':   emit_instruction(state, out, 'I'); break;   // Input
            case '.':   emit_instruction(state, out, 'O'); break;   // Output
            default:    state.comment += c;
        }
    }
    emit_comment(state, out);
    return out;
}

int main(int argc, char *argv[]) {
    std::istream *in = &std::cin;
    std::ostream *out = &std::cout;

    std::ifstream infile;
    std::ofstream outfile;
    std::string filename;

    for (int i = 1; i < argc; ++i) {
        if (argv[i][0] && argv[i][0] != '-') {
            filename = argv[i];
            infile.open(filename);
            outfile.open(filename + ".c");
            in = &infile;
            out = &outfile;
            break;
        }
    }
    emit_boilerplate_head(*out, filename);
    compile(*in, *out);
    emit_boilerplate_tail(*out);
    *out << std::endl;
    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I might be missing something, but why are you methods all return a std::ostream reference? I guess it could facilitate method chaining but it's not really used as far as I can see. \$\endgroup\$ – ChrisWue Jan 16 '14 at 9:38
  • \$\begingroup\$ @ChrisWue That was the intention, but it didn't turn out to be that useful in practice. \$\endgroup\$ – 200_success Jan 16 '14 at 9:58
  • \$\begingroup\$ Would that not be a translator not a compiler. \$\endgroup\$ – Martin York Jan 17 '14 at 21:38
  • \$\begingroup\$ @LokiAstari You could call it a translator. However, it fits Wikipedia's definition of a compiler as "A compiler is a computer program (or set of programs) that transforms source code written in a programming language (the source language) into another computer language (the target language, often having a binary form known as object code)." \$\endgroup\$ – 200_success Jan 17 '14 at 22:39
3
\$\begingroup\$

As far as I can understand

default:    comment.replace(i, 0, "\\");

makes

case '\\':  comment.replace(i, 0, "\\"); break;

useless.

Edit to add another comment :

Please activate all warnings on your code on one hand and on the generated code on the other hand. I think that :

void comment(int line, struct machine_state *m, const char *comment) {\n\
    return;\n\
    fprintf(stderr, \"%d %s\", line, comment);\n\
}\n\

shoud eventually warn you about unreachable code.

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