1 /* $NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $ */
2
3 /*
4 * MurmurHash2 -- from the original code:
5 *
6 * "MurmurHash2 was written by Austin Appleby, and is placed in the public
7 * domain. The author hereby disclaims copyright to this source code."
8 *
9 * References:
10 * http://code.google.com/p/smhasher/
11 * https://sites.google.com/site/murmurhash/
12 */
13
14 #include <sys/cdefs.h>
15
16 #if defined(_KERNEL) || defined(_STANDALONE)
17 __KERNEL_RCSID(0, "$NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $");
18
19 #else
20
21 #if defined(LIBC_SCCS) && !defined(lint)
22 __RCSID("$NetBSD: murmurhash.c,v 1.6 2013/10/26 21:06:38 rmind Exp $");
23 #endif /* LIBC_SCCS and not lint */
24
25 #include "namespace.h"
26 #endif
27
28 #include <sys/types.h>
29 #include <sys/param.h>
30 #include <sys/hash.h>
31
32 #if !defined(_KERNEL) && !defined(_STANDALONE)
33 #ifdef __weak_alias
__weak_alias(murmurhash2,_murmurhash2)34 __weak_alias(murmurhash2,_murmurhash2)
35 #endif
36 #endif
37
38 uint32_t
39 murmurhash2(const void *key, size_t len, uint32_t seed)
40 {
41 /*
42 * Note: 'm' and 'r' are mixing constants generated offline.
43 * They're not really 'magic', they just happen to work well.
44 * Initialize the hash to a 'random' value.
45 */
46 const uint32_t m = 0x5bd1e995;
47 const int r = 24;
48
49 const uint8_t *data = key;
50 uint32_t h = seed ^ (uint32_t)len;
51
52 if (__predict_true(ALIGNED_POINTER(key, uint32_t))) {
53 while (len >= sizeof(uint32_t)) {
54 uint32_t k = *(const uint32_t *)data;
55
56 k *= m;
57 k ^= k >> r;
58 k *= m;
59
60 h *= m;
61 h ^= k;
62
63 data += sizeof(uint32_t);
64 len -= sizeof(uint32_t);
65 }
66 } else {
67 while (len >= sizeof(uint32_t)) {
68 uint32_t k;
69
70 k = data[0];
71 k |= data[1] << 8;
72 k |= data[2] << 16;
73 k |= data[3] << 24;
74
75 k *= m;
76 k ^= k >> r;
77 k *= m;
78
79 h *= m;
80 h ^= k;
81
82 data += sizeof(uint32_t);
83 len -= sizeof(uint32_t);
84 }
85 }
86
87 /* Handle the last few bytes of the input array. */
88 switch (len) {
89 case 3:
90 h ^= data[2] << 16;
91 /* FALLTHROUGH */
92 case 2:
93 h ^= data[1] << 8;
94 /* FALLTHROUGH */
95 case 1:
96 h ^= data[0];
97 h *= m;
98 }
99
100 /*
101 * Do a few final mixes of the hash to ensure the last few
102 * bytes are well-incorporated.
103 */
104 h ^= h >> 13;
105 h *= m;
106 h ^= h >> 15;
107
108 return h;
109 }
110