Line data Source code
1 : // The libMesh Finite Element Library.
2 : // Copyright (C) 2002-2025 Benjamin S. Kirk, John W. Peterson, Roy H. Stogner
3 :
4 : // This library is free software; you can redistribute it and/or
5 : // modify it under the terms of the GNU Lesser General Public
6 : // License as published by the Free Software Foundation; either
7 : // version 2.1 of the License, or (at your option) any later version.
8 :
9 : // This library is distributed in the hope that it will be useful,
10 : // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 : // Lesser General Public License for more details.
13 :
14 : // You should have received a copy of the GNU Lesser General Public
15 : // License along with this library; if not, write to the Free Software
16 : // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17 :
18 : #ifndef LIBMESH_HASHWORD_H
19 : #define LIBMESH_HASHWORD_H
20 :
21 : // ::size_t is defined in the backward compatibility header stddef.h.
22 : // It's been part of ANSI/ISO C and ISO C++ since their very
23 : // beginning. Every C++ implementation has to ship with stddef.h
24 : // (compatibility) and cstddef where only the latter defines
25 : // std::size_t and not necessarily ::size_t. See Annex D of the C++
26 : // Standard.
27 : //
28 : // http://stackoverflow.com/questions/237370/does-stdsize-t-make-sense-in-c
29 : #include <stddef.h>
30 : #include <stdint.h> // uint32_t, uint64_t
31 : #include <vector>
32 :
33 : #include "libmesh_common.h" // libmesh_error_msg(), libmesh_fallthrough
34 :
35 : // Anonymous namespace for utility functions used locally
36 : namespace
37 : {
38 : /**
39 : * Rotate x by k bits.
40 : *
41 : * \author Bob Jenkins
42 : * \date May 2006
43 : * \copyright Public Domain
44 : * http://burtleburtle.net/bob/hash/index.html
45 : */
46 : inline
47 45118316 : uint32_t rot(uint32_t x, uint32_t k)
48 : {
49 92671401 : return (x<<k) | (x>>(32-k));
50 : }
51 :
52 :
53 :
54 : /**
55 : * Mix 3 32-bit values reversibly.
56 : *
57 : * \author Bob Jenkins
58 : * \date May 2006
59 : * \copyright Public Domain
60 : * http://burtleburtle.net/bob/hash/index.html
61 : */
62 : inline
63 2597837 : void mix(uint32_t & a, uint32_t & b, uint32_t & c)
64 : {
65 3673559 : a -= c; a ^= rot(c, 4); c += b;
66 3673559 : b -= a; b ^= rot(a, 6); a += c;
67 3673559 : c -= b; c ^= rot(b, 8); b += a;
68 3673559 : a -= c; a ^= rot(c,16); c += b;
69 3673559 : b -= a; b ^= rot(a,19); a += c;
70 3673559 : c -= b; c ^= rot(b, 4); b += a;
71 2597837 : }
72 :
73 :
74 : /**
75 : * Perform a "final" mixing of 3 32-bit numbers, result is stored in c.
76 : *
77 : * \author Bob Jenkins
78 : * \date May 2006
79 : * \copyright Public Domain
80 : * http://burtleburtle.net/bob/hash/index.html
81 : */
82 : inline
83 13294720 : void final_mix(uint32_t & a, uint32_t & b, uint32_t & c)
84 : {
85 18774898 : c ^= b; c -= rot(b,14);
86 18774898 : a ^= c; a -= rot(c,11);
87 18774898 : b ^= a; b -= rot(a,25);
88 18774898 : c ^= b; c -= rot(b,16);
89 18774898 : a ^= c; a -= rot(c,4);
90 18774898 : b ^= a; b -= rot(a,14);
91 18774898 : c ^= b; c -= rot(b,24);
92 13294720 : }
93 :
94 :
95 : /**
96 : * fnv_64_buf - perform a 64 bit Fowler/Noll/Vo hash on a buffer.
97 : * http://www.isthe.com/chongo/tech/comp/fnv/index.html
98 : *
99 : * \author Phong Vo (http://www.research.att.com/info/kpv/)
100 : * \author Glenn Fowler (http://www.research.att.com/~gsf/)
101 : * \author Landon Curt Noll (http://www.isthe.com/chongo/)
102 : * \date 1991, 2012
103 : * \copyright Public Domain
104 : *
105 : * \param buf start of buffer to hash
106 : * \param len length of buffer in octets
107 : * \returns 64 bit hash as a static hash type
108 : */
109 78121414 : uint64_t fnv_64_buf(const void * buf, size_t len)
110 : {
111 : // Initializing hval with this value corresponds to the FNV-1 hash algorithm.
112 0 : uint64_t hval = static_cast<uint64_t>(0xcbf29ce484222325ULL);
113 :
114 : // start of buffer
115 0 : const unsigned char * bp = static_cast<const unsigned char *>(buf);
116 :
117 : // beyond end of buffer
118 78121414 : const unsigned char * be = bp + len;
119 :
120 : // FNV-1 hash each octet of the buffer
121 2218601718 : while (bp < be)
122 : {
123 : // This line computes hval *= FNV_Prime, where
124 : // FNV_Prime := 1099511628211
125 : // = 2^40 + 2^8 + 179
126 : // is the prime number used for for 64-bit hashes.
127 : // See also: https://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
128 2140480304 : hval +=
129 2140480304 : (hval << 1) + (hval << 4) + (hval << 5) +
130 2140480304 : (hval << 7) + (hval << 8) + (hval << 40);
131 :
132 : // xor the bottom with the current octet
133 2140480304 : hval ^= static_cast<uint64_t>(*bp++);
134 : }
135 :
136 : // return our new hash value
137 78121414 : return hval;
138 : }
139 :
140 : } // end anonymous namespace
141 :
142 :
143 :
144 : namespace libMesh
145 : {
146 : namespace Utility
147 : {
148 : /**
149 : * The hashword function takes an array of uint32_t's of length 'length'
150 : * and computes a single key from it.
151 : *
152 : * \author Bob Jenkins
153 : * \date May 2006
154 : * \copyright Public Domain
155 : * http://burtleburtle.net/bob/hash/index.html
156 : */
157 : inline
158 6812195 : uint32_t hashword(const uint32_t * k, size_t length, uint32_t initval=0)
159 : {
160 : uint32_t a,b,c;
161 :
162 : // Set up the internal state
163 6812195 : a = b = c = 0xdeadbeef + ((static_cast<uint32_t>(length))<<2) + initval;
164 :
165 : //------------------------------------------------- handle most of the key
166 9410032 : while (length > 3)
167 : {
168 2597837 : a += k[0];
169 2597837 : b += k[1];
170 2597837 : c += k[2];
171 2597837 : mix(a,b,c);
172 2597837 : length -= 3;
173 2597837 : k += 3;
174 : }
175 :
176 : //------------------------------------------- handle the last 3 uint32_t's
177 6812195 : switch(length) // all the case statements fall through
178 : {
179 4208778 : case 3 : c+=k[2];
180 : libmesh_fallthrough();
181 4214358 : case 2 : b+=k[1];
182 : libmesh_fallthrough();
183 6812195 : case 1 : a+=k[0];
184 6812195 : final_mix(a,b,c);
185 : libmesh_fallthrough();
186 2843270 : default: // case 0: nothing left to add
187 2843270 : break;
188 : }
189 :
190 : //------------------------------------------------------ report the result
191 6812195 : return c;
192 : }
193 :
194 :
195 :
196 : /**
197 : * Calls function above with slightly more convenient std::vector interface.
198 : */
199 : inline
200 4182 : uint32_t hashword(const std::vector<uint32_t> & keys, uint32_t initval=0)
201 : {
202 10158 : return hashword(keys.data(), keys.size(), initval);
203 : }
204 :
205 :
206 : /**
207 : * This is a hard-coded version of hashword for hashing exactly 2 numbers.
208 : *
209 : * \author Bob Jenkins
210 : * \date May 2006
211 : * \copyright Public Domain
212 : * http://burtleburtle.net/bob/hash/index.html
213 : */
214 : inline
215 3802565 : uint32_t hashword2(const uint32_t & first, const uint32_t & second, uint32_t initval=0)
216 : {
217 : uint32_t a,b,c;
218 :
219 : // Set up the internal state
220 6482525 : a = b = c = 0xdeadbeef + 8 + initval;
221 :
222 6482525 : b+=second;
223 6482525 : a+=first;
224 6482525 : final_mix(a,b,c);
225 :
226 6482525 : return c;
227 : }
228 :
229 : /**
230 : * Computes the same hash as calling fnv_64_buf() with exactly two entries.
231 : * This function allows the compiler to optimize by unrolling loops whose
232 : * number of iterations are known at compile time. By inspecting the assembly
233 : * generated for different optimization levels, we observed that the compiler
234 : * sometimes chooses to unroll only the outer loop, but may also choose to
235 : * unroll both the outer and inner loops.
236 : */
237 : inline
238 171161489 : uint64_t hashword2(const uint64_t first, const uint64_t second)
239 : {
240 : // Initializing hval with this value corresponds to the FNV-1 hash algorithm.
241 : uint64_t hval = static_cast<uint64_t>(0xcbf29ce484222325ULL);
242 :
243 513484467 : for (int i=0; i!=2; ++i)
244 : {
245 : // char pointers to (start, end) of either "first" or "second". We interpret
246 : // the 64 bits of each input 64-bit integer as 8 8-byte characters.
247 342322978 : auto beg = reinterpret_cast<const unsigned char *>(i==0 ? &first : &second);
248 342322978 : auto end = beg + sizeof(uint64_t)/sizeof(unsigned char); // beg+8
249 :
250 : // FNV-1 hash each octet of the buffer
251 3080906802 : while (beg < end)
252 : {
253 2738583824 : hval +=
254 2738583824 : (hval << 1) + (hval << 4) + (hval << 5) +
255 2738583824 : (hval << 7) + (hval << 8) + (hval << 40);
256 :
257 : // xor the bottom with the current octet
258 2738583824 : hval ^= static_cast<uint64_t>(*beg++);
259 : }
260 : }
261 :
262 171161489 : return hval;
263 : }
264 :
265 : inline
266 : uint16_t hashword2(const uint16_t first, const uint16_t second)
267 : {
268 : return static_cast<uint16_t>(first%65449 + (second<<5)%65449);
269 : }
270 :
271 : /**
272 : * Call the 64-bit FNV hash function.
273 : */
274 : inline
275 : uint64_t hashword(const uint64_t * k, size_t length)
276 : {
277 78121414 : return fnv_64_buf(k, 8*length);
278 : }
279 :
280 :
281 :
282 : /**
283 : * In a personal communication from Bob Jenkins, he recommended using
284 : * "Probably final_mix() from lookup3.c... You could hash up to 6 16-bit
285 : * integers that way. The output is c, or the top or bottom 16 bits
286 : * of c if you only need 16 bit hash values." [JWP]
287 : */
288 : inline
289 : uint16_t hashword(const uint16_t * k, size_t length)
290 : {
291 : // Three values that will be passed to final_mix() after they are initialized.
292 : uint32_t a = 0;
293 : uint32_t b = 0;
294 : uint32_t c = 0;
295 :
296 : switch (length)
297 : {
298 : case 3:
299 : {
300 : // Cast the inputs to 32 bit integers and call final_mix().
301 : a = k[0];
302 : b = k[1];
303 : c = k[2];
304 : break;
305 : }
306 : case 4:
307 : {
308 : // Combine the 4 16-bit inputs, "w, x, y, z" into two 32-bit
309 : // inputs "wx" and "yz" using bit operations and call final_mix.
310 : a = ((k[0]<<16) | (k[1] & 0xffff)); // wx
311 : b = ((k[2]<<16) | (k[3] & 0xffff)); // yz
312 : break;
313 : }
314 : default:
315 : libmesh_error_msg("Unsupported length: " << length);
316 : }
317 :
318 : // Result is returned in c
319 : final_mix(a,b,c);
320 : return static_cast<uint16_t>(c);
321 : }
322 :
323 :
324 : /**
325 : * Calls functions above with slightly more convenient
326 : * std::vector/array compatible interface.
327 : */
328 : template <typename Container>
329 : inline
330 2840282 : typename Container::value_type hashword(const Container & keys)
331 : {
332 6805025 : return hashword(keys.data(), keys.size());
333 : }
334 :
335 :
336 :
337 : } // end Utility namespace
338 : } // end libMesh namespace
339 :
340 : #endif // LIBMESH_HASHWORD_H
|
