Permalink
Switch branches/tags
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
175 lines (128 sloc) 3.26 KB
//-----------------------------------------------------------------------------
// MurmurHash was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.
// Note - This code makes a few assumptions about how your machine behaves -
// 1. We can read a 4-byte value from any address without crashing
// 2. sizeof(int) == 4
// And it has a few limitations -
// 1. It will not work incrementally.
// 2. It will not produce the same results on little-endian and big-endian
// machines.
#include "MurmurHash1.h"
//-----------------------------------------------------------------------------
uint32_t MurmurHash1 ( const void * key, int len, uint32_t seed )
{
const unsigned int m = 0xc6a4a793;
const int r = 16;
unsigned int h = seed ^ (len * m);
//----------
const unsigned char * data = (const unsigned char *)key;
while(len >= 4)
{
unsigned int k = *(unsigned int *)data;
h += k;
h *= m;
h ^= h >> 16;
data += 4;
len -= 4;
}
//----------
switch(len)
{
case 3:
h += data[2] << 16;
case 2:
h += data[1] << 8;
case 1:
h += data[0];
h *= m;
h ^= h >> r;
};
//----------
h *= m;
h ^= h >> 10;
h *= m;
h ^= h >> 17;
return h;
}
//-----------------------------------------------------------------------------
// MurmurHash1Aligned, by Austin Appleby
// Same algorithm as MurmurHash1, but only does aligned reads - should be safer
// on certain platforms.
// Performance should be equal to or better than the simple version.
unsigned int MurmurHash1Aligned ( const void * key, int len, unsigned int seed )
{
const unsigned int m = 0xc6a4a793;
const int r = 16;
const unsigned char * data = (const unsigned char *)key;
unsigned int h = seed ^ (len * m);
int align = (uint64_t)data & 3;
if(align && (len >= 4))
{
// Pre-load the temp registers
unsigned int t = 0, d = 0;
switch(align)
{
case 1: t |= data[2] << 16;
case 2: t |= data[1] << 8;
case 3: t |= data[0];
}
t <<= (8 * align);
data += 4-align;
len -= 4-align;
int sl = 8 * (4-align);
int sr = 8 * align;
// Mix
while(len >= 4)
{
d = *(unsigned int *)data;
t = (t >> sr) | (d << sl);
h += t;
h *= m;
h ^= h >> r;
t = d;
data += 4;
len -= 4;
}
// Handle leftover data in temp registers
int pack = len < align ? len : align;
d = 0;
switch(pack)
{
case 3: d |= data[2] << 16;
case 2: d |= data[1] << 8;
case 1: d |= data[0];
case 0: h += (t >> sr) | (d << sl);
h *= m;
h ^= h >> r;
}
data += pack;
len -= pack;
}
else
{
while(len >= 4)
{
h += *(unsigned int *)data;
h *= m;
h ^= h >> r;
data += 4;
len -= 4;
}
}
//----------
// Handle tail bytes
switch(len)
{
case 3: h += data[2] << 16;
case 2: h += data[1] << 8;
case 1: h += data[0];
h *= m;
h ^= h >> r;
};
h *= m;
h ^= h >> 10;
h *= m;
h ^= h >> 17;
return h;
}