Merging upstream version 1.16~pre2.

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

1 files changed, 79 insertions, 44 deletions

diff --git a/encoder.h b/encoder.h
index 4139484..5df34c6 100644
--- a/encoder.h
+++ b/encoder.h
@@ -16,7 +16,7 @@
     along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
-enum { max_num_trials = 1 << 12,
+enum { max_num_trials = 1 << 13,
        price_shift_bits = 6,
        price_step_bits = 2,
        price_step = 1 << price_step_bits };
@@ -59,19 +59,18 @@ class Prob_prices
 public:
   void init()
     {
-    for( int i = price_step / 2; i < bit_model_total; i += price_step )
+    for( int i = 0; i < bit_model_total >> price_step_bits; ++i )
       {
-      unsigned val = i;
-      int bits = 0;			// base 2 logarithm of val
+      unsigned val = ( i * price_step ) + ( price_step / 2 );
+      int bits = 0;				// base 2 logarithm of val
       for( int j = 0; j < price_shift_bits; ++j )
         {
         val = val * val;
         bits <<= 1;
         while( val >= 1 << 16 ) { val >>= 1; ++bits; }
         }
-      bits += 15;			// remaining bits in val
-      data[i >> price_step_bits] =
-        ( bit_model_total_bits << price_shift_bits ) - bits;
+      bits += 15;				// remaining bits in val
+      data[i] = ( bit_model_total_bits << price_shift_bits ) - bits;
       }
     }
 
@@ -268,7 +267,7 @@ public:
     }
 
   int match_len_limit() const { return match_len_limit_; }
-  int get_match_pairs( struct Pair * pairs = 0 );
+  int get_match_pairs( Pair * pairs = 0 );
   };
 
 
@@ -419,42 +418,80 @@ public:
       }
     while( symbol < 0x10000 );
     }
+
+  void encode_len( Len_model & lm, int symbol, const int pos_state )
+    {
+    symbol -= min_match_len;
+    bool bit = ( symbol >= len_low_symbols );
+    encode_bit( lm.choice1, bit );
+    if( !bit )
+      encode_tree3( lm.bm_low[pos_state], symbol );
+    else
+      {
+      bit = ( symbol >= len_low_symbols + len_mid_symbols );
+      encode_bit( lm.choice2, bit );
+      if( !bit )
+        encode_tree3( lm.bm_mid[pos_state], symbol - len_low_symbols );
+      else
+        encode_tree8( lm.bm_high, symbol - len_low_symbols - len_mid_symbols );
+      }
+    }
   };
 
 
-class Len_encoder : public Len_model
+class Len_prices
   {
-  int prices[pos_states][max_len_symbols];
+  const Len_model & lm;
   const int len_symbols;
+  const int count;
+  int prices[pos_states][max_len_symbols];
   int counters[pos_states];
 
-  void update_prices( const int pos_state )
+  void update_low_mid_prices( const int pos_state )
     {
+    counters[pos_state] = count;
     int * const pps = prices[pos_state];
-    int tmp = price0( choice1 );
+    int tmp = price0( lm.choice1 );
     int len = 0;
     for( ; len < len_low_symbols && len < len_symbols; ++len )
-      pps[len] = tmp + price_symbol3( bm_low[pos_state], len );
-    tmp = price1( choice1 );
+      pps[len] = tmp + price_symbol3( lm.bm_low[pos_state], len );
+    if( len >= len_symbols ) return;
+    tmp = price1( lm.choice1 ) + price0( lm.choice2 );
     for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len )
-      pps[len] = tmp + price0( choice2 ) +
-                 price_symbol3( bm_mid[pos_state], len - len_low_symbols );
-    for( ; len < len_symbols; ++len )
+      pps[len] = tmp +
+                 price_symbol3( lm.bm_mid[pos_state], len - len_low_symbols );
+    }
+
+  void update_high_prices()
+    {
+    const int tmp = price1( lm.choice1 ) + price1( lm.choice2 );
+    for( int len = len_low_symbols + len_mid_symbols; len < len_symbols; ++len )
       // using 4 slots per value makes "price" faster
-      prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] =
-                 tmp + price1( choice2 ) +
-                 price_symbol8( bm_high, len - len_low_symbols - len_mid_symbols );
-    counters[pos_state] = len_symbols;
+      prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = tmp +
+        price_symbol8( lm.bm_high, len - len_low_symbols - len_mid_symbols );
     }
 
 public:
-  explicit Len_encoder( const int match_len_limit )
-    : len_symbols( match_len_limit + 1 - min_match_len )
+  Len_prices( const Len_model & m, const int match_len_limit )
+    :
+    lm( m ),
+    len_symbols( match_len_limit + 1 - min_match_len ),
+    count( ( match_len_limit > 12 ) ? 1 : len_symbols )
     {
-    for( int i = 0; i < pos_states; ++i ) update_prices( i );
+    for( int i = 0; i < pos_states; ++i ) counters[i] = 0;
     }
 
-  void encode( Range_encoder & renc, int symbol, const int pos_state );
+  void decrement_counter( const int pos_state ) { --counters[pos_state]; }
+
+  void update_prices()
+    {
+    bool high_pending = false;
+    for( int pos_state = 0; pos_state < pos_states; ++pos_state )
+      if( counters[pos_state] <= 0 )
+        { update_low_mid_prices( pos_state ); high_pending = true; }
+    if( high_pending && len_symbols > len_low_symbols + len_mid_symbols )
+      update_high_prices();
+    }
 
   int price( const int symbol, const int pos_state ) const
     { return prices[pos_state][symbol - min_match_len]; }
@@ -481,18 +518,15 @@ protected:
   Bit_model bm_align[dis_align_size];
 
   Range_encoder renc;
-  Len_encoder match_len_encoder;
-  Len_encoder rep_len_encoder;
+  Len_model match_len_model;
+  Len_model rep_len_model;
 
   unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; }
 
-  LZ_encoder_base( const File_header & header, const int match_len_limit,
-                   const int outfd )
+  LZ_encoder_base( const File_header & header, const int outfd )
     :
     crc_( 0xFFFFFFFFU ),
-    renc( outfd ),
-    match_len_encoder( match_len_limit ),
-    rep_len_encoder( match_len_limit )
+    renc( outfd )
     {
     for( int i = 0; i < File_header::size; ++i )
       renc.put_byte( header.data[i] );
@@ -503,8 +537,8 @@ protected:
 
   int price_matched( const uint8_t prev_byte, const uint8_t symbol,
                      const uint8_t match_byte ) const
-    { return ::price_matched( bm_literal[get_lit_state(prev_byte)],
-                              symbol, match_byte ); }
+    { return ::price_matched( bm_literal[get_lit_state(prev_byte)], symbol,
+                              match_byte ); }
 
   void encode_literal( const uint8_t prev_byte, const uint8_t symbol )
     { renc.encode_tree8( bm_literal[get_lit_state(prev_byte)], symbol ); }
@@ -516,7 +550,7 @@ protected:
 
   void encode_pair( const unsigned dis, const int len, const int pos_state )
     {
-    match_len_encoder.encode( renc, len, pos_state );
+    renc.encode_len( match_len_model, len, pos_state );
     const int dis_slot = get_slot( dis );
     renc.encode_tree6( bm_dis_slot[get_len_state(len)], dis_slot );
 
@@ -584,18 +618,18 @@ class LZ_encoder : public LZ_encoder_base
     };
 
   Matchfinder & matchfinder;
+  Len_prices match_len_prices;
+  Len_prices rep_len_prices;
   int pending_num_pairs;
-  struct Pair pairs[max_match_len+1];
+  Pair pairs[max_match_len+1];
   Trial trials[max_num_trials];
 
-  int dis_prices[len_states][modeled_distances];
   int dis_slot_prices[len_states][2*max_dictionary_bits];
+  int dis_prices[len_states][modeled_distances];
   int align_prices[dis_align_size];
-  int align_price_count;
   const int num_dis_slots;
 
-  void fill_align_prices();
-  void fill_distance_prices();
+  void update_distance_prices();
 
        // move-to-front dis in/into reps if( dis > 0 )
   static void mtf_reps( const int dis, int reps[num_rep_distances] )
@@ -636,12 +670,12 @@ class LZ_encoder : public LZ_encoder_base
   int price_rep0_len( const int len, const State state, const int pos_state ) const
     {
     return price_rep( 0, state, pos_state ) +
-           rep_len_encoder.price( len, pos_state );
+           rep_len_prices.price( len, pos_state );
     }
 
   int price_pair( const int dis, const int len, const int pos_state ) const
     {
-    const int price = match_len_encoder.price( len, pos_state );
+    const int price = match_len_prices.price( len, pos_state );
     const int len_state = get_len_state( len );
     if( dis < modeled_distances )
       return price + dis_prices[len_state][dis];
@@ -709,10 +743,11 @@ class LZ_encoder : public LZ_encoder_base
 public:
   LZ_encoder( Matchfinder & mf, const File_header & header, const int outfd )
     :
-    LZ_encoder_base( header, mf.match_len_limit(), outfd ),
+    LZ_encoder_base( header, outfd ),
     matchfinder( mf ),
+    match_len_prices( match_len_model, mf.match_len_limit() ),
+    rep_len_prices( rep_len_model, mf.match_len_limit() ),
     pending_num_pairs( 0 ),
-    align_price_count( 0 ),
     num_dis_slots( 2 * real_bits( mf.dictionary_size() - 1 ) )
     {}