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#[cfg(target_arch = "aarch64")]
36pub use self::engine_neon::Neon;
37pub(crate) use self::shards::Shards;
38#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
39pub use self::{engine_avx2::Avx2, engine_ssse3::Ssse3};
40pub use self::{
41 engine_default::DefaultEngine, engine_naive::Naive, engine_nosimd::NoSimd, shards::ShardsRefMut,
42};
43pub(crate) use utils::{fft_skew_end, formal_derivative, ifft_skew_end, xor_within};
44
45mod engine_default;
46mod engine_naive;
47mod engine_nosimd;
48
49#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
50mod engine_avx2;
51#[cfg(any(target_arch = "x86", target_arch = "x86_64"))]
52mod engine_ssse3;
53
54#[cfg(target_arch = "aarch64")]
55mod engine_neon;
56
57mod fwht;
58mod shards;
59
60pub mod tables;
61pub mod utils;
62
63// ======================================================================
64// CONST - PUBLIC
65
66/// Size of Galois field element [`GfElement`] in bits.
67pub const GF_BITS: usize = 16;
68
69/// Galois field order, i.e. number of elements.
70pub const GF_ORDER: usize = 65536;
71
72/// `GF_ORDER - 1`
73pub const GF_MODULUS: GfElement = 65535;
74
75/// Galois field polynomial.
76pub const GF_POLYNOMIAL: usize = 0x1002D;
77
78/// Byte width of a shard chunk.
79///
80/// [`Engine`] methods process shard buffers as arrays of this size.
81/// Input shards may span multiple chunks; any partial final chunk is padded
82/// during processing and returned at the original shard length.
83pub const SHARD_CHUNK_BYTES: usize = 64;
84
85/// Cantor basis used by the additive FFT over GF(2^16).
86pub const CANTOR_BASIS: [GfElement; GF_BITS] = [
87 0x0001, 0xACCA, 0x3C0E, 0x163E, 0xC582, 0xED2E, 0x914C, 0x4012, 0x6C98, 0x10D8, 0x6A72, 0xB900,
88 0xFDB8, 0xFB34, 0xFF38, 0x991E,
89];
90
91// ======================================================================
92// TYPE ALIASES - PUBLIC
93
94/// Galois field element.
95pub type GfElement = u16;
96
97// ======================================================================
98// Engine - PUBLIC
99
100/// Trait for compute-intensive low-level algorithms needed
101/// for Reed-Solomon encoding/decoding.
102///
103/// This is the trait you would implement to provide SIMD support
104/// for a CPU architecture not already provided.
105///
106/// [`Naive`] engine is provided for those who want to
107/// study the source code to understand [`Engine`].
108pub trait Engine {
109 // ============================================================
110 // REQUIRED
111
112 /// In-place decimation-in-time FFT (fast Fourier transform).
113 ///
114 /// - FFT is done on chunk `data[pos .. pos + size]`
115 /// - `size` must be `2^n`
116 /// - Before function call `data[pos .. pos + size]` must be valid.
117 /// - After function call
118 /// - `data[pos .. pos + truncated_size]`
119 /// contains valid FFT result.
120 /// - `data[pos + truncated_size .. pos + size]`
121 /// contains valid FFT result if this contained
122 /// only `0u8`:s and garbage otherwise.
123 fn fft(
124 &self,
125 data: &mut ShardsRefMut<'_>,
126 pos: usize,
127 size: usize,
128 truncated_size: usize,
129 skew_delta: usize,
130 );
131
132 /// In-place decimation-in-time IFFT (inverse fast Fourier transform).
133 ///
134 /// - IFFT is done on chunk `data[pos .. pos + size]`
135 /// - `size` must be `2^n`
136 /// - Before function call `data[pos .. pos + size]` must be valid.
137 /// - After function call
138 /// - `data[pos .. pos + truncated_size]`
139 /// contains valid IFFT result.
140 /// - `data[pos + truncated_size .. pos + size]`
141 /// contains valid IFFT result if this contained
142 /// only `0u8`:s and garbage otherwise.
143 fn ifft(
144 &self,
145 data: &mut ShardsRefMut<'_>,
146 pos: usize,
147 size: usize,
148 truncated_size: usize,
149 skew_delta: usize,
150 );
151
152 /// `x[] *= log_m`
153 fn mul(&self, x: &mut [[u8; SHARD_CHUNK_BYTES]], log_m: GfElement);
154
155 // ============================================================
156 // PROVIDED
157
158 /// Evaluate polynomial.
159 fn eval_poly(erasures: &mut [GfElement; GF_ORDER], truncated_size: usize)
160 where
161 Self: Sized,
162 {
163 utils::eval_poly(erasures, truncated_size);
164 }
165}
166
167// ======================================================================
168// TESTS
169
170// Engines are tested indirectly via roundtrip tests of HighRate and LowRate.