libMesh
hashword.h
Go to the documentation of this file.
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 {
46 inline
47 uint32_t rot(uint32_t x, uint32_t k)
48 {
49  return (x<<k) | (x>>(32-k));
50 }
51 
52 
53 
62 inline
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 
82 inline
83 void final_mix(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 
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  // 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  hval +=
129  (hval << 1) + (hval << 4) + (hval << 5) +
130  (hval << 7) + (hval << 8) + (hval << 40);
131 
132  // xor the bottom with the current octet
133  hval ^= static_cast<uint64_t>(*bp++);
134  }
135 
136  // return our new hash value
137  return hval;
138 }
139 
140 } // end anonymous namespace
141 
142 
143 
144 namespace libMesh
145 {
146 namespace Utility
147 {
157 inline
158 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  a = b = c = 0xdeadbeef + ((static_cast<uint32_t>(length))<<2) + initval;
164 
165  //------------------------------------------------- handle most of the key
166  while (length > 3)
167  {
168  a += k[0];
169  b += k[1];
170  c += k[2];
171  mix(a,b,c);
172  length -= 3;
173  k += 3;
174  }
175 
176  //------------------------------------------- handle the last 3 uint32_t's
177  switch(length) // all the case statements fall through
178  {
179  case 3 : c+=k[2];
180  libmesh_fallthrough();
181  case 2 : b+=k[1];
182  libmesh_fallthrough();
183  case 1 : a+=k[0];
184  final_mix(a,b,c);
185  libmesh_fallthrough();
186  default: // case 0: nothing left to add
187  break;
188  }
189 
190  //------------------------------------------------------ report the result
191  return c;
192 }
193 
194 
195 
199 inline
200 uint32_t hashword(const std::vector<uint32_t> & keys, uint32_t initval=0)
201 {
202  return hashword(keys.data(), keys.size(), initval);
203 }
204 
205 
214 inline
215 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  a = b = c = 0xdeadbeef + 8 + initval;
221 
222  b+=second;
223  a+=first;
224  final_mix(a,b,c);
225 
226  return c;
227 }
228 
237 inline
238 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  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  auto beg = reinterpret_cast<const unsigned char *>(i==0 ? &first : &second);
248  auto end = beg + sizeof(uint64_t)/sizeof(unsigned char); // beg+8
249 
250  // FNV-1 hash each octet of the buffer
251  while (beg < end)
252  {
253  hval +=
254  (hval << 1) + (hval << 4) + (hval << 5) +
255  (hval << 7) + (hval << 8) + (hval << 40);
256 
257  // xor the bottom with the current octet
258  hval ^= static_cast<uint64_t>(*beg++);
259  }
260  }
261 
262  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 
274 inline
275 uint64_t hashword(const uint64_t * k, size_t length)
276 {
277  return fnv_64_buf(k, 8*length);
278 }
279 
280 
281 
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 
328 template <typename Container>
329 inline
330 typename Container::value_type hashword(const Container & keys)
331 {
332  return hashword(keys.data(), keys.size());
333 }
334 
335 
336 
337 } // end Utility namespace
338 } // end libMesh namespace
339 
340 #endif // LIBMESH_HASHWORD_H
The libMesh namespace provides an interface to certain functionality in the library.
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval=0)
The hashword function takes an array of uint32_t&#39;s of length &#39;length&#39; and computes a single key from ...
Definition: hashword.h:158
uint32_t hashword2(const uint32_t &first, const uint32_t &second, uint32_t initval=0)
This is a hard-coded version of hashword for hashing exactly 2 numbers.
Definition: hashword.h:215