1 /**
2 Computes $(LINK2 https://en.wikipedia.org/wiki/MurmurHash, MurmurHash) hashes
3 of arbitrary data. MurmurHash is a non-cryptographic hash function suitable
4 for general hash-based lookup. It is optimized for x86 but can be used on
5 all architectures.
6
7 The current version is MurmurHash3, which yields a 32-bit or 128-bit hash value.
8 The older MurmurHash 1 and 2 are currently not supported.
9
10 MurmurHash3 comes in three flavors, listed in increasing order of throughput:
11 $(UL
12 $(LI `MurmurHash3!32` produces a 32-bit value and is optimized for 32-bit architectures)
13 $(LI $(D MurmurHash3!(128, 32)) produces a 128-bit value and is optimized for 32-bit architectures)
14 $(LI $(D MurmurHash3!(128, 64)) produces a 128-bit value and is optimized for 64-bit architectures)
15 )
16
17 Note:
18 $(UL
19 $(LI $(D MurmurHash3!(128, 32)) and $(D MurmurHash3!(128, 64)) produce different values.)
20 $(LI The current implementation is optimized for little endian architectures.
21 It will exhibit different results on big endian architectures and a slightly
22 less uniform distribution.)
23 )
24
25 This module conforms to the APIs defined in $(MREF std, digest).
26
27 This module publicly imports $(MREF std, digest) and can be used as a stand-alone module.
28
29 Source: $(PHOBOSSRC std/digest/murmurhash.d)
30 License: $(HTTP www.boost.org/LICENSE_1_0.txt, Boost License 1.0).
31 Authors: Guillaume Chatelet
32 References: $(LINK2 https://github.com/aappleby/smhasher, Reference implementation)
33 $(BR) $(LINK2 https://en.wikipedia.org/wiki/MurmurHash, Wikipedia)
34 */
35 /* Copyright Guillaume Chatelet 2016.
36 * Distributed under the Boost Software License, Version 1.0.
37 * (See LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
38 */
39 module std.digest.murmurhash;
40
41 version (X86)
42 version = HaveUnalignedLoads;
43 else version (X86_64)
44 version = HaveUnalignedLoads;
45
46 ///
47 @safe unittest
48 {
49 // MurmurHash3!32, MurmurHash3!(128, 32) and MurmurHash3!(128, 64) implement
50 // the std.digest Template API.
51 static assert(isDigest!(MurmurHash3!32));
52 // The convenient digest template allows for quick hashing of any data.
53 ubyte[4] hashed = digest!(MurmurHash3!32)([1, 2, 3, 4]);
54 assert(hashed == [0, 173, 69, 68]);
55 }
56
57 ///
58 @safe unittest
59 {
60 // One can also hash ubyte data piecewise by instanciating a hasher and call
61 // the 'put' method.
62 const(ubyte)[] data1 = [1, 2, 3];
63 const(ubyte)[] data2 = [4, 5, 6, 7];
64 // The incoming data will be buffered and hashed element by element.
65 MurmurHash3!32 hasher;
66 hasher.put(data1);
67 hasher.put(data2);
68 // The call to 'finish' ensures:
69 // - the remaining bits are processed
70 // - the hash gets finalized
71 auto hashed = hasher.finish();
72 assert(hashed == [181, 151, 88, 252]);
73 }
74
75 ///
76 @safe unittest
77 {
78 // Using `putElements`, `putRemainder` and `finalize` you gain full
79 // control over which part of the algorithm to run.
80 // This allows for maximum throughput but needs extra care.
81
82 // Data type must be the same as the hasher's element type:
83 // - uint for MurmurHash3!32
84 // - uint[4] for MurmurHash3!(128, 32)
85 // - ulong[2] for MurmurHash3!(128, 64)
86 const(uint)[] data = [1, 2, 3, 4];
87 // Note the hasher starts with 'Fast'.
88 MurmurHash3!32 hasher;
89 // Push as many array of elements as you need. The less calls the better.
90 hasher.putElements(data);
91 // Put remainder bytes if needed. This method can be called only once.
92 hasher.putRemainder(ubyte(1), ubyte(1), ubyte(1));
93 // Call finalize to incorporate data length in the hash.
94 hasher.finalize();
95 // Finally get the hashed value.
96 auto hashed = hasher.getBytes();
97 assert(hashed == [188, 165, 108, 2]);
98 }
99
100 public import std.digest;
101
102 @safe:
103
104 /*
105 Performance notes:
106 - To help a bit with the performance when compiling with DMD some
107 functions have been rewritten to pass by value instead of by reference.
108 - GDC and LDC are on par with their C++ counterpart.
109 - DMD is typically between 20% to 50% of the GCC version.
110 */
111
112 /++
113 + Implements the MurmurHash3 functions. You can specify the `size` of the
114 + hash in bit. For 128 bit hashes you can specify whether to optimize for 32
115 + or 64 bit architectures. If you don't specify the `opt` value it will select
116 + the fastest version of the host platform.
117 +
118 + This hasher is compatible with the `Digest` API:
119 + $(UL
120 + $(LI `void start()`)
121 + $(LI `void put(scope const(ubyte)[] data...)`)
122 + $(LI `ubyte[Element.sizeof] finish()`)
123 + )
124 +
125 + It also provides a faster, low level API working with data of size
126 + `Element.sizeof`:
127 + $(UL
128 + $(LI `void putElements(scope const(Element[]) elements...)`)
129 + $(LI `void putRemainder(scope const(ubyte[]) data...)`)
130 + $(LI `void finalize()`)
131 + $(LI `Element get()`)
132 + $(LI `ubyte[Element.sizeof] getBytes()`)
133 + )
134 +/
135 struct MurmurHash3(uint size /* 32 or 128 */ , uint opt = size_t.sizeof == 8 ? 64 : 32)
136 {
137 enum blockSize = size; // Number of bits of the hashed value.
138 size_t element_count; // The number of full elements pushed, this is used for finalization.
139
140 static if (size == 32)
141 {
142 private enum uint c1 = 0xcc9e2d51;
143 private enum uint c2 = 0x1b873593;
144 private uint h1;
145 alias Element = uint; /// The element type for 32-bit implementation.
146
147 this(uint seed)
148 {
149 h1 = seed;
150 }
151 /++
152 Adds a single Element of data without increasing `element_count`.
153 Make sure to increase `element_count` by `Element.sizeof` for each call to `putElement`.
154 +/
155 void putElement(uint block) pure nothrow @nogc
156 {
157 h1 = update(h1, block, 0, c1, c2, 15, 13, 0xe6546b64U);
158 }
159
160 /// Put remainder bytes. This must be called only once after `putElement` and before `finalize`.
161 void putRemainder(scope const(ubyte[]) data...) pure nothrow @nogc
162 {
163 assert(data.length < Element.sizeof);
164 assert(data.length >= 0);
165 element_count += data.length;
166 uint k1 = 0;
167 final switch (data.length & 3)
168 {
169 case 3:
170 k1 ^= data[2] << 16;
171 goto case;
172 case 2:
173 k1 ^= data[1] << 8;
174 goto case;
175 case 1:
176 k1 ^= data[0];
177 h1 ^= shuffle(k1, c1, c2, 15);
178 goto case;
179 case 0:
180 }
181 }
182
183 /// Incorporate `element_count` and finalizes the hash.
184 void finalize() pure nothrow @nogc
185 {
186 h1 ^= element_count;
187 h1 = fmix(h1);
188 }
189
190 /// Returns the hash as an uint value.
191 Element get() pure nothrow @nogc
192 {
193 return h1;
194 }
195
196 /// Returns the current hashed value as an ubyte array.
197 ubyte[4] getBytes() pure nothrow @nogc
198 {
199 return cast(typeof(return)) cast(uint[1])[get()];
200 }
201 }
202 else static if (size == 128 && opt == 32)
203 {
204 private enum uint c1 = 0x239b961b;
205 private enum uint c2 = 0xab0e9789;
206 private enum uint c3 = 0x38b34ae5;
207 private enum uint c4 = 0xa1e38b93;
208 private uint h4, h3, h2, h1;
209
210 alias Element = uint[4]; /// The element type for 128-bit implementation.
211
212 this(uint seed4, uint seed3, uint seed2, uint seed1) pure nothrow @nogc
213 {
214 h4 = seed4;
215 h3 = seed3;
216 h2 = seed2;
217 h1 = seed1;
218 }
219
220 this(uint seed) pure nothrow @nogc
221 {
222 h4 = h3 = h2 = h1 = seed;
223 }
224
225 /++
226 Adds a single Element of data without increasing element_count.
227 Make sure to increase `element_count` by `Element.sizeof` for each call to `putElement`.
228 +/
229 void putElement(Element block) pure nothrow @nogc
230 {
231 h1 = update(h1, block[0], h2, c1, c2, 15, 19, 0x561ccd1bU);
232 h2 = update(h2, block[1], h3, c2, c3, 16, 17, 0x0bcaa747U);
233 h3 = update(h3, block[2], h4, c3, c4, 17, 15, 0x96cd1c35U);
234 h4 = update(h4, block[3], h1, c4, c1, 18, 13, 0x32ac3b17U);
235 }
236
237 /// Put remainder bytes. This must be called only once after `putElement` and before `finalize`.
238 void putRemainder(scope const(ubyte[]) data...) pure nothrow @nogc
239 {
240 assert(data.length < Element.sizeof);
241 assert(data.length >= 0);
242 element_count += data.length;
243 uint k1 = 0;
244 uint k2 = 0;
245 uint k3 = 0;
246 uint k4 = 0;
247
248 final switch (data.length & 15)
249 {
250 case 15:
251 k4 ^= data[14] << 16;
252 goto case;
253 case 14:
254 k4 ^= data[13] << 8;
255 goto case;
256 case 13:
257 k4 ^= data[12] << 0;
258 h4 ^= shuffle(k4, c4, c1, 18);
259 goto case;
260 case 12:
261 k3 ^= data[11] << 24;
262 goto case;
263 case 11:
264 k3 ^= data[10] << 16;
265 goto case;
266 case 10:
267 k3 ^= data[9] << 8;
268 goto case;
269 case 9:
270 k3 ^= data[8] << 0;
271 h3 ^= shuffle(k3, c3, c4, 17);
272 goto case;
273 case 8:
274 k2 ^= data[7] << 24;
275 goto case;
276 case 7:
277 k2 ^= data[6] << 16;
278 goto case;
279 case 6:
280 k2 ^= data[5] << 8;
281 goto case;
282 case 5:
283 k2 ^= data[4] << 0;
284 h2 ^= shuffle(k2, c2, c3, 16);
285 goto case;
286 case 4:
287 k1 ^= data[3] << 24;
288 goto case;
289 case 3:
290 k1 ^= data[2] << 16;
291 goto case;
292 case 2:
293 k1 ^= data[1] << 8;
294 goto case;
295 case 1:
296 k1 ^= data[0] << 0;
297 h1 ^= shuffle(k1, c1, c2, 15);
298 goto case;
299 case 0:
300 }
301 }
302
303 /// Incorporate `element_count` and finalizes the hash.
304 void finalize() pure nothrow @nogc
305 {
306 h1 ^= element_count;
307 h2 ^= element_count;
308 h3 ^= element_count;
309 h4 ^= element_count;
310
311 h1 += h2;
312 h1 += h3;
313 h1 += h4;
314 h2 += h1;
315 h3 += h1;
316 h4 += h1;
317
318 h1 = fmix(h1);
319 h2 = fmix(h2);
320 h3 = fmix(h3);
321 h4 = fmix(h4);
322
323 h1 += h2;
324 h1 += h3;
325 h1 += h4;
326 h2 += h1;
327 h3 += h1;
328 h4 += h1;
329 }
330
331 /// Returns the hash as an uint[4] value.
332 Element get() pure nothrow @nogc
333 {
334 return [h1, h2, h3, h4];
335 }
336
337 /// Returns the current hashed value as an ubyte array.
338 ubyte[16] getBytes() pure nothrow @nogc
339 {
340 return cast(typeof(return)) get();
341 }
342 }
343 else static if (size == 128 && opt == 64)
344 {
345 private enum ulong c1 = 0x87c37b91114253d5;
346 private enum ulong c2 = 0x4cf5ad432745937f;
347 private ulong h2, h1;
348
349 alias Element = ulong[2]; /// The element type for 128-bit implementation.
350
351 this(ulong seed) pure nothrow @nogc
352 {
353 h2 = h1 = seed;
354 }
355
356 this(ulong seed2, ulong seed1) pure nothrow @nogc
357 {
358 h2 = seed2;
359 h1 = seed1;
360 }
361
362 /++
363 Adds a single Element of data without increasing `element_count`.
364 Make sure to increase `element_count` by `Element.sizeof` for each call to `putElement`.
365 +/
366 void putElement(Element block) pure nothrow @nogc
367 {
368 h1 = update(h1, block[0], h2, c1, c2, 31, 27, 0x52dce729U);
369 h2 = update(h2, block[1], h1, c2, c1, 33, 31, 0x38495ab5U);
370 }
371
372 /// Put remainder bytes. This must be called only once after `putElement` and before `finalize`.
373 void putRemainder(scope const(ubyte[]) data...) pure nothrow @nogc
374 {
375 assert(data.length < Element.sizeof);
376 assert(data.length >= 0);
377 element_count += data.length;
378 ulong k1 = 0;
379 ulong k2 = 0;
380 final switch (data.length & 15)
381 {
382 case 15:
383 k2 ^= ulong(data[14]) << 48;
384 goto case;
385 case 14:
386 k2 ^= ulong(data[13]) << 40;
387 goto case;
388 case 13:
389 k2 ^= ulong(data[12]) << 32;
390 goto case;
391 case 12:
392 k2 ^= ulong(data[11]) << 24;
393 goto case;
394 case 11:
395 k2 ^= ulong(data[10]) << 16;
396 goto case;
397 case 10:
398 k2 ^= ulong(data[9]) << 8;
399 goto case;
400 case 9:
401 k2 ^= ulong(data[8]) << 0;
402 h2 ^= shuffle(k2, c2, c1, 33);
403 goto case;
404 case 8:
405 k1 ^= ulong(data[7]) << 56;
406 goto case;
407 case 7:
408 k1 ^= ulong(data[6]) << 48;
409 goto case;
410 case 6:
411 k1 ^= ulong(data[5]) << 40;
412 goto case;
413 case 5:
414 k1 ^= ulong(data[4]) << 32;
415 goto case;
416 case 4:
417 k1 ^= ulong(data[3]) << 24;
418 goto case;
419 case 3:
420 k1 ^= ulong(data[2]) << 16;
421 goto case;
422 case 2:
423 k1 ^= ulong(data[1]) << 8;
424 goto case;
425 case 1:
426 k1 ^= ulong(data[0]) << 0;
427 h1 ^= shuffle(k1, c1, c2, 31);
428 goto case;
429 case 0:
430 }
431 }
432
433 /// Incorporate `element_count` and finalizes the hash.
434 void finalize() pure nothrow @nogc
435 {
436 h1 ^= element_count;
437 h2 ^= element_count;
438
439 h1 += h2;
440 h2 += h1;
441 h1 = fmix(h1);
442 h2 = fmix(h2);
443 h1 += h2;
444 h2 += h1;
445 }
446
447 /// Returns the hash as an ulong[2] value.
448 Element get() pure nothrow @nogc
449 {
450 return [h1, h2];
451 }
452
453 /// Returns the current hashed value as an ubyte array.
454 ubyte[16] getBytes() pure nothrow @nogc
455 {
456 return cast(typeof(return)) get();
457 }
458 }
459 else
460 {
461 alias Element = char; // This is needed to trigger the following error message.
462 static assert(false, "MurmurHash3(" ~ size.stringof ~ ", " ~ opt.stringof ~ ") is not implemented");
463 }
464
465 /++
466 Pushes an array of elements at once. It is more efficient to push as much data as possible in a single call.
467 On platforms that do not support unaligned reads (MIPS or old ARM chips), the compiler may produce slower code to ensure correctness.
468 +/
469 void putElements(scope const(Element[]) elements...) pure nothrow @nogc
470 {
471 foreach (const block; elements)
472 {
473 putElement(block);
474 }
475 element_count += elements.length * Element.sizeof;
476 }
477
478 //-------------------------------------------------------------------------
479 // Implementation of the Digest API.
480 //-------------------------------------------------------------------------
481
482 private union BufferUnion
483 {
484 Element block;
485 ubyte[Element.sizeof] data;
486 }
487
488 private BufferUnion buffer;
489 private size_t bufferSize;
490
491 @disable this(this);
492
493 // Initialize
494 void start()
495 {
496 this = this.init;
497 }
498
499 /++
500 Adds data to the digester. This function can be called many times in a row
501 after start but before finish.
502 +/
503 void put(scope const(ubyte)[] data...) pure nothrow
504 {
505 // Buffer should never be full while entering this function.
506 assert(bufferSize < Element.sizeof);
507
508 // Check if the incoming data doesn't fill up a whole block buffer.
509 if (bufferSize + data.length < Element.sizeof)
510 {
511 buffer.data[bufferSize .. bufferSize + data.length] = data[];
512 bufferSize += data.length;
513 return;
514 }
515
516 // Check if there's some leftover data in the first block buffer, and
517 // fill the remaining space first.
518 if (bufferSize != 0)
519 {
520 const bufferLeeway = Element.sizeof - bufferSize;
521 buffer.data[bufferSize .. $] = data[0 .. bufferLeeway];
522 putElement(buffer.block);
523 element_count += Element.sizeof;
524 data = data[bufferLeeway .. $];
525 }
526
527 // Do main work: process chunks of `Element.sizeof` bytes.
528 const numElements = data.length / Element.sizeof;
529 const remainderStart = numElements * Element.sizeof;
530 version (HaveUnalignedLoads)
531 {
532 foreach (ref const Element block; cast(const(Element[])) data[0 .. remainderStart])
533 {
534 putElement(block);
535 }
536 }
537 else
538 {
539 void processChunks(T)() @trusted
540 {
541 alias TChunk = T[Element.sizeof / T.sizeof];
542 foreach (ref const chunk; cast(const(TChunk[])) data[0 .. remainderStart])
543 {
544 static if (T.alignof >= Element.alignof)
545 {
546 putElement(*cast(const(Element)*) chunk.ptr);
547 }
548 else
549 {
550 Element[1] alignedCopy = void;
551 (cast(T[]) alignedCopy)[] = chunk[];
552 putElement(alignedCopy[0]);
553 }
554 }
555 }
556
557 const startAddress = cast(size_t) data.ptr;
558 static if (size >= 64)
559 {
560 if ((startAddress & 7) == 0)
561 {
562 processChunks!ulong();
563 goto L_end;
564 }
565 }
566 static assert(size >= 32);
567 if ((startAddress & 3) == 0)
568 processChunks!uint();
569 else if ((startAddress & 1) == 0)
570 processChunks!ushort();
571 else
572 processChunks!ubyte();
573
574 L_end:
575 }
576 element_count += numElements * Element.sizeof;
577 data = data[remainderStart .. $];
578
579 // Now add remaining data to buffer.
580 assert(data.length < Element.sizeof);
581 bufferSize = data.length;
582 buffer.data[0 .. data.length] = data[];
583 }
584
585 /++
586 Finalizes the computation of the hash and returns the computed value.
587 Note that `finish` can be called only once and that no subsequent calls
588 to `put` is allowed.
589 +/
590 ubyte[Element.sizeof] finish() pure nothrow
591 {
592 auto tail = buffer.data[0 .. bufferSize];
593 if (tail.length > 0)
594 {
595 putRemainder(tail);
596 }
597 finalize();
598 return getBytes();
599 }
600
601 //-------------------------------------------------------------------------
602 // MurmurHash3 utils
603 //-------------------------------------------------------------------------
604
605 private T rotl(T)(T x, uint y)
606 in
607 {
608 import std.traits : isUnsigned;
609
610 static assert(isUnsigned!T);
611 debug assert(y >= 0 && y <= (T.sizeof * 8));
612 }
613 do
614 {
615 return ((x << y) | (x >> ((T.sizeof * 8) - y)));
616 }
617
618 private T shuffle(T)(T k, T c1, T c2, ubyte r1)
619 {
620 import std.traits : isUnsigned;
621
622 static assert(isUnsigned!T);
623 k *= c1;
624 k = rotl(k, r1);
625 k *= c2;
626 return k;
627 }
628
629 private T update(T)(ref T h, T k, T mixWith, T c1, T c2, ubyte r1, ubyte r2, T n)
630 {
631 import std.traits : isUnsigned;
632
633 static assert(isUnsigned!T);
634 h ^= shuffle(k, c1, c2, r1);
635 h = rotl(h, r2);
636 h += mixWith;
637 return h * 5 + n;
638 }
639
640 private uint fmix(uint h) pure nothrow @nogc
641 {
642 h ^= h >> 16;
643 h *= 0x85ebca6b;
644 h ^= h >> 13;
645 h *= 0xc2b2ae35;
646 h ^= h >> 16;
647 return h;
648 }
649
650 private ulong fmix(ulong k) pure nothrow @nogc
651 {
652 k ^= k >> 33;
653 k *= 0xff51afd7ed558ccd;
654 k ^= k >> 33;
655 k *= 0xc4ceb9fe1a85ec53;
656 k ^= k >> 33;
657 return k;
658 }
659 }
660
661
662 /// The convenient digest template allows for quick hashing of any data.
663 @safe unittest
664 {
665 ubyte[4] hashed = digest!(MurmurHash3!32)([1, 2, 3, 4]);
666 assert(hashed == [0, 173, 69, 68]);
667 }
668
669 /**
670 One can also hash ubyte data piecewise by instanciating a hasher and call
671 the 'put' method.
672 */
673 @safe unittest
674 {
675 const(ubyte)[] data1 = [1, 2, 3];
676 const(ubyte)[] data2 = [4, 5, 6, 7];
677 // The incoming data will be buffered and hashed element by element.
678 MurmurHash3!32 hasher;
679 hasher.put(data1);
680 hasher.put(data2);
681 // The call to 'finish' ensures:
682 // - the remaining bits are processed
683 // - the hash gets finalized
684 auto hashed = hasher.finish();
685 assert(hashed == [181, 151, 88, 252]);
686 }
687
688 version (StdUnittest)
689 {
690 private auto hash(H, Element = H.Element)(string data)
691 {
692 H hasher;
693 immutable elements = data.length / Element.sizeof;
694 hasher.putElements(cast(const(Element)[]) data[0 .. elements * Element.sizeof]);
695 hasher.putRemainder(cast(const(ubyte)[]) data[elements * Element.sizeof .. $]);
696 hasher.finalize();
697 return hasher.getBytes();
698 }
699
700 private void checkResult(H)(in string[string] groundtruth)
701 {
702 foreach (data, expectedHash; groundtruth)
703 {
704 assert(data.digest!H.toHexString() == expectedHash);
705 assert(data.hash!H.toHexString() == expectedHash);
706 H hasher;
707 foreach (element; data)
708 {
709 hasher.put(element);
710 }
711 assert(hasher.finish.toHexString() == expectedHash);
712 }
713 }
714 }
715
716 @safe unittest
717 {
718 // dfmt off
719 checkResult!(MurmurHash3!32)([
720 "" : "00000000",
721 "a" : "B269253C",
722 "ab" : "5FD7BF9B",
723 "abc" : "FA93DDB3",
724 "abcd" : "6A67ED43",
725 "abcde" : "F69A9BE8",
726 "abcdef" : "85C08161",
727 "abcdefg" : "069B3C88",
728 "abcdefgh" : "C4CCDD49",
729 "abcdefghi" : "F0061442",
730 "abcdefghij" : "91779288",
731 "abcdefghijk" : "DF253B5F",
732 "abcdefghijkl" : "273D6FA3",
733 "abcdefghijklm" : "1B1612F2",
734 "abcdefghijklmn" : "F06D52F8",
735 "abcdefghijklmno" : "D2F7099D",
736 "abcdefghijklmnop" : "ED9162E7",
737 "abcdefghijklmnopq" : "4A5E65B6",
738 "abcdefghijklmnopqr" : "94A819C2",
739 "abcdefghijklmnopqrs" : "C15BBF85",
740 "abcdefghijklmnopqrst" : "9A711CBE",
741 "abcdefghijklmnopqrstu" : "ABE7195A",
742 "abcdefghijklmnopqrstuv" : "C73CB670",
743 "abcdefghijklmnopqrstuvw" : "1C4D1EA5",
744 "abcdefghijklmnopqrstuvwx" : "3939F9B0",
745 "abcdefghijklmnopqrstuvwxy" : "1A568338",
746 "abcdefghijklmnopqrstuvwxyz" : "6D034EA3"]);
747 // dfmt on
748 }
749
750 @safe unittest
751 {
752 // dfmt off
753 checkResult!(MurmurHash3!(128,32))([
754 "" : "00000000000000000000000000000000",
755 "a" : "3C9394A71BB056551BB056551BB05655",
756 "ab" : "DF5184151030BE251030BE251030BE25",
757 "abc" : "D1C6CD75A506B0A2A506B0A2A506B0A2",
758 "abcd" : "AACCB6962EC6AF452EC6AF452EC6AF45",
759 "abcde" : "FB2E40C5BCC5245D7701725A7701725A",
760 "abcdef" : "0AB97CE12127AFA1F9DFBEA9F9DFBEA9",
761 "abcdefg" : "D941B590DE3A86092869774A2869774A",
762 "abcdefgh" : "3611F4AE8714B1AD92806CFA92806CFA",
763 "abcdefghi" : "1C8C05AD6F590622107DD2147C4194DD",
764 "abcdefghij" : "A72ED9F50E90379A2AAA92C77FF12F69",
765 "abcdefghijk" : "DDC9C8A01E111FCA2DF1FE8257975EBD",
766 "abcdefghijkl" : "FE038573C02482F4ADDFD42753E58CD2",
767 "abcdefghijklm" : "15A23AC1ECA1AEDB66351CF470DE2CD9",
768 "abcdefghijklmn" : "8E11EC75D71F5D60F4456F944D89D4F1",
769 "abcdefghijklmno" : "691D6DEEAED51A4A5714CE84A861A7AD",
770 "abcdefghijklmnop" : "2776D29F5612B990218BCEE445BA93D1",
771 "abcdefghijklmnopq" : "D3A445046F5C51642ADC6DD99D07111D",
772 "abcdefghijklmnopqr" : "AA5493A0DA291D966A9E7128585841D9",
773 "abcdefghijklmnopqrs" : "281B6A4F9C45B9BFC3B77850930F2C20",
774 "abcdefghijklmnopqrst" : "19342546A8216DB62873B49E545DCB1F",
775 "abcdefghijklmnopqrstu" : "A6C0F30D6C738620E7B9590D2E088D99",
776 "abcdefghijklmnopqrstuv" : "A7D421D9095CDCEA393CBBA908342384",
777 "abcdefghijklmnopqrstuvw" : "C3A93D572B014949317BAD7EE809158F",
778 "abcdefghijklmnopqrstuvwx" : "802381D77956833791F87149326E4801",
779 "abcdefghijklmnopqrstuvwxy" : "0AC619A5302315755A80D74ADEFAA842",
780 "abcdefghijklmnopqrstuvwxyz" : "1306343E662F6F666E56F6172C3DE344"]);
781 // dfmt on
782 }
783
784 @safe unittest
785 {
786 // dfmt off
787 checkResult!(MurmurHash3!(128,64))([
788 "" : "00000000000000000000000000000000",
789 "a" : "897859F6655555855A890E51483AB5E6",
790 "ab" : "2E1BED16EA118B93ADD4529B01A75EE6",
791 "abc" : "6778AD3F3F3F96B4522DCA264174A23B",
792 "abcd" : "4FCD5646D6B77BB875E87360883E00F2",
793 "abcde" : "B8BB96F491D036208CECCF4BA0EEC7C5",
794 "abcdef" : "55BFA3ACBF867DE45C842133990971B0",
795 "abcdefg" : "99E49EC09F2FCDA6B6BB55B13AA23A1C",
796 "abcdefgh" : "028CEF37B00A8ACCA14069EB600D8948",
797 "abcdefghi" : "64793CF1CFC0470533E041B7F53DB579",
798 "abcdefghij" : "998C2F770D5BC1B6C91A658CDC854DA2",
799 "abcdefghijk" : "029D78DFB8D095A871E75A45E2317CBB",
800 "abcdefghijkl" : "94E17AE6B19BF38E1C62FF7232309E1F",
801 "abcdefghijklm" : "73FAC0A78D2848167FCCE70DFF7B652E",
802 "abcdefghijklmn" : "E075C3F5A794D09124336AD2276009EE",
803 "abcdefghijklmno" : "FB2F0C895124BE8A612A969C2D8C546A",
804 "abcdefghijklmnop" : "23B74C22A33CCAC41AEB31B395D63343",
805 "abcdefghijklmnopq" : "57A6BD887F746475E40D11A19D49DAEC",
806 "abcdefghijklmnopqr" : "508A7F90EC8CF0776BC7005A29A8D471",
807 "abcdefghijklmnopqrs" : "886D9EDE23BC901574946FB62A4D8AA6",
808 "abcdefghijklmnopqrst" : "F1E237F926370B314BD016572AF40996",
809 "abcdefghijklmnopqrstu" : "3CC9FF79E268D5C9FB3C9BE9C148CCD7",
810 "abcdefghijklmnopqrstuv" : "56F8ABF430E388956DA9F4A8741FDB46",
811 "abcdefghijklmnopqrstuvw" : "8E234F9DBA0A4840FFE9541CEBB7BE83",
812 "abcdefghijklmnopqrstuvwx" : "F72CDED40F96946408F22153A3CF0F79",
813 "abcdefghijklmnopqrstuvwxy" : "0F96072FA4CBE771DBBD9E398115EEED",
814 "abcdefghijklmnopqrstuvwxyz" : "A94A6F517E9D9C7429D5A7B6899CADE9"]);
815 // dfmt on
816 }
817
818 @safe unittest
819 {
820 // Pushing unaligned data and making sure the result is still coherent.
821 void testUnalignedHash(H)()
822 {
823 immutable ubyte[1028] data = 0xAC;
824 immutable alignedHash = digest!H(data[0 .. 1024]);
825 foreach (i; 1 .. 5)
826 {
827 immutable unalignedHash = digest!H(data[i .. 1024 + i]);
828 assert(alignedHash == unalignedHash);
829 }
830 }
831
832 testUnalignedHash!(MurmurHash3!32)();
833 testUnalignedHash!(MurmurHash3!(128, 32))();
834 testUnalignedHash!(MurmurHash3!(128, 64))();
835 }
The D Programming Language's Unofficial Docs
beta