Botan::ZFEC Class Reference

#include <zfec.h>

Public Types
typedef std::function< void(size_t, const uint8_t[], size_t)>	output_cb_t

Public Member Functions
void	decode_shares (const std::map< size_t, const uint8_t * > &shares, size_t share_size, const output_cb_t &output_cb) const
void	encode (const uint8_t input[], size_t size, const output_cb_t &output_cb) const
void	encode_shares (const std::vector< const uint8_t * > &shares, size_t share_size, const output_cb_t &output_cb) const
size_t	generated_shares () const
std::string	provider () const
size_t	recovery_threshold () const
	ZFEC (size_t K, size_t N)

Detailed Description

A forward error correction code compatible with the zfec library (https://github.com/tahoe-lafs/zfec)

This algorithm is not constant time and is likely succeptible to side channels. Do not use this class to encode information that should be kept secret. (If nothing else, because the first K shares are simply the original input!)

Definition at line 30 of file zfec.h.

Member Typedef Documentation

output_cb_t

typedef std::function<void(size_t, const uint8_t[], size_t)> Botan::ZFEC::output_cb_t

Definition at line 32 of file zfec.h.

Constructor & Destructor Documentation

ZFEC()

Botan::ZFEC::ZFEC	(	size_t	K,
		size_t	N )

FEC constructor

Parameters

K	the number of shares needed for recovery
N	the number of shares generated

Definition at line 355 of file zfec.cpp.

                             : 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[0], 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;
      }
   }
}

Member Function Documentation

decode_shares()

void Botan::ZFEC::decode_shares	(	const std::map< size_t, const uint8_t * > &	shares,
		size_t	share_size,
		const output_cb_t &	output_cb ) const

Parameters

shares	map of share id to share contents
share_size	size in bytes of each share
output_cb	the output callback

Definition at line 442 of file zfec.cpp.

                                                             {
   /*
   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(size_t i = 0; i != indexes.size(); ++i) {
         BOTAN_ASSERT_NOMSG(indexes[i] < m_K);
      }
      return;
   }
 
   invert_matrix(&decoding_matrix[0], m_K);
 
   for(size_t i = 0; i != indexes.size(); ++i) {
      if(indexes[i] >= m_K) {
         std::vector<uint8_t> buf(share_size);
         for(size_t col = 0; col != m_K; ++col) {
            addmul(&buf[0], sharesv[col], decoding_matrix[i * m_K + col], share_size);
         }
         output_cb(i, &buf[0], share_size);
      }
   }
}

References BOTAN_ASSERT_NOMSG.

Referenced by botan_zfec_decode().

encode()

void Botan::ZFEC::encode	(	const uint8_t	input[],
		size_t	size,
		const output_cb_t &	output_cb ) const

Parameters

input	the data to FEC
size	the length in bytes of input
output_cb	the output callback

Definition at line 399 of file zfec.cpp.

                                                                                        {
   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);
}

References encode_shares().

Referenced by botan_zfec_encode().

encode_shares()

void Botan::ZFEC::encode_shares	(	const std::vector< const uint8_t * > &	shares,
		size_t	share_size,
		const output_cb_t &	output_cb ) const

Parameters

shares	exactly K shares of data to FEC
share_size	the length in bytes of each share
output_cb	the output callback

Definition at line 414 of file zfec.cpp.

                                                             {
   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) {
      clear_mem(fec_buf.data(), fec_buf.size());
 
      for(size_t j = 0; j != m_K; ++j) {
         addmul(&fec_buf[0], shares[j], m_enc_matrix[i * m_K + j], share_size);
      }
 
      output_cb(i, &fec_buf[0], fec_buf.size());
   }
}

References Botan::clear_mem().

Referenced by encode().

generated_shares()

size_t Botan::ZFEC::generated_shares ( ) const

inline

Definition at line 43 of file zfec.h.

{ return m_N; }

provider()

std::string Botan::ZFEC::provider

(

)

const

Definition at line 528 of file zfec.cpp.

                               {
#if defined(BOTAN_HAS_ZFEC_VPERM)
   if(CPUID::has_vperm()) {
      return "vperm";
   }
#endif
 
#if defined(BOTAN_HAS_ZFEC_SSE2)
   if(CPUID::has_sse2()) {
      return "sse2";
   }
#endif
 
   return "base";
}

References Botan::CPUID::has_vperm().

recovery_threshold()

size_t Botan::ZFEC::recovery_threshold ( ) const

inline

Definition at line 41 of file zfec.h.

{ return m_K; }

---

The documentation for this class was generated from the following files:

• src/lib/misc/zfec/zfec.h
• src/lib/misc/zfec/zfec.cpp