OSSIA
Open Scenario System for Interactive Application
Loading...
Searching...
No Matches
murmur3.hpp
1
5#pragma once
6#include <cstdint>
7#pragma clang attribute push( \
8 __attribute__((no_sanitize("integer"))), apply_to = function)
9
10namespace ossia
11{
12namespace murmur
13{
14
15static constexpr inline uint32_t rotl32(uint32_t x, int8_t r) noexcept
16{
17 return (x << r) | (x >> (32 - r));
18}
19
20static constexpr inline uint64_t rotl64(uint64_t x, int8_t r) noexcept
21{
22 return (x << r) | (x >> (64 - r));
23}
24//-----------------------------------------------------------------------------
25// Finalization mix - force all bits of a hash block to avalanche
26
27static constexpr inline uint32_t fmix32(uint32_t h) noexcept
28{
29 h ^= h >> 16;
30 h *= 0x85ebca6b;
31 h ^= h >> 13;
32 h *= 0xc2b2ae35;
33 h ^= h >> 16;
34
35 return h;
36}
37
38//----------
39
40static constexpr inline uint64_t fmix64(uint64_t k) noexcept
41{
42 k ^= k >> 33;
43 k *= 0xff51afd7ed558ccdULL;
44 k ^= k >> 33;
45 k *= 0xc4ceb9fe1a85ec53ULL;
46 k ^= k >> 33;
47
48 return k;
49}
50
51//-----------------------------------------------------------------------------
52
53inline
54#if defined(__clang__)
55 __attribute__((no_sanitize("undefined")))
56#endif
57 void
58 murmur3_x86_32(const void* key, int len, uint32_t seed, uint32_t& out) noexcept
59{
60 const uint8_t* data = (const uint8_t*)key;
61 const int nblocks = len / 4;
62
63 uint32_t h1 = seed;
64
65 uint32_t c1 = 0xcc9e2d51;
66 uint32_t c2 = 0x1b873593;
67
68 //----------
69 // body
70
71 const uint32_t* blocks = (const uint32_t*)(data + nblocks * 4);
72
73 for(int i = -nblocks; i; i++)
74 {
75 uint32_t k1 = blocks[i];
76
77 k1 *= c1;
78 k1 = rotl32(k1, 15);
79 k1 *= c2;
80
81 h1 ^= k1;
82 h1 = rotl32(h1, 13);
83 h1 = h1 * 5 + 0xe6546b64;
84 }
85
86 //----------
87 // tail
88
89 const uint8_t* tail = (const uint8_t*)(data + nblocks * 4);
90
91 uint32_t k1 = 0;
92
93 switch(len & 3)
94 {
95 case 3:
96 k1 ^= tail[2] << 16;
97 [[fallthrough]];
98 case 2:
99 k1 ^= tail[1] << 8;
100 [[fallthrough]];
101 case 1:
102 k1 ^= tail[0];
103 k1 *= c1;
104 k1 = rotl32(k1, 15);
105 k1 *= c2;
106 h1 ^= k1;
107 };
108
109 //----------
110 // finalization
111
112 h1 ^= len;
113
114 h1 = fmix32(h1);
115
116 out = h1;
117}
118
119//-----------------------------------------------------------------------------
120
121constexpr void murmur3_x86_128(
122 const void* key, const int len, uint32_t seed, uint32_t (&out)[4]) noexcept
123{
124 const uint8_t* data = (const uint8_t*)key;
125 const int nblocks = len / 16;
126
127 uint32_t h1 = seed;
128 uint32_t h2 = seed;
129 uint32_t h3 = seed;
130 uint32_t h4 = seed;
131
132 uint32_t c1 = 0x239b961b;
133 uint32_t c2 = 0xab0e9789;
134 uint32_t c3 = 0x38b34ae5;
135 uint32_t c4 = 0xa1e38b93;
136
137 //----------
138 // body
139
140 const uint32_t* blocks = (const uint32_t*)(data + nblocks * 16);
141
142 for(int i = -nblocks; i; i++)
143 {
144 uint32_t k1 = blocks[i * 4 + 0];
145 uint32_t k2 = blocks[i * 4 + 1];
146 uint32_t k3 = blocks[i * 4 + 2];
147 uint32_t k4 = blocks[i * 4 + 3];
148
149 k1 *= c1;
150 k1 = rotl32(k1, 15);
151 k1 *= c2;
152 h1 ^= k1;
153
154 h1 = rotl32(h1, 19);
155 h1 += h2;
156 h1 = h1 * 5 + 0x561ccd1b;
157
158 k2 *= c2;
159 k2 = rotl32(k2, 16);
160 k2 *= c3;
161 h2 ^= k2;
162
163 h2 = rotl32(h2, 17);
164 h2 += h3;
165 h2 = h2 * 5 + 0x0bcaa747;
166
167 k3 *= c3;
168 k3 = rotl32(k3, 17);
169 k3 *= c4;
170 h3 ^= k3;
171
172 h3 = rotl32(h3, 15);
173 h3 += h4;
174 h3 = h3 * 5 + 0x96cd1c35;
175
176 k4 *= c4;
177 k4 = rotl32(k4, 18);
178 k4 *= c1;
179 h4 ^= k4;
180
181 h4 = rotl32(h4, 13);
182 h4 += h1;
183 h4 = h4 * 5 + 0x32ac3b17;
184 }
185
186 //----------
187 // tail
188
189 const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
190
191 uint32_t k1 = 0;
192 uint32_t k2 = 0;
193 uint32_t k3 = 0;
194 uint32_t k4 = 0;
195
196 switch(len & 15)
197 {
198 case 15:
199 k4 ^= tail[14] << 16;
200 case 14:
201 k4 ^= tail[13] << 8;
202 case 13:
203 k4 ^= tail[12] << 0;
204 k4 *= c4;
205 k4 = rotl32(k4, 18);
206 k4 *= c1;
207 h4 ^= k4;
208
209 case 12:
210 k3 ^= tail[11] << 24;
211 case 11:
212 k3 ^= tail[10] << 16;
213 case 10:
214 k3 ^= tail[9] << 8;
215 case 9:
216 k3 ^= tail[8] << 0;
217 k3 *= c3;
218 k3 = rotl32(k3, 17);
219 k3 *= c4;
220 h3 ^= k3;
221
222 case 8:
223 k2 ^= tail[7] << 24;
224 case 7:
225 k2 ^= tail[6] << 16;
226 case 6:
227 k2 ^= tail[5] << 8;
228 case 5:
229 k2 ^= tail[4] << 0;
230 k2 *= c2;
231 k2 = rotl32(k2, 16);
232 k2 *= c3;
233 h2 ^= k2;
234
235 case 4:
236 k1 ^= tail[3] << 24;
237 case 3:
238 k1 ^= tail[2] << 16;
239 case 2:
240 k1 ^= tail[1] << 8;
241 case 1:
242 k1 ^= tail[0] << 0;
243 k1 *= c1;
244 k1 = rotl32(k1, 15);
245 k1 *= c2;
246 h1 ^= k1;
247 };
248
249 //----------
250 // finalization
251
252 h1 ^= len;
253 h2 ^= len;
254 h3 ^= len;
255 h4 ^= len;
256
257 h1 += h2;
258 h1 += h3;
259 h1 += h4;
260 h2 += h1;
261 h3 += h1;
262 h4 += h1;
263
264 h1 = fmix32(h1);
265 h2 = fmix32(h2);
266 h3 = fmix32(h3);
267 h4 = fmix32(h4);
268
269 h1 += h2;
270 h1 += h3;
271 h1 += h4;
272 h2 += h1;
273 h3 += h1;
274 h4 += h1;
275
276 out[0] = h1;
277 out[1] = h2;
278 out[2] = h3;
279 out[3] = h4;
280}
281
282//-----------------------------------------------------------------------------
283
284constexpr void murmur3_x64_128(
285 const void* key, const int len, const uint32_t seed, uint64_t (&out)[2]) noexcept
286{
287 const uint8_t* data = (const uint8_t*)key;
288 const int nblocks = len / 16;
289
290 uint64_t h1 = seed;
291 uint64_t h2 = seed;
292
293 uint64_t c1 = 0x87c37b91114253d5ULL;
294 uint64_t c2 = 0x4cf5ad432745937fULL;
295
296 //----------
297 // body
298
299 const uint64_t* blocks = (const uint64_t*)(data);
300
301 for(int i = 0; i < nblocks; i++)
302 {
303 uint64_t k1 = blocks[i * 2 + 0];
304 uint64_t k2 = blocks[i * 2 + 1];
305
306 k1 *= c1;
307 k1 = rotl64(k1, 31);
308 k1 *= c2;
309 h1 ^= k1;
310
311 h1 = rotl64(h1, 27);
312 h1 += h2;
313 h1 = h1 * 5 + 0x52dce729;
314
315 k2 *= c2;
316 k2 = rotl64(k2, 33);
317 k2 *= c1;
318 h2 ^= k2;
319
320 h2 = rotl64(h2, 31);
321 h2 += h1;
322 h2 = h2 * 5 + 0x38495ab5;
323 }
324
325 //----------
326 // tail
327
328 const uint8_t* tail = (const uint8_t*)(data + nblocks * 16);
329
330 uint64_t k1 = 0;
331 uint64_t k2 = 0;
332
333 switch(len & 15)
334 {
335 case 15:
336 k2 ^= (uint64_t)(tail[14]) << 48;
337 case 14:
338 k2 ^= (uint64_t)(tail[13]) << 40;
339 case 13:
340 k2 ^= (uint64_t)(tail[12]) << 32;
341 case 12:
342 k2 ^= (uint64_t)(tail[11]) << 24;
343 case 11:
344 k2 ^= (uint64_t)(tail[10]) << 16;
345 case 10:
346 k2 ^= (uint64_t)(tail[9]) << 8;
347 case 9:
348 k2 ^= (uint64_t)(tail[8]) << 0;
349 k2 *= c2;
350 k2 = rotl64(k2, 33);
351 k2 *= c1;
352 h2 ^= k2;
353
354 case 8:
355 k1 ^= (uint64_t)(tail[7]) << 56;
356 case 7:
357 k1 ^= (uint64_t)(tail[6]) << 48;
358 case 6:
359 k1 ^= (uint64_t)(tail[5]) << 40;
360 case 5:
361 k1 ^= (uint64_t)(tail[4]) << 32;
362 case 4:
363 k1 ^= (uint64_t)(tail[3]) << 24;
364 case 3:
365 k1 ^= (uint64_t)(tail[2]) << 16;
366 case 2:
367 k1 ^= (uint64_t)(tail[1]) << 8;
368 case 1:
369 k1 ^= (uint64_t)(tail[0]) << 0;
370 k1 *= c1;
371 k1 = rotl64(k1, 31);
372 k1 *= c2;
373 h1 ^= k1;
374 };
375
376 //----------
377 // finalization
378
379 h1 ^= len;
380 h2 ^= len;
381
382 h1 += h2;
383 h2 += h1;
384
385 h1 = fmix64(h1);
386 h2 = fmix64(h2);
387
388 h1 += h2;
389 h2 += h1;
390
391 out[0] = h1;
392 out[1] = h2;
393}
394}
395}
396
397#pragma clang attribute pop
ossia
Definition git_info.h:7