1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2020 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
rot(uint32_t x,uint32_t k)47 uint32_t rot(uint32_t x, uint32_t k)
48 {
49 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
mix(uint32_t & a,uint32_t & b,uint32_t & c)63 void mix(uint32_t & a, uint32_t & b, uint32_t & c)
64 {
65 a -= c; a ^= rot(c, 4); c += b;
66 b -= a; b ^= rot(a, 6); a += c;
67 c -= b; c ^= rot(b, 8); b += a;
68 a -= c; a ^= rot(c,16); c += b;
69 b -= a; b ^= rot(a,19); a += c;
70 c -= b; c ^= rot(b, 4); b += a;
71 }
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
final(uint32_t & a,uint32_t & b,uint32_t & c)83 void final(uint32_t & a, uint32_t & b, uint32_t & c)
84 {
85 c ^= b; c -= rot(b,14);
86 a ^= c; a -= rot(c,11);
87 b ^= a; b -= rot(a,25);
88 c ^= b; c -= rot(b,16);
89 a ^= c; a -= rot(c,4);
90 b ^= a; b -= rot(a,14);
91 c ^= b; c -= rot(b,24);
92 }
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 */
fnv_64_buf(const void * buf,size_t len)109 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 uint64_t hval = static_cast<uint64_t>(0xcbf29ce484222325ULL);
113
114 // start of buffer
115 const unsigned char * bp = static_cast<const unsigned char *>(buf);
116
117 // beyond end of buffer
118 const unsigned char * be = bp + len;
119
120 // FNV-1 hash each octet of the buffer
121 while (bp < be)
122 {
123 hval +=
124 (hval << 1) + (hval << 4) + (hval << 5) +
125 (hval << 7) + (hval << 8) + (hval << 40);
126
127 // xor the bottom with the current octet
128 hval ^= static_cast<uint64_t>(*bp++);
129 }
130
131 // return our new hash value
132 return hval;
133 }
134
135 } // end anonymous namespace
136
137
138
139 namespace libMesh
140 {
141 namespace Utility
142 {
143 /**
144 * The hashword function takes an array of uint32_t's of length 'length'
145 * and computes a single key from it.
146 *
147 * \author Bob Jenkins
148 * \date May 2006
149 * \copyright Public Domain
150 * http://burtleburtle.net/bob/hash/index.html
151 */
152 inline
153 uint32_t hashword(const uint32_t * k, size_t length, uint32_t initval=0)
154 {
155 uint32_t a,b,c;
156
157 // Set up the internal state
158 a = b = c = 0xdeadbeef + ((static_cast<uint32_t>(length))<<2) + initval;
159
160 //------------------------------------------------- handle most of the key
161 while (length > 3)
162 {
163 a += k[0];
164 b += k[1];
165 c += k[2];
166 mix(a,b,c);
167 length -= 3;
168 k += 3;
169 }
170
171 //------------------------------------------- handle the last 3 uint32_t's
172 switch(length) // all the case statements fall through
173 {
174 case 3 : c+=k[2];
175 libmesh_fallthrough();
176 case 2 : b+=k[1];
177 libmesh_fallthrough();
178 case 1 : a+=k[0];
179 final(a,b,c);
180 libmesh_fallthrough();
181 default: // case 0: nothing left to add
182 break;
183 }
184
185 //------------------------------------------------------ report the result
186 return c;
187 }
188
189
190
191 /**
192 * Calls function above with slightly more convenient std::vector interface.
193 */
194 inline
195 uint32_t hashword(const std::vector<uint32_t> & keys, uint32_t initval=0)
196 {
197 return hashword(keys.data(), keys.size(), initval);
198 }
199
200
201 /**
202 * This is a hard-coded version of hashword for hashing exactly 2 numbers.
203 *
204 * \author Bob Jenkins
205 * \date May 2006
206 * \copyright Public Domain
207 * http://burtleburtle.net/bob/hash/index.html
208 */
209 inline
210 uint32_t hashword2(const uint32_t & first, const uint32_t & second, uint32_t initval=0)
211 {
212 uint32_t a,b,c;
213
214 // Set up the internal state
215 a = b = c = 0xdeadbeef + 8 + initval;
216
217 b+=second;
218 a+=first;
219 final(a,b,c);
220
221 return c;
222 }
223
224 /**
225 * Call the 64-bit FNV hash function.
226 */
227 inline
hashword2(const uint64_t first,const uint64_t second)228 uint64_t hashword2(const uint64_t first, const uint64_t second)
229 {
230 // This isn't optimal (it would be nice to avoid this packing step)
231 // but we are going to go ahead and conform to the 32-bit
232 // hashword2() interface.
233 uint64_t k[2] = {first, second};
234
235 // len is the total number of bytes in two 64-bit ints
236 return fnv_64_buf(k, /*len=*/8*2);
237 }
238
239 inline
hashword2(const uint16_t first,const uint16_t second)240 uint16_t hashword2(const uint16_t first, const uint16_t second)
241 {
242 return static_cast<uint16_t>(first%65449 + (second<<5)%65449);
243 }
244
245 /**
246 * Call the 64-bit FNV hash function.
247 */
248 inline
hashword(const uint64_t * k,size_t length)249 uint64_t hashword(const uint64_t * k, size_t length)
250 {
251 return fnv_64_buf(k, 8*length);
252 }
253
254
255
256 /**
257 * In a personal communication from Bob Jenkins, he recommended using
258 * "Probably final() from lookup3.c... You could hash up to 6 16-bit
259 * integers that way. The output is c, or the top or bottom 16 bits
260 * of c if you only need 16 bit hash values." [JWP]
261 */
262 inline
hashword(const uint16_t * k,size_t length)263 uint16_t hashword(const uint16_t * k, size_t length)
264 {
265 // Three values that will be passed to final() after they are initialized.
266 uint32_t a = 0;
267 uint32_t b = 0;
268 uint32_t c = 0;
269
270 switch (length)
271 {
272 case 3:
273 {
274 // Cast the inputs to 32 bit integers and call final().
275 a = k[0];
276 b = k[1];
277 c = k[2];
278 break;
279 }
280 case 4:
281 {
282 // Combine the 4 16-bit inputs, "w, x, y, z" into two 32-bit
283 // inputs "wx" and "yz" using bit operations and call final.
284 a = ((k[0]<<16) | (k[1] & 0xffff)); // wx
285 b = ((k[2]<<16) | (k[3] & 0xffff)); // yz
286 break;
287 }
288 default:
289 libmesh_error_msg("Unsupported length: " << length);
290 }
291
292 // Result is returned in c
293 final(a,b,c);
294 return static_cast<uint16_t>(c);
295 }
296
297
298 /**
299 * Calls functions above with slightly more convenient
300 * std::vector/array compatible interface.
301 */
302 template <typename Container>
303 inline
hashword(const Container & keys)304 typename Container::value_type hashword(const Container & keys)
305 {
306 return hashword(keys.data(), keys.size());
307 }
308
309
310
311 } // end Utility namespace
312 } // end libMesh namespace
313
314 #endif // LIBMESH_HASHWORD_H
315