00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013 #include "util/murmur_hash.hh"
00014 #include <cstring>
00015
00016 namespace util {
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 uint64_t MurmurHash64A ( const void * key, std::size_t len, uint64_t seed )
00027 {
00028 const uint64_t m = 0xc6a4a7935bd1e995ULL;
00029 const int r = 47;
00030
00031 uint64_t h = seed ^ (len * m);
00032
00033 #if defined(__arm) || defined(__arm__)
00034 const size_t ksize = sizeof(uint64_t);
00035 const unsigned char * data = (const unsigned char *)key;
00036 const unsigned char * end = data + (std::size_t)(len/8) * ksize;
00037 #else
00038 const uint64_t * data = (const uint64_t *)key;
00039 const uint64_t * end = data + (len/8);
00040 #endif
00041
00042 while(data != end)
00043 {
00044 #if defined(__arm) || defined(__arm__)
00045 uint64_t k;
00046 memcpy(&k, data, ksize);
00047 data += ksize;
00048 #else
00049 uint64_t k = *data++;
00050 #endif
00051
00052 k *= m;
00053 k ^= k >> r;
00054 k *= m;
00055
00056 h ^= k;
00057 h *= m;
00058 }
00059
00060 const unsigned char * data2 = (const unsigned char*)data;
00061
00062 switch(len & 7)
00063 {
00064 case 7: h ^= uint64_t(data2[6]) << 48;
00065 case 6: h ^= uint64_t(data2[5]) << 40;
00066 case 5: h ^= uint64_t(data2[4]) << 32;
00067 case 4: h ^= uint64_t(data2[3]) << 24;
00068 case 3: h ^= uint64_t(data2[2]) << 16;
00069 case 2: h ^= uint64_t(data2[1]) << 8;
00070 case 1: h ^= uint64_t(data2[0]);
00071 h *= m;
00072 };
00073
00074 h ^= h >> r;
00075 h *= m;
00076 h ^= h >> r;
00077
00078 return h;
00079 }
00080
00081
00082
00083
00084 uint64_t MurmurHash64B ( const void * key, std::size_t len, uint64_t seed )
00085 {
00086 const unsigned int m = 0x5bd1e995;
00087 const int r = 24;
00088
00089 unsigned int h1 = seed ^ len;
00090 unsigned int h2 = 0;
00091
00092 #if defined(__arm) || defined(__arm__)
00093 size_t ksize = sizeof(unsigned int);
00094 const unsigned char * data = (const unsigned char *)key;
00095 #else
00096 const unsigned int * data = (const unsigned int *)key;
00097 #endif
00098
00099 unsigned int k1, k2;
00100 while(len >= 8)
00101 {
00102 #if defined(__arm) || defined(__arm__)
00103 memcpy(&k1, data, ksize);
00104 data += ksize;
00105 memcpy(&k2, data, ksize);
00106 data += ksize;
00107 #else
00108 k1 = *data++;
00109 k2 = *data++;
00110 #endif
00111
00112 k1 *= m; k1 ^= k1 >> r; k1 *= m;
00113 h1 *= m; h1 ^= k1;
00114 len -= 4;
00115
00116 k2 *= m; k2 ^= k2 >> r; k2 *= m;
00117 h2 *= m; h2 ^= k2;
00118 len -= 4;
00119 }
00120
00121 if(len >= 4)
00122 {
00123 #if defined(__arm) || defined(__arm__)
00124 memcpy(&k1, data, ksize);
00125 data += ksize;
00126 #else
00127 k1 = *data++;
00128 #endif
00129 k1 *= m; k1 ^= k1 >> r; k1 *= m;
00130 h1 *= m; h1 ^= k1;
00131 len -= 4;
00132 }
00133
00134 switch(len)
00135 {
00136 case 3: h2 ^= ((unsigned char*)data)[2] << 16;
00137 case 2: h2 ^= ((unsigned char*)data)[1] << 8;
00138 case 1: h2 ^= ((unsigned char*)data)[0];
00139 h2 *= m;
00140 };
00141
00142 h1 ^= h2 >> 18; h1 *= m;
00143 h2 ^= h1 >> 22; h2 *= m;
00144 h1 ^= h2 >> 17; h1 *= m;
00145 h2 ^= h1 >> 19; h2 *= m;
00146
00147 uint64_t h = h1;
00148
00149 h = (h << 32) | h2;
00150
00151 return h;
00152 }
00153
00154
00155 namespace {
00156 #ifdef __clang__
00157 #pragma clang diagnostic push
00158 #pragma clang diagnostic ignored "-Wunused-function"
00159 #endif
00160 template <unsigned L> inline uint64_t MurmurHashNativeBackend(const void * key, std::size_t len, uint64_t seed) {
00161 return MurmurHash64A(key, len, seed);
00162 }
00163 template <> inline uint64_t MurmurHashNativeBackend<4>(const void * key, std::size_t len, uint64_t seed) {
00164 return MurmurHash64B(key, len, seed);
00165 }
00166 #ifdef __clang__
00167 #pragma clang diagnostic pop
00168 #endif
00169 }
00170
00171 uint64_t MurmurHashNative(const void * key, std::size_t len, uint64_t seed) {
00172 return MurmurHashNativeBackend<sizeof(void*)>(key, len, seed);
00173 }
00174
00175 }