hashword.h
Go to the documentation of this file.
1 // The libMesh Finite Element Library.
2 // Copyright (C) 2002-2014 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 // All functions in this file by Bob Jenkins, May 2006, Public Domain.
22 
23 #include <stdint.h> // uint32_t
24 
25 // ::size_t is defined in the backward compatibility header stddef.h.
26 // It's been part of ANSI/ISO C and ISO C++ since their very
27 // beginning. Every C++ implementation has to ship with stddef.h
28 // (compatibility) and cstddef where only the latter defines
29 // std::size_t and not necessarily ::size_t. See Annex D of the C++
30 // Standard.
31 //
32 // http://stackoverflow.com/questions/237370/does-stdsize-t-make-sense-in-c
33 #include <stddef.h>
34 
35 
36 // Anonymous namespace for utility functions used locally
37 namespace
38 {
39  // Rotate x by k bits
40  // @author Bob Jenkins, May 2006, Public Domain.
41  // http://burtleburtle.net/bob/hash/index.html
42  inline
43  uint32_t rot(uint32_t x, uint32_t k)
44  {
45  return (x<<k) | (x>>(32-k));
46  }
47 
48 
49 
50  // mix 3 32-bit values reversibly
51  // @author Bob Jenkins, May 2006, Public Domain.
52  // http://burtleburtle.net/bob/hash/index.html
53  inline
54  void mix(uint32_t& a, uint32_t& b, uint32_t& c)
55  {
56  a -= c; a ^= rot(c, 4); c += b;
57  b -= a; b ^= rot(a, 6); a += c;
58  c -= b; c ^= rot(b, 8); b += a;
59  a -= c; a ^= rot(c,16); c += b;
60  b -= a; b ^= rot(a,19); a += c;
61  c -= b; c ^= rot(b, 4); b += a;
62  }
63 
64 
65  // 'final' mixing of 3 32-bit numbers, result is stored in c.
66  // @author Bob Jenkins, May 2006, Public Domain.
67  // http://burtleburtle.net/bob/hash/index.html
68  inline
69  void final(uint32_t& a, uint32_t& b, uint32_t& c)
70  {
71  c ^= b; c -= rot(b,14);
72  a ^= c; a -= rot(c,11);
73  b ^= a; b -= rot(a,25);
74  c ^= b; c -= rot(b,16);
75  a ^= c; a -= rot(c,4);
76  b ^= a; b -= rot(a,14);
77  c ^= b; c -= rot(b,24);
78  }
79 } // end anonymous namespace
80 
81 
82 
83 namespace libMesh
84 {
85  namespace Utility
86  {
87  // The hashword function takes an array of uint32_t's of length 'length'
88  // and computes a single key from it.
89  // @author Bob Jenkins, May 2006, Public Domain.
90  // http://burtleburtle.net/bob/hash/index.html
91  inline
92  uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval=0)
93  {
94  uint32_t a,b,c;
95 
96  // Set up the internal state
97  a = b = c = 0xdeadbeef + ((static_cast<uint32_t>(length))<<2) + initval;
98 
99  //------------------------------------------------- handle most of the key
100  while (length > 3)
101  {
102  a += k[0];
103  b += k[1];
104  c += k[2];
105  mix(a,b,c);
106  length -= 3;
107  k += 3;
108  }
109 
110  //------------------------------------------- handle the last 3 uint32_t's
111  switch(length) // all the case statements fall through
112  {
113  case 3 : c+=k[2];
114  case 2 : b+=k[1];
115  case 1 : a+=k[0];
116  final(a,b,c);
117  default: // case 0: nothing left to add
118  break;
119  }
120 
121  //------------------------------------------------------ report the result
122  return c;
123  }
124 
125 
126  // This is a hard-coded version of hashword for hashing exactly 2 numbers
127  // @author Bob Jenkins, May 2006, Public Domain.
128  // http://burtleburtle.net/bob/hash/index.html
129  inline
130  uint32_t hashword2(const uint32_t& first, const uint32_t& second, uint32_t initval=0)
131  {
132  uint32_t a,b,c;
133 
134  // Set up the internal state
135  a = b = c = 0xdeadbeef + 8 + initval;
136 
137  b+=second;
138  a+=first;
139  final(a,b,c);
140 
141  return c;
142  }
143 
144  // Homegrown implementations if we don't have 32-bit unsigned ints
145  inline
146  uint64_t hashword2(const uint64_t first, const uint64_t second)
147  {
148  // big prime number
149  const unsigned int bp = 65449;
150 
151  return (first%bp + (second<<5)%bp);
152  }
153 
154  inline
155  uint16_t hashword2(const uint16_t first, const uint16_t second)
156  {
157  // "big" prime number
158  const uint16_t bp = 257;
159 
160  return static_cast<uint16_t>(first%bp + (second<<3)%bp);
161  }
162 
163  // Another homegrown implementation for 64-bit unsigned ints
164  inline
165  uint64_t hashword(const uint64_t *k, size_t length)
166  {
167  // big prime number
168  const unsigned int bp = 65449;
169 
170  uint64_t c = 0;
171  unsigned int shift=0;
172  for (size_t i=0; i != length; ++i)
173  {
174  c += (k[i] << shift) % bp;
175  shift += 5;
176  }
177 
178  return c;
179  }
180 
181  // Another homegrown implementation for 16-bit unsigned ints
182  inline
183  uint16_t hashword(const uint16_t *k, size_t length)
184  {
185  // "big" prime number
186  const uint16_t bp = 257;
187 
188  uint16_t c = 0;
189  uint16_t shift=0;
190  for (size_t i=0; i != length; ++i)
191  {
192  c = static_cast<uint16_t>
193  (c + static_cast<uint16_t>(k[i] << shift) % bp);
194  shift = static_cast<uint16_t>(shift+3);
195  }
196 
197  return c;
198  }
199 
200  } // end Utility namespace
201 } // end libMesh namespace
202 
203 #endif // LIBMESH_HASHWORD_H

Site Created By: libMesh Developers
Last modified: February 07 2014 16:57:05 UTC

Hosted By:
SourceForge.net Logo