// Reed-Solomon error correction over GF(929).
//
// PDF417 error correction is a systematic Reed-Solomon code over the prime
// field GF(929) with generator polynomial
//
//     g(x) = (x - 3^1)(x - 3^2) ... (x - 3^degree)
//
// where `degree = 2^(level + 1)`.  The parity codewords are the remainder of
// `data(x) * x^degree` divided by `g(x)`, stored most significant first.
//
// This module implements both directions: parity generation for the encoder
// and a Berlekamp-Massey / Chien / Gaussian magnitude decoder for
// verification.  The decoder is what lets tests prove that a generated symbol
// survives a corrupted codeword.

///|
fn modulo929(value : Int) -> Int {
  let remainder = value % 929
  if remainder < 0 {
    remainder + 929
  } else {
    remainder
  }
}

///|
/// `base^exponent mod 929`.
pub fn pow_mod929(base : Int, exponent : Int) -> Int {
  let mut result = 1
  let mut factor = modulo929(base)
  let mut power = exponent
  while power > 0 {
    if power % 2 == 1 {
      result = result * factor % 929
    }
    factor = factor * factor % 929
    power = power / 2
  }
  result
}

///|
/// Multiplicative inverse modulo 929; 929 is prime, so every non-zero value
/// has an inverse.
pub fn inverse929(value : Int) -> Int {
  pow_mod929(value, 927)
}

///|
/// Generator polynomial coefficients for `degree` parity codewords, most
/// significant first.  The leading coefficient is always 1.
pub fn generator_polynomial(degree : Int) -> Array[Int] raise EncodeError {
  if degree < 2 || degree > 512 || degree % 2 != 0 {
    raise InvalidErrorCorrectionLevel(degree)
  }
  let mut polynomial : Array[Int] = [1]
  let mut root = 1
  for _ in 0.. Array[Int] raise EncodeError {
  if level < 0 || level > max_error_correction_level {
    raise InvalidErrorCorrectionLevel(level)
  }
  for word in data {
    if word < 0 || word > max_codewords {
      raise UnrepresentableChar(word)
    }
  }
  let degree = error_correction_codeword_count(level)
  if data.length() + degree > max_codewords {
    raise TooManyCodewords(data.length() + degree)
  }
  let polynomial = generator_polynomial(degree)
  let working : Array[Int] = []
  for word in data {
    working.push(word)
  }
  for _ in 0.. Array[Int] {
  let result : Array[Int] = []
  for index in 0.. Bool {
  for syndrome in syndromes(words, parity_count) {
    if syndrome != 0 {
      return false
    }
  }
  true
}

///|
/// Number of non-zero syndromes: a cheap measure of how damaged a sequence is.
pub fn syndrome_weight(words : Array[Int], parity_count : Int) -> Int {
  let mut weight = 0
  for syndrome in syndromes(words, parity_count) {
    if syndrome != 0 {
      weight += 1
    }
  }
  weight
}

///|
/// Field element attached to codeword `position` of a sequence of `length`
/// codewords: `X = 3^(length - 1 - position)`.
pub fn error_locator_of(position : Int, length : Int) -> Int {
  pow_mod929(3, length - 1 - position)
}

///|
/// Solve `matrix * solution = rhs` over GF(929).  Returns `None` for a
/// singular system.
fn solve_gf929(matrix : Array[Array[Int]], rhs : Array[Int]) -> Array[Int]? {
  let size = rhs.length()
  let rows : Array[Array[Int]] = []
  for index in 0.. Array[Int] {
  let mut locator : Array[Int] = [1]
  let mut previous : Array[Int] = [1]
  let mut shift = 1
  let mut last_discrepancy = 1
  let mut degree = 0
  for index in 0.. Int {
  let mut result = 0
  let mut power = 1
  for coefficient in locator {
    result = modulo929(result + coefficient * power)
    power = power * value % 929
  }
  result
}

///|
/// Chien search: positions whose field element is a root of `locator`.
fn chien_search(
  locator : Array[Int],
  length : Int,
  erasures : Array[Int],
) -> Array[Int] {
  let positions : Array[Int] = []
  for position in 0.. Array[Int]? {
  let count = positions.length()
  if count == 0 {
    return Some([])
  }
  let matrix : Array[Array[Int]] = []
  let rhs : Array[Int] = []
  for row in 0.. (Array[Int], Array[Int]) raise EncodeError {
  if parity_count < 2 || parity_count % 2 != 0 || parity_count > 512 {
    raise InvalidErrorCorrectionLevel(parity_count)
  }
  for position in erasures {
    if position < 0 || position >= words.length() {
      raise UnrepresentableChar(position)
    }
  }
  let observed = syndromes(words, parity_count)
  let mut damaged = false
  for value in observed {
    if value != 0 {
      damaged = true
    }
  }
  if !damaged {
    return (words, [])
  }
  if erasures.length() * 2 > parity_count {
    raise TooManyErasures(erasures.length(), parity_count)
  }
  let locator = berlekamp_massey(observed)
  let positions = chien_search(locator, words.length(), erasures)
  if positions.length() == 0 || positions.length() * 2 > parity_count {
    raise TooManyErasures(positions.length(), parity_count)
  }
  let magnitudes = match solve_magnitudes(observed, positions, words.length()) {
    Some(values) => values
    None => raise TooManyErasures(positions.length(), parity_count)
  }
  let repaired : Array[Int] = []
  for word in words {
    repaired.push(word)
  }
  let changed : Array[Int] = []
  for index in 0.. (Array[Int], Array[Int])? {
  try correct_errors(words, parity_count, erasures) catch {
    _ => None
  } noraise {
    repaired => Some(repaired)
  }
}