Just recently I came across the ‘Synacor VM’ challenge. The problem is an interesting exercise in implementing a virtual machine using a supplied architecture definition and then running the VM using the given binary file as input. When run the program is an adventure type game which many people have completed but I have, so far, resisted that temptation. So here’s the spec.
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
-- -- == Synacor Challenge == In this challenge, your job is to use this architecture spec to create a virtual machine capable of running the included binary. Along the way, you will find codes; submit these to the challenge website to track your progress. Good luck! == architecture == - three storage regions - memory with 15-bit address space storing 16-bit values - eight registers - an unbounded stack which holds individual 16-bit values - all numbers are unsigned integers 0..32767 (15-bit) - all math is modulo 32768; 32758 + 15 => 5 == binary format == - each number is stored as a 16-bit little-endian pair (low byte, high byte) - numbers 0..32767 mean a literal value - numbers 32768..32775 instead mean registers 0..7 - numbers 32776..65535 are invalid - programs are loaded into memory starting at address 0 - address 0 is the first 16-bit value, address 1 is the second 16-bit value, etc == execution == - After an operation is executed, the next instruction to read is immediately after the last argument of the current operation. If a jump was performed, the next operation is instead the exact destination of the jump. - Encountering a register as an operation argument should be taken as reading from the register or setting into the register as appropriate. == hints == - Start with operations 0, 19, and 21. - Here's a code for the challenge website: mzMXMdUpOZeH - The program "9,32768,32769,4,19,32768" occupies six memory addresses and should: - Store into register 0 the sum of 4 and the value contained in register 1. - Output to the terminal the character with the ascii code contained in register 0. == opcode listing == halt: 0 stop execution and terminate the program set: 1 a b set register <a> to the value of <b> push: 2 a push <a> onto the stack pop: 3 a remove the top element from the stack and write it into <a>; empty stack = error eq: 4 a b c set <a> to 1 if <b> is equal to <c>; set it to 0 otherwise gt: 5 a b c set <a> to 1 if <b> is greater than <c>; set it to 0 otherwise jmp: 6 a jump to <a> jt: 7 a b if <a> is nonzero, jump to <b> jf: 8 a b if <a> is zero, jump to <b> add: 9 a b c assign into <a> the sum of <b> and <c> (modulo 32768) mult: 10 a b c store into <a> the product of <b> and <c> (modulo 32768) mod: 11 a b c store into <a> the remainder of <b> divided by <c> and: 12 a b c stores into <a> the bitwise and of <b> and <c> or: 13 a b c stores into <a> the bitwise or of <b> and <c> not: 14 a b stores 15-bit bitwise inverse of <b> in <a> rmem: 15 a b read memory at address <b> and write it to <a> wmem: 16 a b write the value from <b> into memory at address <a> call: 17 a write the address of the next instruction to the stack and jump to <a> ret: 18 remove the top element from the stack and jump to it; empty stack = halt out: 19 a write the character represented by ascii code <a> to the terminal in: 20 a read a character from the terminal and write its ascii code to <a>; it can be assumed that once input starts, it will continue until a newline is encountered; this means that you can safely read whole lines from the keyboard and trust that they will be fully read noop: 21 no operation |
I had a couple of attempts at this – in Haskell – and the main thing I learnt from this was… Yes, the Haskell type system is very expressive and allows for a sophisticated modelling Read More