diff options
Diffstat (limited to '')
| -rw-r--r-- | encoder.h | 123 |
1 files changed, 79 insertions, 44 deletions
@@ -16,7 +16,7 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -enum { max_num_trials = 1 << 12, +enum { max_num_trials = 1 << 13, price_shift_bits = 6, price_step_bits = 2, price_step = 1 << price_step_bits }; @@ -59,19 +59,18 @@ class Prob_prices public: void init() { - for( int i = price_step / 2; i < bit_model_total; i += price_step ) + for( int i = 0; i < bit_model_total >> price_step_bits; ++i ) { - unsigned val = i; - int bits = 0; // base 2 logarithm of val + unsigned val = ( i * price_step ) + ( price_step / 2 ); + 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; + bits += 15; // remaining bits in val + data[i] = ( bit_model_total_bits << price_shift_bits ) - bits; } } @@ -268,7 +267,7 @@ public: } int match_len_limit() const { return match_len_limit_; } - int get_match_pairs( struct Pair * pairs = 0 ); + int get_match_pairs( Pair * pairs = 0 ); }; @@ -419,42 +418,80 @@ public: } while( symbol < 0x10000 ); } + + void encode_len( Len_model & lm, int symbol, const int pos_state ) + { + symbol -= min_match_len; + bool bit = ( symbol >= len_low_symbols ); + encode_bit( lm.choice1, bit ); + if( !bit ) + encode_tree3( lm.bm_low[pos_state], symbol ); + else + { + bit = ( symbol >= len_low_symbols + len_mid_symbols ); + encode_bit( lm.choice2, bit ); + if( !bit ) + encode_tree3( lm.bm_mid[pos_state], symbol - len_low_symbols ); + else + encode_tree8( lm.bm_high, symbol - len_low_symbols - len_mid_symbols ); + } + } }; -class Len_encoder : public Len_model +class Len_prices { - int prices[pos_states][max_len_symbols]; + const Len_model & lm; const int len_symbols; + const int count; + int prices[pos_states][max_len_symbols]; int counters[pos_states]; - void update_prices( const int pos_state ) + void update_low_mid_prices( const int pos_state ) { + counters[pos_state] = count; int * const pps = prices[pos_state]; - int tmp = price0( choice1 ); + int tmp = price0( lm.choice1 ); int len = 0; for( ; len < len_low_symbols && len < len_symbols; ++len ) - pps[len] = tmp + price_symbol3( bm_low[pos_state], len ); - tmp = price1( choice1 ); + pps[len] = tmp + price_symbol3( lm.bm_low[pos_state], len ); + if( len >= len_symbols ) return; + tmp = price1( lm.choice1 ) + price0( lm.choice2 ); for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len ) - pps[len] = tmp + price0( choice2 ) + - price_symbol3( bm_mid[pos_state], len - len_low_symbols ); - for( ; len < len_symbols; ++len ) + pps[len] = tmp + + price_symbol3( lm.bm_mid[pos_state], len - len_low_symbols ); + } + + void update_high_prices() + { + const int tmp = price1( lm.choice1 ) + price1( lm.choice2 ); + for( int len = len_low_symbols + len_mid_symbols; len < len_symbols; ++len ) // using 4 slots per value makes "price" faster - prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = - tmp + price1( choice2 ) + - price_symbol8( bm_high, len - len_low_symbols - len_mid_symbols ); - counters[pos_state] = len_symbols; + prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = tmp + + price_symbol8( lm.bm_high, len - len_low_symbols - len_mid_symbols ); } public: - explicit Len_encoder( const int match_len_limit ) - : len_symbols( match_len_limit + 1 - min_match_len ) + Len_prices( const Len_model & m, const int match_len_limit ) + : + lm( m ), + len_symbols( match_len_limit + 1 - min_match_len ), + count( ( match_len_limit > 12 ) ? 1 : len_symbols ) { - for( int i = 0; i < pos_states; ++i ) update_prices( i ); + for( int i = 0; i < pos_states; ++i ) counters[i] = 0; } - void encode( Range_encoder & renc, int symbol, const int pos_state ); + void decrement_counter( const int pos_state ) { --counters[pos_state]; } + + void update_prices() + { + bool high_pending = false; + for( int pos_state = 0; pos_state < pos_states; ++pos_state ) + if( counters[pos_state] <= 0 ) + { update_low_mid_prices( pos_state ); high_pending = true; } + if( high_pending && len_symbols > len_low_symbols + len_mid_symbols ) + update_high_prices(); + } int price( const int symbol, const int pos_state ) const { return prices[pos_state][symbol - min_match_len]; } @@ -481,18 +518,15 @@ protected: Bit_model bm_align[dis_align_size]; Range_encoder renc; - Len_encoder match_len_encoder; - Len_encoder rep_len_encoder; + Len_model match_len_model; + Len_model rep_len_model; unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; } - LZ_encoder_base( const File_header & header, const int match_len_limit, - const int outfd ) + LZ_encoder_base( const File_header & header, const int outfd ) : crc_( 0xFFFFFFFFU ), - renc( outfd ), - match_len_encoder( match_len_limit ), - rep_len_encoder( match_len_limit ) + renc( outfd ) { for( int i = 0; i < File_header::size; ++i ) renc.put_byte( header.data[i] ); @@ -503,8 +537,8 @@ protected: int price_matched( const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte ) const - { return ::price_matched( bm_literal[get_lit_state(prev_byte)], - symbol, match_byte ); } + { return ::price_matched( bm_literal[get_lit_state(prev_byte)], symbol, + match_byte ); } void encode_literal( const uint8_t prev_byte, const uint8_t symbol ) { renc.encode_tree8( bm_literal[get_lit_state(prev_byte)], symbol ); } @@ -516,7 +550,7 @@ protected: void encode_pair( const unsigned dis, const int len, const int pos_state ) { - match_len_encoder.encode( renc, len, pos_state ); + renc.encode_len( match_len_model, len, pos_state ); const int dis_slot = get_slot( dis ); renc.encode_tree6( bm_dis_slot[get_len_state(len)], dis_slot ); @@ -584,18 +618,18 @@ class LZ_encoder : public LZ_encoder_base }; Matchfinder & matchfinder; + Len_prices match_len_prices; + Len_prices rep_len_prices; int pending_num_pairs; - struct Pair pairs[max_match_len+1]; + Pair pairs[max_match_len+1]; Trial trials[max_num_trials]; - int dis_prices[len_states][modeled_distances]; int dis_slot_prices[len_states][2*max_dictionary_bits]; + int dis_prices[len_states][modeled_distances]; int align_prices[dis_align_size]; - int align_price_count; const int num_dis_slots; - void fill_align_prices(); - void fill_distance_prices(); + void update_distance_prices(); // move-to-front dis in/into reps if( dis > 0 ) static void mtf_reps( const int dis, int reps[num_rep_distances] ) @@ -636,12 +670,12 @@ class LZ_encoder : public LZ_encoder_base int price_rep0_len( const int len, const State state, const int pos_state ) const { return price_rep( 0, state, pos_state ) + - rep_len_encoder.price( len, pos_state ); + rep_len_prices.price( len, pos_state ); } int price_pair( const int dis, const int len, const int pos_state ) const { - const int price = match_len_encoder.price( len, pos_state ); + const int price = match_len_prices.price( len, pos_state ); const int len_state = get_len_state( len ); if( dis < modeled_distances ) return price + dis_prices[len_state][dis]; @@ -709,10 +743,11 @@ class LZ_encoder : public LZ_encoder_base public: LZ_encoder( Matchfinder & mf, const File_header & header, const int outfd ) : - LZ_encoder_base( header, mf.match_len_limit(), outfd ), + LZ_encoder_base( header, outfd ), matchfinder( mf ), + match_len_prices( match_len_model, mf.match_len_limit() ), + rep_len_prices( rep_len_model, mf.match_len_limit() ), pending_num_pairs( 0 ), - align_price_count( 0 ), num_dis_slots( 2 * real_bits( mf.dictionary_size() - 1 ) ) {} |