From Blank Slate to VM in 8 hours from New York to Buffalo
Recently, I was taking a train from NYP to BFX on Amtrak, and faced a grewling 8 hours on a Sunday morning of sitting in a comfy chair with power and a laptop. The wife and kids were already in Buffalo, so I had 8 hours of free time. So I started writing C macros to emulate lots of functional programming techniques:
I managed to write some sample code for each. Performance was great as the code used C pointers and alloca cleverly on the stack. 30 minutes down, and time to start stacks.h.
These used a power of 2 circular stack, using a stack that wraps makes stack overflow a interesting problem, but simplifies the behavior to preent range checks. It is incredibly effective to when you want to say cycle through a set of values over and over again. It is at this point that I realize I'm 60 minutes into my 480 minute trip, and I have 420 minutes to go. Begin defining a vm.h with 32 instructions:
The actual VM definitions take about 10 minutes each to write and test, leaving about 100 minutes left in the trip to make the virtual machine go. The VM mmaps a machine memory image file, and enters into a switch statement with some gotos to short circuit instructions which force a new instruction fetch. The VM works by storing 12-13 instructions in a 64bit cell, and uses 64bit cell based addressing through two memory access registers. As each instruction is just 5 bits wide instructions are not fetched very often, and many times it is cheaper to compute or fetch a value than to encode a literal. Instructions literal and higher require a second 64bit cell to encode a literal or jump location for flow control. As each instruction return and higher requires a instruction fetch, it can only come at the end of a packed instruction cell. The registers used by the VM are:
- s - ALU stack pointer
- r - return stack pointer
- a - memory source address
- d - memory destination address
- i - instruction pointer
- c - current instruction word
- m - base memory address pointer
All of the operations work through manipulating these 7 registers. Typically, ALU instructions mutate memory at the two stack registers, and possibly access memory through the two memory address registers. This design allows for stream oriented processing of memory. Each instruction that does not have an immediate value accessed through the i register, merely shifts the c register 5 bits to the right, left filling with zeros. When the instruction decode logic encounters 00000, it executes the fetch_instruction instruction and loads another value into c through i and increments i. This means the VM has two read address lines and one write address line. The base memory pointer m is used to compensate for running in a Unix environment. What it does allow for is running segmented memories, which provides isolation. At the end of the day, I will almost certainly drop m from a verilog implementation and always base memory at address 0.
The remaining time in the trip was largely spent building an assembler and disassembler for the instruction set. I stubbed out the main sysclock loop and put in the hooks where the memory mapped I/O units would fit. I have a clock, keyboard, mouse, touchpad, display, audio, and network device stub which will eventually implement with the SDL. I think that another 8 hours could make it a fully functional virtual computer out of it.