content/blog/2016/12/chip8-sound.markdown @ 21f5607dfbad

First draft of menus article
author Steve Losh <steve@stevelosh.com>
date Thu, 05 Jan 2017 19:46:43 +0000
parents d9aba755de81
children 71f98b4ce464
+++
title = "CHIP-8 in Common Lisp: Sound"
snip = "Let's add a buzzer."
date = 2016-12-26T17:30:00Z
draft = false

+++

In the previous posts we looked at how to emulate a [CHIP-8][] CPU with Common
Lisp, added a screen to see the results, and added user input so we could play
games.  This is good enough for basic play, but if we want the full experience
we'll need to add sound.  Let's [finish][] the emulator.

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/)

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
[finish]: http://makegames.tumblr.com/post/1136623767/finishing-a-game

<div id="toc"></div>

## CHIP-8 Sound

The CHIP-8 has an *extremely* simple sound and timer system.  See [Cowgod's
documentation][cg-sound] for an overview.

In a nutshell there are two registers: the "sound timer" and "delay timer".
Each of these is decremented sixty times per second whenever they are non-zero.

The delay timer has no special behavior beyond this, but ROMs can read its value
and use it as a real-time clock.

The sound timer cannot be read by ROMs, only written.  Whenever its value is
positive the CHIP-8's buzzer will sound.  That's the extent of the CHIP-8's
sound: one buzzer that's either on or off.

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

## The Emulation Layer

Let's add the required registers and instructions to the emulator.

### Data

First we'll add the registers into the `chip` struct:

```lisp
(defstruct chip
  ; ...
  (delay-timer 0 :type fixnum)
  (sound-timer 0 :type fixnum)
  ; ...
  )
```

These are of type `fixnum` instead of `int8` for reasons we'll see later.

### Instructions

The CHIP-8 has three `LD` instructions for dealing with these registers.  We
actually saw them back in the first post, but now we know their purpose:

```lisp
(macro-map                                              ;; LD
    (NAME           ARGLIST         DESTINATION   SOURCE)
    (; ...
     (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)))
```

### Timers

Next we'll need to decrement the timers at a rate of 60hz.  We could do some
math to figure out the number of cycles between each and do this in the main
loop, but let's use a separate thread instead:

```lisp
(defun run (rom-filename)
  (let ((chip (make-chip)))
    (setf *c* chip)
    (load-rom chip rom-filename)
    (bt:make-thread (curry #'run-cpu chip))
    (bt:make-thread (curry #'run-timers chip)) ; NEW
    (chip8.gui.screen::run-gui chip)))
```

Now we just need to define the `run-timers` function that will be run in that
separate thread:

```lisp
(defun run-timers (chip)
  (iterate
    (while running)
    (decrement-timers chip)
    (sleep 1/60)))
```

Simple enough.  Technically this will run slightly *slower* than 60hz, because
it will take some time to actually decrement the timers, and our thread might
not get woken up exactly 1/60 of a second later.

We could try to fix this by sleeping for less or using a [timer wheel][], but
I think this is good enough for our needs here.  We already have to suffer
through GC pauses anyway, so trying to get absolute precision is going to be
more trouble that it's worth.

[timer wheel]: https://github.com/npatrick04/timer-wheel

Now to decrement the timers.  The CPU thread might be executing a write
instruction as this thread is updating, so we'll use SBCL's atomic
compare-and-swap functionality to avoid losing decrements:

```lisp
(defun decrement-timers (chip)
  (flet ((decrement (i)
           (if (plusp i)
             (1- i)
             0)))
    (with-chip (chip)
      (sb-ext:atomic-update delay-timer #'decrement)
      (sb-ext:atomic-update sound-timer #'decrement)))
  nil)
```

This is why we declared the timer slots in the `chip` struct to be `fixnum`
— the [SBCL manual][] states that for `(atomic-update place function ...)`:

> place can be any place supported by `sb-ext:compare-and-swap`

And that:

> Built-in CAS-able places are accessor forms whose car is one of the following:
>
> ...
>
> **or the name of a defstruct created accessor for a slot whose declared type is
> either fixnum or t. Results are unspecified if the slot has a declared type
> other than fixnum or t.**

(emphasis mine).  Remember that `delay-timer` is `macrolet`ed to
`(chip-delay-timer ...)` by `with-chip`, so it does refer to a "defstruct
created accessor".

We could have used a lock from bordeaux threads to manage this portably (though
more slowly), but I wanted to play around with SBCL's concurrency stuff.

[SBCL manual]: http://www.sbcl.org/manual/#Atomic-Operations

## Sound From Scratch

Now that we've got the timers all set up, all that's left is to play a sound
whenever `sound-timer` is positive.  We could do this in a number of ways, for
example: loading a `WAV` file and looping it.  But that's boring and almost
cheating, so let's do it from scratch.

[Sound][] is a pretty complicated beast.  For this CHIP-8 emulator we'll only
dip our toes into the water and work with the very basics.  I'll explain some
basics here but will simplify and gloss over a lot — there are plenty of
resources online if you want to learn more.

[Sound]: https://en.wikipedia.org/wiki/Sound

For our purposes we'll think of "sound" as a pressure value over time.  For
example, a simple sound wave might look something like this:

[![Graph of a basic sound wave](/media/images/blog/2016/12/chip8-sound-basic.png)](/media/images/blog/2016/12/chip8-sound-basic.png)

The pressure starts at 0, gradually climbs until it hits 1, then falls and
gradually hits -1, then returns to 0 and starts the process over again.

The distance from the highest pressure value to the lowest is called the
"amplitude" of the wave (specifically "peak-to-peak amplitude").  For sound,
this is what determines how loud the sound is.  For the CHIP-8 emulator we'll
always just be using pressure values between -1 and 1.

There are (infinitely) many different types of sound waves, each with their own
distinct character.  Let's look at a few of them that might fit well with the
CHIP-8's retro aesthetic.  [This page][waveforms] has some example audio files
so you can hear what they sound like.

[waveforms]: http://public.wsu.edu/~jkrug/MUS364/audio/Waveforms.htm

### Sine Waves

The wave I used as the example above is a [sine wave][].  It's based on [the
`sine` function][sine] you might have learned about in trigonometry class.

We usually think of `sin` as taking an angle as an argument, not a time.  But we
can convert time to an appropriate angle value later, so let's not get hung up
on that.  Sine performs one complete "wave" in exactly [τ][tau] radians:

[![Graph of a basic sine wave](/media/images/blog/2016/12/chip8-sound-sine.png)](/media/images/blog/2016/12/chip8-sound-sine.png)

Common Lisp has this built in as the `sin` function, so we don't have any work
to do for this one.

[sine]: https://en.wikipedia.org/wiki/Sine
[sine wave]: https://en.wikipedia.org/wiki/Sine_wave
[tau]: https://www.youtube.com/watch?v=jG7vhMMXagQ

### Square Waves

The next wave we'll look at is the [square wave][].  Instead of gradually moving
between -1 and 1 over time like sine, it stays at 1 for half its wave then
immediately jumps straight to -1:

[![Graph of a basic square wave](/media/images/blog/2016/12/chip8-sound-square.png)](/media/images/blog/2016/12/chip8-sound-square.png)

This "jump" gives the square wave kind of a "buzzy" character that you may have
heard before if you've played many old computer games (or like to listen to
chiptunes).


Common Lisp doesn't have this function built in, but we can make it pretty
easily.  First we'll define some useful constants:

```lisp
(defconstant +pi+ (coerce pi 'single-float))
(defconstant +tau+ (* 2 +pi+))
(defconstant +1/4tau+ (* 1/4 +tau+))
(defconstant +1/2tau+ (* 1/2 +tau+))
(defconstant +3/4tau+ (* 3/4 +tau+))
```

We're using single-floats because our audio library is going to want those
later.

Now we can define the square-wave function:

```lisp
(defun sqr (angle)
  (if (< (mod angle +tau+) +1/2tau+)
    1.0
    -1.0))
```

I've called it `sqr` because my utility library already has a function called
"square", and I like that it's three letters like the `sin` function.

The implementation is pretty simple.  We just have to make sure to `mod` the
angle by τ to make the results repeat properly, like this:

[![Graph of several square waves](/media/images/blog/2016/12/chip8-sound-square-repeat.png)](/media/images/blog/2016/12/chip8-sound-square-repeat.png)

[square wave]: https://en.wikipedia.org/wiki/Square_wave

### Sawtooth Waves

The [sawtooth wave][] is next up in our little menagerie of waveforms.  The name
comes from what it looks like when you have a few in a row:

[![Graph of several sawtooth waves](/media/images/blog/2016/12/chip8-sound-saw-repeat.png)](/media/images/blog/2016/12/chip8-sound-saw-repeat.png)

A single wave of it looks like this:

[![Graph of a basic sawtooth wave](/media/images/blog/2016/12/chip8-sound-saw.png)](/media/images/blog/2016/12/chip8-sound-saw.png)

Sawtooth waves still have a bit of a "buzzy" feel to them because of the jump
halfway through their period, but unlike square waves they have *some* gradual
change, so they're often a nice happy medium.

To implement the `saw` function, notice that for the first half of the wave's
life (0 to τ) it goes from 0 to 1, and for the second half (½τ to τ) it goes
from -1 to 0.  We'll also remember to `mod` by τ to proper repeating:

```lisp
(defun saw (angle)
  (let ((a (mod angle +tau+)))
    (if (< a +1/2tau+)
      (map-range 0   +1/2tau+
                 0.0 1.0
                 a)
      (map-range +1/2tau+ +tau+
                 -1.0     0.0
                 a))))
```

[`map-range`][map-range] is a *really* handy function from my utility library.
I wish I could think of a better name for it.  It's kind of like a [lerp][]
function, but instead of assuming the input value is between 0 and 1 it allows
you to specify the input range.

`map-range` takes five arguments:

    (map-range source-start source-end
               dest-start   dest-end
               value)

I think of it as taking a source number line with a value on it, stretching that
number line to become the destination line, and finding the new location of the
value:

<pre class="lineart">
         2  3  4  5  6                2  3  4  5  6
         ━━◉━━━━━━━━━━                ━━━━━━━━━◎━━━
        ╱  │          ╲              ╱         │   ╲
       ╱   │           ╲            ╱          │    ╲
      ╱ ┌──┘            ╲          ╱           └───┐ ╲
     ╱  │                ╲        ╱                │  ╲
    ╱   ▼                 ╲      ╱                 ▼   ╲
    ━━━━◉━━━━━━━━━━━━━━━━━━━     ━━━━━━━━━━━━━━━━━━◎━━━━━
    0  1  2  3  4  5  6  7 8     0  1  2  3  4  5  6  7 8
</pre>

[sawtooth wave]: https://en.wikipedia.org/wiki/Sawtooth_wave
[map-range]: https://github.com/sjl/cl-losh/blob/master/DOCUMENTATION.markdown#map-range-function
[lerp]: https://en.wikipedia.org/wiki/Linear_interpolation

### Triangle Waves

Let's look at one more kind of wave before moving on: the [triangle wave][].  As
you might expect, this wave looks like a big triangle:

[![Graph of a basic triangle wave](/media/images/blog/2016/12/chip8-sound-tri.png)](/media/images/blog/2016/12/chip8-sound-tri.png)

Triangle waves are closer to sine waves than square or sawtooth waves were, but
they've still got a bit of "sharpness" to them because they don't have that
gradual rounding off at the peak like sine waves.

Much like `saw`, we can define `tri` by defining each half of the wave
separately:

```lisp
(defun tri (angle)
  (let ((a (mod angle +tau+)))
    (if (< a +1/2tau+)
      (map-range 0    +1/2tau+
                 -1.0 1.0
                 a)
      (map-range +1/2tau+ +tau+
                 1.0      -1.0
                 a))))
```

That's it for our whirlwind tour of simple sound waves.

[triangle wave]: https://en.wikipedia.org/wiki/Triangle_wave

## Playing Sound

We've got four functions (`sin`, `sqr`, `saw`, and `tri`) that take in angles
and spit out pressure values between -1 and 1, so the next step is to somehow
use them to make the computer play sound.

We'll be using [PortAudio][] and [cl-portaudio][] to handle the OS and sound
device interaction.  If you're following along you'll need to install PortAudio
separately (before Quickloading `cl-portaudio`).  On OS X you can do this with
`brew install portaudio`, for Linux use your distro's package manager.

[PortAudio]: http://www.portaudio.com/
[cl-portaudio]: https://filonenko-mikhail.github.io/cl-portaudio/

### Sampling

In the real world pressure and time vary continuously, but our computer handles
audio differently.  Modern digital audio uses the concept of sampling to split
up the pressure-over-time graph into discrete pieces.  Instead of trying to work
with an infinite number of times, we look at a finite number of individual
samples.

A "sample" is just a pressure value at a particular point in time.  The number
of times per second the computer reads or writes a sample is called the "[sample
rate][]".  If the sampling rate is too low, we won't be able to tell much about
the original wave, and playing it would sound like noise:

[![Graph of a sparse sampling](/media/images/blog/2016/12/chip8-sound-sample-sparse.png)](/media/images/blog/2016/12/chip8-sound-sample-sparse.png)

But a higher sample rate can get us nice and close to the original wave:

[![Graph of a dense sampling](/media/images/blog/2016/12/chip8-sound-sample-dense.png)](/media/images/blog/2016/12/chip8-sound-sample-dense.png)

We'll stick with the most common sample rate, 44.1khz, because it's the most
widely supported (even though it's overkill for our simple waves):

```lisp
(defconstant +sample-rate+ 44100d0)
```

[sample rate]: http://wiki.audacityteam.org/wiki/Sample_Rates

### Buffering

It would be wasteful to keep constantly calling back and forth between our code
and PortAudio's code, so instead we'll be giving PortAudio a buffer of samples
to play which will effectively contain a "chunk" of sound.  This buffer will be
a vanilla Lisp array of `single-float`s.  The size of the buffer is
configurable, with larger buffers representing bigger chunks of sound.

There's a tradeoff between efficiency and responsiveness we
need to decide on.  Larger buffers are more efficient (less switching back and
forth between us and PortAudio) but once we've sent a buffer it's going to play
to its end — we can't stop it midway.  I've found `512` to be a happy medium:

```lisp
(defconstant +audio-buffer-size+ 512
  "The number of samples in the audio buffer.")

(defconstant +audio-buffer-time+ (* +audio-buffer-size+ (/ +sample-rate+))
  "The total time the information in the audio buffer represents, in seconds.")

(defun make-audio-buffer ()
  (make-array +audio-buffer-size+
    :element-type 'single-float
    :initial-element 0.0))
```

A 512-sample buffer with a sample rate of 44100 samples per second means that
each buffer will represent about 11.6 milliseconds of sound.

We're going to need a way to fill an audio buffer with sample values, so let's
make a `fill-buffer` function:

```lisp
(defun fill-buffer (buffer function rate start)
  (iterate
    (for i :index-of-vector buffer)
    (for angle :from start :by rate)
    (setf (aref buffer i) (funcall function angle))
    (finally (return (mod angle +tau+)))))
```

`fill-buffer` will take one of our four waveform functions and fill the given
buffer with samples generated by it.  `rate` will be the rate at which the angle
should be incremented per-sample, which we'll figure out in a moment.

The one snag is that we can't just start from an angle of zero each time we fill
a buffer (unless our buffer size happens to exactly match the period of our
wave).  If we *did* we'd only ever be sending the first chunk of our wave, and
we'd end up with something like:

[![Graph of a shitty buffer filling strategy](/media/images/blog/2016/12/chip8-sound-borked.png)](/media/images/blog/2016/12/chip8-sound-borked.png)

This is obviously not what we want.  The solution is to return the angle we
ended at from `fill-buffer`, and then pass it in as `start` on the next round so
we can pick up where we left off.

### Configuration

Since we've gone to the trouble of writing four separate wave functions, each
with their own character/timbre, let's make the sound the emulator plays
configurable.  First we'll make some helper functions for filling the audio
buffer with a particular wave:

```lisp
(defun fill-square (buffer rate start)
  (fill-buffer buffer #'sqr rate start))

(defun fill-sine (buffer rate start)
  (fill-buffer buffer #'sin rate start))

(defun fill-sawtooth (buffer rate start)
  (fill-buffer buffer #'saw rate start))

(defun fill-triangle (buffer rate start)
  (fill-buffer buffer #'tri rate start))
```

Then we'll add a slot to the `chip` struct:

```lisp
(defstruct chip
  ; ...
  (sound-type :sine :type keyword)
  ; ...
  )
```

And we'll make a helper function for retrieving the appropriate buffer-filling
function:

```lisp
(defun audio-buffer-filler (chip)
  (ecase (chip-sound-type chip)
    (:square #'fill-square)
    (:sine #'fill-sine)
    (:sawtooth #'fill-sawtooth)
    (:triangle #'fill-triangle)))
```

We'll use `ecase` instead of vanilla `case` so we get a nicer error message if
the slot is set to something incorrect.  I actually find myself reaching for
`ecase` more often than `case` these days because a silent `nil` result is
almost never what I want.

### Angle Rate & Frequency

One last bit we need to figure out is how much to increment the angle for each
sample.

All four of our wave functions assume that one wave happens in exactly
τ radians.  So if we assume that we want one wave per second, and there are
`+sample-rate+` samples in every second, we'd just use `(/ +tau+ +sample-rate+)`
to get the angle increment.

But one wave per second is below the range of human hearing.  We want something
more like 440 waves per second (the "frequency" of the note [A440][]), so our
function to find the angle increment will looks like this:

```lisp
(defun audio-rate (frequency)
  (coerce (* (/ +tau+ +sample-rate+) frequency) 'single-float))
```

We coerce it to a `single-float` here to avoid having to do it on every addition
later.

[A440]: https://en.wikipedia.org/wiki/A440_(pitch_standard)

### Running the Sound Loop

We've now got all the bits and pieces we need to make some noise.  Let's build
a `run-sound` function bit by bit.  First we initialize the output stream with
PortAudio:

```lisp
(defun run-sound (chip)
  (portaudio:with-audio
    (portaudio:with-default-audio-stream
        (audio-stream 0 1
                      :sample-format :float
                      :sample-rate +sample-rate+
                      :frames-per-buffer +audio-buffer-size+)
      ; ...
      ))
  nil)
```

The `0 1` arguments mean "zero input channels" (we don't need access to the
microphone!) and "one output channel".

Now we'll add our sound loop:

```lisp
(defun run-sound (chip)
  (portaudio:with-audio
    (portaudio:with-default-audio-stream
        (audio-stream 0 1
                      :sample-format :float
                      :sample-rate +sample-rate+
                      :frames-per-buffer +audio-buffer-size+)
      (with-chip (chip)                              ; NEW
        (iterate (with buffer = (make-audio-buffer)) ; NEW
                 (with angle = 0.0)                  ; NEW
                 (with rate = (audio-rate 440))      ; NEW
                 (while running)                     ; NEW
                 (if (plusp sound-timer)             ; NEW
                   ; ...                             ; NEW
                   (sleep +audio-buffer-time+))))))  ; NEW
  nil)
```

We create a buffer and some extra variables, then we check if the sound timer is
positive.  If *not*, we just sleep for a while.  I decided to sleep for the same
amount of time as a single audio buffer would take so that each iteration of the
loop represents roughly the same slice of time, but this isn't strictly
necessary.

If the sound timer *is* positive we'll need to fill the buffer with pressure
values and ship it off to PortAudio:

```lisp
(defun run-sound (chip)
  (portaudio:with-audio
    (portaudio:with-default-audio-stream
        (audio-stream 0 1
                      :sample-format :float
                      :sample-rate +sample-rate+
                      :frames-per-buffer +audio-buffer-size+)
      (with-chip (chip)
        (iterate (with buffer = (make-audio-buffer))
                 (with angle = 0.0)
                 (with rate = (audio-rate 440))
                 (while running)
                 (if (plusp sound-timer)
                   (progn                                            ; NEW
                     (setf angle (funcall (audio-buffer-filler chip) ; NEW
                                          buffer rate angle))        ; NEW
                     (portaudio:write-stream audio-stream buffer))   ; NEW
                   (sleep +audio-buffer-time+))))))
  nil)
```

Pretty simple: just fill the buffer and ship it.  We keep track of the angle the
buffer-filler returned so we can pass it in on the next iteration to avoid the
"truncated waves" problem we talked about earlier.

### Threading Issues

In a perfect world we could just add one more thread like we did with the others
and be done with it:

```lisp
(defun run (rom-filename)
  (let ((chip (make-chip)))
    (setf *c* chip)
    (load-rom chip rom-filename)
    (bt:make-thread (curry #'run-cpu chip))
    (bt:make-thread (curry #'run-timers chip))
    (bt:make-thread (curry #'run-sound chip))  ; NEW
    (chip8.gui.screen::run-gui chip)))
```

Unfortunately there's one more snag we need to deal with.  It turns out that Qt
becomes very unhappy if we set up our threads this way.  I'm not 100% sure what
the problem is, but it has something to do with control of the main thread on
OS X.

The solution is to let Qt take control of the main thread, and spawn all our
other threads from there.  We'll update `run-gui` to take a thunk and call it
once it's ready:

```lisp
                     ; NEW
(defun run-gui (chip thunk)
  (with-main-window
      (window (make-screen chip))
    (funcall thunk)))            ; NEW
```

And now we can move all the thread spawning into the thunk:

```lisp
(defun run (rom-filename &key start-paused)
  (let ((chip (make-chip)))
    (setf *c* chip)
    (load-rom chip rom-filename)
    (chip8.gui.screen::run-gui chip
      (lambda ()                                       ; NEW
        (bt:make-thread (curry #'run-cpu chip))        ; NEW
        (bt:make-thread (curry #'run-timers chip))     ; NEW
        (bt:make-thread (curry #'run-sound chip))))))  ; NEW
```

Technically only the sound thread needs to be handled this way, but I figured
I'd treat them all the same.

## Result

That's it!  Now you can play games and should get a nice loud buzz when the
sound should fire.  `ufo.rom` is a good game to test it out with — it should
buzz whenever you fire and whenever a ship gets hit.  Turn down your speakers if
you don't want to scare the cat.

The sound type can be changed on the fly (e.g. `(setf (chip-sound-type *c*)
:sawtooth)`), so play around and decide which type is your favorite.  I'm
partial to sawtooth myself.

## Future

With that we've got a full-featured CHIP-8 emulator!  It works, but there's
still work left to be done.  In the next few posts we'll look at things like:

* A menu system for runtime configuration
* Disassembling/debugging infrastructure
* A graphical debugger

*Thanks to [Joe Karl](https://twitter.com/joekarl) for reading a draft of this
post.*