From c845b66d8b17513b64acac9e74d20631a68e22b1 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 7 Nov 2015 15:03:18 +0100 Subject: Merging upstream version 1.6~pre3. Signed-off-by: Daniel Baumann --- encoder.c | 106 +++++++++++++++++++++++++------------------------------------- 1 file changed, 43 insertions(+), 63 deletions(-) (limited to 'encoder.c') diff --git a/encoder.c b/encoder.c index 3a22a25..3c28c4b 100644 --- a/encoder.c +++ b/encoder.c @@ -231,36 +231,6 @@ static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pair } -static void Lee_encode( struct Len_encoder * const le, - struct Range_encoder * const renc, - int symbol, const int pos_state ) - { - symbol -= min_match_len; - if( symbol < len_low_symbols ) - { - Re_encode_bit( renc, &le->lm.choice1, 0 ); - Re_encode_tree( renc, le->lm.bm_low[pos_state], symbol, len_low_bits ); - } - else - { - Re_encode_bit( renc, &le->lm.choice1, 1 ); - if( symbol < len_low_symbols + len_mid_symbols ) - { - Re_encode_bit( renc, &le->lm.choice2, 0 ); - Re_encode_tree( renc, le->lm.bm_mid[pos_state], - symbol - len_low_symbols, len_mid_bits ); - } - else - { - Re_encode_bit( renc, &le->lm.choice2, 1 ); - Re_encode_tree( renc, le->lm.bm_high, - symbol - len_low_symbols - len_mid_symbols, len_high_bits ); - } - } - if( --le->counters[pos_state] <= 0 ) Lee_update_prices( le, pos_state ); - } - - /* End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) */ static bool LZe_full_flush( struct LZ_encoder * const e, const State state ) { @@ -298,16 +268,7 @@ static bool LZe_sync_flush( struct LZ_encoder * const e ) } -static void LZe_fill_align_prices( struct LZ_encoder * const e ) - { - int i; - for( i = 0; i < dis_align_size; ++i ) - e->align_prices[i] = price_symbol_reversed( e->bm_align, i, dis_align_bits ); - e->align_price_count = dis_align_size; - } - - -static void LZe_fill_distance_prices( struct LZ_encoder * const e ) +static void LZe_update_distance_prices( struct LZ_encoder * const e ) { int dis, len_state; for( dis = start_dis_model; dis < modeled_distances; ++dis ) @@ -364,12 +325,15 @@ static bool LZe_init( struct LZ_encoder * const e, e->matchfinder = mf; if( !Re_init( &e->renc ) ) return false; - Lee_init( &e->match_len_encoder, mf->match_len_limit ); - Lee_init( &e->rep_len_encoder, mf->match_len_limit ); + Lm_init( &e->match_len_model ); + Lm_init( &e->rep_len_model ); + Lp_init( &e->match_len_prices, &e->match_len_model, mf->match_len_limit ); + Lp_init( &e->rep_len_prices, &e->rep_len_model, mf->match_len_limit ); for( i = 0; i < num_rep_distances; ++i ) e->reps[i] = 0; - e->align_price_count = 0; e->num_dis_slots = 2 * real_bits( mf->dictionary_size - 1 ); - e->fill_counter = 0; + e->price_counter = 0; + e->dis_price_counter = 0; + e->align_price_counter = 0; e->state = 0; e->member_finished = false; @@ -382,6 +346,7 @@ static bool LZe_init( struct LZ_encoder * const e, /* Return value == number of bytes advanced (ahead). trials[0]..trials[ahead-1] contain the steps to encode. ( trials[0].dis == -1 ) means literal. + A match/rep longer or equal than match_len_limit finishes the sequence. */ static int LZe_sequence_optimizer( struct LZ_encoder * const e, const int reps[num_rep_distances], @@ -468,7 +433,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, for( len = min_match_len; len <= replens[rep]; ++len ) Tr_update( &e->trials[len], price + - Lee_price( &e->rep_len_encoder, len, pos_state ), rep, 0 ); + Lp_price( &e->rep_len_prices, len, pos_state ), rep, 0 ); } if( main_len > replens[0] ) @@ -487,8 +452,6 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, } } - if( !Mf_move_pos( e->matchfinder ) ) return 0; - while( true ) /* price optimization loop */ { struct Trial *cur_trial, *next_trial; @@ -498,6 +461,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, State cur_state; uint8_t prev_byte, cur_byte, match_byte; + if( !Mf_move_pos( e->matchfinder ) ) return 0; if( ++cur >= num_trials ) /* no more initialized trials */ { LZe_backward( e, cur ); @@ -557,7 +521,6 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, prev_byte = Mf_peek( e->matchfinder, 1 ); cur_byte = Mf_peek( e->matchfinder, 0 ); match_byte = Mf_peek( e->matchfinder, cur_trial->reps[0] + 1 ); - if( !Mf_move_pos( e->matchfinder ) ) return 0; next_price = cur_trial->price + price0( e->bm_match[cur_state][pos_state] ); @@ -587,7 +550,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, } } - available_bytes = min( Mf_available_bytes( e->matchfinder ) + 1, + available_bytes = min( Mf_available_bytes( e->matchfinder ), max_num_trials - 1 - cur ); if( available_bytes < min_match_len ) continue; @@ -596,7 +559,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, /* try literal + rep0 */ if( match_byte != cur_byte && next_trial->prev_index != cur ) { - const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1; + const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ); const int dis = cur_trial->reps[0] + 1; const int limit = min( e->matchfinder->match_len_limit + 1, available_bytes ); @@ -619,7 +582,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, /* try rep distances */ for( rep = 0; rep < num_rep_distances; ++rep ) { - const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1; + const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ); int price; const int dis = cur_trial->reps[rep] + 1; @@ -631,7 +594,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, price = rep_match_price + LZe_price_rep( e, rep, cur_state, pos_state ); for( i = min_match_len; i <= len; ++i ) Tr_update( &e->trials[cur+i], price + - Lee_price( &e->rep_len_encoder, i, pos_state ), rep, cur ); + Lp_price( &e->rep_len_prices, i, pos_state ), rep, cur ); if( rep == 0 ) start_len = len + 1; /* discard shorter matches */ @@ -647,7 +610,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, pos_state2 = ( pos_state + len ) & pos_state_mask; state2 = St_set_rep( cur_state ); - price += Lee_price( &e->rep_len_encoder, len, pos_state ) + + price += Lp_price( &e->rep_len_prices, len, pos_state ) + price0( e->bm_match[state2][pos_state2] ) + LZe_price_matched( e, data[len-1], data[len], data[len-dis] ); pos_state2 = ( pos_state2 + 1 ) & pos_state_mask; @@ -683,7 +646,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, /* try match + literal + rep0 */ if( len == e->pairs[i].len ) { - const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1; + const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ); const int dis2 = dis + 1; int len2 = len + 1; const int limit = min( e->matchfinder->match_len_limit + len2, @@ -718,7 +681,10 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const e, static bool LZe_encode_member( struct LZ_encoder * const e ) { - const int fill_count = ( e->matchfinder->match_len_limit > 12 ) ? 128 : 512; + const bool best = ( e->matchfinder->match_len_limit > 12 ); + const int dis_price_count = best ? 1 : 512; + const int align_price_count = best ? 1 : dis_align_size; + const int price_count = ( e->matchfinder->match_len_limit > 36 ) ? 1024 : 4096; int ahead, i; State * const state = &e->state; @@ -733,12 +699,13 @@ static bool LZe_encode_member( struct LZ_encoder * const e ) !Mf_finished( e->matchfinder ) ) /* encode first byte */ { const uint8_t prev_byte = 0; - const uint8_t cur_byte = Mf_peek( e->matchfinder, 0 ); + uint8_t cur_byte; if( !Mf_enough_available_bytes( e->matchfinder ) || !Re_enough_free_bytes( &e->renc ) ) return true; - CRC32_update_byte( &e->crc, cur_byte ); + cur_byte = Mf_peek( e->matchfinder, 0 ); Re_encode_bit( &e->renc, &e->bm_match[*state][0], 0 ); LZe_encode_literal( e, prev_byte, cur_byte ); + CRC32_update_byte( &e->crc, cur_byte ); Mf_get_match_pairs( e->matchfinder, 0 ); if( !Mf_move_pos( e->matchfinder ) ) return false; } @@ -747,15 +714,24 @@ static bool LZe_encode_member( struct LZ_encoder * const e ) { if( !Mf_enough_available_bytes( e->matchfinder ) || !Re_enough_free_bytes( &e->renc ) ) return true; - if( e->pending_num_pairs == 0 ) + if( e->price_counter <= 0 && e->pending_num_pairs == 0 ) { - if( e->fill_counter <= 0 ) - { LZe_fill_distance_prices( e ); e->fill_counter = fill_count; } - if( e->align_price_count <= 0 ) LZe_fill_align_prices( e ); + e->price_counter = price_count; /* recalculate prices every these bytes */ + if( e->dis_price_counter <= 0 ) + { e->dis_price_counter = dis_price_count; LZe_update_distance_prices( e ); } + if( e->align_price_counter <= 0 ) + { + e->align_price_counter = align_price_count; + for( i = 0; i < dis_align_size; ++i ) + e->align_prices[i] = price_symbol_reversed( e->bm_align, i, dis_align_bits ); + } + Lp_update_prices( &e->match_len_prices ); + Lp_update_prices( &e->rep_len_prices ); } ahead = LZe_sequence_optimizer( e, e->reps, *state ); if( ahead <= 0 ) return false; /* can't happen */ + e->price_counter -= ahead; for( i = 0; ahead > 0; ) { @@ -802,14 +778,18 @@ static bool LZe_encode_member( struct LZ_encoder * const e ) if( len == 1 ) *state = St_set_short_rep( *state ); else { - Lee_encode( &e->rep_len_encoder, &e->renc, len, pos_state ); + Re_encode_len( &e->renc, &e->rep_len_model, len, pos_state ); + Lp_decrement_counter( &e->rep_len_prices, pos_state ); *state = St_set_rep( *state ); } } else /* match */ { LZe_encode_pair( e, dis - num_rep_distances, len, pos_state ); - --e->fill_counter; + if( get_slot( dis - num_rep_distances ) >= end_dis_model ) + --e->align_price_counter; + --e->dis_price_counter; + Lp_decrement_counter( &e->match_len_prices, pos_state ); *state = St_set_match( *state ); } } -- cgit v1.2.3