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.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
Cache object: b835fb9e85717a4064fe67ba442fe517
[ 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
