/*
  Fash64: Douglas Crockford (2017-02-02)
  64-bit hash that uses the high 64 bits of a 128-bit product for feedback.

  Notes:
  - Requires a way to get the high half of a 64x64->128 multiply.
  - Uses __uint128_t when available; otherwise uses MSVC _umul128.
*/

#include <stdint.h>
#include <stddef.h>

typedef struct fash64_state {
  uint64_t result;
  uint64_t sum;
} fash64_state;

enum {
  FASH64_PRIME_11 = 11111111111111111027ull,
  FASH64_PRIME_8  = 8888888888888888881ull,
  FASH64_PRIME_3  = 3333333333333333271ull
};

static inline void fash64_mul_hi_lo(uint64_t a, uint64_t b, uint64_t *hi, uint64_t *lo)
{
#if defined(__SIZEOF_INT128__)
  __uint128_t p = (__uint128_t)a * (__uint128_t)b;
  *lo = (uint64_t)p;
  *hi = (uint64_t)(p >> 64);
#elif defined(_MSC_VER) && defined(_M_X64)
  *lo = _umul128(a, b, hi);
#else
  /* Portable fallback (no 128-bit type, no _umul128). */
  uint64_t a0 = (uint32_t)a;
  uint64_t a1 = a >> 32;
  uint64_t b0 = (uint32_t)b;
  uint64_t b1 = b >> 32;

  uint64_t p00 = a0 * b0;
  uint64_t p01 = a0 * b1;
  uint64_t p10 = a1 * b0;
  uint64_t p11 = a1 * b1;

  uint64_t mid = (p00 >> 32) + (uint32_t)p01 + (uint32_t)p10;
  *lo = (p00 & 0xffffffffull) | (mid << 32);
  *hi = p11 + (p01 >> 32) + (p10 >> 32) + (mid >> 32);
#endif
}

static inline void fash64_begin(fash64_state *s)
{
  s->result = (uint64_t)FASH64_PRIME_8;
  s->sum = (uint64_t)FASH64_PRIME_3;
}

static inline void fash64_word(fash64_state *s, uint64_t word)
{
  uint64_t high, low;
  uint64_t mixed = s->result ^ word;

  fash64_mul_hi_lo(mixed, (uint64_t)FASH64_PRIME_11, &high, &low);

  s->sum += high;
  s->result = low ^ s->sum;
}

static inline void fash64_block(fash64_state *s, const uint64_t *block, size_t word_count)
{
  for (size_t i = 0; i < word_count; i++) fash64_word(s, block[i]);
}

static inline uint64_t fash64_end(const fash64_state *s)
{
  return s->result;
}

/* Convenience one-shot helper */
static inline uint64_t fash64_hash_words(const uint64_t *words, size_t word_count, uint64_t extra_word)
{
  fash64_state s;
  fash64_begin(&s);
  fash64_block(&s, words, word_count);
  fash64_word(&s, extra_word);
  return fash64_end(&s);
}

static inline uint64_t fash64_hash_one(uint64_t word)
{
  uint64_t high, low;
  uint64_t mixed = (uint64_t)FASH64_PRIME_8 ^ word;
  fash64_mul_hi_lo(mixed, (uint64_t)FASH64_PRIME_11, &high, &low);
  return low ^ ((uint64_t)FASH64_PRIME_3 + high);
}