reed_solomon_erasure/
lib.rs

1//! This crate provides an encoder/decoder for Reed-Solomon erasure code.
2//!
3//! Please note that erasure coding means errors are not directly detected or corrected,
4//! but missing data pieces (shards) can be reconstructed given that
5//! the configuration provides high enough redundancy.
6//!
7//! You will have to implement error detection separately (e.g. via checksums)
8//! and simply leave out the corrupted shards when attempting to reconstruct
9//! the missing data.
10#![allow(dead_code)]
11#![cfg_attr(not(feature = "std"), no_std)]
12
13#[cfg(test)]
14#[macro_use]
15extern crate quickcheck;
16
17#[cfg(test)]
18extern crate rand;
19
20extern crate smallvec;
21
22#[cfg(feature = "simd-accel")]
23extern crate libc;
24
25use ::core::iter;
26use ::core::iter::FromIterator;
27
28#[macro_use]
29mod macros;
30
31mod core;
32mod errors;
33mod matrix;
34
35#[cfg(test)]
36mod tests;
37
38pub mod galois_16;
39pub mod galois_8;
40
41pub use crate::errors::Error;
42pub use crate::errors::SBSError;
43
44pub use crate::core::ReedSolomon;
45pub use crate::core::ShardByShard;
46
47// TODO: Can be simplified once https://github.com/rust-lang/rfcs/issues/2505 is resolved
48#[cfg(not(feature = "std"))]
49use libm::log2f as log2;
50#[cfg(feature = "std")]
51fn log2(n: f32) -> f32 {
52    n.log2()
53}
54
55/// A finite field to perform encoding over.
56pub trait Field: Sized {
57    /// The order of the field. This is a limit on the number of shards
58    /// in an encoding.
59    const ORDER: usize;
60
61    /// The representational type of the field.
62    type Elem: Default + Clone + Copy + PartialEq + ::core::fmt::Debug;
63
64    /// Add two elements together.
65    fn add(a: Self::Elem, b: Self::Elem) -> Self::Elem;
66
67    /// Multiply two elements together.
68    fn mul(a: Self::Elem, b: Self::Elem) -> Self::Elem;
69
70    /// Divide a by b. Panics is b is zero.
71    fn div(a: Self::Elem, b: Self::Elem) -> Self::Elem;
72
73    /// Raise `a` to the n'th power.
74    fn exp(a: Self::Elem, n: usize) -> Self::Elem;
75
76    /// The "zero" element or additive identity.
77    fn zero() -> Self::Elem;
78
79    /// The "one" element or multiplicative identity.
80    fn one() -> Self::Elem;
81
82    fn nth_internal(n: usize) -> Self::Elem;
83
84    /// Yield the nth element of the field. Panics if n >= ORDER.
85    /// Assignment is arbitrary but must be unique to `n`.
86    fn nth(n: usize) -> Self::Elem {
87        if n >= Self::ORDER {
88            let pow = log2(Self::ORDER as f32) as usize;
89            panic!("{} out of bounds for GF(2^{}) member", n, pow)
90        }
91
92        Self::nth_internal(n)
93    }
94
95    /// Multiply a slice of elements by another. Writes into the output slice.
96    ///
97    /// # Panics
98    /// Panics if the output slice does not have equal length to the input.
99    fn mul_slice(elem: Self::Elem, input: &[Self::Elem], out: &mut [Self::Elem]) {
100        assert_eq!(input.len(), out.len());
101
102        for (i, o) in input.iter().zip(out) {
103            *o = Self::mul(elem.clone(), i.clone())
104        }
105    }
106
107    /// Multiply a slice of elements by another, adding each result to the corresponding value in
108    /// `out`.
109    ///
110    /// # Panics
111    /// Panics if the output slice does not have equal length to the input.
112    fn mul_slice_add(elem: Self::Elem, input: &[Self::Elem], out: &mut [Self::Elem]) {
113        assert_eq!(input.len(), out.len());
114
115        for (i, o) in input.iter().zip(out) {
116            *o = Self::add(o.clone(), Self::mul(elem.clone(), i.clone()))
117        }
118    }
119}
120
121/// Something which might hold a shard.
122///
123/// This trait is used in reconstruction, where some of the shards
124/// may be unknown.
125pub trait ReconstructShard<F: Field> {
126    /// The size of the shard data; `None` if empty.
127    fn len(&self) -> Option<usize>;
128
129    /// Get a mutable reference to the shard data, returning `None` if uninitialized.
130    fn get(&mut self) -> Option<&mut [F::Elem]>;
131
132    /// Get a mutable reference to the shard data, initializing it to the
133    /// given length if it was `None`. Returns an error if initialization fails.
134    fn get_or_initialize(
135        &mut self,
136        len: usize,
137    ) -> Result<&mut [F::Elem], Result<&mut [F::Elem], Error>>;
138}
139
140impl<F: Field, T: AsRef<[F::Elem]> + AsMut<[F::Elem]> + FromIterator<F::Elem>> ReconstructShard<F>
141    for Option<T>
142{
143    fn len(&self) -> Option<usize> {
144        self.as_ref().map(|x| x.as_ref().len())
145    }
146
147    fn get(&mut self) -> Option<&mut [F::Elem]> {
148        self.as_mut().map(|x| x.as_mut())
149    }
150
151    fn get_or_initialize(
152        &mut self,
153        len: usize,
154    ) -> Result<&mut [F::Elem], Result<&mut [F::Elem], Error>> {
155        let is_some = self.is_some();
156        let x = self
157            .get_or_insert_with(|| iter::repeat(F::zero()).take(len).collect())
158            .as_mut();
159
160        if is_some {
161            Ok(x)
162        } else {
163            Err(Ok(x))
164        }
165    }
166}
167
168impl<F: Field, T: AsRef<[F::Elem]> + AsMut<[F::Elem]>> ReconstructShard<F> for (T, bool) {
169    fn len(&self) -> Option<usize> {
170        if !self.1 {
171            None
172        } else {
173            Some(self.0.as_ref().len())
174        }
175    }
176
177    fn get(&mut self) -> Option<&mut [F::Elem]> {
178        if !self.1 {
179            None
180        } else {
181            Some(self.0.as_mut())
182        }
183    }
184
185    fn get_or_initialize(
186        &mut self,
187        len: usize,
188    ) -> Result<&mut [F::Elem], Result<&mut [F::Elem], Error>> {
189        let x = self.0.as_mut();
190        if x.len() == len {
191            if self.1 {
192                Ok(x)
193            } else {
194                Err(Ok(x))
195            }
196        } else {
197            Err(Err(Error::IncorrectShardSize))
198        }
199    }
200}
reed_solomon_erasure/lib.rs

reed_solomon_erasure/
lib.rs
