In my previous post we discussed creating a Virtual CPU in software, today we'll go a little further and create the assembler application, and expand the CPU a little to execute the binary output of that assembler application.
In my very popular post of yesterday, regarding writing ones own virtual CPU in C++ code we speculated about a virtual instruction set, and talked about the asembly language such a virtual machine, and real machines, would use to be instructed by us mere mortals and briefly touched on the topic of assemblers and compilers.
Today, we're going to go a step further with our discussion of the assembler software and the assembly language our virtual CPU uses, so we get a brief insight into how an assembler can be made to work. This will take the form of a complete code example of an assembler to take assembly instructions and turn them into valid code for our virtual CPU, as well as some additions to the virtual CPU application so we can save our assembler output as binary and then run it through the virtual CPU... Making our little virtual CPU a proper programmable device!
Preprocessing
First things first we need to write our assembler program, to do this we need to understand how an assembler works, how compilers work in general. The first step of such software is to take the code given it by the user and to homogenise it for processing. This means we might strip white space, we might check for the inclusion of other files and generate a large conglomerate of numerous code files all together as a single unified body, either on disk or in RAM. For our assembler we're going to perform a pre-parsing step just like this to prepare the code, this will load the whole line as a set of lines (remember we can only have 256 instructions because of the 8 bit width of our CPU, so there won't be that much to hold in RAM) and we're going to convert each line into uppercase characters and then trim any white space off of the front and back of each line.
So, code like this:
load0 3
load1 17
add
Will end up like this:
LOAD0 3
LOAD1 17
ADD
Lexical Analysis
The next step is to analyse each line for validity, we need to make sure each line has the right number of parameters and is an instruction we understand. Most importantly we need to tell the user if its not!
Our lexical analysis is simple, for each line validate what the programmer asks is valid for the processor to carry out.
Assembling
Finally we know the code is valid and formatted right, we can now go a head and convert the human readable assembly language into assembled instructions, so we translate each byte (you see now why we wrote such a simple CPU) and store them in a linear vector, just like the vector we pass through the CPU execute function.
Full Source Code of our Assembler
#include <fstream>
#include <string>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <cstdio>
#include <string.h>
#include <vector>
#include "cpu.hpp"
namespace Assembler
{
using namespace std;
using namespace Emulator;
typedef unsigned char byte;
class Assembler
{
private:
static const string LOAD0;
static const string LOAD1;
static const string STORE0;
static const string STORE1;
static const string ADD;
static const string SUBTRACT;
static const string STORETO;
static const string whitespaces;
void trimRight (string& str, const string& trimChars = whitespaces)
{
string::size_type pos = str.find_last_not_of( trimChars);
str.erase( pos+1 );
}
void trimLeft (string& str, const string& trimChars = whitespaces)
{
string::size_type pos = str.find_first_not_of( trimChars );
str.erase(0, pos);
}
void trim (string& str, const string& trimChars = whitespaces)
{
trimRight(str);
trimLeft(str);
}
vector<byte> m_Inst;
vector<string> m_Code;
bool m_Error;
string m_LastError;
const vector<string> Split (const string& p_String)
{
vector<string> result;
string temp;
istringstream stm (p_String, istringstream::in);
while ( stm.good() )
{
stm >> temp;
result.push_back(temp);
}
return result;
}
void ToUpper (string& p_String)
{
transform (p_String.begin(), p_String.end(), p_String.begin(), ::toupper);
}
void LoadCode (const string& p_Filename)
{
m_Code.clear();
string tmp;
tmp.resize(256);
ifstream file(p_Filename.c_str(), ios_base::in);
while ( file.good() )
{
memset(&tmp[0], 0, 256);
file.getline (&tmp[0], 256);
trim(tmp);
string news (tmp.c_str());
if ( news.length() > 0 )
{
m_Code.push_back(news);
}
}
file.close();
}
void PreprocessCode ()
{
vector<string>::iterator itr;
for (itr = m_Code.begin(); itr != m_Code.end(); itr++)
{
ToUpper((*itr));
}
}
void ListCode ()
{
cout << "----------" << endl;
vector<string>::const_iterator itr;
for (itr = m_Code.begin(); itr != m_Code.end(); itr++)
{
cout << (*itr) << endl;
}
cout << "----------" << endl;
}
void ListInstructions ()
{
cout << "Instructions Generated:" << endl;
vector<byte>::const_iterator itr;
for (itr = m_Inst.begin(); itr != m_Inst.end(); itr++)
{
cout << (int)((*itr)) << endl;
}
}
void Assemble ()
{
cout << "Assembling " << m_Code.size() << " lines of code" << endl;
int lineNumber = 0;
vector<string>::const_iterator itr;
for (itr = m_Code.begin(); itr != m_Code.end(); itr++)
{
lineNumber++;
cout << lineNumber << ". [" << (*itr) << "]" << endl;
vector<string> split = Split((*itr));
Translate (split, lineNumber);
if ( m_Error )
{
cout << "Error, aborting Assemble" << endl;
break;
}
}
}
void TranslateError (const vector<string>& p_Line, const int &p_LineNumber)
{
cout << "Assemble [Translate] Error at [" << p_LineNumber << "]" << endl;
cout << "Message: " << m_LastError << endl;
m_Error = true;
}
const bool ProcessLoad0 (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 2 )
{
try
{
if ( p_Line[0] == LOAD0 )
{
string tmp = p_Line[1];
int value = stoi(tmp);
if ( value >= 0 && value <= CPU::MAX )
{
m_Inst.push_back(CPU::LOAD0);
m_Inst.push_back((byte)value);
l_result = false;
}
else
{
m_LastError = string ("LOAD0 Parameter out of range, must be (0 - 255)");
}
}
else
{
m_LastError = string("Assembler Error; Trying to translate line as LOAD0, when its not LOAD0?");
}
}
catch (exception& l_e)
{
m_LastError = string("Error Processing Load0 Instruction");
}
}
return l_result;
}
const bool ProcessLoad1 (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 2 )
{
try
{
if ( p_Line[0] == LOAD1 )
{
string tmp = p_Line[1];
int value = stoi(tmp);
if ( value >= 0 && value <= CPU::MAX )
{
m_Inst.push_back(CPU::LOAD1);
m_Inst.push_back((byte)value);
l_result = false;
}
else
{
m_LastError = string ("LOAD1 Parameter out of range, must be (0 - 255)");
}
}
else
{
m_LastError = string("Assembler Error; Trying to translate line as LOAD1, when its not LOAD1?");
}
}
catch (exception& l_e)
{
m_LastError = string("Error Processing Load1 Instruction");
}
}
return l_result;
}
const bool ProcessAdd (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 1 )
{
if ( p_Line[0] == ADD )
{
m_Inst.push_back(CPU::ADD);
l_result = false;
}
else
{
m_LastError = string ("Error processing Add instruction");
}
}
else
{
m_LastError = string("Process Add had nothing to do");
}
return l_result;
}
const bool ProcessSubtract (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 1 )
{
if ( p_Line[0] == SUBTRACT )
{
m_Inst.push_back(CPU::SUBTRACT);
l_result = false;
}
}
else
{
m_LastError = string("Process Subtract had nothing to do");
}
return l_result;
}
const bool ProcessStore0 (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 1 )
{
if ( p_Line[0] == STORE0 )
{
m_Inst.push_back(CPU::STORE0);
m_Inst.push_back(CPU::MAX);
l_result = false;
}
}
else
{
m_LastError = string("Process Store0 had nothing to do");
}
return l_result;
}
const bool ProcessStore1 (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 1 )
{
if ( p_Line[0] == STORE1 )
{
m_Inst.push_back(CPU::STORE1);
m_Inst.push_back(CPU::MAX);
l_result = false;
}
}
return l_result;
}
const bool ProcessStoreTo (const vector<string>& p_Line)
{
bool l_result = true;
if ( p_Line.size() == 3 )
{
try
{
string tmp1 = p_Line[1];
string tmp2 = p_Line[2];
int reg = stoi (tmp1);
int var = stoi (tmp2);
if ( reg == 0 || reg == 1 )
{
if ( var >= 0 || var <= 3 )
{
m_Inst.push_back(CPU::STORETO);
m_Inst.push_back((byte)reg);
m_Inst.push_back((byte)var);
l_result = false;
}
else
{
m_LastError = string("Error in StoreTo instruction, invalid target Variable. Only 0, 1, 2 or 3 allowed!");
}
}
else
{
m_LastError = string("Error in StoreTo instruction, invalid register. Only 0 or 1 allowed!");
}
}
catch (exception& l_ex)
{
m_LastError = string ("Error converting StoreTo Parameters");
}
}
else
{
m_LastError = string("Error in StoreTo Parameters");
}
return l_result;
}
void Translate (const vector<string>& p_Line, const int& p_LineNumber)
{
bool error = true;
size_t sze = p_Line.size();
if ( sze > 0 )
{
if ( p_Line[0] == "" )
{
error = false;
}
else if ( p_Line[0] == LOAD0 )
{
error = ProcessLoad0 (p_Line);
}
else if ( p_Line[0] == LOAD1 )
{
error = ProcessLoad1 (p_Line);
}
else if ( p_Line[0] == ADD )
{
error = ProcessAdd (p_Line);
}
else if ( p_Line[0] == SUBTRACT )
{
error = ProcessSubtract (p_Line);
}
else if ( p_Line[0] == STORE0 )
{
error = ProcessStore0 (p_Line);
}
else if ( p_Line[0] == STORE1 )
{
error = ProcessStore1 (p_Line);
}
else if ( p_Line[0] == STORETO )
{
error = ProcessStoreTo (p_Line);
}
else
{
cout << "Unknown Instruction [" << p_Line[0] << "]" << endl;
m_LastError = string("Unknown Instruction");
}
}
else
{
m_LastError = string ("Nothing to do");
}
if ( error )
{
TranslateError (p_Line, p_LineNumber);
}
}
void OutputInstructions ()
{
ofstream file ("asmout.bin", ios_base::out | ios_base::binary);
vector<byte>::const_iterator i;
for (i = m_Inst.begin(); i != m_Inst.end(); i++)
{
file.write(reinterpret_cast<const char*>(&(*i)), sizeof(byte));
}
file.close();
}
public:
Assembler (const string& p_Filename)
:
m_Error (false),
m_LastError (string(""))
{
LoadCode (p_Filename);
PreprocessCode ();
Assemble();
ListInstructions();
OutputInstructions();
}
~Assembler ()
{
}
};
const string Assembler::LOAD0 = string("LOAD0");
const string Assembler::LOAD1 = string("LOAD1");
const string Assembler::STORE0 = string("STORE0");
const string Assembler::STORE1 = string("STORE1");
const string Assembler::ADD = string("ADD");
const string Assembler::SUBTRACT = string("SUBTRACT");
const string Assembler::STORETO = string("STORETO");
const string Assembler::whitespaces = string("\0 \f\n\r\t\v");
}
Advanced Assembling
We're not going to go further than this with our example of an assembler, but you need to know that this is a very rudimentary example, assembling a single file into a single stream of instructions... In a future post we're going to look at defining more advanced structures for our virtual CPU, and therefore expand our assembler.
Alterations to our Virtual CPU
Below is a set of changes to the code of the Virtual CPU, go a head and take a look. We add a new piece to the main function of "RunCPU" so we can pass in a file to execute, this file will be the binary output of our assembler. And we invent the idea of the CPU having an amount of memory available. I'm modelling this memory in the CPU as a set of bytes, which can be assigned as variables VAR0 VAR1 VAR2 VAR3 in our assembler.
In other CPU's these bytes might be allocated in the main system memory, or RAM, and the addresses passed to the CPU so it knows where to store the values! Other CPU's might do this by loading the target memory address into a register, the value to store into another register and being told to store the value off to that location. In our virtual CPU what we have altered is the instruction set, the old STORE0 and STORE1 instructions remain, we can't change them incase we've got a program already using them, so instead we created a new instruction STORETO this takes two parameters, the first is which register we're going to store to somewhere (so a byte of 0 or 1 for register0 and register1 respectively) and the second parameter is the location we're going to store to (so 0, 1, 2, 3 to represent VAR0 VAR1 VAR2 and VAR3).
Below is the full code for the CPU, but I will highlight the changes in bold. However, the most important items are within the new function "DoStoreTo", because we want to store the value of a register to somewhere, we need to use the other register to let the CPU remember what we're doing. This is the burden an assembly language user carries, they must coax out of quite simple instructions very complex results. In this example we need to get the next byte off of the program listing so we know which register is going to be saved to, but without destroying the value in either register... I can't just invent a new location for this value to go into, so I need to find somewhere on the CPU it can go. We can't use the VAR's there might already be values in them, I can't use the instruction register or the program counter... I do have the temporary register however, so I'm going to load the first parameter into the temporary register and step the program counter, but we also need the next parameter, so we know the target location... Ahaaa, temporary is bigger than a byte... if it can hold two we can manipulate it to do the work for us, to store two bytes at a time!
You'll therefore see in the code that the temporary value is loaded with the next two bytes and then we mask off the temporary structure with some binary logic masks - CPU's are very good at using masks - to let the CPU decide what to do for us... (Yes, I know every electrical engineer reading this has just closed their web browser, as this is all rather abstract and all too much cheating, but since we're just demonstrating the principle of assembler, we're doing it this way - despite the fact that this is not actually how a CPU would do things, we'll get to that far more complex stuff much later).
#ifndef CPU_HEADER
#define CPU_HEADER
#include <iostream>
#include <vector>
namespace Emulator
{
using namespace std;
typedef unsigned char byte;
class CPU
{
public:
static const byte MAX;
enum InstructionSet
{
LOAD0 = 0,
LOAD1,
ADD,
SUBTRACT,
STORE0,
STORE1,
STORETO
};
private:
byte m_Register0;
byte m_Register1;
byte m_VAR0, m_VAR1, m_VAR2, m_VAR3;
bool m_Status;
bool m_Overflow;
bool m_Underflow;
byte m_ProgramCounter;
byte m_InstructionRegister;
int m_Temp;
CPU (const CPU&) {}
void ResetCPU ()
{
m_Temp = 0;
m_Register0 = 0;
m_Register1 = 0;
m_Status = true;
m_Overflow = false;
m_Underflow = false;
m_ProgramCounter = 0;
}
void Fault ()
{
m_Status = false;
cout << "Instruction Fault at: " << static_cast<int>(m_ProgramCounter) << endl;
DumpRegisters();
}
void DumpRegisters ()
{
cout << "CPU Registers:" << endl
<< "Register0 [" << static_cast<int>(m_Register0) << "]" << endl
<< "Register1 [" << static_cast<int>(m_Register1) << "]" << endl
<< "Status [" << m_Status << "]" << endl
<< "Overflow [" << m_Overflow << "]" << endl
<< "Underflow [" << m_Underflow << "]" << endl
<< "Program Counter [" << static_cast<int>(m_ProgramCounter) << "]" << endl
<< "Instruction Register [" << static_cast<int>(m_InstructionRegister) << "]" << endl
<< "Temp [" << m_Temp << "]" << endl;
}
void DoLoad0 (const vector<byte>& p_Program)
{
m_Register0 = p_Program[m_ProgramCounter];
m_ProgramCounter++;
}
void DoLoad1 (const vector<byte>& p_Program)
{
m_Register1 = p_Program[m_ProgramCounter];
m_ProgramCounter++;
}
void DoAdd ()
{
m_Temp = m_Register0 + m_Register1;
if ( m_Temp > MAX )
{
m_Overflow = true;
m_Temp = MAX;
}
m_Register0 = m_Temp;
}
void DoSub ()
{
m_Temp = m_Register0 - m_Register1;
if ( m_Temp < 0 )
{
m_Underflow = true;
m_Temp = 0;
}
m_Register0 = m_Temp;
}
void DoStore0 (vector<byte>& p_Program)
{
p_Program[m_ProgramCounter] = m_Register0;
m_ProgramCounter++;
}
void DoStore1 (vector<byte>& p_Program)
{
p_Program[m_ProgramCounter] = m_Register1;
m_ProgramCounter++;
}
void DoStoreTo (const vector<byte>& p_Program)
{
m_Temp = 0;
m_Temp << p_Program[m_ProgramCounter];
m_ProgramCounter++;
if ( m_Temp & 0x00 )
{
m_Temp = 0;
m_Temp << p_Program[m_ProgramCounter];
if ( m_Temp & 0x00 )
{
m_VAR0 = m_Register0;
}
else if ( m_Temp & 0x01 )
{
m_VAR1 = m_Register0;
}
else if ( m_Temp & 0x02 )
{
m_VAR2 = m_Register0;
}
else if ( m_Temp & 0x03 )
{
m_VAR3 = m_Register0;
}
else
{
Fault();
}
}
else if ( m_Temp & 0x01 )
{
m_Temp = 0;
m_Temp << p_Program[m_ProgramCounter];
if ( m_Temp & 0x00 )
{
m_VAR0 = m_Register1;
}
else if ( m_Temp & 0x01 )
{
m_VAR1 = m_Register1;
}
else if ( m_Temp & 0x02 )
{
m_VAR2 = m_Register1;
}
else if ( m_Temp & 0x03 )
{
m_VAR3 = m_Register1;
}
else
{
Fault();
}
}
else
{
Fault();
}
m_ProgramCounter++;
}
public:
CPU ()
{
ResetCPU();
}
~CPU ()
{
}
void Execute (vector<byte>& p_Program, const bool& p_HaltOnOverflow = true, const bool& p_HaltOnUnderflow = true)
{
ResetCPU();
if ( p_Program.size() == 0 )
{
cout << "No Instructions!" << endl;
return;
}
if ( p_Program.size() > MAX )
{
cout << "Error: Unable to process program, more than 255 instructions" << endl
<< "this is more than the Program Counter can handle" << endl;
}
else
{
while ( m_ProgramCounter < p_Program.size() )
{
m_InstructionRegister = p_Program[m_ProgramCounter];
m_ProgramCounter++;
switch (m_InstructionRegister)
{
case LOAD0:
DoLoad0 (p_Program);
break;
case LOAD1:
DoLoad1 (p_Program);
break;
case ADD:
DoAdd ();
break;
case SUBTRACT:
DoSub();
break;
case STORE0:
DoStore0(p_Program);
break;
case STORE1:
DoStore1(p_Program);
break;
case STORETO:
DoStoreTo (p_Program);
break;
default:
Fault();
return;
}
if ( m_Overflow && p_HaltOnOverflow )
{
cout << "Overflow - Halt" << endl;
return;
}
if ( m_Underflow && p_HaltOnUnderflow )
{
cout << "Underflow - Halt" << endl;
return;
}
}
}
}
};
const byte CPU::MAX = 255;
}
#endif
To compile and use these classes I then have two files, "RunCPU.cpp" and "RunAsm.cpp", the code for which are:
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
#include "cpu.hpp"
using namespace std;
using namespace Emulator;
int main (const int argc, const char* argv[])
{
CPU* cpu = new CPU ();
cout << "CPU Ready..." << endl;
vector<byte> inst;
if ( argc == 2 )
{
cout << "Loading Instructions...";
ifstream ifs(argv[1], ifstream::in|ifstream::binary);
int count = 0;
while ( !ifs.eof() && ifs.good() )
{
byte temp = (byte)ifs.get();
if ( !ifs.eof() )
{
count++;
inst.push_back(temp);
}
}
ifs.close();
cout << "Complete [" << count << "]" << endl;
}
cout << "Starting Execution..." << endl;
cpu->Execute(inst);
cout << "Execution Complete" << endl;
vector<byte>::const_iterator itr = inst.begin();
for ( ; itr != inst.end(); itr++)
{
cout << "[" << static_cast<int>((*itr)) << "]" << endl;
}
cout << "Complete" << endl;
delete cpu;
return 0;
}
And:
#include <string>
#include "Assembler.hpp"
using namespace std;
int main (const int argc, const char* argv[])
{
if ( argc == 2 )
{
Assembler::Assembler* asmb = new Assembler::Assembler (string(argv[1]));
delete asmb;
}
else
{
cout << "Usage: " << endl
<< "\tRunAsm <Filename>\t\tWhere <Filename> is the assembly text file." << endl;
}
return 0;
}
Respectively, with these we can compile the code with:
g++ -std=c++0x -I~/ ~/RunCPU.cpp -o runcpu.o
g++ -std=c++0x -I~/ ~/RunAsm.cpp -o runasm.o
I can then assemble and run my code, which is whatever I want from our lexicon of commands, but for this demo its:
load0 1
load1 2
add
load1 1
subtract
Which I have saved as "Code.asm" in the home directory, so to now compile and run this assembly on our virtual CPU I perform:
~/runasm.o ~/Code.asm
~/runcpu.o ~/asmout.bin
Where "asmout.bin" is the output binary file from our written compiler...
Your CPU should execute your Assembly code now, and you should be able to re-run the CPU with each output... Try more assembly code sets... and remember to intentionally crash the CPU, make things go negative...
So, I was messing around with the code and found a huge issue: your implementation of STORETO is unusable. None of the bitwise operations will behave as you would expect them to, most notably that 0 & 0x00 will always evaluate to 0, which is false. Further, 3 & 0x01 will evaluate to true, 2 & 0x03 will always evaluate to true, and no matter what I did I couldn't get STORETO to work. Fortunately, I did find your work on this furthered in 2014, so I will give those a read and hope you fix this.
ReplyDeleteGood call, see one always needs a good tester.
DeleteLooking at my local copy, it's different to the posting from *cough*2012.... First of all, none of this code is C++14 compliant standard, so I'm already thinking about revisiting it to update for that.
DeleteSecond, the binary comparisons are different, you're right it should read something like....
(m_Temp & 0x01) == 0x01
0x02...
0x03... etc
It only took six years for someone to notice, despite this post getting around 300 views a day... impressive my young Padawan. I sense a great power in you, the power of Debugging.