lib/librte_hash/rte_jhash.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2014 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
  49 /* jhash.h: Jenkins hash support.
  50  *
  51  * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
  52  *
  53  * http://burtleburtle.net/bob/hash/
  54  *
  55  * These are the credits from Bob's sources:
  56  *
  57  * lookup2.c, by Bob Jenkins, December 1996, Public Domain.
  58  * hash(), hash2(), hash3, and mix() are externally useful functions.
  59  * Routines to test the hash are included if SELF_TEST is defined.
  60  * You can use this free for any purpose.  It has no warranty.
  61  *
  62  * $FreeBSD$
  63  */
  64
  65 /** @internal Internal function. NOTE: Arguments are modified. */
  66 #define __rte_jhash_mix(a, b, c) do { \
  67         a -= b; a -= c; a ^= (c>>13); \
  68         b -= c; b -= a; b ^= (a<<8); \
  69         c -= a; c -= b; c ^= (b>>13); \
  70         a -= b; a -= c; a ^= (c>>12); \
  71         b -= c; b -= a; b ^= (a<<16); \
  72         c -= a; c -= b; c ^= (b>>5); \
  73         a -= b; a -= c; a ^= (c>>3); \
  74         b -= c; b -= a; b ^= (a<<10); \
  75         c -= a; c -= b; c ^= (b>>15); \
  76 } while (0)
  77
  78 /** The golden ratio: an arbitrary value. */
  79 #define RTE_JHASH_GOLDEN_RATIO      0x9e3779b9
  80
  81 /**
  82  * The most generic version, hashes an arbitrary sequence
  83  * of bytes.  No alignment or length assumptions are made about
  84  * the input key.
  85  *
  86  * @param key
  87  *   Key to calculate hash of.
  88  * @param length
  89  *   Length of key in bytes.
  90  * @param initval
  91  *   Initialising value of hash.
  92  * @return
  93  *   Calculated hash value.
  94  */
  95 static inline uint32_t
  96 rte_jhash(const void *key, uint32_t length, uint32_t initval)
  97 {
  98         uint32_t a, b, c, len;
  99         const uint8_t *k = (const uint8_t *)key;
 100         const uint32_t *k32 = (const uint32_t *)key;
 101
 102         len = length;
 103         a = b = RTE_JHASH_GOLDEN_RATIO;
 104         c = initval;
 105
 106         while (len >= 12) {
 107                 a += k32[0];
 108                 b += k32[1];
 109                 c += k32[2];
 110
 111                 __rte_jhash_mix(a,b,c);
 112
 113                 k += (3 * sizeof(uint32_t)), k32 += 3;
 114                 len -= (3 * sizeof(uint32_t));
 115         }
 116
 117         c += length;
 118         switch (len) {
 119                 case 11: c += ((uint32_t)k[10] << 24);
 120                 case 10: c += ((uint32_t)k[9] << 16);
 121                 case 9 : c += ((uint32_t)k[8] << 8);
 122                 case 8 : b += ((uint32_t)k[7] << 24);
 123                 case 7 : b += ((uint32_t)k[6] << 16);
 124                 case 6 : b += ((uint32_t)k[5] << 8);
 125                 case 5 : b += k[4];
 126                 case 4 : a += ((uint32_t)k[3] << 24);
 127                 case 3 : a += ((uint32_t)k[2] << 16);
 128                 case 2 : a += ((uint32_t)k[1] << 8);
 129                 case 1 : a += k[0];
 130                 default: break;
 131         };
 132
 133         __rte_jhash_mix(a,b,c);
 134
 135         return c;
 136 }
 137
 138 /**
 139  * A special optimized version that handles 1 or more of uint32_ts.
 140  * The length parameter here is the number of uint32_ts in the key.
 141  *
 142  * @param k
 143  *   Key to calculate hash of.
 144  * @param length
 145  *   Length of key in units of 4 bytes.
 146  * @param initval
 147  *   Initialising value of hash.
 148  * @return
 149  *   Calculated hash value.
 150  */
 151 static inline uint32_t
 152 rte_jhash2(uint32_t *k, uint32_t length, uint32_t initval)
 153 {
 154         uint32_t a, b, c, len;
 155
 156         a = b = RTE_JHASH_GOLDEN_RATIO;
 157         c = initval;
 158         len = length;
 159
 160         while (len >= 3) {
 161                 a += k[0];
 162                 b += k[1];
 163                 c += k[2];
 164                 __rte_jhash_mix(a, b, c);
 165                 k += 3; len -= 3;
 166         }
 167
 168         c += length * 4;
 169
 170         switch (len) {
 171                 case 2 : b += k[1];
 172                 case 1 : a += k[0];
 173                 default: break;
 174         };
 175
 176         __rte_jhash_mix(a,b,c);
 177
 178         return c;
 179 }
 180
 181
 182 /**
 183  * A special ultra-optimized versions that knows it is hashing exactly
 184  * 3 words.
 185  *
 186  * @param a
 187  *   First word to calcuate hash of.
 188  * @param b
 189  *   Second word to calcuate hash of.
 190  * @param c
 191  *   Third word to calcuate hash of.
 192  * @param initval
 193  *   Initialising value of hash.
 194  * @return
 195  *   Calculated hash value.
 196  */
 197 static inline uint32_t
 198 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 199 {
 200         a += RTE_JHASH_GOLDEN_RATIO;
 201         b += RTE_JHASH_GOLDEN_RATIO;
 202         c += initval;
 203
 204         __rte_jhash_mix(a, b, c);
 205
 206         /*
 207          * NOTE: In particular the "c += length; __rte_jhash_mix(a,b,c);"
 208          *       normally done at the end is not done here.
 209          */
 210         return c;
 211 }
 212
 213 /**
 214  * A special ultra-optimized versions that knows it is hashing exactly
 215  * 2 words.
 216  *
 217  * @param a
 218  *   First word to calcuate hash of.
 219  * @param b
 220  *   Second word to calcuate hash of.
 221  * @param initval
 222  *   Initialising value of hash.
 223  * @return
 224  *   Calculated hash value.
 225  */
 226 static inline uint32_t
 227 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 228 {
 229         return rte_jhash_3words(a, b, 0, initval);
 230 }
 231
 232 /**
 233  * A special ultra-optimized versions that knows it is hashing exactly
 234  * 1 word.
 235  *
 236  * @param a
 237  *   Word to calcuate hash of.
 238  * @param initval
 239  *   Initialising value of hash.
 240  * @return
 241  *   Calculated hash value.
 242  */
 243 static inline uint32_t
 244 rte_jhash_1word(uint32_t a, uint32_t initval)
 245 {
 246         return rte_jhash_3words(a, 0, 0, initval);
 247 }
 248
 249 #ifdef __cplusplus
 250 }
 251 #endif
 252
 253 #endif /* _RTE_JHASH_H */