diff options
Diffstat (limited to 'fast_encoder.h')
| -rw-r--r-- | fast_encoder.h | 156 |
1 files changed, 26 insertions, 130 deletions
diff --git a/fast_encoder.h b/fast_encoder.h index 188eb92..ce5bae5 100644 --- a/fast_encoder.h +++ b/fast_encoder.h @@ -1,5 +1,5 @@ /* Lzip - Data compressor based on the LZMA algorithm - Copyright (C) 2008, 2009, 2010, 2011 Antonio Diaz Diaz. + Copyright (C) 2008, 2009, 2010, 2011, 2012 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 @@ -15,157 +15,53 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -class Fmatchfinder +class Fmatchfinder : public Matchfinder_base { - enum { // bytes to keep in buffer before dictionary - before_size = max_match_len + 1, - // bytes to keep in buffer after pos - after_size = max_match_len, - num_prev_positions = 1 << 16 }; + enum { before = max_match_len + 1, + dict_size = 65536, + dict_factor = 16, + len_limit = 16, + num_prev_pos = 1 << 16, + pos_array_factor = 1 }; - long long partial_data_pos; - uint8_t * buffer; // input buffer - int32_t * const prev_positions; // last seen position of key - int32_t * prev_pos_chain; - int dictionary_size_; // bytes to keep in buffer before pos - int buffer_size; - int pos; // current pos in buffer - int cyclic_pos; // current pos in dictionary int key4; // key made from latest 4 bytes - int stream_pos; // first byte not yet read from file - int pos_limit; // when reached, a new block must be read - const int match_len_limit_; - const int infd; // input file descriptor - bool at_stream_end; // stream_pos shows real end of file - - bool read_block(); public: - Fmatchfinder( const int ifd ); - - ~Fmatchfinder() - { delete[] prev_pos_chain; delete[] prev_positions; std::free( buffer ); } - - uint8_t operator[]( const int i ) const throw() { return buffer[pos+i]; } - int available_bytes() const throw() { return stream_pos - pos; } - long long data_position() const throw() { return partial_data_pos + pos; } - int dictionary_size() const throw() { return dictionary_size_; } - bool finished() const throw() { return at_stream_end && pos >= stream_pos; } - int match_len_limit() const throw() { return match_len_limit_; } - const uint8_t * ptr_to_current_pos() const throw() { return buffer + pos; } - - int true_match_len( const int index, const int distance, int len_limit ) const throw() - { - if( index + len_limit > available_bytes() ) - len_limit = available_bytes() - index; - const uint8_t * const data = buffer + pos + index - distance; - int i = 0; - while( i < len_limit && data[i] == data[i+distance] ) ++i; - return i; - } - - void reset(); - void move_pos(); + explicit Fmatchfinder( const int ifd ) + : + Matchfinder_base( before, dict_size, dict_factor, len_limit, + num_prev_pos, ifd, pos_array_factor ), + key4( 0 ) + {} + + void reset() { Matchfinder_base::reset(); key4 = 0; } int longest_match_len( int * const distance ) throw(); void longest_match_len() throw(); }; -class FLZ_encoder +class FLZ_encoder : public LZ_encoder_base { - enum { max_marker_size = 16, - num_rep_distances = 4 }; // must be 4 - - uint32_t crc_; - - Bit_model bm_match[State::states][pos_states]; - Bit_model bm_rep[State::states]; - Bit_model bm_rep0[State::states]; - Bit_model bm_rep1[State::states]; - Bit_model bm_rep2[State::states]; - Bit_model bm_len[State::states][pos_states]; - Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits]; - Bit_model bm_dis[modeled_distances-end_dis_model+1]; - Bit_model bm_align[dis_align_size]; - Fmatchfinder & fmatchfinder; - Range_encoder range_encoder; - Len_encoder len_encoder; - Len_encoder rep_match_len_encoder; - Literal_encoder literal_encoder; - - const int num_dis_slots; - int match_distance; - - uint32_t crc() const throw() { return crc_ ^ 0xFFFFFFFFU; } - // move-to-front dis in/into reps - void mtf_reps( const int dis, int reps[num_rep_distances] ) throw() - { - if( dis >= num_rep_distances ) - { - for( int i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1]; - reps[0] = dis - num_rep_distances; - } - else if( dis > 0 ) - { - const int distance = reps[dis]; - for( int i = dis; i > 0; --i ) reps[i] = reps[i-1]; - reps[0] = distance; - } - } - - void encode_pair( const uint32_t dis, const int len, const int pos_state ) throw() - { - len_encoder.encode( range_encoder, len, pos_state ); - const int dis_slot = dis_slots[dis]; - range_encoder.encode_tree( bm_dis_slot[get_dis_state(len)], dis_slot, dis_slot_bits ); - - if( dis_slot >= start_dis_model ) - { - const int direct_bits = ( dis_slot >> 1 ) - 1; - const uint32_t base = ( 2 | ( dis_slot & 1 ) ) << direct_bits; - const uint32_t direct_dis = dis - base; - - if( dis_slot < end_dis_model ) - range_encoder.encode_tree_reversed( bm_dis + base - dis_slot, - direct_dis, direct_bits ); - else - { - range_encoder.encode( direct_dis >> dis_align_bits, direct_bits - dis_align_bits ); - range_encoder.encode_tree_reversed( bm_align, direct_dis, dis_align_bits ); - } - } - } - - int read_match_distances() throw() - { - int len = fmatchfinder.longest_match_len( &match_distance ); - if( len == fmatchfinder.match_len_limit() ) - len += fmatchfinder.true_match_len( len, match_distance + 1, max_match_len - len ); - return len; - } - - void move_pos( int n, bool skip = false ) + void move_pos( int n ) { + if( --n >= 0 ) fmatchfinder.move_pos(); while( --n >= 0 ) { - if( skip ) skip = false; - else fmatchfinder.longest_match_len(); + fmatchfinder.longest_match_len(); fmatchfinder.move_pos(); } } - int sequence_optimizer( const int reps[num_rep_distances], - int * const disp, const State & state ); - - void full_flush( const State & state ); + void sequence_optimizer( int reps[num_rep_distances], State & state ); public: - FLZ_encoder( Fmatchfinder & mf, const File_header & header, const int outfd ); + FLZ_encoder( Fmatchfinder & mf, const File_header & header, const int outfd ) + : + LZ_encoder_base( header, mf.dictionary_size(), mf.match_len_limit(), outfd ), + fmatchfinder( mf ) + {} bool encode_member( const long long member_size ); - - long long member_position() const throw() - { return range_encoder.member_position(); } }; |