lib/jhash.c

   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;                                                        \
  30                 a -= c;                                                        \
  31                 a ^= (c >> 13);                                                \
  32                 b -= c;                                                        \
  33                 b -= a;                                                        \
  34                 b ^= (a << 8);                                                 \
  35                 c -= a;                                                        \
  36                 c -= b;                                                        \
  37                 c ^= (b >> 13);                                                \
  38                 a -= b;                                                        \
  39                 a -= c;                                                        \
  40                 a ^= (c >> 12);                                                \
  41                 b -= c;                                                        \
  42                 b -= a;                                                        \
  43                 b ^= (a << 16);                                                \
  44                 c -= a;                                                        \
  45                 c -= b;                                                        \
  46                 c ^= (b >> 5);                                                 \
  47                 a -= b;                                                        \
  48                 a -= c;                                                        \
  49                 a ^= (c >> 3);                                                 \
  50                 b -= c;                                                        \
  51                 b -= a;                                                        \
  52                 b ^= (a << 10);                                                \
  53                 c -= a;                                                        \
  54                 c -= b;                                                        \
  55                 c ^= (b >> 15);                                                \
  56         }
  57
  58 /* The most generic version, hashes an arbitrary sequence
  59  * of bytes.  No alignment or length assumptions are made about
  60  * the input key.
  61  */
  62 uint32_t jhash(const void *key, uint32_t length, uint32_t initval)
  63 {
  64         uint32_t a, b, c, len;
  65         const uint8_t *k = key;
  66
  67         len = length;
  68         a = b = JHASH_GOLDEN_RATIO;
  69         c = initval;
  70
  71         while (len >= 12) {
  72                 a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16)
  73                       + ((uint32_t)k[3] << 24));
  74                 b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16)
  75                       + ((uint32_t)k[7] << 24));
  76                 c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16)
  77                       + ((uint32_t)k[11] << 24));
  78
  79                 __jhash_mix(a, b, c);
  80
  81                 k += 12;
  82                 len -= 12;
  83         }
  84
  85         c += length;
  86         switch (len) {
  87         case 11:
  88                 c += ((uint32_t)k[10] << 24);
  89         /* fallthru */
  90         case 10:
  91                 c += ((uint32_t)k[9] << 16);
  92         /* fallthru */
  93         case 9:
  94                 c += ((uint32_t)k[8] << 8);
  95         /* fallthru */
  96         case 8:
  97                 b += ((uint32_t)k[7] << 24);
  98         /* fallthru */
  99         case 7:
 100                 b += ((uint32_t)k[6] << 16);
 101         /* fallthru */
 102         case 6:
 103                 b += ((uint32_t)k[5] << 8);
 104         /* fallthru */
 105         case 5:
 106                 b += k[4];
 107         /* fallthru */
 108         case 4:
 109                 a += ((uint32_t)k[3] << 24);
 110         /* fallthru */
 111         case 3:
 112                 a += ((uint32_t)k[2] << 16);
 113         /* fallthru */
 114         case 2:
 115                 a += ((uint32_t)k[1] << 8);
 116         /* fallthru */
 117         case 1:
 118                 a += k[0];
 119         };
 120
 121         __jhash_mix(a, b, c);
 122
 123         return c;
 124 }
 125
 126 /* A special optimized version that handles 1 or more of uint32_ts.
 127  * The length parameter here is the number of uint32_ts in the key.
 128  */
 129 uint32_t jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
 130 {
 131         uint32_t a, b, c, len;
 132
 133         a = b = JHASH_GOLDEN_RATIO;
 134         c = initval;
 135         len = length;
 136
 137         while (len >= 3) {
 138                 a += k[0];
 139                 b += k[1];
 140                 c += k[2];
 141                 __jhash_mix(a, b, c);
 142                 k += 3;
 143                 len -= 3;
 144         }
 145
 146         c += length * 4;
 147
 148         switch (len) {
 149         case 2:
 150                 b += k[1];
 151         /* fallthru */
 152         case 1:
 153                 a += k[0];
 154         };
 155
 156         __jhash_mix(a, b, c);
 157
 158         return c;
 159 }
 160
 161
 162 /* A special ultra-optimized versions that knows they are hashing exactly
 163  * 3, 2 or 1 word(s).
 164  *
 165  * NOTE: In partilar the "c += length; __jhash_mix(a,b,c);" normally
 166  *       done at the end is not done here.
 167  */
 168 uint32_t jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 169 {
 170         a += JHASH_GOLDEN_RATIO;
 171         b += JHASH_GOLDEN_RATIO;
 172         c += initval;
 173
 174         __jhash_mix(a, b, c);
 175
 176         return c;
 177 }
 178
 179 uint32_t jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 180 {
 181         return jhash_3words(a, b, 0, initval);
 182 }
 183
 184 uint32_t jhash_1word(uint32_t a, uint32_t initval)
 185 {
 186         return jhash_3words(a, 0, 0, initval);
 187 }