From ircam!corton!loria!loria.crin.fr!eker Fri Aug 21 15:29:34 MET DST 1992 Article: 5837 of comp.music Xref: ircam comp.music:5837 rec.music.synth:33200 Path: ircam!corton!loria!loria.crin.fr!eker From: eker@loria.crin.fr (Steven Eker) Newsgroups: comp.music,rec.music.synth Subject: Sequencer algorithm article (long) Message-ID: <450@muller.loria.fr> Date: 19 Aug 92 19:41:39 GMT Sender: news@news.loria.fr Followup-To: comp.music Organization: CRIN (CNRS) Nancy - INRIA Lorraine Lines: 375 I'm posting this article which I wrote for a MIDI mag a while ago in the hope that MIDI programmers will find it useful (I saw a posting a week ago asking about how to write a sequencer). Appologies in advance to music reseach people: This article is (very) "dumbed down" because it is written for an audience who were (for eg) treated to a lengthy explaination of binary and hex notation in a previous issue. A couple of questions: (1) How is the "one point" vs "two point" representation of on/off pairs handled in top pro/reseach music software? Do you use binary heaps or something more advanced (eg f-heaps)? (2) I've cross posted to comp.music & rec.music.synth (followups to comp.music) but considering the recent discussion, which group is most appropriate for MIDI programming articles? I know this is MIDI and hence an anathema to some (most?) music research people but rec.music.synth strikes me as user/musician orientated rather than programmer orinetated. Steven MIDI I/O ALGORITHMS =================== by Steven Eker (eker@loria.fr) To a musician, a note is an single object possessing (among other characteristics) a starting point and a length. However to MIDI equipment a note consists of two distinct events - a Note On message and a Note Off message. It is easy to see why MIDI had to be implemented this way: suppose you press a key on a synth, then the synth must immediately transmit a message telling any connected modules to play a note, however there is no way the synth could transmit the length of the note as it hasn't been determined until you release the key. This dichotomy causes a real headache for sequencer designers: how best to store sequences of notes inside the sequencer? The most obvious answer is the so called "two point" format where the notes are stored as a sequence of Note On and Off events, in the order they arrive from the synth. This format is fine when you simply want to store and replay sequences unmodified and is the format chosen for the MIDI file standard - presumably to make life easy for simple-minded sequencers. The problems start when you want to edit sequences. Whenever you move insert or delete a Note On event you have to move insert or delete the corresponding Note Off event otherwise you will end up with the notes which change length unexpectedly or even worse hang indefinitely. Of course a decent sequencer should keep track of the Note On/Off pairs and present the user with notes as single entities. With the two point format a Note On event and its matching Note Off event may be separated by arbitrarily many other events and manipulating such a sequences consistently requires a lot of searching for matching Note On/Off pairs. It is much simpler if sequences of notes are stored in the "one point" format where each Note On/Off pair is combined as a single item in a sequence. This format also saves memory. The big drawback of the one point format is that it has to be converted to and from the two point format for input and output. This has to be done in real time and any lengthly computations will reduce the accuracy of the sequencer. In his book "MIDI sequencing in C", Jim Conger suggests storing MIDI sequences in two point format and then converting them to and from one point format as required for note level editing by the user. This solution has a number of disadvantages. Firstly block move/copy routines (and any other routines that have to manipulate sequences in the two point format) are complicated by the the need to avoid separating Note On and Note Off events. Secondly there is now way the user can edit events during playback and hear the changes as they are being made. Thirdly there is no saving in memory as is possible with the one point format. The method I will explain in this article allows you to have the best of all worlds and even solves two other MIDI I/O headaches at the same time: (1) When a sequencer is replaying a large number of tracks simultaneously the naive approach of sequentially scanning the active tracks to see which should be next to output an event can cause timing inaccuracies and (if interrupts are blocked during this process) cause incomming MIDI messages to be lost. (2) When the user clicks on the stop button, all currently playing notes must be terminated. One naive method is to send an All Notes Off message on each MIDI channel. This method fails when the receiving MIDI device does not implement All Notes Off. Another naive method is to send Note Off messages for every pitch on every channel. Apart from taking a little over 1.3 seconds (with running status) this method can also cause problems if the sequencer output is being merged with another MIDI source. A rather clever idea used by one well known sequencer vendor is to send a single Active Sensing message causing the receiving device to reset itself when no further Active Sensing messages arrive. Unfortunately even this method causes problems with certain synths. The right thing to do is to transmit Note Off messages for just those notes that are actually playing, but this means keeping track of which these are which can be very time consuming (affecting sequencer accuracy) if done a naive way. Overview of the solution ======================== The basic idea is to keep the sequence(s) in one point format and use fast algorithms to convert to and from two point format in real time for input and output. Actually converting incomming data from two point format into one point format is fairly straight-forward. We simply keep a 128x16 entry table. There is one entry for every pitch/channel combination. When a Note On message arrives it is stored in a record in the appropriate sequence and a pointer to this record is stored in the corresponding table entry. When a Note Off message arrives we look at the appropriate entry in the table. If it is null the we have a stray Note Off event and we discard it. Otherwise we have a pointer to the record containing the matching Note On event and we added the extra information, release time and possibly release velocity to this record and place a null in the table entry. There are a couple of subtle points to cope with missing Note Off messages. If when we come to write a pointer in to the table we find that the entry is already filled by a non-null pointer then this pointer points to a record containing a Note On message which (for some reason) has lost its Note Off message. In this case we can use the current time as the release time and 64 as the default release velocity to replace the missing information. At the end of recording we check through the table looking for non-null entries. If we find any then these are pointers to records containing Note On messages without Note Off messages. This can easily happen if the user clicks on the stop button without releasing all the synth keys. Once again we can use the current time and the release velocity 64 to fill in the missing data. The reverse process, converting from one point format into two point format for playback not so simple. We need to use a computer science concept called a priority queue. Priority Queues =============== A priority queue is a collection of items ordered by some property - in our case time. There are several operations that may be performed on a priority queue - for our purposes the following four are sufficient. (1) Inspect the least item (2) Remove the least item (3) Insert a new item (4) Flush the queue - remove all items. Now for playback we keep two priority queues: The first contains the next note/event for each active track. The second contains all of the pending Note Off events. Now when we come to transmit an event we compare the time stamps of the least items in the two priority queues. There are two possibilities/steps: (1) If the time stamp on the least item in the note/event queue was the lesser (or the Note Off queue was empty) we output this event. We remove this item from the note/event queue and insert the next item on the same track into the note/event queue. Also if this item was a note we insert a corresponding Note Off event into the Note Off queue. (2) If the time stamp on the least item in the Note Off queue was the lesser (or equal) we output this Note Off event and remove this Note Off event from the Note Off queue. Actually this explanation is oversimplified since we also should take into account the sequencer clock but I'll come to that later. The reason for giving Note Off events precedence when the least items in each queue have the same time stamp is simply that MIDI devices have limited polyphony and this reduces the likelihood of the polyphony limit being exceeded and notes being arbitrarily cut off. When the user presses the stop button then the Note Off queue contains a Note Off event for every note playing note so we can simply flush this queue (i.e. remove and transmit all the Note Off events in any convenient order) to terminate all currently playing notes. Binary Heaps ============ Up to now I haven't said anything about how the priority queues are actually implemented. An obvious solution is to store them as arrays. There is a snag however: Typically the number of tracks in a sequencer that could be active will be rather large - say 64 and each will have an event in the note/event queue. Also the number of pending Note Offs that might have to be stored in the Note Off queue could be equal to the total polyphony of all the user's synths/modules. Now when we have to find the least item in a queue, in the worst case we might have to check all the items. This is not a good solution. Suppose we kept the array in sorted order - now getting at the least element is easy. However this time we might have to move all the items already in the queue whenever we insert a new item. A sorted linked list is also a poor implementation of a priority queue because we might have to check every item already in the queue to find out where to insert a new item. A better way to implement priority queues is a data structure called a binary heap. This is an array which is "half-sorted" in a very special way that allows both the removal of the least item and the insertion of new items to be performed efficiently. Binary heaps are explained in detail in any decent book on data structures so I will not go into technical details here. A particularly good account of binary heaps for the practising programmer is Chapter 12 of "Programming Pearls" by Jon Bentley. If sequences are stored in one point format, reading and writing them to and from MIDI files (which remember use the two point format) requires the same sort of conversion as that required for MIDI I/O and similar algorithms can be used. The situation for one point format to two point format conversion is somewhat simpler since only one track is written at a time so only a Note Off heap is required. Also speed is not so critical however a binary heap is still a good way to organise the conversion. To illustrate how easily binary heaps can be programmed Figure 1 contains the heap manipulation code (written in 'C') from the MIDI file save module of my own sequencer. ------------------------------------------------------------------------------- typedef struct heap_struct { long time; char byte1, byte2, byte3; } HEAP; static HEAP midi_heap[256]; static int heap_size; ins_heap(time, byte1, byte2, byte3) register long time; char byte1, byte2, byte3; { register int empty = ++heap_size, new; for(;;){ new = empty / 2; if(new == 0 || midi_heap[new].time <= time) break; midi_heap[empty] = midi_heap[new]; empty = new; } midi_heap[empty].time = time; midi_heap[empty].byte1 = byte1; midi_heap[empty].byte2 = byte2; midi_heap[empty].byte3 = byte3; } del_heap() { register int empty = 1, new; register long time = midi_heap[heap_size--].time; for(;;){ new = 2 * empty; if(new > heap_size) break; if(new < heap_size && midi_heap[new + 1].time < midi_heap[new].time) new++; if(midi_heap[new].time >= time) break; midi_heap[empty] = midi_heap[new]; empty = new; } midi_heap[empty] = midi_heap[heap_size + 1]; } Figure 1: Heap manipulation code ------------------------------------------------------------------------------- How the code is used is a follows. Initially the heap is empty and heap_size = 0. The least element (if the heap is not empty) in the heap is always in midi_heap[1]. (Yes - I know 'C' arrays start at 0 but here it is convenient to not use the first element.) Each event in the sequence being written to a MIDI file has its time stamp compared with that of the Note Off event in midi_heap[1] (if the heap is not empty). If the Note Off event in midi_heap[1] has the lesser time stamp it is written to the MIDI file and del_heap() is called to remove it from the heap and the comparison step is repeated with the new occupant of midi_heap[1] (assuming the heap is still not empty). Whenever the current event in the sequence has the lesser time stamp (or the heap is empty) this event is written to the MIDI file. Also if this event was a Note On event, ins_heap is called to put the corresponding Note Off event in the Note Off heap. At the end of the sequence the Note Off events remaining in the heap are written to the MIDI file and removed from the heap in the order least time stamp first. In this way the Note Off events are slotted into their correct places in the MIDI file. Subtle points ============= There are a number of subtle points and refinements when it comes to implementing the above ideas. First off, during playback we need to compare time stamps of events against the current sequencer clock to see if they are due to be output as well as against each other to determine the order. One way of organising this is that we first compare the least element of the Note Off heap against the sequencer clock - if it is less than or equal we take step (2) above. Otherwise we compare the least element of the note/event heap against the sequencer clock - if it is less than or equal we take step (1) above. Otherwise we know that the time stamps on all the next events in all the active tracks and all the pending Note Off events are greater than the current music time and nothing is due to be output until the sequencer clock is next incremented. Doing the tests this way around means that Note Off events can actually be transmitted in before other events with earlier time stamps - however this can only happen when there is a backlog of events due to be transmitted and prioritising Note Off messages under these circumstances may be a good thing. The alternative arrangement is to compare the time stamps of the least elements on the two heaps first and then compare the lesser of these against the sequencer clock. Notice that during playback the Note Off heap starts off as empty and is filled on the fly. To set up the note/event heap at the beginning of playback we simply call the heap insert item routine to insert the first event of each track (or more efficiently a pointer to the first event on each track) into the note/event heap. Also notice that testing the least item in a heap just means testing the item in the first location of the array used to store the heap. So no real work has to be done rearranging the heaps unless a MIDI message is actually transmitted and items have to be inserted and/or deleted from the heaps. Now in a professional sequencer the MIDI output code is interrupt driven and written in assembler both for accuracy and to allow it to run as a background task. Now even though the heap insert and delete item algorithms are very fast and can be coded in very tight assembler (the division and multiplication in the above code are done by shifting) it is possible for that for very large heaps they may not complete their task in the 320us between MIDI output bytes (or input bytes). Thus MIDI bandwidth could be wasted and accuracy impaired (and incomming MIDI data could be lost). A neat (but tricky) way of getting around this problem is allow the code that rearranges the heaps (running in an interrupt routine) to itself be interrupted by other interrupt routines to output and input MIDI bytes. In this way incomming MIDI data will not be lost. Also we have complete timing accuracy (up to sequencer clock resolution and MIDI bandwidth) as long as the heap rearrangement can be done in the 640us or 960us between output messages (Okay some messages can be transmitted in one byte using running status - but these are not Note On messages so we only have to rearrange one heap). Needless to say there has be be some kind of synchronisation between the various layers of interrupts and this is a tricky topic which I will not go into here. A nice refinement is to allow the user to activate and deactivate tracks while the sequencer is playing. This is done using slightly modified versions of the heap insert and delete item routines to insert(remove) the next event of the activated(deactivated) track in the note/event heap. Another refinement is to allow the user to edit (or block copy/move) sequences while they are being played. Both of these refinements require synchronisation between the main program code which is making the change and the interrupt routines that are modifying the heaps and accessing the track sequences.