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