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