# HG changeset patch
# User Steve Losh <steve@stevelosh.com>
# Date 1482033651 18000
# Node ID 58287c034c3c2c5552fafa4d29c15fa6fea9d08d
# Parent  e448a6cc762a918584d5dcf87ae6db9ac3454464
Finish first draft of the chip8 post

diff -r e448a6cc762a -r 58287c034c3c content/blog/2016/12/chip8-cpu.markdown
--- 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