Writing a Virtual CPU in C++ (Accumulators & Multiplication)

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!

Source Code here.

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?

Complete Code to this point...

Minecraft Ordeal #7

Whilst doing a little mining....

I found a skeleton spawner...

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...

But, the view from the top is ace...

Weekends Ending

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...

In the news I noted this article:  http://www.bbc.co.uk/news/entertainment-arts-27187582  

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!

Warhol's Amiga & Camoflage

Two Interesting pieces of obscure computer history came to light via the BBC today, one of which I'm amazed to see I'd already watched and contacted people about.

This video...

About the history of the development of the Amiga, I'd watched about a year ago, and I contacted R J Mical about whether he had any more of his talks video's and could upload them.  He even contacted me back asking about USB connectivity from video recorders - sorry R J I'm in the UK and was unable to help.

But then this article appeared today on the BBC, quite obviously they're talking about the Amiga Launch video which is tacked onto the end of the Amiga History video I had watched, in the above video skip to the 58th minute.

Warhol's Amiga on the BBC

It's interesting to see the PIC format described as un-readable, I can read it on my Atari ST's... If they'd have asked, I could have opened the format, converted it to 256bit BMP and re-saved it in about 15 minutes...

The other computing Gem was this article:

http://www.bbc.co.uk/news/entertainment-arts-26820227

Specifically the reference to Chris having created the  first every Computer Promo for a Music single, which has been uploaded to YouTube for a few years now, but which did have me very interested:

I'm surprised with it appearing on the BBC it still only has around 10,000 views though.

Load/Save Virtual CPU Memory State & Debugging Code (C++)

Before we go further with our CPU project we need to do some house keeping on the code, we need to add some helpers, the first I'm going to add is a "debug" flag to the CPU code, this is not an official part of our specification, so we leave our diagram for the chip unchanged.

This flag however is going to make some logging come out of our code, so we need to add the following headers to the CPU class header.

#include <string>

And inside the CPU class we're going to add a new function:

void Log(const std::string& p_Message);

The body of this function is going to be very boring:

void CPU::Log(const std::string& p_Message)

{

std::cout << p_Message << std::endl;

}

Simple squirting the message string to the output stream.

And we're going to add calls to this message function from all the other functions we use, so we know what the CPU is going to do... But first we need to add the new flag to the CPU:

bool m_DebugMode;

Then update the CPU class constructor to default this to false....

CPU::CPU(Memory* p_TheMemory)

:

c_ReservedAddress(0),

c_BaseAddress(2),

c_JumpToAddress(1),

c_AddressCeiling(253),

m_ProgramCounter(c_BaseAddress),

m_Register0(0),

m_Register1(0),

m_OverflowError(false),

m_UnderflowError(false),

m_SignedMode(false),

m_TheMemory(p_TheMemory), // DOH!

m_Halt(false),

m_DebugMode(false)

{

}

Next we need to be able to create the CPU in debug node, so we're going to add a parameter to the constuctor, but we're going to make this parameter optional, if the programmer does not pass the flag it will default to false, i.e. no debugging.  Only when they actively pass the flag as true will one see the debug output.

CPU(Memory* p_TheMemory, const bool& p_DebugMode = false);

And the implementation:

CPU::CPU(Memory* p_TheMemory,

const bool& p_DebugMode)

:

c_ReservedAddress(0),

c_BaseAddress(2),

c_JumpToAddress(1),

c_AddressCeiling(253),

m_ProgramCounter(c_BaseAddress),

m_Register0(0),

m_Register1(0),

m_OverflowError(false),

m_UnderflowError(false),

m_SignedMode(false),

m_TheMemory(p_TheMemory),

m_Halt(false),

m_DebugMode(p_DebugMode) // AND THIS!

{

}

This code compiles, we've changed the CPU constructor, but our code can still call it with just the memory parameter because we've specified a default for the debug mode!

Our first piece of logging is if we get an unknown OP Code, in our Decode function we need to add a new case, the default case... And we want to stop the application running if there's an invalid op code:

default:

Log("Unknown Op code - halting");

Halt();

break;

I'm going to set mine to log and then Halt, you might just want to Log, its up to you.  I always want this to happen, so there's no checking for debug mode!

So what do we want the CPU to outptu when we're in Debug mode?... Well the program counter each step would be good to know, so how about we start in the while loop within the Run function, before the Fetch we can add the following code:

if ( m_DebugMode )

{

    std::cout << "[" << (int)m_ProgramCounter << "]" 

              << std::endl;

}

Next in each op code function I'm going to add a debug message with "Log", so here's a few:

void CPU::Load1()

{

if ( m_DebugMode )

{

Log("Load1");

}

Or

void CPU::JumpEqual()

{

if ( m_Register0 == m_Register1 )

{

if ( m_DebugMode )

{

Log ("Jump Equal - Jumping");

}

JumpTo();

}

else

{

if ( m_DebugMode )

{

Log ("Jump Equal - Not Jumping");

}

// Skip over the address of the jump!

++m_ProgramCounter;

}

}

Or

void CPU::ClearBoth()

{

if ( m_DebugMode )

{

Log("Clear Both");

}

ClearRegister0();

ClearRegister1();

}

Then we also have functions which we want a little more debugging out of... Such as Add, it would be useful to have the values of the registers before and then after...

void CPU::Add()

{

if ( m_DebugMode )

{

Log("Add");

std::cout << "Before [" << (int)m_Register0 << ", " << (int)m_Register1 << "]" << std::endl;

}

m_Register0 = m_Register0 + m_Register1;

if ( m_DebugMode )

{

std::cout << "After [" << (int)m_Register0 << ", " << (int)m_Register1 << "]" << std::endl;

}

}

So we stream out the two registers before and after, and the same in multiply, what about a more complex operation like store?... Well, we could output the register when we've read in the target address, then output the value from the register we're saving and then we know what we jsut wrote & where.

void CPU::Store()

{

if ( m_DebugMode )

{

Log("Store");

}

// Load the target address into register 1

m_Register1 = m_TheMemory->Read(m_ProgramCounter);

if ( m_DebugMode )

{

std::cout << "Target Address: " << (int)m_Register1 << std::endl;

std::cout << "Value to Write: " << (int)m_Register0 << std::endl;

}

++m_ProgramCounter; // Skip the memory location data

// Write the register 0 value to this address

m_TheMemory->Write(m_Register1, m_Register0);

// Remember the order of our parameters

// was ADDRESS then VALUE!

if ( m_DebugMode )

{

std::cout << "Written value: " << (int)m_TheMemory->Read(m_Register1) << std::endl;

}

}

Finally to use the Debug Mode we need to add something into the main program... Well, I'm going to have a bool set to false, and add an option to my menu which toggles the flag... So everytime I use the toggle option debugging switches "debugging = !debugging", and on the menu I'm going to output the debugging setting.  You can do this yourself :)

Once done I just feed this into my "new CPU" call as the second parameter, and voila I can turn CPU debugging on and off to run my program.

Next, typing in all those program bytes is getting on my nerves, so how about we load them from a text file?

In the main menu I'm adding "S" and "L" and they are going to Load and Save the current memory, given a filename.

I'm going to pipe these to a simple pair of functions which ask for a filename, and then call into the Memory Class to load and save itself.

So the two functions I'm adding to the main program are like this:

void LoadMemory(Memory* theMemory)

{

if ( theMemory != nullptr )

{

cout << endl << "Load Memory from: ";

string filename;

cin >> filename;

theMemory->Load(filename);

cout << endl;

}

}

void SaveMemory(Memory* theMemory)

{

if ( theMemory != nullptr )

{

cout << endl << "Save Memory to: ";

string filename;

cin >> filename;

theMemory->Save(filename);

cout << endl;

}

}

In the memory header I then add "#include <string>" and these two function prototypes:

/// Save to file

void Save(const std::string& p_Filename);

/// Load from file

void Load(const std::string& p_Filename);

The memory save function is then very simple, for each byte in our address space (including bytes 0 and 1) we're going to write out the integer as text on a line, so each line of our file will contain one byte.

void Memory::Save(const std::string& p_Filename)

{

using namespace std;

ofstream file (p_Filename, ios_base::out);

if ( file.good() )

{

for (byte i = 0; i < c_MaxAddress; ++i)

{

file << (int)m_MemorySpace[i] << endl;

}

file.close();

}

else

{

cout << "Bad path [" << p_Filename << "]" << endl;

}

}

If we could not open the file, then we output bad path.

Load is similar, but we don't know how many bytes the user might give us, so lets follow through the code:

void Memory::Load(const std::string& p_Filename)

{

Clear();

So we've cleared the memory and everything is zero, we now know we need to open a file, so at the top of the file I'm going to add "#include <fstream>" and we also know we're going to convert the text we load into a binary number in memory so we need "#include <cstdlib>" the standard C library implementation for C++.

Our code then continues, opening the file and checking its good:

using namespace std;

ifstream file(p_Filename, ios_base::in);

if ( file.good() )

{

Next we need two values the index (byte) we've read to  and a temporary location for the text to number conversion we're doing each step.

int i = 0;

int temp;

And while the file is good, that is whilst we've not run out of bytes...

while ( file.good() )

{

Read a line of text...

string buff;

file >> buff;

Convert it from text (ascii to integer)...

temp = atoi(buff.c_str());

And then we assign the byte we loaded into the memory space we've got, and move onto the next memory index.

m_MemorySpace[i] = (byte)temp;

++i;

}

file.close();

}

else

{

cout << "File not found [" << p_Filename << "]" << endl;

}

}

This function is quick and dirty, it has some problems, if you can see them or want to address them and check back with me what you spot to build experience/knowledge let me know in the comments below.

Now when we want to write a program, we can just open a text editor, add two lines with "0" and "0" on them at the top to skip our reserved memory area and then enter bytes of memory...

Remember once you've used load, you can use Report Memory to list back what you've loaded.

So go a head try to use your virtual CPU before you just jump to the page with the code.

Ukrainian Viewers

I just took a look at my blog statistics and for the first time in year a new country is the number 1 source of viewers.  The usual top 3 have been:

United States, United Kingdom and then France, followed by Canada, Australia and then Russia.

Over the last week however one country has not only appeared on the list, but rocketed to the top spot above the United States... And that country is...

The Ukraine...

I like the Ukraine; I'm not making a political statement about the current strange activity and rhetoric coming from Russia; but I do like the Ukraine, I remember watching the celebrations in Kiev as they won independence in the 90's.  An old man crying like a baby, it struck me as quite a deep moment, almost like the fall of the Berlin wall.

I also remember the Ukraine for the coverage of Chernobyl when I was very young.

But quite what's bringing Ukrainian viewers I'm not sure... Would any of them like to tell me?  I don't know which post you're being directed to, and no post shows a sudden peak in interest... So I'm just in the dark.

General Dross

With a week between posts you might get an idea how busy I've been, I'm fighting several problems at work, project problems, and I'm also trying to figure a few things out at home.

Hopefully over the next few weeks some regular game-play items might be brought up.

I did have a play with some red stone and rails in a test work on Minecraft... And I had a few hours playing my big main world over the weekend... but Enjoyed a brief swim in Lava which put me off.

My current big world project is an mob spawner, which of course means I'm spending a lot of time lighting u p the caves below my world.

I've also enjoyed the latest installment from Acquisitions Inc...