reed_solomon_simd/engine/
utils.rs

1//! A collection of utility functions and helpers to facilitate the implementation of the [`Engine`] trait.
2//!
3//! [`Engine`]: crate::engine::Engine
4
5use crate::engine::{fwht, tables, Engine, GfElement, ShardsRefMut, GF_BITS, GF_ORDER};
6use std::iter::zip;
7
8// ======================================================================
9// FUNCTIONS - PUBLIC
10
11/// Evaluate Polynomial using Fast Walsh-Hadamard Transform (FWHT).
12///
13/// This function is designed to be inlined and be compiled with SIMD
14/// features enabled within an Engine's implementation of `eval_poly`.
15///
16/// See [`Avx2`] for an example on how to do this.
17///
18/// [`Avx2`]: crate::engine::Avx2
19#[inline(always)]
20pub fn eval_poly(erasures: &mut [GfElement; GF_ORDER], truncated_size: usize) {
21    let log_walsh = &*tables::LOG_WALSH;
22
23    fwht::fwht(erasures, truncated_size);
24
25    for (e, factor) in std::iter::zip(erasures.iter_mut(), log_walsh.iter()) {
26        let product = u32::from(*e) * u32::from(*factor);
27        *e = add_mod(product as GfElement, (product >> GF_BITS) as GfElement);
28    }
29
30    fwht::fwht(erasures, GF_ORDER);
31}
32
33/// `x[] ^= y[]`
34#[inline(always)]
35pub fn xor(xs: &mut [[u8; 64]], ys: &[[u8; 64]]) {
36    debug_assert_eq!(xs.len(), ys.len());
37
38    for (x_chunk, y_chunk) in zip(xs.iter_mut(), ys.iter()) {
39        for (x, y) in zip(x_chunk.iter_mut(), y_chunk.iter()) {
40            *x ^= y;
41        }
42    }
43}
44
45/// `data[x .. x + count] ^= data[y .. y + count]`
46///
47/// Ranges must not overlap.
48#[inline(always)]
49pub fn xor_within(data: &mut ShardsRefMut, x: usize, y: usize, count: usize) {
50    let (xs, ys) = data.flat2_mut(x, y, count);
51    xor(xs, ys);
52}
53
54// ======================================================================
55// FUNCTIONS - CRATE - Galois field operations
56
57/// Some kind of addition.
58#[inline(always)]
59pub(crate) fn add_mod(x: GfElement, y: GfElement) -> GfElement {
60    let sum = u32::from(x) + u32::from(y);
61    (sum + (sum >> GF_BITS)) as GfElement
62}
63
64/// Some kind of subtraction.
65#[inline(always)]
66pub(crate) fn sub_mod(x: GfElement, y: GfElement) -> GfElement {
67    let dif = u32::from(x).wrapping_sub(u32::from(y));
68    dif.wrapping_add(dif >> GF_BITS) as GfElement
69}
70
71// ======================================================================
72// FUNCTIONS - CRATE
73
74/// FFT with `skew_delta = pos + size`.
75#[inline(always)]
76pub(crate) fn fft_skew_end(
77    engine: &impl Engine,
78    data: &mut ShardsRefMut,
79    pos: usize,
80    size: usize,
81    truncated_size: usize,
82) {
83    engine.fft(data, pos, size, truncated_size, pos + size);
84}
85
86/// IFFT with `skew_delta = pos + size`.
87#[inline(always)]
88pub(crate) fn ifft_skew_end(
89    engine: &impl Engine,
90    data: &mut ShardsRefMut,
91    pos: usize,
92    size: usize,
93    truncated_size: usize,
94) {
95    engine.ifft(data, pos, size, truncated_size, pos + size);
96}
97
98// Formal derivative.
99pub(crate) fn formal_derivative(data: &mut ShardsRefMut) {
100    for i in 1..data.len() {
101        let width: usize = 1 << i.trailing_zeros();
102        xor_within(data, i - width, i, width);
103    }
104}
reed_solomon_simd/engine/utils.rs

reed_solomon_simd/engine/
utils.rs
