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

ps_ecc/
reed_solomon.rs
