orion-sdr 0.0.50

// Copyright (c) 2026 G & R Associates LLC
// SPDX-License-Identifier: MIT OR Apache-2.0

// src/fec/gf.rs
//
// Arithmetic over the Galois field GF(2^8), the shared foundation for the
// algebraic block codes in this module (BCH now, Reed–Solomon later). The
// field is generated by the primitive polynomial 0x11D (x^8 + x^4 + x^3 + x^2
// + 1) — the conventional choice, and the one used by both the DVB RS(204,188)
// outer code and countless BCH constructions.
//
// Addition/subtraction in GF(2^m) are both bitwise XOR. Multiplication is done
// via precomputed log/antilog (exp) tables: with `g` a generator (primitive
// element, here the field element 2), every nonzero element equals `g^i` for a
// unique `i` in 0..255, so `a*b = g^(log[a] + log[b])`. The tables are built
// once by `Gf256::new()`.

use std::sync::OnceLock;

/// The primitive polynomial x^8 + x^4 + x^3 + x^2 + 1, low 9 bits set.
const PRIMITIVE_POLY: u16 = 0x11D;

/// Process-wide singleton, built once on first use. The tables are a pure
/// function of [`PRIMITIVE_POLY`], so a single shared instance is always valid;
/// [`Gf256::shared`] hands out `&'static` references so the algebraic codes can
/// borrow it instead of rebuilding the 512+256-byte tables per construction
/// (which, in the COFDM frame layer, means per frame).
static SHARED: OnceLock<Gf256> = OnceLock::new();

/// Precomputed GF(2^8) log/antilog tables for fast multiply/divide/inverse.
#[derive(Debug, Clone)]
pub struct Gf256 {
    /// `exp[i] = g^i` for `i` in 0..510 (doubled span so `exp[log[a]+log[b]]`
    /// never needs a modulo — the sum of two logs is at most 254+254 = 508).
    exp: [u8; 512],
    /// `log[a]` such that `g^log[a] == a`, for `a` in 1..=255. `log[0]` is
    /// unused (0 has no logarithm); left at 0.
    log: [u8; 256],
}

impl Default for Gf256 {
    fn default() -> Self {
        Self::new()
    }
}

impl Gf256 {
    /// Builds the log/antilog tables for GF(2^8) under [`PRIMITIVE_POLY`].
    pub fn new() -> Self {
        let mut exp = [0u8; 512];
        let mut log = [0u8; 256];

        // Walk the powers of the primitive element g = 2: start at g^0 = 1 and
        // repeatedly multiply by x (left shift), reducing modulo the primitive
        // polynomial whenever the result exceeds 8 bits. `i` indexes `exp` while
        // the tracked element `x` indexes `log` — the two arrays are written at
        // unrelated positions each step, so an enumerate-style rewrite doesn't
        // apply.
        #[allow(clippy::needless_range_loop)]
        {
            let mut x: u16 = 1;
            for i in 0..255 {
                exp[i] = x as u8;
                log[x as usize] = i as u8;
                x <<= 1;
                if x & 0x100 != 0 {
                    x ^= PRIMITIVE_POLY;
                }
            }
        }
        // Duplicate the cycle so exp[i] is valid for i up to 509 without a
        // modulo (g has order 255, so exp[i] = exp[i - 255]).
        for i in 255..512 {
            exp[i] = exp[i - 255];
        }

        Self { exp, log }
    }

    /// Returns the process-wide shared `Gf256`, building it once on first call.
    ///
    /// Prefer this over [`Gf256::new`] wherever the tables would otherwise be
    /// rebuilt repeatedly (block-code construction, per-frame decode). The
    /// returned reference is `'static` and the instance is immutable, so it is
    /// freely shareable across threads. The tables are bit-identical to
    /// [`Gf256::new`]'s — this only avoids recomputing them.
    pub fn shared() -> &'static Gf256 {
        SHARED.get_or_init(Gf256::new)
    }

    /// Field addition (= subtraction): bitwise XOR.
    #[inline(always)]
    pub fn add(&self, a: u8, b: u8) -> u8 {
        a ^ b
    }

    /// Field multiplication. `0` is absorbing.
    #[inline(always)]
    pub fn mul(&self, a: u8, b: u8) -> u8 {
        if a == 0 || b == 0 {
            0
        } else {
            self.exp[self.log[a as usize] as usize + self.log[b as usize] as usize]
        }
    }

    /// Field division `a / b`. Panics if `b == 0`.
    #[inline]
    pub fn div(&self, a: u8, b: u8) -> u8 {
        assert!(b != 0, "GF(2^8) division by zero");
        if a == 0 {
            0
        } else {
            // log[a] - log[b] taken mod 255, kept non-negative by adding 255.
            let idx = self.log[a as usize] as usize + 255 - self.log[b as usize] as usize;
            self.exp[idx]
        }
    }

    /// Multiplicative inverse `a^-1`. Panics if `a == 0`.
    #[inline]
    pub fn inv(&self, a: u8) -> u8 {
        assert!(a != 0, "GF(2^8) inverse of zero");
        self.exp[255 - self.log[a as usize] as usize]
    }

    /// `a` raised to the (integer) power `n`, `n` reduced modulo 255.
    #[inline]
    pub fn pow(&self, a: u8, n: usize) -> u8 {
        if a == 0 {
            return if n == 0 { 1 } else { 0 };
        }
        let idx = (self.log[a as usize] as usize * n) % 255;
        self.exp[idx]
    }

    /// The primitive element's `i`-th power, `g^i` (`i` reduced modulo 255).
    /// Used to build generator polynomials whose roots are consecutive powers
    /// of `g`.
    #[inline]
    pub fn exp_of(&self, i: usize) -> u8 {
        self.exp[i % 255]
    }

    /// The discrete logarithm of a nonzero element: `log_g(a)`. Panics if
    /// `a == 0`.
    #[inline]
    pub fn log_of(&self, a: u8) -> u8 {
        assert!(a != 0, "GF(2^8) log of zero");
        self.log[a as usize]
    }
}