commonware_cryptography/reed_solomon/engine/
engine_naive.rs

1use crate::reed_solomon::engine::{
2    tables::{self, Exp, Log, Skew},
3    utils, Engine, GfElement, ShardsRefMut, GF_MODULUS, SHARD_CHUNK_BYTES,
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 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::reed_solomon::engine::tables::LogWalsh
30    pub fn new() -> Self {
31        let exp_log = tables::get_exp_log();
32        let skew = tables::get_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        assert!(size.is_power_of_two());
52        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        assert!(size.is_power_of_two());
84        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; SHARD_CHUNK_BYTES]], log_m: GfElement) {
108        for chunk in x.iter_mut() {
109            for i in 0..SHARD_CHUNK_BYTES / 2 {
110                let lo = GfElement::from(chunk[i]);
111                let hi = GfElement::from(chunk[i + SHARD_CHUNK_BYTES / 2]);
112                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
113                chunk[i] = prod as u8;
114                chunk[i + SHARD_CHUNK_BYTES / 2] = (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(
135        &self,
136        x: &mut [[u8; SHARD_CHUNK_BYTES]],
137        y: &[[u8; SHARD_CHUNK_BYTES]],
138        log_m: GfElement,
139    ) {
140        assert_eq!(x.len(), y.len());
141
142        for (x_chunk, y_chunk) in core::iter::zip(x.iter_mut(), y.iter()) {
143            for i in 0..SHARD_CHUNK_BYTES / 2 {
144                let lo = GfElement::from(y_chunk[i]);
145                let hi = GfElement::from(y_chunk[i + SHARD_CHUNK_BYTES / 2]);
146                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
147                x_chunk[i] ^= prod as u8;
148                x_chunk[i + SHARD_CHUNK_BYTES / 2] ^= (prod >> 8) as u8;
149            }
150        }
151    }
152}
153
154// ======================================================================
155// TESTS
156
157// 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
