1 /*****************************************************************************
2
3 Hash.hpp
4 Author: Laurent de Soras, 2020
5
6 --- Legal stuff ---
7
8 This program is free software. It comes without any warranty, to
9 the extent permitted by applicable law. You can redistribute it
10 and/or modify it under the terms of the Do What The Fuck You Want
11 To Public License, Version 2, as published by Sam Hocevar. See
12 http://www.wtfpl.net/ for more details.
13
14 *Tab=3***********************************************************************/
15
16
17
18 #if ! defined (fstb_Hash_CODEHEADER_INCLUDED)
19 #define fstb_Hash_CODEHEADER_INCLUDED
20
21
22
23 /*\\\ INCLUDE FILES \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
24
25 #include "fstb/fnc.h"
26
27 #include <cassert>
28 #include <climits>
29
30
31
32 namespace fstb
33 {
34
35
36
37 // Newton-Raphson iteration to find the zero of g (y) = 1 / y - x
38 template <typename T>
Hash_nr_int(T x,T y)39 inline constexpr T Hash_nr_int (T x, T y) noexcept
40 {
41 return y * (2 - y * x);
42 }
43
44
45
46 // x must be odd
47 template <typename T>
Hash_find_inverse_n(T x,int n)48 inline constexpr T Hash_find_inverse_n (T x, int n) noexcept
49 {
50 assert ((x & T (1)) != T (0));
51
52 T y = x;
53
54 for (int k = 0; k < n; ++k)
55 {
56 y = Hash_nr_int (x, y);
57 }
58
59 return y;
60 }
61
62
63
Hash_find_inverse(uint32_t x)64 inline constexpr uint32_t Hash_find_inverse (uint32_t x) noexcept
65 {
66 return Hash_find_inverse_n (x, 4);
67 }
68
69
70
Hash_find_inverse(uint64_t x)71 inline constexpr uint64_t Hash_find_inverse (uint64_t x) noexcept
72 {
73 return Hash_find_inverse_n (x, 5);
74 }
75
76
77
78 template <typename T>
Hash_reverse_xor_shift(T y,int shift)79 static inline constexpr T Hash_reverse_xor_shift (T y, int shift) noexcept
80 {
81 constexpr int resol = CHAR_BIT * sizeof (T);
82 assert (shift < resol);
83
84 int delta = resol - shift;
85 T x = (y >> delta) << delta;
86 int reversed = shift;
87 delta -= shift;
88 do
89 {
90 T xd =
91 ((y << reversed ) >> reversed)
92 ^ ((x << (reversed - shift)) >> reversed);
93 if (delta > 0)
94 {
95 xd = (xd >> delta) << delta;
96 }
97 x += xd;
98 delta -= shift;
99 reversed += shift;
100 }
101 while (reversed < resol);
102
103 return x;
104 }
105
106
107
108 /*\\\ PUBLIC \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
109
110
111
hash(uint32_t x)112 constexpr uint32_t Hash::hash (uint32_t x) noexcept
113 {
114 x ^= x >> 16;
115 x *= uint32_t (0x7FEB352Dlu);
116 x ^= x >> 15;
117 x *= uint32_t (0x846CA68Blu);
118 x ^= x >> 16;
119
120 return x;
121 }
122
123
124
hash_inv(uint32_t x)125 constexpr uint32_t Hash::hash_inv (uint32_t x) noexcept
126 {
127 #if 0
128 x = Hash_reverse_xor_shift (x, 16);
129 x *= uint32_t (0x43021123lu);
130 x = Hash_reverse_xor_shift (x, 15);
131 x *= uint32_t (0x1D69E2A5lu);
132 x = Hash_reverse_xor_shift (x, 16);
133 #else
134 x ^= x >> 16;
135 x *= uint32_t (0x43021123lu);
136 x ^= x >> 15 ^ x >> 30;
137 x *= uint32_t (0x1D69E2A5lu);
138 x ^= x >> 16;
139 #endif
140
141 return x;
142 }
143
144
145
146 // SplittableRandom / SplitMix64
hash(uint64_t x)147 constexpr uint64_t Hash::hash (uint64_t x) noexcept
148 {
149 x ^= x >> 30;
150 x *= uint64_t (0xBF58476D1CE4E5B9llu);
151 x ^= x >> 27;
152 x *= uint64_t (0x94D049BB133111EBllu);
153 x ^= x >> 31;
154
155 return x;
156 }
157
158
159
160 // Source:
161 // https://www.vincent-lunot.com/post/playing-with-pseudo-random-number-generators-part-3/
hash_inv(uint64_t x)162 constexpr uint64_t Hash::hash_inv (uint64_t x) noexcept
163 {
164 x = Hash_reverse_xor_shift (x, 31);
165 x *= Hash_find_inverse (uint64_t (0x94D049BB133111EBllu));
166 x = Hash_reverse_xor_shift (x, 27);
167 x *= Hash_find_inverse (uint64_t (0xBF58476D1CE4E5B9llu));
168 x = Hash_reverse_xor_shift (x, 30);
169
170 return x;
171 }
172
173
174
rrmxmx(uint64_t x)175 constexpr uint64_t Hash::rrmxmx (uint64_t x) noexcept
176 {
177 constexpr int s = 28;
178 constexpr uint64_t m = 0x9FB21C651E98DF25ULL;
179
180 x ^= fstb::rotr (x, 49) ^ fstb::rotr (x, 24);
181 x *= m;
182 x ^= x >> s;
183 x *= m;
184 x ^= x >> s;
185
186 return x;
187 }
188
189
190
nasam(uint64_t x)191 constexpr uint64_t Hash::nasam (uint64_t x) noexcept
192 {
193 x ^= fstb::rotr (x, 25) ^ fstb::rotr (x, 47);
194 x *= 0x9E6C63D0676A9A99ULL;
195 x ^= (x >> 23) ^ (x >> 51);
196 x *= 0x9E6D62D06F6A9A9BULL;
197 x ^= (x >> 23) ^ (x >> 51);
198
199 return x;
200 }
201
202
203
pelican(uint64_t x)204 constexpr uint64_t Hash::pelican (uint64_t x) noexcept
205 {
206 x ^= fstb::rotr (x, 23) ^ fstb::rotr (x, 47) ^ 0xD1B54A32D192ED03ULL;
207 x *= 0xAEF17502108EF2D9ULL;
208 x ^= (x >> 43) ^ (x >> 31) ^ (x >> 23);
209 x *= 0xDB4F0B9175AE2165ULL;
210 x ^= x >> 28;
211
212 return x;
213 }
214
215
216
217 /*\\\ PROTECTED \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
218
219
220
221 /*\\\ PRIVATE \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
222
223
224
225 } // namespace fstb
226
227
228
229 #endif // fstb_Hash_CODEHEADER_INCLUDED
230
231
232
233 /*\\\ EOF \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\*/
234