libecc/rs/
mod.rs

1use super::{error::*, math::*, types::*, ByteUnitCode, Code, Decoded, Encoded};
2use futures::{
3  future::join_all,
4  stream::{self, StreamExt},
5};
6use tokio::task::{spawn_blocking, JoinError};
7
8#[derive(Debug, Clone)]
9pub struct ReedSolomon {
10  pub code_symbol_len: usize,             // n over GF(2^8)
11  pub info_symbol_len: usize,             // k over GF(2^8)
12  pub deviation_symbol_len: usize,        // deviation length over GF(2^8)
13  generator_matrix_parity: Matrix<GF256>, // parity part P of systematic generator matrix G = [I P] as a look-up table for encoding
14  precoding: Option<Matrix<GF256>>,       // precoding matrix for error_alignment
15  postcoding: Option<Matrix<GF256>>,      // postcoding matrix for error_alignment
16}
17
18impl ReedSolomon {
19  pub async fn new(code_symbol_len: usize, info_symbol_len: usize) -> Result<Self> {
20    ensure!(
21      code_symbol_len > info_symbol_len && code_symbol_len < ORDER && info_symbol_len < ORDER,
22      "Invalid params"
23    );
24
25    let res: Vec<_> = join_all(
26      stream::iter(0..info_symbol_len)
27        .map(|row| {
28          spawn_blocking(move || {
29            (0..code_symbol_len)
30              .map(|col| GF256(ROOT).pow((row * col) as isize))
31              .collect::<Vec<GF256>>()
32          })
33        })
34        .collect::<Vec<_>>()
35        .await,
36    )
37    .await;
38    let vandermonde_matrix = Matrix::new(
39      &res
40        .into_iter()
41        .collect::<Result<Vec<Vec<GF256>>, JoinError>>()?,
42    )?;
43
44    let inverse_matrix = vandermonde_matrix
45      .clone()
46      .inverse_left_submatrix(GF256(0), GF256(1))?;
47
48    // Systematic generator matrix for ease
49    let systematic_generator_matrix = inverse_matrix * vandermonde_matrix;
50    let parity_part = systematic_generator_matrix
51      .clone()
52      .column_submat(info_symbol_len, code_symbol_len)?;
53
54    Ok(ReedSolomon {
55      code_symbol_len,
56      info_symbol_len,
57      deviation_symbol_len: code_symbol_len - info_symbol_len, // redundancy length
58      generator_matrix_parity: parity_part,
59      precoding: None,
60      postcoding: None,
61    })
62  }
63
64  fn msg_encode_gf256_within(
65    &self,
66    message: &Vectorized<GF256>,
67    dev: &mut Vectorized<GF256>,
68  ) -> Result<()> {
69    let parity_gf256 = self
70      .generator_matrix_parity
71      .clone()
72      .mul_on_vec_from_right(message); //Matrix(vec![message.to_owned()]) * self.generator_matrix_parity.clone();
73
74    // Deviation is defined as the difference between error-free codeword and erroneous one at the redundancy part of the codeword.
75    dev.add_within(parity_gf256);
76
77    Ok(())
78  }
79}
80
81impl ByteUnitCode for ReedSolomon {
82  fn code_byte_len(&self) -> usize {
83    self.code_symbol_len
84  }
85  fn info_byte_len(&self) -> usize {
86    self.info_symbol_len
87  }
88  fn set_precoding(&mut self, pre: &[U8VRep]) -> Result<()> {
89    let mat = Matrix::of_gf256_from_u8(pre);
90    ensure!(mat.is_ok(), "Failed to set matrix");
91    self.precoding = Some(mat.unwrap());
92
93    let mat = self.precoding.as_ref().unwrap();
94    ensure!(mat.is_square(), "Matrix for error alignment must be square");
95    let inv = mat
96      .inverse_left_submatrix(GF256(0), GF256(1))
97      .map_err(|e| anyhow!("Singular matrix: {}", e))?;
98    self.postcoding = Some(inv);
99    // assert!((mat.clone() * inv.clone()).is_identity_matrix(GF256(0), GF256(1)));
100    Ok(())
101  }
102}
103impl Code for ReedSolomon {
104  type Slice = U8SRep;
105  type Vector = U8VRep;
106
107  fn decode(&self, data: &Self::Slice) -> Result<Decoded<Self::Vector>> {
108    ensure!(data.len() == self.code_symbol_len, "Invalid data length");
109    let mut precoded = Vectorized::of_gf256_from_u8(data);
110    if self.precoding.is_some() {
111      precoded = self
112        .precoding
113        .as_ref()
114        .unwrap()
115        .mul_on_vec_from_right(&precoded);
116    }
117
118    let (message_part, mut parity_part) = (
119      precoded.subvec(0, self.info_symbol_len),
120      precoded.subvec(self.info_symbol_len, self.code_symbol_len),
121    );
122
123    self.msg_encode_gf256_within(&message_part, &mut parity_part)?;
124
125    Ok(Decoded::<Self::Vector> {
126      base: message_part.to_u8_vec(),
127      deviation: parity_part.to_u8_vec(),
128    })
129  }
130
131  fn encode(&self, message: &Self::Slice, dev: &Self::Slice) -> Result<Encoded<Self::Vector>> {
132    ensure!(
133      message.len() == self.info_symbol_len,
134      "Invalid message length"
135    );
136    ensure!(
137      dev.len() == self.deviation_symbol_len,
138      "Invalid deviation length"
139    );
140    let (msg_gf256, mut dev_gf256) = (
141      Vectorized::of_gf256_from_u8(message),
142      Vectorized::of_gf256_from_u8(dev),
143    );
144    self.msg_encode_gf256_within(&msg_gf256, &mut dev_gf256)?;
145
146    let mut cw = msg_gf256.clone();
147    cw.extend_from_slice(&dev_gf256.0);
148
149    let postcoded = if self.postcoding.is_some() {
150      // TODO: More efficient precoding scheme
151      self.postcoding.as_ref().unwrap().mul_on_vec_from_right(&cw)
152    } else {
153      cw
154    };
155
156    Ok(Encoded::<Self::Vector>(postcoded.to_u8_vec()))
157  }
158}
159
160#[cfg(test)]
161mod tests {
162  use super::*;
163  use crate::HexDump;
164
165  const N: usize = 10;
166  const K: usize = 4;
167
168  #[tokio::test]
169  async fn decode_works() {
170    let rs = ReedSolomon::new(N, K).await.unwrap();
171    let message = (0u8..K as u8).map(|x| x).collect::<U8VRep>();
172    let dev = &[0u8; N - K];
173    let encoded = rs.encode(&message, dev).unwrap();
174    let decoded = rs.decode(&encoded.0).unwrap();
175
176    assert_eq!(message, decoded.base);
177    assert_eq!(dev.to_vec(), decoded.deviation);
178    assert_eq!(message.hexdump().unwrap(), decoded.base.hexdump().unwrap());
179    assert_eq!(
180      dev.as_slice().hexdump().unwrap(),
181      decoded.deviation.hexdump().unwrap()
182    );
183
184    let message = (0u8..K as u8).map(|x| x).collect::<U8VRep>();
185    let dev = (0u8..(N - K) as u8).rev().map(|x| x).collect::<U8VRep>();
186    let encoded = rs.encode(&message, &dev).unwrap();
187    let decoded = rs.decode(&encoded.0).unwrap();
188
189    assert_eq!(message, decoded.base);
190    assert_eq!(dev, decoded.deviation);
191    assert_eq!(message.hexdump().unwrap(), decoded.base.hexdump().unwrap());
192    assert_eq!(dev.hexdump().unwrap(), decoded.deviation.hexdump().unwrap())
193  }
194
195  #[tokio::test]
196  async fn encode_works() {
197    let rs = ReedSolomon::new(N, K).await.unwrap();
198    let message = &[0u8; K];
199    let dev = &[0u8; N - K];
200    let encoded = rs.encode(message, dev).unwrap();
201    assert_eq!(encoded.0, vec![0u8; N]);
202
203    let message = &[1u8; K];
204    let dev = &[1u8; N - K];
205    let encoded = rs.encode(message, dev).unwrap();
206    let ans_cw_parity = rs
207      .generator_matrix_parity
208      .0
209      .iter()
210      .fold(Vectorized(vec![GF256(0); N - K]), |acc, v| acc + v.clone())
211      .0
212      .iter()
213      .map(|gf| gf.0)
214      .collect::<U8VRep>();
215    let ans_err_parity: U8VRep = ans_cw_parity
216      .iter()
217      .enumerate()
218      .map(|(i, v)| *v ^ dev[i])
219      .collect();
220    let mut ans_cw = message.to_vec();
221    let mut ans_err = message.to_vec();
222    ans_cw.extend_from_slice(ans_cw_parity.as_slice());
223    ans_err.extend_from_slice(ans_err_parity.as_slice());
224    assert_eq!(encoded.0, ans_err);
225
226    let message = (0u8..K as u8).map(|x| x).collect::<U8VRep>();
227    let dev = &[0u8; N - K];
228    let encoded = rs.encode(&message, dev).unwrap();
229    let ans_cw_parity = rs
230      .generator_matrix_parity
231      .0
232      .iter()
233      .enumerate()
234      .fold(Vectorized(vec![GF256(0); N - K]), |acc, (row_idx, v)| {
235        acc + v.clone().mul_scalar(GF256(row_idx as u8))
236      })
237      .0
238      .iter()
239      .map(|gf| gf.0)
240      .collect::<U8VRep>();
241    let mut ans_cw = message.to_vec();
242    ans_cw.extend_from_slice(ans_cw_parity.as_slice());
243    assert_eq!(encoded.0, ans_cw);
244  }
245
246  #[tokio::test]
247  async fn new_works() {
248    let rs = ReedSolomon::new(N, K).await.unwrap();
249    // [
250    //  [GF256(1), GF256(1), GF256(1), GF256(1), GF256(1), GF256(1), GF256(1), GF256(1), GF256(1), GF256(1)],
251    //  [GF256(1), GF256(2), GF256(4), GF256(8), GF256(16), GF256(32), GF256(64), GF256(128), GF256(29), GF256(58)],
252    //  [GF256(1), GF256(4), GF256(16), GF256(64), GF256(29), GF256(116), GF256(205), GF256(19), GF256(76), GF256(45)],
253    //  [GF256(1), GF256(8), GF256(64), GF256(58), GF256(205), GF256(38), GF256(45), GF256(117), GF256(143), GF256(12)]
254    // ]
255    assert_eq!(
256      rs.generator_matrix_parity,
257      Matrix::new(&vec![
258        vec![
259          GF256(64),
260          GF256(231),
261          GF256(229),
262          GF256(158),
263          GF256(164),
264          GF256(178)
265        ],
266        vec![
267          GF256(120),
268          GF256(210),
269          GF256(191),
270          GF256(71),
271          GF256(219),
272          GF256(188)
273        ],
274        vec![
275          GF256(54),
276          GF256(87),
277          GF256(7),
278          GF256(140),
279          GF256(217),
280          GF256(213)
281        ],
282        vec![
283          GF256(15),
284          GF256(99),
285          GF256(92),
286          GF256(84),
287          GF256(167),
288          GF256(218)
289        ]
290      ])
291      .unwrap()
292    );
293  }
294}
libecc/rs/mod.rs

libecc/rs/
mod.rs
