The simple computer (part 2)

Features Gordon Moore Feb 4, 2013

Gordon Moore continues to look at the Simple Computer and discusses how it works internally and how to make it add a list of numbers

In the first part of this article we looked at how we might put together a simple processor for running computer programs, then and we programmed it using an Assembly Language. Eventually, we could use it to add two numbers together, and then we worked out how to make it multiply two numbers together. Now we’ve had a little break, it’s time to move on to greater things.

In this second part we shall look at what is going on under the Assembly Language hood, and then look at how we can add a list of numbers toget - a very common operation in ‘real’computer programming. Common, but actually a little more difficult to do than you might have thought.

How simple is simple?

You have probably already noted that Simple Computer is limited. Firstly it is quite slow, which I’m afraid is down to my programming skills. I wrote the application in C#, and it is quite complicated underneath (I wanted to allow it to also demonstrate other ideas) and each instruction requires needs quite a bit of code.

The other issue is that it is very limited in the amount of memory it can address. You have probably only seen the 16 memory locations and we have already used most of those for quite simple programs. We can extend it to 32 locations (by pressing the red right arrow button at the top right), but that is our limit, due to Simple Computer’s architecture. I made some of these design decisions for a reason, and now I’d like to explain what is really going on underneath the Assembly Language.

The first key concept to think about is that computers work with binary digits - bits - each of which has just two states: true and false (or ‘0’ and ‘1’). In contrast, our decimal (or denary) system has 10 states: 0 to 9. That, in itself, is not a problem, though, as we can represent every number in binary assuming we have enough bits to play with.

The problem is, we often don’t have enough bits... and the more bits we use, the more circuitry we need. In the early days of computing, hardware was expensive; the first microprocessor chip (the Intel 4004) only had four bits, and thus could represent only 16 states. Early home computers used eight bits - and now we are used to 64 bits.

So, considering the memory store, I had to decide how many bits it was going to hold and I decided on a word length of 16 bits (two bytes). This was so I had enough flexibility to do what I wanted, but not so many that no one would get overawed by too many 0s and 1s.

However, this still means that each memory location could hold numbers from 0 to 216 -1, i.e. 0 to 65,535 (or rather, since it allows negative numbers - using a method called Two’s Complement, which you can see explained at youtu.be/9W67I2zzAfo) the numbers go from -32,768 to 0 and on to 32,767.

If you try and do a multiplication like 16000 x 7, though, you will see that after the second step the numbers are ridiculous. This is because the Simple Computer’s memory cannot store numbers of the size we require. This is linked to an idea called ‘overflow’, where numbers overflow the size of the memory (or buffer) - something you may have even seen one of your computers object too in the past.

The next questions are: how does the computer know what instruction to execute, and where to store or load results in memory? Well, to do this I split each memory location’s 16 bits into different parts. The first four bits hold a code for the instructions: so 0001 is a MOV operation (or op-code), ADD is represented by the binary digits ‘0010’. The DECrement op-code is ‘1001’, JNZ is ‘1101’ and STP is ‘1111’. This means that, since I only have 4 bits, I can only have 16 instructions - well, 15 actually, as ‘0000’ is not used for an instruction.

The next two bits are used by the computer to determine what it should do with the rest of the bits. This is called the addressing mode and applies to the MOV and ADD instructions only. If the bits are 00 then the number that follows will be used as a literal, that is as a number. If the addressing mode is ‘01’ then the number following is used as a memory address i.e. [12]. This is called direct addressing. If the bits are ‘10’ then a special indirect addressing mode is used and we shall see later how that is used. The fourth combination 11 is unused.

We then have just 10 bits left and these are split into two parts each of five bits: also known as ‘operand1’ and ‘operand2’. Depending on the instruction, this will either refer to the AC or to a literal or memory location. Five bits only allows numbers from 0 to 31, which is why we can only address 32 ‘words’ of memory.

In retrospect, perhaps this was not a good design decision. I had it in mind that the operands would also be used for addressing many registers, just like on a real computer chip. I could have made one of the operands just three bits long, which would have allowed eight registers - and then the memory that could have been addressed would have used seven bits, giving an address space of 128 words.

Of course trying to display all these words and have my pretty coloured lines pointing to them would have been a little problematic and complex to program and this app is meant for demonstration purposes. Also I would have needed to create two instructions for the MOV, one for memory to register, and another for doing the register to store operation. Not a major issue in itself, but at the time the decision I made seemed reasonable.

Anyway, we are where we are, and this is exactly what happens in real life; computer designers have to make all kinds of decisions as to how to implement the instruction set, the addressing modes and how to address memory locations just as I have had to. For instance, another way of implementing a computer might have been to use one 16-bit word for the instruction and addressing mode and then the following words to provide the address for the operands. Maybe it could use one or two or four words depending on the instruction. It can all get very complex, and real microprocessors are very complex.

Our layout and an example can be found in the box marked AT&T Style (over). Unfortunately, just to make things even more complex this different to how values are stored in Intel style - the operands are back to front. For AT&T style this is perfect, but we are using Intel Style. So we have what looks like Intel Style (Intel Style box out, below). However, this is for the instruction ‘MOV AC, [15]’! Again this was due to a decision I made early on, when I was deciding which style to use.

So now we can see what happens when we execute each instruction. A computer’s Instruction Decoder breaks the memory word into the various parts, after which it can work out what instruction to execute and where to get its operands. Simple, eh? What..? No, wait...
Within Simple Computer you can look at the actual machine code by clicking on the radio button of the same name; the display will now show all the bits that are actually stored. You might notice that the numbers have an N in front of them. In a real computer this would not exist - but, again for programming reasons, I decided it would make my life much easier to distinguish numbers as numbers.

If you can imagine that each of these 0 and 1s has a light associated with it, you can perhaps picture yourself looking at a Star Trek computer (you know, with all the flashing lights). In fact, the earliest computers did display the results and memory values with lights, with toggle switches used to set the initial values.

One set would select the memory address and another set would set up the values to go into that memory address. There were no keyboards, mice and LCD displays in those days. It was all done by lights and switches. Being a programmer was a tough job.

Totalling a list of numbers

Let’s get back to the programming. A very common task in programming is adding up a list of numbers, say 3, 7, 4, 6 and 5. So let’s try that...

We will need to save any previous program in Simple Computer and, after clearing the memory, we can enter these numbers into memory addresses 16 to 20. We will use location 31 for the result, so write the instruction to clear that value first. Yes, write ‘MOV [31], AC’ - the accumulator is also set to zero when Simple Computer is reset. Now go ahead and write a program to add these five numbers...

Done? Good. You may have simply used five add instructions, which is okay, but your program will then only work for lists of five numbers. What if we wanted to add six numbers, or seven, or a hundred? We need something more flexible, so let’s put a 5 in memory location 30 and, to make our program re-usable we should write the code to copy that to memory location 29. That is:

MOV AC, [30]
MOV [29], AC

Now, try to write the program decrementing the number in [29] each time and jumping when not equal to zero. Can you see the problem? How do you change where the ADD instruction gets its value from. You could say:

ADD AC, [16]

That gives the first value. Then next time around you want this to say:

ADD AC, [17]

Then:

ADD AC, [18]

And so on, but how can we do this? Well, one approach is to change the code itself. Yes, that’s right. The program is going to change itself, as it runs. Here is the ADD instruction for ADD AC, [16]:
0010011000000000

Let’s break it up, remembering we are in Intel style, so things are a bit back to front

0010 = ADD
01 = Direct Addressing Mode

Then the two operands are:

10000 (memory address 16)
00000 (the accumulator)

I want to change the memory address to be the next one (i.e. 10001), which would give us 0010011000100000. So, why don’t I just load in the whole binary word and add the one to it. After all, the computer doesn’t care what I do to it. But notice it isn’t one that I want to add, but 1 and the 00000 i.e. 100000 (because I have a second operand.) This number is 32. It would be nice if I could just use this as a literal and do something like:

(load in the ADD instruction)
MOV AC, [4] (i.e. the ADD instruction is in memory location 4, say)
ADD AC, 32
MOV [4], AC

Unfortunately, I cannot store 32 as a literal, as I only have five bits and the maximum number I can use as a literal is 31. No matter, we can simply store 32 in a memory location, say at [28] and add this. In other words:

MOV AC, [4]
ADD AC, [28] (where the number 32 is stored)
MOV [4], AC

The instruction will then read:

ADD AC, [17]

Exactly what we wanted! We can then repeat this each time we need to add the next number from the list. The code in full is at Fig. 1
Now when you run it, perhaps step by step at first, you will see that memory address four changes from ADD AC, [16] to ADD AC, [17] and so on. We get the result 25 at the end.

Of course this means that our program has changed and we need to restore the correct line of code in order to run the program again. Not too difficult, but a bit of a pain (and actually very painful in the Simple Computer - you actually have to store “MOV AC, [16]” somewhere and store it at memory location four before the main part of the code runs. This type of programming is called self-modifying code and is to be avoided like a nest of wasps. It is extremely difficult to find errors and to fix code like this. We need a better way.

Indirect addressing

If we look more closely at the problem we have, we can see that we need some method of changing where the ADD instruction gets its operand from. We looked at changing the code itself, but what if we had a memory location that stored the address of the next number to add?

Let me repeat that: we need a memory location that contains a memory location that holds the value we want.

If we want to add the next number we then change the value of the memory location stored in the first memory location. It is definitely hard to get your head around this at first.

So we ADD AC,

Then what we are doing is getting the contents of the memory location pointed to by the contents of memory location 25, that is from memory location 16 which contains the number we want to add. Note how we use double square brackets to show this.

Now in order to change where we get our value from we only need to change the contents of memory address 25, say from 16 to 17. We can then add from memory address 17.

Internally the addressing mode is changed to 10 rather than 00 for literal or 01 for direct addressing mode. Our new program is at Fig. 3.

Did you notice the new instruction we used - INC. This increment the accumulator by 1. That means add 1 to the accumulator. This is used to point to the next memory address, where our data is stored. Also note that we make a copy of the memory address in 26 so that we can re-use the program.

Where next?

I’d like to say the sky’s the limit, but clearly not in this case. As we have discussed, the computer is severely limited by the amount of memory it can access. There are some additional instructions:

SUB: subtract
MUL: multiply
DIV: give the whole number part of a division
RDR: give the remainder part of a whole number division
JMP: jump to the specified memory location
JEZ: jump if equal to zero
JLT: Jump if less than zero, that is if the number is negative

That’s about it. I usually ask my students to write a program to calculate the factorial of a number, e.g. 5! = 5 x 4 x 3 x 2 x 1, which is fairly easy, and also to calculate the nth Fibonacci number, which is a little harder. (The Fibonacci sequence goes 1, 1, 2, 3, 5, 8, 13, 21, etc., each term is the result of adding the previous two terms). Another candidate is to work out if a number is prime (that is only has as factors 1 and itself, or to calculate a square root). Finding the highest common factor of two numbers using Euclid’s algorithm is a possibility as well. Why not post any solutions to these or other problems to the Micro Mart forum, I’d be really interested in seeing them.

The source code is available if you want to send me an email (gfmoore01@gmail.com). This is provided on the basis that you supply any source code improvements back to me for further distribution to others.

Feel free to redesign the machine as well. I know it can be improved, but I just don’t have the time. It may be that you are enthused enough to start writing in real assembly language and there are a many sources of information available as listed in the further information boxout.

I hope that these articles have given you some understanding of just some of what is happening under the hood the next time you write an email or post a tweet.

Further information

Obtain the SimpleComputer.exe as a zip file: bit.ly/RWjPVX
Programming From the Ground Up: bit.ly/SsM2k2
Dr Paul Carter’s Assembly language for the PC: bit.ly/Zktz1
EMU8086 - an 8086 Emulator: bit.ly/XJ2ZNA