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 #include <limits.h>
  50
  51 #include <rte_log.h>
  52 #include <rte_byteorder.h>
  53
  54 /* jhash.h: Jenkins hash support.
  55  *
  56  * Copyright (C) 2006 Bob Jenkins (bob_jenkins@burtleburtle.net)
  57  *
  58  * http://burtleburtle.net/bob/hash/
  59  *
  60  * These are the credits from Bob's sources:
  61  *
  62  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  63  *
  64  * These are functions for producing 32-bit hashes for hash table lookup.
  65  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  66  * are externally useful functions.  Routines to test the hash are included
  67  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  68  * the public domain.  It has no warranty.
  69  *
  70  * $FreeBSD$
  71  */
  72
  73 #define rot(x, k) (((x) << (k)) | ((x) >> (32-(k))))
  74
  75 /** @internal Internal function. NOTE: Arguments are modified. */
  76 #define __rte_jhash_mix(a, b, c) do { \
  77         a -= c; a ^= rot(c, 4); c += b; \
  78         b -= a; b ^= rot(a, 6); a += c; \
  79         c -= b; c ^= rot(b, 8); b += a; \
  80         a -= c; a ^= rot(c, 16); c += b; \
  81         b -= a; b ^= rot(a, 19); a += c; \
  82         c -= b; c ^= rot(b, 4); b += a; \
  83 } while (0)
  84
  85 #define __rte_jhash_final(a, b, c) do { \
  86         c ^= b; c -= rot(b, 14); \
  87         a ^= c; a -= rot(c, 11); \
  88         b ^= a; b -= rot(a, 25); \
  89         c ^= b; c -= rot(b, 16); \
  90         a ^= c; a -= rot(c, 4);  \
  91         b ^= a; b -= rot(a, 14); \
  92         c ^= b; c -= rot(b, 24); \
  93 } while (0)
  94
  95 /** The golden ratio: an arbitrary value. */
  96 #define RTE_JHASH_GOLDEN_RATIO      0xdeadbeef
  97
  98 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
  99 #define BIT_SHIFT(x, y, k) (((x) >> (k)) | ((uint64_t)(y) << (32-(k))))
 100 #else
 101 #define BIT_SHIFT(x, y, k) (((uint64_t)(x) << (k)) | ((y) >> (32-(k))))
 102 #endif
 103
 104 #define LOWER8b_MASK rte_le_to_cpu_32(0xff)
 105 #define LOWER16b_MASK rte_le_to_cpu_32(0xffff)
 106 #define LOWER24b_MASK rte_le_to_cpu_32(0xffffff)
 107
 108 static inline void
 109 __rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc,
 110                 uint32_t *pb, unsigned check_align)
 111 {
 112         uint32_t a, b, c;
 113
 114         /* Set up the internal state */
 115         a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc;
 116         c += *pb;
 117
 118         /*
 119          * Check key alignment. For x86 architecture, first case is always optimal
 120          * If check_align is not set, first case will be used
 121          */
 122 #if defined(RTE_ARCH_X86_64) || defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_X32)
 123         const uint32_t *k = (const uint32_t *)key;
 124         const uint32_t s = 0;
 125 #else
 126         const uint32_t *k = (uint32_t *)((uintptr_t)key & (uintptr_t)~3);
 127         const uint32_t s = ((uintptr_t)key & 3) * CHAR_BIT;
 128 #endif
 129         if (!check_align || s == 0) {
 130                 while (length > 12) {
 131                         a += k[0];
 132                         b += k[1];
 133                         c += k[2];
 134
 135                         __rte_jhash_mix(a, b, c);
 136
 137                         k += 3;
 138                         length -= 12;
 139                 }
 140
 141                 switch (length) {
 142                 case 12:
 143                         c += k[2]; b += k[1]; a += k[0]; break;
 144                 case 11:
 145                         c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
 146                 case 10:
 147                         c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
 148                 case 9:
 149                         c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
 150                 case 8:
 151                         b += k[1]; a += k[0]; break;
 152                 case 7:
 153                         b += k[1] & LOWER24b_MASK; a += k[0]; break;
 154                 case 6:
 155                         b += k[1] & LOWER16b_MASK; a += k[0]; break;
 156                 case 5:
 157                         b += k[1] & LOWER8b_MASK; a += k[0]; break;
 158                 case 4:
 159                         a += k[0]; break;
 160                 case 3:
 161                         a += k[0] & LOWER24b_MASK; break;
 162                 case 2:
 163                         a += k[0] & LOWER16b_MASK; break;
 164                 case 1:
 165                         a += k[0] & LOWER8b_MASK; break;
 166                 /* zero length strings require no mixing */
 167                 case 0:
 168                         *pc = c;
 169                         *pb = b;
 170                         return;
 171                 };
 172         } else {
 173                 /* all but the last block: affect some 32 bits of (a, b, c) */
 174                 while (length > 12) {
 175                         a += BIT_SHIFT(k[0], k[1], s);
 176                         b += BIT_SHIFT(k[1], k[2], s);
 177                         c += BIT_SHIFT(k[2], k[3], s);
 178                         __rte_jhash_mix(a, b, c);
 179
 180                         k += 3;
 181                         length -= 12;
 182                 }
 183
 184                 /* last block: affect all 32 bits of (c) */
 185                 switch (length) {
 186                 case 12:
 187                         a += BIT_SHIFT(k[0], k[1], s);
 188                         b += BIT_SHIFT(k[1], k[2], s);
 189                         c += BIT_SHIFT(k[2], k[3], s);
 190                         break;
 191                 case 11:
 192                         a += BIT_SHIFT(k[0], k[1], s);
 193                         b += BIT_SHIFT(k[1], k[2], s);
 194                         c += BIT_SHIFT(k[2], k[3], s) & LOWER24b_MASK;
 195                         break;
 196                 case 10:
 197                         a += BIT_SHIFT(k[0], k[1], s);
 198                         b += BIT_SHIFT(k[1], k[2], s);
 199                         c += BIT_SHIFT(k[2], k[3], s) & LOWER16b_MASK;
 200                         break;
 201                 case 9:
 202                         a += BIT_SHIFT(k[0], k[1], s);
 203                         b += BIT_SHIFT(k[1], k[2], s);
 204                         c += BIT_SHIFT(k[2], k[3], s) & LOWER8b_MASK;
 205                         break;
 206                 case 8:
 207                         a += BIT_SHIFT(k[0], k[1], s);
 208                         b += BIT_SHIFT(k[1], k[2], s);
 209                         break;
 210                 case 7:
 211                         a += BIT_SHIFT(k[0], k[1], s);
 212                         b += BIT_SHIFT(k[1], k[2], s) & LOWER24b_MASK;
 213                         break;
 214                 case 6:
 215                         a += BIT_SHIFT(k[0], k[1], s);
 216                         b += BIT_SHIFT(k[1], k[2], s) & LOWER16b_MASK;
 217                         break;
 218                 case 5:
 219                         a += BIT_SHIFT(k[0], k[1], s);
 220                         b += BIT_SHIFT(k[1], k[2], s) & LOWER8b_MASK;
 221                         break;
 222                 case 4:
 223                         a += BIT_SHIFT(k[0], k[1], s);
 224                         break;
 225                 case 3:
 226                         a += BIT_SHIFT(k[0], k[1], s) & LOWER24b_MASK;
 227                         break;
 228                 case 2:
 229                         a += BIT_SHIFT(k[0], k[1], s) & LOWER16b_MASK;
 230                         break;
 231                 case 1:
 232                         a += BIT_SHIFT(k[0], k[1], s) & LOWER8b_MASK;
 233                         break;
 234                 /* zero length strings require no mixing */
 235                 case 0:
 236                         *pc = c;
 237                         *pb = b;
 238                         return;
 239                 }
 240         }
 241
 242         __rte_jhash_final(a, b, c);
 243
 244         *pc = c;
 245         *pb = b;
 246 }
 247
 248 /**
 249  * Same as rte_jhash, but takes two seeds and return two uint32_ts.
 250  * pc and pb must be non-null, and *pc and *pb must both be initialized
 251  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 252  * the same as the return value from rte_jhash.
 253  *
 254  * @param key
 255  *   Key to calculate hash of.
 256  * @param length
 257  *   Length of key in bytes.
 258  * @param pc
 259  *   IN: seed OUT: primary hash value.
 260  * @param pb
 261  *   IN: second seed OUT: secondary hash value.
 262  */
 263 static inline void
 264 rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
 265 {
 266         __rte_jhash_2hashes(key, length, pc, pb, 1);
 267 }
 268
 269 /**
 270  * Same as rte_jhash_32b, but takes two seeds and return two uint32_ts.
 271  * pc and pb must be non-null, and *pc and *pb must both be initialized
 272  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 273  * the same as the return value from rte_jhash_32b.
 274  *
 275  * @param k
 276  *   Key to calculate hash of.
 277  * @param length
 278  *   Length of key in units of 4 bytes.
 279  * @param pc
 280  *   IN: seed OUT: primary hash value.
 281  * @param pb
 282  *   IN: second seed OUT: secondary hash value.
 283  */
 284 static inline void
 285 rte_jhash_32b_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb)
 286 {
 287         __rte_jhash_2hashes((const void *) k, (length << 2), pc, pb, 0);
 288 }
 289
 290 /**
 291  * The most generic version, hashes an arbitrary sequence
 292  * of bytes.  No alignment or length assumptions are made about
 293  * the input key.
 294  *
 295  * @param key
 296  *   Key to calculate hash of.
 297  * @param length
 298  *   Length of key in bytes.
 299  * @param initval
 300  *   Initialising value of hash.
 301  * @return
 302  *   Calculated hash value.
 303  */
 304 static inline uint32_t
 305 rte_jhash(const void *key, uint32_t length, uint32_t initval)
 306 {
 307         uint32_t initval2 = 0;
 308
 309         rte_jhash_2hashes(key, length, &initval, &initval2);
 310
 311         return initval;
 312 }
 313
 314 /**
 315  * A special optimized version that handles 1 or more of uint32_ts.
 316  * The length parameter here is the number of uint32_ts in the key.
 317  *
 318  * @param k
 319  *   Key to calculate hash of.
 320  * @param length
 321  *   Length of key in units of 4 bytes.
 322  * @param initval
 323  *   Initialising value of hash.
 324  * @return
 325  *   Calculated hash value.
 326  */
 327 static inline uint32_t
 328 rte_jhash_32b(const uint32_t *k, uint32_t length, uint32_t initval)
 329 {
 330         uint32_t initval2 = 0;
 331
 332         rte_jhash_32b_2hashes(k, length, &initval, &initval2);
 333
 334         return initval;
 335 }
 336
 337 static inline uint32_t
 338 __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 339 {
 340         a += RTE_JHASH_GOLDEN_RATIO + initval;
 341         b += RTE_JHASH_GOLDEN_RATIO + initval;
 342         c += RTE_JHASH_GOLDEN_RATIO + initval;
 343
 344         __rte_jhash_final(a, b, c);
 345
 346         return c;
 347 }
 348
 349 /**
 350  * A special ultra-optimized versions that knows it is hashing exactly
 351  * 3 words.
 352  *
 353  * @param a
 354  *   First word to calculate hash of.
 355  * @param b
 356  *   Second word to calculate hash of.
 357  * @param c
 358  *   Third word to calculate hash of.
 359  * @param initval
 360  *   Initialising value of hash.
 361  * @return
 362  *   Calculated hash value.
 363  */
 364 static inline uint32_t
 365 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 366 {
 367         return __rte_jhash_3words(a + 12, b + 12, c + 12, initval);
 368 }
 369
 370 /**
 371  * A special ultra-optimized versions that knows it is hashing exactly
 372  * 2 words.
 373  *
 374  * @param a
 375  *   First word to calculate hash of.
 376  * @param b
 377  *   Second word to calculate hash of.
 378  * @param initval
 379  *   Initialising value of hash.
 380  * @return
 381  *   Calculated hash value.
 382  */
 383 static inline uint32_t
 384 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 385 {
 386         return __rte_jhash_3words(a + 8, b + 8, 8, initval);
 387 }
 388
 389 /**
 390  * A special ultra-optimized versions that knows it is hashing exactly
 391  * 1 word.
 392  *
 393  * @param a
 394  *   Word to calculate hash of.
 395  * @param initval
 396  *   Initialising value of hash.
 397  * @return
 398  *   Calculated hash value.
 399  */
 400 static inline uint32_t
 401 rte_jhash_1word(uint32_t a, uint32_t initval)
 402 {
 403         return __rte_jhash_3words(a + 4, 4, 4, initval);
 404 }
 405
 406 #ifdef __cplusplus
 407 }
 408 #endif
 409
 410 #endif /* _RTE_JHASH_H */