seyd_fec/
gf.rs

1// Copyright 2026 Anton Gravestam
2// SPDX-License-Identifier: Apache-2.0
3//! GF(256) arithmetic, field polynomial 0x11d.
4//!
5//! Every constant here is part of the wire contract: the pilot's TypeScript
6//! implementation and the legacy Python reference (`packages/agent/fec.py`)
7//! derive the same tables from the same polynomial, and
8//! `tools/fec-vectors.py` exists to prove it byte for byte.
9
10use std::sync::LazyLock;
11
12pub const POLY: u16 = 0x11d;
13
14const fn build_tables() -> ([u8; 512], [u8; 256]) {
15    let mut exp = [0u8; 512];
16    let mut log = [0u8; 256];
17    let mut x: u16 = 1;
18    let mut i = 0;
19    while i < 255 {
20        exp[i] = x as u8;
21        log[x as usize] = i as u8;
22        x <<= 1;
23        if x & 0x100 != 0 {
24            x ^= POLY;
25        }
26        i += 1;
27    }
28    let mut i = 255;
29    while i < 512 {
30        exp[i] = exp[i - 255];
31        i += 1;
32    }
33    (exp, log)
34}
35
36const TABLES: ([u8; 512], [u8; 256]) = build_tables();
37const EXP: &[u8; 512] = &TABLES.0;
38const LOG: &[u8; 256] = &TABLES.1;
39
40/// Flat 64 KiB multiply table: `MUL[(a << 8) | b] == a * b`.
41static MUL: LazyLock<Box<[u8]>> = LazyLock::new(|| {
42    let mut t = vec![0u8; 65536];
43    for a in 0..256usize {
44        for b in 0..256usize {
45            t[(a << 8) | b] = mul(a as u8, b as u8);
46        }
47    }
48    t.into_boxed_slice()
49});
50
51#[inline]
52pub fn mul(a: u8, b: u8) -> u8 {
53    if a == 0 || b == 0 {
54        0
55    } else {
56        EXP[LOG[a as usize] as usize + LOG[b as usize] as usize]
57    }
58}
59
60#[inline]
61pub fn inv(a: u8) -> u8 {
62    debug_assert!(a != 0, "inverse of zero");
63    EXP[255 - LOG[a as usize] as usize]
64}
65
66/// `dst[i] ^= coeff * src[i]` over the whole slice.
67///
68/// Scalar table lookup for now; the SIMD split-table variant lands with the
69/// performance pass (PLAN.md §1.7) behind the same signature.
70#[inline]
71pub fn madd_into(dst: &mut [u8], src: &[u8], coeff: u8) {
72    if coeff == 0 {
73        return;
74    }
75    debug_assert_eq!(dst.len(), src.len());
76    let base = (coeff as usize) << 8;
77    let table = &MUL[base..base + 256];
78    for (d, s) in dst.iter_mut().zip(src) {
79        *d ^= table[*s as usize];
80    }
81}
82
83#[cfg(test)]
84mod tests {
85    use super::*;
86
87    #[test]
88    fn inverse_roundtrip() {
89        for a in 1..=255u8 {
90            assert_eq!(mul(a, inv(a)), 1, "a={a}");
91        }
92    }
93
94    #[test]
95    fn known_products() {
96        // Spot checks against the Python reference tables.
97        assert_eq!(mul(2, 128), 0x1d);
98        assert_eq!(mul(3, 7), 9);
99        assert_eq!(inv(2), 0x8e);
100    }
101}
seyd_fec/gf.rs

seyd_fec/
gf.rs
