murmurhash3.h File Reference

Inline block and incremental versions of Austin Appleby's MurmurHash3 hash function. More...

#include "platform.h"
#include "hqmemcpy.h"

Data Structures
struct	MURMURHASH_STATE

Functions
static uint32	getblock32 (const uint32 *p, int i)
static uint32	fmix32 (uint32 h)
static void	MurmurHash3_32 (const void *key, int len, uint32 seed, uint32 *out)
static uint64	fmix64 (uint64 k)
static HqBool	getblock128_64 (MURMURHASH_STATE *state, uint8 **data, int *len, uint64 *k)
static void	MurmurHash3_128_init (MURMURHASH_STATE *state, void *seed)
static void	MurmurHash3_128_incremental (MURMURHASH_STATE *state, const void *key, const int inlen)
static void	MurmurHash3_128_finalize (MURMURHASH_STATE *state, void *out)
static void	MurmurHash3_128 (const void *key, const int len, void *seed, void *out)

Detailed Description

Inline block and incremental versions of Austin Appleby's MurmurHash3 hash function.

MurmurHash3 was written by Austin Appleby, and is placed in the public domain. The author hereby disclaims copyright to this source code.

Note - The x86 and x64 versions do not produce the same results, as the algorithms are optimized for their respective platforms. You can still compile and run any of them on any platform, but your performance with the non-native version will be less than optimal.

The versions of the 128 bit hash functions here are adapted from the originals to allow incremental hashing so that we can make compound hashes for streams that for whatever reason arrive in dribs and drabs. The explicit intention here is that hashing a given stream will arrive at the same hash value, regardless of how it is split into chunks. This involves some local copying because we don't necessarily have a whole 128 bits to hash at any given time, and even if we do it's not guaranteed to be on a 32 or 64 bit boundary and we don't rely on misaligned memory access being optimal (or even possible). Verification that the implementation is doing what we'd expect is done in murmurhash3.c.

Function Documentation

fmix32()

static uint32 fmix32 ( uint32  h )

inlinestatic

Finalization mix - force all bits of a hash block to avalanche. 32 bit version.

fmix64()

static uint64 fmix64 ( uint64  k )

inlinestatic

Finalization mix - force all bits of a hash block to avalanche. 64 bit version.

getblock128_64()

static HqBool getblock128_64 ( MURMURHASH_STATE *  state, uint8 **  data, int *  len, uint64 *  k  )

inlinestatic

Data accessor for the 64 bit MurmurHash3 function. Returns TRUE if a new 128 bit value has been returned in k - otherwise hangs on to the input in the state ready for more to arrive later.

getblock32()

static uint32 getblock32 ( const uint32 *  p, int  i  )

inlinestatic

Block read - if the platform needs to do endian-swapping or can only handle aligned reads, do the conversion here

MurmurHash3_128()

static void MurmurHash3_128 ( const void *  key, const int  len, void *  seed, void *  out  )

inlinestatic

Monolithic 128 bit MurmurHash3 hash function, written in terms of the incremental versions. The 128 bit *seed value can be NULL.

MurmurHash3_128_finalize()

static void MurmurHash3_128_finalize ( MURMURHASH_STATE *  state, void *  out  )

inlinestatic

64 bit MurmurHash3 hash function finaliser. Any bytes left in the state are hashed and then the final mixing takes place.

MurmurHash3_128_incremental()

static void MurmurHash3_128_incremental ( MURMURHASH_STATE *  state, const void *  key, const int  inlen  )

inlinestatic

64 bit incremental MurmurHash3 hash function. The state must first have been initialised. The hash will keep accumulating until the finaliser is called.

MurmurHash3_128_init()

static void MurmurHash3_128_init ( MURMURHASH_STATE *  state, void *  seed  )

inlinestatic

64 bit MurmurHash3 hash state initialisation. Note that unlike the originally published code, the seed is a pointer to a 128 bit value rather than just 32 bits (or NULL if there is no seed).

MurmurHash3_32()

static void MurmurHash3_32 ( const void *  key, int  len, uint32  seed, uint32 *  out  )

inlinestatic

32 bit MurmurHash3 hash function. Note this assumes 32 bit alignment of key, or that misaligned 32 bit access is supported on the runtime platform.