libd.data.hash source code

1 module libd.data.hash;
2 
3 import libd.util.bitwise : rol;
4 
5 // Doesn't include all prime numbers in series as this is used by things like HashMap for determining size.
6 // Taken from https://github.com/skarupke/flat_hash_map/blob/master/flat_hash_map.hpp#L1124
7 // Credit to skarupe under an unknown license.
8 immutable PrimeNumberForSizeLookup = [
9     2UL, 13UL, 17UL, 23UL, 29UL, 37UL, 47UL,
10     59UL, 73UL, 97UL, 127UL, 151UL, 197UL, 251UL, 313UL, 397UL,
11     499UL, 631UL, 797UL, 1009UL, 1259UL, 1597UL, 2011UL, 2539UL,
12     3203UL, 4027UL, 5087UL, 6421UL, 8089UL, 10193UL, 12853UL, 16193UL,
13     20399UL, 25717UL, 32401UL, 40823UL, 51437UL, 64811UL, 81649UL,
14     102877UL, 129607UL, 163307UL, 205759UL, 259229UL, 326617UL,
15     411527UL, 518509UL, 653267UL, 823117UL, 1037059UL, 1306601UL,
16     1646237UL, 2074129UL, 2613229UL, 3292489UL, 4148279UL, 5226491UL,
17     6584983UL, 8296553UL, 10453007UL, 13169977UL, 16593127UL, 20906033UL,
18     26339969UL, 33186281UL, 41812097UL, 52679969UL, 66372617UL,
19     83624237UL, 105359939UL, 132745199UL, 167248483UL, 210719881UL,
20     265490441UL, 334496971UL, 421439783UL, 530980861UL, 668993977UL,
21     842879579UL, 1061961721UL, 1337987929UL, 1685759167UL, 2123923447UL,
22     2675975881UL, 3371518343UL, 4247846927UL, 5351951779UL, 6743036717UL,
23     8495693897UL, 10703903591UL, 13486073473UL, 16991387857UL,
24     21407807219UL, 26972146961UL, 33982775741UL, 42815614441UL,
25     53944293929UL, 67965551447UL, 85631228929UL, 107888587883UL,
26     135931102921UL, 171262457903UL, 215777175787UL, 271862205833UL,
27     342524915839UL, 431554351609UL, 543724411781UL, 685049831731UL,
28     863108703229UL, 1087448823553UL, 1370099663459UL, 1726217406467UL,
29     2174897647073UL, 2740199326961UL, 3452434812973UL, 4349795294267UL,
30     5480398654009UL, 6904869625999UL, 8699590588571UL, 10960797308051UL,
31     13809739252051UL, 17399181177241UL, 21921594616111UL, 27619478504183UL,
32     34798362354533UL, 43843189232363UL, 55238957008387UL, 69596724709081UL,
33     87686378464759UL, 110477914016779UL, 139193449418173UL,
34     175372756929481UL, 220955828033581UL, 278386898836457UL,
35     350745513859007UL, 441911656067171UL, 556773797672909UL,
36     701491027718027UL, 883823312134381UL, 1113547595345903UL,
37     1402982055436147UL, 1767646624268779UL, 2227095190691797UL,
38     2805964110872297UL, 3535293248537579UL, 4454190381383713UL,
39     5611928221744609UL, 7070586497075177UL, 8908380762767489UL,
40     11223856443489329UL, 14141172994150357UL, 17816761525534927UL,
41     22447712886978529UL, 28282345988300791UL, 35633523051069991UL,
42     44895425773957261UL, 56564691976601587UL, 71267046102139967UL,
43     89790851547914507UL, 113129383953203213UL, 142534092204280003UL,
44     179581703095829107UL, 226258767906406483UL, 285068184408560057UL,
45     359163406191658253UL, 452517535812813007UL, 570136368817120201UL,
46     718326812383316683UL, 905035071625626043UL, 1140272737634240411UL,
47     1436653624766633509UL, 1810070143251252131UL, 2280545475268481167UL,
48     2873307249533267101UL, 3620140286502504283UL, 4561090950536962147UL,
49     5746614499066534157UL, 7240280573005008577UL, 9122181901073924329UL,
50     11493228998133068689UL, 14480561146010017169UL, 18446744073709551557UL
51 ];
52 
53 // Conversion of the canonical source, wrapped into an incremental struct.
54 // Original code is public domain with copyright waived.
55 @nogc nothrow
56 struct HashMurmur3_32(uint Seed)
57 {
58     static if(Seed == -1)
59     {
60         private uint _seed;
61         @safe
62         this(uint seed) pure
63         {
64             this._seed = seed;
65         }
66     }
67     else
68         private uint _seed = Seed;
69 
70     @property @safe
71     uint value() pure const
72     {
73         return this._seed;
74     }
75 
76     @trusted
77     void put(const void[] key)
78     {
79         const data    = (cast(const(ubyte)[])key).ptr;
80         const nblocks = cast(uint)(key.length / 4);
81 
82         uint h1 = this._seed;
83 
84         const uint c1 = 0xcc9e2d51;
85         const uint c2 = 0x1b873593;
86 
87         if(!__ctfe)
88         {
89             const blocks = cast(uint*)(data + (nblocks * 4));
90             for(int i = -nblocks; i; i++)
91             {
92                 version(LittleEndian)
93                     uint k1 = blocks[i];
94                 else
95                     static assert(false, "TODO for Big endian");
96 
97                 k1 *= c1;
98                 k1 = rol(k1, 15);
99                 k1 *= c2;
100 
101                 h1 ^= k1;
102                 h1 = rol(h1, 13);
103                 h1 = h1*5+0xe6546b64; // ok
104             }
105         }
106         else // CTFE can't do reinterpret casts of different byte widths.
107         {
108             for(int i = nblocks; i; i--)
109             {
110                 const blockI = (i * 4);
111                 uint k1 = (
112                     (data[blockI-4] << 24)
113                   | (data[blockI-3] << 16)
114                   | (data[blockI-2] << 8)
115                   | (data[blockI-1] << 0)
116                 );
117 
118                 k1 *= c1;
119                 k1 = rol(k1, 15);
120                 k1 *= c2;
121 
122                 h1 ^= k1;
123                 h1 = rol(h1, 13);
124                 h1 = h1*5+0xe6546b64;
125             }
126         }
127 
128         const tail = (data + (nblocks * 4));
129 
130         uint k1 = 0;
131 
132         final switch(key.length & 3)
133         {
134             case 3: k1 ^= tail[2] << 16; goto case;
135             case 2: k1 ^= tail[1] << 8; goto case;
136             case 1: k1 ^= tail[0]; goto case;
137             case 0: k1 *= c1;
138                     k1 = rol(k1, 15);
139                     k1 *= c2;
140                     h1 ^= k1;
141                     break;
142         }
143 
144         h1 ^= key.length;
145         h1 ^= h1 >> 16;
146         h1 *= 0x85ebca6b;
147         h1 ^= h1 >> 13;
148         h1 *= 0xc2b2ae35;
149         h1 ^= h1 >> 16;
150         this._seed = h1;
151     }
152 }
153 ///
154 @("Murmur3_32")
155 unittest
156 {
157     const key      = "The quick brown fox jumps over the lazy dog.";
158     const seed     = 0;
159     const expected = 0xD5C48BFC;
160 
161     HashMurmur3_32!seed hash;
162     hash.put(key);
163     assert(hash.value == expected);
164 }
165 
166 alias Murmur3_32 = HashMurmur3_32!104_729; // Constant taken from the internet somewhere.
167 alias RtMurmur3_32 = HashMurmur3_32!(-1);
168 
169 uint murmur3_32HashOf(T)(auto ref T value)
170 {
171     Murmur3_32 hasher;
172     hasher.put((&value)[0..1]);
173     return hasher.value;
174 }