1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
use alloc::vec;
use alloc::vec::Vec;
use crate::common;
/// Sparce Matrix
///
/// Original implementation
/// https://github.com/google/gofountain/blob/master/block.go
///
/// A^block = intermediate
pub struct SparseMatrix {
/// Indices of the source blocks which are xor-ed together
/// | 0 0 1 1 | [[ 2, 3],
/// | 0 1 0 1 | [ 1, 3 ],
/// | 1 1 1 0 | -> coeff [ 0, 1, 2],
/// | 1 0 0 0 | [ 0 ] ]
pub coeff: Vec<Vec<u32>>,
/// Intermediate symbols
pub intermediate: Vec<Vec<u8>>,
}
impl SparseMatrix {
pub fn new(l: usize) -> Self {
SparseMatrix {
coeff: vec![Vec::new(); l],
intermediate: vec![Vec::new(); l],
}
}
/// On the fly Gaussian Elimination (OFG)
///
/// Add an XOR equation to the sparse matrix
///
/// # Arguments
///
/// * `components` - A vector of u32 numbers representing the indices of the
/// source blocks
/// * `b` - A vector of u8 numbers representing the intermediate symbols
///
/// variant of Valerio Bioglio, Marco Grangetto algorithm,
/// On the fly Gaussian Elimination for LT codes, 2009
///
/// OFG builds a triangular matrix G by exploiting every received packet
/// starting from the very first one.
///
/// Spreads decoding complexity during packets reception
pub fn add_equation(&mut self, components: Vec<u32>, b: Vec<u8>) {
let mut components = components;
let mut b = b;
// while EqOnes > 0 and G[s][s] = 1 do
while components.len() > 0 && self.coeff[components[0] as usize].len() > 0 {
// s <- LeftmostOne
let s = components[0];
// if EqOnes ≥ NumOnes[s] then
if components.len() >= self.coeff[s as usize].len() {
// NewEq <- NewEq ^ G[s]
common::symmetric_difference(&mut components, &self.coeff[s as usize]);
// NewY <- NewY ^ Y [s]
common::xor(&mut b, &self.intermediate[s as usize]);
} else {
// Swap matrix row with the new row
core::mem::swap(&mut self.coeff[s as usize], &mut components);
core::mem::swap(&mut self.intermediate[s as usize], &mut b);
}
}
// if EqOnes > 0 then
if components.len() > 0 {
let s = components[0] as usize;
// G[s] <- NewEq
self.coeff[s] = components;
// Y [s] <- NewY
self.intermediate[s] = b;
}
}
/// Check is the decode matrix is fully specified
pub fn fully_specified(&self) -> bool {
self.coeff.iter().find(|coeff| coeff.is_empty()).is_none()
}
/// Gaussian Elimination.
/// Algo from from gofountain project
/// https://github.com/google/gofountain
pub fn reduce(&mut self) {
// Build reverse index: coefficient value -> rows containing it
let l = self.coeff.len();
let mut reverse_index: Vec<Vec<usize>> = vec![Vec::new(); l];
for (j, row) in self.coeff.iter().enumerate() {
for &k in row {
reverse_index[k as usize].push(j);
}
}
for i in (0..l).rev() {
let first_coeff_i = self.coeff[i][0];
let (inter_j, inter_i) = self.intermediate.split_at_mut(i);
for &j in &reverse_index[first_coeff_i as usize] {
if j < i {
common::xor(&mut inter_j[j], &inter_i[0]);
}
}
self.coeff[i].resize(1, 0);
}
}
}