Merging upstream version 1.13~rc2.

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

1 files changed, 84 insertions, 232 deletions

diff --git a/fast_encoder.cc b/fast_encoder.cc
index ba7c34c..319250a 100644
--- a/fast_encoder.cc
+++ b/fast_encoder.cc
@@ -1,5 +1,5 @@
 /*  Lzip - Data compressor based on the LZMA algorithm
-    Copyright (C) 2008, 2009, 2010, 2011 Antonio Diaz Diaz.
+    Copyright (C) 2008, 2009, 2010, 2011, 2012 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
@@ -30,97 +30,6 @@
 #include "fast_encoder.h"
 
 
-bool Fmatchfinder::read_block()
-  {
-  if( !at_stream_end && stream_pos < buffer_size )
-    {
-    const int size = buffer_size - stream_pos;
-    const int rd = readblock( infd, buffer + stream_pos, size );
-    stream_pos += rd;
-    if( rd != size && errno ) throw Error( "Read error" );
-    at_stream_end = ( rd < size );
-    }
-  return pos < stream_pos;
-  }
-
-
-Fmatchfinder::Fmatchfinder( const int ifd )
-  :
-  partial_data_pos( 0 ),
-  prev_positions( new int32_t[num_prev_positions] ),
-  pos( 0 ),
-  cyclic_pos( 0 ),
-  key4( 0 ),
-  stream_pos( 0 ),
-  match_len_limit_( 16 ),
-  infd( ifd ),
-  at_stream_end( false )
-  {
-  const int dict_size = 65536;
-  const int buffer_size_limit = ( 16 * dict_size ) + before_size + after_size;
-  buffer_size = dict_size;
-  buffer = (uint8_t *)std::malloc( buffer_size );
-  if( !buffer ) { delete[] prev_positions; throw std::bad_alloc(); }
-  if( read_block() && !at_stream_end && buffer_size < buffer_size_limit )
-    {
-    buffer_size = buffer_size_limit;
-    uint8_t * const tmp = (uint8_t *)std::realloc( buffer, buffer_size );
-    if( !tmp )
-      { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
-    buffer = tmp;
-    read_block();
-    }
-  if( at_stream_end && stream_pos < dict_size )
-    dictionary_size_ = std::max( (int)min_dictionary_size, stream_pos );
-  else dictionary_size_ = dict_size;
-  pos_limit = buffer_size;
-  if( !at_stream_end ) pos_limit -= after_size;
-  prev_pos_chain = new( std::nothrow ) int32_t[dictionary_size_];
-  if( !prev_pos_chain )
-    { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
-  for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
-  }
-
-
-void Fmatchfinder::reset()
-  {
-  const int size = stream_pos - pos;
-  if( size > 0 ) std::memmove( buffer, buffer + pos, size );
-  partial_data_pos = 0;
-  stream_pos -= pos;
-  pos = 0;
-  cyclic_pos = 0;
-  key4 = 0;
-  for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
-  read_block();
-  }
-
-
-void Fmatchfinder::move_pos()
-  {
-  if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0;
-  if( ++pos >= pos_limit )
-    {
-    if( pos > stream_pos )
-      internal_error( "pos > stream_pos in Fmatchfinder::move_pos" );
-    if( !at_stream_end )
-      {
-      const int offset = pos - dictionary_size_ - before_size;
-      const int size = stream_pos - offset;
-      std::memmove( buffer, buffer + offset, size );
-      partial_data_pos += offset;
-      pos -= offset;
-      stream_pos -= offset;
-      for( int i = 0; i < num_prev_positions; ++i )
-        if( prev_positions[i] >= 0 ) prev_positions[i] -= offset;
-      for( int i = 0; i < dictionary_size_; ++i )
-        if( prev_pos_chain[i] >= 0 ) prev_pos_chain[i] -= offset;
-      read_block();
-      }
-    }
-  }
-
-
 int Fmatchfinder::longest_match_len( int * const distance ) throw()
   {
   int len_limit = match_len_limit_;
@@ -130,28 +39,26 @@ int Fmatchfinder::longest_match_len( int * const distance ) throw()
     if( len_limit < 4 ) return 0;
     }
 
-  const uint8_t * const data = buffer + pos;
-  key4 = ( ( key4 << 4 ) ^ data[3] ) & ( num_prev_positions - 1 );
+  key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & ( num_prev_pos - 1 );
 
   int newpos = prev_positions[key4];
   prev_positions[key4] = pos;
 
-  int32_t * ptr0 = prev_pos_chain + cyclic_pos;
+  int32_t * ptr0 = pos_array + cyclic_pos;
   int maxlen = 0;
 
   for( int count = 4; ; )
     {
     if( newpos < (pos - dictionary_size_ + 1) || newpos < 0 || --count < 0 )
       { *ptr0 = -1; break; }
-    const uint8_t * const newdata = buffer + newpos;
     int len = 0;
-    if( newdata[maxlen] == data[maxlen] )
-      while( len < len_limit && newdata[len] == data[len] ) ++len;
+    if( buffer[maxlen+newpos] == buffer[maxlen+pos] )
+      while( len < len_limit && buffer[len+newpos] == buffer[len+pos] ) ++len;
 
     const int delta = pos - newpos;
     if( maxlen < len ) { maxlen = len; *distance = delta - 1; }
 
-    int32_t * const newptr = prev_pos_chain +
+    int32_t * const newptr = pos_array +
       ( cyclic_pos - delta +
           ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) );
 
@@ -167,6 +74,8 @@ int Fmatchfinder::longest_match_len( int * const distance ) throw()
       break;
       }
     }
+  if( maxlen == match_len_limit_ && maxlen < max_match_len )
+    maxlen += true_match_len( maxlen, *distance + 1, max_match_len - maxlen );
   return maxlen;
   }
 
@@ -180,68 +89,86 @@ void Fmatchfinder::longest_match_len() throw()
     if( len_limit < 4 ) return;
     }
 
-  const uint8_t * const data = buffer + pos;
-  key4 = ( ( key4 << 4 ) ^ data[3] ) & ( num_prev_positions - 1 );
+  key4 = ( ( key4 << 4 ) ^ buffer[pos+3] ) & ( num_prev_pos - 1 );
 
   const int newpos = prev_positions[key4];
   prev_positions[key4] = pos;
 
-  int32_t * const ptr0 = prev_pos_chain + cyclic_pos;
+  int32_t * const ptr0 = pos_array + cyclic_pos;
 
-  if( newpos < (pos - dictionary_size_ + 1) || newpos < 0 ) *ptr0 = -1;
+  if( newpos < (pos - dictionary_size_ + 1) || newpos < 0 )
+    *ptr0 = -1;
+  else if( buffer[len_limit-1+newpos] != buffer[len_limit-1+pos] ||
+           std::memcmp( buffer + newpos, buffer + pos, len_limit - 1 ) )
+    *ptr0 = newpos;
   else
     {
-    const uint8_t * const newdata = buffer + newpos;
-    if( newdata[len_limit-1] != data[len_limit-1] ||
-        std::memcmp( newdata, data, len_limit - 1 ) ) *ptr0 = newpos;
-    else
-      {
-      int idx = cyclic_pos - pos + newpos;
-      if( idx < 0 ) idx += dictionary_size_;
-      *ptr0 = prev_pos_chain[idx];
-      }
+    int idx = cyclic_pos - pos + newpos;
+    if( idx < 0 ) idx += dictionary_size_;
+    *ptr0 = pos_array[idx];
     }
   }
 
 
-// Return value == number of bytes advanced (len).
-// *disp returns the distance to encode.
-// ( *disp == -1 && len == 1 ) means literal.
-int FLZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
-                                     int * const disp, const State & state )
+void FLZ_encoder::sequence_optimizer( int reps[num_rep_distances],
+                                      State & state )
   {
-  const int main_len = read_match_distances();
+  int match_distance;
+  const int main_len = fmatchfinder.longest_match_len( &match_distance );
+  const int pos_state = fmatchfinder.data_position() & pos_state_mask;
+  int dis = 0;
+  int len = 0;
 
-  int replen = 0;
-  int rep_index = 0;
   for( int i = 0; i < num_rep_distances; ++i )
     {
-    const int len = fmatchfinder.true_match_len( 0, reps[i] + 1, max_match_len );
-    if( len > replen ) { replen = len; rep_index = i; }
+    const int tlen =
+      fmatchfinder.true_match_len( 0, reps[i] + 1, max_match_len );
+    if( tlen > len ) { len = tlen; dis = i; }
     }
-  if( replen > min_match_len && replen + 4 > main_len )
+  if( len > min_match_len && len + 4 > main_len )
     {
-    *disp = rep_index;
-    move_pos( replen, true );
-    return replen;
+    crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), len );
+    mtf_reps( dis, reps );
+    range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+    range_encoder.encode_bit( bm_rep[state()], 1 );
+    const bool bit = ( dis == 0 );
+    range_encoder.encode_bit( bm_rep0[state()], !bit );
+    if( bit )
+      range_encoder.encode_bit( bm_len[state()][pos_state], 1 );
+    else
+      {
+      range_encoder.encode_bit( bm_rep1[state()], dis > 1 );
+      if( dis > 1 )
+        range_encoder.encode_bit( bm_rep2[state()], dis > 2 );
+      }
+    rep_match_len_encoder.encode( range_encoder, len, pos_state );
+    state.set_rep();
+    move_pos( len );
+    return;
     }
 
   if( main_len > min_match_len ||
       ( main_len == min_match_len && match_distance < modeled_distances ) )
     {
-    *disp = num_rep_distances + match_distance;
-    move_pos( main_len, true );
-    return main_len;
+    crc32.update( crc_, fmatchfinder.ptr_to_current_pos(), main_len );
+    dis = match_distance;
+    mtf_reps( dis + num_rep_distances, reps );
+    range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+    range_encoder.encode_bit( bm_rep[state()], 0 );
+    encode_pair( dis, main_len, pos_state );
+    state.set_match();
+    move_pos( main_len );
+    return;
     }
 
+  const uint8_t prev_byte = fmatchfinder[-1];
   const uint8_t cur_byte = fmatchfinder[0];
   const uint8_t match_byte = fmatchfinder[-reps[0]-1];
+  crc32.update( crc_, cur_byte );
+  fmatchfinder.move_pos();
 
-  *disp = -1;
   if( match_byte == cur_byte )
     {
-    const uint8_t prev_byte = fmatchfinder[-1];
-    const int pos_state = fmatchfinder.data_position() & pos_state_mask;
     int price = price0( bm_match[state()][pos_state] );
     if( state.is_char() )
       price += literal_encoder.price_symbol( prev_byte, cur_byte );
@@ -251,44 +178,25 @@ int FLZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
                                 price1( bm_rep[state()] ) +
                                 price0( bm_rep0[state()] ) +
                                 price0( bm_len[state()][pos_state] );
-    if( short_rep_price < price ) *disp = 0;
+    if( short_rep_price < price )
+      {
+      range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
+      range_encoder.encode_bit( bm_rep[state()], 1 );
+      range_encoder.encode_bit( bm_rep0[state()], 0 );
+      range_encoder.encode_bit( bm_len[state()][pos_state], 0 );
+      state.set_short_rep();
+      return;
+      }
     }
 
-  fmatchfinder.move_pos();
-  return 1;
-  }
-
-
-     // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len)
-void FLZ_encoder::full_flush( const State & state )
-  {
-  const int pos_state = fmatchfinder.data_position() & pos_state_mask;
-  range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
-  range_encoder.encode_bit( bm_rep[state()], 0 );
-  encode_pair( 0xFFFFFFFFU, min_match_len, pos_state );
-  range_encoder.flush();
-  File_trailer trailer;
-  trailer.data_crc( crc() );
-  trailer.data_size( fmatchfinder.data_position() );
-  trailer.member_size( range_encoder.member_position() + File_trailer::size() );
-  for( int i = 0; i < File_trailer::size(); ++i )
-    range_encoder.put_byte( trailer.data[i] );
-  range_encoder.flush_data();
-  }
-
-
-FLZ_encoder::FLZ_encoder( Fmatchfinder & mf, const File_header & header,
-                          const int outfd )
-  :
-  crc_( 0xFFFFFFFFU ),
-  fmatchfinder( mf ),
-  range_encoder( outfd ),
-  len_encoder( fmatchfinder.match_len_limit() ),
-  rep_match_len_encoder( fmatchfinder.match_len_limit() ),
-  num_dis_slots( 2 * real_bits( fmatchfinder.dictionary_size() - 1 ) )
-  {
-  for( int i = 0; i < File_header::size; ++i )
-    range_encoder.put_byte( header.data[i] );
+  // literal byte
+  range_encoder.encode_bit( bm_match[state()][pos_state], 0 );
+  if( state.is_char() )
+    literal_encoder.encode( range_encoder, prev_byte, cur_byte );
+  else
+    literal_encoder.encode_matched( range_encoder,
+                                    prev_byte, cur_byte, match_byte );
+  state.set_char();
   }
 
 
@@ -304,77 +212,21 @@ bool FLZ_encoder::encode_member( const long long member_size )
       range_encoder.member_position() != File_header::size )
     return false;			// can be called only once
 
-  if( !fmatchfinder.finished() )		// encode first byte
+  if( !fmatchfinder.finished() )	// encode first byte
     {
     const uint8_t prev_byte = 0;
     const uint8_t cur_byte = fmatchfinder[0];
     range_encoder.encode_bit( bm_match[state()][0], 0 );
     literal_encoder.encode( range_encoder, prev_byte, cur_byte );
     crc32.update( crc_, cur_byte );
-    move_pos( 1 );
+    fmatchfinder.longest_match_len();
+    fmatchfinder.move_pos();
     }
 
-  while( true )
-    {
-    if( fmatchfinder.finished() ) { full_flush( state ); return true; }
-
-    const int pos_state = fmatchfinder.data_position() & pos_state_mask;
-    int dis;
-    const int len = sequence_optimizer( rep_distances, &dis, state );
-    if( len <= 0 ) return false;
+  while( !fmatchfinder.finished() &&
+         range_encoder.member_position() < member_size_limit )
+    sequence_optimizer( rep_distances, state );
 
-    bool bit = ( dis < 0 && len == 1 );
-    range_encoder.encode_bit( bm_match[state()][pos_state], !bit );
-    if( bit )				// literal byte
-      {
-      const uint8_t prev_byte = fmatchfinder[-len-1];
-      const uint8_t cur_byte = fmatchfinder[-len];
-      crc32.update( crc_, cur_byte );
-      if( state.is_char() )
-        literal_encoder.encode( range_encoder, prev_byte, cur_byte );
-      else
-        {
-        const uint8_t match_byte = fmatchfinder[-len-rep_distances[0]-1];
-        literal_encoder.encode_matched( range_encoder,
-                                        prev_byte, cur_byte, match_byte );
-        }
-      state.set_char();
-      }
-    else				// match or repeated match
-      {
-      crc32.update( crc_, fmatchfinder.ptr_to_current_pos() - len, len );
-      mtf_reps( dis, rep_distances );
-      bit = ( dis < num_rep_distances );
-      range_encoder.encode_bit( bm_rep[state()], bit );
-      if( bit )
-        {
-        bit = ( dis == 0 );
-        range_encoder.encode_bit( bm_rep0[state()], !bit );
-        if( bit )
-          range_encoder.encode_bit( bm_len[state()][pos_state], len > 1 );
-        else
-          {
-          range_encoder.encode_bit( bm_rep1[state()], dis > 1 );
-          if( dis > 1 )
-            range_encoder.encode_bit( bm_rep2[state()], dis > 2 );
-          }
-        if( len == 1 ) state.set_short_rep();
-        else
-          {
-          rep_match_len_encoder.encode( range_encoder, len, pos_state );
-          state.set_rep();
-          }
-        }
-      else
-        {
-        encode_pair( dis - num_rep_distances, len, pos_state );
-        state.set_match();
-        }
-      }
-    if( range_encoder.member_position() >= member_size_limit )
-      {
-      full_flush( state );
-      return true;
-      }
-    }
+  full_flush( fmatchfinder.data_position(), state );
+  return true;
   }