summaryrefslogtreecommitdiffstats
path: root/decoder.h
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--decoder.h124
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 );
};