viterbi 0.2.0

// 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 the engine.
    ///
    /// Reserved: this increment's engine supports the full `1..=9` range, so this variant is not
    /// currently produced; it is kept for a future increment that restricts `K`.
    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 {}

/// Discoverable registry of preconfigured standard convolutional codes (decision 5). Each variant
/// resolves — infallibly — to a validated [`CodeParams`] via [`CodeProfile::params`]. This is the
/// front door for well-known codes; [`CodeParams::new`] remains for arbitrary valid codes.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum CodeProfile {
    /// First-class CCSDS R=1/2 profile: `K=7`, generators `[0o171, 0o133]`, `G2` inverted, `d_free = 10`.
    CcsdsR1_2,
    /// CCSDS R=1/3 mother code: `K=7`, generators `[0o133, 0o171, 0o145]`, no inversion, `d_free = 14`.
    CcsdsR1_3,
    /// Well-known **non-CCSDS** `K=9` R=1/2 code (`[0o561, 0o753]`, `d_free = 12`). Exercises the generic
    /// `K` path (RK4) and stays discoverable.
    ///
    /// # Note
    /// `params()` here yields a *constructible*, valid [`CodeParams`], and a `K=9` **decoder**
    /// (`ViterbiDecoder<256, _>`) is **fully supported end-to-end**: the `m = k-1` tail-length
    /// generalization has landed, so a `K=9` decode uses the correct zero-tail length and round-trips.
    K9R1_2,
}

impl CodeProfile {
    /// Resolve the profile to its validated [`CodeParams`].
    ///
    /// Infallible: every variant is a known-good, verified non-catastrophic preset, so this never
    /// panics and never returns an error (`every_code_profile_params_is_valid` proves it in a release
    /// test build, not only via `debug_assert`).
    #[must_use]
    pub fn params(self) -> CodeParams {
        match self {
            CodeProfile::CcsdsR1_2 => CodeParams::ccsds_r1_2(),
            CodeProfile::CcsdsR1_3 => CodeParams::ccsds_r1_3(),
            // Known-good non-CCSDS K=9 code, constructed **directly** (fields are in-crate) like
            // `ccsds_r1_2`/`ccsds_r1_3` — no `new`/`expect`, so there is **no panic path**. The
            // `debug_assert` self-check and `every_code_profile_params_is_valid` prove it valid.
            CodeProfile::K9R1_2 => {
                let p = CodeParams {
                    k: 9,
                    generators: vec![0o561, 0o753],
                    invert_outputs: vec![false, false],
                };
                debug_assert!(p.validate().is_ok(), "K9R1_2 preset must be valid");
                p
            }
        }
    }
}

/// 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
    }

    /// Number of output bits per input bit (`n = generators.len()`): `2` for rate 1/2, `3` for rate 1/3.
    #[must_use]
    pub fn n(&self) -> usize {
        self.generators.len()
    }

    /// 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
    }

    /// CCSDS R=1/3 mother code profile (known-good). `K=7`, generators `[0o133, 0o171, 0o145]` in output
    /// order, `invert_outputs = [false, false, false]` (no inversion), `d_free = 14` — the stronger
    /// CCSDS inner code for the most hostile links. Constructed **directly** (fields are in-crate) — no
    /// validation call, so there is **no panic path**; the `debug_assert` self-check mirrors `ccsds_r1_2`.
    ///
    /// The generators and output order are **data**, cross-checked against an independent rate-1/3
    /// reference vector (RT2); if a normative reference contradicts them, the reference wins.
    #[must_use]
    pub fn ccsds_r1_3() -> Self {
        let p = Self {
            k: CCSDS_K,
            generators: vec![0o133, 0o171, 0o145],
            invert_outputs: vec![false, false, false],
        };
        // 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 rate-1/3 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_generator_out_of_range() {
        // K=3 ⇒ generators must be < 2^3 = 8; 0b1000 = 8 is exactly one past the K-bit range.
        assert_eq!(
            CodeParams::new(3, vec![0b1000, 0b101], vec![false, false]),
            Err(ParamError::GeneratorOutOfRange { g: 0b1000, k: 3 })
        );
    }
    #[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)
        );
    }

    #[test]
    fn ccsds_r1_3_preset_is_valid_and_correct() {
        let p = CodeParams::ccsds_r1_3();
        assert_eq!(p.k, 7);
        assert_eq!(p.generators, vec![0o133, 0o171, 0o145]);
        assert_eq!(p.invert_outputs, vec![false, false, false]);
        assert!(p.validate().is_ok());
    }

    #[test]
    fn code_profile_ccsds_r1_3_resolves_to_ccsds_r1_3_params() {
        assert_eq!(CodeProfile::CcsdsR1_3.params(), CodeParams::ccsds_r1_3());
    }

    #[test]
    fn code_profile_ccsds_r1_2_resolves_to_ccsds_r1_2_params() {
        assert_eq!(CodeProfile::CcsdsR1_2.params(), CodeParams::ccsds_r1_2());
    }

    #[test]
    fn n_reports_generator_count() {
        assert_eq!(CodeParams::ccsds_r1_2().n(), 2);
        assert_eq!(CodeParams::ccsds_r1_3().n(), 3);
    }

    #[test]
    fn every_code_profile_params_is_valid() {
        // Runs validate() directly (not the debug_assert), so an invalid preset fails even in release tests.
        for p in [
            CodeProfile::CcsdsR1_2,
            CodeProfile::CcsdsR1_3,
            CodeProfile::K9R1_2,
        ] {
            assert!(
                p.params().validate().is_ok(),
                "profile {p:?} must produce valid CodeParams"
            );
        }
    }
}