sys/contrib/dpdk_rte_lpm/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 <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 */