1f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 2f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHash2 was written by Austin Appleby, and is placed in the public 3f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// domain. The author hereby disclaims copyright to this source code. 4f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 5f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Note - This code makes a few assumptions about how your machine behaves - 6f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 7f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 1. We can read a 4-byte value from any address without crashing 8f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 2. sizeof(int) == 4 9f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 10f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// And it has a few limitations - 11f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 12f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 1. It will not work incrementally. 13f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 2. It will not produce the same results on little-endian and big-endian 14f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// machines. 15f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 16f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#include "MurmurHash2.h" 17f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 18f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 19f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Platform-specific functions and macros 20f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 21f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Microsoft Visual Studio 22f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 23f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#if defined(_MSC_VER) 24f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 25f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define BIG_CONSTANT(x) (x) 26f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 27f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Other compilers 28f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 29f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#else // defined(_MSC_VER) 30f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 31f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define BIG_CONSTANT(x) (x##LLU) 32f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 33f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#endif // !defined(_MSC_VER) 34f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 35f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 36f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 37f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint32_t MurmurHash2 ( const void * key, int len, uint32_t seed ) 38f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 39f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // 'm' and 'r' are mixing constants generated offline. 40f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // They're not really 'magic', they just happen to work well. 41f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 42f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t m = 0x5bd1e995; 43f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 24; 44f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 45f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Initialize the hash to a 'random' value 46f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 47f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h = seed ^ len; 48f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 49f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Mix 4 bytes at a time into the hash 50f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 51f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const unsigned char * data = (const unsigned char *)key; 52f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 53f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 54f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 55f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = *(uint32_t*)data; 56f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 57f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 58f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> r; 59f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 60f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 61f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 62f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= k; 63f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 64f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 65f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 66f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 67f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 68f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Handle the last few bytes of the input array 69f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 70f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 71f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 72f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h ^= data[2] << 16; 73f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h ^= data[1] << 8; 74f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h ^= data[0]; 75f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 76f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 77f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 78f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Do a few final mixes of the hash to ensure the last few 79f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // bytes are well-incorporated. 80f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 81f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 82f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 83f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 15; 84f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 85f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 86f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 87f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 88f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 89f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHash2, 64-bit versions, by Austin Appleby 90f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 91f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment 92f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// and endian-ness issues if used across multiple platforms. 93f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 94f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 64-bit hash for 64-bit platforms 95f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 96f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint64_t MurmurHash64A ( const void * key, int len, uint64_t seed ) 97f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 98f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint64_t m = BIG_CONSTANT(0xc6a4a7935bd1e995); 99f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 47; 100f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 101f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t h = seed ^ (len * m); 102f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 103f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint64_t * data = (const uint64_t *)key; 104f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint64_t * end = data + (len/8); 105f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 106f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(data != end) 107f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 108f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t k = *data++; 109f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 110f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 111f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> r; 112f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 113f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 114f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= k; 115f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 116f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 117f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 118f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const unsigned char * data2 = (const unsigned char*)data; 119f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 120f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len & 7) 121f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 122f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 7: h ^= uint64_t(data2[6]) << 48; 123f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 6: h ^= uint64_t(data2[5]) << 40; 124f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 5: h ^= uint64_t(data2[4]) << 32; 125f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 4: h ^= uint64_t(data2[3]) << 24; 126f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h ^= uint64_t(data2[2]) << 16; 127f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h ^= uint64_t(data2[1]) << 8; 128f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h ^= uint64_t(data2[0]); 129f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 130f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 131f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 132f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> r; 133f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 134f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> r; 135f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 136f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 137f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 138f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 139f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 140f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// 64-bit hash for 32-bit platforms 141f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 142f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint64_t MurmurHash64B ( const void * key, int len, uint64_t seed ) 143f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 144f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t m = 0x5bd1e995; 145f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 24; 146f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 147f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h1 = uint32_t(seed) ^ len; 148f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h2 = uint32_t(seed >> 32); 149f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 150f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t * data = (const uint32_t *)key; 151f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 152f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 8) 153f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 154f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k1 = *data++; 155f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= m; k1 ^= k1 >> r; k1 *= m; 156f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 *= m; h1 ^= k1; 157f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 158f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 159f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k2 = *data++; 160f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k2 *= m; k2 ^= k2 >> r; k2 *= m; 161f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 *= m; h2 ^= k2; 162f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 163f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 164f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 165f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(len >= 4) 166f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 167f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k1 = *data++; 168f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k1 *= m; k1 ^= k1 >> r; k1 *= m; 169f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 *= m; h1 ^= k1; 170f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 171f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 172f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 173f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 174f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 175f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h2 ^= ((unsigned char*)data)[2] << 16; 176f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h2 ^= ((unsigned char*)data)[1] << 8; 177f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h2 ^= ((unsigned char*)data)[0]; 178f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 *= m; 179f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 180f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 181f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= h2 >> 18; h1 *= m; 182f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 ^= h1 >> 22; h2 *= m; 183f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h1 ^= h2 >> 17; h1 *= m; 184f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h2 ^= h1 >> 19; h2 *= m; 185f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 186f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint64_t h = h1; 187f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 188f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h = (h << 32) | h2; 189f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 190f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 191f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 192f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 193f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 194f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHash2A, by Austin Appleby 195f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 196f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// This is a variant of MurmurHash2 modified to use the Merkle-Damgard 197f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// construction. Bulk speed should be identical to Murmur2, small-key speed 198f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// will be 10%-20% slower due to the added overhead at the end of the hash. 199f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 200f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// This variant fixes a minor issue where null keys were more likely to 201f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// collide with each other than expected, and also makes the function 202f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// more amenable to incremental implementations. 203f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 204f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define mmix(h,k) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } 205f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 206f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint32_t MurmurHash2A ( const void * key, int len, uint32_t seed ) 207f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 208f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t m = 0x5bd1e995; 209f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 24; 210f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t l = len; 211f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 212f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const unsigned char * data = (const unsigned char *)key; 213f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 214f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h = seed; 215f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 216f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 217f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 218f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = *(uint32_t*)data; 219f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 220f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(h,k); 221f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 222f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 223f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 224f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 225f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 226f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t t = 0; 227f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 228f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 229f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 230f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: t ^= data[2] << 16; 231f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: t ^= data[1] << 8; 232f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: t ^= data[0]; 233f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 234f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 235f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(h,t); 236f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(h,l); 237f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 238f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 239f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 240f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 15; 241f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 242f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 243f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 244f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 245f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 246f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// CMurmurHash2A, by Austin Appleby 247f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 248f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// This is a sample implementation of MurmurHash2A designed to work 249f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// incrementally. 250f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 251f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Usage - 252f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 253f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// CMurmurHash2A hasher 254f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hasher.Begin(seed); 255f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hasher.Add(data1,size1); 256f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hasher.Add(data2,size2); 257f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// ... 258f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// hasher.Add(dataN,sizeN); 259f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// uint32_t hash = hasher.End() 260f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 261f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comclass CMurmurHash2A 262f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 263f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.compublic: 264f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 265f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com void Begin ( uint32_t seed = 0 ) 266f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 267f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_hash = seed; 268f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_tail = 0; 269f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_count = 0; 270f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_size = 0; 271f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 272f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 273f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com void Add ( const unsigned char * data, int len ) 274f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 275f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_size += len; 276f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 277f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com MixTail(data,len); 278f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 279f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 280f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 281f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = *(uint32_t*)data; 282f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 283f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(m_hash,k); 284f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 285f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 286f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 287f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 288f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 289f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com MixTail(data,len); 290f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 291f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 292f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t End ( void ) 293f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 294f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(m_hash,m_tail); 295f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(m_hash,m_size); 296f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 297f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_hash ^= m_hash >> 13; 298f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_hash *= m; 299f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_hash ^= m_hash >> 15; 300f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 301f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return m_hash; 302f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 303f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 304f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comprivate: 305f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 306f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com static const uint32_t m = 0x5bd1e995; 307f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com static const int r = 24; 308f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 309f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com void MixTail ( const unsigned char * & data, int & len ) 310f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 311f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while( len && ((len<4) || m_count) ) 312f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 313f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_tail |= (*data++) << (m_count * 8); 314f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 315f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_count++; 316f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len--; 317f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 318f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(m_count == 4) 319f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 320f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com mmix(m_hash,m_tail); 321f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_tail = 0; 322f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com m_count = 0; 323f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 324f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 325f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 326f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 327f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t m_hash; 328f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t m_tail; 329f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t m_count; 330f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t m_size; 331f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com}; 332f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 333f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 334f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHashNeutral2, by Austin Appleby 335f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 336f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Same as MurmurHash2, but endian- and alignment-neutral. 337f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Half the speed though, alas. 338f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 339f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint32_t MurmurHashNeutral2 ( const void * key, int len, uint32_t seed ) 340f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 341f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t m = 0x5bd1e995; 342f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 24; 343f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 344f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h = seed ^ len; 345f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 346f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const unsigned char * data = (const unsigned char *)key; 347f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 348f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 349f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 350f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k; 351f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 352f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k = data[0]; 353f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k |= data[1] << 8; 354f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k |= data[2] << 16; 355f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k |= data[3] << 24; 356f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 357f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 358f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k ^= k >> r; 359f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com k *= m; 360f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 361f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 362f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= k; 363f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 364f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 365f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 366f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 367f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 368f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 369f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 370f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h ^= data[2] << 16; 371f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h ^= data[1] << 8; 372f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h ^= data[0]; 373f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 374f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 375f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 376f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 377f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 378f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 15; 379f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 380f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 381f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 382f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 383f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 384f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// MurmurHashAligned2, by Austin Appleby 385f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 386f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Same algorithm as MurmurHash2, but only does aligned reads - should be safer 387f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// on certain platforms. 388f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 389f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com// Performance will be lower than MurmurHash2 390f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 391f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com#define MIX(h,k,m) { k *= m; k ^= k >> r; k *= m; h *= m; h ^= k; } 392f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 393f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 394f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.comuint32_t MurmurHashAligned2 ( const void * key, int len, uint32_t seed ) 395f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com{ 396f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const uint32_t m = 0x5bd1e995; 397f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const int r = 24; 398f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 399f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com const unsigned char * data = (const unsigned char *)key; 400f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 401f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t h = seed ^ len; 402f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 403f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int align = (uint64_t)data & 3; 404f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 405f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(align && (len >= 4)) 406f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 407f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Pre-load the temp registers 408f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 409f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t t = 0, d = 0; 410f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 411f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(align) 412f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 413f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: t |= data[2] << 16; 414f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: t |= data[1] << 8; 415f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: t |= data[0]; 416f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 417f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 418f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com t <<= (8 * align); 419f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 420f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4-align; 421f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4-align; 422f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 423f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int sl = 8 * (4-align); 424f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com int sr = 8 * align; 425f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 426f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Mix 427f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 428f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 429f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 430f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com d = *(uint32_t *)data; 431f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com t = (t >> sr) | (d << sl); 432f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 433f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = t; 434f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 435f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com MIX(h,k,m); 436f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 437f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com t = d; 438f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 439f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 440f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 441f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 442f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 443f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Handle leftover data in temp registers 444f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 445f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com d = 0; 446f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 447f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com if(len >= align) 448f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 449f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(align) 450f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 451f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: d |= data[2] << 16; 452f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: d |= data[1] << 8; 453f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: d |= data[0]; 454f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 455f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 456f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = (t >> sr) | (d << sl); 457f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com MIX(h,k,m); 458f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 459f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += align; 460f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= align; 461f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 462f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 463f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Handle tail bytes 464f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 465f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 466f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 467f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h ^= data[2] << 16; 468f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h ^= data[1] << 8; 469f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h ^= data[0]; 470f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 471f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 472f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 473f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else 474f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 475f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 476f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 477f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: d |= data[2] << 16; 478f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: d |= data[1] << 8; 479f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: d |= data[0]; 480f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 0: h ^= (t >> sr) | (d << sl); 481f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 482f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 483f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 484f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 485f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 486f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 487f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 15; 488f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 489f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 490f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 491f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com else 492f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 493f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com while(len >= 4) 494f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 495f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com uint32_t k = *(uint32_t *)data; 496f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 497f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com MIX(h,k,m); 498f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 499f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com data += 4; 500f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com len -= 4; 501f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 502f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 503f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com //---------- 504f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com // Handle tail bytes 505f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 506f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com switch(len) 507f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com { 508f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 3: h ^= data[2] << 16; 509f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 2: h ^= data[1] << 8; 510f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com case 1: h ^= data[0]; 511f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 512f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com }; 513f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 514f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 13; 515f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h *= m; 516f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com h ^= h >> 15; 517f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 518f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com return h; 519f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com } 520f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com} 521f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 522f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com//----------------------------------------------------------------------------- 523f3b789787b93945c974e2cc517b7dc352b28354etanjent@gmail.com 524