Can you crack it part 2

Posted on 18.04.2013

Following on from part 1 of the challenge ""can you crack it"" which I decided to have a pop at. Part two consists of a virtual machine object written in Javascript, with a cpu sub object and memory storage. The challenge is to complete exec() such that the VM runs. The encoding instructions are given:

// virtual machine architecture
// ++++++++++++++++++++++++++++
//
// segmented memory model with 16-byte segment size (notation seg:offset)
//
// 4 general-purpose registers (r0-r3)
// 2 segment registers (cs, ds equiv. to r4, r5)
// 1 flags register (fl)
//
// instruction encoding
// ++++++++++++++++++++
//
//           byte 1               byte 2 (optional)
// bits      [ 7 6 5 4 3 2 1 0 ]  [ 7 6 5 4 3 2 1 0 ]
// opcode      - - -             
// mod               -           
// operand1            - - - -
// operand2                         - - - - - - - -
//
// operand1 is always a register index
// operand2 is optional, depending upon the instruction set specified below
// the value of mod alters the meaning of any operand2
//   0: operand2 = reg ix
//   1: operand2 = fixed immediate value or target segment (depending on instruction)
//
// instruction set
// +++++++++++++++
// 
// Notes:
//   * r1, r2 => operand 1 is register 1, operand 2 is register 2
//   * movr r1, r2 => move contents of register r2 into register r1
// 
// opcode | instruction | operands (mod 0) | operands (mod 1)
// -------+-------------+------------------+-----------------
// 0x00   | jmp         | r1               | r2:r1
// 0x01   | movr        | r1, r2           | rx,   imm 
// 0x02   | movm        | r1, [ds:r2]      | [ds:r1], r2
// 0x03   | add         | r1, r2           | r1,   imm
// 0x04   | xor         | r1, r2           | r1,   imm 
// 0x05   | cmp         | r1, r2           | r1,   imm 
// 0x06   | jmpe        | r1               | r2:r1
// 0x07   | hlt         | N/A              | N/A
//
// flags
// +++++
// 
// cmp r1, r2 instruction results in:
//   r1 == r2 => fl = 0
//   r1 < r2  => fl = 0xff
//   r1 > r2  => fl = 1
// 
// jmpe r1
//   => if (fl == 0) jmp r1
//      else nop

It is fair to say this particular challenge is one of implementation, rather than anything beyond that.

So, rather than describe step by step how I wrote my VM, I'll instead explain some key concepts and gotchas.

If a code segment is specified (on x86, this would be a segment selector and the CPU would go and look up the base) then we jump to segment base + offset. If not, we jump to cs+offset, since cs contains the segment base. Remember, if you switch segments via a jump, you must set the segment selector.

Once you're done, dump the memory somewhere and run strings on it.

I'll be honest, the biggest time cost from this challenge was a misplaced variable in my code. I calculated the actual linear offset when jmp rx was called, but then used the value from rx to jump to, meaning the code was stuck in an infinite loop. Once I realised what I was doing, easy.