commonware_cryptography/reed_solomon/
engine.rs

1//! Low-level building blocks for Reed-Solomon encoding/decoding.
2//!
3//! **This is an advanced module which is not needed for [simple usage] or [basic usage].**
4//!
5//! This module is relevant if you want to
6//! - use [`rate`] module and need an [`Engine`] to use with it.
7//! - create your own [`Engine`].
8//! - understand/benchmark/test at low level.
9//!
10//! # Engines
11//!
12//! An [`Engine`] is an implementation of basic low-level algorithms
13//! needed for Reed-Solomon encoding/decoding.
14//!
15//! - [`Naive`]
16//!     - Simple reference implementation.
17//! - [`NoSimd`]
18//!     - Basic optimized engine without SIMD so that it works on all CPUs.
19//! - `Avx2`
20//!     - Optimized engine that takes advantage of the x86(-64) AVX2 SIMD instructions.
21//! - `Ssse3`
22//!     - Optimized engine that takes advantage of the x86(-64) SSSE3 SIMD instructions.
23//! - `Neon`
24//!     - Optimized engine that takes advantage of the `AArch64` Neon SIMD instructions.
25//! - [`DefaultEngine`]
26//!     - Default engine which is used when no specific engine is given.
27//!     - Automatically selects best engine at runtime.
28//!
29//! [simple usage]: crate::reed_solomon#simple-usage
30//! [basic usage]: crate::reed_solomon#basic-usage
31//! [`Encoder`]: crate::reed_solomon::Encoder
32//! [`Decoder`]: crate::reed_solomon::Decoder
33//! [`rate`]: crate::reed_solomon::rate
34
35// TODO(https://github.com/commonwarexyz/monorepo/issues/4414): Bump cpufeatures and remove this workaround.
36#[allow(
37    unfulfilled_lint_expectations,
38    reason = "stable Rust does not emit this nightly-only deprecation"
39)]
40#[expect(
41    deprecated,
42    reason = "tracked by https://github.com/commonwarexyz/monorepo/issues/4414"
43)]
44mod cpu_features {
45    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
46    cpufeatures::new!(has_avx2, "avx2");
47    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
48    cpufeatures::new!(has_ssse3, "ssse3");
49    #[cfg(target_arch = "aarch64")]
50    cpufeatures::new!(has_neon, "neon");
51
52    #[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
53    pub(super) use self::{has_avx2::get as avx2, has_ssse3::get as ssse3};
54    #[cfg(target_arch = "aarch64")]
55    pub(super) use has_neon::get as neon;
56}
57
58#[cfg(target_arch = "aarch64")]
59pub use self::engine_neon::Neon;
60pub(crate) use self::shards::Shards;
61#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
62pub use self::{engine_avx2::Avx2, engine_ssse3::Ssse3};
63pub use self::{
64    engine_default::DefaultEngine, engine_naive::Naive, engine_nosimd::NoSimd, shards::ShardsRefMut,
65};
66pub(crate) use utils::{fft_skew_end, formal_derivative, ifft_skew_end, xor_within};
67
68mod engine_default;
69mod engine_naive;
70mod engine_nosimd;
71
72#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
73mod engine_avx2;
74#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
75mod engine_ssse3;
76
77#[cfg(target_arch = "aarch64")]
78mod engine_neon;
79
80mod fwht;
81mod shards;
82
83pub mod tables;
84pub mod utils;
85
86// ======================================================================
87// CONST - PUBLIC
88
89/// Size of Galois field element [`GfElement`] in bits.
90pub const GF_BITS: usize = 16;
91
92/// Galois field order, i.e. number of elements.
93pub const GF_ORDER: usize = 65536;
94
95/// `GF_ORDER - 1`
96pub const GF_MODULUS: GfElement = 65535;
97
98/// Galois field polynomial.
99pub const GF_POLYNOMIAL: usize = 0x1002D;
100
101/// Byte width of a shard chunk.
102///
103/// [`Engine`] methods process shard buffers as arrays of this size.
104/// Input shards may span multiple chunks; any partial final chunk is padded
105/// during processing and returned at the original shard length.
106pub const SHARD_CHUNK_BYTES: usize = 64;
107
108/// Cantor basis used by the additive FFT over GF(2^16).
109pub const CANTOR_BASIS: [GfElement; GF_BITS] = [
110    0x0001, 0xACCA, 0x3C0E, 0x163E, 0xC582, 0xED2E, 0x914C, 0x4012, 0x6C98, 0x10D8, 0x6A72, 0xB900,
111    0xFDB8, 0xFB34, 0xFF38, 0x991E,
112];
113
114// ======================================================================
115// TYPE ALIASES - PUBLIC
116
117/// Galois field element.
118pub type GfElement = u16;
119
120// ======================================================================
121// Engine - PUBLIC
122
123/// Trait for compute-intensive low-level algorithms needed
124/// for Reed-Solomon encoding/decoding.
125///
126/// This is the trait you would implement to provide SIMD support
127/// for a CPU architecture not already provided.
128///
129/// [`Naive`] engine is provided for those who want to
130/// study the source code to understand [`Engine`].
131pub trait Engine {
132    // ============================================================
133    // REQUIRED
134
135    /// In-place decimation-in-time FFT (fast Fourier transform).
136    ///
137    /// - FFT is done on chunk `data[pos .. pos + size]`
138    /// - `size` must be `2^n`
139    /// - Before function call `data[pos .. pos + size]` must be valid.
140    /// - After function call
141    ///     - `data[pos .. pos + truncated_size]`
142    ///       contains valid FFT result.
143    ///     - `data[pos + truncated_size .. pos + size]`
144    ///       contains valid FFT result if this contained
145    ///       only `0u8`:s and garbage otherwise.
146    fn fft(
147        &self,
148        data: &mut ShardsRefMut<'_>,
149        pos: usize,
150        size: usize,
151        truncated_size: usize,
152        skew_delta: usize,
153    );
154
155    /// In-place decimation-in-time IFFT (inverse fast Fourier transform).
156    ///
157    /// - IFFT is done on chunk `data[pos .. pos + size]`
158    /// - `size` must be `2^n`
159    /// - Before function call `data[pos .. pos + size]` must be valid.
160    /// - After function call
161    ///     - `data[pos .. pos + truncated_size]`
162    ///       contains valid IFFT result.
163    ///     - `data[pos + truncated_size .. pos + size]`
164    ///       contains valid IFFT result if this contained
165    ///       only `0u8`:s and garbage otherwise.
166    fn ifft(
167        &self,
168        data: &mut ShardsRefMut<'_>,
169        pos: usize,
170        size: usize,
171        truncated_size: usize,
172        skew_delta: usize,
173    );
174
175    /// `x[] *= log_m`
176    fn mul(&self, x: &mut [[u8; SHARD_CHUNK_BYTES]], log_m: GfElement);
177
178    // ============================================================
179    // PROVIDED
180
181    /// Evaluate polynomial.
182    fn eval_poly(erasures: &mut [GfElement; GF_ORDER], truncated_size: usize)
183    where
184        Self: Sized,
185    {
186        utils::eval_poly(erasures, truncated_size);
187    }
188}
189
190// ======================================================================
191// TESTS
192
193// Engines are tested indirectly via roundtrip tests of HighRate and LowRate.
commonware_cryptography/reed_solomon/engine.rs

commonware_cryptography/reed_solomon/
engine.rs
