"Fossies" - the Fresh Open Source Software Archive

Member "lzip-1.22-rc2/encoder.h" (30 Apr 2020, 9125 Bytes) of package /linux/misc/lzip-1.22-rc2.tar.lz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "encoder.h" see the Fossies "Dox" file reference documentation and the last Fossies "Diffs" side-by-side code changes report: 1.21_vs_1.22-rc1.

    1 /* Lzip - LZMA lossless data compressor
    2    Copyright (C) 2008-2020 Antonio Diaz Diaz.
    3 
    4    This program is free software: you can redistribute it and/or modify
    5    it under the terms of the GNU General Public License as published by
    6    the Free Software Foundation, either version 2 of the License, or
    7    (at your option) any later version.
    8 
    9    This program is distributed in the hope that it will be useful,
   10    but WITHOUT ANY WARRANTY; without even the implied warranty of
   11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   12    GNU General Public License for more details.
   13 
   14    You should have received a copy of the GNU General Public License
   15    along with this program.  If not, see <http://www.gnu.org/licenses/>.
   16 */
   17 
   18 class Len_prices
   19   {
   20   const Len_model & lm;
   21   const int len_symbols;
   22   const int count;
   23   int prices[pos_states][max_len_symbols];
   24   int counters[pos_states];         // may decrement below 0
   25 
   26   void update_low_mid_prices( const int pos_state )
   27     {
   28     int * const pps = prices[pos_state];
   29     int tmp = price0( lm.choice1 );
   30     int len = 0;
   31     for( ; len < len_low_symbols && len < len_symbols; ++len )
   32       pps[len] = tmp + price_symbol3( lm.bm_low[pos_state], len );
   33     if( len >= len_symbols ) return;
   34     tmp = price1( lm.choice1 ) + price0( lm.choice2 );
   35     for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len )
   36       pps[len] = tmp +
   37                  price_symbol3( lm.bm_mid[pos_state], len - len_low_symbols );
   38     }
   39 
   40   void update_high_prices()
   41     {
   42     const int tmp = price1( lm.choice1 ) + price1( lm.choice2 );
   43     for( int len = len_low_symbols + len_mid_symbols; len < len_symbols; ++len )
   44       // using 4 slots per value makes "price" faster
   45       prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = tmp +
   46         price_symbol8( lm.bm_high, len - len_low_symbols - len_mid_symbols );
   47     }
   48 
   49 public:
   50   void reset() { for( int i = 0; i < pos_states; ++i ) counters[i] = 0; }
   51 
   52   Len_prices( const Len_model & m, const int match_len_limit )
   53     :
   54     lm( m ),
   55     len_symbols( match_len_limit + 1 - min_match_len ),
   56     count( ( match_len_limit > 12 ) ? 1 : len_symbols )
   57     { reset(); }
   58 
   59   void decrement_counter( const int pos_state ) { --counters[pos_state]; }
   60 
   61   void update_prices()
   62     {
   63     bool high_pending = false;
   64     for( int pos_state = 0; pos_state < pos_states; ++pos_state )
   65       if( counters[pos_state] <= 0 )
   66         { counters[pos_state] = count;
   67           update_low_mid_prices( pos_state ); high_pending = true; }
   68     if( high_pending && len_symbols > len_low_symbols + len_mid_symbols )
   69       update_high_prices();
   70     }
   71 
   72   int price( const int len, const int pos_state ) const
   73     { return prices[pos_state][len - min_match_len]; }
   74   };
   75 
   76 
   77 class LZ_encoder : public LZ_encoder_base
   78   {
   79   struct Pair           // distance-length pair
   80     {
   81     int dis;
   82     int len;
   83     };
   84 
   85   enum { infinite_price = 0x0FFFFFFF,
   86          max_num_trials = 1 << 13,
   87          single_step_trial = -2,
   88          dual_step_trial = -1 };
   89 
   90   struct Trial
   91     {
   92     State state;
   93     int price;      // dual use var; cumulative price, match length
   94     int dis4;       // -1 for literal, or rep, or match distance + 4
   95     int prev_index; // index of prev trial in trials[]
   96     int prev_index2;    //   -2  trial is single step
   97             //   -1  literal + rep0
   98             // >= 0  ( rep or match ) + literal + rep0
   99     int reps[num_rep_distances];
  100 
  101     void update( const int pr, const int distance4, const int p_i )
  102       {
  103       if( pr < price )
  104         { price = pr; dis4 = distance4; prev_index = p_i;
  105           prev_index2 = single_step_trial; }
  106       }
  107 
  108     void update2( const int pr, const int p_i )
  109       {
  110       if( pr < price )
  111         { price = pr; dis4 = 0; prev_index = p_i;
  112           prev_index2 = dual_step_trial; }
  113       }
  114 
  115     void update3( const int pr, const int distance4, const int p_i,
  116                   const int p_i2 )
  117       {
  118       if( pr < price )
  119         { price = pr; dis4 = distance4; prev_index = p_i;
  120           prev_index2 = p_i2; }
  121       }
  122     };
  123 
  124   const int cycles;
  125   const int match_len_limit;
  126   Len_prices match_len_prices;
  127   Len_prices rep_len_prices;
  128   int pending_num_pairs;
  129   Pair pairs[max_match_len+1];
  130   Trial trials[max_num_trials];
  131 
  132   int dis_slot_prices[len_states][2*max_dictionary_bits];
  133   int dis_prices[len_states][modeled_distances];
  134   int align_prices[dis_align_size];
  135   const int num_dis_slots;
  136 
  137   bool dec_pos( const int ahead )
  138     {
  139     if( ahead < 0 || pos < ahead ) return false;
  140     pos -= ahead;
  141     if( cyclic_pos < ahead ) cyclic_pos += dictionary_size + 1;
  142     cyclic_pos -= ahead;
  143     return true;
  144     }
  145 
  146   int get_match_pairs( Pair * pairs = 0 );
  147   void update_distance_prices();
  148 
  149        // move-to-front dis in/into reps; do nothing if( dis4 <= 0 )
  150   static void mtf_reps( const int dis4, int reps[num_rep_distances] )
  151     {
  152     if( dis4 >= num_rep_distances )         // match
  153       {
  154       reps[3] = reps[2]; reps[2] = reps[1]; reps[1] = reps[0];
  155       reps[0] = dis4 - num_rep_distances;
  156       }
  157     else if( dis4 > 0 )             // repeated match
  158       {
  159       const int distance = reps[dis4];
  160       for( int i = dis4; i > 0; --i ) reps[i] = reps[i-1];
  161       reps[0] = distance;
  162       }
  163     }
  164 
  165   int price_shortrep( const State state, const int pos_state ) const
  166     {
  167     return price0( bm_rep0[state()] ) + price0( bm_len[state()][pos_state] );
  168     }
  169 
  170   int price_rep( const int rep, const State state, const int pos_state ) const
  171     {
  172     if( rep == 0 ) return price0( bm_rep0[state()] ) +
  173                           price1( bm_len[state()][pos_state] );
  174     int price = price1( bm_rep0[state()] );
  175     if( rep == 1 )
  176       price += price0( bm_rep1[state()] );
  177     else
  178       {
  179       price += price1( bm_rep1[state()] );
  180       price += price_bit( bm_rep2[state()], rep - 2 );
  181       }
  182     return price;
  183     }
  184 
  185   int price_rep0_len( const int len, const State state, const int pos_state ) const
  186     {
  187     return price_rep( 0, state, pos_state ) +
  188            rep_len_prices.price( len, pos_state );
  189     }
  190 
  191   int price_pair( const int dis, const int len, const int pos_state ) const
  192     {
  193     const int price = match_len_prices.price( len, pos_state );
  194     const int len_state = get_len_state( len );
  195     if( dis < modeled_distances )
  196       return price + dis_prices[len_state][dis];
  197     else
  198       return price + dis_slot_prices[len_state][get_slot( dis )] +
  199              align_prices[dis & (dis_align_size - 1)];
  200     }
  201 
  202   int read_match_distances()
  203     {
  204     const int num_pairs = get_match_pairs( pairs );
  205     if( num_pairs > 0 )
  206       {
  207       const int len = pairs[num_pairs-1].len;
  208       if( len == match_len_limit && len < max_match_len )
  209         pairs[num_pairs-1].len =
  210           true_match_len( len, pairs[num_pairs-1].dis + 1 );
  211       }
  212     return num_pairs;
  213     }
  214 
  215   void move_and_update( int n )
  216     {
  217     while( true )
  218       {
  219       move_pos();
  220       if( --n <= 0 ) break;
  221       get_match_pairs();
  222       }
  223     }
  224 
  225   void backward( int cur )
  226     {
  227     int dis4 = trials[cur].dis4;
  228     while( cur > 0 )
  229       {
  230       const int prev_index = trials[cur].prev_index;
  231       Trial & prev_trial = trials[prev_index];
  232 
  233       if( trials[cur].prev_index2 != single_step_trial )
  234         {
  235         prev_trial.dis4 = -1;                   // literal
  236         prev_trial.prev_index = prev_index - 1;
  237         prev_trial.prev_index2 = single_step_trial;
  238         if( trials[cur].prev_index2 >= 0 )
  239           {
  240           Trial & prev_trial2 = trials[prev_index-1];
  241           prev_trial2.dis4 = dis4; dis4 = 0;            // rep0
  242           prev_trial2.prev_index = trials[cur].prev_index2;
  243           prev_trial2.prev_index2 = single_step_trial;
  244           }
  245         }
  246       prev_trial.price = cur - prev_index;          // len
  247       cur = dis4; dis4 = prev_trial.dis4; prev_trial.dis4 = cur;
  248       cur = prev_index;
  249       }
  250     }
  251 
  252   int sequence_optimizer( const int reps[num_rep_distances],
  253                           const State state );
  254 
  255   enum { before_size = max_num_trials,
  256          // bytes to keep in buffer after pos
  257          after_size = ( 2 * max_match_len ) + 1,
  258          dict_factor = 2,
  259          num_prev_positions3 = 1 << 16,
  260          num_prev_positions2 = 1 << 10,
  261          num_prev_positions23 = num_prev_positions2 + num_prev_positions3,
  262          pos_array_factor = 2 };
  263 
  264 public:
  265   LZ_encoder( const int dict_size, const int len_limit,
  266               const int ifd, const int outfd )
  267     :
  268     LZ_encoder_base( before_size, dict_size, after_size, dict_factor,
  269                      num_prev_positions23, pos_array_factor, ifd, outfd ),
  270     cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 ),
  271     match_len_limit( len_limit ),
  272     match_len_prices( match_len_model, match_len_limit ),
  273     rep_len_prices( rep_len_model, match_len_limit ),
  274     pending_num_pairs( 0 ),
  275     num_dis_slots( 2 * real_bits( dictionary_size - 1 ) )
  276     {
  277     trials[1].prev_index = 0;
  278     trials[1].prev_index2 = single_step_trial;
  279     }
  280 
  281   void reset()
  282     {
  283     LZ_encoder_base::reset();
  284     match_len_prices.reset();
  285     rep_len_prices.reset();
  286     pending_num_pairs = 0;
  287     }
  288 
  289   bool encode_member( const unsigned long long member_size );
  290   };