| Geant4 Cross Reference |
1 //
2 // ********************************************************************
3 // * License and Disclaimer *
4 // * *
5 // * The Geant4 software is copyright of the Copyright Holders of *
6 // * the Geant4 Collaboration. It is provided under the terms and *
7 // * conditions of the Geant4 Software License, included in the file *
8 // * LICENSE and available at http://cern.ch/geant4/license . These *
9 // * include a list of copyright holders. *
10 // * *
11 // * Neither the authors of this software system, nor their employing *
12 // * institutes,nor the agencies providing financial support for this *
13 // * work make any representation or warranty, express or implied, *
14 // * regarding this software system or assume any liability for its *
15 // * use. Please see the license in the file LICENSE and URL above *
16 // * for the full disclaimer and the limitation of liability. *
17 // * *
18 // * This code implementation is the result of the scientific and *
19 // * technical work of the GEANT4 collaboration. *
20 // * By using, copying, modifying or distributing the software (or *
21 // * any work based on the software) you agree to acknowledge its *
22 // * use in resulting scientific publications, and indicate your *
23 // * acceptance of all terms of the Geant4 Software license. *
24 // ********************************************************************
25 //
26 //
27 //
28 // MolecularDNAHashing.hh
29 // Geant4
30 //
31 // Created by Mathieu Karamitros
32 //
33 //
34
35 #ifndef MolecularDNAHashing_h
36 #define MolecularDNAHashing_h
37
38 #include <cstdint>
39 #include <string>
40 #include <type_traits>
41 #include <utility>
42
43 //....oooOO0OOooo........oooOO0OOooo........oooOO0OOooo........oooOO0OOooo......
44
45 namespace G4::hashing
46 {
47 namespace crc32
48 {
49 //--------------------------------------------------------------------------
50 // Generate CRC lookup table
51 //--------------------------------------------------------------------------
52
53 template<unsigned long long c, int k = 8>
54 struct f : f<((c & 1) ? 0xedb88320 : 0) ^ (c >> 1), k - 1>
55 {};
56 template<unsigned long long c>
57 struct f<c, 0>
58 {
59 enum
60 {
61 value = c
62 };
63 };
64
65 #define _A_(x) _B_(x) _B_(x + 128llu)
66 #define _B_(x) _C_(x) _C_(x + 64llu)
67 #define _C_(x) _D_(x) _D_(x + 32llu)
68 #define _D_(x) _E_(x) _E_(x + 16llu)
69 #define _E_(x) _F_(x) _F_(x + 8llu)
70 #define _F_(x) _G_(x) _G_(x + 4llu)
71 #define _G_(x) _H_(x) _H_(x + 2llu)
72 #define _H_(x) _I_(x) _I_(x + 1llu)
73 #define _I_(x) f<x>::value,
74
75 static constexpr unsigned fCrc_table[] = {_A_(0llu)};
76
77 //--------------------------------------------------------------------------
78 // CRC32 ALGO
79 //--------------------------------------------------------------------------
80
81 //--------------------------------
82 // RUN TIME ALGO
83 uint32_t Hash(const char* str, size_t len);
84
85 //--------------------------------------------------------------------------
86 // Details for compilation time
87 namespace detail
88 {
89 // CRC32 Table (zlib polynomial)
90 template<size_t idx>
91 constexpr uint32_t Combine_crc32(const char* str, uint32_t part)
92 {
93 return (part >> 8) ^ fCrc_table[(part ^ str[idx]) & 0x000000FF];
94 }
95
96 // recursion
97 template<size_t idx>
98 constexpr uint32_t Crc32(const char* str)
99 {
100 return Combine_crc32<idx>(str, Crc32<idx - 1>(str));
101 }
102
103 // stop-recursion
104 template<>
105 constexpr uint32_t Crc32<size_t(-1)>(const char* /*str*/)
106 {
107 return 0xFFFFFFFF;
108 }
109 } // namespace detail
110
111 //--------------------------------------------------------------------------
112 // use COMPILATION TIME CRC32 as a hash function
113 template<size_t len>
114 constexpr uint32_t Hash(const char (&str)[len])
115 {
116 return (detail::Crc32<len - 2>(str)) ^ 0xFFFFFFFF;
117 }
118
119 //--------------------------------------------------------------------------
120 // std::string hasher for convenience
121 uint32_t Hash(const std::string& str);
122 // in window
123 // warning C4717: 'G4::hashing::crc32::crc32_hasher<G4String>::operator()':
124 // recursive on all control paths, function will cause runtime stack overflow
125 /*
126 template <typename T>
127 struct crc32_hasher
128 {
129 template <size_t len>
130 uint32_t constexpr operator()(const char (&str)[len]) const
131 {
132 return hash(str);
133 }
134
135 uint32_t operator()(T str) const { return hash(str); }
136 };
137
138 template <typename T>
139 uint32_t constexpr hash(T&& t)
140 {
141 return crc32_hasher<typename std::decay<T>::type>()(std::forward<T>(t));
142 }
143 */
144 } // namespace crc32
145
146 //--------------------------------------------------------------------------
147 // fnv ALGO
148 //--------------------------------------------------------------------------
149
150 namespace fnv
151 {
152 // Fowler / Noll / Vo (fnv) Hash - 1a
153 // magic numbers from http://www.isthe.com/chongo/tech/comp/fnv/
154 #define fnv_offset_basis 0xcbf29ce484222325U
155 #define fnv_prime 0x100000001b3U // 64 bits
156 // 224 + 28 + 0x93
157
158 //------------------------------------------------------------------------
159 // Run time
160 size_t Hash(const std::string& str);
161
162 //--------------------------------------------------------------------------
163 // Details for compilation time
164 namespace detail
165 {
166 // recursion
167 template<int idx>
168 constexpr size_t Fnv(const char* str, size_t len, size_t hash)
169 {
170 return Fnv<idx - 1>(str, len, (hash ^ (str[len - idx])) * fnv_prime);
171 }
172
173 // stop-recursion
174 template<>
175 constexpr size_t Fnv<-1>(const char*, size_t, size_t hash)
176 {
177 return hash;
178 }
179 } // namespace detail
180
181 //------------------------------------------------------------------------
182 // COMPILATION TIME
183 template<size_t len>
184 constexpr size_t Hash(const char (&str)[len])
185 {
186 return detail::Fnv<len - 2>(str, len - 2, fnv_offset_basis);
187 }
188
189 //------------------------------------------------------------------------
190 template<class>
191 struct fnv_hasher;
192
193 template<typename T>
194 struct fnv_hasher
195 {
196 template<size_t len>
197 size_t constexpr operator()(const char (&str)[len]) const
198 {
199 return Hash(str);
200 }
201
202 size_t operator()(const T& str) const { return Hash(str); }
203 };
204
205 // template<>
206 // size_t fnv_hasher<std::string>::operator()(const std::string& str)
207 // const{
208 // return hash(str.c_str());
209 // }
210
211 template<typename T>
212 size_t constexpr Hash(T&& t)
213 {
214 return fnv_hasher<typename std::decay<T>::type>()(std::forward<T>(t));
215 }
216 } // namespace fnv
217
218 //--------------------------------------------------------------------------
219 // LARSON
220 //--------------------------------------------------------------------------
221
222 namespace larson
223 {
224 //------------------------------------------------------------------------
225 // Details for compilation time
226 namespace detail
227 {
228 // recursion
229 template<int idx>
230 constexpr size_t Larson(const char* str, size_t len, size_t hash)
231 {
232 return Larson<idx - 1>(str, len + 1, hash * 101 + str[len]);
233 }
234
235 // stop-recursion
236 template<>
237 constexpr size_t Larson<-1>(const char*, size_t, size_t hash)
238 {
239 return hash;
240 }
241 } // namespace detail
242
243 //------------------------------------------------------------------------
244 // COMPILATION TIME
245 template<size_t len>
246 constexpr size_t Cthash(const char (&str)[len], unsigned int seed = 0)
247 {
248 return detail::Larson<len - 2>(str, 0, seed);
249 }
250
251 //------------------------------------------------------------------------
252 // RUN TIME
253 size_t Hash(const char* str, unsigned int seed = 0);
254
255 size_t Hash(std::string str, unsigned int seed = 0);
256 } // namespace larson
257
258 //--------------------------------------------------------------------------
259 // DEFAULT STRING HASHER
260 //--------------------------------------------------------------------------
261
262 template<typename T>
263 struct hasher
264 {
265 std::size_t constexpr operator()(char const* input) const
266 {
267 return *input ? static_cast<std::size_t>(*input) + 33 * (*this)(input + 1) : 5381;
268 }
269
270 std::size_t operator()(const std::string& str) const { return (*this)(str.c_str()); }
271 };
272
273 template<typename T>
274 std::size_t constexpr Hash(T&& t)
275 {
276 return hasher<typename std::decay<T>::type>()(std::forward<T>(t));
277 }
278
279 // not necessary
280 template<>
281 std::size_t constexpr Hash<const char*>(const char*&& str)
282 {
283 return hasher<std::string>()(str);
284 }
285
286 inline namespace literals
287 {
288 std::size_t constexpr operator"" _hash(const char* s, size_t)
289 {
290 return hasher<std::string>()(s);
291 }
292 } // namespace literals
293 } // namespace G4::hashing
294
295 using namespace G4::hashing::literals;
296
297 //....oooOO0OOooo........oooOO0OOooo........oooOO0OOooo........oooOO0OOooo......
298
299 #endif
300