]>
Commit | Line | Data |
---|---|---|
064af421 | 1 | /* |
1f26e796 | 2 | * Copyright (c) 2008, 2009, 2010 Nicira Networks. |
064af421 | 3 | * |
a14bc59f BP |
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: | |
064af421 | 7 | * |
a14bc59f BP |
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. | |
064af421 BP |
15 | */ |
16 | #ifndef HASH_H | |
17 | #define HASH_H 1 | |
18 | ||
8e542118 | 19 | #include <stdbool.h> |
064af421 BP |
20 | #include <stddef.h> |
21 | #include <stdint.h> | |
22 | #include <string.h> | |
cce1d8bd | 23 | #include "util.h" |
064af421 BP |
24 | |
25 | /* This is the public domain lookup3 hash by Bob Jenkins from | |
26 | * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */ | |
27 | ||
28 | #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k)))) | |
29 | ||
30 | #define HASH_MIX(a, b, c) \ | |
31 | do { \ | |
32 | a -= c; a ^= HASH_ROT(c, 4); c += b; \ | |
33 | b -= a; b ^= HASH_ROT(a, 6); a += c; \ | |
34 | c -= b; c ^= HASH_ROT(b, 8); b += a; \ | |
35 | a -= c; a ^= HASH_ROT(c, 16); c += b; \ | |
36 | b -= a; b ^= HASH_ROT(a, 19); a += c; \ | |
37 | c -= b; c ^= HASH_ROT(b, 4); b += a; \ | |
38 | } while (0) | |
39 | ||
40 | #define HASH_FINAL(a, b, c) \ | |
41 | do { \ | |
42 | c ^= b; c -= HASH_ROT(b, 14); \ | |
43 | a ^= c; a -= HASH_ROT(c, 11); \ | |
44 | b ^= a; b -= HASH_ROT(a, 25); \ | |
45 | c ^= b; c -= HASH_ROT(b, 16); \ | |
46 | a ^= c; a -= HASH_ROT(c, 4); \ | |
47 | b ^= a; b -= HASH_ROT(a, 14); \ | |
48 | c ^= b; c -= HASH_ROT(b, 24); \ | |
49 | } while (0) | |
50 | ||
51 | uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis); | |
1f26e796 BP |
52 | uint32_t hash_2words(uint32_t, uint32_t); |
53 | uint32_t hash_3words(uint32_t, uint32_t, uint32_t); | |
064af421 BP |
54 | uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis); |
55 | ||
56 | static inline uint32_t hash_string(const char *s, uint32_t basis) | |
57 | { | |
58 | return hash_bytes(s, strlen(s), basis); | |
59 | } | |
60 | ||
61 | /* This is Bob Jenkins' integer hash from | |
1f26e796 BP |
62 | * http://burtleburtle.net/bob/hash/integer.html, modified for style. |
63 | * | |
64 | * This hash is faster than hash_2words(), but it isn't as good when 'basis' is | |
65 | * important. So use this function for speed or hash_2words() for hash | |
66 | * quality. */ | |
064af421 BP |
67 | static inline uint32_t hash_int(uint32_t x, uint32_t basis) |
68 | { | |
69 | x -= x << 6; | |
70 | x ^= x >> 17; | |
71 | x -= x << 9; | |
72 | x ^= x << 4; | |
44528c54 | 73 | x += basis; |
064af421 BP |
74 | x -= x << 3; |
75 | x ^= x << 10; | |
76 | x ^= x >> 15; | |
44528c54 | 77 | return x; |
064af421 BP |
78 | } |
79 | ||
8e542118 BP |
80 | /* An attempt at a useful 1-bit hash function. Has not been analyzed for |
81 | * quality. */ | |
82 | static inline uint32_t hash_boolean(bool x, uint32_t basis) | |
83 | { | |
84 | enum { P0 = 0xc2b73583 }; /* This is hash_int(1, 0). */ | |
85 | enum { P1 = 0xe90f1258 }; /* This is hash_int(2, 0). */ | |
86 | return (x ? P0 : P1) ^ HASH_ROT(basis, 1); | |
87 | } | |
88 | ||
cce1d8bd BP |
89 | static inline uint32_t hash_double(double x, uint32_t basis) |
90 | { | |
91f227ca JG |
91 | uint32_t value[2]; |
92 | BUILD_ASSERT_DECL(sizeof x == sizeof value); | |
93 | ||
94 | memcpy(value, &x, sizeof value); | |
1f26e796 | 95 | return hash_3words(value[0], value[1], basis); |
cce1d8bd BP |
96 | } |
97 | ||
00644675 BP |
98 | static inline uint32_t hash_pointer(const void *p, uint32_t basis) |
99 | { | |
100 | /* Often pointers are hashed simply by casting to integer type, but that | |
101 | * has pitfalls since the lower bits of a pointer are often all 0 for | |
102 | * alignment reasons. It's hard to guess where the entropy really is, so | |
103 | * we give up here and just use a high-quality hash function. | |
104 | * | |
105 | * The double cast suppresses a warning on 64-bit systems about casting to | |
106 | * an integer to different size. That's OK in this case, since most of the | |
107 | * entropy in the pointer is almost certainly in the lower 32 bits. */ | |
108 | return hash_int((uint32_t) (uintptr_t) p, basis); | |
109 | } | |
110 | ||
064af421 | 111 | #endif /* hash.h */ |