"Fossies" - the Fresh Open Source Software Archive

Member "lzip-1.22-rc2/fast_encoder.cc" (30 Apr 2020, 5873 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 "fast_encoder.cc" 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 #define _FILE_OFFSET_BITS 64
   19 
   20 #include <algorithm>
   21 #include <cerrno>
   22 #include <cstdlib>
   23 #include <cstring>
   24 #include <string>
   25 #include <vector>
   26 #include <stdint.h>
   27 
   28 #include "lzip.h"
   29 #include "encoder_base.h"
   30 #include "fast_encoder.h"
   31 
   32 
   33 int FLZ_encoder::longest_match_len( int * const distance )
   34   {
   35   enum { len_limit = 16 };
   36   const int available = std::min( available_bytes(), (int)max_match_len );
   37   if( available < len_limit ) return 0;
   38 
   39   const uint8_t * const data = ptr_to_current_pos();
   40   key4 = ( ( key4 << 4 ) ^ data[3] ) & key4_mask;
   41   const int pos1 = pos + 1;
   42   int newpos1 = prev_positions[key4];
   43   prev_positions[key4] = pos1;
   44   int32_t * ptr0 = pos_array + cyclic_pos;
   45   int maxlen = 0;
   46 
   47   for( int count = 4; ; )
   48     {
   49     int delta;
   50     if( newpos1 <= 0 || --count < 0 ||
   51         ( delta = pos1 - newpos1 ) > dictionary_size ) { *ptr0 = 0; break; }
   52     int32_t * const newptr = pos_array +
   53       ( cyclic_pos - delta +
   54           ( ( cyclic_pos >= delta ) ? 0 : dictionary_size + 1 ) );
   55 
   56     if( data[maxlen-delta] == data[maxlen] )
   57       {
   58       int len = 0;
   59       while( len < available && data[len-delta] == data[len] ) ++len;
   60       if( maxlen < len )
   61         { maxlen = len; *distance = delta - 1;
   62           if( maxlen >= len_limit ) { *ptr0 = *newptr; break; } }
   63       }
   64 
   65     *ptr0 = newpos1;
   66     ptr0 = newptr;
   67     newpos1 = *ptr0;
   68     }
   69   return maxlen;
   70   }
   71 
   72 
   73 bool FLZ_encoder::encode_member( const unsigned long long member_size )
   74   {
   75   const unsigned long long member_size_limit =
   76     member_size - Lzip_trailer::size - max_marker_size;
   77   int rep = 0;
   78   int reps[num_rep_distances];
   79   State state;
   80   for( int i = 0; i < num_rep_distances; ++i ) reps[i] = 0;
   81 
   82   if( data_position() != 0 || renc.member_position() != Lzip_header::size )
   83     return false;               // can be called only once
   84 
   85   if( !data_finished() )            // encode first byte
   86     {
   87     const uint8_t prev_byte = 0;
   88     const uint8_t cur_byte = peek( 0 );
   89     renc.encode_bit( bm_match[state()][0], 0 );
   90     encode_literal( prev_byte, cur_byte );
   91     crc32.update_byte( crc_, cur_byte );
   92     reset_key4();
   93     update_and_move( 1 );
   94     }
   95 
   96   while( !data_finished() && renc.member_position() < member_size_limit )
   97     {
   98     int match_distance;
   99     const int main_len = longest_match_len( &match_distance );
  100     const int pos_state = data_position() & pos_state_mask;
  101     int len = 0;
  102 
  103     for( int i = 0; i < num_rep_distances; ++i )
  104       {
  105       const int tlen = true_match_len( 0, reps[i] + 1 );
  106       if( tlen > len ) { len = tlen; rep = i; }
  107       }
  108     if( len > min_match_len && len + 3 > main_len )
  109       {
  110       crc32.update_buf( crc_, ptr_to_current_pos(), len );
  111       renc.encode_bit( bm_match[state()][pos_state], 1 );
  112       renc.encode_bit( bm_rep[state()], 1 );
  113       renc.encode_bit( bm_rep0[state()], rep != 0 );
  114       if( rep == 0 )
  115         renc.encode_bit( bm_len[state()][pos_state], 1 );
  116       else
  117         {
  118         renc.encode_bit( bm_rep1[state()], rep > 1 );
  119         if( rep > 1 )
  120           renc.encode_bit( bm_rep2[state()], rep > 2 );
  121         const int distance = reps[rep];
  122         for( int i = rep; i > 0; --i ) reps[i] = reps[i-1];
  123         reps[0] = distance;
  124         }
  125       state.set_rep();
  126       renc.encode_len( rep_len_model, len, pos_state );
  127       move_pos();
  128       update_and_move( len - 1 );
  129       continue;
  130       }
  131 
  132     if( main_len > min_match_len )
  133       {
  134       crc32.update_buf( crc_, ptr_to_current_pos(), main_len );
  135       renc.encode_bit( bm_match[state()][pos_state], 1 );
  136       renc.encode_bit( bm_rep[state()], 0 );
  137       state.set_match();
  138       for( int i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1];
  139       reps[0] = match_distance;
  140       encode_pair( match_distance, main_len, pos_state );
  141       move_pos();
  142       update_and_move( main_len - 1 );
  143       continue;
  144       }
  145 
  146     const uint8_t prev_byte = peek( 1 );
  147     const uint8_t cur_byte = peek( 0 );
  148     const uint8_t match_byte = peek( reps[0] + 1 );
  149     move_pos();
  150     crc32.update_byte( crc_, cur_byte );
  151 
  152     if( match_byte == cur_byte )
  153       {
  154       const int short_rep_price = price1( bm_match[state()][pos_state] ) +
  155                                   price1( bm_rep[state()] ) +
  156                                   price0( bm_rep0[state()] ) +
  157                                   price0( bm_len[state()][pos_state] );
  158       int price = price0( bm_match[state()][pos_state] );
  159       if( state.is_char() )
  160         price += price_literal( prev_byte, cur_byte );
  161       else
  162         price += price_matched( prev_byte, cur_byte, match_byte );
  163       if( short_rep_price < price )
  164         {
  165         renc.encode_bit( bm_match[state()][pos_state], 1 );
  166         renc.encode_bit( bm_rep[state()], 1 );
  167         renc.encode_bit( bm_rep0[state()], 0 );
  168         renc.encode_bit( bm_len[state()][pos_state], 0 );
  169         state.set_short_rep();
  170         continue;
  171         }
  172       }
  173 
  174     // literal byte
  175     renc.encode_bit( bm_match[state()][pos_state], 0 );
  176     if( state.is_char_set_char() )
  177       encode_literal( prev_byte, cur_byte );
  178     else
  179       encode_matched( prev_byte, cur_byte, match_byte );
  180     }
  181 
  182   full_flush( state );
  183   return true;
  184   }