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