Meet Tiny-8

In Part I we built every part a processor needs: adders, registers, multiplexers, a clock and a program counter. A pile of parts isn't a computer yet, though. What turns it into one is a plan: a way of telling the parts what to do, step by step, that we can change without rewiring anything.

Programs are just numbers

The earliest electronic computers were "programmed" with cables and switches. To give ENIAC a new problem, its operators spent days plugging wires into new places. The breakthrough came in 1945, in a report on a new machine written by the mathematician John von Neumann: store the program in memory, as numbers, right next to the data it works on.

The processor then does just one thing, over and over, as fast as its clock allows:

1. Fetch: read the number at the address in the program counter.
2. Decode: work out which instruction that number means.
3. Execute: do it, and move the program counter on to the next instruction.

To change what the computer does, you just change some numbers in memory. That's called the stored-program idea, and every computer since works this way, from the IBM PC to your phone.

Tiny-8's parts

Tiny-8 is deliberately tiny, so we can see every bit of it. Here's everything inside:

• Memory: 16 bytes, at addresses 0 to 15. It holds the program and its data, side by side.
• PC, the program counter from Chapter 4. It only needs 4 bits, because 4 bits can count from 0 to 15.
• A, the accumulator: Tiny-8's only working register, 8 bits wide. Results "accumulate" here.
• The ALU (arithmetic logic unit): the adder-subtractor from Chapter 2. It works on A and a byte from memory.
• Two flags, one-bit registers that remember something about the last calculation. Z is 1 if the result was zero. C is 1 if an addition carried out of 8 bits, or a subtraction had to borrow (it went below zero), exactly like x86's carry flag.
• OUT, a register wired to a display, so the program can show us its answers.
• The control unit, which reads each instruction and switches all the multiplexers and LOAD signals to make it happen. It's the subject of the next chapter.

Tiny-8's instructions

Every Tiny-8 instruction is exactly one byte, which is two hex digits. The first digit is the opcode: what to do. The second digit is the operand: what to do it with, usually a memory address from 0 to 15. Because raw numbers are hard to remember, each instruction also has a short name called a mnemonic, like LDA for "load A".

So the byte 1E means "opcode 1, operand E", or LDA 14: load A from address 14. The byte 4F is ADD 15. And 00 is HLT, which is handy: empty memory stops the processor rather than doing something random. Only ADD and SUB change the flags. Loading and storing leave them alone, just as moving data around does on x86.

Your first program

Here's a program that adds 7 and 5. The two numbers sit at addresses 14 and 15; the instructions start at address 0, where the PC begins:

0:  1E   LDA 14    ; A = 7
1:  4F   ADD 15    ; A = 7 + 5
2:  A0   OUT       ; show 12
3:  00   HLT
…
14: 07             ; data: 7
15: 05             ; data: 5

Each line shows the address, the byte stored there, and what it means. Writing programs this way, with mnemonics instead of raw bytes, is called assembly language. Turning it into bytes is called assembling.

Look at the "As an instruction" column for addresses 14 and 15. The simulator decodes every byte as if it were an instruction, so the data bytes 7 and 5 show up as HLT. Memory doesn't know which bytes are code and which are data; only the PC decides, by which bytes it lands on.

Loops and decisions

A program that runs straight through once isn't very powerful. The real magic is in the conditional jumps. A jump instruction checks a flag, and either jumps or carries on, depending on what the last calculation produced. That's how a program makes a decision, and jumping backwards is how it makes a loop.

0:  35   LDI 5     ; A = 5
1:  A0   OUT       ; show A
2:  5F   SUB 15    ; A = A − 1   (address 15 holds a 1)
3:  81   JNZ 1     ; not zero yet? go back to address 1
4:  A0   OUT       ; show the final 0
5:  00   HLT

Building multiplication from addition

Tiny-8 has no multiply instruction. It doesn't need one: 3 × 4 is just 3 + 3 + 3 + 3. So we keep a running total, add 3 to it, count a counter down from 4, and loop until the counter hits zero. This is our first real algorithm:

0:  1C   LDA 12    ; A = total
1:  4D   ADD 13    ; A = total + 3
2:  2C   STA 12    ; total = A
3:  1E   LDA 14    ; A = counter
4:  5F   SUB 15    ; A = counter − 1
5:  2E   STA 14    ; counter = A
6:  80   JNZ 0     ; more to do? loop
7:  1C   LDA 12
8:  A0   OUT       ; show the total: 12
9:  00   HLT
12: 00             ; total (starts at 0)
13: 03             ; the number to add
14: 04             ; the counter
15: 01             ; the constant 1

Notice how the program changes its own memory as it goes: the total and the counter are just bytes, read and written like any others. The early 8-bit microprocessors really had no multiply instruction either, and programmers wrote loops much like this one.

Meanwhile, inside a real CPU

Real instructions are numbers too, just longer. Here's "put 5 in a register" on all three machines:

Tiny-8   LDI 5             →  35                (1 byte)
x86-64   mov eax, 5        →  B8 05 00 00 00    (5 bytes)
RISC-V   li  a0, 5         →  00500513          (4 bytes: one 32-bit word)

In the x86 version, B8 is the opcode ("move a number into eax") and the next four bytes are the number 5, stored lowest byte first. The RISC-V version packs an opcode, a destination register, a source register and the number 5 into fixed fields of one 32-bit word: the same idea as Tiny-8's two hex digits, with more fields.

• Tiny-8 has 1 working register; x86-64 has 16 general-purpose registers and RISC-V has 32.
• Tiny-8 has 11 instructions. RISC-V's basic integer set has about 40. x86-64 has well over a thousand, accumulated over 45 years.
• Tiny-8 can address 16 bytes; a 64-bit processor can, in principle, address 2⁶⁴.

Yet the cycle is exactly the same: fetch the bytes at the PC, decode them, execute, repeat.

Try it yourself

1. Decode these bytes by hand: 3A, 2D, 9F.
   Show answer

   3A = LDI 10 (load A with the number 10). 2D = STA 13 (store A at address 13). 9F = JC 15 (jump to address 15 if the carry flag is set).
2. Change the countdown program so it counts down from 9 instead of 5. Which single byte do you change?
   Show answer

   Address 0: change 35 (LDI 5) to 39 (LDI 9).
3. In the "Add two numbers" program, make it compute 7 + 5 − 3. (Hint: there's room at addresses 4 to 13.)
   Show answer

   One way: put the number 3 at address 13, and change address 2 to 5D (SUB 13), address 3 to A0 (OUT) and address 4 to 00 (HLT). The display shows 9.
4. Load the multiply program and set it up to compute 20 × 20. What happens, and why?
   Show answer

   Put 14 (hex for 20) at both address 13 and 14. The true answer is 400, which doesn't fit in 8 bits, so the total wraps around: 400 − 256 = 144. The carry flag gets set along the way, but this program never checks it.
5. What would happen if a program jumped to address 15 in the multiply program, where the data byte 01 sits?
   Show answer

   The processor would run it as an instruction: 01 has opcode 0, so it's HLT, and the machine stops. If the byte had been, say, 63, it would have been treated as JMP 3. The processor can't tell data from code.

What we learned

• In a stored-program computer, the program is just numbers in memory, side by side with the data.
• A processor repeats fetch, decode, execute forever.
• Tiny-8 has 16 bytes of memory, an accumulator, a program counter, flags (Z and C), an ALU and a control unit.
• Each instruction has an opcode (what to do) and an operand (what to do it with). Assembly language writes them as mnemonics like LDA 14.
• Conditional jumps check flags, which lets programs make decisions and loops.
• Complex operations, like multiplication, can be built from simple ones in a loop.

We've treated Tiny-8's control unit as a black box that "just does" each instruction. In the next chapter we open it up. We'll slow the clock right down and watch each instruction happen in tiny steps, as the control unit switches multiplexers and LOAD signals on and off.