hash/rte_jhash.h

   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 (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 */