lib/librte_hash/rte_jhash.h

   1 /*-
   2  *   BSD LICENSE
   3  *
   4  *   Copyright(c) 2010-2012 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
 102         len = length;
 103         a = b = RTE_JHASH_GOLDEN_RATIO;
 104         c = initval;
 105
 106         while (len >= 12) {
 107                 a += (k[0] + ((uint32_t)k[1] << 8) + ((uint32_t)k[2] << 16) +
 108                       ((uint32_t)k[3] << 24));
 109                 b += (k[4] + ((uint32_t)k[5] << 8) + ((uint32_t)k[6] << 16) +
 110                       ((uint32_t)k[7] << 24));
 111                 c += (k[8] + ((uint32_t)k[9] << 8) + ((uint32_t)k[10] << 16) +
 112                       ((uint32_t)k[11] << 24));
 113
 114                 __rte_jhash_mix(a,b,c);
 115
 116                 k += 12;
 117                 len -= 12;
 118         }
 119
 120         c += length;
 121         switch (len) {
 122                 case 11: c += ((uint32_t)k[10] << 24);
 123                 case 10: c += ((uint32_t)k[9] << 16);
 124                 case 9 : c += ((uint32_t)k[8] << 8);
 125                 case 8 : b += ((uint32_t)k[7] << 24);
 126                 case 7 : b += ((uint32_t)k[6] << 16);
 127                 case 6 : b += ((uint32_t)k[5] << 8);
 128                 case 5 : b += k[4];
 129                 case 4 : a += ((uint32_t)k[3] << 24);
 130                 case 3 : a += ((uint32_t)k[2] << 16);
 131                 case 2 : a += ((uint32_t)k[1] << 8);
 132                 case 1 : a += k[0];
 133                 default: break;
 134         };
 135
 136         __rte_jhash_mix(a,b,c);
 137
 138         return c;
 139 }
 140
 141 /**
 142  * A special optimized version that handles 1 or more of uint32_ts.
 143  * The length parameter here is the number of uint32_ts in the key.
 144  *
 145  * @param k
 146  *   Key to calculate hash of.
 147  * @param length
 148  *   Length of key in units of 4 bytes.
 149  * @param initval
 150  *   Initialising value of hash.
 151  * @return
 152  *   Calculated hash value.
 153  */
 154 static inline uint32_t
 155 rte_jhash2(uint32_t *k, uint32_t length, uint32_t initval)
 156 {
 157         uint32_t a, b, c, len;
 158
 159         a = b = RTE_JHASH_GOLDEN_RATIO;
 160         c = initval;
 161         len = length;
 162
 163         while (len >= 3) {
 164                 a += k[0];
 165                 b += k[1];
 166                 c += k[2];
 167                 __rte_jhash_mix(a, b, c);
 168                 k += 3; len -= 3;
 169         }
 170
 171         c += length * 4;
 172
 173         switch (len) {
 174                 case 2 : b += k[1];
 175                 case 1 : a += k[0];
 176                 default: break;
 177         };
 178
 179         __rte_jhash_mix(a,b,c);
 180
 181         return c;
 182 }
 183
 184
 185 /**
 186  * A special ultra-optimized versions that knows it is hashing exactly
 187  * 3 words.
 188  *
 189  * @param a
 190  *   First word to calcuate hash of.
 191  * @param b
 192  *   Second word to calcuate hash of.
 193  * @param c
 194  *   Third word to calcuate hash of.
 195  * @param initval
 196  *   Initialising value of hash.
 197  * @return
 198  *   Calculated hash value.
 199  */
 200 static inline uint32_t
 201 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
 202 {
 203         a += RTE_JHASH_GOLDEN_RATIO;
 204         b += RTE_JHASH_GOLDEN_RATIO;
 205         c += initval;
 206
 207         __rte_jhash_mix(a, b, c);
 208
 209         /*
 210          * NOTE: In particular the "c += length; __rte_jhash_mix(a,b,c);"
 211          *       normally done at the end is not done here.
 212          */
 213         return c;
 214 }
 215
 216 /**
 217  * A special ultra-optimized versions that knows it is hashing exactly
 218  * 2 words.
 219  *
 220  * NOTE: In partilar the "c += length; __rte_jhash_mix(a,b,c);" normally
 221  *       done at the end is not done here.
 222  *
 223  * @param a
 224  *   First word to calcuate hash of.
 225  * @param b
 226  *   Second word to calcuate hash of.
 227  * @param initval
 228  *   Initialising value of hash.
 229  * @return
 230  *   Calculated hash value.
 231  */
 232 static inline uint32_t
 233 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
 234 {
 235         return rte_jhash_3words(a, b, 0, initval);
 236 }
 237
 238 /**
 239  * A special ultra-optimized versions that knows it is hashing exactly
 240  * 1 word.
 241  *
 242  * NOTE: In partilar the "c += length; __rte_jhash_mix(a,b,c);" normally
 243  *       done at the end is not done here.
 244  *
 245  * @param a
 246  *   Word to calcuate hash of.
 247  * @param initval
 248  *   Initialising value of hash.
 249  * @return
 250  *   Calculated hash value.
 251  */
 252 static inline uint32_t
 253 rte_jhash_1word(uint32_t a, uint32_t initval)
 254 {
 255         return rte_jhash_3words(a, 0, 0, initval);
 256 }
 257
 258 #ifdef __cplusplus
 259 }
 260 #endif
 261
 262 #endif /* _RTE_JHASH_H */