ps-ecc 0.1.0-9

Generates Reed-Solomon error correction codes.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130

use crate::{
    finite_field::{add, mul},
    Polynomial,
};

impl Polynomial {
    /// Evaluates a polynomial given its coefficients at the given point using Horner's method.
    ///
    /// Coefficients are ordered from degree 0 (constant term) to the leading term.
    #[must_use]
    pub fn eval_coefficients_at(coefficients: &[u8], x: u8) -> u8 {
        let mut result = 0u8;

        for &coef in coefficients.iter().rev() {
            result = add(mul(result, x), coef);
        }

        result
    }
}

#[cfg(test)]
mod tests {
    use crate::{
        finite_field::{add, mul},
        Polynomial,
    };

    /// Computes expected value using naive polynomial evaluation.
    fn naive_eval(coefficients: &[u8], x: u8) -> u8 {
        let mut result = 0u8;
        let mut x_pow = 1u8;

        for &c in coefficients {
            result = add(result, mul(c, x_pow));
            x_pow = mul(x_pow, x);
        }

        result
    }

    /// Asserts that `eval_coefficients_at` matches naive evaluation for all x in 0..=255.
    fn assert_exhaustive(coefficients: &[u8]) {
        for x in 0..=255u8 {
            assert_eq!(
                Polynomial::eval_coefficients_at(coefficients, x),
                naive_eval(coefficients, x)
            );
        }
    }

    #[test]
    fn empty_slice() {
        assert_exhaustive(&[]);
    }

    #[test]
    fn zero_polynomial() {
        assert_exhaustive(&[0]);
    }

    #[test]
    fn constant_polynomial() {
        assert_exhaustive(&[1]);
        assert_exhaustive(&[42]);
        assert_exhaustive(&[128]);
        assert_exhaustive(&[255]);
    }

    #[test]
    fn linear_polynomial() {
        assert_exhaustive(&[5, 3]);
        assert_exhaustive(&[0, 1]);
        assert_exhaustive(&[255, 255]);
    }

    #[test]
    fn quadratic_polynomial() {
        assert_exhaustive(&[1, 0, 1]);
        assert_exhaustive(&[0, 0, 1]);
        assert_exhaustive(&[255, 128, 64]);
    }

    #[test]
    fn cubic_polynomial() {
        assert_exhaustive(&[0x12, 0x34, 0x56, 0x78]);
        assert_exhaustive(&[1, 1, 1, 1]);
        assert_exhaustive(&[0, 0, 0, 1]);
    }

    #[test]
    fn high_degree_polynomial() {
        assert_exhaustive(&[1, 2, 3, 4, 5, 6, 7, 8]);
        assert_exhaustive(&[0, 0, 0, 0, 0, 0, 0, 1]);
    }

    #[test]
    fn sparse_polynomial() {
        assert_exhaustive(&[1, 0, 0, 0, 1]);
        assert_exhaustive(&[0, 1, 0, 1, 0]);
    }

    #[test]
    fn all_coefficients_max() {
        assert_exhaustive(&[255, 255, 255, 255]);
    }

    #[test]
    fn max_degree_monomial() {
        let mut coefficients = [0u8; Polynomial::MAX_COEFFICIENTS as usize];

        coefficients[Polynomial::MAX_DEGREE as usize] = 1;

        assert_exhaustive(&coefficients);
    }

    #[test]
    fn max_degree_all_ones() {
        let coefficients = [1u8; Polynomial::MAX_COEFFICIENTS as usize];

        assert_exhaustive(&coefficients);
    }

    #[test]
    fn max_degree_all_max() {
        let coefficients = [255u8; Polynomial::MAX_COEFFICIENTS as usize];

        assert_exhaustive(&coefficients);
    }
}