Merging upstream version 1.14.

Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>

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();
           }
         }