midictl.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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
Cache object: 3ad8de34da6197c516301a4ed9d45dc7
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/dev/midictl.c

FreeBSD/Linux Kernel Cross Reference
sys/dev/midictl.c
