murmur3a

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

import gleam/bit_array
import gleam/function
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/string

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 {
  key
  |> string.to_utf_codepoints
  |> list.fold(
    #(Hash(..default, seed:), 0),
    make_fold(string.utf_codepoint_to_int),
  )
  |> finalize
}

/// Computes a 32 bit Murmur3 hash of the supplied list of integers.
///
/// ## Examples
///
/// ```gleam
/// hash_ints([1, 2, 3], 0)
/// // -> Hash(0, 24, -2133732860)
/// ```
pub fn hash_ints(key: List(Int), seed: Int) -> Hash {
  key
  |> list.fold(#(Hash(..default, seed:), 0), make_fold(function.identity))
  |> finalize
}

fn hash_chunk(hash: Hash, chunk: Int) -> Hash {
  let state =
    chunk
    |> and(0xff)
    |> 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(input: #(Hash, Int)) -> Hash {
  let #(hash, length) = input
  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
}

@target(javascript)
@external(javascript, "./murmur3a_ffi.mjs", "signed_multiply")
fn signed_multiply(m: Int, n: Int) -> Int

@target(erlang)
const int32_max: Int = 0x7fffffff

@target(erlang)
const int32_modulus: Int = 0x100000000

@target(erlang)
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))
}

fn make_fold(transform: fn(a) -> Int) -> fn(#(Hash, Int), a) -> #(Hash, Int) {
  fn(acc: #(Hash, Int), a) {
    let #(hash, length) = acc

    #(hash_chunk(hash, transform(a)), length + 1)
  }
}