drivers/net/bnxt/tf_core/lookup3.h

   1 /* SPDX-License-Identifier: BSD-3-Clause
   2  *
   3  * Based on lookup3.c, by Bob Jenkins, May 2006, Public Domain.
   4  * http://www.burtleburtle.net/bob/c/lookup3.c
   5  *
   6  * These functions for producing 32-bit hashes for has table lookup.
   7  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
   8  * are externally useful functions. Routines to test the hash are included
   9  * if SELF_TEST is defined. You can use this free for any purpose. It is in
  10  * the public domain. It has no warranty.
  11  */
  12
  13 #ifndef _LOOKUP3_H_
  14 #define _LOOKUP3_H_
  15
  16 #define rot(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
  17
  18 /** -------------------------------------------------------------------------
  19  * This is reversible, so any information in (a,b,c) before mix() is
  20  * still in (a,b,c) after mix().
  21  *
  22  * If four pairs of (a,b,c) inputs are run through mix(), or through
  23  * mix() in reverse, there are at least 32 bits of the output that
  24  * are sometimes the same for one pair and different for another pair.
  25  * This was tested for:
  26  *   pairs that differed by one bit, by two bits, in any combination
  27  *   of top bits of (a,b,c), or in any combination of bottom bits of
  28  *   (a,b,c).
  29  *   "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  30  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  31  *   is commonly produced by subtraction) look like a single 1-bit
  32  *   difference.
  33  *   the base values were pseudorandom, all zero but one bit set, or
  34  *   all zero plus a counter that starts at zero.
  35  *
  36  * Some k values for my "a-=c; a^=rot(c,k); c+=b;" arrangement that
  37  * satisfy this are
  38  *     4  6  8 16 19  4
  39  *     9 15  3 18 27 15
  40  *    14  9  3  7 17  3
  41  * Well, "9 15 3 18 27 15" didn't quite get 32 bits diffing
  42  * for "differ" defined as + with a one-bit base and a two-bit delta.  I
  43  * used http://burtleburtle.net/bob/hash/avalanche.html to choose
  44  * the operations, constants, and arrangements of the variables.
  45  *
  46  * This does not achieve avalanche.  There are input bits of (a,b,c)
  47  * that fail to affect some output bits of (a,b,c), especially of a.  The
  48  * most thoroughly mixed value is c, but it doesn't really even achieve
  49  * avalanche in c.
  50  *
  51  * This allows some parallelism.  Read-after-writes are good at doubling
  52  * the number of bits affected, so the goal of mixing pulls in the opposite
  53  * direction as the goal of parallelism.  I did what I could.  Rotates
  54  * seem to cost as much as shifts on every machine I could lay my hands
  55  * on, and rotates are much kinder to the top and bottom bits, so I used
  56  * rotates.
  57  * --------------------------------------------------------------------------
  58  */
  59 #define mix(a, b, c) \
  60 { \
  61         (a) -= (c); (a) ^= rot((c), 4);  (c) += b; \
  62         (b) -= (a); (b) ^= rot((a), 6);  (a) += c; \
  63         (c) -= (b); (c) ^= rot((b), 8);  (b) += a; \
  64         (a) -= (c); (a) ^= rot((c), 16); (c) += b; \
  65         (b) -= (a); (b) ^= rot((a), 19); (a) += c; \
  66         (c) -= (b); (c) ^= rot((b), 4);  (b) += a; \
  67 }
  68
  69 /** --------------------------------------------------------------------------
  70  * final -- final mixing of 3 32-bit values (a,b,c) into c
  71  *
  72  * Pairs of (a,b,c) values differing in only a few bits will usually
  73  * produce values of c that look totally different.  This was tested for
  74  *  pairs that differed by one bit, by two bits, in any combination
  75  *   of top bits of (a,b,c), or in any combination of bottom bits of
  76  *   (a,b,c).
  77  *   "differ" is defined as +, -, ^, or ~^.  For + and -, I transformed
  78  *   the output delta to a Gray code (a^(a>>1)) so a string of 1's (as
  79  *   is commonly produced by subtraction) look like a single 1-bit
  80  *   difference.
  81  *   the base values were pseudorandom, all zero but one bit set, or
  82  *   all zero plus a counter that starts at zero.
  83  *
  84  * These constants passed:
  85  *  14 11 25 16 4 14 24
  86  *  12 14 25 16 4 14 24
  87  * and these came close:
  88  *   4  8 15 26 3 22 24
  89  *  10  8 15 26 3 22 24
  90  *  11  8 15 26 3 22 24
  91  * --------------------------------------------------------------------------
  92  */
  93 #define final(a, b, c) \
  94 { \
  95         (c) ^= (b); (c) -= rot((b), 14); \
  96         (a) ^= (c); (a) -= rot((c), 11); \
  97         (b) ^= (a); (b) -= rot((a), 25); \
  98         (c) ^= (b); (c) -= rot((b), 16); \
  99         (a) ^= (c); (a) -= rot((c), 4);  \
 100         (b) ^= (a); (b) -= rot((a), 14); \
 101         (c) ^= (b); (c) -= rot((b), 24); \
 102 }
 103
 104 /** --------------------------------------------------------------------
 105  *  This works on all machines.  To be useful, it requires
 106  *  -- that the key be an array of uint32_t's, and
 107  *  -- that the length be the number of uint32_t's in the key
 108
 109  *  The function hashword() is identical to hashlittle() on little-endian
 110  *  machines, and identical to hashbig() on big-endian machines,
 111  *  except that the length has to be measured in uint32_ts rather than in
 112  *  bytes. hashlittle() is more complicated than hashword() only because
 113  *  hashlittle() has to dance around fitting the key bytes into registers.
 114  *
 115  *  Input Parameters:
 116  *       key: an array of uint32_t values
 117  *       length: the length of the key, in uint32_ts
 118  *       initval: the previous hash, or an arbitrary value
 119  * --------------------------------------------------------------------
 120  */
 121 static inline uint32_t hashword(const uint32_t *k,
 122                                 size_t length,
 123                                 uint32_t initval) {
 124         uint32_t a, b, c;
 125         int index = length - 1;
 126
 127         /* Set up the internal state */
 128         a = 0xdeadbeef + (((uint32_t)length) << 2) + initval;
 129         b = a;
 130         c = a;
 131
 132         /*-------------------------------------------- handle most of the key */
 133         while (length > 3) {
 134                 a += k[index];
 135                 b += k[index - 1];
 136                 c += k[index - 2];
 137                 mix(a, b, c);
 138                 length -= 3;
 139                 index -= 3;
 140         }
 141
 142         /*-------------------------------------- handle the last 3 uint32_t's */
 143         switch (length) {             /* all the case statements fall through */
 144         case 3:
 145                 c += k[index - 2];
 146                 /* Falls through. */
 147         case 2:
 148                 b += k[index - 1];
 149                 /* Falls through. */
 150         case 1:
 151                 a += k[index];
 152                 final(a, b, c);
 153                 /* Falls through. */
 154         case 0:     /* case 0: nothing left to add */
 155                 break;
 156         }
 157         /*------------------------------------------------- report the result */
 158         return c;
 159 }
 160
 161 #endif /* _LOOKUP3_H_ */