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