Skip to main content

cu_fec/
field.rs

1//! Finite-field operations used by RFC 8681.
2
3/// The finite field used for repair-symbol coefficients.
4#[derive(Clone, Copy, Debug, Eq, PartialEq)]
5pub enum Field {
6    /// Binary coefficients. Multiplication is logical AND and symbol addition is XOR.
7    Gf2,
8    /// Byte coefficients in GF(2^8), using the RFC 8681 polynomial `0x11d`.
9    Gf256,
10}
11
12impl Field {
13    /// Returns the RFC 8681 FEC Encoding ID: 9 for GF(2), 10 for GF(2^8).
14    pub const fn fec_encoding_id(self) -> u8 {
15        match self {
16            Self::Gf2 => 9,
17            Self::Gf256 => 10,
18        }
19    }
20
21    pub(crate) fn mul(self, lhs: u8, rhs: u8) -> u8 {
22        match self {
23            Self::Gf2 => lhs & rhs,
24            Self::Gf256 => gf256_mul(lhs, rhs),
25        }
26    }
27
28    pub(crate) fn inv(self, value: u8) -> u8 {
29        debug_assert_ne!(value, 0);
30        match self {
31            Self::Gf2 => 1,
32            Self::Gf256 => gf256_pow(value, 254),
33        }
34    }
35}
36
37fn gf256_mul(mut lhs: u8, mut rhs: u8) -> u8 {
38    let mut product = 0_u8;
39    for _ in 0..8 {
40        if rhs & 1 != 0 {
41            product ^= lhs;
42        }
43        let carry = lhs & 0x80 != 0;
44        lhs <<= 1;
45        if carry {
46            lhs ^= 0x1d;
47        }
48        rhs >>= 1;
49    }
50    product
51}
52
53fn gf256_pow(mut base: u8, mut exponent: u8) -> u8 {
54    let mut result = 1_u8;
55    while exponent != 0 {
56        if exponent & 1 != 0 {
57            result = gf256_mul(result, base);
58        }
59        base = gf256_mul(base, base);
60        exponent >>= 1;
61    }
62    result
63}
64
65#[cfg(test)]
66mod tests {
67    use super::*;
68
69    #[test]
70    fn gf256_uses_the_rfc_polynomial() {
71        assert_eq!(gf256_mul(0x80, 0x02), 0x1d);
72        assert_eq!(gf256_mul(0x57, 0x83), 0x31);
73    }
74
75    #[test]
76    fn every_nonzero_byte_has_an_inverse() {
77        for value in 1..=u8::MAX {
78            assert_eq!(gf256_mul(value, Field::Gf256.inv(value)), 1);
79        }
80    }
81}