4 * Copyright(c) 2010-2012 Intel Corporation. All rights reserved.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
33 * version: DPDK.L.1.2.3-3
51 /* jhash.h: Jenkins hash support.
53 * Copyright (C) 1996 Bob Jenkins (bob_jenkins@burtleburtle.net)
55 * http://burtleburtle.net/bob/hash/
57 * These are the credits from Bob's sources:
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.
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); \
80 /** The golden ratio: an arbitrary value. */
81 #define RTE_JHASH_GOLDEN_RATIO 0x9e3779b9
84 * The most generic version, hashes an arbitrary sequence
85 * of bytes. No alignment or length assumptions are made about
89 * Key to calculate hash of.
91 * Length of key in bytes.
93 * Initialising value of hash.
95 * Calculated hash value.
97 static inline uint32_t
98 rte_jhash(const void *key, uint32_t length, uint32_t initval)
100 uint32_t a, b, c, len;
101 const uint8_t *k = (const uint8_t *) key;
104 a = b = RTE_JHASH_GOLDEN_RATIO;
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));
115 __rte_jhash_mix(a,b,c);
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);
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);
137 __rte_jhash_mix(a,b,c);
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.
147 * Key to calculate hash of.
149 * Length of key in units of 4 bytes.
151 * Initialising value of hash.
153 * Calculated hash value.
155 static inline uint32_t
156 rte_jhash2(uint32_t *k, uint32_t length, uint32_t initval)
158 uint32_t a, b, c, len;
160 a = b = RTE_JHASH_GOLDEN_RATIO;
168 __rte_jhash_mix(a, b, c);
180 __rte_jhash_mix(a,b,c);
187 * A special ultra-optimized versions that knows it is hashing exactly
191 * First word to calcuate hash of.
193 * Second word to calcuate hash of.
195 * Third word to calcuate hash of.
197 * Initialising value of hash.
199 * Calculated hash value.
201 static inline uint32_t
202 rte_jhash_3words(uint32_t a, uint32_t b, uint32_t c, uint32_t initval)
204 a += RTE_JHASH_GOLDEN_RATIO;
205 b += RTE_JHASH_GOLDEN_RATIO;
208 __rte_jhash_mix(a, b, c);
211 * NOTE: In particular the "c += length; __rte_jhash_mix(a,b,c);"
212 * normally done at the end is not done here.
218 * A special ultra-optimized versions that knows it is hashing exactly
221 * NOTE: In partilar the "c += length; __rte_jhash_mix(a,b,c);" normally
222 * done at the end is not done here.
225 * First word to calcuate hash of.
227 * Second word to calcuate hash of.
229 * Initialising value of hash.
231 * Calculated hash value.
233 static inline uint32_t
234 rte_jhash_2words(uint32_t a, uint32_t b, uint32_t initval)
236 return rte_jhash_3words(a, b, 0, initval);
240 * A special ultra-optimized versions that knows it is hashing exactly
243 * NOTE: In partilar the "c += length; __rte_jhash_mix(a,b,c);" normally
244 * done at the end is not done here.
247 * Word to calcuate hash of.
249 * Initialising value of hash.
251 * Calculated hash value.
253 static inline uint32_t
254 rte_jhash_1word(uint32_t a, uint32_t initval)
256 return rte_jhash_3words(a, 0, 0, initval);
263 #endif /* _RTE_JHASH_H */