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.
23 /* This is the public domain lookup3 hash by Bob Jenkins from
24 * http://burtleburtle.net/bob/c/lookup3.c, modified for style. */
26 #define HASH_ROT(x, k) (((x) << (k)) | ((x) >> (32 - (k))))
28 #define HASH_MIX(a, b, c) \
30 a -= c; a ^= HASH_ROT(c, 4); c += b; \
31 b -= a; b ^= HASH_ROT(a, 6); a += c; \
32 c -= b; c ^= HASH_ROT(b, 8); b += a; \
33 a -= c; a ^= HASH_ROT(c, 16); c += b; \
34 b -= a; b ^= HASH_ROT(a, 19); a += c; \
35 c -= b; c ^= HASH_ROT(b, 4); b += a; \
38 #define HASH_FINAL(a, b, c) \
40 c ^= b; c -= HASH_ROT(b, 14); \
41 a ^= c; a -= HASH_ROT(c, 11); \
42 b ^= a; b -= HASH_ROT(a, 25); \
43 c ^= b; c -= HASH_ROT(b, 16); \
44 a ^= c; a -= HASH_ROT(c, 4); \
45 b ^= a; b -= HASH_ROT(a, 14); \
46 c ^= b; c -= HASH_ROT(b, 24); \
49 uint32_t hash_words(const uint32_t *, size_t n_word, uint32_t basis);
50 uint32_t hash_bytes(const void *, size_t n_bytes, uint32_t basis);
52 static inline uint32_t hash_string(const char *s, uint32_t basis)
54 return hash_bytes(s, strlen(s), basis);
57 /* This is Bob Jenkins' integer hash from
58 * http://burtleburtle.net/bob/hash/integer.html, modified for style. */
59 static inline uint32_t hash_int(uint32_t x, uint32_t basis)
71 static inline uint32_t hash_pointer(const void *p, uint32_t basis)
73 /* Often pointers are hashed simply by casting to integer type, but that
74 * has pitfalls since the lower bits of a pointer are often all 0 for
75 * alignment reasons. It's hard to guess where the entropy really is, so
76 * we give up here and just use a high-quality hash function.
78 * The double cast suppresses a warning on 64-bit systems about casting to
79 * an integer to different size. That's OK in this case, since most of the
80 * entropy in the pointer is almost certainly in the lower 32 bits. */
81 return hash_int((uint32_t) (uintptr_t) p, basis);