Branch data Line data Source code
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 : : #include <stdint.h>
15 : : #include <string.h>
16 : : #include <limits.h>
17 : :
18 : : #include <rte_config.h>
19 : : #include <rte_log.h>
20 : : #include <rte_byteorder.h>
21 : :
22 : : #ifdef __cplusplus
23 : : extern "C" {
24 : : #endif
25 : :
26 : : /* jhash.h: Jenkins hash support.
27 : : *
28 : : * Copyright (C) 2006 Bob Jenkins (bob_jenkins@burtleburtle.net)
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
81 : 407106 : __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 : 407106 : a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc;
88 : 407106 : 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 [ + + ]: 814210 : while (length > 12) {
103 : 407104 : a += k[0];
104 : 407104 : b += k[1];
105 : 407104 : c += k[2];
106 : :
107 : 407104 : __rte_jhash_mix(a, b, c);
108 : :
109 : 407104 : k += 3;
110 : 407104 : length -= 12;
111 : : }
112 : :
113 [ - + + + : 407106 : switch (length) {
+ + + + +
+ + - + ]
114 : 0 : case 12:
115 : 0 : c += k[2]; b += k[1]; a += k[0]; break;
116 : 1 : case 11:
117 : 1 : c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
118 : 1 : case 10:
119 : 1 : c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
120 : 2 : case 9:
121 : 2 : c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
122 : 7625 : case 8:
123 : 7625 : b += k[1]; a += k[0]; break;
124 : 2 : case 7:
125 : 2 : b += k[1] & LOWER24b_MASK; a += k[0]; break;
126 : 1 : case 6:
127 : 1 : b += k[1] & LOWER16b_MASK; a += k[0]; break;
128 : 1 : case 5:
129 : 1 : b += k[1] & LOWER8b_MASK; a += k[0]; break;
130 : 399469 : case 4:
131 : 399469 : a += k[0]; break;
132 : 2 : case 3:
133 : 2 : a += k[0] & LOWER24b_MASK; break;
134 : 1 : case 2:
135 : 1 : a += k[0] & LOWER16b_MASK; break;
136 : 0 : case 1:
137 : 0 : a += k[0] & LOWER8b_MASK; break;
138 : : /* zero length strings require no mixing */
139 : 1 : case 0:
140 : 1 : *pc = c;
141 : 1 : *pb = b;
142 : 1 : 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 : 407105 : __rte_jhash_final(a, b, c);
215 : :
216 : 407105 : *pc = c;
217 : 407105 : *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
236 : : rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
237 : : {
238 : 407102 : __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
257 : : rte_jhash_32b_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb)
258 : : {
259 : 4 : __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
280 : 399481 : rte_jhash(const void *key, uint32_t length, uint32_t initval)
281 : : {
282 : 407102 : uint32_t initval2 = 0;
283 : :
284 : : rte_jhash_2hashes(key, length, &initval, &initval2);
285 : :
286 [ # # # # : 407102 : 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
303 : 0 : rte_jhash_32b(const uint32_t *k, uint32_t length, uint32_t initval)
304 : : {
305 : 4 : uint32_t initval2 = 0;
306 : :
307 : : rte_jhash_32b_2hashes(k, length, &initval, &initval2);
308 : :
309 [ # # ]: 4 : return initval;
310 : : }
311 : :
312 : : static inline uint32_t
313 : 6 : __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
314 : : {
315 : 6 : a += RTE_JHASH_GOLDEN_RATIO + initval;
316 : 6 : b += RTE_JHASH_GOLDEN_RATIO + initval;
317 : 6 : c += RTE_JHASH_GOLDEN_RATIO + initval;
318 : :
319 : 6 : __rte_jhash_final(a, b, c);
320 : :
321 : 6 : 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
340 : : rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
341 : : {
342 [ # # ]: 2 : 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
359 : : rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
360 : : {
361 [ # # ]: 2 : 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
376 : 0 : rte_jhash_1word(uint32_t a, uint32_t initval)
377 : : {
378 [ # # ]: 2 : return __rte_jhash_3words(a + 4, 4, 4, initval);
379 : : }
380 : :
381 : : #ifdef __cplusplus
382 : : }
383 : : #endif
384 : :
385 : : #endif /* _RTE_JHASH_H */
|
