1 /* SPDX-License-Identifier: BSD-3-Clause
2 * Copyright(c) 2010-2015 Intel Corporation.
3 */
4
5 #ifndef _RTE_JHASH_H
6 #define _RTE_JHASH_H
7
8 /**
9 * @file
10 *
11 * jhash functions.
12 */
13
14 #ifdef __cplusplus
15 extern "C" {
16 #endif
17
18 //#include <rte_byteorder.h>
19
20 /* jhash.h: Jenkins hash support.
21 *
22 * Copyright (C) 2006 Bob Jenkins (bob_jenkins@burtleburtle.net)
23 *
24 * http://burtleburtle.net/bob/hash/
25 *
26 * These are the credits from Bob's sources:
27 *
28 * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
29 *
30 * These are functions for producing 32-bit hashes for hash table lookup.
31 * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
32 * are externally useful functions. Routines to test the hash are included
33 * if SELF_TEST is defined. You can use this free for any purpose. It's in
34 * the public domain. It has no warranty.
35 *
36 * $FreeBSD$
37 */
38
39 #define rot(x, k) (((x) << (k)) | ((x) >> (32-(k))))
40
41 /** @internal Internal function. NOTE: Arguments are modified. */
42 #define __rte_jhash_mix(a, b, c) do { \
43 a -= c; a ^= rot(c, 4); c += b; \
44 b -= a; b ^= rot(a, 6); a += c; \
45 c -= b; c ^= rot(b, 8); b += a; \
46 a -= c; a ^= rot(c, 16); c += b; \
47 b -= a; b ^= rot(a, 19); a += c; \
48 c -= b; c ^= rot(b, 4); b += a; \
49 } while (0)
50
51 #define __rte_jhash_final(a, b, c) do { \
52 c ^= b; c -= rot(b, 14); \
53 a ^= c; a -= rot(c, 11); \
54 b ^= a; b -= rot(a, 25); \
55 c ^= b; c -= rot(b, 16); \
56 a ^= c; a -= rot(c, 4); \
57 b ^= a; b -= rot(a, 14); \
58 c ^= b; c -= rot(b, 24); \
59 } while (0)
60
61 /** The golden ratio: an arbitrary value. */
62 #define RTE_JHASH_GOLDEN_RATIO 0xdeadbeef
63
64 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
65 #define BIT_SHIFT(x, y, k) (((x) >> (k)) | ((uint64_t)(y) << (32-(k))))
66 #else
67 #define BIT_SHIFT(x, y, k) (((uint64_t)(x) << (k)) | ((y) >> (32-(k))))
68 #endif
69
70 #define LOWER8b_MASK rte_le_to_cpu_32(0xff)
71 #define LOWER16b_MASK rte_le_to_cpu_32(0xffff)
72 #define LOWER24b_MASK rte_le_to_cpu_32(0xffffff)
73
74 static inline void
__rte_jhash_2hashes(const void * key,uint32_t length,uint32_t * pc,uint32_t * pb,unsigned check_align)75 __rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc,
76 uint32_t *pb, unsigned check_align)
77 {
78 uint32_t a, b, c;
79
80 /* Set up the internal state */
81 a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc;
82 c += *pb;
83
84 /*
85 * Check key alignment. For x86 architecture, first case is always optimal
86 * If check_align is not set, first case will be used
87 */
88 #if defined(RTE_ARCH_X86_64) || defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_X32)
89 const uint32_t *k = (const uint32_t *)key;
90 const uint32_t s = 0;
91 #else
92 const uint32_t *k = (uint32_t *)((uintptr_t)key & (uintptr_t)~3);
93 const uint32_t s = ((uintptr_t)key & 3) * CHAR_BIT;
94 #endif
95 if (!check_align || s == 0) {
96 while (length > 12) {
97 a += k[0];
98 b += k[1];
99 c += k[2];
100
101 __rte_jhash_mix(a, b, c);
102
103 k += 3;
104 length -= 12;
105 }
106
107 switch (length) {
108 case 12:
109 c += k[2]; b += k[1]; a += k[0]; break;
110 case 11:
111 c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
112 case 10:
113 c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
114 case 9:
115 c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
116 case 8:
117 b += k[1]; a += k[0]; break;
118 case 7:
119 b += k[1] & LOWER24b_MASK; a += k[0]; break;
120 case 6:
121 b += k[1] & LOWER16b_MASK; a += k[0]; break;
122 case 5:
123 b += k[1] & LOWER8b_MASK; a += k[0]; break;
124 case 4:
125 a += k[0]; break;
126 case 3:
127 a += k[0] & LOWER24b_MASK; break;
128 case 2:
129 a += k[0] & LOWER16b_MASK; break;
130 case 1:
131 a += k[0] & LOWER8b_MASK; break;
132 /* zero length strings require no mixing */
133 case 0:
134 *pc = c;
135 *pb = b;
136 return;
137 };
138 } else {
139 /* all but the last block: affect some 32 bits of (a, b, c) */
140 while (length > 12) {
141 a += BIT_SHIFT(k[0], k[1], s);
142 b += BIT_SHIFT(k[1], k[2], s);
143 c += BIT_SHIFT(k[2], k[3], s);
144 __rte_jhash_mix(a, b, c);
145
146 k += 3;
147 length -= 12;
148 }
149
150 /* last block: affect all 32 bits of (c) */
151 switch (length) {
152 case 12:
153 a += BIT_SHIFT(k[0], k[1], s);
154 b += BIT_SHIFT(k[1], k[2], s);
155 c += BIT_SHIFT(k[2], k[3], s);
156 break;
157 case 11:
158 a += BIT_SHIFT(k[0], k[1], s);
159 b += BIT_SHIFT(k[1], k[2], s);
160 c += BIT_SHIFT(k[2], k[3], s) & LOWER24b_MASK;
161 break;
162 case 10:
163 a += BIT_SHIFT(k[0], k[1], s);
164 b += BIT_SHIFT(k[1], k[2], s);
165 c += BIT_SHIFT(k[2], k[3], s) & LOWER16b_MASK;
166 break;
167 case 9:
168 a += BIT_SHIFT(k[0], k[1], s);
169 b += BIT_SHIFT(k[1], k[2], s);
170 c += BIT_SHIFT(k[2], k[3], s) & LOWER8b_MASK;
171 break;
172 case 8:
173 a += BIT_SHIFT(k[0], k[1], s);
174 b += BIT_SHIFT(k[1], k[2], s);
175 break;
176 case 7:
177 a += BIT_SHIFT(k[0], k[1], s);
178 b += BIT_SHIFT(k[1], k[2], s) & LOWER24b_MASK;
179 break;
180 case 6:
181 a += BIT_SHIFT(k[0], k[1], s);
182 b += BIT_SHIFT(k[1], k[2], s) & LOWER16b_MASK;
183 break;
184 case 5:
185 a += BIT_SHIFT(k[0], k[1], s);
186 b += BIT_SHIFT(k[1], k[2], s) & LOWER8b_MASK;
187 break;
188 case 4:
189 a += BIT_SHIFT(k[0], k[1], s);
190 break;
191 case 3:
192 a += BIT_SHIFT(k[0], k[1], s) & LOWER24b_MASK;
193 break;
194 case 2:
195 a += BIT_SHIFT(k[0], k[1], s) & LOWER16b_MASK;
196 break;
197 case 1:
198 a += BIT_SHIFT(k[0], k[1], s) & LOWER8b_MASK;
199 break;
200 /* zero length strings require no mixing */
201 case 0:
202 *pc = c;
203 *pb = b;
204 return;
205 }
206 }
207
208 __rte_jhash_final(a, b, c);
209
210 *pc = c;
211 *pb = b;
212 }
213
214 /**
215 * Same as rte_jhash, but takes two seeds and return two uint32_ts.
216 * pc and pb must be non-null, and *pc and *pb must both be initialized
217 * with seeds. If you pass in (*pb)=0, the output (*pc) will be
218 * the same as the return value from rte_jhash.
219 *
220 * @param key
221 * Key to calculate hash of.
222 * @param length
223 * Length of key in bytes.
224 * @param pc
225 * IN: seed OUT: primary hash value.
226 * @param pb
227 * IN: second seed OUT: secondary hash value.
228 */
229 static inline void
rte_jhash_2hashes(const void * key,uint32_t length,uint32_t * pc,uint32_t * pb)230 rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
231 {
232 __rte_jhash_2hashes(key, length, pc, pb, 1);
233 }
234
235 /**
236 * Same as rte_jhash_32b, but takes two seeds and return two uint32_ts.
237 * pc and pb must be non-null, and *pc and *pb must both be initialized
238 * with seeds. If you pass in (*pb)=0, the output (*pc) will be
239 * the same as the return value from rte_jhash_32b.
240 *
241 * @param k
242 * Key to calculate hash of.
243 * @param length
244 * Length of key in units of 4 bytes.
245 * @param pc
246 * IN: seed OUT: primary hash value.
247 * @param pb
248 * IN: second seed OUT: secondary hash value.
249 */
250 static inline void
rte_jhash_32b_2hashes(const uint32_t * k,uint32_t length,uint32_t * pc,uint32_t * pb)251 rte_jhash_32b_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb)
252 {
253 __rte_jhash_2hashes((const void *) k, (length << 2), pc, pb, 0);
254 }
255
256 /**
257 * The most generic version, hashes an arbitrary sequence
258 * of bytes. No alignment or length assumptions are made about
259 * the input key. For keys not aligned to four byte boundaries
260 * or a multiple of four bytes in length, the memory region
261 * just after may be read (but not used in the computation).
262 * This may cross a page boundary.
263 *
264 * @param key
265 * Key to calculate hash of.
266 * @param length
267 * Length of key in bytes.
268 * @param initval
269 * Initialising value of hash.
270 * @return
271 * Calculated hash value.
272 */
273 static inline uint32_t
rte_jhash(const void * key,uint32_t length,uint32_t initval)274 rte_jhash(const void *key, uint32_t length, uint32_t initval)
275 {
276 uint32_t initval2 = 0;
277
278 rte_jhash_2hashes(key, length, &initval, &initval2);
279
280 return initval;
281 }
282
283 /**
284 * A special optimized version that handles 1 or more of uint32_ts.
285 * The length parameter here is the number of uint32_ts in the key.
286 *
287 * @param k
288 * Key to calculate hash of.
289 * @param length
290 * Length of key in units of 4 bytes.
291 * @param initval
292 * Initialising value of hash.
293 * @return
294 * Calculated hash value.
295 */
296 static inline uint32_t
rte_jhash_32b(const uint32_t * k,uint32_t length,uint32_t initval)297 rte_jhash_32b(const uint32_t *k, uint32_t length, uint32_t initval)
298 {
299 uint32_t initval2 = 0;
300
301 rte_jhash_32b_2hashes(k, length, &initval, &initval2);
302
303 return initval;
304 }
305
306 static inline uint32_t
__rte_jhash_3words(uint32_t a,uint32_t b,uint32_t c,uint32_t initval)307 __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
308 {
309 a += RTE_JHASH_GOLDEN_RATIO + initval;
310 b += RTE_JHASH_GOLDEN_RATIO + initval;
311 c += RTE_JHASH_GOLDEN_RATIO + initval;
312
313 __rte_jhash_final(a, b, c);
314
315 return c;
316 }
317
318 /**
319 * A special ultra-optimized versions that knows it is hashing exactly
320 * 3 words.
321 *
322 * @param a
323 * First word to calculate hash of.
324 * @param b
325 * Second word to calculate hash of.
326 * @param c
327 * Third word to calculate hash of.
328 * @param initval
329 * Initialising value of hash.
330 * @return
331 * Calculated hash value.
332 */
333 static inline uint32_t
rte_jhash_3words(uint32_t a,uint32_t b,uint32_t c,uint32_t initval)334 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
335 {
336 return __rte_jhash_3words(a + 12, b + 12, c + 12, initval);
337 }
338
339 /**
340 * A special ultra-optimized versions that knows it is hashing exactly
341 * 2 words.
342 *
343 * @param a
344 * First word to calculate hash of.
345 * @param b
346 * Second word to calculate hash of.
347 * @param initval
348 * Initialising value of hash.
349 * @return
350 * Calculated hash value.
351 */
352 static inline uint32_t
rte_jhash_2words(uint32_t a,uint32_t b,uint32_t initval)353 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
354 {
355 return __rte_jhash_3words(a + 8, b + 8, 8, initval);
356 }
357
358 /**
359 * A special ultra-optimized versions that knows it is hashing exactly
360 * 1 word.
361 *
362 * @param a
363 * Word to calculate hash of.
364 * @param initval
365 * Initialising value of hash.
366 * @return
367 * Calculated hash value.
368 */
369 static inline uint32_t
rte_jhash_1word(uint32_t a,uint32_t initval)370 rte_jhash_1word(uint32_t a, uint32_t initval)
371 {
372 return __rte_jhash_3words(a + 4, 4, 4, initval);
373 }
374
375 #ifdef __cplusplus
376 }
377 #endif
378
379 #endif /* _RTE_JHASH_H */
380