murmur3.c

   1 /*
   2  * based on code written by Austin Appleby and placed in the public domain
   3  */
   4
   5 /* TODO: x86 and big endian */
   6
   7 #include <stdint.h>
   8
   9 #define ROTL64(x,n) (((x) << (n)) | ((x) >> (64 - (n))))
  10
  11 static inline uint64_t
  12 getblock64(const uint64_t *p, int i)
  13 {
  14         return p[i];
  15 }
  16
  17 static inline uint64_t
  18 fmix64(uint64_t k)
  19 {
  20         k ^= k >> 33;
  21         k *= 0xff51afd7ed558ccdLLU;
  22         k ^= k >> 33;
  23         k *= 0xc4ceb9fe1a85ec53LLU;
  24         k ^= k >> 33;
  25         return k;
  26 }
  27
  28 void
  29 murmurhash3_x64_128(const void *key, const int len, const uint32_t seed, void *out)
  30 {
  31         const uint8_t *data = (const uint8_t *)key;
  32         const uint64_t *blocks = (const uint64_t *)(data);
  33         const int nblocks = len / 16;
  34         const uint64_t c1 = 0x87c37b91114253d5LLU;
  35         const uint64_t c2 = 0x4cf5ad432745937fLLU;
  36         const uint8_t *tail = (const uint8_t *)(data + nblocks * 16);
  37         uint64_t h1 = seed;
  38         uint64_t h2 = seed;
  39         uint64_t k1;
  40         uint64_t k2;
  41         int i;
  42
  43         for(i = 0 ; i < nblocks ; i++) {
  44                 k1 = getblock64(blocks, i * 2 + 0);
  45                 k2 = getblock64(blocks, i * 2 + 1);
  46                 k1 *= c1;
  47                 k1  = ROTL64(k1, 31);
  48                 k1 *= c2;
  49                 h1 ^= k1;
  50                 h1 = ROTL64(h1, 27);
  51                 h1 += h2;
  52                 h1 = h1 * 5 + 0x52dce729;
  53                 k2 *= c2;
  54                 k2  = ROTL64(k2, 33);
  55                 k2 *= c1;
  56                 h2 ^= k2;
  57                 h2 = ROTL64(h2, 31);
  58                 h2 += h1;
  59                 h2 = h2 * 5 + 0x38495ab5;
  60         }
  61
  62         k1 = 0;
  63         k2 = 0;
  64         switch(len & 15) {
  65         case 15:
  66                 k2 ^= ((uint64_t)tail[14]) << 48;
  67         case 14:
  68                 k2 ^= ((uint64_t)tail[13]) << 40;
  69         case 13:
  70                 k2 ^= ((uint64_t)tail[12]) << 32;
  71         case 12:
  72                 k2 ^= ((uint64_t)tail[11]) << 24;
  73         case 11:
  74                 k2 ^= ((uint64_t)tail[10]) << 16;
  75         case 10:
  76                 k2 ^= ((uint64_t)tail[9]) << 8;
  77         case  9:
  78                 k2 ^= ((uint64_t)tail[8]) << 0;
  79                 k2 *= c2;
  80                 k2  = ROTL64(k2, 33);
  81                 k2 *= c1;
  82                 h2 ^= k2;
  83         case  8:
  84                 k1 ^= ((uint64_t)tail[7]) << 56;
  85         case  7:
  86                 k1 ^= ((uint64_t)tail[6]) << 48;
  87         case  6:
  88                 k1 ^= ((uint64_t)tail[5]) << 40;
  89         case  5:
  90                 k1 ^= ((uint64_t)tail[4]) << 32;
  91         case  4:
  92                 k1 ^= ((uint64_t)tail[3]) << 24;
  93         case  3:
  94                 k1 ^= ((uint64_t)tail[2]) << 16;
  95         case  2:
  96                 k1 ^= ((uint64_t)tail[1]) << 8;
  97         case  1:
  98                 k1 ^= ((uint64_t)tail[0]) << 0;
  99                 k1 *= c1;
 100                 k1  = ROTL64(k1, 31);
 101                 k1 *= c2;
 102                 h1 ^= k1;
 103         };
 104
 105         h1 ^= len;
 106         h2 ^= len;
 107         h1 += h2;
 108         h2 += h1;
 109         h1 = fmix64(h1);
 110         h2 = fmix64(h2);
 111         h1 += h2;
 112         h2 += h1;
 113
 114         ((uint64_t*)out)[0] = h1;
 115         ((uint64_t*)out)[1] = h2;
 116 }
 117