--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/content/blog/2016/12/chip8-sound.markdown Fri Dec 23 12:00:54 2016 -0500
@@ -0,0 +1,665 @@
++++
+title = "CHIP-8 in Common Lisp: Sound"
+snip = "Let's add a buzzer."
+date = 2016-12-30T14:50:00Z
+draft = true
+
++++
+
+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/)
+
+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
+
+[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:
+
+[](/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:
+
+[](/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:
+
+[](/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:
+
+[](/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:
+
+[](/media/images/blog/2016/12/chip8-sound-saw-repeat.png)
+
+A single wave of it looks like this:
+
+[](/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:
+
+[](/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:
+
+[](/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:
+
+[](/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've 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:
+
+[](/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
+
