Showing posts with label Audio. Show all posts
Showing posts with label Audio. Show all posts

Friday, September 2, 2016

Snake Rock 'n' Roll: Sound Effects List

Thus far in the series, we have examined the data and workings of the audio module with respect to the background music. In this post, we will examine its support for the sound effects in the game.

There are forty sound effects in Snake Rattle 'n' Roll. Each sound effect is played by a single APU channel, and while it is playing, any song playing in the background is suppressed: the track data continues to be read, and the state of any active effects are updated, but the song's notes never get written to the APU channel. Although the audio module supports playing a sound effect on any of the APU's four channels, Snake Rattle 'n' Roll only plays sound effects on the pulse and noise channels, never on the triangle channel.

Sound effects, like the tracks of a song, are played from tapes. The format of the tape data for sound effects is much simpler than that for song tracks. A list of the available tapes for sound effects can be located at $DB94:

SFX ID$DB94,X\$DB95,XPurpose
$00FB\DBnone
$02FB\DBBigFoot death/Snake pop/Pibbly bomb
$0410\DCPibbly Chomp
$0619\DCPibbly Ejection
$082D\DCLid Opening
$0A34\DC?? Mystery Sound Effect??
$0C3F\DCPLAY ON/1-UP
$0E65\DCControl inverter pickup
$106E\DCTongue extender pickup
$127B\DCWormhole opening
$149E\DCWormhole sucking up object
$16AE\DCBigFoot stomp/-RGGG THUD
$18BE\DCScale bell ring
$1ADC\DCExploding enemy 1/2
$1CE5\DCExploding enemy 2/2
$1EEE\DCSnake OW
$20F7\DCInvincibility diamond pickup
$220E\DDSnake death spin
$2435\DDPibbly countdown (low)
$2627\DDPibbly countdown (medium)
$2843\DDPibbly countdown (high)
$2AE3\00Score rollup (pulse)
$2C51\DDScore rollup (noise)
$2EC6\DCJaws (slow)
$3063\DDARRRGGG-
$3274\DDPibbly chunk spit
$34B1\03Crescendo (game over screen, extra continue pickup)
$368E\DDExit door point scored
$389E\DDBounce/lick enemy
$3AA3\DDLick foot
$3CBD\DDDiving splash
$3ECF\DDWater jump jet
$40E5\DDTime extension pickup
$42EA\DDTime running out beep
$4454\DCTail fin pickup
$46FB\DDWind-up key pickup
$4806\DE?? Mystery Sound Effect??
$4AF3\DBRocket take-off
$4CE6\DBAsteriod Fall
$4E0D\DESnake gulp
$50D1\DCJaws (fast)

Some observations on this table:

  • The table is two bytes per entry, and lists the low byte\high byte of the address of the start of that sound effect's tape data
  • Sound effect ID $00 is not a real sound effect; it is just a sentinel value in the table.
  • There are two sound effects ($0A and $48) whose purpose is unknown to me. I could not find any action in the game that caused them to play, and when I hacked the ROM to play them in place of other sound effects, I did not recognize them.
  • There are two other sound effects ($2A and $34) whose tape address is in RAM instead of ROM. This means that the sound effect actually played is dynamic, and can differ between runs. Sound effect $34 is particularly interesting, in that the audio module itself contains code to dynamically alter the sound effect's tape data. We shall see this firsthand in a later post, when we examine the machine code of the audio module in depth.

The sound effect list has an unusual layout. In most other cases, the tape address data would have been stored in two lists, say $D000,X and $D028,X, and the sound effect IDs would have been ordered sequentially starting from zero. Instead, the address data has been interleaved into a single table, and the sound effect IDs are incremented by two, starting from zero. It turns out that this is not accidental, because it allows a sound effect to have TWO IDs: the ID listed in the table above, or 'primary' ID, and that ID number plus one, or 'locked' ID. But what use is that?

CAUTION: the next section is a bit esoteric. Read carefully.

The audio module contains code to suppress repeat sound effects. For example, sound effect $24 was currently playing on pulse channel 1, and the game logic issued a call to play sound effect $24, it would be ignored. When the sound effect is finished, the audio module resets itself so that it is 'playing' sound effect $00, and then the game logic could issue a call to play sound effect $24 again.

The same example, mutatis mutandis, applies to any given sound effect ID, in particular, $25, the 'locked' ID for $24. The key here is that if sound effect $24 was playing, it could be overwritten by sound effect $25, and vice versa. This fact comes into play when we look at the SFX UNLOCK message we glossed over in the last post.

At the implementation level, the SFX UNLOCK message will cause the audio module to change its record of the currently-playing sound effect from a 'locked' ID to a 'primary' ID (it has no actual effect if it is executed while the audio module is already playing a sound effect by its primary ID). The sound effect will continue to play normally, but it is now able to be preempted by re-playing the sound effect's locked ID.

Snake Rattle 'n' Roll makes use of this advanced feature in a few places, but the most noticeable is in the 'pibbly countdown' at the end of each stage. While it is counting out the number of nibbly pibblys eaten, there is a sound effect being played repeatedly. When the sound effect gets about halfway through, it is started over, until the end of a countdown, when it plays to completion.

Under the hood, the game is attempting to play sound effect $25 every frame (or, 60 hz). Many of these attempts will be rejected, because the audio module is already playing that sound effect, but halfway through the effect it reaches an SFX UNLOCK message, switches to being recorded as playing sound effect $24, and is overwritten on the next frame.

End esoteric section. That was a bit weird, but it is the only complicated part of sound effects: the SFX UNLOCK message is the only control message available in sound effect tape data. We will examine the rest of the sound effect tape data in the next post.

Wednesday, August 31, 2016

Snake Rock 'n' Roll: Effect Messages

Thus far, we have looked at the control messages and the note/rest messages that appear in a track's tape data. There are still a few messages left before we can fully understand the tape data in its entirety. These messages have to do with the various effects which can be applied to change how a note sounds. To begin, let us review the list of effects available:

  • Sound effect rate-limiting control
  • Direct control of APU channel values
  • Applying vibrato to a note
  • Applying a slide effect to a note, dropping its pitch
  • Applying a crescendo or decrescendo to a note's volume
  • Shifting the pitch of the notes in a song
  • Adjusting the tempo of a song

We will examine the use of the first one in a later post, discussing the sound effect processing in the audio module. For now, suffice it to name the message SFX UNLOCK, and note that it is encoded as a single byte: value $02. Let us now examine the rest of the list in order.

Before we do so, however, there is one other concept which must be introduced. Remember last post, when I said that each channel is on a 30hz 'update' timer (assuming that the tempo hasn't been lowered)? Things get a bit more complicated with the effects, because these typically undergo changes ever frame (60hz), regardless of the tempo value. I will refer to this second frequency as an 'output', to differentiate it from an 'update'.


APU channel values

As can be read on the NES dev APU wiki page, each channel in the APU is controlled by writing to four eight-bit registers. The note messages and various other effects control the timer and volume values of the channel, ajusting its period (and also frequency) and volume, respectively.

The other components of a channel's register values are typically set once, and then not modified afterwards. The sweep controls for the pulse channels ($4001/$4005) are initialized with value $43, effectively disabling the channel's sweep unit (the $4009 and $400D registers also get initialized to this value, but it does not have any effect on the triangle and pulse channels). The 'control' registers ($4000/$4004/$4008/$400C) and the length counter ($4003/$4007/$400B/$400F) are initialized from a list located at $DE44 and $DE45. It is indexed similarly to the tape start address table described earlier:

Track #Track NameChannel$DE44,X
(Initial $4000,X)
$DE45,X
(Initial $4003,X)
0Level 1 Pulse 1 $77$9A
Pulse 2 $76$9A
Triangle$1F$03
Noise $17$28
1Levels 5 and 8 Pulse 1 $789A
Pulse 2 $789A
Triangle$1F38
Noise $5828
2Levels 6, 9 and 10 Pulse 1 $7B$9A
Pulse 2 $7B$9A
Triangle$1F$03
Noise $58$28
3Level 2 Pulse 1 $55$9A
Pulse 2 $55$9A
Triangle$1F$03
Noise $19$28
4Level 3 Pulse 1 $16$9A
Pulse 2 $15$9A
Triangle$1F$03
Noise $17$28
5Levels 4 and7 Pulse 1 $77$9A
Pulse 2 $77$9A
Triangle$1F$01
Noise $15$01
6Time Out Pulse 1 $D7$03
Pulse 2 $D5$03
Triangle$1F$03
Noise $00$00
7Game Over Pulse 1 $97$03
Pulse 2 $97$03
Triangle$1F$03
Noise $00$00
8Main Titles and End Credits Pulse 1 $FB$9A
Pulse 2 $F6$9A
Triangle$1F$03
Noise $17$28

The third register of each channel is devoted to the timer period, and so is modified for each note message. If a track wishes to update the values in any of the other registers, the UPDATE APU message can be issued. It is encoded as four bytes: the value $03, and the byte values to be written to the first, second and fourth channel registers for that track's channel.


Vibrado

By itself, a square or triangle wave is a very plain-sounding instrument. The audio module supports a vibrado effect that gets applied to each note, which will increase or decrease the period of a note at regular intervals. To enable this effect, a tape can encode a START VIBRADO message, which is four bytes long. The first byte is the value $08, the second byte specifies (one less than) the number of distinct periods to use, the third byte specifies (one less than) the period of the vibrado effect (in outputs), and the fourth byte specifies the amount by which to adjust the channel period each time the vibrado period changes.

That description is perhaps a bit opaque, and a few examples would clarify. Let us assume that the initial channel period is 100, and examine what the resulting period would look like under various parameter configurations.

Number of PeriodsVibrado PeriodChannel Period DeltaResultant Output Channel Period
215 100,105,100,105,100,105,…
218 100,108,100,108,100,108,…
225 100,100,105,105,100,100,105,105,…
315 100,105,100,95,100,105,100,95,…
415 100,105,110,105,100,95,100,105,110,105,100,95,…

Note that the base channel period becomes the middle period in the progression.

The songs in Snake Rattle 'n' Roll use very small channel period delta values and typically only use two distinct periods. This gives the notes a bit more texture than a plain pulse channel, but do not fundamentally alter the perceived pitch of the notes.


Pitch Slide

In the main titles for Snake Rattle 'n' Roll, you can hear some notes that have a slide effect applied to them, causing their pitch to lower, similar to the effect that a guitar player would get by playing a note and then sliding towards the headstock of their guitar. This effect is enabled by the PITCH DOWN SLIDE message, which is encoded with a single byte, of value $0B.

A pitch slide message only applies the effect to the single note following it on the tape. At a low level, the pitch slide effect will wait for five outputs after the note starts, and then, every other output, the note's period will be increased by sixteen. The period is increased nine times in total.1


(De)crescendo

The NES APU has built-in hardware allowing it to play a note that has a decrescendo: starting at a high volume, and linearly decreasing the volume to nothing. The (de)crescendo effect is more general than this, as it allows a note to play at its initial volume for a length of time, then to linearly decrease OR increase towards a target volume, and then remain at the newer constant volume.

This effect is started with the DECRESCENDO START message, which is four bytes long. The first byte has value $16, the second byte specifies the delay (in outputs) before the (de)crescendo starts, the third byte specifies the delay (in outputs) between each volume adjustment, and the fourth byte specifies the target volume.

This effect also comes with another message: the DECRESCENDO IGNORE message, which is two bytes long. The first byte is value $0C, and the second byte specifies a volume value. When this message appears in tape data, the next note is played as though the (de)crescendo effect is not enabled, instead playing with the specified constant volume. Subsequent notes continue to use the existing (de)crescendo settings.


Pitch Shift

Many of the songs in Snake Rattle 'n' Roll share a common melody, but at different pitches (the music of levels 6, 9 and 10 being notable in this regard). In order to avoid the necessity of writing out the similar melodies repeatedly with different note values, there are three messages which can be used to adjust the pitch of a note.

The simplest message is the ABSOLUTE PITCH SHIFT message, which is two bytes long. The first byte is the value $12, and the second byte specifies the pitch shift. After encountering this message in tape data, the audio module will play subsequent note messages at a pitch that is the specified amount up or down from the note as it appears in the tape data.

There is also a RELATIVE PITCH SHIFT message. It is encoded with byte value $13, followed by a relative offset. Instead of setting the pitch shift for the audio module, it instead adjusts the current pitch shift up or down by the amount specified.

Lastly, there is a CROSS-CHANNEL PITCH SHIFT message. It is encoded with byte value $14, followed by an absolute pitch shift value. This message operates similarly to the absolute pitch shift message, except that the specified absolute pitch shift value is set for all four tracks, instead of just the track for which it is found. It is one of two such messages that can affect channels other than itself. Speaking of which…


Song Tempo

In the previous post, we saw that the tempo of the song can be controlled from its default value (30 updates/second) by a given ratio of skipped updates. Each song has an initial value specified for its tempo value, but this value can be adjusted during the song playback with the ADJUST TEMPO message. It is two bytes long; the first byte is value $11, and the second byte is an adjustment value.

This message is a bit tricky to make use of: the current tempo value for the song is adjusted up or down by the specified value, not set to the specified value. You will end up with unexpected results unless you are aware of the initial tempo value and know how this instruction will adjust it. Noted above, this message affects the tempo for all four tracks, not just the track being played.


Summary

Rolling up the information above and the previous post yields the following list of messages:

MessageEncoding
END OF TRACK[$00]
 
SFX UNLOCK[$02]
UPDATE APU[$03] [channel 1 value] [channel 2 value] [channel 4 value]
START LOOP (long format)[$04] [loop count] [address low] [address high]
END OF LOOP[$05]
SET LENGTH OVERRIDE[$06] [length]
CLEAR LENGTH OVERRIDE[$07]
START VIBRADO[$08] [step count] [step delay] [period step]
 
 
PITCH DOWN SLIDE[$0B]
DECRESCENDO IGNORE[$0C] [volume]
 
 
 
ADJUST TEMPO[$11] [tempo offset]
ABSOLUTE PITCH SHIFT[$12] [pitch shift]
RELATIVE PITCH SHIFT[$13] [pitch shift offset]
CROSS-CHANNEL PITCH SHIFT[$14] [pitch shift]
 
DECRESCENDO START[$16]
START LOOP (short format)[$17…$7F] [address low] [address high]
REST[$80] [length?]
NOTE[$81…$BC] [length?]

That's odd. We are still missing eight potential messages. The short answer is that it does not matter: the messages listed above make up all of the messages that appear in the tape data for the songs of Snake Rattle 'n' Roll. It doesn't matter what the other messages do, since they never end up actually doing it while you are playing.

If you are like me, however, such an answer is maddening. We will examine what those messages may or may not do at the end of the series, where we dive into the code.


  1. The machine code implementing the pitch slide effect appears to be more general than this description suggests: there is some seemingly unused code that would cause the change in period to vary, instead of being a constant $10, for example.

Friday, August 26, 2016

Snake Rock 'n' Roll: Note messages and control messages

At this point, we know where on the cartridge the tapes for Snake Rattle 'n' Roll songs are located. Let us look now at the format of this data. At a high level, a track's tape is a list of messages, terminating with an END OF TRACK message, which is encoded with a single byte of value $00.

A simple song would just be a list of NOTE messages and REST messages. Note messages are encoded starting with a byte in the range [$81, $BC]. The byte $81 corresponds to pitch C2, increasing up to byte $BC, which is the pitch B6 (giving a five octave range). Rest messages are encoded starting with byte value $80.

Both note and rest messages are usually followed by an additional byte, giving the length of the note or rest in terms of 'updates' (I say 'usually' here because there is an exception, noted below). The audio module is temporally synchronized with the frame rate of the NES, 60 Hz1. In each frame, only two of the four channels are updated: the pulse channels are updated on even numbered frames, while the triangle and noise channels are updated on odd numbered frames. This means that a note or rest whose length is given as $1E (30) would usually play for an entire second. (Again, I say 'usually' because there is another exception, noted belower.)

The first exception listed above concerns the encoding of a note or rest message. In a song, it is not uncommon to have a long run of notes or rests which share a common length. In these cases, it would be wasteful to encode each note with two bytes for its pitch and length. The audio module has a SET LENGTH OVERRIDE message for this use case. The set length override message is encoded with two bytes: the first has value $06, and the second byte specifies the shared length of the following notes. While the length override is set, the audio module will use its value whenever it encounters a note or rest message, instead of attempting to read a second byte to get the length. The length override can be cleared by a set note length override message specifying a length of zero. For convenience, there is also a CLEAR LENGTH OVERRIDE message, encoded with byte value $07, which does the same thing but does not require a second byte.

In addition to the note length override, there is a second compression technique available for tape data. It is common in NES-era music to have repeated sections of music. The tape data format has a control message, START LOOP, which instructs the audio module to play another section of the tape one or more times. This loop section is terminated by the STOP LOOP control message, encoded with byte $05.

There are actually two different ways that the START LOOP message can be encoded. The long format is four bytes: byte value $04, the number of loop iterations, the low address byte, and the high address byte of the start of the loop section. The short format is three bytes: a byte value in the range [$17, $7F], the low address byte and the high address byte of the start of the loop section. In the short format, the number of loop iterations is the value of the initial byte, minus $16.2

Loops are very common in the Snake Rattle 'n' Roll songs. Most of the track tapes are little more than a dozen or so loop messages. One cautionary note to developers, though: you are doubtlessly used to being able to nest subroutine calls to an arbitrary depth. The audio module does not support this. It has exactly one nesting level, and for a given update call it is either playing the 'main' section of the music or a 'loop' section. You cannot call a loop within a loop. Aside from this, any message that is valid in the main section of a tape is valid in a loop section of a tape.

The second exception listed above concerns the tempo of a song. The normal mode in the audio module for a track is thirty updates per second, but it is also possible for a song to specify a lower update rate by skipping occasional updates. The details of how the audio module decides which updates to skip will wait until we dive into the source code, but for know, it is enough to know that you can specify a number x in the range [$0, $7F] and for every $80 update calls, only x are actually performed. The skipped updates are evenly spaced among the $80 update calls; at least, as evenly as they can be up to the precision of integer division. In Snake Rattle 'n' Roll, only two tempo values are used, besides maximum tempo of $80: $68, which keeps 81.25% of updates, and $6A, which keeps 82.8125% of updates. These tempos are stored in a list at address $D621, according to the following table:

Song #Song Name$D621Tempo
0Level 1 $80Full
1Levels 5 and 8 $6881.25%
2Levels 6, 9 and 10 $6A82.8125%
3Level 2 $6A82.8125%
4Level 3 $83Full
5Levels 4 and 7 $6A82.8125%
6Time Out $80Full
7Game Over $80Full
8Main Titles and End Credits$80Full

This strategy for slowing down the tempo of the song is a bit strange at first glance: at random, some of the notes with a given length may be stretched to be one note longer, because one of their update calls were switched. However, because the maximum update rate is 30 Hz, you don't actually notice that notes which should share a common length are not the same length. The effect is also less pronounced because the skipped updates are at uneven intervals.

To summarize: we now recognize the following messages encoded in a tape data stream:

MessageEncoding
END OF TRACK[$00]
START LOOP (long format)[$04] [loop count] [address low] [address high]
END OF LOOP[$05]
SET LENGTH OVERRIDE[$06] [length]
CLEAR LENGTH OVERRIDE[$07]
START LOOP (short format)[$17,$7F] [address low] [address high]
REST[$80] [length?]
NOTE[$81,$BC] [length?]

There are no messages with an initial byte above $BC; these would be interpreted by the audio moduel as a note message, but it would overrun the list on the cartridge containing the pitch periods and would play with seemingly random pitches. That just leaves eighteen other messages, starting with bytes in the range [$01,$16]. We will examine these messages in the next post.

  1. Technically, it is actually 60.1 Hz, but what's a tenth of a Hertz between friends?
  2. I am not actually sure why there were two encodings for the start loop message. I suspect that the long form was invented first, and that the short form was added later when the developers had to squeeze a few more bytes of space out of the cartridge. This makes me wonder why they didn't just remove the long format (and its machine instructions) entirely. There is one song still in Snake Rattle 'n' Roll that uses the long format, looping $50 times. This is still within the loop count that the short format can encode.

Wednesday, August 24, 2016

Snake Rock 'n' Roll: The Location of the Tapes

You see something very odd when you look at the character ROM (CHR ROM) for Snake Rattle 'n' Roll:

CHR Pages 0 & 1 CHR pages 2 & 3 CHR pages 4 & 5 CHR pages 6 & 7

In these images, the upper half corresponds to the first page number listed, and the bottom half to the second page number listed.

In these renderings, you can see areas that look like corrupted data, or static. Pages two and six are the most noticeable, being entirely 'snow', but every page except for page zero contains at least some snow. What is going on here? Anyone who has played the game knows that this visual corruption never actually appears while playing, so something else must be going on.

At the risk of spoilers, it has to do with the audio module. I am pretty sure that you figured that out from the theme of this blog series; I just wanted to eliminate all doubt.

In the PRG ROM, starting at address $9505, is a nine-element list which will be of some interest to us:

Song #Song Name$9505
0Level 1 $02
1Levels 5 and 8 $02
2Levels 6, 9 and 10 $06
3Level 2 $02
4Level 3 $02
5Levels 4 and 7 $02
6Time Out $03
7Game Over $03
8Main Titles and End Credits$06

This table suggests that the tape data specifying the background music is actually stored in character ROM, not program ROM. Now, knowing the page number is nice, but which of the 4096 bytes in a page is the start of the tape? Another list (actually, two) comes to the rescue. These lists are each 36 (9x4) entries long. They start at $DE42 and $DE43, and you must increment your table index by four to get each successive element:

Song #Song NamePulse 1Pulse 2TriangleNoise
$DE42$DE43$DE46$DE47$DE4A$DE4B$DE4E$DE4F
0Level 1 $00$00 $01$07 $02$30 $02$BF
1Levels 5 and 8 $0C$8D $0C$FC $0E$44 $0E$B6
2Levels 6, 9 and 10 $00$00 $00$D9 $01$4D $01$82
3Level 2 $03$2B $03$FD $04$D8 $05$62
4Level 3 $05$98 $06$D0 $07$D0 $08$7F
5Levels 4 and 7 $08$CB $0A$43 $0B$63 $0C$26
6Time Out $01$F0 $02$11 $02$32 $02$45
7Game Over $02$46 $02$63 $02$80 $02$45
8Main Titles and End Credits $03$96 $04$DB $06$14 $06$60

This table provides the address on the corresponding table where the tape data for each track begins. Note that the list data is stored at $DE42 + $10 * SongNumber + TrackNumber, and likewise for the $DE43 list.

We now know that if we wanted to examine the tape data for the audio for the pulse 2 channel on level 3, we should start looking at $06D0 on CHR ROM page 2. In the next post, we will examine the file format of the tape data.

Monday, August 22, 2016

Snake Rock 'n' Roll: Introduction

As I have mentioned previously on this blog, one of my most favourite games of all time is the 1989 classic Snake Rattle 'n' Roll, brought to us by a very young Rare. I fondly remember playing it as a child, and thinking to myself, "Wow, video games are awesome. When I grow up, I am going to make video games for a living." This was a far more pragmatic choice than the average eight-year-old, who imagines being an astronaut, or a cowboy, or a dinosaur when they grow up.

Nowadays, twenty-seven years later, I still say the same thing: when I grow up, I fully intend to make video games for a living. In the meantime, I study the works of the Old Masters carefully, to see how they worked within the limitations of their time, and I find their works fascinating. Regular readers of this blog have already seen the results of this study in the Tileset series I wrote at the inception of this blog. This post marks the first in a series exploring the gritty details, nuts and bolts of the audio module for Snake Rattle 'n' Roll.

Producing this series required many hours of poring over documentation to gain skills that are practically lost to developers today. The excellent 6500 Programming Manual is the go-to source for the NMOS 6502 microprocessor. Knowledge of 6502 assembly programming (or, more specifically, 6502 disassembly) was instrumental in understanding the Snake Rattle 'n' Roll cartridge, as the NES uses a modified 6502 microprocesor: the 2A03 microprocessor manufactured by Ricoh. The wiki at NES DEV was likewise indispensable for its details on the NES architecture, filling in the gaps left behind once the assembly code was understood. For tools, I cannot recommend Nintendulator highly enough: it is by far the most accurate NES emulator available today, and its debugging capabilities were invaluable in producing this document.

This series will not go into the details of how I reverse-engineered the audio module. I thought about including information on my techniques, but opted against it on the grounds that it would make the series much less accessible to the lay reader. If you are sufficiently inclined, you can take the linked resources above and a copy of the Snake Rattle 'n' Roll ROM dump (or another game of your choice), and start working backwards with liberal use of breakpoints in Nintendulator. If you do decide to embark on this path, drop me a line and let me know what you find. I would be keenly interested to know if other games have a similar audio module; I have an untested theory that NES development kits (if they even existed) may have included a boilerplate audio module that developers could leverage, similar to (but much more simpler than) the audio modules in today's consoles.

Let us begin the series, then, by heeding the advice from the novel Dune to "take the most delicate care that the balances are correct", and define some terminology for use in later installments of this series. Snake Rattle 'n' Roll has nine 'songs': the audio you hear in the background while you are playing, according to the following list:

Song NumberSong Name
0Level 1
1Levels 5 and 8
2Levels 6, 9 and 10
3Level 2
4Level 3
5Levels 4 and 7
6Time Out
7Game Over
8Main Titles and End Credits

Each song is composed of four 'tracks', and each track provides the data for one of the four audio channels present in the NES Audio Processing Unit (APU), according to the following list:

Track NumberAPU Channel
$0Pulse 1
$4Pulse 2
$8Triangle
$CNoise

Throughout this series, I will adopt the 6502 convention of writing hexadecimal numbers with a leading dollar sign, as in $DEADBEEF, as opposed to the more modern convention of using '0x', as in 0xCAFEBABE. It may seem odd that I have numbered the song tracks incrementing by four instead of by one; my reasoning will become apparent in later posts.

To continue the cassette metaphor, the data for each track are stored in a 'tape'. A tape consists of a sequence of 'messages'. Some of these are 'control messages', which alter how the audio module interprets the bytes in the tape. Some of these are 'effect messages', which alter how a given note will be played by the APU channel. Most of these are 'note messages', which tell the audio module to emit a note to the APU channel. A large portion of the audio module handles reading of tape bytes, interpreting the messages, and processing them.

The audio module supports many 'effects', as controlled by effect messages. These are:

  • Sound effect rate-limiting control
  • Direct control of APU channel values
  • Applying vibrato to a note
  • Applying a slide effect to a note, dropping its pitch
  • Applying a crescendo or decrescendo to a note's volume
  • Shifting the pitch of the notes in a song
  • Adjusting the tempo of a song

The APU channels do double-duty, playing both the background music and sound effects while the game is being played. You can observe this while playing, noting that while a sound effect is being played, parts of the background music are not heard. This is not unique to Snake Rattle 'n' Roll: most NES games had the same limitation, although there were a few that included additional audio processors in the cartridge itself to produce richer audio than the basic system provided. The audio module for Snake Rattle 'n' Roll supports playing sound effects over the background music, while remembering where in the music it is so that it can continue playing the song once the effect ends.

In the next post in the series, we will find where on the cartridge the track tapes are located.

Tuesday, April 7, 2015

The Sound of Noise

There has been enough theory in this blog of late. Time to make it concrete.

What do the numbers 31 and 32767 have in common? The former is equal to 25 - 1. The latter is equal to 215 - 1, or equivalently (and tellingly), 25 * 3 - 1.

Why does this relationship have anything to do with the cryptic picture from two posts back?

Consider the relationship between this image and another lightpost. This one has only five lights, and is connected to produce its next light from the fifth and third lights:

If you investigate this shorter lightpost, you will find that has two cycles: the trivial cycle, with every light off, and one other, which covers the other 31 possible light patterns. You will also find that this single, 31-length cycle matches the 'seed' cycle we found in the last post.

Here, then, we have our answer: the lightpost we have been studying has behaviour that resembles the behaviour of three shorter lightposts, which have been interleaved together. We got a bunch of different cycles in the larger lightpost, depending on how the three smaller 'internal' lightposts were initially configured, which explains why the hot bits go a long way in classifying the various cycles.

Why did this structure arise in this case, but our initial lightpost did not? (Recall that the original produced a single, 32767-length cycle, with no apparent substructure.) The answer is in which lights were used to determine the next light's state: in the latter case, the output light and the input lights were all multiples of three apart. This meant that changing a single light's initial configuration could only affect a third of the lights in a cycle. Thus we find that there are three lightposts, leading largely independent lives. In contrast, the first lightpost we encountered was not separable in this manner.

I probably won't go into any more depth about the cycles and structure of lightposts, but I will say that I have only scratched the surface of their behaviour. Consider how many different lightpost families there are. We only looked at lightposts where two of the lights controlled the next light, but since the operation is exclusive or, we could 'tap' as many as we wanted. This means that each lightpost with N lights can produce 2N - 1 possible configurations of cycles (we exclude the case where none of the lights are tapped). The simplest structure between each family to find is that each configuration of taps has a 'twin' configuration that produces the same number and length of cycles, but reverses the lights in each. (It is pretty easy to see why: remember that the predecessor and successor of each lightpost is deterministic, so we expect and can find that each tap configuration will have a 'twin' tap configuration that will swap the predecessor and successor operation).

Now, at last: what does this have to do with NES audio? To answer this, I will at last reveal that our various lighposts are examples of what electrical engineers call Linear Feedback Shift Registers: that is, they are shift registers, where the feedback value shifted in to the empty place at each shift is not a constant 0 or 1, but some linear combination of the pre-shifted state. Unsurprisingly, the NES audio processing unit contains an LFSR, which it uses for its 'noise' channel, and equally unsurprisingly, it is 15 bits long, and has two modes: one where bits 14 and 15 are tapped, and another where bits 9 and 15 are tapped. Now you understand my particular interest in these two tap configurations.

The NES APU's noise channel uses bit 15 of this LFSR as an output signal to your television. When it is set up to feedback according to bits 14 and 15, the signal that it outputs is 32767 units long. This 'wavelength' is so long that humans don't perceive any tone in it, and instead it sounds like static. If you instead set it up to feedback on bits 9 and 15, the signal is only 93 units long, and the human ear can distinguish a definite tone in the output. You can get subtly different timbres depending on whether your particular cycle has 16, 32 or 48 'on' bits: sixteen bits gives a metallic buzz, while 48 bits is a bit more mellow. The tone gets much higher if in addition to tapping bits 9 and 15, you also seed the LFSR with a bit pattern which forces it to the length-31 cycle. This outputs a harsh metallic buzz.

You can hear samples of all five different modes in the WAV files in this zip file.

It was not common to have the noise channel outputting long samples like this. Instead, it was played in very short bursts, and was used to approximate percussive instruments. My favourite example of a slick 'drum' beat can be heard in Wood Man's theme from Mega Man 2.

That is the story of how a seemingly useless thought experiment can have a very practical application. Tune in again when we look at the other audio channels available in the NES, and of the challenges of duplicating the characteristic sound on more modern hardware.


The audio samples attached to this story were created by simulating a linear feedback shift register in software. The source code for that simulation can be seen below:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

/// <summary>
/// Represents a shift register whose feedback is a linear function (XOR) of a subset of the bits
/// in its current value, referred to as the tap bits.
/// </summary>
public class LinearFeedbackShiftRegister
{
    #region Member variables

    int[] taps;
    int highBit;
    ulong registerValue;

    #endregion


    #region Properties

    /// <summary>
    /// Gets or sets the current value of the shift register.
    /// </summary>
    public ulong RegisterValue
    {
        get
        {
            return registerValue;
        }
        set
        {
            if (value == 0)
                throw new ArgumentOutOfRangeException("value", "RegisterValue cannot be set to zero.");

            // --- If the 63rd bit is the high bit, then any
            // --- input is valid. Otherwise, check that the input
            // --- doesn't set any bits beyond the register size

            if (highBit < 63 && (value >> (highBit + 1)) > 0)
                throw new ArgumentOutOfRangeException("value", "Input value is larger than the shift register");

            registerValue = value;
        }
    }

    #endregion


    #region Constructors

    /// <summary>
    /// Initializes a new instance of the LinearFeedbackShiftRegister class.
    /// </summary>
    /// <param name="numBits">The size, in bits, of the shift register.</param>
    /// <param name="tappedBits">A binary value where a bit value of 1 means that the corresponding bit of the register will be tapped.</param>
    public LinearFeedbackShiftRegister(int numBits, ulong tappedBits)
        : this(numBits, TapsFromBits(tappedBits))
    {
    }

    static int[] TapsFromBits(ulong taps)
    {
        return Enumerable.Range(0, 64).Where(i => (taps & (1ul << i)) == (1ul << i)).ToArray();
    }


    /// <summary>
    /// Initializes a new instance of the LinearFeedbackShiftRegister class.
    /// </summary>
    /// <param name="numBits">The size, in bits, of the shift register.</param>
    /// <param name="tappedBits">An array of integers specifying which bits of the register will be tapped.</param>
    public LinearFeedbackShiftRegister(int numBits, int[] tappedBits)
    {
        if (numBits < 2 || numBits > 64)
            throw new ArgumentOutOfRangeException("numBits", "NumBits must be between 2 and 64 inclusive.");
        if (tappedBits == null)
            throw new ArgumentNullException("tappedBits");
        if (tappedBits.Length == 0)
            throw new ArgumentException("No taps specified.", "tappedBits");
        if (tappedBits.Length != tappedBits.Distinct().Count())
            throw new ArgumentException("Duplicate taps specified.", "tappedBits");
        foreach (var tappedBit in tappedBits)
            if (tappedBit < 0 || tappedBit >= numBits)
                throw new ArgumentOutOfRangeException("tappedBits", string.Format("{0} is not between 0 and {1} inclusive.", tappedBit, numBits - 1));

        taps = tappedBits.ToArray(); // Make a copy so caller can't modify the array from underneath us
        highBit = numBits - 1;
        registerValue = 1;
    }

    #endregion


    #region Instance methods

    /// <summary>
    /// Advances the shift register to its next state.
    /// </summary>
    public void Shift()
    {
        if (CurrentRegisterValueProducesFeedback)
            registerValue = (registerValue >> 1) | (1ul << (highBit));
        else
            registerValue = (registerValue >> 1);
    }

    bool CurrentRegisterValueProducesFeedback
    {
        get { return (taps.Where(tap => IsRegisterBitSet(tap)).Count() & 1) == 1; }
    }

    bool IsRegisterBitSet(int index)
    {
        var mask = 1ul << index;
        return ((registerValue & mask) == mask);
    }

    /// <summary>
    /// Determines how many times the shift register can be shifted before it returns to its current value.
    /// </summary>
    public ulong GetCycleLength()
    {
        var result = 0ul;
        IterateCycle(val => result++);
        return result;
    }

    /// <summary>
    /// Computes the bit pattern that is produced by one iteration of the current cycle.
    /// </summary>
    public string GetCyclePattern()
    {
        var result = new StringBuilder();
        IterateCycle(val => result.Append((val & 1ul) == 1ul ? '1' : '0'));
        return result.ToString();
    }

    /// <summary>
    /// Determines the state in the current cycle of the shift register with the smallest binary value.
    /// </summary>
    public ulong GetSmallestValueInCycle()
    {
        var result = ulong.MaxValue;
        IterateCycle(val => result = Math.Min(result, val));
        return result;
    }

    /// <summary>
    /// Computes the shift register values possible in the current cycle.
    /// </summary>
    public List<ulong> GetCycleValues()
    {
        var result = new List<ulong>();
        IterateCycle(val => result.Add(val));
        return result;
    }

    /// <summary>
    /// Iterate through the shift register values in the current cycle and pass them to the input callback.
    /// </summary>
    /// <param name="callback">The callback to invoke on each shift register value.</param>
    public void IterateCycle(Action<ulong> callback)
    {
        var startingValue = registerValue;

        do
        {
            callback(registerValue);
            Shift();
        }
        while (registerValue != startingValue);
    }

    #endregion
}

Wednesday, April 1, 2015

Nonagintricycles

The story so far: we want to figure out how many unique length-31 cycles and length-93 cycles there are in our second lightpost.

I'll be honest. I didn't know. One of the biggest boons to mathematics has been the advent of the computer, for it allows us to experiment with some mathematical concept, in small to medium sizes. Looking at the small cases might be enough to give us insight if we scale up.

With that in mind, I decided just to enumerate through all the cycles, and then try to explain what I see after the fact. Here they all are:

Each row represents a unique cycle. The red lights are 'on', and the gray lights are 'off'. If you were to take fifteen consecutive lights in one row, and set up the original lightpost to that configuration, then pressing the button would cause the lights to shift once along the cycle.

It is important to note that each row is in fact a cycle: it loops around on itself. This picture would more accurately depict the state of things if it were printed out and wrapped around a cylinder. For our purposes, we need only be aware that if you shifted each pattern once in a direction, and filled in the vacant spot with the value that was 'off the end', you would come up with a different representation of the same cycle. You would not have a new cycle.

What is the answer to the question, then? If you look very carefully, you will find exactly one cycle that is 31 units long; all 352 others are 93 units long. I deliberately hid it by repeating it three times. It is the second-to-last:

Is there a pattern in this data? Maybe. It seems like there is some regular shapes in it, but that may be more a trick of how they are sorted than of any fundamental concept. (For reference, these cycles are ordered by the smallest binary value in the cycle.) Is there perhaps a more 'natural' ordering or grouping that might give us more insight? To begin, I started by counting the number of 'on' lights in each cycle. Doing so, I found three groups: one cycle had 16 lights on; 31 cycles had 32 lights on, and the rest (321) had 48 lights on. This immediately suggested a pattern, for two reasons: multiples of 16 in the number of lights on, and the size of the second group being 31, a number that keeps popping up.

So I took a look at the cycle with 16 lights on:

And at the cycles with 32 lights on:

The first row of the 32-light cycles bears a strong resemblance to the 16-light cycle, and as I looked, the other 32-light cycles seemed to as well. To see the resemblance more clearly, I decided on an arbitrary pattern: five lights, all on, each separated by two other lights, whose state was not important. I then tagged my cycles by highlighting what I call the 'hot bits':


ALL of the 32-light cycles have TWO hot bits. Believing myself to be on the right track, I then rotated each cycle so that one of the two hot bits was in the rightmost position:

Now we're getting somewhere. All of the cycles are identical in 16 columns: the on lights. But a stronger statement is also true, though not as easy to spot: they are also identical in 15 other columns, where they are all off. Sixteen plus fifteen is 31, hmm.

I chose which hot bit to put in the rightmost position arbitrarily. Therefore, my next step was to try choosing the hot bit to align so that the other hot bit had a position that was a multiple of three from the right side:

All of these cycles are now identical in sixty-two columns, or 31 * 2. I did one last operation, to swap the cycles vertically so that they were ordered by their second hot bit:

I daresay we've found a pattern.

We have observed that the number 31 appears over and over as we investigate this lightpost's cycles. An amazing thing happens if we take these cycles, and take from them every third bit. Each cycle will yield three sub-patterns, each 31 units long:

It has become abundantly clear that there is a seed cycle that is growing these patterns:

Finally, the $64,000 question: is this cycle the same as the lightpost's single length-31 cycle?

Damn. Try as you might, you won't be able to rotate one of these two cycles to align with the other. However, they are strongly similar in one sense: if you count the number of runs of lights in the 'on' state, and how many times such a run appears, they match perfectly; the same is true of the runs of lights in the 'off' state. Their only difference is the order of those runs.

Guided by the insights gleaned above, I performed a similar ordering of the remaining 320 cycles containing 48 lights, plus the length-31 cycle. I was not at all surprised to discover that all of these patterns, possessing 48 lights on, each had three hot bits, and that the length-31 cycle has only one hot bit:



This result is a perfect example of why I enjoy recreational mathematics. You will recall that this discussion started with a seemingly-random lightpost, with a button that caused its light pattern to change according to a very simple rule. Despite its simplicity, it actually gives rise to some very rich structure and patterns that have quite pleasing symmetry. Note also a very non-obvious property that is nevertheless guaranteed by how I constructed these images: EVERY fifteen-bit, non-zero can be found in these three images exactly ONCE, if you remember to allow for the number to start at the left and then wrap around and finish at the right.

Join us next time when I explain the origin of the mysterious seed cycle (assuming you haven't already figured out where it comes from), and answer the question that's burning a hole in your brain: just how could any of this have the slightest bearing whatsoever on how the NES and SNES produce audio?

Monday, March 30, 2015

Disproving the Proof

Last time, we 'proved' that the 15-9 lightpost has cycles of length 93, but I ended the post claiming that result is impossible. Why?

In the first post in this series, we observed that the lightpost is deterministic: from a given starting pattern, we can unambiguously determine the next pattern, and the next, and the next, and on and on, until we eventually return to the original pattern, which we always eventually do, because they come in cycles. This determinism property means that no two unique cycles share a common light pattern: if they did, then we could deterministically derive the rest of the pattern, and we would find that they had to the be same cycle, violating our original assumption that they were unique.

We can now explain why our cycles cannot be length 93. The lightpost has fifteen lights, for a total of 32768 different patterns. One of these patterns, the one with all ligths off, stands in its own lonely cycle of length 1, leaving 32767 other patterns unaccounted for. Each of the remaining patterns must appear in exactly one cycle. If all of the remaining cycles were length 93, then 32767 must be divisible by 93. It is not.

We must therefore have non-93 length cycles. Where is the error in our last proof, then? There isn't one. How can we reconcile these two facts?

The error turns out to be in our conclusion from the algebra: that each cycle was length 93. What we actually demonstrated was something subtly different: that each cycle repeats after 93 steps.

The difference is best explained by a story. Imagine that there is a racetrack, and it just so happens that the length of my stride is such that it takes me exactly 100 steps to run around this track. Now, imagine that there is also a freakishly tall, 12-foot man, standing next to me. His legs are twice as long, making his stride length twice as long, so he only takes 50 steps to run around the track. Here, however, is the key: after 100 steps, he is ALSO back at the starting line. The only difference between me and him is that he has gone through two cycles, whereas I have only gone through one.

All that we have proven, then, is that the cycles in the 15-9 lightpost repeat after 93 steps. The number 93 can be decomposed into prime factors 3 * 31. Therefore, the cycles of this lightpost can be 93, 31, 3, or 1 patterns long. (The '1' case is important, because we already know that the pattern with all lights off is part of a cycle with only one pattern).

We also know that the sum of the lengths of all of the cycles must be 32768. We can therefore state that 32768 = N1 + 3 * N3 + 31 * N31 + 93 * N93, for some constants N1, N3, N31 and N93 giving the number of cycles Nx with length x.

It is not too difficult to show that N1 = 1. There are only two possible light patterns that could repeat themselves: representing a light being 'on' with a 1, and a light being 'off' with a 0, these two patterns are '000000000000000' and '111111111111111'. Of these, only the former actually repeats itself; the latter turns into '011111111111111' after the button is pressed.

It is also not too difficult to show that N3 = 0. There are only eight possible light patterns that could repeat themselves after three steps: if we declare three state variables a, b and c, then these light patterns are of the form 'abcabcabcabcabc'. Note that the case where a = b = c = 0 has already been covered above, so we will restrict our attention to the seven remaining cases where at least one of a, b, and c is equal to 1. If we start with a pattern of this form, after we push the button three times, the pattern will be transformed into '000abcabcabcabc'. This is only equal to the original pattern if a = b = c = 0, which we just said we weren't going to consider.

Knowing these two facts, we can conclude that 32767 = 31 * N31 + 93 * N93, or, equivalently, that 1057 = N31 + 3 * N93. Math buffs will immediately recognize this as a Diophantine equation, first studied by the Greek mathematician Diophantus around the middle of the the 3rd century. They can tell you that the equation has possible solutions; specifically, 353 diifferent possible solutions. They can even parameterize them for you: for an integer parameter T in the range [0, 352], N31 = 1057 - 3 * T, and N93 = 3 * T.

This is all well and good, but we aren't looking for the solutions to a Diophantine equation, we are looking to characterize the cycle lengths of our lightpost. Only one of the 353 possible solutions is the correct one. The math buffs shrug their shoulders and move on, leaving us to ponder alone. Diophantus had nothing to say on the subject of lightposts, as he preceded the lightbulb by sixteen centuries.

Your question for next time: which of the 353 possible solutions for N31 and N93 is correct? A few hints follow:

  • What do the numbers 31 and 32767 have in common?

Wednesday, March 25, 2015

Ring around the Rosie

The story so far: we have a lightpost, with fifteen lights, and the input light is the exclusive or of the fifteenth and ninth light. What is the cycle length?

In order to find the answer, we will first observe that we can map our lightpost, and the successive states, not as fifteen disjoint lights, but as a sliding window overtop of a single pattern of lights:

Under this mapping, each pattern of lights contributes a single light to the larger sequence, and conversely, each set of fifteen contiguous lights forms a single, unique pattern.

Having made this observation, we can represent the rule that produces a new pattern from an existing one as follows. If we assign each light in the sequence a number starting from some arbitrary starting light, and we represent Lx as the state of light N, then we have that Lx = Lx-9 ⊕ Lx-15. Here, ⊕ represents the 'exclusive or' operation.

We can go further, and apply this definition recursively. That is, Lx-9 = Lx-18 ⊕ Lx-24, so Lx = Lx-15 ⊕ Lx-18 ⊕ Lx-24. We also have Lx-15 = Lx-24 ⊕ Lx-30, and so learn that Lx = Lx-18 ⊕ Lx-24 ⊕ Lx-24 ⊕ Lx-30.

This is where things start to get interesting. The exclusive or operation has two identities that will be key to our proof: for a variable X, it is the case that X ⊕ X = False, and X ⊕ False = X. In our derivation above, Lx-24 appears twice. We can apply these two identities to conclude that Lx = Lx-18 ⊕ Lx-30.

Let's see what happens if we turn the crank of this algebraic jack-in-the-box:

Lx = Lx-9 ⊕ Lx-15
Lx = Lx-15 ⊕ Lx-18 ⊕ Lx-24
Lx = Lx-18 ⊕ Lx-24 ⊕ Lx-24 ⊕ Lx-30
Lx = Lx-18 ⊕ Lx-30
Lx = Lx-27 ⊕ Lx-30 ⊕ Lx-33
Lx = Lx-30 ⊕ Lx-33 ⊕ Lx-36 ⊕ Lx-42
Lx = Lx-33 ⊕ Lx-36 ⊕ Lx-39 ⊕ Lx-42 ⊕ Lx-45
Lx = Lx-36 ⊕ Lx-39 ⊕ Lx-42 ⊕ Lx-42 ⊕ Lx-45 ⊕ Lx-48
Lx = Lx-36 ⊕ Lx-39 ⊕ Lx-45 ⊕ Lx-48
Lx = Lx-39 ⊕ Lx-45 ⊕ Lx-45 ⊕ Lx-48 ⊕ Lx-51
Lx = Lx-39 ⊕ Lx-48 ⊕ Lx-51
Lx = Lx-48 ⊕ Lx-48 ⊕ Lx-51 ⊕ Lx-54
Lx = Lx-51 ⊕ Lx-54
Lx = Lx-54 ⊕ Lx-60 ⊕ Lx-66
Lx = Lx-60 ⊕ Lx-63 ⊕ Lx-66 ⊕ Lx-69
Lx = Lx-63 ⊕ Lx-66 ⊕ Lx-69 ⊕ Lx-69 ⊕ Lx-75
Lx = Lx-63 ⊕ Lx-66 ⊕ Lx-75
Lx = Lx-66 ⊕ Lx-72 ⊕ Lx-75 ⊕ Lx-78
Lx = Lx-72 ⊕ Lx-75 ⊕ Lx-75 ⊕ Lx-78 ⊕ Lx-81
Lx = Lx-72 ⊕ Lx-78 ⊕ Lx-81
Lx = Lx-78 ⊕ Lx-81 ⊕ Lx-81 ⊕ Lx-87
Lx = Lx-78 ⊕ Lx-87
Lx = Lx-87 ⊕ Lx-87 ⊕ Lx-93
Lx = Lx-93

The jack has popped! This demonstrates that for each cycle in our lightpost, each light is the same as the light 93 indices prior. From this we conclude that the length of each cycle in the lightpost is 93. There is only one problem with this result: it is impossible, and therefore wrong. Your questions for next time:

  • Why it is impossibe for every cycle of this lightpost to be 93 sequences in length?
  • Why does this impossibility not pose a problem for the proof that we have just derived?

Wednesday, March 18, 2015

Lightpost Characteristics

I hope you have given some thought to the questions posed in the previous post. If not, give that a read and a think before coming back.

What can we say about the patterns of lights that show up on the signpost? Let us start simple. There are 15 lights, and each can be either on or off. This means that there are at most 215 = 32768 possible patterns. The fact that this is a finite number means that we can conclude that repeatedly pusing the button will eventually cause us to repeat a pattern that has previously appeared.

What sort of linked structure do these patterns present? For example, if there were only eight states, there are several different possible linking structures. Here is an example of three:

We can exclude a link structure that has 'spokes', like the first example. We do this by observing that each pattern has a unique 'successor' pattern. What abot predecessor? It turns out that each pattern also has a unique 'predecessor' pattern: you get this by shifting all the lights left, instead of right, and setting the rightmost light to be the exclusive or of the leftmost and rightmost light in the previous pattern:

The uniqueness of the predecessor and successor means that the patterns of lights must form simple loops, with no other, more complex shapes. This is because, on a link graph like the ones above, there must be exactly one arrow going into and exactly one arrow going out of each node.

How many loops are there? How many different patterns are in each loop? (We call this number of patterns the 'cycle length' of a loop). There is an easy loop to characterize. If all of the lights are initially off, then the predecessor and successor patterns are both equal to the initial pattern. Therefore there is one loop, with cycle length one.

We will thus restrict our attention to patterns with at least one light on. How many loops do they form, and what is the cycle length of each? Interestingly, there is only one other loop, containing every other pattern. That is right: starting from any pattern, you can keep pressing the button, and eventually reach any other pattern you desire (except, of course, for all the lights being off). This property will turn out to be very useful for the purposes of making an audio signal, but for now, I will simply state the result without proof.

At this point, you get bored of the lightpost, and continue walking to wherever it is you were originally headed. Before you can get there, however, you find another lightpost, also with fifteen lights. You push the button a few times, and discover that this one behaves slightly differently than the one before: instead of taking the exclusive or of the rightmost two lights, it takes the exclusive or of the rightmost light (let's call it light 15) and light 9:

The question for next time: how many cycles are in this second ligthpost, and what is the length of each? (Spoiler alert: the answer isn't the same as that of the first lightpost).

Friday, March 13, 2015

Chiptunes

A while back, I wrote a series of posts on some of the graphical techniques used by early 90's video game consoles. For an encore, I have decided to write about the audio techniques of said consoles. I will specifically talk about the NES, as I have studied in detail its audio processing unit.

I will start this series by saying that I love the music from the NES era. Some of it is very primitive, like the underground theme from Super Mario Bros., while some of it is actually very intricate, like the clockwork theme from Castlevania III. Of course, the softest spot in my cold, hard heart is for the intro music for Snake Rattle 'n' Roll.

The impressive part of all three of those tracks, from a technical perspective, is that they are all playing on the exact same (very limited) hardware. The audio subsystem of the NES's 2a03 processor had only five channels: two pulse channels, one triangle channel, one noise channel, and one (rarely used) pulse-code modulated channel. These five (four) channels made up all of the sound in an NES game, which is the reason why, when sound effects were also playing, parts of the background music would go silent.

Over the next few posts, I will attempt to reproduce the NES's classic sound on a computer, which will require a fair bit of digression into some pretty advanced math in order to get it to sound just right.

Unlike my series on the NES graphics, however, you can't really appreciate the sounds in this series unless you can hear them. I will try to upload some samples, but it works best if you program it on your own machine, so that you can also tinker with the program and hear the result.

To start us off, we first just need to be able to synthesize an audio signal, and play it to the computer speakers. The most primitive way I have found to do that is to just dump a digitized signal into a .wav file. This is pretty simple to do, using the following helper method:

using System.IO;
using System.Text;

public static class WaveFileFormatExtension
{
 // --- This class only supports one format: 44.1 kHz, 16-bit, mono PCM ---
 const int SAMPLE_RATE = 44100;
 const int BITS_PER_SAMPLE = 16;
 const int BYTES_PER_SAMPLE = BITS_PER_SAMPLE / 8;
 const int NUM_CHANNELS = 1;
 const int PCM_FORMAT = 1;

 public static void WriteWaveFile(this Stream destination, short[] data)
 {
  var writer = new BinaryWriter(destination);

  // --- RIFF chunk ---

  writer.Write(Encoding.ASCII.GetBytes("RIFF"));
  writer.Write((uint)(36 + (data.Length * BYTES_PER_SAMPLE * NUM_CHANNELS)));
  writer.Write(Encoding.ASCII.GetBytes("WAVE"));


  // --- fmt chunk ---

  writer.Write(Encoding.ASCII.GetBytes("fmt "));
  writer.Write((uint)16);

  writer.Write((short)PCM_FORMAT);                                    // wFormatTag
  writer.Write((short)NUM_CHANNELS);                                  // nChannels
  writer.Write((int)SAMPLE_RATE);                                     // nSamplesPerSec
  writer.Write((int)SAMPLE_RATE * BYTES_PER_SAMPLE * NUM_CHANNELS);   // nAvgBytesPerSec
  writer.Write((short)(BYTES_PER_SAMPLE * NUM_CHANNELS));             // nBlockAlign
  writer.Write((short)BITS_PER_SAMPLE);                               // wBitsPerSample


  // --- data chunk ---

  writer.Write(Encoding.ASCII.GetBytes("data"));
  writer.Write((uint)(data.Length * BYTES_PER_SAMPLE * NUM_CHANNELS));

  foreach (var datum in data)
   writer.Write(datum);
 }
}

The method above will produce a wave file with one 16-bit channel with a frequency of 44.1 kHz. I will leave it as an exercise to the reader if you want to modify it to support other channel counts, bit depths or frequencies. This detailed specification of the wave file format will be of some assistance in this regard.

Using this helper method, you can write a quick and dirty application that will play one second worth of simple audio and then close:

using System.IO;
using System.Linq;
using System.Media;

public static class Program
{
 public static void Main()
 {
  var buffer = new MemoryStream();
  buffer.WriteWaveFile(SynthesizeSquareWave(44100));
  buffer.Seek(0, SeekOrigin.Begin);

  var player = new SoundPlayer(buffer);
  player.Load();
  player.PlaySync();
 }

 public static short[] SynthesizeSquareWave(int numSamples)
 {
  var result = new short[numSamples];

  foreach (var i in Enumerable.Range(0, numSamples))
   result[i] = (short)((i % 440) >= 220 ? -4096:4095);

  return result;
 }
}

If you run this program, it should sound a little something like this.