/// Deterministic 256-bit digest implementation.
///
/// The mixer is intentionally dependency-free so the core package works on
/// every MoonBit backend. It is designed for content addressing and corruption
/// detection, not password storage or adversarial cryptography. Applications
/// requiring cryptographic authentication should wrap the manifest in a signed
/// envelope.

fn rotate_left(x : UInt, n : Int) -> UInt {
  (x << n) | (x >> (32 - n))
}

fn lane_seed(i : Int) -> UInt {
  match i {
    0 => 0x243f6a88U
    1 => 0x85a308d3U
    2 => 0x13198a2eU
    _ => 0x03707344U
  }
}

fn mix_lane(state : UInt, byte : UInt, index : Int, lane : Int) -> UInt {
  let salt = (index.reinterpret_as_uint() + 0x9e3779b9U * (lane + 1).reinterpret_as_uint())
  let x = state ^ (byte + salt)
  let y = x * 0x85ebca6bU + 0xc2b2ae35U
  rotate_left(y ^ (y >> 13), (lane * 7 + index) % 31 + 1)
}

fn digest_lanes(data : Array[Byte]) -> Array[UInt] {
  let lanes = [lane_seed(0), lane_seed(1), lane_seed(2), lane_seed(3)]
  let mut index = 0
  for byte in data {
    let b = byte.to_int().reinterpret_as_uint()
    lanes[0] = mix_lane(lanes[0], b, index, 0)
    lanes[1] = mix_lane(lanes[1], b ^ 0xa5U, index, 1)
    lanes[2] = mix_lane(lanes[2], b ^ 0x5aU, index, 2)
    lanes[3] = mix_lane(lanes[3], b + 17U, index, 3)
    index = index + 1
  }
  for i in 0..<4 {
    let v = lanes[i]
    lanes[i] = mix_lane(v, data.length().reinterpret_as_uint(), index + i, i)
  }
  lanes
}

fn hex_digit(n : UInt) -> String {
  match n {
    0U => "0"
    1U => "1"
    2U => "2"
    3U => "3"
    4U => "4"
    5U => "5"
    6U => "6"
    7U => "7"
    8U => "8"
    9U => "9"
    10U => "a"
    11U => "b"
    12U => "c"
    13U => "d"
    14U => "e"
    _ => "f"
  }
}

fn uint_hex(x : UInt) -> String {
  let out = StringBuilder::new()
  for shift = 28; shift >= 0; shift = shift - 4 {
    out.write_string(hex_digit((x >> shift) & 0xfU))
  }
  out.to_string()
}

pub fn digest_bytes(data : Array[Byte]) -> String {
  let lanes = digest_lanes(data)
  uint_hex(lanes[0]) + uint_hex(lanes[1]) + uint_hex(lanes[2]) + uint_hex(lanes[3])
}

pub fn digest_string(value : String) -> String {
  digest_bytes(value.to_bytes().to_array())
}

pub fn digest_equal(left : String, right : String) -> Bool {
  if left.length() != right.length() { return false }
  let mut same = true
  for i in 0.. String {
  digest_string(left + ":" + right)
}

pub fn merkle_root(digests : Array[String]) -> String {
  if digests.length() == 0 { return digest_string("") }
  let mut level = digests.copy()
  while level.length() > 1 {
    let next = []
    let mut i = 0
    while i < level.length() {
      let right = if i + 1 < level.length() { level[i + 1] } else { level[i] }
      next.push(digest_pair(level[i], right))
      i = i + 2
    }
    level = next
  }
  level[0]
}

pub fn merkle_proof(digests : Array[String], index : Int) -> Array[(String, Bool)] {
  let proof = []
  if index < 0 || index >= digests.length() { return proof }
  let mut level = digests.copy()
  let mut cursor = index
  while level.length() > 1 {
    let sibling = if cursor % 2 == 0 {
      if cursor + 1 < level.length() { cursor + 1 } else { cursor }
    } else { cursor - 1 }
    proof.push((level[sibling], cursor % 2 != 0))
    let next = []
    let mut i = 0
    while i < level.length() {
      let r = if i + 1 < level.length() { level[i + 1] } else { level[i] }
      next.push(digest_pair(level[i], r))
      i = i + 2
    }
    level = next
    cursor = cursor / 2
  }
  proof
}

pub fn verify_merkle_proof(leaf : String, proof : Array[(String, Bool)], root : String) -> Bool {
  let mut current = leaf
  for pair in proof {
    let sibling = pair.0
    let sibling_left = pair.1
    current = if sibling_left { digest_pair(sibling, current) } else { digest_pair(current, sibling) }
  }
  digest_equal(current, root)
}