sys/dev/midictl.c

   1 /* $NetBSD: midictl.c,v 1.5 2008/04/28 20:23:47 martin Exp $ */
   2
   3 /*-
   4  * Copyright (c) 2006 The NetBSD Foundation, Inc.
   5  * All rights reserved.
   6  *
   7  * This code is derived from software contributed to The NetBSD Foundation
   8  * by Chapman Flack.
   9  *
  10  * Redistribution and use in source and binary forms, with or without
  11  * modification, are permitted provided that the following conditions
  12  * are met:
  13  * 1. Redistributions of source code must retain the above copyright
  14  *    notice, this list of conditions and the following disclaimer.
  15  * 2. Redistributions in binary form must reproduce the above copyright
  16  *    notice, this list of conditions and the following disclaimer in the
  17  *    documentation and/or other materials provided with the distribution.
  18  *
  19  * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
  20  * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  21  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  22  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
  23  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
  24  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
  25  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
  26  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
  27  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  28  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  29  * POSSIBILITY OF SUCH DAMAGE.
  30  */
  31 #include <sys/cdefs.h>
  32 __KERNEL_RCSID(0, "$NetBSD: midictl.c,v 1.5 2008/04/28 20:23:47 martin Exp $");
  33
  34 /*
  35  * See midictl.h for an overview of the purpose and use of this module.
  36  */
  37
  38 #if defined(_KERNEL)
  39 #define _MIDICTL_ASSERT(x) KASSERT(x)
  40 #define _MIDICTL_MALLOC(s,t) malloc((s), (t), M_WAITOK)
  41 #define _MIDICTL_ZMALLOC(s,t) malloc((s), (t), M_WAITOK|M_ZERO)
  42 #define _MIDICTL_IMZMALLOC(s,t) malloc((s), (t), M_NOWAIT|M_ZERO)
  43 #define _MIDICTL_PANIC(...) panic(__VA_ARGS__)
  44 #define _MIDICTL_FREE(s,t) free((s), (t))
  45 #include <sys/systm.h>
  46 #include <sys/types.h>
  47 #else
  48 #include <assert.h>
  49 #include <err.h>
  50 #include <inttypes.h>
  51 #include <stdio.h>
  52 #include <stdlib.h>
  53 #define _MIDICTL_ASSERT(x) assert(x)
  54 #define _MIDICTL_MALLOC(s,t) malloc((s))
  55 #define _MIDICTL_ZMALLOC(s,t) calloc(1,(s))
  56 #define _MIDICTL_IMZMALLOC(s,t) calloc(1,(s))
  57 #define _MIDICTL_PANIC(...) errx(1,__VA_ARGS__)
  58 #define _MIDICTL_FREE(s,t) free((s))
  59 #endif
  60
  61 #include "midictl.h"
  62
  63 /*
  64  * The upper part of this file is MIDI-aware, and deals with things like
  65  * decoding MIDI Control Change messages, dealing with the ones that require
  66  * special handling as mode messages or parameter updates, and so on.
  67  *
  68  * It relies on a "store" layer (implemented in the lower part of this file)
  69  * that only must be able to stash away 2-, 8-, or 16-bit quantities (which
  70  * it may pack into larger units as it sees fit) and find them again given
  71  * a class, channel, and key (controller/parameter number).
  72  *
  73  * The MIDI controllers can have 1-, 7-, or 14-bit values; the parameters are
  74  * also 14-bit. The 14-bit values have to be set in two MIDI messages, 7 bits
  75  * at a time. The MIDI layer uses store-managed 2- or 8-bit slots for the
  76  * smaller types, and uses the free high bit to indicate that it has explicitly
  77  * set the value. (Because the store is allowed to pack things, it may 'find'
  78  * a zero entry for a value we never set, because it shares a word with a
  79  * different value that has been set. We know it is not a real value because
  80  * the high bit is clear.)
  81  *
  82  * The 14-bit values are handled similarly: 16-bit store slots are used to hold
  83  * them, with the two free high bits indicating independently whether the MSB
  84  * and the LSB have been explicitly set--as two separate MIDI messages are
  85  * required. If such a control is queried when only one half has been explicitly
  86  * set, the result is as if it had been set to the specified default value
  87  * before the explicit set.
  88  */
  89
  90 typedef enum { CTL1, CTL7, CTL14, RPN, NRPN } class;
  91
  92 /*
  93  * assert(does_not_apply(KNFNamespaceArgumentAgainstNamesInPrototypes,
  94  *    PrototypesOfStaticFunctionsWithinNonIncludedFile));
  95  */
  96 static void reset_all_controllers(midictl *mc, uint_fast8_t chan);
  97 static void enter14(midictl *mc, uint_fast8_t chan, class c,
  98                     uint_fast16_t key, _Bool islsb, uint8_t val);
  99 static uint_fast16_t read14(midictl *mc, uint_fast8_t chan, class c,
 100                             uint_fast16_t key, uint_fast16_t dflt);
 101 static class classify(uint_fast16_t *key, _Bool *islsb);
 102 static midictl_notify notify_no_one;
 103
 104 static midictl_store *store_init(void);
 105 static void store_done(midictl_store *s);
 106 static _Bool store_locate(midictl_store *s, class c,
 107                             uint_fast8_t chan, uint_fast16_t key);
 108 /*
 109  * store_extract and store_update operate on the bucket most recently found
 110  * by store_locate on this store. That works because reentrancy of midictl
 111  * functions is limited: they /can/ be reentered during midictl_notify
 112  * callbacks, but not at other arbitrary times. We never call notify /during/
 113  * a locate/extract/update transaction.
 114  */
 115 static uint16_t store_extract(midictl_store *s, class c,
 116                               uint_fast8_t chan, uint_fast16_t key);
 117 static void store_update(midictl_store *s, class c,
 118                          uint_fast8_t chan, uint_fast16_t key, uint16_t value);
 119
 120 #define PN_SET 0x8000  /* a parameter number has been explicitly set */
 121 #define C14MSET 0x8000 /* MSB of a 14-bit val has been set */
 122 #define C14LSET 0x4000 /* LSB of a 14-bit val has been set */
 123 #define C7_SET 0x80    /* a 7-bit ctl has been set */
 124 #define C1_SET 2       /* a 1-bit ctl has been set */
 125
 126 #if defined(_MIDICTL_MAIN)
 127 #define XS(s) [MIDICTL_##s]=#s
 128 char const * const evt_strings[] = {
 129         XS(CTLR), XS(RPN), XS(NRPN), XS(RESET), XS(NOTES_OFF),
 130         XS(SOUND_OFF), XS(LOCAL), XS(MODE)
 131 };
 132 #undef XS
 133
 134 void
 135 dbgnotify(void *cookie, midictl_evt e, uint_fast8_t chan, uint_fast16_t key)
 136 {
 137         printf("NFY %p %s chan %u #%u\n", cookie, evt_strings[e], chan, key);
 138 }
 139
 140 midictl mc = {
 141         .accept_any_ctl_rpn = 0,
 142         .accept_any_nrpn = 0,
 143         .base_channel = 16,
 144         .cookie = NULL,
 145         .notify = dbgnotify
 146 };
 147
 148 int
 149 main(int argc, char **argv)
 150 {
 151         int cnt, a, b, c;
 152
 153         midictl_open(&mc);
 154         do {
 155                 cnt = scanf("%i %i %i", &a, &b, &c);
 156                 if ( 3 == cnt ) {
 157                         midictl_change(&mc, a, (uint8_t[]){b,c});
 158                 }
 159         } while ( EOF != cnt );
 160         midictl_close(&mc);
 161         return 0;
 162 }
 163 #endif /* defined(_MIDICTL_MAIN) */
 164
 165 void
 166 midictl_open(midictl *mc)
 167 {
 168         if ( NULL == mc->notify )
 169                 mc->notify = notify_no_one;
 170         mc->store = store_init();
 171 }
 172
 173 void
 174 midictl_close(midictl *mc)
 175 {
 176         store_done(mc->store);
 177 }
 178
 179 void
 180 midictl_change(midictl *mc, uint_fast8_t chan, uint8_t *ctlval)
 181 {
 182         class c;
 183         uint_fast16_t key, val;
 184         _Bool islsb, present;
 185
 186         switch ( ctlval[0] ) {
 187         /*
 188          * Channel mode messages:
 189          */
 190         case MIDI_CTRL_OMNI_OFF:
 191         case MIDI_CTRL_OMNI_ON:
 192         case MIDI_CTRL_POLY_OFF:
 193         case MIDI_CTRL_POLY_ON:
 194                 if ( chan != mc->base_channel )
 195                         return; /* ignored - not on base channel */
 196                 else
 197                         return; /* XXX ignored anyway - not implemented yet */
 198         case MIDI_CTRL_NOTES_OFF:
 199                 mc->notify(mc->cookie, MIDICTL_NOTES_OFF, chan, 0);
 200                 return;
 201         case MIDI_CTRL_LOCAL:
 202                 mc->notify(mc->cookie, MIDICTL_LOCAL, chan, ctlval[1]);
 203                 return;
 204         case MIDI_CTRL_SOUND_OFF:
 205                 mc->notify(mc->cookie, MIDICTL_SOUND_OFF, chan, 0);
 206                 return;
 207         case MIDI_CTRL_RESET:
 208                 reset_all_controllers(mc, chan);
 209                 return;
 210         /*
 211          * Control changes to be handled specially:
 212          */
 213         case MIDI_CTRL_RPN_LSB:
 214                 mc-> rpn &= ~0x7f;
 215                 mc-> rpn |=  PN_SET | (0x7f & ctlval[1]);
 216                 mc->nrpn &= ~PN_SET;
 217                 return;
 218         case MIDI_CTRL_RPN_MSB:
 219                 mc-> rpn &= ~0x7f<<7;
 220                 mc-> rpn |=  PN_SET | (0x7f & ctlval[1])<<7;
 221                 mc->nrpn &= ~PN_SET;
 222                 return;
 223         case MIDI_CTRL_NRPN_LSB:
 224                 mc->nrpn &= ~0x7f;
 225                 mc->nrpn |=  PN_SET | (0x7f & ctlval[1]);
 226                 mc-> rpn &= ~PN_SET;
 227                 return;
 228         case MIDI_CTRL_NRPN_MSB:
 229                 mc->nrpn &= ~0x7f<<7;
 230                 mc->nrpn |=  PN_SET | (0x7f & ctlval[1])<<7;
 231                 mc-> rpn &= ~PN_SET;
 232                 return;
 233         case MIDI_CTRL_DATA_ENTRY_LSB:
 234                 islsb = 1;
 235                 goto whichparm;
 236         case MIDI_CTRL_DATA_ENTRY_MSB:
 237                 islsb = 0;
 238         whichparm:
 239                 if ( 0 == ( (mc->rpn ^ mc->nrpn) & PN_SET ) )
 240                         return; /* exactly one must be current */
 241                 if ( mc->rpn & PN_SET ) {
 242                         key = mc->rpn;
 243                         c = RPN;
 244                 } else {
 245                         key = mc->nrpn;
 246                         c = NRPN;
 247                 }
 248                 key &= 0x3fff;
 249                 if ( 0x3fff == key ) /* 'null' parm# to lock out changes */
 250                         return;
 251                 enter14(mc, chan, c, key, islsb, ctlval[1]);
 252                 return;
 253         case MIDI_CTRL_RPN_INCREMENT: /* XXX for later - these are a PITA to */
 254         case MIDI_CTRL_RPN_DECREMENT: /* get right - 'right' varies by param */
 255                         /* see http://www.midi.org/about-midi/rp18.shtml */
 256                 return;
 257         }
 258
 259         /*
 260          * Channel mode, RPN, and NRPN operations have been ruled out.
 261          * This is an ordinary control change.
 262          */
 263
 264         key = ctlval[0];
 265         c = classify(&key, &islsb);
 266
 267         switch ( c ) {
 268         case CTL14:
 269                 enter14(mc, chan, c, key, islsb, ctlval[1]);
 270                 return;
 271         case CTL7:
 272                 present = store_locate(mc->store, c, chan, key);
 273                 if ( !mc->accept_any_ctl_rpn ) {
 274                         if ( !present )
 275                                 break;
 276                         val = store_extract(mc->store, c, chan, key);
 277                         if ( !(val&C7_SET) )
 278                                 break;
 279                 }
 280                 store_update(mc->store, c, chan, key,
 281                     C7_SET | (0x7f & ctlval[1]));
 282                 mc->notify(mc->cookie, MIDICTL_CTLR, chan, key);
 283                 return;
 284         case CTL1:
 285                 present = store_locate(mc->store, c, chan, key);
 286                 if ( !mc->accept_any_ctl_rpn ) {
 287                         if ( !present )
 288                                 break;
 289                         val = store_extract(mc->store, c, chan, key);
 290                         if ( !(val&C1_SET) )
 291                                 break;
 292                 }
 293                 store_update(mc->store, c, chan, key,
 294                     C1_SET | (ctlval[1]>63));
 295                 mc->notify(mc->cookie, MIDICTL_CTLR, chan, key);
 296                 return;
 297         case RPN:
 298         case NRPN:
 299                 return; /* won't see these - sop for gcc */
 300         }
 301 }
 302
 303 uint_fast16_t
 304 midictl_read(midictl *mc, uint_fast8_t chan, uint_fast8_t ctlr,
 305              uint_fast16_t dflt)
 306 {
 307         uint_fast16_t key, val;
 308         class c;
 309         _Bool islsb, present;
 310
 311         key = ctlr;
 312         c = classify(&key, &islsb);
 313         switch ( c ) {
 314         case CTL1:
 315                 present = store_locate(mc->store, c, chan, key);
 316                 if ( !present ||
 317                     !(C1_SET&(val = store_extract(mc->store, c, chan, key))) ) {
 318                         val = C1_SET | (dflt > 63); /* convert to boolean */
 319                         store_update(mc->store, c, chan, key, val);
 320                 }
 321                 return (val & 1) ? 127 : 0;
 322         case CTL7:
 323                 present = store_locate(mc->store, c, chan, key);
 324                 if ( !present ||
 325                     !(C7_SET&(val = store_extract(mc->store, c, chan, key))) ) {
 326                         val = C7_SET | (dflt & 0x7f);
 327                         store_update(mc->store, c, chan, key, val);
 328                 }
 329                 return val & 0x7f;
 330         case CTL14:
 331                 _MIDICTL_ASSERT(!islsb);
 332                 return read14(mc, chan, c, key, dflt);
 333         case RPN:
 334         case NRPN:
 335                 break; /* sop for gcc */
 336         }
 337         return 0; /* sop for gcc */
 338 }
 339
 340 uint_fast16_t
 341 midictl_rpn_read(midictl *mc, uint_fast8_t chan, uint_fast16_t ctlr,
 342                  uint_fast16_t dflt)
 343 {
 344         return read14(mc, chan, RPN, ctlr, dflt);
 345 }
 346
 347 uint_fast16_t
 348 midictl_nrpn_read(midictl *mc, uint_fast8_t chan, uint_fast16_t ctlr,
 349                   uint_fast16_t dflt)
 350 {
 351         return read14(mc, chan, NRPN, ctlr, dflt);
 352 }
 353
 354 static void
 355 reset_all_controllers(midictl *mc, uint_fast8_t chan)
 356 {
 357         uint_fast16_t ctlr, key;
 358         class c;
 359         _Bool islsb, present;
 360
 361         for ( ctlr = 0 ; ; ++ ctlr ) {
 362                 switch ( ctlr ) {
 363                 /*
 364                  * exempt by http://www.midi.org/about-midi/rp15.shtml:
 365                  */
 366                 case MIDI_CTRL_BANK_SELECT_MSB:         /* 0 */
 367                 case MIDI_CTRL_CHANNEL_VOLUME_MSB:      /* 7 */
 368                 case MIDI_CTRL_PAN_MSB:                 /* 10 */
 369                         continue;
 370                 case MIDI_CTRL_BANK_SELECT_LSB:         /* 32 */
 371                         ctlr += 31; /* skip all these LSBs anyway */
 372                         continue;
 373                 case MIDI_CTRL_SOUND_VARIATION:         /* 70 */
 374                         ctlr += 9; /* skip all Sound Controllers */
 375                         continue;
 376                 case MIDI_CTRL_EFFECT_DEPTH_1:          /* 91 */
 377                         goto loop_exit; /* nothing more gets reset */
 378                 /*
 379                  * exempt for our own personal reasons:
 380                  */
 381                 case MIDI_CTRL_DATA_ENTRY_MSB:          /* 6 */
 382                         continue; /* doesn't go to the store */
 383                 }
 384
 385                 key = ctlr;
 386                 c = classify(&key, &islsb);
 387
 388                 present = store_locate(mc->store, c, chan, key);
 389                 if ( !present )
 390                         continue;
 391                 store_update(mc->store, c, chan, key, 0); /* no C*SET */
 392         }
 393 loop_exit:
 394         mc->notify(mc->cookie, MIDICTL_RESET, chan, 0);
 395 }
 396
 397 static void
 398 enter14(midictl *mc, uint_fast8_t chan, class c, uint_fast16_t key,
 399         _Bool islsb, uint8_t val)
 400 {
 401         uint16_t stval;
 402         _Bool present;
 403
 404         present = store_locate(mc->store, c, chan, key);
 405         stval = (present) ? store_extract(mc->store, c, chan, key) : 0;
 406         if ( !( stval & (C14MSET|C14LSET) ) ) {
 407                 if ( !((NRPN==c)? mc->accept_any_nrpn: mc->accept_any_ctl_rpn) )
 408                         return;
 409         }
 410         if ( islsb )
 411                 stval = C14LSET | val | ( stval & ~0x7f );
 412         else
 413                 stval = C14MSET | ( val << 7 ) | ( stval & ~0x3f80 );
 414         store_update(mc->store, c, chan, key, stval);
 415         mc->notify(mc->cookie, CTL14 == c ? MIDICTL_CTLR
 416                              : RPN   == c ? MIDICTL_RPN
 417                              : MIDICTL_NRPN, chan, key);
 418 }
 419
 420 static uint_fast16_t
 421 read14(midictl *mc, uint_fast8_t chan, class c, uint_fast16_t key,
 422        uint_fast16_t dflt)
 423 {
 424         uint16_t val;
 425         _Bool present;
 426
 427         present = store_locate(mc->store, c, chan, key);
 428         if ( !present )
 429                 goto neitherset;
 430
 431         val = store_extract(mc->store, c, chan, key);
 432         switch ( val & (C14MSET|C14LSET) ) {
 433         case C14MSET|C14LSET:
 434                 return val & 0x3fff;
 435         case C14MSET:
 436                 val = C14LSET | (val & ~0x7f) | (dflt & 0x7f);
 437                 break;
 438         case C14LSET:
 439                 val = C14MSET | (val & ~0x3f8) | (dflt & 0x3f8);
 440                 break;
 441 neitherset:
 442         case 0:
 443                 val = C14MSET|C14LSET | (dflt & 0x3fff);
 444         }
 445         store_update(mc->store, c, chan, key, val);
 446         return val & 0x3fff;
 447 }
 448
 449 /*
 450  * Determine the controller class; ranges based on
 451  * http://www.midi.org/about-midi/table3.shtml dated 1995/1999/2002
 452  * and viewed 2 June 2006.
 453  */
 454 static class
 455 classify(uint_fast16_t *key, _Bool *islsb) {
 456         if ( *key < 32 ) {
 457                 *islsb = 0;
 458                 return CTL14;
 459         } else if ( *key < 64 ) {
 460                 *islsb = 1;
 461                 *key -= 32;
 462                 return CTL14;
 463         } else if ( *key < 70 ) {
 464                 return CTL1;
 465         }               /* 70-84 defined, 85-90 undef'd, 91-95 def'd */
 466         return CTL7;    /* 96-101,120- handled above, 102-119 all undef'd */
 467                         /* treat them all as CTL7 */
 468 }
 469
 470 static void
 471 notify_no_one(void *cookie, midictl_evt evt,
 472     uint_fast8_t chan, uint_fast16_t k)
 473 {
 474 }
 475
 476 #undef PN_SET
 477 #undef C14MSET
 478 #undef C14LSET
 479 #undef C7_SET
 480 #undef C1_SET
 481
 482 /*
 483  *   I M P L E M E N T A T I O N     O F     T H E     S T O R E :
 484  *
 485  * MIDI defines a metric plethora of possible controllers, registered
 486  * parameters, and nonregistered parameters: a bit more than 32k possible words
 487  * to store. The saving grace is that only a handful are likely to appear in
 488  * typical MIDI data, and only a handful are likely implemented by or
 489  * interesting to a typical client. So the store implementation needs to be
 490  * suited to a largish but quite sparse data set.
 491  *
 492  * A double-hashed, open address table is used here. Each slot is a uint64
 493  * that contains the match key (control class|channel|ctl-or-PN-number) as
 494  * well as the values for two or more channels. CTL14s, RPNs, and NRPNs can
 495  * be packed two channels to the slot; CTL7s, six channels; and CTL1s get all
 496  * 16 channels into one slot. The channel value used in the key is the lowest
 497  * channel stored in the slot. Open addressing is appropriate here because the
 498  * link fields in a chained approach would be at least 100% overhead, and also,
 499  * we don't delete (MIDICTL_RESET is the only event that logically deletes
 500  * things, and at the moment it does not remove anything from the table, but
 501  * zeroes the stored value). If wanted, the deletion algorithm for open
 502  * addressing could be used, with shrinking/rehashing when the load factor
 503  * drops below 3/8 (3/4 is the current threshold for expansion), and the
 504  * rehashing would relieve the fills-with-DELETED problem in most cases. But
 505  * for now the table never shrinks while the device is open.
 506  */
 507
 508 #include <sys/malloc.h>
 509
 510 #define INITIALLGCAPACITY 6 /* initial capacity 1<<6 */
 511 #define IS_USED 1<<15
 512 #define IS_CTL7 1<<14
 513
 514 #define CTL1SHIFT(chan) (23+((chan)<<1))
 515 #define CTL7SHIFT(chan) (16+((chan)<<3))
 516 #define CTLESHIFT(chan) (23+((chan)<<4))
 517
 518 static uint_fast8_t const packing[] = {
 519         [CTL1 ] = 16, /* 16 * 2 bits ==> 32 bits, all chns in one bucket */
 520         [CTL7 ] =  6, /*  6 * 8 bits ==> 48 bits, 6 chns in one bucket */
 521         [CTL14] =  2, /*  2 *16 bits ==> 32 bits, 2 chns in one bucket */
 522         [RPN  ] =  2,
 523         [NRPN ] =  2
 524 };
 525
 526 struct midictl_store {
 527         uint64_t *table;
 528         uint64_t key;
 529         uint32_t idx;
 530         uint32_t lgcapacity;
 531         uint32_t used;
 532 };
 533
 534 static uint32_t store_idx(uint32_t lgcapacity,
 535                           uint64_t *table,
 536                           uint64_t key, uint64_t mask);
 537 static void store_rehash(midictl_store *s);
 538
 539 static midictl_store *
 540 store_init(void)
 541 {
 542         midictl_store *s;
 543
 544         s = _MIDICTL_MALLOC(sizeof *s, M_DEVBUF);
 545         s->used = 0;
 546         s->lgcapacity = INITIALLGCAPACITY;
 547         s->table = _MIDICTL_ZMALLOC(sizeof *s->table<<s->lgcapacity, M_DEVBUF);
 548         return s;
 549 }
 550
 551 static void
 552 store_done(midictl_store *s)
 553 {
 554         _MIDICTL_FREE(s->table, M_DEVBUF);
 555         _MIDICTL_FREE(s, M_DEVBUF);
 556 }
 557
 558 static _Bool
 559 store_locate(midictl_store *s, class c, uint_fast8_t chan, uint_fast16_t key)
 560 {
 561         uint64_t mask;
 562
 563         if ( s->used >= 1 << s->lgcapacity )
 564                 _MIDICTL_PANIC("%s: repeated attempts to expand table failed, "
 565                     "plumb ran out of space", __func__);
 566
 567         chan = packing[c] * (chan/packing[c]);
 568
 569         if ( CTL7 == c ) {      /* only 16 bits here (key's only 7) */
 570                 s->key = IS_USED | IS_CTL7 | (chan << 7) | key;
 571                 mask = 0xffff;
 572         } else {                /* use 23 bits (key could be 14) */
 573                 s->key = (c << 20) | (chan << 16) | IS_USED | key;
 574                 mask = 0x7fffff;
 575         }
 576
 577         s->idx = store_idx(s->lgcapacity, s->table, s->key, mask);
 578
 579         if ( !(s->table[s->idx] & IS_USED) )
 580                 return 0;
 581
 582         return 1;
 583 }
 584
 585 static uint16_t
 586 store_extract(midictl_store *s, class c, uint_fast8_t chan,
 587     uint_fast16_t key)
 588 {
 589         chan %= packing[c];
 590         switch ( c ) {
 591         case CTL1:
 592                 return 3 & (s->table[s->idx]>>CTL1SHIFT(chan));
 593         case CTL7:
 594                 return 0xff & (s->table[s->idx]>>CTL7SHIFT(chan));
 595         case CTL14:
 596         case RPN:
 597         case NRPN:
 598                 break;
 599         }
 600         return 0xffff & (s->table[s->idx]>>CTLESHIFT(chan));
 601 }
 602
 603 static void
 604 store_update(midictl_store *s, class c, uint_fast8_t chan,
 605     uint_fast16_t key, uint16_t value)
 606 {
 607         uint64_t orig;
 608
 609         orig = s->table[s->idx];
 610         if ( !(orig & IS_USED) ) {
 611                 orig = s->key;
 612                 ++ s->used;
 613         }
 614
 615         chan %= packing[c];
 616
 617         switch ( c ) {
 618         case CTL1:
 619                 orig &= ~(((uint64_t)3)<<CTL1SHIFT(chan));
 620                 orig |= ((uint64_t)(3 & value)) << CTL1SHIFT(chan);
 621                 break;
 622         case CTL7:
 623                 orig &= ~(((uint64_t)0xff)<<CTL7SHIFT(chan));
 624                 orig |= ((uint64_t)(0xff & value)) << CTL7SHIFT(chan);
 625                 break;
 626         case CTL14:
 627         case RPN:
 628         case NRPN:
 629                 orig &= ~(((uint64_t)0xffff)<<CTLESHIFT(chan));
 630                 orig |= ((uint64_t)value) << CTLESHIFT(chan);
 631                 break;
 632         }
 633
 634         s->table[s->idx] = orig;
 635         if ( s->used * 4 >= 3 << s->lgcapacity )
 636                 store_rehash(s);
 637 }
 638
 639 static uint32_t
 640 store_idx(uint32_t lgcapacity, uint64_t *table,
 641           uint64_t key, uint64_t mask)
 642 {
 643         uint32_t val;
 644         uint32_t k, h1, h2;
 645         int32_t idx;
 646
 647         k = key;
 648
 649         h1 = ((k * 0x61c88646) >> (32-lgcapacity)) & ((1<<lgcapacity) - 1);
 650         h2 = ((k * 0x9e3779b9) >> (32-lgcapacity)) & ((1<<lgcapacity) - 1);
 651         h2 |= 1;
 652
 653         for ( idx = h1 ;; idx -= h2 ) {
 654                 if ( idx < 0 )
 655                         idx += 1<<lgcapacity;
 656                 val = (uint32_t)(table[idx] & mask);
 657                 if ( val == k )
 658                         break;
 659                 if ( !(val & IS_USED) )
 660                         break;
 661         }
 662
 663         return idx;
 664 }
 665
 666 static void
 667 store_rehash(midictl_store *s)
 668 {
 669         uint64_t *newtbl, mask;
 670         uint32_t newlgcap, oidx, nidx;
 671
 672         newlgcap = 1 + s->lgcapacity;
 673         newtbl = _MIDICTL_IMZMALLOC(sizeof *newtbl << newlgcap, M_DEVBUF);
 674
 675         /*
 676          * Because IMZMALLOC can't sleep, it might have returned NULL.
 677          * We rehash when there is some capacity left in the table, so
 678          * just leave it alone; we'll get another chance on the next insertion.
 679          * Nothing to panic about unless the load factor really hits 1.
 680          */
 681         if ( NULL == newtbl )
 682                 return;
 683
 684         for ( oidx = 1<<s->lgcapacity ; oidx --> 0 ; ) {
 685                 if ( !(s->table[oidx] & IS_USED) )
 686                         continue;
 687                 if ( s->table[oidx] & IS_CTL7 )
 688                         mask = 0xffff;
 689                 else
 690                         mask = 0x3fffff;
 691                 nidx = store_idx(newlgcap, newtbl, s->table[oidx]&mask, mask);
 692                 newtbl[nidx] = s->table[oidx];
 693         }
 694
 695         _MIDICTL_FREE(s->table, M_DEVBUF);
 696         s->table = newtbl;
 697         s->lgcapacity = newlgcap;
 698 }
 699
 700 #if defined(_MIDICTL_MAIN)
 701 void
 702 dumpstore(void)
 703 {
 704         uint64_t val;
 705         uint32_t i, remain;
 706         midictl_store *s;
 707         char const *lbl;
 708         uint_fast16_t key;
 709         uint_fast8_t chan;
 710         class c;
 711
 712         s = mc.store;
 713
 714         printf("store capacity %u, used %u\n", 1<<s->lgcapacity, s->used);
 715         remain = s->used;
 716
 717         for ( i = 1<<s->lgcapacity; i --> 0; ) {
 718                 if ( !(s->table[i] & IS_USED) )
 719                         continue;
 720                 -- remain;
 721                 if ( s->table[i] & IS_CTL7 ) {
 722                         c = CTL7;
 723                         chan = 0xf & (s->table[i]>>7);
 724                         key = 0x7f & s->table[i];
 725                 } else {
 726                         c = 0x7 & (s->table[i]>>20);
 727                         chan = 0xf & (s->table[i]>>16);
 728                         key = 0x3fff & s->table[i];
 729                 }
 730                 switch ( c ) {
 731                 case CTL1:
 732                         lbl = "CTL1";
 733                         val = s->table[i] >> CTL1SHIFT(0);
 734                         break;
 735                 case CTL7:
 736                         lbl = "CTL7";
 737                         val = s->table[i] >> CTL7SHIFT(0);
 738                         break;
 739                 case CTL14:
 740                         lbl = "CTL14";
 741                         val = s->table[i] >> CTLESHIFT(0);
 742                         break;
 743                 case RPN:
 744                         lbl = "RPN";
 745                         val = s->table[i] >> CTLESHIFT(0);
 746                         break;
 747                 case NRPN:
 748                         lbl = "NRPN";
 749                         val = s->table[i] >> CTLESHIFT(0);
 750                         break;
 751                 default:
 752                         lbl = "???";
 753                         chan = 0;
 754                         key = 0;
 755                         val = s->table[i];
 756                 }
 757                 printf("[%7u] %5s chans %x-%x key %5u: %"PRIx64"\n",
 758                     i, lbl, chan, chan+packing[c]-1, key, val);
 759         }
 760
 761         if ( 0 != remain )
 762                 printf("remain == %u ??\n", remain);
 763 }
 764 #endif