diff options
Diffstat (limited to 'encoder.cc')
| -rw-r--r-- | encoder.cc | 498 |
1 files changed, 321 insertions, 177 deletions
@@ -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 @@ -69,45 +69,51 @@ void Matchfinder_base::normalize_pos() Matchfinder_base::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 ) : partial_data_pos( 0 ), - prev_positions( new int32_t[num_prev_pos] ), - num_prev_positions( num_prev_pos ), before_size( before ), - match_len_limit_( len_limit ), - infd( ifd ), + match_len_limit_( match_len_limit ), pos( 0 ), cyclic_pos( 0 ), stream_pos( 0 ), + infd( ifd ), at_stream_end( false ) { - for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1; const int buffer_size_limit = - ( dict_size * dict_factor ) + before_size + after_size; + ( dict_factor * dict_size ) + before_size + after_size; buffer_size = std::max( 65536, dict_size ); buffer = (uint8_t *)std::malloc( buffer_size ); - if( !buffer ) { delete[] prev_positions; throw std::bad_alloc(); } + if( !buffer ) throw std::bad_alloc(); if( read_block() && !at_stream_end && buffer_size < buffer_size_limit ) { buffer_size = buffer_size_limit; uint8_t * const tmp = (uint8_t *)std::realloc( buffer, buffer_size ); - if( !tmp ) - { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); } + if( !tmp ) { std::free( buffer ); throw std::bad_alloc(); } buffer = tmp; read_block(); } if( at_stream_end && stream_pos < dict_size ) dictionary_size_ = std::max( (int)min_dictionary_size, stream_pos ); - else dictionary_size_ = dict_size; + else + dictionary_size_ = dict_size; pos_limit = buffer_size; if( !at_stream_end ) pos_limit -= after_size; - pos_array_size = pos_array_factor * dictionary_size_; - pos_array = new( std::nothrow ) int32_t[pos_array_size]; - if( !pos_array ) - { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); } + int size = 1 << std::max( 16, real_bits( dictionary_size_ - 1 ) - 2 ); + if( dictionary_size_ > 1 << 26 ) + size >>= 1; + key4_mask = size - 1; + size += num_prev_positions23; + + num_prev_positions = size; + pos_array_size = pos_array_factor * ( dictionary_size_ + 1 ); + size += pos_array_size; + prev_positions = new( std::nothrow ) int32_t[size]; + if( !prev_positions ) { std::free( buffer ); throw std::bad_alloc(); } + pos_array = prev_positions + num_prev_positions; + for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1; } @@ -124,7 +130,7 @@ void Matchfinder_base::reset() } -int Matchfinder::longest_match_len( int * const distances ) +int Matchfinder::get_match_pairs( struct Pair * pairs ) { int len_limit = match_len_limit_; if( len_limit > available_bytes() ) @@ -134,28 +140,44 @@ int Matchfinder::longest_match_len( int * const distances ) } int maxlen = min_match_len - 1; - const int min_pos = (pos >= dictionary_size_) ? - (pos - dictionary_size_ + 1) : 0; + int num_pairs = 0; + const int min_pos = (pos > dictionary_size_) ? + pos - dictionary_size_ : 0; const uint8_t * const data = buffer + pos; - const int key2 = num_prev_positions4 + num_prev_positions3 + - ( ( (int)data[0] << 8 ) | data[1] ); - const uint32_t tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 ); - const int key3 = num_prev_positions4 + - (int)( tmp & ( num_prev_positions3 - 1 ) ); - const int key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) & - ( num_prev_positions4 - 1 ) ); - - if( distances ) + + unsigned tmp = crc32[data[0]] ^ data[1]; + const int key2 = tmp & ( num_prev_positions2 - 1 ); + tmp ^= (uint32_t)data[2] << 8; + const int key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) ); + const int key4 = num_prev_positions2 + num_prev_positions3 + + ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & key4_mask ); + + if( pairs ) { - int np = prev_positions[key2]; - if( np >= min_pos ) - { distances[2] = pos - np - 1; maxlen = 2; } - else distances[2] = 0x7FFFFFFF; - np = prev_positions[key3]; - if( np >= min_pos && buffer[np] == data[0] ) - { distances[3] = pos - np - 1; maxlen = 3; } - else distances[3] = 0x7FFFFFFF; - distances[4] = 0x7FFFFFFF; + int np2 = prev_positions[key2]; + int np3 = prev_positions[key3]; + if( np2 >= min_pos && buffer[np2] == data[0] ) + { + pairs[0].dis = pos - np2 - 1; + pairs[0].len = maxlen = 2; + num_pairs = 1; + } + if( np2 != np3 && np3 >= min_pos && buffer[np3] == data[0] ) + { + maxlen = 3; + pairs[num_pairs].dis = pos - np3 - 1; + ++num_pairs; + np2 = np3; + } + if( num_pairs > 0 ) + { + const int delta = pos - np2; + while( maxlen < len_limit && data[maxlen-delta] == data[maxlen] ) + ++maxlen; + pairs[num_pairs-1].len = maxlen; + if( maxlen >= len_limit ) pairs = 0; + } + if( maxlen < 3 ) maxlen = 3; } prev_positions[key2] = pos; @@ -170,46 +192,43 @@ int Matchfinder::longest_match_len( int * const distances ) for( int count = cycles; ; ) { if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; } - const uint8_t * const newdata = buffer + newpos; - while( len < len_limit && newdata[len] == data[len] ) ++len; const int delta = pos - newpos; - if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1; - int32_t * const newptr = pos_array + ( ( cyclic_pos - delta + - ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) ) << 1 ); - - if( len < len_limit ) + ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ + 1 ) ) << 1 ); + if( data[len-delta] == data[len] ) { - if( newdata[len] < data[len] ) + while( ++len < len_limit && data[len-delta] == data[len] ) {} + if( pairs && maxlen < len ) { - *ptr0 = newpos; - ptr0 = newptr + 1; - newpos = *ptr0; - len0 = len; if( len1 < len ) len = len1; + pairs[num_pairs].dis = delta - 1; + pairs[num_pairs].len = maxlen = len; + ++num_pairs; } - else + if( len >= len_limit ) { - *ptr1 = newpos; - ptr1 = newptr; - newpos = *ptr1; - len1 = len; if( len0 < len ) len = len0; + *ptr0 = newptr[0]; + *ptr1 = newptr[1]; + break; } } + if( data[len-delta] < data[len] ) + { + *ptr0 = newpos; + ptr0 = newptr + 1; + newpos = *ptr0; + len0 = len; if( len1 < len ) len = len1; + } else { - *ptr0 = newptr[0]; - *ptr1 = newptr[1]; - break; + *ptr1 = newpos; + ptr1 = newptr; + newpos = *ptr1; + len1 = len; if( len0 < len ) len = len0; } } - if( distances ) - { - if( distances[3] > distances[4] ) distances[3] = distances[4]; - if( distances[2] > distances[3] ) distances[2] = distances[3]; - } - return maxlen; + return num_pairs; } @@ -240,12 +259,14 @@ void Len_encoder::encode( Range_encoder & range_encoder, int symbol, if( symbol < len_low_symbols + len_mid_symbols ) { range_encoder.encode_bit( choice2, 0 ); - range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols, len_mid_bits ); + range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols, + len_mid_bits ); } else { range_encoder.encode_bit( choice2, 1 ); - range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols, len_high_bits ); + range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols, + len_high_bits ); } } if( --counters[pos_state] <= 0 ) update_prices( pos_state ); @@ -253,7 +274,7 @@ void Len_encoder::encode( Range_encoder & range_encoder, int symbol, // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) -void LZ_encoder_base::full_flush( const long long data_position, +void LZ_encoder_base::full_flush( const unsigned long long data_position, const State state ) { const int pos_state = data_position & pos_state_mask; @@ -283,11 +304,11 @@ void LZ_encoder::fill_distance_prices() { for( int dis = start_dis_model; dis < modeled_distances; ++dis ) { - const int dis_slot = dis_slots.table( dis ); + const int dis_slot = dis_slots[dis]; const int direct_bits = ( dis_slot >> 1 ) - 1; const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits; - const int price = - price_symbol_reversed( bm_dis + base - dis_slot, dis - base, direct_bits ); + const int price = price_symbol_reversed( bm_dis + base - dis_slot - 1, + dis - base, direct_bits ); for( int dis_state = 0; dis_state < max_dis_states; ++dis_state ) dis_prices[dis_state][dis] = price; } @@ -301,14 +322,14 @@ void LZ_encoder::fill_distance_prices() dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ); for( ; slot < num_dis_slots; ++slot ) dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) + - (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift ); + (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift_bits ); int * const dp = dis_prices[dis_state]; int dis = 0; for( ; dis < start_dis_model; ++dis ) dp[dis] = dsp[dis]; for( ; dis < modeled_distances; ++dis ) - dp[dis] += dsp[dis_slots.table( dis )]; + dp[dis] += dsp[dis_slots[dis]]; } } @@ -316,16 +337,20 @@ void LZ_encoder::fill_distance_prices() // Return value == number of bytes advanced (ahead). // trials[0]..trials[retval-1] contain the steps to encode. // ( trials[0].dis == -1 && trials[0].price == 1 ) means literal. +// int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], const State state ) { - int main_len; - if( longest_match_found > 0 ) // from previous call + int num_pairs, num_trials; + + if( pending_num_pairs > 0 ) // from previous call { - main_len = longest_match_found; - longest_match_found = 0; + num_pairs = pending_num_pairs; + pending_num_pairs = 0; } - else main_len = read_match_distances(); + else + num_pairs = read_match_distances(); + const int main_len = ( num_pairs > 0 ) ? pairs[num_pairs-1].len : 0; int replens[num_rep_distances]; int rep_index = 0; @@ -344,36 +369,34 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], if( main_len >= matchfinder.match_len_limit() ) { - trials[0].dis = match_distances[matchfinder.match_len_limit()] + - num_rep_distances; + trials[0].dis = pairs[num_pairs-1].dis + num_rep_distances; trials[0].price = main_len; move_pos( main_len ); return main_len; } - { const int pos_state = matchfinder.data_position() & pos_state_mask; const uint8_t prev_byte = matchfinder[-1]; const uint8_t cur_byte = matchfinder[0]; const uint8_t match_byte = matchfinder[-reps[0]-1]; trials[0].state = state; - for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i]; trials[1].dis = -1; - trials[1].prev_index = 0; trials[1].price = price0( bm_match[state()][pos_state] ); if( state.is_char() ) - trials[1].price += literal_encoder.price_symbol( prev_byte, cur_byte ); + trials[1].price += price_literal( prev_byte, cur_byte ); else - trials[1].price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte ); + trials[1].price += price_matched( prev_byte, cur_byte, match_byte ); const int match_price = price1( bm_match[state()][pos_state] ); const int rep_match_price = match_price + price1( bm_rep[state()] ); if( match_byte == cur_byte ) - trials[1].update( 0, 0, rep_match_price + price_rep_len1( pos_state, state ) ); + trials[1].update( rep_match_price + price_rep_len1( state, pos_state ), 0, 0 ); - if( main_len < min_match_len ) + num_trials = std::max( main_len, replens[rep_index] ); + + if( num_trials < min_match_len ) { trials[0].dis = trials[1].dis; trials[0].price = 1; @@ -381,71 +404,107 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], return 1; } - if( main_len <= replens[rep_index] ) + for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i]; + trials[1].prev_index = 0; + trials[1].prev_index2 = single_step_trial; + + for( int len = min_match_len; len <= num_trials; ++len ) + trials[len].price = infinite_price; + + for( int rep = 0; rep < num_rep_distances; ++rep ) { - main_len = replens[rep_index]; - for( int len = min_match_len; len <= main_len; ++len ) - trials[len].price = infinite_price; + if( replens[rep] < min_match_len ) continue; + const int price = rep_match_price + price_rep( rep, state, pos_state ); + for( int len = min_match_len; len <= replens[rep]; ++len ) + trials[len].update( price + rep_match_len_encoder.price( len, pos_state ), + rep, 0 ); } - else + + if( main_len > replens[0] ) { const int normal_match_price = match_price + price0( bm_rep[state()] ); - for( int len = min_match_len; len <= main_len; ++len ) + int i = 0, len = std::max( replens[0] + 1, (int)min_match_len ); + while( len > pairs[i].len ) ++i; + while( true ) { - trials[len].dis = match_distances[len] + num_rep_distances; - trials[len].prev_index = 0; - trials[len].price = normal_match_price + - price_pair( match_distances[len], len, pos_state ); + const int dis = pairs[i].dis; + trials[len].update( normal_match_price + price_pair( dis, len, pos_state ), + dis + num_rep_distances, 0 ); + if( ++len > pairs[i].len && ++i >= num_pairs ) break; } } - for( int rep = 0; rep < num_rep_distances; ++rep ) - { - const int price = rep_match_price + price_rep( rep, pos_state, state ); - for( int len = min_match_len; len <= replens[rep]; ++len ) - trials[len].update( rep, 0, price + - rep_match_len_encoder.price( len, pos_state ) ); - } - } - int cur = 0; - int num_trials = main_len; matchfinder.move_pos(); - while( true ) + while( true ) // price optimization loop { if( ++cur >= num_trials ) // no more initialized trials { backward( cur ); return cur; } - const int newlen = read_match_distances(); + + const int num_pairs = read_match_distances(); + const int newlen = ( num_pairs > 0 ) ? pairs[num_pairs-1].len : 0; if( newlen >= matchfinder.match_len_limit() ) { - longest_match_found = newlen; + pending_num_pairs = num_pairs; backward( cur ); return cur; } + // give final values to current trial Trial & cur_trial = trials[cur]; - const int prev_index = cur_trial.prev_index; - - cur_trial.state = trials[prev_index].state; + int prev_index = cur_trial.prev_index; + const int prev_index2 = cur_trial.prev_index2; + State cur_state; - for( int i = 0; i < num_rep_distances; ++i ) - cur_trial.reps[i] = trials[prev_index].reps[i]; + if( prev_index2 != single_step_trial ) + { + --prev_index; + if( prev_index2 >= 0 ) + { + cur_state = trials[prev_index2].state; + if( cur_trial.dis2 < num_rep_distances ) + cur_state.set_rep(); + else + cur_state.set_match(); + } + else + cur_state = trials[prev_index].state; + cur_state.set_char(); + } + else + cur_state = trials[prev_index].state; if( prev_index == cur - 1 ) { - if( cur_trial.dis == 0 ) cur_trial.state.set_short_rep(); - else cur_trial.state.set_char(); + if( cur_trial.dis == 0 ) cur_state.set_short_rep(); + else cur_state.set_char(); + for( int i = 0; i < num_rep_distances; ++i ) + cur_trial.reps[i] = trials[prev_index].reps[i]; } else { - if( cur_trial.dis < num_rep_distances ) cur_trial.state.set_rep(); - else cur_trial.state.set_match(); - mtf_reps( cur_trial.dis, cur_trial.reps ); + int dis; + if( prev_index2 >= 0 ) + { + dis = cur_trial.dis2; + prev_index = prev_index2; + cur_state.set_rep(); + } + else + { + dis = cur_trial.dis; + if( dis < num_rep_distances ) cur_state.set_rep(); + else cur_state.set_match(); + } + for( int i = 0; i < num_rep_distances; ++i ) + cur_trial.reps[i] = trials[prev_index].reps[i]; + mtf_reps( dis, cur_trial.reps ); } + cur_trial.state = cur_state; const int pos_state = matchfinder.data_position() & pos_state_mask; const uint8_t prev_byte = matchfinder[-1]; @@ -453,85 +512,168 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances], const uint8_t match_byte = matchfinder[-cur_trial.reps[0]-1]; int next_price = cur_trial.price + - price0( bm_match[cur_trial.state()][pos_state] ); - if( cur_trial.state.is_char() ) - next_price += literal_encoder.price_symbol( prev_byte, cur_byte ); + price0( bm_match[cur_state()][pos_state] ); + if( cur_state.is_char() ) + next_price += price_literal( prev_byte, cur_byte ); else - next_price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte ); + next_price += price_matched( prev_byte, cur_byte, match_byte ); matchfinder.move_pos(); + // try last updates to next trial Trial & next_trial = trials[cur+1]; - next_trial.update( -1, cur, next_price ); + next_trial.update( next_price, -1, cur ); - const int match_price = cur_trial.price + price1( bm_match[cur_trial.state()][pos_state] ); - const int rep_match_price = match_price + price1( bm_rep[cur_trial.state()] ); + const int match_price = cur_trial.price + price1( bm_match[cur_state()][pos_state] ); + const int rep_match_price = match_price + price1( bm_rep[cur_state()] ); if( match_byte == cur_byte && next_trial.dis != 0 ) - next_trial.update( 0, cur, rep_match_price + - price_rep_len1( pos_state, cur_trial.state ) ); + { + const int price = rep_match_price + + price_rep_len1( cur_state, pos_state ); + if( price <= next_trial.price ) + { + next_trial.price = price; + next_trial.dis = 0; + next_trial.prev_index = cur; + next_trial.prev_index2 = single_step_trial; + } + } - const int len_limit = std::min( std::min( max_num_trials - 1 - cur, - matchfinder.available_bytes() ), matchfinder.match_len_limit() ); - if( len_limit < min_match_len ) continue; + const int available_bytes = std::min( matchfinder.available_bytes() + 1, + max_num_trials - 1 - cur ); + if( available_bytes < min_match_len ) continue; - for( int rep = 0; rep < num_rep_distances; ++rep ) + const int len_limit = std::min( matchfinder.match_len_limit(), + available_bytes ); + + // try literal + rep0 + if( match_byte != cur_byte && next_trial.prev_index != cur ) { - const int dis = cur_trial.reps[rep] + 1; - int len = 0; const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; - while( len < len_limit && data[len] == data[len-dis] ) ++len; - if( len >= min_match_len ) + const int dis = cur_trial.reps[0] + 1; + const int limit = std::min( matchfinder.match_len_limit() + 1, + available_bytes ); + int len = 1; + while( len < limit && data[len-dis] == data[len] ) ++len; + if( --len >= min_match_len ) { - const int price = rep_match_price + - price_rep( rep, pos_state, cur_trial.state ); - while( num_trials < cur + len ) + const int pos_state2 = ( pos_state + 1 ) & pos_state_mask; + State state2 = cur_state; state2.set_char(); + const int price = next_price + + price1( bm_match[state2()][pos_state2] ) + + price1( bm_rep[state2()] ) + + price_rep0_len( len, state2, pos_state2 ); + while( num_trials < cur + 1 + len ) trials[++num_trials].price = infinite_price; - for( ; len >= min_match_len; --len ) - trials[cur+len].update( rep, cur, price + - rep_match_len_encoder.price( len, pos_state ) ); + trials[cur+1+len].update2( price, 0, cur + 1 ); } } - if( newlen <= len_limit && - ( newlen > min_match_len || - ( newlen == min_match_len && - match_distances[min_match_len] < modeled_distances ) ) ) + int start_len = min_match_len; + + // try rep distances + for( int rep = 0; rep < num_rep_distances; ++rep ) + { + const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; + int len; + const int dis = cur_trial.reps[rep] + 1; + + if( data[-dis] != data[0] || data[1-dis] != data[1] ) continue; + for( len = min_match_len; len < len_limit; ++len ) + if( data[len-dis] != data[len] ) break; + while( num_trials < cur + len ) + trials[++num_trials].price = infinite_price; + int price = rep_match_price + price_rep( rep, cur_state, pos_state ); + for( int i = min_match_len; i <= len; ++i ) + trials[cur+i].update( price + + rep_match_len_encoder.price( i, pos_state ), + rep, cur ); + + if( rep == 0 ) start_len = len + 1; // discard shorter matches + + // try rep + literal + rep0 + int len2 = len + 1; + const int limit = std::min( matchfinder.match_len_limit() + len2, + available_bytes ); + while( len2 < limit && data[len2-dis] == data[len2] ) ++len2; + len2 -= len + 1; + if( len2 < min_match_len ) continue; + + int pos_state2 = ( pos_state + len ) & pos_state_mask; + State state2 = cur_state; state2.set_rep(); + price += rep_match_len_encoder.price( len, pos_state ) + + price0( bm_match[state2()][pos_state2] ) + + price_matched( data[len-1], data[len], data[len-dis] ); + pos_state2 = ( pos_state2 + 1 ) & pos_state_mask; + state2.set_char(); + price += price1( bm_match[state2()][pos_state2] ) + + price1( bm_rep[state2()] ) + + price_rep0_len( len2, state2, pos_state2 ); + while( num_trials < cur + len + 1 + len2 ) + trials[++num_trials].price = infinite_price; + trials[cur+len+1+len2].update3( price, 0, cur + len + 1, rep, cur ); + } + + // try matches + if( newlen >= start_len && newlen <= len_limit ) { const int normal_match_price = match_price + - price0( bm_rep[cur_trial.state()] ); + price0( bm_rep[cur_state()] ); + while( num_trials < cur + newlen ) trials[++num_trials].price = infinite_price; - int dis = match_distances[min_match_len]; - int dis_state = get_dis_state( min_match_len ); - int dis_price = infinite_price; - if( dis < modeled_distances ) - trials[cur+min_match_len].update( dis + num_rep_distances, cur, - normal_match_price + dis_prices[dis_state][dis] + - len_encoder.price( min_match_len, pos_state ) ); - for( int len = min_match_len + 1; len <= newlen; ++len ) + int i = 0; + while( start_len > pairs[i].len ) ++i; + int dis = pairs[i].dis; + for( int len = start_len; ; ++len ) { - if( dis != match_distances[len] || dis_state < max_dis_states - 1 ) + int price = normal_match_price + price_pair( dis, len, pos_state ); + + trials[cur+len].update( price, dis + num_rep_distances, cur ); + + // try match + literal + rep0 + if( len == pairs[i].len ) { - dis = match_distances[len]; - dis_state = get_dis_state( len ); - dis_price = price_dis( dis, dis_state ); + const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; + const int dis2 = dis + 1; + int len2 = len + 1; + const int limit = std::min( matchfinder.match_len_limit() + len2, + available_bytes ); + while( len2 < limit && data[len2-dis2] == data[len2] ) ++len2; + len2 -= len + 1; + if( len2 >= min_match_len ) + { + int pos_state2 = ( pos_state + len ) & pos_state_mask; + State state2 = cur_state; state2.set_match(); + price += price0( bm_match[state2()][pos_state2] ) + + price_matched( data[len-1], data[len], data[len-dis2] ); + pos_state2 = ( pos_state2 + 1 ) & pos_state_mask; + state2.set_char(); + price += price1( bm_match[state2()][pos_state2] ) + + price1( bm_rep[state2()] ) + + price_rep0_len( len2, state2, pos_state2 ); + + while( num_trials < cur + len + 1 + len2 ) + trials[++num_trials].price = infinite_price; + trials[cur+len+1+len2].update3( price, 0, cur + len + 1, + dis + num_rep_distances, cur ); + } + if( ++i >= num_pairs ) break; + dis = pairs[i].dis; } - trials[cur+len].update( dis + num_rep_distances, cur, - normal_match_price + dis_price + - len_encoder.price( len, pos_state ) ); } } } } -bool LZ_encoder::encode_member( const long long member_size ) +bool LZ_encoder::encode_member( const unsigned long long member_size ) { - const long long member_size_limit = + const unsigned long long member_size_limit = member_size - File_trailer::size() - max_marker_size; - const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 512 : 2048; + const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 128 : 512; int fill_counter = 0; int rep_distances[num_rep_distances]; State state; @@ -546,20 +688,23 @@ bool LZ_encoder::encode_member( const long long member_size ) const uint8_t prev_byte = 0; const uint8_t cur_byte = matchfinder[0]; range_encoder.encode_bit( bm_match[state()][0], 0 ); - literal_encoder.encode( range_encoder, prev_byte, cur_byte ); + encode_literal( prev_byte, cur_byte ); crc32.update( crc_, cur_byte ); - matchfinder.longest_match_len(); + matchfinder.get_match_pairs(); matchfinder.move_pos(); } while( !matchfinder.finished() ) { - if( fill_counter <= 0 ) - { fill_distance_prices(); fill_counter = fill_count; } + if( pending_num_pairs == 0 ) + { + if( fill_counter <= 0 ) + { fill_distance_prices(); fill_counter = fill_count; } + if( align_price_count <= 0 ) fill_align_prices(); + } int ahead = sequence_optimizer( rep_distances, state ); if( ahead <= 0 ) return false; // can't happen - fill_counter -= ahead; for( int i = 0; ; ) { @@ -576,12 +721,11 @@ bool LZ_encoder::encode_member( const long long member_size ) const uint8_t cur_byte = matchfinder[-ahead]; crc32.update( crc_, cur_byte ); if( state.is_char() ) - literal_encoder.encode( range_encoder, prev_byte, cur_byte ); + encode_literal( prev_byte, cur_byte ); else { const uint8_t match_byte = matchfinder[-ahead-rep_distances[0]-1]; - literal_encoder.encode_matched( range_encoder, - prev_byte, cur_byte, match_byte ); + encode_matched( prev_byte, cur_byte, match_byte ); } state.set_char(); } @@ -613,9 +757,9 @@ bool LZ_encoder::encode_member( const long long member_size ) else { encode_pair( dis - num_rep_distances, len, pos_state ); - if( dis_slots[dis - num_rep_distances] >= end_dis_model && - --align_price_count <= 0 ) - fill_align_prices(); + if( get_slot( dis - num_rep_distances ) >= end_dis_model ) + --align_price_count; + --fill_counter; state.set_match(); } } |