#include "libmin.h"

/**
 * `murmurhash.h' - murmurhash
 *
 * copyright (c) 2014-2022 joseph werle <joseph.werle@gmail.com>
 */

/**
 * Returns a murmur hash of `key' based on `seed'
 * using the MurmurHash3 algorithm
 */

uint32_t murmurhash(const char *, uint32_t, uint32_t);

/**
 * `murmurhash.h' - murmurhash
 *
 * copyright (c) 2014-2022 joseph werle <joseph.werle@gmail.com>
 */

uint32_t
murmurhash (const char *key, uint32_t len, uint32_t seed)
{
  uint32_t c1 = 0xcc9e2d51;
  uint32_t c2 = 0x1b873593;
  uint32_t r1 = 15;
  uint32_t r2 = 13;
  uint32_t m = 5;
  uint32_t n = 0xe6546b64;
  uint32_t h = 0;
  uint32_t k = 0;
  uint8_t *d = (uint8_t *) key; // 32 bit extract from `key'
  const uint32_t *chunks = NULL;
  const uint8_t *tail = NULL; // tail - last 8 bytes
  int i = 0;
  int l = len / 4; // chunk length

  h = seed;

  chunks = (const uint32_t *) (d + l * 4); // body
  tail = (const uint8_t *) (d + l * 4); // last 8 byte chunk of `key'

  // for each 4 byte chunk of `key'
  for (i = -l; i != 0; ++i) {
    // next 4 byte chunk of `key'
    k = chunks[i];

    // encode next 4 byte chunk of `key'
    k *= c1;
    k = (k << r1) | (k >> (32 - r1));
    k *= c2;

    // append to hash
    h ^= k;
    h = (h << r2) | (h >> (32 - r2));
    h = h * m + n;
  }

  k = 0;

  // remainder
  switch (len & 3) { // `len % 4'
    case 3: k ^= (tail[2] << 16);
    case 2: k ^= (tail[1] << 8);

    case 1:
      k ^= tail[0];
      k *= c1;
      k = (k << r1) | (k >> (32 - r1));
      k *= c2;
      h ^= k;
  }

  h ^= len;

  h ^= (h >> 16);
  h *= 0x85ebca6b;
  h ^= (h >> 13);
  h *= 0xc2b2ae35;
  h ^= (h >> 16);

  return h;
}

int
main(void)
{
    uint32_t seed = 0;

    {
      const char *key = "kinkajou"; // 0xb6d99cf8
      uint32_t hash = murmurhash(key, (uint32_t)libmin_strlen(key), seed);
      libmin_printf("murmurhash(\"%s\") = 0x%x\n", key, hash);
    }

    {
      const char *key = "The bringup-bench benchmark MURMUR made this.";
      uint32_t hash = murmurhash(key, (uint32_t)libmin_strlen(key), seed);
      libmin_printf("murmurhash(\"%s\") = 0x%x\n", key, hash);
    }

    {
      const char *key = "It has to start somewhere, it has to start sometime, what better place than here? What better time than now?";
      uint32_t hash = murmurhash(key, (uint32_t)libmin_strlen(key), seed);
      libmin_printf("murmurhash(\"%s\") = 0x%x\n", key, hash);
    }

    libmin_success();
    return 0;
}
