Derive-C
Loading...
Searching...
No Matches
murmur.h
Go to the documentation of this file.
1
3#pragma once
4
5#include <stddef.h>
6#include <stdint.h>
7#include <string.h>
8
9#include <derive-c/core/prelude.h>
10#include <derive-c/core/std/reflect.h>
11
12DC_INLINE uint32_t PRIV(murmur_rotl32)(uint32_t x, int8_t r) { return (x << r) | (x >> (32 - r)); }
13
14DC_INLINE uint64_t PRIV(murmur_rotl64)(uint64_t x, int8_t r) { return (x << r) | (x >> (64 - r)); }
15
16DC_INLINE uint32_t PRIV(murmur_getblock32)(const uint8_t* p, int32_t i) {
17 uint32_t out;
18 memcpy(&out, p + ((ptrdiff_t)i * 4), sizeof(out));
19 return out;
20}
21
22DC_INLINE uint64_t PRIV(murmur_getblock64)(const uint8_t* p, int32_t i) {
23 uint64_t out;
24 memcpy(&out, p + ((ptrdiff_t)i * 8), sizeof(out));
25 return out;
26}
27
28DC_INLINE uint32_t PRIV(murmur_fmix32)(uint32_t h) {
29 h ^= h >> 16;
30 h *= 0x85ebca6b;
31 h ^= h >> 13;
32 h *= 0xc2b2ae35;
33 h ^= h >> 16;
34
35 return h;
36}
37
38DC_INLINE uint64_t PRIV(murmur_fmix64)(uint64_t k) {
39 k ^= k >> 33;
40 k *= 0xff51afd7ed558ccdLLU;
41 k ^= k >> 33;
42 k *= 0xc4ceb9fe1a85ec53LLU;
43 k ^= k >> 33;
44
45 return k;
46}
47
48DC_PUBLIC static inline void dc_MurmurHash3_x86_32(const void* key, int32_t len, uint32_t seed,
49 void* out) {
50 const uint8_t* data = (const uint8_t*)key;
51 const int32_t nblocks = len / 4;
52
53 uint32_t h1 = seed;
54
55 const uint32_t c1 = 0xcc9e2d51;
56 const uint32_t c2 = 0x1b873593;
57
58 // body
59
60 const uint8_t* blocks = data + (ptrdiff_t)(nblocks * 4);
61
62 for (int i = -nblocks; i; i++) {
63 uint32_t k1 = PRIV(murmur_getblock32)(blocks, i);
64
65 k1 *= c1;
66 k1 = PRIV(murmur_rotl32)(k1, 15);
67 k1 *= c2;
68
69 h1 ^= k1;
70 h1 = PRIV(murmur_rotl32)(h1, 13);
71 h1 = h1 * 5 + 0xe6546b64;
72 }
73
74 // tail
75
76 const uint8_t* tail = (const uint8_t*)(data + (ptrdiff_t)(nblocks * 4));
77
78 uint32_t k1 = 0;
79
80 switch (len & 3) {
81 case 3:
82 k1 ^= ((uint32_t)tail[2]) << 16;
83 [[fallthrough]];
84 case 2:
85 k1 ^= ((uint32_t)tail[1]) << 8;
86 [[fallthrough]];
87 case 1:
88 k1 ^= ((uint32_t)tail[0]);
89 k1 *= c1;
90 k1 = PRIV(murmur_rotl32)(k1, 15);
91 k1 *= c2;
92 h1 ^= k1;
93 [[fallthrough]];
94 default:
95 };
96
97 // finalization
98
99 h1 ^= (uint32_t)len;
100
101 h1 = PRIV(murmur_fmix32)(h1);
102
103 *(uint32_t*)out = h1;
104}
105
106DC_PUBLIC static inline void dc_MurmurHash3_x86_128(const void* key, const int32_t len,
107 uint32_t seed, void* out) {
108 const uint8_t* data = (const uint8_t*)key;
109 const int32_t nblocks = len / 16;
110
111 uint32_t h1 = seed;
112 uint32_t h2 = seed;
113 uint32_t h3 = seed;
114 uint32_t h4 = seed;
115
116 const uint32_t c1 = 0x239b961b;
117 const uint32_t c2 = 0xab0e9789;
118 const uint32_t c3 = 0x38b34ae5;
119 const uint32_t c4 = 0xa1e38b93;
120
121 // body
122
123 const uint8_t* blocks = data + (ptrdiff_t)(nblocks * 16);
124
125 for (int i = -nblocks; i; i++) {
126 uint32_t k1 = PRIV(murmur_getblock32)(blocks, (i * 4) + 0);
127 uint32_t k2 = PRIV(murmur_getblock32)(blocks, (i * 4) + 1);
128 uint32_t k3 = PRIV(murmur_getblock32)(blocks, (i * 4) + 2);
129 uint32_t k4 = PRIV(murmur_getblock32)(blocks, (i * 4) + 3);
130
131 k1 *= c1;
132 k1 = PRIV(murmur_rotl32)(k1, 15);
133 k1 *= c2;
134 h1 ^= k1;
135
136 h1 = PRIV(murmur_rotl32)(h1, 19);
137 h1 += h2;
138 h1 = h1 * 5 + 0x561ccd1b;
139
140 k2 *= c2;
141 k2 = PRIV(murmur_rotl32)(k2, 16);
142 k2 *= c3;
143 h2 ^= k2;
144
145 h2 = PRIV(murmur_rotl32)(h2, 17);
146 h2 += h3;
147 h2 = h2 * 5 + 0x0bcaa747;
148
149 k3 *= c3;
150 k3 = PRIV(murmur_rotl32)(k3, 17);
151 k3 *= c4;
152 h3 ^= k3;
153
154 h3 = PRIV(murmur_rotl32)(h3, 15);
155 h3 += h4;
156 h3 = h3 * 5 + 0x96cd1c35;
157
158 k4 *= c4;
159 k4 = PRIV(murmur_rotl32)(k4, 18);
160 k4 *= c1;
161 h4 ^= k4;
162
163 h4 = PRIV(murmur_rotl32)(h4, 13);
164 h4 += h1;
165 h4 = h4 * 5 + 0x32ac3b17;
166 }
167
168 // tail
169
170 const uint8_t* tail = (const uint8_t*)(data + (ptrdiff_t)(nblocks * 16));
171
172 uint32_t k1 = 0;
173 uint32_t k2 = 0;
174 uint32_t k3 = 0;
175 uint32_t k4 = 0;
176
177 switch (len & 15) {
178 case 15:
179 k4 ^= ((uint32_t)tail[14]) << 16;
180 [[fallthrough]];
181 case 14:
182 k4 ^= ((uint32_t)tail[13]) << 8;
183 [[fallthrough]];
184 case 13:
185 k4 ^= ((uint32_t)tail[12]) << 0;
186 k4 *= c4;
187 k4 = PRIV(murmur_rotl32)(k4, 18);
188 k4 *= c1;
189 h4 ^= k4;
190
191 [[fallthrough]];
192 case 12:
193 k3 ^= ((uint32_t)tail[11]) << 24;
194 [[fallthrough]];
195 case 11:
196 k3 ^= ((uint32_t)tail[10]) << 16;
197 [[fallthrough]];
198 case 10:
199 k3 ^= ((uint32_t)tail[9]) << 8;
200 [[fallthrough]];
201 case 9:
202 k3 ^= ((uint32_t)tail[8]) << 0;
203 k3 *= c3;
204 k3 = PRIV(murmur_rotl32)(k3, 17);
205 k3 *= c4;
206 h3 ^= k3;
207
208 [[fallthrough]];
209 case 8:
210 k2 ^= ((uint32_t)tail[7]) << 24;
211 [[fallthrough]];
212 case 7:
213 k2 ^= ((uint32_t)tail[6]) << 16;
214 [[fallthrough]];
215 case 6:
216 k2 ^= ((uint32_t)tail[5]) << 8;
217 [[fallthrough]];
218 case 5:
219 k2 ^= ((uint32_t)tail[4]) << 0;
220 k2 *= c2;
221 k2 = PRIV(murmur_rotl32)(k2, 16);
222 k2 *= c3;
223 h2 ^= k2;
224
225 [[fallthrough]];
226 case 4:
227 k1 ^= ((uint32_t)tail[3]) << 24;
228 [[fallthrough]];
229 case 3:
230 k1 ^= ((uint32_t)tail[2]) << 16;
231 [[fallthrough]];
232 case 2:
233 k1 ^= ((uint32_t)tail[1]) << 8;
234 [[fallthrough]];
235 case 1:
236 k1 ^= ((uint32_t)tail[0]) << 0;
237 k1 *= c1;
238 k1 = PRIV(murmur_rotl32)(k1, 15);
239 k1 *= c2;
240 h1 ^= k1;
241 [[fallthrough]];
242 default:
243 };
244
245 // finalization
246
247 h1 ^= (uint32_t)len;
248 h2 ^= (uint32_t)len;
249 h3 ^= (uint32_t)len;
250 h4 ^= (uint32_t)len;
251
252 h1 += h2;
253 h1 += h3;
254 h1 += h4;
255 h2 += h1;
256 h3 += h1;
257 h4 += h1;
258
259 h1 = PRIV(murmur_fmix32)(h1);
260 h2 = PRIV(murmur_fmix32)(h2);
261 h3 = PRIV(murmur_fmix32)(h3);
262 h4 = PRIV(murmur_fmix32)(h4);
263
264 h1 += h2;
265 h1 += h3;
266 h1 += h4;
267 h2 += h1;
268 h3 += h1;
269 h4 += h1;
270
271 ((uint32_t*)out)[0] = h1;
272 ((uint32_t*)out)[1] = h2;
273 ((uint32_t*)out)[2] = h3;
274 ((uint32_t*)out)[3] = h4;
275}
276
277DC_PUBLIC static inline void dc_MurmurHash3_x64_128(const void* key, const int32_t len,
278 const uint32_t seed, void* out) {
279 const uint8_t* data = (const uint8_t*)key;
280 const int32_t nblocks = len / 16;
281
282 uint64_t h1 = seed;
283 uint64_t h2 = seed;
284
285 const uint64_t c1 = 0x87c37b91114253d5LLU;
286 const uint64_t c2 = 0x4cf5ad432745937fLLU;
287
288 // body
289
290 const uint8_t* blocks = data;
291
292 for (int32_t i = 0; i < nblocks; i++) {
293 uint64_t k1 = PRIV(murmur_getblock64)(blocks, (i * 2) + 0);
294 uint64_t k2 = PRIV(murmur_getblock64)(blocks, (i * 2) + 1);
295
296 k1 *= c1;
297 k1 = PRIV(murmur_rotl64)(k1, 31);
298 k1 *= c2;
299 h1 ^= k1;
300
301 h1 = PRIV(murmur_rotl64)(h1, 27);
302 h1 += h2;
303 h1 = h1 * 5 + 0x52dce729;
304
305 k2 *= c2;
306 k2 = PRIV(murmur_rotl64)(k2, 33);
307 k2 *= c1;
308 h2 ^= k2;
309
310 h2 = PRIV(murmur_rotl64)(h2, 31);
311 h2 += h1;
312 h2 = h2 * 5 + 0x38495ab5;
313 }
314
315 // tail
316
317 const uint8_t* tail = (const uint8_t*)(data + (ptrdiff_t)(nblocks * 16));
318
319 uint64_t k1 = 0;
320 uint64_t k2 = 0;
321
322 switch (len & 15) {
323 case 15:
324 k2 ^= ((uint64_t)tail[14]) << 48;
325 [[fallthrough]];
326 case 14:
327 k2 ^= ((uint64_t)tail[13]) << 40;
328 [[fallthrough]];
329 case 13:
330 k2 ^= ((uint64_t)tail[12]) << 32;
331 [[fallthrough]];
332 case 12:
333 k2 ^= ((uint64_t)tail[11]) << 24;
334 [[fallthrough]];
335 case 11:
336 k2 ^= ((uint64_t)tail[10]) << 16;
337 [[fallthrough]];
338 case 10:
339 k2 ^= ((uint64_t)tail[9]) << 8;
340 [[fallthrough]];
341 case 9:
342 k2 ^= ((uint64_t)tail[8]) << 0;
343 k2 *= c2;
344 k2 = PRIV(murmur_rotl64)(k2, 33);
345 k2 *= c1;
346 h2 ^= k2;
347
348 [[fallthrough]];
349 case 8:
350 k1 ^= ((uint64_t)tail[7]) << 56;
351 [[fallthrough]];
352 case 7:
353 k1 ^= ((uint64_t)tail[6]) << 48;
354 [[fallthrough]];
355 case 6:
356 k1 ^= ((uint64_t)tail[5]) << 40;
357 [[fallthrough]];
358 case 5:
359 k1 ^= ((uint64_t)tail[4]) << 32;
360 [[fallthrough]];
361 case 4:
362 k1 ^= ((uint64_t)tail[3]) << 24;
363 [[fallthrough]];
364 case 3:
365 k1 ^= ((uint64_t)tail[2]) << 16;
366 [[fallthrough]];
367 case 2:
368 k1 ^= ((uint64_t)tail[1]) << 8;
369 [[fallthrough]];
370 case 1:
371 k1 ^= ((uint64_t)tail[0]) << 0;
372 k1 *= c1;
373 k1 = PRIV(murmur_rotl64)(k1, 31);
374 k1 *= c2;
375 h1 ^= k1;
376 [[fallthrough]];
377 default:
378 };
379
380 // finalization
381
382 h1 ^= (uint64_t)len;
383 h2 ^= (uint64_t)len;
384
385 h1 += h2;
386 h2 += h1;
387
388 h1 = PRIV(murmur_fmix64)(h1);
389 h2 = PRIV(murmur_fmix64)(h2);
390
391 h1 += h2;
392 h2 += h1;
393
394 ((uint64_t*)out)[0] = h1;
395 ((uint64_t*)out)[1] = h2;
396}
397
398DC_PUBLIC static inline size_t dc_murmurhash(const void* key, int32_t len, uint32_t seed) {
399#if SIZE_MAX == UINT64_MAX
400 // 64-bit platform: use the x64 128-bit variant, return lower 64 bits
401 uint64_t out128[2];
402 dc_MurmurHash3_x64_128(key, len, seed, out128);
403 return (size_t)out128[0];
404#elif SIZE_MAX == UINT32_MAX
405 // 32-bit platform: use the x86 32-bit variant
406 uint32_t out32;
407 dc_MurmurHash3_x86_32(key, len, seed, &out32);
408 return (size_t)out32;
409#else
410 #error "Unsupported size_t width"
411#endif
412}
413
417// JUSTIFY: Casting signed to unsigned. This is just a hash, and signed->unsigned is not UB.
418#define MURMURHASH_3_FMIx64(type, ...) \
419 DC_PUBLIC static size_t type##_hash_murmurhash3(type const* key) { \
420 DC_STATIC_ASSERT(sizeof(type) <= sizeof(uint64_t), \
421 "MurmurHash3 only supports up to 64-bit integers"); \
422 return (size_t)PRIV(murmur_fmix64)((uint64_t)(*key)); \
423 }
424
425DC_INT_REFLECT(MURMURHASH_3_FMIx64)
426
427#undef MURMURHASH_3_FMIx64
428
429// clang-format off
430#define STRING_SIZES(_apply) \
431 _apply(1) \
432 _apply(2) \
433 _apply(3) \
434 _apply(4) \
435 _apply(5) \
436 _apply(6) \
437 _apply(7) \
438 _apply(8)
439// clang-format on
440
441#define MURMURHASH_DEFAULT_SEED 0x9747b28c
442
443#define MURMURHASH_STRING_FIXED_SIZE(size) \
444 DC_PUBLIC static size_t dc_murmur_hash_string_##size(const char str[size]) { \
445 return dc_murmurhash(str, size, MURMURHASH_DEFAULT_SEED); \
446 }
447
448STRING_SIZES(MURMURHASH_STRING_FIXED_SIZE)
449
450DC_PUBLIC static inline size_t dc_murmur_hash_string(const char* str) {
451 return dc_murmurhash(str, (int)strlen(str), MURMURHASH_DEFAULT_SEED);
452}
453
454#undef MURMURHASH_STRING_FIXED_SIZE
455#undef MURMURHASH_DEFAULT_SEED
456#undef STRING_SIZES
DC_INLINE
#define DC_INLINE
Definition attributes.h:3
data
static DC_PUBLIC ITEM * data(SELF *self)
Definition template.h:284
murmur_getblock32
DC_INLINE uint32_t PRIV murmur_getblock32(const uint8_t *p, int32_t i)
Definition murmur.h:16
dc_MurmurHash3_x86_128
static DC_PUBLIC void dc_MurmurHash3_x86_128(const void *key, const int32_t len, uint32_t seed, void *out)
Definition murmur.h:106
murmur_fmix32
DC_INLINE uint32_t PRIV murmur_fmix32(uint32_t h)
Definition murmur.h:28
dc_murmur_hash_string
static DC_PUBLIC size_t dc_murmur_hash_string(const char *str)
Definition murmur.h:450
dc_MurmurHash3_x86_32
static DC_PUBLIC void dc_MurmurHash3_x86_32(const void *key, int32_t len, uint32_t seed, void *out)
Definition murmur.h:48
MURMURHASH_STRING_FIXED_SIZE
#define MURMURHASH_STRING_FIXED_SIZE(size)
Definition murmur.h:443
MURMURHASH_DEFAULT_SEED
#define MURMURHASH_DEFAULT_SEED
Definition murmur.h:441
STRING_SIZES
#define STRING_SIZES(_apply)
Definition murmur.h:430
dc_murmurhash
static DC_PUBLIC size_t dc_murmurhash(const void *key, int32_t len, uint32_t seed)
Definition murmur.h:398
MURMURHASH_3_FMIx64
#define MURMURHASH_3_FMIx64(type,...)
Definition murmur.h:418
murmur_getblock64
DC_INLINE uint64_t PRIV murmur_getblock64(const uint8_t *p, int32_t i)
Definition murmur.h:22
dc_MurmurHash3_x64_128
static DC_PUBLIC void dc_MurmurHash3_x64_128(const void *key, const int32_t len, const uint32_t seed, void *out)
Definition murmur.h:277
murmur_rotl32
DC_INLINE uint32_t PRIV murmur_rotl32(uint32_t x, int8_t r)
MurmurHash3 implementation, copied (with love) from Austin Appleby's implementation.
Definition murmur.h:12
murmur_rotl64
DC_INLINE uint64_t PRIV murmur_rotl64(uint64_t x, int8_t r)
Definition murmur.h:14
murmur_fmix64
DC_INLINE uint64_t PRIV murmur_fmix64(uint64_t k)
Definition murmur.h:38
DC_PUBLIC
#define DC_PUBLIC
Definition namespace.h:25
PRIV
#define PRIV(name)
Definition namespace.h:20
DC_INT_REFLECT
#define DC_INT_REFLECT(F,...)
Definition reflect.h:11