/*====================================================================
 * midicomp.c++
 *
 * midicomp is a tool for compressing midi sequence files from standard
 * midi types (0 and 1) into a format unique to the Ultra64. Compressiong
 * comes first from removing note offs, and storing a duration value
 * with the note on. After that, the file is scanned for repeated data,
 * and when a repeat is found, it is replace by a four byte code. The code
 * is composed of a one byte identifier (0xFE) a two byte back up distance,
 * and a one byte length.
 *
 * Copyright 1995, Silicon Graphics, Inc.
 * All Rights Reserved.
 *
 * This is UNPUBLISHED PROPRIETARY SOURCE CODE of Silicon Graphics,
 * Inc.; the contents of this file may not be disclosed to third
 * parties, copied or duplicated in any form, in whole or in part,
 * without the prior written permission of Silicon Graphics, Inc.
 *
 * RESTRICTED RIGHTS LEGEND:
 * Use, duplication or disclosure by the Government is subject to
 * restrictions as set forth in subdivision (c)(1)(ii) of the Rights
 * in Technical Data and Computer Software clause at DFARS
 * 252.227-7013, and/or in similar or successor clauses in the FAR,
 * DOD or NASA FAR Supplement. Unpublished - rights reserved under the
 * Copyright Laws of the United States.
 *====================================================================*/

#include <stdio.h>
#include <stdlib.h>
#include <bstring.h>
#include <assert.h>
#include <getopt.h>
#include <math.h>

#include <libaudio.h>
#include "midifile.h"
#include "list.h"
#include "midicomp.h"

static char usage[] = "[-o] <infile> <outfile>";


MIDIList    list;


void main(int argc, char **argv)
{
    int c;
    extern char *optarg;
    extern int  optind;
    int         errflg=0;
    char        *ifile=0;
    char        *ofile=0;

    
    while ((c = getopt(argc, argv, "o")) != EOF)
    {
        if(c == '?')
            errflg++;
	else if(c == 'o')
	    list.OrderEvents(1);
    }


    if (errflg || optind == argc)
    {
        (void)fprintf(stderr, "%s %s\n", argv[0], usage);
        exit (2);
    }

    ifile = argv[optind++];
    if (optind == argc)
    {
        fprintf(stderr,"%s: must specify an output file\n", argv[0]);
        exit(1);
    }

    ofile = argv[optind];
    
    MIDIComp *midiIn = new MIDIComp;
    if (!midiIn)
        exit(1);
    
    midiIn->Open(ifile, "r");  /* open the input file */

    MIDIComp *midiOut = new MIDIComp;
    if (!midiOut)
        exit(1);

    midiOut->Open(ofile, "w");
    
    midiIn->Parse();

    /* set sequence end to one tick past last note,
       this makes sure last event gets processed */
    midiOut->sequenceEnd = midiIn->sequenceEnd + 1; 
    midiOut->division = midiIn->division;
    
    midiOut->fileSize = midiIn->fileSize;
    
    midiOut->Write();
    
    midiIn->Close();
    midiOut->Close();
}

void MIDIComp::midiHeader(TrackHdr *hdr)
{
    sequenceEnd = 0;
    division = (long)hdr->division;
}

/* Meta Message handlers */
void MIDIComp::midiTempo(long tempo)
{
    Node *node = new Node();

    node->type = META_TYPE;
    node->subtype = 0x51;
    node->time = curTime;
    node->data = (char *)malloc(3);
    node->len  = 3;

    node->data[0] = (char)(tempo >> 16) & 0xff;
    node->data[1] = (char)(tempo >>  8) & 0xff;
    node->data[2] = (char)(tempo & 0xff);

    list.Insert(node);    
}

void MIDIComp::midiEndOfTrack()
{
    if(sequenceEnd < curTime)
        sequenceEnd = curTime;
}



/* Channel Message handlers */
void MIDIComp::midiNoteOn(char chan, char key, char velocity)
{
    if(velocity)
    {
        Node *node = new Node();

        node->type = MIDI_TYPE;
        node->time = curTime;
        node->status = MIDI_NoteOn | chan;
        node->b1 = key;
        node->b2 = velocity;
        node->dur = 0;
    
        list.Insert(node);
    }
    else /* must be a note off really */
        list.endNote(curTime,chan,key);
}

void MIDIComp::midiNoteOff(char chan, char key, char)
{
    list.endNote(curTime,chan,key);
}

void MIDIComp::midiKeyPressure(char chan, char key, char velocity)
{
    Node *node = new Node();

    node->type = MIDI_TYPE;
    node->time = curTime;
    node->status = MIDI_PolyKeyPressure | chan;
    node->b1 = key;
    node->b2 = velocity;
    
    list.Insert(node);    
}

void MIDIComp::midiControlChange(char chan, char control, char value)
{
    Node *node = new Node();

    node->type = MIDI_TYPE;
    node->time = curTime;
    node->status = MIDI_ControlChange | chan;
    node->b1 = control;
    node->b2 = value;
    
    list.Insert(node);    
}

void MIDIComp::midiPitchBend(char chan, char msb, char lsb)
{
    Node *node = new Node();

    node->type = MIDI_TYPE;
    node->time = curTime;
    node->status = MIDI_PitchBendChange | chan;
    node->b1 = msb;
    node->b2 = lsb;
    
    list.Insert(node);    
}

void MIDIComp::midiProgramChange(char chan, char program)
{
    Node *node = new Node();

    node->type = MIDI_TYPE;
    node->time = curTime;
    node->status = MIDI_ProgramChange | chan;
    node->b1 = program;
    node->b2 = 0;

    list.Insert(node);    
}

void MIDIComp::midiChannelPressure(char chan, char pressure)
{
    Node *node = new Node();

    node->type = MIDI_TYPE;
    node->time = curTime;
    node->status = MIDI_ChannelPressure | chan;
    node->b1 = pressure;
    node->b2 = 0;
    
    list.Insert(node);    
}

void MIDIComp::Write()
{
    int     i,fSize;
    long    compTrackSize;
    float   percent;
    
    /* parse out each individual track in uncompressed form */
    for(i = 0; i < 16; i++)
        buildTrack(i);

    /* compress all tracks into one buffer */
    compressTracks();
    
    /* write the header */
    writeHeader();

    /* write the compressed track buffer */
    compTrackSize  = curOutPtr - compData;
    fwrite(compData,compTrackSize,1,file); 

    free(compData); /* free the compressed track buffer */

    /* print out the amount of compression achieved */
    fSize = compTrackSize + sizeof(ALCMidiHdr);    
    percent = (float)fSize / (float)fileSize;
    percent *= 100;
    printf("%s: compressed from %6d to %6d    %6f percent of original size\n",name,fileSize,fSize,percent);

}

void MIDIComp::writeHeader()
{
    ALCMidiHdr  theHdr;
    int         i;
    long        curOffset = sizeof(ALCMidiHdr);
    
    theHdr.division = division;

    for(i=0;i<16;i++)
    {
        if(compTrackSizes[i])
        {
            theHdr.trackOffset[i] = curOffset;
            curOffset += compTrackSizes[i];
        }
        else
            theHdr.trackOffset[i] = 0;
    }
    
    fwrite(&theHdr, sizeof(ALCMidiHdr), 1, file);
}

void MIDIComp::compressTracks(void)
{
    long    hashTableSize,compBufSize = 0;
    long    trackNum,i;


    for(i=0;i<16;i++)
        compBufSize += trackSizes[i];

    nextHashPtr = curOutPtr = compData = (char*)malloc(compBufSize);
    if(!compData)
    {
        printf("Failed to allocate memory for compression buffer\n");
        exit(-1);
    }
    
    hashTableSize = HashSize(compBufSize);
    hashTable = (char **)calloc(hashTableSize,sizeof(char *));
    if(!hashTable)
    {
        printf("Unable to alloc memory for hash table. size = %d\n",hashTableSize);
        exit(1);
    }

    if(trackSizes[0] <MIN_MATCH_SIZE)
    {
        printf("First track is too small. You must have some data on channel zero!\n");
        exit(-1);
    }
    
    trackNum = 0;    
    while(trackNum < 16)
    {
        if(trackSizes[trackNum]) /* if there is data in the track */
            compress1Track(trackNum);
        else
        {
            compTrackBufs[trackNum] = 0;
            compTrackSizes[trackNum] = 0;
        }
        trackNum++;
    }
    free(hashTable);
}

/*******************************************************************************
 *   Compress1Track, takes a track of data in trackBufs, and steps through,
 *   searching for repeated data.  It does this, by taking the current data,
 *   referred to as the window, running it through the hash routine, which
 *   returns a value that is used with a hash table to lookup possible matches.
 *   If a match is found, a backup code is inserted, otherwise, a byte of data
 *   is copied to the output buffer, and the hash is added to the hash table.
 *   Then the routine advances the window a byte and checks again.
 *******************************************************************************/

void MIDIComp::compress1Track(long track)
{
    char    *trackEnd = trackBufs[track] + trackSizes[track];
    char    *checkEnd = trackEnd - MIN_MATCH_SIZE;
    char    *windPtr  = trackBufs[track];
    char    *tryPtr,*bestStart,*startPtr;
    char    hiBackUp,loBackUp,whichLoop;
    long    hashVal,backup,i;
    long    bestLen,matchLen;
    
    
    compTrackBufs[track] = curOutPtr;    
    
    if(track == 0)  /* set up first track by copying MIN_MATCH_SIZE and making first hash entry */
    {
        curOutPtr = CopyData(trackBufs[0],curOutPtr,MIN_MATCH_SIZE);
        hashVal = HashString(nextHashPtr,hashMask);
        hashTable[hashVal] = nextHashPtr;
        nextHashPtr++;
        windPtr += MIN_MATCH_SIZE;
    }
        
    while( windPtr < checkEnd)
    {
        bestLen = 0;
        hashVal = HashString(windPtr,hashMask);
        tryPtr = hashTable[hashVal];

        /*
         * as long as tryPtr != 0, check for a match between the
         * data in the window, and what the hash points to.
         */
        while(tryPtr) 
        {
            if((curOutPtr-tryPtr) <= MAX_WIND_ADV)
            {
                matchLen = matchPattern(windPtr,tryPtr);
                if(matchLen > (curOutPtr-tryPtr)) /* don't match back over yourself */
                    matchLen = curOutPtr-tryPtr;
                if(matchLen > MAX_MATCH_LEN) /* if match length is to big, trim it down */
                {
                    matchLen = MAX_MATCH_LEN;
                    bestLen = matchLen;
                    bestStart = tryPtr;
                    break; /* you won't do any better, so bust outta here */
                }
                
                if(matchLen > MIN_MATCH_SIZE && matchLen > bestLen) /* got a better match */
                {
                    bestLen = matchLen;
                    bestStart = tryPtr;
                }
            }
            hashVal++; /* increment and try next hash value. when zero, out of candidates */
            hashVal = hashVal & hashMask; /* if looped around, reset hashVal */
            tryPtr = hashTable[hashVal];
        }
            
        if(bestLen) /* only will be !0 if there was a good match */
        {
            backup = curOutPtr - bestStart;
            hiBackUp = (char)(backup >> 8);
            loBackUp = (char)(backup & 0xFF);
            *curOutPtr++ = AL_CMIDI_BLOCK_CODE; /* write the code */
            *curOutPtr++ = hiBackUp;            /* write the backup */
            *curOutPtr++ = loBackUp;
            *curOutPtr++ = (char)bestLen;       /* write the length */
            windPtr += bestLen;
            for(i = 0; i<4; i++) 
            {
                hashVal = HashString(nextHashPtr,hashMask);
                while(hashTable[hashVal])
                {
                    hashVal++;
                    hashVal = hashVal & hashMask;
                }
                hashTable[hashVal] = nextHashPtr;
                nextHashPtr++;
            }
        }
        else /* didn't get a match */
        {
            /* if it's a 0xFE data, repeat it!!! */
            if(*windPtr == AL_CMIDI_BLOCK_CODE)
                *curOutPtr++ = *windPtr;

            *curOutPtr++ = *windPtr++; /* write the data byte */
                                       /* then add to hash table */
            hashVal = HashString(nextHashPtr,hashMask);
            while(hashTable[hashVal])
            {
                hashVal++;
                hashVal = hashVal & hashMask;
            }
            hashTable[hashVal] = nextHashPtr;
            nextHashPtr++;
        }       
    }

    /* copy the remaining data on over. */
    curOutPtr = CopyData(windPtr,curOutPtr,trackEnd-windPtr);
    compTrackSizes[track] = curOutPtr - compTrackBufs[track];    
    free(trackBufs[track]);

    tryPtr = compTrackBufs[track];  /* reset tryPtr to begining of compressed track */

    while(tryPtr<curOutPtr) /* go through track and find loopends */
    {
        if(*tryPtr == 0xFF)  /* begining of a Meta */
        {
            tryPtr++;
            if(*tryPtr == AL_CMIDI_LOOPEND_CODE) /* find the loopends */
            {
                tryPtr+=3; /* skip over loop counts */
                whichLoop = *tryPtr;
                startPtr = compTrackBufs[track];  /* start back at begining, */
                while(startPtr<tryPtr)            /* and scan for loopstart */
                {
                    if(*startPtr == 0xFF) /* potential */
                    {
                        startPtr++;
                        if(*startPtr == AL_CMIDI_LOOPSTART_CODE) /* yes loopstart */
                        {
                            startPtr++;
                            if(*startPtr == whichLoop) /* yes correct loop! */
                            {
                                /* now calculate backup, and set to value in data */
                                startPtr += 2; /* set to end of loopstart */
                                backup = (long)(tryPtr+4) - (long)startPtr;
                                *tryPtr++ = (char)((backup & 0xFF000000) >> 24);
                                *tryPtr++ = (char)((backup & 0x00FF0000) >> 16);
                                *tryPtr++ = (char)((backup & 0x0000FF00) >> 8);
                                *tryPtr++ = (char)(backup & 0x000000FF);
                                goto foundLoopMatch;
                            }
                        }
                    }
                    else
                        startPtr++;
                }
                printf("No loopstart found for %d\n",whichLoop);
              foundLoopMatch:                
                tryPtr+=4;
            }
        }
        else
            tryPtr++;
    }

    return;
}

/*************************************************************************************
 * BuildTrack.  Assemblies a track worth of data, uncompressed. First goes through and
 * calculates the size of the buffer, and allocates that much space. Then goes through
 * a second time and actually builds the buffer.
 *************************************************************************************/
void MIDIComp::buildTrack(int track)
{
    Node    *item;
    long    bufOffset = 0;
    long    bufSize = 0;
    long    trackTime = 0;
    long    delta;
    char    *trackBuf;
    long    trackEnd = 0;
    long    loopCount = 0;

    lastStatus = 0;

    /* first time through list, just calculate size */
    for (item = list.head; item != 0; item = item->next)
    {
        if(item->type == MIDI_TYPE && (item->status &  MIDI_ChannelMask) == track)
        {
            switch(item->status &  MIDI_StatusMask)
            {
                case MIDI_NoteOn:
                    if(item->dur)  /* if the note has a duration */
                    {
                        bufSize += deltaSize(item->time - trackTime);
                        if(lastStatus != item->status)
                        {
                            bufSize += 3;   /* three bytes for note on */
                            lastStatus = item->status;
                        }
                        else
                            bufSize += 2;   /* running status note only adds 2 bytes */
                        bufSize += deltaSize(item->dur);
                        trackEnd = item->time + item->dur;
                        trackTime = item->time;
                    }
                    break;
                case MIDI_PolyKeyPressure:
                    bufSize += deltaSize(item->time - trackTime);
                    if(lastStatus != item->status)
                    {
                        bufSize += 3;   /* three bytes for poly pressure */
                        lastStatus = item->status;
                    }
                    else
                        bufSize += 2;
                    trackTime = item->time;
                    break;
                case MIDI_ControlChange:
                    switch(item->b1) /* see what type controller we are dealing with */
                    {
                        case AL_MIDI_VOLUME_CTRL:
                        case AL_MIDI_PAN_CTRL:
                        case AL_MIDI_FX_CTRL_0:
                        case AL_MIDI_FX_CTRL_1:
                        case AL_MIDI_FX_CTRL_2:
                        case AL_MIDI_FX_CTRL_3:
                        case AL_MIDI_FX_CTRL_4:
                        case AL_MIDI_FX_CTRL_5:
                        case AL_MIDI_FX_CTRL_6:
                        case AL_MIDI_FX_CTRL_7:
                        case AL_MIDI_FX_CTRL_8:
                        case AL_MIDI_FX_CTRL_9:
                        case AL_MIDI_SUSTAIN_CTRL:
                        case AL_MIDI_FX1_CTRL:
                        case AL_MIDI_FX3_CTRL:
                            bufSize += deltaSize(item->time - trackTime);
                            if(lastStatus != item->status)
                            {
                                bufSize += 3;   /* two bytes for program change */
                                lastStatus = item->status;
                            }
                            else
                                bufSize += 2;
                            trackTime = item->time;
                            break;
                        case AL_CMIDI_CNTRL_LOOPSTART:
                            bufSize += deltaSize(item->time - trackTime);
                            bufSize += 4; 
                            trackTime = item->time; 
                            lastStatus = 0; /* running status not allowed with meta msgs */
                            break; 
                        case AL_CMIDI_CNTRL_LOOPEND:
                            bufSize += deltaSize(item->time - trackTime);
                            bufSize += 8; /* a loopend message is 13 bytes */
                            lastStatus = 0; /* running status not allowed with meta msgs */
                            trackTime = item->time;
                            break;
                    }
                    break;
                case MIDI_ProgramChange:
                    bufSize += deltaSize(item->time - trackTime);
                    if(lastStatus != item->status)
                    {
                        bufSize += 2;   /* two bytes for control change */
                        lastStatus = item->status;
                    }
                    else
                        bufSize += 1;
                    trackTime = item->time;
                    break;
                case MIDI_ChannelPressure:
                    bufSize += deltaSize(item->time - trackTime);
                    if(lastStatus != item->status)
                    {
                        bufSize += 2;   /* two bytes for channel pressure */
                        lastStatus = item->status;
                    }
                    else
                        bufSize += 1;
                    trackTime = item->time;
                    break;
                case MIDI_PitchBendChange:
                    bufSize += deltaSize(item->time - trackTime);
                    if(lastStatus != item->status)
                    {
                        bufSize += 3;   /* three bytes for pitch bend */
                        lastStatus = item->status;
                    }
                    else
                        bufSize += 2;
                    trackTime = item->time;
                    break;
                default:
                    lastStatus = 0;
                    printf("What is a status %x with type %d\n",item->status, item->type);
                    break;
            }
        }
        else if(track == 0 && item->type == META_TYPE)
        {
            bufSize += deltaSize(item->time - trackTime);
            bufSize += 2 + item->len;      /* currently only support tempo events */
            trackTime = item->time;
            lastStatus = 0;
        }
    }

/* OK, should have track size now. */
    
    if(!bufSize && track!=0) /* no events in this track */
    {
        trackSizes[track] = 0;
        trackBufs[track] = 0;
        return;
    }

    if(track == 0 && trackEnd < sequenceEnd)
        trackEnd = sequenceEnd;
    
    if(trackEnd < trackTime)
        trackEnd = trackTime;

    bufSize += deltaSize(trackEnd - trackTime);
    bufSize += 2;  /* add two bytes for end of track */

    trackBuf = (char *)malloc(bufSize);
    if(!trackBuf)
    {
        printf("Out of memory for track%d,  buffer size = %d\n",track,bufSize);
        exit(-1);
    }

    trackTime = 0;  /* reset track time to start of track */
    lastStatus = 0; /* reset running status */

    /* go through and assemble track */
    for (item = list.head; item != 0; item = item->next)
    {
        if(item->type == MIDI_TYPE && (item->status &  MIDI_ChannelMask) == track)
        {
            switch(item->status &  MIDI_StatusMask)
            {
                case MIDI_NoteOn:
                    if(item->dur == 0)
                        printf("ZeroDuration chan %d, key %d, vel %d, time %d\n",
                               item->status & MIDI_ChannelMask,
                               item->b1,item->b2,item->time);
                    else
                    {
                        delta = item->time - trackTime;
                        trackTime = item->time;
                        delta2Buf(trackBuf,&bufOffset,delta);
                        noteOn2Buf(trackBuf,&bufOffset,item);
                    }
                    break;

                case MIDI_ProgramChange:
                case MIDI_ChannelPressure:
                    delta = item->time - trackTime;
                    trackTime = item->time;
                    delta2Buf(trackBuf,&bufOffset,delta);
                    TwoByteMidi2Buf(trackBuf,&bufOffset,item);
                    break;

                case MIDI_PitchBendChange:
                case MIDI_PolyKeyPressure:
                    delta = item->time - trackTime;
                    trackTime = item->time;
                    delta2Buf(trackBuf,&bufOffset,delta);
                    ThreeByteMidi2Buf(trackBuf,&bufOffset,item);
                    break;

                case MIDI_ControlChange:
                    switch(item->b1) /* see what type controller we are dealing with */
                    {
                        case AL_MIDI_VOLUME_CTRL:
                        case AL_MIDI_PAN_CTRL:
                        case AL_MIDI_FX_CTRL_0:
                        case AL_MIDI_FX_CTRL_1:
                        case AL_MIDI_FX_CTRL_2:
                        case AL_MIDI_FX_CTRL_3:
                        case AL_MIDI_FX_CTRL_4:
                        case AL_MIDI_FX_CTRL_5:
                        case AL_MIDI_FX_CTRL_6:
                        case AL_MIDI_FX_CTRL_7:
                        case AL_MIDI_FX_CTRL_8:
                        case AL_MIDI_FX_CTRL_9:
                        case AL_MIDI_SUSTAIN_CTRL:
                        case AL_MIDI_FX1_CTRL:
                        case AL_MIDI_FX3_CTRL:
                            delta = item->time - trackTime;
                            trackTime = item->time;
                            delta2Buf(trackBuf,&bufOffset,delta);
                            ThreeByteMidi2Buf(trackBuf,&bufOffset,item);
                            break;
                        case AL_CMIDI_CNTRL_LOOPSTART:
                            delta = item->time - trackTime;
                            trackTime = item->time;
                            delta2Buf(trackBuf,&bufOffset,delta);
                            loopStart2Buf(trackBuf,&bufOffset,item);
                            break;
                        case AL_CMIDI_CNTRL_LOOPEND:
                            delta = item->time - trackTime;
                            trackTime = item->time;
                            delta2Buf(trackBuf,&bufOffset,delta);
                            loopEnd2Buf(trackBuf,&bufOffset,item,loopCount);
                            break;
                        case AL_CMIDI_CNTRL_LOOPCOUNT_SM:
                            loopCount = item->b2;
                            break;
                        case AL_CMIDI_CNTRL_LOOPCOUNT_BIG:
                            loopCount = item->b2 | BIG_LOOPCOUNT_ADD;
                            break;
                    }
                    break;

                default:
                    lastStatus = 0;
                    printf("Unknown midi status %x\n",item->status & MIDI_StatusMask);
                    break;
            }
        }           /* currently only support meta tempo events */
        else if(track == 0 && item->type == META_TYPE)
        {
            delta = item->time - trackTime;
            trackTime = item->time;
            delta2Buf(trackBuf,&bufOffset,delta);
            meta2Buf(trackBuf,&bufOffset,item); /* tempo only */
        }
    }

    delta = trackEnd - trackTime;
    delta2Buf(trackBuf,&bufOffset,delta);
    trackBuf[bufOffset++] = 0xFF;
    trackBuf[bufOffset++] = 0x2F;

    if(bufOffset != bufSize)
        printf("Buffer size %d but track %d used %d bytes of buffer\n",bufSize,track,bufOffset);

    trackSizes[track] = bufOffset;
    trackBufs[track] = trackBuf;
    return;
}

void MIDIComp::noteOn2Buf(char *trackBuf,long *bufOffset,Node *item)
{
    long  tmpCt = *bufOffset;
    
    if(lastStatus!= item->status)
    {
        trackBuf[tmpCt++] = item->status;
        lastStatus = item->status;
    }
    trackBuf[tmpCt++] = item->b1;
    trackBuf[tmpCt++] = item->b2;

    delta2Buf(trackBuf,&tmpCt,item->dur);

    *bufOffset = tmpCt;
}

void MIDIComp::ThreeByteMidi2Buf(char *trackBuf,long *bufOffset,Node *item)
{
    long  tmpCt = *bufOffset;
            
    if(lastStatus!= item->status)
    {
        trackBuf[tmpCt++] = item->status;
        lastStatus = item->status;
    }
    trackBuf[tmpCt++] = item->b1;
    trackBuf[tmpCt++] = item->b2;
    
    *bufOffset = tmpCt;
}

void MIDIComp::TwoByteMidi2Buf(char *trackBuf,long *bufOffset,Node *item)
{
    long  tmpCt = *bufOffset;

    if(lastStatus!= item->status)
    {
        trackBuf[tmpCt++] = item->status;
        lastStatus = item->status;
    }    
    trackBuf[tmpCt++] = item->b1;

    *bufOffset = tmpCt;
}

/* Currently only support tempo meta events */
void MIDIComp::meta2Buf(char *trackBuf,long *bufOffset,Node *item)
{
    long    i,tmpCt = *bufOffset;
    
    trackBuf[tmpCt++] = (char)0xFF;
    trackBuf[tmpCt++] = (char)item->subtype; /* better be a tempo event */

    for(i=0;i<item->len;i++)
        trackBuf[tmpCt++] = item->data[i];
    
    *bufOffset = tmpCt;
    lastStatus = 0;
}

void MIDIComp::loopStart2Buf(char *trackBuf,long *bufOffset,Node *item)
{
    long  tmpCt = *bufOffset;

    trackBuf[tmpCt++] = (char)0xFF;
    trackBuf[tmpCt++] = (char)AL_CMIDI_LOOPSTART_CODE;
    trackBuf[tmpCt++] = (char)item->b2;
    trackBuf[tmpCt++] = (char)META_PLACEHOLDER;

    *bufOffset = tmpCt;
    lastStatus = 0;
}

void MIDIComp::loopEnd2Buf(char *trackBuf,long *bufOffset,Node *item,long loopCount)
{
    long  tmpCt = *bufOffset;
    
    trackBuf[tmpCt++] = (char)0xFF;
    trackBuf[tmpCt++] = (char)AL_CMIDI_LOOPEND_CODE;
    trackBuf[tmpCt++] = (char)loopCount-1; /* minus one sets to number of times played */
    trackBuf[tmpCt++] = (char)loopCount-1; /* as opposed to number of times to jump back */
    trackBuf[tmpCt++] = (char)item->b2;    /* also makes default, 0, repeat forever */
    trackBuf[tmpCt++] = (char)META_PLACEHOLDER;
    trackBuf[tmpCt++] = (char)META_PLACEHOLDER;
    trackBuf[tmpCt++] = (char)META_PLACEHOLDER;

    *bufOffset = tmpCt;
    lastStatus = 0;
}

void MIDIComp::delta2Buf(char *trackBuf, long *bufOffset, long delta)
{
    unsigned long buffer;
    long   tmpCt = *bufOffset;
    
    buffer = delta & 0x7f;
    while((delta >>= 7) > 0)
    {
        buffer <<= 8;
        buffer |= 0x80;
        buffer += (delta & 0x7f);
    }
    while(1)
    {
        trackBuf[tmpCt++] = (char) (buffer & 0xFF);
       
        if(buffer & 0x80)
            buffer >>= 8;
        else
            break;
    }

    *bufOffset = tmpCt;
}

long MIDIComp::deltaSize(long delta)
{
    if(delta <= 0x0000007F)
        return 1;
    if(delta <= 0x00003FFF)
        return 2;
    if(delta <= 0x001FFFFF)
        return 3;
    return 4;
}

long MIDIComp::matchPattern(char *test, char *tryPtr)
{
    long res = 0;

    /* Don't match with META_PLACEHOLDER, these are bytes that serve
       as place holders and can change during playback!  */
    while(test[res] == tryPtr[res] && test[res] != META_PLACEHOLDER)
        res++;

    return res;
}

char *MIDIComp::CopyData(char *src, char *dst, long len)
{
    long  i;
    
    for(i=0;i<len;i++)
    {
        if(*src!=AL_CMIDI_BLOCK_CODE)
            *dst++ = *src++;
        else    /* if it's a block code, repeat it */
        {
            *dst++ = *src;
            *dst++ = *src++;
        }
    }
    return dst;
}

#define HASH_MIN_SIZE    0x100 /* must be a value with only one bit set */

long MIDIComp::HashSize(long numObjs)
{
    long     size = HASH_MIN_SIZE;
    long     hashSize = numObjs * 2;

    while(hashSize > size)
        size = size << 1;

    hashMask = size - 1;
    
    return size;
}

#define BIG_PRIME  33554393
long MIDIComp::HashString(char *str, long hashMask)
{
    long  hash = 1, i;

    for(i = 0; i<MIN_MATCH_SIZE; i++)
    {
        hash = (BIG_PRIME * hash) + str[i];
        hash = hash & hashMask;
    }
    return hash;
}

                    
       
void MIDIList::endNote(long time, char chan, char key)
{
    Node *node;
    int     found = 0;

    chan = chan | 0x90; /* or in midi note on value */
    
    if(head == 0 || tail == 0)
    {
        printf("no head tail error\n");
        return;
    }

    node = tail;

    while(node != 0)
    {
        if(node->time < time && node->status == chan && node->b1 == key  && node->dur==0)
        {
            found = 1;
            node->dur = time - node->time;
            break;
        }
        else
            node = node->prev;
    }

    if(!found)
        printf("Didn't match note off to note on. status = 0x%x, key %d, noteoff time %d\n",chan,key,time);

}