summaryrefslogtreecommitdiffstats
path: root/encoder.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--encoder.cc498
1 files changed, 321 insertions, 177 deletions
diff --git a/encoder.cc b/encoder.cc
index 56820b5..2e00c3d 100644
--- a/encoder.cc
+++ b/encoder.cc
@@ -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();
}
}