lib/librte_hash/rte_jhash.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2015 Intel Corporation. All rights reserved.
   5  *   All rights reserved.
   6  *
   7  *   Redistribution and use in source and binary forms, with or without
   8  *   modification, are permitted provided that the following conditions
   9  *   are met:
  10  *
  11  *     * Redistributions of source code must retain the above copyright
  12  *       notice, this list of conditions and the following disclaimer.
  13  *     * Redistributions in binary form must reproduce the above copyright
  14  *       notice, this list of conditions and the following disclaimer in
  15  *       the documentation and/or other materials provided with the
  16  *       distribution.
  17  *     * Neither the name of Intel Corporation nor the names of its
  18  *       contributors may be used to endorse or promote products derived
  19  *       from this software without specific prior written permission.
  20  *
  21  *   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  *   "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  *   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  24  *   A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  25  *   OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  26  *   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  27  *   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  28  *   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  29  *   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  30  *   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  31  *   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  32  */
  33
  34 #ifndef _RTE_JHASH_H
  35 #define _RTE_JHASH_H
  36
  37 /**
  38  * @file
  39  *
  40  * jhash functions.
  41  */
  42
  43 #ifdef __cplusplus
  44 extern "C" {
  45 #endif
  46
  47 #include <stdint.h>
  48 #include <string.h>
  49
  50 #include <rte_log.h>
  51 #include <rte_byteorder.h>
  52
  53 /* jhash.h: Jenkins hash support.
  54  *
  55  * Copyright (C) 2006 Bob Jenkins (bob_jenkins@burtleburtle.net)
  56  *
  57  * http://burtleburtle.net/bob/hash/
  58  *
  59  * These are the credits from Bob's sources:
  60  *
  61  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  62  *
  63  * These are functions for producing 32-bit hashes for hash table lookup.
  64  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  65  * are externally useful functions.  Routines to test the hash are included
  66  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  67  * the public domain.  It has no warranty.
  68  *
  69  * $FreeBSD$
  70  */
  71
  72 #define rot(x, k) (((x) << (k)) | ((x) >> (32-(k))))
  73
  74 /** @internal Internal function. NOTE: Arguments are modified. */
  75 #define __rte_jhash_mix(a, b, c) do { \
  76         a -= c; a ^= rot(c, 4); c += b; \
  77         b -= a; b ^= rot(a, 6); a += c; \
  78         c -= b; c ^= rot(b, 8); b += a; \
  79         a -= c; a ^= rot(c, 16); c += b; \
  80         b -= a; b ^= rot(a, 19); a += c; \
  81         c -= b; c ^= rot(b, 4); b += a; \
  82 } while (0)
  83
  84 #define __rte_jhash_final(a, b, c) do { \
  85         c ^= b; c -= rot(b, 14); \
  86         a ^= c; a -= rot(c, 11); \
  87         b ^= a; b -= rot(a, 25); \
  88         c ^= b; c -= rot(b, 16); \
  89         a ^= c; a -= rot(c, 4);  \
  90         b ^= a; b -= rot(a, 14); \
  91         c ^= b; c -= rot(b, 24); \
  92 } while (0)
  93
  94 /** The golden ratio: an arbitrary value. */
  95 #define RTE_JHASH_GOLDEN_RATIO      0xdeadbeef
  96
  97 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
  98 #define BIT_SHIFT(x, y, k) (((x) >> (k)) | ((uint64_t)(y) << (32-(k))))
  99 #else
 100 #define BIT_SHIFT(x, y, k) (((uint64_t)(x) << (k)) | ((y) >> (32-(k))))
 101 #endif
 102
 103 #define LOWER8b_MASK rte_le_to_cpu_32(0xff)
 104 #define LOWER16b_MASK rte_le_to_cpu_32(0xffff)
 105 #define LOWER24b_MASK rte_le_to_cpu_32(0xffffff)
 106
 107 static inline void
 108 __rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc,
 109                 uint32_t *pb, unsigned check_align)
 110 {
 111         uint32_t a, b, c;
 112
 113         /* Set up the internal state */
 114         a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc;
 115         c += *pb;
 116
 117         /*
 118          * Check key alignment. For x86 architecture, first case is always optimal
 119          * If check_align is not set, first case will be used
 120          */
 121 #if defined(RTE_ARCH_X86_64) || defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_X32)
 122         const uint32_t *k = key;
 123         const uint32_t s = 0;
 124 #else
 125         const uint32_t *k = (uint32_t *)(uintptr_t)key & (uintptr_t)~3);
 126         const uint32_t s = ((uintptr_t)key & 3) * CHAR_BIT;
 127 #endif
 128         if (!check_align || s == 0) {
 129                 while (length > 12) {
 130                         a += k[0];
 131                         b += k[1];
 132                         c += k[2];
 133
 134                         __rte_jhash_mix(a, b, c);
 135
 136                         k += 3;
 137                         length -= 12;
 138                 }
 139
 140                 switch (length) {
 141                 case 12:
 142                         c += k[2]; b += k[1]; a += k[0]; break;
 143                 case 11:
 144                         c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
 145                 case 10:
 146                         c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
 147                 case 9:
 148                         c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
 149                 case 8:
 150                         b += k[1]; a += k[0]; break;
 151                 case 7:
 152                         b += k[1] & LOWER24b_MASK; a += k[0]; break;
 153                 case 6:
 154                         b += k[1] & LOWER16b_MASK; a += k[0]; break;
 155                 case 5:
 156                         b += k[1] & LOWER8b_MASK; a += k[0]; break;
 157                 case 4:
 158                         a += k[0]; break;
 159                 case 3:
 160                         a += k[0] & LOWER24b_MASK; break;
 161                 case 2:
 162                         a += k[0] & LOWER16b_MASK; break;
 163                 case 1:
 164                         a += k[0] & LOWER8b_MASK; break;
 165                 /* zero length strings require no mixing */
 166                 case 0:
 167                         *pc = c;
 168                         *pb = b;
 169                         return;
 170                 };
 171         } else {
 172                 /* all but the last block: affect some 32 bits of (a, b, c) */
 173                 while (length > 12) {
 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);
 177                         __rte_jhash_mix(a, b, c);
 178
 179                         k += 3;
 180                         length -= 12;
 181                 }
 182
 183                 /* last block: affect all 32 bits of (c) */
 184                 switch (length) {
 185                 case 12:
 186                         a += BIT_SHIFT(k[0], k[1], s);
 187                         b += BIT_SHIFT(k[1], k[2], s);
 188                         c += BIT_SHIFT(k[2], k[3], s);
 189                         break;
 190                 case 11:
 191                         a += BIT_SHIFT(k[0], k[1], s);
 192                         b += BIT_SHIFT(k[1], k[2], s);
 193                         c += BIT_SHIFT(k[2], k[3], s) & LOWER24b_MASK;
 194                         break;
 195                 case 10:
 196                         a += BIT_SHIFT(k[0], k[1], s);
 197                         b += BIT_SHIFT(k[1], k[2], s);
 198                         c += BIT_SHIFT(k[2], k[3], s) & LOWER16b_MASK;
 199                         break;
 200                 case 9:
 201                         a += BIT_SHIFT(k[0], k[1], s);
 202                         b += BIT_SHIFT(k[1], k[2], s);
 203                         c += BIT_SHIFT(k[2], k[3], s) & LOWER8b_MASK;
 204                         break;
 205                 case 8:
 206                         a += BIT_SHIFT(k[0], k[1], s);
 207                         b += BIT_SHIFT(k[1], k[2], s);
 208                         break;
 209                 case 7:
 210                         a += BIT_SHIFT(k[0], k[1], s);
 211                         b += BIT_SHIFT(k[1], k[2], s) & LOWER24b_MASK;
 212                         break;
 213                 case 6:
 214                         a += BIT_SHIFT(k[0], k[1], s);
 215                         b += BIT_SHIFT(k[1], k[2], s) & LOWER16b_MASK;
 216                         break;
 217                 case 5:
 218                         a += BIT_SHIFT(k[0], k[1], s);
 219                         b += BIT_SHIFT(k[1], k[2], s) & LOWER8b_MASK;
 220                         break;
 221                 case 4:
 222                         a += BIT_SHIFT(k[0], k[1], s);
 223                         break;
 224                 case 3:
 225                         a += BIT_SHIFT(k[0], k[1], s) & LOWER24b_MASK;
 226                         break;
 227                 case 2:
 228                         a += BIT_SHIFT(k[0], k[1], s) & LOWER16b_MASK;
 229                         break;
 230                 case 1:
 231                         a += BIT_SHIFT(k[0], k[1], s) & LOWER8b_MASK;
 232                         break;
 233                 /* zero length strings require no mixing */
 234                 case 0:
 235                         *pc = c;
 236                         *pb = b;
 237                         return;
 238                 }
 239         }
 240
 241         __rte_jhash_final(a, b, c);
 242
 243         *pc = c;
 244         *pb = b;
 245 }
 246
 247 /**
 248  * Same as rte_jhash, but takes two seeds and return two uint32_ts.
 249  * pc and pb must be non-null, and *pc and *pb must both be initialized
 250  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 251  * the same as the return value from rte_jhash.
 252  *
 253  * @param key
 254  *   Key to calculate hash of.
 255  * @param length
 256  *   Length of key in bytes.
 257  * @param pc
 258  *   IN: seed OUT: primary hash value.
 259  * @param pb
 260  *   IN: second seed OUT: secondary hash value.
 261  */
 262 static inline void
 263 rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
 264 {
 265         __rte_jhash_2hashes(key, length, pc, pb, 1);
 266 }
 267
 268 /**
 269  * Same as rte_jhash2, but takes two seeds and return two uint32_ts.
 270  * pc and pb must be non-null, and *pc and *pb must both be initialized
 271  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 272  * the same as the return value from rte_jhash2.
 273  *
 274  * @param k
 275  *   Key to calculate hash of.
 276  * @param length
 277  *   Length of key in units of 4 bytes.
 278  * @param pc
 279  *   IN: seed OUT: primary hash value.
 280  * @param pb
 281  *   IN: second seed OUT: secondary hash value.
 282  */
 283 static inline void
 284 rte_jhash_32b_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb)
 285 {
 286         __rte_jhash_2hashes((const void *) k, (length << 2), pc, pb, 0);
 287 }
 288
 289 /**
 290  * The most generic version, hashes an arbitrary sequence
 291  * of bytes.  No alignment or length assumptions are made about
 292  * the input key.
 293  *
 294  * @param key
 295  *   Key to calculate hash of.
 296  * @param length
 297  *   Length of key in bytes.
 298  * @param initval
 299  *   Initialising value of hash.
 300  * @return
 301  *   Calculated hash value.
 302  */
 303 static inline uint32_t
 304 rte_jhash(const void *key, uint32_t length, uint32_t initval)
 305 {
 306         uint32_t initval2 = 0;
 307
 308         rte_jhash_2hashes(key, length, &initval, &initval2);
 309
 310         return initval;
 311 }
 312
 313 /**
 314  * A special optimized version that handles 1 or more of uint32_ts.
 315  * The length parameter here is the number of uint32_ts in the key.
 316  *
 317  * @param k
 318  *   Key to calculate hash of.
 319  * @param length
 320  *   Length of key in units of 4 bytes.
 321  * @param initval
 322  *   Initialising value of hash.
 323  * @return
 324  *   Calculated hash value.
 325  */
 326 static inline uint32_t
 327 rte_jhash_32b(const uint32_t *k, uint32_t length, uint32_t initval)
 328 {
 329         uint32_t initval2 = 0;
 330
 331         rte_jhash_32b_2hashes(k, length, &initval, &initval2);
 332
 333         return initval;
 334 }
 335
 336 static inline uint32_t
 337 __attribute__ ((deprecated))
 338 rte_jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
 339 {
 340         uint32_t initval2 = 0;
 341
 342         rte_jhash_32b_2hashes(k, length, &initval, &initval2);
 343
 344         return initval;
 345 }
 346
 347 static inline uint32_t
 348 __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 349 {
 350         a += RTE_JHASH_GOLDEN_RATIO + initval;
 351         b += RTE_JHASH_GOLDEN_RATIO + initval;
 352         c += RTE_JHASH_GOLDEN_RATIO + initval;
 353
 354         __rte_jhash_final(a, b, c);
 355
 356         return c;
 357 }
 358
 359 /**
 360  * A special ultra-optimized versions that knows it is hashing exactly
 361  * 3 words.
 362  *
 363  * @param a
 364  *   First word to calculate hash of.
 365  * @param b
 366  *   Second word to calculate hash of.
 367  * @param c
 368  *   Third word to calculate hash of.
 369  * @param initval
 370  *   Initialising value of hash.
 371  * @return
 372  *   Calculated hash value.
 373  */
 374 static inline uint32_t
 375 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 376 {
 377         return __rte_jhash_3words(a + 12, b + 12, c + 12, initval);
 378 }
 379
 380 /**
 381  * A special ultra-optimized versions that knows it is hashing exactly
 382  * 2 words.
 383  *
 384  * @param a
 385  *   First word to calculate hash of.
 386  * @param b
 387  *   Second word to calculate hash of.
 388  * @param initval
 389  *   Initialising value of hash.
 390  * @return
 391  *   Calculated hash value.
 392  */
 393 static inline uint32_t
 394 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 395 {
 396         return __rte_jhash_3words(a + 8, b + 8, 8, initval);
 397 }
 398
 399 /**
 400  * A special ultra-optimized versions that knows it is hashing exactly
 401  * 1 word.
 402  *
 403  * @param a
 404  *   Word to calculate hash of.
 405  * @param initval
 406  *   Initialising value of hash.
 407  * @return
 408  *   Calculated hash value.
 409  */
 410 static inline uint32_t
 411 rte_jhash_1word(uint32_t a, uint32_t initval)
 412 {
 413         return __rte_jhash_3words(a + 4, 4, 4, initval);
 414 }
 415
 416 #ifdef __cplusplus
 417 }
 418 #endif
 419
 420 #endif /* _RTE_JHASH_H */