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