Virtual Machine

Advice on general approaches or feasibility and discussions about game design

Virtual Machine

Postby leiradel » Thu Jan 05, 2017 11:34 pm

I'm designing a virtual machine to implement my first Gamebuino project (viewtopic.php?f=13&t=3579)

My first draft is here, I'd love to get some feedback before starting its implementation. Despite my project involving a BASIC compiler, I'd like the VM to be general enough to run other compiled languages, like Pascal and C/C++.

Sorry for the bad alignment.

REGISTERS

uint16_t PC (program counter, wraps around after 65535)
uint16_t SP (stack pointer, each element in the stack has 16 bits)
uint16_t CS (code segment)
uint16_t DS (data segment)
uint16_t PS (pending code segment)

The current instruction is pointed to by CS:PC. CS doesn't change when PC wraps. All data accesses are relative to DS.

INSTRUCTION SET

+----------------------------+----------+-------------------------------------------------------------------------------------------------------+
| OPCODE | MNEMONIC | DESCRIPTION |
+----------------------------+----------+-------------------------------------------------------------------------------------------------------+
| 00xxxxx0 -------- -------- | getl x | gets the value of the local variable x and pushes onto the stack (0 <= x <= 31) |
| 00xxxxx1 -------- -------- | setl x | sets the value of the local variable x from the top of the stack (0 <= x <= 31) |
| 01xxxxxx -------- -------- | asp x | adds x to the stack pointer (-32 <= x <= 31) |
| 100xxxxx -------- -------- | push x | pushes a constant onto the stack (-15 <= x <= 16) |
| 1010xxxx -------- -------- | sys x | calls a native function with an array of x values (0 <= x <= 15) |
| 10110xxx -------- -------- | cmp x | pops b and then a from the stack and pushes the result of their comparison [1] |
| 10111000 yyyyyyyy yyyyyyyy | jmp y | continues execution at y [2] |
| 10111001 -------- -------- | ijmp | pops an address from the stack and continues execution at that location [2] |
| 10111010 yyyyyyyy yyyyyyyy | jf y | pops a value from the stack and continues execution at y if the value is zero |
| 10111011 yyyyyyyy yyyyyyyy | jt y | pops a value from the stack and continues execution at y if the value is not zero |
| 10111100 yyyyyyyy yyyyyyyy | call y | pushes the current selector and the address of the next instruction onto the stack and jumps to y [2] |
| 10111101 -------- -------- | dup | duplicates the value at the top of the stack |
| 10111110 -------- -------- | ret | pops an address and a code selector from the stack and jumps to that location |
| 10111111 -------- -------- | retv | pops an address and a code selector from the stack and jumps to that location [3] |
| 11000000 -------- -------- | add | pops two values x and y from the stack, and pushes x + y |
| 11000001 -------- -------- | sub | same as add but pushes x - y |
| 11000010 -------- -------- | mul | same as add but pushes x * y |
| 11000011 -------- -------- | div | same as add but pushes x / y |
| 11000100 -------- -------- | mod | same as add but pushes x % y |
| 11000101 -------- -------- | and | same as add but pushes x & y |
| 11000110 -------- -------- | or | same as add but pushes x | y |
| 11000111 -------- -------- | xor | same as add but pushes x ^ y |
| 11001000 -------- -------- | neg | pops x from the stack and pushes -x |
| 11001001 -------- -------- | not | same as neg but pushes !x |
| 11001010 -------- -------- | shl | same as add but pushes x << y |
| 11001011 -------- -------- | shr | same as add but pushes x >> y |
| 11001100 -------- -------- | ldb | pops an address from the stack and pushes the byte at that location |
| 11001101 -------- -------- | ldw | same as ldc, but reads a 16-bit signed value at address and address+1 [4] |
| 11001110 -------- -------- | stb | pops an address and a value from the stack, and sets memory |
| 11001111 -------- -------- | stw | same as stb, but writes a 16-bit value |
| 11010000 -------- -------- | setcs | sets the code segment selector [5] |
| 11010001 -------- -------- | setds | sets the data segment selector |
| 11010010 yyyyyyyy -------- | push y | pushes a constant onto the stack (-128 <= y <= 127) |
| 11010011 yyyyyyyy -------- | push y | pushes a constant onto the stack (128 <= y <= 383) |
| 11010100 yyyyyyyy yyyyyyyy | push y | pushes a constant onto the stack (-32768 <= x <= 32767) |
| 11010101 yyyyyyyy | asp y | adds y to the stack pointer (-128 <= y <= 127) |
| 11010110 yyyyyyyy | getl | gets the value of the local variable y and pushes onto the stack (32 <= y <= 287) |
| 11010111 yyyyyyyy | setl | sets the value of the local variable x from the top of the stack (32 <= x <= 287) |
+----------------------------+----------+-------------------------------------------------------------------------------------------------------+

[1] The comparison depends on the value of x (0=z, nz, eq, ne, lt le, gt, 7=ge). For x=0 and x=1, only b is popped from the stack, and is checked if is's zero or not zero, respectively
[2] These operations set the pending value of the code segment
[3] This return instruction pops a value from the stack, pops the address and the selector, pushes the value back onto the stack, and then resumes operation at the popped segment and address
[4] The most significant byte it in the memory pointed to by the data segment and the address, the next byte in memory is the least significant byte.
[5] The code segment is not set at the time the instruction is issued, but keeps pending until an actual jump or call instruction is issued
leiradel
 
Posts: 13
Joined: Wed Aug 27, 2014 5:02 am

Re: Virtual Machine

Postby leiradel » Fri Jan 06, 2017 6:38 pm

Scratch that, I'm over-engineering the solution. I'll write a BASIC compiler (which just translates keywords into tokens) and an interpreter.
leiradel
 
Posts: 13
Joined: Wed Aug 27, 2014 5:02 am

Re: Virtual Machine

Postby wuuff » Sat Jan 07, 2017 1:40 am

leiradel wrote:Scratch that, I'm over-engineering the solution. I'll write a BASIC compiler (which just translates keywords into tokens) and an interpreter.


One thing you're probably already aware of but important to keep in mind is that you will most likely want to have some way of streaming tokens off of the SD card (or having a small buffer to hold tokens), so that the BASIC programs will not be constrained by the limited program space. This is necessary to be able to have something the size of gamebooks. I figure there will be performance tradeoffs for this, and efficiently loading code into a buffer will be difficult with branching code (branch prediction seems a bit complex for a simple BASIC interpreter!). If you followed this thread, you might remember issues with certain SD cards and latency. Perhaps for something like a gamebook it won't be a big deal, but it might be something to keep in mind.
wuuff
 
Posts: 61
Joined: Sun Aug 28, 2016 6:05 am

Re: Virtual Machine

Postby leiradel » Sat Jan 07, 2017 2:37 pm

wuuff wrote:One thing you're probably already aware of but important to keep in mind is that you will most likely want to have some way of streaming tokens off of the SD card (or having a small buffer to hold tokens), so that the BASIC programs will not be constrained by the limited program space.


That's why I've added code and data segments to the VM. I didn't want to increase the integer types to 32 bits, but a 16 bit address space would indeed be too little for a gamebook.

wuuff wrote:I figure there will be performance tradeoffs for this, and efficiently loading code into a buffer will be difficult with branching code


Yes, but it's a gamebook adventure, so it's not a big deal.

wuuff wrote:branch prediction seems a bit complex for a simple BASIC interpreter!


With cache buffers in RAM I believe I could look ahead into the token stream and pre-load "pages" from the SD card before they're needed. I'll give it a try if performance is bad, but I really doubt it will be the case.

Thanks for the tips.
leiradel
 
Posts: 13
Joined: Wed Aug 27, 2014 5:02 am


Return to Project Guidance & Game development

Who is online

Users browsing this forum: No registered users and 31 guests

cron