content/blog/2016/12/chip8-input.markdown @ 9dd13d5e7522

+++
title = "CHIP-8 in Common Lisp: Input"
snip = "Let's add a keypad."
date = 2016-12-23T16:00:00Z
draft = false

+++

In the previous posts we looked at how to emulate a [CHIP-8][] CPU with Common
Lisp, and added a screen to see the results.  This is enough for graphical demos
like `maze.rom`, but in this post we'll add user input so we can actually *play*
games.

The full series of posts so far:

1. [CHIP-8 in Common Lisp: The CPU](http://stevelosh.com/blog/2016/12/chip8-cpu/)
2. [CHIP-8 in Common Lisp: Graphics](http://stevelosh.com/blog/2016/12/chip8-graphics/)
3. [CHIP-8 in Common Lisp: Input](http://stevelosh.com/blog/2016/12/chip8-input/)
4. [CHIP-8 in Common Lisp: Sound](http://stevelosh.com/blog/2016/12/chip8-sound/)
5. [CHIP-8 in Common Lisp: Disassembly](http://stevelosh.com/blog/2017/01/chip8-disassembly/)
6. [CHIP-8 in Common Lisp: Debugging Infrastructure](http://stevelosh.com/blog/2017/01/chip8-debugging-infrastructure/)
7. [CHIP-8 in Common Lisp: Menus](http://stevelosh.com/blog/2017/01/chip8-menus/)

The full emulator source is on [BitBucket][] and [GitHub][].

[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>

## The Keypad

The CHIP-8 was designed to work with a hexadecimal keypad like this:

<pre class="lineart">
    ┌─┬─┬─┬─┐
    │1│2│3│C│
    ├─┼─┼─┼─┤
    │4│5│6│D│
    ├─┼─┼─┼─┤
    │7│8│9│E│
    ├─┼─┼─┼─┤
    │A│0│B│F│
    └─┴─┴─┴─┘
</pre>

This is kind of a strange input device compared to most other keyboards and
controllers.  Often it can be a bit tricky to figure out how to control
a particular game, since most don't include any instructions.  But at least the
*implementation* is pretty simple.

## Architecture

Once again we'll separate the emulation layer from the user interface layer,
like we did with the graphics.  The `chip` struct will have an array of
"keyboard memory" to read from, and the user interface will write into this
array as the user presses keys.

## The Emulation Layer

We'll start with the emulation side of things.

### Keyboard Memory

First we'll add an array of sixteen booleans to the `chip` struct to hold the
currently-pressed state of each keypad key:

```lisp
(defstruct chip
  ; ...
  (keys (make-array 16 :element-type 'boolean :initial-element nil)
        :type (simple-array boolean (16))
        :read-only t)
  ; ...
  )
```

We'll also add two functions for writing to this array that the user interface
will eventually use:

```lisp
(defun keydown (chip key)
  (setf (aref (chip-keys chip) key) t))

(defun keyup (chip key)
  (setf (aref (chip-keys chip) key) nil))
```

And let's make sure to clear it when we reset the emulator:

```lisp
(defun reset (chip)
  (with-chip (chip)
    ; ...
    (fill keys nil)
    ; ...
    )
  (values))
```

### Keyboard Branching: SKP and SKNP

The CHIP-8 has two keyboard-related branching instructions: `SKP` and `SKNP`
("skip when pressed" and "skip when not pressed").

Much like the other branching instructions the make the CPU skip the next
instruction if a particular key is pressed.  Their implementation is pretty
simple — to check if key `N` is pressed we just look at the value of index `N`
in the keyboard memory:

```lisp
(define-instruction op-skp (_ r _ _)                    ;; SKP
  (when (aref keys (register r))
    (incf program-counter 2)))

(define-instruction op-sknp (_ r _ _)                   ;; SKNP
  (when (not (aref keys (register r)))
    (incf program-counter 2)))
```

### Waiting for Input: LD Vx, K

The other keyboard-related instruction is a bit trickier.  From [Cowgod's
documentation][cg-key]:

    Fx0A - LD Vx, K
    Wait for a key press, store the value of the key in Vx.

    All execution stops until a key is pressed, then the value of
    that key is stored in Vx.

It's not 100% clear what "all execution" means, as we'll see when we get to the
post on audio.  But we can put together a basic implementation pretty easily:

```lisp
(define-instruction op-ld-reg<key (_ r _ _)    ;; LD Vx, Key (await)
  (let ((key (position t keys)))
    (if key
      (setf (register r) key)
      ;; If we don't have a key, just execute this instruction
      ;; again next time.
      (decf program-counter 2))))
```

The `(position t keys)` here takes advantage of the fact that the index of
a slot in the `keys` array also happens to be the name/number of the key.  If
`position` doesn't find a `t` in the array it will just return `nil`.

To simulate the stopping of execution we just use a little trick: we rewind the
program counter so this instruction gets executed again on the next cycle.

We could probably come up with a way to avoid this busy-looping, but it would
add extra complexity, especially when we get to the pausing and debugging
infrastructure later.  This should work fine for our needs.

[cg-key]: http://devernay.free.fr/hacks/chip8/C8TECH10.HTM#Fx0A

## The User Interface Layer

That's all we have to do on the emulation side of things.  Now we need to get Qt
to read our keyboard input and pass it along to the `chip`.

### Key Mappings

The first thing we'll need to do is decide how we'd like to map the CHIP-8's
keyboard onto our modern keyboard.  If you've got a keyboard with a number pad
you might prefer something like this:

<pre class="lineart">
    Original Chip-8 Pad → Modern Numpad
    ┌─┬─┬─┬─┐             ┌─┬─┬─┬─┐
    │1│2│3│C│             │←│/│*│-│
    ├─┼─┼─┼─┤             ├─┼─┼─┼─┤
    │4│5│6│D│             │7│8│9│+│
    ├─┼─┼─┼─┤             ├─┼─┼─┤ │
    │7│8│9│E│             │4│5│6│ │
    ├─┼─┼─┼─┤             ├─┼─┼─┼─┤
    │A│0│B│F│             │1│2│3│↲│
    └─┴─┴─┴─┘             ├─┴─┼─┤ │
                          │0  │.│ │
                          └───┴─┴─┘
</pre>

Which we can implement with a big `qtenumcase`:

```lisp
(defun pad-key-for (code)
  (qtenumcase code
    ((q+:qt.key_clear) #x1)
    ((q+:qt.key_slash) #x2)
    ((q+:qt.key_asterisk) #x3)
    ((q+:qt.key_minus) #xC)

    ((q+:qt.key_7) #x4)
    ((q+:qt.key_8) #x5)
    ((q+:qt.key_9) #x6)
    ((q+:qt.key_plus) #xD)

    ((q+:qt.key_4) #x7)
    ((q+:qt.key_5) #x8)
    ((q+:qt.key_6) #x9)
    ((q+:qt.key_enter) #xE)

    ((q+:qt.key_1) #xA)
    ((q+:qt.key_2) #x0)
    ((q+:qt.key_3) #xB)
    ((q+:qt.key_0) #xF)))
```

Note that even though the constants like `q+:qt.key_clear` end up being numbers,
you still need to surround them with parentheses for Qtools' magic name-mangling
to take effect properly.  If you just say `(qtenumcase code (q+:qt.key_clear #x1) ...)`
you'll get an error like:

```
;     (QTOOLS:QTENUMCASE CHIP8.GUI.SCREEN::CODE
;       (QTOOLS:Q+ "QT.KEY_CLEAR" 1))
; --> LET COND IF
; ==>
;   (QT:ENUM-EQUAL #:KEY0 QTOOLS:Q+)
;
; caught WARNING:
;   undefined variable: Q+
;
; compilation unit finished
;   Undefined variable:
;     Q+
;   caught 1 WARNING condition
```

The magic name-mangling in Qtools bothers me a little, but I'm sure the
alternative would be far more verbose, so I live with it.

Anyway, moving on.  If you've got a laptop or a tenkeyless keyboard you might
prefer a key mapping scheme more like this:

<pre class="lineart">
    Original Chip-8 Pad → Laptop
    ┌─┬─┬─┬─┐             ┌─┬─┬─┬─┐
    │1│2│3│C│             │1│2│3│4│
    ├─┼─┼─┼─┤             ├─┼─┼─┼─┤
    │4│5│6│D│             │Q│W│E│R│
    ├─┼─┼─┼─┤             ├─┼─┼─┼─┤
    │7│8│9│E│             │A│S│D│F│
    ├─┼─┼─┼─┤             ├─┼─┼─┼─┤
    │A│0│B│F│             │Z│X│C│V│
    └─┴─┴─┴─┘             └─┴─┴─┴─┘
</pre>

```lisp
(defun pad-key-for (code)
  (qtenumcase code
    ((q+:qt.key_1) #x1)
    ((q+:qt.key_2) #x2)
    ((q+:qt.key_3) #x3)
    ((q+:qt.key_4) #xC)

    ((q+:qt.key_q) #x4)
    ((q+:qt.key_w) #x5)
    ((q+:qt.key_e) #x6)
    ((q+:qt.key_r) #xD)

    ((q+:qt.key_a) #x7)
    ((q+:qt.key_s) #x8)
    ((q+:qt.key_d) #x9)
    ((q+:qt.key_f) #xE)

    ((q+:qt.key_z) #xA)
    ((q+:qt.key_x) #x0)
    ((q+:qt.key_c) #xB)
    ((q+:qt.key_v) #xF)))
```

Of course the ideal solution is to make the mapping configurable at run time,
but I'll leave that as an exercise you can do if you're interested.

### Qt Keyboard Overrides

Now that we have `pad-key-for` to turn a Qt key into a CHIP-8 key we can write
the overrides for our Qt `screen`.  We'll start with the `key-press-event`:

```lisp
(define-override (screen key-press-event) (ev)
  (let* ((key (q+:key ev))
         (pad-key (pad-key-for key)))
    (when pad-key
      (chip8::keydown chip pad-key)))
  (stop-overriding))
```

We check to see if the key we got was a pad key, and if so we call `keyup`
from earlier to mark it in the keyboard array.  We'll ignore any presses of
unknown keys in this handler.

Next we'll handle when the user releases a key:

```lisp
(define-override (screen key-release-event) (ev)
  (let* ((key (q+:key ev))
         (pad-key (pad-key-for key)))
    (if pad-key
      (chip8::keyup chip pad-key)
      (qtenumcase key
        ((q+:qt.key_escape) (die screen))
        ((q+:qt.key_f1)     (chip8::reset chip))
        (t (pr :unknown-key (format nil "~X" key))))))
  (stop-overriding))
```

Much like `key-press-event` we check for a pad key and call `keyup` if we got
one.  We also set up a couple of other handy mappings to control the emulator:

* `F1` calls `reset` so we can easily reset the emulator without having to tab
  back to the Lisp REPL.
* `Esc` will quit the emulator (and GUI).

I've also included a fallback case that will print out any unknown keys in hex.
This was useful to cross reference with the Qt docs when I was trying to figure
out what the Qt constant name was for a particular key like "clear" on the
number pad.

## Results

That's all we need to do to handle user input!  Now we can finally *play* some
games!  `ufo.rom` is one of my favorites, as is `blitz.rom` (once I figured out
the screen clipping bug).

## Future

We're nearing the end of the emulator — the only thing strictly necessary is
adding sound, which we'll take care of in the next post.

After that I'll talk about adding some debugging infrastructure to the emulator
so we can look at what's going on, as well as adding a basic graphical debugger
UI with Qt.