Paver

This project is based on an original 16-bit CPU, implemented in Verilog on a DE1/SoC FPGA development board made by Terasic.

The download package (see towards end of article) includes the Altera II files that allow you to write a working image to the board, if you happen to have one.

The Verilog implementation includes modules for PS/2 input and custom VGA output coupled to the virtual “Paver” micro-controller using a dual-ported RAM. So essentially, it turns the DE1/SOC into a home-computer.

On startup, a small native IDE with an editor runs. I wrote a little, mostly working Forth interpreter experimenting with the system. There is even a native assembler and IO routines for saving/restoring from SD-card!

Developing for a new CPU of your own invention gets you to jump through some interesting “hoops”, because no-one is going to do it for you:

Step 1

I started out writing a simulator in C for the CPU, then added an assembler (“cyf”) in C that generated machine code for the simulator. This meant that I could write assembly programs for the new CPU and experiment.

Step 2

Then I wrote one particularly interesting program for the CPU, which was a port of my C assembler. After a bit of fiddling around both with the C assembler and the native Assembler I had just written, both programs accepted the same source files, and produced identical machine code output. This meant that I could assemble the assembler natively, and could ditch the C assembler.

So, in other words, I had created two ways to generate the binary image of my native assembler:

1. Just feed its source code into my earlier assembler, the one written in the C language. Out comes the binary.

2. Load the binary image that was output by either assembler into the simulator, and feed the simulator the source-code. Out comes another binary.

It’s a bit of a mind-twister, admittedly. Can you see how the native assembler consists of two things: (1) the simulator (needed to run native code), and (2) a working binary image of our assembler (which tells the simulator what to do, how to actually “assemble” anything).

One thing I should explain is, how can the simulated assembler program access the source code file? How does that happen? It’s a little bit of a trick. The simulated CPU uses an array (a list of bytes in real memory) that it treats as its (simulated!) RAM. I’ve programmed the simulator so that it just reads the assembler source file and stores its text into that particular array of memory, where the simulator can then see and read it, as if it had gotten there by magic.

Step 3

So let’s call the assembler – that combo of simulator and its binary image input – the “hen”. If you run this hen on the source-code of your assembler, it outputs another binary image – that’s what an assembler is supposed to do. Let’s call this binary image that comes out an “egg”. It’s a new version of your assembler.

Can you see that you cannot have a hen without loading an “egg” into the simulator so it knows what to do? That’s important. You need exactly three things, the source file (the new version of the assembler you want to create, the blue-print), the input egg (a previous version of the assembler, telling the simulator how to behave), and the simulator itself.

In my project, I actually renamed a stripped-down version of the simulator “hen”, because it automatically loaded the assembler source file for me, and automatically loaded the most recent “egg” binary image as the program to run.

In case you wanted to experiment with this, without getting too much into the rest of this project, I’ve “distilled” a small subset of the code with just the hen and its sourcefile. It’s called poppy.

So the hen laid an egg, which was then used to assemble the next revision of my assembler source, and so on.

The trick (and this often got me!) is to be very careful about making only gradual, compatible changes to the assembler, so that it would continue to be able to compile itself. It had to slowly evolve, in the true sense of the term!

Otherwise your egg would become “it’s own species”, turn into an incompatible hen, and you potentially locked yourself out badly. If I was foolish enough to have kept only the most recent egg, in the worst case I would lose all my modifications/bug fixes right back to the first native run. The last output generated by the C version of the assembler was my fall-back, as it was written in a high-level language. So you had to keep copies of your eggs, because some bugs only manifested themselves two generations down etc.

How do you mean, you may ask, two generations down? Well, if you change a data structure in your assembler, the next generation of it will still have to read the old data structure, but write into the new data structure. Then from the generation after that, you hope to be able to read those data back. This means that you will only know whether it worked after two assembler runs.

Bonus “Rabbit Hole”

One thing I mentioned is a rabbit-hole: I said that we could discard the earlier assembler I had written in C, because there is now a native version that does its job. Okay… so we delete the source code, cyf.c. After all, the binary assembler program is enough to “run” the assembler on the simulator. But if you pause and think, wasn’t the source the only thing that allowed us to see what the assembler actually does? How can you tell with just the binary?

Sure, we can verify that it continues to assemble our source code. But is that all it does? Could we have planted malicious behaviour that persists, iteration after iteration of our assembler assembling its lineage? Ken Thompson, the inventor of UTF-8 and a real getter-done of Unix, presented a paper called Reflections on Trusting Trust for his Turing award speech:

What I am about to describe is one of many “chicken and egg” problems that arise when compilers are written in their own language. In this case, I will use a specific example from the C compiler.
… First we compile the modified source [of the C compiler] with the normal C compiler to produce a bugged binary. We install this binary as the official C. We can now remove the bugs from the source of the compiler and the new binary will reinsert the bugs whenever it is compiled. Of course, the login command will remain bugged with no trace in source anywhere.
- Ken Thompson

He basically says that hidden in the massive binaries of large compilers such as CLANG or GCC may be hidden all sorts of intricate artefacts that are very difficult for a human to detect and vet, and which are remnants of how the source code of the compiler was at some point, rather than how it presents itself now. It theory, this can go unnoticed for decades. In theory, since C is widely used for writing compilers and entire languages, it could possibly trickle down into other eco-systems, couldn’t it?

Step 4

Since the .egg files are literally native binary images, we can simply load them into a RAM component of the DE1/SOC machine and attach them to your “CPU”. But first, you need to describe your CPU (the behaviour of the C simulator) in a hardware description language called Verilog and program the FPGA (a Cyclone 5) with it, so that it can execute the program you put in its RAM.

So I would write my firmware (see download package) in assembler on the computer, deploy it to the board and then test it out. Eventually I wouldn’t need a computer even, since I had my own assembler, monitor screen, keyboard and SD storage.

If you haven’t had the experience, writing a system from zero like this takes a bit of will-power. There are so many interconnected parts that you really have to take your time with, it’s unholy.

But eventually you will get there. The layout of the character bitmap finally matches your Verilog rasterization logic, and there is this quiet, properly synched monitor signal, showing some terminal output with text, generated by a CPU you designed… It’s cool somehow, like if you had climbed up some mountain for a few months or something.

GUI Simulators

Further, the package includes simulators (“Phos”) of the DE1/SoC system with native GUIs for macOS (OpenGL, Objective-C), Windows (OpenGL, C), Android (C) and iOS (Objective-C). The mobile versions are super silly - I have no idea who would ever use them, including me. But I still learned something I guess.

This is the only time I’ve worked with Objective-C. The fact that Objective-C can handle ANSI C, and that C++ can handle ANSI C, and that both Windows and Apple had/have? excellent support for OpenGL made porting the simulators pretty easy. This was just before Swift came out and Apple deprecated OpenGL.

Downloads

The dowload package has lots of stuff in it. I haven’t looked at it for years, but it should still all be reproducible on current systems.