File size: 4,074 Bytes
1ce325b |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 |
/* Downloaded from http://sites.google.com/site/murmurhash/ which says "All
* code is released to the public domain. For business purposes, Murmurhash is
* under the MIT license."
* This is modified from the original:
* ULL tag on 0xc6a4a7935bd1e995 so this will compile on 32-bit.
* length changed to unsigned int.
* placed in namespace util
* add MurmurHashNative
* default option = 0 for seed
* ARM port from NICT
*/
#include "murmur_hash.hh"
#include <cstring>
namespace util {
//-----------------------------------------------------------------------------
// MurmurHash2, 64-bit versions, by Austin Appleby
// The same caveats as 32-bit MurmurHash2 apply here - beware of alignment
// and endian-ness issues if used across multiple platforms.
// 64-bit hash for 64-bit platforms
uint64_t MurmurHash64A ( const void * key, std::size_t len, uint64_t seed )
{
const uint64_t m = 0xc6a4a7935bd1e995ULL;
const int r = 47;
uint64_t h = seed ^ (len * m);
#if defined(__arm) || defined(__arm__)
const size_t ksize = sizeof(uint64_t);
const unsigned char * data = (const unsigned char *)key;
const unsigned char * end = data + (std::size_t)(len/8) * ksize;
#else
const uint64_t * data = (const uint64_t *)key;
const uint64_t * end = data + (len/8);
#endif
while(data != end)
{
#if defined(__arm) || defined(__arm__)
uint64_t k;
memcpy(&k, data, ksize);
data += ksize;
#else
uint64_t k = *data++;
#endif
k *= m;
k ^= k >> r;
k *= m;
h ^= k;
h *= m;
}
const unsigned char * data2 = (const unsigned char*)data;
switch(len & 7)
{
case 7: h ^= uint64_t(data2[6]) << 48;
case 6: h ^= uint64_t(data2[5]) << 40;
case 5: h ^= uint64_t(data2[4]) << 32;
case 4: h ^= uint64_t(data2[3]) << 24;
case 3: h ^= uint64_t(data2[2]) << 16;
case 2: h ^= uint64_t(data2[1]) << 8;
case 1: h ^= uint64_t(data2[0]);
h *= m;
};
h ^= h >> r;
h *= m;
h ^= h >> r;
return h;
}
// 64-bit hash for 32-bit platforms
uint64_t MurmurHash64B ( const void * key, std::size_t len, uint64_t seed )
{
const unsigned int m = 0x5bd1e995;
const int r = 24;
unsigned int h1 = seed ^ len;
unsigned int h2 = 0;
#if defined(__arm) || defined(__arm__)
size_t ksize = sizeof(unsigned int);
const unsigned char * data = (const unsigned char *)key;
#else
const unsigned int * data = (const unsigned int *)key;
#endif
unsigned int k1, k2;
while(len >= 8)
{
#if defined(__arm) || defined(__arm__)
memcpy(&k1, data, ksize);
data += ksize;
memcpy(&k2, data, ksize);
data += ksize;
#else
k1 = *data++;
k2 = *data++;
#endif
k1 *= m; k1 ^= k1 >> r; k1 *= m;
h1 *= m; h1 ^= k1;
len -= 4;
k2 *= m; k2 ^= k2 >> r; k2 *= m;
h2 *= m; h2 ^= k2;
len -= 4;
}
if(len >= 4)
{
#if defined(__arm) || defined(__arm__)
memcpy(&k1, data, ksize);
data += ksize;
#else
k1 = *data++;
#endif
k1 *= m; k1 ^= k1 >> r; k1 *= m;
h1 *= m; h1 ^= k1;
len -= 4;
}
switch(len)
{
case 3: h2 ^= ((unsigned char*)data)[2] << 16;
case 2: h2 ^= ((unsigned char*)data)[1] << 8;
case 1: h2 ^= ((unsigned char*)data)[0];
h2 *= m;
};
h1 ^= h2 >> 18; h1 *= m;
h2 ^= h1 >> 22; h2 *= m;
h1 ^= h2 >> 17; h1 *= m;
h2 ^= h1 >> 19; h2 *= m;
uint64_t h = h1;
h = (h << 32) | h2;
return h;
}
// Trick to test for 64-bit architecture at compile time.
namespace {
#ifdef __clang__
#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wunused-function"
#endif
template <unsigned L> inline uint64_t MurmurHashNativeBackend(const void * key, std::size_t len, uint64_t seed) {
return MurmurHash64A(key, len, seed);
}
template <> inline uint64_t MurmurHashNativeBackend<4>(const void * key, std::size_t len, uint64_t seed) {
return MurmurHash64B(key, len, seed);
}
#ifdef __clang__
#pragma clang diagnostic pop
#endif
} // namespace
uint64_t MurmurHashNative(const void * key, std::size_t len, uint64_t seed) {
return MurmurHashNativeBackend<sizeof(void*)>(key, len, seed);
}
} // namespace util
|