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 ///
42 @safe unittest
43 {
44     // MurmurHash3!32, MurmurHash3!(128, 32) and MurmurHash3!(128, 64) implement
45     // the std.digest Template API.
46     static assert(isDigest!(MurmurHash3!32));
47     // The convenient digest template allows for quick hashing of any data.
48     ubyte[4] hashed = digest!(MurmurHash3!32)([1, 2, 3, 4]);
49     assert(hashed == [0, 173, 69, 68]);
50 }
51 
52 ///
53 @safe unittest
54 {
55     // One can also hash ubyte data piecewise by instanciating a hasher and call
56     // the 'put' method.
57     const(ubyte)[] data1 = [1, 2, 3];
58     const(ubyte)[] data2 = [4, 5, 6, 7];
59     // The incoming data will be buffered and hashed element by element.
60     MurmurHash3!32 hasher;
61     hasher.put(data1);
62     hasher.put(data2);
63     // The call to 'finish' ensures:
64     // - the remaining bits are processed
65     // - the hash gets finalized
66     auto hashed = hasher.finish();
67     assert(hashed == [181, 151, 88, 252]);
68 }
69 
70 ///
71 @safe unittest
72 {
73     // Using `putElements`, `putRemainder` and `finalize` you gain full
74     // control over which part of the algorithm to run.
75     // This allows for maximum throughput but needs extra care.
76 
77     // Data type must be the same as the hasher's element type:
78     // - uint for MurmurHash3!32
79     // - uint[4] for MurmurHash3!(128, 32)
80     // - ulong[2] for MurmurHash3!(128, 64)
81     const(uint)[] data = [1, 2, 3, 4];
82     // Note the hasher starts with 'Fast'.
83     MurmurHash3!32 hasher;
84     // Push as many array of elements as you need. The less calls the better.
85     hasher.putElements(data);
86     // Put remainder bytes if needed. This method can be called only once.
87     hasher.putRemainder(ubyte(1), ubyte(1), ubyte(1));
88     // Call finalize to incorporate data length in the hash.
89     hasher.finalize();
90     // Finally get the hashed value.
91     auto hashed = hasher.getBytes();
92     assert(hashed == [188, 165, 108, 2]);
93 }
94 
95 version (X86)
96     version = HaveUnalignedLoads;
97 else version (X86_64)
98     version = HaveUnalignedLoads;
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 }