reed_solomon_16/engine/
engine_naive.rs1use crate::engine::{
2 self,
3 tables::{self, Exp, Log, Skew},
4 Engine, GfElement, ShardsRefMut, GF_MODULUS, GF_ORDER,
5};
6
7#[derive(Clone)]
17pub struct Naive {
18 exp: &'static Exp,
19 log: &'static Log,
20 skew: &'static Skew,
21}
22
23impl Naive {
24 pub fn new() -> Self {
30 let (exp, log) = tables::initialize_exp_log();
31 let skew = tables::initialize_skew();
32
33 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 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 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
152impl Default for Naive {
156 fn default() -> Self {
157 Self::new()
158 }
159}
160
161impl Naive {
165 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