Friday, 26 June 2009

ICFP Contest 2009

The ICFP Contest 2009 started today, so I thought I'd have an attempt at solving the problem in Clojure.

The contest involves implementing a virtual machine which acts as a control module for a satellite. The fun bit is controlling the satellite (which I haven't got to yet), the really *annoying* bit is decoding the virtual machine instructions.

The code below decodes the first dump and prints out the list of op codes. I've no idea if it prints out the right code though...


(ns uk.co.fatvat.icfp
(:import [java.lang.reflect Array])
(:import [java.io FileInputStream File]))

;;; Location of relevant files
(def bin1 "/home/jfoster/clojureprojects/icfp/uk/co/fatvat/bin1.obf")

;;; Boring static definitions
(def d-type-instructions {1 'Add, 2 'Sub, 3 'Mult, 4 'Div, 5 'Output, 6 'Phi})
(def s-type-instructions {0 'Noop, 1 'Cmpz, 2 'Sqrt, 3 'Copy, 4 'Input})
(def comparison {0 'LTZ, 1 'LEZ, 2 'EQZ, 3 'GEZ, 4 'GTZ})

;;; Define what the virtual memory looks like
(defstruct vm :data-memory :instruction-memory :programcounter :status)

(defn get-bytes
"Read the bytes for the given file, stored as a sequence of bytes"
[filename]
(let [file (File. filename)]
(assert (.exists file))
(with-open [x (FileInputStream. file)]
(doall
(into [] (take-while (partial not= -1) (repeatedly #(.read x))))))))

(defn get-op-code
[bytes]
(println "bytes" bytes)
(bit-shift-right (bit-and (byte (first bytes)) 0xF0) 4))

(defn to-double
[bytes]
(Double/longBitsToDouble
(long
(reduce bit-or
(map (fn [x shift] (bit-shift-left (bit-and (int x) 0xFF) shift))
bytes
(range 0 64 8))))))

(defn to-int
[bytes]
(int (reduce bit-or
(map (fn [x shift] (bit-shift-left (bit-and (int x) 0xFF) shift))
bytes
(range 0 32 8)))))

(defn get-op
[ins]
(let [d-opcode (bit-shift-right (bit-and 0xF0 (last ins)) 4)
s-opcode (bit-and 0x0F (last ins))]
(if (zero? d-opcode)
(let [sins (s-type-instructions s-opcode)]
[sins (s-args sins ins)])
[(d-type-instructions d-opcode) (d-args ins)])))

(defn d-args
[ins]
(let [x (to-int ins)]
[(bit-shift-right (bit-and x 0xFFFC000) 14) (bit-and x 0x00003FFF)]))

(defn s-args
[op ins]
(if (= 'Cmpz op)
[(comparison (bit-shift-right (bit-and (to-int ins) 0x700000) 21)) (bit-and (to-int ins) 0x00003FFF)]
[(bit-and (to-int ins) 0x00003FFF)
(bit-shift-right (bit-and (last (butlast ins)) 0xF0) 4)]))

(defn get-instruction-data
[image address]
(if (even? (/ address 12))
[(get-op (subvec image (+ address 8) (+ address 8 4)))
(to-double (subvec image address (+ address 8)))]

[(get-op (subvec image address (+ address 4)))
(to-double (subvec image (+ address 4) (+ address 12)))]))

(defn read-data
[image pc]
(map (fn [x] (get-instruction-data image x)) (range 0 (count image) 12)))



Currently you can just see the op codes, but not execute them. For example:


uk.co.fatvat.icfp> (take 10 (read-data (get-bytes bin1) 0))
([[Noop [0 0]] 1.0]
[[Copy [265 0]] 0.0]
[[Noop [0 0]] 30.0]
[[Noop [0 0]] 0.0]
[[Copy [248 0]] 0.0]
[[Sub [4 3]] 0.0]
[[Cmpz [EQZ 5]] 0.0]
[[Phi [2 1]] 0.0]
[[Sub [7 0]] 0.0]
[[Copy [263 0]] 0.0])


Initially the spec was slightly wrong which meant a little banging of my head against a brick rule. Next plan is to get the VM to execute the instructions. I *think* I can do this by replacing my symbols with the real functions, and then just applying them to the arguments. The tricky bit will be modelling the memory model of the VM in Clojure (e.g. not a functional style but with references and so on).