Tuesday, May 30, 2017

TTL Brainfuck Computer Part 1 - Intro

Part 2

A couple months ago I stumbled across Ben Eater's series building a breadboard computer out of TTL chips. I've had the idea in the back of my mind to do something like this for a while now, but Ben's series has kicked a lot of people over the edge and it's turning into a bit of a trend.

I've always had a soft spot for Brainfuck (and more generally, esolangs and obfuscated code). Way back in ought 6, I wrote an obfuscated Brainfuck interpreter to use as my e-mail signature (the yin-yang light bulb was my personal logo before Gnomes took over my identity):

#include      <iostream>       //  //    _            |  |
#include       <fstream>      //| //|  // \\        \  __  /
#include       <cstring>     //||//|| //  //       __ /o)\ __
#define S          32768    // |// || \\_//RLANDO     \(o/
#define b        ;break;   //  |/  ||ATTHEW    2006    ZZ
#define c(x,y)  case x:y  //==================================
char a[2*S],*m=a,*p=a+S,*r=p,o; void i(int n=0){char*l=p;while
(p<r){switch(*p++){c(43,++*m)b c(45, --*m)b c(62,++m)b c(60,--
m)b c(46,std::cout.put(*m))b c(44, *m=std::cin.get(o)?o:*m)b c
(91,if(*m)i(n+1);else for(o= 1;o&&p<r;++p){o+=*p==91;o-=*p==93
;})b c(93,if(*m)p=l; else return;)}}}int main(int _, char**f){
memset(a,0,2*S);std::ifstream z(f[1]); while(z.get(*r++));i();
return 0;} //BF interpreter. No err chk. 32k mem, 32k program.

Someone who knows me well enough probably could've predicted my urge to make a hardware Brainfuck computer after seeing Ben's series.

From the beginning, I had some guiding principles for the design:

  • Provide enough storage for non-trivial programs - Minimum specs matching my Brainfuck signature: 32 K instructions, 32 K data.
  • One-to-one correspondence between Brainfuck commands and CPU instructions - There is merely an encoding difference
  • Constant time execution of each instruction - It should never take more than 3 cycles to execute any instruction
  • Minimal number of execution steps - If an instruction can be executed in one cycle, it should be
The RAM needs are behind most of my departures from Ben's design. He's using a pair 74189s (or equivalent) which are 16 x 4 bit each, for a total of 16 bytes of RAM. His computer uses a Von Neumann architecture, so his RAM is used for both code and data, and all data transfers happen over a single bus. This makes his computer much closer in design to the CPUs inside desktop computers, smartphones, etc.

Brainfuck programs are extremely inefficient in code size, and fairly inefficient in memory usage. Only the most trivial programs would fit in 16 bytes (nothing close to printing the Fibonacci sequence). Since I'm targeting minimal clock cycles, a Harvard architecture makes more sense, where data and instructions are transferred on separate buses. Since Brainfuck programs are so inefficient in code size, it would be extremely tedious to have to enter the program every time the system powers on. I decided to use EEPROMs for the program memory.

I spent some time playing with logisim-evolution, a digital circuit designer/simulator to get a rough idea of the implementation. By using RAM with asynchronous outputs (output changes immediately when the address changes) and separate inputs, I was able to make a design that executed one instruction per cycle.

Then I started looking at hardware. Jameco sells a kit with 10 or 20 each of 35 different 74LS chips, which I believe is the same kit Ben used. Except for the RAM and ROM, this kit has pretty much everything I needed. The most important parts are the binary up/down counters (74LS193) since half of all Brainfuck operations involve either incrementing or decrementing a number (either the location in memory or the data in memory). They also had a suitable EEPROM. So that side of things is fine, but I still needed RAM.

Even if I used every flip flop & latch in the kit, I would still only have probably a hundred or so bytes of RAM, so I went looking for SRAM chips with 15+ address lines. Unfortunately, the only asynchronous SRAM chips available with separate input & output lines are fully dual port, meaning both sets of I/O lines can act as input or output. This makes them much more complicated in design and the cost for a 32KB chip is north of $40. On top of the cost, they're all surface mount devices (BGA, QFP, etc), so I'd have to solder them onto a break-out board. I've never done surface mount soldering, and there's no way I'm going to practice on a $40 chip.

So I decided to scale back my ambitions and go for a 2-cycle design using single port RAM. I was able to get ten of CY7C199-35PC for half the price of a single dual-port.

In the next post, I'll show the initial breadboard layout and give an overview of the design of the computer.

Part 2

1 comment: