viterbi 0.0.1

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Convolutional code parameters and their validation (R8, R19).
use crate::K as CCSDS_K;

/// Errors from constructing/validating [`CodeParams`].
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ParamError {
    /// A generator polynomial was zero (every generator must be non-zero).
    ZeroGenerator,
    /// A generator polynomial was `>= 2^k` (out of the `K`-bit range).
    GeneratorOutOfRange {
        /// The offending generator value.
        g: u32,
        /// The constraint length it was checked against.
        k: u8,
    },
    /// `k` was outside the supported constraint-length range `1..=9`.
    KOutOfRange {
        /// The rejected constraint length.
        k: u8,
    },
    /// `k` is valid but not supported by this increment's engine (only `K = 7`).
    KUnsupported {
        /// The unsupported constraint length.
        k: u8,
    },
    /// The generator count is valid but the rate is unsupported by this increment (only rate 1/2, `n = 2`).
    RateUnsupported {
        /// The unsupported number of generators (output bits per input bit).
        n: usize,
    },
    /// The generator and inversion arrays had mismatched (or empty) lengths.
    InconsistentLengths,
    /// The generator set is catastrophic (GCD over GF(2) is not a monomial `x^i`).
    Catastrophic,
    /// The const state count `S` did not equal `2^(k-1)`.
    StateCountMismatch {
        /// The provided const state count `S`.
        states: usize,
        /// The constraint length whose `2^(k-1)` it must match.
        k: u8,
    },
}
impl core::fmt::Display for ParamError {
    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
        write!(f, "{self:?}")
    }
}
impl std::error::Error for ParamError {}

/// A convolutional code definition (data, not hardcoded — R8). Fields are `pub(crate)` so the **only**
/// way to obtain a `CodeParams` is through the validating `new`/`ccsds_r1_2` — a struct literal cannot
/// bypass the non-catastrophic check (security). Read them via the accessors.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct CodeParams {
    pub(crate) k: u8,
    pub(crate) generators: Vec<u32>,
    pub(crate) invert_outputs: Vec<bool>,
}

impl CodeParams {
    /// Constraint length `K`.
    #[must_use]
    pub fn k(&self) -> u8 {
        self.k
    }
    /// Generator polynomials, in output order.
    #[must_use]
    pub fn generators(&self) -> &[u32] {
        &self.generators
    }
    /// Per-generator output inversion flags.
    #[must_use]
    pub fn invert_outputs(&self) -> &[bool] {
        &self.invert_outputs
    }

    /// Validated constructor (R19). `k` in `1..=9`; generators non-zero and `< 2^k`;
    /// `invert_outputs.len() == generators.len()`; the set must be non-catastrophic.
    pub fn new(k: u8, generators: Vec<u32>, invert_outputs: Vec<bool>) -> Result<Self, ParamError> {
        let p = Self {
            k,
            generators,
            invert_outputs,
        };
        p.validate()?;
        Ok(p)
    }

    /// Re-check the full invariant (R19): `k` in `1..=9`; non-empty, consistent-length generator /
    /// inversion arrays; each generator non-zero and `< 2^k`; the set non-catastrophic. `pub(crate)`
    /// so `ViterbiEncoder::new` / `ViterbiDecoder::new` can **re-validate defensively in release**
    /// (not only the preset's debug_assert) — any `CodeParams` reaching the engines is proven valid.
    pub(crate) fn validate(&self) -> Result<(), ParamError> {
        if !(1..=9).contains(&self.k) {
            return Err(ParamError::KOutOfRange { k: self.k });
        }
        if self.generators.is_empty() || self.invert_outputs.len() != self.generators.len() {
            return Err(ParamError::InconsistentLengths);
        }
        let limit = 1u32 << self.k;
        for &g in &self.generators {
            if g == 0 {
                return Err(ParamError::ZeroGenerator);
            }
            if g >= limit {
                return Err(ParamError::GeneratorOutOfRange { g, k: self.k });
            }
        }
        if is_catastrophic(&self.generators) {
            return Err(ParamError::Catastrophic);
        }
        Ok(())
    }

    /// First-class CCSDS R=1/2 profile (known-good). `K=7`, generators `[0o171, 0o133]` in output order
    /// (`C1` from `0o171`, `C2` from `0o133`); `invert_outputs = [false, true]` aligns element-wise with
    /// `generators`, i.e. **only the `0o133` (`G2`/`C2`) output is inverted** per the CCSDS convention.
    /// Constructed **directly** (fields are in-crate) — no validation call, so there is **no panic path**
    /// (`ccsds_preset_equals_validated_new` asserts it matches the validated constructor).
    #[must_use]
    pub fn ccsds_r1_2() -> Self {
        let p = Self {
            k: CCSDS_K,
            generators: vec![0o171, 0o133],
            invert_outputs: vec![false, true],
        };
        // Debug-only self-check: the preset must satisfy the same invariant as `new` (via `validate`,
        // no clone/allocation). No release cost and no release panic.
        debug_assert!(p.validate().is_ok(), "CCSDS preset must be valid");
        p
    }
}

/// A code is catastrophic iff the GCD of its generator polynomials over GF(2) is not a monomial `x^i`.
/// Minimal sufficient check for this increment: reject when the GCD has more than one set bit.
fn is_catastrophic(generators: &[u32]) -> bool {
    let mut g = 0u32;
    for &x in generators {
        g = gcd_gf2(g, x);
    }
    // GCD is a monomial x^i ⇔ it has exactly one set bit (or is zero, impossible here).
    g.count_ones() != 1
}

/// Polynomial GCD over GF(2) (bit i = coefficient of x^i), Euclid with XOR long division.
/// `leading_zeros` is only ever taken of a non-zero value (loop guard), so no underflow;
/// `gcd_gf2(0, x) == x`.
fn gcd_gf2(mut a: u32, mut b: u32) -> u32 {
    while a != 0 && b != 0 {
        // Ensure deg(a) >= deg(b): fewer leading zeros = higher degree.
        if a.leading_zeros() > b.leading_zeros() {
            core::mem::swap(&mut a, &mut b);
        }
        // shift = deg(a) - deg(b) >= 0, and both degrees are < 32 (u32), so `shift < 32`:
        // the `b << shift` can never be an overflowing shift (no panic). `b`'s top set bit is at
        // deg(b) <= deg(a) < 32, so `b << shift` also stays within the u32 without dropping bits.
        let shift = b.leading_zeros() - a.leading_zeros();
        a ^= b << shift;
    }
    a | b // the non-zero one (the other is 0)
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn ccsds_preset_is_valid_and_correct() {
        let p = CodeParams::ccsds_r1_2();
        assert_eq!(p.k, 7);
        assert_eq!(p.generators, vec![0o171, 0o133]);
        assert_eq!(p.invert_outputs, vec![false, true]);
    }
    #[test]
    fn rejects_zero_generator() {
        assert_eq!(
            CodeParams::new(7, vec![0o171, 0], vec![false, true]),
            Err(ParamError::ZeroGenerator)
        );
    }
    #[test]
    fn rejects_k_out_of_range() {
        assert_eq!(
            CodeParams::new(10, vec![1, 1], vec![false, false]),
            Err(ParamError::KOutOfRange { k: 10 })
        );
    }
    #[test]
    fn rejects_inconsistent_lengths() {
        assert_eq!(
            CodeParams::new(7, vec![0o171, 0o133], vec![false]),
            Err(ParamError::InconsistentLengths)
        );
    }
    #[test]
    fn rejects_catastrophic_equal_generators() {
        // identical generators share every factor → catastrophic
        assert_eq!(
            CodeParams::new(7, vec![0o171, 0o171], vec![false, false]),
            Err(ParamError::Catastrophic)
        );
    }
    #[test]
    fn accepts_ccsds_generators() {
        assert!(CodeParams::new(7, vec![0o171, 0o133], vec![false, true]).is_ok());
    }
    #[test]
    fn ccsds_preset_equals_validated_new() {
        // the directly-constructed preset (no panic path) equals the validated constructor
        assert_eq!(
            CodeParams::ccsds_r1_2(),
            CodeParams::new(7, vec![0o171, 0o133], vec![false, true]).unwrap()
        );
    }
    #[test]
    fn rejects_catastrophic_shared_factor() {
        // K=3, generators 0b011 (1+D) and 0b101 (1+D² = (1+D)²) share the factor (1+D):
        // GCD over GF(2) = 0b011 (not a monomial) ⇒ catastrophic (a finite error burst → unbounded output).
        assert_eq!(
            CodeParams::new(3, vec![0b011, 0b101], vec![false, false]),
            Err(ParamError::Catastrophic)
        );
    }
    #[test]
    fn accepts_monomial_gcd_non_catastrophic() {
        // K=3, generators 0b110 (x²+x) and 0b100 (x²): GCD over GF(2) = 0b10 (x) — a monomial x^i,
        // i.e. a pure delay, NOT a shared non-trivial factor ⇒ non-catastrophic (accepted).
        assert!(CodeParams::new(3, vec![0b110, 0b100], vec![false, false]).is_ok());
    }
    #[test]
    fn catastrophic_check_handles_multistep_gcd() {
        // K=4, generators 0b1001 (x³+1 = (x+1)(x²+x+1)) and 0b0101 (x²+1 = (x+1)²) share (x+1).
        // The GF(2) Euclid needs several reduction steps here → GCD = 0b11 ⇒ catastrophic (rejected).
        assert_eq!(
            CodeParams::new(4, vec![0b1001, 0b0101], vec![false, false]),
            Err(ParamError::Catastrophic)
        );
    }
}