commonware_cryptography/reed_solomon/engine/
engine_naive.rs

1use crate::reed_solomon::engine::{
2    Engine, GF_MODULUS, GfElement, SHARD_CHUNK_BYTES, ShardsRefMut,
3    tables::{self, Exp, Log, Skew},
4    utils,
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 assertions
15///   which are not present in other implementations.
16#[derive(Clone, Copy)]
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    /// [`LogWalsh`] (128 kiB) which is only needed for decoding.
29    ///
30    /// [`LogWalsh`]: crate::reed_solomon::engine::tables::LogWalsh
31    pub fn new() -> Self {
32        let exp_log = tables::get_exp_log();
33        let skew = tables::get_skew();
34
35        Self {
36            exp: &exp_log.exp,
37            log: &exp_log.log,
38            skew,
39        }
40    }
41}
42
43impl Engine for Naive {
44    fn fft(
45        &self,
46        data: &mut ShardsRefMut<'_>,
47        pos: usize,
48        size: usize,
49        truncated_size: usize,
50        skew_delta: usize,
51    ) {
52        assert!(size.is_power_of_two());
53        assert!(truncated_size <= size);
54
55        let mut dist = size / 2;
56        while dist > 0 {
57            let mut r = 0;
58            while r < truncated_size {
59                let log_m = self.skew[r + dist + skew_delta - 1];
60                for i in r..r + dist {
61                    let (a, b) = data.dist2_mut(pos + i, dist);
62
63                    // FFT BUTTERFLY
64
65                    if log_m != GF_MODULUS {
66                        self.mul_add(a, b, log_m);
67                    }
68                    utils::xor(b, a);
69                }
70                r += dist * 2;
71            }
72            dist /= 2;
73        }
74    }
75
76    fn ifft(
77        &self,
78        data: &mut ShardsRefMut<'_>,
79        pos: usize,
80        size: usize,
81        truncated_size: usize,
82        skew_delta: usize,
83    ) {
84        assert!(size.is_power_of_two());
85        assert!(truncated_size <= size);
86
87        let mut dist = 1;
88        while dist < size {
89            let mut r = 0;
90            while r < truncated_size {
91                let log_m = self.skew[r + dist + skew_delta - 1];
92                for i in r..r + dist {
93                    let (a, b) = data.dist2_mut(pos + i, dist);
94
95                    // IFFT BUTTERFLY
96
97                    utils::xor(b, a);
98                    if log_m != GF_MODULUS {
99                        self.mul_add(a, b, log_m);
100                    }
101                }
102                r += dist * 2;
103            }
104            dist *= 2;
105        }
106    }
107
108    fn mul(&self, x: &mut [[u8; SHARD_CHUNK_BYTES]], log_m: GfElement) {
109        for chunk in x.iter_mut() {
110            for i in 0..SHARD_CHUNK_BYTES / 2 {
111                let lo = GfElement::from(chunk[i]);
112                let hi = GfElement::from(chunk[i + SHARD_CHUNK_BYTES / 2]);
113                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
114                chunk[i] = prod as u8;
115                chunk[i + SHARD_CHUNK_BYTES / 2] = (prod >> 8) as u8;
116            }
117        }
118    }
119}
120
121// ======================================================================
122// Naive - IMPL Default
123
124impl Default for Naive {
125    fn default() -> Self {
126        Self::new()
127    }
128}
129
130// ======================================================================
131// Naive - PRIVATE
132
133impl Naive {
134    /// `x[] ^= y[] * log_m`
135    fn mul_add(
136        &self,
137        x: &mut [[u8; SHARD_CHUNK_BYTES]],
138        y: &[[u8; SHARD_CHUNK_BYTES]],
139        log_m: GfElement,
140    ) {
141        assert_eq!(x.len(), y.len());
142
143        for (x_chunk, y_chunk) in core::iter::zip(x.iter_mut(), y.iter()) {
144            for i in 0..SHARD_CHUNK_BYTES / 2 {
145                let lo = GfElement::from(y_chunk[i]);
146                let hi = GfElement::from(y_chunk[i + SHARD_CHUNK_BYTES / 2]);
147                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
148                x_chunk[i] ^= prod as u8;
149                x_chunk[i + SHARD_CHUNK_BYTES / 2] ^= (prod >> 8) as u8;
150            }
151        }
152    }
153}
154
155// ======================================================================
156// TESTS
157
158// Engines are tested indirectly via roundtrip tests of HighRate and LowRate.
commonware_cryptography/reed_solomon/engine/engine_naive.rs

commonware_cryptography/reed_solomon/engine/
engine_naive.rs
