net/ice/base: init boost TCAM table for parser
[dpdk.git] / 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_ */