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

rustfs_erasure_codec/
lib.rs
