The virtual CPU implementation challenge

virtualCpuImplementationChallenge.txt

# The virtual CPU implementation test

Hello, I am Steven de Luca, CTO. 

I'd like to engage you in a test which consits of designing and implementing a virtual processor capables of running actual small binary programs.

In this test, I 'd like to evaluate your understanding of a technical problem to solve, measure your sw architecturing skills and the quality of the code you write, including style and maintainability over time and across a whole team.

It is probable that you never use Dart language so far, learning it during the test is also a way to evaluate your capacity to face the ever changing nature of the programing world.

This is why I'd like you program in Dart, take full advantage of language construction if offers to the programmers, including type decoration, functional programming, etc.

The result of your test must be published to `https://dartpad.dev` and you send the related URL back to me for the final evaluation.

Usually, it takes between one to four hours to complete the test.

Wishing you the best and have fun crafting your virtual CPU!

Sdl



# The Virtual CPU 

The virtual CPU-8 is a simple computer with a limited instruction set that performs arithmetic and control flow operations.

The byte code is provided as an array of bytes which are valid instructions and related operands.


## Your goal

Your goal is to build the virtual machine able to run this CPU programs.

To do that, we provide the full documentation of the CPU we designed along with 3 différents programs byte codes and the expected results.


## The CPU

The virtual machine does not have memory (aka there is no RAM).

Instead, it has 4 registers (A, B, C, and D), a stack, and the code EEPROM (hence you cannot make use of the EEPROM to store data).

Byte code is executed by moving an instruction pointer (IP). 

Registers A, B, C, D are identified as 0-3.



*Example of byte codes: The input [2, 0, 42] is translated to : LDV A 42 aka load the value 42 into register A.*


## Instructions to run the test

* You run the 3 programs below and get the exact same results to validate your CPU (TDD);
* Use Dart language;
* Use the CPU specification below;
* Handle errors! For example, if the program overflows the stack, your program should print STACK OVERFLOW and halts and whenever other errors occur, the CPU prints ERROR and halts;
* Provide your implementation with a DartPad URL.

# CPU specifications

* Wordsize = 8-bit;
* Big-endian;
* IP (instruction pointer) 8-bit
* There are 4 8-bit registers (A, B, C, D)
* Stack size = 8K

## Values

VALUE | DESCRIPTION|
----------|--------
0x00-0x03 | Registers A, B, C, D

## Basic Instructions

VAL  | NAME       | DESCRIPTION
-----|------------|------------
0x01 | LDR r2, r1 | sets r2 to r1
0x02 | LDV r1, v  | sets r1 to v (v is a literal value)
0x03 | ADD r2, r1 | sets r2 to r2+r1
0x04 | SUB r2, r1 | sets r2 to r2-r1

## Control Instructions

VAL  | NAME           | DESCRIPTION
-----|----------------|--------------------------------------------------------
0x20 | PSH r1         | Pushes the value of r1 on the stack
0x21 | POP r1         | Pops the last value from the stack and loads into r1
0x22 | JMP r1         | Sets the IP to the value in r1
0x23 | JPZ r2, r1     | Sets the IP to the value in r1 if r2 == 0
0x24 | JPL r3, r2, r1 | Sets the IP to the value in r1 if r3 < r2
0x25 | CLL r1         | Pushes address of the instruction following CLL 
     |                | onto stack and then jumps to address in r1
0x26 | RET            | Pops a number from the stack and jumps to that address

## Special Instructions

VAL  | NAME   | DESCRIPTION
-----|--------|------------------------------------
0x27 | PRT r1 | Prints the value contained in r1
0xFF | HLT    | Prints EXIT and halts the execution
Programs

# Program #1: Simple load

## Input (array of numbers) 

2,0,42,39,0,255

## Expected output 
42
EXIT

## Bytecode
LDV A, 42 
PRT A
HLT

# Program #2: Stack Multiplication

## Input
2,0,5,
32,0,
32,0,
32,0,
33,1,
33,2,
33,3,
3,0,1,
3,0,2,
3,0,3,
39,0,
255

## Expected output
20
EXIT

## Bytecode
LDV A, 5 PSH A
PSH A
PSH A
POP B
POP C
POP D
ADD A, B 
ADD A, C 
ADD A, D 
PRT A 
HLT

# Program #3: Looping

## Input
2,0,0, 
39,0, 
2,1,1, 
3,0,1, 
2,1,10, 
2,2,3, 
36,0,1,2, 
255

## Expected output 
0
1
2
3
4
5
6
7
8
9 
EXIT

## Bytecode 
LDV A, 0 
PRT A
LDV B, 1 
ADD A, B 
LDV B, 10 
LDV C, 3 
JPL A, B, C 
HLT