1 /** Various hash functions, including integer ones.
2  */
3 module nxt.hash_functions;
4 
5 @safe nothrow:
6 
7 /** See_Also: http://forum.dlang.org/post/o1igoc$21ma$1@digitalmars.com
8  *
9  * Doesn't work: integers are returned as is.
10  */
11 size_t typeidHashOf(T)(in T x) @trusted
12 {
13     version(D_Coverage) {} else pragma(inline, true);
14     return typeid(T).getHash(&x);
15 }
16 
17 ///
18 @safe nothrow unittest
19 {
20     scope x = typeidHashOf(cast(int)17);
21 }
22 
23 pure @nogc:
24 
25 hash_t hashOfTypeInfoPtr(TypeInfo_Class typeinfo) @trusted pure nothrow @nogc
26 {
27     version(D_Coverage) {} else pragma(inline, true);
28     assert(typeof(typeinfo).alignof == 8);
29     return (cast(hash_t)(cast(void*)typeinfo) >> 3);
30 }
31 
32 /** Hash that incorporates the hash of `typeid` bit-xored with `hashOf(a)`.
33  *
34  * See_Also: https://forum.dlang.org/post/lxqoknwuujbymolnlyfw@forum.dlang.org
35  */
36 hash_t hashOfPolymorphic(Class)(Class a) @trusted pure nothrow @nogc
37 if (is(Class == class))
38 {
39     version(D_Coverage) {} else pragma(inline, true);
40     static assert(typeid(Class).alignof == 8);
41     // const class_typeid_hash = (cast(hash_t)(cast(void*)typeid(Class)) >> 3)
42     import core.internal.hash : hashOf;
43     return fibonacci_hash(hashOf(cast(void*)typeid(a))) ^ hashOf(a);
44 }
45 
46 size_t fibonacci_hash(hash_t hash) @safe pure nothrow @nogc
47 {
48     version(D_Coverage) {} else pragma(inline, true);
49     return (hash * 11400714819323198485LU);
50 }
51 
52 version(unittest)
53 {
54     private static:
55 
56     class Thing
57     {
58     }
59 
60     class Expr : Thing
61     {
62         @safe pure nothrow @nogc:
63         alias Data = string;
64         this(Data data)
65         {
66             this.data = data;
67         }
68         @property override hash_t toHash() const @safe pure nothrow @nogc
69         {
70             return hashOf(data);
71         }
72         Data data;
73     }
74 
75     class NounExpr : Expr
76     {
77         @safe pure nothrow @nogc:
78         this(Data data)
79         {
80             super(data);
81         }
82         @property override hash_t toHash() const @safe pure nothrow @nogc
83         {
84             return hashOf(data);
85         }
86     }
87 }
88 
89 ///
90 @safe pure nothrow @nogc unittest
91 {
92     scope car1 = new Expr("car");
93     scope car2 = new Expr("car");
94     scope bar1 = new Expr("bar");
95     scope ncar = new NounExpr("car");
96 
97     void testEqual() @safe pure nothrow @nogc
98     {
99         assert(hashOf(car1) == hashOf(car2));
100         assert(hashOfPolymorphic(car1) == hashOfPolymorphic(car2));
101     }
102 
103     void testDifferent1() @safe pure nothrow @nogc
104     {
105         assert(hashOf(car1) != hashOf(bar1));
106         assert(hashOfPolymorphic(car1) != hashOfPolymorphic(bar1));
107     }
108 
109     void testDifferent2() @safe pure nothrow @nogc
110     {
111         assert(hashOf(car1) == hashOf(ncar));
112         assert(hashOfPolymorphic(car1) != hashOfPolymorphic(ncar));
113     }
114 
115     testEqual();
116     testDifferent1();
117     testDifferent2();
118 }
119 
120 @nogc:
121 
122 /** Dummy-hash for benchmarking performance of HashSet. */
123 ulong identityHash64Of(in ulong x)
124 {
125     version(D_Coverage) {} else pragma(inline, true);
126     return x;               // maps -1 to ulong.max
127 }
128 
129 ///
130 @safe pure nothrow @nogc unittest
131 {
132     assert(identityHash64Of(-1) == ulong.max);
133     assert(identityHash64Of(int.max) == int.max);
134     assert(identityHash64Of(ulong.max) == ulong.max);
135 }
136 
137 /** Mueller integer hash function (bit mixer) A (32-bit).
138  *
139  * See_Also: https://stackoverflow.com/a/12996028/683710
140  * See_Also: http://zimbry.blogspot.se/2011/09/better-bit-mixing-improving-on.html
141  */
142 uint muellerHash32(uint x)
143 {
144     version(D_Coverage) {} else pragma(inline, true);
145     x = ((x >> 16) ^ x) * 0x45d9f3b;
146     x = ((x >> 16) ^ x) * 0x45d9f3b;
147     x = (x >> 16) ^ x;
148     return x;
149 }
150 
151 /** Mueller integer hash function (bit mixer) A (64-bit).
152  *
153  * Based on splitmix64, which seems to be based on the blog article "Better Bit
154  * Mixing" (mix 13).
155  *
156  * See_Also: https://stackoverflow.com/a/12996028/683710
157  * See_Also: http://zimbry.blogspot.se/2011/09/better-bit-mixing-improving-on.html
158  * See_Also: http://xorshift.di.unimi.it/splitmix64.c
159  */
160 ulong muellerHash64(in ulong x)
161 {
162     version(D_Coverage) {} else pragma(inline, true);
163     typeof(return) y = x;
164     y = (y ^ (y >> 30)) * 0xbf58476d1ce4e5b9UL;
165     y = (y ^ (y >> 27)) * 0x94d049bb133111ebUL;
166     y = y ^ (y >> 31);
167     return y;
168 }
169 
170 /** Thomas Wang 64-bit mix integer hash function.
171  *
172  * See_Also: https://gist.github.com/badboy/6267743#64-bit-mix-functions
173  */
174 public ulong wangMixHash64(ulong x)
175 {
176     version(D_Coverage) {} else pragma(inline, true);
177     x = (~x) + (x << 21); // x = (x << 21) - x - 1;
178     x = x ^ (x >>> 24);
179     x = (x + (x << 3)) + (x << 8); // x * 265
180     x = x ^ (x >>> 14);
181     x = (x + (x << 2)) + (x << 4); // x * 21
182     x = x ^ (x >>> 28);
183     x = x + (x << 31);
184     return x;
185 }
186 
187 ///
188 @safe pure nothrow @nogc unittest
189 {
190     assert(wangMixHash64(0) == 8633297058295171728UL);
191     assert(wangMixHash64(1) == 6614235796240398542UL);
192 }
193 
194 /** Inspired by lemire's strongly universal hashing.
195  *
196  * See_Also: https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
197  *
198  * Instead of shifts, we use rotations so we don't lose any bits.
199  *
200  * Added a final multiplcation with a constant for more mixing. It is most important that the
201  * lower bits are well mixed.
202  */
203 ulong lemireHash64(in ulong x)
204 {
205     version(D_Coverage) {} else pragma(inline, true);
206     import core.bitop : ror;
207     const ulong h1 = x * 0xA24BAED4963EE407UL;
208     const ulong h2 = ror(x, 32U) * 0x9FB21C651E98DF25UL;
209     const ulong h = ror(h1 + h2, 32U);
210     return h;
211 }
212 
213 ///
214 @safe pure nothrow @nogc unittest
215 {
216     assert(lemireHash64(0) == 0UL);
217     assert(lemireHash64(1) == 10826341276197359097UL);
218     assert(lemireHash64(2) == 3205938474390199283UL);
219 }
220 
221 /** Inspired by lemire's strongly universal hashing.
222  *
223  * See_Also: https://lemire.me/blog/2018/08/15/fast-strongly-universal-64-bit-hashing-everywhere/
224  *
225  * Instead of shifts, we use rotations so we don't lose any bits.
226  *
227  * Added a final multiplcation with a constant for more mixing. It is most important that the
228  * lower bits are well mixed.
229  */
230 ulong lemireHash64(in double x) @trusted
231 {
232     version(D_Coverage) {} else pragma(inline, true);
233     import core.bitop : ror;
234     const ulong h1 = *(cast(ulong*)&x) * 0xA24BAED4963EE407UL;
235     const ulong h2 = ror(*(cast(ulong*)&x), 32U) * 0x9FB21C651E98DF25UL;
236     const ulong h = ror(h1 + h2, 32U);
237     return h;
238 }
239 
240 ///
241 @safe pure nothrow @nogc unittest
242 {
243     assert(lemireHash64(0f) == 0UL);
244     assert(lemireHash64(1f) == 5597974336836488763);
245     assert(lemireHash64(2f) == 4611686018555721673UL);
246 }