1 /* $NetBSD: midictl.c,v 1.6 2008/06/24 10:55:48 gmcgarry 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.6 2008/06/24 10:55:48 gmcgarry 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 765