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)