///|
/// CRC-32 (the reflected 0xEDB88320 form) over the secret bytes, carried
/// in every share. This is an integrity label for catching a mistyped,
/// truncated or foreign share during combine - explicitly not a MAC, and
/// the sharing secrecy itself rests only on the information-theoretic
/// argument, never on this checksum.
fn crc32(bytes : Array[Int32]) -> UInt32 {
  let mut crc = 0xFFFFFFFFU
  for byte in bytes {
    crc = crc ^ byte.reinterpret_as_uint()
    for _ in 0..<8 {
      if (crc & 1U) == 1U {
        crc = (crc >> 1) ^ 0xEDB88320U
      } else {
        crc = crc >> 1
      }
    }
  }
  crc ^ 0xFFFFFFFFU
}

///|
/// The integrity label as 8 lowercase hex digits, the share's wire form.
fn digest_hex(digest : UInt32) -> String {
  to_hex([
    ((digest >> 24) & 0xFFU).reinterpret_as_int(),
    ((digest >> 16) & 0xFFU).reinterpret_as_int(),
    ((digest >> 8) & 0xFFU).reinterpret_as_int(),
    (digest & 0xFFU).reinterpret_as_int(),
  ])
}

///|
fn digest_of_bytes(bytes : Array[Int32]) -> UInt32 {
  (bytes[0].reinterpret_as_uint() << 24) |
  (bytes[1].reinterpret_as_uint() << 16) |
  (bytes[2].reinterpret_as_uint() << 8) |
  bytes[3].reinterpret_as_uint()
}

///|
/// One share: the x coordinate (1..255), the threshold it was made for,
/// the integrity label of the secret, and one evaluation of each byte's
/// polynomial at x.
priv struct Share {
  index : Int32
  threshold : Int32
  digest : UInt32
  data : Array[Int32]
}

///|
/// Split `secret` into n shares of which any k recover it. Each byte gets
/// its own random polynomial of degree k-1 whose constant term is that
/// byte; share i is the evaluation of every polynomial at x = i. Fewer
/// than k shares leave every possible secret equally likely - that is the
/// information-theoretic guarantee, and it holds for any coefficient
/// stream that is uniform; the caller seeds the stream.
fn shamir_split(
  secret : Array[Int32],
  threshold : Int32,
  shares : Int32,
  seed : UInt64,
) -> Array[Share] {
  let rng = splitmix64(seed)
  let digest = crc32(secret)
  // coefficients[b] is byte b's polynomial, constant term first.
  let coefficients : Array[Array[Int32]] = []
  for byte in secret {
    let poly : Array[Int32] = [byte]
    for _ in 1.. (Array[Int32], Bool) raise InputError {
  let threshold = shares[0].threshold
  let digest = shares[0].digest
  let width = shares[0].data.length()
  for share in shares {
    if share.threshold != threshold {
      raise InputError("shares come from different thresholds")
    }
    if share.digest != digest {
      raise InputError("shares come from different splits")
    }
    if share.index < 1 || share.index > 255 {
      raise InputError("share index must be in 1..255")
    }
    if share.data.length() != width {
      raise InputError("shares have different lengths")
    }
  }
  for i in 0.. message == "need at least 3 shares to combine, got 2"
  }
  assert_eq(refused, true)
  // Below the threshold the interpolation itself lands anywhere but the
  // secret: two points of a degree-2 polynomial fix nothing about zero.
  let points : Array[(Int32, Int32)] = [
    (1, shares[0].data[0]),
    (2, shares[1].data[0]),
  ]
  assert_not_eq(gf_interpolate_zero(points), secret[0])
}

///|
/// Diagnose a share set: enumerate every k-sized subset, interpolate each,
/// and keep the subsets whose recovered bytes carry the label the shares
/// agree on. A share that appears in no consistent subset disagrees with
/// every quorum and is named a suspect; a set with at least one
/// consistent subset is consistent, and its secret is reported. The
/// enumeration is exhaustive, so it is bounded: at most 12 shares of a
/// threshold at most 6 (C(12,6) = 924 interpolations per byte position).
fn shamir_diagnose(shares : Array[Share]) -> Value raise InputError {
  let threshold = shares[0].threshold
  let digest = shares[0].digest
  let width = shares[0].data.length()
  for share in shares {
    if share.threshold != threshold {
      raise InputError("shares come from different thresholds")
    }
    if share.digest != digest {
      raise InputError("shares come from different splits")
    }
    if share.index < 1 || share.index > 255 {
      raise InputError("share index must be in 1..255")
    }
    if share.data.length() != width {
      raise InputError("shares have different lengths")
    }
  }
  if shares.length() > 12 {
    raise InputError("diagnose accepts at most 12 shares")
  }
  if threshold > 6 {
    raise InputError("diagnose accepts a threshold of at most 6")
  }
  if shares.length() < threshold {
    raise InputError(
      "need at least " +
      threshold.to_string() +
      " shares to diagnose, got " +
      shares.length().to_string(),
    )
  }
  for i in 0..> i) & 1) == 1 {
        picked.push(shares[i])
      }
    }
    if picked.length() != threshold {
      continue
    }
    let candidate : Array[Int32] = []
    for b in 0.. 0)),
    ("good", Array(good_list)),
    ("suspects", Array(suspects)),
    (
      "secret_hex",
      String(if consistent_subsets > 0 { to_hex(recovered) } else { "" }),
    ),
  ])
}