A blog about my rantings, including Games, Game Development, Gaming, Consoles, PC Gaming, Role Playing Games, People, Gaming tips & cheats, Game Programming and a plethora of other stuff.
I'm afraid I have a very busy week on my hands, both with work project and home projects, so no CPU project update his week. However, I have just spent an inordinate amount of time trying to think around a problem which I've come to the conclusion is in the Operating System below my software.
And I set about the interwebs to satisfy my self proclaimed hunch... I'm yet to get my confirmation, but I did run across this two year old post which pretty much sums up working on any damn project in Windows.
The next CPU Update may be skipping to the Z80 CPU, so bear with me... Is that the right spelling of bear?... Bare... Bear... Whatever... Stick around!
This post forms part of a series, you can start at Part One here.
First things first, armed with our Electronics code, containing our Binary Adder in C++ we can go to our CPU and change the arithmetic logic add function for our new "AddTwoBytes" electronics function...
We can also, for the first time set the Overflow flag!
We saw our first program ran once again, try out some more yourself...
However, we're still very much limiting our CPU, and before we can go much further we need to introduce to ourselves the idea that the CPU, rather then using a reserved byte in memory, or the two registers we already have it performs arithmetic into an intermediary location, a temporary store if you will, this was a natural evolution of real processors, they moved from having very few registers and using the memory to store intermediate values to using new internal registers. As the electronics got cheaper and the processors for creating chips streamlined and one of the first things added was this temporary location.
So in our code where we see:
Register0 = Register0 + Register1;
Really the register has no idea about overflows it just holds a binary number, now we've included out Binary Adder we get the overflow, so really storing the resulting value back to register 0 is a bit of a fudge.
The real location it should go to is called the Accumulator, in fact when the Accumulator was added to processors it gave rise to a whole new way of thinking in computing, and some even call it "Accumulator Based Computing" or ABC. I was very briefly introduced to this during my A-Level Computing course in 1994, however 20 years on I have yet to meet a recent software graduate who realises there was a time when we didn't store intermediates in the processor.
For using an Accumulator has become so ubiquitous as completely block out the idea of labouring saving values back and forth with the memory as we have been doing. Indeed my wishing to highlight that using an Accumulator is not the same as storing to a register then saving to memory has been the reason behind our labouring over our registers and reserved memory!
To add an accumulator however we need a new specification for our CPU...
You can read more about accumulators and their history here.
So now we include the Accumulator, and fix the bugs I made by making a mistake in the last video :)
Armed with an accumulator, and the Overflow flag working, we can now implement our Multiply differently...
Clear Accumulator to zero
for each time add value to accumulator
if overflow halt
This is not an unreasonable implementation, it is also a lot shorter already, you see we're still building more and more into the CPU, and again because this is something which could be done by a program adding this is a complex operation, so our CPU is a CISC architecture.
However, we still need to store the count of times through the loop in memory and swap it back and forth, so we clearly need a new register in our CPU another accumulator, but one for counting iterative processes... How does a real processor handle this?
Well, the processor contains a Complex of arithmetic operation modules, and many of them operate in different ways, if it were to implement the Multiply program in the CPU itself, storing the bytes of instructions to carry out this would be code within the processor itself. Code inside a processor like this is often called "Microcode", however, what we're after is not microcode because we know its slower, what we want is to use the accumulator for the cumulative addition of the multiply, and then we want to count how many multiplies into another register...
This use of iterating (repeating) additions to achieve a multiplication is quite old, but we're all about building up knowledge... so on our processor we need a new counter... And that is exactly what I'm going to call it.
Now we can add some new op codes, lets add them to clear the accumulator, load the next value in memory into the accumulator and clear the counter...
With these our multiply is going to contain microcode to clear the counter, load the two parameters into registers 0 and 1 then perform a loop. The loop we're going to perform is summing into the accumulator, taking it as a parameter itself, and we're going to simplify that the logic controlling the counter is included in the cpu for us... Yes we're going to cheat.
Our machine code program just then was:
// Load 0 from 20
1
100
// Load 1 from 21
2
101
// Multiply
14
// Store accumulator to 0
22
// Store 0 to 22
5
22
// Print from 22
6
22
As you saw, we got our answer 15... You try some other multiplications... And of course see what happens when we over flow... think about adding op codes to report to your program whether it has an overflow, how would we check? Would we load overflow into a register and then compare it? Should we Halt the whole processor?
So having noted down its coordinates I went to the above ground coordinates and decided to make a water trap, leading to a mob elevator to bring them up to ground level...
I cleared the forest, and began to build...
Once it was working, I then made it a tad taller, to put the skeletons onto 1 hit kills, and made this an Arrow/Bone/XP farm, my first serious farm... But it got a little taller...
I'm not sure whether my weekend actually deserved to contain the word "end", because I didn't stop once, between jet washing, and cooking, shopping and actually coming into the office on Saturday I don't feel rested at all...
I did get to play some Minecraft however - screen shots to follow - and I also began more looking into OpenGL, you can skip back through the blog and see I was working on texture mapping some area and viewing it a few years ago, I never really got to use that as work in the office took me in a different location.
But I'm looking at an OpenGL application to leverage Windows, Linux and MacOS... Possibly even OpenGLES, so the Pi & mobile platforms in the longer run.
I have prepared Wednesdays next post about the Virtual CPU code we're working on, so stay tunes for that...
Of course this is NOT how a real processor handles adding, a real processor adds in binary. There are many better sources for binary addition instructions out there, so rather than labour the point let us just cover the important point which is carrying...
Given a 4 bit binary number, we could add like this:
0000
+ 0000
------
0000 (No Carries)
0001
+ 0000
------
0000 (No Carries)
0001
+ 0001
------
0010 (Carry over 1 to the next column)
What we're doing is looking at the columns and performing a truth operation, 0 + 0 = 0, 0 + 1 or 1 + 0 = 1 and 1 + 1 = 1 plus a carry... The first column (the right most) is always starting with a carry of zero.... So in this third binary sum the second column when we come to evaluate it will have a carry over, and the sum is now 0 + 0 + 1 = 1.
Essentially we take each column, plus an input so three inputs and turn it into two outputs, one being the value we want to store and the other being the third input into the next column.
This is known as a combinational logic circuit, and again there are many many other better sources to explain this to you...
What has this got to do with our CPU though? Well, we've so far added with the processor in our machine, we've not looked at the actual nuts and bolts of addition. At the silicon level what we have is a bunch of logic gates, these flow electrical current around.
We'll consider the positive electrical current represented by a "boolean" set to true, and a negative or null, electrical current as a "boolean" set to false.
When we present our Register instead of a byte in our code really we should hold a set of 8 boolean's.
I'm not going to go that far, instead I'm going to implement some electronics in software to manipulate our bytes like they're binary electrics.
The first thing we need to think about is something known as an Adder, you can go look elsewhere for the full low down, however there are two kinds of adder, a full adder which takes the two columns and the carry in and gives the sum plus a carry out... And then there is a half-adder, which just adds the two binary values together and it forms a sub-part of the full adder.
Now these adders are circuits with logic gates, we've got similar logic for acting on boolean's in C++... "&&" is a logical "AND"... "||" is a logical "OR"....
With this code:
bool a = true;
bool b = false;
bool c = a && b;
c will have a value of false, both a AND b were not true.
bool d = a || b;
d will be true, because one of a OR b was already true...
We need three logical operations to create an adder... AND and OR, but also we need XOR, this is Exclusive OR, whereby in the example above d would only be true if only one of the inputs was true, if both inputs were true, or both inputs were false then d would have been false.
Lets get on with a live coding session creating our electronic logic in code form. We're going to build debugging into this, so you will see examples of both Binary Logic, Binary Shifting and the std::bitset, all useful things for manipulating binary data in programs.
So that's a binary adder implemented in C++.
But on its own its not much use, we need to add two of our registers together.
In a real CPU the adders would be wired to the register bits with wires, physical gold wires inside the chip. But we can't do that, so instead I'll pass both registers by reference to a function which will operate directly on them and return the new value plus whether there was an overflow.
So this function will carry out the binary addition on each column in the register, I'll do this in code with a moving mask, to I shift the bit we're interested into the right hand most column each time and then run the adder on it and then mask and shift the bit result back into the register.
You may find other ways... That's a challenge!
So now we can see adding two unsigned bytes, and their overflowing being reported.
How might we then change our CPU?... Well, this adder only works in unsigned mode, so in our CPU we can check if we're in Unsigned mode and employ this adder and now successfully set the over flow flag!
With that done, lets think what else you need to do... Well, in our Machine Code programs it would be nice to know whether we've had an over flow after an addition...
Now, with an addition in our CPU we can see that the adder leaves some value in register 0 which might be of use, it might have overflowed, but it contains the remainder.
So, how about we add an instruction Op Code which loads the overflow flag into register 1. We can then save register 0 somewhere, clear register 0 and do a jump equal based on the value!
I'll leave you to do this yourself... There is no code with this edition, the code will come later, but you can see my code in the video... Lets see those YouTube likes & subscriptions folks!
