Merging upstream version 1.4.

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

1 files changed, 356 insertions, 218 deletions

diff --git a/encoder.c b/encoder.c
index 84e2586..cb6c8d6 100644
--- a/encoder.c
+++ b/encoder.c
@@ -1,5 +1,5 @@
 /*  Clzip - Data compressor based on the LZMA algorithm
-    Copyright (C) 2010, 2011, 2012 Antonio Diaz Diaz.
+    Copyright (C) 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
@@ -60,9 +60,9 @@ void Mf_normalize_pos( struct Matchfinder * const mf )
     mf->partial_data_pos += offset;
     mf->pos -= offset;
     mf->stream_pos -= offset;
-    for( i = 0; i < num_prev_positions; ++i )
+    for( i = 0; i < mf->num_prev_positions; ++i )
       if( mf->prev_positions[i] >= 0 ) mf->prev_positions[i] -= offset;
-    for( i = 0; i < 2 * mf->dictionary_size; ++i )
+    for( i = 0; i < 2 * ( mf->dictionary_size + 1 ); ++i )
       if( mf->prev_pos_tree[i] >= 0 ) mf->prev_pos_tree[i] -= offset;
     Mf_read_block( mf );
     }
@@ -70,44 +70,53 @@ void Mf_normalize_pos( struct Matchfinder * const mf )
 
 
 bool Mf_init( struct Matchfinder * const mf,
-              const int dict_size, const int len_limit, const int ifd )
+              const int dict_size, const int match_len_limit, const int ifd )
   {
   const int buffer_size_limit = ( 2 * dict_size ) + before_size + after_size;
-  int i;
+  int i, size;
+
   mf->partial_data_pos = 0;
-  mf->prev_positions = (int32_t *)malloc( num_prev_positions * sizeof (int32_t) );
-  if( !mf->prev_positions ) return false;
+  mf->match_len_limit = match_len_limit;
   mf->pos = 0;
   mf->cyclic_pos = 0;
   mf->stream_pos = 0;
-  mf->match_len_limit = len_limit;
-  mf->cycles = ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256;
+  mf->cycles = ( match_len_limit < max_match_len ) ?
+               16 + ( match_len_limit / 2 ) : 256;
   mf->infd = ifd;
   mf->at_stream_end = false;
 
-  for( i = 0; i < num_prev_positions; ++i ) mf->prev_positions[i] = -1;
   mf->buffer_size = max( 65536, dict_size );
   mf->buffer = (uint8_t *)malloc( mf->buffer_size );
-  if( !mf->buffer ) { free( mf->prev_positions ); return false; }
+  if( !mf->buffer ) return false;
   if( Mf_read_block( mf ) && !mf->at_stream_end &&
       mf->buffer_size < buffer_size_limit )
     {
+    uint8_t * tmp;
     mf->buffer_size = buffer_size_limit;
-    uint8_t * const tmp = (uint8_t *)realloc( mf->buffer, mf->buffer_size );
-    if( !tmp )
-      { free( mf->buffer ); free( mf->prev_positions ); return false; }
+    tmp = (uint8_t *)realloc( mf->buffer, mf->buffer_size );
+    if( !tmp ) { free( mf->buffer ); return false; }
     mf->buffer = tmp;
     Mf_read_block( mf );
     }
   if( mf->at_stream_end && mf->stream_pos < dict_size )
     mf->dictionary_size = max( min_dictionary_size, mf->stream_pos );
-  else mf->dictionary_size = dict_size;
+  else
+    mf->dictionary_size = dict_size;
   mf->pos_limit = mf->buffer_size;
   if( !mf->at_stream_end ) mf->pos_limit -= after_size;
-  mf->prev_pos_tree =
-    (int32_t *)malloc( 2 * mf->dictionary_size * sizeof (int32_t) );
-  if( !mf->prev_pos_tree )
-    { free( mf->buffer ); free( mf->prev_positions ); return false; }
+  size = 1 << max( 16, real_bits( mf->dictionary_size - 1 ) - 2 );
+  if( mf->dictionary_size > 1 << 26 )
+    size >>= 1;
+  mf->key4_mask = size - 1;
+  size += num_prev_positions2;
+  size += num_prev_positions3;
+
+  mf->num_prev_positions = size;
+  size += ( 2 * ( mf->dictionary_size + 1 ) );
+  mf->prev_positions = (int32_t *)malloc( size * sizeof (int32_t) );
+  if( !mf->prev_positions ) { free( mf->buffer ); return false; }
+  mf->prev_pos_tree = mf->prev_positions + mf->num_prev_positions;
+  for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
   return true;
   }
 
@@ -121,23 +130,24 @@ void Mf_reset( struct Matchfinder * const mf )
   mf->stream_pos -= mf->pos;
   mf->pos = 0;
   mf->cyclic_pos = 0;
-  for( i = 0; i < num_prev_positions; ++i ) mf->prev_positions[i] = -1;
+  for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
   Mf_read_block( mf );
   }
 
 
-int Mf_longest_match_len( struct Matchfinder * const mf, int * const distances )
+int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pairs )
   {
   int32_t * ptr0 = mf->prev_pos_tree + ( mf->cyclic_pos << 1 );
   int32_t * ptr1 = ptr0 + 1;
   int32_t * newptr;
-  const uint8_t * newdata;
   int len = 0, len0 = 0, len1 = 0;
   int maxlen = min_match_len - 1;
-  const int min_pos = (mf->pos >= mf->dictionary_size) ?
-                      (mf->pos - mf->dictionary_size + 1) : 0;
+  int num_pairs = 0;
+  const int min_pos = (mf->pos > mf->dictionary_size) ?
+                       mf->pos - mf->dictionary_size : 0;
   const uint8_t * const data = mf->buffer + mf->pos;
-  int count, delta, key2, key3, key4, newpos, tmp;
+  int count, delta, key2, key3, key4, newpos;
+  unsigned tmp;
   int len_limit = mf->match_len_limit;
 
   if( len_limit > Mf_available_bytes( mf ) )
@@ -146,24 +156,39 @@ int Mf_longest_match_len( struct Matchfinder * const mf, int * const distances )
     if( len_limit < 4 ) return 0;
     }
 
-  key2 = num_prev_positions4 + num_prev_positions3 +
-         ( ( (int)data[0] << 8 ) | data[1] );
-  tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 );
-  key3 = num_prev_positions4 + (int)( tmp & ( num_prev_positions3 - 1 ) );
-  key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) &
-                ( num_prev_positions4 - 1 ) );
+  tmp = crc32[data[0]] ^ data[1];
+  key2 = tmp & ( num_prev_positions2 - 1 );
+  tmp ^= (uint32_t)data[2] << 8;
+  key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) );
+  key4 = num_prev_positions2 + num_prev_positions3 +
+         ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & mf->key4_mask );
 
-  if( distances )
+  if( pairs )
     {
-    int np = mf->prev_positions[key2];
-    if( np >= min_pos )
-      { distances[2] = mf->pos - np - 1; maxlen = 2; }
-    else distances[2] = 0x7FFFFFFF;
-    np = mf->prev_positions[key3];
-    if( np >= min_pos && mf->buffer[np] == data[0] )
-      { distances[3] = mf->pos - np - 1; maxlen = 3; }
-    else distances[3] = 0x7FFFFFFF;
-    distances[4] = 0x7FFFFFFF;
+    int np2 = mf->prev_positions[key2];
+    int np3 = mf->prev_positions[key3];
+    if( np2 >= min_pos && mf->buffer[np2] == data[0] )
+      {
+      pairs[0].dis = mf->pos - np2 - 1;
+      pairs[0].len = maxlen = 2;
+      num_pairs = 1;
+      }
+    if( np2 != np3 && np3 >= min_pos && mf->buffer[np3] == data[0] )
+      {
+      maxlen = 3;
+      pairs[num_pairs].dis = mf->pos - np3 - 1;
+      ++num_pairs;
+      np2 = np3;
+      }
+    if( num_pairs > 0 )
+      {
+      delta = mf->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;
     }
 
   mf->prev_positions[key2] = mf->pos;
@@ -174,46 +199,43 @@ int Mf_longest_match_len( struct Matchfinder * const mf, int * const distances )
   for( count = mf->cycles; ; )
     {
     if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; }
-    newdata = mf->buffer + newpos;
-    while( len < len_limit && newdata[len] == data[len] ) ++len;
 
     delta = mf->pos - newpos;
-    if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1;
-
     newptr = mf->prev_pos_tree +
       ( ( mf->cyclic_pos - delta +
-          ( ( mf->cyclic_pos >= delta ) ? 0 : mf->dictionary_size ) ) << 1 );
-
-    if( len < len_limit )
+          ( (mf->cyclic_pos >= delta) ? 0 : mf->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;
   }
 
 
@@ -222,8 +244,7 @@ void Re_flush_data( struct Range_encoder * const renc )
   if( renc->pos > 0 )
     {
     if( renc->outfd >= 0 &&
-        writeblock( renc->outfd, renc->buffer,
-                    renc->pos ) != renc->pos )
+        writeblock( renc->outfd, renc->buffer, renc->pos ) != renc->pos )
       { show_error( "Write error", errno, false ); cleanup_and_fail( 1 ); }
     renc->partial_member_pos += renc->pos;
     renc->pos = 0;
@@ -263,7 +284,7 @@ void Lee_encode( struct Len_encoder * const len_encoder,
 
 
      /* End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) */
-void LZe_full_flush( struct LZ_encoder * const encoder, const State state )
+static void LZe_full_flush( struct LZ_encoder * const encoder, const State state )
   {
   int i;
   const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
@@ -282,7 +303,7 @@ void LZe_full_flush( struct LZ_encoder * const encoder, const State state )
   }
 
 
-void LZe_fill_align_prices( struct LZ_encoder * const encoder )
+static void LZe_fill_align_prices( struct LZ_encoder * const encoder )
   {
   int i;
   for( i = 0; i < dis_align_size; ++i )
@@ -292,7 +313,7 @@ void LZe_fill_align_prices( struct LZ_encoder * const encoder )
   }
 
 
-void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
+static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
   {
   int dis, dis_state;
   for( dis = start_dis_model; dis < modeled_distances; ++dis )
@@ -301,7 +322,7 @@ void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
     const int direct_bits = ( dis_slot >> 1 ) - 1;
     const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
     const int price =
-      price_symbol_reversed( encoder->bm_dis + base - dis_slot,
+      price_symbol_reversed( encoder->bm_dis + base - dis_slot - 1,
                              dis - base, direct_bits );
     for( dis_state = 0; dis_state < max_dis_states; ++dis_state )
       encoder->dis_prices[dis_state][dis] = price;
@@ -317,7 +338,7 @@ void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
       dsp[slot] = price_symbol( bmds, slot, dis_slot_bits );
     for( ; slot < encoder->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 );
 
     for( dis = 0; dis < start_dis_model; ++dis )
       dp[dis] = dsp[dis];
@@ -331,39 +352,29 @@ bool LZe_init( struct LZ_encoder * const encoder,
                struct Matchfinder * const mf,
                const File_header header, const int outfd )
   {
-  int i, j;
-  encoder->longest_match_found = 0;
+  int i;
+  encoder->pending_num_pairs = 0;
   encoder->crc = 0xFFFFFFFFU;
 
-  for( i = 0; i < states; ++i )
-    {
-    for( j = 0; j < pos_states; ++j )
-      {
-      Bm_init( &encoder->bm_match[i][j] );
-      Bm_init( &encoder->bm_len[i][j] );
-      }
-    Bm_init( &encoder->bm_rep[i] );
-    Bm_init( &encoder->bm_rep0[i] );
-    Bm_init( &encoder->bm_rep1[i] );
-    Bm_init( &encoder->bm_rep2[i] );
-    }
-  for( i = 0; i < max_dis_states; ++i )
-    for( j = 0; j < 1<<dis_slot_bits; ++j )
-      Bm_init( &encoder->bm_dis_slot[i][j] );
-  for( i = 0; i < modeled_distances-end_dis_model+1; ++i )
-    Bm_init( &encoder->bm_dis[i] );
-  for( i = 0; i < dis_align_size; ++i )
-    Bm_init( &encoder->bm_align[i] );
+  Bm_array_init( encoder->bm_literal[0], (1 << literal_context_bits) * 0x300 );
+  Bm_array_init( encoder->bm_match[0], states * pos_states );
+  Bm_array_init( encoder->bm_rep, states );
+  Bm_array_init( encoder->bm_rep0, states );
+  Bm_array_init( encoder->bm_rep1, states );
+  Bm_array_init( encoder->bm_rep2, states );
+  Bm_array_init( encoder->bm_len[0], states * pos_states );
+  Bm_array_init( encoder->bm_dis_slot[0], max_dis_states * (1 << dis_slot_bits) );
+  Bm_array_init( encoder->bm_dis, modeled_distances - end_dis_model );
+  Bm_array_init( encoder->bm_align, dis_align_size );
 
   encoder->matchfinder = mf;
   if( !Re_init( &encoder->range_encoder, outfd ) ) return false;
   Lee_init( &encoder->len_encoder, encoder->matchfinder->match_len_limit );
   Lee_init( &encoder->rep_match_len_encoder, encoder->matchfinder->match_len_limit );
-  Lie_init( &encoder->literal_encoder );
   encoder->num_dis_slots =
     2 * real_bits( encoder->matchfinder->dictionary_size - 1 );
 
-  LZe_fill_align_prices( encoder );
+  encoder->align_price_count = 0;
 
   for( i = 0; i < Fh_size; ++i )
     Re_put_byte( &encoder->range_encoder, header[i] );
@@ -375,24 +386,27 @@ bool LZe_init( struct LZ_encoder * const encoder,
    trials[0]..trials[retval-1] contain the steps to encode.
    ( trials[0].dis == -1 && trials[0].price == 1 ) means literal.
 */
-int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
-                            const int reps[num_rep_distances],
-                            const State state )
+static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
+                                   const int reps[num_rep_distances],
+                                   const State state )
   {
-  int main_len, i, rep, cur = 0, num_trials;
+  int main_len, num_pairs, i, rep, cur = 0, num_trials, len;
   int replens[num_rep_distances];
   int rep_index = 0;
 
-  if( encoder->longest_match_found > 0 )	/* from previous call */
+  if( encoder->pending_num_pairs > 0 )		/* from previous call */
     {
-    main_len = encoder->longest_match_found;
-    encoder->longest_match_found = 0;
+    num_pairs = encoder->pending_num_pairs;
+    encoder->pending_num_pairs = 0;
     }
-  else main_len = LZe_read_match_distances( encoder );
+  else
+    num_pairs = LZe_read_match_distances( encoder );
+  main_len = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
 
   for( i = 0; i < num_rep_distances; ++i )
     {
-    replens[i] = Mf_true_match_len( encoder->matchfinder, 0, reps[i] + 1, max_match_len );
+    replens[i] =
+      Mf_true_match_len( encoder->matchfinder, 0, reps[i] + 1, max_match_len );
     if( replens[i] > replens[rep_index] ) rep_index = i;
     }
   if( replens[rep_index] >= encoder->matchfinder->match_len_limit )
@@ -405,9 +419,7 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
 
   if( main_len >= encoder->matchfinder->match_len_limit )
     {
-    encoder->trials[0].dis =
-      encoder->match_distances[encoder->matchfinder->match_len_limit] +
-      num_rep_distances;
+    encoder->trials[0].dis = encoder->pairs[num_pairs-1].dis + num_rep_distances;
     encoder->trials[0].price = main_len;
     LZe_move_pos( encoder, main_len );
     return main_len;
@@ -422,23 +434,22 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
   const uint8_t match_byte = Mf_peek( encoder->matchfinder, -reps[0]-1 );
 
   encoder->trials[0].state = state;
-  for( i = 0; i < num_rep_distances; ++i )
-    encoder->trials[0].reps[i] = reps[i];
   encoder->trials[1].dis = -1;
-  encoder->trials[1].prev_index = 0;
   encoder->trials[1].price = price0( encoder->bm_match[state][pos_state] );
   if( St_is_char( state ) )
     encoder->trials[1].price +=
-      Lie_price_symbol( &encoder->literal_encoder, prev_byte, cur_byte );
+      LZe_price_literal( encoder, prev_byte, cur_byte );
   else
     encoder->trials[1].price +=
-      Lie_price_matched( &encoder->literal_encoder, prev_byte, cur_byte, match_byte );
+      LZe_price_matched( encoder, prev_byte, cur_byte, match_byte );
 
   if( match_byte == cur_byte )
-    Tr_update( &encoder->trials[1], 0, 0, rep_match_price +
-               LZe_price_rep_len1( encoder, state, pos_state ) );
+    Tr_update( &encoder->trials[1], rep_match_price +
+               LZe_price_rep_len1( encoder, state, pos_state ), 0, 0 );
+
+  num_trials = max( main_len, replens[rep_index] );
 
-  if( main_len < min_match_len )
+  if( num_trials < min_match_len )
     {
     encoder->trials[0].dis = encoder->trials[1].dis;
     encoder->trials[0].price = 1;
@@ -446,45 +457,51 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
     return 1;
     }
 
-  if( main_len <= replens[rep_index] )
+  for( i = 0; i < num_rep_distances; ++i )
+    encoder->trials[0].reps[i] = reps[i];
+  encoder->trials[1].prev_index = 0;
+  encoder->trials[1].prev_index2 = single_step_trial;
+
+  for( len = min_match_len; len <= num_trials; ++len )
+    encoder->trials[len].price = infinite_price;
+
+  for( rep = 0; rep < num_rep_distances; ++rep )
     {
-    int len;
-    main_len = replens[rep_index];
-    for( len = min_match_len; len <= main_len; ++len )
-      encoder->trials[len].price = infinite_price;
+    int price;
+    if( replens[rep] < min_match_len ) continue;
+    price = rep_match_price + LZe_price_rep( encoder, rep, state, pos_state );
+
+    for( len = min_match_len; len <= replens[rep]; ++len )
+      Tr_update( &encoder->trials[len], price +
+                 Lee_price( &encoder->rep_match_len_encoder, len, pos_state ),
+                 rep, 0 );
     }
-  else
+
+  if( main_len > replens[0] )
     {
-    int len;
     const int normal_match_price = match_price + price0( encoder->bm_rep[state] );
-    for( len = min_match_len; len <= main_len; ++len )
+    i = 0, len = max( replens[0] + 1, min_match_len );
+    while( len > encoder->pairs[i].len ) ++i;
+    while( true )
       {
-      encoder->trials[len].dis = encoder->match_distances[len] + num_rep_distances;
-      encoder->trials[len].prev_index = 0;
-      encoder->trials[len].price = normal_match_price +
-        LZe_price_pair( encoder, encoder->match_distances[len], len, pos_state );
+      const int dis = encoder->pairs[i].dis;
+      Tr_update( &encoder->trials[len], normal_match_price +
+                 LZe_price_pair( encoder, dis, len, pos_state ),
+                 dis + num_rep_distances, 0 );
+      if( ++len > encoder->pairs[i].len && ++i >= num_pairs ) break;
       }
     }
-
-  for( rep = 0; rep < num_rep_distances; ++rep )
-    {
-    const int price = rep_match_price +
-                      LZe_price_rep( encoder, rep, state, pos_state );
-    int len;
-    for( len = min_match_len; len <= replens[rep]; ++len )
-      Tr_update( &encoder->trials[len], rep, 0, price +
-                 Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) );
-    }
   }
 
-  num_trials = main_len;
   Mf_move_pos( encoder->matchfinder );
 
-  while( true )
+  while( true )				/* price optimization loop */
     {
     struct Trial *cur_trial, *next_trial;
-    int newlen, pos_state, prev_index, len_limit;
+    int newlen, pos_state, prev_index, prev_index2, available_bytes, len_limit;
+    int start_len = min_match_len;
     int next_price, match_price, rep_match_price;
+    State cur_state;
     uint8_t prev_byte, cur_byte, match_byte;
 
     if( ++cur >= num_trials )		/* no more initialized trials */
@@ -492,33 +509,70 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
       LZe_backward( encoder, cur );
       return cur;
       }
-    newlen = LZe_read_match_distances( encoder );
+
+    num_pairs = LZe_read_match_distances( encoder );
+    newlen = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
     if( newlen >= encoder->matchfinder->match_len_limit )
       {
-      encoder->longest_match_found = newlen;
+      encoder->pending_num_pairs = num_pairs;
       LZe_backward( encoder, cur );
       return cur;
       }
 
+    /* give final values to current trial */
     cur_trial = &encoder->trials[cur];
     prev_index = cur_trial->prev_index;
+    prev_index2 = cur_trial->prev_index2;
 
-    cur_trial->state = encoder->trials[prev_index].state;
-
-    for( i = 0; i < num_rep_distances; ++i )
-      cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
+    if( prev_index2 != single_step_trial )
+      {
+      --prev_index;
+      if( prev_index2 >= 0 )
+        {
+        cur_state = encoder->trials[prev_index2].state;
+        if( cur_trial->dis2 < num_rep_distances )
+          cur_state = St_set_rep( cur_state );
+        else
+          cur_state = St_set_match( cur_state );
+        }
+      else
+        cur_state = encoder->trials[prev_index].state;
+      cur_state = St_set_char( cur_state );
+      }
+    else
+      cur_state = encoder->trials[prev_index].state;
 
     if( prev_index == cur - 1 )
       {
-      if( cur_trial->dis == 0 ) St_set_short_rep( &cur_trial->state );
-      else St_set_char( &cur_trial->state );
+      if( cur_trial->dis == 0 )
+        cur_state = St_set_short_rep( cur_state );
+      else
+        cur_state = St_set_char( cur_state );
+      for( i = 0; i < num_rep_distances; ++i )
+        cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
       }
     else
       {
-      if( cur_trial->dis < num_rep_distances ) St_set_rep( &cur_trial->state );
-      else St_set_match( &cur_trial->state );
-      LZe_mtf_reps( cur_trial->dis, cur_trial->reps );
+      int dis;
+      if( prev_index2 >= 0 )
+        {
+        dis = cur_trial->dis2;
+        prev_index = prev_index2;
+        cur_state = St_set_rep( cur_state );
+        }
+      else
+        {
+        dis = cur_trial->dis;
+        if( dis < num_rep_distances )
+          cur_state = St_set_rep( cur_state );
+        else
+          cur_state = St_set_match( cur_state );
+        }
+      for( i = 0; i < num_rep_distances; ++i )
+        cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
+      LZe_mtf_reps( dis, cur_trial->reps );
       }
+    cur_trial->state = cur_state;
 
     pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
     prev_byte = Mf_peek( encoder->matchfinder, -1 );
@@ -526,81 +580,162 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
     match_byte = Mf_peek( encoder->matchfinder, -cur_trial->reps[0]-1 );
 
     next_price = cur_trial->price +
-                 price0( encoder->bm_match[cur_trial->state][pos_state] );
-    if( St_is_char( cur_trial->state ) )
-      next_price += Lie_price_symbol( &encoder->literal_encoder,
-                                      prev_byte, cur_byte );
+                 price0( encoder->bm_match[cur_state][pos_state] );
+    if( St_is_char( cur_state ) )
+      next_price += LZe_price_literal( encoder, prev_byte, cur_byte );
     else
-      next_price += Lie_price_matched( &encoder->literal_encoder,
+      next_price += LZe_price_matched( encoder,
                                        prev_byte, cur_byte, match_byte );
     Mf_move_pos( encoder->matchfinder );
 
+    /* try last updates to next trial */
     next_trial = &encoder->trials[cur+1];
 
-    Tr_update( next_trial, -1, cur, next_price );
+    Tr_update( next_trial, next_price, -1, cur );
 
-    match_price = cur_trial->price + price1( encoder->bm_match[cur_trial->state][pos_state] );
-    rep_match_price = match_price + price1( encoder->bm_rep[cur_trial->state] );
+    match_price = cur_trial->price + price1( encoder->bm_match[cur_state][pos_state] );
+    rep_match_price = match_price + price1( encoder->bm_rep[cur_state] );
 
     if( match_byte == cur_byte && next_trial->dis != 0 )
-      Tr_update( next_trial, 0, cur, rep_match_price +
-                 LZe_price_rep_len1( encoder, cur_trial->state, pos_state ) );
+      {
+      const int price = rep_match_price +
+                        LZe_price_rep_len1( encoder, 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;
+        }
+      }
 
-    len_limit = min( min( max_num_trials - 1 - cur,
-                          Mf_available_bytes( encoder->matchfinder ) ),
-                     encoder->matchfinder->match_len_limit );
-    if( len_limit < min_match_len ) continue;
+    available_bytes = min( Mf_available_bytes( encoder->matchfinder ) + 1,
+                           max_num_trials - 1 - cur );
+    if( available_bytes < min_match_len ) continue;
 
-    for( rep = 0; rep < num_rep_distances; ++rep )
+    len_limit = min( encoder->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 = Mf_ptr_to_current_pos( encoder->matchfinder ) - 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 = min( encoder->matchfinder->match_len_limit + 1,
+                             available_bytes );
+      len = 1;
+      while( len < limit && data[len-dis] == data[len] ) ++len;
+      if( --len >= min_match_len )
         {
-        const int price = rep_match_price +
-                          LZe_price_rep( encoder, rep, cur_trial->state, pos_state );
-        while( num_trials < cur + len )
+        const int pos_state2 = ( pos_state + 1 ) & pos_state_mask;
+        const State state2 = St_set_char( cur_state );
+        const int price = next_price +
+                  price1( encoder->bm_match[state2][pos_state2] ) +
+                  price1( encoder->bm_rep[state2] ) +
+                  LZe_price_rep0_len( encoder, len, state2, pos_state2 );
+        while( num_trials < cur + 1 + len )
           encoder->trials[++num_trials].price = infinite_price;
-        for( ; len >= min_match_len; --len )
-          Tr_update( &encoder->trials[cur+len], rep, cur, price +
-                     Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) );
+        Tr_update2( &encoder->trials[cur+1+len], price, 0, cur + 1 );
         }
       }
 
-    if( newlen <= len_limit &&
-        ( newlen > min_match_len ||
-          ( newlen == min_match_len &&
-            encoder->match_distances[min_match_len] < modeled_distances ) ) )
+    /* try rep distances */
+    for( rep = 0; rep < num_rep_distances; ++rep )
       {
+      const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+      int price;
+      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 )
+        encoder->trials[++num_trials].price = infinite_price;
+      price = rep_match_price +
+              LZe_price_rep( encoder, rep, cur_state, pos_state );
+      for( i = min_match_len; i <= len; ++i )
+        Tr_update( &encoder->trials[cur+i], price +
+                   Lee_price( &encoder->rep_match_len_encoder, i, pos_state ),
+                   rep, cur );
+
+      if( rep == 0 ) start_len = len + 1;	/* discard shorter matches */
+
+      /* try rep + literal + rep0 */
+      {
+      int len2 = len + 1, pos_state2;
+      const int limit = min( encoder->matchfinder->match_len_limit + len2,
+                             available_bytes );
+      State state2;
+      while( len2 < limit && data[len2-dis] == data[len2] ) ++len2;
+      len2 -= len + 1;
+      if( len2 < min_match_len ) continue;
+
+      pos_state2 = ( pos_state + len ) & pos_state_mask;
+      state2 = St_set_rep( cur_state );
+      price += Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) +
+               price0( encoder->bm_match[state2][pos_state2] ) +
+               LZe_price_matched( encoder, data[len-1], data[len], data[len-dis] );
+      pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
+      state2 = St_set_char( state2 );
+      price += price1( encoder->bm_match[state2][pos_state2] ) +
+               price1( encoder->bm_rep[state2] ) +
+               LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+      while( num_trials < cur + len + 1 + len2 )
+        encoder->trials[++num_trials].price = infinite_price;
+      Tr_update3( &encoder->trials[cur+len+1+len2], price, 0, cur + len + 1,
+                  rep, cur );
+      }
+      }
+
+    /* try matches */
+    if( newlen >= start_len && newlen <= len_limit )
+      {
+      int dis;
       const int normal_match_price = match_price +
-                                     price0( encoder->bm_rep[cur_trial->state] );
-      int len;
-      int dis = encoder->match_distances[min_match_len];
-      int dis_state = get_dis_state( min_match_len );
-      int dis_price = infinite_price;
+                                     price0( encoder->bm_rep[cur_state] );
 
       while( num_trials < cur + newlen )
         encoder->trials[++num_trials].price = infinite_price;
 
-      if( dis < modeled_distances )
-        Tr_update( &encoder->trials[cur+min_match_len], dis + num_rep_distances,
-                   cur, normal_match_price + encoder->dis_prices[dis_state][dis] +
-                   Lee_price( &encoder->len_encoder, min_match_len, pos_state ) );
-
-      for( len = min_match_len + 1; len <= newlen; ++len )
+      i = 0;
+      while( start_len > encoder->pairs[i].len ) ++i;
+      dis = encoder->pairs[i].dis;
+      for( len = start_len; ; ++len )
         {
-        if( dis != encoder->match_distances[len] ||
-            dis_state < max_dis_states - 1 )
+        int price = normal_match_price +
+                    LZe_price_pair( encoder, dis, len, pos_state );
+
+        Tr_update( &encoder->trials[cur+len], price, dis + num_rep_distances, cur );
+
+        /* try match + literal + rep0 */
+        if( len == encoder->pairs[i].len )
           {
-          dis = encoder->match_distances[len];
-          dis_state = get_dis_state( len );
-          dis_price = LZe_price_dis( encoder, dis, dis_state );
+          const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+          const int dis2 = dis + 1;
+          int len2 = len + 1;
+          const int limit = min( encoder->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 = St_set_match( cur_state );
+            price += price0( encoder->bm_match[state2][pos_state2] ) +
+                     LZe_price_matched( encoder, data[len-1], data[len], data[len-dis2] );
+            pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
+            state2 = St_set_char( state2 );
+            price += price1( encoder->bm_match[state2][pos_state2] ) +
+                     price1( encoder->bm_rep[state2] ) +
+                     LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+
+            while( num_trials < cur + len + 1 + len2 )
+              encoder->trials[++num_trials].price = infinite_price;
+            Tr_update3( &encoder->trials[cur+len+1+len2], price, 0,
+                        cur + len + 1, dis + num_rep_distances, cur );
+            }
+          if( ++i >= num_pairs ) break;
+          dis = encoder->pairs[i].dis;
           }
-        Tr_update( &encoder->trials[cur+len], dis + num_rep_distances, cur,
-                   normal_match_price + dis_price +
-                   Lee_price( &encoder->len_encoder, len, pos_state ) );
         }
       }
     }
@@ -608,12 +743,12 @@ int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
 
 
 bool LZe_encode_member( struct LZ_encoder * const encoder,
-                        const long long member_size )
+                        const unsigned long long member_size )
   {
-  const long long member_size_limit =
+  const unsigned long long member_size_limit =
     member_size - Ft_size - max_marker_size;
   const int fill_count =
-    ( encoder->matchfinder->match_len_limit > 12 ) ? 512 : 2048;
+    ( encoder->matchfinder->match_len_limit > 12 ) ? 128 : 512;
   int fill_counter = 0;
   int ahead, i;
   int rep_distances[num_rep_distances];
@@ -629,20 +764,24 @@ bool LZe_encode_member( struct LZ_encoder * const encoder,
     const uint8_t prev_byte = 0;
     const uint8_t cur_byte = Mf_peek( encoder->matchfinder, 0 );
     Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[state][0], 0 );
-    Lie_encode( &encoder->literal_encoder, &encoder->range_encoder, prev_byte, cur_byte );
+    LZe_encode_literal( encoder, prev_byte, cur_byte );
     CRC32_update_byte( &encoder->crc, cur_byte );
-    Mf_longest_match_len( encoder->matchfinder, 0 );
+    Mf_get_match_pairs( encoder->matchfinder, 0 );
     Mf_move_pos( encoder->matchfinder );
     }
 
   while( !Mf_finished( encoder->matchfinder ) )
     {
-    if( fill_counter <= 0 )
-      { LZe_fill_distance_prices( encoder ); fill_counter = fill_count; }
+    if( encoder->pending_num_pairs == 0 )
+      {
+      if( fill_counter <= 0 )
+        { LZe_fill_distance_prices( encoder ); fill_counter = fill_count; }
+      if( encoder->align_price_count <= 0 )
+        LZe_fill_align_prices( encoder );
+      }
 
     ahead = LZe_sequence_optimizer( encoder, rep_distances, state );
     if( ahead <= 0 ) return false;		/* can't happen */
-    fill_counter -= ahead;
 
     for( i = 0; ; )
       {
@@ -660,18 +799,16 @@ bool LZe_encode_member( struct LZ_encoder * const encoder,
         const uint8_t cur_byte = Mf_peek( encoder->matchfinder, -ahead );
         CRC32_update_byte( &encoder->crc, cur_byte );
         if( St_is_char( state ) )
-          Lie_encode( &encoder->literal_encoder, &encoder->range_encoder,
-                      prev_byte, cur_byte );
+          LZe_encode_literal( encoder, prev_byte, cur_byte );
         else
           {
           const uint8_t match_byte =
             Mf_peek( encoder->matchfinder, -ahead-rep_distances[0]-1 );
-          Lie_encode_matched( &encoder->literal_encoder, &encoder->range_encoder,
-                              prev_byte, cur_byte, match_byte );
+          LZe_encode_matched( encoder, prev_byte, cur_byte, match_byte );
           }
-        St_set_char( &state );
+        state = St_set_char( state );
         }
-      else				/* match or repeated match */
+      else					/* match or repeated match */
         {
         CRC32_update_buf( &encoder->crc, Mf_ptr_to_current_pos( encoder->matchfinder ) - ahead, len );
         LZe_mtf_reps( dis, rep_distances );
@@ -689,17 +826,18 @@ bool LZe_encode_member( struct LZ_encoder * const encoder,
             if( dis > 1 )
               Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep2[state], dis > 2 );
             }
-          if( len == 1 ) St_set_short_rep( &state );
+          if( len == 1 ) state = St_set_short_rep( state );
           else
             {
             Lee_encode( &encoder->rep_match_len_encoder, &encoder->range_encoder, len, pos_state );
-            St_set_rep( &state );
+            state = St_set_rep( state );
             }
           }
         else
           {
           LZe_encode_pair( encoder, dis - num_rep_distances, len, pos_state );
-          St_set_match( &state );
+          --fill_counter;
+          state = St_set_match( state );
           }
         }
       ahead -= len; i += len;