You are the processor

Chapter 31 left Iskra-8 in an odd state. The ALU can add and subtract, the registers hold numbers, the memory keeps 256 bytes, and the clock says “step” again and again. But who decides what to do on that step? In Chapter 31 we decided ourselves, by hand: we put numbers on the inputs and pressed buttons. A machine that has to be told every step by a person is still a calculator.

The answer is hidden in the memory itself. Suppose the cells hold orders as well as numbers: “add R2 and R0,” “decrease R0 by one,” “if it isn’t zero, go back.” Suppose the counter from Chapter 31 points at the next order. Then all we need is a small circuit that on every cycle reads the order, works out what it means and sets the switchmen. Before building that circuit, we will play its part. In this chapter, the processor is you.

The cast

There are five characters on stage, and you know three of them already. The memory: the 256 bytes of Chapter 31, with a program at the beginning. The ALU from Chapter 30, with its three flags: Z, the result is zero; C, there was a carry or a borrow; N, the top bit of the result is 1. The working registers R0–R3. And two new characters, both of them registers too.

The first is the program counter, PC. It holds the address of the instruction that is due next. It is the counter from Chapter 31: after each instruction it adds the instruction’s length to itself and points at the next one. The second is the instruction register, where the fetched byte is put so that it can be examined. The one who examines it is the control unit, and that part is yours.

The rules of the game are the same for every instruction. A move consists of three actions.

1. Fetch. Take the byte at the address in PC from memory, and add one to PC.
2. Decode. Work out which instruction it is. If it needs a second byte, a number or an address, fetch that too, again adding one to PC.
3. Execute. Do what the instruction says: put a number in a register, add, write to memory or change PC.

Then it all starts again from the next address. This round is called the fetch–decode–execute cycle, and a device that goes round it is a processor. On Iskra-8 every instruction, from fetch to execution, takes one clock cycle. The processors in our computers split an instruction into several stages and keep several instructions going at once, each at its own stage; that pipeline is the subject of Chapter 35.

Your first shift

In Chapter 31 the beginning of Iskra-8’s memory held eleven bytes, and we promised to explain what they were. Here are almost the same bytes; we only made one number smaller, so that you won’t have to go round the loop for long:

10 03 18 00 58 A3 C8 04 38 FE 00

This is a program. You will find out what it does by executing it. The widget shows the memory and the processor, and the line at the top tells you which action is expected of you. The “Codes” button opens a cheat sheet of the instructions. Mistakes are harmless: the widget shows you where you went wrong and lets you try again.

The program added up $3 + 2 + 1$ and printed 6. To do it, you made thirteen moves: two setup instructions, three laps of three instructions each, the output and the halt. Each decision you made is one that some circuit from the earlier chapters already knows how to make.

• Tapping the cell at the address in PC means feeding the output of the PC register to the address lines of the RAM and reading the byte with the tree of switchmen from Chapter 31. Adding one to PC is the counter from the same chapter.
• The decoder of Chapter 31 helps you work out which instruction it is: the top four bits of the byte are the opcode, and the opcode lights one of sixteen lines.
• Choosing which register to add is a switchman controlled by the bits aa and bb of the same byte. Choosing what the ALU does is the switchman at its output, from Chapter 30.
• Whether to jump is decided by an AND of the inverted Z flag and the decoder’s “JNZ” line. The jump itself is writing a new value into PC, a register with a LOAD input.

The control unit, which takes a byte, then a second byte, then executes, is one of the state machines of Chapter 31, with a few states. No new parts were needed. The only new thing was an idea: the orders lie in the same memory as the numbers.

The program in the same memory

The first stored program ran not on EDVAC but on a small machine in Manchester, the Baby, on June 21, 1948. Less than a year later the Cambridge EDSAC came to life, the machine we met in Chapter 5. Almost all computers have been built this way ever since, and so is Iskra-8. The design is called the stored-program architecture.

A new program is now loaded into memory the way numbers are, and switching to a new problem takes a second, where ENIAC needed days. What’s more, a program can be read as data. Here is a program that walks through memory from address 0 to its own end and prints everything it finds there, which is to say, itself.

This is a machine-code cousin of the quine from Chapter 7, only a cheating one: the program doesn’t carry its own text but reads its bytes straight from memory. On a stored-program machine that is allowed. And since programs are data, one program can write another. That is how an assembler works (you will meet one shortly), and so does the compiler you will write in Chapter 52. This power has a dark side: if attackers manage to slip their own bytes into a place where the processor will later jump, the machine will obediently execute them as instructions. How that is done, and how machines defend against it, is the story of Chapter 61.

Machine code

The instructions a processor understands directly, written as numbers, are called machine code, and their complete list is the instruction set. Iskra-8 has 26 instructions, and each one begins with a byte of the same shape: oooo aa bb. The top four bits are the opcode, the next two are the number of the first register, and the bottom two are either the number of the second register or a tag saying which member of an instruction family this is. If an instruction needs a number or an address, it lies in the second byte.

Take the byte 58 from the program you executed and decode it. $58_{16} = 0101\,10\,00_2$. Code 5 is addition. The field aa is $10_2 = 2$, that is, R2, and the field bb is 0, that is, R0. We get ADD R2, R0: $R2 \leftarrow R2 + R0$. The byte C8 is $1100\,10\,00_2$: code C is a jump, the field aa = 10 says that it is JNZ, “jump if not zero,” and the destination is in the second byte, 04.

Every Iskra-8 instruction is written as 4 bits of opcode, 2 bits for each register and perhaps one more byte. The machine’s limits grow out of this: there are four registers because a register number gets two bits, and sixteen opcodes because an opcode gets four. That is also why some instructions share an opcode and differ in the field bb. Commercial processors make the same compromises, only with more bits.

Try the example “the word HELLO.” Letters are bytes too, and a processor sent their way will try to execute them as instructions without a moment’s hesitation. The byte 48, the letter H, turns out to be the instruction MOV R2, R0. The bytes themselves don’t know where the program ends and the data begins; only whoever put them there knows. Starting one byte off is even more fun. Iskra-8 instructions are one or two bytes long, and if you start reading in the wrong place, the second byte of one instruction is taken for the first byte of another, and the whole program turns into a different one.

The assembler

Writing programs in bytes is torture. You have to remember the table of codes, put the bits of the fields together and, worst of all, count addresses: the JNZ in our program jumps to address 04, and if you insert one more instruction before the loop, the address shifts and the jump has to be rewritten. So programs are written in words, called mnemonics, and addresses are replaced by labels, names given to lines. The translation from this notation into bytes is done by a program called an assembler. The language of mnemonics is called assembly language, or often assembler too.

The assembler produced the familiar eleven bytes, the program you executed by hand. The label loop has address 4, because two instructions of two bytes each come before it. The assembler finds that out by counting the lengths of instructions. A jump forward is harder: JMP done at the start of a program refers to a label the assembler hasn’t reached yet. So it reads the text twice. On the first pass it only counts the lengths of the instructions and records the addresses of all the labels. On the second it translates the instructions into bytes, already knowing every address. You will write such a two-pass assembler in the task “Your own assembler”.

The Iskra-8 assembler understands a few more words that don’t become instructions. .byte 1, 2, 3 puts bytes into memory as they are, .text "HI" puts in the codes of the letters of a string, .equ N, 10 gives a number a name, and .org 0x80 says to carry on from another address. A comment starts with a semicolon. The Apollo Guidance Computer had an assembler of its own, YUL, written in the same MIT laboratory. YUL produced punched tape, and from that tape the machine from Chapter 31 moved the right core under the needle. A program in mnemonics turned into bytes, and the bytes into wires.

Iskra-8 in full

The machine is now complete, and the processor’s part can go back to it. Below is Iskra-8 with all its parts: the program text, the registers, the flags, the screen, the output and the whole memory. Pick an example or write a program of your own, press “Assemble,” then “Step” or “Run.” While the machine works, the text is replaced by a listing: addresses, bytes and the line being executed. The slider sets the speed, from one instruction a second to thousands.

The same programs run in Python too: the cs.iskra module in the sandbox is the same machine, bit for bit. It is also what checks your solutions to the tasks.

Forks and loops made of jumps

The Iskra-8 instruction set has neither if nor while. It has flags and conditional jumps, and they are enough. A condition from Chapter 3 is a comparison and a jump over a piece of code. CMP R0, R1 subtracts R1 from R0 without storing the difference anywhere, and only sets the flags. If the numbers are equal, the difference is zero and the Z flag goes up. If R0 is less than R1, the subtraction had to borrow a one from a ninth bit that doesn’t exist, and the C flag goes up. This is how a fork in the road is translated:

Here a, b and x live in the registers R0, R1 and R2. A while loop from Chapter 4 is a jump backward: the body, the check, and a jump to the start for as long as the condition holds. The loop in the program you executed works this way: DEC R0 decreases the counter and sets Z along the way, and JNZ loop goes back to the start until the counter reaches zero. In machine code every loop, function and recursion turns into jumps like these.

Here it is again on Iskra-8. Our registers are eight bits wide, so we take a smaller number, 221, and the same method: the candidates are 220, 219, …, and the division is subtraction until we hit zero or a borrow.

$221 = 13 \cdot 17$, and the machine found 17 in 3,177 instructions. Zero and a borrow never come together after SUB: if the difference is exactly 0, there is no borrow, so the two checks could also go in the other order. Change N to a prime, 251 for instance, and the program will try every candidate all the way down to one.

The screen and the output are memory too

Iskra-8 has no instructions to “draw” or “print.” Instead, a few addresses at the end of memory are special. Cells 0xF0–0xF7 are wired to the screen: each byte is a row of eight pixels, with the top bit on the left. Writing to 0xFE prints a number, and reading from it takes a number from the input. Writing to 0xFF prints the character with that code. This technique is called memory-mapped input/output. The processor doesn’t need to know anything about devices: it writes to an address, and what answers at that address is a screen or a printer rather than a memory cell.

The instructions at work here are LDR and STR: they take the address from a register, and a register can be increased in a loop. That is a pointer, the number of a cell, itself kept in a cell. Python hides its pointers, but the list from Chapter 14 and its a[i] work this way underneath. The video memory of home computers once worked like the screen of Iskra-8: on the ZX Spectrum, a British home computer of the 1980s, the picture on the screen was an ordinary area of memory, and games drew by writing bytes into it.

Subroutines: the Wheeler jump in hardware

In Chapter 5 David Wheeler taught EDSAC’s subroutines to find their way back: before the jump, the calling program left its own address behind, and the subroutine jumped back to it. Iskra-8 has a pair of instructions for this. CALL square puts the address of the next instruction on the stack and jumps to the label square. RET takes the address off the stack and jumps to it. The stack lives at the top of memory, right below the screen, and grows downward: the SP register points at its top and starts out at 0xF0. Every call puts its return address on top of the previous one, so a subroutine can call another, that one a third, and they all return to their own places. This is the call stack of Chapter 5, made of bytes. The “Squares” example in the machine above calls a subroutine five times.

A processor on a single chip

In design, Iskra-8 is closer to the 4004 than to the processor in your phone: one instruction at a time, a few registers, a tiny memory. A modern processor has tens of billions of transistors, hundreds or even thousands of instructions, pipelines and caches. But the cycle is the same: take the instruction at the address in the counter, work out what it means, carry it out.

Is this enough for everything?

Iskra-8 has 26 instructions. Can you write any program on it: the sorting of Chapter 20, Dijkstra’s algorithm from Chapter 24, a Python interpreter? There are good reasons to think so, given enough memory. A list is a row of cells plus a pointer in a register, and LDR and STR walk along it. A function is CALL and RET, and recursion runs on the same stack. Multiplication, division and fractions are programs made of additions, subtractions and shifts, like the division on the Manchester Baby. What limits the machine is the size of its memory; a meager instruction set doesn’t hold it back. The Baby had seven instructions, and one is known to be enough if it is well chosen, for example “subtract, and jump if the result is not positive.”

What “any program” means precisely, and whether there are problems that no machine can solve however much memory it gets, is a conversation for Chapter 55, where Alan Turing will build a machine even simpler than ours. For now, we can sum up four chapters.

Tasks

Three programs for Iskra-8 and one program about programs. In the first three, the solution is a string, PROGRAM, holding assembly text; the checker assembles it with cs.iskra, runs it on different inputs and looks at the output or the screen. Debugging is easiest in the machine from the section “Iskra-8 in full”: copy the program text over there.

What next

Iskra-8 has come to life. The counter points at an instruction, the control unit takes it apart, the ALU computes, and jumps send the program round loops and around the code it should skip. You have written a sum, a multiplication and a picture for it, and you have probably noticed how much effort that took. Multiplying two numbers takes a dozen lines; every variable has to live in one of four registers, and you have to remember which. The histogram that Python writes in two lines takes sixteen in assembly.

And yet everything you have written in Python in this course is executed, in the end, by the same fetch–decode–execute cycle, only on a bigger processor. So somewhere between the line total += x and the processor’s instructions, an enormous job of translation gets done. How do lines of Python turn into instructions? In Chapter 33 we will X-ray a single function layer by layer: Python, bytecode, C, x86-64 assembly, and Iskra-8 once again.