viterbi 0.2.0

// Author: BolivarTech
// Version: 1.0.0
// Date: 2026-07-02
//! Branch-metric abstraction: hard-decision Hamming now, soft/erasure-ready (R7).

/// Sentinel `Sample` for [`HardHamming`] meaning "erased" (contributes zero).
pub const HARD_ERASURE: u8 = 0xFF;

/// Cost model for a trellis branch, generic over the received sample type.
///
/// # Contract (bounded branch distance)
/// `branch_distance` MUST return a per-stage cost small enough that, combined with the decoder's
/// per-stage subtract-min renormalization (which keeps the *spread* of state metrics bounded), the
/// accumulated `u32` state metric never exceeds `u32::MAX`. Concretely a bound on the order of a few
/// times `N` per stage is expected — [`HardHamming`] returns at most `N` (one per output bit). The
/// decoder guards its ACS additions with `saturating_add`, so a metric that *violates* this bound
/// **degrades to an incorrect (saturated) result rather than panicking** — the no-panic invariant
/// (R11/S9) always holds — but *correct* decoding requires implementations to respect the bound.
pub trait BranchMetric {
    /// The per-output-bit received sample type.
    type Sample: Copy;
    /// Upper bound on the post-renormalization spread of *reachable* state metrics this metric can
    /// produce (`max reachable metric` after each stage's subtract-min). The decoder `debug_assert!`s
    /// reachable metrics stay `<= MAX_SPREAD`, so the bound is a property of the metric, not hard-coded
    /// in the generic ACS. For [`HardHamming`] it is a conservative value for the CCSDS K=7 profile.
    const MAX_SPREAD: u32;
    /// Maximum per-output-bit branch cost this metric can contribute in one stage
    /// ([`HardHamming`] = `1` per mismatched bit; [`SoftLlr`] = `|λ|_max = 128`). The ACS combines it
    /// with the code geometry into the **tight** post-renorm spread bound `(k−1)·n·PER_BIT_MAX`
    /// (clamped to `MAX_SPREAD`) that its `debug_assert!` checks.
    ///
    /// **Defaults to `u32::MAX`** so external `BranchMetric` implementors need not set it (additive,
    /// non-breaking): with the default the `(k−1)·n·PER_BIT_MAX` product saturates and the bound falls
    /// back to `MAX_SPREAD` (the previous, looser behavior). The crate metrics override it with their
    /// exact per-bit ceiling to catch a moderate renorm regression the loose cap alone would miss.
    const PER_BIT_MAX: u32 = u32::MAX;
    /// Cost of a branch whose expected N-bit `expected` symbol (C1 in the high bit) meets `received`.
    /// See the trait-level contract: the returned value must be bounded (see [`BranchMetric`]).
    fn branch_distance(expected: u32, received: &[Self::Sample]) -> u32;
    /// A neutral "erasure" sample that contributes zero to any branch distance.
    fn erasure() -> Self::Sample;
}

/// Hard-decision Hamming metric. `Sample = u8`: `0`/`1` are bits, [`HARD_ERASURE`] (`0xFF`) is an erasure
/// (contributes zero). Any other value is interpreted by its least-significant bit (`s & 1`); the
/// on-air `decode_block` path only ever produces `0`/`1`, so this matters only for the raw `decode` API.
/// Distance per stage is at most `N`, satisfying the [`BranchMetric`] bound contract.
pub struct HardHamming;
impl BranchMetric for HardHamming {
    type Sample = u8;
    /// Conservative bound for the CCSDS K=7 profile — the true post-renorm spread is ~`(K-1)·N`; this
    /// loose value only needs to exceed it to catch an overflow/renorm bug in debug builds.
    const MAX_SPREAD: u32 = 256;
    /// One unit of Hamming distance per mismatched output bit.
    const PER_BIT_MAX: u32 = 1;
    fn branch_distance(expected: u32, received: &[Self::Sample]) -> u32 {
        let n = received.len();
        let mut d: u32 = 0;
        for (j, &s) in received.iter().enumerate() {
            if s == HARD_ERASURE {
                continue;
            }
            // `expected` holds `n` output bits (C1 in the high bit). Guard the shift so a caller passing a
            // slice longer than 32 samples (never happens on the N=2 decode path) can't overflow-shift a
            // `u32`: positions at/above bit 32 hold no expected bit, so treat them as 0. No panic (R11).
            let shift = n - 1 - j;
            let exp_bit = if shift < 32 {
                ((expected >> shift) & 1) as u8
            } else {
                0
            };
            if exp_bit != (s & 1) {
                d = d.saturating_add(1); // saturating for consistency (d ≤ received.len(), never overflows here)
            }
        }
        d
    }
    fn erasure() -> u8 {
        HARD_ERASURE
    }
}

/// Conservative post-renorm spread bound for the soft metric (K≤9, n≤3): (K-1)·n·|λ|_max = 8·3·128 = 3072.
pub const SOFT_MAX_SPREAD: u32 = 4096;

/// Soft-decision LLR metric. `Sample=i8` quantized LLR, convention **λ>0 ⇒ bit 0**. `branch_distance` =
/// Σ `|λ|` on disagreement, `0` on agreement — max-log ML up to a per-stage constant (cancels in ACS),
/// reduces to Hamming at λ=±1, `erasure()=0` is a free match. `|λ|` via `unsigned_abs` (whole i8 domain
/// incl. `i8::MIN`; `.abs()` would overflow-panic; `i8::unsigned_abs` is stable since Rust 1.51 ≪ MSRV 1.96).
pub struct SoftLlr;
impl BranchMetric for SoftLlr {
    type Sample = i8;
    const MAX_SPREAD: u32 = SOFT_MAX_SPREAD;
    /// `|λ|_max = i8::unsigned_abs(i8::MIN) = 128` — the largest per-bit LLR magnitude.
    const PER_BIT_MAX: u32 = 128;
    fn branch_distance(expected: u32, received: &[Self::Sample]) -> u32 {
        let n = received.len();
        let mut d: u32 = 0;
        for (j, &lam) in received.iter().enumerate() {
            let shift = n - 1 - j; // C1 high bit
            let exp_bit = if shift < 32 {
                (expected >> shift) & 1
            } else {
                0
            };
            let disagree = (exp_bit == 0 && lam < 0) || (exp_bit == 1 && lam > 0);
            if disagree {
                d = d.saturating_add(u32::from(lam.unsigned_abs()));
            }
        }
        d
    }
    fn erasure() -> i8 {
        0
    }
}
impl SoftLlr {
    /// Correctly-signed, clipped `i8` LLR from a BPSK soft sample (λ>0 ⇒ bit 0). Saturates to `[-127,127]`.
    /// `scale` is a **magnitude**: it is applied as `scale.abs()` so a negative `scale` can **never** invert
    /// the sign convention — the LLR sign always comes from `sample` (release-safe, Caspar). A `debug_assert!`
    /// still flags a negative `scale` early as a likely caller mistake. A `NaN` sample maps to `0`
    /// (`NaN.clamp(..) as i8 == 0`) — a safe neutral LLR, never a panic. **Do NOT replace `.clamp(..)` with
    /// `.max(..).min(..)`** (Caspar): `f32::clamp` propagates `NaN` (→ `0` on the `as i8` cast), whereas a
    /// hand-rolled `min/max` chain can yield a different, non-neutral result for `NaN`. The `clamp`+`as i8`
    /// NaN→0 behavior is a **tested contract**, not incidental: it rests on **stable Rust semantics**
    /// (Melchior) — the saturating `f32 as i8` cast (NaN→0) has been defined since Rust 1.45, and
    /// `f32::clamp` NaN-propagation follows IEEE-754 — so it is platform-independent, not a lucky accident.
    #[must_use]
    pub fn llr_from_bpsk(sample: f32, scale: f32) -> i8 {
        // `partial_cmp(..) != Some(Less)` (NOT `scale >= 0.0`, NOT `!(scale < 0.0)`): this form is
        // clippy-clean — `-D warnings` rejects `!(scale < 0.0)` via `neg_cmp_op_on_partial_ord` — AND
        // NaN-safe: a NaN scale gives `None != Some(Less)` ⇒ the assert holds (no false panic), then NaN
        // flows to `NaN.clamp(..) as i8 == 0` (safe). `scale >= 0.0` would instead FALSE-FIRE on NaN.
        debug_assert!(
            scale.partial_cmp(&0.0) != Some(core::cmp::Ordering::Less),
            "llr_from_bpsk scale is a magnitude; negative is a likely caller mistake"
        );
        (sample * scale.abs()).round().clamp(-127.0, 127.0) as i8
    }
    /// Integer LLR helper. Clamps `shift` to ≤15 first (a `shift≥16` on `i16` is a Rust shift-overflow —
    /// **panics in debug, masked to `shift & 15` in release** (Melchior: it is masked, not "wrapped");
    /// the `.min(15)` clamp avoids that path entirely), so it can never panic; the `>>` is an
    /// **arithmetic (sign-preserving) right shift** (`i16` is
    /// signed), i.e. a floor-division by `2^shift` that keeps the LLR sign; result saturates to
    /// `[-127,127]`, never `i8::MIN`. (Larger `shift` ⇒ smaller-magnitude LLR: e.g. `i16::MIN>>15 = -1`.)
    #[must_use]
    pub fn llr_from_bpsk_int(sample: i16, shift: u8) -> i8 {
        (sample >> shift.min(15)).clamp(-127, 127) as i8
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn hamming_counts_bit_mismatches() {
        // expected symbol 0b10 (C1=1,C2=0), received [1,0] → distance 0; received [0,0] → 1; [0,1] → 2
        assert_eq!(HardHamming::branch_distance(0b10, &[1, 0]), 0);
        assert_eq!(HardHamming::branch_distance(0b10, &[0, 0]), 1);
        assert_eq!(HardHamming::branch_distance(0b10, &[0, 1]), 2);
    }
    #[test]
    fn erasure_sample_is_free() {
        assert_eq!(HardHamming::erasure(), 0xFF);
        assert_eq!(HardHamming::branch_distance(0b11, &[0xFF, 0xFF]), 0);
        assert_eq!(HardHamming::branch_distance(0b11, &[0xFF, 0]), 1); // one real mismatch
    }
    #[test]
    fn soft_llr_agree_costs_zero_disagree_costs_abs() {
        // expected 0b10 (C1 high bit): pos0 expected bit 1 (needs λ<0), pos1 expected bit 0 (needs λ>0).
        assert_eq!(SoftLlr::branch_distance(0b10, &[40, -20]), 60); // both disagree: 40 + 20
        assert_eq!(SoftLlr::branch_distance(0b10, &[-40, 20]), 0); // both agree
    }
    #[test]
    fn soft_llr_erasure_zero_and_min_is_safe() {
        assert_eq!(SoftLlr::erasure(), 0);
        assert_eq!(SoftLlr::branch_distance(0b11, &[0, 0]), 0); // erasures → 0
        assert_eq!(SoftLlr::branch_distance(0b00, &[i8::MIN, i8::MIN]), 256); // disagree×2: i8::MIN(-128)⇒bit1 vs exp 0; 128+128 (unsigned_abs, no panic)
        assert_eq!(SoftLlr::branch_distance(0b11, &[i8::MIN, i8::MIN]), 0); // agree: i8::MIN⇒bit1 == exp bits 1,1
    }
    #[test]
    fn soft_llr_reduces_to_hamming_at_unit_llr() {
        assert_eq!(SoftLlr::branch_distance(0b10, &[-1, 1]), 0);
        assert_eq!(SoftLlr::branch_distance(0b10, &[1, 1]), 1);
        assert_eq!(SoftLlr::branch_distance(0b10, &[1, -1]), 2);
    }
    #[test]
    fn soft_llr_equals_hamming_over_all_2bit_symbols() {
        // Exhaustive reduction proof (Melchior): at λ=±1, SoftLlr == HardHamming for EVERY expected symbol
        // and every received pattern. λ>0 ⇒ hard bit 0, λ<0 ⇒ hard bit 1.
        for expected in 0u32..4 {
            for &a in &[-1i8, 1] {
                for &b in &[-1i8, 1] {
                    let hard = [u8::from(a < 0), u8::from(b < 0)];
                    assert_eq!(
                        SoftLlr::branch_distance(expected, &[a, b]),
                        HardHamming::branch_distance(expected, &hard),
                        "reduction mismatch at expected={expected} a={a} b={b}"
                    );
                }
            }
        }
    }
    #[test]
    fn llr_helpers_signed_clipped_never_min() {
        assert!(SoftLlr::llr_from_bpsk(10.0, 100.0) > 0);
        assert_eq!(SoftLlr::llr_from_bpsk(1000.0, 1000.0), 127);
        assert_eq!(SoftLlr::llr_from_bpsk(-1000.0, 1000.0), -127);
        assert_eq!(SoftLlr::llr_from_bpsk_int(i16::MIN, 0), -127); // shift 0: -32768 clamps to -127 (saturates, never i8::MIN)
        assert_eq!(SoftLlr::llr_from_bpsk_int(i16::MIN, 99), -1); // shift clamped ≤15: -32768>>15 = -1 (arithmetic shift), no panic
        assert_eq!(SoftLlr::llr_from_bpsk(f32::NAN, 100.0), 0); // NaN sample → 0 (safe neutral LLR), never a panic (Caspar)
    }
}