#include "MurmurHash1.h" | |
//----------------------------------------------------------------------------- | |
// MurmurHash1, by Austin Appleby | |
// 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. | |
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 = (int)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; | |
} | |