In previous articles of the series on Amiga MOD files I wrote about implementing a system to read the file format and print the notes. The goal is to be able to render audio output. Rather than directly have audio go to a sound device I decided that writing the output to an audio file would be easier. One of the simplest audio file formats is the uncompressed Waveform Audio File Format, WAVE, or just WAV. It was created in the early 90s by IBM and Microsoft—right around the time I was learning how to write my own software. So along with BMP it became one of the first file formats I reverse engineered sometime between 1994 and 1996. With ready access to the Internet it is no longer necessary to manually workout the details by trial and error. In this article I want to look at what will take me much longer to write about than it did to implement.

Although my goal was to write WAV files, the first step was to be able to read them. The format supports storing multiple chunks of data, but most of the time there is just a single chunk. This site gave me enough detail on how the header to a WAV file is laid out. To correctly read a WAV file I would really need to account for all of the chunks. But the assumption was we were only going to use a single chunk—so that is all I was concerned about.

Now there is a weird mix of little/big endian. Why anyone would do this I couldn’t say—usually you pick one or the other. Intel has always been little endian and it turns out the specification only defines headers descriptions in big endian. It is easier just to tread those as 4 characters. Right away I could most of the all the data was 32-bit aligned. The are 16-bit fields but they come in pairs. Knowing I was writing for a little endian system I could take a shortcut—I could read the header directly into a C structure. C structures are get complected due to alignment. However, this structure was already aligned so I could use the structure trick. To be sure I used bitfields, making the 16-bit words actually bit fields in 32-bit words.

Let’s look at code that simply reads the WAV file header and prints the fields.

This code was created in a very short amount of time so very little through was given to cleaning it up. What I really wanted now was to create a WAV file. Armed with the header information I wrote a program to produce a cord and write the results to a WAV file.

Here is a simple file that uses a default header for an 8-bit, mono wave file of a fixed duration. Small modifications such as to duration and sample rate can be made and tested. It simply makes a C major seventh chord with a linear fade out and writes the data to the wave file. Part of this process requires building a table of note frequencies. A typical piano has 88 keys, but I didn’t like the odd range—7.3 octaves. So I went for an extended note rage of 108 keys—a full 9 octaves, from C₀ to B₈. The frequency of each notes follows this equation:

Where f is frequency, and n is the note from 0 to 107 with 0 being C₀ and 107 being B₈. This is a slight modification of the equation found for piano key freuencies being offset of account for the large range. Most of the file is fairly self-explanatory. The note generation happens here:

First, we find the time in seconds. Then we calculate the angle of this time in radians. Multiplying this by the note frequency and take the sine and we get a the desired note. Add these notes up and we get a chord. The amplitude of each sine wave is 1, so adding four of them together will result in a maximum amplitude of 4. Thus we divide by 4. That produces a number between -1 and 1. For 8-bit PCM we need a value between 0 and 255 with 128 being the zero point. The maximum volume is 128 so we multiply by this changing our range from -128 to +128. Adding 128 will give a range between 0 and 256. 256 is too high so we clip it to 255. We now have the 8-bit PCM value that is stored in the sample buffer.

Just for fun I generated a couple of other chords, picked difference sample frequencies and duration. Naturally they are all functional as there isn’t anything special. All of this was to demonstrate I could write a valid WAV file. Now satisfied, it was time to make a library to create WAV files from a sample set.

My first library was more or less a wrapper of what is shown here. A single function that took a sample frequency and a set of samples and wrote them to a WAV file. That was enough for my first day’s work, but as the project progressed I needed better functions.

The second function I wrote simply appended samples to a WAV file. This allowed me to incrementally add data. The third and most useful function set allows a WAV file to be opened, samples added, and then closed at which time the header details are completed. The this version also included the number of channels so stereo WAV files could be created.

If I expand the MOD library to handle other formats I might also add the ability to work with 16-bit data. For now, 8-bit data is sufficient.

Added two more effects today: arpeggio and portamento (slides). I have arpeggio (effect 0) slide up (effect 1) and slide down (effect 2) tested but not slide to note (effect 3). Arpeggio turned out to be more of a pain than I had anticipated. The parameters are not pitch, but simitones. That meant I had to add a reference to the note being played as well as the note’s period. This allows me to select and lookup the other notes in the simitone.

Slides are fairly simple except for the ticks-1 ending. Not sure why but this means the note doesn’t slide on the last tick of the division. For testing I use a fairly notorious song: CYBER.MOD. There is more than one rendition of this song and it is an adaptation of Jeroen Tel’s theme to the 1987 game Cybernoid: The Fighting Machine. Who composed this MOD is unknown.

There are several problems with this MOD. First, the slides are not slide to note, but just slides with values set so they get close to their desired note. As a result, many (most) of the slides end up out-of-tune. Another problem is that the sample looping is incorrect. Some instruments have loop lengths that extend beyond the last sample.

This song is a version of a C64 track, and a common practice for the SID 6581/8580 sound generated music was to use arpeggio to mimic chords. This technique quickly plays several notes, usually 2 or 3, one after another (an arpeggio), to make a simulated chord. The sound is emblematic to chiptunes. MODs have the effect but it isn’t used very often, mainly because if one wants chord they can simply sample the chord and include it. Nonetheless this song makes heavy use of arpeggio to simulate the C64 sound.

The arpeggio and slides make it a good song for testing because it is easy to hear differences if the playback isn’t working correctly. I have successfully reproduced the song and that should prove slides and arpeggio are functional.

I meant to try another MOD that uses slide, but I cannot load 15 instrument MOD files. So that will have to wait for another day.

Note: Yes, the slides are out-of-tune—that is how the song is written and that is how it is being reproduced.

Today instead of tending to yard work I decided to dive into the next phase if a new project: an Amiga module player. The first milestone has been reached and I’m impressed by how much I’ve already accomplished.

The journey started on Friday when I used some base reference material to read in a standard 4 channel MOD file. Initially I thought I’d detail all those steps are part of this article but I have decided instead to make a multi-part series on the process of creating my own MOD player. In this article I will focus on what happened during the day that allowed me take a skeleton of a library that was able to load a MOD file, and a very simple WAV file writer to render the first MOD I composed.

I spent a fair amount of time on Saturday trying to work out how the Amiga computer played back notes. The reference document was fairly vague and their numbers slightly inaccurate but we’ll save the details for another article. In the end, I learned that the sample period defines the rate at which new words are sent to the analog to digital converter. This determines the samples’ pitch. That part was easy. What I wasn’t sure about was how to convert these values to the sample frequency I was using. I finished Saturday with some understanding of how the rates worked.

Today it was time to make sound. It made sense to me to render the first MOD I ever wrote: Que’s First. While technically Crazzy was the first MOD I wrote, it was not composed so much as randomly thrown together. Que’s First’s melody was composed on a keyboard before it was put into MOD form. So it is really the first MOD I composed.

I started by ignoring periods all together. Somewhere I had read the the samples that make MOD instruments were sampled at 8000 Hz. So I made a program to extract MOD samples and turn them into WAV files setup with a 8000 Hz playback frequency. This is quick but required one conversion. Amiga samples are two’s complement 8-bit signed integers, and was a WAV sample is an 8-bit unsigned integer. So all the samples need to have 0x80 added to them.

The produced all the samples from my MOD as I expected, and their pitch sounded reasonable. My first pass at playback would simply render the first channel of the pattern. This would work well because for that song, the first channel is the drum beat—a simple kick drum and snare combination. Pitch doesn’t matter too much. This would allow me to get the speed of playback correct.

This produced a WAV file that had my bass/snare beat. A good start. The next step was to render all 4 channels. The song begins with a measure of just the beat. There is the kick/snare on the first track, and the second channel which has a rattle shake (like a Maraca). The volume of the shake alternates between full and half which loosely mimics the beads in the rattle sounding at different volumes depending on the side they hit.

This code produced the entire beat which is looped throughout the song. Now it was time for pitch. My work yesterday gave me an equation to convert the note’s period value to the number of samples per second sent to the Digital-to-Analog Converter (DAC). I had a fixed number of samples per second sent to the DAC, so what I needed to calculate was which sample would be getting sent to the DAC at a moment in time. I plan to write in much more detail about how MOD timing works, but for now just understand that songs are broken up in to patterns which consist of 64 divisions in which a note can be played. The speed at which divisions are played is based on the tempo which defaults to 125 beats/minute. There are 4 divisions in a beat. A division is further divided into ticks but other than knowing that the speed calculations assume 6 ticks/division, ticks are not yet used elsewhere.

So I added a function to mix a single division worth of samples. This function has a fixed-point index used to figure out where in the channel’s instrument sample the next output sample comes from. The is some fractional number based on the note’s period. We only use the whole number for the index, but keep the fractional part so it can properly accumulate as playback continues.

I needed to add the calculation to compute the note’s playback increment rate. This is how many counts (including fractional) the instrument sample index changes for each output sample of the mix. Just simple scaling math here. To make it easy on myself I used floating-point for doing the calculation. There are no speed concerns and I was just trying to move quickly so I didn’t feel bad about this.

The results: I had a full playback of my first module that was mostly accurate. For my next iteration I addressed two issues: the pattern break effect and volume slides. In order to do this I needed to address ticks. As briefly stated, each division is further broken into a number of ticks. Effects are applied on the tick level. For volume slide, the amount the volume changes is applied each tick.

Although I didn’t need it for this song, I also added instrument loops. While rendering my own song, I was also rendering a classic: Bjorn Lynne’s 12^th Warrior. I wasn’t worried about getting everything correct—just pieces—and did get instrument loops working.

That was it. With the volume slide functional I was able to fully render my very first Amiga module. For the first time I am releasing this MOD and my first rendering of it. Be aware, I was 13 or 14 years old when I composed this song and was no (and am still not a) musical prodigy.

The song itself was composed around 1991 or 1992 on a Yamaha Protasound PSS-140 keyboard acquired from a garage sale, and I tracked this MOD sometime in between mid and late 1993. 28 years latter, I am able to render it into a playable waveform using only my own software.

All the code posted here was written in a full day of work, based on code written over bits of the prior 4 days. I typically don’t release uncleaned code, but this is kind of a unique project in its ability to show developing code.

After implementing an iterative AVL tree using a stack, I immediately asked myself it were possible to to eliminate the stack.  For those who found this page first, this article is part of my series on command handler lookups.  An AVL tree is probably not the best solution for a command handler, but is being explored to demonstrate some basics on its implementation.

The quick answer to if the stack can be eliminated from the iterative AVL tree insert function is yes, but at the cost of additional memory needed for each node. The stack is needed so the balance process can traverse back up the tree from the node just inserted to the trunk. However, if each node knows its parent then the tree can be traversed in either direction. This is basically makes the tree—alright a kind of single linked-list—a double linked list.

The modifications needed for implementation all have to do with the parent node. For every node there is a pointer to the parent. The first node of the tree has no parent and is the only node to have a parent of NULL. Unlike a conventional double linked list, the parent node isn’t the only information we need to concern ourselves with. The parent node has two children—left and right—and during rebalance rotations the child needs to know which of those children it is.  This should become more evident as we explore the implementation.

The node insert has three parts.  The first part searches for the location the new needs to be placed.  This happens the same way the search for a specific key happens.  Start at the trunk and pick the left or right branch based based on a comparison of the new node's key value.  When the next node to search is NULL, meaning the end of the branch has been reached, the insert location has been found.  The search for the insert location only has one change: we remember the parent node.

Now the new node insertion after finding the insert location:

We just have to set the parent in the new node. Otherwise, the first part of the insert remains the same. From this point forward the changes are more complex and much easier to get wrong.

Notice we start the balance process with the parent node. There isn’t anything wrong with starting at the new node except this node is always starts balanced as it has no children. The loop will run until there are no parent nodes.  Now to the outer part of the loop itself.

First we need to remember the parent node for latter. Then we need to figure out which of the parent’s children point to this node. This is important because if a rotation is needed we are going to reassign children. Now keep in mind we want a link to the pointer to the current node—a double pointer. There are three possibilities, left, right and trunk. Left and right is simple: if they point to our node, they are the pointer we are looking for. However, if our parent is NULL it means this is the trunk of the tree. In that case, we need modify the pointer to the first node—the trunk of the tree itself. The last condition is something that should never happen—the assigned parent does not have this child node. In that case, something went wrong and the tree is dysfunctional.

Now onto the rotations. We will just explore one rotation but the same rules apply to the other.

The change here is is simply updating the parent nodes. It is simply the reverse of the lines just above it. The right child of x is assigned to y, thus the parent of y parent is x. We do have to check the hold value before setting the parent because it may NULL meaning it isn’t yet assigned.

This will take care of the right/left rotation basics, but not the entire rotation process. Each rotation returns a node which is further modified.

Here we see parentLink being used during a rotation. Remember that parent link points to either parent->left or parent->right. After the rotation sets the parent link the last step that needs to be done is updating the parent link of the child that was just modified.

That’s it, but each of those steps are important. Missing one can easily corrupt the tree.  Below is a link to a fully functional demonstration using an AVL tree as a lookup table.