commonware_cryptography/reed_solomon/engine/
utils.rs

1//! A collection of utility functions and helpers to facilitate the implementation of the [`Engine`] trait.
2//!
3//! [`Engine`]: crate::reed_solomon::engine::Engine
4
5use crate::reed_solomon::engine::{
6    fwht, tables, Engine, GfElement, ShardsRefMut, GF_BITS, GF_ORDER, SHARD_CHUNK_BYTES,
7};
8use core::iter::zip;
9
10// ======================================================================
11// FUNCTIONS - PUBLIC
12
13/// Evaluate Polynomial using Fast Walsh-Hadamard Transform (FWHT).
14///
15/// This function is designed to be inlined and be compiled with SIMD
16/// features enabled within an Engine's implementation of `eval_poly`.
17///
18/// See `Avx2` for an example on how to do this.
19#[inline(always)]
20pub fn eval_poly(erasures: &mut [GfElement; GF_ORDER], truncated_size: usize) {
21    let log_walsh = tables::get_log_walsh();
22
23    fwht::fwht(erasures, truncated_size);
24
25    for (e, factor) in 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; SHARD_CHUNK_BYTES]], ys: &[[u8; SHARD_CHUNK_BYTES]]) {
36    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}
commonware_cryptography/reed_solomon/engine/utils.rs

commonware_cryptography/reed_solomon/engine/
utils.rs
