Sunday 27 April 2014

Binary Adder written in C++ (Binary Logic in Code)

In our virtual CPU so far, when adding we've simply used the arithmetic operation "+" on our bytes.

You can see Part 1 or Part 2 yourself.

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!

5 comments:

  1. This is pretty amazing stuff, I'm saddened as I'm unsure if my maths is good enough to start going this low down. :(

    ReplyDelete
    Replies
    1. This is as low as we can go... 1 + 1 = 10... Tada :) very seriously though, go look at any electronics for processing and the first thing they'll introduce is the half-adder then the full-adder. Which is just logic gates, we have the same thing here in C++ code. And once written into our CPU, we just call "Add"... This fundamentally explains how a computer is built up... I'm already filming putting this into the CPU and testing a few adding programs for speed, then using it to do the Mutliply command, once that's done, this week will do signing the values...

      Delete
    2. I have looked at electronics, it really interests me but my head just doesn't seem to compute it half the time so I ended up switching to a computer science course instead of an electronic engineering one so I know I wouldn't fail and bring myself into a heavy debt.

      After finishing off my debugging mode ( I've added colour woo ) I'm going to try and write this logic today.


      If I complete it today with any luck I'll carry on with my '4001B' and finish off the 16bit addressing mode. :)

      I can't thank you enough for these tutorials.

      Delete
    3. 16 bit is the 4004 ;) or the Z80, which I was planning to look at as I moved through... If you go back through the last couple of weeks of my posts you'll find my posting about an Altair 8800 series... I'm aiming to get my machine there, but will have to swap to a real CPU instruction set soon... But yeah, a running program, which is an emulator, which I can serial port connect to, would be interesting... A complete waste of compute cycles, but interesting to me. lol.

      Delete
    4. Tomorrows post is already scheduled, you can get a sneak peak from my C++ Play list on YouTube... but the post itself will help.

      Delete