Derive-C
Loading...
Searching...
No Matches
murmur.h File Reference
#include <stddef.h>
#include <stdint.h>
#include <string.h>
#include <derive-c/core/prelude.h>
#include <derive-c/core/std/reflect.h>

Go to the source code of this file.

Macros

#define MURMURHASH_3_FMIx64(type, ...)
#define STRING_SIZES(_apply)
#define MURMURHASH_DEFAULT_SEED   0x9747b28c
#define MURMURHASH_STRING_FIXED_SIZE(size)

Functions

DC_INLINE uint32_t PRIV murmur_rotl32 (uint32_t x, int8_t r)
 MurmurHash3 implementation, copied (with love) from Austin Appleby's implementation.
DC_INLINE uint64_t PRIV murmur_rotl64 (uint64_t x, int8_t r)
DC_INLINE uint32_t PRIV murmur_getblock32 (const uint8_t *p, int32_t i)
DC_INLINE uint64_t PRIV murmur_getblock64 (const uint8_t *p, int32_t i)
DC_INLINE uint32_t PRIV murmur_fmix32 (uint32_t h)
DC_INLINE uint64_t PRIV murmur_fmix64 (uint64_t k)
static DC_PUBLIC void dc_MurmurHash3_x86_32 (const void *key, int32_t len, uint32_t seed, void *out)
static DC_PUBLIC void dc_MurmurHash3_x86_128 (const void *key, const int32_t len, uint32_t seed, void *out)
static DC_PUBLIC void dc_MurmurHash3_x64_128 (const void *key, const int32_t len, const uint32_t seed, void *out)
static DC_PUBLIC size_t dc_murmurhash (const void *key, int32_t len, uint32_t seed)
static DC_PUBLIC size_t dc_murmur_hash_string (const char *str)

Macro Definition Documentation

◆ MURMURHASH_3_FMIx64

#define MURMURHASH_3_FMIx64 ( type,
... )
Value:
DC_PUBLIC static size_t type##_hash_murmurhash3(type const* key) { \
DC_STATIC_ASSERT(sizeof(type) <= sizeof(uint64_t), \
"MurmurHash3 only supports up to 64-bit integers"); \
return (size_t)PRIV(murmur_fmix64)((uint64_t)(*key)); \
}
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

Using MurmurHash3's finalizer for integer hashing.

Definition at line 418 of file murmur.h.

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 }

◆ MURMURHASH_DEFAULT_SEED

#define MURMURHASH_DEFAULT_SEED   0x9747b28c

Definition at line 441 of file murmur.h.

◆ MURMURHASH_STRING_FIXED_SIZE

#define MURMURHASH_STRING_FIXED_SIZE ( size)
Value:
DC_PUBLIC static size_t dc_murmur_hash_string_##size(const char str[size]) { \
return dc_murmurhash(str, size, MURMURHASH_DEFAULT_SEED); \
}
size
static DC_PUBLIC size_t size(SELF const *self)
Definition template.h:252
MURMURHASH_DEFAULT_SEED
#define MURMURHASH_DEFAULT_SEED
Definition murmur.h:441
dc_murmurhash
static DC_PUBLIC size_t dc_murmurhash(const void *key, int32_t len, uint32_t seed)
Definition murmur.h:398

Definition at line 443 of file murmur.h.

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 }

◆ STRING_SIZES

#define STRING_SIZES ( _apply)
Value:
_apply(1) \
_apply(2) \
_apply(3) \
_apply(4) \
_apply(5) \
_apply(6) \
_apply(7) \
_apply(8)

Definition at line 430 of file murmur.h.

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)

Function Documentation

◆ dc_murmur_hash_string()

DC_PUBLIC size_t dc_murmur_hash_string ( const char * str)
inlinestatic

Definition at line 450 of file murmur.h.

450 {
451 return dc_murmurhash(str, (int)strlen(str), MURMURHASH_DEFAULT_SEED);
452}

◆ dc_murmurhash()

DC_PUBLIC size_t dc_murmurhash ( const void * key,
int32_t len,
uint32_t seed )
inlinestatic

Definition at line 398 of file murmur.h.

398 {
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}
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
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

◆ dc_MurmurHash3_x64_128()

DC_PUBLIC void dc_MurmurHash3_x64_128 ( const void * key,
const int32_t len,
const uint32_t seed,
void * out )
inlinestatic

Definition at line 277 of file murmur.h.

278 {
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}
data
static DC_PUBLIC ITEM * data(SELF *self)
Definition template.h:284
murmur_getblock64
DC_INLINE uint64_t PRIV murmur_getblock64(const uint8_t *p, int32_t i)
Definition murmur.h:22
murmur_rotl64
DC_INLINE uint64_t PRIV murmur_rotl64(uint64_t x, int8_t r)
Definition murmur.h:14

◆ dc_MurmurHash3_x86_128()

DC_PUBLIC void dc_MurmurHash3_x86_128 ( const void * key,
const int32_t len,
uint32_t seed,
void * out )
inlinestatic

Definition at line 106 of file murmur.h.

107 {
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}
murmur_getblock32
DC_INLINE uint32_t PRIV murmur_getblock32(const uint8_t *p, int32_t i)
Definition murmur.h:16
murmur_fmix32
DC_INLINE uint32_t PRIV murmur_fmix32(uint32_t h)
Definition murmur.h:28
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

◆ dc_MurmurHash3_x86_32()

DC_PUBLIC void dc_MurmurHash3_x86_32 ( const void * key,
int32_t len,
uint32_t seed,
void * out )
inlinestatic

Definition at line 48 of file murmur.h.

49 {
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}

◆ murmur_fmix32()

DC_INLINE uint32_t PRIV murmur_fmix32 ( uint32_t h)

Definition at line 28 of file murmur.h.

28 {
29 h ^= h >> 16;
30 h *= 0x85ebca6b;
31 h ^= h >> 13;
32 h *= 0xc2b2ae35;
33 h ^= h >> 16;
34
35 return h;
36}

◆ murmur_fmix64()

DC_INLINE uint64_t PRIV murmur_fmix64 ( uint64_t k)

Definition at line 38 of file murmur.h.

38 {
39 k ^= k >> 33;
40 k *= 0xff51afd7ed558ccdLLU;
41 k ^= k >> 33;
42 k *= 0xc4ceb9fe1a85ec53LLU;
43 k ^= k >> 33;
44
45 return k;
46}

◆ murmur_getblock32()

DC_INLINE uint32_t PRIV murmur_getblock32 ( const uint8_t * p,
int32_t i )

Definition at line 16 of file murmur.h.

16 {
17 uint32_t out;
18 memcpy(&out, p + ((ptrdiff_t)i * 4), sizeof(out));
19 return out;
20}

◆ murmur_getblock64()

DC_INLINE uint64_t PRIV murmur_getblock64 ( const uint8_t * p,
int32_t i )

Definition at line 22 of file murmur.h.

22 {
23 uint64_t out;
24 memcpy(&out, p + ((ptrdiff_t)i * 8), sizeof(out));
25 return out;
26}

◆ 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 at line 12 of file murmur.h.

12{ return (x << r) | (x >> (32 - r)); }

◆ murmur_rotl64()

DC_INLINE uint64_t PRIV murmur_rotl64 ( uint64_t x,
int8_t r )

Definition at line 14 of file murmur.h.

14{ return (x << r) | (x >> (64 - r)); }