git.m6w6.name Git - awesomized/libmemcached/blob - src/libhashkit/murmur3.cc

   1 //-----------------------------------------------------------------------------
   2 //MurmurHash3 was written by Austin Appleby, and is placed in the public
   3 //domain. The author hereby disclaims copyright to this source code.
   4
   5 // Note - The x86 and x64 versions do _not_ produce the same results, as the
   6 // algorithms are optimized for their respective platforms. You can still
   7 // compile and run any of them on any platform, but your performance with the
   8 // non-native version will be less than optimal.
   9
  10 #include "libhashkit/hashkitcon.h"
  11
  12 #include "libhashkit/murmur3.h"
  13
  14 //-----------------------------------------------------------------------------
  15 // Platform-specific functions and macros
  16
  17 #ifdef __GNUC__
  18 #define FORCE_INLINE __attribute__((always_inline)) inline
  19 #else
  20 #define FORCE_INLINE inline
  21 #endif
  22
  23 static FORCE_INLINE uint32_t rotl32 ( uint32_t x, int8_t r )
  24 {
  25   return (x << r) | (x >> (32 - r));
  26 }
  27
  28 static FORCE_INLINE uint64_t rotl64 ( uint64_t x, int8_t r )
  29 {
  30   return (x << r) | (x >> (64 - r));
  31 }
  32
  33 #define ROTL32(x,y)     rotl32(x,y)
  34 #define ROTL64(x,y)     rotl64(x,y)
  35
  36 #define BIG_CONSTANT(x) (x##LLU)
  37
  38 //-----------------------------------------------------------------------------
  39 // Block read - if your platform needs to do endian-swapping or can only
  40 // handle aligned reads, do the conversion here
  41
  42 #include <cassert>
  43 #include <cstring>
  44 template <typename T>
  45 static inline T getblock(const T *blocks, int i) {
  46   T b;
  47   memcpy(&b, ((const uint8_t *) blocks) + i * sizeof(T), sizeof(T));
  48   return b;
  49 }
  50
  51 //-----------------------------------------------------------------------------
  52 // Finalization mix - force all bits of a hash block to avalanche
  53
  54 static FORCE_INLINE uint32_t fmix32 ( uint32_t h )
  55 {
  56   h ^= h >> 16;
  57   h *= 0x85ebca6b;
  58   h ^= h >> 13;
  59   h *= 0xc2b2ae35;
  60   h ^= h >> 16;
  61
  62   return h;
  63 }
  64
  65 //----------
  66
  67 static FORCE_INLINE uint64_t fmix64 ( uint64_t k )
  68 {
  69   k ^= k >> 33;
  70   k *= BIG_CONSTANT(0xff51afd7ed558ccd);
  71   k ^= k >> 33;
  72   k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
  73   k ^= k >> 33;
  74
  75   return k;
  76 }
  77
  78 //-----------------------------------------------------------------------------
  79
  80 void MurmurHash3_x86_32 ( const void * key, int len,
  81                           uint32_t seed, void * out )
  82 {
  83   const uint8_t * data = (const uint8_t*)key;
  84   const int nblocks = len / 4;
  85   int i;
  86
  87   uint32_t h1 = seed;
  88
  89   uint32_t c1 = 0xcc9e2d51;
  90   uint32_t c2 = 0x1b873593;
  91
  92   //----------
  93   // body
  94
  95   const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
  96
  97   for(i = -nblocks; i; i++)
  98   {
  99     uint32_t k1 = getblock(blocks,i);
 100 #if WORDS_BIGENDIAN
 101     k1 = BYTESWAP_32(k1);
 102 #endif
 103
 104     k1 *= c1;
 105     k1 = ROTL32(k1,15);
 106     k1 *= c2;
 107
 108     h1 ^= k1;
 109     h1 = ROTL32(h1,13);
 110     h1 = h1*5+0xe6546b64;
 111   }
 112
 113   //----------
 114   // tail
 115
 116   const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
 117
 118   uint32_t k1 = 0;
 119   memcpy(&k1, tail, len & 3);
 120 #if WORDS_BIGENDIAN
 121   k1 = BYTESWAP_32(k1);
 122 #endif
 123
 124   k1 *= c1;
 125   k1 = ROTL32(k1,15);
 126   k1 *= c2;
 127   h1 ^= k1;
 128
 129   //----------
 130   // finalization
 131
 132   h1 ^= len;
 133
 134   h1 = fmix32(h1);
 135
 136   *(uint32_t*)out = h1;
 137 }
 138
 139 //-----------------------------------------------------------------------------
 140
 141 void MurmurHash3_x86_128 ( const void * key, const int len,
 142                            uint32_t seed, void * out )
 143 {
 144   const uint8_t * data = (const uint8_t*)key;
 145   const int nblocks = len / 16;
 146   int i;
 147
 148   uint32_t h1 = seed;
 149   uint32_t h2 = seed;
 150   uint32_t h3 = seed;
 151   uint32_t h4 = seed;
 152
 153   uint32_t c1 = 0x239b961b;
 154   uint32_t c2 = 0xab0e9789;
 155   uint32_t c3 = 0x38b34ae5;
 156   uint32_t c4 = 0xa1e38b93;
 157
 158   //----------
 159   // body
 160
 161   const uint32_t * blocks = (const uint32_t *)(data + nblocks*16);
 162
 163   for(i = -nblocks; i; i++)
 164   {
 165     uint32_t k1 = getblock(blocks,i*4+0);
 166     uint32_t k2 = getblock(blocks,i*4+1);
 167     uint32_t k3 = getblock(blocks,i*4+2);
 168     uint32_t k4 = getblock(blocks,i*4+3);
 169
 170     k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
 171
 172     h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
 173
 174     k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
 175
 176     h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
 177
 178     k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
 179
 180     h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
 181
 182     k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
 183
 184     h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
 185   }
 186
 187   //----------
 188   // tail
 189
 190   const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
 191
 192   uint32_t k1 = 0;
 193   uint32_t k2 = 0;
 194   uint32_t k3 = 0;
 195   uint32_t k4 = 0;
 196
 197   switch(len & 15)
 198   {
 199   case 15: k4 ^= tail[14] << 16;
 200            /* fall through */
 201   case 14: k4 ^= tail[13] << 8;
 202            /* fall through */
 203   case 13: k4 ^= tail[12] << 0;
 204            k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
 205            /* fall through */
 206   case 12: k3 ^= tail[11] << 24;
 207            /* fall through */
 208   case 11: k3 ^= tail[10] << 16;
 209            /* fall through */
 210   case 10: k3 ^= tail[ 9] << 8;
 211            /* fall through */
 212   case  9: k3 ^= tail[ 8] << 0;
 213            k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
 214            /* fall through */
 215   case  8: k2 ^= tail[ 7] << 24;
 216            /* fall through */
 217   case  7: k2 ^= tail[ 6] << 16;
 218            /* fall through */
 219   case  6: k2 ^= tail[ 5] << 8;
 220            /* fall through */
 221   case  5: k2 ^= tail[ 4] << 0;
 222            k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
 223            /* fall through */
 224   case  4: k1 ^= tail[ 3] << 24;
 225            /* fall through */
 226   case  3: k1 ^= tail[ 2] << 16;
 227            /* fall through */
 228   case  2: k1 ^= tail[ 1] << 8;
 229            /* fall through */
 230   case  1: k1 ^= tail[ 0] << 0;
 231            k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
 232   };
 233
 234   //----------
 235   // finalization
 236
 237   h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
 238
 239   h1 += h2; h1 += h3; h1 += h4;
 240   h2 += h1; h3 += h1; h4 += h1;
 241
 242   h1 = fmix32(h1);
 243   h2 = fmix32(h2);
 244   h3 = fmix32(h3);
 245   h4 = fmix32(h4);
 246
 247   h1 += h2; h1 += h3; h1 += h4;
 248   h2 += h1; h3 += h1; h4 += h1;
 249
 250   ((uint32_t*)out)[0] = h1;
 251   ((uint32_t*)out)[1] = h2;
 252   ((uint32_t*)out)[2] = h3;
 253   ((uint32_t*)out)[3] = h4;
 254 }
 255
 256 //-----------------------------------------------------------------------------
 257
 258 void MurmurHash3_x64_128 ( const void * key, const int len,
 259                            const uint32_t seed, void * out )
 260 {
 261   const uint8_t * data = (const uint8_t*)key;
 262   const int nblocks = len / 16;
 263   int i;
 264
 265   uint64_t h1 = seed;
 266   uint64_t h2 = seed;
 267
 268   uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
 269   uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
 270
 271   //----------
 272   // body
 273
 274   const uint64_t * blocks = (const uint64_t *)(data);
 275
 276   for(i = 0; i < nblocks; i++)
 277   {
 278     uint64_t k1 = getblock(blocks,i*2+0);
 279     uint64_t k2 = getblock(blocks,i*2+1);
 280
 281     k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
 282
 283     h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
 284
 285     k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
 286
 287     h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
 288   }
 289
 290   //----------
 291   // tail
 292
 293   const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
 294
 295   uint64_t k1 = 0;
 296   uint64_t k2 = 0;
 297
 298   switch(len & 15)
 299   {
 300   case 15: k2 ^= (uint64_t)(tail[14]) << 48;
 301            /* fall through */
 302   case 14: k2 ^= (uint64_t)(tail[13]) << 40;
 303            /* fall through */
 304   case 13: k2 ^= (uint64_t)(tail[12]) << 32;
 305            /* fall through */
 306   case 12: k2 ^= (uint64_t)(tail[11]) << 24;
 307            /* fall through */
 308   case 11: k2 ^= (uint64_t)(tail[10]) << 16;
 309            /* fall through */
 310   case 10: k2 ^= (uint64_t)(tail[ 9]) << 8;
 311            /* fall through */
 312   case  9: k2 ^= (uint64_t)(tail[ 8]) << 0;
 313            k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
 314            /* fall through */
 315   case  8: k1 ^= (uint64_t)(tail[ 7]) << 56;
 316            /* fall through */
 317   case  7: k1 ^= (uint64_t)(tail[ 6]) << 48;
 318            /* fall through */
 319   case  6: k1 ^= (uint64_t)(tail[ 5]) << 40;
 320            /* fall through */
 321   case  5: k1 ^= (uint64_t)(tail[ 4]) << 32;
 322            /* fall through */
 323   case  4: k1 ^= (uint64_t)(tail[ 3]) << 24;
 324            /* fall through */
 325   case  3: k1 ^= (uint64_t)(tail[ 2]) << 16;
 326            /* fall through */
 327   case  2: k1 ^= (uint64_t)(tail[ 1]) << 8;
 328            /* fall through */
 329   case  1: k1 ^= (uint64_t)(tail[ 0]) << 0;
 330            k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
 331   };
 332
 333   //----------
 334   // finalization
 335
 336   h1 ^= len; h2 ^= len;
 337
 338   h1 += h2;
 339   h2 += h1;
 340
 341   h1 = fmix64(h1);
 342   h2 = fmix64(h2);
 343
 344   h1 += h2;
 345   h2 += h1;
 346
 347   ((uint64_t*)out)[0] = h1;
 348   ((uint64_t*)out)[1] = h2;
 349 }
 350
 351 //-----------------------------------------------------------------------------
 352