// MurmurHash3 (x86 32-bit) over UTF-16 code units, the hash used by hashwheel.
//
// MoonBit's `UInt` is a wrapping 32-bit integer with logical shifts, which is
// exactly the arithmetic javascript performs on `Math.imul` results and
// values coerced with `>>> 0`.  MoonBit strings are indexed by UTF-16 code
// unit, like javascript strings, so this produces bit-identical hashes.

///|
/// Rotate the 32 bits of `x` left by `n` bits (javascript
/// `(x << n) | (x >>> (32 - n))`).
fn rotl(x : UInt, n : Int) -> UInt {
  (x << n) | (x >> (32 - n))
}

///|
/// MurmurHash3 (x86 32-bit) of the UTF-16 code units of `s`, as an unsigned
/// 32-bit value.
///
/// Two code units (four bytes) are consumed per round, the remainder is mixed
/// in as a tail, and the finalization mix spreads the bits out.  The hash does
/// not have to be perfect, just well distributed; the ring takes it modulo
/// `range`.
///
/// The values below are the ones the javascript `hashwheel` package returns
/// for the same inputs:
///
/// ```mbt check
/// test {
///   inspect(@hashwheel.murmur3(""), content="0")
///   inspect(@hashwheel.murmur3("a"), content="1009084850")
///   inspect(@hashwheel.murmur3("abc"), content="1968171120")
///   inspect(@hashwheel.murmur3("resourceName"), content="2023144987")
///   inspect(@hashwheel.murmur3("🌟"), content="2007303233")
/// }
/// ```
pub fn murmur3(s : String) -> UInt {
  let c1 = 0xCC9E2D51U
  let c2 = 0x1B873593U
  let units = s.code_units()
  let len = units.length()
  let mut h = 0U
  let mut i = 0
  // main loop: 4 bytes (two code units) at a time, little endian
  while i + 1 < len {
    let mut k = units[i].to_int().reinterpret_as_uint() |
      (units[i + 1].to_int().reinterpret_as_uint() << 16)
    k = k * c1
    k = rotl(k, 15)
    k = k * c2
    h = h ^ k
    h = rotl(h, 13)
    h = h * 5U + 0xE6546B64U
    i = i + 2
  }
  // tail: one leftover code unit
  if i < len {
    let mut k = units[i].to_int().reinterpret_as_uint()
    k = k * c1
    k = rotl(k, 15)
    k = k * c2
    h = h ^ k
  }
  // finalization mix
  h = h ^ len.reinterpret_as_uint()
  h = h ^ (h >> 16)
  h = h * 0x85EBCA6BU
  h = h ^ (h >> 13)
  h = h * 0xC2B2AE35U
  h = h ^ (h >> 16)
  h
}