29801022385

Committed 21 Jul 2026 02:12AM UTC coverage: 89.404% (-0.02%) from 89.419%

Build # 29801022385

Build Type

push

github

Committed by

web-flow

Commit Message

Merge pull request #5747 from randombit/jack/zfec-avx512-gfni

ZFEC optimizations and improvements

Coverage Stats

114453 of 128018 relevant lines covered (89.4%)

10848451.21 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

89.27

/src/lib/misc/zfec/zfec.cpp

/*
* Forward error correction based on Vandermonde matrices
*
* (C) 1997-1998 Luigi Rizzo (luigi@iet.unipi.it)
* (C) 2009,2010,2021 Jack Lloyd
* (C) 2011 Billy Brumley (billy.brumley@aalto.fi)
*
* Botan is released under the Simplified BSD License (see license.txt)
*/

#include <botan/zfec.h>

#include <botan/exceptn.h>
#include <botan/mem_ops.h>
#include <cstring>
#include <vector>

#if defined(BOTAN_HAS_CPUID)
   #include <botan/internal/cpuid.h>
#endif

namespace Botan {

namespace {

/* Tables for arithmetic in GF(2^8) using 1+x^2+x^3+x^4+x^8
*
* See Lin & Costello, Appendix A, and Lee & Messerschmitt, p. 453.
*
* Generate GF(2**m) from the irreducible polynomial p(X) in p[0]..p[m]
* Lookup tables:
*     index->polynomial form           gf_exp[] contains j= \alpha^i;
*     polynomial form -> index form    gf_log[ j = \alpha^i ] = i
* \alpha=x is the primitive element of GF(2^m)
*/
alignas(256) const uint8_t GF_EXP[255] = {
   0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40, 0x80, 0x1D, 0x3A, 0x74, 0xE8, 0xCD, 0x87, 0x13, 0x26, 0x4C, 0x98, 0x2D,
   0x5A, 0xB4, 0x75, 0xEA, 0xC9, 0x8F, 0x03, 0x06, 0x0C, 0x18, 0x30, 0x60, 0xC0, 0x9D, 0x27, 0x4E, 0x9C, 0x25, 0x4A,
   0x94, 0x35, 0x6A, 0xD4, 0xB5, 0x77, 0xEE, 0xC1, 0x9F, 0x23, 0x46, 0x8C, 0x05, 0x0A, 0x14, 0x28, 0x50, 0xA0, 0x5D,
   0xBA, 0x69, 0xD2, 0xB9, 0x6F, 0xDE, 0xA1, 0x5F, 0xBE, 0x61, 0xC2, 0x99, 0x2F, 0x5E, 0xBC, 0x65, 0xCA, 0x89, 0x0F,
   0x1E, 0x3C, 0x78, 0xF0, 0xFD, 0xE7, 0xD3, 0xBB, 0x6B, 0xD6, 0xB1, 0x7F, 0xFE, 0xE1, 0xDF, 0xA3, 0x5B, 0xB6, 0x71,
   0xE2, 0xD9, 0xAF, 0x43, 0x86, 0x11, 0x22, 0x44, 0x88, 0x0D, 0x1A, 0x34, 0x68, 0xD0, 0xBD, 0x67, 0xCE, 0x81, 0x1F,
   0x3E, 0x7C, 0xF8, 0xED, 0xC7, 0x93, 0x3B, 0x76, 0xEC, 0xC5, 0x97, 0x33, 0x66, 0xCC, 0x85, 0x17, 0x2E, 0x5C, 0xB8,
   0x6D, 0xDA, 0xA9, 0x4F, 0x9E, 0x21, 0x42, 0x84, 0x15, 0x2A, 0x54, 0xA8, 0x4D, 0x9A, 0x29, 0x52, 0xA4, 0x55, 0xAA,
   0x49, 0x92, 0x39, 0x72, 0xE4, 0xD5, 0xB7, 0x73, 0xE6, 0xD1, 0xBF, 0x63, 0xC6, 0x91, 0x3F, 0x7E, 0xFC, 0xE5, 0xD7,
   0xB3, 0x7B, 0xF6, 0xF1, 0xFF, 0xE3, 0xDB, 0xAB, 0x4B, 0x96, 0x31, 0x62, 0xC4, 0x95, 0x37, 0x6E, 0xDC, 0xA5, 0x57,
   0xAE, 0x41, 0x82, 0x19, 0x32, 0x64, 0xC8, 0x8D, 0x07, 0x0E, 0x1C, 0x38, 0x70, 0xE0, 0xDD, 0xA7, 0x53, 0xA6, 0x51,
   0xA2, 0x59, 0xB2, 0x79, 0xF2, 0xF9, 0xEF, 0xC3, 0x9B, 0x2B, 0x56, 0xAC, 0x45, 0x8A, 0x09, 0x12, 0x24, 0x48, 0x90,
   0x3D, 0x7A, 0xF4, 0xF5, 0xF7, 0xF3, 0xFB, 0xEB, 0xCB, 0x8B, 0x0B, 0x16, 0x2C, 0x58, 0xB0, 0x7D, 0xFA, 0xE9, 0xCF,
   0x83, 0x1B, 0x36, 0x6C, 0xD8, 0xAD, 0x47, 0x8E,
};

alignas(256) const uint8_t GF_LOG[256] = {
   0xFF, 0x00, 0x01, 0x19, 0x02, 0x32, 0x1A, 0xC6, 0x03, 0xDF, 0x33, 0xEE, 0x1B, 0x68, 0xC7, 0x4B, 0x04, 0x64, 0xE0,
   0x0E, 0x34, 0x8D, 0xEF, 0x81, 0x1C, 0xC1, 0x69, 0xF8, 0xC8, 0x08, 0x4C, 0x71, 0x05, 0x8A, 0x65, 0x2F, 0xE1, 0x24,
   0x0F, 0x21, 0x35, 0x93, 0x8E, 0xDA, 0xF0, 0x12, 0x82, 0x45, 0x1D, 0xB5, 0xC2, 0x7D, 0x6A, 0x27, 0xF9, 0xB9, 0xC9,
   0x9A, 0x09, 0x78, 0x4D, 0xE4, 0x72, 0xA6, 0x06, 0xBF, 0x8B, 0x62, 0x66, 0xDD, 0x30, 0xFD, 0xE2, 0x98, 0x25, 0xB3,
   0x10, 0x91, 0x22, 0x88, 0x36, 0xD0, 0x94, 0xCE, 0x8F, 0x96, 0xDB, 0xBD, 0xF1, 0xD2, 0x13, 0x5C, 0x83, 0x38, 0x46,
   0x40, 0x1E, 0x42, 0xB6, 0xA3, 0xC3, 0x48, 0x7E, 0x6E, 0x6B, 0x3A, 0x28, 0x54, 0xFA, 0x85, 0xBA, 0x3D, 0xCA, 0x5E,
   0x9B, 0x9F, 0x0A, 0x15, 0x79, 0x2B, 0x4E, 0xD4, 0xE5, 0xAC, 0x73, 0xF3, 0xA7, 0x57, 0x07, 0x70, 0xC0, 0xF7, 0x8C,
   0x80, 0x63, 0x0D, 0x67, 0x4A, 0xDE, 0xED, 0x31, 0xC5, 0xFE, 0x18, 0xE3, 0xA5, 0x99, 0x77, 0x26, 0xB8, 0xB4, 0x7C,
   0x11, 0x44, 0x92, 0xD9, 0x23, 0x20, 0x89, 0x2E, 0x37, 0x3F, 0xD1, 0x5B, 0x95, 0xBC, 0xCF, 0xCD, 0x90, 0x87, 0x97,
   0xB2, 0xDC, 0xFC, 0xBE, 0x61, 0xF2, 0x56, 0xD3, 0xAB, 0x14, 0x2A, 0x5D, 0x9E, 0x84, 0x3C, 0x39, 0x53, 0x47, 0x6D,
   0x41, 0xA2, 0x1F, 0x2D, 0x43, 0xD8, 0xB7, 0x7B, 0xA4, 0x76, 0xC4, 0x17, 0x49, 0xEC, 0x7F, 0x0C, 0x6F, 0xF6, 0x6C,
   0xA1, 0x3B, 0x52, 0x29, 0x9D, 0x55, 0xAA, 0xFB, 0x60, 0x86, 0xB1, 0xBB, 0xCC, 0x3E, 0x5A, 0xCB, 0x59, 0x5F, 0xB0,
   0x9C, 0xA9, 0xA0, 0x51, 0x0B, 0xF5, 0x16, 0xEB, 0x7A, 0x75, 0x2C, 0xD7, 0x4F, 0xAE, 0xD5, 0xE9, 0xE6, 0xE7, 0xAD,
   0xE8, 0x74, 0xD6, 0xF4, 0xEA, 0xA8, 0x50, 0x58, 0xAF};

alignas(256) const uint8_t GF_INVERSE[256] = {
   0x00, 0x01, 0x8E, 0xF4, 0x47, 0xA7, 0x7A, 0xBA, 0xAD, 0x9D, 0xDD, 0x98, 0x3D, 0xAA, 0x5D, 0x96, 0xD8, 0x72, 0xC0,
   0x58, 0xE0, 0x3E, 0x4C, 0x66, 0x90, 0xDE, 0x55, 0x80, 0xA0, 0x83, 0x4B, 0x2A, 0x6C, 0xED, 0x39, 0x51, 0x60, 0x56,
   0x2C, 0x8A, 0x70, 0xD0, 0x1F, 0x4A, 0x26, 0x8B, 0x33, 0x6E, 0x48, 0x89, 0x6F, 0x2E, 0xA4, 0xC3, 0x40, 0x5E, 0x50,
   0x22, 0xCF, 0xA9, 0xAB, 0x0C, 0x15, 0xE1, 0x36, 0x5F, 0xF8, 0xD5, 0x92, 0x4E, 0xA6, 0x04, 0x30, 0x88, 0x2B, 0x1E,
   0x16, 0x67, 0x45, 0x93, 0x38, 0x23, 0x68, 0x8C, 0x81, 0x1A, 0x25, 0x61, 0x13, 0xC1, 0xCB, 0x63, 0x97, 0x0E, 0x37,
   0x41, 0x24, 0x57, 0xCA, 0x5B, 0xB9, 0xC4, 0x17, 0x4D, 0x52, 0x8D, 0xEF, 0xB3, 0x20, 0xEC, 0x2F, 0x32, 0x28, 0xD1,
   0x11, 0xD9, 0xE9, 0xFB, 0xDA, 0x79, 0xDB, 0x77, 0x06, 0xBB, 0x84, 0xCD, 0xFE, 0xFC, 0x1B, 0x54, 0xA1, 0x1D, 0x7C,
   0xCC, 0xE4, 0xB0, 0x49, 0x31, 0x27, 0x2D, 0x53, 0x69, 0x02, 0xF5, 0x18, 0xDF, 0x44, 0x4F, 0x9B, 0xBC, 0x0F, 0x5C,
   0x0B, 0xDC, 0xBD, 0x94, 0xAC, 0x09, 0xC7, 0xA2, 0x1C, 0x82, 0x9F, 0xC6, 0x34, 0xC2, 0x46, 0x05, 0xCE, 0x3B, 0x0D,
   0x3C, 0x9C, 0x08, 0xBE, 0xB7, 0x87, 0xE5, 0xEE, 0x6B, 0xEB, 0xF2, 0xBF, 0xAF, 0xC5, 0x64, 0x07, 0x7B, 0x95, 0x9A,
   0xAE, 0xB6, 0x12, 0x59, 0xA5, 0x35, 0x65, 0xB8, 0xA3, 0x9E, 0xD2, 0xF7, 0x62, 0x5A, 0x85, 0x7D, 0xA8, 0x3A, 0x29,
   0x71, 0xC8, 0xF6, 0xF9, 0x43, 0xD7, 0xD6, 0x10, 0x73, 0x76, 0x78, 0x99, 0x0A, 0x19, 0x91, 0x14, 0x3F, 0xE6, 0xF0,
   0x86, 0xB1, 0xE2, 0xF1, 0xFA, 0x74, 0xF3, 0xB4, 0x6D, 0x21, 0xB2, 0x6A, 0xE3, 0xE7, 0xB5, 0xEA, 0x03, 0x8F, 0xD3,
   0xC9, 0x42, 0xD4, 0xE8, 0x75, 0x7F, 0xFF, 0x7E, 0xFD};

const uint8_t* GF_MUL_TABLE(uint8_t y) {
   class GF_Table final {
      public:
         GF_Table() {
            m_table.resize(256 * 256);

            // x*0 = 0*y = 0 so we iterate over [1,255)
            for(size_t i = 1; i != 256; ++i) {
               for(size_t j = 1; j != 256; ++j) {
                  m_table[256 * i + j] = GF_EXP[(GF_LOG[i] + GF_LOG[j]) % 255];
               }
            }
         }

         const uint8_t* ptr(uint8_t y) const { return &m_table[256 * y]; }

      private:
         std::vector<uint8_t> m_table;
   };

   static const GF_Table table;
   return table.ptr(y);
}

/*
* invert_matrix() takes a K*K matrix and produces its inverse
* (Gauss-Jordan algorithm, adapted from Numerical Recipes in C)
*/
void invert_matrix(uint8_t matrix[], size_t K) {
   class pivot_searcher final {
      public:
         explicit pivot_searcher(size_t K) : m_ipiv(K) {}

         std::pair<size_t, size_t> operator()(size_t col, const uint8_t matrix[]) {
            /*
            * Zeroing column 'col', look for a non-zero element.
            * First try on the diagonal, if it fails, look elsewhere.
            */

            const size_t K = m_ipiv.size();

            if(m_ipiv[col] == false && matrix[col * K + col] != 0) {
               m_ipiv[col] = true;
               return std::make_pair(col, col);
            }

            for(size_t row = 0; row != K; ++row) {
               if(m_ipiv[row]) {
                  continue;
               }

               for(size_t i = 0; i != K; ++i) {
                  if(m_ipiv[i] == false && matrix[row * K + i] != 0) {
                     m_ipiv[i] = true;
                     return std::make_pair(row, i);
                  }
               }
            }

            throw Invalid_Argument("ZFEC: pivot not found in invert_matrix");
         }

      private:
         // Marks elements already used as pivots
         std::vector<bool> m_ipiv;
   };

   pivot_searcher pivot_search(K);
   std::vector<size_t> indxc(K);
   std::vector<size_t> indxr(K);

   for(size_t col = 0; col != K; ++col) {
      const auto icolrow = pivot_search(col, matrix);

      const size_t icol = icolrow.first;
      const size_t irow = icolrow.second;

      /*
      * swap rows irow and icol, so afterwards the diagonal
      * element will be correct. Rarely done, not worth
      * optimizing.
      */
      if(irow != icol) {
         for(size_t i = 0; i != K; ++i) {
            std::swap(matrix[irow * K + i], matrix[icol * K + i]);
         }
      }

      indxr[col] = irow;
      indxc[col] = icol;
      uint8_t* pivot_row = &matrix[icol * K];
      const uint8_t c = pivot_row[icol];
      pivot_row[icol] = 1;

      if(c == 0) {
         throw Invalid_Argument("ZFEC: singular matrix");
      }

      if(c != 1) {
         const uint8_t* mul_c = GF_MUL_TABLE(GF_INVERSE[c]);
         for(size_t i = 0; i != K; ++i) {
            pivot_row[i] = mul_c[pivot_row[i]];
         }
      }

      /*
      * From all rows, remove multiples of the selected row to zero
      * the relevant entry (in fact, the entry is not zero because we
      * know it must be zero).
      */
      for(size_t i = 0; i != K; ++i) {
         if(i != icol) {
            const uint8_t z = matrix[i * K + icol];
            matrix[i * K + icol] = 0;

            // This is equivalent to addmul()
            const uint8_t* mul_z = GF_MUL_TABLE(z);
            for(size_t j = 0; j != K; ++j) {
               matrix[i * K + j] ^= mul_z[pivot_row[j]];
            }
         }
      }
   }

   for(size_t i = 0; i != K; ++i) {
      if(indxr[i] != indxc[i]) {
         for(size_t row = 0; row != K; ++row) {
            std::swap(matrix[row * K + indxr[i]], matrix[row * K + indxc[i]]);
         }
      }
   }
}

/*
* Generate and invert a Vandermonde matrix.
*
* Only uses the second column of the matrix, containing the p_i's
* (contents - 0, GF_EXP[0...n])
*
* Algorithm borrowed from "Numerical recipes in C", section 2.8, but
* largely revised for my purposes.
*
* p = coefficients of the matrix (p_i)
* q = values of the polynomial (known)
*/
void create_inverted_vdm(uint8_t vdm[], size_t K) {
   if(K == 0) {
      return;
   }

   if(K == 1) {
      // degenerate case, matrix must be p^0 = 1
      vdm[0] = 1;
      return;
   }

   /*
   * c holds the coefficient of P(x) = Prod (x - p_i), i=0..K-1
   * b holds the coefficient for the matrix inversion
   */
   std::vector<uint8_t> b(K);
   std::vector<uint8_t> c(K);

   /*
   * construct coeffs. recursively. We know c[K] = 1 (implicit)
   * and start P_0 = x - p_0, then at each stage multiply by
   * x - p_i generating P_i = x P_{i-1} - p_i P_{i-1}
   * After K steps we are done.
   */
   c[K - 1] = 0; /* really -p(0), but x = -x in GF(2^m) */
   for(size_t i = 1; i < K; ++i) {
      const uint8_t* mul_p_i = GF_MUL_TABLE(GF_EXP[i]);

      for(size_t j = K - 1 - (i - 1); j < K - 1; ++j) {
         c[j] ^= mul_p_i[c[j + 1]];
      }
      c[K - 1] ^= GF_EXP[i];
   }

   for(size_t row = 0; row < K; ++row) {
      // synthetic division etc.
      const uint8_t* mul_p_row = GF_MUL_TABLE(row == 0 ? 0 : GF_EXP[row]);

      uint8_t t = 1;
      b[K - 1] = 1; /* this is in fact c[K] */
      for(size_t i = K - 1; i > 0; i--) {
         b[i - 1] = c[i] ^ mul_p_row[b[i]];
         t = b[i - 1] ^ mul_p_row[t];
      }

      const uint8_t* mul_t_inv = GF_MUL_TABLE(GF_INVERSE[t]);
      for(size_t col = 0; col != K; ++col) {
         vdm[col * K + row] = mul_t_inv[b[col]];
      }
   }
}

}  // namespace

/*
* addmul() computes z[] = z[] + x[] * y
*/
void ZFEC::addmul(uint8_t z[], const uint8_t x[], uint8_t y, size_t size) {
   if(y == 0) {
      return;
   }

   const uint8_t* GF_MUL_Y = GF_MUL_TABLE(y);

   while(size >= 16) {
      z[0] ^= GF_MUL_Y[x[0]];
      z[1] ^= GF_MUL_Y[x[1]];
      z[2] ^= GF_MUL_Y[x[2]];
      z[3] ^= GF_MUL_Y[x[3]];
      z[4] ^= GF_MUL_Y[x[4]];
      z[5] ^= GF_MUL_Y[x[5]];
      z[6] ^= GF_MUL_Y[x[6]];
      z[7] ^= GF_MUL_Y[x[7]];
      z[8] ^= GF_MUL_Y[x[8]];
      z[9] ^= GF_MUL_Y[x[9]];
      z[10] ^= GF_MUL_Y[x[10]];
      z[11] ^= GF_MUL_Y[x[11]];
      z[12] ^= GF_MUL_Y[x[12]];
      z[13] ^= GF_MUL_Y[x[13]];
      z[14] ^= GF_MUL_Y[x[14]];
      z[15] ^= GF_MUL_Y[x[15]];

      x += 16;
      z += 16;
      size -= 16;
   }

   // Clean up the trailing pieces
   for(size_t i = 0; i != size; ++i) {
      z[i] ^= GF_MUL_Y[x[i]];
   }
}

/*
* linear_combination() computes z[] = x[0][] * y[0] + ... + x[k-1][] * y[k-1]
*/
void ZFEC::linear_combination(uint8_t z[], const uint8_t* const x[], const uint8_t y[], size_t k, size_t size) {
#if defined(BOTAN_HAS_ZFEC_GFNI)
   if(CPUID::has(CPUID::Feature::AVX512, CPUID::Feature::GFNI)) {
      linear_combination_gfni(z, x, y, k, size);
      return;
   }
#endif

   size_t consumed = 0;

#if defined(BOTAN_HAS_ZFEC_VPERM)
   if(CPUID::has(CPUID::Feature::SIMD_4X32)) {
      consumed = linear_combination_vperm(z, x, y, k, size);
   }
#endif

   if(consumed < size) {
      clear_mem(z + consumed, size - consumed);
      for(size_t j = 0; j != k; ++j) {
         addmul(z + consumed, x[j] + consumed, y[j], size - consumed);
      }
   }
}

/*
* This section contains the proper FEC encoding/decoding routines.
* The encoding matrix is computed starting with a Vandermonde matrix,
* and then transforming it into a systematic matrix.
*/

/*
* ZFEC constructor
*/
ZFEC::ZFEC(size_t K, size_t N) : m_K(K), m_N(N), m_enc_matrix(N * K) {
   if(m_K == 0 || m_N == 0 || m_K >= 256 || m_N >= 256 || m_K > N) {
      throw Invalid_Argument("ZFEC: violated 1 <= K <= N < 256");
   }

   std::vector<uint8_t> temp_matrix(m_N * m_K);

   /*
   * quick code to build systematic matrix: invert the top
   * K*K Vandermonde matrix, multiply right the bottom n-K rows
   * by the inverse, and construct the identity matrix at the top.
   */
   create_inverted_vdm(temp_matrix.data(), m_K);

   for(size_t i = m_K * m_K; i != temp_matrix.size(); ++i) {
      temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];
   }

   /*
   * the upper part of the encoding matrix is I
   */
   for(size_t i = 0; i != m_K; ++i) {
      m_enc_matrix[i * (m_K + 1)] = 1;
   }

   /*
   * computes C = AB where A is n*K, B is K*m, C is n*m
   */
   for(size_t row = m_K; row != m_N; ++row) {
      for(size_t col = 0; col != m_K; ++col) {
         uint8_t acc = 0;
         for(size_t i = 0; i != m_K; i++) {
            const uint8_t row_v = temp_matrix[row * m_K + i];
            const uint8_t row_c = temp_matrix[col + m_K * i];
            acc ^= GF_MUL_TABLE(row_v)[row_c];
         }
         m_enc_matrix[row * m_K + col] = acc;
      }
   }
}

/*
* ZFEC encoding routine
*/
void ZFEC::encode(const uint8_t input[], size_t size, const output_cb_t& output_cb) const {
   if(size % m_K != 0) {
      throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");
   }

   const size_t share_size = size / m_K;

   std::vector<const uint8_t*> shares;
   for(size_t i = 0; i != m_K; ++i) {
      shares.push_back(input + i * share_size);
   }

   this->encode_shares(shares, share_size, output_cb);
}

void ZFEC::encode_shares(const std::vector<const uint8_t*>& shares,
                         size_t share_size,
                         const output_cb_t& output_cb) const {
   if(shares.size() != m_K) {
      throw Invalid_Argument("ZFEC::encode_shares must provide K shares");
   }

   // The initial shares are just the original input shares
   for(size_t i = 0; i != m_K; ++i) {
      output_cb(i, shares[i], share_size);
   }

   std::vector<uint8_t> fec_buf(share_size);

   for(size_t i = m_K; i != m_N; ++i) {
      linear_combination(fec_buf.data(), shares.data(), &m_enc_matrix[i * m_K], m_K, share_size);
      output_cb(i, fec_buf.data(), fec_buf.size());
   }
}

/*
* ZFEC decoding routine
*/
void ZFEC::decode_shares(const std::map<size_t, const uint8_t*>& shares,
                         size_t share_size,
                         const output_cb_t& output_cb) const {
   /*
   Todo:
   If shares.size() < K:
   signal decoding error for missing shares < K
   emit existing shares < K
   (ie, partial recovery if possible)
   Assert share_size % K == 0
   */

   if(shares.size() < m_K) {
      throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");
   }

   std::vector<uint8_t> decoding_matrix(m_K * m_K);
   std::vector<size_t> indexes(m_K);
   std::vector<const uint8_t*> sharesv(m_K);

   auto shares_b_iter = shares.begin();
   auto shares_e_iter = shares.rbegin();

   bool missing_primary_share = false;

   for(size_t i = 0; i != m_K; ++i) {
      size_t share_id = 0;
      const uint8_t* share_data = nullptr;

      if(shares_b_iter->first == i) {
         share_id = shares_b_iter->first;
         share_data = shares_b_iter->second;
         ++shares_b_iter;
      } else {
         // if share i not found, use the unused one closest to n
         share_id = shares_e_iter->first;
         share_data = shares_e_iter->second;
         ++shares_e_iter;
         missing_primary_share = true;
      }

      if(share_id >= m_N) {
         throw Decoding_Error("ZFEC: invalid share id detected during decode");
      }

      /*
      This is a systematic code (encoding matrix includes K*K identity
      matrix), so shares less than K are copies of the input data,
      can output_cb directly. Also we know the encoding matrix in those rows
      contains I, so we can set the single bit directly without copying
      the entire row
      */
      if(share_id < m_K) {
         decoding_matrix[i * (m_K + 1)] = 1;
         output_cb(share_id, share_data, share_size);
      } else {
         // will decode after inverting matrix
         std::memcpy(&decoding_matrix[i * m_K], &m_enc_matrix[share_id * m_K], m_K);
      }

      sharesv[i] = share_data;
      indexes[i] = share_id;
   }

   // If we had the original data shares then no need to perform
   // a matrix inversion, return immediately.
   if(!missing_primary_share) {
      for(const size_t index : indexes) {
         BOTAN_ASSERT_NOMSG(index < m_K);
      }
      return;
   }

   invert_matrix(decoding_matrix.data(), m_K);

   for(size_t i = 0; i != indexes.size(); ++i) {
      if(indexes[i] >= m_K) {
         std::vector<uint8_t> buf(share_size);
         linear_combination(buf.data(), sharesv.data(), &decoding_matrix[i * m_K], m_K, share_size);
         output_cb(i, buf.data(), share_size);
      }
   }
}

std::string ZFEC::provider() const {
#if defined(BOTAN_HAS_ZFEC_GFNI)
   if(auto feat = CPUID::check(CPUID::Feature::AVX512, CPUID::Feature::GFNI)) {
      return *feat;
   }
#endif

#if defined(BOTAN_HAS_ZFEC_VPERM)
   if(auto feat = CPUID::check(CPUID::Feature::SIMD_4X32)) {
      return *feat;
   }
#endif

   return "base";
}

}  // namespace Botan

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
22	namespace Botan {
23
24	namespace {
25
26	/* Tables for arithmetic 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	*/
36	alignas(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
53	alignas(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
69	alignas(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
85	const uint8_t* GF_MUL_TABLE(uint8_t y) {	7,258,153✔
86	class GF_Table final {	7,258,153✔
87	public:
88	GF_Table() {	5✔
89	m_table.resize(256 * 256);	5✔
90
91	// x0 = 0y = 0 so we iterate over [1,255)
92	for(size_t i = 1; i != 256; ++i) {	1,280✔
93	for(size_t j = 1; j != 256; ++j) {	326,400✔
94	m_table[256 * i + j] = GF_EXP[(GF_LOG[i] + GF_LOG[j]) % 255];	325,125✔
95	}
96	}
97	}	5✔
98
99	const uint8_t* ptr(uint8_t y) const { return &m_table[256 * y]; }	7,258,153✔
100
101	private:
102	std::vector<uint8_t> m_table;
103	};
104
105	static const GF_Table table;	7,258,153✔
106	return table.ptr(y);	7,258,153✔
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	*/
113	void invert_matrix(uint8_t matrix[], size_t K) {	87,702✔
114	class pivot_searcher final {	263,106✔
115	public:
116	explicit pivot_searcher(size_t K) : m_ipiv(K) {}	87,702✔
117
118	std::pair<size_t, size_t> operator()(size_t col, const uint8_t matrix[]) {	337,030✔
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();	337,030✔
125
126	if(m_ipiv[col] == false && matrix[col * K + col] != 0) {	337,030✔
127	m_ipiv[col] = true;	337,030✔
128	return std::make_pair(col, col);	337,030✔
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);	87,702✔
153	std::vector<size_t> indxc(K);	87,702✔
154	std::vector<size_t> indxr(K);	87,702✔
155
156	for(size_t col = 0; col != K; ++col) {	424,732✔
157	const auto icolrow = pivot_search(col, matrix);	337,030✔
158
159	const size_t icol = icolrow.first;	337,030✔
160	const size_t irow = icolrow.second;	337,030✔
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) {	337,030✔
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;	337,030✔
174	indxc[col] = icol;	337,030✔
175	uint8_t* pivot_row = &matrix[icol * K];	337,030✔
176	const uint8_t c = pivot_row[icol];	337,030✔
177	pivot_row[icol] = 1;	337,030✔
178
179	if(c == 0) {	337,030✔
180	throw Invalid_Argument("ZFEC: singular matrix");	×
181	}
182
183	if(c != 1) {	337,030✔
184	const uint8_t* mul_c = GF_MUL_TABLE(GF_INVERSE[c]);	158,765✔
185	for(size_t i = 0; i != K; ++i) {	774,285✔
186	pivot_row[i] = mul_c[pivot_row[i]];	615,520✔
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) {	1,650,534✔
196	if(i != icol) {	1,313,504✔
197	const uint8_t z = matrix[i * K + icol];	976,474✔
198	matrix[i * K + icol] = 0;	976,474✔
199
200	// This is equivalent to addmul()
201	const uint8_t* mul_z = GF_MUL_TABLE(z);	976,474✔
202	for(size_t j = 0; j != K; ++j) {	4,836,108✔
203	matrix[i * K + j] ^= mul_z[pivot_row[j]];	3,859,634✔
204	}
205	}
206	}
207	}
208
209	for(size_t i = 0; i != K; ++i) {	424,732✔
210	if(indxr[i] != indxc[i]) {	337,030✔
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	}	175,404✔
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	*/
230	void create_inverted_vdm(uint8_t vdm[], size_t K) {	92,534✔
231	if(K == 0) {	92,534✔
232	return;	547✔
233	}
234
235	if(K == 1) {	92,534✔
236	// degenerate case, matrix must be p^0 = 1
237	vdm[0] = 1;	547✔
238	return;	547✔
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);	91,987✔
246	std::vector<uint8_t> c(K);	91,987✔
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) */	91,987✔
255	for(size_t i = 1; i < K; ++i) {	353,305✔
256	const uint8_t* mul_p_i = GF_MUL_TABLE(GF_EXP[i]);	261,318✔
257
258	for(size_t j = K - 1 - (i - 1); j < K - 1; ++j) {	510,916✔
259	c[j] ^= mul_p_i[c[j + 1]];	249,598✔
260	}
261	c[K - 1] ^= GF_EXP[i];	261,318✔
262	}
263
264	for(size_t row = 0; row < K; ++row) {	445,292✔
265	// synthetic division etc.
266	const uint8_t* mul_p_row = GF_MUL_TABLE(row == 0 ? 0 : GF_EXP[row]);	353,305✔
267
268	uint8_t t = 1;	353,305✔
269	b[K - 1] = 1; /* this is in fact c[K] */	353,305✔
270	for(size_t i = K - 1; i > 0; i--) {	1,375,137✔
271	b[i - 1] = c[i] ^ mul_p_row[b[i]];	1,021,832✔
272	t = b[i - 1] ^ mul_p_row[t];	1,021,832✔
273	}
274
275	const uint8_t* mul_t_inv = GF_MUL_TABLE(GF_INVERSE[t]);	353,305✔
276	for(size_t col = 0; col != K; ++col) {	1,728,442✔
277	vdm[col * K + row] = mul_t_inv[b[col]];	1,375,137✔
278	}
279	}
280	}	91,987✔
281
282	} // namespace
283
284	/*
285	* addmul() computes z[] = z[] + x[] * y
286	*/
287	void ZFEC::addmul(uint8_t z[], const uint8_t x[], uint8_t y, size_t size) {	577,076✔
288	if(y == 0) {	577,076✔
289	return;
290	}
291
292	const uint8_t* GF_MUL_Y = GF_MUL_TABLE(y);	577,076✔
293
294	while(size >= 16) {	1,205,919✔
295	z[0] ^= GF_MUL_Y[x[0]];	51,767✔
296	z[1] ^= GF_MUL_Y[x[1]];	51,767✔
297	z[2] ^= GF_MUL_Y[x[2]];	51,767✔
298	z[3] ^= GF_MUL_Y[x[3]];	51,767✔
299	z[4] ^= GF_MUL_Y[x[4]];	51,767✔
300	z[5] ^= GF_MUL_Y[x[5]];	51,767✔
301	z[6] ^= GF_MUL_Y[x[6]];	51,767✔
302	z[7] ^= GF_MUL_Y[x[7]];	51,767✔
303	z[8] ^= GF_MUL_Y[x[8]];	51,767✔
304	z[9] ^= GF_MUL_Y[x[9]];	51,767✔
305	z[10] ^= GF_MUL_Y[x[10]];	51,767✔
306	z[11] ^= GF_MUL_Y[x[11]];	51,767✔
307	z[12] ^= GF_MUL_Y[x[12]];	51,767✔
308	z[13] ^= GF_MUL_Y[x[13]];	51,767✔
309	z[14] ^= GF_MUL_Y[x[14]];	51,767✔
310	z[15] ^= GF_MUL_Y[x[15]];	51,767✔
311
312	x += 16;	51,767✔
313	z += 16;	51,767✔
314	size -= 16;	51,767✔
315	}
316
317	// Clean up the trailing pieces
318	for(size_t i = 0; i != size; ++i) {	5,402,556✔
319	z[i] ^= GF_MUL_Y[x[i]];	4,825,480✔
320	}
321	}
322
323	/*
324	* linear_combination() computes z[] = x[0][] * y[0] + ... + x[k-1][] * y[k-1]
325	*/
326	void ZFEC::linear_combination(uint8_t z[], const uint8_t* const x[], const uint8_t y[], size_t k, size_t size) {	161,330✔
327	#if defined(BOTAN_HAS_ZFEC_GFNI)
328	if(CPUID::has(CPUID::Feature::AVX512, CPUID::Feature::GFNI)) {	161,330✔
329	linear_combination_gfni(z, x, y, k, size);	×
330	return;	×
331	}
332	#endif
333
334	size_t consumed = 0;	161,330✔
335
336	#if defined(BOTAN_HAS_ZFEC_VPERM)
337	if(CPUID::has(CPUID::Feature::SIMD_4X32)) {	161,330✔
338	consumed = linear_combination_vperm(z, x, y, k, size);	160,174✔
339	}
340	#endif
341
342	if(consumed < size) {	161,330✔
343	clear_mem(z + consumed, size - consumed);	149,014✔
344	for(size_t j = 0; j != k; ++j) {	726,090✔
345	addmul(z + consumed, x[j] + consumed, y[j], size - consumed);	577,076✔
346	}
347	}
348	}
349
350	/*
351	* This section contains the proper FEC encoding/decoding routines.
352	* The encoding matrix is computed starting with a Vandermonde matrix,
353	* and then transforming it into a systematic matrix.
354	*/
355
356	/*
357	* ZFEC constructor
358	*/
359	ZFEC::ZFEC(size_t K, size_t N) : m_K(K), m_N(N), m_enc_matrix(N * K) {	92,534✔
360	if(m_K == 0 \|\| m_N == 0 \|\| m_K >= 256 \|\| m_N >= 256 \|\| m_K > N) {	92,534✔
361	throw Invalid_Argument("ZFEC: violated 1 <= K <= N < 256");	×
362	}
363
364	std::vector<uint8_t> temp_matrix(m_N * m_K);	92,534✔
365
366	/*
367	* quick code to build systematic matrix: invert the top
368	* K*K Vandermonde matrix, multiply right the bottom n-K rows
369	* by the inverse, and construct the identity matrix at the top.
370	*/
371	create_inverted_vdm(temp_matrix.data(), m_K);	92,534✔
372
373	for(size_t i = m_K * m_K; i != temp_matrix.size(); ++i) {	1,266,632✔
374	temp_matrix[i] = GF_EXP[((i / m_K) * (i % m_K)) % 255];	1,174,098✔
375	}
376
377	/*
378	* the upper part of the encoding matrix is I
379	*/
380	for(size_t i = 0; i != m_K; ++i) {	446,386✔
381	m_enc_matrix[i * (m_K + 1)] = 1;	353,852✔
382	}
383
384	/*
385	* computes C = AB where A is nK, B is Km, C is n*m
386	*/
387	for(size_t row = m_K; row != m_N; ++row) {	398,413✔
388	for(size_t col = 0; col != m_K; ++col) {	1,479,977✔
389	uint8_t acc = 0;
390	for(size_t i = 0; i != m_K; i++) {	5,752,008✔
391	const uint8_t row_v = temp_matrix[row * m_K + i];	4,577,910✔
392	const uint8_t row_c = temp_matrix[col + m_K * i];	4,577,910✔
393	acc ^= GF_MUL_TABLE(row_v)[row_c];	4,577,910✔
394	}
395	m_enc_matrix[row * m_K + col] = acc;	1,174,098✔
396	}
397	}
398	}	92,534✔
399
400	/*
401	* ZFEC encoding routine
402	*/
403	void ZFEC::encode(const uint8_t input[], size_t size, const output_cb_t& output_cb) const {	769✔
404	if(size % m_K != 0) {	769✔
405	throw Invalid_Argument("ZFEC::encode: input must be multiple of K uint8_ts");	×
406	}
407
408	const size_t share_size = size / m_K;	769✔
409
410	std::vector<const uint8_t*> shares;	769✔
411	for(size_t i = 0; i != m_K; ++i) {	3,302✔
412	shares.push_back(input + i * share_size);	2,533✔
413	}
414
415	this->encode_shares(shares, share_size, output_cb);	769✔
416	}	769✔
417
418	void ZFEC::encode_shares(const std::vector<const uint8_t*>& shares,	769✔
419	size_t share_size,
420	const output_cb_t& output_cb) const {
421	if(shares.size() != m_K) {	769✔
422	throw Invalid_Argument("ZFEC::encode_shares must provide K shares");	×
423	}
424
425	// The initial shares are just the original input shares
426	for(size_t i = 0; i != m_K; ++i) {	3,302✔
427	output_cb(i, shares[i], share_size);	5,066✔
428	}
429
430	std::vector<uint8_t> fec_buf(share_size);	769✔
431
432	for(size_t i = m_K; i != m_N; ++i) {	3,052✔
433	linear_combination(fec_buf.data(), shares.data(), &m_enc_matrix[i * m_K], m_K, share_size);	2,283✔
434	output_cb(i, fec_buf.data(), fec_buf.size());	4,566✔
435	}
436	}	769✔
437
438	/*
439	* ZFEC decoding routine
440	*/
441	void ZFEC::decode_shares(const std::map<size_t, const uint8_t*>& shares,	92,252✔
442	size_t share_size,
443	const output_cb_t& output_cb) const {
444	/*
445	Todo:
446	If shares.size() < K:
447	signal decoding error for missing shares < K
448	emit existing shares < K
449	(ie, partial recovery if possible)
450	Assert share_size % K == 0
451	*/
452
453	if(shares.size() < m_K) {	92,252✔
454	throw Decoding_Error("ZFEC: could not decode, less than K surviving shares");	×
455	}
456
457	std::vector<uint8_t> decoding_matrix(m_K * m_K);	92,252✔
458	std::vector<size_t> indexes(m_K);	92,252✔
459	std::vector<const uint8_t*> sharesv(m_K);	92,252✔
460
461	auto shares_b_iter = shares.begin();	92,252✔
462	auto shares_e_iter = shares.rbegin();	92,252✔
463
464	bool missing_primary_share = false;	92,252✔
465
466	for(size_t i = 0; i != m_K; ++i) {	446,005✔
467	size_t share_id = 0;	353,753✔
468	const uint8_t* share_data = nullptr;	353,753✔
469
470	if(shares_b_iter->first == i) {	353,753✔
471	share_id = shares_b_iter->first;	194,706✔
472	share_data = shares_b_iter->second;	194,706✔
473	++shares_b_iter;	194,706✔
474	} else {
475	// if share i not found, use the unused one closest to n
476	share_id = shares_e_iter->first;	159,047✔
477	share_data = shares_e_iter->second;	159,047✔
478	++shares_e_iter;	159,047✔
479	missing_primary_share = true;	159,047✔
480	}
481
482	if(share_id >= m_N) {	353,753✔
483	throw Decoding_Error("ZFEC: invalid share id detected during decode");	×
484	}
485
486	/*
487	This is a systematic code (encoding matrix includes K*K identity
488	matrix), so shares less than K are copies of the input data,
489	can output_cb directly. Also we know the encoding matrix in those rows
490	contains I, so we can set the single bit directly without copying
491	the entire row
492	*/
493	if(share_id < m_K) {	353,753✔
494	decoding_matrix[i * (m_K + 1)] = 1;	194,706✔
495	output_cb(share_id, share_data, share_size);	389,412✔
496	} else {
497	// will decode after inverting matrix
498	std::memcpy(&decoding_matrix[i * m_K], &m_enc_matrix[share_id * m_K], m_K);	159,047✔
499	}
500
501	sharesv[i] = share_data;	353,753✔
502	indexes[i] = share_id;	353,753✔
503	}
504
505	// If we had the original data shares then no need to perform
506	// a matrix inversion, return immediately.
507	if(!missing_primary_share) {	92,252✔
508	for(const size_t index : indexes) {	21,273✔
509	BOTAN_ASSERT_NOMSG(index < m_K);	16,723✔
510	}
511	return;	4,550✔
512	}
513
514	invert_matrix(decoding_matrix.data(), m_K);	87,702✔
515
516	for(size_t i = 0; i != indexes.size(); ++i) {	424,732✔
517	if(indexes[i] >= m_K) {	337,030✔
518	std::vector<uint8_t> buf(share_size);	159,047✔
519	linear_combination(buf.data(), sharesv.data(), &decoding_matrix[i * m_K], m_K, share_size);	159,047✔
520	output_cb(i, buf.data(), share_size);	159,047✔
521	}	159,047✔
522	}
523	}	184,504✔
524
525	std::string ZFEC::provider() const {	243✔
526	#if defined(BOTAN_HAS_ZFEC_GFNI)
527	if(auto feat = CPUID::check(CPUID::Feature::AVX512, CPUID::Feature::GFNI)) {	243✔
528	return *feat;	×
529	}	×
530	#endif
531
532	#if defined(BOTAN_HAS_ZFEC_VPERM)
533	if(auto feat = CPUID::check(CPUID::Feature::SIMD_4X32)) {	243✔
534	return *feat;	162✔
535	}	81✔
536	#endif
537
538	return "base";	162✔
539	}
540
541	} // namespace Botan

randombit / botan / 29801022385

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous