/* $NetBSD: midiplay.c,v 1.34 2021/11/27 22:16:41 rillig Exp $ */ /* * Copyright (c) 1998, 2002 The NetBSD Foundation, Inc. * All rights reserved. * * This code is derived from software contributed to The NetBSD Foundation * by Lennart Augustsson (augustss@NetBSD.org). * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice, this list of conditions and the following disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE * POSSIBILITY OF SUCH DAMAGE. */ #include #ifndef lint __RCSID("$NetBSD: midiplay.c,v 1.34 2021/11/27 22:16:41 rillig Exp $"); #endif #include #include #include #include #include #include #include #include #include #include #include #include #define DEVMUSIC "/dev/music" struct track { struct track *indirect; /* for fast swaps in heap code */ u_char *start, *end; u_long delta; u_char status; }; #define MIDI_META 0xff #define META_SEQNO 0x00 #define META_TEXT 0x01 #define META_COPYRIGHT 0x02 #define META_TRACK 0x03 #define META_INSTRUMENT 0x04 #define META_LYRIC 0x05 #define META_MARKER 0x06 #define META_CUE 0x07 #define META_CHPREFIX 0x20 #define META_EOT 0x2f #define META_SET_TEMPO 0x51 #define META_KEY 0x59 #define META_SMPTE 0x54 #define META_TIMESIGN 0x58 static const char *metanames[] = { "", "Text", "Copyright", "Track", "Instrument", "Lyric", "Marker", "Cue", }; static int midi_lengths[] = { 2, 2, 2, 2, 1, 1, 2, 0 }; /* Number of bytes in a MIDI command */ #define MIDI_LENGTH(d) (midi_lengths[((d) >> 4) & 7]) #define SEQ_MK_SYSEX0(_dev,...) \ SEQ_MK_EVENT(sysex, 0x94, .device=(_dev), .buffer={__VA_ARGS__}) static void usage(void); static void send_event(seq_event_t *); static void dometa(u_int, u_char *, u_int); #if 0 static void midireset(void); #endif static void send_sysex(u_char *, u_int); static u_long getvar(struct track *); static u_long getlen(struct track *); static void playfile(FILE *, const char *); static void playdata(u_char *, u_int, const char *); static void Heapify(struct track *, int, int); static void BuildHeap(struct track *, int); static int ShrinkHeap(struct track *, int); /* * This sample plays at an apparent tempo of 120 bpm when the BASETEMPO is 150 * bpm, because the quavers are 5 divisions (4 on 1 off) rather than 4 total. */ #define P(c) 1, 0x90, c, 0x7f, 4, 0x80, c, 0 #define PL(c) 1, 0x90, c, 0x7f, 8, 0x80, c, 0 #define C 0x3c #define D 0x3e #define E 0x40 #define F 0x41 static u_char sample[] = { 'M', 'T', 'h', 'd', 0, 0, 0, 6, 0, 1, 0, 1, 0, 8, 'M', 'T', 'r', 'k', 0, 0, 0, 4+13*8, P(C), P(C), P(C), P(E), P(D), P(D), P(D), P(F), P(E), P(E), P(D), P(D), PL(C), 0, 0xff, 0x2f, 0 }; #undef P #undef PL #undef C #undef D #undef E #undef F static u_char silence_sample[] = { 'M', 'T', 'h', 'd', 0, 0, 0, 6, 0, 1, 0, 1, 0, 8, 'M', 'T', 'r', 'k', 0, 0, 0, 8, 0, 0xb0, 0x78, 0x00, 0, 0xff, 0x2f, 0 }; #define MARK_HEADER "MThd" #define MARK_TRACK "MTrk" #define MARK_LEN 4 #define RMID_SIG "RIFF" #define RMID_MIDI_ID "RMID" #define RMID_DATA_ID "data" #define SIZE_LEN 4 #define HEADER_LEN 6 #define GET8(p) ((p)[0]) #define GET16(p) (((p)[0] << 8) | (p)[1]) #define GET24(p) (((p)[0] << 16) | ((p)[1] << 8) | (p)[2]) #define GET32(p) (((p)[0] << 24) | ((p)[1] << 16) | ((p)[2] << 8) | (p)[3]) #define GET32_LE(p) (((p)[3] << 24) | ((p)[2] << 16) | ((p)[1] << 8) | (p)[0]) static void __attribute__((__noreturn__)) usage(void) { fprintf(stderr, "usage: %s [-lmqsvx] [-d devno] [-f file] " "[-p pgm] [-t tempo] [file ...]\n", getprogname()); exit(1); } static int showmeta = 0; static int verbose = 0; #define BASETEMPO 400000 /* us/beat(=24 clks or qn) (150 bpm) */ static u_int tempo_set = 0; static u_int tempo_abs = 0; static u_int ttempo = 100; static int unit = 0; static int play = 1; static int fd = -1; static int sameprogram = 0; static int insysex = 0; static int svsysex = 0; /* number of sysex bytes saved internally */ static void send_event(seq_event_t *ev) { /* printf("%02x %02x %02x %02x %02x %02x %02x %02x\n", ev->arr[0], ev->arr[1], ev->arr[2], ev->arr[3], ev->arr[4], ev->arr[5], ev->arr[6], ev->arr[7]); */ if (play) write(fd, ev, sizeof *ev); } static u_long getvar(struct track *tp) { u_long r, c; r = 0; do { c = *tp->start++; r = (r << 7) | (c & 0x7f); } while ((c & 0x80) && tp->start < tp->end); return r; } static u_long getlen(struct track *tp) { u_long len; len = getvar(tp); if (tp->start + len > tp->end) errx(1, "bogus item length exceeds remaining track size"); return len; } static void dometa(u_int meta, u_char *p, u_int len) { static char const * const keys[] = { "Cb", "Gb", "Db", "Ab", "Eb", "Bb", "F", "C", "G", "D", "A", "E", "B", "F#", "C#", "G#", "D#", "A#" /* for minors */ }; seq_event_t ev; uint32_t usperbeat; switch (meta) { case META_TEXT: case META_COPYRIGHT: case META_TRACK: case META_INSTRUMENT: case META_LYRIC: case META_MARKER: case META_CUE: if (showmeta) { printf("%s: ", metanames[meta]); fwrite(p, len, 1, stdout); printf("\n"); } break; case META_SET_TEMPO: usperbeat = GET24(p); ev = SEQ_MK_TIMING(TEMPO, .bpm=(60000000. / usperbeat) * (ttempo / 100.) + 0.5); if (showmeta) printf("Tempo: %u us/'beat'(24 midiclks)" " at %u%%; adjusted bpm = %u\n", usperbeat, ttempo, ev.t_TEMPO.bpm); if (tempo_abs) warnx("tempo event ignored" " in absolute-timed MIDI file"); else { send_event(&ev); if (!tempo_set) { tempo_set = 1; send_event(&SEQ_MK_TIMING(START)); } } break; case META_TIMESIGN: ev = SEQ_MK_TIMING(TIMESIG, .numerator=p[0], .lg2denom=p[1], .clks_per_click=p[2], .dsq_per_24clks=p[3]); if (showmeta) { printf("Time signature: %d/%d." " Click every %d midiclk%s" " (24 midiclks = %d 32nd note%s)\n", ev.t_TIMESIG.numerator, 1 << ev.t_TIMESIG.lg2denom, ev.t_TIMESIG.clks_per_click, 1 == ev.t_TIMESIG.clks_per_click ? "" : "s", ev.t_TIMESIG.dsq_per_24clks, 1 == ev.t_TIMESIG.dsq_per_24clks ? "" : "s"); } /* send_event(&ev); not implemented in sequencer */ break; case META_KEY: if (showmeta) printf("Key: %s %s\n", keys[((char)p[0]) + p[1] ? 10 : 7], p[1] ? "minor" : "major"); break; default: break; } } #if 0 static void midireset(void) { /* General MIDI reset sequence */ send_event(&SEQ_MK_SYSEX0(unit, 0x7e, 0x7f, 0x09, 0x01, 0xf7, 0xff)); } #endif #define SYSEX_CHUNK 6 static void send_sysex(u_char *p, u_int l) { seq_event_t event; static u_char bf[6]; if (0 == l) { warnx("zero-length system-exclusive event"); return; } /* * This block is needed only to handle the possibility that a sysex * message is broken into multiple events in a MIDI file that do not * have length six; the /dev/music sequencer assumes a sysex message is * finished with the first SYSEX event carrying fewer than six bytes, * even if the last is not MIDI_SYSEX_END. So, we need to be careful * not to send a short sysex event until we have seen the end byte. * Instead, save some straggling bytes in bf, and send when we have a * full six (or an end byte). Note bf/saved/insysex should be per- * device, if we supported output to more than one device at a time. */ if (svsysex > 0) { if (l > sizeof bf - svsysex) { memcpy(bf + svsysex, p, sizeof bf - svsysex); l -= sizeof bf - svsysex; p += sizeof bf - svsysex; send_event(&SEQ_MK_SYSEX0(unit, bf[0], bf[1], bf[2], bf[3], bf[4], bf[5])); svsysex = 0; } else { memcpy(bf + svsysex, p, l); svsysex += l; p += l; if (MIDI_SYSEX_END == bf[svsysex-1]) { event = SEQ_MK_SYSEX(unit); memcpy(event.sysex.buffer, bf, svsysex); send_event(&event); svsysex = insysex = 0; } else insysex = 1; return; } } /* * l > 0. May as well test now whether we will be left 'insysex' * after processing this event. */ insysex = (MIDI_SYSEX_END != p[l-1]); /* * If not for multi-event sysexes and chunk-size weirdness, this * function could pretty much start here. :) */ while (l >= SYSEX_CHUNK) { send_event(&SEQ_MK_SYSEX0(unit, p[0], p[1], p[2], p[3], p[4], p[5])); p += SYSEX_CHUNK; l -= SYSEX_CHUNK; } if (l > 0) { if (insysex) { memcpy(bf, p, l); svsysex = l; } else { /* a <6 byte chunk is ok if it's REALLY the end */ event = SEQ_MK_SYSEX(unit); memcpy(event.sysex.buffer, p, l); send_event(&event); } } } static void playfile(FILE *f, const char *name) { u_char *buf, *nbuf; u_int tot, n, size, nread; /* * We need to read the whole file into memory for easy processing. * Using mmap() would be nice, but some file systems do not support * it, nor does reading from e.g. a pipe. The latter also precludes * finding out the file size without reading it. */ size = 1000; buf = malloc(size); if (buf == 0) errx(1, "malloc() failed"); nread = size; tot = 0; for (;;) { n = fread(buf + tot, 1, nread, f); tot += n; if (n < nread) break; /* There must be more to read. */ nread = size; nbuf = realloc(buf, size * 2); if (nbuf == NULL) errx(1, "realloc() failed"); buf = nbuf; size *= 2; } playdata(buf, tot, name); free(buf); } static void playdata(u_char *buf, u_int tot, const char *name) { int format, ntrks, divfmt, ticks, t; u_int len, mlen, status, chan; u_char *p, *end, byte, meta, *msg; struct synth_info info; struct track *tracks; struct track *tp; /* verify that the requested midi unit exists */ info.device = unit; if (play && ioctl(fd, SEQUENCER_INFO, &info) < 0) err(1, "ioctl(SEQUENCER_INFO) failed"); end = buf + tot; if (verbose) { printf("Playing %s (%d bytes)", name, tot); if (play) printf(" on %s (unit %d)...", info.name, info.device); puts("\n"); } if (tot < MARK_LEN + 4) { warnx("Not a MIDI file, too short"); return; } if (memcmp(buf, RMID_SIG, MARK_LEN) == 0) { u_char *eod; /* Detected a RMID file, let's just check if it's * a MIDI file */ if ((u_int)GET32_LE(buf + MARK_LEN) != tot - 8) { warnx("Not a RMID file, bad header"); return; } buf += MARK_LEN + 4; if (memcmp(buf, RMID_MIDI_ID, MARK_LEN) != 0) { warnx("Not a RMID file, bad ID"); return; } /* Now look for the 'data' chunk, which contains * MIDI data */ buf += MARK_LEN; /* Test against end-8 since we must have at least 8 bytes * left to read */ while(buf < end-8 && memcmp(buf, RMID_DATA_ID, MARK_LEN)) buf += GET32_LE(buf+4) + 8; /* MARK_LEN + 4 */ if (buf >= end-8) { warnx("Not a valid RMID file, no data chunk"); return; } buf += MARK_LEN; /* "data" */ eod = buf + 4 + GET32_LE(buf); if (eod >= end) { warnx("Not a valid RMID file, bad data chunk size"); return; } end = eod; buf += 4; } if (memcmp(buf, MARK_HEADER, MARK_LEN) != 0) { warnx("Not a MIDI file, missing header"); return; } if (GET32(buf + MARK_LEN) != HEADER_LEN) { warnx("Not a MIDI file, bad header"); return; } format = GET16(buf + MARK_LEN + SIZE_LEN); ntrks = GET16(buf + MARK_LEN + SIZE_LEN + 2); divfmt = GET8(buf + MARK_LEN + SIZE_LEN + 4); ticks = GET8(buf + MARK_LEN + SIZE_LEN + 5); p = buf + MARK_LEN + SIZE_LEN + HEADER_LEN; /* * Set the timebase (or timebase and tempo, for absolute-timed files). * PORTABILITY: some sequencers actually check the timebase against * available timing sources and may adjust it accordingly (storing a * new value in the ioctl arg) which would require us to compensate * somehow. That possibility is ignored for now, as NetBSD's sequencer * currently synthesizes all timebases, for better or worse, from the * system clock. * * For a non-absolute file, if timebase is set to the file's divisions * value, and tempo set in the obvious way, then the timing deltas in * the MTrks require no scaling. A downside to this approach is that * the sequencer API wants tempo in (integer) beats per minute, which * limits how finely tempo can be specified. That might be got around * in some cases by frobbing tempo and timebase more obscurely, but this * player is meant to be simple and clear. */ if (!play) /* do nothing */; else if ((divfmt & 0x80) == 0) { ticks |= divfmt << 8; if (ioctl(fd, SEQUENCER_TMR_TIMEBASE, &(int){ticks}) < 0) err(1, "SEQUENCER_TMR_TIMEBASE"); } else { tempo_abs = tempo_set = 1; divfmt = -(int8_t)divfmt; /* * divfmt is frames per second; multiplying by 60 to set tempo * in frames per minute could exceed sequencer's (arbitrary) * tempo limits, so factor 60 as 12*5, set tempo in frames per * 12 seconds, and account for the 5 in timebase. */ send_event(&SEQ_MK_TIMING(TEMPO, .bpm=(12*divfmt) * (ttempo/100.) + 0.5)); if (ioctl(fd, SEQUENCER_TMR_TIMEBASE, &(int){5*ticks}) < 0) err(1, "SEQUENCER_TMR_TIMEBASE"); } if (verbose > 1) printf(tempo_abs ? "format=%d ntrks=%d abs fps=%u subdivs=%u\n" : "format=%d ntrks=%d divisions=%u\n", format, ntrks, tempo_abs ? divfmt : ticks, ticks); if (format != 0 && format != 1) { warnx("Cannot play MIDI file of type %d", format); return; } if (ntrks == 0) return; tracks = malloc(ntrks * sizeof(struct track)); if (tracks == NULL) errx(1, "malloc() tracks failed"); for (t = 0; t < ntrks;) { if (p >= end - MARK_LEN - SIZE_LEN) { warnx("Cannot find track %d", t); goto ret; } len = GET32(p + MARK_LEN); if (len > 1000000) { /* a safe guard */ warnx("Crazy track length"); goto ret; } if (memcmp(p, MARK_TRACK, MARK_LEN) == 0) { tracks[t].start = p + MARK_LEN + SIZE_LEN; tracks[t].end = tracks[t].start + len; tracks[t].delta = getvar(&tracks[t]); tracks[t].indirect = &tracks[t]; /* -> self for now */ t++; } p += MARK_LEN + SIZE_LEN + len; } /* * Force every channel to the same patch if requested by the user. */ if (sameprogram) { for(t = 0; t < 16; t++) { send_event(&SEQ_MK_CHN(PGM_CHANGE, .device=unit, .channel=t, .program=sameprogram-1)); } } /* * Play MIDI events by selecting the track with the lowest * delta. Execute the event, update the delta and repeat. * * The ticks variable is the number of ticks that make up a beat * (beat: 24 MIDI clocks always, a quarter note by usual convention) * and is used as a reference value for the delays between * the MIDI events. */ BuildHeap(tracks, ntrks); /* tracks[0].indirect is always next */ for (;;) { tp = tracks[0].indirect; if ((verbose > 2 && tp->delta > 0) || verbose > 3) { printf("DELAY %4ld TRACK %2td%s", tp->delta, tp - tracks, verbose>3?" ":"\n"); fflush(stdout); } if (tp->delta > 0) { if (!tempo_set) { if (verbose || showmeta) printf("No initial tempo;" " defaulting:\n"); dometa(META_SET_TEMPO, (u_char[]){ BASETEMPO >> 16, (BASETEMPO >> 8) & 0xff, BASETEMPO & 0xff}, 3); } send_event(&SEQ_MK_TIMING(WAIT_REL, .divisions=tp->delta)); } byte = *tp->start++; if (byte == MIDI_META) { meta = *tp->start++; mlen = getlen(tp); if (verbose > 3) printf("META %02x (%d)\n", meta, mlen); dometa(meta, tp->start, mlen); tp->start += mlen; } else { if (MIDI_IS_STATUS(byte)) tp->status = byte; else tp->start--; mlen = MIDI_LENGTH(tp->status); msg = tp->start; if (verbose > 3) { if (mlen == 1) printf("MIDI %02x (%d) %02x\n", tp->status, mlen, msg[0]); else printf("MIDI %02x (%d) %02x %02x\n", tp->status, mlen, msg[0], msg[1]); } if (insysex && tp->status != MIDI_SYSEX_END) { warnx("incomplete system exclusive message" " aborted"); svsysex = insysex = 0; } status = MIDI_GET_STATUS(tp->status); chan = MIDI_GET_CHAN(tp->status); switch (status) { case MIDI_NOTEOFF: send_event(&SEQ_MK_CHN(NOTEOFF, .device=unit, .channel=chan, .key=msg[0], .velocity=msg[1])); break; case MIDI_NOTEON: send_event(&SEQ_MK_CHN(NOTEON, .device=unit, .channel=chan, .key=msg[0], .velocity=msg[1])); break; case MIDI_KEY_PRESSURE: send_event(&SEQ_MK_CHN(KEY_PRESSURE, .device=unit, .channel=chan, .key=msg[0], .pressure=msg[1])); break; case MIDI_CTL_CHANGE: send_event(&SEQ_MK_CHN(CTL_CHANGE, .device=unit, .channel=chan, .controller=msg[0], .value=msg[1])); break; case MIDI_PGM_CHANGE: if (!sameprogram) send_event(&SEQ_MK_CHN(PGM_CHANGE, .device=unit, .channel=chan, .program=msg[0])); break; case MIDI_CHN_PRESSURE: send_event(&SEQ_MK_CHN(CHN_PRESSURE, .device=unit, .channel=chan, .pressure=msg[0])); break; case MIDI_PITCH_BEND: send_event(&SEQ_MK_CHN(PITCH_BEND, .device=unit, .channel=chan, .value=(msg[0] & 0x7f) | ((msg[1] & 0x7f)<<7))); break; case MIDI_SYSTEM_PREFIX: mlen = getlen(tp); if (tp->status == MIDI_SYSEX_START) { send_sysex(tp->start, mlen); break; } else if (tp->status == MIDI_SYSEX_END) { /* SMF uses SYSEX_END as CONTINUATION/ESCAPE */ if (insysex) { /* CONTINUATION */ send_sysex(tp->start, mlen); } else { /* ESCAPE */ for (; mlen > 0 ; -- mlen) { send_event( &SEQ_MK_EVENT(putc, SEQOLD_MIDIPUTC, .device=unit, .byte=*(tp->start++) )); } } break; } /* Sorry, can't do this yet */ /* FALLTHROUGH */ default: if (verbose) printf("MIDI event 0x%02x ignored\n", tp->status); } tp->start += mlen; } if (tp->start >= tp->end) { ntrks = ShrinkHeap(tracks, ntrks); /* track gone */ if (0 == ntrks) break; } else tp->delta = getvar(tp); Heapify(tracks, ntrks, 0); } if (play && ioctl(fd, SEQUENCER_SYNC, 0) < 0) err(1, "SEQUENCER_SYNC"); ret: free(tracks); } static int parse_unit(const char *sunit) { const char *osunit = sunit; long n; char *ep; if (strncmp(sunit, "midi", strlen("midi")) == 0) sunit += strlen("midi"); errno = 0; n = strtol(sunit, &ep, 10); if (n < 0 || n > INT_MAX || *ep != '\0' || (errno == ERANGE && (n == LONG_MAX || n == LONG_MIN))) errx(1, "bad midi unit -- %s", osunit); return (int)n; } int main(int argc, char **argv) { int ch; int listdevs = 0; int example = 0; int silence = 0; int nmidi; const char *file = DEVMUSIC; const char *sunit; struct synth_info info; FILE *f; if ((sunit = getenv("MIDIUNIT"))) unit = parse_unit(sunit); while ((ch = getopt(argc, argv, "?d:f:lmp:qst:vx")) != -1) { switch(ch) { case 'd': unit = parse_unit(optarg); break; case 'f': file = optarg; break; case 'l': listdevs++; break; case 'm': showmeta++; break; case 'p': sameprogram = atoi(optarg); break; case 'q': play = 0; break; case 's': silence++; break; case 't': ttempo = atoi(optarg); break; case 'v': verbose++; break; case 'x': example++; break; case '?': default: usage(); } } argc -= optind; argv += optind; if (!play) goto output; fd = open(file, O_WRONLY); if (fd < 0) err(1, "%s", file); if (ioctl(fd, SEQUENCER_NRMIDIS, &nmidi) < 0) err(1, "ioctl(SEQUENCER_NRMIDIS) failed, "); if (nmidi == 0) errx(1, "Sorry, no MIDI devices available"); if (listdevs) { for (info.device = 0; info.device < nmidi; info.device++) { if (ioctl(fd, SEQUENCER_INFO, &info) < 0) err(1, "ioctl(SEQUENCER_INFO) failed, "); printf("%d: %s\n", info.device, info.name); } exit(0); } output: if (example) while (example--) playdata(sample, sizeof sample, ""); else if (silence) while (silence--) playdata(silence_sample, sizeof silence_sample, ""); else if (argc == 0) playfile(stdin, ""); else while (argc--) { f = fopen(*argv, "r"); if (f == NULL) err(1, "%s", *argv); else { playfile(f, *argv); fclose(f); } argv++; } exit(0); } /* * relative-time priority queue (min-heap). Properties: * 1. The delta time at a node is relative to the node's parent's time. * 2. When an event is dequeued from a track, the delta time of the new head * event is relative to the time of the event just dequeued. * Therefore: * 3. After dequeueing the head event from the track at heap root, the next * event's time is directly comparable to the root's children. * These properties allow the heap to be maintained with delta times throughout. * Insert is also implementable, but not needed: all the tracks are present * at first; they just go away as they end. */ #define PARENT(i) ((i - 1) >> 1) #define LEFT(i) ((i << 1) + 1) #define RIGHT(i) ((i + 1) << 1) #define DTIME(i) (t[i].indirect->delta) #define SWAP(i, j) do { \ struct track *_t = t[i].indirect; \ t[i].indirect = t[j].indirect; \ t[j].indirect = _t; \ } while (0) static void Heapify(struct track *t, int ntrks, int node) { int lc, rc, mn; lc = LEFT(node); rc = RIGHT(node); if (rc >= ntrks) { /* no right child */ if (lc >= ntrks) /* node is a leaf */ return; if (DTIME(node) > DTIME(lc)) SWAP(node, lc); DTIME(lc) -= DTIME(node); return; /* no rc ==> lc is a leaf */ } mn = lc; if (DTIME(lc) > DTIME(rc)) mn = rc; if (DTIME(node) <= DTIME(mn)) { DTIME(rc) -= DTIME(node); DTIME(lc) -= DTIME(node); return; } SWAP(node, mn); DTIME(rc) -= DTIME(node); DTIME(lc) -= DTIME(node); Heapify(t, ntrks, mn); /* gcc groks tail recursion */ } static void BuildHeap(struct track *t, int ntrks) { int node; for (node = PARENT(ntrks - 1); node --> 0;) Heapify(t, ntrks, node); } /* * Make the heap 1 item smaller by discarding the track at the root. Move the * rightmost bottom-level leaf to the root and decrement ntrks. It remains to * run Heapify, which the caller is expected to do. Returns the new ntrks. */ static int ShrinkHeap(struct track *t, int ntrks) { int ancest; --ntrks; for (ancest = PARENT(ntrks); ancest > 0; ancest = PARENT(ancest)) DTIME(ntrks) += DTIME(ancest); t[0].indirect = t[ntrks].indirect; return ntrks; }