--- a/content/blog/2016/12/chip8-cpu.markdown Sat Dec 17 21:37:05 2016 -0500
+++ b/content/blog/2016/12/chip8-cpu.markdown Sat Dec 17 23:00:51 2016 -0500
@@ -24,7 +24,7 @@
`cloc` reports:
* Basic emulator: 415 lines
-* Debugging infrastructure: 142 lines
+* Debugging/disassembling infrastructure: 142 lines
* Screen GUI: 153 lines
* Graphical debugger: 295 lines
@@ -968,33 +968,325 @@
[BCD]: https://en.wikipedia.org/wiki/Binary-coded_decimal
+### Arithmetic
+Next up at the arithmetic instructions. The CHIP-8 only supports addition and
+subtraction — there are no multiplication or division instructions.
+
+The first two instructions are `ADD` and `SUB`:
+
+ ADD Vx, Vy → Vx = Vx + Vy
+ SUB Vx, Vy → Vx = Vx - Vy
+
+Once again we'll start by creating two helper functions to perform the 8-bit
+addition/subtraction with overflow/underflow. These functions will return
+a second value that represents the carry/borrow bit.
+
+```lisp
+(defun-inline +_8 (x y)
+ (let ((result (+ x y)))
+ (values (chop 8 result)
+ (if (> result 255) 1 0)))) ; carry
+
+(defun-inline -_8 (x y)
+ (let ((result (- x y)))
+ (values (chop 8 result)
+ (if (> x y) 1 0)))) ; borrow
+```
+
+And now the instructions themselves are trivial:
```lisp
+(define-instruction op-add-reg<reg (_ rx ry) ;; ADD Vx, Vy (8-bit)
+ (setf (values (register rx) flag)
+ (+_8 (register rx) (register ry))))
+
+(define-instruction op-sub-reg<reg (_ rx ry) ;; SUB Vx, Vy (8-bit)
+ (setf (values (register rx) flag)
+ (-_8 (register rx) (register ry))))
```
+Again we use `(setf (values ...))` to avoid having to name intermediate results.
+
+Notice how we just assign to `flag`. Under the hood that `flag` has been bound
+with our `with-chip` macro to mean `(chip-flag chip)`, which we defined way back
+in the beginning to mean `(aref (chip-registers chip) #xF)`. But isn't it much
+nicer to just say `(setf flag ...)`?
+
+There's also a `SUBN` instruction for subtracting the operands in reverse order
+(but still storing the result in the first):
+
+```lisp
+(define-instruction op-subn-reg<reg (_ rx ry) ;; SUBN Vx, Vy (8-bit)
+ (setf (values (register rx) flag)
+ ;; subtraction order is swapped for SUBN
+ (-_8 (register ry) (register rx))))
+```
+
+Next is an `ADD` instruction that takes an immediate value. Unlike the other
+instructions this one does *not* set the flag for some reason (that was a fun
+bug to track down):
+
+```lisp
+(define-instruction op-add-reg<imm (_ r (immediate 2)) ;; ADD Vx, Imm
+ ;; For some weird reason the ADD immediate op doesn't set the flag
+ (zapf (register r) (+_8 % immediate)))
+```
+
+Because Common Lisp will just ignore extra return values if we don't use them,
+we can just use our `+_8` helper function here too and ignore the carry result.
+
+There's also a single 16-bit `ADD` instruction that adds the value in
+a particular register to the index register. It too ignores the `flag`:
+
```lisp
+(define-instruction op-add-index<reg (_ r) ;; ADD I, Vx (16-bit)
+ (zapf index (chop 16 (+ % (register r)))))
```
+### Shifting
+
+The CHIP-8 has two bit-shifting instructions: `SHR` and `SHL` which shift
+a register's contents right or left by a single bit. Both of these instructions
+also set the flag to the bit that got shifted "off the end" of the register.
+
+We'll define two more helpers to do the actual 8-bit shifting and keep track of
+the bit that falls off the end:
+
+```lisp
+(defun-inline get-bit (position integer)
+ (ldb (byte 1 position) integer))
+
+(defun-inline >>_8 (v)
+ (values (ash v -1)
+ (get-bit 0 v)))
+
+(defun-inline <<_8 (v)
+ (values (chop 8 (ash v 1))
+ (get-bit 7 v)))
+```
+
+The instructions themselves are trivial:
+
```lisp
+(define-instruction op-shr (_ r) ;; SHR
+ (setf (values (register r) flag)
+ (>>_8 (register r))))
+
+(define-instruction op-shl (_ r) ;; SHL
+ (setf (values (register r) flag)
+ (<<_8 (register r))))
+```
+
+### Logical Operations
+
+Next up are the logical `AND`/`OR`/`XOR` instructions. We could define these
+like so:
+
+```lisp
+(define-instruction op-and (_ destination source _)
+ (zapf (register destination) (logand % (register source))))
+
+(define-instruction op-or (_ destination source _)
+ (zapf (register destination) (logior % (register source))))
+
+(define-instruction op-xor (_ destination source _)
+ (zapf (register destination) (logxor % (register source))))
```
+This works, but aside from the name and the operation they're all completely
+identical. The next few groups of instructions are also going to be mostly
+similar, so let's step back for a moment and see if we can abstract away the
+tedium.
+
+### Macro-Map
+
+Instead of typing the same thing over and over, we'd like to just say when we
+want once. The traditional way to do this is with `macrolet`:
+
```lisp
+(macrolet
+ ((define-logical-instruction (name function)
+ `(define-instruction ,name (_ destination source _)
+ (zapf (register destination)
+ (,function % (register source))))))
+ (define-logical-instruction op-and logand)
+ (define-logical-instruction op-or logior)
+ (define-logical-instruction op-xor logxor))
```
+Now we're only writing out the actual functionality once instead of three times.
+That's better, but I'm still not satisfied. Using `macrolet` means I need to
+think of a name for the macro that I'm just going to use within this block and
+throw away, and naming things is hard.
+
+What I *really* want to do here is just "map" a macro over a bunch of arguments
+and be done with it. I've played around a bit and ended up with a macro called
+`macro-map` that does just that:
+
```lisp
+(defmacro macro-map (lambda-list items &rest body)
+ (with-gensyms (macro)
+ `(macrolet ((,macro ,(ensure-list lambda-list) ,@body))
+ ,@(iterate (for item :in items)
+ (collect `(,macro ,@(ensure-list item)))))))
```
+`macro-map` takes a lambda list, list of arguments, and a body for the macro and
+builds the `macrolet` we wrote by hand earlier using a `gensym` for the name so
+we don't have to waste brain cells thinking of one. Now we can define our
+logical operations all at once:
+
```lisp
+(macro-map ;; AND/OR/XOR
+ (NAME OP)
+ ((op-and logand)
+ (op-or logior)
+ (op-xor logxor))
+ `(define-instruction ,name (_ destination source _)
+ (zapf (register destination) (,op % (register source)))))
```
+This actually ends up being one line of code longer than the copy/pasted version
+because I like to linebreak liberally, but the important thing is that we only
+say each thing we need to say once.
+
+Notice how this almost starts to look like a table of data rather than code.
+I've taken advantage of the fact that the Lisp reader reads everything as
+uppercase by default and uppercased the "header" row (the lambda list) to make
+it stand out a bit more.
+
+If you squint a little bit you might imagine how defining a set of related
+instructions could almost look like [a page from a CPU
+manual](https://i.imgur.com/8jbXmVj.png).
+
+### Branching
+
+Now that we've got a way to define batches of similar instructions without going
+crazy we can tackle the branching instructions.
+
+Most CPUs have some form of "jump to some location if zero, otherwise continue"
+instruction to implement branching. The CHIP-8 needs to fit every instruction
+into two bytes, so it does something a bit simpler. Instead of an arbitrary
+jump on a condition, it has a series of *skip* instructions.
+
+For example, `SE Vx, 0` means "skip the next instruction if register X is zero".
+Skipping the next instruction is a simple as incrementing the program counter by
+an extra two bytes.
+
+There are four variants of this instruction:
+
+ SE Vx, Immediate → Skip when Vx equals Immediate
+ SNE Vx, Immediate → Skip when Vx does not equal Immediate
+ SE Vx, Vy → Skip when Vx equals Vy
+ SNE Vx, Vy → Skip when Vx does not equal Vy
+
+Let's use `macro-map` to write this out as a table of code:
+
```lisp
+(macro-map ;; SE/SNE
+ ((NAME TEST X-ARG X-FORM Y-ARG Y-FORM)
+ ((op-se-reg-imm = (r 1) (register r) (immediate 2) immediate)
+ (op-sne-reg-imm not= (r 1) (register r) (immediate 2) immediate)
+ (op-se-reg-reg = (rx 1) (register rx) (ry 1) (register ry))
+ (op-sne-reg-reg not= (rx 1) (register rx) (ry 1) (register ry))))
+ `(define-instruction ,name (_ ,x-arg ,y-arg)
+ (when (,test ,x-form ,y-form)
+ (incf program-counter 2))))
+```
+
+After the macroexpansion we end up with things like:
+
+```lisp
+(define-instruction op-sne-reg-imm (_ (r 1) (immediate 2))
+ (when (not= (register r) immediate)
+ (incf program-counter 2)))
```
+We'll also need `not=` itself to avoid having to do messy things inside the
+macro body:
+
```lisp
+(defun-inline not= (x y)
+ (not (= x y)))
```
+Just one more group of instructions left (for this post).
+
+### Loads
+
+The final group of instructions we'll look at for now is the `LD` family of
+loads. Normally we'd implement these first, but I wanted to introduce
+`macro-map` as gently as possible.
+
+Most of the `LD` instructions simple take a value from a source and stick it
+into a destination, and we can implement them as a single `setf` form:
+
```lisp
+(macro-map ;; LD
+ (NAME ARGLIST DESTINATION SOURCE)
+ ((op-ld-i<imm (_ (value 3)) index value)
+ (op-ld-reg<imm (_ r (value 2)) (register r) value)
+ (op-ld-reg<reg (_ rx ry _) (register rx) (register ry))
+ (op-ld-reg<dt (_ r _ _) (register r) delay-timer)
+ (op-ld-dt<reg (_ r _ _) delay-timer (register r))
+ (op-ld-st<reg (_ r _ _) sound-timer (register r)))
+ `(define-instruction ,name ,arglist
+ (setf ,destination ,source)))
```
+We haven't talked about the timers yet, so don't worry about them. I'm leaving
+them in so you can see how nice the `macro-map` is when you need to define lots
+of very similar operations at once.
+There are two other more interesting `LD` instructions which move data between
+multiple registers and memory.
+
+`LD [I], n` loads consecutive bytes of memory with the contents of registers
+`V0` through `Vn`, starting at wherever the index register is pointing. For
+example, `LD [I], 2` would be:
+
+<pre class="lineart">
+ V0 V1 V2 V3 V4 ...
+ ┌──┐ ┌──┐ ┌──┐ ┌──┐ ┌──┐
+ │ │ │ │ │ │ │ │ │ │ ...
+ └─┬┘ └─┬┘ └─┬┘ └──┘ └──┘
+ └───┐└──┐ └─┐
+ │ │ │
+ ▼ ▼ ▼
+ ┌───┬───┬───┬───┬───┐
+ │ │ │ │ │ │ Memory
+ └───┴───┴───┴───┴───┘
+ ▲ ┌───┐
+ └──│...│ Index Register
+ └───┘
+</pre>
+
+`LD n, [I]` does the opposite: it loads the contents of memory into the
+registers `V0` through `Vn`.
+
+Because we've used Lisp arrays for both the registers and memory, these
+instructions are really lovely to implement — they end up being just a single
+call to `replace`:
+
+```lisp
+(define-instruction op-ld-mem<regs (_ n _ _) ;; LD [I] < Vn
+ (replace memory registers :start1 index :end2 (1+ n)))
+
+(define-instruction op-ld-regs<mem (_ n _ _) ;; LD Vn < [I]
+ (replace registers memory :end1 (1+ n) :start2 index))
+```
+
+That's it for the `LD` instructions (for now) and for the instructions in
+general!
+
+## Future
+
+With these instructions implemented (and with some stubs for the rest) we can
+load and run a ROM and it will push bytes around in memory and mostly work. In
+the next few posts we'll look at the next steps to getting a fully-functional
+emulator up and running, including:
+
+* Graphics and input
+* Sound
+* Debugging