viterbi 0.2.0

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Add-Compare-Select + renormalization + deterministic tie-break (R9, R17).
use crate::metric::BranchMetric;
use crate::trellis::Trellis;

/// Initial metric for unreachable states — large, with headroom below `u32::MAX` (R9).
pub const SENTINEL: u32 = u32::MAX / 2;

/// Advance one trellis stage. `cur` holds the current (already renormalized) state metrics;
/// results go to `next`. `survivors` is this stage's `⌈S/64⌉` decision words — one bit per state
/// (which predecessor survived), so it scales to any `S` (R12). Returns the pre-renorm minimum
/// (diagnostic). Bounds-safe by construction (fixed `[_; S]`; `survivors.len() == ⌈S/64⌉`).
pub fn acs_stage<const S: usize, M: BranchMetric>(
    cur: &[u32; S],
    next: &mut [u32; S],
    survivors: &mut [u64],
    trellis: &Trellis<S>,
    received: &[M::Sample],
) -> u32 {
    let mut min = u32::MAX;
    for w in survivors.iter_mut() {
        *w = 0;
    }
    for state in 0..S {
        let [a, b] = trellis.preds[state];
        // `saturating_add` upholds the no-panic invariant (R11/S9) for the PUBLIC GENERIC API: a custom
        // `BranchMetric` that violates the documented branch-distance bound (see `BranchMetric`) could
        // otherwise overflow this addition. It is not masking a real bug — for `HardHamming` (and any
        // metric respecting the contract) the §4.3 subtract-min renormalization keeps every reachable
        // metric ≤ `METRIC_SPREAD_BOUND` ≪ u32::MAX, so saturation never triggers; the `debug_assert`
        // below still validates that real bound over reachable (non-sentinel) states. Unreachable
        // `SENTINEL` states (first K-1 stages) stay near u32::MAX/2 and are excluded from that check.
        let ca = cur[a.from].saturating_add(M::branch_distance(a.output, received));
        let cb = cur[b.from].saturating_add(M::branch_distance(b.output, received));
        // Tie-break compares the two predecessors by their STATE number (`.from`), NOT the slot index:
        // keep slot 0 (`a`) iff its metric is strictly lower, or (on a tie) `a.from <= b.from` — i.e.
        // always the LOWER-NUMBERED predecessor state (R17). Because the decision reads `.from` (not the
        // slot), it is independent of the order in which `Trellis::from_params` filled the predecessor
        // table: swapping the two predecessor slots yields the identical survivor. Fully deterministic.
        let (winner_metric, winner_slot) = if ca < cb || (ca == cb && a.from <= b.from) {
            (ca, 0u64)
        } else {
            (cb, 1u64)
        };
        next[state] = winner_metric;
        survivors[state / 64] |= winner_slot << (state % 64); // decision bit for this state
        if winner_metric < min {
            min = winner_metric;
        }
    }
    for m in next.iter_mut() {
        *m -= min;
    } // renormalize (lossless): the new minimum is 0
      // Contract guard (debug-only): validate the §4.3 bound with the **tight per-config** spread
      // `b = (k−1)·n·PER_BIT_MAX`, clamped to the metric's declared `MAX_SPREAD`. `k`/`n` come from the
      // trellis (the code's own geometry, not a hard-coded K=7/N=2), so this scales to rate-1/3 and K≤9.
      // `saturating_mul` keeps the default `PER_BIT_MAX = u32::MAX` from overflowing `u32`: it saturates,
      // then `min(MAX_SPREAD)` yields the old loose cap for external metrics; the crate metrics
      // (`PER_BIT_MAX` 1/128) get the tight value. Every reachable metric (< SENTINEL/2; still-sentinel
      // states of the first K-1 stages are excluded and never false-fail) must stay within `b`. A
      // `BranchMetric` that violates its declared bound trips this in debug; release is unaffected
      // (ACS uses saturating_add).
    let b = (u32::from(trellis.k - 1).saturating_mul(trellis.n as u32))
        .saturating_mul(M::PER_BIT_MAX)
        .min(M::MAX_SPREAD);
    debug_assert!(
        next.iter().filter(|&&m| m < SENTINEL / 2).all(|&m| m <= b),
        "reachable-state metric spread exceeded the tight (k−1)·n·PER_BIT_MAX bound (§4.3)"
    );
    min
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::metric::HardHamming;
    use crate::params::CodeParams;
    use crate::trellis::Trellis;
    #[test]
    fn stage_selects_min_and_renormalizes_to_zero() {
        let t = Trellis::<64>::from_params(&CodeParams::ccsds_r1_2()).unwrap();
        let mut cur = [SENTINEL; 64];
        cur[0] = 0;
        let mut next = [0u32; 64];
        let mut surv = [0u64; 1]; // ⌈64/64⌉ = 1 word per stage
                                  // feed the exact expected symbol of the (state0,input0) branch → a zero-cost branch must exist
        let exp = t.forward[0][0].output;
        let recv = [((exp >> 1) & 1) as u8, (exp & 1) as u8];
        let min = acs_stage::<64, HardHamming>(&cur, &mut next, &mut surv, &t, &recv);
        assert_eq!(min, 0); // renorm subtracts the min
        assert_eq!(*next.iter().min().unwrap(), 0); // post-renorm min is 0
    }
}