A Brainfuck CPU in FPGA

About two and a half years ago, a wave of interest in electronics swept across the Budapest office of Intentional. We desperately wanted to create something tangible from first principles. The idea we settled on was to design and eventually build a CPU that uses Brainfuck as its machine language.

Looking back, it really was a case of people with insufficient knowledge trying to use inappropriate tools. But damn if we didn't have fun during the process! After filling a couple of notebooks with sketches, we ended up with an initial design in Logisim. It had horrible timing problems, of course, since too much of it was asynchronous. Before ironing out all the wrinkles, though, I remember Maya pointing at one of the lines tangled up on the screen, and saying "You guys realise this single line will be 16 wires if we actually want to solder this together, right?" So basically we gave up on building the thing. Later on, Maya and Encsé went on to enroll to a bachelor's program in EE as a hobby; and I decided to stick to discrete logic, ordered a bunch of 7400 TTL's and some LEDs and seven-segment displays and started wiring together much simpler circuits on breadboards. I never got to soldering, not to mention getting access to anything that could produce PCB's, Then as I moved to Singapore, I left all my electronics stuff at home, and put the whole electronics thing on the backburner indefinitely.

Then, a couple months ago I discovered the Papilio FPGA platform, which has this collection of nice IO daughterboards (called "wings") that snap right into it, no soldering or even wiring required. I ordered one with the LogicStart IO board which features, among other, more advanced stuff, eight toggle switches and four seven-segment displays. Perfect for my baby steps into the world of FPGA's!

So what else could my Hello World project have had been, than the Brainfuck CPU.

Basic design

We can use the Harvard architecture: since the Brainfuck language has no reflection capabilities, the program can be stored in ROM with no programmable access. Memory is implemented as a RAM of 32K 8-bit bytes. The CPU also has several internal registers:

• Internal state: As we will see, it takes several clock cycles for the CPU to execute a given Brainfuck opcode. Rather unfortunately, I ended up with 9 states, so I need 4 bits to store it.
• Program counter (PC): directly connected to the address pin of the ROM.
• Opcode register: loaded from the data pin of the ROM in the Fetch state.
• Memory pointer (idx): a 15-bit register that is directly connected to the address pin of the RAM.
• Data out register: for simplicity's sake, new values for RAM[idx], and the write enable leg of the RAM, are buffered
• Depth counter (DC): Used in the implementation of the [ and ] opcodes (see below)

Output is implemented by an 9-bit signal: 8 bits of data and an enable bit. When a . opcode is encountered, the CPU sets these 9 bits, and enters a special state until it receives an acknowledgment signal. Input is implemented similarily. On the actual board, the output signals are connected to the seven-segment display, the input signals are fed from the eight toggle switches, and the directional "mini-joystick" is used to acknowledge input/output.

Implementing [ and ]

Compared to a normal machine language, it's really just [ and ] that requires special handling. Everything else is just straightforward manipulation of either idx or RAM[idx] via incrementing/decrementing; or pushing data between RAM[idx] and the IO port. [ and ] are tricky because we need to search for their matching pairs, and pre-processing the Brainfuck program to attach pair addresses would be against the spirit of this (self-imposed) challange.

One solution would be to maintain a stack in a separate RAM, and push PC into it whenever a [ is encountered. In that case, ] is a simple matter of popping PC if RAM[idx] does not equal 0. However, here we've basically changed [/] from a while loop to a do while loop. So if RAM[idx] is 0 when we first enter the [, we have to scan the program forward to find its matching ].

For simplicity's sake, I decided not to worry about performance and skip the stack part, and just implement scanning in both directions. Scanning is where the DC register is used (explained here for [, but ] is similar): if the opcode is [ and RAM[idx] is 0, DC is set to 1, and the CPU enters a special skip-forward state from the next opcode. In this state, only [ and ] opcodes have any effect: they increment and decrement, respectively, the DC register. When DC gets to 0, we know we've found the matching ], and so we can go back to the regular fetch-execute cycle.

Lava → VHDL → Xilinx

I originally planned to implement the whole thing in VHDL, and compile that using the Xilinx synthesizer tools (since the Papilio One board uses a Xilinx FPGA chip). However, I've found VHDL to be quite a horrible language from a software programmer's point of view. The whole point, for me, of going from physical chips to FPGA's was to enable using abstractions to manage complexity; so why settle for a poor language like VHDL? Fortunately, there's a whole family of Haskell-embedded DSLs for hardware description called Lava. Of these, Kansas Lava seemed the only one actively maintained, and it already had support for a Xilinx dev board; so adding support for the Papilio was straightforward (see my kansas-lava-papilio package).

The complete code for my Brainfuck CPU (including IO via the LogicStart daughterboard) is available on GitHub. There are quite some rough edges left to file off; I'd say the most pressing is adding the ability to synthesize the program ROM separately from the CPU definition.

Videos

This first video shows a simple countdown (actually, count-up) program: ,[>+.<-]. I had to record these slightly out-of-focus, otherwise the seven-segment LEDs were hard to read.

Next up is "Hello world!":

And the final one shows Maya's solution to the 9-digit problem. This one really shows how slow this naïve, stackless implementation is.

Adventi Menger-szivacs

Az egész azzal kezdődött, hogy évekkel ezelőtt, amikor még nem is dolgoztam az ISC-nél, megkapták a kollégák a névjegykártyáikat, amikre persze semmi szükségük nem volt (egyébként azóta sincs). Mivel ez egy ilyen kreatív bagázs, csináltak belőle egy Menger-szivacsot, illetve annak egy elsőszintű közelítését. Ez ugyebár húsz darab, névjegykártyákból hajtogatott kockából áll.

Aztán pár hete, amikor megyek be, kiderült, hogy Maya és Encsé elkezdte a régi szivacs köré építeni a másodrendű közelítést, vagyis még tizenkilenc ugyanakkora, lyukas kockát. Ez már emberes feladat volt, a fél Netvisor hordta a felesleges névjegykártyákat, végül Zapéval és velem kiegészülve négyen fejeztük be, összesen három nap alatt (persze a három nap közben dolgoztunk is, ez nem a tiszta játékidő). A végeredmény elég impozáns lett:

Ezt az ötletet gondoltuk tovább Vikivel, és kitaláltuk, hogy készítünk egy hasonló adventi naptárat, persze ünnepi színes papírból:

Mivel 20 kis kocka van a nagyban, ezért még négyre szükségünk volt, hogy végül mind a 24 napra el tudjunk rejteni benne csokikat. Ezeket körben a tetejére raktuk, mert így oldalra lelógnak, és tök jól néznek ki.

A legnehezebb része a feladatnak az volt, hogy ne felejtsünk el minden dobozba berakni két kis csokit ahogy építjük, mert utólag nehéz lett volna pótolni. Nagyrészt belga csokit raktunk bele, kagylókat meg keserűcsokit meg narancsosat meg minden finomságot, közémixelve egy kis Rafaellót meg Rochét, hogy minden napra jusson valami meglepetés.

És most megyünk, és kibontjuk az első dobozt!

Update: Kikockáztam Encsét a fenti fotóból

Geekparty és egy breaking news

Múlt héten, csütörtökre raktuk a lakásavató geekbulit az ISC-s kollegákkal. A terv az volt, hogy spagettit és Guitar Herot tolunk az arcunkba, mindkettőt nagyobb mennyiségben. Végül mindkettő sikerült is.

Elsőre mondjuk gigászi feladatnak tűnt egyedül főzni hat emberre, már csak azért is, mert teljesen ismeretlenek voltak számomra az arányok. Ennek megfelelően sikerült is egy egész kiló pasta-t kifőzni, aminek a fele sem fogyott persze el, ráadásul a visionary leader-ünk hatására a lé, amiben a tészta főtt, viszonylag egyenletesen beterítette a főzőlapot. Viszont mentségére legyen mondva, hogy beszerzőmissziót szervezett az Ikeába, ahonnan feltehetőleg Büdåppest márkájú sajtreszelőt zsákmányolva érkeztek (kiváncsi vagyok, hogy vezethetett Zape, ha azóta se Maya, se Encsé nem nagyon akar beülni mellé).

Nyomkodom a "Műköggyé" gombot

A héten kétszer is volt alkalmam meglepődni, hogy valamilyen szoftver-termék Magától Működik™. Vagy én lettem túlontúl szkeptikus vagy szarkasztikus vagy whatever, vagy kézzelfogható a fejlődés...

Az első kedden történt, amikoris délutánra úgydöntött az irodai gépemen futó Outlook, hogy akkor ő nem kíván több levelet fogadni: mihelyst leszedte POP3-mal az első bejövő levelet, feljött az ismerős "szóljunk-e a Microsoftnak hogy megint híg fossal lett tele a pelus, hátha nem történik akkor se semmi" ablak. És ezt megbízhatóan csinálta, minden indításkor.

Egyszer sikerült olyan gyorsan megnyomni a "Kapcsolat nélküli munka" gombot, hogy nem szedte le a levelet, így legalább el lehetett indítani. Aztán jöttek a Microsoft szoftverekkel eltöltött évtizednyi tapasztalat eredményei: indítsuk újra a gépet, töröljük ki az IMAP fiókokat hátha az a baj, nézzük meg az Exchange webes szarjával hogy hátha a konkrét levéllel van a baj, próbáljuk meg üres mailbox-szal, stb. Semmi.

Viszont a sok próbálgatás alatt kb 100x crashelt le az Outlook, ami már feltűnt a gépnek is, felugrott ugyanis egy ablak kb olyan szöveggel, hogy ő most az Office Segéd és úgy látja baj van, hadd segítsen. Hát segítsél, mondtuk, de nem csak én, a linuxos junkie, hanem senki kolléga nem bízott abban, hogy ebből lesz valami. Aztán elkezdett futni kb fél óráig egy varázsló, és a végén...

Structure and Interpretation of Computer Programs

Az egyik dolog, amit nagyon szeretek a progmaton a Simon-féle analízis kurzusban, az az, ahogyan gyakorlatilag a semmiből, vagyis a ZF-ből és a valós számok axiómáiból építkezünk, és ha néha ki is hagyunk egy-egy bizonyítást, akkor arra külön fel van hívva a figyelmünk. Ennek az a csodálatos eredménye, hogy még így a hatodik félév közepén is bármilyen bonyolult tétel bizonyítása esetén elvileg rekonstruálható a teljes út az axiómáktól.

A SICP, mint alant kifejtem, ugyanilyen előadássorozat illetve könyv, a programozásról. Én egy-két évvel ezelőtt először az előadással találkoztam, ma már nem tudom, miért hagytam abba akkoriban a 6. előadás környékén. Most viszont elémkerült a könyv is, nekiugrottam, és kiderült, hogy a lényeg pont a második felében van.