reed_solomon_16/engine/
engine_naive.rs

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

reed_solomon_16/engine/
engine_naive.rs
