IceShard 1
A personal game engine project, with development focused on 2D/2.5D games.
Loading...
Searching...
No Matches
murmur3.hxx
Go to the documentation of this file.
1
3
4//-----------------------------------------------------------------------------
5// MurmurHash3 was written by Austin Appleby, and is placed in the public
6// domain. The author hereby disclaims copyright to this source code.
7
8// Note - The x86 and x64 versions do _not_ produce the same results, as the
9// algorithms are optimized for their respective platforms. You can still
10// compile and run any of them on any platform, but your performance with the
11// non-native version will be less than optimal.
12
13#pragma once
14#include <ice/types.hxx>
15#include <string_view>
16
17namespace ice::detail::murmur3_hash
18{
19
20 struct mm3_x86_h32
21 {
22 ice::u32 h[1];
23 };
24
25 struct mm3_x86_h128
26 {
27 ice::u32 h[4];
28 };
29
30 struct mm3_x64_h128
31 {
32 ice::u64 h[2];
33 };
34
35 constexpr auto cexpr_murmur3_x86_32(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h32;
36 constexpr auto cexpr_murmur3_x86_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h128;
37 constexpr auto cexpr_murmur3_x64_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x64_h128;
38
39 constexpr auto cexpr_murmur3_x86_32(std::string_view key, ice::u32 seed) noexcept -> mm3_x86_h32;
40 constexpr auto cexpr_murmur3_x86_128(std::string_view key, ice::u32 seed) noexcept -> mm3_x86_h128;
41 constexpr auto cexpr_murmur3_x64_128(std::string_view key, ice::u32 seed) noexcept -> mm3_x64_h128;
42
43 namespace detail
44 {
45
46 constexpr auto cexpr_rotl32(ice::u32 x, ice::i8 r) noexcept -> ice::u32
47 {
48 return (x << r) | (x >> (32 - r));
49 }
50
51 constexpr auto cexpr_rotl64(ice::u64 x, ice::i8 r) noexcept -> ice::u64
52 {
53 return (x << r) | (x >> (64 - r));
54 }
55
56 template<typename Char>
57 constexpr auto cexpr_block_x32(Char const* data) noexcept -> ice::u32
58 {
59 ice::u32 result = 0;
60 result |= static_cast<ice::u8 const>(data[3]);
61 result <<= 8;
62 result |= static_cast<ice::u8 const>(data[2]);
63 result <<= 8;
64 result |= static_cast<ice::u8 const>(data[1]);
65 result <<= 8;
66 result |= static_cast<ice::u8 const>(data[0]);
67 return result;
68 }
69
70 template<typename Char>
71 constexpr auto cexpr_block_x64(Char const* data) noexcept -> ice::u64
72 {
73 ice::u64 result = 0;
74 result |= static_cast<ice::u8 const>(data[7]);
75 result <<= 8;
76 result |= static_cast<ice::u8 const>(data[6]);
77 result <<= 8;
78 result |= static_cast<ice::u8 const>(data[5]);
79 result <<= 8;
80 result |= static_cast<ice::u8 const>(data[4]);
81 result <<= 8;
82 result |= static_cast<ice::u8 const>(data[3]);
83 result <<= 8;
84 result |= static_cast<ice::u8 const>(data[2]);
85 result <<= 8;
86 result |= static_cast<ice::u8 const>(data[1]);
87 result <<= 8;
88 result |= static_cast<ice::u8 const>(data[0]);
89 return result;
90 }
91
92 //-----------------------------------------------------------------------------
93 // Finalization mix - force all bits of a hash block to avalanche
94
95 constexpr auto cexpr_fmix32(ice::u32 h) noexcept -> ice::u32
96 {
97 h ^= h >> 16;
98 h *= 0x85ebca6b;
99 h ^= h >> 13;
100 h *= 0xc2b2ae35;
101 h ^= h >> 16;
102 return h;
103 }
104
105 //----------
106
107 constexpr ice::u64 cexpr_fmix64(ice::u64 k) noexcept
108 {
109 k ^= k >> 33;
110 k *= 0xFF51AFD7ED558CCDllu;
111 k ^= k >> 33;
112 k *= 0xC4CEB9FE1A85EC53llu;
113 k ^= k >> 33;
114 return k;
115 }
116
117 //-----------------------------------------------------------------------------
118
119 template<typename Char>
120 constexpr auto cexpr_murmur3_x86_32(std::basic_string_view<Char> key, ice::u32 seed) noexcept -> mm3_x86_h32
121 {
122 Char const* string_data = key.data();
123 ice::u32 const string_length = static_cast<ice::u32>(key.length());
124
125 ice::u32 const block_byte_size = 4u;
126 ice::u32 const block_num = string_length / block_byte_size;
127
128 //----------
129 // body
130
131 ice::u32 const const_1 = 0xcc9e2d51;
132 ice::u32 const const_2 = 0x1b873593;
133 ice::u32 hash_r1 = seed;
134
135 Char const* blocks_end = string_data + static_cast<ice::uptr>(block_num) * block_byte_size;
136
137 for (size_t idx = block_num; idx > 0; --idx)
138 {
139 ice::u32 k1 = cexpr_block_x32(blocks_end - (idx * block_byte_size));
140
141 k1 = cexpr_rotl32(k1 * const_1, 15) * const_2;
142
143 hash_r1 ^= k1;
144
145 hash_r1 = cexpr_rotl32(hash_r1, 13) * 5 + 0xe6546b64;
146 }
147
148 //----------
149 // tail
150
151 Char const* tail = blocks_end;
152
153 ice::u32 k1 = 0;
154
155 switch (string_length & 3)
156 {
157 case 3:
158 k1 ^= static_cast<ice::u8 const>(tail[2]) << 16;
159 [[fallthrough]];
160 case 2:
161 k1 ^= static_cast<ice::u8 const>(tail[1]) << 8;
162 [[fallthrough]];
163 case 1:
164 k1 ^= static_cast<ice::u8 const>(tail[0]);
165 };
166
167 k1 = cexpr_rotl32(k1 * const_1, 15) * const_2;
168 hash_r1 ^= k1;
169
170 //----------
171 // finalization
172
173 hash_r1 ^= static_cast<ice::u32>(string_length);
174
175 hash_r1 = cexpr_fmix32(hash_r1);
176
177 return mm3_x86_h32{ .h = { hash_r1 } };
178 }
179
180 //-----------------------------------------------------------------------------
181
182 template<typename Char>
183 constexpr auto cexpr_murmur3_x86_128(std::basic_string_view<Char> key, ice::u32 seed) noexcept -> mm3_x86_h128
184 {
185 Char const* string_data = key.data();
186 ice::u32 const string_length = static_cast<ice::u32>(key.length());
187
188 ice::u32 const block_byte_size = 16u;
189 ice::u32 const block_num = string_length / block_byte_size;
190
191 //----------
192 // body
193
194 ice::u32 hash_r1 = seed;
195 ice::u32 hash_r2 = seed;
196 ice::u32 hash_r3 = seed;
197 ice::u32 hash_r4 = seed;
198
199 ice::u32 const const_1 = 0x239b961b;
200 ice::u32 const const_2 = 0xab0e9789;
201 ice::u32 const const_3 = 0x38b34ae5;
202 ice::u32 const const_4 = 0xa1e38b93;
203
204 Char const* blocks_end = string_data + static_cast<ice::uptr>(block_num) * block_byte_size;
205
206 for (size_t idx = block_num; idx > 0; --idx)
207 {
208 ice::u32 k1 = cexpr_block_x32(blocks_end - (idx * block_byte_size - 0));
209 ice::u32 k2 = cexpr_block_x32(blocks_end - (idx * block_byte_size - 4));
210 ice::u32 k3 = cexpr_block_x32(blocks_end - (idx * block_byte_size - 8));
211 ice::u32 k4 = cexpr_block_x32(blocks_end - (idx * block_byte_size - 12));
212
213 k1 = cexpr_rotl32(k1 * const_1, 15) * const_2;
214 hash_r1 ^= k1;
215
216 hash_r1 = cexpr_rotl32(hash_r1, 19) + hash_r2;
217 hash_r1 = hash_r1 * 5 + 0x561ccd1b;
218
219 k2 = cexpr_rotl32(k2 * const_2, 16) * const_3;
220 hash_r2 ^= k2;
221
222 hash_r2 = cexpr_rotl32(hash_r2, 17) + hash_r3;
223 hash_r2 = hash_r2 * 5 + 0x0bcaa747;
224
225 k3 = cexpr_rotl32(k3 * const_3, 17) * const_4;
226 hash_r3 ^= k3;
227
228 hash_r3 = cexpr_rotl32(hash_r3, 15) + hash_r4;
229 hash_r3 = hash_r3 * 5 + 0x96cd1c35;
230
231 k4 = cexpr_rotl32(k4 * const_4, 18) * const_1;
232 hash_r4 ^= k4;
233
234 hash_r4 = cexpr_rotl32(hash_r4, 13) + hash_r1;
235 hash_r4 = hash_r4 * 5 + 0x32ac3b17;
236 }
237
238 //----------
239 // tail
240
241 Char const* tail = blocks_end;
242
243 ice::u32 k1 = 0;
244 ice::u32 k2 = 0;
245 ice::u32 k3 = 0;
246 ice::u32 k4 = 0;
247
248 switch (string_length & 15)
249 {
250 case 15: k4 ^= static_cast<ice::u8 const>(tail[14]) << 16;
251 [[fallthrough]];
252 case 14: k4 ^= static_cast<ice::u8 const>(tail[13]) << 8;
253 [[fallthrough]];
254 case 13: k4 ^= static_cast<ice::u8 const>(tail[12]) << 0;
255 k4 = cexpr_rotl32(k4 * const_4, 18) * const_1;
256 hash_r4 ^= k4;
257 [[fallthrough]];
258
259 case 12: k3 ^= static_cast<ice::u8 const>(tail[11]) << 24;
260 [[fallthrough]];
261 case 11: k3 ^= static_cast<ice::u8 const>(tail[10]) << 16;
262 [[fallthrough]];
263 case 10: k3 ^= static_cast<ice::u8 const>(tail[9]) << 8;
264 [[fallthrough]];
265 case 9: k3 ^= static_cast<ice::u8 const>(tail[8]) << 0;
266 k3 = cexpr_rotl32(k3 * const_3, 17) * const_4;
267 hash_r3 ^= k3;
268 [[fallthrough]];
269
270 case 8: k2 ^= static_cast<ice::u8 const>(tail[7]) << 24;
271 [[fallthrough]];
272 case 7: k2 ^= static_cast<ice::u8 const>(tail[6]) << 16;
273 [[fallthrough]];
274 case 6: k2 ^= static_cast<ice::u8 const>(tail[5]) << 8;
275 [[fallthrough]];
276 case 5: k2 ^= static_cast<ice::u8 const>(tail[4]) << 0;
277 k2 = cexpr_rotl32(k2 * const_2, 16) * const_3;
278 hash_r2 ^= k2;
279 [[fallthrough]];
280
281 case 4: k1 ^= static_cast<ice::u8 const>(tail[3]) << 24;
282 [[fallthrough]];
283 case 3: k1 ^= static_cast<ice::u8 const>(tail[2]) << 16;
284 [[fallthrough]];
285 case 2: k1 ^= static_cast<ice::u8 const>(tail[1]) << 8;
286 [[fallthrough]];
287 case 1: k1 ^= static_cast<ice::u8 const>(tail[0]) << 0;
288 k1 = cexpr_rotl32(k1 * const_1, 15) * const_2;
289 hash_r1 ^= k1;
290 };
291
292 //----------
293 // finalization
294
295 hash_r1 ^= string_length;
296 hash_r2 ^= string_length;
297 hash_r3 ^= string_length;
298 hash_r4 ^= string_length;
299
300 hash_r1 += hash_r2;
301 hash_r1 += hash_r3;
302 hash_r1 += hash_r4;
303 hash_r2 += hash_r1;
304 hash_r3 += hash_r1;
305 hash_r4 += hash_r1;
306
307 hash_r1 = cexpr_fmix32(hash_r1);
308 hash_r2 = cexpr_fmix32(hash_r2);
309 hash_r3 = cexpr_fmix32(hash_r3);
310 hash_r4 = cexpr_fmix32(hash_r4);
311
312 hash_r1 += hash_r2;
313 hash_r1 += hash_r3;
314 hash_r1 += hash_r4;
315 hash_r2 += hash_r1;
316 hash_r3 += hash_r1;
317 hash_r4 += hash_r1;
318
319 return mm3_x86_h128{ .h = { hash_r1, hash_r2, hash_r3, hash_r4 } };
320 }
321
322 //-----------------------------------------------------------------------------
323
324 template<typename Char>
325 constexpr auto cexpr_murmur3_x64_128(std::basic_string_view<Char> key, ice::u32 seed) noexcept -> mm3_x64_h128
326 {
327 Char const* string_data = key.data();
328 ice::u64 const string_length = key.length();
329
330 ice::u64 const block_byte_size = 16u;
331 ice::u64 const block_num = string_length / block_byte_size;
332
333 //----------
334 // body
335
336 ice::u64 hash_r1 = seed;
337 ice::u64 hash_r2 = seed;
338
339 ice::u64 const const_1 = 0x87c37b91114253d5llu;
340 ice::u64 const const_2 = 0x4cf5ad432745937fllu;
341
342 Char const* blocks_beg = string_data;
343
344 for (ice::u32 idx = 0; idx < block_num; ++idx)
345 {
346 ice::u64 k1 = cexpr_block_x64(blocks_beg + (idx * block_byte_size + 0));
347 ice::u64 k2 = cexpr_block_x64(blocks_beg + (idx * block_byte_size + 8));
348
349 k1 = cexpr_rotl64(k1 * const_1, 31) * const_2;
350 hash_r1 ^= k1;
351
352 hash_r1 = cexpr_rotl64(hash_r1, 27) + hash_r2;
353 hash_r1 = hash_r1 * 5 + 0x52dce729;
354
355 k2 = cexpr_rotl64(k2 * const_2, 33) * const_1;
356 hash_r2 ^= k2;
357
358 hash_r2 = cexpr_rotl64(hash_r2, 31) + hash_r1;
359 hash_r2 = hash_r2 * 5 + 0x38495ab5;
360 }
361
362 //----------
363 // tail
364
365 Char const* tail = blocks_beg + block_num * block_byte_size;
366
367 ice::u64 k1 = 0;
368 ice::u64 k2 = 0;
369
370 switch (string_length & 15)
371 {
372 case 15: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[14])) << 48;
373 [[fallthrough]];
374 case 14: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[13])) << 40;
375 [[fallthrough]];
376 case 13: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[12])) << 32;
377 [[fallthrough]];
378 case 12: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[11])) << 24;
379 [[fallthrough]];
380 case 11: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[10])) << 16;
381 [[fallthrough]];
382 case 10: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[9])) << 8;
383 [[fallthrough]];
384 case 9: k2 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[8])) << 0;
385 k2 = cexpr_rotl64(k2 * const_2, 33) * const_1;
386 hash_r2 ^= k2;
387 [[fallthrough]];
388
389 case 8: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[7])) << 56;
390 [[fallthrough]];
391 case 7: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[6])) << 48;
392 [[fallthrough]];
393 case 6: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[5])) << 40;
394 [[fallthrough]];
395 case 5: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[4])) << 32;
396 [[fallthrough]];
397 case 4: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[3])) << 24;
398 [[fallthrough]];
399 case 3: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[2])) << 16;
400 [[fallthrough]];
401 case 2: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[1])) << 8;
402 [[fallthrough]];
403 case 1: k1 ^= static_cast<ice::u64 const>(static_cast<ice::u8 const>(tail[0])) << 0;
404 k1 = cexpr_rotl64(k1 * const_1, 31) * const_2;
405 hash_r1 ^= k1;
406 };
407
408 //----------
409 // finalization
410
411 hash_r1 ^= string_length;
412 hash_r2 ^= string_length;
413
414 hash_r1 += hash_r2;
415 hash_r2 += hash_r1;
416
417 hash_r1 = cexpr_fmix64(hash_r1);
418 hash_r2 = cexpr_fmix64(hash_r2);
419
420 hash_r1 += hash_r2;
421 hash_r2 += hash_r1;
422
423 return mm3_x64_h128{ .h = { hash_r1, hash_r2 } };
424 }
425
426 } // namespace detail
427
428 constexpr auto cexpr_murmur3_x86_32(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h32
429 {
430 return detail::cexpr_murmur3_x86_32<ice::utf8>(key, seed);
431 }
432
433 constexpr auto cexpr_murmur3_x86_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h128
434 {
435 return detail::cexpr_murmur3_x86_128<ice::utf8>(key, seed);
436 }
437
438 constexpr auto cexpr_murmur3_x64_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x64_h128
439 {
440 return detail::cexpr_murmur3_x64_128<ice::utf8>(key, seed);
441 }
442
443 constexpr auto cexpr_murmur3_x86_32(std::string_view key, ice::u32 seed) noexcept -> mm3_x86_h32
444 {
445 return detail::cexpr_murmur3_x86_32<char>(key, seed);
446 }
447
448 constexpr auto cexpr_murmur3_x86_128(std::string_view key, ice::u32 seed) noexcept -> mm3_x86_h128
449 {
450 return detail::cexpr_murmur3_x86_128<char>(key, seed);
451 }
452
453 constexpr auto cexpr_murmur3_x64_128(std::string_view key, ice::u32 seed) noexcept -> mm3_x64_h128
454 {
455 return detail::cexpr_murmur3_x64_128<char>(key, seed);
456 }
457
458} // namespace ice::detail::murmur3_hash
ice::data
Definition span.hxx:129
ice::detail::murmur3_hash::detail
Definition murmur3.hxx:44
ice::detail::murmur3_hash::detail::cexpr_fmix32
constexpr auto cexpr_fmix32(ice::u32 h) noexcept -> ice::u32
Definition murmur3.hxx:95
ice::detail::murmur3_hash::detail::cexpr_fmix64
constexpr ice::u64 cexpr_fmix64(ice::u64 k) noexcept
Definition murmur3.hxx:107
ice::detail::murmur3_hash::detail::cexpr_murmur3_x86_128
constexpr auto cexpr_murmur3_x86_128(std::basic_string_view< Char > key, ice::u32 seed) noexcept -> mm3_x86_h128
Definition murmur3.hxx:183
ice::detail::murmur3_hash::detail::cexpr_rotl32
constexpr auto cexpr_rotl32(ice::u32 x, ice::i8 r) noexcept -> ice::u32
Definition murmur3.hxx:46
ice::detail::murmur3_hash::detail::cexpr_block_x64
constexpr auto cexpr_block_x64(Char const *data) noexcept -> ice::u64
Definition murmur3.hxx:71
ice::detail::murmur3_hash::detail::cexpr_murmur3_x86_32
constexpr auto cexpr_murmur3_x86_32(std::basic_string_view< Char > key, ice::u32 seed) noexcept -> mm3_x86_h32
Definition murmur3.hxx:120
ice::detail::murmur3_hash::detail::cexpr_murmur3_x64_128
constexpr auto cexpr_murmur3_x64_128(std::basic_string_view< Char > key, ice::u32 seed) noexcept -> mm3_x64_h128
Definition murmur3.hxx:325
ice::detail::murmur3_hash::detail::cexpr_block_x32
constexpr auto cexpr_block_x32(Char const *data) noexcept -> ice::u32
Definition murmur3.hxx:57
ice::detail::murmur3_hash::detail::cexpr_rotl64
constexpr auto cexpr_rotl64(ice::u64 x, ice::i8 r) noexcept -> ice::u64
Definition murmur3.hxx:51
ice::detail::murmur3_hash
Definition murmur3.hxx:18
ice::detail::murmur3_hash::cexpr_murmur3_x86_32
constexpr auto cexpr_murmur3_x86_32(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h32
Definition murmur3.hxx:428
ice::detail::murmur3_hash::cexpr_murmur3_x86_128
constexpr auto cexpr_murmur3_x86_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x86_h128
Definition murmur3.hxx:433
ice::detail::murmur3_hash::cexpr_murmur3_x64_128
constexpr auto cexpr_murmur3_x64_128(std::u8string_view key, ice::u32 seed) noexcept -> mm3_x64_h128
Definition murmur3.hxx:438
ice::i8
std::int8_t i8
Definition types.hxx:19
ice::u64
std::uint64_t u64
Definition types.hxx:27
ice::uptr
std::uintptr_t uptr
Definition types.hxx:29
ice::u32
std::uint32_t u32
Definition types.hxx:26
ice::u8
std::uint8_t u8
Definition types.hxx:24
ice::detail::murmur3_hash::mm3_x64_h128
Definition murmur3.hxx:31
ice::detail::murmur3_hash::mm3_x64_h128::h
ice::u64 h[2]
Definition murmur3.hxx:32
ice::detail::murmur3_hash::mm3_x86_h128
Definition murmur3.hxx:26
ice::detail::murmur3_hash::mm3_x86_h128::h
ice::u32 h[4]
Definition murmur3.hxx:27
ice::detail::murmur3_hash::mm3_x86_h32
Definition murmur3.hxx:21
ice::detail::murmur3_hash::mm3_x86_h32::h
ice::u32 h[1]
Definition murmur3.hxx:22
Generated by doxygen 1.18.0