Loading...
Searching...
No Matches
murmurhash.h File Reference
Include dependency graph for murmurhash.h:
This graph shows which files directly or indirectly include this file:
Go to the source code of this file.
Functions | |
| FORCE_INLINE uint32_t | derive_c_rotl32 (uint32_t x, int8_t r) |
| MurmurHash3 implementation, copied (with love) from Austin Appleby's implementation | |
| FORCE_INLINE uint64_t | derive_c_rotl64 (uint64_t x, int8_t r) |
| FORCE_INLINE uint32_t | derive_c_getblock32 (const uint32_t *p, int i) |
| FORCE_INLINE uint64_t | derive_c_getblock64 (const uint64_t *p, int i) |
| FORCE_INLINE uint32_t | derive_c_fmix32 (uint32_t h) |
| FORCE_INLINE uint64_t | derive_c_fmix64 (uint64_t k) |
| void | derive_c_MurmurHash3_x86_32 (const void *key, int len, uint32_t seed, void *out) |
| void | derive_c_MurmurHash3_x86_128 (const void *key, const int len, uint32_t seed, void *out) |
| void | derive_c_MurmurHash3_x64_128 (const void *key, const int len, const uint32_t seed, void *out) |
| size_t | derive_c_murmurhash (const void *key, int len, uint32_t seed) |
Function Documentation
◆ derive_c_fmix32()
| FORCE_INLINE uint32_t derive_c_fmix32 | ( | uint32_t | h | ) |
Definition at line 15 of file murmurhash.h.
15 {
16 h ^= h >> 16;
17 h *= 0x85ebca6b;
18 h ^= h >> 13;
19 h *= 0xc2b2ae35;
20 h ^= h >> 16;
21
22 return h;
23}
Here is the caller graph for this function:
◆ derive_c_fmix64()
| FORCE_INLINE uint64_t derive_c_fmix64 | ( | uint64_t | k | ) |
Definition at line 25 of file murmurhash.h.
25 {
26 k ^= k >> 33;
27 k *= 0xff51afd7ed558ccdLLU;
28 k ^= k >> 33;
29 k *= 0xc4ceb9fe1a85ec53LLU;
30 k ^= k >> 33;
31
32 return k;
33}
Here is the caller graph for this function:
◆ derive_c_getblock32()
| FORCE_INLINE uint32_t derive_c_getblock32 | ( | const uint32_t * | p, |
| int | i ) |
Definition at line 11 of file murmurhash.h.
11{ return p[i]; }
Here is the caller graph for this function:
◆ derive_c_getblock64()
| FORCE_INLINE uint64_t derive_c_getblock64 | ( | const uint64_t * | p, |
| int | i ) |
Definition at line 13 of file murmurhash.h.
13{ return p[i]; }
Here is the caller graph for this function:
◆ derive_c_murmurhash()
| size_t derive_c_murmurhash | ( | const void * | key, |
| int | len, | ||
| uint32_t | seed ) |
Definition at line 346 of file murmurhash.h.
346 {
347#if SIZE_MAX == UINT64_MAX
348 // 64-bit platform: use the x64 128-bit variant, return lower 64 bits
349 uint64_t out128[2];
350 derive_c_MurmurHash3_x64_128(key, len, seed, out128);
351 return (size_t)out128[0];
352#elif SIZE_MAX == UINT32_MAX
353 // 32-bit platform: use the x86 32-bit variant
354 uint32_t out32;
355 MurmurHash3_x86_32(key, len, seed, &out32);
356 return (size_t)out32;
357#else
358#error "Unsupported size_t width"
359#endif
360}
void derive_c_MurmurHash3_x64_128(const void *key, const int len, const uint32_t seed, void *out)
Definition murmurhash.h:242
Here is the call graph for this function:
Here is the caller graph for this function:
◆ derive_c_MurmurHash3_x64_128()
| void derive_c_MurmurHash3_x64_128 | ( | const void * | key, |
| const int | len, | ||
| const uint32_t | seed, | ||
| void * | out ) |
Definition at line 242 of file murmurhash.h.
242 {
243 const uint8_t* data = (const uint8_t*)key;
244 const int nblocks = len / 16;
245
246 uint64_t h1 = seed;
247 uint64_t h2 = seed;
248
249 const uint64_t c1 = 0x87c37b91114253d5LLU;
250 const uint64_t c2 = 0x4cf5ad432745937fLLU;
251
252 // body
253
254 const uint64_t* blocks = (const uint64_t*)(data);
255
256 for (int i = 0; i < nblocks; i++) {
257 uint64_t k1 = derive_c_getblock64(blocks, i * 2 + 0);
258 uint64_t k2 = derive_c_getblock64(blocks, i * 2 + 1);
259
260 k1 *= c1;
261 k1 = derive_c_rotl64(k1, 31);
262 k1 *= c2;
263 h1 ^= k1;
264
265 h1 = derive_c_rotl64(h1, 27);
266 h1 += h2;
267 h1 = h1 * 5 + 0x52dce729;
268
269 k2 *= c2;
270 k2 = derive_c_rotl64(k2, 33);
271 k2 *= c1;
272 h2 ^= k2;
273
274 h2 = derive_c_rotl64(h2, 31);
275 h2 += h1;
276 h2 = h2 * 5 + 0x38495ab5;
277 }
278
279 // tail
280
281 const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
282
283 uint64_t k1 = 0;
284 uint64_t k2 = 0;
285
286 switch (len & 15) {
287 case 15:
288 k2 ^= ((uint64_t)tail[14]) << 48;
289 case 14:
290 k2 ^= ((uint64_t)tail[13]) << 40;
291 case 13:
292 k2 ^= ((uint64_t)tail[12]) << 32;
293 case 12:
294 k2 ^= ((uint64_t)tail[11]) << 24;
295 case 11:
296 k2 ^= ((uint64_t)tail[10]) << 16;
297 case 10:
298 k2 ^= ((uint64_t)tail[9]) << 8;
299 case 9:
300 k2 ^= ((uint64_t)tail[8]) << 0;
301 k2 *= c2;
302 k2 = derive_c_rotl64(k2, 33);
303 k2 *= c1;
304 h2 ^= k2;
305
306 case 8:
307 k1 ^= ((uint64_t)tail[7]) << 56;
308 case 7:
309 k1 ^= ((uint64_t)tail[6]) << 48;
310 case 6:
311 k1 ^= ((uint64_t)tail[5]) << 40;
312 case 5:
313 k1 ^= ((uint64_t)tail[4]) << 32;
314 case 4:
315 k1 ^= ((uint64_t)tail[3]) << 24;
316 case 3:
317 k1 ^= ((uint64_t)tail[2]) << 16;
318 case 2:
319 k1 ^= ((uint64_t)tail[1]) << 8;
320 case 1:
321 k1 ^= ((uint64_t)tail[0]) << 0;
322 k1 *= c1;
323 k1 = derive_c_rotl64(k1, 31);
324 k1 *= c2;
325 h1 ^= k1;
326 };
327
328 // finalization
329
330 h1 ^= len;
331 h2 ^= len;
332
333 h1 += h2;
334 h2 += h1;
335
336 h1 = derive_c_fmix64(h1);
337 h2 = derive_c_fmix64(h2);
338
339 h1 += h2;
340 h2 += h1;
341
342 ((uint64_t*)out)[0] = h1;
343 ((uint64_t*)out)[1] = h2;
344}
FORCE_INLINE uint64_t derive_c_getblock64(const uint64_t *p, int i)
Definition murmurhash.h:13
Here is the call graph for this function:
Here is the caller graph for this function:
◆ derive_c_MurmurHash3_x86_128()
| void derive_c_MurmurHash3_x86_128 | ( | const void * | key, |
| const int | len, | ||
| uint32_t | seed, | ||
| void * | out ) |
Definition at line 88 of file murmurhash.h.
88 {
89 const uint8_t* data = (const uint8_t*)key;
90 const int nblocks = len / 16;
91
92 uint32_t h1 = seed;
93 uint32_t h2 = seed;
94 uint32_t h3 = seed;
95 uint32_t h4 = seed;
96
97 const uint32_t c1 = 0x239b961b;
98 const uint32_t c2 = 0xab0e9789;
99 const uint32_t c3 = 0x38b34ae5;
100 const uint32_t c4 = 0xa1e38b93;
101
102 // body
103
104 const uint32_t* blocks = (const uint32_t*)(data + nblocks * 16);
105
106 for (int i = -nblocks; i; i++) {
107 uint32_t k1 = derive_c_getblock32(blocks, i * 4 + 0);
108 uint32_t k2 = derive_c_getblock32(blocks, i * 4 + 1);
109 uint32_t k3 = derive_c_getblock32(blocks, i * 4 + 2);
110 uint32_t k4 = derive_c_getblock32(blocks, i * 4 + 3);
111
112 k1 *= c1;
113 k1 = derive_c_rotl32(k1, 15);
114 k1 *= c2;
115 h1 ^= k1;
116
117 h1 = derive_c_rotl32(h1, 19);
118 h1 += h2;
119 h1 = h1 * 5 + 0x561ccd1b;
120
121 k2 *= c2;
122 k2 = derive_c_rotl32(k2, 16);
123 k2 *= c3;
124 h2 ^= k2;
125
126 h2 = derive_c_rotl32(h2, 17);
127 h2 += h3;
128 h2 = h2 * 5 + 0x0bcaa747;
129
130 k3 *= c3;
131 k3 = derive_c_rotl32(k3, 17);
132 k3 *= c4;
133 h3 ^= k3;
134
135 h3 = derive_c_rotl32(h3, 15);
136 h3 += h4;
137 h3 = h3 * 5 + 0x96cd1c35;
138
139 k4 *= c4;
140 k4 = derive_c_rotl32(k4, 18);
141 k4 *= c1;
142 h4 ^= k4;
143
144 h4 = derive_c_rotl32(h4, 13);
145 h4 += h1;
146 h4 = h4 * 5 + 0x32ac3b17;
147 }
148
149 // tail
150
151 const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
152
153 uint32_t k1 = 0;
154 uint32_t k2 = 0;
155 uint32_t k3 = 0;
156 uint32_t k4 = 0;
157
158 switch (len & 15) {
159 case 15:
160 k4 ^= tail[14] << 16;
161 case 14:
162 k4 ^= tail[13] << 8;
163 case 13:
164 k4 ^= tail[12] << 0;
165 k4 *= c4;
166 k4 = derive_c_rotl32(k4, 18);
167 k4 *= c1;
168 h4 ^= k4;
169
170 case 12:
171 k3 ^= tail[11] << 24;
172 case 11:
173 k3 ^= tail[10] << 16;
174 case 10:
175 k3 ^= tail[9] << 8;
176 case 9:
177 k3 ^= tail[8] << 0;
178 k3 *= c3;
179 k3 = derive_c_rotl32(k3, 17);
180 k3 *= c4;
181 h3 ^= k3;
182
183 case 8:
184 k2 ^= tail[7] << 24;
185 case 7:
186 k2 ^= tail[6] << 16;
187 case 6:
188 k2 ^= tail[5] << 8;
189 case 5:
190 k2 ^= tail[4] << 0;
191 k2 *= c2;
192 k2 = derive_c_rotl32(k2, 16);
193 k2 *= c3;
194 h2 ^= k2;
195
196 case 4:
197 k1 ^= tail[3] << 24;
198 case 3:
199 k1 ^= tail[2] << 16;
200 case 2:
201 k1 ^= tail[1] << 8;
202 case 1:
203 k1 ^= tail[0] << 0;
204 k1 *= c1;
205 k1 = derive_c_rotl32(k1, 15);
206 k1 *= c2;
207 h1 ^= k1;
208 };
209
210 // finalization
211
212 h1 ^= len;
213 h2 ^= len;
214 h3 ^= len;
215 h4 ^= len;
216
217 h1 += h2;
218 h1 += h3;
219 h1 += h4;
220 h2 += h1;
221 h3 += h1;
222 h4 += h1;
223
224 h1 = derive_c_fmix32(h1);
225 h2 = derive_c_fmix32(h2);
226 h3 = derive_c_fmix32(h3);
227 h4 = derive_c_fmix32(h4);
228
229 h1 += h2;
230 h1 += h3;
231 h1 += h4;
232 h2 += h1;
233 h3 += h1;
234 h4 += h1;
235
236 ((uint32_t*)out)[0] = h1;
237 ((uint32_t*)out)[1] = h2;
238 ((uint32_t*)out)[2] = h3;
239 ((uint32_t*)out)[3] = h4;
240}
FORCE_INLINE uint32_t derive_c_rotl32(uint32_t x, int8_t r)
MurmurHash3 implementation, copied (with love) from Austin Appleby's implementation
Definition murmurhash.h:7
FORCE_INLINE uint32_t derive_c_getblock32(const uint32_t *p, int i)
Definition murmurhash.h:11
Here is the call graph for this function:
◆ derive_c_MurmurHash3_x86_32()
| void derive_c_MurmurHash3_x86_32 | ( | const void * | key, |
| int | len, | ||
| uint32_t | seed, | ||
| void * | out ) |
Definition at line 35 of file murmurhash.h.
35 {
36 const uint8_t* data = (const uint8_t*)key;
37 const int nblocks = len / 4;
38
39 uint32_t h1 = seed;
40
41 const uint32_t c1 = 0xcc9e2d51;
42 const uint32_t c2 = 0x1b873593;
43
44 // body
45
46 const uint32_t* blocks = (const uint32_t*)(data + nblocks * 4);
47
48 for (int i = -nblocks; i; i++) {
49 uint32_t k1 = derive_c_getblock32(blocks, i);
50
51 k1 *= c1;
52 k1 = derive_c_rotl32(k1, 15);
53 k1 *= c2;
54
55 h1 ^= k1;
56 h1 = derive_c_rotl32(h1, 13);
57 h1 = h1 * 5 + 0xe6546b64;
58 }
59
60 // tail
61
62 const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
63
64 uint32_t k1 = 0;
65
66 switch (len & 3) {
67 case 3:
68 k1 ^= tail[2] << 16;
69 case 2:
70 k1 ^= tail[1] << 8;
71 case 1:
72 k1 ^= tail[0];
73 k1 *= c1;
74 k1 = derive_c_rotl32(k1, 15);
75 k1 *= c2;
76 h1 ^= k1;
77 };
78
79 // finalization
80
81 h1 ^= len;
82
83 h1 = derive_c_fmix32(h1);
84
85 *(uint32_t*)out = h1;
86}
Here is the call graph for this function:
◆ derive_c_rotl32()
| FORCE_INLINE uint32_t derive_c_rotl32 | ( | uint32_t | x, |
| int8_t | r ) |
MurmurHash3 implementation, copied (with love) from Austin Appleby's implementation
Definition at line 7 of file murmurhash.h.
7{ return (x << r) | (x >> (32 - r)); }
Here is the caller graph for this function:
◆ derive_c_rotl64()
| FORCE_INLINE uint64_t derive_c_rotl64 | ( | uint64_t | x, |
| int8_t | r ) |
Definition at line 9 of file murmurhash.h.
9{ return (x << r) | (x >> (64 - r)); }
Here is the caller graph for this function:
