PROBLEM STATEMENT:
You are designing a computer based on your own IRISC (Incredibly Reduced
Instruction Set Computer) Architecture. To allow others to develop for your
computer, you need to create a virtual machine representing your computer. The
virtual machine should allow a user to run a program written in assembly for
your computer.
The virtual machine must support the following registers and memory locations:
* The CPU consists of 8 general-purpose registers, numbered 0 - 7, a PC
(program counter) register, an IR (instruction register), and a status register.
* There are two memories, a data memory and a program memory.
* The data memory contains 32 locations, numbered 0 - 31.
* The program memory contains 32 locations, numbers 0 - 31.
* The 8 general purpose registers, PC register, and data memory locations are
32 bits and the virtual machine must only support their holding integer values,
with the values being between -2147483648 and 2147483647, inclusive.
* The status register is 3 bits. The bits are the EQUAL, GREATER, and OVERFLOW
bits.
* The program memory locations and IR are 64 bits, but the virtual machine
should consider the locations Strings, where each String is an assembly
instruction.
The computer operates as follows:
1. The value 0 is loaded into the general purpose and PC registers and status
bits.
2. The instruction in the program memory at the location in PC is loaded into IR.
3. The PC is incremented.
4. The instruction in the IR is executed.
5. If the value in the PC is between 0 and 31, inclusive, go back to step 2,
otherwise stop.
Here is the instruction set the virtual machine must support (All r1, r2 and x
represent integer values. r1 and r2 are integers between 0 and 7, inclusive.
x is an integer between -2147483648 and 2147483647, inclusive):
ADD r1 r2
The OVERFLOW bit is set to 0.
Adds the contents of registers r1 and r2, storing the result in r2.
If overflow occurs, the OVERFLOW bit is set to 1 and 0 is stored in r2.
OVERFLOW occurs if the actual result of the addition is greater than
2147483647 or less than -2147483648.
SUB r1 r2
The OVERFLOW bit is set to 0.
Subtracts the contents of register r2 from register r1, storing the result in
r2.
If overflow occurs, the OVERFLOW bit is set to 1 and 0 is stored in r2.
OVERFLOW occurs if the actual result of the subtraction is greater than
2147483647 or less than -2147483648.
LOAD r1 r2
Loads the value in the data memory location pointed to by r1 into the
register r2.
In other words, if the value in r1 is A, the value in data memory location A
is copied to
r2. If the value in r1 is less than 0 or greater than 31 (out of the memory
range),
execution should halt (set the value in the PC to -1).
LOAD #x r1
Loads the value x into the register r1.
STOR r1 r2
Stores the value in register r1 into the data memory location pointed to by
r2.
In other words, if the value in r1 is A and the value in r2 is B, A is put in
the data memory location B. If the value in r2 is less than 0 or greater
than 31
(out of the memory range), execution should halt (set the value in the PC to
-1).
CMP r1 r2
The GREATER and EQUAL bit are set to 0.
The values in r1 and r2 are compared.
If they are equal, the EQUAL bit is set to 1.
If the value in r1 is greater than the value in r2, the GREATER
bit is set to 1.
BA #x
Sets the value in the program counter to x.
BE #x
Sets the value in the program counter to x if the EQUAL bit is 1.
BG #x
Sets the value in the program counter to x if the GREATER bit is 1.
BL #x
Sets the value in the program counter to x if the EQUAL and GREATER bits are 0.
HALT
Sets the value in the PC to -1.
NOP
Does nothing.
You are to implement a class VirtualMachine, which contains a method run. The
method takes as parameters an int[] (dMem) and String[] (pMem). dMem
represents the data memory where dMem[0] is the value in the 0th memory
location. If there are less than 32 values in dMem, it is implied that the
value 0 is in each of the unspecified data memory locations. pMem represents
the program memory where pMem[0] is the value in the 0th memory location. If
there are less than 32 values in pMem, it is implied that the instructions in
the unspecified memory locations are "NOP". The method should run the virtual
machine starting with step 1 of "The computer operates as follows:" above and
goes until execution stops or until 1000 instructions have been executed. The
method should return an int[] representing the data memory at the time virtual
machine execution completes.
DEFINITION:
Class: VirtualMachine
Method: run
Parameters: int[], String[]
Returns: int[]
Method Signature: int[] run(int[] dMem, String[] pMem);
(Be sure your method is public)
TOPCODER WILL ENSURE:
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
* Each instruction in pMem is in the form of one of the instructions listed
above.
* In the instructions, r1 and r2 are between 0 and 7, inclusive, and x is between
-2147483648 and 2147483647, inclusive.
* dMem contains between 0 and 32 elements, inclusive.
* pMem contains between 0 and 32 elements, inclusive.
* Elements of pMem contain at most 50 characters.
* Elements of pMem contain only capital letters (A - Z), spaces, digits (0 - 9
inclusive), and '#'.
* Elements of dMem are between -2147483648 and 2147483647, inclusive.
NOTE:
* There can be arbitrary amounts of whitespace between, before, or after the
arguments and instructions.
* If an instruction reads and writes from the same register, the read is done
before the write.
* The returned int[] should have exactly 32 elements.
* The internal functioning of the virtual machine is not important, it must only
output the correct data memory at the end of the program execution.
* Leading zeroes are allowed.
EXAMPLES:
EXAMPLE 1:
If dMem = { 3,
2,
-1024,
45}
and pMem = {" LOAD #0 1",
" LOAD 1 1",
" LOAD #1 2",
" LOAD 2 2",
" ADD 1 2",
" LOAD #2 3",
" LOAD 3 3",
" CMP 2 3",
" BG #12 ",
" ADD 1 2",
" ADD 1 2",
" ADD 1 2",
" LOAD #0 1",
" STOR 2 1",
" HALT "}
The virtual machine will first load 0 into the PC,
Then " LOAD #0 1" is loaded into the IR. PC is incremented to 1.
The value 0 is loaded into register 1.
Then " LOAD 1 1" is loaded into the IR, PC is incremented to 2, and the value
dMem[0] = 3 is stored in register 1. Execution proceeds and results in:
1 is loaded into register 2,
dMem[1] = 2 is loaded into register 2.
The contents of 1 and 2 are added, and 3 + 2 = 5 is stored in register 2.
2 is loaded into register 3,
dMem[2] = -1024 is loaded into register 3.
The values in registers 2 and 3 are compared, this results in the GREATER
bit being set to 1 because 5 > -1024.
The program counter is now at 8. "BG #12" is loaded into the IR. The PC is
incremented to 9. Because the GREATER bit is 1, the value 12 is loaded into
the PC.
The instruction at pMem[12] is loaded into the IR: "LOAD #0 1".
Execution proceeds and results in:
0 is loaded into register 1.
The value in register 2 is stored in data memory at the index in register 1.
dMem[0] = 5.
Execution halts.
The program returns {5, 2, -1024, 45, 0, 0, ... } (There are 32 elements, the
last 28 are 0).
EXAMPLE 2:
If dMem = {-1234,
1000000000,
3,
0}
and pMem = {"LOAD #1 0",
"LOAD 0 1",
"ADD 1 2",
"ADD 0 7",
"STOR 2 3",
"LOAD #2 4",
"LOAD 4 5",
"CMP 5 7",
"BG #0"}
This program loops three times, and on the third time through, the "ADD 1 2"
results in an OVERFLOW.
The method should return:
{0, 1000000000, 3, 0, ...} (There are 32 elements, the last 29 are 0).
EXAMPLE 3:
If dMem = {-1234,
1000000000,
2,
0}
and pMem = {"LOAD #1 0",
"LOAD 0 1",
"ADD 1 2",
"ADD 0 7",
"STOR 2 3",
"LOAD #2 4",
"LOAD 4 5",
"CMP 5 7",
"BG #0"}
Same as example 2, but because the program only loops twice, there is no
overflow.
The method should return:
{2000000000, 1000000000, 2, 0, ...} (There are 32 elements, the last 29 are 0).
EXAMPLE 4:
If dMem = {}
and pMem = {"LOAD #0001 00001",
"ADD 00001 00002",
"LOAD #0002 00003",
"LOAD 00003 00003",
"STOR 00002 00003",
"BA #1"}
This program loops forever. The virtual machine ends after executing 1000
instructions, so the method returns:
{200, 0, 0, ....} There are 32 elements, the last 31 are 0.
EXAMPLE 5:
If dMem =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32}
and pMem = {"LOAD #-002147483648 0",
"LOAD #31 1
"SUB 0 0"
"STOR 0 1"
Overflow does not happen in this case. The method returns:
{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 0}
EXAMPLE 6:
If dMem =
{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,3
0,31,32}
and pMem = {"LOAD #1 7"
"STOR 0 7"
"STOR 0 6"
"ADD 7 7"
"LOAD #1 6"
"SUB 7 6"
"BA #1"}
Execution stops at instruction "STOR 0 7" when the value in 7 is 32. The
method returns:
{0, 0, 0, 0, 0, 6, 7, 0, 0, 10, 11, 12, 13, 14, 15, 0, 0, 18, 19, 20, 21, 22,
23, 24, 25, 26, 27, 28, 29, 30, 31, 32}