MIDI parsing algorithms

[gstopp at fibermux.com]

     John Speth wrote:
     
     >
     >I wrote such a MIDI parser in C for a MIDI-to-Prophet controller for 
     >my el-cheapo 16 Mhz 286 machine which has no problem keeping up.  But 
     >the code quickly turned into something I wasn't very proud of 
     >(spaghetti code but it worked!).  In hindsight, I would have put alot 
     >more effort up front into a real sleek event dispatcher (kinda like a 
     >Windows 3.1 style thing).  Then the actual parsing code would have 
     >been alot simpler.  Better yet, a multitasking kernel would be best.  
     >Instead I chose a dumb loop that waits for a byte then enters this 
     >big huge switch statement.  It was all downhill from there. Enuf 
     >said!
     >
     
     The code described above sounds remarkably like a description of my 
     code! So - do great minds think alike, or should I be also ashamed of 
     my spaghetti code too? :) Anyway here's a description of my approach. 
     It's only one way of doing it, and it may not even be the best way, 
     but it does work pretty good:
     
     The parsing of MIDI data is pretty straightforward, but there are two 
     things in the 1.0 spec that cause some trouble. The first is the 
     System Real Time message, and the second is Running Status.
     
     In the MIDI protocol, valid messages can be one, two, or three bytes 
     long. Therefore it is tempting for the first-time writer of parser 
     code to grab messages from the MIDI line according to how long they 
     should be, and then once a complete message is received then go off to 
     some subroutine and do the appropriate task and return to the message 
     grabber. System Real Time messages are one byte long, but they can 
     occur at any time, including between any two bytes of an otherwise 
     valid two- or three-byte message. This will turn a three-byte message 
     for example into a four-byte message! Our simplistic hypothetical 
     grabber will choke on this. So the thing that needs to be done is to 
     have the Real Time messages stripped out and dealt with before they 
     ever reach the message grabber.
     
     Now it seems that we have saved our grabber from the possibility of 
     losing track of where it's at. But now we introduce Running Status - 
     this concept allows any of the channel messages to have a length that 
     is indeterminate! In other words, a valid three-byte message can have 
     multiple instances of the last two bytes tagged on to the end of it. 
     For example a three-note chord played on the MIDI transmitter can 
     cause a single seven-byte note-on message rather than three three-byte 
     note-on messages. This destroys our grabber idea and forces us to have 
     program control jump around from function to function, calling for the 
     next byte, depending on the context of things. This is why we need the 
     state machine approach.
     
     So - we have two fundamental requirements that are not obvious from 
     the start: first, we need to have a "get-a-byte" function that can be 
     called from anywhere, that deals with Real-Time messages. Second, we 
     need to call that function from several places in the program, not 
     just from one central place. Exactly where we are in the program at 
     any given time is determined by a handful of global variables that can 
     be updated from several places.
     
     Another advantage to the state machine approach is that it allows you 
     to add some simple tests to reset everything if an invalid message 
     comes in. In other words, if a three-byte message is missing the third 
     byte, a state machine can detect this and abort the message. In fact, 
     the state machine can act on the first two bytes as they come in, so 
     that a note-on for example can turn a note on, change the note number, 
     yet leave the velocity at its last valid value. This means that 
     yanking a MIDI cable cannot possibly lock up your parser.
     
     As soon as I can dig up my C listing I can post fragments of it. I can 
     post parts of the QuickBasic version right away but I suspect that C 
     would be a better language to share code with.
     
     - Gene
     gstopp at fibermux.com