libMesh
hashword.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2017 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(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  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 {
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 
194 inline
195 uint32_t hashword(const std::vector<uint32_t> & keys, uint32_t initval=0)
196 {
197  return hashword(&keys[0], keys.size(), initval);
198 }
199 
200 
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 
227 inline
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
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 
248 inline
249 uint64_t hashword(const uint64_t * k, size_t length)
250 {
251  return fnv_64_buf(k, 8*length);
252 }
253 
254 
255 
259 inline
260 uint64_t hashword(const std::vector<uint64_t> & keys)
261 {
262  return hashword(&keys[0], keys.size());
263 }
264 
271 inline
272 uint16_t hashword(const uint16_t * k, size_t length)
273 {
274  // Three values that will be passed to final() after they are initialized.
275  uint32_t a = 0;
276  uint32_t b = 0;
277  uint32_t c = 0;
278 
279  switch (length)
280  {
281  case 3:
282  {
283  // Cast the inputs to 32 bit integers and call final().
284  a = k[0];
285  b = k[1];
286  c = k[2];
287  break;
288  }
289  case 4:
290  {
291  // Combine the 4 16-bit inputs, "w, x, y, z" into two 32-bit
292  // inputs "wx" and "yz" using bit operations and call final.
293  a = ((k[0]<<16) | (k[1] & 0xffff)); // wx
294  b = ((k[2]<<16) | (k[3] & 0xffff)); // yz
295  break;
296  }
297  default:
298  libmesh_error_msg("Unsupported length: " << length);
299  }
300 
301  // Result is returned in c
302  final(a,b,c);
303  return static_cast<uint16_t>(c);
304 }
305 
306 
310 inline
311 uint16_t hashword(const std::vector<uint16_t> & keys)
312 {
313  return hashword(&keys[0], keys.size());
314 }
315 
316 
317 
318 } // end Utility namespace
319 } // end libMesh namespace
320 
321 #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:153
PetscErrorCode Vec x
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:210