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 <rte_byteorder.h>
  50
  51 /* jhash.h: Jenkins hash support.
  52  *
  53  * Copyright (C) 2006 Bob Jenkins (bob_jenkins@burtleburtle.net)
  54  *
  55  * http://burtleburtle.net/bob/hash/
  56  *
  57  * These are the credits from Bob's sources:
  58  *
  59  * lookup3.c, by Bob Jenkins, May 2006, Public Domain.
  60  *
  61  * These are functions for producing 32-bit hashes for hash table lookup.
  62  * hashword(), hashlittle(), hashlittle2(), hashbig(), mix(), and final()
  63  * are externally useful functions.  Routines to test the hash are included
  64  * if SELF_TEST is defined.  You can use this free for any purpose.  It's in
  65  * the public domain.  It has no warranty.
  66  *
  67  * $FreeBSD$
  68  */
  69
  70 #define rot(x, k) (((x) << (k)) | ((x) >> (32-(k))))
  71
  72 /** @internal Internal function. NOTE: Arguments are modified. */
  73 #define __rte_jhash_mix(a, b, c) do { \
  74         a -= c; a ^= rot(c, 4); c += b; \
  75         b -= a; b ^= rot(a, 6); a += c; \
  76         c -= b; c ^= rot(b, 8); b += a; \
  77         a -= c; a ^= rot(c, 16); c += b; \
  78         b -= a; b ^= rot(a, 19); a += c; \
  79         c -= b; c ^= rot(b, 4); b += a; \
  80 } while (0)
  81
  82 #define __rte_jhash_final(a, b, c) do { \
  83         c ^= b; c -= rot(b, 14); \
  84         a ^= c; a -= rot(c, 11); \
  85         b ^= a; b -= rot(a, 25); \
  86         c ^= b; c -= rot(b, 16); \
  87         a ^= c; a -= rot(c, 4);  \
  88         b ^= a; b -= rot(a, 14); \
  89         c ^= b; c -= rot(b, 24); \
  90 } while (0)
  91
  92 /** The golden ratio: an arbitrary value. */
  93 #define RTE_JHASH_GOLDEN_RATIO      0xdeadbeef
  94
  95 #if RTE_BYTE_ORDER == RTE_LITTLE_ENDIAN
  96 #define BIT_SHIFT(x, y, k) (((x) >> (k)) | ((uint64_t)(y) << (32-(k))))
  97 #else
  98 #define BIT_SHIFT(x, y, k) (((uint64_t)(x) << (k)) | ((y) >> (32-(k))))
  99 #endif
 100
 101 #define LOWER8b_MASK rte_le_to_cpu_32(0xff)
 102 #define LOWER16b_MASK rte_le_to_cpu_32(0xffff)
 103 #define LOWER24b_MASK rte_le_to_cpu_32(0xffffff)
 104
 105 /**
 106  * The most generic version, hashes an arbitrary sequence
 107  * of bytes.  No alignment or length assumptions are made about
 108  * the input key.
 109  *
 110  * @param key
 111  *   Key to calculate hash of.
 112  * @param length
 113  *   Length of key in bytes.
 114  * @param initval
 115  *   Initialising value of hash.
 116  * @return
 117  *   Calculated hash value.
 118  */
 119 static inline uint32_t
 120 rte_jhash(const void *key, uint32_t length, uint32_t initval)
 121 {
 122         uint32_t a, b, c;
 123
 124         /* Set up the internal state */
 125         a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + initval;
 126
 127         /* Check key alignment. For x86 architecture, first case is always optimal */
 128 #if defined(RTE_ARCH_X86_64) || defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_X32)
 129         const uint32_t *k = key;
 130         const uint32_t s = 0;
 131 #else
 132         const uint32_t *k = (uint32_t *)(uintptr_t)key & (uintptr_t)~3);
 133         const uint32_t s = ((uintptr_t)key & 3) * CHAR_BIT;
 134 #endif
 135
 136         if (s == 0) {
 137                 while (length > 12) {
 138                         a += k[0];
 139                         b += k[1];
 140                         c += k[2];
 141
 142                         __rte_jhash_mix(a, b, c);
 143
 144                         k += 3;
 145                         length -= 12;
 146                 }
 147
 148                 switch (length) {
 149                 case 12:
 150                         c += k[2]; b += k[1]; a += k[0]; break;
 151                 case 11:
 152                         c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
 153                 case 10:
 154                         c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
 155                 case 9:
 156                         c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
 157                 case 8:
 158                         b += k[1]; a += k[0]; break;
 159                 case 7:
 160                         b += k[1] & LOWER24b_MASK; a += k[0]; break;
 161                 case 6:
 162                         b += k[1] & LOWER16b_MASK; a += k[0]; break;
 163                 case 5:
 164                         b += k[1] & LOWER8b_MASK; a += k[0]; break;
 165                 case 4:
 166                         a += k[0]; break;
 167                 case 3:
 168                         a += k[0] & LOWER24b_MASK; break;
 169                 case 2:
 170                         a += k[0] & LOWER16b_MASK; break;
 171                 case 1:
 172                         a += k[0] & LOWER8b_MASK; break;
 173                 /* zero length strings require no mixing */
 174                 case 0:
 175                         return c;
 176                 };
 177         } else {
 178                 /* all but the last block: affect some 32 bits of (a, b, c) */
 179                 while (length > 12) {
 180                         a += BIT_SHIFT(k[0], k[1], s);
 181                         b += BIT_SHIFT(k[1], k[2], s);
 182                         c += BIT_SHIFT(k[2], k[3], s);
 183                         __rte_jhash_mix(a, b, c);
 184
 185                         k += 3;
 186                         length -= 12;
 187                 }
 188
 189                 /* last block: affect all 32 bits of (c) */
 190                 switch (length) {
 191                 case 12:
 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);
 195                         break;
 196                 case 11:
 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) & LOWER24b_MASK;
 200                         break;
 201                 case 10:
 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) & LOWER16b_MASK;
 205                         break;
 206                 case 9:
 207                         a += BIT_SHIFT(k[0], k[1], s);
 208                         b += BIT_SHIFT(k[1], k[2], s);
 209                         c += BIT_SHIFT(k[2], k[3], s) & LOWER8b_MASK;
 210                         break;
 211                 case 8:
 212                         a += BIT_SHIFT(k[0], k[1], s);
 213                         b += BIT_SHIFT(k[1], k[2], s);
 214                         break;
 215                 case 7:
 216                         a += BIT_SHIFT(k[0], k[1], s);
 217                         b += BIT_SHIFT(k[1], k[2], s) & LOWER24b_MASK;
 218                         break;
 219                 case 6:
 220                         a += BIT_SHIFT(k[0], k[1], s);
 221                         b += BIT_SHIFT(k[1], k[2], s) & LOWER16b_MASK;
 222                         break;
 223                 case 5:
 224                         a += BIT_SHIFT(k[0], k[1], s);
 225                         b += BIT_SHIFT(k[1], k[2], s) & LOWER8b_MASK;
 226                         break;
 227                 case 4:
 228                         a += BIT_SHIFT(k[0], k[1], s);
 229                         break;
 230                 case 3:
 231                         a += BIT_SHIFT(k[0], k[1], s) & LOWER24b_MASK;
 232                         break;
 233                 case 2:
 234                         a += BIT_SHIFT(k[0], k[1], s) & LOWER16b_MASK;
 235                         break;
 236                 case 1:
 237                         a += BIT_SHIFT(k[0], k[1], s) & LOWER8b_MASK;
 238                         break;
 239                 /* zero length strings require no mixing */
 240                 case 0:
 241                         return c;
 242                 }
 243         }
 244
 245         __rte_jhash_final(a, b, c);
 246
 247         return c;
 248 }
 249
 250 /**
 251  * A special optimized version that handles 1 or more of uint32_ts.
 252  * The length parameter here is the number of uint32_ts in the key.
 253  *
 254  * @param k
 255  *   Key to calculate hash of.
 256  * @param length
 257  *   Length of key in units of 4 bytes.
 258  * @param initval
 259  *   Initialising value of hash.
 260  * @return
 261  *   Calculated hash value.
 262  */
 263 static inline uint32_t
 264 rte_jhash2(const uint32_t *k, uint32_t length, uint32_t initval)
 265 {
 266         uint32_t a, b, c;
 267
 268         /* Set up the internal state */
 269         a = b = c = RTE_JHASH_GOLDEN_RATIO + (((uint32_t)length) << 2) + initval;
 270
 271         /* Handle most of the key */
 272         while (length > 3) {
 273                 a += k[0];
 274                 b += k[1];
 275                 c += k[2];
 276
 277                 __rte_jhash_mix(a, b, c);
 278
 279                 k += 3;
 280                 length -= 3;
 281         }
 282
 283         /* Handle the last 3 uint32_t's */
 284         switch (length) {
 285         case 3:
 286                 c += k[2];
 287                 /* Fallthrough */
 288         case 2:
 289                 b += k[1];
 290                 /* Fallthrough */
 291         case 1:
 292                 a += k[0];
 293                 __rte_jhash_final(a, b, c);
 294                 /* Fallthrough */
 295         /* case 0: nothing left to add */
 296         case 0:
 297                 break;
 298         };
 299
 300         return c;
 301 }
 302
 303 /**
 304  * Same as rte_jhash, but takes two seeds and return two uint32_ts.
 305  * pc and pb must be non-null, and *pc and *pb must both be initialized
 306  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 307  * the same as the return value from rte_jhash.
 308  *
 309  * @param key
 310  *   Key to calculate hash of.
 311  * @param length
 312  *   Length of key in bytes.
 313  * @param pc
 314  *   IN: seed OUT: primary hash value.
 315  * @param pb
 316  *   IN: second seed OUT: secondary hash value.
 317  */
 318 static inline void
 319 rte_jhash_2hashes(const void *key, uint32_t length, uint32_t *pc, uint32_t *pb)
 320 {
 321         uint32_t a, b, c;
 322
 323         /* Set up the internal state */
 324         a = b = c = RTE_JHASH_GOLDEN_RATIO + ((uint32_t)length) + *pc;
 325         c += *pb;
 326
 327         /* Check key alignment. For x86 architecture, first case is always optimal */
 328 #if defined(RTE_ARCH_X86_64) || defined(RTE_ARCH_I686) || defined(RTE_ARCH_X86_X32)
 329         const uint32_t *k = key;
 330         const uint32_t s = 0;
 331 #else
 332         const uint32_t *k = (uint32_t *)(uintptr_t)key & (uintptr_t)~3);
 333         const uint32_t s = ((uintptr_t)key & 3) * CHAR_BIT;
 334 #endif
 335
 336         if (s == 0) {
 337                 while (length > 12) {
 338                         a += k[0];
 339                         b += k[1];
 340                         c += k[2];
 341
 342                         __rte_jhash_mix(a, b, c);
 343
 344                         k += 3;
 345                         length -= 12;
 346                 }
 347
 348                 switch (length) {
 349                 case 12:
 350                         c += k[2]; b += k[1]; a += k[0]; break;
 351                 case 11:
 352                         c += k[2] & LOWER24b_MASK; b += k[1]; a += k[0]; break;
 353                 case 10:
 354                         c += k[2] & LOWER16b_MASK; b += k[1]; a += k[0]; break;
 355                 case 9:
 356                         c += k[2] & LOWER8b_MASK; b += k[1]; a += k[0]; break;
 357                 case 8:
 358                         b += k[1]; a += k[0]; break;
 359                 case 7:
 360                         b += k[1] & LOWER24b_MASK; a += k[0]; break;
 361                 case 6:
 362                         b += k[1] & LOWER16b_MASK; a += k[0]; break;
 363                 case 5:
 364                         b += k[1] & LOWER8b_MASK; a += k[0]; break;
 365                 case 4:
 366                         a += k[0]; break;
 367                 case 3:
 368                         a += k[0] & LOWER24b_MASK; break;
 369                 case 2:
 370                         a += k[0] & LOWER16b_MASK; break;
 371                 case 1:
 372                         a += k[0] & LOWER8b_MASK; break;
 373                 /* zero length strings require no mixing */
 374                 case 0:
 375                         *pc = c;
 376                         *pb = b;
 377                         return;
 378                 };
 379         } else {
 380                 /* all but the last block: affect some 32 bits of (a, b, c) */
 381                 while (length > 12) {
 382                         a += BIT_SHIFT(k[0], k[1], s);
 383                         b += BIT_SHIFT(k[1], k[2], s);
 384                         c += BIT_SHIFT(k[2], k[3], s);
 385                         __rte_jhash_mix(a, b, c);
 386
 387                         k += 3;
 388                         length -= 12;
 389                 }
 390
 391                 /* last block: affect all 32 bits of (c) */
 392                 switch (length) {
 393                 case 12:
 394                         a += BIT_SHIFT(k[0], k[1], s);
 395                         b += BIT_SHIFT(k[1], k[2], s);
 396                         c += BIT_SHIFT(k[2], k[3], s);
 397                         break;
 398                 case 11:
 399                         a += BIT_SHIFT(k[0], k[1], s);
 400                         b += BIT_SHIFT(k[1], k[2], s);
 401                         c += BIT_SHIFT(k[2], k[3], s) & LOWER24b_MASK;
 402                         break;
 403                 case 10:
 404                         a += BIT_SHIFT(k[0], k[1], s);
 405                         b += BIT_SHIFT(k[1], k[2], s);
 406                         c += BIT_SHIFT(k[2], k[3], s) & LOWER16b_MASK;
 407                         break;
 408                 case 9:
 409                         a += BIT_SHIFT(k[0], k[1], s);
 410                         b += BIT_SHIFT(k[1], k[2], s);
 411                         c += BIT_SHIFT(k[2], k[3], s) & LOWER8b_MASK;
 412                         break;
 413                 case 8:
 414                         a += BIT_SHIFT(k[0], k[1], s);
 415                         b += BIT_SHIFT(k[1], k[2], s);
 416                         break;
 417                 case 7:
 418                         a += BIT_SHIFT(k[0], k[1], s);
 419                         b += BIT_SHIFT(k[1], k[2], s) & LOWER24b_MASK;
 420                         break;
 421                 case 6:
 422                         a += BIT_SHIFT(k[0], k[1], s);
 423                         b += BIT_SHIFT(k[1], k[2], s) & LOWER16b_MASK;
 424                         break;
 425                 case 5:
 426                         a += BIT_SHIFT(k[0], k[1], s);
 427                         b += BIT_SHIFT(k[1], k[2], s) & LOWER8b_MASK;
 428                         break;
 429                 case 4:
 430                         a += BIT_SHIFT(k[0], k[1], s);
 431                         break;
 432                 case 3:
 433                         a += BIT_SHIFT(k[0], k[1], s) & LOWER24b_MASK;
 434                         break;
 435                 case 2:
 436                         a += BIT_SHIFT(k[0], k[1], s) & LOWER16b_MASK;
 437                         break;
 438                 case 1:
 439                         a += BIT_SHIFT(k[0], k[1], s) & LOWER8b_MASK;
 440                         break;
 441                 /* zero length strings require no mixing */
 442                 case 0:
 443                         *pc = c;
 444                         *pb = b;
 445                         return;
 446                 }
 447         }
 448
 449         __rte_jhash_final(a, b, c);
 450
 451         *pc = c;
 452         *pb = b;
 453 }
 454
 455 /**
 456  * Same as rte_jhash2, but takes two seeds and return two uint32_ts.
 457  * pc and pb must be non-null, and *pc and *pb must both be initialized
 458  * with seeds. If you pass in (*pb)=0, the output (*pc) will be
 459  * the same as the return value from rte_jhash2.
 460  *
 461  * @param k
 462  *   Key to calculate hash of.
 463  * @param length
 464  *   Length of key in units of 4 bytes.
 465  * @param pc
 466  *   IN: seed OUT: primary hash value.
 467  * @param pb
 468  *   IN: second seed OUT: secondary hash value.
 469  */
 470 static inline void
 471 rte_jhash2_2hashes(const uint32_t *k, uint32_t length, uint32_t *pc, uint32_t *pb)
 472 {
 473         uint32_t a, b, c;
 474
 475         /* Set up the internal state */
 476         a = b = c = RTE_JHASH_GOLDEN_RATIO + (((uint32_t)length) << 2) + *pc;
 477         c += *pb;
 478
 479         /* Handle most of the key */
 480         while (length > 3) {
 481                 a += k[0];
 482                 b += k[1];
 483                 c += k[2];
 484
 485                 __rte_jhash_mix(a, b, c);
 486
 487                 k += 3;
 488                 length -= 3;
 489         }
 490
 491         /* Handle the last 3 uint32_t's */
 492         switch (length) {
 493         case 3:
 494                 c += k[2];
 495                 /* Fallthrough */
 496         case 2:
 497                 b += k[1];
 498                 /* Fallthrough */
 499         case 1:
 500                 a += k[0];
 501                 __rte_jhash_final(a, b, c);
 502                 /* Fallthrough */
 503         /* case 0: nothing left to add */
 504         case 0:
 505                 break;
 506         };
 507
 508         *pc = c;
 509         *pb = b;
 510 }
 511
 512 static inline uint32_t
 513 __rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 514 {
 515         a += RTE_JHASH_GOLDEN_RATIO + initval;
 516         b += RTE_JHASH_GOLDEN_RATIO + initval;
 517         c += RTE_JHASH_GOLDEN_RATIO + initval;
 518
 519         __rte_jhash_final(a, b, c);
 520
 521         return c;
 522 }
 523
 524 /**
 525  * A special ultra-optimized versions that knows it is hashing exactly
 526  * 3 words.
 527  *
 528  * @param a
 529  *   First word to calcuate hash of.
 530  * @param b
 531  *   Second word to calcuate hash of.
 532  * @param c
 533  *   Third word to calcuate hash of.
 534  * @param initval
 535  *   Initialising value of hash.
 536  * @return
 537  *   Calculated hash value.
 538  */
 539 static inline uint32_t
 540 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 541 {
 542         return __rte_jhash_3words(a + 12, b + 12, c + 12, initval);
 543 }
 544
 545 /**
 546  * A special ultra-optimized versions that knows it is hashing exactly
 547  * 2 words.
 548  *
 549  * @param a
 550  *   First word to calcuate hash of.
 551  * @param b
 552  *   Second word to calcuate hash of.
 553  * @param initval
 554  *   Initialising value of hash.
 555  * @return
 556  *   Calculated hash value.
 557  */
 558 static inline uint32_t
 559 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 560 {
 561         return __rte_jhash_3words(a + 8, b + 8, 8, initval);
 562 }
 563
 564 /**
 565  * A special ultra-optimized versions that knows it is hashing exactly
 566  * 1 word.
 567  *
 568  * @param a
 569  *   Word to calcuate hash of.
 570  * @param initval
 571  *   Initialising value of hash.
 572  * @return
 573  *   Calculated hash value.
 574  */
 575 static inline uint32_t
 576 rte_jhash_1word(uint32_t a, uint32_t initval)
 577 {
 578         return __rte_jhash_3words(a + 4, 4, 4, initval);
 579 }
 580
 581 #ifdef __cplusplus
 582 }
 583 #endif
 584
 585 #endif /* _RTE_JHASH_H */