There are two ways of getting a programming language to run – interpreting, sometimes called a virtual machine or emulator, which essentially has a big switch statement which looks at every instruction and acts accordingly; and compiling, where the code is translated into the native machine code.
Interpreters are a lot easier to make than compilers, but they're vastly slower when it comes to running the program.
Since it's the kind of quirky thing that entertains me, I've made many brainfuck interpreters on different platforms, for fun. But in actual fact, Brainfuck was designed as a language that's very easy to compile. I had never written a compiler before. Until today!
To compile C, I'm using lcc-win32, and to assemble assembly, I'm using FASM.
An .EXE as we know it is called a "Portable Executable" by Microsoft. There is a lot of overhead in there. Even a hello world program, compiled in C, seems to end up about 3kB. I don't know the spec too well (or even at all, until yesterday) but there are multiple 'sections', which can be executable code, data, resources or import tables. An import table pulls in DLL files in order to call their functions.
It's usually possible to get a compiler to output an .ASM file, but lcc seems to output an inconveniently different syntax to FASM (even with reversed argument order). But after some tinkering I was able to get a simple assembly console application working:
format PE console entry start include 'win32a.inc' ; Import section section '.idata' import data readable library kernel32, 'kernel32.dll', msvcrt,'msvcrt.dll' import kernel32, ExitProcess, 'ExitProcess' import msvcrt, getchar, 'getchar', printf, 'printf' section '.text' code readable executable start: push ebp mov ebp, esp call [getchar] push eax push mystr call [printf] add esp,8 mov esp, ebp pop ebp call [ExitProcess] mystr: db "You typed 0x%2x",10,0
which assembles to this glorious little program:
It takes keyboard input and outputs a hex value.
The first half of the code is all directives about what goes into the exe file. 'PE console' is our command line, Portable Executable format. "start" is my label at the first line of code, which is pointed to by a field in the header. 'win32a.inc' is a bit like windows.h, but doesn't actually translate to any code as far as I'm aware, just definitions.
The import section brings in ExitProcess, without which our program would hang at the end, and our IO functions. Importing getchar and printf, which we're familiar with from C, turned out to be easy, and means outputting a number as hex is a piece of cake.
It's apparently the etiquette that every program or routine should preserve the stack pointer on starting, and restore it at the end. To be clear, in this syntax, the first argument is the destination, and the second argument is the source (opposite to what lcc was using, grrr). By convention, when you call a function, its return value is in the register eax. The arguments to the function are pushed onto the stack before calling it, so afterwards we have to add to the stack pointer to restore it (We're 32-bit here, so two arguments means 8 bytes).
Square brackets around a register or label use it as a pointer, much like the & symbol in C. Anything followed by a colon (:) is a label. The label at the end points to our string, which is included as data in the code section. Really I suppose it should have gone in its own data section.
Fantastic, so to produce a simple compiler we need to come up with blocks of assembly instructions that correspond to brainfuck operations, and then it's just a matter of search-and-replace! I used the register ebx as the pointer to memory, so the > and < instructions become
inc ebx and
dec ebx, while the + and - become
inc [ebx] and
The comma needs to call getchar, which destroys the ebx register, so we have to push it and pop afterwards:
push ebx call [getchar] pop ebx mov [ebx], al
al is an 8 bit register which points to the same memory as eax. So getchar returns in eax, but the mov instruction now only shifts the lowest 8 bits. Since the memory is (I decided) an array of 8 bit values, moving the full 32 bits would wipe the 3 cells preceding it.
Dot (putchar) is called in much the same way, but the loop instructions are where it becomes complicated. If the cell is zero, the opening loop must jump to the end, and if the cell is non-zero, the closing loop must jump to the beginning. In the interpreter, at an opening bracket it has to read forwards in the program, keeping track of 'depth' every time another loop opens, until it finds the corresponding closing bracket to jump to. For our search-and-replace ASM construction, we can use labels. This means the actual jumps in the compiled code become almost instantaneous, instead of having to iterate.
Here it is:
Paste the assembly output into FASM and it should produce a perfectly working .exe file.
To simplify things, I opted to always give the [ instruction a 'far' jump. This slightly pads the code size, but means we can insert dummy bytes, push the address onto a stack, and when we reach the closing bracket we will know both addresses, so we can calculate the distance and fill in the jump details for both. The closing bracket hence can make use of 'near' jumps. (To use foward 'near' jumps would require multiple passes (and indeed FASM iteratively passes the file until all labels are resolved) but I'm not convinced the reduction in code size is worth it.)
There's also a whole lot of header data to fill in. I tried looking for references for this, but most of them were pretty difficult to make sense of. Some sources claim the checksum algorithm is proprietary (??) and others say it isn't used. There is data in the checksum field that FASM produces, it changes from program to program, but if I manually edit it to something different, the .exe still runs.
This image was found on a blog, which didn't give a source for it, so I won't either:
The timestamp is easy. The other fields... well, the easiest thing to do is just look at what FASM is outputting and copy it. I wrote a few assembly files of different lengths (the 'repeat' directive is useful) and watched how the fields changed. We only need to reverse-engineer the bare minimum in order to get a working exe file.
I used lcc to produce the compiler, about 200 lines of C code. It's now on github for you to enjoy. There's no limitation on the pointer, if the brainfuck code tries to access a negative index windows will probably throw a seg fault ("asdf.exe has stopped working, windows is searching for a solution to the problem"). The upper limit is 32768 and the cells are 8-bit.
To use, call the program like
bf.exe program.bf output.exe
Then run output.exe, and be amazed.
I must say it's remarkably satisfying. The first hello-world in compiled brainfuck was most entertaining. Additionally, and as we would hope, really intensive programs like the mandelbrot plotter run super quick (1.4 seconds on my machine).
To do: Add a compile-time flag to set the cell size. Would have been quite easy if I'd thought of it at the beginning. Some programs depend on bigger cell sizes to work, but really I feel brainfuck is very much an 8-bit affair.
A debugger with memory inspection, breakpointing, run-to-cursor and so on would be quite useful. But I'm not interested in making that (yet). I just want a glorified version of notepad that invokes the compiler. After my first attempt mucking about with the windows API (making a calculator) I feel this is the perfect opportunity to further develop our err... for further mucking about.
Notepad is just a big "EDIT" window (a textarea) with some extra stuff. The file/open/saveas dialogs are standard calls. This is pretty standard stuff and there are lots of tutorials about it. I took one of the first search results ("theForger's Win32 API Programming Tutorial") as a starting point. On window resize, the edit box is resized accordingly. And a resource file is used to manage the file menu.
It's interesting to see what a default edit box can and can't do. Ctrl+C will copy the selected text, Ctrl+V will paste it, but Ctrl+A won't do anything. But there is a select-all option in the default right-click context menu. Similarly we want Ctrl+O, Ctrl+N, and Ctrl-S to invoke the file menu items, so the first thing to do is add these using "accelerators". Accelerators can be loaded from the resource file and seem pretty straight forward, just a list of key combinations and IDs. We give them the same IDs as the file menu is using. We also need to add a line to our message loop, calling TranslateAccelerator(). As you can probably imagine, this looks at keyboard events coming in, and if they match the keystrokes listed, sends the appropriate WM_COMMAND message. For select-all, in our switch statement we send an EM_SETSEL message with parameters 0 and -1.
Next thing to add is accepting a file-open argument. When you drag a file onto an application icon, or select "open with", the filename gets passed to the program as its command-line argument. We don't have the usual argc and argv in our main function, but WinMain has an lpCmdLine argument which contains the filename passed. I copied this into a global variable, then in WM_CREATE, after we've made the edit box, we can load the file if present.
There are other reasons to remember the working file name. We want an option to save without a save-as dialog each time. We also need to come up with a suitable filename for the output of the compiler. Another global variable we need is to keep track of whether the file has changed since it was opened or last saved, and if so, we can put a little asterisk in the title bar, and give warning messages before closing or opening a new file. We have to be sure to pay attention to the difference between 'no' and 'cancel', but it's all pretty simple stuff.
I noticed right away that if you alt-tab onto the window, you can't just start typing. In the WM_ACTIVATE event we need to explicitly SetFocus() back to the edit box to fix this. Other simple things I added: an icon (I just took the mitxela.com favicon because I'm incorrigibly lazy), loaded as a resource; and a status bar, which is – you guessed it – another type of window. I set the text, when needed, to the length of the text selection, because that's invaluable information when writing brainfuck. When to update the status bar is a difficult one. I ended up having to call our UpdateStatusBar() function on all keydown and keyup events, and also on WM_MOUSEACTIVATE and WM_CTLCOLOREDIT. The latter two are needed for the status bar to reflect text selections done using the mouse.
All right, now for the big kahuna...
system("bf.exe");or ShellExecute() or whatever. We want to invoke the compiler in the background, capture its standard output and if there were no errors, then we can execute the resulting file.
CreateProcess() is a more flexible way of launching another application. Its last two arguments are references to structs: StartupInfo and ProcessInfo. While the process is running, we can pass the process info to WaitForSingleObject(), which will halt our code until the compiler has finished. This does mean the application will freeze if the compiler takes a long time, but even on the longest programs it seems almost instantaneous. Perhaps next time we can make a loading-bar dialog. There's also a Creation Flags parameter to CreateProcess, in which we can signal the process not to create a window. Without this, the instant compilation means a console window flashes on the screen for a split second, which is just annoying.
One member of the StartupInfo struct is hStdOutput, a handle to its standard output. Sounds good, but to this we need to assign a handle populated by the CreatePipe() function. And this function, in turn, takes a struct argument of type SECURITY_ATTRIBUTES. This whole struct is just to let us set a boolean, bInheritHandle = true.
It's rather a lot of code for the simple task of redirecting a process' output, but now that we have a handle to it, after we've called CreateProcess() and waited for it to terminate, we can read the handle with ReadFile(). The return code of the compiler, as is customary, is zero on success, so we can take action according to the response of GetExitCodeProcess(). If it failed, we read the pipe and display the error in a message box. If it succeeded, we can now create another process, launching the newborn application, this time letting it form a new window and existing on its own.
Most excellent. We have learnt about exe files and windows programming and created a tool which may not be entirely useless to potentially more than one person. Potentially. I, for one, have enjoyed the journey, regardless of how pointless it was, and though I'm now going to go off and do something completely different, I may return and add some more features, possibly even useful ones. Maybe!
The source code and the executable download is all on github.