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/// Simple reference implementation of [`Engine`].
8///
9/// - [`Naive`] is meant for those who want to study
10///   the source code to understand [`Engine`].
11/// - [`Naive`] also includes some assertions
12///   which are not present in other implementations.
13#[derive(Clone, Copy)]
14pub struct Naive {
15    exp: &'static Exp,
16    log: &'static Log,
17    skew: &'static Skew,
18}
19
20impl Naive {
21    /// Creates a new [`Naive`] and initializes its multiplication and skew [tables].
22    ///
23    /// Decoding builds its Walsh transform tables on first use.
24    pub fn new() -> Self {
25        let exp_log = tables::get_exp_log();
26        let skew = tables::get_skew();
27
28        Self {
29            exp: &exp_log.exp,
30            log: &exp_log.log,
31            skew,
32        }
33    }
34}
35
36impl Engine for Naive {
37    fn fft(
38        &self,
39        data: &mut ShardsRefMut<'_>,
40        pos: usize,
41        size: usize,
42        truncated_size: usize,
43        skew_delta: usize,
44    ) {
45        super::validate_transform(data, pos, size, truncated_size, skew_delta);
46
47        let mut dist = size / 2;
48        while dist > 0 {
49            let mut r = 0;
50            while r < truncated_size {
51                let log_m = self.skew[r + dist + skew_delta - 1];
52                for i in r..r + dist {
53                    let (a, b) = data.dist2_mut(pos + i, dist);
54
55                    // FFT butterfly.
56                    if log_m != GF_MODULUS {
57                        self.mul_add(a, b, log_m);
58                    }
59                    utils::xor(b, a);
60                }
61                r += dist * 2;
62            }
63            dist /= 2;
64        }
65    }
66
67    fn ifft(
68        &self,
69        data: &mut ShardsRefMut<'_>,
70        pos: usize,
71        size: usize,
72        truncated_size: usize,
73        skew_delta: usize,
74    ) {
75        super::validate_transform(data, pos, size, truncated_size, skew_delta);
76
77        let mut dist = 1;
78        while dist < size {
79            let mut r = 0;
80            while r < truncated_size {
81                let log_m = self.skew[r + dist + skew_delta - 1];
82                for i in r..r + dist {
83                    let (a, b) = data.dist2_mut(pos + i, dist);
84
85                    // IFFT butterfly.
86                    utils::xor(b, a);
87                    if log_m != GF_MODULUS {
88                        self.mul_add(a, b, log_m);
89                    }
90                }
91                r += dist * 2;
92            }
93            dist *= 2;
94        }
95    }
96
97    fn mul(&self, x: &mut [[u8; SHARD_CHUNK_BYTES]], log_m: GfElement) {
98        for chunk in x.iter_mut() {
99            for i in 0..SHARD_CHUNK_BYTES / 2 {
100                let lo = GfElement::from(chunk[i]);
101                let hi = GfElement::from(chunk[i + SHARD_CHUNK_BYTES / 2]);
102                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
103                chunk[i] = prod as u8;
104                chunk[i + SHARD_CHUNK_BYTES / 2] = (prod >> 8) as u8;
105            }
106        }
107    }
108}
109
110impl Default for Naive {
111    fn default() -> Self {
112        Self::new()
113    }
114}
115
116impl Naive {
117    /// Computes `x ^= y * m` for each chunk, where `m` is the field element with logarithm
118    /// `log_m`.
119    ///
120    /// # Panics
121    ///
122    /// If `x` and `y` have different lengths.
123    fn mul_add(
124        &self,
125        x: &mut [[u8; SHARD_CHUNK_BYTES]],
126        y: &[[u8; SHARD_CHUNK_BYTES]],
127        log_m: GfElement,
128    ) {
129        assert_eq!(x.len(), y.len());
130
131        for (x_chunk, y_chunk) in core::iter::zip(x.iter_mut(), y.iter()) {
132            for i in 0..SHARD_CHUNK_BYTES / 2 {
133                let lo = GfElement::from(y_chunk[i]);
134                let hi = GfElement::from(y_chunk[i + SHARD_CHUNK_BYTES / 2]);
135                let prod = tables::mul(lo | (hi << 8), log_m, self.exp, self.log);
136                x_chunk[i] ^= prod as u8;
137                x_chunk[i + SHARD_CHUNK_BYTES / 2] ^= (prod >> 8) as u8;
138            }
139        }
140    }
141}
commonware_cryptography/reed_solomon/engine/engine_naive.rs

commonware_cryptography/reed_solomon/engine/
engine_naive.rs
