bp_core/coding/
gf256.rs

1//! Arithmetic in GF(2⁸) — the Galois field with 256 elements.
2//!
3//! Uses the standard AES irreducible polynomial:
4//!   **p(x) = x⁸ + x⁴ + x³ + x + 1** (0x11b)
5//!
6//! ## Operations
7//! - [`add`] — addition = XOR (free)
8//! - [`mul`] — multiplication via Russian-peasant (8 iterations, no lookup tables)
9//! - [`inv`] — multiplicative inverse via Fermat: a⁻¹ = a²⁵⁴
10//! - [`div`] — division = mul(a, inv(b))
11//!
12//! Element 0 is the additive identity. Element 1 is the multiplicative identity.
13//! Calling [`inv`] or [`div`] with b=0 panics (division by zero).
14
15/// Lower 8 bits of the AES reduction polynomial (x⁸ + x⁴ + x³ + x + 1).
16const POLY: u8 = 0x1b;
17
18/// Addition in GF(2⁸) — identical to XOR.
19#[inline(always)]
20pub fn add(a: u8, b: u8) -> u8 {
21    a ^ b
22}
23
24/// Multiplication in GF(2⁸) using the Russian-peasant algorithm.
25/// Runs in exactly 8 iterations regardless of input values.
26#[inline]
27pub fn mul(mut a: u8, mut b: u8) -> u8 {
28    let mut result = 0u8;
29    for _ in 0..8 {
30        if b & 1 != 0 {
31            result ^= a;
32        }
33        let high = a & 0x80;
34        a <<= 1;
35        if high != 0 {
36            a ^= POLY;
37        }
38        b >>= 1;
39    }
40    result
41}
42
43/// Multiplicative inverse of `a` via Fermat's little theorem: a⁻¹ = a^254.
44///
45/// # Panics
46/// Panics if `a == 0`.
47#[inline]
48pub fn inv(a: u8) -> u8 {
49    assert!(a != 0, "gf256::inv: inverse of 0 is undefined");
50    // Compute a^254 using repeated squaring.
51    // 254 = 0b11111110 → exponents: 2, 4, 8, 16, 32, 64, 128 → product = 2^1*...*2^7 = 2^(1+2+...+7)
52    // But we need exactly a^254:
53    //   a^2 * a^4 * a^8 * a^16 * a^32 * a^64 * a^128
54    //   = a^(2+4+8+16+32+64+128) = a^254 ✓
55    let a2 = mul(a, a);
56    let a4 = mul(a2, a2);
57    let a8 = mul(a4, a4);
58    let a16 = mul(a8, a8);
59    let a32 = mul(a16, a16);
60    let a64 = mul(a32, a32);
61    let a128 = mul(a64, a64);
62    mul(mul(mul(mul(mul(mul(a2, a4), a8), a16), a32), a64), a128)
63}
64
65/// Division in GF(2⁸): `a / b = a · b⁻¹`.
66///
67/// # Panics
68/// Panics if `b == 0`.
69#[inline]
70pub fn div(a: u8, b: u8) -> u8 {
71    if a == 0 {
72        return 0;
73    }
74    mul(a, inv(b))
75}
76
77/// `acc[i] ^= coeff * symbol[i]` over GF(2⁸) — the inner loop of RLNC encoding.
78///
79/// # Panics
80/// Panics if `acc.len() != symbol.len()`.
81pub fn mul_acc(acc: &mut [u8], symbol: &[u8], coeff: u8) {
82    assert_eq!(acc.len(), symbol.len(), "gf256::mul_acc: length mismatch");
83    if coeff == 0 {
84        return;
85    }
86    if coeff == 1 {
87        for (a, &s) in acc.iter_mut().zip(symbol.iter()) {
88            *a ^= s;
89        }
90        return;
91    }
92    for (a, &s) in acc.iter_mut().zip(symbol.iter()) {
93        *a ^= mul(coeff, s);
94    }
95}
96
97#[cfg(test)]
98mod tests {
99    use super::*;
100
101    #[test]
102    fn add_is_xor() {
103        assert_eq!(add(0x53, 0xca), 0x53 ^ 0xca);
104    }
105
106    #[test]
107    fn mul_known_value() {
108        // 0x53 * 0xca == 0x01 in GF(2^8) with poly 0x11b — verified by hand
109        assert_eq!(mul(0x53, 0xca), 0x01);
110    }
111
112    #[test]
113    fn mul_by_zero_and_one() {
114        assert_eq!(mul(0xff, 0x00), 0x00);
115        assert_eq!(mul(0x00, 0x53), 0x00);
116        assert_eq!(mul(0xab, 0x01), 0xab);
117        assert_eq!(mul(0x01, 0xcd), 0xcd);
118    }
119
120    #[test]
121    fn mul_commutative() {
122        for a in [0x00u8, 0x01, 0x53, 0xca, 0xff] {
123            for b in [0x00u8, 0x01, 0x53, 0xca, 0xff] {
124                assert_eq!(mul(a, b), mul(b, a));
125            }
126        }
127    }
128
129    #[test]
130    fn inv_times_self_is_one() {
131        for a in 1u8..=255 {
132            assert_eq!(mul(a, inv(a)), 1, "a*inv(a) != 1 for a={a:#x}");
133        }
134    }
135
136    #[test]
137    fn div_round_trip() {
138        assert_eq!(mul(div(0x53, 0x2b), 0x2b), 0x53);
139    }
140
141    #[test]
142    fn mul_acc_accumulates_correctly() {
143        let mut acc = vec![0u8; 3];
144        mul_acc(&mut acc, &[0x01, 0x02, 0x03], 0x02);
145        assert_eq!(acc[0], mul(0x02, 0x01));
146        assert_eq!(acc[1], mul(0x02, 0x02));
147        assert_eq!(acc[2], mul(0x02, 0x03));
148    }
149}
bp_core/coding/gf256.rs

bp_core/coding/
gf256.rs
