A Bytecoded Brainfuck

A Bytecoded Brainfuck

I've this old program from when I was playing with language implementation ideas. It's a Brainfuck "interpreter" that executes source much like bytecode, except the source is concatenated onto the executable itself.

Weirdly enough it works very well, though I hate how I implemented the looping constructs [ and ]. They skip over characters until a "matching" bracket is found, recording how many levels of nesting there are.

The Program Itself

If wtbrainf is concatenated with a Brainfuck script, the resulting file will run the script when executed.

Example command: "cat wtbrainf script > demo". Running demo will execute the script itself. This will only work so long as the final executable is less than 32kb. Any more will require the corresponding ELF header settings to be adjusted (but really, whos coding such large scripts in Brainfuck? someone will prove me wrong eventually).

This works for simple programs, but gives weird results for test programs, especially the ones testing for wraparound, which I don't recall implementing in this version.

The Implementation

A trick with ELF is used to allow it to load more data than what existed when the executable was first created. Surprisingly my system doesn't complain when a larger filesize is specified in the ELF headers than the file's true size. It just loads what it can and ignores what's missing.

Now regarding the interpreter itself:

I am using three separate lookup tables to map the script characters to code handling them: one table for regular mode; another for when [ looks forward for the matching ]; and another for when ] looks backwards for the matching [.

Why am I doing it this way? Because writing a dispatch function to test for each character in machine code is not something I enjoy. A lookup table is easier to separate the logic into independent words and works smoothly with ASCII characters.

As an additional bonus, the specific approach used resembles an indirect threaded forth, where each function handles reading and executing the next word, except it's relying on a lookup table rather than memory locations. This lets me use a small amount of boot code to setup the bytecode instruction pointer and start executing it directly.

Normal Mode

This contains the normal behaviors for the following Brainfuck instructions: '>'; '<'; '+'; '-'; ','; and '.'. The last two, '[' and ']', test the currently pointed to data and, depending on the result, switches into the corresponding modes.

Other characters are treated as comments and merely execute the next character.

[ Mode

[ instructions increment the nesting counter.

] instructions decrement the nesting counter and, if zero, switch back to Normal mode.

All other characters are skipped.

] Mode

In this mode, instead of executing the next instruction, execution proceeds backwards.

] instructions increment the nesting counter.

[ instructions decrement the nesting counter and, if zero, switch back to Normal mode (Note: my implementation has to skip the current instruction when it does, otherwise it would execute the matched [).

All other characters are skipped.

How I Generate The Executable

Naturally I used a custom executable format to play with it without stressing over ELF details, but I figured before sharing it I should migrate it so it can be tried out. Took me a bit to recall what everything is (mostly trial and error), but I finally got it working on my Linux system. It should be mostly portable, but I have no idea how much.

And the script to build the executable is written in my personal Forth, so while it is unusable outside of my system, I believe it would be interesting to disect.

This generates a 4097 byte executable.