rte_jhash.h

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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 */
Cache object: 2bc1f0fa5a7f352ba05f8933603219ed
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/dpdk_rte_lpm/rte_jhash.h

FreeBSD/Linux Kernel Cross Reference
sys/contrib/dpdk_rte_lpm/rte_jhash.h
