Botan 2.19.3
Crypto and TLS for C&
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
18namespace Botan {
19
20namespace {
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*/
32alignas(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
59alignas(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
85alignas(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
111const 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*/
146void 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*/
271void 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*/
331void 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*/
405ZFEC::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
597std::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}
#define BOTAN_ASSERT_NOMSG(expr)
Definition assert.h:68
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
std::string provider() const
Definition zfec.cpp:597
ZFEC(size_t K, size_t N)
Definition zfec.cpp:405
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
std::function< void(size_t, const uint8_t[], size_t)> output_cb_t
Definition zfec.h:33
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
Definition zfec.cpp:468
int(* final)(unsigned char *, CTX *)
void clear_mem(T *ptr, size_t n)
Definition mem_ops.h:115