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

ps_ecc/
reed_solomon.rs
