c_cpp/readscorr/MurmurHash3.c

   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 // This version is based on the C++ version and trimed to only MurmurHash3_x64_128.
  11 // Edited by Hu Xuesong @ Apr 26 2011, based on r135 | 2011-04-14 07:36:49 +0800 (Thu, 14 Apr 2011)
  12
  13 #include "MurmurHash3.h"
  14
  15 //-----------------------------------------------------------------------------
  16 // Platform-specific functions and macros
  17
  18 // Microsoft Visual Studio
  19
  20 #if defined(_MSC_VER)
  21
  22 #define FORCE_INLINE    __forceinline
  23
  24 #include <stdlib.h>
  25
  26 #define ROTL32(x,y)     _rotl(x,y)
  27 #define ROTL64(x,y)     _rotl64(x,y)
  28
  29 #define BIG_CONSTANT(x) (x)
  30
  31 // Other compilers
  32
  33 #else   // defined(_MSC_VER)
  34
  35 #define FORCE_INLINE __attribute__((always_inline))
  36
  37 inline uint32_t rotl32 ( uint32_t x, int8_t r )
  38 {
  39   return (x << r) | (x >> (32 - r));
  40 }
  41
  42 inline uint64_t rotl64 ( uint64_t x, int8_t r )
  43 {
  44   return (x << r) | (x >> (64 - r));
  45 }
  46
  47 #define ROTL32(x,y)     rotl32(x,y) // at least -O is needed for this to work.
  48 #define ROTL64(x,y)     rotl64(x,y) // Or, MurmurHash3.c:127: undefined reference to `rotl64' when link.
  49
  50 #define BIG_CONSTANT(x) (x##LLU)
  51
  52 #endif // !defined(_MSC_VER)
  53
  54 //-----------------------------------------------------------------------------
  55 // Block read - if your platform needs to do endian-swapping or can only
  56 // handle aligned reads, do the conversion here
  57
  58
  59 FORCE_INLINE uint64_t getblock ( const uint64_t * p, int i )
  60 {
  61   return p[i];
  62 }
  63
  64 //-----------------------------------------------------------------------------
  65 // Finalization mix - force all bits of a hash block to avalanche
  66
  67
  68
  69 FORCE_INLINE uint64_t fmix ( uint64_t k )
  70 {
  71   k ^= k >> 33;
  72   k *= BIG_CONSTANT(0xff51afd7ed558ccd);
  73   k ^= k >> 33;
  74   k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
  75   k ^= k >> 33;
  76
  77   return k;
  78 }
  79
  80 //-----------------------------------------------------------------------------
  81
  82 void MurmurHash3_x64_128 ( const void * key, const int len,
  83                            const uint32_t seed, void * out )
  84 {
  85   const uint8_t * data = (const uint8_t*)key;
  86   const int nblocks = len / 16;
  87
  88   uint64_t h1 = seed;
  89   uint64_t h2 = seed;
  90
  91   uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
  92   uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
  93
  94   //----------
  95   // body
  96
  97   const uint64_t * blocks = (const uint64_t *)(data);
  98
  99   for(int i = 0; i < nblocks; i++)
 100   {
 101     uint64_t k1 = getblock(blocks,i*2+0);
 102     uint64_t k2 = getblock(blocks,i*2+1);
 103
 104     k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
 105
 106     h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
 107
 108     k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
 109
 110     h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
 111   }
 112
 113   //----------
 114   // tail
 115
 116   const uint8_t * tail = (const uint8_t*)(data + nblocks*16);
 117
 118   uint64_t k1 = 0;
 119   uint64_t k2 = 0;
 120
 121   switch(len & 15)
 122   {
 123   case 15: k2 ^= ((uint64_t) tail[14]) << 48;
 124   case 14: k2 ^= ((uint64_t) tail[13]) << 40;
 125   case 13: k2 ^= ((uint64_t) tail[12]) << 32;
 126   case 12: k2 ^= ((uint64_t) tail[11]) << 24;
 127   case 11: k2 ^= ((uint64_t) tail[10]) << 16;
 128   case 10: k2 ^= ((uint64_t) tail[ 9]) << 8;
 129   case  9: k2 ^= ((uint64_t) tail[ 8]) << 0;
 130            k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
 131
 132   case  8: k1 ^= ((uint64_t) tail[ 7]) << 56;
 133   case  7: k1 ^= ((uint64_t) tail[ 6]) << 48;
 134   case  6: k1 ^= ((uint64_t) tail[ 5]) << 40;
 135   case  5: k1 ^= ((uint64_t) tail[ 4]) << 32;
 136   case  4: k1 ^= ((uint64_t) tail[ 3]) << 24;
 137   case  3: k1 ^= ((uint64_t) tail[ 2]) << 16;
 138   case  2: k1 ^= ((uint64_t) tail[ 1]) << 8;
 139   case  1: k1 ^= ((uint64_t) tail[ 0]) << 0;
 140            k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
 141   };
 142
 143   //----------
 144   // finalization
 145
 146   h1 ^= len; h2 ^= len;
 147
 148   h1 += h2;
 149   h2 += h1;
 150
 151   h1 = fmix(h1);
 152   h2 = fmix(h2);
 153
 154   h1 += h2;
 155   h2 += h1;
 156
 157   ((uint64_t*)out)[0] = h1;
 158   ((uint64_t*)out)[1] = h2;
 159 }
 160
 161 //-----------------------------------------------------------------------------
 162