synacor-vm.nim

import 
  std/algorithm,
  std/bitops,
  std/streams,
  std/strformat,
  std/sugar

type 
  Memory = array[0..32767,uint16] 
  Registers = array[0..7,uint16]
  Program = seq[uint16]
  Stack = seq[uint16]

const
  REGISTER_OFFSET = 32768'u16
  MOD_I15 = 32768'u16

proc readProgram(filename: string): Program =
  var strm = newFileStream(filename, fmRead)
  defer: strm.close()

  while not isNil(strm):
    try:
      result.add(strm.readuint16())
    except IOError:
      break

proc valu(num: uint16, regs: Registers): uint16 =
  case num
    of 0..32767:
      result = num
    of 32768..32775:
      result = regs[num - REGISTER_OFFSET]
    else:
      assert(false, "Value out of range")


proc outp(num: uint16) =
  stdout.write(char(num))

proc set(registers: var Registers, destination: uint16, value: uint16) =
  registers[destination - REGISTER_OFFSET] = value

proc add(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  registers.set(destination, (lhs + rhs) mod MOD_I15)

proc mul(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  registers.set(destination, (lhs * rhs) mod MOD_I15)

proc modu(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  registers.set(destination, lhs mod rhs)

proc eq(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  if lhs == rhs:
    registers.set(destination, 1)
  else:
    registers.set(destination, 0)

proc gt(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  if lhs > rhs:
    registers.set(destination, 1)
  else:
    registers.set(destination, 0)

proc band(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  registers.set(destination, lhs.bitand(rhs))

proc bor(registers: var Registers, destination: uint16, lhs: uint16, rhs: uint16) =
  registers.set(destination, lhs.bitor(rhs))

proc bnot(registers: var Registers, destination: uint16, value: uint16) =
  registers.set(destination, value.bitnot().bitand(0x7FFF))

proc loadProgram(memory: var Memory, prog: Program) =
  for idx, val in prog.pairs:
    memory[idx] = val


proc main() =
  var 
    memory: Memory 
    regs: Registers
    stack: Stack
    prog: Program
    ip = 0'u16
    charBuf: seq[uint16]

  prog = readProgram("challenge.bin")
  memory.loadProgram(prog)

  #echo memory
  while true:
    var op = memory[ip]
    #echo fmt"ip: {ip}, op: {op}"
    case op
      of 0: # halt
        #echo "halt"
        break
      of 1: # set a b
        #echo fmt"set {memory[ip + 1]} {memory[ip+2]}"
        regs.set(memory[ip + 1], valu(memory[ip + 2], regs))
        ip += 3
      of 2: # push a
        #echo fmt"push {memory[ip + 1]}"
        stack.add(valu(memory[ip + 1], regs))
        ip += 2
      of 3: # pop a
        #echo fmt"pop {memory[ip + 1]}"
        if len(stack) < 1:
          assert(true, "Stack underflow")
        else:
          regs.set(memory[ip + 1], stack.pop())
        ip += 2
      of 4: # eq a b c
        #echo fmt"eq {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.eq(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 5: # gt a b c
        #echo fmt"gt {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.gt(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 6: # jmp a
        #echo fmt"jmp {memory[ip + 1]}"
        ip = valu(memory[ip + 1], regs) 
      of 7: # jt a b
        #echo fmt"jt {memory[ip + 1]} {memory[ip+2]}"
        if valu(memory[ip + 1], regs) != 0:
          ip = valu(memory[ip + 2], regs)
        else:
          ip += 3
      of 8: # jf a b
        #echo fmt"jf {memory[ip + 1]} {memory[ip+2]}"
        if valu(memory[ip + 1], regs) == 0:
          ip = valu(memory[ip + 2], regs)
        else:
          ip += 3
      of 9: # add a b c
        #echo fmt"add {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.add(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 10: # mul a b c
        #echo fmt"mul {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.mul(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 11: # mod a b c
        #echo fmt"mod {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.modu(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 12: # and a b c
        #echo fmt"and {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.band(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 13: # or a b c
        #echo fmt"or {memory[ip + 1]} {memory[ip+2]} {memory[ip+2]}"
        regs.bor(memory[ip + 1], valu(memory[ip + 2], regs), valu(memory[ip + 3], regs))
        ip += 4
      of 14: # not a b
        #echo fmt"not {memory[ip + 1]} {memory[ip+2]}"
        regs.bnot(memory[ip + 1], valu(memory[ip + 2], regs))
        ip += 3
      of 15: # rmem a b
        #echo fmt"rmem {memory[ip+1]} {memory[valu(memory[ip+2], regs)]}"
        regs.set(memory[ip + 1], valu(memory[valu(memory[ip + 2], regs)],regs))
        ip += 3
      of 16: # wmem a b
        #echo fmt"wmem {memory[ip+1]} {valu(memory[ip+2], regs)}"
        memory[valu(memory[ip + 1], regs)] = valu(memory[ip + 2], regs)
        ip += 3
      of 17: # call a
        #echo fmt"call {memory[ip + 1]}"
        stack.add(ip + 2)
        ip = valu(memory[ip + 1], regs)
      of 18: # ret
        #echo "ret"
        if stack.len() < 1:
          echo "ret: stack underflow. Halting"
          break
        else:
          ip = stack.pop()
      of 19: # out a
        #echo fmt"out {memory[ip + 1]}"
        outp(valu(memory[ip + 1], regs))
        ip += 2
      of 20: # in a
        # This one is a bit special, since the documentation says we can rely on whole lines being
        # read the first time we encounter this we make a buffer of characters, and then the next
        # times we encounter it we feed it the next character from the buffer until it reaches a
        # newline
        if charBuf.len() < 1:
          let str = stdin.readLine()
          charBuf = collect(newSeq):
            for ch in str:
              uint16(ch)

          charBuf.add(10)
          charBuf.reverse()

        regs.set(memory[ip + 1], charBuf.pop())
        #echo fmt"in: {memory[ip + 1]}"
        ip += 2
      of 21: # nop
        #echo "nop"
        ip += 1
      else: 
        echo fmt"{ip}: unknown op {op}"
        break
  echo ""
  echo "--------------" 
  echo "Program halted"
  echo "--------------" 
when is_main_module:
  main()