Merging upstream version 1.6~pre3.

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

1 files changed, 43 insertions, 63 deletions

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