diff options
Diffstat (limited to 'fec.h')
| -rw-r--r-- | fec.h | 297 |
1 files changed, 297 insertions, 0 deletions
@@ -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 ); |