ps_ecc/
reed_solomon.rs

1use ps_buffer::{Buffer, BufferError, ByteIteratorIntoBuffer, ToBuffer};
2
3use crate::cow::Cow;
4use crate::error::{
5    PolynomialError, RSConstructorError, RSDecodeError, RSEncodeError, RSGenerateParityError,
6};
7use crate::finite_field::{div, inv, mul, ANTILOG_TABLE};
8use crate::polynomial::{
9    poly_div, poly_eval, poly_eval_deriv, poly_eval_detached, poly_mul, poly_rem, poly_sub,
10};
11use crate::{Codeword, RSComputeErrorsError, RSEuclideanError, RSValidationError};
12
13pub struct ReedSolomon {
14    parity: u8,
15}
16
17impl ReedSolomon {
18    /// Creates a new Reed-Solomon codec with parameters n and k.
19    /// # Errors
20    /// - `ParityTooHigh` is returned if parity > 127
21    pub const fn new(parity: u8) -> Result<Self, RSConstructorError> {
22        use RSConstructorError::ParityTooHigh;
23
24        if parity > 127 {
25            return Err(ParityTooHigh);
26        }
27
28        let codec = Self { parity };
29
30        Ok(codec)
31    }
32
33    #[inline]
34    #[must_use]
35    pub const fn parity(&self) -> u8 {
36        self.parity
37    }
38
39    #[inline]
40    #[must_use]
41    pub const fn parity_bytes(&self) -> u8 {
42        self.parity() << 1
43    }
44
45    /// Generates parity bytes.
46    /// # Errors
47    /// - `BufferError` if an allocation fails
48    /// - `PolynomialError` if generator polynomial is zero (shouldn't happen)
49    pub fn generate_parity(&self, message: &[u8]) -> Result<Buffer, RSGenerateParityError> {
50        let num_parity = usize::from(self.parity_bytes());
51        let g = generate_generator_poly(num_parity)?;
52        let dividend = vec![0u8; num_parity]
53            .into_iter()
54            .chain(message.iter().copied())
55            .into_buffer()?;
56        let mut r = poly_rem(dividend, &g)?;
57        if r.len() != num_parity {
58            r.resize(num_parity, 0)?;
59        }
60        Ok(r)
61    }
62
63    /// Encodes a message into a codeword.
64    /// # Errors
65    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
66    /// - `PolynomialError` if generator polynomial is zero (shouldn't happen)
67    pub fn encode(&self, message: &[u8]) -> Result<Buffer, RSEncodeError> {
68        let mut buffer = Buffer::with_capacity(message.len() + usize::from(self.parity_bytes()))?;
69
70        buffer.extend_from_slice(&self.generate_parity(message)?)?;
71        buffer.extend_from_slice(message)?;
72
73        Ok(buffer)
74    }
75
76    /// Computes the syndromes of a given codeword.
77    /// # Errors
78    /// - [`BufferError`] if allocation fails
79    pub fn compute_syndromes(
80        num_parity_bytes: impl Into<usize>,
81        received: &[u8],
82    ) -> Result<Buffer, BufferError> {
83        (0..num_parity_bytes.into())
84            .map(|i| poly_eval(received, ANTILOG_TABLE[i + 1].get()))
85            .into_buffer()
86    }
87
88    /// Computes the syndromes of a given detached codeword.
89    /// # Errors
90    /// - [`BufferError`] if allocation fails
91    pub fn compute_syndromes_detached(parity: &[u8], data: &[u8]) -> Result<Buffer, BufferError> {
92        (0..parity.len())
93            .map(|i| poly_eval_detached(parity, data, ANTILOG_TABLE[i + 1].get()))
94            .into_buffer()
95    }
96
97    /// Validates a received codeword.
98    /// # Errors
99    /// `Err(syndromes)` is returned if the codeword is invalid.
100    pub fn validate(&self, received: &[u8]) -> Result<Option<Buffer>, RSValidationError> {
101        let syndromes = Self::compute_syndromes(self.parity_bytes(), received)?;
102
103        if syndromes.iter().all(|&s| s == 0) {
104            Ok(None)
105        } else {
106            Ok(Some(syndromes))
107        }
108    }
109
110    /// Validates a regregated (parity, message) pair.
111    /// # Errors
112    /// `Err(syndromes)` is returned if the codeword is invalid.
113    #[allow(clippy::cast_possible_truncation)]
114    pub fn validate_detached(
115        parity: &[u8],
116        data: &[u8],
117    ) -> Result<Option<Buffer>, RSValidationError> {
118        let syndromes = Self::compute_syndromes_detached(parity, data)?;
119
120        if syndromes.iter().all(|&s| s == 0) {
121            Ok(None)
122        } else {
123            Ok(Some(syndromes))
124        }
125    }
126
127    #[inline]
128    /// # Errors
129    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
130    /// - [`RSDecodeError::TooManyErrors`] is returned if the input is unrecoverable.
131    pub fn compute_errors(
132        &self,
133        length: usize,
134        syndromes: &[u8],
135    ) -> Result<Option<Buffer>, RSComputeErrorsError> {
136        Self::compute_errors_detached(self.parity(), length, syndromes)
137    }
138
139    /// Computes errors in a received codeword.
140    /// # Parameters
141    /// - `length`: full length of codeword, including parity bytes
142    /// - `syndromes`: see [`ReedSolomon::validate`]
143    /// # Errors
144    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
145    /// - `GFError` if an arithmetic operation fails
146    /// - `PolynomialError` if `euclidean_for_rs` fails (division by zero)
147    /// - `TooManyErrors` if the input is unrecoverable
148    /// - `ZeroDerivative` shouldn't happen
149    fn compute_errors_detached(
150        parity: impl Into<usize>,
151        length: usize,
152        syndromes: &[u8],
153    ) -> Result<Option<Buffer>, RSComputeErrorsError> {
154        if syndromes.iter().all(|&syndrome| syndrome == 0) {
155            return Ok(None);
156        }
157
158        let parity = parity.into();
159
160        // Euclidean algorithm to find error locator and evaluator polynomials
161        let (mut sigma, mut omega) = euclidean_for_rs(syndromes, parity)?;
162
163        // Normalize sigma, omega
164        let scale = inv(sigma[0])?.get();
165        sigma.iter_mut().for_each(|x| *x = mul(*x, scale));
166        omega.iter_mut().for_each(|x| *x = mul(*x, scale));
167
168        // Find error positions
169        let error_positions: Vec<usize> = (0..length)
170            .filter(|&m| {
171                let x = ANTILOG_TABLE[(255 - m) % 255].get();
172                poly_eval(&sigma, x) == 0
173            })
174            .collect();
175
176        if error_positions.len() > parity || error_positions.is_empty() {
177            return Err(RSComputeErrorsError::TooManyErrors);
178        }
179
180        // Compute error values using Forney's formula
181        let mut errors = Buffer::alloc(length)?;
182        for &j in &error_positions {
183            let x = ANTILOG_TABLE[(255 - j) % 255].get();
184            let omega_x = poly_eval(&omega, x);
185            let sigma_deriv_x = poly_eval_deriv(&sigma, x);
186            if sigma_deriv_x == 0 {
187                return Err(RSComputeErrorsError::ZeroErrorLocatorDerivative);
188            }
189            errors[j] = div(omega_x, sigma_deriv_x)?;
190        }
191
192        Ok(Some(errors))
193    }
194
195    /// Corrects a received codeword, returning the corrected codeword.
196    /// # Errors
197    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
198    /// - [`RSDecodeError`] is propagated from [`ReedSolomon::compute_errors`].
199    pub fn correct<'lt>(&self, received: &'lt [u8]) -> Result<Cow<'lt>, RSDecodeError> {
200        let syndromes = Self::compute_syndromes(self.parity_bytes(), received)?;
201
202        let errors = match self.compute_errors(received.len(), &syndromes)? {
203            None => return Ok(Cow::Borrowed(received)),
204            Some(errors) => errors,
205        };
206
207        // Correct the received codeword
208        let mut corrected = Buffer::from_slice(received)?;
209
210        Self::apply_corrections(&mut corrected, &errors);
211
212        match Self::validate(self, &corrected)? {
213            None => Ok(corrected.into()),
214            Some(_) => Err(RSDecodeError::TooManyErrors),
215        }
216    }
217    /// Corrects a received codeword in-place.
218    /// # Errors
219    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
220    /// - [`RSDecodeError`] is propagated from [`ReedSolomon::compute_errors`].
221    /// - [`RSDecodeError::TooManyErrors`] is returned if the data is unrecoverable.
222    pub fn correct_in_place(&self, received: &mut [u8]) -> Result<(), RSDecodeError> {
223        let syndromes = Self::compute_syndromes(self.parity_bytes(), received)?;
224
225        let errors = match self.compute_errors(received.len(), &syndromes)? {
226            None => return Ok(()),
227            Some(errors) => errors,
228        };
229
230        Self::apply_corrections(received, errors);
231
232        match Self::validate(self, received)? {
233            None => Ok(()),
234            Some(_) => Err(RSDecodeError::TooManyErrors),
235        }
236    }
237
238    /// Decodes a received codeword, correcting errors if possible.
239    /// # Errors
240    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
241    /// - [`RSDecodeError`] is propagated from [`ReedSolomon::compute_errors`].
242    pub fn decode<'lt>(&self, received: &'lt [u8]) -> Result<Codeword<'lt>, RSDecodeError> {
243        let corrected = self.correct(received)?;
244        let codeword = Codeword {
245            codeword: corrected,
246            range: self.parity_bytes().into()..received.len(),
247        };
248
249        Ok(codeword)
250    }
251
252    /// Corrects a message based on detached parity bytes.
253    /// # Errors
254    /// - [`ps_buffer::BufferError`] is returned if memory allocation fails.
255    /// - [`RSDecodeError`] is propagated from [`ReedSolomon::compute_errors`].
256    pub fn correct_detached<'lt>(
257        parity: &[u8],
258        data: &'lt [u8],
259    ) -> Result<Codeword<'lt>, RSDecodeError> {
260        let parity_bytes = parity.len();
261        let num_parity = parity_bytes >> 1;
262        let length = parity_bytes + data.len();
263        let rs = Self::new(num_parity.try_into()?)?;
264
265        let syndromes = Self::compute_syndromes_detached(parity, data)?;
266
267        let errors = match Self::compute_errors_detached(num_parity, length, &syndromes)? {
268            None => return Ok(data.into()),
269            Some(errors) => errors,
270        };
271
272        // Correct the received codeword
273        let mut corrected = Buffer::with_capacity(parity.len() + data.len())?;
274
275        corrected.extend_from_slice(parity)?;
276        corrected.extend_from_slice(data)?;
277
278        Self::apply_corrections(&mut corrected, &errors);
279
280        if let Some(_syndromes) = rs.validate(&corrected)? {
281            return Err(RSDecodeError::TooManyErrors);
282        };
283
284        let range = parity.len()..corrected.len();
285        let codeword = Cow::Owned(corrected);
286        let codeword = Codeword { codeword, range };
287
288        Ok(codeword)
289    }
290
291    /// Corrects a message based on detached parity bytes.
292    /// # Errors
293    /// - [`RSDecodeError`] is returned if `data` is not recoverable.
294    #[inline]
295    pub fn correct_detached_data_in_place(
296        parity: &[u8],
297        data: &mut [u8],
298    ) -> Result<(), RSDecodeError> {
299        Self::correct_detached_in_place(&mut parity.to_buffer()?, data)
300    }
301
302    /// Corrects a message based on detached parity bytes.
303    /// Also corrects the parity bytes.
304    /// # Errors
305    /// - [`RSDecodeError`] is propagated from [`ReedSolomon::compute_errors`].
306    pub fn correct_detached_in_place(
307        parity: &mut [u8],
308        data: &mut [u8],
309    ) -> Result<(), RSDecodeError> {
310        let parity_bytes = parity.len();
311        let num_parity = parity_bytes >> 1;
312        let length = parity_bytes + data.len();
313
314        let syndromes = Self::compute_syndromes_detached(parity, data)?;
315
316        let errors = match Self::compute_errors_detached(num_parity, length, &syndromes)? {
317            None => return Ok(()),
318            Some(errors) => errors,
319        };
320
321        Self::apply_corrections_detached(parity, data, &errors);
322
323        match Self::validate_detached(parity, data)? {
324            None => Ok(()),
325            Some(_) => Err(RSDecodeError::TooManyErrors),
326        }
327    }
328
329    pub fn apply_corrections(target: &mut [u8], corrections: impl AsRef<[u8]>) {
330        target
331            .iter_mut()
332            .zip(corrections.as_ref().iter())
333            .for_each(|(target, correction)| *target ^= *correction);
334    }
335
336    pub fn apply_corrections_detached(
337        parity: &mut [u8],
338        data: &mut [u8],
339        corrections: impl AsRef<[u8]>,
340    ) {
341        let corrections = corrections.as_ref();
342        Self::apply_corrections(parity, &corrections[..parity.len()]);
343        Self::apply_corrections(data, &corrections[parity.len()..]);
344    }
345}
346
347/// Generates the generator polynomial `g(x)` = `(x - α^1)(x - α^2)`...`(x - α^num_roots`).
348#[allow(clippy::needless_range_loop)]
349fn generate_generator_poly(num_roots: usize) -> Result<Buffer, PolynomialError> {
350    let mut g = Buffer::from_slice([1])?;
351    for i in 1..=num_roots {
352        let root = ANTILOG_TABLE[i].get();
353        g = poly_mul(&g, &[root, 1])?; // x + α^i
354    }
355    Ok(g)
356}
357
358/// Extended Euclidean algorithm for Reed-Solomon decoding.
359fn euclidean_for_rs(s: &[u8], t: usize) -> Result<(Buffer, Buffer), RSEuclideanError> {
360    let mut r0 = Buffer::alloc(2 * t + 1)?;
361    r0[2 * t] = 1; // x^{2t}
362    let mut r1 = s.to_buffer()?;
363    let mut t0 = Buffer::from_slice([0])?;
364    let mut t1 = Buffer::from_slice([1])?;
365    while degree(&r1).unwrap_or(0) >= t {
366        let (q, r) = poly_div(&r0, &r1)?;
367        let new_t1 = poly_sub(&t0, &poly_mul(&q, &t1)?)?;
368        t0 = t1;
369        t1 = new_t1;
370        r0 = r1;
371        r1 = r;
372    }
373    Ok((t1, r1))
374}
375
376fn degree(poly: &[u8]) -> Option<usize> {
377    poly.iter().rposition(|&x| x != 0)
378}
379
380#[cfg(test)]
381mod tests {
382    use super::*;
383    use ps_buffer::ToBuffer;
384    use thiserror::Error;
385
386    #[derive(Error, Debug)]
387    enum TestError {
388        #[error(transparent)]
389        Buffer(#[from] ps_buffer::BufferError),
390        #[error(transparent)]
391        Polynomial(#[from] PolynomialError),
392        #[error(transparent)]
393        RSConstructor(#[from] RSConstructorError),
394        #[error(transparent)]
395        RSEncode(#[from] RSEncodeError),
396        #[error(transparent)]
397        RSDecode(#[from] RSDecodeError),
398        #[error(transparent)]
399        RSGenerateParity(#[from] RSGenerateParityError),
400        #[error(transparent)]
401        RSValidation(#[from] RSValidationError),
402    }
403
404    #[test]
405    fn test_encode_decode() -> Result<(), TestError> {
406        let rs = ReedSolomon::new(4)?;
407        let message = b"Hello, World!".to_buffer()?;
408        let encoded = rs.encode(&message)?;
409
410        let mut corrupted = Buffer::with_capacity(encoded.len())?;
411        corrupted.extend_from_slice(&encoded)?;
412        corrupted[2] ^= 1;
413
414        let decoded = rs.decode(&corrupted)?;
415        assert_eq!(&decoded[..], &message[..]);
416
417        Ok(())
418    }
419
420    #[test]
421    fn test_too_many_errors() -> Result<(), TestError> {
422        let rs = ReedSolomon::new(2)?;
423        let message = b"Hello, World!".to_buffer()?;
424        let encoded = rs.encode(&message)?;
425
426        let mut corrupted = Buffer::with_capacity(encoded.len())?;
427        corrupted.extend_from_slice(&encoded)?;
428        corrupted[5] ^= 113;
429        corrupted[6] ^= 59;
430        corrupted[7] ^= 3;
431
432        assert_eq!(
433            rs.decode(&corrupted),
434            Err(RSDecodeError::RSComputeErrorsError(
435                RSComputeErrorsError::TooManyErrors
436            ))
437        );
438
439        Ok(())
440    }
441
442    #[test]
443    fn test_validate() -> Result<(), TestError> {
444        let rs = ReedSolomon::new(4)?;
445        let message = b"Hello, World!".to_buffer()?;
446        let encoded = rs.encode(&message)?;
447
448        assert!(rs.validate(&encoded)?.is_none());
449
450        let mut corrupted = Buffer::with_capacity(encoded.len())?;
451        corrupted.extend_from_slice(&encoded)?;
452        corrupted[2] ^= 1;
453
454        assert!(rs.validate(&corrupted)?.is_some());
455
456        Ok(())
457    }
458
459    #[test]
460    fn test_validate_detached() -> Result<(), TestError> {
461        let rs = ReedSolomon::new(4)?;
462        let message = b"Hello, World!".to_buffer()?;
463        let parity = rs.generate_parity(&message)?;
464
465        assert!(ReedSolomon::validate_detached(&parity, &message)?.is_none());
466
467        let mut corrupted = Buffer::with_capacity(message.len())?;
468        corrupted.extend_from_slice(&message)?;
469        corrupted[2] ^= 1;
470
471        assert!(ReedSolomon::validate_detached(&parity, &corrupted)?.is_some());
472
473        Ok(())
474    }
475
476    #[test]
477    fn test_correct_both_detached_in_place() -> Result<(), TestError> {
478        let rs = ReedSolomon::new(4)?;
479        let message = b"Hello, World!".to_buffer()?;
480        let mut data = Buffer::with_capacity(message.len())?;
481        data.extend_from_slice(&message)?;
482        let mut parity = rs.generate_parity(&message)?;
483
484        data[2] ^= 1;
485
486        ReedSolomon::correct_detached_in_place(&mut parity, &mut data)?;
487
488        assert_eq!(data.as_slice(), message.as_slice());
489        assert_eq!(parity, rs.generate_parity(&message)?);
490
491        Ok(())
492    }
493
494    #[test]
495    fn test_new() {
496        assert!(ReedSolomon::new(0).is_ok());
497        assert!(ReedSolomon::new(10).is_ok());
498        assert!(ReedSolomon::new(127).is_ok());
499        assert!(ReedSolomon::new(128).is_err());
500    }
501
502    #[test]
503    fn test_parity() -> Result<(), RSConstructorError> {
504        let rs = ReedSolomon::new(8)?;
505        assert_eq!(rs.parity(), 8);
506        Ok(())
507    }
508
509    #[test]
510    fn test_parity_bytes() -> Result<(), RSConstructorError> {
511        let rs = ReedSolomon::new(8)?;
512        assert_eq!(rs.parity_bytes(), 16);
513        Ok(())
514    }
515
516    #[test]
517    fn test_generate_parity_no_errors() -> Result<(), TestError> {
518        let rs = ReedSolomon::new(4)?;
519        let message = b"Test".to_buffer()?;
520        let parity = rs.generate_parity(&message)?;
521        assert_eq!(parity.len(), 8); // 4 parity * 2 bytes
522        Ok(())
523    }
524
525    #[test]
526    fn test_generate_parity_empty_message() -> Result<(), TestError> {
527        let rs = ReedSolomon::new(2)?;
528        let message = b"".to_buffer()?;
529        let parity = rs.generate_parity(&message)?;
530        assert_eq!(parity.len(), 4);
531        assert_eq!(parity.as_slice(), &[0, 0, 0, 0]);
532        Ok(())
533    }
534
535    #[test]
536    fn test_encode_correct_no_errors() -> Result<(), TestError> {
537        let rs = ReedSolomon::new(2)?;
538        let message = b"Data".to_buffer()?;
539        let encoded = rs.encode(&message)?;
540        let decoded = rs.decode(&encoded)?;
541        assert_eq!(&decoded[..], &message[..]);
542        Ok(())
543    }
544
545    #[test]
546    fn test_encode_correct_one_error() -> Result<(), TestError> {
547        let rs = ReedSolomon::new(3)?;
548        let message = b"Example".to_buffer()?;
549        let encoded = rs.encode(&message)?;
550        let mut corrupted = encoded.clone()?;
551        corrupted[1] ^= 0b1010_1010;
552        let decoded = rs.decode(&corrupted)?;
553        assert_eq!(&decoded[..], &message[..]);
554        Ok(())
555    }
556
557    #[test]
558    fn test_encode_correct_multiple_recoverable_errors() -> Result<(), TestError> {
559        let rs = ReedSolomon::new(4)?;
560        let message = b"Multiple".to_buffer()?;
561        let encoded = rs.encode(&message)?;
562        let mut corrupted = encoded.clone()?;
563        corrupted[3] ^= 0b0011_0011;
564        corrupted[7] ^= 0b1100_1100;
565        let decoded = rs.decode(&corrupted)?;
566        assert_eq!(&decoded[..], &message[..]);
567        Ok(())
568    }
569
570    #[test]
571    fn test_compute_syndromes_no_errors() -> Result<(), TestError> {
572        let rs = ReedSolomon::new(2)?;
573        let message = b"Syndrome".to_buffer()?;
574        let encoded = rs.encode(&message)?;
575        let syndromes = ReedSolomon::compute_syndromes(rs.parity_bytes(), &encoded)?;
576        assert!(syndromes.iter().all(|&s| s == 0));
577        Ok(())
578    }
579
580    #[test]
581    fn test_compute_syndromes_with_errors() -> Result<(), TestError> {
582        let rs = ReedSolomon::new(2)?;
583        let message = b"Syndrome".to_buffer()?;
584        let encoded = rs.encode(&message)?;
585        let mut corrupted = encoded.clone()?;
586        corrupted[0] ^= 1;
587        let syndromes = ReedSolomon::compute_syndromes(rs.parity_bytes(), &corrupted)?;
588        assert!(syndromes.iter().any(|&s| s != 0));
589        Ok(())
590    }
591
592    #[test]
593    fn test_compute_syndromes_detached_no_errors() -> Result<(), TestError> {
594        let rs = ReedSolomon::new(3)?;
595        let message = b"Detached".to_buffer()?;
596        let parity = rs.generate_parity(&message)?;
597        let syndromes = ReedSolomon::compute_syndromes_detached(&parity, &message)?;
598        assert!(syndromes.iter().all(|&s| s == 0));
599        Ok(())
600    }
601
602    #[test]
603    fn test_compute_syndromes_detached_with_errors() -> Result<(), TestError> {
604        let rs = ReedSolomon::new(3)?;
605        let message = b"Detached".to_buffer()?;
606        let parity = rs.generate_parity(&message)?;
607        let mut corrupted = message.clone()?;
608        corrupted[2] ^= 2;
609        let syndromes = ReedSolomon::compute_syndromes_detached(&parity, &corrupted)?;
610        assert!(syndromes.iter().any(|&s| s != 0));
611        Ok(())
612    }
613
614    #[test]
615    fn test_validate_no_errors() -> Result<(), TestError> {
616        let rs = ReedSolomon::new(1)?;
617        let message = b"Valid".to_buffer()?;
618        let encoded = rs.encode(&message)?;
619        assert!(rs.validate(&encoded)?.is_none());
620        Ok(())
621    }
622
623    #[test]
624    fn test_validate_with_errors() -> Result<(), TestError> {
625        let rs = ReedSolomon::new(1)?;
626        let message = b"Valid".to_buffer()?;
627        let encoded = rs.encode(&message)?;
628        let mut corrupted = encoded.clone()?;
629        corrupted[0] ^= 4;
630        assert!(rs.validate(&corrupted)?.is_some());
631        Ok(())
632    }
633
634    #[test]
635    fn test_validate_detached_no_errors_case_2() -> Result<(), TestError> {
636        let rs = ReedSolomon::new(2)?;
637        let message = b"Detached2".to_buffer()?;
638        let parity = rs.generate_parity(&message)?;
639        assert!(ReedSolomon::validate_detached(&parity, &message)?.is_none());
640        Ok(())
641    }
642
643    #[test]
644    fn test_validate_detached_with_errors_case_2() -> Result<(), TestError> {
645        let rs = ReedSolomon::new(2)?;
646        let message = b"Detached2".to_buffer()?;
647        let parity = rs.generate_parity(&message)?;
648        let mut corrupted = message.clone()?;
649        corrupted[1] ^= 8;
650        assert!(ReedSolomon::validate_detached(&parity, &corrupted)?.is_some());
651        Ok(())
652    }
653
654    #[test]
655    fn test_correct_in_place_no_errors() -> Result<(), TestError> {
656        let rs = ReedSolomon::new(2)?;
657        let message = b"InPlace".to_buffer()?;
658        let mut encoded = rs.encode(&message)?;
659        rs.correct_in_place(&mut encoded)?;
660        assert_eq!(encoded.slice(4..), message.as_slice());
661        Ok(())
662    }
663
664    #[test]
665    fn test_correct_in_place_one_error() -> Result<(), TestError> {
666        let rs = ReedSolomon::new(3)?;
667        let message = b"InPlace1".to_buffer()?;
668        let mut encoded = rs.encode(&message)?;
669        encoded[4] ^= 16;
670        rs.correct_in_place(&mut encoded)?;
671        assert_eq!(encoded.slice(6..), message.as_slice());
672        Ok(())
673    }
674
675    #[test]
676    fn test_correct_in_place_too_many_errors() -> Result<(), TestError> {
677        let rs = ReedSolomon::new(1)?;
678        let message = b"TooMany".to_buffer()?;
679        let mut encoded = rs.encode(&message)?;
680        encoded[0] ^= 1;
681        encoded[1] ^= 2;
682        assert_eq!(
683            rs.correct_in_place(&mut encoded),
684            Err(RSDecodeError::RSComputeErrorsError(
685                RSComputeErrorsError::TooManyErrors
686            ))
687        );
688        Ok(())
689    }
690
691    #[test]
692    fn test_decode_no_errors() -> Result<(), TestError> {
693        let rs = ReedSolomon::new(2)?;
694        let message = b"DecodeOk".to_buffer()?;
695        let encoded = rs.encode(&message)?;
696        let decoded = rs.decode(&encoded)?;
697        assert_eq!(&decoded[..], &message[..]);
698        Ok(())
699    }
700
701    #[test]
702    fn test_decode_one_error() -> Result<(), TestError> {
703        let rs = ReedSolomon::new(3)?;
704        let message = b"DecodeErr".to_buffer()?;
705        let encoded = rs.encode(&message)?;
706        let mut corrupted = encoded.clone()?;
707        corrupted[5] ^= 32;
708        let decoded = rs.decode(&corrupted)?;
709        assert_eq!(&decoded[..], &message[..]);
710        Ok(())
711    }
712
713    #[test]
714    fn test_decode_too_many_errors() -> Result<(), TestError> {
715        let rs = ReedSolomon::new(1)?;
716        let message = b"DecodeMany".to_buffer()?;
717        let encoded = rs.encode(&message)?;
718        let mut corrupted = encoded.clone()?;
719        corrupted[0] ^= 1;
720        corrupted[2] ^= 2;
721        assert_eq!(
722            rs.decode(&corrupted),
723            Err(RSDecodeError::RSComputeErrorsError(
724                RSComputeErrorsError::TooManyErrors
725            ))
726        );
727        Ok(())
728    }
729
730    #[test]
731    fn test_correct_detached_no_errors() -> Result<(), TestError> {
732        let rs = ReedSolomon::new(2)?;
733        let message = b"DetachOk".to_buffer()?;
734        let parity = rs.generate_parity(&message)?;
735        let corrected = ReedSolomon::correct_detached(&parity, &message)?;
736        assert_eq!(&corrected[..], &message[..]);
737        Ok(())
738    }
739
740    #[test]
741    fn test_correct_detached_one_error() -> Result<(), TestError> {
742        let rs = ReedSolomon::new(3)?;
743        let message = b"DetachErr".to_buffer()?;
744        let parity = rs.generate_parity(&message)?;
745        let mut corrupted = message.clone()?;
746        corrupted[1] ^= 64;
747        let corrected = ReedSolomon::correct_detached(&parity, &corrupted)?;
748        assert_eq!(&corrected[..], &message[..]);
749        Ok(())
750    }
751
752    #[test]
753    fn test_correct_detached_too_many_errors() -> Result<(), TestError> {
754        let rs = ReedSolomon::new(1)?;
755        let message = b"DetachMany".to_buffer()?;
756        let parity = rs.generate_parity(&message)?;
757        let mut corrupted = message.clone()?;
758        corrupted[0] ^= 1;
759        corrupted[2] ^= 2;
760        assert_eq!(
761            ReedSolomon::correct_detached(&parity, &corrupted),
762            Err(RSDecodeError::RSComputeErrorsError(
763                RSComputeErrorsError::TooManyErrors
764            ))
765        );
766        Ok(())
767    }
768
769    #[test]
770    fn test_correct_detached_data_in_place_no_errors() -> Result<(), TestError> {
771        let rs = ReedSolomon::new(2)?;
772        let message = b"DataInPlaceOk".to_buffer()?;
773        let parity = rs.generate_parity(&message)?;
774        let mut data = message.clone()?;
775        ReedSolomon::correct_detached_data_in_place(&parity, &mut data)?;
776        assert_eq!(data.as_slice(), message.as_slice());
777        Ok(())
778    }
779
780    #[test]
781    fn test_correct_detached_data_in_place_one_error() -> Result<(), TestError> {
782        let rs = ReedSolomon::new(3)?;
783        let message = b"DataInPlaceErr".to_buffer()?;
784        let parity = rs.generate_parity(&message)?;
785        let mut data = message.clone()?;
786        data[3] ^= 128;
787        ReedSolomon::correct_detached_data_in_place(&parity, &mut data)?;
788        assert_eq!(data.as_slice(), message.as_slice());
789        Ok(())
790    }
791
792    #[test]
793    fn test_correct_detached_data_in_place_too_many_errors() -> Result<(), TestError> {
794        let rs = ReedSolomon::new(1)?;
795        let message = b"DataInPlaceMany".to_buffer()?;
796        let parity = rs.generate_parity(&message)?;
797        let mut data = message.clone()?;
798        data[0] ^= 1;
799        data[2] ^= 2;
800        assert_eq!(
801            ReedSolomon::correct_detached_data_in_place(&parity, &mut data),
802            Err(RSDecodeError::RSComputeErrorsError(
803                RSComputeErrorsError::TooManyErrors
804            ))
805        );
806        Ok(())
807    }
808
809    #[test]
810    fn test_apply_corrections() -> Result<(), TestError> {
811        let mut target = Buffer::from_slice([1, 2, 3, 4])?;
812        let corrections = [0, 3, 0, 5];
813        ReedSolomon::apply_corrections(&mut target, corrections);
814        assert_eq!(target.as_slice(), &[1, 2 ^ 3, 3, 4 ^ 5]);
815        Ok(())
816    }
817
818    #[test]
819    fn test_apply_corrections_detached() -> Result<(), TestError> {
820        let mut parity = Buffer::from_slice([10, 20])?;
821        let mut data = Buffer::from_slice([30, 40, 50])?;
822        let corrections = [1, 2, 3, 4, 5];
823        ReedSolomon::apply_corrections_detached(&mut parity, &mut data, corrections);
824        assert_eq!(parity.as_slice(), &[10 ^ 1, 20 ^ 2]);
825        assert_eq!(data.as_slice(), &[30 ^ 3, 40 ^ 4, 50 ^ 5]);
826        Ok(())
827    }
828
829    #[test]
830    fn test_correct_both_detached_in_place_with_parity_error() -> Result<(), TestError> {
831        let rs = ReedSolomon::new(4)?;
832        let message = b"HelloAgain!".to_buffer()?;
833        let mut data = Buffer::with_capacity(message.len())?;
834        data.extend_from_slice(&message)?;
835        let mut parity = rs.generate_parity(&message)?;
836
837        parity[1] ^= 8;
838
839        ReedSolomon::correct_detached_in_place(&mut parity, &mut data)?;
840
841        assert_eq!(data.as_slice(), message.as_slice());
842        assert_eq!(parity, rs.generate_parity(&message)?);
843
844        Ok(())
845    }
846
847    #[test]
848    fn test_correct_both_detached_in_place_with_both_errors() -> Result<(), TestError> {
849        let rs = ReedSolomon::new(4)?;
850        let message = b"BothErrors".to_buffer()?;
851        let mut data = Buffer::with_capacity(message.len())?;
852        data.extend_from_slice(&message)?;
853        let mut parity = rs.generate_parity(&message)?;
854
855        data[3] ^= 16;
856        parity[0] ^= 4;
857
858        ReedSolomon::correct_detached_in_place(&mut parity, &mut data)?;
859
860        assert_eq!(data.as_slice(), message.as_slice());
861        assert_eq!(parity, rs.generate_parity(&message)?);
862
863        Ok(())
864    }
865
866    #[test]
867    fn test_correct_both_detached_in_place_too_many_errors() -> Result<(), TestError> {
868        let rs = ReedSolomon::new(2)?;
869        let message = b"TooManyBoth".to_buffer()?;
870        let mut data = Buffer::with_capacity(message.len())?;
871        data.extend_from_slice(&message)?;
872        let mut parity = rs.generate_parity(&message)?;
873
874        data[0] ^= 1;
875        data[2] ^= 2;
876        parity[1] ^= 4;
877        parity[3] ^= 8;
878
879        assert_eq!(
880            ReedSolomon::correct_detached_in_place(&mut parity, &mut data),
881            Err(RSDecodeError::RSComputeErrorsError(
882                RSComputeErrorsError::TooManyErrors
883            ))
884        );
885
886        Ok(())
887    }
888
889    #[test]
890    fn test_generate_parity_large_message() -> Result<(), TestError> {
891        let rs = ReedSolomon::new(8)?;
892        let message = vec![42; 200].to_buffer()?;
893        let parity = rs.generate_parity(&message)?;
894        assert_eq!(parity.len(), 16); // 8 parity * 2 bytes
895        let encoded = rs.encode(&message)?;
896        assert_eq!(&encoded[..16], parity.as_slice());
897        Ok(())
898    }
899
900    #[test]
901    fn test_encode_empty_message() -> Result<(), TestError> {
902        let rs = ReedSolomon::new(2)?;
903        let message = b"".to_buffer()?;
904        let encoded = rs.encode(&message)?;
905        assert_eq!(encoded.len(), 4); // 2 parity * 2 bytes
906        assert!(rs.validate(&encoded)?.is_none());
907        Ok(())
908    }
909
910    #[test]
911    fn test_correct_in_place_multiple_errors_at_boundaries() -> Result<(), TestError> {
912        let rs = ReedSolomon::new(4)?;
913        let message = b"Boundary".to_buffer()?;
914        let mut encoded = rs.encode(&message)?;
915        let len = encoded.len();
916        encoded[0] ^= 1; // Error at start
917        encoded[len - 1] ^= 2; // Error at end
918        rs.correct_in_place(&mut encoded)?;
919        assert_eq!(encoded.slice(8..), message.as_slice());
920        Ok(())
921    }
922
923    #[test]
924    fn test_decode_with_errors_in_parity_only() -> Result<(), TestError> {
925        let rs = ReedSolomon::new(3)?;
926        let message = b"ParityErr".to_buffer()?;
927        let encoded = rs.encode(&message)?;
928        let mut corrupted = encoded.clone()?;
929        corrupted[1] ^= 4; // Error in parity
930        corrupted[3] ^= 8; // Error in parity
931        let decoded = rs.decode(&corrupted)?;
932        assert_eq!(&decoded[..], &message[..]);
933        Ok(())
934    }
935
936    #[test]
937    fn test_correct_detached_data_in_place_multiple_errors() -> Result<(), TestError> {
938        let rs = ReedSolomon::new(4)?;
939        let message = b"MultiErr".to_buffer()?;
940        let parity = rs.generate_parity(&message)?;
941        let mut data = message.clone()?;
942        data[0] ^= 1;
943        data[4] ^= 16;
944        ReedSolomon::correct_detached_data_in_place(&parity, &mut data)?;
945        assert_eq!(data.as_slice(), message.as_slice());
946        Ok(())
947    }
948
949    #[test]
950    fn test_compute_syndromes_empty_codeword() -> Result<(), TestError> {
951        let syndromes = ReedSolomon::compute_syndromes(4u8, &[])?;
952        assert_eq!(syndromes.len(), 4);
953        assert!(syndromes.iter().all(|&s| s == 0));
954        Ok(())
955    }
956
957    #[test]
958    fn test_compute_syndromes_detached_empty_data() -> Result<(), TestError> {
959        let rs = ReedSolomon::new(2)?;
960        let parity = rs.generate_parity(&[])?;
961        let syndromes = ReedSolomon::compute_syndromes_detached(&parity, &[])?;
962        assert_eq!(syndromes.len(), 4);
963        assert!(syndromes.iter().all(|&s| s == 0));
964        Ok(())
965    }
966
967    #[test]
968    fn test_correct_maximum_correctable_errors() -> Result<(), TestError> {
969        let rs = ReedSolomon::new(4)?;
970        let message = b"MaxErrors".to_buffer()?;
971        let encoded = rs.encode(&message)?;
972        let mut corrupted = encoded.clone()?;
973        corrupted[0] ^= 1;
974        corrupted[2] ^= 2;
975        corrupted[4] ^= 4;
976        corrupted[6] ^= 8;
977        let decoded = rs.decode(&corrupted)?;
978        assert_eq!(&decoded[..], &message[..]);
979        Ok(())
980    }
981
982    #[test]
983    fn test_correct_detached_with_errors_in_parity_only() -> Result<(), TestError> {
984        let rs = ReedSolomon::new(3)?;
985        let message = b"ParityOnly".to_buffer()?;
986        let mut parity = rs.generate_parity(&message)?;
987        parity[0] ^= 2;
988        parity[2] ^= 4;
989        let corrected = ReedSolomon::correct_detached(&parity, &message)?;
990        assert_eq!(&corrected[..], &message[..]);
991        Ok(())
992    }
993
994    #[test]
995    fn test_apply_corrections_empty_target() -> Result<(), TestError> {
996        let mut target = Buffer::from_slice([])?;
997        let corrections = [];
998        ReedSolomon::apply_corrections(&mut target, corrections);
999        assert_eq!(target.as_slice(), &[]);
1000        Ok(())
1001    }
1002
1003    #[test]
1004    fn test_apply_corrections_detached_empty() -> Result<(), TestError> {
1005        let mut parity = Buffer::from_slice([])?;
1006        let mut data = Buffer::from_slice([])?;
1007        let corrections = [];
1008        ReedSolomon::apply_corrections_detached(&mut parity, &mut data, corrections);
1009        assert_eq!(parity.as_slice(), &[]);
1010        assert_eq!(data.as_slice(), &[]);
1011        Ok(())
1012    }
1013
1014    #[test]
1015    fn test_validate_large_parity() -> Result<(), TestError> {
1016        let rs = ReedSolomon::new(16)?;
1017        let message = b"LargeParity".to_buffer()?;
1018        let encoded = rs.encode(&message)?;
1019        assert!(rs.validate(&encoded)?.is_none());
1020        let mut corrupted = encoded.clone()?;
1021        corrupted[10] ^= 1;
1022        assert!(rs.validate(&corrupted)?.is_some());
1023        Ok(())
1024    }
1025
1026    #[test]
1027    fn test_correct_in_place_all_zeros() -> Result<(), TestError> {
1028        let rs = ReedSolomon::new(2)?;
1029        let message = vec![0; 10].to_buffer()?;
1030        let mut encoded = rs.encode(&message)?;
1031        encoded[2] ^= 1;
1032        rs.correct_in_place(&mut encoded)?;
1033        assert_eq!(encoded.slice(4..), message.as_slice());
1034        Ok(())
1035    }
1036}
ps_ecc/reed_solomon.rs

ps_ecc/
reed_solomon.rs
