code_rs/coding/
reed_solomon.rs

1//! Encoding and decoding of the (24, 12, 13) short, (24, 16, 9) medium, and (36, 20, 17)
2//! long Reed-Solomon codes described by P25.
3//!
4//! These algorithms are sourced from *Coding Theory and Cryptography: The Essentials*,
5//! Hankerson, Hoffman, et al, 2000.
6
7use std;
8
9use collect_slice::CollectSlice;
10
11use crate::bits::Hexbit;
12use crate::coding::bmcf;
13use crate::coding::galois::{P25Codeword, Polynomial, PolynomialCoefs};
14
15/// Encoding and decoding of the (24, 12, 13) code.
16pub mod short {
17    use crate::bits::Hexbit;
18
19    /// Transpose of G_LC.
20    const GEN: [[u8; 12]; 12] = [
21        [
22            0o62, 0o11, 0o03, 0o21, 0o30, 0o01, 0o61, 0o24, 0o72, 0o72, 0o73, 0o71,
23        ],
24        [
25            0o44, 0o12, 0o01, 0o70, 0o22, 0o41, 0o76, 0o22, 0o42, 0o14, 0o65, 0o05,
26        ],
27        [
28            0o03, 0o11, 0o05, 0o27, 0o03, 0o27, 0o21, 0o71, 0o05, 0o65, 0o36, 0o55,
29        ],
30        [
31            0o25, 0o11, 0o75, 0o45, 0o75, 0o56, 0o55, 0o56, 0o20, 0o54, 0o61, 0o03,
32        ],
33        [
34            0o14, 0o16, 0o14, 0o16, 0o15, 0o76, 0o76, 0o21, 0o43, 0o35, 0o42, 0o71,
35        ],
36        [
37            0o16, 0o64, 0o06, 0o67, 0o15, 0o64, 0o01, 0o35, 0o47, 0o25, 0o22, 0o34,
38        ],
39        [
40            0o27, 0o67, 0o20, 0o23, 0o33, 0o21, 0o63, 0o73, 0o33, 0o41, 0o17, 0o60,
41        ],
42        [
43            0o03, 0o55, 0o44, 0o64, 0o15, 0o53, 0o35, 0o42, 0o56, 0o16, 0o04, 0o11,
44        ],
45        [
46            0o53, 0o01, 0o66, 0o73, 0o51, 0o04, 0o30, 0o57, 0o01, 0o15, 0o44, 0o74,
47        ],
48        [
49            0o04, 0o76, 0o06, 0o33, 0o03, 0o25, 0o13, 0o74, 0o16, 0o40, 0o20, 0o02,
50        ],
51        [
52            0o36, 0o26, 0o70, 0o44, 0o53, 0o01, 0o64, 0o43, 0o13, 0o71, 0o25, 0o41,
53        ],
54        [
55            0o47, 0o73, 0o66, 0o21, 0o50, 0o12, 0o70, 0o76, 0o76, 0o26, 0o05, 0o50,
56        ],
57    ];
58
59    /// Calculate the 12 parity hexbits for the first 12 data hexbits in the given buffer,
60    /// placing the parity hexbits at the end of the buffer.
61    pub fn encode(buf: &mut [Hexbit; 24]) {
62        let (data, parity) = buf.split_at_mut(12);
63        super::encode(data, parity, GEN.iter().map(|r| &r[..]));
64    }
65
66    /// Try to decode the given 24-hexbit word to the nearest codeword, correcting up to 6
67    /// hexbit errors (up to 36 bit errors.)
68    ///
69    /// If decoding was successful, return `Some((data, err))`, where `data` is the 12
70    /// data hexbits and `err` is the number of corrected hexbits. Otherwise, return
71    /// `None` to indicate an unrecoverable error.
72    pub fn decode(buf: &mut [Hexbit; 24]) -> Option<(&[Hexbit], usize)> {
73        super::decode::<super::ShortCoefs>(buf)
74            .map(move |(poly, err)| (super::extract_data(poly, &mut buf[..12]), err))
75    }
76}
77
78/// Encoding and decoding of the (24, 16, 9) code.
79pub mod medium {
80    use crate::bits::Hexbit;
81
82    /// Transpose of G_ES.
83    const GEN: [[u8; 16]; 8] = [
84        [
85            0o51, 0o57, 0o05, 0o73, 0o75, 0o20, 0o02, 0o24, 0o42, 0o32, 0o65, 0o64, 0o62, 0o55,
86            0o24, 0o67,
87        ],
88        [
89            0o45, 0o25, 0o01, 0o07, 0o15, 0o32, 0o75, 0o74, 0o64, 0o32, 0o36, 0o06, 0o63, 0o43,
90            0o23, 0o75,
91        ],
92        [
93            0o67, 0o63, 0o31, 0o47, 0o51, 0o14, 0o43, 0o15, 0o07, 0o55, 0o25, 0o54, 0o74, 0o34,
94            0o23, 0o45,
95        ],
96        [
97            0o15, 0o73, 0o04, 0o14, 0o51, 0o42, 0o05, 0o72, 0o22, 0o41, 0o07, 0o32, 0o70, 0o71,
98            0o05, 0o60,
99        ],
100        [
101            0o64, 0o71, 0o16, 0o41, 0o17, 0o75, 0o01, 0o24, 0o61, 0o57, 0o50, 0o76, 0o05, 0o57,
102            0o50, 0o57,
103        ],
104        [
105            0o67, 0o22, 0o54, 0o77, 0o67, 0o42, 0o40, 0o26, 0o20, 0o66, 0o16, 0o46, 0o27, 0o76,
106            0o70, 0o24,
107        ],
108        [
109            0o52, 0o40, 0o25, 0o47, 0o17, 0o70, 0o12, 0o74, 0o40, 0o21, 0o40, 0o14, 0o37, 0o50,
110            0o42, 0o06,
111        ],
112        [
113            0o12, 0o15, 0o76, 0o11, 0o57, 0o54, 0o64, 0o61, 0o65, 0o77, 0o51, 0o36, 0o46, 0o64,
114            0o23, 0o26,
115        ],
116    ];
117
118    /// Calculate the 8 parity hexbits for the first 16 data hexbits in the given buffer,
119    /// placing the parity hexbits at the end of the buffer.
120    pub fn encode(buf: &mut [Hexbit; 24]) {
121        let (data, parity) = buf.split_at_mut(16);
122        super::encode(data, parity, GEN.iter().map(|r| &r[..]));
123    }
124
125    /// Try to decode the given 24-hexbit word to the nearest codeword, correcting up to 4
126    /// hexbit errors (up to 24 bit errors.)
127    ///
128    /// If decoding was successful, return `Some((data, err))`, where `data` is the 16
129    /// data hexbits and `err` is the number of corrected hexbits. Otherwise, return
130    /// `None` to indicate an unrecoverable error.
131    pub fn decode(buf: &mut [Hexbit; 24]) -> Option<(&[Hexbit], usize)> {
132        super::decode::<super::MedCoefs>(buf)
133            .map(move |(poly, err)| (super::extract_data(poly, &mut buf[..16]), err))
134    }
135}
136
137/// Encoding and decoding of the (36, 20, 17) code.
138pub mod long {
139    use crate::bits::Hexbit;
140
141    /// Transpose of P_HDR.
142    const GEN: [[u8; 20]; 16] = [
143        [
144            0o74, 0o04, 0o07, 0o26, 0o23, 0o24, 0o52, 0o55, 0o54, 0o74, 0o54, 0o51, 0o01, 0o11,
145            0o06, 0o34, 0o63, 0o71, 0o02, 0o34,
146        ],
147        [
148            0o37, 0o17, 0o23, 0o05, 0o73, 0o51, 0o33, 0o62, 0o51, 0o41, 0o70, 0o07, 0o65, 0o70,
149            0o02, 0o31, 0o43, 0o21, 0o01, 0o35,
150        ],
151        [
152            0o34, 0o50, 0o37, 0o07, 0o73, 0o25, 0o14, 0o56, 0o32, 0o30, 0o11, 0o72, 0o32, 0o05,
153            0o65, 0o01, 0o25, 0o70, 0o53, 0o02,
154        ],
155        [
156            0o06, 0o24, 0o46, 0o63, 0o41, 0o23, 0o02, 0o25, 0o65, 0o41, 0o03, 0o30, 0o70, 0o10,
157            0o11, 0o15, 0o44, 0o44, 0o74, 0o23,
158        ],
159        [
160            0o02, 0o11, 0o56, 0o63, 0o72, 0o22, 0o20, 0o73, 0o77, 0o43, 0o13, 0o65, 0o13, 0o65,
161            0o41, 0o44, 0o77, 0o56, 0o02, 0o21,
162        ],
163        [
164            0o07, 0o05, 0o75, 0o27, 0o34, 0o41, 0o06, 0o60, 0o12, 0o22, 0o22, 0o54, 0o44, 0o24,
165            0o20, 0o64, 0o63, 0o04, 0o14, 0o27,
166        ],
167        [
168            0o44, 0o30, 0o43, 0o63, 0o21, 0o74, 0o14, 0o15, 0o54, 0o51, 0o16, 0o06, 0o73, 0o15,
169            0o45, 0o16, 0o17, 0o30, 0o52, 0o22,
170        ],
171        [
172            0o64, 0o57, 0o45, 0o40, 0o51, 0o66, 0o25, 0o30, 0o13, 0o06, 0o57, 0o21, 0o24, 0o77,
173            0o42, 0o24, 0o17, 0o74, 0o74, 0o33,
174        ],
175        [
176            0o26, 0o33, 0o55, 0o06, 0o67, 0o74, 0o52, 0o13, 0o35, 0o64, 0o03, 0o36, 0o12, 0o22,
177            0o46, 0o52, 0o64, 0o04, 0o12, 0o64,
178        ],
179        [
180            0o14, 0o03, 0o21, 0o04, 0o16, 0o65, 0o23, 0o17, 0o32, 0o33, 0o45, 0o63, 0o52, 0o24,
181            0o54, 0o16, 0o14, 0o23, 0o57, 0o42,
182        ],
183        [
184            0o26, 0o02, 0o50, 0o40, 0o31, 0o70, 0o35, 0o20, 0o56, 0o03, 0o72, 0o50, 0o21, 0o24,
185            0o35, 0o06, 0o40, 0o71, 0o24, 0o05,
186        ],
187        [
188            0o44, 0o02, 0o31, 0o45, 0o74, 0o36, 0o74, 0o02, 0o12, 0o47, 0o31, 0o61, 0o55, 0o74,
189            0o12, 0o62, 0o74, 0o70, 0o63, 0o73,
190        ],
191        [
192            0o54, 0o15, 0o45, 0o47, 0o11, 0o67, 0o75, 0o70, 0o75, 0o27, 0o30, 0o64, 0o12, 0o07,
193            0o40, 0o20, 0o31, 0o63, 0o15, 0o51,
194        ],
195        [
196            0o13, 0o16, 0o27, 0o30, 0o21, 0o45, 0o75, 0o55, 0o01, 0o12, 0o56, 0o52, 0o35, 0o44,
197            0o64, 0o13, 0o72, 0o45, 0o42, 0o46,
198        ],
199        [
200            0o77, 0o25, 0o71, 0o75, 0o12, 0o64, 0o43, 0o14, 0o72, 0o55, 0o35, 0o01, 0o14, 0o07,
201            0o65, 0o55, 0o54, 0o56, 0o52, 0o73,
202        ],
203        [
204            0o05, 0o26, 0o62, 0o07, 0o21, 0o01, 0o27, 0o47, 0o63, 0o47, 0o22, 0o60, 0o72, 0o46,
205            0o33, 0o57, 0o06, 0o43, 0o33, 0o60,
206        ],
207    ];
208
209    /// Calculate the 16 parity hexbits for the first 20 data hexbits in the given buffer,
210    /// placing the parity hexbits at the end of the buffer.
211    pub fn encode(buf: &mut [Hexbit; 36]) {
212        let (data, parity) = buf.split_at_mut(20);
213        super::encode(data, parity, GEN.iter().map(|r| &r[..]))
214    }
215
216    /// Try to decode the given 36-hexbit word to the nearest codeword, correcting up to 8
217    /// hexbit errors (up to 48 bit errors.)
218    ///
219    /// If decoding was successful, return `Some((data, err))`, where `data` is the 20
220    /// data hexbits and `err` is the number of corrected hexbits. Otherwise, return
221    /// `None` to indicate an unrecoverable error.
222    pub fn decode(buf: &mut [Hexbit; 36]) -> Option<(&[Hexbit], usize)> {
223        super::decode::<super::LongCoefs>(buf)
224            .map(move |(poly, err)| (super::extract_data(poly, &mut buf[..20]), err))
225    }
226}
227
228/// Encode the given data with the given generator matrix and place the resulting parity
229/// symbols in the given destination.
230fn encode<'g, G>(data: &[Hexbit], parity: &mut [Hexbit], gen: G)
231where
232    G: Iterator<Item = &'g [u8]>,
233{
234    gen.map(|row| {
235        row.iter()
236            .zip(data.iter())
237            .fold(P25Codeword::default(), |s, (&col, &d)| {
238                s + P25Codeword::new(d.bits()) * P25Codeword::new(col)
239            })
240            .bits()
241    })
242    .map(Hexbit::new)
243    .collect_slice_checked(parity);
244}
245
246/// Try to fix any errors in the given word.
247///
248/// On success, return `Some((poly, err))`, where `poly` is the polynomial representation
249/// of the corrected word (with the last data symbol as the degree-0 coefficient) and
250/// `err` is the number of corrected hexbit symbols. Otherwise, return `None` to indicate
251/// an unrecoverable error.
252fn decode<P: PolynomialCoefs>(word: &[Hexbit]) -> Option<(Polynomial<P>, usize)> {
253    // In the polynomial representation, the first received symbol corresponds to the
254    // coefficient of the highest-degree term.
255    let mut poly = Polynomial::new(word.iter().rev().map(|&b| P25Codeword::new(b.bits())));
256
257    bmcf::Errors::new(syndromes(&poly)).and_then(|(nerr, errs)| {
258        for (loc, pat) in errs {
259            match poly.get_mut(loc) {
260                Some(coef) => *coef = *coef + pat,
261                None => return None,
262            }
263        }
264
265        Some((poly, nerr))
266    })
267}
268
269/// Generate the syndrome polynomial s(x) from the given received word r(x).
270///
271/// The resulting polynomial has the form s(x) = s<sub>1</sub> + s<sub>2</sub>x + ··· +
272/// s<sub>2t</sub>x<sup>2t</sup>, where s<sub>i</sub> = r(α<sup>i</sup>).
273fn syndromes<P: PolynomialCoefs>(word: &Polynomial<P>) -> Polynomial<P> {
274    Polynomial::new((1..=P::syndromes()).map(|p| {
275        // Compute r(α^p).
276        word.eval(P25Codeword::for_power(p))
277    }))
278}
279
280/// Extract the data symbols from the given polynomial-form word and write them to the
281/// given slice.
282fn extract_data<P>(poly: Polynomial<P>, data: &mut [Hexbit]) -> &[Hexbit]
283where
284    P: PolynomialCoefs,
285{
286    poly.iter()
287        .rev()
288        .map(|coef| Hexbit::new(coef.bits()))
289        .collect_slice_fill(data);
290    data
291}
292
293impl_polynomial_coefs!(ShortCoefs, 13, 24);
294impl_polynomial_coefs!(MedCoefs, 9, 24);
295impl_polynomial_coefs!(LongCoefs, 17, 36);
296
297#[cfg(test)]
298mod test {
299    use super::*;
300    use super::{LongCoefs, MedCoefs, ShortCoefs};
301    use crate::bits::Hexbit;
302    use crate::coding::galois::{P25Codeword, Polynomial, PolynomialCoefs};
303    use collect_slice::CollectSlice;
304
305    #[test]
306    fn validate_coefs() {
307        ShortCoefs::default().validate();
308        MedCoefs::default().validate();
309        LongCoefs::default().validate();
310    }
311
312    #[test]
313    fn verify_short_gen() {
314        let p = Polynomial::<ShortCoefs>::new(
315            [P25Codeword::for_power(1), P25Codeword::for_power(0)]
316                .iter()
317                .cloned(),
318        ) * Polynomial::new(
319            [P25Codeword::for_power(2), P25Codeword::for_power(0)]
320                .iter()
321                .cloned(),
322        ) * Polynomial::new(
323            [P25Codeword::for_power(3), P25Codeword::for_power(0)]
324                .iter()
325                .cloned(),
326        ) * Polynomial::new(
327            [P25Codeword::for_power(4), P25Codeword::for_power(0)]
328                .iter()
329                .cloned(),
330        ) * Polynomial::new(
331            [P25Codeword::for_power(5), P25Codeword::for_power(0)]
332                .iter()
333                .cloned(),
334        ) * Polynomial::new(
335            [P25Codeword::for_power(6), P25Codeword::for_power(0)]
336                .iter()
337                .cloned(),
338        ) * Polynomial::new(
339            [P25Codeword::for_power(7), P25Codeword::for_power(0)]
340                .iter()
341                .cloned(),
342        ) * Polynomial::new(
343            [P25Codeword::for_power(8), P25Codeword::for_power(0)]
344                .iter()
345                .cloned(),
346        );
347
348        assert_eq!(p.degree().unwrap(), 8);
349        assert_eq!(p.coef(0).bits(), 0o26);
350        assert_eq!(p.coef(1).bits(), 0o06);
351        assert_eq!(p.coef(2).bits(), 0o24);
352        assert_eq!(p.coef(3).bits(), 0o57);
353        assert_eq!(p.coef(4).bits(), 0o60);
354        assert_eq!(p.coef(5).bits(), 0o45);
355        assert_eq!(p.coef(6).bits(), 0o75);
356        assert_eq!(p.coef(7).bits(), 0o67);
357        assert_eq!(p.coef(8).bits(), 0o01);
358    }
359
360    #[test]
361    fn verify_med_gen() {
362        let p = Polynomial::<MedCoefs>::new(
363            [P25Codeword::for_power(1), P25Codeword::for_power(0)]
364                .iter()
365                .cloned(),
366        ) * Polynomial::new(
367            [P25Codeword::for_power(2), P25Codeword::for_power(0)]
368                .iter()
369                .cloned(),
370        ) * Polynomial::new(
371            [P25Codeword::for_power(3), P25Codeword::for_power(0)]
372                .iter()
373                .cloned(),
374        ) * Polynomial::new(
375            [P25Codeword::for_power(4), P25Codeword::for_power(0)]
376                .iter()
377                .cloned(),
378        ) * Polynomial::new(
379            [P25Codeword::for_power(5), P25Codeword::for_power(0)]
380                .iter()
381                .cloned(),
382        ) * Polynomial::new(
383            [P25Codeword::for_power(6), P25Codeword::for_power(0)]
384                .iter()
385                .cloned(),
386        ) * Polynomial::new(
387            [P25Codeword::for_power(7), P25Codeword::for_power(0)]
388                .iter()
389                .cloned(),
390        ) * Polynomial::new(
391            [P25Codeword::for_power(8), P25Codeword::for_power(0)]
392                .iter()
393                .cloned(),
394        ) * Polynomial::new(
395            [P25Codeword::for_power(9), P25Codeword::for_power(0)]
396                .iter()
397                .cloned(),
398        ) * Polynomial::new(
399            [P25Codeword::for_power(10), P25Codeword::for_power(0)]
400                .iter()
401                .cloned(),
402        ) * Polynomial::new(
403            [P25Codeword::for_power(11), P25Codeword::for_power(0)]
404                .iter()
405                .cloned(),
406        ) * Polynomial::new(
407            [P25Codeword::for_power(12), P25Codeword::for_power(0)]
408                .iter()
409                .cloned(),
410        );
411
412        assert_eq!(p.degree().unwrap(), 12);
413        assert_eq!(p.coef(0).bits(), 0o50);
414        assert_eq!(p.coef(1).bits(), 0o41);
415        assert_eq!(p.coef(2).bits(), 0o02);
416        assert_eq!(p.coef(3).bits(), 0o74);
417        assert_eq!(p.coef(4).bits(), 0o11);
418        assert_eq!(p.coef(5).bits(), 0o60);
419        assert_eq!(p.coef(6).bits(), 0o34);
420        assert_eq!(p.coef(7).bits(), 0o71);
421        assert_eq!(p.coef(8).bits(), 0o03);
422        assert_eq!(p.coef(9).bits(), 0o55);
423        assert_eq!(p.coef(10).bits(), 0o05);
424        assert_eq!(p.coef(11).bits(), 0o71);
425        assert_eq!(p.coef(12).bits(), 0o01);
426    }
427
428    #[test]
429    fn verify_long_gen() {
430        let p = Polynomial::<LongCoefs>::new(
431            [P25Codeword::for_power(1), P25Codeword::for_power(0)]
432                .iter()
433                .cloned(),
434        ) * Polynomial::new(
435            [P25Codeword::for_power(2), P25Codeword::for_power(0)]
436                .iter()
437                .cloned(),
438        ) * Polynomial::new(
439            [P25Codeword::for_power(3), P25Codeword::for_power(0)]
440                .iter()
441                .cloned(),
442        ) * Polynomial::new(
443            [P25Codeword::for_power(4), P25Codeword::for_power(0)]
444                .iter()
445                .cloned(),
446        ) * Polynomial::new(
447            [P25Codeword::for_power(5), P25Codeword::for_power(0)]
448                .iter()
449                .cloned(),
450        ) * Polynomial::new(
451            [P25Codeword::for_power(6), P25Codeword::for_power(0)]
452                .iter()
453                .cloned(),
454        ) * Polynomial::new(
455            [P25Codeword::for_power(7), P25Codeword::for_power(0)]
456                .iter()
457                .cloned(),
458        ) * Polynomial::new(
459            [P25Codeword::for_power(8), P25Codeword::for_power(0)]
460                .iter()
461                .cloned(),
462        ) * Polynomial::new(
463            [P25Codeword::for_power(9), P25Codeword::for_power(0)]
464                .iter()
465                .cloned(),
466        ) * Polynomial::new(
467            [P25Codeword::for_power(10), P25Codeword::for_power(0)]
468                .iter()
469                .cloned(),
470        ) * Polynomial::new(
471            [P25Codeword::for_power(11), P25Codeword::for_power(0)]
472                .iter()
473                .cloned(),
474        ) * Polynomial::new(
475            [P25Codeword::for_power(12), P25Codeword::for_power(0)]
476                .iter()
477                .cloned(),
478        ) * Polynomial::new(
479            [P25Codeword::for_power(13), P25Codeword::for_power(0)]
480                .iter()
481                .cloned(),
482        ) * Polynomial::new(
483            [P25Codeword::for_power(14), P25Codeword::for_power(0)]
484                .iter()
485                .cloned(),
486        ) * Polynomial::new(
487            [P25Codeword::for_power(15), P25Codeword::for_power(0)]
488                .iter()
489                .cloned(),
490        ) * Polynomial::new(
491            [P25Codeword::for_power(16), P25Codeword::for_power(0)]
492                .iter()
493                .cloned(),
494        );
495
496        assert_eq!(p.degree().unwrap(), 16);
497        assert_eq!(p.coef(0).bits(), 0o60);
498        assert_eq!(p.coef(1).bits(), 0o73);
499        assert_eq!(p.coef(2).bits(), 0o46);
500        assert_eq!(p.coef(3).bits(), 0o51);
501        assert_eq!(p.coef(4).bits(), 0o73);
502        assert_eq!(p.coef(5).bits(), 0o05);
503        assert_eq!(p.coef(6).bits(), 0o42);
504        assert_eq!(p.coef(7).bits(), 0o64);
505        assert_eq!(p.coef(8).bits(), 0o33);
506        assert_eq!(p.coef(9).bits(), 0o22);
507        assert_eq!(p.coef(10).bits(), 0o27);
508        assert_eq!(p.coef(11).bits(), 0o21);
509        assert_eq!(p.coef(12).bits(), 0o23);
510        assert_eq!(p.coef(13).bits(), 0o02);
511        assert_eq!(p.coef(14).bits(), 0o35);
512        assert_eq!(p.coef(15).bits(), 0o34);
513        assert_eq!(p.coef(16).bits(), 0o01);
514    }
515
516    #[test]
517    fn test_decode_short() {
518        let mut buf = [Hexbit::default(); 24];
519        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
520            .iter()
521            .map(|&b| Hexbit::new(b))
522            .collect_slice(&mut buf[..]);
523
524        short::encode(&mut buf);
525
526        buf[0] = Hexbit::new(0o00);
527        buf[2] = Hexbit::new(0o60);
528        buf[7] = Hexbit::new(0o42);
529        buf[13] = Hexbit::new(0o14);
530        buf[18] = Hexbit::new(0o56);
531        buf[23] = Hexbit::new(0o72);
532
533        let dec = short::decode(&mut buf);
534        let exp = [
535            Hexbit::new(1),
536            Hexbit::new(0),
537            Hexbit::new(0),
538            Hexbit::new(0),
539            Hexbit::new(0),
540            Hexbit::new(0),
541            Hexbit::new(0),
542            Hexbit::new(0),
543            Hexbit::new(0),
544            Hexbit::new(0),
545            Hexbit::new(0),
546            Hexbit::new(0),
547        ];
548
549        assert_eq!(dec, Some((&exp[..], 6)));
550    }
551
552    #[test]
553    fn test_decode_med() {
554        let mut buf = [Hexbit::default(); 24];
555        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
556            .iter()
557            .map(|&b| Hexbit::new(b))
558            .collect_slice(&mut buf[..]);
559
560        medium::encode(&mut buf);
561
562        buf[0] = Hexbit::new(0o00);
563        buf[10] = Hexbit::new(0o60);
564        buf[16] = Hexbit::new(0o42);
565        buf[23] = Hexbit::new(0o14);
566
567        let dec = medium::decode(&mut buf);
568        let exp = [
569            Hexbit::new(1),
570            Hexbit::new(0),
571            Hexbit::new(0),
572            Hexbit::new(0),
573            Hexbit::new(0),
574            Hexbit::new(0),
575            Hexbit::new(0),
576            Hexbit::new(0),
577            Hexbit::new(0),
578            Hexbit::new(0),
579            Hexbit::new(0),
580            Hexbit::new(0),
581            Hexbit::new(0),
582            Hexbit::new(0),
583            Hexbit::new(0),
584            Hexbit::new(0),
585        ];
586
587        assert_eq!(dec, Some((&exp[..], 4)));
588    }
589
590    #[test]
591    fn test_decode_long() {
592        // Test random error locations.
593        let mut buf = [Hexbit::default(); 36];
594        [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
595            .iter()
596            .map(|&b| Hexbit::new(b))
597            .collect_slice(&mut buf[..]);
598
599        long::encode(&mut buf);
600
601        buf[0] = Hexbit::new(0o00);
602        buf[2] = Hexbit::new(0o43);
603        buf[5] = Hexbit::new(0o21);
604        buf[10] = Hexbit::new(0o11);
605        buf[18] = Hexbit::new(0o67);
606        buf[22] = Hexbit::new(0o04);
607        buf[27] = Hexbit::new(0o12);
608        buf[30] = Hexbit::new(0o32);
609
610        let dec = long::decode(&mut buf);
611        let exp = [
612            Hexbit::new(1),
613            Hexbit::new(0),
614            Hexbit::new(0),
615            Hexbit::new(0),
616            Hexbit::new(0),
617            Hexbit::new(0),
618            Hexbit::new(0),
619            Hexbit::new(0),
620            Hexbit::new(0),
621            Hexbit::new(0),
622            Hexbit::new(0),
623            Hexbit::new(0),
624            Hexbit::new(0),
625            Hexbit::new(0),
626            Hexbit::new(0),
627            Hexbit::new(0),
628            Hexbit::new(0),
629            Hexbit::new(0),
630            Hexbit::new(0),
631            Hexbit::new(0),
632        ];
633
634        assert_eq!(dec, Some((&exp[..], 8)));
635
636        let exp = [
637            Hexbit::new(0o77),
638            Hexbit::new(0o77),
639            Hexbit::new(0o77),
640            Hexbit::new(0o77),
641            Hexbit::new(0o77),
642            Hexbit::new(0o77),
643            Hexbit::new(0o77),
644            Hexbit::new(0o77),
645            Hexbit::new(0o77),
646            Hexbit::new(0o77),
647            Hexbit::new(0o77),
648            Hexbit::new(0o77),
649            Hexbit::new(0o77),
650            Hexbit::new(0o77),
651            Hexbit::new(0o77),
652            Hexbit::new(0o77),
653            Hexbit::new(0o77),
654            Hexbit::new(0o77),
655            Hexbit::new(0o77),
656            Hexbit::new(0o77),
657        ];
658
659        // Test 6-bit error in each location.
660        for i in 0..36 {
661            let mut buf = [Hexbit::default(); 36];
662            [
663                0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77,
664                0o77, 0o77, 0o77, 0o77, 0o77, 0o77,
665            ]
666            .iter()
667            .cloned()
668            .map(Hexbit::new)
669            .collect_slice(&mut buf[..]);
670            long::encode(&mut buf);
671
672            buf[i] = Hexbit::new(0);
673            let dec = long::decode(&mut buf);
674
675            assert_eq!(dec, Some((&exp[..], 1)));
676        }
677
678        // Test contiguous 48-bit error.
679        for i in 0..29 {
680            let mut buf = [Hexbit::default(); 36];
681            [
682                0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77, 0o77,
683                0o77, 0o77, 0o77, 0o77, 0o77, 0o77,
684            ]
685            .iter()
686            .cloned()
687            .map(Hexbit::new)
688            .collect_slice(&mut buf[..]);
689            long::encode(&mut buf);
690
691            buf[i] = Hexbit::new(0);
692            buf[i + 1] = Hexbit::new(0);
693            buf[i + 2] = Hexbit::new(0);
694            buf[i + 3] = Hexbit::new(0);
695            buf[i + 4] = Hexbit::new(0);
696            buf[i + 5] = Hexbit::new(0);
697            buf[i + 6] = Hexbit::new(0);
698            buf[i + 7] = Hexbit::new(0);
699            let dec = long::decode(&mut buf);
700
701            assert_eq!(dec, Some((&exp[..], 8)));
702        }
703    }
704
705    #[test]
706    fn test_unrecoverable() {
707        // These unrecoverable received words caused divide-by-zero errors due to
708        // detectable discrepancy between the degree of the error locator polynomial and
709        // the number of roots found.
710
711        let mut w = [
712            Hexbit::new(0),
713            Hexbit::new(0),
714            Hexbit::new(0),
715            Hexbit::new(0),
716            Hexbit::new(0),
717            Hexbit::new(0),
718            Hexbit::new(0),
719            Hexbit::new(0),
720            Hexbit::new(0),
721            Hexbit::new(0),
722            Hexbit::new(0),
723            Hexbit::new(0),
724            Hexbit::new(0),
725            Hexbit::new(8),
726            Hexbit::new(0),
727            Hexbit::new(0),
728            Hexbit::new(0),
729            Hexbit::new(6),
730            Hexbit::new(46),
731            Hexbit::new(28),
732            Hexbit::new(27),
733            Hexbit::new(63),
734            Hexbit::new(38),
735            Hexbit::new(0),
736            Hexbit::new(36),
737            Hexbit::new(4),
738            Hexbit::new(0),
739            Hexbit::new(0),
740            Hexbit::new(24),
741            Hexbit::new(0),
742            Hexbit::new(27),
743            Hexbit::new(47),
744            Hexbit::new(0),
745            Hexbit::new(0),
746            Hexbit::new(0),
747            Hexbit::new(0),
748        ];
749        assert_eq!(long::decode(&mut w), None);
750
751        let mut w = [
752            Hexbit::new(0),
753            Hexbit::new(0),
754            Hexbit::new(0),
755            Hexbit::new(0),
756            Hexbit::new(0),
757            Hexbit::new(0),
758            Hexbit::new(0),
759            Hexbit::new(0),
760            Hexbit::new(0),
761            Hexbit::new(0),
762            Hexbit::new(0),
763            Hexbit::new(0),
764            Hexbit::new(0),
765            Hexbit::new(8),
766            Hexbit::new(0),
767            Hexbit::new(0),
768            Hexbit::new(0),
769            Hexbit::new(3),
770            Hexbit::new(28),
771            Hexbit::new(0),
772            Hexbit::new(0),
773            Hexbit::new(29),
774            Hexbit::new(4),
775            Hexbit::new(8),
776            Hexbit::new(46),
777            Hexbit::new(0),
778            Hexbit::new(19),
779            Hexbit::new(0),
780            Hexbit::new(0),
781            Hexbit::new(11),
782            Hexbit::new(0),
783            Hexbit::new(52),
784            Hexbit::new(0),
785            Hexbit::new(53),
786            Hexbit::new(35),
787            Hexbit::new(3),
788        ];
789        assert_eq!(long::decode(&mut w), None);
790
791        // More general unrecoverable words.
792
793        let mut w = [
794            Hexbit::new(0),
795            Hexbit::new(0),
796            Hexbit::new(0),
797            Hexbit::new(0),
798            Hexbit::new(0),
799            Hexbit::new(0),
800            Hexbit::new(0),
801            Hexbit::new(0),
802            Hexbit::new(0),
803            Hexbit::new(0),
804            Hexbit::new(0),
805            Hexbit::new(0),
806            Hexbit::new(0),
807            Hexbit::new(0),
808            Hexbit::new(4),
809            Hexbit::new(51),
810            Hexbit::new(0),
811            Hexbit::new(33),
812            Hexbit::new(39),
813            Hexbit::new(34),
814            Hexbit::new(0),
815            Hexbit::new(20),
816            Hexbit::new(48),
817            Hexbit::new(44),
818            Hexbit::new(0),
819            Hexbit::new(25),
820            Hexbit::new(0),
821            Hexbit::new(0),
822            Hexbit::new(0),
823            Hexbit::new(16),
824            Hexbit::new(40),
825            Hexbit::new(0),
826            Hexbit::new(0),
827            Hexbit::new(60),
828            Hexbit::new(51),
829            Hexbit::new(38),
830        ];
831        assert_eq!(long::decode(&mut w), None);
832
833        let mut w = [
834            Hexbit::new(0),
835            Hexbit::new(0),
836            Hexbit::new(0),
837            Hexbit::new(0),
838            Hexbit::new(0),
839            Hexbit::new(0),
840            Hexbit::new(0),
841            Hexbit::new(0),
842            Hexbit::new(0),
843            Hexbit::new(0),
844            Hexbit::new(0),
845            Hexbit::new(0),
846            Hexbit::new(0),
847            Hexbit::new(8),
848            Hexbit::new(0),
849            Hexbit::new(0),
850            Hexbit::new(0),
851            Hexbit::new(0),
852            Hexbit::new(0),
853            Hexbit::new(19),
854            Hexbit::new(39),
855            Hexbit::new(0),
856            Hexbit::new(11),
857            Hexbit::new(12),
858            Hexbit::new(0),
859            Hexbit::new(0),
860            Hexbit::new(33),
861            Hexbit::new(35),
862            Hexbit::new(3),
863            Hexbit::new(36),
864            Hexbit::new(0),
865            Hexbit::new(0),
866            Hexbit::new(37),
867            Hexbit::new(46),
868            Hexbit::new(0),
869            Hexbit::new(20),
870        ];
871        assert_eq!(long::decode(&mut w), None);
872    }
873
874    #[test]
875    fn test_received_decode() {
876        // Just a few examples of received words that should be recoverable.
877
878        let mut w = [
879            Hexbit::new(0),
880            Hexbit::new(0),
881            Hexbit::new(0),
882            Hexbit::new(0),
883            Hexbit::new(0),
884            Hexbit::new(0),
885            Hexbit::new(0),
886            Hexbit::new(0),
887            Hexbit::new(0),
888            Hexbit::new(0),
889            Hexbit::new(0),
890            Hexbit::new(0),
891            Hexbit::new(0),
892            Hexbit::new(8),
893            Hexbit::new(0),
894            Hexbit::new(0),
895            Hexbit::new(0),
896            Hexbit::new(13),
897            Hexbit::new(21),
898            Hexbit::new(46),
899            Hexbit::new(4),
900            Hexbit::new(22),
901            Hexbit::new(12),
902            Hexbit::new(9),
903            Hexbit::new(52),
904            Hexbit::new(25),
905            Hexbit::new(13),
906            Hexbit::new(58),
907            Hexbit::new(28),
908            Hexbit::new(58),
909            Hexbit::new(0),
910            Hexbit::new(51),
911            Hexbit::new(62),
912            Hexbit::new(41),
913            Hexbit::new(34),
914            Hexbit::new(22),
915        ];
916        let exp = [
917            Hexbit::new(0),
918            Hexbit::new(0),
919            Hexbit::new(0),
920            Hexbit::new(0),
921            Hexbit::new(0),
922            Hexbit::new(0),
923            Hexbit::new(0),
924            Hexbit::new(0),
925            Hexbit::new(0),
926            Hexbit::new(0),
927            Hexbit::new(0),
928            Hexbit::new(0),
929            Hexbit::new(0),
930            Hexbit::new(8),
931            Hexbit::new(0),
932            Hexbit::new(0),
933            Hexbit::new(0),
934            Hexbit::new(13),
935            Hexbit::new(21),
936            Hexbit::new(46),
937        ];
938        assert_eq!(long::decode(&mut w), Some((&exp[..], 6)));
939
940        let mut w = [
941            Hexbit::new(0),
942            Hexbit::new(0),
943            Hexbit::new(0),
944            Hexbit::new(0),
945            Hexbit::new(0),
946            Hexbit::new(0),
947            Hexbit::new(0),
948            Hexbit::new(0),
949            Hexbit::new(0),
950            Hexbit::new(0),
951            Hexbit::new(0),
952            Hexbit::new(0),
953            Hexbit::new(0),
954            Hexbit::new(8),
955            Hexbit::new(0),
956            Hexbit::new(0),
957            Hexbit::new(0),
958            Hexbit::new(3),
959            Hexbit::new(18),
960            Hexbit::new(63),
961            Hexbit::new(14),
962            Hexbit::new(62),
963            Hexbit::new(37),
964            Hexbit::new(37),
965            Hexbit::new(41),
966            Hexbit::new(45),
967            Hexbit::new(54),
968            Hexbit::new(14),
969            Hexbit::new(49),
970            Hexbit::new(31),
971            Hexbit::new(15),
972            Hexbit::new(48),
973            Hexbit::new(46),
974            Hexbit::new(0),
975            Hexbit::new(0),
976            Hexbit::new(0),
977        ];
978        let exp = [
979            Hexbit::new(0),
980            Hexbit::new(0),
981            Hexbit::new(0),
982            Hexbit::new(0),
983            Hexbit::new(0),
984            Hexbit::new(0),
985            Hexbit::new(0),
986            Hexbit::new(0),
987            Hexbit::new(0),
988            Hexbit::new(0),
989            Hexbit::new(0),
990            Hexbit::new(0),
991            Hexbit::new(0),
992            Hexbit::new(8),
993            Hexbit::new(0),
994            Hexbit::new(0),
995            Hexbit::new(0),
996            Hexbit::new(3),
997            Hexbit::new(18),
998            Hexbit::new(63),
999        ];
1000        assert_eq!(long::decode(&mut w), Some((&exp[..], 3)));
1001
1002        let mut w = [
1003            Hexbit::new(0),
1004            Hexbit::new(0),
1005            Hexbit::new(0),
1006            Hexbit::new(0),
1007            Hexbit::new(0),
1008            Hexbit::new(0),
1009            Hexbit::new(0),
1010            Hexbit::new(0),
1011            Hexbit::new(0),
1012            Hexbit::new(0),
1013            Hexbit::new(0),
1014            Hexbit::new(0),
1015            Hexbit::new(0),
1016            Hexbit::new(8),
1017            Hexbit::new(0),
1018            Hexbit::new(0),
1019            Hexbit::new(0),
1020            Hexbit::new(3),
1021            Hexbit::new(18),
1022            Hexbit::new(63),
1023            Hexbit::new(14),
1024            Hexbit::new(62),
1025            Hexbit::new(37),
1026            Hexbit::new(37),
1027            Hexbit::new(41),
1028            Hexbit::new(45),
1029            Hexbit::new(54),
1030            Hexbit::new(14),
1031            Hexbit::new(49),
1032            Hexbit::new(31),
1033            Hexbit::new(15),
1034            Hexbit::new(48),
1035            Hexbit::new(46),
1036            Hexbit::new(58),
1037            Hexbit::new(51),
1038            Hexbit::new(54),
1039        ];
1040        let exp = [
1041            Hexbit::new(0),
1042            Hexbit::new(0),
1043            Hexbit::new(0),
1044            Hexbit::new(0),
1045            Hexbit::new(0),
1046            Hexbit::new(0),
1047            Hexbit::new(0),
1048            Hexbit::new(0),
1049            Hexbit::new(0),
1050            Hexbit::new(0),
1051            Hexbit::new(0),
1052            Hexbit::new(0),
1053            Hexbit::new(0),
1054            Hexbit::new(8),
1055            Hexbit::new(0),
1056            Hexbit::new(0),
1057            Hexbit::new(0),
1058            Hexbit::new(3),
1059            Hexbit::new(18),
1060            Hexbit::new(63),
1061        ];
1062        assert_eq!(long::decode(&mut w), Some((&exp[..], 0)));
1063
1064        let mut w = [
1065            Hexbit::new(0),
1066            Hexbit::new(0),
1067            Hexbit::new(0),
1068            Hexbit::new(0),
1069            Hexbit::new(0),
1070            Hexbit::new(0),
1071            Hexbit::new(0),
1072            Hexbit::new(0),
1073            Hexbit::new(0),
1074            Hexbit::new(0),
1075            Hexbit::new(0),
1076            Hexbit::new(0),
1077            Hexbit::new(0),
1078            Hexbit::new(8),
1079            Hexbit::new(0),
1080            Hexbit::new(0),
1081            Hexbit::new(0),
1082            Hexbit::new(3),
1083            Hexbit::new(18),
1084            Hexbit::new(63),
1085            Hexbit::new(14),
1086            Hexbit::new(62),
1087            Hexbit::new(37),
1088            Hexbit::new(37),
1089            Hexbit::new(41),
1090            Hexbit::new(45),
1091            Hexbit::new(54),
1092            Hexbit::new(14),
1093            Hexbit::new(49),
1094            Hexbit::new(31),
1095            Hexbit::new(15),
1096            Hexbit::new(48),
1097            Hexbit::new(47),
1098            Hexbit::new(40),
1099            Hexbit::new(0),
1100            Hexbit::new(12),
1101        ];
1102        let exp = [
1103            Hexbit::new(0),
1104            Hexbit::new(0),
1105            Hexbit::new(0),
1106            Hexbit::new(0),
1107            Hexbit::new(0),
1108            Hexbit::new(0),
1109            Hexbit::new(0),
1110            Hexbit::new(0),
1111            Hexbit::new(0),
1112            Hexbit::new(0),
1113            Hexbit::new(0),
1114            Hexbit::new(0),
1115            Hexbit::new(0),
1116            Hexbit::new(8),
1117            Hexbit::new(0),
1118            Hexbit::new(0),
1119            Hexbit::new(0),
1120            Hexbit::new(3),
1121            Hexbit::new(18),
1122            Hexbit::new(63),
1123        ];
1124        assert_eq!(long::decode(&mut w), Some((&exp[..], 4)));
1125    }
1126
1127    #[test]
1128    fn test_out_of_bounds() {
1129        // Tests received words that cause attempted out-of-bounds corrections
1130
1131        // 4 errors, attempted access at location 34.
1132        let mut w = [
1133            Hexbit::new(0),
1134            Hexbit::new(0),
1135            Hexbit::new(0),
1136            Hexbit::new(0),
1137            Hexbit::new(51),
1138            Hexbit::new(19),
1139            Hexbit::new(8),
1140            Hexbit::new(35),
1141            Hexbit::new(48),
1142            Hexbit::new(61),
1143            Hexbit::new(0),
1144            Hexbit::new(1),
1145            Hexbit::new(11),
1146            Hexbit::new(44),
1147            Hexbit::new(10),
1148            Hexbit::new(0),
1149            Hexbit::new(11),
1150            Hexbit::new(0),
1151            Hexbit::new(15),
1152            Hexbit::new(56),
1153            Hexbit::new(50),
1154            Hexbit::new(0),
1155            Hexbit::new(0),
1156            Hexbit::new(0),
1157        ];
1158
1159        assert_eq!(medium::decode(&mut w), None);
1160
1161        // 6 errors, attempted access at location 61.
1162        let mut w = [
1163            Hexbit::new(0),
1164            Hexbit::new(0),
1165            Hexbit::new(0),
1166            Hexbit::new(4),
1167            Hexbit::new(0),
1168            Hexbit::new(3),
1169            Hexbit::new(34),
1170            Hexbit::new(28),
1171            Hexbit::new(7),
1172            Hexbit::new(13),
1173            Hexbit::new(61),
1174            Hexbit::new(32),
1175            Hexbit::new(27),
1176            Hexbit::new(55),
1177            Hexbit::new(49),
1178            Hexbit::new(7),
1179            Hexbit::new(0),
1180            Hexbit::new(0),
1181            Hexbit::new(0),
1182            Hexbit::new(0),
1183            Hexbit::new(0),
1184            Hexbit::new(0),
1185            Hexbit::new(0),
1186            Hexbit::new(0),
1187        ];
1188
1189        assert_eq!(short::decode(&mut w), None);
1190    }
1191}
code_rs/coding/reed_solomon.rs

code_rs/coding/
reed_solomon.rs
