Let’s write a Virtual Machine with it’s own instructions. Pt-1.

binary data into the void

Virtual Machines and how computers work means a lot to several developers, maybe you are one of these developers and always wanted to create or to understand about this topic.

I’m creating this series to cover the creation of a Virtual Machine from the beginning, first we are going to implement a working machine with several instructions, like a real one. After that we are going to create a higher level language to work with this Virtual Machine, it will be great since we are going to cover several low level concepts, parsing and interpretation of code.

Lets start. I’m using C, since it’s great and perfect, but you can use any language of your choice.

How a Virtual Machine works?

Several Virtual Machines work with stack’s, they are called Stack based Virtual Machines. Those machines perform pushing values to the stack and executing opcodes using these values, over and over again. Python is a good example, generally we say that Python is a slower language compared to other interpreted programming languages, that is a fact but it’s happening due to the way its Virtual Machines are built. LUA is an amazing example of a Register Based Virtual Machine, compared to Python it performs pretty great, but why?

The operation of pushing and popping data from the Stack makes the real machine code running behind these languages creates several instructions compared to a register based one, since this architecture brings something more close to a real CPU, you have some fixed number of registers, you can operate with there registers using pointers and you can interact with memory easily. In the end, the number of instructions that a register based machine will do is just smaller than a stack based one, making those machines faster.

Defining the basics of our CPU

For the sake of simplicity, we are going to have 8 general purpose registers, those registers can be manipulated by the programmer and they are able to store any 32 bits data.

Modern CPU’s like ARM64 Architecture can hold 64 bit numbers inside of its registers.

Be patient, let’s start with these general purpose registers.

So, to begin, our cpu will be like:

We’ve just created a cpu type that has an array of unsigned 32 bits integers that can hold 8 elements. That’s it. We have our 8 general purpose registers.

A register means nothing if it can’t hold numbers, so our CPU should understand when we say for example, I want to store the value 10 in the register one.

Let’s create our first instruction, and to begin we are creating the instruction to store value in a register. But how?
Well, computers understand binary, and our machine is trying to simulate that, so we tell our CPU to execute instructions through binary data, let’s understand more about this topic.

Our CPU will read 64 bits and store it in a 64 bit unsigned integer, it means that we have 64 bits to store any information we want(It’s a lot!). But remember that our registers are 32 bits long? So from these 64 bits we have to reserve 32 bits for values that we might use.

A quick example:
0000000000000000000000000000000100000000000000000000000000000011

This is a 64 bit binary number. You can see that if you take the last 32 numbers, you will have: 00000000000000000000000000000011 = 3 in decimal.

With binary numbers we must count by the last element to the first. Look that we have the 11 as the only enabled bits in this 32 bit binary number. It means that this binary number represents the number 3 in decimal. I’ll not cover how to convert binary to decimal, but if you are not familiar with this you can see this explanation (https://en.wikipedia.org/wiki/Binary_number).

We already know how to extract 32 bits from a number by looking at it, but we also need to extract at least 8 bits to represent our general purpose registers and other registers that we are going to implement in the future.

Another quick example,
0000000000000000000000000000000100000000000000000000000000000011.

First 32 bits represents the number 3, last 32 bits represents the number one, since we have just: 00000000000000000000000000001.
That is ok for our first instruction, we have a value for the number to be stored and the value that represents the identification of the register.

Let’s create some Macros that will lead us to a much more performance while extracting those bits.

It’s not that difficult as it looks. First let’s understand what is that 0x20 (32 in decimal). I put that Hexadecimal number to make you familiar with this representation, it saves a lot of time. Basically, in this Macro we are taking the last 32 bits given 64 bits number.

Another important Macro would be this one.

Since we are going to use a lot, we define this Macro where we can pass a number, the size we want to extract and the position we want to start. So it will make our life much more easier when parsing binary data to understandable Virtual Machine Code. If you are not familiar with bitwise operations, check this link (https://en.wikipedia.org/wiki/Bitwise_operation), I’ll not cover this here, but we are just shifting bits in order to get where we want.

We must pay attention in how we are going to pass information to the CPU, let’s make a deal…

  1. The first 8 bits represents which operation we want, like store, add…
  2. The next 24 bits we will be using to indicate registers, macros, anything that we might need…
  3. The last 32 bits we represent the data itself.

So, we have 8 + 24 + 32 = 64.

Now we can write a function to understand the following instruction.

0000000000000000000000000000001100000000000000000000000100000000

  1. First 8 bits 00000000 = instruction 0x0 or 0, we will define it as store. Store some value into the register…
  2. Next 24 bits 000000000000000000000001 = 0x1 or 1, means that we will store this value into the register 1.
  3. Last 32 bits 00000000000000000000000000000011 = 0x3 or 3, the value we are going to store into the register 0x1.

We have a function to find and store the value, but we still need to define a parser, that will read the first 8 bits and call store_r function.

Let’s create some way to access our function, in a very optimized way.

First of all we need to define a type for our instruction functions, all the instructions will have the same signature, we pass a pointer to cpu and a frame of unsigned 64 bits.

Now, we have to create our opcode array in order to store reference of functions on it.

We now have the opcodes, we must link our functions in every slot of this array. We have created with the size of 2 because today we will implement 2 instructions. Don’t mind, we are going to create more in the next chapter.

Let’s define our cpu and then link with our first instruction.

Instruction linked with the first slot of the array. Now we need a function to parse the first 8 bits and determine which instruction function it’s going to call.

First 8 bits, grab the opcode index, select the array element with that index and then, since its typed as op_fn (opcode function), call passing cpu and frame.

Finally, we are able call our parser function after defining our CPU.

If you run this program, you’ll see that the parser function will understand that the opcode index is zero and zero means store into some register, the store_r function will understand that it might grab the register at the position 1 and store the last 32 bits number on it.

Nice! Now let’s create another instruction to do something with those registers, we are going to define a function that will add two numbers, and the rule is going to be: Grab position of register a; Grab position of register b; Add these two numbers and store the result into the register b.

That’s easy, we did the most difficult part before.

Finally, we define our new instruction. Let’s add the number of register index 1 with the number of register index 1. Since we’ve stored 3 in the first instruction, we should have at register index 1 the value of 6 at the end.

The program is going to do:

  1. Store the value 3 into the register index 1.
  2. Add the register index 1 with register index 1.
  3. Result is stored in register index 1 since it’s represented as the register b in the add operation.

We are going to use,
0000000000000000000000000000000000000000000000010000000100000001

  1. 00000001 = add
  2. 00000001 = register index 1
  3. 00000001 = register index 1

Look at the debugger,

Well, that’s it for today. You already know how a very basic machine works, you can manipulate data into registers and also detect which instruction you need to run. In the next chapter we are going to implement the loop in which our CPU will be running, today we are calling the parser function manually, but the idea is to read a bunch of binary numbers and understand what to do, just like a real machine works.

Thank you!

:)