murmur3a

// SPDX-FileCopyrightText: 2025 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/string

const c1: Int = 0xcc9e2d51

const c2: Int = 0x1b873593

const m1: Int = 0xffffffff

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

/// 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.map(string.utf_codepoint_to_int)
  |> hash_ints(seed)
}

/// 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(seed:, shift: 0, state: 0), hash_chunk)
  |> finalize(list.length(key))
}

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(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
}

@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_min: Int = -2_147_483_648

@target(erlang)
fn signed_multiply(m: Int, n: Int) -> Int {
  case m * n {
    amount if amount > int32_max -> {
      overflow(amount)
    }
    amount if amount < int32_min -> {
      overflow(int.subtract(amount, int32_min))
    }
    amount -> amount
  }
}

@target(erlang)
fn overflow(overflow: Int) -> Int {
  int.subtract(overflow, int32_min) % 0x100000000 + int32_min
}

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

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