A Discrete-Event Network Simulator
API
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Groups Pages
hash-murmur3.cc
Go to the documentation of this file.
1 /* -*- Mode:C++; c-file-style:"gnu"; indent-tabs-mode:nil; -*- */
2 /*
3  * Copyright (c) 2012 Lawrence Livermore National Laboratory
4  *
5  * This program is free software; you can redistribute it and/or modify
6  * it under the terms of the GNU General Public License version 2 as
7  * published by the Free Software Foundation;
8  *
9  * This program 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
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software
16  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
17  *
18  * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov>
19  *
20  * This copyright notice applies strictly to the wrapper material.
21  *
22  * The murmur3 source code itself is in the public domain. The murmur3 source
23  * code sections are marked by
24  * // Begin <murmur3-file> ---->
25  * and
26  * // End <murmur3-file> ---->
27  * comments.
28  *
29  * Changes from the murmur3 distribution are marked with `//PDB'
30  */
31 
32 #include "log.h"
33 #include "hash-murmur3.h"
34 
35 #include <iomanip>
36 
37 /*
38  * \brief Silence erroneous strict alias warning from a gcc 4.4 bug
39  *
40  * Casting \c (void*) triggers a strict alias warning bug
41  * in gcc 4.4 (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39390).
42  *
43  * In the murmur3 code, data is returned by
44  * \code
45  * void Function (... , void * out)
46  * {
47  * ...
48  * *(uint32_t *)out = ...
49  * }
50  * \endcode
51  *
52  * which triggers the erroneous warning.
53  *
54  * We suppress strict-alias warnings in this compilation unit.
55  * (gcc 4.4 doesn't support the <tt>diagnostic push/pop</tt> pragmas,
56  * so we can't narrow down the suppression any further.)
57  */
58 // Test for gcc 4.4.x
59 #define GCC_VERSION (__GNUC__ * 100 + __GNUC_MINOR__)
60 #if (GCC_VERSION == 404)
61 # pragma GCC diagnostic ignored "-Wstrict-aliasing"
62 #endif
63 
64 namespace ns3 {
65 
66 NS_LOG_COMPONENT_DEFINE ("Hash-Murmur3");
67 
68 namespace Hash {
69 
70 namespace Function {
71 
72 namespace Murmur3Implementation {
73 
74 // Changes from Murmur3 distribution are marked with `//PDB'
75 //
76 
77 /*************************************************
78  ** class Murmur3HashImplementation
79  ************************************************/
80 
81 // Adapted from http://code.google.com/p/smhasher/
82 
83 // Begin Murmur3.cpp ----------------------------->
84 
85 //
86 //-----------------------------------------------------------------------------
87 // MurmurHash3 was written by Austin Appleby, and is placed in the public
88 // domain. The author hereby disclaims copyright to this source code.
89 
90 // Note - The x86 and x64 versions do _not_ produce the same results, as the
91 // algorithms are optimized for their respective platforms. You can still
92 // compile and run any of them on any platform, but your performance with the
93 // non-native version will be less than optimal.
94 
95 
96 inline uint32_t rotl32 ( uint32_t x, int8_t r )
97 {
98  return (x << r) | (x >> (32 - r));
99 }
100 
101 inline uint64_t rotl64 ( uint64_t x, int8_t r )
102 {
103  return (x << r) | (x >> (64 - r));
104 }
105 
106 #define BIG_CONSTANT(x) (x##LLU)
107 
108 //-----------------------------------------------------------------------------
109 // Block read - if your platform needs to do endian-swapping or can only
110 // handle aligned reads, do the conversion here
111 
112 inline uint32_t getblock ( const uint32_t * p, int i )
113 {
114  return p[i];
115 }
116 
117 inline uint64_t getblock ( const uint64_t * p, int i )
118 {
119  return p[i];
120 }
121 
122 //-----------------------------------------------------------------------------
123 // Finalization mix - force all bits of a hash block to avalanche
124 
125 inline uint32_t fmix ( uint32_t h )
126 {
127  h ^= h >> 16;
128  h *= 0x85ebca6b;
129  h ^= h >> 13;
130  h *= 0xc2b2ae35;
131  h ^= h >> 16;
132 
133  return h;
134 }
135 
136 //----------
137 
138 inline uint64_t fmix ( uint64_t k )
139 {
140  k ^= k >> 33;
141  k *= BIG_CONSTANT(0xff51afd7ed558ccd);
142  k ^= k >> 33;
143  k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
144  k ^= k >> 33;
145 
146  return k;
147 }
148 
149 //-----------------------------------------------------------------------------
150 
151 //PDB forward
152 void MurmurHash3_x86_32_incr ( const void * key, int len,
153  uint32_t seed, void * out );
154 void MurmurHash3_x86_32_fin ( int len,
155  uint32_t seed, void * out );
156 
157 //PDB - incremental hashing
158 void MurmurHash3_x86_32 ( const void * key, int len,
159  uint32_t seed, void * out )
160 {
161  uint32_t h1;
162  MurmurHash3_x86_32_incr (key, len, seed, &h1);
163  MurmurHash3_x86_32_fin (len, h1, out);
164 }
165 
166 void MurmurHash3_x86_32_incr ( const void * key, int len,
167  uint32_t seed, void * out )
168 {
169  const uint8_t * data = (const uint8_t*)key;
170  const int nblocks = len / 4;
171 
172  uint32_t h1 = seed;
173 
174  uint32_t c1 = 0xcc9e2d51;
175  uint32_t c2 = 0x1b873593;
176 
177  //----------
178  // body
179 
180  const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
181 
182  for(int i = -nblocks; i; i++)
183  {
184  uint32_t k1 = getblock(blocks,i);
185 
186  k1 *= c1;
187  k1 = rotl32(k1,15);
188  k1 *= c2;
189 
190  h1 ^= k1;
191  h1 = rotl32(h1,13);
192  h1 = h1*5+0xe6546b64;
193  }
194 
195  //----------
196  // tail
197 
198  const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
199 
200  uint32_t k1 = 0;
201 
202  switch(len & 3)
203  {
204  case 3: k1 ^= tail[2] << 16;
205  case 2: k1 ^= tail[1] << 8;
206  case 1: k1 ^= tail[0];
207  k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
208  };
209 
210  *(uint32_t *)out = h1;
211 }
212 
213 //PDB - incremental hashing - finalization
214 void MurmurHash3_x86_32_fin ( int len,
215  uint32_t seed, void * out )
216 {
217  uint32_t h1 = seed;
218 
219  //----------
220  // finalization
221 
222  h1 ^= len;
223 
224  h1 = fmix(h1);
225 
226  *(uint32_t *)out = h1;
227 }
228 
229 //-----------------------------------------------------------------------------
230 
231 //PDB forward
232 void MurmurHash3_x86_128_incr ( const void * key, const int len,
233  uint32_t * seeds, void * out );
234 void MurmurHash3_x86_128_fin ( const int len,
235  uint32_t * seeds, void * out );
236 
237 //PDB - incremental hashing
238 void MurmurHash3_x86_128 ( const void * key, const int len,
239  uint32_t seed, void * out )
240 {
241  uint32_t seeds[4];
242  uint32_t h[4];
243  seeds[0] = seeds[1] = seeds[2] = seeds[3] = seed;
244  MurmurHash3_x86_128_incr (key, len, seeds, h);
245  MurmurHash3_x86_128_fin (len, h, out);
246 }
247 
248 void MurmurHash3_x86_128_incr ( const void * key, const int len,
249  uint32_t * seeds, void * out )
250 {
251  const uint8_t * data = (const uint8_t*)key;
252  const int nblocks = len / 16;
253 
254  uint32_t h1 = seeds[0];
255  uint32_t h2 = seeds[1];
256  uint32_t h3 = seeds[2];
257  uint32_t h4 = seeds[3];
258 
259  uint32_t c1 = 0x239b961b;
260  uint32_t c2 = 0xab0e9789;
261  uint32_t c3 = 0x38b34ae5;
262  uint32_t c4 = 0xa1e38b93;
263 
264  //----------
265  // body
266 
267  const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
268 
269  for(int i = -nblocks; i; i++)
270  {
271  uint32_t k1 = getblock(blocks,i*4+0);
272  uint32_t k2 = getblock(blocks,i*4+1);
273  uint32_t k3 = getblock(blocks,i*4+2);
274  uint32_t k4 = getblock(blocks,i*4+3);
275 
276  k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
277 
278  h1 = rotl32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
279 
280  k2 *= c2; k2 = rotl32(k2,16); k2 *= c3; h2 ^= k2;
281 
282  h2 = rotl32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
283 
284  k3 *= c3; k3 = rotl32(k3,17); k3 *= c4; h3 ^= k3;
285 
286  h3 = rotl32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
287 
288  k4 *= c4; k4 = rotl32(k4,18); k4 *= c1; h4 ^= k4;
289 
290  h4 = rotl32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
291  }
292 
293  //----------
294  // tail
295 
296  const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
297 
298  uint32_t k1 = 0;
299  uint32_t k2 = 0;
300  uint32_t k3 = 0;
301  uint32_t k4 = 0;
302 
303  switch(len & 15)
304  {
305  case 15: k4 ^= tail[14] << 16;
306  case 14: k4 ^= tail[13] << 8;
307  case 13: k4 ^= tail[12] << 0;
308  k4 *= c4; k4 = rotl32(k4,18); k4 *= c1; h4 ^= k4;
309 
310  case 12: k3 ^= tail[11] << 24;
311  case 11: k3 ^= tail[10] << 16;
312  case 10: k3 ^= tail[ 9] << 8;
313  case 9: k3 ^= tail[ 8] << 0;
314  k3 *= c3; k3 = rotl32(k3,17); k3 *= c4; h3 ^= k3;
315 
316  case 8: k2 ^= tail[ 7] << 24;
317  case 7: k2 ^= tail[ 6] << 16;
318  case 6: k2 ^= tail[ 5] << 8;
319  case 5: k2 ^= tail[ 4] << 0;
320  k2 *= c2; k2 = rotl32(k2,16); k2 *= c3; h2 ^= k2;
321 
322  case 4: k1 ^= tail[ 3] << 24;
323  case 3: k1 ^= tail[ 2] << 16;
324  case 2: k1 ^= tail[ 1] << 8;
325  case 1: k1 ^= tail[ 0] << 0;
326  k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
327  };
328 
329  ((uint32_t *)out)[0] = h1;
330  ((uint32_t *)out)[1] = h2;
331  ((uint32_t *)out)[2] = h3;
332  ((uint32_t *)out)[3] = h4;
333 }
334 
335 //PDB - incremental hashing - finalization
336 void MurmurHash3_x86_128_fin ( const int len,
337  uint32_t * seeds, void * out )
338 {
339  //----------
340  // finalization
341 
342  uint32_t h1 = seeds[0];
343  uint32_t h2 = seeds[1];
344  uint32_t h3 = seeds[2];
345  uint32_t h4 = seeds[3];
346 
347  h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
348 
349  h1 += h2; h1 += h3; h1 += h4;
350  h2 += h1; h3 += h1; h4 += h1;
351 
352  h1 = fmix(h1);
353  h2 = fmix(h2);
354  h3 = fmix(h3);
355  h4 = fmix(h4);
356 
357  h1 += h2; h1 += h3; h1 += h4;
358  h2 += h1; h3 += h1; h4 += h1;
359 
360  ((uint32_t *)out)[0] = h1;
361  ((uint32_t *)out)[1] = h2;
362  ((uint32_t *)out)[2] = h3;
363  ((uint32_t *)out)[3] = h4;
364 }
365 
366 //-----------------------------------------------------------------------------
367 
368 void MurmurHash3_x64_128 ( const void * key, const int len,
369  const uint32_t seed, void * out )
370 {
371  const uint8_t * data = (const uint8_t*)key;
372  const int nblocks = len / 16;
373 
374  uint64_t h1 = seed;
375  uint64_t h2 = seed;
376 
377  uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
378  uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
379 
380  //----------
381  // body
382 
383  const uint64_t * blocks = (const uint64_t *)(data);
384 
385  for(int i = 0; i < nblocks; i++)
386  {
387  uint64_t k1 = getblock(blocks,i*2+0);
388  uint64_t k2 = getblock(blocks,i*2+1);
389 
390  k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1;
391 
392  h1 = rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
393 
394  k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2;
395 
396  h2 = rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
397  }
398 
399  //----------
400  // tail
401 
402  const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
403 
404  uint64_t k1 = 0;
405  uint64_t k2 = 0;
406 
407  switch(len & 15)
408  {
409  case 15: k2 ^= uint64_t(tail[14]) << 48;
410  case 14: k2 ^= uint64_t(tail[13]) << 40;
411  case 13: k2 ^= uint64_t(tail[12]) << 32;
412  case 12: k2 ^= uint64_t(tail[11]) << 24;
413  case 11: k2 ^= uint64_t(tail[10]) << 16;
414  case 10: k2 ^= uint64_t(tail[ 9]) << 8;
415  case 9: k2 ^= uint64_t(tail[ 8]) << 0;
416  k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2;
417 
418  case 8: k1 ^= uint64_t(tail[ 7]) << 56;
419  case 7: k1 ^= uint64_t(tail[ 6]) << 48;
420  case 6: k1 ^= uint64_t(tail[ 5]) << 40;
421  case 5: k1 ^= uint64_t(tail[ 4]) << 32;
422  case 4: k1 ^= uint64_t(tail[ 3]) << 24;
423  case 3: k1 ^= uint64_t(tail[ 2]) << 16;
424  case 2: k1 ^= uint64_t(tail[ 1]) << 8;
425  case 1: k1 ^= uint64_t(tail[ 0]) << 0;
426  k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1;
427  };
428 
429  //----------
430  // finalization
431 
432  h1 ^= len; h2 ^= len;
433 
434  h1 += h2;
435  h2 += h1;
436 
437  h1 = fmix(h1);
438  h2 = fmix(h2);
439 
440  h1 += h2;
441  h2 += h1;
442 
443  ((uint32_t *)out)[0] = h1;
444  ((uint32_t *)out)[1] = h2;
445 }
446 
447 
448 // End Murmur3.cpp ----------------------------->
449 
450 #undef BIG_CONSTANT
451 
452 
453 //-----------------------------------------------------------------------------
454 
455 
456 } // namespace Murmur3Implementation
457 
458 
460 {
461  clear ();
462 }
463 
464 uint32_t
465 Murmur3::GetHash32 (const char * buffer, const size_t size)
466 {
467  using namespace Murmur3Implementation;
468 
469  MurmurHash3_x86_32_incr (buffer, size, m_hash32, (void *) & m_hash32);
470  m_size32 += size;
471  uint32_t hash;
472  MurmurHash3_x86_32_fin (m_size32, m_hash32, (void *) & hash);
473 
474  return hash;
475 }
476 
477 uint64_t
478 Murmur3::GetHash64 (const char * buffer, const size_t size)
479 {
480  using namespace Murmur3Implementation;
481  MurmurHash3_x86_128_incr (buffer, size,
482  (uint32_t *)(void *)m_hash64, (void *)(m_hash64));
483  m_size64 += size;
484  uint64_t hash[2];
486  (uint32_t*)(void *)m_hash64, (void *)hash);
487  return hash[0];
488 }
489 
490 void
492 {
493  m_hash32 = (uint32_t)SEED;
494  m_size32 = 0;
495  m_hash64[0] = ((uint64_t)(SEED) << 32) + (uint64_t)SEED;
496  m_hash64[1] = ((uint64_t)(SEED) << 32) + (uint64_t)SEED;
497  m_size64 = 0;
498 }
499 
500 } // namespace Function
501 
502 } // namespace Hash
503 
504 } // namespace ns3