git.m6w6.name Git - m6w6/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 #define ROTL32(x,y)     rotl32(x,y)
  29
  30 //-----------------------------------------------------------------------------
  31 // Block read - if your platform needs to do endian-swapping or can only
  32 // handle aligned reads, do the conversion here
  33
  34 #include <cassert>
  35 #include <cstring>
  36 template <typename T>
  37 static inline T getblock(const T *blocks, int i) {
  38   T b;
  39   memcpy(&b, ((const uint8_t *) blocks) + i * sizeof(T), sizeof(T));
  40   return b;
  41 }
  42
  43 //-----------------------------------------------------------------------------
  44 // Finalization mix - force all bits of a hash block to avalanche
  45
  46 static FORCE_INLINE uint32_t fmix32 ( uint32_t h )
  47 {
  48   h ^= h >> 16;
  49   h *= 0x85ebca6b;
  50   h ^= h >> 13;
  51   h *= 0xc2b2ae35;
  52   h ^= h >> 16;
  53
  54   return h;
  55 }
  56
  57 //-----------------------------------------------------------------------------
  58
  59 void MurmurHash3_x86_32 ( const void * key, int len,
  60                           uint32_t seed, void * out )
  61 {
  62   const uint8_t * data = (const uint8_t*)key;
  63   const int nblocks = len / 4;
  64   int i;
  65
  66   uint32_t h1 = seed;
  67
  68   uint32_t c1 = 0xcc9e2d51;
  69   uint32_t c2 = 0x1b873593;
  70
  71   //----------
  72   // body
  73
  74   const uint32_t * blocks = (const uint32_t *)(data + nblocks*4);
  75
  76   for(i = -nblocks; i; i++)
  77   {
  78     uint32_t k1 = getblock(blocks,i);
  79 #if WORDS_BIGENDIAN
  80     k1 = BYTESWAP_32(k1);
  81 #endif
  82
  83     k1 *= c1;
  84     k1 = ROTL32(k1,15);
  85     k1 *= c2;
  86
  87     h1 ^= k1;
  88     h1 = ROTL32(h1,13);
  89     h1 = h1*5+0xe6546b64;
  90   }
  91
  92   //----------
  93   // tail
  94
  95   const uint8_t * tail = (const uint8_t*)(data + nblocks*4);
  96
  97   uint32_t k1 = 0;
  98   memcpy(&k1, tail, len & 3);
  99 #if WORDS_BIGENDIAN
 100   k1 = BYTESWAP_32(k1);
 101 #endif
 102
 103   k1 *= c1;
 104   k1 = ROTL32(k1,15);
 105   k1 *= c2;
 106   h1 ^= k1;
 107
 108   //----------
 109   // finalization
 110
 111   h1 ^= len;
 112
 113   h1 = fmix32(h1);
 114
 115   *(uint32_t*)out = h1;
 116 }