Branch data Line data Source code
1 : : /*
2 : : * Copyright (c) 2008, 2009, 2010, 2012, 2013, 2014, 2016 Nicira, Inc.
3 : : *
4 : : * Licensed under the Apache License, Version 2.0 (the "License");
5 : : * you may not use this file except in compliance with the License.
6 : : * You may obtain a copy of the License at:
7 : : *
8 : : * http://www.apache.org/licenses/LICENSE-2.0
9 : : *
10 : : * Unless required by applicable law or agreed to in writing, software
11 : : * distributed under the License is distributed on an "AS IS" BASIS,
12 : : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 : : * See the License for the specific language governing permissions and
14 : : * limitations under the License.
15 : : */
16 : : #ifndef HASH_H
17 : : #define HASH_H 1
18 : :
19 : : #include <stdbool.h>
20 : : #include <stddef.h>
21 : : #include <stdint.h>
22 : : #include <string.h>
23 : : #include "util.h"
24 : :
25 : : #ifdef __cplusplus
26 : : extern "C" {
27 : : #endif
28 : :
29 : : static inline uint32_t
30 : 4295057588 : hash_rot(uint32_t x, int k)
31 : : {
32 : 4295057588 : return (x << k) | (x >> (32 - k));
33 : : }
34 : :
35 : : uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis);
36 : : /* The hash input must be a word larger than 128 bits. */
37 : : void hash_bytes128(const void *_, size_t n_bytes, uint32_t basis,
38 : : ovs_u128 *out);
39 : :
40 : : static inline uint32_t hash_int(uint32_t x, uint32_t basis);
41 : : static inline uint32_t hash_2words(uint32_t, uint32_t);
42 : : static inline uint32_t hash_uint64(const uint64_t);
43 : : static inline uint32_t hash_uint64_basis(const uint64_t x,
44 : : const uint32_t basis);
45 : : uint32_t hash_3words(uint32_t, uint32_t, uint32_t);
46 : :
47 : : static inline uint32_t hash_boolean(bool x, uint32_t basis);
48 : : uint32_t hash_double(double, uint32_t basis);
49 : :
50 : : static inline uint32_t hash_pointer(const void *, uint32_t basis);
51 : : static inline uint32_t hash_string(const char *, uint32_t basis);
52 : :
53 : : /* Murmurhash by Austin Appleby,
54 : : * from http://code.google.com/p/smhasher/source/browse/trunk/MurmurHash3.cpp.
55 : : *
56 : : * The upstream license there says:
57 : : *
58 : : * // MurmurHash3 was written by Austin Appleby, and is placed in the public
59 : : * // domain. The author hereby disclaims copyright to this source code.
60 : : *
61 : : * See hash_words() for sample usage. */
62 : :
63 : 2147527713 : static inline uint32_t mhash_add__(uint32_t hash, uint32_t data)
64 : : {
65 : 2147527713 : data *= 0xcc9e2d51;
66 : 2147527713 : data = hash_rot(data, 15);
67 : 2147527725 : data *= 0x1b873593;
68 : 2147527725 : return hash ^ data;
69 : : }
70 : :
71 : 2147527743 : static inline uint32_t mhash_add(uint32_t hash, uint32_t data)
72 : : {
73 : 2147527743 : hash = mhash_add__(hash, data);
74 : 2147527656 : hash = hash_rot(hash, 13);
75 : 2147527658 : return hash * 5 + 0xe6546b64;
76 : : }
77 : :
78 : 602882909 : static inline uint32_t mhash_finish(uint32_t hash)
79 : : {
80 : 602882909 : hash ^= hash >> 16;
81 : 602882909 : hash *= 0x85ebca6b;
82 : 602882909 : hash ^= hash >> 13;
83 : 602882909 : hash *= 0xc2b2ae35;
84 : 602882909 : hash ^= hash >> 16;
85 : 602882909 : return hash;
86 : : }
87 : :
88 : : #if !(defined(__SSE4_2__) && defined(__x86_64__))
89 : : /* Mhash-based implementation. */
90 : :
91 : 2147527748 : static inline uint32_t hash_add(uint32_t hash, uint32_t data)
92 : : {
93 : 2147527748 : return mhash_add(hash, data);
94 : : }
95 : :
96 : 692178496 : static inline uint32_t hash_add64(uint32_t hash, uint64_t data)
97 : : {
98 : 692178496 : return hash_add(hash_add(hash, data), data >> 32);
99 : : }
100 : :
101 : 602882896 : static inline uint32_t hash_finish(uint32_t hash, uint32_t final)
102 : : {
103 : 602882896 : return mhash_finish(hash ^ final);
104 : : }
105 : :
106 : : /* Returns the hash of the 'n' 32-bit words at 'p', starting from 'basis'.
107 : : * 'p' must be properly aligned.
108 : : *
109 : : * This is inlined for the compiler to have access to the 'n_words', which
110 : : * in many cases is a constant. */
111 : : static inline uint32_t
112 : 6908993 : hash_words_inline(const uint32_t p[], size_t n_words, uint32_t basis)
113 : : {
114 : : uint32_t hash;
115 : : size_t i;
116 : :
117 : 6908993 : hash = basis;
118 [ + + ]: 27741678 : for (i = 0; i < n_words; i++) {
119 : 20832684 : hash = hash_add(hash, p[i]);
120 : : }
121 : 6908994 : return hash_finish(hash, n_words * 4);
122 : : }
123 : :
124 : : static inline uint32_t
125 : 4372417 : hash_words64_inline(const uint64_t p[], size_t n_words, uint32_t basis)
126 : : {
127 : : uint32_t hash;
128 : : size_t i;
129 : :
130 : 4372417 : hash = basis;
131 [ + + ]: 323495548 : for (i = 0; i < n_words; i++) {
132 : 319123131 : hash = hash_add64(hash, p[i]);
133 : : }
134 : 4372417 : return hash_finish(hash, n_words * 8);
135 : : }
136 : :
137 : 1751397 : static inline uint32_t hash_pointer(const void *p, uint32_t basis)
138 : : {
139 : : /* Often pointers are hashed simply by casting to integer type, but that
140 : : * has pitfalls since the lower bits of a pointer are often all 0 for
141 : : * alignment reasons. It's hard to guess where the entropy really is, so
142 : : * we give up here and just use a high-quality hash function.
143 : : *
144 : : * The double cast suppresses a warning on 64-bit systems about casting to
145 : : * an integer to different size. That's OK in this case, since most of the
146 : : * entropy in the pointer is almost certainly in the lower 32 bits. */
147 : 1751397 : return hash_int((uint32_t) (uintptr_t) p, basis);
148 : : }
149 : :
150 : 303576503 : static inline uint32_t hash_2words(uint32_t x, uint32_t y)
151 : : {
152 : 303576503 : return hash_finish(hash_add(hash_add(x, 0), y), 8);
153 : : }
154 : :
155 : 3431554 : static inline uint32_t hash_uint64_basis(const uint64_t x,
156 : : const uint32_t basis)
157 : : {
158 : 3431554 : return hash_finish(hash_add64(basis, x), 8);
159 : : }
160 : :
161 : 3341802 : static inline uint32_t hash_uint64(const uint64_t x)
162 : : {
163 : 3341802 : return hash_uint64_basis(x, 0);
164 : : }
165 : :
166 : : #else /* __SSE4_2__ && __x86_64__ */
167 : : #include <smmintrin.h>
168 : :
169 : : static inline uint32_t hash_add(uint32_t hash, uint32_t data)
170 : : {
171 : : return _mm_crc32_u32(hash, data);
172 : : }
173 : :
174 : : /* Add the halves of 'data' in the memory order. */
175 : : static inline uint32_t hash_add64(uint32_t hash, uint64_t data)
176 : : {
177 : : return _mm_crc32_u64(hash, data);
178 : : }
179 : :
180 : : static inline uint32_t hash_finish(uint64_t hash, uint64_t final)
181 : : {
182 : : /* The finishing multiplier 0x805204f3 has been experimentally
183 : : * derived to pass the testsuite hash tests. */
184 : : hash = _mm_crc32_u64(hash, final) * 0x805204f3;
185 : : return hash ^ (uint32_t)hash >> 16; /* Increase entropy in LSBs. */
186 : : }
187 : :
188 : : /* Returns the hash of the 'n' 32-bit words at 'p_', starting from 'basis'.
189 : : * We access 'p_' as a uint64_t pointer, which is fine for __SSE_4_2__.
190 : : *
191 : : * This is inlined for the compiler to have access to the 'n_words', which
192 : : * in many cases is a constant. */
193 : : static inline uint32_t
194 : : hash_words_inline(const uint32_t p_[], size_t n_words, uint32_t basis)
195 : : {
196 : : const uint64_t *p = (const void *)p_;
197 : : uint64_t hash1 = basis;
198 : : uint64_t hash2 = 0;
199 : : uint64_t hash3 = n_words;
200 : : const uint32_t *endp = (const uint32_t *)p + n_words;
201 : : const uint64_t *limit = p + n_words / 2 - 3;
202 : :
203 : : while (p <= limit) {
204 : : hash1 = _mm_crc32_u64(hash1, p[0]);
205 : : hash2 = _mm_crc32_u64(hash2, p[1]);
206 : : hash3 = _mm_crc32_u64(hash3, p[2]);
207 : : p += 3;
208 : : }
209 : : switch (endp - (const uint32_t *)p) {
210 : : case 1:
211 : : hash1 = _mm_crc32_u32(hash1, *(const uint32_t *)&p[0]);
212 : : break;
213 : : case 2:
214 : : hash1 = _mm_crc32_u64(hash1, p[0]);
215 : : break;
216 : : case 3:
217 : : hash1 = _mm_crc32_u64(hash1, p[0]);
218 : : hash2 = _mm_crc32_u32(hash2, *(const uint32_t *)&p[1]);
219 : : break;
220 : : case 4:
221 : : hash1 = _mm_crc32_u64(hash1, p[0]);
222 : : hash2 = _mm_crc32_u64(hash2, p[1]);
223 : : break;
224 : : case 5:
225 : : hash1 = _mm_crc32_u64(hash1, p[0]);
226 : : hash2 = _mm_crc32_u64(hash2, p[1]);
227 : : hash3 = _mm_crc32_u32(hash3, *(const uint32_t *)&p[2]);
228 : : break;
229 : : }
230 : : return hash_finish(hash1, hash2 << 32 | hash3);
231 : : }
232 : :
233 : : /* A simpler version for 64-bit data.
234 : : * 'n_words' is the count of 64-bit words, basis is 64 bits. */
235 : : static inline uint32_t
236 : : hash_words64_inline(const uint64_t p[], size_t n_words, uint32_t basis)
237 : : {
238 : : uint64_t hash1 = basis;
239 : : uint64_t hash2 = 0;
240 : : uint64_t hash3 = n_words;
241 : : const uint64_t *endp = p + n_words;
242 : : const uint64_t *limit = endp - 3;
243 : :
244 : : while (p <= limit) {
245 : : hash1 = _mm_crc32_u64(hash1, p[0]);
246 : : hash2 = _mm_crc32_u64(hash2, p[1]);
247 : : hash3 = _mm_crc32_u64(hash3, p[2]);
248 : : p += 3;
249 : : }
250 : : switch (endp - p) {
251 : : case 1:
252 : : hash1 = _mm_crc32_u64(hash1, p[0]);
253 : : break;
254 : : case 2:
255 : : hash1 = _mm_crc32_u64(hash1, p[0]);
256 : : hash2 = _mm_crc32_u64(hash2, p[1]);
257 : : break;
258 : : }
259 : : return hash_finish(hash1, hash2 << 32 | hash3);
260 : : }
261 : :
262 : : static inline uint32_t hash_uint64_basis(const uint64_t x,
263 : : const uint32_t basis)
264 : : {
265 : : /* '23' chosen to mix bits enough for the test-hash to pass. */
266 : : return hash_finish(hash_add64(basis, x), 23);
267 : : }
268 : :
269 : : static inline uint32_t hash_uint64(const uint64_t x)
270 : : {
271 : : return hash_uint64_basis(x, 0);
272 : : }
273 : :
274 : : static inline uint32_t hash_2words(uint32_t x, uint32_t y)
275 : : {
276 : : return hash_uint64((uint64_t)y << 32 | x);
277 : : }
278 : :
279 : : static inline uint32_t hash_pointer(const void *p, uint32_t basis)
280 : : {
281 : : return hash_uint64_basis((uint64_t) (uintptr_t) p, basis);
282 : : }
283 : : #endif
284 : :
285 : : uint32_t hash_words__(const uint32_t p[], size_t n_words, uint32_t basis);
286 : : uint32_t hash_words64__(const uint64_t p[], size_t n_words, uint32_t basis);
287 : :
288 : : /* Inline the larger hash functions only when 'n_words' is known to be
289 : : * compile-time constant. */
290 : : #if __GNUC__ >= 4
291 : : static inline uint32_t
292 : 13817988 : hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
293 : : {
294 : : if (__builtin_constant_p(n_words)) {
295 : : return hash_words_inline(p, n_words, basis);
296 : : } else {
297 : 6908994 : return hash_words__(p, n_words, basis);
298 : : }
299 : : }
300 : :
301 : : static inline uint32_t
302 : 8744834 : hash_words64(const uint64_t p[], size_t n_words, uint32_t basis)
303 : : {
304 : : if (__builtin_constant_p(n_words)) {
305 : : return hash_words64_inline(p, n_words, basis);
306 : : } else {
307 : 4372417 : return hash_words64__(p, n_words, basis);
308 : : }
309 : : }
310 : :
311 : : #else
312 : :
313 : : static inline uint32_t
314 : : hash_words(const uint32_t p[], size_t n_words, uint32_t basis)
315 : : {
316 : : return hash_words__(p, n_words, basis);
317 : : }
318 : :
319 : : static inline uint32_t
320 : : hash_words64(const uint64_t p[], size_t n_words, uint32_t basis)
321 : : {
322 : : return hash_words64__(p, n_words, basis);
323 : : }
324 : : #endif
325 : :
326 : : static inline uint32_t
327 : 6883490 : hash_bytes32(const uint32_t p[], size_t n_bytes, uint32_t basis)
328 : : {
329 : 6883490 : return hash_words(p, n_bytes / 4, basis);
330 : : }
331 : :
332 : : static inline uint32_t
333 : 4372417 : hash_bytes64(const uint64_t p[], size_t n_bytes, uint32_t basis)
334 : : {
335 : 4372417 : return hash_words64(p, n_bytes / 8, basis);
336 : : }
337 : :
338 : 46892057 : static inline uint32_t hash_string(const char *s, uint32_t basis)
339 : : {
340 : 46892057 : return hash_bytes(s, strlen(s), basis);
341 : : }
342 : :
343 : 10866455 : static inline uint32_t hash_int(uint32_t x, uint32_t basis)
344 : : {
345 : 10866455 : return hash_2words(x, basis);
346 : : }
347 : :
348 : : /* An attempt at a useful 1-bit hash function. Has not been analyzed for
349 : : * quality. */
350 : 2610 : static inline uint32_t hash_boolean(bool x, uint32_t basis)
351 : : {
352 : 2610 : const uint32_t P0 = 0xc2b73583; /* This is hash_int(1, 0). */
353 : 2610 : const uint32_t P1 = 0xe90f1258; /* This is hash_int(2, 0). */
354 [ + + ]: 2610 : return (x ? P0 : P1) ^ hash_rot(basis, 1);
355 : : }
356 : :
357 : : #ifdef __cplusplus
358 : : }
359 : : #endif
360 : :
361 : : #endif /* hash.h */
|
