Botan  2.19.1
Crypto and TLS for C++11
zfec.cpp
Go to the documentation of this file.
1 /*
2 * Forward error correction based on Vandermonde matrices
3 *
4 * (C) 1997-1998 Luigi Rizzo (luigi@iet.unipi.it)
5 * (C) 2009,2010,2021 Jack Lloyd
6 * (C) 2011 Billy Brumley (billy.brumley@aalto.fi)
7 *
8 * Botan is released under the Simplified BSD License (see license.txt)
9 */
10 
11 #include <botan/zfec.h>
12 #include <botan/exceptn.h>
13 #include <botan/cpuid.h>
14 #include <botan/mem_ops.h>
15 #include <vector>
16 #include <cstring>
17 
18 namespace Botan {
19 
20 namespace {
21 
22 /* Tables for arithetic in GF(2^8) using 1+x^2+x^3+x^4+x^8
23 *
24 * See Lin & Costello, Appendix A, and Lee & Messerschmitt, p. 453.
25 *
26 * Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
27 * Lookup tables:
28 * index->polynomial form gf_exp[] contains j= \alpha^i;
29 * polynomial form -> index form gf_log[ j = \alpha^i ] = i
30 * \alpha=x is the primitive element of GF(2^m)
31 */
32 alignas(256) const uint8_t GF_EXP[255] = {
33  0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1D, 0x3A, 0x74,
34  0xE8, 0xCD, 0x87, 0x13, 0x26, 0x4C, 0x98, 0x2D, 0x5A, 0xB4, 0x75,
35  0xEA, 0xC9, 0x8F, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, 0x9D,
36  0x27, 0x4E, 0x9C, 0x25, 0x4A, 0x94, 0x35, 0x6A, 0xD4, 0xB5, 0x77,
37  0xEE, 0xC1, 0x9F, 0x23, 0x46, 0x8C, 0x05, 0x0A, 0x14, 0x28, 0x50,
38  0xA0, 0x5D, 0xBA, 0x69, 0xD2, 0xB9, 0x6F, 0xDE, 0xA1, 0x5F, 0xBE,
39  0x61, 0xC2, 0x99, 0x2F, 0x5E, 0xBC, 0x65, 0xCA, 0x89, 0x0F, 0x1E,
40  0x3C, 0x78, 0xF0, 0xFD, 0xE7, 0xD3, 0xBB, 0x6B, 0xD6, 0xB1, 0x7F,
41  0xFE, 0xE1, 0xDF, 0xA3, 0x5B, 0xB6, 0x71, 0xE2, 0xD9, 0xAF, 0x43,
42  0x86, 0x11, 0x22, 0x44, 0x88, 0x0D, 0x1A, 0x34, 0x68, 0xD0, 0xBD,
43  0x67, 0xCE, 0x81, 0x1F, 0x3E, 0x7C, 0xF8, 0xED, 0xC7, 0x93, 0x3B,
44  0x76, 0xEC, 0xC5, 0x97, 0x33, 0x66, 0xCC, 0x85, 0x17, 0x2E, 0x5C,
45  0xB8, 0x6D, 0xDA, 0xA9, 0x4F, 0x9E, 0x21, 0x42, 0x84, 0x15, 0x2A,
46  0x54, 0xA8, 0x4D, 0x9A, 0x29, 0x52, 0xA4, 0x55, 0xAA, 0x49, 0x92,
47  0x39, 0x72, 0xE4, 0xD5, 0xB7, 0x73, 0xE6, 0xD1, 0xBF, 0x63, 0xC6,
48  0x91, 0x3F, 0x7E, 0xFC, 0xE5, 0xD7, 0xB3, 0x7B, 0xF6, 0xF1, 0xFF,
49  0xE3, 0xDB, 0xAB, 0x4B, 0x96, 0x31, 0x62, 0xC4, 0x95, 0x37, 0x6E,
50  0xDC, 0xA5, 0x57, 0xAE, 0x41, 0x82, 0x19, 0x32, 0x64, 0xC8, 0x8D,
51  0x07, 0x0E, 0x1C, 0x38, 0x70, 0xE0, 0xDD, 0xA7, 0x53, 0xA6, 0x51,
52  0xA2, 0x59, 0xB2, 0x79, 0xF2, 0xF9, 0xEF, 0xC3, 0x9B, 0x2B, 0x56,
53  0xAC, 0x45, 0x8A, 0x09, 0x12, 0x24, 0x48, 0x90, 0x3D, 0x7A, 0xF4,
54  0xF5, 0xF7, 0xF3, 0xFB, 0xEB, 0xCB, 0x8B, 0x0B, 0x16, 0x2C, 0x58,
55  0xB0, 0x7D, 0xFA, 0xE9, 0xCF, 0x83, 0x1B, 0x36, 0x6C, 0xD8, 0xAD,
56  0x47, 0x8E,
57 };
58 
59 alignas(256) const uint8_t GF_LOG[256] = {
60  0xFF, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1A, 0xC6, 0x03, 0xDF, 0x33,
61  0xEE, 0x1B, 0x68, 0xC7, 0x4B, 0x04, 0x64, 0xE0, 0x0E, 0x34, 0x8D,
62  0xEF, 0x81, 0x1C, 0xC1, 0x69, 0xF8, 0xC8, 0x08, 0x4C, 0x71, 0x05,
63  0x8A, 0x65, 0x2F, 0xE1, 0x24, 0x0F, 0x21, 0x35, 0x93, 0x8E, 0xDA,
64  0xF0, 0x12, 0x82, 0x45, 0x1D, 0xB5, 0xC2, 0x7D, 0x6A, 0x27, 0xF9,
65  0xB9, 0xC9, 0x9A, 0x09, 0x78, 0x4D, 0xE4, 0x72, 0xA6, 0x06, 0xBF,
66  0x8B, 0x62, 0x66, 0xDD, 0x30, 0xFD, 0xE2, 0x98, 0x25, 0xB3, 0x10,
67  0x91, 0x22, 0x88, 0x36, 0xD0, 0x94, 0xCE, 0x8F, 0x96, 0xDB, 0xBD,
68  0xF1, 0xD2, 0x13, 0x5C, 0x83, 0x38, 0x46, 0x40, 0x1E, 0x42, 0xB6,
69  0xA3, 0xC3, 0x48, 0x7E, 0x6E, 0x6B, 0x3A, 0x28, 0x54, 0xFA, 0x85,
70  0xBA, 0x3D, 0xCA, 0x5E, 0x9B, 0x9F, 0x0A, 0x15, 0x79, 0x2B, 0x4E,
71  0xD4, 0xE5, 0xAC, 0x73, 0xF3, 0xA7, 0x57, 0x07, 0x70, 0xC0, 0xF7,
72  0x8C, 0x80, 0x63, 0x0D, 0x67, 0x4A, 0xDE, 0xED, 0x31, 0xC5, 0xFE,
73  0x18, 0xE3, 0xA5, 0x99, 0x77, 0x26, 0xB8, 0xB4, 0x7C, 0x11, 0x44,
74  0x92, 0xD9, 0x23, 0x20, 0x89, 0x2E, 0x37, 0x3F, 0xD1, 0x5B, 0x95,
75  0xBC, 0xCF, 0xCD, 0x90, 0x87, 0x97, 0xB2, 0xDC, 0xFC, 0xBE, 0x61,
76  0xF2, 0x56, 0xD3, 0xAB, 0x14, 0x2A, 0x5D, 0x9E, 0x84, 0x3C, 0x39,
77  0x53, 0x47, 0x6D, 0x41, 0xA2, 0x1F, 0x2D, 0x43, 0xD8, 0xB7, 0x7B,
78  0xA4, 0x76, 0xC4, 0x17, 0x49, 0xEC, 0x7F, 0x0C, 0x6F, 0xF6, 0x6C,
79  0xA1, 0x3B, 0x52, 0x29, 0x9D, 0x55, 0xAA, 0xFB, 0x60, 0x86, 0xB1,
80  0xBB, 0xCC, 0x3E, 0x5A, 0xCB, 0x59, 0x5F, 0xB0, 0x9C, 0xA9, 0xA0,
81  0x51, 0x0B, 0xF5, 0x16, 0xEB, 0x7A, 0x75, 0x2C, 0xD7, 0x4F, 0xAE,
82  0xD5, 0xE9, 0xE6, 0xE7, 0xAD, 0xE8, 0x74, 0xD6, 0xF4, 0xEA, 0xA8,
83  0x50, 0x58, 0xAF };
84 
85 alignas(256) const uint8_t GF_INVERSE[256] = {
86  0x00, 0x01, 0x8E, 0xF4, 0x47, 0xA7, 0x7A, 0xBA, 0xAD, 0x9D, 0xDD,
87  0x98, 0x3D, 0xAA, 0x5D, 0x96, 0xD8, 0x72, 0xC0, 0x58, 0xE0, 0x3E,
88  0x4C, 0x66, 0x90, 0xDE, 0x55, 0x80, 0xA0, 0x83, 0x4B, 0x2A, 0x6C,
89  0xED, 0x39, 0x51, 0x60, 0x56, 0x2C, 0x8A, 0x70, 0xD0, 0x1F, 0x4A,
90  0x26, 0x8B, 0x33, 0x6E, 0x48, 0x89, 0x6F, 0x2E, 0xA4, 0xC3, 0x40,
91  0x5E, 0x50, 0x22, 0xCF, 0xA9, 0xAB, 0x0C, 0x15, 0xE1, 0x36, 0x5F,
92  0xF8, 0xD5, 0x92, 0x4E, 0xA6, 0x04, 0x30, 0x88, 0x2B, 0x1E, 0x16,
93  0x67, 0x45, 0x93, 0x38, 0x23, 0x68, 0x8C, 0x81, 0x1A, 0x25, 0x61,
94  0x13, 0xC1, 0xCB, 0x63, 0x97, 0x0E, 0x37, 0x41, 0x24, 0x57, 0xCA,
95  0x5B, 0xB9, 0xC4, 0x17, 0x4D, 0x52, 0x8D, 0xEF, 0xB3, 0x20, 0xEC,
96  0x2F, 0x32, 0x28, 0xD1, 0x11, 0xD9, 0xE9, 0xFB, 0xDA, 0x79, 0xDB,
97  0x77, 0x06, 0xBB, 0x84, 0xCD, 0xFE, 0xFC, 0x1B, 0x54, 0xA1, 0x1D,
98  0x7C, 0xCC, 0xE4, 0xB0, 0x49, 0x31, 0x27, 0x2D, 0x53, 0x69, 0x02,
99  0xF5, 0x18, 0xDF, 0x44, 0x4F, 0x9B, 0xBC, 0x0F, 0x5C, 0x0B, 0xDC,
100  0xBD, 0x94, 0xAC, 0x09, 0xC7, 0xA2, 0x1C, 0x82, 0x9F, 0xC6, 0x34,
101  0xC2, 0x46, 0x05, 0xCE, 0x3B, 0x0D, 0x3C, 0x9C, 0x08, 0xBE, 0xB7,
102  0x87, 0xE5, 0xEE, 0x6B, 0xEB, 0xF2, 0xBF, 0xAF, 0xC5, 0x64, 0x07,
103  0x7B, 0x95, 0x9A, 0xAE, 0xB6, 0x12, 0x59, 0xA5, 0x35, 0x65, 0xB8,
104  0xA3, 0x9E, 0xD2, 0xF7, 0x62, 0x5A, 0x85, 0x7D, 0xA8, 0x3A, 0x29,
105  0x71, 0xC8, 0xF6, 0xF9, 0x43, 0xD7, 0xD6, 0x10, 0x73, 0x76, 0x78,
106  0x99, 0x0A, 0x19, 0x91, 0x14, 0x3F, 0xE6, 0xF0, 0x86, 0xB1, 0xE2,
107  0xF1, 0xFA, 0x74, 0xF3, 0xB4, 0x6D, 0x21, 0xB2, 0x6A, 0xE3, 0xE7,
108  0xB5, 0xEA, 0x03, 0x8F, 0xD3, 0xC9, 0x42, 0xD4, 0xE8, 0x75, 0x7F,
109  0xFF, 0x7E, 0xFD };
110 
111 const uint8_t* GF_MUL_TABLE(uint8_t y)
112  {
113  class GF_Table final
114  {
115  public:
116  GF_Table()
117  {
118  m_table.resize(256 * 256);
119 
120  // x*0 = 0*y = 0 so we iterate over [1,255)
121  for(size_t i = 1; i != 256; ++i)
122  {
123  for(size_t j = 1; j != 256; ++j)
124  {
125  m_table[256*i + j] = GF_EXP[(GF_LOG[i] + GF_LOG[j]) % 255];
126  }
127  }
128  }
129 
130  const uint8_t* ptr(uint8_t y) const
131  {
132  return &m_table[256*y];
133  }
134  private:
135  std::vector<uint8_t> m_table;
136  };
137 
138  static GF_Table table;
139  return table.ptr(y);
140  }
141 
142 /*
143 * invert_matrix() takes a K*K matrix and produces its inverse
144 * (Gauss-Jordan algorithm, adapted from Numerical Recipes in C)
145 */
146 void invert_matrix(uint8_t matrix[], size_t K)
147  {
148  class pivot_searcher
149  {
150  public:
151  pivot_searcher(size_t K) : m_ipiv(K) {}
152 
153  std::pair<size_t, size_t> operator()(size_t col, const uint8_t matrix[])
154  {
155  /*
156  * Zeroing column 'col', look for a non-zero element.
157  * First try on the diagonal, if it fails, look elsewhere.
158  */
159 
160  const size_t K = m_ipiv.size();
161 
162  if(m_ipiv[col] == false && matrix[col*K + col] != 0)
163  {
164  m_ipiv[col] = true;
165  return std::make_pair(col, col);
166  }
167 
168  for(size_t row = 0; row != K; ++row)
169  {
170  if(m_ipiv[row])
171  continue;
172 
173  for(size_t i = 0; i != K; ++i)
174  {
175  if(m_ipiv[i] == false && matrix[row*K + i] != 0)
176  {
177  m_ipiv[i] = true;
178  return std::make_pair(row, i);
179  }
180  }
181  }
182 
183  throw Invalid_Argument("ZFEC: pivot not found in invert_matrix");
184  }
185 
186  private:
187  // Marks elements already used as pivots
188  std::vector<bool> m_ipiv;
189  };
190 
191  pivot_searcher pivot_search(K);
192  std::vector<size_t> indxc(K);
193  std::vector<size_t> indxr(K);
194 
195  for(size_t col = 0; col != K; ++col)
196  {
197  const auto icolrow = pivot_search(col, matrix);
198 
199  const size_t icol = icolrow.first;
200  const size_t irow = icolrow.second;
201 
202  /*
203  * swap rows irow and icol, so afterwards the diagonal
204  * element will be correct. Rarely done, not worth
205  * optimizing.
206  */
207  if(irow != icol)
208  {
209  for(size_t i = 0; i != K; ++i)
210  std::swap(matrix[irow*K + i], matrix[icol*K + i]);
211  }
212 
213  indxr[col] = irow;
214  indxc[col] = icol;
215  uint8_t* pivot_row = &matrix[icol*K];
216  const uint8_t c = pivot_row[icol];
217  pivot_row[icol] = 1;
218 
219  if(c == 0)
220  throw Invalid_Argument("ZFEC: singlar matrix");
221 
222  if(c != 1)
223  {
224  const uint8_t* mul_c = GF_MUL_TABLE(GF_INVERSE[c]);
225  for(size_t i = 0; i != K; ++i)
226  pivot_row[i] = mul_c[pivot_row[i]];
227  }
228 
229  /*
230  * From all rows, remove multiples of the selected row to zero
231  * the relevant entry (in fact, the entry is not zero because we
232  * know it must be zero).
233  */
234  for(size_t i = 0; i != K; ++i)
235  {
236  if(i != icol)
237  {
238  const uint8_t z = matrix[i*K + icol];
239  matrix[i*K + icol] = 0;
240 
241  // This is equivalent to addmul()
242  const uint8_t* mul_z = GF_MUL_TABLE(z);
243  for(size_t j = 0; j != K; ++j)
244  matrix[i*K + j] ^= mul_z[pivot_row[j]];
245  }
246  }
247  }
248 
249  for(size_t i = 0; i != K; ++i)
250  {
251  if(indxr[i] != indxc[i])
252  {
253  for(size_t row = 0; row != K; ++row)
254  std::swap(matrix[row*K + indxr[i]], matrix[row*K + indxc[i]]);
255  }
256  }
257  }
258 
259 /*
260 * Generate and invert a Vandermonde matrix.
261 *
262 * Only uses the second column of the matrix, containing the p_i's
263 * (contents - 0, GF_EXP[0...n])
264 *
265 * Algorithm borrowed from "Numerical recipes in C", section 2.8, but
266 * largely revised for my purposes.
267 *
268 * p = coefficients of the matrix (p_i)
269 * q = values of the polynomial (known)
270 */
271 void create_inverted_vdm(uint8_t vdm[], size_t K)
272  {
273  if(K == 0)
274  {
275  return;
276  }
277 
278  if(K == 1) /* degenerate case, matrix must be p^0 = 1 */
279  {
280  vdm[0] = 1;
281  return;
282  }
283 
284  /*
285  * c holds the coefficient of P(x) = Prod (x - p_i), i=0..K-1
286  * b holds the coefficient for the matrix inversion
287  */
288  std::vector<uint8_t> b(K);
289  std::vector<uint8_t> c(K);
290 
291  /*
292  * construct coeffs. recursively. We know c[K] = 1 (implicit)
293  * and start P_0 = x - p_0, then at each stage multiply by
294  * x - p_i generating P_i = x P_{i-1} - p_i P_{i-1}
295  * After K steps we are done.
296  */
297  c[K-1] = 0; /* really -p(0), but x = -x in GF(2^m) */
298  for(size_t i = 1; i < K; ++i)
299  {
300  const uint8_t* mul_p_i = GF_MUL_TABLE(GF_EXP[i]);
301 
302  for(size_t j = K-1 - (i - 1); j < K-1; ++j)
303  c[j] ^= mul_p_i[c[j+1]];
304  c[K-1] ^= GF_EXP[i];
305  }
306 
307  for(size_t row = 0; row < K; ++row)
308  {
309  // synthetic division etc.
310  const uint8_t* mul_p_row = GF_MUL_TABLE(row == 0 ? 0 : GF_EXP[row]);
311 
312  uint8_t t = 1;
313  b[K-1] = 1; /* this is in fact c[K] */
314  for(size_t i = K - 1; i > 0; i--)
315  {
316  b[i-1] = c[i] ^ mul_p_row[b[i]];
317  t = b[i-1] ^ mul_p_row[t];
318  }
319 
320  const uint8_t* mul_t_inv = GF_MUL_TABLE(GF_INVERSE[t]);
321  for(size_t col = 0; col != K; ++col)
322  vdm[col*K + row] = mul_t_inv[b[col]];
323  }
324  }
325 
326 }
327 
328 /*
329 * addmul() computes z[] = z[] + x[] * y
330 */
331 void ZFEC::addmul(uint8_t z[], const uint8_t x[], uint8_t y, size_t size)
332  {
333  if(y == 0)
334  return;
335 
336  const uint8_t* GF_MUL_Y = GF_MUL_TABLE(y);
337 
338  // first align z to 16 bytes
339  while(size > 0 && reinterpret_cast<uintptr_t>(z) % 16)
340  {
341  z[0] ^= GF_MUL_Y[x[0]];
342  ++z;
343  ++x;
344  size--;
345  }
346 
347 #if defined(BOTAN_HAS_ZFEC_VPERM)
348  if(size >= 16 && CPUID::has_vperm())
349  {
350  const size_t consumed = addmul_vperm(z, x, y, size);
351  z += consumed;
352  x += consumed;
353  size -= consumed;
354  }
355 #endif
356 
357 #if defined(BOTAN_HAS_ZFEC_SSE2)
358  if(size >= 64 && CPUID::has_sse2())
359  {
360  const size_t consumed = addmul_sse2(z, x, y, size);
361  z += consumed;
362  x += consumed;
363  size -= consumed;
364  }
365 #endif
366 
367  while(size >= 16)
368  {
369  z[0] ^= GF_MUL_Y[x[0]];
370  z[1] ^= GF_MUL_Y[x[1]];
371  z[2] ^= GF_MUL_Y[x[2]];
372  z[3] ^= GF_MUL_Y[x[3]];
373  z[4] ^= GF_MUL_Y[x[4]];
374  z[5] ^= GF_MUL_Y[x[5]];
375  z[6] ^= GF_MUL_Y[x[6]];
376  z[7] ^= GF_MUL_Y[x[7]];
377  z[8] ^= GF_MUL_Y[x[8]];
378  z[9] ^= GF_MUL_Y[x[9]];
379  z[10] ^= GF_MUL_Y[x[10]];
380  z[11] ^= GF_MUL_Y[x[11]];
381  z[12] ^= GF_MUL_Y[x[12]];
382  z[13] ^= GF_MUL_Y[x[13]];
383  z[14] ^= GF_MUL_Y[x[14]];
384  z[15] ^= GF_MUL_Y[x[15]];
385 
386  x += 16;
387  z += 16;
388  size -= 16;
389  }
390 
391  // Clean up the trailing pieces
392  for(size_t i = 0; i != size; ++i)
393  z[i] ^= GF_MUL_Y[x[i]];
394  }
395 
396 /*
397 * This section contains the proper FEC encoding/decoding routines.
398 * The encoding matrix is computed starting with a Vandermonde matrix,
399 * and then transforming it into a systematic matrix.
400 */
401 
402 /*
403 * ZFEC constructor
404 */
405 ZFEC::ZFEC(size_t K, size_t N) :
406  m_K(K), m_N(N), m_enc_matrix(N * K)
407  {
408  if(m_K == 0 || m_N == 0 || m_K > 256 || m_N > 256 || m_K > N)
409  throw Invalid_Argument("ZFEC: violated 1 <= K <= N <= 256");
410 
411  std::vector<uint8_t> temp_matrix(m_N * m_K);
412 
413  /*
414  * quick code to build systematic matrix: invert the top
415  * K*K Vandermonde matrix, multiply right the bottom n-K rows
416  * by the inverse, and construct the identity matrix at the top.
417  */
418  create_inverted_vdm(&temp_matrix[0], m_K);
419 
420  for(size_t i = m_K*m_K; i != temp_matrix.size(); ++i)
421  temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
422 
423  /*
424  * the upper part of the encoding matrix is I
425  */
426  for(size_t i = 0; i != m_K; ++i)
427  m_enc_matrix[i*(m_K+1)] = 1;
428 
429  /*
430  * computes C = AB where A is n*K, B is K*m, C is n*m
431  */
432  for(size_t row = m_K; row != m_N; ++row)
433  {
434  for(size_t col = 0; col != m_K; ++col)
435  {
436  uint8_t acc = 0;
437  for(size_t i = 0; i != m_K; i++)
438  {
439  const uint8_t row_v = temp_matrix[row * m_K + i];
440  const uint8_t row_c = temp_matrix[col + m_K * i];
441  acc ^= GF_MUL_TABLE(row_v)[row_c];
442  }
443  m_enc_matrix[row * m_K + col] = acc;
444  }
445  }
446  }
447 
448 /*
449 * ZFEC encoding routine
450 */
452  const uint8_t input[], size_t size,
453  output_cb_t output_cb)
454  const
455  {
456  if(size % m_K != 0)
457  throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
458 
459  const size_t share_size = size / m_K;
460 
461  std::vector<const uint8_t*> shares;
462  for(size_t i = 0; i != m_K; ++i)
463  shares.push_back(input + i*share_size);
464 
465  this->encode_shares(shares, share_size, output_cb);
466  }
467 
469  const std::vector<const uint8_t*>& shares,
470  size_t share_size,
471  output_cb_t output_cb)
472  const
473  {
474  if(shares.size() != m_K)
475  throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
476 
477  // The initial shares are just the original input shares
478  for(size_t i = 0; i != m_K; ++i)
479  output_cb(i, shares[i], share_size);
480 
481  std::vector<uint8_t> fec_buf(share_size);
482 
483  for(size_t i = m_K; i != m_N; ++i)
484  {
485  clear_mem(fec_buf.data(), fec_buf.size());
486 
487  for(size_t j = 0; j != m_K; ++j)
488  {
489  addmul(&fec_buf[0], shares[j],
490  m_enc_matrix[i*m_K+j], share_size);
491  }
492 
493  output_cb(i, &fec_buf[0], fec_buf.size());
494  }
495  }
496 
497 /*
498 * ZFEC decoding routine
499 */
501  const std::map<size_t, const uint8_t*>& shares,
502  size_t share_size,
503  output_cb_t output_cb) const
504  {
505  /*
506  Todo:
507  If shares.size() < K:
508  signal decoding error for missing shares < K
509  emit existing shares < K
510  (ie, partial recovery if possible)
511  Assert share_size % K == 0
512  */
513 
514  if(shares.size() < m_K)
515  throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
516 
517  std::vector<uint8_t> decoding_matrix(m_K * m_K);
518  std::vector<size_t> indexes(m_K);
519  std::vector<const uint8_t*> sharesv(m_K);
520 
521  auto shares_b_iter = shares.begin();
522  auto shares_e_iter = shares.rbegin();
523 
524  bool missing_primary_share = false;
525 
526  for(size_t i = 0; i != m_K; ++i)
527  {
528  size_t share_id = 0;
529  const uint8_t* share_data = nullptr;
530 
531  if(shares_b_iter->first == i)
532  {
533  share_id = shares_b_iter->first;
534  share_data = shares_b_iter->second;
535  ++shares_b_iter;
536  }
537  else
538  {
539  // if share i not found, use the unused one closest to n
540  share_id = shares_e_iter->first;
541  share_data = shares_e_iter->second;
542  ++shares_e_iter;
543  missing_primary_share = true;
544  }
545 
546  if(share_id >= m_N)
547  throw Decoding_Error("ZFEC: invalid share id detected during decode");
548 
549  /*
550  This is a systematic code (encoding matrix includes K*K identity
551  matrix), so shares less than K are copies of the input data,
552  can output_cb directly. Also we know the encoding matrix in those rows
553  contains I, so we can set the single bit directly without copying
554  the entire row
555  */
556  if(share_id < m_K)
557  {
558  decoding_matrix[i*(m_K+1)] = 1;
559  output_cb(share_id, share_data, share_size);
560  }
561  else // will decode after inverting matrix
562  {
563  std::memcpy(&decoding_matrix[i*m_K], &m_enc_matrix[share_id*m_K], m_K);
564  }
565 
566  sharesv[i] = share_data;
567  indexes[i] = share_id;
568  }
569 
570  // If we had the original data shares then no need to perform
571  // a matrix inversion, return immediately.
572  if(!missing_primary_share)
573  {
574  for(size_t i = 0; i != indexes.size(); ++i)
575  {
576  BOTAN_ASSERT_NOMSG(indexes[i] < m_K);
577  }
578  return;
579  }
580 
581  invert_matrix(&decoding_matrix[0], m_K);
582 
583  for(size_t i = 0; i != indexes.size(); ++i)
584  {
585  if(indexes[i] >= m_K)
586  {
587  std::vector<uint8_t> buf(share_size);
588  for(size_t col = 0; col != m_K; ++col)
589  {
590  addmul(&buf[0], sharesv[col], decoding_matrix[i*m_K + col], share_size);
591  }
592  output_cb(i, &buf[0], share_size);
593  }
594  }
595  }
596 
597 std::string ZFEC::provider() const
598  {
599 #if defined(BOTAN_HAS_ZFEC_VPERM)
600  if(CPUID::has_vperm())
601  {
602  return "vperm";
603  }
604 #endif
605 
606 #if defined(BOTAN_HAS_ZFEC_SSE2)
607  if(CPUID::has_sse2())
608  {
609  return "sse2";
610  }
611 #endif
612 
613  return "base";
614  }
615 
616 }
std::string provider() const
Definition: zfec.cpp:597
void clear_mem(T *ptr, size_t n)
Definition: mem_ops.h:115
int(* final)(unsigned char *, CTX *)
void decode_shares(const std::map< size_t, const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
Definition: zfec.cpp:500
#define BOTAN_ASSERT_NOMSG(expr)
Definition: assert.h:68
std::function< void(size_t, const uint8_t[], size_t)> output_cb_t
Definition: zfec.h:33
Definition: alg_id.cpp:13
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
Definition: zfec.cpp:468
static bool has_vperm()
Definition: cpuid.h:362
void encode(const uint8_t input[], size_t size, output_cb_t output_cb) const
Definition: zfec.cpp:451
ZFEC(size_t K, size_t n)
Definition: zfec.cpp:405