Work/midiseq/MIDIDATA/SEQUENCE.TXT

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 sequence 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 no 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 in 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 incoming 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
then 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
add 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 is 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.