2 * Copyright (c) 2008, 2009 Nicira Networks.
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:
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
25 /* This is the public domain lookup3 hash by Bob Jenkins from
26 * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */
28 #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
30 #define HASH_MIX(a, b, c) \
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; \
40 #define HASH_FINAL(a, b, c) \
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); \
51 uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis);
52 uint32_t hash_2words(const uint32_t *, uint32_t basis);
53 uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis);
55 static inline uint32_t hash_string(const char *s, uint32_t basis)
57 return hash_bytes(s, strlen(s), basis);
60 /* This is Bob Jenkins' integer hash from
61 * http://burtleburtle.net/bob/hash/integer.html, modified for style. */
62 static inline uint32_t hash_int(uint32_t x, uint32_t basis)
75 /* An attempt at a useful 1-bit hash function. Has not been analyzed for
77 static inline uint32_t hash_boolean(bool x, uint32_t basis)
79 enum { P0 = 0xc2b73583 }; /* This is hash_int(1, 0). */
80 enum { P1 = 0xe90f1258 }; /* This is hash_int(2, 0). */
81 return (x ? P0 : P1) ^ HASH_ROT(basis, 1);
84 static inline uint32_t hash_double(double x, uint32_t basis)
87 BUILD_ASSERT_DECL(sizeof x == sizeof value);
89 memcpy(value, &x, sizeof value);
90 return hash_2words(value, basis);
93 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
95 /* Often pointers are hashed simply by casting to integer type, but that
96 * has pitfalls since the lower bits of a pointer are often all 0 for
97 * alignment reasons. It's hard to guess where the entropy really is, so
98 * we give up here and just use a high-quality hash function.
100 * The double cast suppresses a warning on 64-bit systems about casting to
101 * an integer to different size. That's OK in this case, since most of the
102 * entropy in the pointer is almost certainly in the lower 32 bits. */
103 return hash_int((uint32_t) (uintptr_t) p, basis);