rs2/
lib.rs

1//! Reed-Solomon Forward Error Correction for spacecraft data conforming to [CCSDS](https://public.ccsds.org)
2//! TM SYNCHRONIZATION AND CHANNEL CODING ([131.0-B-5](https://public.ccsds.org/Pubs/131x0b5.pdf).
3//!
4//! This is only intended to perform RS as documented in the CCSDS document linked above. It is not
5//! a general purpose Reed-Solomon FEC implementation.
6//!
7//! This has been ported and adopted from the Python code found in the excelent article
8//! [Reed-Solomon Codes for Coders](https://en.wikiversity.org/wiki/Reed%E2%80%93Solomon_codes_for_coders).
9pub mod dual_basis;
10pub mod gf;
11
12/// Symbols per code word
13pub const N: u8 = 255;
14/// Bits per symbol
15#[allow(unused)]
16pub const J: u8 = 8;
17/// Common irreducible primative polynomial x^8 + x^7 + x^2 + x + 1
18#[allow(unused)]
19pub const PRIM: i32 = 391;
20/// Primative element: alpha 11
21pub const GEN: u8 = 173;
22/// First consecutive root in g(x): 128-E
23pub const FCR: i32 = 112;
24/// Number of bytes of parity for each message.
25pub const PARITY_LEN: usize = 32;
26
27/// Disposition of the RS process
28#[derive(Debug, PartialEq, Clone)]
29pub enum RSState {
30    /// RS was performed and no errors were found
31    Ok,
32    /// RS was performed and the provided number of errors were successfully correct.
33    Corrected(i32),
34    /// RS was performed but the RS codeblock was not correctable, e.g., there were
35    /// more errors than could be corrected.
36    Uncorrectable(String),
37    NotPerformed,
38}
39
40fn correct_errata(input: &[u8], synd: &[u8], errpos: &[i32]) -> Result<Vec<u8>, &'static str> {
41    let mut coef_pos = vec![0i32; errpos.len()];
42    for (i, p) in errpos.iter().enumerate() {
43        coef_pos[i] = input.len() as i32 - 1 - p;
44    }
45
46    let errloc = find_errata_locator(&coef_pos[..]);
47    let mut rev_synd = synd.to_owned();
48    rev_synd.reverse();
49    let mut erreval = find_error_evaluator(&rev_synd, &errloc, errloc.len() as i32 - 1);
50    erreval.reverse();
51
52    let mut x = vec![0u8; coef_pos.len()];
53    for (i, p) in coef_pos.iter().enumerate() {
54        x[i] = gf::pow(GEN as u8, -(N as i32 - p));
55    }
56
57    let mut e = vec![0u8; input.len()];
58    for (i, xi) in x.iter().enumerate() {
59        let xi_inv = gf::inv(*xi);
60        let mut errloc_prime_tmp: Vec<u8> = Vec::new();
61        for j in 0..x.len() {
62            if j != i {
63                errloc_prime_tmp.push(1 ^ gf::mult(xi_inv, x[j]));
64            }
65        }
66        let mut errloc_prime = 1u8;
67        for c in errloc_prime_tmp.iter() {
68            errloc_prime = gf::mult(errloc_prime, *c);
69        }
70
71        let mut erreval_rev = erreval.to_owned();
72        erreval_rev.reverse();
73        let mut y = gf::poly_eval(&erreval_rev, xi_inv);
74        y = gf::mult(gf::pow(*xi, 1 - FCR), y);
75
76        if errloc_prime == 0 {
77            return Err("failed to find error magnitude");
78        }
79
80        e[errpos[i] as usize] = gf::div(y, errloc_prime);
81    }
82
83    let zult = &gf::poly_add(&input, &e);
84    Ok(zult.to_vec())
85}
86
87fn find_errata_locator(errpos: &[i32]) -> Vec<u8> {
88    let mut errloc = vec![1u8];
89    for p in errpos.iter() {
90        let x = &[gf::pow(GEN as u8, *p), 0];
91        let y = gf::poly_add(&[1u8], x);
92        errloc = gf::poly_mult(&errloc, &y);
93    }
94    errloc
95}
96
97fn find_error_evaluator(synd: &[u8], errloc: &[u8], n: i32) -> Vec<u8> {
98    let mut divisor: Vec<u8> = vec![0u8; n as usize + 2];
99    divisor[0] = 1;
100    let (_, rem) = gf::poly_div(&gf::poly_mult(&synd, &errloc), &divisor);
101    rem
102}
103
104fn find_errors(errloc: &[u8]) -> Vec<i32> {
105    let num_errs = errloc.len() - 1;
106    let mut errpos: Vec<i32> = Vec::with_capacity(num_errs);
107    let n = N as i32;
108    for i in 0..n {
109        if gf::poly_eval(errloc, gf::pow(GEN, i as i32)) == 0 {
110            errpos.push(N as i32 - 1 - i);
111        }
112    }
113    errpos
114}
115
116fn find_error_locator(synd: &[u8], parity_len: usize) -> Vec<u8> {
117    let mut errloc = vec![1u8];
118    let mut oldloc = vec![1u8];
119    let mut synd_shift = 0;
120    if synd.len() > parity_len {
121        synd_shift = synd.len() - parity_len;
122    }
123    for i in 0..parity_len {
124        let k = i as usize + synd_shift;
125        let mut delta = synd[k];
126        for j in 1..errloc.len() {
127            delta ^= gf::mult(errloc[errloc.len() - j - 1], synd[k - j]);
128        }
129        oldloc.push(0);
130        if delta != 0 {
131            if oldloc.len() > errloc.len() {
132                let newloc = gf::poly_scale(&oldloc, delta);
133                oldloc = gf::poly_scale(&errloc, gf::inv(delta));
134                errloc = newloc;
135            }
136            errloc = gf::poly_add(&errloc, &gf::poly_scale(&oldloc, delta));
137        }
138    }
139
140    while errloc.len() > 0 && errloc[0] == 0 {
141        errloc = errloc[1..].to_vec();
142    }
143
144    errloc
145}
146
147fn forney_syndromes(synd: &[u8], pos: &[i32], nmess: i32) -> Vec<u8> {
148    let mut erase_pos_rev = vec![0i32; pos.len()];
149    for (i, p) in pos.iter().enumerate() {
150        erase_pos_rev[i] = nmess - 1 - p;
151    }
152    let mut fsynd: Vec<u8> = Vec::with_capacity(synd.len() - 1);
153    fsynd.extend_from_slice(&synd[1..]);
154    for i in 0..pos.len() {
155        let x = gf::pow(GEN as u8, erase_pos_rev[i]);
156        for j in 0..fsynd.len() - 1 {
157            fsynd[j] = gf::mult(fsynd[j], x) ^ fsynd[j + 1];
158        }
159    }
160    fsynd
161}
162
163fn calc_syndromes(input: &[u8], parity_len: usize) -> Vec<u8> {
164    let mut synd: Vec<u8> = vec![0u8; parity_len + 1];
165    for i in 0..parity_len {
166        let p = gf::pow(GEN, i as i32 + FCR);
167        synd[i + 1] = gf::poly_eval(&input, p);
168    }
169    synd
170}
171
172pub struct Block {
173    /// Resuting state of the RS process for all contained RS messages.
174    pub state: RSState,
175    /// The checked codeblock without the RS check symbols.
176    pub message: Option<Vec<u8>>,
177}
178
179/// Correct a Reed-Solomon 255 byte code block, where the last [PARITY_LEN] bytes are
180/// the parity/check bytes. The code block is also assumed to be in dual basis
181/// representation.
182///
183/// The returned [Block::message} will contain the corrected message iff the state is
184/// [RSState::Corrected]. Otherwise it will be None.
185///
186/// The state will be [RSState::Uncorrectable] if there are more errors than can be
187/// corrected or if an algorithm failure occurs.
188pub fn correct_message(input: &[u8]) -> Block {
189    let input = input.to_vec();
190    if input.len() != N as usize {
191        return Block {
192            state: RSState::Uncorrectable("invalid input".to_owned()),
193            message: None,
194        };
195    }
196    let out = dual_basis::to_conv(&input).clone();
197
198    let synd = calc_syndromes(&out, PARITY_LEN);
199    let max = synd.iter().max().unwrap();
200    // if there are no non-zero elements there are no errors
201    if *max == 0 {
202        return Block {
203            state: RSState::Ok,
204            message: Some(input),
205        };
206    }
207
208    let fsynd = forney_syndromes(&synd, &[], out.len() as i32);
209    let errloc = find_error_locator(&fsynd[..], PARITY_LEN);
210
211    let num_errs = errloc.len() - 1;
212    if num_errs * 2 > PARITY_LEN {
213        return Block {
214            state: RSState::Uncorrectable(format!(
215                "too many errors to correct; expected no more than {:?}, found {:?}",
216                PARITY_LEN / 2,
217                num_errs
218            ))
219            .to_owned(),
220            message: None,
221        };
222    }
223
224    let mut errloc_rev = errloc.clone();
225    errloc_rev.reverse();
226    let errpos = find_errors(&errloc_rev[..]);
227    if errpos.len() != num_errs {
228        return Block {
229            state: RSState::Uncorrectable(
230                format!(
231                    "failed to generate error positions; expected {} postions, got {}",
232                    num_errs,
233                    errpos.len()
234                )
235                .to_owned(),
236            ),
237            message: None,
238        };
239    }
240
241    let out = match correct_errata(&out, &synd, &errpos) {
242        Err(err) => {
243            return Block {
244                state: RSState::Uncorrectable(err.to_owned()),
245                message: None,
246            }
247        }
248        Ok(block) => block,
249    };
250
251    let synd = calc_syndromes(&out, PARITY_LEN);
252    if *synd.iter().max().unwrap() > 0 {
253        return Block {
254            state: RSState::Uncorrectable("failed to correct all errors".to_owned()),
255            message: None,
256        };
257    }
258
259    Block {
260        state: RSState::Corrected(errloc.len() as i32 - 1),
261        message: Some(dual_basis::to_dual(&out)),
262    }
263}
264
265/// Return true if the input code block contains 1 or more errors.
266pub fn has_errors(msg: &[u8]) -> bool {
267    let msg = dual_basis::to_conv(msg);
268    let mut x = 0;
269    for i in calc_syndromes(&msg[..], PARITY_LEN) {
270        if i > x {
271            x = i;
272        }
273    }
274    x != 0
275}
276
277#[cfg(test)]
278mod tests {
279    use super::*;
280
281    // RS message, no pn
282    const FIXTURE_MSG: &[u8; 255] = &[
283        0x67, 0xc4, 0x6b, 0xa7, 0x3e, 0xbe, 0x4c, 0x33, 0x6c, 0xb2, 0x23, 0x3a, 0x74, 0x06, 0x2b,
284        0x18, 0xab, 0xb8, 0x09, 0xe6, 0x7d, 0xaf, 0x5d, 0xe5, 0xdf, 0x76, 0x25, 0x3f, 0xb9, 0x14,
285        0xee, 0xec, 0xd1, 0xa3, 0x39, 0x5f, 0x38, 0x68, 0xf0, 0x26, 0xa6, 0x8a, 0xcb, 0x09, 0xaf,
286        0x4e, 0xf8, 0x93, 0xf7, 0x45, 0x4b, 0x0d, 0xa9, 0xb8, 0x74, 0x0e, 0xf3, 0xc7, 0xed, 0x6e,
287        0xa3, 0x0f, 0xf6, 0x79, 0x94, 0x16, 0xe2, 0x7f, 0xad, 0x91, 0x91, 0x04, 0xac, 0xa4, 0xae,
288        0xb4, 0x51, 0x76, 0x2f, 0x62, 0x03, 0x5e, 0xa1, 0xe5, 0x5c, 0x45, 0xf8, 0x1f, 0x7a, 0x7b,
289        0xe8, 0x35, 0xd8, 0xcc, 0x51, 0x0e, 0xae, 0x3a, 0x2a, 0x64, 0x1d, 0x03, 0x10, 0xcd, 0x18,
290        0xe6, 0x7f, 0xef, 0xba, 0xd9, 0xe8, 0x98, 0x47, 0x82, 0x9c, 0xa1, 0x58, 0x47, 0x25, 0xdf,
291        0x41, 0xd2, 0x01, 0x62, 0x3c, 0x24, 0x88, 0x90, 0xe9, 0xd7, 0x38, 0x1b, 0xa0, 0xa2, 0xb4,
292        0x23, 0xea, 0x7e, 0x58, 0x0d, 0xf4, 0x61, 0x24, 0x14, 0xb0, 0x41, 0x90, 0x0c, 0xb7, 0xbb,
293        0x5c, 0x59, 0x1b, 0xc6, 0x69, 0x24, 0x0f, 0xb6, 0x0e, 0x14, 0xa1, 0xb1, 0x8e, 0x48, 0x0f,
294        0x17, 0x1d, 0xfb, 0x0f, 0x38, 0x42, 0xe3, 0x24, 0x58, 0xab, 0x82, 0xa8, 0xfd, 0xdf, 0xac,
295        0x68, 0x93, 0x3d, 0x0d, 0x8f, 0x50, 0x52, 0x44, 0x6c, 0xba, 0xd3, 0x51, 0x99, 0x9c, 0x3e,
296        0xad, 0xd5, 0xa8, 0xd7, 0x9d, 0xc7, 0x7f, 0x9f, 0xc9, 0x2a, 0xac, 0xe5, 0xc2, 0xcd, 0x9a,
297        0x9b, 0xfa, 0x2d, 0x72, 0xab, 0x6b, 0xa4, 0x6b, 0x8b, 0x7d, 0xfa, 0x6c, 0x83, 0x63, 0x77,
298        0x9f, 0x4e, 0x9a, 0x20, 0x35, 0xd2, 0x91, 0xce, 0xf4, 0x21, 0x1a, 0x97, 0x3c, 0x1a, 0x15,
299        0x9d, 0xfc, 0x98, 0xba, 0x72, 0x1b, 0x9a, 0xa2, 0xe9, 0xc9, 0x46, 0x68, 0xce, 0xad, 0x27,
300    ];
301
302    #[test]
303    fn test_calc_syndromes() {
304        const EXPECTED: &[u8] = &[
305            0x00, 0xb7, 0xd5, 0x62, 0x7b, 0xf5, 0xa0, 0x52, 0x91, 0xc1, 0xd2, 0x97, 0xd0, 0x40,
306            0x68, 0x59, 0x0d, 0xcb, 0xc0, 0x84, 0x84, 0x68, 0xa6, 0xd9, 0x79, 0xf9, 0xad, 0x4c,
307            0x81, 0x9f, 0x14, 0x2f, 0x78,
308        ];
309
310        let zult = calc_syndromes(FIXTURE_MSG, PARITY_LEN);
311
312        for ((i, z), e) in zult.iter().enumerate().zip(EXPECTED.iter()) {
313            assert_eq!(
314                z, e,
315                "not all elements equal: expected {}, got {} at index {}\n{:?}",
316                e, z, i, zult
317            );
318        }
319    }
320
321    #[test]
322    fn test_correct_message_noerrors() {
323        let msg = FIXTURE_MSG.clone();
324
325        assert!(!has_errors(&msg), "expected message not to have errors");
326
327        let block = correct_message(&msg);
328
329        assert_eq!(block.message.unwrap().len(), 255);
330        assert_eq!(
331            block.state,
332            RSState::Ok,
333            "correcting a message with no errors should be Ok"
334        );
335    }
336
337    #[test]
338    fn test_correct_message_introduced_errors() {
339        let mut msg = FIXTURE_MSG.clone();
340
341        // corrupt the message
342        msg[0] = 0;
343        msg[2] = 2;
344        msg[4] = 2;
345        msg[6] = 2;
346
347        assert!(has_errors(&msg), "expected message to have errors");
348
349        let block = correct_message(&msg);
350        assert_eq!(block.message.unwrap().len(), 255);
351        assert_eq!(block.state, RSState::Corrected(4));
352    }
353
354    #[test]
355    fn test_correct_message2() {
356        // block 80 message 0 from overpass_snpp_2017_7min.dat
357        // This block contains errors and is already pn decoded
358        let msg = vec![
359            0x67, 0x4c, 0x00, 0xff, 0xff, 0x80, 0x02, 0xf8, 0x7f, 0x01, 0xf7, 0x4f, 0xb5, 0x65,
360            0x14, 0x29, 0xfd, 0x68, 0x38, 0x9e, 0x6a, 0xca, 0x28, 0x53, 0xfa, 0xd0, 0x71, 0x3d,
361            0xd4, 0x95, 0x50, 0xa6, 0xf4, 0xa0, 0xe2, 0x7b, 0xa9, 0x2a, 0xa1, 0x4c, 0xe9, 0x41,
362            0xc5, 0xf6, 0x52, 0x54, 0x42, 0x99, 0xd2, 0x83, 0x8b, 0xed, 0xa5, 0xa8, 0x84, 0x33,
363            0xa4, 0x06, 0x16, 0xdb, 0x4b, 0x51, 0x08, 0x66, 0x48, 0x0d, 0x2c, 0xb7, 0x97, 0xa2,
364            0x10, 0xcd, 0x90, 0x1a, 0x59, 0x6e, 0x2e, 0x45, 0x21, 0x9b, 0x20, 0x35, 0xb2, 0xdd,
365            0x5d, 0x8a, 0x43, 0x37, 0x40, 0x6b, 0x64, 0xba, 0xbb, 0x15, 0x87, 0x6f, 0x80, 0xd7,
366            0xc9, 0x74, 0x77, 0x2b, 0x0f, 0xde, 0x01, 0xae, 0x92, 0xe8, 0xef, 0x57, 0x1e, 0xbd,
367            0x03, 0x5c, 0x24, 0xd1, 0xdf, 0xaf, 0x3c, 0x7a, 0x07, 0xb8, 0x49, 0xa3, 0xbe, 0x5f,
368            0x78, 0xf5, 0x0e, 0x70, 0x93, 0x46, 0x7d, 0xbf, 0xf1, 0xea, 0x1d, 0xe1, 0x27, 0x8d,
369            0xfb, 0x7e, 0xe3, 0xd5, 0x3b, 0xc2, 0x4e, 0x1b, 0xf7, 0xfc, 0xc6, 0xaa, 0x76, 0x85,
370            0x9d, 0x36, 0xee, 0xf9, 0x8c, 0x55, 0xec, 0x0b, 0x3a, 0x6c, 0xdc, 0xf3, 0x18, 0xab,
371            0xd8, 0x17, 0x75, 0xd9, 0xb9, 0xe7, 0x31, 0x56, 0xb0, 0x2f, 0xeb, 0xb3, 0x73, 0xcf,
372            0x62, 0xac, 0x60, 0x5e, 0xd6, 0x67, 0xe6, 0x9f, 0xc4, 0x58, 0xc0, 0xbc, 0xad, 0xce,
373            0xcc, 0x3e, 0x88, 0xb1, 0x81, 0x79, 0x5b, 0x9c, 0x98, 0x7c, 0x11, 0x63, 0x02, 0xf2,
374            0xb6, 0x39, 0x30, 0xf8, 0x22, 0xc7, 0x04, 0xe4, 0x6d, 0x72, 0x61, 0xf0, 0x44, 0x8f,
375            0x09, 0xc8, 0xda, 0xe5, 0xc3, 0xe0, 0x89, 0x1f, 0x13, 0x91, 0xb4, 0xcb, 0x86, 0xc1,
376            0x12, 0x3f, 0x26, 0x23, 0x69, 0x96, 0x0c, 0x82, 0x25, 0x7f, 0x4d, 0x47, 0xd3, 0x2d,
377            0x19, 0x05, 0x4a,
378        ];
379
380        assert!(has_errors(&msg), "expected message to have errors");
381
382        let block = correct_message(&msg);
383        assert_eq!(block.message.unwrap().len(), 255);
384        assert_eq!(block.state, RSState::Corrected(11));
385    }
386}
rs2/lib.rs

rs2/
lib.rs
