11#include <botan/zfec.h>
12#include <botan/exceptn.h>
13#include <botan/cpuid.h>
14#include <botan/mem_ops.h>
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,
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,
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,
111const uint8_t* GF_MUL_TABLE(uint8_t y)
118 m_table.resize(256 * 256);
121 for(
size_t i = 1; i != 256; ++i)
123 for(
size_t j = 1; j != 256; ++j)
125 m_table[256*i + j] = GF_EXP[(GF_LOG[i] + GF_LOG[j]) % 255];
130 const uint8_t* ptr(uint8_t y)
const
132 return &m_table[256*y];
135 std::vector<uint8_t> m_table;
138 static GF_Table table;
146void invert_matrix(uint8_t matrix[],
size_t K)
151 pivot_searcher(
size_t K) : m_ipiv(K) {}
153 std::pair<size_t, size_t> operator()(
size_t col,
const uint8_t matrix[])
160 const size_t K = m_ipiv.size();
162 if(m_ipiv[col] ==
false && matrix[col*K + col] != 0)
165 return std::make_pair(col, col);
168 for(
size_t row = 0; row != K; ++row)
173 for(
size_t i = 0; i != K; ++i)
175 if(m_ipiv[i] ==
false && matrix[row*K + i] != 0)
178 return std::make_pair(row, i);
183 throw Invalid_Argument(
"ZFEC: pivot not found in invert_matrix");
188 std::vector<bool> m_ipiv;
191 pivot_searcher pivot_search(K);
192 std::vector<size_t> indxc(K);
193 std::vector<size_t> indxr(K);
195 for(
size_t col = 0; col != K; ++col)
197 const auto icolrow = pivot_search(col, matrix);
199 const size_t icol = icolrow.first;
200 const size_t irow = icolrow.second;
209 for(
size_t i = 0; i != K; ++i)
210 std::swap(matrix[irow*K + i], matrix[icol*K + i]);
215 uint8_t* pivot_row = &matrix[icol*K];
216 const uint8_t c = pivot_row[icol];
220 throw Invalid_Argument(
"ZFEC: singlar matrix");
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]];
234 for(
size_t i = 0; i != K; ++i)
238 const uint8_t z = matrix[i*K + icol];
239 matrix[i*K + icol] = 0;
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]];
249 for(
size_t i = 0; i != K; ++i)
251 if(indxr[i] != indxc[i])
253 for(
size_t row = 0; row != K; ++row)
254 std::swap(matrix[row*K + indxr[i]], matrix[row*K + indxc[i]]);
271void create_inverted_vdm(uint8_t vdm[],
size_t K)
288 std::vector<uint8_t> b(K);
289 std::vector<uint8_t> c(K);
298 for(
size_t i = 1; i < K; ++i)
300 const uint8_t* mul_p_i = GF_MUL_TABLE(GF_EXP[i]);
302 for(
size_t j = K-1 - (i - 1); j < K-1; ++j)
303 c[j] ^= mul_p_i[c[j+1]];
307 for(
size_t row = 0; row < K; ++row)
310 const uint8_t* mul_p_row = GF_MUL_TABLE(row == 0 ? 0 : GF_EXP[row]);
314 for(
size_t i = K - 1; i > 0; i--)
316 b[i-1] = c[i] ^ mul_p_row[b[i]];
317 t = b[i-1] ^ mul_p_row[t];
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]];
331void ZFEC::addmul(uint8_t z[],
const uint8_t x[], uint8_t y,
size_t size)
336 const uint8_t* GF_MUL_Y = GF_MUL_TABLE(y);
339 while(size > 0 &&
reinterpret_cast<uintptr_t
>(z) % 16)
341 z[0] ^= GF_MUL_Y[x[0]];
347#if defined(BOTAN_HAS_ZFEC_VPERM)
350 const size_t consumed = addmul_vperm(z, x, y, size);
357#if defined(BOTAN_HAS_ZFEC_SSE2)
358 if(size >= 64 && CPUID::has_sse2())
360 const size_t consumed = addmul_sse2(z, x, y, size);
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]];
392 for(
size_t i = 0; i != size; ++i)
393 z[i] ^= GF_MUL_Y[x[i]];
406 m_K(K), m_N(N), m_enc_matrix(N * K)
408 if(m_K == 0 || m_N == 0 || m_K > 256 || m_N > 256 || m_K > N)
411 std::vector<uint8_t> temp_matrix(m_N * m_K);
418 create_inverted_vdm(&temp_matrix[0], m_K);
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];
426 for(
size_t i = 0; i != m_K; ++i)
427 m_enc_matrix[i*(m_K+1)] = 1;
432 for(
size_t row = m_K; row != m_N; ++row)
434 for(
size_t col = 0; col != m_K; ++col)
437 for(
size_t i = 0; i != m_K; i++)
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];
443 m_enc_matrix[row * m_K + col] = acc;
452 const uint8_t input[],
size_t size,
457 throw Invalid_Argument(
"ZFEC::encode: input must be multiple of K uint8_ts");
459 const size_t share_size = size / m_K;
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);
469 const std::vector<const uint8_t*>& shares,
474 if(shares.size() != m_K)
478 for(
size_t i = 0; i != m_K; ++i)
479 output_cb(i, shares[i], share_size);
481 std::vector<uint8_t> fec_buf(share_size);
483 for(
size_t i = m_K; i != m_N; ++i)
485 clear_mem(fec_buf.data(), fec_buf.size());
487 for(
size_t j = 0; j != m_K; ++j)
489 addmul(&fec_buf[0], shares[j],
490 m_enc_matrix[i*m_K+j], share_size);
493 output_cb(i, &fec_buf[0], fec_buf.size());
501 const std::map<size_t, const uint8_t*>& shares,
514 if(shares.size() < m_K)
515 throw Decoding_Error(
"ZFEC: could not decode, less than K surviving shares");
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);
521 auto shares_b_iter = shares.begin();
522 auto shares_e_iter = shares.rbegin();
524 bool missing_primary_share =
false;
526 for(
size_t i = 0; i != m_K; ++i)
529 const uint8_t* share_data =
nullptr;
531 if(shares_b_iter->first == i)
533 share_id = shares_b_iter->first;
534 share_data = shares_b_iter->second;
540 share_id = shares_e_iter->first;
541 share_data = shares_e_iter->second;
543 missing_primary_share =
true;
547 throw Decoding_Error(
"ZFEC: invalid share id detected during decode");
558 decoding_matrix[i*(m_K+1)] = 1;
559 output_cb(share_id, share_data, share_size);
563 std::memcpy(&decoding_matrix[i*m_K], &m_enc_matrix[share_id*m_K], m_K);
566 sharesv[i] = share_data;
567 indexes[i] = share_id;
572 if(!missing_primary_share)
574 for(
size_t i = 0; i != indexes.size(); ++i)
581 invert_matrix(&decoding_matrix[0], m_K);
583 for(
size_t i = 0; i != indexes.size(); ++i)
585 if(indexes[i] >= m_K)
587 std::vector<uint8_t> buf(share_size);
588 for(
size_t col = 0; col != m_K; ++col)
590 addmul(&buf[0], sharesv[col], decoding_matrix[i*m_K + col], share_size);
592 output_cb(i, &buf[0], share_size);
599#if defined(BOTAN_HAS_ZFEC_VPERM)
606#if defined(BOTAN_HAS_ZFEC_SSE2)
607 if(CPUID::has_sse2())
#define BOTAN_ASSERT_NOMSG(expr)
void encode(const uint8_t input[], size_t size, output_cb_t output_cb) const
std::string provider() const
void decode_shares(const std::map< size_t, const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
std::function< void(size_t, const uint8_t[], size_t)> output_cb_t
void encode_shares(const std::vector< const uint8_t * > &shares, size_t share_size, output_cb_t output_cb) const
int(* final)(unsigned char *, CTX *)
void clear_mem(T *ptr, size_t n)