lib/librte_hash/rte_jhash.h

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