//-----------------------------------------------------------------------------
// MurmurHash3 was written by Austin Appleby, and is placed in the public
// domain. The author hereby disclaims copyright to this source code.

// Note - The x86 and x64 versions do _not_ produce the same results, as the
// algorithms are optimized for their respective platforms. You can still
// compile and run any of them on any platform, but your performance with the
// non-native version will be less than optimal.

#include <stdint.h>
#include <inttypes.h>

//-----------------------------------------------------------------------------
// Platform-specific functions and macros

#ifndef __always_inline
#  if defined(__GNUC__) || defined(__clang__) || defined(__ICC)
#    define __always_inline __attribute__((always_inline)) inline
#  elif defined(_MSC_VER)
#    define __always_inline __forceinline
#  else
#    define __always_inline inline
#  endif
#endif

static __always_inline uint64_t rotl64 ( uint64_t x, int8_t r )
{
  return (x << r) | (x >> (64 - r));
}

#define	ROTL32(x,y)	rotl32(x,y)
#define ROTL64(x,y)	rotl64(x,y)

#define slipcompress() \
        h1 += h2; h2 = ROTL64(h2, 13); \
        h2 ^= h1; h1 = ROTL64(h1, 32); \
        h1 += h2; h2 = ROTL64(h2, 17); \
        h2 ^= h1; h1 = ROTL64(h1, 21); \

  static const uint64_t c[64] = {
        0x4cecc78634c53084, 0x0c766e0ff64ae5e1, 0xde817641bdf2bd9f, 0x4ead9d56d7178e4f,
        0x9b557f22edf99c9c, 0xac3f1f750a7af01b, 0x020fa0f3bf003147, 0x37c1fc48794cbea6,
        0xc2e31ee1eb63d9a4, 0xce7ca4e4165559d7, 0xbce8bb43ca4d01fb, 0xc41a8295fd9985ad,
        0x67658f62acea71f7, 0x36757e6c65391e83, 0xd2533aeda908a387, 0xe9ece76df432e59b,
        0x61bf1d9c60f1c9a4, 0xdd5f2d5c98bf627c, 0x783d5d3a36d58aa1, 0x01ba3fc3ff4aa0a9,
        0x813f4630d5505305, 0x06e26ba20d4540ed, 0xc8d7242341e7799b, 0x1a5950ff63344e50,
        0x37afd8e7e08490e6, 0x2a1ecce6ffaea8ec, 0x2995af827fb9b9cc, 0x66e9049bbcd98c04,
        0x1a5205d34d62b511, 0xd058576900ae4db9, 0x471f5ab6fa38581e, 0x5326521fd26d230d,
        0xa9d33cb5ca3aad5d, 0xbbdfc541282c5cfa, 0x95e4e38929ec2abb, 0x3e1a7fec25f41adc,
        0x2439f5f5a2fea437, 0xb0f793f6782510cd, 0x411f3230c6790555, 0xbe7288179509a346,
        0xa56add5d4dc4c5c9, 0xbbfefebd664a592c, 0xa702e75b897902f0, 0xeffd47eab564273e,
        0xaf0366f902358f90, 0x2031475ac27c7742, 0x8703032613891cd2, 0xdb805105d4c29614,
        0x48408454f2b1966a, 0x6e1705d7ae1b26e3, 0x7feb956af5c743d4, 0x4e6f5b1a231bfc12,
        0x1c5666a86397c829, 0x561c8767d827b622, 0x46d2bad312b3f8c2, 0x2dd64cc213e0ee3b,
        0x70af8c36ade441da, 0x4217c8dd74c52f0b, 0x4644e2909a8dcb07, 0x71da9faf994db739,
        0xd4d80f368932e971, 0xb81274a473068edb, 0xba1924cb62318aa3, 0x10361a1838d26ca9
};

static __always_inline void MurmurHash4(const void *key, const size_t len,
                                        uint64_t h1, uint64_t h2, void *out)
{
  const uint8_t *data = (const uint8_t*)key;
  const size_t nblocks = len / 16;
  int i;
  uint64_t k1 = 0xef237da42e8e9d0b, k2 = 0xb86e0e09d6987c17;
 
  //----------
  // body
  const uint64_t *blocks = (const uint64_t *)(data);

  for(i = 0; i < nblocks; i++)
  {
    k1 ^= blocks[i*2+0];
    k2 ^= blocks[i*2+1];

    k1 = ROTL64(k1,31);
    k1 *= c[__builtin_popcount(k1)];
    k1 += 0x8f8379b30168a6d7;
    h1 ^= k1;
    h1 = ROTL64(h1, 7);

    k2 = ROTL64(k2,27);
    k2 *= c[__builtin_popcount(k2)];
    k2 += 0x36321f85821f2b3e;
    h2 ^= k2;
    h2 = ROTL64(h2, 9);
  }

  //----------
  // tail
  const uint8_t *tail = (const uint8_t*)(data + nblocks*16);

  switch(len & 15)
  {
  case 15: k2 ^= (uint64_t)(tail[14]) << 48;
  case 14: k2 ^= (uint64_t)(tail[13]) << 40;
  case 13: k2 ^= (uint64_t)(tail[12]) << 32;
  case 12: k2 ^= (uint64_t)(tail[11]) << 24;
  case 11: k2 ^= (uint64_t)(tail[10]) << 16;
  case 10: k2 ^= (uint64_t)(tail[ 9]) << 8;
  case  9: k2 ^= (uint64_t)(tail[ 8]) << 0;
    k2 = ROTL64(k2,27);
    k2 *= c[__builtin_popcount(k2)]; 
    k2 += 0x36321f85821f2b3e;
    h2 ^= k2;

  case  8: k1 ^= (uint64_t)(tail[ 7]) << 56;
  case  7: k1 ^= (uint64_t)(tail[ 6]) << 48;
  case  6: k1 ^= (uint64_t)(tail[ 5]) << 40;
  case  5: k1 ^= (uint64_t)(tail[ 4]) << 32;
  case  4: k1 ^= (uint64_t)(tail[ 3]) << 24;
  case  3: k1 ^= (uint64_t)(tail[ 2]) << 16;
  case  2: k1 ^= (uint64_t)(tail[ 1]) << 8;
  case  1: k1 ^= (uint64_t)(tail[ 0]) << 0;
    k1 = ROTL64(k1,31);
    k1 *= c[__builtin_popcount(k1)];
    k1 += 0x8f8379b30168a6d7;
    h1 ^= k1; 
  };

  //----------
  // finalization
  h1 ^= len;
  h1 *= c[h2 % 64];
  h2 *= c[h1 % 64];
  slipcompress();
  h2 ^= 0xFF;
  slipcompress();

  ((uint64_t*)out)[0] = h1;
  ((uint64_t*)out)[1] = h2;
}