A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
hash-murmur3.cc
Go to the documentation of this file.
1/*
2 * Copyright (c) 2012 Lawrence Livermore National Laboratory
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Peter D. Barnes, Jr. <pdbarnes@llnl.gov>
7 *
8 * This copyright notice applies strictly to the wrapper material.
9 *
10 * The murmur3 source code itself is in the public domain. The murmur3 source
11 * code sections are marked by
12 * // Begin <murmur3-file> ---->
13 * and
14 * // End <murmur3-file> ---->
15 * comments.
16 *
17 * Changes from the murmur3 distribution are marked with `//PDB'
18 * In addition comment blocks have been converted to Doxygen format.
19 * Function arguments for buffer length which were originally
20 * "int len" or "int i" have been changed to "std::size_t".
21 * In the _x86 versions the main loop used negative indexes, as shown.
22 * Other conversions to std::size_t are marked.
23 */
24
25#include "hash-murmur3.h"
26
27#include "log.h"
28
29#include <iomanip>
30
31/**
32 * \file
33 * \ingroup hash
34 * \brief ns3::Hash::Function::Murmur3 implementation.
35 */
36
37namespace ns3
38{
39
40NS_LOG_COMPONENT_DEFINE("Hash-Murmur3");
41
42namespace Hash
43{
44
45namespace Function
46{
47
48/** Murmur3 hash implementation details. */
49namespace Murmur3Implementation
50{
51
52/**
53 * \ingroup hash
54 * \defgroup hash_murmur3 Murmur3 Hash Implementation
55 */
56/**@{*/
57
58// Changes from Murmur3 distribution are marked with `//PDB'
59//
60
61/*************************************************
62 ** class Murmur3HashImplementation
63 ************************************************/
64
65// Adapted from http://code.google.com/p/smhasher/
66
67// NOLINTBEGIN
68// clang-format off
69
70//
71//-----------------------------------------------------------------------------
72// MurmurHash3 was written by Austin Appleby, and is placed in the public
73// domain. The author hereby disclaims copyright to this source code.
74
75// Note - The x86 and x64 versions do _not_ produce the same results, as the
76// algorithms are optimized for their respective platforms. You can still
77// compile and run any of them on any platform, but your performance with the
78// non-native version will be less than optimal.
79
80
81/**
82 * Barrel shift (rotate) left on 32 bits.
83 *
84 * \param [in] x The initial value.
85 * \param [in] r The number of bit positions to rotate.
86 * \return The rotated value.
87 */
89{
90 return (x << r) | (x >> (32 - r));
91}
92
93/**
94 * Barrel shift (rotate) left on 64 bits.
95 *
96 * \param [in] x The initial value.
97 * \param [in] r The number of bit positions to rotate.
98 * \return The rotated value.
99 */
100inline uint64_t rotl64 ( uint64_t x, int8_t r )
101{
102 return (x << r) | (x >> (64 - r));
103}
104
105/** Unsigned long long constants. */
106#define BIG_CONSTANT(x) (x##LLU)
107
108//-----------------------------------------------------------------------------
109/**
110 * Block read
111 *
112 * If your platform needs to do endian-swapping or can only
113 * handle aligned reads, do the conversion here.
114 *
115 * \param [in] p Block base address.
116 * \param [in] i Index into the block.
117 * \returns The \c i'th word from the block.
118 */
119inline uint32_t getblock ( const uint32_t * p, std::size_t i )
120{
121 return p[i];
122}
123/** \copydoc getblock(const uint32_t*,std::size_t) */
124inline uint64_t getblock ( const uint64_t * p, std::size_t i )
125{
126 return p[i];
127}
128
129//-----------------------------------------------------------------------------
130/**
131 * Finalization mix - force all bits of a hash block to avalanche.
132 *
133 * \param [in] h Final word of the hash block.
134 * \returns Fully mixed final word.
135 */
137{
138 h ^= h >> 16;
139 h *= 0x85ebca6b;
140 h ^= h >> 13;
141 h *= 0xc2b2ae35;
142 h ^= h >> 16;
143
144 return h;
145}
146
147//----------
148/** \copydoc fmix(uint32_t) */
149inline uint64_t fmix ( uint64_t h )
150{
151 h ^= h >> 33;
152 h *= BIG_CONSTANT(0xff51afd7ed558ccd);
153 h ^= h >> 33;
154 h *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
155 h ^= h >> 33;
156
157 return h;
158}
159
160//-----------------------------------------------------------------------------
161
162//PDB forward
163/**
164 * Initial and incremental hash.
165 *
166 * \param [in] key Data to be hashed.
167 * \param [in] len Number of words in the \c key.
168 * \param [in] seed Initial or current hash state.
169 * \param [out] out Output hash value.
170 */
171void MurmurHash3_x86_32_incr ( const void * key, std::size_t len,
172 uint32_t seed, void * out );
173/**
174 * Finalize a hash.
175 *
176 * \param [in] len Total number of words that have gone in to the hash.
177 * \param [in] seed Initial or current hash state.
178 * \param [out] out Output hash value.
179 */
180void MurmurHash3_x86_32_fin ( std::size_t len,
181 uint32_t seed, void * out );
182
183//PDB - incremental hashing
184/** \copydoc MurmurHash3_x86_32_incr() */
185void MurmurHash3_x86_32 ( const void * key, std::size_t len,
186 uint32_t seed, void * out )
187{
188 uint32_t h1;
189 MurmurHash3_x86_32_incr (key, len, seed, &h1);
190 MurmurHash3_x86_32_fin (len, h1, out);
191}
192
193void MurmurHash3_x86_32_incr ( const void * key, std::size_t len,
194 uint32_t seed, void * out )
195{
196 const uint8_t * data = (const uint8_t*)key;
197 const std::size_t nblocks = len / 4; //PDB: was const int nblocks
198
199 uint32_t h1 = seed;
200
201 uint32_t c1 = 0xcc9e2d51;
202 uint32_t c2 = 0x1b873593;
203
204 //----------
205 // body
206
207 //PDB: const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
208 const uint32_t * blocks = (const uint32_t *)(data);
209
210 //PDB: for(int i = -nblocks; i; i++)
211 for(std::size_t i = 0; i < nblocks; i++)
212 {
213 uint32_t k1 = getblock(blocks,i);
214
215 k1 *= c1;
216 k1 = rotl32(k1,15);
217 k1 *= c2;
218
219 h1 ^= k1;
220 h1 = rotl32(h1,13);
221 h1 = h1*5+0xe6546b64;
222 }
223
224 //----------
225 // tail
226
227 const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
228
229 uint32_t k1 = 0;
230
231 switch(len & 3)
232 {
233 case 3: k1 ^= tail[2] << 16;
234 case 2: k1 ^= tail[1] << 8;
235 case 1: k1 ^= tail[0];
236 k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
237 };
238
239 *(uint32_t *)out = h1;
240}
241
242//PDB - incremental hashing - finalization
243void MurmurHash3_x86_32_fin ( std::size_t len,
244 uint32_t seed, void * out )
245{
246 uint32_t h1 = seed;
247
248 //----------
249 // finalization
250
251 h1 ^= len;
252
253 h1 = fmix(h1);
254
255 *(uint32_t *)out = h1;
256}
257
258//-----------------------------------------------------------------------------
259
260//PDB forward
261/**
262 * Initial and incremental hash.
263 *
264 * \param [in] key Data to be hashed.
265 * \param [in] len Number of words in the \c key.
266 * \param [in] seeds Initial or current hash state.
267 * \param [out] out Output hash value.
268 */
269void MurmurHash3_x86_128_incr ( const void * key, const std::size_t len,
270 uint32_t * seeds, void * out );
271/**
272 * Finalize a hash.
273 *
274 * \param [in] len Total number of words that have gone in to the hash.
275 * \param [in] seeds Initial or current hash state.
276 * \param [out] out Output hash value.
277 */
278void MurmurHash3_x86_128_fin ( const std::size_t len,
279 uint32_t * seeds, void * out );
280
281//PDB - incremental hashing
282/**
283 * Initial and incremental hash.
284 *
285 * \param [in] key Data to be hashed.
286 * \param [in] len Number of words in the \c key.
287 * \param [in] seed Initial or current hash state.
288 * \param [out] out Output hash value.
289 */
290void MurmurHash3_x86_128 ( const void * key, const std::size_t len,
291 uint32_t seed, void * out )
292{
293 uint32_t seeds[4];
294 uint32_t h[4];
295 seeds[0] = seeds[1] = seeds[2] = seeds[3] = seed;
296 MurmurHash3_x86_128_incr (key, len, seeds, h);
297 MurmurHash3_x86_128_fin (len, h, out);
298}
299
300void MurmurHash3_x86_128_incr ( const void * key, const std::size_t len,
301 uint32_t * seeds, void * out )
302{
303 const uint8_t * data = (const uint8_t*)key;
304 const std::size_t nblocks = len / 16; //PDB: was const int nblocks
305
306 uint32_t h1 = seeds[0];
307 uint32_t h2 = seeds[1];
308 uint32_t h3 = seeds[2];
309 uint32_t h4 = seeds[3];
310
311 uint32_t c1 = 0x239b961b;
312 uint32_t c2 = 0xab0e9789;
313 uint32_t c3 = 0x38b34ae5;
314 uint32_t c4 = 0xa1e38b93;
315
316 //----------
317 // body
318
319 //PDB: const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
320 const uint32_t * blocks = (const uint32_t *)(data);
321
322 //PDB: for(int i = -nblocks; i; i++)
323 for(std::size_t i = 0; i < nblocks; i++)
324 {
325 uint32_t k1 = getblock(blocks,i*4+0);
326 uint32_t k2 = getblock(blocks,i*4+1);
327 uint32_t k3 = getblock(blocks,i*4+2);
328 uint32_t k4 = getblock(blocks,i*4+3);
329
330 k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
331
332 h1 = rotl32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
333
334 k2 *= c2; k2 = rotl32(k2,16); k2 *= c3; h2 ^= k2;
335
336 h2 = rotl32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
337
338 k3 *= c3; k3 = rotl32(k3,17); k3 *= c4; h3 ^= k3;
339
340 h3 = rotl32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
341
342 k4 *= c4; k4 = rotl32(k4,18); k4 *= c1; h4 ^= k4;
343
344 h4 = rotl32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
345 }
346
347 //----------
348 // tail
349
350 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
351
352 uint32_t k1 = 0;
353 uint32_t k2 = 0;
354 uint32_t k3 = 0;
355 uint32_t k4 = 0;
356
357 switch(len & 15)
358 {
359 case 15: k4 ^= tail[14] << 16;
360 case 14: k4 ^= tail[13] << 8;
361 case 13: k4 ^= tail[12] << 0;
362 k4 *= c4; k4 = rotl32(k4,18); k4 *= c1; h4 ^= k4;
363
364 case 12: k3 ^= tail[11] << 24;
365 case 11: k3 ^= tail[10] << 16;
366 case 10: k3 ^= tail[ 9] << 8;
367 case 9: k3 ^= tail[ 8] << 0;
368 k3 *= c3; k3 = rotl32(k3,17); k3 *= c4; h3 ^= k3;
369
370 case 8: k2 ^= tail[ 7] << 24;
371 case 7: k2 ^= tail[ 6] << 16;
372 case 6: k2 ^= tail[ 5] << 8;
373 case 5: k2 ^= tail[ 4] << 0;
374 k2 *= c2; k2 = rotl32(k2,16); k2 *= c3; h2 ^= k2;
375
376 case 4: k1 ^= tail[ 3] << 24;
377 case 3: k1 ^= tail[ 2] << 16;
378 case 2: k1 ^= tail[ 1] << 8;
379 case 1: k1 ^= tail[ 0] << 0;
380 k1 *= c1; k1 = rotl32(k1,15); k1 *= c2; h1 ^= k1;
381 };
382
383 ((uint32_t *)out)[0] = h1;
384 ((uint32_t *)out)[1] = h2;
385 ((uint32_t *)out)[2] = h3;
386 ((uint32_t *)out)[3] = h4;
387}
388
389//PDB - incremental hashing - finalization
390void MurmurHash3_x86_128_fin ( const std::size_t len,
391 uint32_t * seeds, void * out )
392{
393 //----------
394 // finalization
395
396 uint32_t h1 = seeds[0];
397 uint32_t h2 = seeds[1];
398 uint32_t h3 = seeds[2];
399 uint32_t h4 = seeds[3];
400
401 h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
402
403 h1 += h2; h1 += h3; h1 += h4;
404 h2 += h1; h3 += h1; h4 += h1;
405
406 h1 = fmix(h1);
407 h2 = fmix(h2);
408 h3 = fmix(h3);
409 h4 = fmix(h4);
410
411 h1 += h2; h1 += h3; h1 += h4;
412 h2 += h1; h3 += h1; h4 += h1;
413
414 ((uint32_t *)out)[0] = h1;
415 ((uint32_t *)out)[1] = h2;
416 ((uint32_t *)out)[2] = h3;
417 ((uint32_t *)out)[3] = h4;
418}
419
420//-----------------------------------------------------------------------------
421/** \copydoc MurmurHash3_x86_32() */
422void MurmurHash3_x64_128 ( const void * key, const std::size_t len,
423 const uint32_t seed, void * out )
424{
425 const uint8_t * data = (const uint8_t*)key;
426 const std::size_t nblocks = len / 16; //PDB: was const int nblocks
427
428 uint64_t h1 = seed;
429 uint64_t h2 = seed;
430
431 uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
432 uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
433
434 //----------
435 // body
436
437 const uint64_t * blocks = (const uint64_t *)(data);
438
439 for(std::size_t i = 0; i < nblocks; i++) //PDB: was int i
440 {
441 uint64_t k1 = getblock(blocks,i*2+0);
442 uint64_t k2 = getblock(blocks,i*2+1);
443
444 k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1;
445
446 h1 = rotl64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
447
448 k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2;
449
450 h2 = rotl64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
451 }
452
453 //----------
454 // tail
455
456 const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
457
458 uint64_t k1 = 0;
459 uint64_t k2 = 0;
460
461 switch(len & 15)
462 {
463 case 15: k2 ^= uint64_t(tail[14]) << 48;
464 case 14: k2 ^= uint64_t(tail[13]) << 40;
465 case 13: k2 ^= uint64_t(tail[12]) << 32;
466 case 12: k2 ^= uint64_t(tail[11]) << 24;
467 case 11: k2 ^= uint64_t(tail[10]) << 16;
468 case 10: k2 ^= uint64_t(tail[ 9]) << 8;
469 case 9: k2 ^= uint64_t(tail[ 8]) << 0;
470 k2 *= c2; k2 = rotl64(k2,33); k2 *= c1; h2 ^= k2;
471
472 case 8: k1 ^= uint64_t(tail[ 7]) << 56;
473 case 7: k1 ^= uint64_t(tail[ 6]) << 48;
474 case 6: k1 ^= uint64_t(tail[ 5]) << 40;
475 case 5: k1 ^= uint64_t(tail[ 4]) << 32;
476 case 4: k1 ^= uint64_t(tail[ 3]) << 24;
477 case 3: k1 ^= uint64_t(tail[ 2]) << 16;
478 case 2: k1 ^= uint64_t(tail[ 1]) << 8;
479 case 1: k1 ^= uint64_t(tail[ 0]) << 0;
480 k1 *= c1; k1 = rotl64(k1,31); k1 *= c2; h1 ^= k1;
481 };
482
483 //----------
484 // finalization
485
486 h1 ^= len; h2 ^= len;
487
488 h1 += h2;
489 h2 += h1;
490
491 h1 = fmix(h1);
492 h2 = fmix(h2);
493
494 h1 += h2;
495 h2 += h1;
496
497 ((uint32_t *)out)[0] = static_cast<uint32_t> (h1); //PDB cast
498 ((uint32_t *)out)[1] = static_cast<uint32_t> (h2); //PDB cast
499}
500
501// clang-format on
502// NOLINTEND
503
504#undef BIG_CONSTANT
505
506//-----------------------------------------------------------------------------
507
508/**@}*/ // \defgroup hash_murmur3
509
510} // namespace Murmur3Implementation
511
513{
514 clear();
515}
516
518Murmur3::GetHash32(const char* buffer, const std::size_t size)
519{
520 using namespace Murmur3Implementation;
521
522 MurmurHash3_x86_32_incr(buffer, size, m_hash32, (void*)&m_hash32);
523 m_size32 += static_cast<uint32_t>(size);
524 uint32_t hash;
525 MurmurHash3_x86_32_fin(m_size32, m_hash32, (void*)&hash);
526
527 return hash;
528}
529
530uint64_t
531Murmur3::GetHash64(const char* buffer, const std::size_t size)
532{
533 using namespace Murmur3Implementation;
534
535 MurmurHash3_x86_128_incr(buffer, static_cast<int>(size), (uint32_t*)(void*)m_hash64, m_hash64);
536 m_size64 += size;
537
538 // Simpler would be:
539 //
540 // uint64_t hash[2];
541 // MurmurHash3_x86_128_fin (m_size64, m_hash64, hash);
542 // return hash[0];
543 //
544 // but this triggers an aliasing bug in gcc-4.4 (perhaps related to
545 // http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39390).
546 // In ns-3, this bug produces incorrect results in static optimized
547 // builds only.
548 //
549 // Using uint32_t here avoids the bug, and continues to works with newer gcc.
550 uint32_t hash[4];
551
552 MurmurHash3_x86_128_fin(static_cast<int>(m_size64), (uint32_t*)(void*)m_hash64, hash);
553 uint64_t result = hash[1];
554 result = (result << 32) | hash[0];
555 return result;
556}
557
558void
560{
562 m_size32 = 0;
563 m_hash64[0] = m_hash64[1] = ((uint64_t)SEED << 32) | (uint32_t)SEED;
564 m_size64 = 0;
565}
566
567} // namespace Function
568
569} // namespace Hash
570
571} // namespace ns3
void clear() override
Restore initial state.
Murmur3()
Constructor, clears internal state.
std::size_t m_size32
Cache last hash value, and total bytes hashed (needed to finalize), for incremental hashing.
uint64_t m_hash64[2]
murmur3 produces 128-bit hash and state; we use just the first 64-bits.
uint32_t GetHash32(const char *buffer, const std::size_t size) override
Compute 32-bit hash of a byte buffer.
uint32_t m_hash32
Cache last hash value, and total bytes hashed (needed to finalize), for incremental hashing.
static constexpr auto SEED
Seed value.
uint64_t GetHash64(const char *buffer, const std::size_t size) override
Compute 64-bit hash of a byte buffer.
std::size_t m_size64
murmur3 produces 128-bit hash and state; we use just the first 64-bits.
void MurmurHash3_x86_128_fin(const std::size_t len, uint32_t *seeds, void *out)
Finalize a hash.
void MurmurHash3_x86_128_incr(const void *key, const std::size_t len, uint32_t *seeds, void *out)
Initial and incremental hash.
uint32_t getblock(const uint32_t *p, std::size_t i)
Block read.
uint64_t rotl64(uint64_t x, int8_t r)
Barrel shift (rotate) left on 64 bits.
uint32_t fmix(uint32_t h)
Finalization mix - force all bits of a hash block to avalanche.
uint32_t rotl32(uint32_t x, int8_t r)
Barrel shift (rotate) left on 32 bits.
void MurmurHash3_x64_128(const void *key, const std::size_t len, const uint32_t seed, void *out)
Initial and incremental hash.
void MurmurHash3_x86_32(const void *key, std::size_t len, uint32_t seed, void *out)
Initial and incremental hash.
void MurmurHash3_x86_128(const void *key, const std::size_t len, uint32_t seed, void *out)
Initial and incremental hash.
void MurmurHash3_x86_32_fin(std::size_t len, uint32_t seed, void *out)
Finalize a hash.
void MurmurHash3_x86_32_incr(const void *key, std::size_t len, uint32_t seed, void *out)
Initial and incremental hash.
#define BIG_CONSTANT(x)
Unsigned long long constants.
#define NS_LOG_COMPONENT_DEFINE(name)
Define a Log component with a specific name.
Definition log.h:191
ns3::Hash::Function::Murmur3 declaration.
Debug message logging.
Every class exported by the ns3 library is enclosed in the ns3 namespace.
uint8_t data[writeSize]