hashword.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2018 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.data(), 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 
262 inline
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 
302 template <typename Container>
303 inline
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
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval=0)
Definition: hashword.h:153
uint32_t hashword2(const uint32_t &first, const uint32_t &second, uint32_t initval=0)
Definition: hashword.h:210