Brian Robert Callahan

academic, developer, with an eye towards a brighter techno-social life

2021-07-10
I wrote a 231-byte Brainfuck compiler by abusing everything

We wrote a Brainfuck compiler back in April. That one developed a simple architecture to support multiple backends. Today, I want to write a new Brainfuck compiler. One that can only run on a single system, OpenBSD/amd64. And one that is as small as I can possibly make it. I broke into the sub-256 bytes club with my compiler, so I thought it was worthwhile sharing and talking about how I was able to pull it off.

While this works on my machine, there may be subtle differences about how your machine works that cause this compiler not to work. Make sure to check your machine's behavior if there are any differences!

We are optimizing exclusively for size. That means that we may make decisions that are less performant than other ways of writing a Brainfuck compiler. That's OK.

The assembly code will be written using AT&T syntax. Last time I had a blog post with assembly code, someone complained that it was not Intel syntax. I am not much bothered by either and I teach my undergraduates both syntaxes because I think it is important to be able to read both. If you are an Intel syntax person, take this post as an opportunity to improve your AT&T syntax skills.

Reviewing Brainfuck

Let's quickly review the syntax of Brainfuck so we know what we need to implement. The table below presumes that we are translating Brainfuck to C, have a global array acting as the Brainfuck tape, and have a pointer, *p, that is intialized to the beginning of the array.

Choosing an implementation language

I think the only way we stand a chance at creating a compiler as small as possible is to use hand-optimized assembly. Those precious bytes aren't going to save themselves!

Symbol	C equivalent
`<`	`--p;`
`>`	`++p;`
`-`	`--*p;`
`+`	`++*p;`
`,`	`*p = getchar();`
`.`	`putchar(*p);`
`[`	`while (*p) {`
`]`	`}`

We will be using the GNU binutils for our assembler and the OpenBSD system linker, which is LLVM lld, for our linker. I am using the GNU assembler from ports, which is a much newer version of the assembler. This newer assembler is a little bit smarter when it comes to encoding and that ends up saving a byte for us down the line. I'll point it out when we get there.

Coding our strings

Our compiler will compile Brainfuck to C. I chose C because it will allow us to have some of the smallest output code, and by extension the shortest strings needed to have built-in to our compiler. We will use the table above for our translation.

The top is some boilerplate to inform the toolchain that we have a global symbol named main and it (and everything else, for that matter) lives in the text section of our binary.

Beginning with .LSprototype is our strings. Labels beginning with .L are considered local labels for ELF targets like my machine. After each string I put a comment with the number of characters in the string. We will use the OpenBSD kernel facilities for reading and writing, and the write(2) system call has a parameter for number of bytes to write. Yes, we could write a strlen(3) function, and in fact we did that for our echo program. However, writing such a function would take too many bytes compared to simply shoving the correct value into the register.

The .LSprologue string is separate from the rest of the .LS strings because the way I organized the compiler the prologue is used directly and for all other strings we index into the string starting at .LS.

You'll also notice I am using the .ascii pseudo-op rather than the .asciz pseudo-op. This means that there is no NUL-termination of any of these strings, so they are not C strings. Since we are providing the exact number of bytes to write with each write(2) call, we can get away with this and save a number of bytes in the process.

We are also leaving them in the .text section. That technically means they are code. We could place them in the .rodata section but since these string are never written to, I think it is fine.

We can also see some more byte-shaving at work. While we are compiling to C, we didn't specify which standard we were targeting. We are going very old by having implicit ints everywhere. We are also going to be implicitly declaring getchar(3) and putchar(3) which is invalid in C99 and later, according to clang. So we will target C89 and/or K&R C.

As a result of the implicit ints the cells on the Brainfuck tape are 32-bits in size. There is no requirement for any particular cell size, so this is acceptable from a Brainfuck perspective.

I also made the getchar and putchar strings equal length, even though the putchar string is actually one character shorter. We will spend a byte now to save several bytes later.

Reading code into a buffer

Our parser needs to read in the program one character at a time and process each character. If it is one of the Brainfuck characers, we output the appropriate translation, otherwise we move on to the next character. We are going to take advantage of the fact that we can read from stdin and write to stdout without having to set anything up outselves; these facilities are set up for us by our environment.

We will also need to look up the syscall numbers for read(2) and write(2), which are 3 and 4.

We must read in a character before we can parse it and write anything. Our read can look like this:

We can take advantage of some assumptions on our system for this to work. On our system all general-purpose registers are initialized to 0 by the environment before program start. The movb instructions require only 2 bytes but do not 0-out the remainder of the register. If there was something already in %rax or %rdx above the lowest byte, it would remain as-is. But since our environment set these registers to 0, we are OK. These movb instructions are 2 bytes each.

We also chose to use xorl instead of movb for the %rdi register. This is because you cannot use movb on %rdi since it is at its smallest a 16-bit register. Since we are making it 0, xor'ing any 32-bit register with itself is the smallest way to do this at 2 bytes.

The leaq instruction is expensive at 4 bytes. It's actually one of the smallest versions of this instruction and we will see a 7-byte version later. Finally, we need to call the syscall for 2 bytes. That's 12 bytes total to get a character from stdin.

We are also assuming that our environment set up some stack for us and that our stack pointer points to something reasonable. That happens to be true. As we learned before, the environment does contain our argc and argv variables and that is the case here too. So we have a reasonable stack pointer.

While it is not directly related to reading in a character, it turns out that %rdi stays the same across read(2) calls, so we can increment it to prepare for an upcoming write(2) call. Incrementing is 2 bytes, which is the smallest way to turn a 0 into a 1 for us. Even in the case where we do not actually end up writing anything, for example because we read in a comment character, it does not much matter since we xor the register before the read(2) call every time.

Checking for EOF

Now would be a good time to check if we are at the end of the file, since if we are we have finished our work and should exit the program. Fortunately, read(2) returns the number of bytes read in %rax. If that number is 1, then we are not yet finished. Otherwise, if it is 0 or -1 then we are finished. A 0 means end of file and a -1 means an error occured. We don't actually care if we reached end of file or encountered an error. Both of those mean it is time to exit for us.

Quick aside: The System V AMD64 ABI calling convention

Our machine uses the System V AMD64 ABI calling convention. This dictates how our registers are used and how registers are saved or not across function calls, including syscalls. For us, we need to know that %rax will contain the return value of a call, so we should presume that it will change after each call. Additionally, %rax contains the syscall number prior to making the syscall. The calling convention also says that the %rbx, %rsp, %rbp, and %r12-%r15 registers must be restored to their original value by the callee if they are used. That means as far as we are concerned, we can use those registers across calls and presume that their value will stay the same. Any other registers may be clobbered by calls. We must also respect the registers used for call parameters. Since read(2) and write(2) use three parameters, we must make sure to use %rdi, %rsi, and %rdx for those parameters, like we did with our read(2) call above.

It happens to be the case that that %rdi and %rdx do not get clobbered by read(2) and write(2) calls on our machine, which we will use to our advantage.

Checking for EOF, part 2

That's all we need. Since %rdx does not get clobbered on our system, we know it is 1. If %rax is less than that, we know we either reached the end of the file or an error occured. In that case, we should jump to the code that exits the program.

Parsing the input

Something that we need to know is that the smallest cmp is when you compare a byte against %al. But as of now, %rax contains the return code of the read(2) call. We stand to save eight bytes using the smallest cmp. We will end up spending three bytes to save eight bytes, which is great.

We can make this happen by slightly tweaking our end of file check and then parsing our input after the end of file check:

We can xchg to get our smallest cmp. This is the reason for the newer GNU assembler. The older assembler in base always encodes this to a 2-byte sequence but the newer assembler is smart enough to know this can be encoded as a 1-byte instruction and does so. We then put the character we read in into %rax and preload the address of all our strings via a 7-byte leal. That's very expensive, in fact it is the most expensive instruction we will encounter. But it is a necessary evil for us. Now we perform our end of file check and if we are not at the end of the file we continue on figuring out which character we have and what to do with it.

Processing each possibility

Let's leave the end of file processing for later and now tackle the Brainfuck symbol processing. There are eight symbols we need to handle:

Let's take a look at just this for right now. This code handles both the < and > symbols. Recall that .LS contains all our strings, prologue notwithstanding. The first character of .LS corresponds to the < symbol. We are calling that the .Lleft label. That has an offset of 0 so we immediately move to telling write(2) we want to write 4 characters and then head to the syscall. If we instead see a > that's the .Lright label and we need to offset the starting point of the string by 4. We then fall through because both outputs are 4 characters in length so we can combine the code to save bytes.

We will use these tricks a few more times. Let's continue writing the symbol processing code:

Let's stop here too and take a look at one more trick. Both .Ldec and .Linc output strings that are the same length. We want to be able to combine the code like we did in the .Lleft and .Lright case. However, we don't have an index of 0 for either. We get around this by creatively subtracting the length of the string from the offset of the string farther from the beginning of .LS to get the offset of the string closer to the beginning of .LS and then fall through from there. These subtractions and additions, because they are within the range of -128 and 127 all encode to 2 bytes.

Exactly the same tricks as .Linc and .Ldec. Note though that if I did not extend the putchar string by one character at the beginning, we could not use any of these tricks and it would cost us a whole lot more than the one byte it cost to elongate the putchar string.

Unfortunately, we cannot use the fall through trick here but there are some other tricks we can use. We use the fact that all our general-purpose registers are initialized to 0 and the fact that %rbx is saved across calls to just start using it effectively out of nowhere to act as our loop counter. The .Lopenloop label is otherwise straightforward.

The .Lcloseloop label has an additional trick. Because we want to have a good compiler that has proper return values, 0 for success and 1 for failure, we decrement the loop counter and check to see if it has fallen below 0. If it has, there is an imbalance of brackets and we should stop processing and error out. Unfortunately, dec preserves the value of the carry flag, so we cannot use it to determine if we have gone below 0. However, it alters all other flags and we can use the sign flag to check if we have gone negative. The js opcode jumps if the sign flag is set, which it only will be if we have gone negative. We can avoid a cmp against -1 this way. Fortunately, %rdi has already been set to 1 and is exactly the value we want for _exit(2) when we error out so we do not have to make any adjustments to %rdi. The rest is straightfoward.

Writing output

We will use the fact that stdout comes available to use from our environment without us having to do anything and as such we will write our compiled code to stdout. We are also going to use another trick here: we will place the .Lwrite label between the .Lparse and .Lright labels. This is because if you have a jmp that is within the range of -128 and 127 bytes, that encodes to a short jump which is only 2 bytes. That is the smallest jmp there is. We want all our jmps to be short jumps. Our .Lwrite labels ends with a jmp to .Lparse in order to read in the next character and if it came after all the code we just wrote, it will be more than -128 bytes away.

That's it. All the writes have to put 4 into %rax, make the syscall, and then read in the next character.

Dealing with end of file and exiting

Now let's write the code to handle end of file and the code to handle exit, since we will use some fall through to handle them. Let's also put this new code immediately after .Lwrite and before .Lright, again to ensure all our jmps are short jumps.

When we reach the end of the file, we need to make sure our loop counter is 0. If it is not, we have a bracket imbalance and should error out immediately. Like before, %rdi happens to be 1 from the set up for the write(2) call so we do not need to make any adjustments.

The remainder of the .Leof label is writing the C epilogue. It then sets %rdi to 0 because we are going to exit successfully and falls through to .Lexit which sets the syscall number to the _exit(2) syscall and calls it, which exits the program.

Writing the prologue

The last thing we need to write in order to finish our compiler is the prologue. This code goes immediately after the main label and before the .Lparse label.

Our final trick is immediately popping the top of the stack into %rdi right at the start. As we learned before, our environment puts argc in there. So long as argc is 1, which it should be, that allows us to set up %rdi correctly for this initial write(2) call in just 1 byte. If not, well then your output will be incorrect. It is the one error that goes undetected by our compiler. We are going to accept that we have cut this corner.

Putting it all together

How many bytes is our compiler?

On OpenBSD, there is some mandatory overhead, 24 bytes worth. We will measure the size of our compiler three ways: by itself, with the OpenBSD overhead, and with all the ELF overhead.

Only 231 bytes! Not bad. If I remember correctly, supposedly the original Brainfuck compiler was 240 bytes.

So even if you insist that it is unfair that I excluded the OpenBSD overhead in my count, we still come in at only 255 bytes.

Well, 952 bytes. OK, that's where the ELF overhead gets you. I don't want to get out a hex editor and start whittling down all that. I am going to say it is good enough and giving us all permission to ignore all the ELF overhead.

Conclusion

It is time for me to put away the text editor. My target was 256 bytes and I just scraped by. Can you find additional bytes to shave off?

Update: A 207-byte compiler

I was able to save an additional jmp and an extraneous movb $1, %dl, saving an additional 4 bytes, which allowed me to add back one byte and change the initial popq %rdi to an incl %edi, guaranteeing that the initial prologue write will always work regardless of the number of arguments to the program and still save a byte. See it here.

I was able to save an additional byte by removing the extra space in the putchar string and using the last character in the getchar string to pad out the putchar string. As this is a ; character, in C that becomes an empty statement, which is legal C. This gets us down to 944 bytes with all the ELF overhead. See it here.

I was able to save an additional 11 bytes by removing the epilogue string entirely and simply using the closeloop string for the epilogue. It seems that clang does not miss it. That gets us to 936 bytes with all the ELF overhead. See it here.

I was able to save an additional 6 bytes adapting a suggestion offered by @isaacg1 on GitHub, which was to combine strings in a way that allowed us to eliminate the left and right strings entirely. It ended up being more complicated than the initial suggestion. Now down to 928 bytes with all the ELF overhead. See it here.

I was able to save an additional 2 bytes by flipping the last entry in the parser switch, saving a jmp. This was discovered when working with the QBE compiler backend. Now only 208 bytes! See it here.

I was able to save an additional byte by replacing a movb with an xchg. Now only 207 bytes! See it here.

Brian Robert Callahan

[prev]

[next]

2021-07-10
I wrote a 231-byte Brainfuck compiler by abusing everything

Reviewing Brainfuck

Choosing an implementation language

Coding our strings

Reading code into a buffer

Checking for `EOF`

Quick aside: The System V AMD64 ABI calling convention

Checking for `EOF`, part 2

Parsing the input

Processing each possibility

Writing output

Dealing with end of file and exiting

Writing the prologue

Putting it all together

How many bytes is our compiler?

Conclusion

Update: A 207-byte compiler

Brian Robert Callahan

[prev]

[next]

2021-07-10I wrote a 231-byte Brainfuck compiler by abusing everything

Reviewing Brainfuck

Choosing an implementation language

Coding our strings

Reading code into a buffer

Checking for EOF

Quick aside: The System V AMD64 ABI calling convention

Checking for EOF, part 2

Parsing the input

Processing each possibility

Writing output

Dealing with end of file and exiting

Writing the prologue

Putting it all together

How many bytes is our compiler?

Conclusion

Update: A 207-byte compiler

2021-07-10
I wrote a 231-byte Brainfuck compiler by abusing everything

Checking for `EOF`

Checking for `EOF`, part 2