reed_solomon_32/gf/
poly_math.rs

1use core::cmp::max;
2use crate::gf::poly::Polynom;
3use crate::gf;
4
5pub trait Scale {
6    fn scale(&self, x: u8) -> Polynom;
7    fn scale_assign(&mut self, x: u8) -> &mut Self;
8}
9
10pub trait Add {
11    fn add(&self, rhs: &Self) -> Polynom;
12    fn add_assign(&mut self, rhs: &Self) -> &mut Self;
13}
14
15pub trait Mul {
16    fn mul(&self, rhs: &Self) -> Polynom;
17}
18
19pub trait Div {
20    fn div(&self, rhs: &Self) -> (Polynom, Polynom);
21}
22
23pub trait Eval {
24    fn eval(&self, x: u8) -> u8;
25}
26
27impl Scale for [u8] {
28    #[inline]
29    fn scale(&self, x: u8) -> Polynom {
30        let mut poly = Polynom::from(self);
31        poly.scale_assign(x);
32        poly
33    }
34
35    #[inline]
36    fn scale_assign(&mut self, x: u8) -> &mut Self {
37        for px in self.iter_mut() {
38            *px = gf::mul(*px, x);
39        }
40        self
41    }
42}
43
44impl Add for [u8] {
45    fn add(&self, rhs: &Self) -> Polynom {
46        let mut poly = Polynom::with_length(max(self.len(), rhs.len()));
47
48        for (i, x) in self.iter().enumerate() {
49            let index = i + poly.len() - self.len();
50            poly[index] = *x;
51        }
52
53        for (i, x) in rhs.iter().enumerate() {
54            let index = i + poly.len() - rhs.len();
55            poly[index] ^= *x;
56        }
57
58        poly
59    }
60
61    fn add_assign(&mut self, rhs: &Self) -> &mut Self {
62        let poly = self.add(rhs);
63        self.copy_from_slice(&poly);
64        self
65    }
66}
67
68impl Mul for [u8] {
69    #[inline]
70    fn mul(&self, rhs: &Self) -> Polynom {
71        let mut poly = Polynom::with_length(self.len() + rhs.len() - 1);
72
73        for (j, rhs_x) in rhs.iter().enumerate() {
74            for (i, self_x) in self.iter().enumerate() {
75                poly[i + j] ^= gf::mul(*self_x, *rhs_x);
76            }
77        }
78
79        poly
80    }
81}
82
83impl Div for [u8] {
84    fn div(&self, rhs: &Self) -> (Polynom, Polynom) {
85        let mut poly = Polynom::from(self);
86
87        // If divisor's degree (len-1) is bigger, all dividend is a remainder
88        let divisor_degree = rhs.len() - 1;
89        if self.len() < divisor_degree {
90            return (Polynom::new(), poly);
91        }
92
93        for i in 0..(self.len() - divisor_degree) {
94            let coef = poly[i];
95            if coef != 0 {
96                for j in 1..rhs.len() {
97                    if rhs[j] != 0 {
98                        poly[i + j] ^= gf::mul(rhs[j], coef);
99                    }
100                }
101            }
102        }
103
104        let separator = self.len() - (rhs.len() - 1);
105
106        // Quotient is after separator
107        let remainder = Polynom::from(&poly[separator..]);
108
109        // And reminder is before separator, so just shrink to it
110        poly.set_length(separator);
111
112        (poly, remainder)
113    }
114}
115
116impl Eval for [u8] {
117    #[inline]
118    fn eval(&self, x: u8) -> u8 {
119        let mut y = self[0];
120        for px in self.iter().skip(1) {
121            y = gf::mul(y, x) ^ px;
122        }
123        y
124    }
125}
126
127
128#[cfg(test)]
129mod tests {
130    use super::*;
131
132    #[test]
133    fn scale() {
134        let poly = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
135        let answer = [0, 3, 6, 5, 12, 15, 10, 9, 24, 27];
136        assert_eq!(answer, *(poly.scale(3)));
137    }
138
139    #[test]
140    fn scale_assign() {
141        let mut poly = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
142        let answer = [0, 3, 6, 5, 12, 15, 10, 9, 24, 27];
143        assert_eq!(answer,
144                   *({
145                       poly.scale_assign(3);
146                       &poly
147                   }));
148    }
149
150    #[test]
151    fn add() {
152        let px = [0, 5, 10, 15, 20];
153        let py = [3, 9, 17, 24, 75];
154        assert_eq!([3, 12, 27, 23, 95], *(px.add(&py)));
155
156        let px = [0, 5, 10];
157        let py = [3, 9, 17, 24, 75];
158
159        assert_eq!([3, 9, 17, 29, 65], *(px.add(&py)));
160        assert_eq!([3, 9, 17, 29, 65], *(py.add(&px)))
161    }
162
163    #[test]
164    fn mul() {
165        let px = [0, 5, 10, 15];
166        let py = [3, 9, 17, 24];
167        assert_eq!([0, 15, 22, 30, 20, 15, 28], *(px.mul(&py)));
168
169        let px = [0, 5, 10];
170        let py = [3, 9, 17, 24];
171
172        assert_eq!([0, 15, 22, 15, 12, 11], *(px.mul(&py)));
173        assert_eq!([0, 15, 22, 15, 12, 11], *(py.mul(&px)));
174    }
175
176    #[test]
177    fn div() {
178        let px = [0, 5, 10, 15];
179        let py = [3, 9, 17, 24];
180
181        let (q, r) = px.div(&py);
182        assert_eq!([0], *q);
183        assert_eq!([5, 10, 15], *r);
184
185        let (q, r) = py.div(&px);
186        assert_eq!([3], *q);
187        assert_eq!([6, 15, 9], *r);
188    }
189
190    #[test]
191    fn eval() {
192        let p = [0, 5, 10, 15, 20];
193        let tests = [4, 7, 21];
194        let answers = [27, 30, 21];
195
196        for i in 0..tests.len() {
197            assert_eq!(answers[i], p.eval(tests[i]));
198        }
199    }
200}
reed_solomon_32/gf/poly_math.rs

reed_solomon_32/gf/
poly_math.rs
