murmur3a

// SPDX-FileCopyrightText: 2025-2026 eaon <eaon@posteo.net>
// SPDX-License-Identifier: MIT

import gleam/bit_array
import gleam/int.{
  bitwise_and as and, bitwise_exclusive_or as xor, bitwise_or as or,
  bitwise_shift_left as shift_left, bitwise_shift_right as shift_right,
}
import gleam/list
import gleam/result

const c1: Int = 0xcc9e2d51

const c2: Int = 0x1b873593

const m1: Int = 0xffffffff

pub opaque type Hash {
  Hash(seed: Int, shift: Int, state: Int)
}

const default: Hash = Hash(seed: 0, shift: 0, state: 0)

/// Computes a 32 bit Murmur3 hash of the input string.
///
/// ## Examples
///
/// ```gleam
/// hash_string("murmur3a", 0)
/// // -> Hash(3521997819, 0, -391047908)
/// ```
pub fn hash_string(key: String, seed: Int) -> Hash {
  let assert Ok(hash) = hash_bytes(<<key:utf8>>, seed)

  hash
}

/// Computes a 32 bit Murmur3 hash of the supplied bit array.
///
/// Returns `Error(Nil)` if the bit array is not byte-aligned.
///
/// ## Examples
///
/// ```gleam
/// hash_bytes(<<"murmur3a">>, 0)
/// // -> Ok(Hash(3521997819, 0, -391047908))
/// ```
pub fn hash_bytes(key: BitArray, seed: Int) -> Result(Hash, Nil) {
  do_hash_bytes(Hash(..default, seed:), key)
  |> result.map(finalize(_, bit_array.byte_size(key)))
}

fn do_hash_bytes(hash: Hash, key: BitArray) -> Result(Hash, Nil) {
  case key {
    <<first, second, third, fourth, rest:bytes>> -> {
      let seed =
        first
        |> or(shift_left(second, 8))
        |> or(shift_left(third, 16))
        |> or(shift_left(fourth, 24))
        |> mix(hash.seed)
      do_hash_bytes(Hash(..hash, seed:), rest)
    }
    <<byte, rest:bytes>> ->
      hash_byte(hash, byte)
      |> do_hash_bytes(rest)
    <<>> -> Ok(hash)
    _ -> Error(Nil)
  }
}

/// Computes a 32 bit Murmur3 hash of the supplied list of integers.
///
/// **Note:** Values outside the 0–255 range will be truncated to their lowest
/// byte before hashing.
///
/// ## Examples
///
/// ```gleam
/// hash_ints([1, 2, 3], 0)
/// // -> Hash(0, 24, -2133732860)
/// ```
pub fn hash_ints(key: List(Int), seed: Int) -> Hash {
  let #(hash, length) =
    key
    |> list.fold(#(Hash(..default, seed:), 0), fn(acc, i) {
      let #(hash, length) = acc

      #(hash_byte(hash, and(i, 0xff)), length + 1)
    })

  finalize(hash, length)
}

fn hash_byte(hash: Hash, byte: Int) -> Hash {
  let state =
    byte
    |> shift_left(hash.shift)
    |> or(hash.state)

  case hash.shift {
    24 -> Hash(seed: mix(state, hash.seed), shift: 0, state: 0)
    _ -> Hash(..hash, shift: hash.shift + 8, state:)
  }
}

fn mix(state: Int, seed: Int) -> Int {
  state
  |> signed_multiply(c1)
  |> rotate_left(15)
  |> signed_multiply(c2)
  |> xor(seed)
  |> rotate_left(13)
  |> signed_multiply(5)
  |> int.add(0xe6546b64)
}

fn finalize(hash: Hash, length: Int) -> Hash {
  let state =
    case hash.state {
      0 -> hash.seed
      _ ->
        hash.state
        |> signed_multiply(c1)
        |> rotate_left(15)
        |> signed_multiply(c2)
        |> xor(hash.seed)
        |> and(m1)
    }
    |> xor(length)
  let state =
    shift_right(state, 16)
    |> xor(state)
    |> signed_multiply(0x85ebca6b)
    |> and(m1)
  let state =
    shift_right(state, 13)
    |> xor(state)
    |> signed_multiply(0xc2b2ae35)

  Hash(
    ..hash,
    state: shift_right(state, 16)
      |> and(0xffff)
      |> xor(state),
  )
}

/// Returns the 32 bit _signed_ integer digest of the hash.
///
/// Keep in mind that these values may return negative numbers!
///
/// ## Examples
///
/// ```gleam
/// hash_ints([1, 2, 3], 0)
/// |> int_digest
/// // -> -2133732860
/// ```
pub fn int_digest(hash: Hash) -> Int {
  hash.state
}

/// Returns 32 bit digest of the hash as a BitArray.
///
/// ## Examples
///
/// ```gleam
/// hash_string("murmur3a", 0)
/// |> bit_array_digest
/// // -> <<232, 177, 21, 28>>
/// ```
pub fn bit_array_digest(hash: Hash) -> BitArray {
  <<int_digest(hash):32>>
}

/// Returns a hexadecimal digest of the hash.
///
/// ## Examples
///
/// ```gleam
/// hash_string("murmur3a", 0)
/// |> hex_digest
/// // -> "E8B1151C"
/// ```
pub fn hex_digest(hash: Hash) -> String {
  hash
  |> bit_array_digest
  |> bit_array.base16_encode
}

const int32_max: Int = 0x7fffffff

const int32_modulus: Int = 0x100000000

@external(javascript, "./murmur3a_ffi.mjs", "signed_multiply")
fn signed_multiply(m: Int, n: Int) -> Int {
  let result = and(m * n, m1)

  case result > int32_max {
    True -> result - int32_modulus
    False -> result
  }
}

fn rotate_left(n: Int, shift: Int) {
  let n = and(n, m1)

  shift_left(n, shift)
  |> and(m1)
  |> or(shift_right(n, 32 - shift))
}