rustfs_erasure_codec/
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(any(
23    feature = "simd-neon",
24    feature = "simd-ssse3",
25    feature = "simd-avx2",
26    feature = "simd-avx512",
27    feature = "simd-gfni",
28))]
29extern crate libc;
30
31use ::core::iter::FromIterator;
32
33#[macro_use]
34mod macros;
35
36mod core;
37mod errors;
38mod matrix;
39
40#[cfg(test)]
41mod tests;
42
43pub mod galois_16;
44pub mod galois_8;
45
46pub use crate::errors::Error;
47pub use crate::errors::SBSError;
48
49pub use crate::core::CodecFamily;
50pub use crate::core::CodecOptions;
51#[cfg(feature = "std")]
52pub use crate::core::LeopardGf8ProfileStats;
53pub use crate::core::MatrixMode;
54#[cfg(feature = "std")]
55pub use crate::core::PARALLEL_POLICY_VERSION;
56#[cfg(feature = "std")]
57pub use crate::core::ParallelDecision;
58#[cfg(feature = "std")]
59pub use crate::core::ParallelPolicy;
60#[cfg(feature = "std")]
61pub use crate::core::ReconstructionCacheAnalysis;
62#[cfg(feature = "std")]
63pub use crate::core::ReconstructionCacheStats;
64pub use crate::core::ReedSolomon;
65#[cfg(feature = "std")]
66pub use crate::core::RuntimeProfileStats;
67pub use crate::core::ShardByShard;
68pub use crate::core::VerifyWorkspace;
69#[cfg(feature = "std")]
70pub use crate::core::stream;
71
72#[cfg(feature = "std")]
73pub fn leopard_gf8_profile_stats() -> LeopardGf8ProfileStats {
74    crate::core::leopard_gf8_profile_stats()
75}
76
77#[cfg(feature = "std")]
78pub fn reset_leopard_gf8_profile_stats() {
79    crate::core::reset_leopard_gf8_profile_stats()
80}
81
82// TODO: Can be simplified once https://github.com/rust-lang/rfcs/issues/2505 is resolved
83#[cfg(not(feature = "std"))]
84use libm::log2f as log2;
85#[cfg(feature = "std")]
86fn log2(n: f32) -> f32 {
87    n.log2()
88}
89
90/// A finite field to perform encoding over.
91pub trait Field: Sized {
92    /// The order of the field. This is a limit on the number of shards
93    /// in an encoding.
94    const ORDER: usize;
95
96    /// The representational type of the field.
97    type Elem: Default + Clone + Copy + PartialEq + ::core::fmt::Debug;
98
99    /// Add two elements together.
100    fn add(a: Self::Elem, b: Self::Elem) -> Self::Elem;
101
102    /// Multiply two elements together.
103    fn mul(a: Self::Elem, b: Self::Elem) -> Self::Elem;
104
105    /// Divide a by b. Panics is b is zero.
106    fn div(a: Self::Elem, b: Self::Elem) -> Self::Elem;
107
108    /// Raise `a` to the n'th power.
109    fn exp(a: Self::Elem, n: usize) -> Self::Elem;
110
111    /// The "zero" element or additive identity.
112    fn zero() -> Self::Elem;
113
114    /// The "one" element or multiplicative identity.
115    fn one() -> Self::Elem;
116
117    fn nth_internal(n: usize) -> Self::Elem;
118
119    /// Return `Some` when `n < ORDER`, otherwise `None`.
120    fn nth_checked(n: usize) -> Option<Self::Elem> {
121        if n >= Self::ORDER {
122            None
123        } else {
124            Some(Self::nth_internal(n))
125        }
126    }
127
128    /// Yield the nth element of the field.
129    ///
130    /// For out-of-range `n`, returns a wrapping value in production and triggers a
131    /// debug assertion.
132    /// Assignment is arbitrary but must be unique to `n`.
133    fn nth(n: usize) -> Self::Elem {
134        Self::nth_checked(n).unwrap_or_else(|| {
135            debug_assert!(
136                false,
137                "Field::nth received out-of-range index: {} for GF(2^{}) order {}",
138                n,
139                log2(Self::ORDER as f32) as usize,
140                Self::ORDER
141            );
142            let fallback_n = n % Self::ORDER.max(1);
143            Self::nth_internal(fallback_n)
144        })
145    }
146
147    /// Multiply a slice of elements by another. Writes into the output slice.
148    ///
149    /// # Panics
150    /// Panics if the output slice does not have equal length to the input.
151    fn mul_slice(elem: Self::Elem, input: &[Self::Elem], out: &mut [Self::Elem]) {
152        assert_eq!(input.len(), out.len());
153
154        for (i, o) in input.iter().zip(out) {
155            *o = Self::mul(elem, *i)
156        }
157    }
158
159    /// Multiply a slice of elements by another, adding each result to the corresponding value in
160    /// `out`.
161    ///
162    /// # Panics
163    /// Panics if the output slice does not have equal length to the input.
164    fn mul_slice_add(elem: Self::Elem, input: &[Self::Elem], out: &mut [Self::Elem]) {
165        assert_eq!(input.len(), out.len());
166
167        for (i, o) in input.iter().zip(out) {
168            *o = Self::add(*o, Self::mul(elem, *i))
169        }
170    }
171}
172
173pub type ReconstructInitResult<'a, F> =
174    Result<&'a mut [<F as Field>::Elem], Result<&'a mut [<F as Field>::Elem], Error>>;
175
176/// A reusable shard container for reconstruction workflows.
177///
178/// Unlike `Option<Vec<_>>`, this keeps ownership of the backing buffer even when
179/// the shard is marked missing, which lets callers reuse preallocated storage
180/// across repeated reconstruct calls.
181#[derive(Clone, Debug, PartialEq, Eq)]
182pub struct ShardSlot<T> {
183    data: T,
184    present: bool,
185}
186
187impl<T> ShardSlot<T> {
188    /// Create a shard slot whose data is already present.
189    pub fn new_present(data: T) -> Self {
190        Self {
191            data,
192            present: true,
193        }
194    }
195
196    /// Create a shard slot whose buffer exists but is currently marked missing.
197    pub fn new_missing(data: T) -> Self {
198        Self {
199            data,
200            present: false,
201        }
202    }
203
204    /// Create a shard slot with an explicit presence flag.
205    pub fn with_present(data: T, present: bool) -> Self {
206        Self { data, present }
207    }
208
209    /// Returns whether the shard is currently marked present.
210    pub fn is_present(&self) -> bool {
211        self.present
212    }
213
214    /// Mark the shard as present.
215    pub fn mark_present(&mut self) {
216        self.present = true;
217    }
218
219    /// Mark the shard as missing while retaining ownership of its buffer.
220    pub fn mark_missing(&mut self) {
221        self.present = false;
222    }
223
224    /// Access the inner storage regardless of presence state.
225    pub fn as_inner(&self) -> &T {
226        &self.data
227    }
228
229    /// Mutably access the inner storage regardless of presence state.
230    pub fn as_inner_mut(&mut self) -> &mut T {
231        &mut self.data
232    }
233
234    /// Consume the slot and return the inner storage.
235    pub fn into_inner(self) -> T {
236        self.data
237    }
238}
239
240/// Something which might hold a shard.
241///
242/// This trait is used in reconstruction, where some of the shards
243/// may be unknown.
244pub trait ReconstructShard<F: Field> {
245    /// The size of the shard data; `None` if empty.
246    fn len(&self) -> Option<usize>;
247
248    fn is_empty(&self) -> bool {
249        self.len().is_none()
250    }
251
252    /// Get a mutable reference to the shard data, returning `None` if uninitialized.
253    fn get(&mut self) -> Option<&mut [F::Elem]>;
254
255    /// Get a mutable reference to the shard data, initializing it to the
256    /// given length if it was `None`. Returns an error if initialization fails.
257    fn get_or_initialize(&mut self, len: usize) -> ReconstructInitResult<'_, F>;
258}
259
260impl<F: Field, T: AsRef<[F::Elem]> + AsMut<[F::Elem]> + FromIterator<F::Elem>> ReconstructShard<F>
261    for Option<T>
262{
263    fn len(&self) -> Option<usize> {
264        self.as_ref().map(|x| x.as_ref().len())
265    }
266
267    fn get(&mut self) -> Option<&mut [F::Elem]> {
268        self.as_mut().map(|x| x.as_mut())
269    }
270
271    fn get_or_initialize(&mut self, len: usize) -> ReconstructInitResult<'_, F> {
272        let is_some = self.is_some();
273        let x = self
274            .get_or_insert_with(|| ::core::iter::repeat_n(F::zero(), len).collect())
275            .as_mut();
276
277        if is_some { Ok(x) } else { Err(Ok(x)) }
278    }
279}
280
281impl<F: Field, T: AsRef<[F::Elem]> + AsMut<[F::Elem]>> ReconstructShard<F> for (T, bool) {
282    fn len(&self) -> Option<usize> {
283        if !self.1 {
284            None
285        } else {
286            Some(self.0.as_ref().len())
287        }
288    }
289
290    fn get(&mut self) -> Option<&mut [F::Elem]> {
291        if !self.1 { None } else { Some(self.0.as_mut()) }
292    }
293
294    fn get_or_initialize(&mut self, len: usize) -> ReconstructInitResult<'_, F> {
295        let x = self.0.as_mut();
296        if x.len() == len {
297            if self.1 {
298                Ok(x)
299            } else {
300                self.1 = true;
301                Err(Ok(x))
302            }
303        } else {
304            Err(Err(Error::IncorrectShardSize))
305        }
306    }
307}
308
309impl<F: Field, T: AsRef<[F::Elem]> + AsMut<[F::Elem]>> ReconstructShard<F> for ShardSlot<T> {
310    fn len(&self) -> Option<usize> {
311        if self.present {
312            Some(self.data.as_ref().len())
313        } else {
314            None
315        }
316    }
317
318    fn get(&mut self) -> Option<&mut [F::Elem]> {
319        if self.present {
320            Some(self.data.as_mut())
321        } else {
322            None
323        }
324    }
325
326    fn get_or_initialize(&mut self, len: usize) -> ReconstructInitResult<'_, F> {
327        let x = self.data.as_mut();
328        if x.len() == len {
329            if self.present {
330                Ok(x)
331            } else {
332                self.present = true;
333                Err(Ok(x))
334            }
335        } else {
336            Err(Err(Error::IncorrectShardSize))
337        }
338    }
339}
rustfs_erasure_codec/lib.rs

rustfs_erasure_codec/
lib.rs
