Merging upstream version 1.14~rc1.

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

1 files changed, 66 insertions, 58 deletions

diff --git a/decoder.h b/decoder.h
index 92da2b3..c446802 100644
--- a/decoder.h
+++ b/decoder.h
@@ -1,5 +1,5 @@
 /*  Lziprecover - Data recovery tool for lzipped files
-    Copyright (C) 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+    Copyright (C) 2009, 2010, 2011, 2012, 2013 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
@@ -18,7 +18,7 @@
 class Range_decoder
   {
   enum { buffer_size = 16384 };
-  long long partial_member_pos;
+  unsigned long long partial_member_pos;
   uint8_t * const buffer;	// input buffer
   int pos;			// current pos in buffer
   int stream_pos;		// when reached, a new block must be read
@@ -42,22 +42,23 @@ public:
     code( 0 ),
     range( 0xFFFFFFFFU ),
     infd( ifd ),
-    at_stream_end( false ) {}
+    at_stream_end( false )
+    {}
 
   ~Range_decoder() { delete[] buffer; }
 
   bool code_is_zero() const { return ( code == 0 ); }
   bool finished() { return pos >= stream_pos && !read_block(); }
-  long long member_position() const { return partial_member_pos + pos; }
+  unsigned long long member_position() const { return partial_member_pos + pos; }
   void reset_member_position() { partial_member_pos = -pos; }
 
   uint8_t get_byte()
     {
-    if( finished() ) return 0x55;		// make code != 0
+    if( finished() ) return 0xAA;		// make code != 0
     return buffer[pos++];
     }
 
-  int read( uint8_t * const outbuf, const int size )
+  int read_data( uint8_t * const outbuf, const int size )
     {
     int rest = size;
     while( rest > 0 && !finished() )
@@ -67,14 +68,14 @@ public:
       pos += rd;
       rest -= rd;
       }
-    return ( rest > 0 ) ? size - rest : size;
+    return size - rest;
     }
 
   void load()
     {
     code = 0;
-    range = 0xFFFFFFFFU;
     for( int i = 0; i < 5; ++i ) code = (code << 8) | get_byte();
+    range = 0xFFFFFFFFU;
     }
 
   void normalize()
@@ -88,17 +89,14 @@ public:
     int symbol = 0;
     for( int i = num_bits; i > 0; --i )
       {
-      symbol <<= 1;
-      if( range <= 0x00FFFFFFU )
-        {
-        range <<= 7; code = (code << 8) | get_byte();
-        if( code >= range ) { code -= range; symbol |= 1; }
-        }
-      else
-        {
-        range >>= 1;
-        if( code >= range ) { code -= range; symbol |= 1; }
-        }
+      normalize();
+      range >>= 1;
+//      symbol <<= 1;
+//      if( code >= range ) { code -= range; symbol |= 1; }
+      const uint32_t mask = 0U - (code < range);
+      code -= range;
+      code += range & mask;
+      symbol = (symbol << 1) + (mask + 1);
       }
     return symbol;
     }
@@ -130,36 +128,63 @@ public:
     return model - (1 << num_bits);
     }
 
+  int decode_tree6( Bit_model bm[] )
+    {
+    int model = 1;
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    model = ( model << 1 ) | decode_bit( bm[model] );
+    return model - (1 << 6);
+    }
+
   int decode_tree_reversed( Bit_model bm[], const int num_bits )
     {
     int model = 1;
     int symbol = 0;
     for( int i = 0; i < num_bits; ++i )
       {
-      const int bit = decode_bit( bm[model] );
+      const bool bit = decode_bit( bm[model] );
       model <<= 1;
-      if( bit ) { model |= 1; symbol |= (1 << i); }
+      if( bit ) { ++model; symbol |= (1 << i); }
       }
     return symbol;
     }
 
-  int decode_matched( Bit_model bm[], const int match_byte )
+  int decode_tree_reversed4( Bit_model bm[] )
+    {
+    int model = 1;
+    int symbol = 0;
+    int bit = decode_bit( bm[model] );
+    model = (model << 1) + bit; symbol |= bit;
+    bit = decode_bit( bm[model] );
+    model = (model << 1) + bit; symbol |= (bit << 1);
+    bit = decode_bit( bm[model] );
+    model = (model << 1) + bit; symbol |= (bit << 2);
+    if( decode_bit( bm[model] ) ) symbol |= 8;
+    return symbol;
+    }
+
+  int decode_matched( Bit_model bm[], int match_byte )
     {
     Bit_model * const bm1 = bm + 0x100;
     int symbol = 1;
     for( int i = 7; i >= 0; --i )
       {
-      const int match_bit = ( match_byte >> i ) & 1;
-      const int bit = decode_bit( bm1[(match_bit<<8)+symbol] );
-      symbol = ( symbol << 1 ) | bit;
-      if( match_bit != bit )
+      match_byte <<= 1;
+      const int match_bit = match_byte & 0x100;
+      const int bit = decode_bit( bm1[match_bit+symbol] );
+      symbol = ( symbol << 1 ) + bit;
+      if( match_bit != bit << 8 )
         {
-        while( --i >= 0 )
-          symbol = ( symbol << 1 ) | decode_bit( bm[symbol] );
+        while( symbol < 0x100 )
+          symbol = ( symbol << 1 ) + decode_bit( bm[symbol] );
         break;
         }
       }
-    return symbol & 0xFF;
+    return symbol - 0x100;
     }
   };
 
@@ -186,29 +211,12 @@ public:
   };
 
 
-class Literal_decoder
-  {
-  Bit_model bm_literal[1<<literal_context_bits][0x300];
-
-  int lstate( const uint8_t prev_byte ) const
-    { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
-
-public:
-  uint8_t decode( Range_decoder & range_decoder, const uint8_t prev_byte )
-    { return range_decoder.decode_tree( bm_literal[lstate(prev_byte)], 8 ); }
-
-  uint8_t decode_matched( Range_decoder & range_decoder,
-                          const uint8_t prev_byte, const uint8_t match_byte )
-    { return range_decoder.decode_matched( bm_literal[lstate(prev_byte)],
-                                           match_byte ); }
-  };
-
-
 class LZ_decoder
   {
-  const long long outskip;
-  const long long outend;
-  long long partial_data_pos;
+  const unsigned long long outskip;
+  const unsigned long long outend;
+  unsigned long long partial_data_pos;
+  Range_decoder & range_decoder;
   const int dictionary_size;
   const int buffer_size;
   uint8_t * const buffer;	// output buffer
@@ -217,9 +225,8 @@ class LZ_decoder
   uint32_t crc_;
   const int outfd;		// output file descriptor
   const int member_version;
-  Range_decoder & range_decoder;
 
-  long long stream_position() const { return partial_data_pos + stream_pos; }
+  unsigned long long stream_position() const { return partial_data_pos + stream_pos; }
   void flush_data();
   bool verify_trailer( const Pretty_print & pp ) const;
 
@@ -248,7 +255,7 @@ class LZ_decoder
     if( i < 0 ) i += buffer_size;
     if( len < buffer_size - std::max( pos, i ) && len <= std::abs( pos - i ) )
       {
-      std::memcpy( buffer + pos, buffer + i, len );
+      std::memcpy( buffer + pos, buffer + i, len );	// no wrap, no overlap
       pos += len;
       }
     else for( ; len > 0; --len )
@@ -264,11 +271,13 @@ class LZ_decoder
 
 public:
   LZ_decoder( const File_header & header, Range_decoder & rdec, const int ofd,
-              const long long oskip = 0, const long long oend = LLONG_MAX )
+              const unsigned long long oskip = 0,
+              const unsigned long long oend = -1ULL )
     :
     outskip( oskip ),
     outend( oend ),
     partial_data_pos( 0 ),
+    range_decoder( rdec ),
     dictionary_size( header.dictionary_size() ),
     buffer_size( std::max( 65536, dictionary_size ) ),
     buffer( new uint8_t[buffer_size] ),
@@ -276,15 +285,14 @@ public:
     stream_pos( 0 ),
     crc_( 0xFFFFFFFFU ),
     outfd( ofd ),
-    member_version( header.version() ),
-    range_decoder( rdec )
+    member_version( header.version() )
     { buffer[buffer_size-1] = 0; }	// prev_byte of first_byte
 
   ~LZ_decoder() { delete[] buffer; }
 
-  uint32_t crc() const { return crc_ ^ 0xFFFFFFFFU; }
+  unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; }
 
-  long long data_position() const { return partial_data_pos + pos; }
+  unsigned long long data_position() const { return partial_data_pos + pos; }
 
   int decode_member( const Pretty_print & pp );
   };