From e9eff495255f6597233d54ad40ac1efe3f4d416f Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 7 Nov 2015 10:34:27 +0100 Subject: Merging upstream version 1.14. Signed-off-by: Daniel Baumann --- encoder.h | 345 +++++++++++++++++++++++++++++++++++--------------------------- 1 file changed, 195 insertions(+), 150 deletions(-) (limited to 'encoder.h') diff --git a/encoder.h b/encoder.h index 75250ca..da83a3c 100644 --- a/encoder.h +++ b/encoder.h @@ -1,5 +1,5 @@ /* Lzip - Data compressor based on the LZMA algorithm - Copyright (C) 2008, 2009, 2010, 2011, 2012 Antonio Diaz Diaz. + Copyright (C) 2008, 2009, 2010, 2011, 2012, 2013 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 @@ -16,17 +16,19 @@ */ enum { max_num_trials = 1 << 12, - price_shift = 6 }; + price_shift_bits = 6, + price_step_bits = 2, + price_step = 1 << price_step_bits }; class Dis_slots { - unsigned char data[1<<12]; + uint8_t data[1<<10]; public: void init() { for( int slot = 0; slot < 4; ++slot ) data[slot] = slot; - for( int i = 4, size = 2, slot = 4; slot < 24; slot += 2 ) + for( int i = 4, size = 2, slot = 4; slot < 20; slot += 2 ) { std::memset( &data[i], slot, size ); std::memset( &data[i+size], slot + 1, size ); @@ -35,51 +37,57 @@ public: } } - unsigned char table( const int dis ) const { return data[dis]; } - - int operator[]( const uint32_t dis ) const - { - if( dis < (1 << 12) ) return data[dis]; - if( dis < (1 << 23) ) return data[dis>>11] + 22; - return data[dis>>22] + 44; - } + uint8_t operator[]( const int dis ) const { return data[dis]; } }; extern Dis_slots dis_slots; +static inline uint8_t get_slot( const uint32_t dis ) + { + if( dis < (1 << 10) ) return dis_slots[dis]; + if( dis < (1 << 19) ) return dis_slots[dis>> 9] + 18; + if( dis < (1 << 28) ) return dis_slots[dis>>18] + 36; + return dis_slots[dis>>27] + 54; + } + class Prob_prices { - int data[bit_model_total >> 2]; + short data[bit_model_total >> price_step_bits]; public: void init() { - const int num_bits = ( bit_model_total_bits - 2 ); - int j = 1, end = 2; - data[0] = bit_model_total_bits << price_shift; - for( int i = num_bits - 1; i >= 0; --i, end <<= 1 ) + for( int i = price_step / 2; i < bit_model_total; i += price_step ) { - for( ; j < end; ++j ) - data[j] = ( i << price_shift ) + - ( ( (end - j) << price_shift ) >> ( num_bits - i - 1 ) ); + unsigned val = i; + int bits = 0; // base 2 logarithm of val + for( int j = 0; j < price_shift_bits; ++j ) + { + val = val * val; + bits <<= 1; + while( val >= 1 << 16 ) { val >>= 1; ++bits; } + } + bits += 15; // remaining bits in val + data[i >> price_step_bits] = + ( bit_model_total_bits << price_shift_bits ) - bits; } } int operator[]( const int probability ) const - { return data[probability >> 2]; } + { return data[probability >> price_step_bits]; } }; extern Prob_prices prob_prices; -inline int price0( const Bit_model & bm ) +inline int price0( const Bit_model bm ) { return prob_prices[bm.probability]; } -inline int price1( const Bit_model & bm ) - { return prob_prices[bit_model_total-bm.probability]; } +inline int price1( const Bit_model bm ) + { return prob_prices[bit_model_total - bm.probability]; } -inline int price_bit( const Bit_model & bm, const int bit ) +inline int price_bit( const Bit_model bm, const int bit ) { if( bit ) return price1( bm ); else return price0( bm ); } @@ -113,29 +121,22 @@ inline int price_symbol_reversed( const Bit_model bm[], int symbol, } -inline int price_matched( const Bit_model bm[], const int symbol, - const int match_byte ) +inline int price_matched( const Bit_model bm[], unsigned symbol, + unsigned match_byte ) { int price = 0; - int model = 1; - - for( int i = 7; i >= 0; --i ) - { - const int match_bit = ( match_byte >> i ) & 1; - int bit = ( symbol >> i ) & 1; - price += price_bit( bm[(match_bit<<8)+model+0x100], bit ); - model = ( model << 1 ) | bit; - if( match_bit != bit ) - { - while( --i >= 0 ) - { - bit = ( symbol >> i ) & 1; - price += price_bit( bm[model], bit ); - model = ( model << 1 ) | bit; - } - break; - } + unsigned mask = 0x100; + symbol |= 0x100; + + do { + match_byte <<= 1; + const unsigned match_bit = match_byte & mask; + symbol <<= 1; + const unsigned bit = symbol & 0x100; + price += price_bit( bm[match_bit+(symbol>>9)+mask], bit ); + mask &= ~(match_byte ^ symbol); // if( match_bit != bit ) mask = 0; } + while( symbol < 0x10000 ); return price; } @@ -149,37 +150,36 @@ class Matchfinder_base void operator=( const Matchfinder_base & ); // declared as private protected: - enum { after_size = max_match_len }; // bytes to keep in buffer after pos - - long long partial_data_pos; - int32_t * const prev_positions; // last seen position of key - uint8_t * buffer; // input buffer - int32_t * pos_array; // may be tree or chain - const int num_prev_positions; + unsigned long long partial_data_pos; + uint8_t * buffer; // input buffer + int32_t * prev_positions; // last seen position of key + int32_t * pos_array; // may be tree or chain const int before_size; // bytes to keep in buffer before dictionary const int match_len_limit_; - const int infd; // input file descriptor int buffer_size; int dictionary_size_; // bytes to keep in buffer before pos int pos; // current pos in buffer - int cyclic_pos; // current pos in dictionary + int cyclic_pos; // cycles through [0, dictionary_size] int pos_limit; // when reached, a new block must be read int stream_pos; // first byte not yet read from file + unsigned key4_mask; + int num_prev_positions; // size of prev_positions int pos_array_size; + const int infd; // input file descriptor bool at_stream_end; // stream_pos shows real end of file Matchfinder_base( const int before, const int dict_size, - const int dict_factor, const int len_limit, - const int num_prev_pos, const int ifd, - const int pos_array_factor ); + const int after_size, const int dict_factor, + const int match_len_limit, const int num_prev_positions23, + const int pos_array_factor, const int ifd ); ~Matchfinder_base() - { delete[] pos_array; std::free( buffer ); delete[] prev_positions; } + { delete[] prev_positions; std::free( buffer ); } public: uint8_t operator[]( const int i ) const { return buffer[pos+i]; } int available_bytes() const { return stream_pos - pos; } - long long data_position() const { return partial_data_pos + pos; } + unsigned long long data_position() const { return partial_data_pos + pos; } int dictionary_size() const { return dictionary_size_; } bool finished() const { return at_stream_end && pos >= stream_pos; } int match_len_limit() const { return match_len_limit_; } @@ -195,34 +195,43 @@ public: return i; } - void reset(); void move_pos() { - if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0; + if( ++cyclic_pos > dictionary_size_ ) cyclic_pos = 0; if( ++pos >= pos_limit ) normalize_pos(); } + + void reset(); + }; + + +struct Pair /* distance-length pair */ + { + int dis; + int len; }; class Matchfinder : public Matchfinder_base { - enum { before = max_num_trials + 1, + enum { before_size = max_num_trials + 1, + // bytes to keep in buffer after pos + after_size = ( 2 * max_match_len ) + 1, dict_factor = 2, - num_prev_positions4 = 1 << 20, - num_prev_positions3 = 1 << 18, - num_prev_positions2 = 1 << 16, - num_prev_pos = num_prev_positions4 + num_prev_positions3 + - num_prev_positions2, + num_prev_positions3 = 1 << 16, + num_prev_positions2 = 1 << 10, + num_prev_positions23 = num_prev_positions2 + num_prev_positions3, pos_array_factor = 2 }; const int cycles; public: - Matchfinder( const int dict_size, const int len_limit, const int ifd ) + Matchfinder( const int dict_size, const int match_len_limit, const int ifd ) : - Matchfinder_base( before, dict_size, dict_factor, len_limit, - num_prev_pos, ifd, pos_array_factor ), - cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 ) + Matchfinder_base( before_size, dict_size, after_size, dict_factor, + match_len_limit, num_prev_positions23, pos_array_factor, ifd ), + cycles( ( match_len_limit < max_match_len ) ? + 16 + ( match_len_limit / 2 ) : 256 ) {} bool dec_pos( const int ahead ) @@ -230,11 +239,11 @@ public: if( ahead < 0 || pos < ahead ) return false; pos -= ahead; cyclic_pos -= ahead; - if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_; + if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_ + 1; return true; } - int longest_match_len( int * const distances = 0 ); + int get_match_pairs( struct Pair * pairs = 0 ); }; @@ -242,7 +251,7 @@ class Range_encoder { enum { buffer_size = 65536 }; uint64_t low; - long long partial_member_pos; + unsigned long long partial_member_pos; uint8_t * const buffer; // output buffer int pos; // current pos in buffer uint32_t range; @@ -281,7 +290,7 @@ public: ~Range_encoder() { delete[] buffer; } - long long member_position() const + unsigned long long member_position() const { return partial_member_pos + pos + ff_count; } void flush() { for( int i = 0; i < 5; ++i ) shift_low(); } @@ -345,26 +354,20 @@ public: } } - void encode_matched( Bit_model bm[], int symbol, int match_byte ) + void encode_matched( Bit_model bm[], unsigned symbol, unsigned match_byte ) { - int model = 1; - for( int i = 7; i >= 0; --i ) - { - const int match_bit = ( match_byte >> i ) & 1; - int bit = ( symbol >> i ) & 1; - encode_bit( bm[(match_bit<<8)+model+0x100], bit ); - model = ( model << 1 ) | bit; - if( match_bit != bit ) - { - while( --i >= 0 ) - { - bit = ( symbol >> i ) & 1; - encode_bit( bm[model], bit ); - model = ( model << 1 ) | bit; - } - break; - } + unsigned mask = 0x100; + symbol |= 0x100; + + do { + match_byte <<= 1; + const unsigned match_bit = match_byte & mask; + symbol <<= 1; + const unsigned bit = symbol & 0x100; + encode_bit( bm[match_bit+(symbol>>9)+mask], bit ); + mask &= ~(match_byte ^ symbol); // if( match_bit != bit ) mask = 0; } + while( symbol < 0x10000 ); } }; @@ -401,8 +404,8 @@ class Len_encoder } public: - explicit Len_encoder( const int len_limit ) - : len_symbols( len_limit + 1 - min_match_len ) + explicit Len_encoder( const int match_len_limit ) + : len_symbols( match_len_limit + 1 - min_match_len ) { for( int i = 0; i < pos_states; ++i ) update_prices( i ); } @@ -415,33 +418,6 @@ public: }; -class Literal_encoder - { - Bit_model bm_literal[1<> ( 8 - literal_context_bits ) ); } - -public: - void encode( Range_encoder & range_encoder, - uint8_t prev_byte, uint8_t symbol ) - { range_encoder.encode_tree( bm_literal[lstate(prev_byte)], symbol, 8 ); } - - void encode_matched( Range_encoder & range_encoder, - uint8_t prev_byte, uint8_t symbol, uint8_t match_byte ) - { range_encoder.encode_matched( bm_literal[lstate(prev_byte)], - symbol, match_byte ); } - - int price_symbol( uint8_t prev_byte, uint8_t symbol ) const - { return ::price_symbol( bm_literal[lstate(prev_byte)], symbol, 8 ); } - - int price_matched( uint8_t prev_byte, uint8_t symbol, - uint8_t match_byte ) const - { return ::price_matched( bm_literal[lstate(prev_byte)], - symbol, match_byte ); } - }; - - class LZ_encoder_base { protected: @@ -450,6 +426,7 @@ protected: uint32_t crc_; + Bit_model bm_literal[1<= start_dis_model ) @@ -511,7 +503,7 @@ protected: const uint32_t direct_dis = dis - base; if( dis_slot < end_dis_model ) - range_encoder.encode_tree_reversed( bm_dis + base - dis_slot, + range_encoder.encode_tree_reversed( bm_dis + base - dis_slot - 1, direct_dis, direct_bits ); else { @@ -521,31 +513,58 @@ protected: } } - void full_flush( const long long data_position, const State state ); + void full_flush( const unsigned long long data_position, const State state ); public: - long long member_position() const { return range_encoder.member_position(); } + unsigned long long member_position() const + { return range_encoder.member_position(); } }; class LZ_encoder : public LZ_encoder_base { - enum { infinite_price = 0x0FFFFFFF }; + enum { infinite_price = 0x0FFFFFFF, + single_step_trial = -2, + dual_step_trial = -1 }; struct Trial { State state; - int dis; - int prev_index; // index of prev trial in trials[] int price; // dual use var; cumulative price, match length + int dis; // rep index or match distance + int prev_index; // index of prev trial in trials[] + int dis2; + int prev_index2; // -2 trial is single step + // -1 literal + rep0 + // >= 0 rep or match + literal + rep0 int reps[num_rep_distances]; - void update( const int d, const int p_i, const int pr ) - { if( pr < price ) { dis = d; prev_index = p_i; price = pr; } } + + void update( const int pr, const int d, const int p_i ) + { + if( pr < price ) + { price = pr; dis = d; prev_index = p_i; + prev_index2 = single_step_trial; } + } + + void update2( const int pr, const int d, const int p_i ) + { + if( pr < price ) + { price = pr; dis = d; prev_index = p_i; + prev_index2 = dual_step_trial; } + } + + void update3( const int pr, const int d, const int p_i, + const int d2, const int p_i2 ) + { + if( pr < price ) + { price = pr; dis = d; prev_index = p_i; + dis2 = d2; prev_index2 = p_i2; } + } }; Matchfinder & matchfinder; - int longest_match_found; - int match_distances[max_match_len+1]; + int pending_num_pairs; + struct Pair pairs[max_match_len+1]; Trial trials[max_num_trials]; int dis_slot_prices[max_dis_states][2*max_dictionary_bits]; @@ -556,12 +575,12 @@ class LZ_encoder : public LZ_encoder_base void fill_align_prices(); void fill_distance_prices(); - int price_rep_len1( const int pos_state, const State state ) const + int price_rep_len1( const State state, const int pos_state ) const { return price0( bm_rep0[state()] ) + price0( bm_len[state()][pos_state] ); } - int price_rep( const int rep, const int pos_state, const State state ) const + int price_rep( const int rep, const State state, const int pos_state ) const { if( rep == 0 ) return price0( bm_rep0[state()] ) + price1( bm_len[state()][pos_state] ); @@ -576,30 +595,41 @@ class LZ_encoder : public LZ_encoder_base return price; } + int price_rep0_len( const int len, const State state, const int pos_state ) const + { + return price_rep( 0, state, pos_state ) + + rep_match_len_encoder.price( len, pos_state ); + } + int price_dis( const int dis, const int dis_state ) const { if( dis < modeled_distances ) return dis_prices[dis_state][dis]; else - return dis_slot_prices[dis_state][dis_slots[dis]] + + return dis_slot_prices[dis_state][get_slot( dis )] + align_prices[dis & (dis_align_size - 1)]; } int price_pair( const int dis, const int len, const int pos_state ) const { - if( len <= min_match_len && dis >= modeled_distances ) - return infinite_price; return len_encoder.price( len, pos_state ) + price_dis( dis, get_dis_state( len ) ); } int read_match_distances() { - int len = matchfinder.longest_match_len( match_distances ); - if( len == matchfinder.match_len_limit() && len < max_match_len ) - len += matchfinder.true_match_len( len, match_distances[len] + 1, - max_match_len - len ); - return len; + const int num_pairs = matchfinder.get_match_pairs( pairs ); + if( num_pairs > 0 ) + { + int len = pairs[num_pairs-1].len; + if( len == matchfinder.match_len_limit() && len < max_match_len ) + { + len += matchfinder.true_match_len( len, pairs[num_pairs-1].dis + 1, + max_match_len - len ); + pairs[num_pairs-1].len = len; + } + } + return num_pairs; } void move_pos( int n ) @@ -607,7 +637,7 @@ class LZ_encoder : public LZ_encoder_base if( --n >= 0 ) matchfinder.move_pos(); while( --n >= 0 ) { - matchfinder.longest_match_len(); + matchfinder.get_match_pairs(); matchfinder.move_pos(); } } @@ -619,6 +649,20 @@ class LZ_encoder : public LZ_encoder_base { const int prev_index = trials[cur].prev_index; Trial & prev_trial = trials[prev_index]; + + if( trials[cur].prev_index2 != single_step_trial ) + { + prev_trial.dis = -1; + prev_trial.prev_index = prev_index - 1; + prev_trial.prev_index2 = single_step_trial; + if( trials[cur].prev_index2 >= 0 ) + { + Trial & prev_trial2 = trials[prev_index-1]; + prev_trial2.dis = trials[cur].dis2; + prev_trial2.prev_index = trials[cur].prev_index2; + prev_trial2.prev_index2 = single_step_trial; + } + } prev_trial.price = cur - prev_index; // len cur = dis; dis = prev_trial.dis; prev_trial.dis = cur; cur = prev_index; @@ -633,8 +677,9 @@ public: : LZ_encoder_base( header, mf.dictionary_size(), mf.match_len_limit(), outfd ), matchfinder( mf ), - longest_match_found( 0 ) - { fill_align_prices(); } + pending_num_pairs( 0 ), + align_price_count( 0 ) + {} - bool encode_member( const long long member_size ); + bool encode_member( const unsigned long long member_size ); }; -- cgit v1.2.3