///|
/// 纯 MoonBit 无符号大数(M6-1,W6 公钥验签·仅 RSA)。
///
/// 内部原语:以 `Array[UInt32]` 为 limb(**小端**:limb[0] 为最低位),每个 limb 32 位,
/// 归一化(最高位 limb 不为 0;空数组代表值 0)。提供加 / 减 / 乘 / 模 / 模幂。
///
/// 用途:RSA PKCS#1 v1.5 验签原语(M6-2)的底层;后续接入 v1/v2/v3/v3.1 签名值验证。
/// 本模块**不进入公开 API**(内部原语),公开入口在 M6-4/M6-5 的 `verify_signatures`。
///
/// 实现口径:纯值、无外部依赖、无全局状态;输入只读。`big_mod` 用二进制长除法
/// (移位-减),`big_mod_pow` 用右到左二进制模幂——对离线分析工具的 APK 级输入可接受;
/// 大 RSA 模数的模运算复杂度 O(bitlen·limbs),属分析工具可接受的非实时口径。
///
/// 语义防火墙:本模块只做无符号整数运算,**不做**符号/小数/负数;调用方保证
/// `big_sub` 的 a≥b、`big_mod`/`big_mod_pow` 的模数非 0 且为奇(RSA 模数天然满足)。
/// 密码学正确性由 M6-1 已知向量测试承载(见 `bigint_test.mbt`)。

///|
/// 大数:小端 UInt32 limb 数组(空数组 = 0,无前导 0 limb)。
priv struct BigInt {
  limbs : Array[UInt32]
}

///|
/// 值 0。
fn big_zero() -> BigInt {
  { limbs: [], }
}

///|
/// 值 1。
fn big_one() -> BigInt {
  { limbs: [1], }
}

///|
/// 判断是否为 0。
fn big_is_zero(a : BigInt) -> Bool {
  a.limbs.length() == 0
}

///|
/// 比较 a 与 b:ab → 1。
fn big_cmp(a : BigInt, b : BigInt) -> Int32 {
  let la = a.limbs.length()
  let lb = b.limbs.length()
  if la != lb {
    if la < lb {
      -1
    } else {
      1
    }
  } else {
    for i = la - 1; i >= 0; i = i - 1 {
      if a.limbs[i] != b.limbs[i] {
        return if a.limbs[i] < b.limbs[i] { -1 } else { 1 }
      }
    }
    0
  }
}

///|
/// 位长(最高置位位下标 + 1;0 返回 0)。
fn big_bit_length(a : BigInt) -> Int32 {
  let n = a.limbs.length()
  if n == 0 {
    return 0
  }
  let top = a.limbs[n - 1]
  (n - 1) * 32 + (32 - top.clz())
}

///|
/// 取第 `i` 位(LSB 为位 0)。
fn big_bit_at(a : BigInt, i : Int32) -> Bool {
  let limb = a.limbs[i / 32]
  ((limb >> (i % 32)) & 1U) != 0U
}

///|
/// 左移 1 位。
fn big_shl1(a : BigInt) -> BigInt {
  let out : Array[UInt32] = []
  let mut carry : UInt32 = 0U
  for limb in a.limbs {
    out.push((limb << 1) | carry)
    carry = limb >> 31
  }
  if carry != 0U {
    out.push(carry)
  }
  { limbs: out, }
}

///|
/// 归一化:去掉最高位的 0 limb(空数组 = 0)。
fn big_normalize(limbs : Array[UInt32]) -> BigInt {
  let mut n = limbs.length()
  while n > 0 && limbs[n - 1] == 0U {
    n = n - 1
  }
  let out : Array[UInt32] = []
  for i = 0; i < n; i = i + 1 {
    out.push(limbs[i])
  }
  { limbs: out, }
}

///|
/// 加:a + b。
fn big_add(a : BigInt, b : BigInt) -> BigInt {
  let na = a.limbs.length()
  let nb = b.limbs.length()
  let n = if na > nb { na } else { nb }
  let out : Array[UInt32] = []
  let mut carry : UInt64 = 0UL
  for i = 0; i < n; i = i + 1 {
    let ai = if i < na { a.limbs[i].to_uint64() } else { 0UL }
    let bi = if i < nb { b.limbs[i].to_uint64() } else { 0UL }
    let s = ai + bi + carry
    out.push(s.to_uint())
    carry = s >> 32
  }
  if carry != 0UL {
    out.push(carry.to_uint())
  }
  big_normalize(out)
}

///|
/// 减:a - b(要求 a ≥ b)。
fn big_sub(a : BigInt, b : BigInt) -> BigInt {
  let na = a.limbs.length()
  let nb = b.limbs.length()
  let n = if na > nb { na } else { nb }
  let out : Array[UInt32] = []
  let mut borrow : UInt64 = 0UL
  for i = 0; i < n; i = i + 1 {
    let ai = if i < na { a.limbs[i].to_uint64() } else { 0UL }
    let bi = if i < nb { b.limbs[i].to_uint64() } else { 0UL }
    let diff = ai + 4294967296UL - borrow - bi
    out.push(diff.to_uint())
    borrow = if ai < bi + borrow { 1UL } else { 0UL }
  }
  big_normalize(out)
}

///|
/// 乘:a * b(教科书逐位乘,limb 中间用 UInt64 承接)。
fn big_mul(a : BigInt, b : BigInt) -> BigInt {
  if big_is_zero(a) || big_is_zero(b) {
    return big_zero()
  }
  let na = a.limbs.length()
  let nb = b.limbs.length()
  let res = Array::make(na + nb, 0U)
  for i = 0; i < na; i = i + 1 {
    let mut carry : UInt64 = 0UL
    let ai = a.limbs[i].to_uint64()
    for j = 0; j < nb; j = j + 1 {
      let cur = res[i + j].to_uint64() + ai * b.limbs[j].to_uint64() + carry
      res[i + j] = cur.to_uint()
      carry = cur >> 32
    }
    res[i + nb] = carry.to_uint()
  }
  big_normalize(res)
}

///|
/// 模:a mod m(二进制长除法,m ≠ 0;结果 < m)。
fn big_mod(a : BigInt, m : BigInt) -> BigInt {
  if big_is_zero(a) {
    return big_zero()
  }
  if big_cmp(a, m) < 0 {
    return a
  }
  let mut r = big_zero()
  let bit_len = big_bit_length(a)
  for i = bit_len - 1; i >= 0; i = i - 1 {
    r = big_shl1(r)
    if big_bit_at(a, i) {
      r = big_add(r, big_one())
    }
    if big_cmp(r, m) >= 0 {
      r = big_sub(r, m)
    }
  }
  r
}

///|
/// 模幂:base^exp mod m(右到左二进制模幂;exp ≥ 0,m ≠ 0)。
fn big_mod_pow(base : BigInt, exp : BigInt, m : BigInt) -> BigInt {
  let mut result = big_one()
  let mut b = big_mod(base, m)
  let bit_len = big_bit_length(exp)
  for i = 0; i < bit_len; i = i + 1 {
    if big_bit_at(exp, i) {
      result = big_mod(big_mul(result, b), m)
    }
    b = big_mod(big_mul(b, b), m)
  }
  result
}

///|
/// 从大端字节构造(b[0] 为最高位字节)。空/全零 → 0。
fn big_from_be_bytes(b : Bytes) -> BigInt {
  let len = b.length()
  if len == 0 {
    return big_zero()
  }
  let nlimbs = (len + 3) / 4
  let out : Array[UInt32] = []
  for i = 0; i < nlimbs; i = i + 1 {
    let mut v : UInt32 = 0U
    // 每个 limb 覆盖大端字节 [len-4i-4, len-4i-1);k=0 为该 limb 的最高字节。
    for k = 0; k < 4; k = k + 1 {
      let byte_idx = len - 4 * i - 4 + k
      if byte_idx >= 0 && byte_idx < len {
        v = (v << 8) | b[byte_idx].to_uint()
      }
    }
    out.push(v)
  }
  big_normalize(out)
}

///|
/// 转大端字节(最小字节数;0 → 单字节 0x00)。
fn big_to_be_bytes(a : BigInt) -> Bytes {
  if big_is_zero(a) {
    return b"\x00"
  }
  let bytes : Array[Byte] = []
  for i = a.limbs.length() - 1; i >= 0; i = i - 1 {
    let limb = a.limbs[i]
    bytes.push(((limb >> 24) & 0xFFU).to_byte())
    bytes.push(((limb >> 16) & 0xFFU).to_byte())
    bytes.push(((limb >> 8) & 0xFFU).to_byte())
    bytes.push((limb & 0xFFU).to_byte())
  }
  let mut start = 0
  while start < bytes.length() - 1 && bytes[start] == b'\x00' {
    start = start + 1
  }
  let out : Array[Byte] = []
  for i = start; i < bytes.length(); i = i + 1 {
    out.push(bytes[i])
  }
  Bytes::from_array(out[:])
}