src/lib/murmurhash3.c

f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi/* MurmurHash3 was written by Austin Appleby, and is placed in the public
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi   domain. The author hereby disclaims copyright to this source code.
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi   Note - The x86 and x64 versions do _not_ produce the same results, as the
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi   algorithms are optimized for their respective platforms. You can still
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi   compile and run any of them on any platform, but your performance with the
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi   non-native version will be less than optimal.
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
c9a7c4d24386315524222f3da805a693fb3cd3bfMartti Rannanjärvi   Adapted for Dovecot by Aki Tuomi <aki.tuomi@dovecot.fi> 2017-11-27
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi*/
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#include "lib.h"
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#include "murmurhash3.h"
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#define ROTL32(x,y) bits_rotl32(x,y)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#define ROTL64(x,y) bits_rotl64(x,y)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#define BIG_CONSTANT(x) (x##LLU)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi//-----------------------------------------------------------------------------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi// Block read - if your platform needs to do endian-swapping or can only
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi// handle aligned reads, do the conversion here
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomistatic inline uint32_t getblock32(const uint32_t *p, int i)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  return p[i];
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi//-----------------------------------------------------------------------------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi// Finalization mix - force all bits of a hash block to avalanche
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomistatic inline uint32_t fmix32(uint32_t h)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h ^= h >> 16;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h *= 0x85ebca6b;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h ^= h >> 13;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h *= 0xc2b2ae35;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h ^= h >> 16;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  return h;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi//----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomivoid murmurhash3_32 (const void *key, size_t len, uint32_t seed,
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi             unsigned char out[STATIC_ARRAY MURMURHASH3_32_RESULTBYTES])
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *data = (const uint8_t *)key;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  size_t nblocks = len / 4;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t h1 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c1 = 0xcc9e2d51;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c2 = 0x1b873593;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // body
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint32_t *blocks = (const uint32_t *)data;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  for(size_t i = 0; i < nblocks; i++)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint32_t k1 = getblock32(blocks,i);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k1 *= c1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k1 = ROTL32(k1,15);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k1 *= c2;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h1 = ROTL32(h1,13);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h1 = h1*5+0xe6546b64;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  }
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // tail
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *tail = (const uint8_t *)(data + nblocks*4);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t k1 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  switch(len & 3)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 3: k1 ^= tail[2] << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi          /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 2: k1 ^= tail[1] << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi          /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 1: k1 ^= tail[0];
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi          k1 *= c1; k1 = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  };
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // finalization
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 ^= len;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 = fmix32(h1);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  memcpy(out, &h1, sizeof(h1));
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi//-----------------------------------------------------------------------------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#ifdef _LP64
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomistatic inline uint64_t getblock64(const uint64_t *p, int i)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  return p[i];
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomistatic inline uint64_t fmix64(uint64_t k)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  k ^= k >> 33;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  k *= BIG_CONSTANT(0xff51afd7ed558ccd);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  k ^= k >> 33;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  k *= BIG_CONSTANT(0xc4ceb9fe1a85ec53);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  k ^= k >> 33;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  return k;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomivoid murmurhash3_128(const void *key, size_t len, uint32_t seed,
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi             unsigned char out[STATIC_ARRAY MURMURHASH3_128_RESULTBYTES])
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *data = (const uint8_t *)key;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  size_t nblocks = len / 16;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint64_t h1 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint64_t h2 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint64_t c1 = BIG_CONSTANT(0x87c37b91114253d5);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint64_t c2 = BIG_CONSTANT(0x4cf5ad432745937f);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // body
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint64_t *blocks = (const uint64_t *)data;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  for(size_t i = 0; i < nblocks; i++)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint64_t k1 = getblock64(blocks,i*2+0);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint64_t k2 = getblock64(blocks,i*2+1);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h1 = ROTL64(h1,27); h1 += h2; h1 = h1*5+0x52dce729;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h2 = ROTL64(h2,31); h2 += h1; h2 = h2*5+0x38495ab5;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  }
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // tail
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *tail = (const uint8_t *)(data + nblocks*16);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint64_t k1 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint64_t k2 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  switch(len & 15)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 15: k2 ^= ((uint64_t)tail[14]) << 48;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 14: k2 ^= ((uint64_t)tail[13]) << 40;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 13: k2 ^= ((uint64_t)tail[12]) << 32;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 12: k2 ^= ((uint64_t)tail[11]) << 24;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 11: k2 ^= ((uint64_t)tail[10]) << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 10: k2 ^= ((uint64_t)tail[ 9]) << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  9: k2 ^= ((uint64_t)tail[ 8]) << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k2 *= c2; k2  = ROTL64(k2,33); k2 *= c1; h2 ^= k2;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  8: k1 ^= ((uint64_t)tail[ 7]) << 56;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  7: k1 ^= ((uint64_t)tail[ 6]) << 48;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  6: k1 ^= ((uint64_t)tail[ 5]) << 40;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  5: k1 ^= ((uint64_t)tail[ 4]) << 32;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  4: k1 ^= ((uint64_t)tail[ 3]) << 24;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  3: k1 ^= ((uint64_t)tail[ 2]) << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  2: k1 ^= ((uint64_t)tail[ 1]) << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  1: k1 ^= ((uint64_t)tail[ 0]) << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k1 *= c1; k1  = ROTL64(k1,31); k1 *= c2; h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  };
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // finalization
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 ^= len; h2 ^= len;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 += h2;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 += h1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 = fmix64(h1);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 = fmix64(h2);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 += h2;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 += h1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  memcpy(out, &h1, sizeof(h1));
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  memcpy(out+sizeof(h1), &h2, sizeof(h2));
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#else
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomivoid murmurhash3_128(const void *key, size_t len, uint32_t seed,
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi             unsigned char out[STATIC_ARRAY MURMURHASH3_128_RESULTBYTES])
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi{
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *data = (const uint8_t *)key;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  size_t nblocks = len / 16;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t h1 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t h2 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t h3 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t h4 = seed;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c1 = 0x239b961b;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c2 = 0xab0e9789;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c3 = 0x38b34ae5;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t c4 = 0xa1e38b93;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // body
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint32_t *blocks = (const uint32_t *)data;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  for(size_t i = 0 ; i < nblocks; i++)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint32_t k1 = getblock32(blocks,i*4+0);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint32_t k2 = getblock32(blocks,i*4+1);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint32_t k3 = getblock32(blocks,i*4+2);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    uint32_t k4 = getblock32(blocks,i*4+3);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h1 = ROTL32(h1,19); h1 += h2; h1 = h1*5+0x561ccd1b;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h2 = ROTL32(h2,17); h2 += h3; h2 = h2*5+0x0bcaa747;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h3 = ROTL32(h3,15); h3 += h4; h3 = h3*5+0x96cd1c35;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi    h4 = ROTL32(h4,13); h4 += h1; h4 = h4*5+0x32ac3b17;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  }
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // tail
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  const uint8_t *tail = (const uint8_t *)(data + nblocks*16);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t k1 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t k2 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t k3 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  uint32_t k4 = 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  switch(len & 15)
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  {
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 15: k4 ^= tail[14] << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 14: k4 ^= tail[13] << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 13: k4 ^= tail[12] << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k4 *= c4; k4  = ROTL32(k4,18); k4 *= c1; h4 ^= k4;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 12: k3 ^= tail[11] << 24;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 11: k3 ^= tail[10] << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case 10: k3 ^= tail[ 9] << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  9: k3 ^= tail[ 8] << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k3 *= c3; k3  = ROTL32(k3,17); k3 *= c4; h3 ^= k3;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  8: k2 ^= tail[ 7] << 24;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  7: k2 ^= tail[ 6] << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  6: k2 ^= tail[ 5] << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  5: k2 ^= tail[ 4] << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k2 *= c2; k2  = ROTL32(k2,16); k2 *= c3; h2 ^= k2;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  4: k1 ^= tail[ 3] << 24;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  3: k1 ^= tail[ 2] << 16;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  2: k1 ^= tail[ 1] << 8;
0351233834ffe10f4e64d12064680d4b01ffc138Martti Rannanjärvi           /* fall through */
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  case  1: k1 ^= tail[ 0] << 0;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi           k1 *= c1; k1  = ROTL32(k1,15); k1 *= c2; h1 ^= k1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  };
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  //----------
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  // finalization
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 ^= len; h2 ^= len; h3 ^= len; h4 ^= len;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 += h2; h1 += h3; h1 += h4;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 += h1; h3 += h1; h4 += h1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 = fmix32(h1);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 = fmix32(h2);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h3 = fmix32(h3);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h4 = fmix32(h4);
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h1 += h2; h1 += h3; h1 += h4;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  h2 += h1; h3 += h1; h4 += h1;
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  memcpy(out, &h1, sizeof(h1));
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi  memcpy(out+sizeof(h1), &h2, sizeof(h2));
aa6cd0d62ab34864c476c7fb3344e8e4ba035261Aki Tuomi  memcpy(out+sizeof(h1)*2, &h3, sizeof(h3));
aa6cd0d62ab34864c476c7fb3344e8e4ba035261Aki Tuomi  memcpy(out+sizeof(h1)*3, &h4, sizeof(h4));
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi}
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi
f6de86ea29e87fba001b6231d38a4c51e8a5c543Aki Tuomi#endif