Return to jhash.c CVS log

Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / quagga / lib

quagga 1.0.20160315

    1: /* jhash.h: Jenkins hash support.
    2:  *
    3:  * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
    4:  *
    5:  * http://burtleburtle.net/bob/hash/
    6:  *
    7:  * These are the credits from Bob's sources:
    8:  *
    9:  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
   10:  * hash(), hash2(), hash3, and mix() are externally useful functions.
   11:  * Routines to test the hash are included if SELF_TEST is defined.
   12:  * You can use this free for any purpose.  It has no warranty.
   13:  *
   14:  * Copyright (C) 2003 David S. Miller (davem@redhat.com)
   15:  *
   16:  * I've modified Bob's hash to be useful in the Linux kernel, and
   17:  * any bugs present are surely my fault.  -DaveM
   18:  */
   19: 
   20: #include "zebra.h"
   21: #include "jhash.h"
   22: 
   23: /* The golden ration: an arbitrary value */
   24: #define JHASH_GOLDEN_RATIO  0x9e3779b9
   25: 
   26: /* NOTE: Arguments are modified. */
   27: #define __jhash_mix(a, b, c) \
   28: { \
   29:   a -= b; a -= c; a ^= (c>>13); \
   30:   b -= c; b -= a; b ^= (a<<8); \
   31:   c -= a; c -= b; c ^= (b>>13); \
   32:   a -= b; a -= c; a ^= (c>>12);  \
   33:   b -= c; b -= a; b ^= (a<<16); \
   34:   c -= a; c -= b; c ^= (b>>5); \
   35:   a -= b; a -= c; a ^= (c>>3);  \
   36:   b -= c; b -= a; b ^= (a<<10); \
   37:   c -= a; c -= b; c ^= (b>>15); \
   38: }
   39: 
   40: /* The most generic version, hashes an arbitrary sequence
   41:  * of bytes.  No alignment or length assumptions are made about
   42:  * the input key.
   43:  */
   44: u_int32_t
   45: jhash (const void *key, u_int32_t length, u_int32_t initval)
   46: {
   47:   u_int32_t a, b, c, len;
   48:   const u_int8_t *k = key;
   49: 
   50:   len = length;
   51:   a = b = JHASH_GOLDEN_RATIO;
   52:   c = initval;
   53: 
   54:   while (len >= 12)
   55:     {
   56:       a +=
   57:         (k[0] + ((u_int32_t) k[1] << 8) + ((u_int32_t) k[2] << 16) +
   58:          ((u_int32_t) k[3] << 24));
   59:       b +=
   60:         (k[4] + ((u_int32_t) k[5] << 8) + ((u_int32_t) k[6] << 16) +
   61:          ((u_int32_t) k[7] << 24));
   62:       c +=
   63:         (k[8] + ((u_int32_t) k[9] << 8) + ((u_int32_t) k[10] << 16) +
   64:          ((u_int32_t) k[11] << 24));
   65: 
   66:       __jhash_mix (a, b, c);
   67: 
   68:       k += 12;
   69:       len -= 12;
   70:     }
   71: 
   72:   c += length;
   73:   switch (len)
   74:     {
   75:     case 11:
   76:       c += ((u_int32_t) k[10] << 24);
   77:     case 10:
   78:       c += ((u_int32_t) k[9] << 16);
   79:     case 9:
   80:       c += ((u_int32_t) k[8] << 8);
   81:     case 8:
   82:       b += ((u_int32_t) k[7] << 24);
   83:     case 7:
   84:       b += ((u_int32_t) k[6] << 16);
   85:     case 6:
   86:       b += ((u_int32_t) k[5] << 8);
   87:     case 5:
   88:       b += k[4];
   89:     case 4:
   90:       a += ((u_int32_t) k[3] << 24);
   91:     case 3:
   92:       a += ((u_int32_t) k[2] << 16);
   93:     case 2:
   94:       a += ((u_int32_t) k[1] << 8);
   95:     case 1:
   96:       a += k[0];
   97:     };
   98: 
   99:   __jhash_mix (a, b, c);
  100: 
  101:   return c;
  102: }
  103: 
  104: /* A special optimized version that handles 1 or more of u_int32_ts.
  105:  * The length parameter here is the number of u_int32_ts in the key.
  106:  */
  107: u_int32_t
  108: jhash2 (const u_int32_t *k, u_int32_t length, u_int32_t initval)
  109: {
  110:   u_int32_t a, b, c, len;
  111: 
  112:   a = b = JHASH_GOLDEN_RATIO;
  113:   c = initval;
  114:   len = length;
  115: 
  116:   while (len >= 3)
  117:     {
  118:       a += k[0];
  119:       b += k[1];
  120:       c += k[2];
  121:       __jhash_mix (a, b, c);
  122:       k += 3;
  123:       len -= 3;
  124:     }
  125: 
  126:   c += length * 4;
  127: 
  128:   switch (len)
  129:     {
  130:     case 2:
  131:       b += k[1];
  132:     case 1:
  133:       a += k[0];
  134:     };
  135: 
  136:   __jhash_mix (a, b, c);
  137: 
  138:   return c;
  139: }
  140: 
  141: 
  142: /* A special ultra-optimized versions that knows they are hashing exactly
  143:  * 3, 2 or 1 word(s).
  144:  *
  145:  * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
  146:  *       done at the end is not done here.
  147:  */
  148: u_int32_t
  149: jhash_3words (u_int32_t a, u_int32_t b, u_int32_t c, u_int32_t initval)
  150: {
  151:   a += JHASH_GOLDEN_RATIO;
  152:   b += JHASH_GOLDEN_RATIO;
  153:   c += initval;
  154: 
  155:   __jhash_mix (a, b, c);
  156: 
  157:   return c;
  158: }
  159: 
  160: u_int32_t
  161: jhash_2words (u_int32_t a, u_int32_t b, u_int32_t initval)
  162: {
  163:   return jhash_3words (a, b, 0, initval);
  164: }
  165: 
  166: u_int32_t
  167: jhash_1word (u_int32_t a, u_int32_t initval)
  168: {
  169:   return jhash_3words (a, 0, 0, initval);
  170: }