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 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 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 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 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 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 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 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 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 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