+++
title = "CHIP-8 in Common Lisp: The CPU"
snip = "Let's write an emulator."
date = 2016-12-19T14:50:00Z
draft = true
+++
A while back I decided to try to write a Game Boy emulator in Common Lisp based
on [this series of articles][imran]. I made some good progress but eventually
got bogged down because I was trying to learn a bunch of complex new things at
once:
* How to write an emulator
* How to use QT with Common Lisp
* How the Game Boy works internally
Instead of dragging on, I decided to take a break and try something simpler:
a [CHIP-8][] emulator/interpreter. The CHIP-8 is much simpler than the Game
Boy, which made it easier to experiment with the rest of the infrastructure.
In this post and a couple of future ones I'll walk through all of my CHIP-8
emulator implementation. To give you a rough idea of the size of the project,
`cloc` reports:
* Basic emulator: 415 lines
* Debugging infrastructure: 142 lines
* Screen GUI: 153 lines
* Graphical debugger: 295 lines
This first post will deal with emulating the CHIP-8's CPU.
The full emulator source is on [BitBucket][] and [GitHub][].
[imran]: http://imrannazar.com/GameBoy-Emulation-in-JavaScript
[CHIP-8]: https://en.wikipedia.org/wiki/CHIP-8
[BitBucket]: https://bitbucket.org/sjl/cl-chip8
[GitHub]: https://github.com/sjl/cl-chip8
<div id="toc"></div>
## Libraries
The emulator uses a few Common Lisp libraries to make things easier:
* [bordeaux-threads][] to handle threading.
* [cl-arrows][] for an implementation of Clojure's `-<>` threading macro.
* [cl-losh][] is my own personal utility library.
* [cl-portaudio][] for audio.
* [iterate][] for a much nicer version of `loop` called `iterate`. My utility
library contains several `iterate` drivers (some of which I've written about
before).
* [qtools][] to handle creating a GUI with QT.
* [quickutil][] for some miscellaneous utility functions from Alexandria and
elsewhere.
I'll try to remember to mention whenever I use a function that's not built-in to
Common Lisp, but I might forget, in which case it's probably in one of these.
[bordeaux-threads]: https://common-lisp.net/project/bordeaux-threads/
[cl-arrows]: https://github.com/nightfly19/cl-arrows
[cl-losh]: https://github.com/sjl/cl-losh
[cl-portaudio]: https://filonenko-mikhail.github.io/cl-portaudio/
[iterate]: https://common-lisp.net/project/iterate/
[qtools]: https://shinmera.github.io/qtools/
[quickutil]: https://github.com/tarballs-are-good/quickutil
## CHIP-8 References
There's a good amount of information available about the CHIP-8 online. The
references I used most often were:
* [Cowgod's "CHIP-8 Technical Reference"](http://devernay.free.fr/hacks/chip8/C8TECH10.HTM)
* [Laurence Muller's "How to write an emulator (CHIP-8 interpreter)"](http://www.multigesture.net/articles/how-to-write-an-emulator-CHIP-8-interpreter/)
* [Matthew Mikolay's "Mastering CHIP-8"](http://mattmik.com/files/chip8/mastering/chip8.html)
* [(Super)CHIP 8 Secrets](https://github.com/AfBu/haxe-CHIP-8-emulator/wiki/\(Super\)CHIP-8-Secrets)
## The Main Data Structure
Let's dive into the code. We'll start with the main data structure that will
hold an instance of a CHIP-8 for emulation:
```lisp
(defstruct chip
(running t :type boolean)
; ...more to come later
)
```
We're using a Lisp struct instead of a CLOS class because we're going to be
accessing the fields of this thing *a lot* and CLOS accessors can be
comparatively slow. This is one of the very few concessions we'll make to
performance.
The first field is `running`, which is just a boolean that represents whether
the emulator is currently running.
We'll eventually have multiple threads poking at this struct, and they'll
generally be doing something like `(loop :while (chip-running chip) :do ...)`.
That way when we want to quit the emulator we can just set `running` to `nil`
and everything will (eventually) stop.
### Registers
The CHIP-8 has sixteen main registers, as well as a few other special ones:
```lisp
(defstruct chip
; ...
(registers (make-array 16 :element-type 'int8)
:type (simple-array int8 (16))
:read-only t)
(index 0 :type int16)
(program-counter #x200 :type int12)
; ...
)
```
We'll keep the main registers in an array, and the others will just be separate
slots. I've added type declarations in the struct for two reasons:
* With a high `safety` declaration many implementations (including SBCL, the one
I'm using) will type check at runtime to make sure we're setting things
appropriately.
* With low `safety` and high `speed` declarations, SBCL can generate much faster
code if it knows the types of the struct slots.
To make the integer types a bit less wordy I've defined a few simple synonyms:
```lisp
(deftype int4 () '(unsigned-byte 4))
(deftype int8 () '(unsigned-byte 8))
(deftype int12 () '(unsigned-byte 12))
(deftype int16 () '(unsigned-byte 16))
```
So `registers` is a 16-element simple array of `(unsigned-byte 8)`s. It's
`read-only` because we'll be changing the *elements* of the array, but we should
never be swapping out the entire array itself.
The index register is 16 bits, and the program counter can store up to 12 bits
(we'll never need more than that because of the size of the CHIP-8's memory).
Also note that the program counter starts at address `#x200`, because that's
where the ROM data eventually gets loaded into the CHIP-8 memory.
### The Stack
The CHIP-8 also has an internal stack to store return addresses when calling
procedures. We'll just use a Lisp vector with a fill pointer for this:
```lisp
(defstruct chip
; ...
(stack (make-array 16 :element-type 'int12 :fill-pointer 0)
:type (vector int12 16)
:read-only t)
; ...
)
```
### Memory
The CHIP-8 has 4 kilobytes of main memory:
```lisp
(defconstant +memory-size+ (* 1024 4))
(defstruct chip
; ...
(memory (make-array +memory-size+ :element-type 'int8)
:type (simple-array int8 (#.+memory-size+))
:read-only t)
; ...
)
```
Pretty simple. Note the `#.` reader macro trick/hack to be able to use
a variable where we normally need a raw type specifier.
### Currently-Loaded ROM
Finally we'll add a slot for keeping track of the path to the currently-loaded
ROM, for easy resetting later:
```lisp
(defstruct chip
; ...
(loaded-rom nil :type (or null string))
; ...
)
```
That's it for now. We'll need a few more slots once we get to things like
graphics and sound, but I'll introduce them when we need them.
### The Flag Register
Register number 15, or `#xF` in hex, is special. It's nicknamed the "flag"
register, and gets set by some instructions. We could just access it like the
rest of the registers in our code:
```lisp
(setf (aref (chip-registers chip) 15) 1) ; set flag to 1
(print (aref (chip-registers chip) #xF)) ; print the flag
```
But even with the `#xF` hex index to get that mnemonic "F" this is a bit too
hard to read. Let's define some extra reader and writer functions to clean
things up:
```lisp
(defun-inline chip-flag (chip)
(aref (chip-registers chip) #xF))
(defun-inline (setf chip-flag) (new-value chip)
(setf (aref (chip-registers chip) #xF) new-value))
```
[`defun-inline`][defun-inline] is from my utility library — it just `defun`s the
function and `declaim`s it inline all in one step. Now things are much nicer:
```lisp
(setf (chip-flag chip) 1) ; set flag to 1
(print (chip-flag chip)) ; print the flag
```
[defun-inline]: https://github.com/sjl/cl-losh/blob/master/DOCUMENTATION.markdown#defun-inline-macro
## Removing Tedium
What we've got so far *works*, but I want to add one more piece of syntactic
sugar before moving on.
We're going to be accessing the slots of the `chip` struct a *lot*, and it's
going to get tedious to write `(chip-SLOT chip)` over and over again. For
example, when we're resetting the emulator we'll have to do something like this:
```lisp
(defun reset (chip)
(fill (chip-memory chip) 0)
(fill (chip-registers chip) 0)
(setf (chip-running chip) t
(chip-program-counter chip) #x200
(fill-pointer (chip-stack chip)) 0))
```
This is annoying. Languages like Javascript and Python use `.` for slot
access, so it ends up being a bit more concise: `chip.memory()` instead of
`(chip-memory chip)`.
We could use Lisp's `with-accessors` to clean up the actual usage a bit:
```lisp
(defun reset (chip)
(with-accessors ((memory chip-memory)
(registers chip-registers)
(running chip-running)
(program-counter chip-program-counter)
(stack chip-stack))
chip
(fill memory 0)
(fill registers 0)
(setf running t
program-counter #x200
(fill-pointer stack) 0)))
```
The *usage* looks much nicer now (`(fill memory 0)` is wonderfully readable) but
we haven't actually fixed anything. We've just shifted all the typing a few
lines up. But this is Lisp, we can do better!
Ideally what we'd like is to be able to do say something like `(with-chip (chip)
...)` to mean the giant `with-accessors` form above:
```lisp
(defun reset (chip)
(with-chip (chip)
(fill memory 0)
(fill registers 0)
(setf running t
program-counter #x200
(fill-pointer stack) 0)))
```
This is nice and readable. Some folks will dislike the fact that it introduces
new variable bindings that are "hidden" in the macro definition, but I like the
concision you get from it, especially for a small project like this.
We could write `with-chip` ourselves, if we wanted to. It would look something
like this:
```lisp
(defmacro with-chip ((chip) &body body)
`(with-accessors ((memory chip-memory)
(registers chip-registers)
; ...
)
,chip
,@body)`
)
```
It's not hard to write, just tedious. But we're using Lisp, so anything tedious
calls out for abstraction. Another macro from my utility library is
[`define-with-macro`][define-with-macro]. This is a macro-defining macro that
we can use to define `with-chip` for us:
```lisp
(define-with-macro chip
running memory stack registers index program-counter flag)
```
If the hairiness of a macro-defining macro scares you, don't worry about it. We
could have just written it by hand as shown above. I've just needed `with-FOO`
macros like these often enough that it's been worth it to abstract away the
tedium of writing them.
So one way or another we've got a nice `with-chip` macro that will let us access
the fields of our struct with bare names.
[define-with-macro]: https://github.com/sjl/cl-losh/blob/master/DOCUMENTATION.markdown#define-with-macro-macro
## Infrastructure
We'll need to define a bit of infrastructure for running things before we jump
into implementing the CHIP-8 CPU instructions.
### Resetting
Before we can emulate a ROM, we need to read it into our memory array. I've
chosen to do this in the `reset` function so we can just `(reset my-chip)` to
reload everything at once — it wouldn't make much sense to load a new ROM
*without* resetting the rest of the emulation state (though the results could
be... "interesting").
`reset` looks like this:
```lisp
(defun reset (chip)
(with-chip (chip)
(fill memory 0)
(fill registers 0)
(replace memory (read-file-into-byte-vector loaded-rom)
:start1 #x200)
(setf running t
program-counter #x200
(fill-pointer stack) 0))
(values))
```
This is pretty self explanatory, except for the actual ROM-loading bit:
```lisp
(replace memory (read-file-into-byte-vector loaded-rom)
:start1 #x200)
```
`replace` is just the standard Common Lisp `replace` function that copies the
contents of one sequence into another. `read-file-into-byte-vector` is from
Alexandria, and will just read the file at `loaded-rom` into a byte vector.
Then all we need to do is say that we want to start the copying at index `#x200`
in the destination, because that's where the CHIP-8 ROM data is supposed start
(there's other internal data (like font sprites) before it, which we'll see
later).
One last thing to note is that `reset` just returns `(values)`, i.e. it returns
nothing at all. This is something I sometimes do for functions I call at the
REPL for side effects, to avoid returning a meaningless result. I think of it
as an application of [The Rule of Silence][] for Lisp.
[The Rule of Silence]: http://www.linfo.org/rule_of_silence.html
### Loading ROMs
Now that we've got a reset function, it's trivial to define a function to load
a new ROM into our emulator:
```lisp
(defun load-rom (chip filename)
(setf (chip-loaded-rom chip) filename)
(reset chip))
```
I didn't bother with the `with-chip` macro here because we're only accessing
a single field.
### The Main Loop(s)
Now let's wrap things up into a nice interface. We'll define a top-level `run`
function that will be what we call to fire up the emulator:
```lisp
(defparameter *c* nil)
(defun run (rom-filename)
(let ((chip (make-chip)))
(setf *c* chip)
(load-rom chip rom-filename)
(run-cpu chip)))
```
This will get more complicated in the future, but for now it's pretty simple.
Make a new `chip` object, load the specified ROM, and start emulating.
I've added a `*c*` global variable that's bound to the currently-running
emulator so we can poke at it in NREPL or SLIME as it's running.
Now to write `run-cpu`:
```lisp
(defconstant +cycles-per-second+ 500)
(defconstant +cycles-before-sleep+ 10)
(defun run-cpu (chip)
(iterate
(while (chip-running chip))
(emulate-cycle chip)
(for tick :every-nth +cycles-before-sleep+ :do
(sleep (/ +cycles-before-sleep+ +cycles-per-second+)))))
```
CHIP-8 was designed to run on much weaker hardware than we have these days.
Even though we're emulating it, if we just run as fast as possible we'll be
running *far* too fast to be playable.
`+cycles-per-second+` is a constant describing our ideal emulation speed.
Anything from 300 to 800 or so is playable, depending on how fast you want games
to run. We'll just use 500 for now as a happy medium.
It would be wasteful to call `(sleep)` after every single cycle, so instead
we'll batch them together: run 10 instructions, sleep for a bit, repeat. This
is the job of the `(for ... every-nth N)` iterate driver, which is also in my
utility library. Every 10 iterations through the loop it will sleep for the
appropriate amount of time.
The size of the cycle batches is arbitrary — larger batches will result in fewer
`(sleep)` calls, but if you go too large you'll start noticing the emulator
getting "jumpy". 10-cycle batches at 500 cycles per second means that the
emulator will sleep for about 1/50 of a second each time, which isn't too
noticeable.
Now we've got the main loop all set up and just need to emulate each individual
cycle.
### Individual Cycles
CHIP-8 instructions are each two bytes long, and are stored
[big-endian](https://en.wikipedia.org/wiki/Endianness) in memory. So to emulate
a single cycle we:
* Read the two bytes starting at the program counter and concatenate them to get the instruction.
* Advance the program counter (to avoid having to do it inside every single instruction).
* Dispatch to the appropriate instruction code.
We'll define `emulate-cycle` and a couple of helper functions for this:
```lisp
(defun-inline chop (size integer)
(ldb (byte size 0) integer))
(defun-inline cat-bytes (high-order low-order)
(dpb high-order (byte 8 8) low-order))
(defun emulate-cycle (chip)
(with-chip (chip)
(let ((instruction (cat-bytes (aref memory program-counter)
(aref memory (1+ program-counter)))))
(zapf program-counter (chop 12 (+ % 2)))
(dispatch-instruction chip instruction))))
```
`chop` truncates an integer to the given number of bits. `cat-bytes`
concatenates two bytes. This are pretty simple, but I prefer the more
descriptive names over writing `dpb` (deposit byte) and `ldb` (load byte)
everywhere.
`zapf` is from my utility library. I've written [an entire post][zapf] about
it.
What happens when the program counter is at the final index into memory? None
of the CHIP-8 references I found specify what should happen. We could signal an
error, or just wrap around to 0. I've chosen the latter by chopping `(+
program-counter 2)` to 12 bits, but signaling an error would be easy too.
[zapf]: http://stevelosh.com/blog/2016/08/playing-with-syntax/
### Instruction Dispatch
The CHIP-8's instruction scheme is a bit different than most others that I've
seen.
For systems like the Game Boy instructions have a one- or two-byte opcode, with
arguments following. For systems like this you can dispatch on opcode by doing
a giant `case` statement:
```lisp
(case opcode
(#x00 (op-foo ...))
(#x01 (op-bar ...))
; ...
)
```
But a more efficient way to do it is often to shove all the `op-` functions into
an array, and then just use the opcode itself as the index into the array to
find the function:
```lisp
(funcall (aref opcodes opcode) ...)
```
But the CHIP-8 differentiates instructions a bit strangely. All instructions
are two bytes long, *including* their arguments. Instead of just using the
first N bits as the opcode, some instructions use a combination of high- and
low-order bits. For example, the logical `AND`, `OR`, and `XOR` are specified
by starting the instruction with an `8` nibble and ending it with `1`, `2`, or
`3`, with the "arguments" being the two nibbles in the middle:
8xy1 - OR Vx, Vy
8xy2 - AND Vx, Vy
8xy3 - XOR Vx, Vy
This makes it rather annoying to use some kind of function table approach.
There are only a few dozen opcodes, so instead of trying to hack something
together we'll just use a big old `case` instead:
```lisp
(defun dispatch-instruction (chip instruction)
(macrolet ((call (name) `(,name chip instruction)))
(ecase (logand #xF000 instruction)
(#x0000 (ecase instruction
(#x00E0 (call op-cls))
(#x00EE (call op-ret))))
(#x1000 (call op-jp-imm))
(#x2000 (call op-call))
(#x3000 (call op-se-reg-imm))
(#x4000 (call op-sne-reg-imm))
(#x5000 (ecase (logand #x000F instruction)
(#x0 (call op-se-reg-reg))))
(#x6000 (call op-ld-reg<imm))
(#x7000 (call op-add-reg<imm))
(#x8000 (ecase (logand #x000F instruction)
(#x0 (call op-ld-reg<reg))
(#x1 (call op-or))
(#x2 (call op-and))
(#x3 (call op-xor))
(#x4 (call op-add-reg<reg))
(#x5 (call op-sub-reg<reg))
(#x6 (call op-shr))
(#x7 (call op-subn-reg<reg))
(#xE (call op-shl))))
(#x9000 (ecase (logand #x000F instruction)
(#x0 (call op-sne-reg-reg))))
(#xA000 (call op-ld-i<imm))
(#xB000 (call op-jp-imm+reg))
(#xC000 (call op-rand))
(#xD000 (call op-draw))
(#xE000 (ecase (logand #x00FF instruction)
(#x9E (call op-skp))
(#xA1 (call op-sknp))))
(#xF000 (ecase (logand #x00FF instruction)
(#x07 (call op-ld-reg<dt))
(#x0A (call op-ld-reg<key))
(#x15 (call op-ld-dt<reg))
(#x18 (call op-ld-st<reg))
(#x1E (call op-add-index<reg))
(#x29 (call op-ld-font<vx))
(#x33 (call op-ld-bcd<vx))
(#x55 (call op-ld-mem<regs))
(#x65 (call op-ld-regs<mem)))))))
```
The `macrolet` at the beginning saves us a bit of typing, but otherwise this is
just a big boring table to figure out which instruction to call.
That's all the boring infrastructure work we need — on to implementing the
actual instructions.
## Instructions
The CHIP-8 support thirty six instructions, all of which we'll need to
implement. We'll start with the simpler ones, and we'll be leaving some of the
others (the graphics/sound related ones) for later articles.
(In contrast, the Game Boy has roughly five hundred instructions, so now you
might see why I thought CHIP-8 would be simpler!)
### Random Numbers
We'll start with the `RND` instruction, which generates random numbers. This
may seem like an odd place to start, but I want to describe some extra syntactic
sugar and `RND` is a nice standalone instruction to use as an example.
Cowgod's reference describes `RND` like so:
Cxkk - RND Vx, byte
Set Vx = random byte AND kk.
The interpreter generates a random number from 0 to 255,
which is then ANDed with the value kk. The results are
stored in Vx.
A first stab at the implementation in Lisp might look like this:
```lisp
(defun op-rand (chip instruction)
(let ((reg (logand #x0F00 instruction))
(mask (logand #x00FF instruction)))
(with-chip (chip)
(setf (aref registers reg)
(logand (random 256) mask)))))
```
This would work, but it's an awful lot of code for something that just takes
a sentence or two to describe. We're going to be defining a lot of
instructions, so let's take a few minutes and make our lives easier.
### Define-Instruction
We'll create a `define-instruction` macro that will abstract away some of the
boring bits. The goal is to end up with instruction definitions that read as
close to the documentation as possible.
We'll start by removing the need to use the `with-chip` macro. Every
instruction needs to deal with the `chip` struct, so let's not repeat ourselves
thirty six times. Every instruction will also take `chip` and `instruction`
arguments, so we can remove those too:
```lisp
(defmacro define-instruction (name &body body)
`(defun ,name (chip instruction)
(declare (ignorable instruction))
(with-chip (chip)
,@body)
nil))
(define-instruction op-rand
(let ((reg (logand #x0F00 instruction))
(mask (logand #x00FF instruction)))
(setf (aref registers reg)
(logand (random 256) mask))))
```
That's a little better. We're going to be calling these instructions a *lot*,
so it wouldn't hurt to add a type declaration for each function. This is easy
because they all take and return the same types:
```lisp
(defmacro define-instruction (name &body body)
`(progn
(declaim (ftype (function (chip int16) null) ,name)) ; NEW
(defun ,name (chip instruction)
(declare (ignorable instruction))
(with-chip (chip)
,@body)
nil)))
```
Now all of our instruction functions will have type hints, and SBCL can check
them (if `safety` is high) or use them to generate faster code (if `speed` is
high).
We'll be accessing the values of registers quite often (`(aref registers ...)`)
so let's add a little `macrolet` to make that read nicer:
```lisp
(defmacro define-instruction (name &body body)
`(progn
(declaim (ftype (function (chip int16) null) ,name))
(defun ,name (chip instruction)
(declare (ignorable instruction))
(with-chip (chip)
(macrolet ((register (index) ; NEW
`(aref registers ,index))) ; NEW
,@body))
nil)))
(define-instruction op-rand
(let ((reg (logand #x0F00 instruction))
(mask (logand #x00FF instruction)))
(setf (register reg) ; NEW
(logand (random 256) mask))))
```
Now instead of `(aref registers ...)` we can just say `(register ...)`. Cool.
```lisp
(defmacro define-instruction (name &body body)
`(progn
(declaim (ftype (function (chip int16) null) ,name))
(defun ,name (chip instruction)
(declare (ignorable instruction))
(with-chip (chip)
(macrolet ((register (index)
`(aref registers ,index)))
(let ,(parse-instruction-argument-bindings argument-list)
,@body))
nil))))
(define-instruction op-rand
(let ((reg (logand #x0F00 instruction))
(mask (logand #x00FF instruction)))
(setf (aref registers reg)
(logand (random 256) mask))))
```
The one thing that still bothers me is having to manually pull the instruction
arguments out of the instruction with bitmasking. It would be much nicer if we
could just declare what the arguments look like and have the computer generate
the appropriate masking code to deal with them. The goal is to be able to write
something like this:
```lisp
(define-instruction op-rand (_ r (mask 2)) ;; RND
(setf (register r)
(logand (random 256) mask)))
```
The `(_ r (mask 2))` is the "argument list" of the instruction. It says:
* A single-nibble value which we don't care about: `_`
* A single-nibble value should be bound to `r`: `r`
* A two-nibble value should be bound to `mask`: `(mask 2)`
Compare the Lisp code and Cowgod's documentation:
```
Cxkk - RND Vx, byte
Set Vx = random byte AND kk.
(define-instruction op-rand (_ r (mask 2)) ;; RND
(setf (register r)
(logand (random 256) mask)))
```
Cowgod uses `V` as a shorthand for `register`, and calls the argument `x`
instead of `r`, but otherwise I think this is pretty damn close to the
documentation for actual running code.
So let's implement the argument-parsing macro. Feel free to skip this if you're
not really comfortable with macros. But it's a good demonstration of how you
can use them to get a nice clean language for a simple project.
First we'll wrap the `body` in a `let`:
```lisp
; NEW
(defmacro define-instruction (name argument-list &body body)
`(progn
(declaim (ftype (function (chip int16) null) ,name))
(defun ,name (chip instruction)
(declare (ignorable instruction))
(with-chip (chip)
(macrolet ((register (index)
`(aref registers ,index)))
(let ,(parse-instruction-argument-bindings argument-list) ; NEW
,@body))
nil))))
```
We'll use a helper function to parse the argument list into a list of `let`
bindings, instead of trying to cram it all into this one macro. It might look
scary, but it's not actually too bad:
```lisp
(defun parse-instruction-argument-bindings (argument-list)
(flet ((normalize-arg (arg)
(destructuring-bind (symbol &optional (nibbles 1))
(ensure-list arg)
(list symbol nibbles))))
(iterate
(for (symbol nibbles) :in (mapcar #'normalize-arg argument-list))
(for position :first 3 :then (- position nibbles))
(when (not (eql symbol '_))
(collect `(,symbol (ldb (byte ,(* nibbles 4)
,(* position 4))
instruction)))))))
```
`normalize-arg` takes each argument from the list and turns it into `(symbol
nibbles)`, so we don't have to write the lengths for single-nibble arguments
like this: `((_ 1) (r 1) (mask 2))`.
Then we loop through each `(symbol nibbles)` pair in the argument list. We
start at position `3` in the byte (the highest-order nibble) because we want to
write the argument list from left to right, high-order to low-order, like the
documentation.
For each pair, if the symbol is anything other than `_` we collect a `let`
binding with the appropriate `ldb` call for it. So for our example of `(_
r (mask 2))` we end up with two `let` bindings:
* `(r (ldb (byte 4 8) instruction))`
* `(mask (ldb (byte 8 0) instruction))`
Notice that we only bother parsing out the bindings we *need* from the
instruction. For instructions that don't need any arguments we'll end up with
an empty `(let () ...)` which the compiler will optimize away.
This might seem a bit hairy. The nice thing about using a helper function like
this is that we can call it on its own with a variety of argument lists to see
what gets generated:
```
(map nil #'print
(parse-instruction-argument-bindings '(_ r (mask 2))))
(R (LDB (BYTE 4 8) INSTRUCTION))
(MASK (LDB (BYTE 8 0) INSTRUCTION))
(map nil #'print
(parse-instruction-argument-bindings '(_ x y _)))
(X (LDB (BYTE 4 8) INSTRUCTION))
(Y (LDB (BYTE 4 4) INSTRUCTION))
(map nil #'print
(parse-instruction-argument-bindings '(_ (foo 3))))
(FOO (LDB (BYTE 12 0) INSTRUCTION))
```
And that wraps up `define-instruction`. So instead of writing `RND` as
a vanilla function:
```lisp
(defun op-rand (chip instruction)
(let ((reg (logand #x0F00 instruction))
(mask (logand #x00FF instruction)))
(with-chip (chip)
(setf (aref registers reg)
(logand (random 256) mask)))))
```
We can do something much cleaner:
```lisp
(define-instruction op-rand (_ r (mask 2)) ;; RND
(setf (register r)
(logand (random 256) mask)))
```
This is going to pay off nicely as we implement the other thirty five
instructions.
### Jumps and Calls
The CHIP-8 has two instructions for jumping directly to an address. The first
jumps to an immediate, literal address. The second adds an immediate value to
whatever is in register `#x0` and jumps to the result:
```lisp
(define-instruction op-jp-imm (_ (target 3)) ;; JP addr
(setf program-counter target))
(define-instruction op-jp-imm+reg (_ (target 3)) ;; JP V0 + addr
(setf program-counter (chop 12 (+ target (register 0)))))
```
Our `define-instruction` macro is already paying off. The immediate values of
these arguments are three nibbles each, but our macro doesn't care.
There are also two instructions for implementing traditional function calls and
returns using the CHIP-8's stack:
```lisp
(define-instruction op-call (_ (target 3)) ;; CALL addr
(vector-push program-counter stack)
(setf program-counter target))
(define-instruction op-ret () ;; RET
(setf program-counter (vector-pop stack)))
```
We just use the built in `vector-push` and `vector-pop` functions to manage the
stack's fill pointer trivially.
Note that we're NOT using `vector-push-extend` because the CHIP-8 stack is
defined by the spec to only hold at most sixteen addresses — any ROM that tries
to push more is broken.
### Binary-Coded Decimal
Let's take another self-contained instruction next: `BCD`, which stands for
[binary-coded decimal][BCD] (some references call this instruction `LD B, Vx`
but I think it's different enough to deserve its own name).
The problem this instruction is designed to solve goes something like this.
Let's say you've got a game where the player has a score that changes over time.
You can store the player's score in a register or memory somewhere, and
add/subtract to/from it with the normal arithmetic opcodes no problem.
But now you want to *display* the score to the player, and you probably want to
do that in base 10 because humans are generally bad at reading binary or hex.
So how do you take a byte like `#xA5` and determine the hundreds, tens, and ones
sprites to draw on the screen to read "165 points"?
This is what the `BCD` instruction does. It takes a single argument (the
register) and stores the hundreds, tens, and ones digits of that register's
value into three separate bytes of memory, starting at wherever the `index`
register is currently pointing.
<pre class="lineart">
Register V3 Index Register
┌───┐ ┌───┐
│135│ │...│
└───┘ └─┬─┘
┌─────────────┘
│
▼
┌───┬───┬───┬───┬───┐
│ │ │ │ │ │ Memory
└───┴───┴───┴───┴───┘
Run BCD V3 instruction =================
Register V3 Index Register
┌───┐ ┌───┐
│135│ │...│
└───┘ └─┬─┘
┌─────────────┘
│
▼
┌───┬───┬───┬───┬───┐
│ 1 │ 3 │ 5 │ │ │ Memory
└───┴───┴───┴───┴───┘
</pre>
We'll split this into two parts to make it easier to read. First we'll make
a `bcd` function to actually get the digits:
```lisp
(defun-inline bcd (integer)
(values (-<> integer (floor <> 100) (mod <> 10))
(-<> integer (floor <> 10) (mod <> 10))
(-<> integer (floor <> 1) (mod <> 10))))
```
And make sure it works on its own:
```
[SBCL] CHIP8> (bcd 135)
1
3
5
```
And then we can define the actual operation:
```lisp
(define-instruction op-ld-bcd<vx (_ r _ _) ;; LD B, Vx
(setf (values (aref memory (+ index 0)) ; hundreds
(aref memory (+ index 1)) ; tens
(aref memory (+ index 2))) ; ones
(bcd (register r))))
```
This takes advantage of the fact that you can use `(setf (values ...) ...)` to
assign all the multiple values returned by `bcd` at once, without binding them
to local variables (though because `bcd` itself is inline, there won't actually
be any *returning* at all...).
[BCD]: https://en.wikipedia.org/wiki/Binary-coded_decimal
```lisp
```
```lisp
```
```lisp
```
```lisp
```
```lisp
```
```lisp
```
```lisp
```
```lisp
```
```lisp
```