reed_solomon_simd/engine/
engine_naive.rs

1use crate::engine::{
2    tables::{self, Exp, Log, Skew},
3    utils, Engine, GfElement, ShardsRefMut, GF_MODULUS,
4};
5
6// ======================================================================
7// Naive - PUBLIC
8
9/// Simple reference implementation of [`Engine`].
10///
11/// - [`Naive`] is meant for those who want to study
12///   the source code to understand [`Engine`].
13/// - [`Naive`] also includes some debug assertions
14///   which are not present in other implementations.
15#[derive(Clone, Copy)]
16pub struct Naive {
17    exp: &'static Exp,
18    log: &'static Log,
19    skew: &'static Skew,
20}
21
22impl Naive {
23    /// Creates new [`Naive`], initializing all [tables]
24    /// needed for encoding or decoding.
25    ///
26    /// Currently only difference between encoding/decoding is
27    /// [`LogWalsh`] (128 kiB) which is only needed for decoding.
28    ///
29    /// [`LogWalsh`]: crate::engine::tables::LogWalsh
30    pub fn new() -> Self {
31        let exp_log = &*tables::EXP_LOG;
32        let skew = &*tables::SKEW;
33
34        Self {
35            exp: &exp_log.exp,
36            log: &exp_log.log,
37            skew,
38        }
39    }
40}
41
42impl Engine for Naive {
43    fn fft(
44        &self,
45        data: &mut ShardsRefMut,
46        pos: usize,
47        size: usize,
48        truncated_size: usize,
49        skew_delta: usize,
50    ) {
51        debug_assert!(size.is_power_of_two());
52        debug_assert!(truncated_size <= size);
53
54        let mut dist = size / 2;
55        while dist > 0 {
56            let mut r = 0;
57            while r < truncated_size {
58                let log_m = self.skew[r + dist + skew_delta - 1];
59                for i in r..r + dist {
60                    let (a, b) = data.dist2_mut(pos + i, dist);
61
62                    // FFT BUTTERFLY
63
64                    if log_m != GF_MODULUS {
65                        self.mul_add(a, b, log_m);
66                    }
67                    utils::xor(b, a);
68                }
69                r += dist * 2;
70            }
71            dist /= 2;
72        }
73    }
74
75    fn ifft(
76        &self,
77        data: &mut ShardsRefMut,
78        pos: usize,
79        size: usize,
80        truncated_size: usize,
81        skew_delta: usize,
82    ) {
83        debug_assert!(size.is_power_of_two());
84        debug_assert!(truncated_size <= size);
85
86        let mut dist = 1;
87        while dist < size {
88            let mut r = 0;
89            while r < truncated_size {
90                let log_m = self.skew[r + dist + skew_delta - 1];
91                for i in r..r + dist {
92                    let (a, b) = data.dist2_mut(pos + i, dist);
93
94                    // IFFT BUTTERFLY
95
96                    utils::xor(b, a);
97                    if log_m != GF_MODULUS {
98                        self.mul_add(a, b, log_m);
99                    }
100                }
101                r += dist * 2;
102            }
103            dist *= 2;
104        }
105    }
106
107    fn mul(&self, x: &mut [[u8; 64]], log_m: GfElement) {
108        for chunk in x.iter_mut() {
109            for i in 0..32 {
110                let lo = GfElement::from(chunk[i]);
111                let hi = GfElement::from(chunk[i + 32]);
112                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
113                chunk[i] = prod as u8;
114                chunk[i + 32] = (prod >> 8) as u8;
115            }
116        }
117    }
118}
119
120// ======================================================================
121// Naive - IMPL Default
122
123impl Default for Naive {
124    fn default() -> Self {
125        Self::new()
126    }
127}
128
129// ======================================================================
130// Naive - PRIVATE
131
132impl Naive {
133    /// `x[] ^= y[] * log_m`
134    fn mul_add(&self, x: &mut [[u8; 64]], y: &[[u8; 64]], log_m: GfElement) {
135        debug_assert_eq!(x.len(), y.len());
136
137        for (x_chunk, y_chunk) in std::iter::zip(x.iter_mut(), y.iter()) {
138            for i in 0..32 {
139                let lo = GfElement::from(y_chunk[i]);
140                let hi = GfElement::from(y_chunk[i + 32]);
141                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
142                x_chunk[i] ^= prod as u8;
143                x_chunk[i + 32] ^= (prod >> 8) as u8;
144            }
145        }
146    }
147}
148
149// ======================================================================
150// TESTS
151
152// Engines are tested indirectly via roundtrip tests of HighRate and LowRate.
reed_solomon_simd/engine/engine_naive.rs

reed_solomon_simd/engine/
engine_naive.rs
