Adding upstream version 1.25~pre1.upstream/1.25_pre1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 297 insertions, 0 deletions

diff --git a/fec.h b/fec.h
new file mode 100644
index 0000000..6922362
--- /dev/null
+++ b/fec.h
@@ -0,0 +1,297 @@
+/* Lziprecover - Data recovery tool for the lzip format
+   Copyright (C) 2023-2024 Antonio Diaz Diaz.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation, either version 2 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.
+*/
+
+struct le32
+  {
+  enum { size = 4 };
+  uint8_t data[size];
+
+  le32 & operator=( unsigned n )
+    { for( int i = 0; i < size; ++i ) { data[i] = (uint8_t)n; n >>= 8; }
+      return *this; }
+  unsigned val() const
+    { unsigned n = 0;
+      for( int i = size - 1; i >= 0; --i ) { n <<= 8; n += data[i]; }
+      return n; }
+  bool operator==( const le32 & b ) const
+    { return std::memcmp( data, b.data, size ) == 0; }
+  bool operator!=( const le32 & b ) const { return !( *this == b ); }
+  };
+
+
+inline unsigned long long get_le( const uint8_t * const buf, int size )
+  { unsigned long long n = 0;
+    while( --size >= 0 ) { n <<= 8; n += buf[size]; } return n; }
+
+inline unsigned long long ceil_divide( const unsigned long long size,
+                                       const unsigned long block_size )
+  { return size / block_size + ( size % block_size > 0 ); }
+
+inline unsigned long ceil_divide( const unsigned long size,
+                                  const unsigned long block_size )
+  { return size / block_size + ( size % block_size > 0 ); }
+
+inline uint8_t * set_lastbuf( const uint8_t * const prodata,
+                   const unsigned long prodata_size, const unsigned long fbs,
+                   const bool last_is_missing = false )
+  {
+  const unsigned long rest = prodata_size % fbs;
+  if( rest == 0 ) return 0;		// last data block is complete
+  uint8_t * const lastbuf = new uint8_t[fbs];
+  if( last_is_missing ) return lastbuf;	// uninitialized buffer
+  std::memcpy( lastbuf, prodata + ( prodata_size - rest ), rest );
+  std::memset( lastbuf + rest, 0, fbs - rest );
+  return lastbuf;		// copy of last data block padded to fbs bytes
+  }
+
+enum { min_fbs = 512, max_unit_fbs = 1 << 30 };		//   1 GiB
+const unsigned long long max_fbs = 1ULL << 47;		// 128 TiB
+
+inline bool isvalid_fbs( const unsigned long long fbs )
+  { return fbs >= min_fbs && fbs <= max_fbs && fbs % min_fbs == 0; }
+
+struct Coded_fbs				// fec_block_size
+  {
+  enum { size = 2 };
+  uint8_t data[size];			// 11-bit mantissa, 5-bit exponent
+
+  Coded_fbs() {}				// default constructor
+  Coded_fbs( const unsigned long long fbs, const unsigned unit_fbs )
+    {
+    unsigned long long m = fbs;
+    int e = 0;
+    while( m > 2047 || ( m > 1 && e < 9 ) ) { m >>= 1; ++e; }
+    if( m << e < fbs && ++m > 2047 ) { m >>= 1; ++e; }
+    while( ( m << e ) % unit_fbs != 0 ) if( ++m > 2047 ) { m >>= 1; ++e; }
+    if( m == 0 || m > 2047 || e < 9 || e > 40 || m << e < fbs ||
+        !isvalid_fbs( m << e ) || !isvalid_fbs( fbs ) )
+      internal_error( "Coded_fbs: can't fit fec_block_size in packet." );
+    data[0] = m;
+    data[1] = ( e - 9 ) << 3 | m >> 8;
+    }
+
+  void copy( uint8_t * const buf ) const
+    { buf[0] = data[0]; buf[1] = data[1]; }
+
+  unsigned long long val() const
+    {
+    unsigned long long m = ( ( data[1] & 7 ) << 8 ) | data[0];
+    const int e = ( data[1] >> 3 ) + 9;
+    return m << e;
+    }
+  };
+
+enum { fec_magic_l = 4, crc32_l = le32::size };
+const uint8_t fec_magic[4] = { 0xB3, 0xA5, 0xB6, 0xAF };	// ~"LZIP"
+const uint8_t fec_packet_magic[4] = { fec_magic[0], 'F', 'E', 'C' };
+
+inline bool check_fec_magic( const uint8_t * const image_buffer )
+  { return std::memcmp( image_buffer, fec_magic, 4 ) == 0; }
+
+class Packet_base
+  {
+protected:
+  // the packet trailer contains the CRC32 of the payload
+  enum Lengths { trailer_size = crc32_l };
+
+  // header_size must be a multiple of 4 for uint32_t alignment in mul_add
+  const uint8_t * image_;		// header + payload + trailer
+  bool image_is_external;
+
+  Packet_base() : image_is_external( false ) {}
+  explicit Packet_base( const uint8_t * const image_buffer )
+    : image_( image_buffer ), image_is_external( true ) {}
+  ~Packet_base() { if( !image_is_external ) delete[] image_; }
+
+public:
+  const uint8_t * image() const { return image_; }
+  };
+
+
+class Chksum_packet : public Packet_base
+  {
+  enum { current_version = 0 };
+  enum Lengths { version_l = 1, flags_l = 1, prodata_size_l = 8,
+                 prodata_md5_l = 16 };
+  enum Offsets { version_o = fec_magic_l,
+                 flags_o = version_o + version_l,
+                 fbs_o = flags_o + flags_l,
+                 prodata_size_o = fbs_o + Coded_fbs::size,
+                 prodata_md5_o = prodata_size_o + prodata_size_l,
+                 header_crc_o = prodata_md5_o + prodata_md5_l,
+                 header_size = header_crc_o + crc32_l,
+                 crc_array_o = header_size };
+
+  static unsigned compute_header_crc( const uint8_t * const image_buffer )
+    { return crc32.compute_crc( image_buffer, header_crc_o ); }
+
+public:
+  // check image_buffer with check_image before calling this constructor
+  explicit Chksum_packet( const uint8_t * const image_buffer )
+    : Packet_base( image_buffer ) {}
+  Chksum_packet( const uint8_t * const prodata,
+                 const unsigned long prodata_size,
+                 const md5_type & prodata_md5, const Coded_fbs coded_fbs,
+                 const bool gf16_, const bool is_crc_c_ );
+
+  unsigned long long packet_size() const
+    { return ceil_divide( prodata_size(), fec_block_size() ) *
+             sizeof crc_array()[0] + header_size + trailer_size; }
+  unsigned long long prodata_size() const
+    { return get_le( image_ + prodata_size_o, prodata_size_l ); }
+  const md5_type & prodata_md5() const
+    { return *(md5_type *)(image_ + prodata_md5_o); }
+  unsigned long long fec_block_size() const
+    { return ((Coded_fbs *)(image_ + fbs_o))->val(); }
+  static bool check_flags( const uint8_t * const image_buffer )
+    { return image_buffer[flags_o] <= 3; }
+  bool gf16() const { return image_[flags_o] & 2; }
+  bool is_crc_c() const { return image_[flags_o] & 1; }
+  // crc_array contains one CRC32 or one CRC32-C per protected data block
+  const le32 * crc_array() const
+    { return (const le32 *)(image_ + crc_array_o); }
+
+  static unsigned min_packet_size()
+    { return header_size + le32::size + trailer_size; }
+  static uint8_t version( const uint8_t * const image_buffer )
+    { return image_buffer[version_o]; }
+  static bool check_version( const uint8_t * const image_buffer )
+    { return image_buffer[version_o] == current_version; }
+
+  static unsigned check_image( const uint8_t * const image_buffer,
+                               const unsigned long max_size );
+  bool check_payload_crc() const
+    {
+    const unsigned paysize = packet_size() - header_size - trailer_size;
+    const unsigned payload_crc_o = crc_array_o + paysize;
+    const unsigned payload_crc = get_le( image_ + payload_crc_o, crc32_l );
+    return crc32.compute_crc( image_ + crc_array_o, paysize ) == payload_crc;
+    }
+  };
+
+
+class Fec_packet : public Packet_base
+  {
+  enum Lengths { fbn_l = 2 };
+  enum Offsets { fbn_o = fec_magic_l,
+                 fbs_o = fbn_o + fbn_l,
+                 header_crc_o = fbs_o + Coded_fbs::size,
+                 header_size = header_crc_o + crc32_l,
+                 fec_block_o = header_size };
+
+  static unsigned compute_header_crc( const uint8_t * const image_buffer )
+    { return crc32.compute_crc( image_buffer, header_crc_o ); }
+
+public:
+  // check image_buffer with check_image before calling this constructor
+  explicit Fec_packet( const uint8_t * const image_buffer )
+    : Packet_base( image_buffer ) {}
+  Fec_packet( const uint8_t * const prodata, const uint8_t * const lastbuf,
+              const unsigned fbn, const unsigned k,
+              const Coded_fbs coded_fbs, const bool gf16 );
+
+  unsigned long long packet_size() const
+    { return header_size + fec_block_size() + trailer_size; }
+  unsigned fec_block_number() const
+    { return get_le( image_ + fbn_o, fbn_l ); }
+  unsigned long long fec_block_size() const	// number of fec bytes
+    { return ((Coded_fbs *)(image_ + fbs_o))->val(); }
+  const uint8_t * fec_block() const { return image_ + fec_block_o; }
+
+  static unsigned min_packet_size()
+    { return header_size + min_fbs + trailer_size; }
+
+  static unsigned long check_image( const uint8_t * const image_buffer,
+                                    const unsigned long max_size );
+  };
+
+
+enum { max_k8 = 128, max_k16 = 32768, max_nk16 = 2048 };
+const char * const fec_extension = ".fec";
+
+inline void prot_stdin()
+  { show_file_error( "(stdin)", "Can't read protected data from standard input." ); }
+
+// defined in fec_create.cc
+enum { fc_percent, fc_blocks, fc_bytes };
+void cleanup_mutex_lock();
+int gf_check( const unsigned k, const bool cl_gf16, const bool fec_random );
+void extract_dirname( const std::string & name, std::string & srcdir );
+void replace_dirname( const std::string & name, const std::string & srcdir,
+                      const std::string & destdir, std::string & outname );
+bool has_fec_extension( const std::string & name );
+const char * printable_name( const std::string & filename, const bool in = true );
+int fec_create( const std::vector< std::string > & filenames,
+                const std::string & default_output_filename,
+                const unsigned long fb_or_pct, const unsigned cl_block_size,
+                const unsigned num_workers, const char debug_level,
+                const char fctype, const char fec_level, const char recursive,
+                const bool cl_gf16, const bool fec_random, const bool force,
+                const bool to_stdout );
+
+// defined in fec_repair.cc
+int fec_test( const std::vector< std::string > & filenames,
+              const std::string & cl_fec_filename,
+              const std::string & default_output_filename,
+              const char recursive, const bool force, const bool ignore_errors,
+              const bool repair, const bool to_stdout );
+int fec_list( const std::vector< std::string > & filenames,
+              const bool ignore_errors );
+int fec_dc( const std::string & input_filename,
+            const std::string & cl_fec_filename, const unsigned cblocks );
+int fec_dz( const std::string & input_filename,
+            const std::string & cl_fec_filename,
+            std::vector< Block > & range_vector );
+int fec_dZ( const std::string & input_filename,
+            const std::string & cl_fec_filename,
+            const unsigned delta, const int sector_size );
+
+// defined in recursive.cc
+bool next_filename( std::list< std::string > & filelist,
+                    std::string & input_filename, int & retval,
+                    const char recursive );
+
+// defined in gf8.cc, gf16.cc
+void gf8_init();
+void gf16_init();
+bool gf8_check( const std::vector< unsigned > & fbn_vector, const unsigned k );
+bool gf16_check( const std::vector< unsigned > & fbn_vector, const unsigned k );
+
+/* buffer, lastbuf: k blocks of input data, last one possibly padded to fbs.
+   fbn: number of the fec block to be created (fbn < max_k).
+*/
+void rs8_encode( const uint8_t * const buffer, const uint8_t * const lastbuf,
+                 uint8_t * const fec_block, const unsigned long fbs,
+                 const unsigned fbn, const unsigned k );
+void rs16_encode( const uint8_t * const buffer, const uint8_t * const lastbuf,
+                  uint8_t * const fec_block, const unsigned long fbs,
+                  const unsigned fbn, const unsigned k );
+
+/* buffer, lastbuf: k data blocks, those in bb_vector are missing.
+   fecbuf: as many fec blocks as missing data blocks in the order of fbn_vector.
+   The repaired data blocks are written in their place in buffer and lastbuf.
+*/
+void rs8_decode( uint8_t * const buffer, uint8_t * const lastbuf,
+                 const std::vector< unsigned > & bb_vector,
+                 const std::vector< unsigned > & fbn_vector,
+                 uint8_t * const fecbuf, const unsigned long fbs,
+                 const unsigned k );
+void rs16_decode( uint8_t * const buffer, uint8_t * const lastbuf,
+                  const std::vector< unsigned > & bb_vector,
+                  const std::vector< unsigned > & fbn_vector,
+                  uint8_t * const fecbuf, const unsigned long fbs,
+                  const unsigned k );