code.octet-stream.net Git - m17rt/blob - m17core/src/fec.rs

   1 use crate::bits::{Bits, BitsMut};
   2 use log::debug;
   3
   4 struct Transition {
   5     input: u8,
   6     output: [u8; 2],
   7     source: usize,
   8 }
   9
  10 static TRANSITIONS: [Transition; 32] = [
  11     Transition {
  12         input: 0,
  13         output: [0, 0],
  14         source: 0,
  15     },
  16     Transition {
  17         input: 0,
  18         output: [1, 1],
  19         source: 1,
  20     },
  21     Transition {
  22         input: 0,
  23         output: [1, 0],
  24         source: 2,
  25     },
  26     Transition {
  27         input: 0,
  28         output: [0, 1],
  29         source: 3,
  30     },
  31     Transition {
  32         input: 0,
  33         output: [0, 1],
  34         source: 4,
  35     },
  36     Transition {
  37         input: 0,
  38         output: [1, 0],
  39         source: 5,
  40     },
  41     Transition {
  42         input: 0,
  43         output: [1, 1],
  44         source: 6,
  45     },
  46     Transition {
  47         input: 0,
  48         output: [0, 0],
  49         source: 7,
  50     },
  51     Transition {
  52         input: 0,
  53         output: [0, 1],
  54         source: 8,
  55     },
  56     Transition {
  57         input: 0,
  58         output: [1, 0],
  59         source: 9,
  60     },
  61     Transition {
  62         input: 0,
  63         output: [1, 1],
  64         source: 10,
  65     },
  66     Transition {
  67         input: 0,
  68         output: [0, 0],
  69         source: 11,
  70     },
  71     Transition {
  72         input: 0,
  73         output: [0, 0],
  74         source: 12,
  75     },
  76     Transition {
  77         input: 0,
  78         output: [1, 1],
  79         source: 13,
  80     },
  81     Transition {
  82         input: 0,
  83         output: [1, 0],
  84         source: 14,
  85     },
  86     Transition {
  87         input: 0,
  88         output: [0, 1],
  89         source: 15,
  90     },
  91     Transition {
  92         input: 1,
  93         output: [1, 1],
  94         source: 0,
  95     },
  96     Transition {
  97         input: 1,
  98         output: [0, 0],
  99         source: 1,
 100     },
 101     Transition {
 102         input: 1,
 103         output: [0, 1],
 104         source: 2,
 105     },
 106     Transition {
 107         input: 1,
 108         output: [1, 0],
 109         source: 3,
 110     },
 111     Transition {
 112         input: 1,
 113         output: [1, 0],
 114         source: 4,
 115     },
 116     Transition {
 117         input: 1,
 118         output: [0, 1],
 119         source: 5,
 120     },
 121     Transition {
 122         input: 1,
 123         output: [0, 0],
 124         source: 6,
 125     },
 126     Transition {
 127         input: 1,
 128         output: [1, 1],
 129         source: 7,
 130     },
 131     Transition {
 132         input: 1,
 133         output: [1, 0],
 134         source: 8,
 135     },
 136     Transition {
 137         input: 1,
 138         output: [0, 1],
 139         source: 9,
 140     },
 141     Transition {
 142         input: 1,
 143         output: [0, 0],
 144         source: 10,
 145     },
 146     Transition {
 147         input: 1,
 148         output: [1, 1],
 149         source: 11,
 150     },
 151     Transition {
 152         input: 1,
 153         output: [1, 1],
 154         source: 12,
 155     },
 156     Transition {
 157         input: 1,
 158         output: [0, 0],
 159         source: 13,
 160     },
 161     Transition {
 162         input: 1,
 163         output: [0, 1],
 164         source: 14,
 165     },
 166     Transition {
 167         input: 1,
 168         output: [1, 0],
 169         source: 15,
 170     },
 171 ];
 172
 173 pub(crate) fn p_1(step: usize) -> (bool, bool) {
 174     let mod61 = step % 61;
 175     let is_even = mod61 % 2 == 0;
 176     (mod61 > 30 || is_even, mod61 < 30 || is_even)
 177 }
 178
 179 pub(crate) fn p_2(step: usize) -> (bool, bool) {
 180     let mod6 = step % 6;
 181     (true, mod6 != 5)
 182 }
 183
 184 pub(crate) fn p_3(step: usize) -> (bool, bool) {
 185     let mod4 = step % 4;
 186     (true, mod4 != 3)
 187 }
 188
 189 fn best_previous(table: &[[u8; 32]; 244], step: usize, state: usize) -> u8 {
 190     if step == 0 {
 191         if state == 0 {
 192             return 0;
 193         } else {
 194             return u8::MAX;
 195         }
 196     }
 197     let prev1 = table[step - 1][state * 2];
 198     let prev2 = table[step - 1][state * 2 + 1];
 199     prev1.min(prev2)
 200 }
 201
 202 fn hamming_distance(first: &[u8], second: &[u8]) -> u8 {
 203     first
 204         .iter()
 205         .zip(second.iter())
 206         .map(|(x, y)| if *x == *y { 0 } else { 1 })
 207         .sum()
 208 }
 209
 210 // maximum 368 type 3 bits, maximum 240 type 1 bits, 4 flush bits
 211 pub(crate) fn decode(
 212     type3: &[u8], // up to len 46
 213     input_len: usize,
 214     puncture: fn(usize) -> (bool, bool),
 215 ) -> Option<[u8; 30]> {
 216     let type3_bits = Bits::new(type3);
 217     let mut type3_iter = type3_bits.iter();
 218     let mut table = [[0u8; 32]; 244];
 219     for step in 0..(input_len + 4) {
 220         let (use_g1, use_g2) = puncture(step);
 221         let split_idx = if use_g1 && use_g2 { 2 } else { 1 };
 222         let mut input_bits = [0u8; 2];
 223         input_bits[0] = type3_iter.next().unwrap();
 224         let step_input = if split_idx == 1 {
 225             &input_bits[0..1]
 226         } else {
 227             input_bits[1] = type3_iter.next().unwrap();
 228             &input_bits[0..2]
 229         };
 230         for (t_idx, t) in TRANSITIONS.iter().enumerate() {
 231             let t_offer = if use_g1 && use_g2 {
 232                 &t.output[..]
 233             } else if use_g1 {
 234                 &t.output[0..1]
 235             } else {
 236                 &t.output[1..2]
 237             };
 238             let step_dist = hamming_distance(step_input, t_offer);
 239             table[step][t_idx] = best_previous(&table, step, t.source).saturating_add(step_dist);
 240         }
 241     }
 242     let (mut best_idx, best) = table[input_len + 3]
 243         .iter()
 244         .enumerate()
 245         .min_by_key(|(_, i)| *i)
 246         .unwrap();
 247     debug!("Best score is {best}, transition {best_idx}");
 248     if *best > 6 {
 249         None
 250     } else {
 251         let mut out = [0u8; 30];
 252         let mut out_bits = BitsMut::new(&mut out);
 253         for step in (0..(input_len + 4)).rev() {
 254             let input = TRANSITIONS[best_idx].input;
 255             if step < input_len {
 256                 out_bits.set_bit(step, input);
 257             }
 258             if step > 0 {
 259                 let state = TRANSITIONS[best_idx].source;
 260                 let prev1 = table[step - 1][state * 2];
 261                 let prev2 = table[step - 1][state * 2 + 1];
 262                 best_idx = if prev1 < prev2 {
 263                     state * 2
 264                 } else {
 265                     state * 2 + 1
 266                 };
 267             }
 268         }
 269         Some(out)
 270     }
 271 }
 272
 273 /// Perform convolutional encoding on payload.
 274 ///
 275 /// Four flush bits will be appended automatically.
 276 ///
 277 /// Parameters:
 278 /// * `type1`: Type 1 bits, maximum length 30 bytes
 279 /// * `input_len`: Number of type 1 bits, up to 240
 280 /// * `puncture`: Puncturing scheme - `p_1`, `p_2` or `p_3`
 281 ///
 282 /// Returns up to 368 type 3 bits. Caller is responsible for knowing the number of
 283 /// filled bits in the returned array, which is known statically by the type of
 284 /// payload and puncturing scheme in use.
 285 pub(crate) fn encode(
 286     type1: &[u8],
 287     input_len: usize,
 288     puncture: fn(usize) -> (bool, bool),
 289 ) -> [u8; 46] {
 290     let mut out = [0u8; 46];
 291     let bits = Bits::new(type1);
 292     let mut out_idx = 0;
 293     let mut out_bits = BitsMut::new(&mut out);
 294     let mut state: u8 = 0;
 295     for (t1_idx, b) in bits
 296         .iter()
 297         .take(input_len)
 298         .chain(core::iter::repeat_n(0, 4))
 299         .enumerate()
 300     {
 301         let (use_g1, use_g2) = puncture(t1_idx);
 302         if use_g1 {
 303             let g1 = (b + ((state & 0x02) >> 1) + (state & 0x01)) & 0x01;
 304             out_bits.set_bit(out_idx, g1);
 305             out_idx += 1;
 306         }
 307         if use_g2 {
 308             let g2 = (b + ((state & 0x08) >> 3) + ((state & 0x04) >> 2) + (state & 0x01)) & 0x01;
 309             out_bits.set_bit(out_idx, g2);
 310             out_idx += 1;
 311         }
 312         state = (state >> 1) | (b << 3);
 313     }
 314     out
 315 }
 316
 317 #[cfg(test)]
 318 mod tests {
 319     use super::*;
 320
 321     #[test]
 322     fn lsf_fec_round_trip() {
 323         let lsf = [
 324             255, 255, 255, 255, 255, 255, 0, 0, 0, 159, 221, 81, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 325             0, 0, 0, 0, 0, 131, 53,
 326         ];
 327         let expected_encoded = [
 328             222, 73, 36, 146, 73, 37, 182, 219, 109, 76, 0, 0, 0, 5, 191, 47, 25, 186, 30, 214,
 329             237, 110, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 42, 153, 208,
 330             119,
 331         ];
 332         let encoded = encode(&lsf, 240, p_1);
 333         assert_eq!(encoded, expected_encoded);
 334         let decoded = decode(&encoded, 240, p_1);
 335         assert_eq!(decoded, Some(lsf));
 336     }
 337
 338     #[test]
 339     fn fec_damage() {
 340         let lsf = [
 341             255, 255, 255, 255, 255, 255, 0, 0, 0, 159, 221, 81, 5, 5, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 342             0, 0, 0, 0, 0, 131, 53,
 343         ];
 344         let mut encoded = encode(&lsf, 240, p_1);
 345
 346         // progressively flip more bits
 347         for idx in [50, 90, 51, 200, 15, 7, 100] {
 348             let mut bits = BitsMut::new(&mut encoded);
 349             let bit = bits.get_bit(idx);
 350             bits.set_bit(idx, if bit == 1 { 0 } else { 1 });
 351             let decoded = decode(&encoded, 240, p_1);
 352             if idx == 100 {
 353                 assert_eq!(decoded, None); // 7 bits is too much damage
 354             } else {
 355                 assert_eq!(decoded, Some(lsf)); // recovered from errors
 356             }
 357         }
 358     }
 359 }