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

ps_ecc/
reed_solomon.rs
