A Brainfuck compiler that creates a small x86_64 Linux executable from scratch

Question

This program compiles Brainfuck source code to an x86_64 ELF executable. It doesn't rely on any backend, just raw binary stream to a functional executable.

In the implementation, each cell holds an 8-bit unsigned value with usual wrapping behavior for overflow. The pointer can safely access from cell 0 to 65535, but it does not wrap around and going beyond is undefined behavior.

For an empty input program, the output executable size is 145 bytes. It is possible to make it smaller (even by overlapping some of the sections which is totally valid), but since the objective of this program is not to produce the smallest possible executable, this is the minimum.

For this wonderful 72-byte "Hello, world!" program from this guy, the result is a 374-byte executable.

    +[-->-[>>+>-----<<]<--<---]>-.>>>+.>>..+++[.>]<<<<.+++.------.<<-.>>>>+.

The compiler does some obvious optimizations such as replacing

    inc rsp; inc rsp; inc rsp; inc rsp; ...

with

    add rsp, N

Also, when an instruction can take either 8-bit or 32-bit immediate operand, the program chooses the smaller option if the value fits.

No structural kind of optimization is done, and everything is translated in a single pass. The most complicated part is calculating the jump offset.

main.c

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <elf.h>
#include <sys/stat.h>

typedef uint8_t byte;
typedef __attribute__((may_alias)) uint32_t adword;

typedef struct {
    byte *buf;
    intptr_t sz;
} buf_t;

typedef struct {
    int32_t sz;
    byte bin[12];
} bin_t;

typedef struct __attribute__((packed)) {
    Elf64_Ehdr e;
    Elf64_Phdr p;
} hdr_t;

static void chk(int ok, char *msg) {
    if (!ok) {
        printf("error: %s\n", msg);
        __asm__ volatile (
            "int3"
        );
    }
}

static buf_t strip(byte *buf, int sz) {
    int n;
    for (int i = 0, j = 0;; i += n + 1, ++j) {
        n = 0;
        for (;;) {
            if (i + n >= sz) {
                return (buf_t){buf, j};
            }
            byte c = buf[i + n];
            if (c == ',' || c == '.' || c == '>' || c == '<' || c == '+' ||
            c == '-' || c == '[' || c == ']') {
                break;
            }
            ++n;
        }
        buf[j] = buf[i + n];
    }
}

static int count(byte *buf, byte c) {
    int n = 0;
    do {
        ++n;
    } while (*++buf == c);
    return n;
}

static int jmpdist(bin_t *x, bin_t *y) {
    int d = 0;
    for (; x < y; ++x) {
        d += x->sz;
    }
    return d;
}

#define COPY(d, s) memcpy(d, s, sizeof(s) - 1)
#define BCOPY(p, s) b[j].sz = p + sizeof(s) - 1; COPY(b[j].bin, s)

static buf_t compile(byte *buf, int sz) {
    bin_t *b = malloc(sz * sizeof(*b));
    chk(b, "malloc");
    bin_t *jmp[0x1000];
    int j = 0;
    int k = -1;
    int n;
    for (int i = 0; i < sz; i += n, ++j) {
        switch (buf[i]) {
        case ',':
            n = 1;
            BCOPY(0, "\x31\xc0\x89\xc7\x48\x89\xe6\x0f\x05");
            /*
                xor eax, eax
                mov edi, eax
                mov rsi, rsp
                syscall
            */
            break;
        case '.':
            n = 1;
            BCOPY(0, "\x31\xc0\xff\xc0\x89\xc7\x48\x89\xe6\x0f\x05");
            /*
                xor eax, eax
                inc eax
                mov edi, eax
                mov rsi, rsp
                syscall
            */
            break;
        case '>':
            n = count(buf + i, '>');
            if (n == 1) {
                BCOPY(0, "\x48\xff\xcc");
                /*
                    dec rsp
                */
            } else if (n < 128) {
                BCOPY(1, "\x48\x83\xec");
                /*
                    sub rsp, ib
                */
                b[j].bin[3] = n;
            } else {
                BCOPY(4, "\x48\x81\xec");
                /*
                    sub rsp, id
                */
                *(adword *)(b[j].bin + 3) = n;
            }
            break;
        case '<':
            n = count(buf + i, '<');
            if (n == 1) {
                BCOPY(0, "\x48\xff\xc4");
                /*
                    inc rsp
                */
            } else if (n < 128) {
                BCOPY(1, "\x48\x83\xc4");
                /*
                    add rsp, ib
                */
                b[j].bin[3] = n;
            } else {
                BCOPY(4, "\x48\x81\xc4");
                /*
                    add rsp, id
                */
                *(adword *)(b[j].bin + 3) = n;
            }
            break;
        case '+':
            n = count(buf + i, '+');
            if (n == 1) {
                BCOPY(0, "\xfe\x04\x24");
                /*
                    inc byte [rsp]
                */
            } else {
                BCOPY(1, "\x80\x04\x24");
                /*
                    add byte [rsp], ib
                */
                b[j].bin[3] = n % 256;
            }
            break;
        case '-':
            n = count(buf + i, '-');
            if (n == 1) {
                BCOPY(0, "\xfe\x0c\x24");
                /*
                    dec byte [rsp]
                */
            } else {
                BCOPY(1, "\x80\x2c\x24");
                /*
                    sub byte [rsp], ib
                */
                b[j].bin[3] = n % 256;
            }
            break;
        case '[':
            n = 1;
            COPY(b[j].bin, "\x80\x3c\x24\x00");
            /*
                cmp byte [rsp], 0
            */
            jmp[++k] = b + j;
            break;
        case ']':
            n = 1;
            int d = jmpdist(jmp[k] + 1, b + j);
            if (d + 8 <= 128) {
                b[j].sz = 2;
                b[j].bin[0] = 0xeb;
                b[j].bin[1] = -(d + 8);
                /*
                    jmp ib
                */
                jmp[k]->sz = 6;
                jmp[k]->bin[4] = 0x74;
                jmp[k]->bin[5] = d + 2;
                /*
                    je ib
                */
            } else {
                b[j].sz = 5;
                b[j].bin[0] = 0xe9;
                /*
                    jmp id
                */
                if (d + 5 < 128) {
                    *(adword *)(b[j].bin + 1) = -(d + 11);
                    jmp[j]->sz = 6;
                    jmp[k]->bin[4] = 0x74;
                    jmp[k]->bin[5] = d + 5;
                    /*
                        je ib
                    */
                } else {
                    *(adword *)(b[j].bin + 1) = -(d + 15);
                    jmp[k]->sz = 10;
                    COPY(jmp[k]->bin + 4, "\x0f\x84");
                    *(adword *)(jmp[k]->bin + 6) = d + 5;
                    /*
                        je id
                    */
                }
            }
            --k;
            break;
        default:
            __builtin_unreachable();
        }
    }
    enum {
        hdrsize = 20,
        ftrsize = 5
    };
    n = hdrsize;
    for (int i = 0; i < j; ++i) {
        n += b[i].sz;
    }
    free(buf);
    buf = malloc(n + ftrsize);
    chk(buf, "malloc");
    COPY(buf, "\x6a\x01\x5a\x31\xc0\x48\x8d\xbc\x24\x01\x00\xff\xff\xb9\x00"
    "\x00\x01\x00\xf3\xaa");
    /*
        push 1
        pop rdx
        xor eax, eax
        lea rdi, [rsp - 0xffff]
        mov ecx, 0x10000
        rep stosb
    */
    k = hdrsize;
    for (int i = 0; i < j; ++i) {
        memcpy(buf + k, b[i].bin, b[i].sz);
        k += b[i].sz;
    }
    COPY(buf + n, "\x6a\x3c\x58\x0f\x05");
    /*
        push 0x3c
        pop rax
        syscall
    */
    free(b);
    return (buf_t){buf, n + ftrsize};
}

static void hdr_init(hdr_t *h) {
    enum {
        bottom = 0x400000
    };
    memset(h, 0, sizeof(*h));
    COPY(h->e.e_ident, "\x7f\x45\x4c\x46\x02\x01\x01");
    h->e.e_type = ET_EXEC;
    h->e.e_machine = EM_X86_64;
    h->e.e_version = EV_CURRENT;
    h->e.e_entry = bottom + sizeof(*h);
    h->e.e_ehsize = h->e.e_phoff = sizeof(h->e);
    h->e.e_phentsize = sizeof(h->p);
    h->e.e_phnum = 1;
    h->p.p_type = PT_LOAD;
    h->p.p_flags = PF_R | PF_X;
    h->p.p_paddr = h->p.p_vaddr = bottom;
    h->p.p_align = 0x1000;
}

int main(int argc, char **argv) {
    static const char *name = "e";
    chk(argc == 2, "argc != 2");
    FILE *f = fopen(argv[1], "rb");
    chk(f, "fopen");
    chk(!fseek(f, 0, SEEK_END), "fseek(SEEK_END)");
    buf_t b;
    b.sz = ftell(f);
    chk(b.sz > 0, "ftell");
    chk(!fseek(f, 0, SEEK_SET), "fseek(SEEK_SET)");
    b.buf = malloc(b.sz);
    chk(b.buf, "malloc");
    chk(fread(b.buf, 1, b.sz, f) == b.sz, "fread");
    chk(!fclose(f), "fclose");
    b = strip(b.buf, b.sz);
    b = compile(b.buf, b.sz);
    f = fopen(name, "wb");
    hdr_t h;
    hdr_init(&h);
    h.p.p_memsz = h.p.p_filesz = sizeof(h) + b.sz;
    chk(fwrite(&h, 1, sizeof(h), f) == sizeof(h), "fwrite");
    chk(fwrite(b.buf, 1, b.sz, f) == b.sz, "fwrite");
    chk(!fclose(f), "fclose");
    struct stat s;
    chk(!stat(name, &s), "stat");
    s.st_mode |= S_IXUSR | S_IXGRP | S_IXOTH;
    chk(!chmod(name, s.st_mode), "chmod");
    free(b.buf);
    return 0;
}

---

As a final test, I found an amazing program that computes the digits of \$e\$ infinitely, which gets compiled down to a 2233-byte executable.

(c) 2016 Daniel B Cristofani (not me)
http://brainfuck(dot)org/

>>>>++>+>++>+>>++<+[
  [>[>>[>>>>]<<<<[[>>>>+<<<<-]<<<<]>>>>>>]+<]>-
  >>--[+[+++<<<<--]++>>>>--]+[>>>>]<<<<[<<+<+<]<<[
    >>>>>>[[<<<<+>>>>-]>>>>]<<<<<<<<[<<<<]
    >>-[<<+>>-]+<<[->>>>[-[+>>>>-]-<<-[>>>>-]++>>+[-<<<<+]+>>>>]<<<<[<<<<]]
    >[-[<+>-]]+<[->>>>[-[+>>>>-]-<<<-[>>>>-]++>>>+[-<<<<+]+>>>>]<<<<[<<<<]]<<
  ]>>>+[>>>>]-[+<<<<--]++[<<<<]>>>+[
    >-[
      >>[--[++>>+>>--]-<[-[-[+++<<<<-]+>>>>-]]++>+[-<<<<+]++>>+>>]
      <<[>[<-<<<]+<]>->>>
    ]+>[>>>>]-[+<<<<--]++<[
      [>>>>]<<<<[
        -[+>[<->-]++<[[>-<-]++[<<<<]+>>+>>-]++<<<<-]
        >-[+[<+[<<<<]>]<+>]+<[->->>>[-]]+<<<<
      ]
    ]>[<<<<]>[
      -[
        -[
          +++++[>++++++++<-]>-.>>>-[<<<----.<]<[<<]>>[-]>->>+[
            [>>>>]+[-[->>>>+>>>>>>>>-[-[+++<<<<[-]]+>>>>-]++[<<<<]]+<<<<]>>>
          ]+<+<<
        ]>[
          -[
            ->[--[++>>>>--]->[-[-[+++<<<<-]+>>>>-]]++<+[-<<<<+]++>>>>]
            <<<<[>[<<<<]+<]>->>
          ]<
        ]>>>>[--[++>>>>--]-<--[+++>>>>--]+>+[-<<<<+]++>>>>]<<<<<[<<<<]<
      ]>[>+<<++<]<
    ]>[+>[--[++>>>>--]->--[+++>>>>--]+<+[-<<<<+]++>>>>]<<<[<<<<]]>>
  ]>
]

output

2.718281828459045235360287471352662497757247093699959574966967627724076630353547
59457138217852516642742746639193200305992181741359662904357290033429526059563073
... (forever)

Answer 1

You solved a tough problem and the question is a good one, before I wrote this answer I up voted the question. Obviously you have a good command of the gcc compiler, there may be issues with portability to other systems.

To be honest, just because the language being compiled is barely readable doesn't mean the compiler that translates it should be barely readable, in fact the opposite is true. The lack of vertical spacing as well as the complexity of some of the functions is troubling. The code is barely maintainable. One of the things a programmer or software engineer needs to keep in mind is that code needs to be maintained, and it may be necessary for someone besides the original author of the code to do the maintenance. In 6 months to a year, you might not be easily able to maintain this code yourself.

Static Function Declarations

It is unclear why all of the functions except main() are declared as static functions, since this program is a single module. Static declarations should only be necessary if the same function is defined in multiple modules in the program.

The Use of the Volatile Key Word

The volatile key word has a very specific use, it prevents a variable from being optimized out of the code when that variable may be affected by actions outside the code. It is used when the code is accessing hardware locations or in multi-threaded code. This code is not performing hardware I/O nor is it multi-threaded.

Enum Declarations

This enum declaration is in the in the body of the compile() function, it should be outside of the function so that it is reusable.

    enum {
        hdrsize = 20,
        ftrsize = 5
    };

In the C programming language enums are symbolic constants, which means they should be all capitals, it makes them easier to find when they are referenced.

Variable and Function Names

To write self documenting code variable on function names generally consist of full words, this code uses abbreviations for function names and enum values, and most of the variable names are single characters. An example of a badly named function in the code is the function static void chk(int ok, char* msg), a better name for this function might be test_and_report_error(). The function static int jmpdist(bin_t* x, bin_t* y) might be better named calculate_jump_distance().

Complexity

The function main() and the function static buf_t compile(byte* buf, int sz) are too complex (does too much). As programs grow in size the use of main() should be limited to calling functions that parse the command line, calling functions that set up for processing, calling functions that execute the desired function of the program, and calling functions to clean up after the main portion of the program. Each case in the switch statement in the compile function should probably call a function as well. The compile() function is 199 lines of code. A best practice in programming is to make sure any function fits into a single screen in an editor or IDE, generally this is 60 lines of code or less depending on the editor and the size of the computer monitor.

There is also a programming principle called the Single Responsibility Principle that applies here. The Single Responsibility Principle states:

that every module, class, or function should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by that module, class or function.

The macros COPY and BCOPY are also hiding the details of the implementation increasing the code complexity. BCOPY should probably be implemented as a function.

Missing Documentation / Comments

What does this code at the end of the compile() function do? It should be a function and should probably have some comments explaining what is going on.

    enum {
        hdrsize = 20,
        ftrsize = 5
    };
    n = hdrsize;
    for (int i = 0; i < j; ++i) {
        n += b[i].sz;
    }
    free(buf);
    buf = malloc(n + ftrsize);
    chk(buf, "malloc");
    COPY(buf, "\x6a\x01\x5a\x31\xc0\x48\x8d\xbc\x24\x01\x00\xff\xff\xb9\x00"
        "\x00\x01\x00\xf3\xaa");
    /*
        push 1
        pop rdx
        xor eax, eax
        lea rdi, [rsp - 0xffff]
        mov ecx, 0x10000
        rep stosb
    */
    k = hdrsize;
    for (int i = 0; i < j; ++i) {
        memcpy(buf + k, b[i].bin, b[i].sz);
        k += b[i].sz;
    }
    COPY(buf + n, "\x6a\x3c\x58\x0f\x05");
    /*
        push 0x3c
        pop rax
        syscall
    */
    free(b);