Introduction

The Brainfuck (BF) programming language is an esoteric programming language that is essentially impossible—or at least highly impractical—to actually write useful programs in. Even if you became a very skilled programmer in this language, the resulting programs would be incredibly slow to execute. Despite this, many programmers have challenged themselves to write stunning pieces of code just for fun or for the learning experience it offers. Doing so teaches us about computer architecture, compilers/interpreters, memory, pointers and much more. For more information on the language itself, see Section Brainfuck.

Goals

The main goal of this project was to build a computer that can actually run BF code natively. Normally, after having written some new piece of BF, the programmer presents this code to some program that either compiles it to an executable native to the host architecture or interprets it in a virtual BF machine. However, instead of treating BF as a language that requires compilation or interpretation, why not view it as the instruction set of a yet-to-exist BF CPU?

Our goal was to build this BF-CPU without making use of any programmable chips, relying solely on Transistor-Transistor-Logic (TTL) chips such as registers, buffers and (de)multiplexers in addition to the necessary RAM and ROM. The computer was to be implemented entirely on breadboards, as it was inspired by Ben Eater’s 8-bit breadboard computer [5]. It should be able to run any compliant BF program directly, as long as it fits in the program ROM and does not exhaust the available amount of memory or stack-space. In other words: the computer should be capable of running canonical BF without doing any preprocessing steps like pre-calculating jump-addresses.

Outcome

Over roughly 2.5 years (intermittently), the design evolved into a stable microcoded CPU with a Harvard-like memory map, a two-phase clock that can drive the system at over 250 kHz, and a supporting software toolchain (assembler, EEPROM programmer, microcode compiler and emulation library) that makes prototyping, editing, assembling and flashing programs and microcode practical. It has a sophisticated IO module that handles input (both random numbers and keyboard input) and output (to a $20\times4$ character LCD display). This IO module is driven by an ATmega328P to be able to manage IO buffers, implement the PS/2 protocol and drive the screen, in addition to managing all the IO settings (echo, autoscroll, output modes, etc.) and providing a user interface for selecting the active program at runtime. A deliberate choice was made to use a programmable chip in this case, since it is not really part of the CPU itself and makes the IO capabilities a lot more advanced and convenient. To the CPU core, the outside world is a black box that accepts certain control signals and acts accordingly, similar to how the BF input and output commands (. and ,) interact with an abstract external world.

The machine has been tested by running many different BF programs on it that can be found online, validating its stability and BF-standard conformity (if such a thing even exists). The source code for all supporting software is available on GitHub at https://github.com/jorenheit/bfcpu.

Document structure

• Section Brainfuck recaps the BF programming language: how does this language work, what does a simple interpreter look like and how does it relate to the architecture of Synapse-191?

• Chapter Synapse-191 Architecture describes the architecture from a modular perspective: what is the purpose of each of the high-level modules, what control signals do they accept and what actions do they perform when clocked?

• Chapter Opcodes and Control Sequences explains microcode and control sequences; how do all these signals and modules work together to perform the computations necessary to run BF programs?

• Chapter Hardware Implementation discusses hardware implementation: what kinds of chips and techniques were used to implement the modules on a hardware level?

• Chapter Supporting Tools covers supporting utilities, like the assembler, microcode compiler, EEPROM programming utilities, etc.

• Chapter Runtime Results goes through a number of test programs that were used during development.

• Chapter Introduction to Acus introduces Acus, the higher-level compiler targeting BF.

• Chapter Reflection lists a number of possible improvements that could still be implemented in the future, as well as some more general final thoughts.

• We conclude in Section Conclusion with a brief retrospective on the project.

Brainfuck

Language Description

Brainfuck is a popular esoteric programming language. Just like any other programming language, it allows the programmer to write programs consisting of commands that are executed in order. The key limitation is that the language provides only eight commands to the programmer, all written as a single character: “+-<>[].,”. Each of these commands corresponds to an operation on an array of memory or a pointer, pointing to some location within this memory. At the start of the program, every cell in (an infinite amount of) memory is initialized to 0 and the pointer is pointing to the very first element (index 0, see Figure 1).

The commands then modify the contents of memory or the pointer as follows:

• + : add 1 to the current cell;

• - : subtract 1 from the current cell;

• < : move the pointer 1 cell to its left;

• > : move the pointer 1 cell to its right;

• [ : if the current cell is nonzero, continue to the next instruction. Otherwise, skip all instructions and continue beyond the matching closing ];

• ] : if the current cell is zero, exit the loop and continue to the next instruction. Otherwise, loop back to its matching opening [;

• . : send the value in the current cell to the output device;

• , : read a value from the input device and store it into the current cell.

Although the instruction set is minimal, it has been proven to be sufficient for performing any possible computation or program, a property known as Turing completeness [2]. The catch is that this requires an unbounded (or infinite) amount of memory, which is obviously impossible. However, the same caveat holds for traditional systems, so we should be safe to assume that BF is Turing complete for all practical purposes.

Interpreters

To run a BF program, one usually feeds these commands into an interpreter written in a more common language. These interpreters are very straightforward to write. Listing 1 shows a very basic implementation (about 40 lines) of a BF interpreter written in C. This implementation initializes a block of memory to zero and defines a pointer to its first element. This pointer can be incremented or decremented to move along the array, increment or decrement the value it points to, or print it to the standard output. Most of its complexity is embedded in the handling of the loop operators. When an opening bracket is encountered, the index of this instruction is stored in a jump table. When control reaches its matching closing bracket and the value of the cell pointed to is nonzero, this stored index is reloaded in order to return to the start of the loop. When skipping a loop, i.e. the current cell holds a zero when the opening bracket is evaluated, all commands up to and including the matching closing bracket are skipped.

void bfint(char const *program) {
  unsigned char mem[MEM_SIZE];
  memset(mem, 0, MEM_SIZE);
  unsigned char *ptr = mem;

  int jmp_table[JMP_TABLE_SIZE];
  int jmp_index = 0;

  int program_size = strlen(program);
  int index = 0;

  while (index < program_size) {
    switch (program[index]) {      
    case '+': ++(*ptr); break;
    case '-': --(*ptr); break;
    case '<': --ptr; break;
    case '>': ++ptr; break;
    case '.': putchar(*ptr); break;
    case ',': (*ptr) = getchar(); break;
    case '[': {
      if (*ptr) jmp_table[jmp_index++] = index;
      else { 
        int count = 1;
        while (count != 0) {
          switch (program[++index]) {
          case '[': ++count; break;
          case ']': --count; break;
          }
        }
      }
      break;
    }
    case ']': {
      --jmp_index;
      if (*ptr) index = jmp_table[jmp_index++];
      break; 
    }}
    ++index;
  }
}

When the Hello World program from Wikipedia [1] is fed into the function of Listing 1, it prints out the string Hello World!, as expected.

$ ./bfint "++++++++[>++++[>++>+++>+++>+<<<<-]>+>+>->>+[<]<-]>>.> \
           ---.+++++++..+++.>>.<-.<.+++.------.--------.>>+.>++."
Hello World!

Brainfuck Instruction Set

BISC

Instead of viewing BF as a language that needs to be compiled or interpreted on a traditional machine, it can also be seen as an instruction set to a processor, built according to the BF architecture described above; let’s refer to this as a Brainfuck Instruction Set Computer (BISC). A true BISC implementation would operate on the basis of only the 8 aforementioned instructions, which is truly tiny compared to more conventional instruction sets such as those implemented by modern processors or even microcontrollers and older 8-bit systems. Broadly speaking, Complex Instruction Set Computers (CISC) are designed to do as much work as possible in the least number of clock cycles, whereas Reduced Instruction Set Computers (RISC) focus on having a small instruction set with basic operations. For comparison, the x86 instruction set is massive with over 2000 instructions implemented in hardware (depending on the way you count, [6]), whereas RISC-V processors have a fixed opcode width of only 7 bits, allowing for a maximum of 128 different opcodes [7]. BISC is therefore tiny even compared to the smallest instruction sets in use today. While compact, such a small instruction set inevitably leads to less efficient execution; a smaller number of instructions simply means you need more of them to perform meaningful computations, which is reflected by the fact that complex BF programs are typically very large in size.

Harvard Architecture

Modern computers are built according to the von Neumann architecture [4], which specifies a CPU (containing registers and an ALU), a single unit of memory and input/output devices. In this architecture, both the program’s instructions and data are stored in RAM. This allows programs to change their own code at runtime (self-modifying code) because the program itself is data in a sense. This model does not naturally fit the Brainfuck model, which has a strict separation between instructions and data; the data pointer can never point to the instructions that govern it. This is why a Harvard architecture was adopted. In the Harvard architecture, two kinds of memory exist: program memory containing the instructions—stored in read-only memory (ROM)—and data memory—stored in random-access memory (RAM)—containing the modifiable data (Figure 2).