Introduction

The macro rotl() appears to be part of Visual C++ dialect. It would be nicer if you could provide code that compiles with any compiler (i.e., ISO standard).

Cross-platform support is in the works, but I'm a bit pressed for time - the platform-specific stuff should mostly be restricted to rotl and some timing / setup code.

gcc will turn an expression like:

   (NUM << AMOUNT) | (NUM >> (32 - AMOUNT))

into a single "roll" instruction on x86-type processors (ok, sometimes it will actually use "rorl" with a count of (32 - amount), but same difference).

So you could use a portable macro like:

#define ROTL32(num,amount) (((num) << (amount)) | ((num) >> (32 - (amount))))

and that should work a treat on gcc (and perhaps other compilers).

p.s., note that only works if "num" is a 32-bit type; for gcc on x86_64 (and x86), that's true for int / unsigned int, but one might want to throw in a few casts to make it explicit.

(or even better, use an inline function, but I guess those aren't really portable in C...)

Would you mind kindly adding this fast SSE2-based hash to your list of tested hash functions? http://cessu.blogspot.com/2008/11/hashing-with-sse2-revisited-or-my-hash.html

And instead of rotl64, just use 64 where it says 32.

Though I'm using an inline functions instead (LLVM compiler on OS X):

uint32_t inline rotl(uint32_t value, int8_t amount) {

return ((value) << (amount)) | ((value) >> (32 - (amount)));

uint64_t inline rotl64(uint64_t value, int8_t amount) {

return ((value) << (amount)) | ((value) >> (64 - (amount)));

To get this working on Android/NDK (GCC 4.4.0) I had to do the following:

1. I utilized the ROTL stuff from the above comment
2. Create a FORCE_INLINE define for where forceinline was used:

#if defined(_MSC_VER)
	#define FORCE_INLINE	__forceinline
#else
	#define	FORCE_INLINE	__attribute__((always_inline)) 
#endif

Note that I have not yet done any real testing, so YMMV :)

This header file is quite useful for a portable rotl and rotl64:

https://www.cosic.esat.kuleuven.be/nessie/testvectors/test/portable.h

If anyone is interested I've ported the murmur3 hash to mingw gcc and it seems to be working.

What would be a good way to use the mix functions to hash 32/64 bit integers? Its sure possible to simply use bmix32 twice and fmix32 for a 64 bit int. But I guess there are some steps that are not really necessary then.

How do I generate 64-bit hash values? Looking at MurmurHash3_x64_128, it returns the 128-bit hash value in 2 uint64_t values, h1 and h2. So do I simply take either h1 or h2? Which one should I take?

@a.goed - Use the finalization mix functions fmix32/fmix64 - they do exactly what you want.

@lancer6 - Yep, just throw away whatever bits you don't use. All bits of the output should be equally well mixed.

I'm a bit confused about the results I'm getting. I got the latest trunk (r96) and ran smhasher on Murmur3C and Murmur3F on a Core i5 760 system thinking the 64bit Murmur3F should run faster.

Under the bulk speed test, Murmur3C averages 2363.28 MiB/sec while Murmur3F averages 452.15 MiB/sec. In all of the small key speed tests, Murmur3F also used roughly 3 times as many cycles per hash on average.

I'm just trying to figure out why my results are so different from those shown.

Jonathan - That's almost definitely due to your using a 32-bit compiler - Murmur3F needs to be compiled in x64 mode, otherwise the 64-bit math operations are done as function calls (verrrry slow). In Visual Studio this is done by creating a new build configuration, but I'm not sure how things will work with the new CMake setup.

-Austin

That was exactly the problem. I knew I was overlooking something simple.

Thanks!

What's the intended purpose of the seed param? I'm considering implementing a progressive MurmurHash3_x86_32 in pure ANSI-C. In which case a similar effect to the seed can be achieved by appending it at the end as regular data just before the finalisation stage. This also allows generating multiple hashes with different "seeds" without reprocessing the entire byte stream.

Hello,JSpren...@gmail.com,

can you send me your "c" implementation of murmurhash3?

abhay180@yahoo.com

Hello,

Has somebody implmented the Murmurhash3 in "c". I want to take a look at the code

Here's a C version of MurmurHash 3, with some handy API documentation and an example program:

https://github.com/PeterScott/murmur3

To make the .cpp file Borland C++ compatible:

#if defined(MSC_VER)

...

// Other compilers

#else // defined(MSC_VER)

#ifdef BORLANDC #define FORCE_INLINE inline #else #define FORCE_INLINE attribute((always_inline)) #endif

...

#endif

To Peter Scott: Hello, I started using your C version in a personal project. Thank you very much! (You may contact me if you like: denis DOT spir AT gmail DOT com. I may also have some question.) Denis

Hi, why didn't you do something like the following for non-MSC compilers? Or is it that other compilers optimize it out, and Visual Studio requires the intrinsic? I'm was just wondering about the oddness.

#if defined(i386)

inline uint32_t rotl32 ( uint32_t x, int8_t r ) {

asm volatile("rol %b1, %0" : "+mr" (x) : "Ic" (r)); return x;

inline uint64_t rotl64 ( uint64_t x, int8_t r ) {

asm volatile("rol %b1, %0" : "+mr" (x) : "Jc" (r)); return x;

#else .. old code ..

how to get the binary such as md5sum?

@khubert - Virtually all compilers are smart enough to convert the shifts and ors into a rotate instruction (you can verify this by dissassembling the function in GDB or Visual Studio), so adding the assembly doesn't gain anything.

Hi guys,

how can I write an incremental version of murmur3 x64_128, that combines hashing results in one final hash; Keeping the final result collition free?

Many Thanks

How about using a previous hash value to initialize h1 and h2 instead of using a seed? Will this work?

thanks

I am curious why the constants used in the body of x64_128 (n1 in the Details section of the wiki) are only 32bits. They are also 32 bits for the x86 versions, so it makes me think they would be 64 bits for the x64 version.

Be careful with the macros/inline functions pasted above:

(NUM << AMOUNT) | (NUM >> (32 - AMOUNT))

(NUM << AMOUNT) | (NUM >> (64 - AMOUNT))

These won't work correctly if AMOUNT > 32 or 64, respectively. The correct versions are:

(NUM << (AMOUNT & 31)) | (NUM >> (32 - (AMOUNT & 31)))

(NUM << (AMOUNT & 63)) | (NUM >> (64 - (AMOUNT & 63)))

Hi guys,

I've just included an incremental implementation of MurmurHash3 in one of my projects an stumbled upon this: http://emboss.github.com/blog/2012/12/14/breaking-murmur-hash-flooding-dos-reloaded/

I was just bitten by the fact that the block count values are all signed 32 bit, and this is a problem when hashing very large data (> 2 GB). Values should be changed to size_t:

const int nblocks = len / 16; // <--- should be const size_t

FORCE_INLINE uint64_t getblock64 ( const uint64_t p, int i ) // <- 32 bit index should be size_t {

return pi?;

Have you considered testing against tabulation hashing as well?

Isn't the 32b and 64b accesses (uint32_t k1 = getblock32(blocks,i);) breaking the strict-aliasing rule ? Shouldn't memcpy be used instead (memcpy(&k1, data + i*4, 4);) ?

If you need a fast Java implementation of Murmur3A or Murmur3F, check out my new open source project: https://github.com/greenrobot/greenrobot-common

Murmur3F does 3.7 GB/s using sun.misc.Unsafe, which is the fastest implementation known to me. For more information including performance benchmarks, have a look at https://github.com/greenrobot/greenrobot-common/blob/master/hash-functions.md