From: eker@loria.crin.fr (Steven Eker)
Newsgroups: comp.music,rec.music.synth
Subject: MIDI I/O Algorithms (repost + new idea)
Keywords: binary heaps, priority queues, linked lists
Date: 2 Oct 92 11:07:21 GMT
Followup-To: comp.music
Organization: CRIN (CNRS) Nancy - INRIA Lorraine

Since I mentioned my "MIDI I/O Algorithms" article in a previous post
a number of people have asked me to repost it or make it available over ftp
- I guess a lot of people were on vacation in August when I first posted it.

Since then I've had a new idea which may also be of interest and which I've
included at the end of this post.

If anyone one wants to make this info available via ftp, feel free -
the article originally appeared in
"MIDI Monitor", issue 6, pp20-23, July/August 1992
but I retained the copyright so that I could distribute it over the net.

Please bear in mind that I wrote it for an audience of MIDI hackers/users -
not CS academics!

I doubt that I'm the first person to think of this idea and I'd be interested
to know of references to similar I/O schemes.

Also I never received any response to my question which accompanied my first
post as to which news group is most suitable for technical MIDI discussion
of this sort.

Please email any responses since incomming news takes ~2 weeks to reach this
site.

Steven

===> Original article

MIDI I/O ALGORITHMS
===================
by Steven M. Eker

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
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 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.

<=== End of original article

New idea ===>

A potential problem with this approach was pointed out to me by
Bruce Petherick (MUSBEP@lure.latrobe.edu.au). What happens if you get
two or more Note On messages for the same channel/pitch combination
without an intervening Note Off for that channel/pitch?

One answer is that the MIDI specification provides no way to decide which
Note On message matches which Note Off. Nor does the MIDI spec say what
a sequencer or sound module should do under such circumstances.

What my sequencer does when a second such Note On arrives is assume it has
missed a Note Off and terminate the existing note then and there.
The first Note Off terminates the 2nd Note On and 
the remaining extra Note Off is ignored as spurious.

This approach may not be satisfactory for all applications since
the output of the sequencer is not identical to the input for such ambiguous
sequences of messages. However there is an elegant fix.

First we adopt one of two conventions to give semantics to such ambiguous
sequences of messages:
(1) First Note On matches first Note Off
(2) First Note On matches last Note Off
Conceptually we then replace the 128x16 table of pointers to combined
Note On/Off pair records with a table of queues (respectively stacks).
As each Note On message arrives it is stored in a Note On/Off pair record
and a pointer to the record is pushed on to the appropriate
queue (stack). Note Offs are matched with the first element of the
queue (stack) which is then removed. It's easy to see that either convention
will provide output=input behaviour for ambiguous message sequences.

The naive way of implementing this table of queues (stacks)
would be quite expensive in terms of dynamic storage management. However
it can be implemented at no extra cost as follows:

Firstly we keep an extra pointer in each combined Note On/Off pair record.
This is used to form a linked list of records that make up a queue (stack)
(recall that a singly linked list can be used to implement both queues and
stacks). So the 128x16 table need only contain pointers to the
Note On/Off pair record at the head of each queue (stack).
(Added elements to a singly linked list implementation of a queue
requires either that a 2nd pointer be maintained
or that the list be traversed but since the queues will be very small
traversing the list will usually be acceptable.)

Now keeping an extra pointer in each Note On/Off pair record might
appear to be expensive since a typical sequencer may store hundreds
of thousands of notes. However since we are storing Note On and Note Off
messages as pairs each Note On/Off pair record must include
storage for either the length of the note or the release time.
On most architectures this will be the same size as a machine pointer.
Since while a note is in a queue (stack) its length (or release time)
is not known, this piece of storage can be used to hold the extra pointer
at no extra cost in memory over the original scheme.

<=== End of new idea
Newsgroups: comp.music