Welcome to the machine: emulating a CPU
Inspired by surprisingly real events.
Eleven hours and sixteen minutes ago, our scientists lost contact with the Trailblazer 1 probe en route to Proxima Centauri. Since then we’ve been trying without success to re-establish contact with the spacecraft’s onboard computer. If we can’t rectify the problem, we may be faced with a total loss of the vehicle and mission.
That’s why we need your help.
Classified briefing
Welcome to the Situation Room. Thank you for coming in at such short notice. Do you have coffee? Okay, then let’s get right to it, because time is a factor.
Riding on a beam of light
As you know, the Trailblazer mission is a multi-billion-dollar international scientific collaboration to send a lightsail-powered robotic probe to the Proxima Centauri star system, a journey of about 20 years. The tiny spacecraft, about the size of a smartphone, was launched 15 years ago on a drive beam powered by giant phased laser arrays located in over 40 countries, and reached its coasting velocity of 20% light speed within about 10 minutes, crossing the orbit of Mars half an hour after launch and heading rapidly for the outskirts of the solar system.
Artist’s impression of the Trailblazer probe
For the last 15 years Trailblazer has been sailing serenely through interstellar space, sending back valuable science data and engineering telemetry, as the mission team tested, checked, and rechecked all the onboard instruments in preparation for the probe’s flyby through the Prox Cen system and its many interesting exoplanets.
Then everything went dead.
The machine stops
The binary data modulated onto the optical carrier signal suddenly changed from valid telemetry data to a meaningless string of 1s. Since we’re still receiving the signal, we know the spacecraft is intact, powered, and with its communication laser aimed correctly towards Earth. Doppler radar data indicates that its trajectory is unchanged, making it unlikely that the craft was hit by a meteorite or space debris. It’s just no longer able to talk to us.
The problem appears to be localised to a subsystem known as the RTFM (Remote Telemetry and Flight Management) computer, responsible for the communications link between the spacecraft and Earth. Engineers are speculating that its memory may have been corrupted by a cosmic ray impact, causing the software to malfunction.
Trailblazer spacecraft block diagram
A series of unfortunate events
Unfortunately, it seems that while the probe’s computers and flight software were thoroughly documented before launch, that documentation is no longer available, due to… well, let’s just say mistakes were made. We also no longer have the source code or any way to reproduce it. It seems that these files were deleted when one of our cloud drives ran low on space, and everybody thought some other department had a copy.
This regrettable oversight has been dealt with through internal disciplinary procedures, but that’s not important right now. What’s critical is that we restore communication with the spacecraft in time for its all-important encounter.
There’s no way for Trailblazer to slow down, as it’s a pure lightsail craft, with no onboard propulsion. When it reaches Prox Cen, things will start to happen very quickly. At 20% of the speed of light, it will take the probe only a couple of days to pass right through the system, during which time it must do all its science-gathering and imaging and relay this data back to Earth. After that, it will just hurtle onwards into the void, forever. We don’t get a do-over.
We need the RTFM communications system to be working again by that time, but there’s a snag. Because Trailblazer is such an immense distance away, any software update we send it will take about four years to be received at the spacecraft. That means we only have a few weeks to diagnose and fix the problem in time for Encounter.
Racing against time
That’s where you come in. We urgently need your help to investigate the RTFM software issue. Specifically, the first thing we need is a program that can execute code written for the spacecraft’s onboard computer.
A program like this is called an emulator: it acts like a model of the computer’s central processing unit (CPU), and will enable us to write and test code before uploading it to the RTFM for real. Time is running out, and there’s no room for mistakes: a botched software update could put the probe out of action for good.
You might also have heard the term virtual machine, meaning not “nearly a machine”, but something more like “not actually a machine, but behaving like one”. Emulator, virtual machine, same thing.
It sounds complicated, but emulators are actually fairly easy to write, once you understand how the emulated machine (the guest) works. The RTFM computer uses a relatively small and simple CPU, compared to the one in your computer (the host machine).
RTFM computer block diagram
Booting up
This CPU is called the R8, and to emulate it, you’ll be writing the necessary code to implement the R8’s instruction set: the commands it understands. You can use any programming language you like to do this, but we’ve set up starter repos for you for a couple of popular languages:
Sebastián Alvarez has kindly contributed a starter repo for TypeScript, too:
These repos will give you the basic structure of the project, plus some tests and stub functions to get you up and running, but after that it’s entirely up to you what to do. So if you want to use a language other than Go or Rust, you’re welcome: look at one of these repos to see what’s there, and start by reproducing it in your language of choice.
There’ll be a series of challenges throughout this project, to help you evaluate what you’ve learned. If you get stuck, or if you want to compare your answer with one suggested version, you’ll find complete, working solutions for all the challenges in these repos:
- go-machine (Go)
- rust-machine (Rust)
- ts-r8-solutions (TypeScript, courtesy of Sebastián Alvarez)
The soul of a new machine
The first thing the emulator needs is a properly-initialised CPU,
ready to work. So, in the Go repo, for example, there’s an
r8.NewCPU function that returns a CPU in its default
initial state, which is specified by a test. In the Rust repo you’ll
find an implementation of Default for the CPU that does the
same thing.
The test and the constructor function are already provided in the starter repo, so your first challenge is a straightforward one:
GOAL: Run the test and make sure it passes.
In Go, for example, run go test, or in Rust run
cargo test.
Powering on
The CPU is the heart of any computer: it does the data processing, executes the software, and controls every other part of the system. Usually made up of many transistors and other electronic components on a silicon chip, each different model of CPU understands a different machine language: the programming language that tells it what to do.
Every program that runs on your computer is actually in machine code, then: even if it was written in a higher-level language like Rust, it has to be compiled—automatically translated—into the equivalent machine-code program before the CPU can understand it.
Everything we want the machine to do has to be spelled out in tiny, discrete steps involving moving numbers around. The CPU itself has no concept of things like strings, functions, variables, graphics, or processes: those are all abstractions provided by software, and ultimately implemented in machine language.
Machine language consists of commands that mean things like “add this number to this other number”, “read the value at this memory address”, “jump to the program starting at this other address”, and so on.
Putting two and two together
For example, here’s a human-readable version of a short program for the R8:
ld a, 2
add a, 2Can you guess what it does? That’s right, it adds 2 and 2. The
ld a (load) instruction puts a number into one of the CPU’s
working areas, called a register. In this case, it
loads the register named A with the value 2.
Then the add a instruction adds another number
to the A register. In this case, it adds the number 2. The result is
that A will contain the value 4—or at least, it will if everything’s
working correctly, which it may not be on the Trailblazer spacecraft,
but that’s what we’re here to find out.
Cracking the code
The R8 doesn’t understand words like ld a or
add a directly, though: those are
mnemonics (from the Greek for “remember”), symbolic
terms designed to be easy for humans to read and write. Actual machine
language just consists of numbers, but there’s a one-to-one
correspondence between these numbers and the mnemonic instruction
names.
Every R8 instruction has its own unique identifying number:
instruction number 1, instruction number 2, and so on. These are called
opcodes (for “operation codes”). For example, the
opcode for ld a is 16, and the opcode for
add a is 80. (Don’t worry about why these
particular numbers; they’re basically arbitrary, like phone
numbers.)
So the “add 2 and 2” program we just saw actually looks like this in machine language:
16 2 80 2You can see why mnemonics were invented! It would be difficult for us
to write programs using only numbers, even though that’s the language
that the R8 (like all CPUs) actually speaks. Instead, we use the
symbolic names like add a and ld a for
convenience, which is what’s called assembly language
(I’m not sure why: maybe because writing programs is a bit like putting
together IKEA furniture?)
A trip down memory lane
To work out the final result of the example program, you had to hold its intermediate results in your head. The CPU does the same thing by storing them in its working register, which is like your short-term memory.
R8 machine-code programs are also a sequence of numbers, as we’ve seen, but unlike the data in the working register, they’re not stored on the chip. So where do these numbers actually live in the computer, and how does the CPU know where to find them?
Another important component of every computer is memory: also a silicon chip, but a different kind of chip from a CPU. Its job is not to compute anything, but just to store numbers so that the CPU can retrieve them when needed. The memory has many different storage slots, or locations, each of which can hold a single number.
Each memory location has its own address, which is also a number. Think of memory addresses as being just like postal addresses. Address 66, for example, is like “Number 66, Memory Lane, Computerville”.
Memory layout
Each address identifies a unique location, which contains a number. What that number actually means to the computer is irrelevant as far as the memory device is concerned—it doesn’t care about that. All it knows is how to store or retrieve a data value in a specified address.
From the CPU’s point of view, though, many of these data values are opcodes representing instructions for the machine to execute. So its job is to read the program from memory, one instruction at a time, and do whatever each instruction tells it to do.
Getting nowhere fast
Even though a CPU might seem complicated, then, and in detail it is, it’s very simple in principle. It just does these two things, over and over, forever:
- Fetch the next instruction from memory
- Execute it.
This is called the fetch-execute cycle, understandably. And this is all your emulator needs to do, in principle: fetch the next instruction, and execute it. Repeat forever.
Saying ‘the next instruction’ implies that the CPU has some way of remembering where it currently is in the program. There’s a CPU register called PC (for “Program Counter”) that does just this: it stores the memory address of the next instruction to execute. Every time the CPU fetches the next instruction from this address, it adds one to the program counter so that it keeps moving steadily through the memory, one location at a time.
Suppose PC holds 0, for example. If we were to start the CPU running now, the first thing it would do would be to read the contents of memory address 0 (we say that PC points to this address). It will interpret this as an opcode, and do whatever that opcode tells it to do.
Next, it will increment the address in PC (add 1 to it), and the cycle repeats: read the contents of memory address 1, execute it as an opcode, and… well, you know the rest.
And that’s what your emulator will do, too: perform this fetch-execute cycle continuously. For testing and debugging purposes, though, we’ll start by just fetching and executing one instruction at a time.
Stepping out
We’ll need a way for users to tell the machine to do one iteration of
its fetch-execute cycle: fetch the next instruction from memory at the
address held by PC, execute it, and return. So there’s a method on the
CPU type named Step that does this.
Or, at least, it will do that with your help, but right now
it’s just a stub: it does nothing. To implement the real behaviour of
Step, we’ll start with a test.
A journey of a thousand miles…
How could we test that the CPU is correctly updating PC every time
Step is called? Well, we can start by calling
NewCPU to create a freshly-initialised CPU. And we know
that the starting value of the program counter is zero.
Calling Step on that CPU, then, should (once it’s
working) increment PC to point to the next instruction. If we do this a
couple of times, we can check that after each call, PC holds
successively 1, 2, and so on.
Let’s find out!
GOAL: Uncomment and run the
TestStepIncrementsPC test, which does the following:
- Creates a new CPU.
- Calls
Stepon the machine. - Tests that PC contains the value 1. If not, the test fails with a
message like
"want PC == 1, got ..." - Calls
Stepagain. - Tests that PC now contains 2.
This test will not pass yet, because the Step method
currently does nothing. Over to you now to fix that.
GOAL: Write the code in Step needed to
make this test pass. You don’t need much!
HINT: We don’t need to actually read the
next instruction from memory yet, because the test doesn’t test anything
about that. The only thing that Step has to do to pass the
test right now is increment PC, so that’s what we’ll focus on first.
SOLUTION: Check your solution against one of these:
It doesn’t matter if you’ve implemented Step slightly
differently, as long as the test passes. After all, the real CPU on the
spacecraft implements it using transistors! It’s the behaviour that
matters with an emulator, not the implementation.
When the test is passing, you can go on to the next section. Or if you like, pause for tea and biscuits, and some deserved self-congratulation: you’ve written a working CPU emulator!
Admittedly, it doesn’t implement any actual instructions yet, but that can soon be fixed. The point is that your program accurately models how the real computer works, by performing the fetch-execute cycle. The rest is just detail.
Monitoring the situation
We know PC is incrementing properly when the machine steps, because the test proves it. All the same, it would be nice to actually see this happening. How could we do that?
One way would be to write a program that advances the machine one instruction step at a time, printing out its internal state after each step. A program like this is called a monitor, because it lets us monitor what’s going on inside the CPU.
You might have used a similar kind of program with a high-level language such as Go or Rust, where it’s usually called a debugger, but the principle is the same. We execute one code one step at a time and verify that the machine state changes in the way we expect. If not, we can look and see exactly where it’s gone wrong.
GOAL: Write a simple monitor program like this for your R8 emulator. Users should be able to run the program and see the value of PC change with each step of the machine.
HINT: If we just kept calling Step
continuously and printing the value of PC afterwards, the emulator would
run so fast that it would be hard to read the ever-scrolling output.
Any useful monitor, then, lets the user single-step the machine, for example by pressing Enter after each step to see the next one. See if you can arrange this in your program: most languages have a way to read from standard input (in other words, the terminal).
SOLUTION: Here are my suggested possible solutions:
It doesn’t matter if your solution is a bit different, and the output of the program doesn’t have to look exactly the same as mine. If you can keep pressing Enter and seeing the value of PC increase by one each time, that’s the important thing.
It’s fun to see the little machine actually running and stepping through memory, one location at a time:
PC
0000 >
0001 >
0002 >
0003 >
...Of course it’s not actually doing much yet, but this is still a good start. Tomorrow, we’ll put our fledgling computer to work, and actually do some computing with it.
For now, though, this is a good point to pause. You’ve made amazing progress for your first day, and while the Trailblazer scientists are still anxiously scanning their scrambled readouts, we’re well on the way to having an R8 emulator they can use to start troubleshooting the problem.
See you back here tomorrow. If you could also bring doughnuts? That would be outstanding.
If you want to skip ahead and learn a bit about the R8 architecture (and maybe implement more of its instructions), have a look at the RX82 project, which uses it to emulate a fantasy retro 8-bit computer from an alternate 1982.
