///|
/// MD5 message-digest (RFC 1321), implemented from the specification in
/// pure MoonBit. Deterministic and dependency-free so DIGEST-MD5 works on
/// every backend.
let md5_shifts : Array[Int] = [
  7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9,
  14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23,
  4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21,
]

///|
let md5_k : Array[UInt] = [
  0xd76aa478U, 0xe8c7b756U, 0x242070dbU, 0xc1bdceeeU, 0xf57c0fafU, 0x4787c62aU, 0xa8304613U,
  0xfd469501U, 0x698098d8U, 0x8b44f7afU, 0xffff5bb1U, 0x895cd7beU, 0x6b901122U, 0xfd987193U,
  0xa679438eU, 0x49b40821U, 0xf61e2562U, 0xc040b340U, 0x265e5a51U, 0xe9b6c7aaU, 0xd62f105dU,
  0x02441453U, 0xd8a1e681U, 0xe7d3fbc8U, 0x21e1cde6U, 0xc33707d6U, 0xf4d50d87U, 0x455a14edU,
  0xa9e3e905U, 0xfcefa3f8U, 0x676f02d9U, 0x8d2a4c8aU, 0xfffa3942U, 0x8771f681U, 0x6d9d6122U,
  0xfde5380cU, 0xa4beea44U, 0x4bdecfa9U, 0xf6bb4b60U, 0xbebfbc70U, 0x289b7ec6U, 0xeaa127faU,
  0xd4ef3085U, 0x04881d05U, 0xd9d4d039U, 0xe6db99e5U, 0x1fa27cf8U, 0xc4ac5665U, 0xf4292244U,
  0x432aff97U, 0xab9423a7U, 0xfc93a039U, 0x655b59c3U, 0x8f0ccc92U, 0xffeff47dU, 0x85845dd1U,
  0x6fa87e4fU, 0xfe2ce6e0U, 0xa3014314U, 0x4e0811a1U, 0xf7537e82U, 0xbd3af235U, 0x2ad7d2bbU,
  0xeb86d391U,
]

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

///|
fn md5_word(data : Array[Byte], offset : Int) -> UInt {
  data[offset].to_uint() |
  (data[offset + 1].to_uint() << 8) |
  (data[offset + 2].to_uint() << 16) |
  (data[offset + 3].to_uint() << 24)
}

///|
fn md5_out_byte(v : UInt, shift : Int) -> Int {
  ((v >> shift) & 0xffU).reinterpret_as_int()
}

///|
const HEX_DIGITS : String = "0123456789abcdef"

///|
fn hex_byte(b : Int) -> String {
  let buf = StringBuilder()
  buf.write_char(HEX_DIGITS[(b >> 4) & 0xf].to_char().unwrap())
  buf.write_char(HEX_DIGITS[b & 0xf].to_char().unwrap())
  buf.to_string()
}

///|
/// Compute the MD5 digest of `data` as a lowercase hex string.
pub fn md5_hex(data : Bytes) -> String {
  let len = data.length()
  // Padded length: original + 0x80 + zeros + 8-byte little-endian bit count.
  let padded_len = if len % 64 < 56 {
    len + 56 - len % 64
  } else {
    len + 120 - len % 64
  }
  let m : Array[Byte] = Array::make(padded_len + 8, b'\x00')
  for i in 0..> 8) & 0xffU).to_byte()
  m[padded_len + 2] = ((bits >> 16) & 0xffU).to_byte()
  m[padded_len + 3] = ((bits >> 24) & 0xffU).to_byte()
  let mut a0 = 0x67452301U
  let mut b0 = 0xefcdab89U
  let mut c0 = 0x98badcfeU
  let mut d0 = 0x10325476U
  let w : Array[UInt] = Array::make(16, 0U)
  for block in 0..<((padded_len + 8) / 64) {
    let start = block * 64
    for j in 0..<16 {
      w[j] = md5_word(m, start + j * 4)
    }
    let mut a = a0
    let mut b = b0
    let mut c = c0
    let mut d = d0
    for i in 0..<64 {
      let mut f : UInt = 0U
      let mut g : Int = 0
      if i < 16 {
        f = (b & c) | (b.lnot() & d)
        g = i
      } else if i < 32 {
        f = (d & b) | (d.lnot() & c)
        g = (5 * i + 1) % 16
      } else if i < 48 {
        f = b ^ c ^ d
        g = (3 * i + 5) % 16
      } else {
        f = c ^ (b | d.lnot())
        g = 7 * i % 16
      }
      f = f + a + md5_k[i] + w[g]
      a = d
      d = c
      c = b
      b = b + rotl32(f, md5_shifts[i])
    }
    a0 = a0 + a
    b0 = b0 + b
    c0 = c0 + c
    d0 = d0 + d
  }
  let out = StringBuilder()
  for v in [a0, b0, c0, d0] {
    for shift in [0, 8, 16, 24] {
      out.write_string(hex_byte(md5_out_byte(v, shift)))
    }
  }
  out.to_string()
}