OSSIA
Open Scenario System for Interactive Application
murmur3.hpp
1 
5 #pragma once
6 #include <cstdint>
7 #pragma clang attribute push( \
8  __attribute__((no_sanitize("integer"))), apply_to = function)
9 
10 namespace ossia
11 {
12 namespace murmur
13 {
14 
15 static constexpr inline uint32_t rotl32(uint32_t x, int8_t r) noexcept
16 {
17  return (x << r) | (x >> (32 - r));
18 }
19 
20 static 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 
27 static 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 
40 static 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 
53 inline
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 
121 constexpr 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 
284 constexpr 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