summaryrefslogtreecommitdiffstats
path: root/encoder.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--encoder.cc166
1 files changed, 83 insertions, 83 deletions
diff --git a/encoder.cc b/encoder.cc
index 79dd5cf..67e9d95 100644
--- a/encoder.cc
+++ b/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
@@ -33,7 +33,7 @@ Dis_slots dis_slots;
Prob_prices prob_prices;
-bool Matchfinder::read_block()
+bool Matchfinder_base::read_block()
{
if( !at_stream_end && stream_pos < buffer_size )
{
@@ -41,26 +41,51 @@ bool Matchfinder::read_block()
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 );
+ if( rd < size ) { at_stream_end = true; pos_limit = buffer_size; }
}
return pos < stream_pos;
}
-Matchfinder::Matchfinder( const int dict_size, const int len_limit,
- const int ifd )
+void Matchfinder_base::normalize_pos()
+ {
+ if( pos > stream_pos )
+ internal_error( "pos > stream_pos in Matchfinder_base::normalize_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 < pos_array_size; ++i )
+ if( pos_array[i] >= 0 ) pos_array[i] -= offset;
+ read_block();
+ }
+ }
+
+
+Matchfinder_base::Matchfinder_base( const int before, const int dict_size,
+ const int dict_factor, const int len_limit,
+ const int num_prev_pos, const int ifd,
+ const int pos_array_factor )
:
partial_data_pos( 0 ),
- prev_positions( new int32_t[num_prev_positions] ),
+ prev_positions( new int32_t[num_prev_pos] ),
+ num_prev_positions( num_prev_pos ),
+ before_size( before ),
+ match_len_limit_( len_limit ),
+ infd( ifd ),
pos( 0 ),
cyclic_pos( 0 ),
stream_pos( 0 ),
- match_len_limit_( len_limit ),
- cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 ),
- infd( ifd ),
at_stream_end( false )
{
- const int buffer_size_limit = ( 2 * dict_size ) + before_size + after_size;
+ const int buffer_size_limit =
+ ( dict_size * dict_factor ) + before_size + after_size;
buffer_size = std::max( 65536, dict_size );
buffer = (uint8_t *)std::malloc( buffer_size );
if( !buffer ) { delete[] prev_positions; throw std::bad_alloc(); }
@@ -78,14 +103,15 @@ Matchfinder::Matchfinder( const int dict_size, const int len_limit,
else dictionary_size_ = dict_size;
pos_limit = buffer_size;
if( !at_stream_end ) pos_limit -= after_size;
- prev_pos_tree = new( std::nothrow ) int32_t[2*dictionary_size_];
- if( !prev_pos_tree )
- { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
+ pos_array_size = pos_array_factor * dictionary_size_;
+ pos_array = new( std::nothrow ) int32_t[pos_array_size];
+ if( !pos_array )
+ { std::free( buffer ); delete[] prev_positions; throw std::bad_alloc(); }
}
-void Matchfinder::reset()
+void Matchfinder_base::reset()
{
const int size = stream_pos - pos;
if( size > 0 ) std::memmove( buffer, buffer + pos, size );
@@ -98,28 +124,13 @@ void Matchfinder::reset()
}
-void Matchfinder::move_pos()
+bool Matchfinder::dec_pos( const int ahead ) throw()
{
- if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0;
- if( ++pos >= pos_limit )
- {
- if( pos > stream_pos )
- internal_error( "pos > stream_pos in Matchfinder::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 < 2 * dictionary_size_; ++i )
- if( prev_pos_tree[i] >= 0 ) prev_pos_tree[i] -= offset;
- read_block();
- }
- }
+ if( ahead < 0 || pos < ahead ) return false;
+ pos -= ahead;
+ cyclic_pos -= ahead;
+ if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_;
+ return true;
}
@@ -162,7 +173,7 @@ int Matchfinder::longest_match_len( int * const distances ) throw()
int newpos = prev_positions[key4];
prev_positions[key4] = pos;
- int32_t * ptr0 = prev_pos_tree + ( cyclic_pos << 1 );
+ int32_t * ptr0 = pos_array + ( cyclic_pos << 1 );
int32_t * ptr1 = ptr0 + 1;
int len = 0, len0 = 0, len1 = 0;
@@ -175,7 +186,7 @@ int Matchfinder::longest_match_len( int * const distances ) throw()
const int delta = pos - newpos;
if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1;
- int32_t * const newptr = prev_pos_tree +
+ int32_t * const newptr = pos_array +
( ( cyclic_pos - delta +
( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) ) << 1 );
@@ -251,6 +262,25 @@ void Len_encoder::encode( Range_encoder & range_encoder, int symbol,
}
+ // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len)
+void LZ_encoder_base::full_flush( const long long data_position,
+ const State & state )
+ {
+ const int pos_state = 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( 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();
+ }
+
+
void LZ_encoder::fill_align_prices() throw()
{
for( int i = 0; i < dis_align_size; ++i )
@@ -300,7 +330,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
const State & state )
{
int main_len;
- if( longest_match_found > 0 ) // from previous call
+ if( longest_match_found > 0 ) // from previous call
{
main_len = longest_match_found;
longest_match_found = 0;
@@ -318,7 +348,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
{
trials[0].dis = rep_index;
trials[0].price = replens[rep_index];
- move_pos( replens[rep_index], true );
+ move_pos( replens[rep_index] );
return replens[rep_index];
}
@@ -327,7 +357,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
trials[0].dis = match_distances[matchfinder.match_len_limit()] +
num_rep_distances;
trials[0].price = main_len;
- move_pos( main_len, true );
+ move_pos( main_len );
return main_len;
}
@@ -415,6 +445,7 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
for( int i = 0; i < num_rep_distances; ++i )
cur_trial.reps[i] = trials[prev_index].reps[i];
+
if( prev_index == cur - 1 )
{
if( cur_trial.dis == 0 ) cur_trial.state.set_short_rep();
@@ -507,42 +538,6 @@ int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
}
- // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len)
-void LZ_encoder::full_flush( const State & state )
- {
- const int pos_state = matchfinder.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( matchfinder.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();
- }
-
-
-LZ_encoder::LZ_encoder( Matchfinder & mf, const File_header & header,
- const int outfd )
- :
- longest_match_found( 0 ),
- crc_( 0xFFFFFFFFU ),
- matchfinder( mf ),
- range_encoder( outfd ),
- len_encoder( matchfinder.match_len_limit() ),
- rep_match_len_encoder( matchfinder.match_len_limit() ),
- num_dis_slots( 2 * real_bits( matchfinder.dictionary_size() - 1 ) )
- {
- fill_align_prices();
-
- for( int i = 0; i < File_header::size; ++i )
- range_encoder.put_byte( header.data[i] );
- }
-
-
bool LZ_encoder::encode_member( const long long member_size )
{
const long long member_size_limit =
@@ -564,17 +559,17 @@ bool LZ_encoder::encode_member( const long long member_size )
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 );
+ matchfinder.longest_match_len();
+ matchfinder.move_pos();
}
- while( true )
+ while( !matchfinder.finished() )
{
- if( matchfinder.finished() ) { full_flush( state ); return true; }
if( fill_counter <= 0 )
{ fill_distance_prices(); fill_counter = fill_count; }
int ahead = sequence_optimizer( rep_distances, state );
- if( ahead <= 0 ) return false;
+ if( ahead <= 0 ) return false; // can't happen
fill_counter -= ahead;
for( int i = 0; ; )
@@ -586,7 +581,7 @@ bool LZ_encoder::encode_member( const long long member_size )
bool bit = ( dis < 0 && len == 1 );
range_encoder.encode_bit( bm_match[state()][pos_state], !bit );
- if( bit ) // literal byte
+ if( bit ) // literal byte
{
const uint8_t prev_byte = matchfinder[-ahead-1];
const uint8_t cur_byte = matchfinder[-ahead];
@@ -601,7 +596,7 @@ bool LZ_encoder::encode_member( const long long member_size )
}
state.set_char();
}
- else // match or repeated match
+ else // match or repeated match
{
crc32.update( crc_, matchfinder.ptr_to_current_pos() - ahead, len );
mtf_reps( dis, rep_distances );
@@ -629,6 +624,9 @@ bool LZ_encoder::encode_member( const long long member_size )
else
{
encode_pair( dis - num_rep_distances, len, pos_state );
+ if( dis_slots[dis - num_rep_distances] >= end_dis_model &&
+ --align_price_count <= 0 )
+ fill_align_prices();
state.set_match();
}
}
@@ -636,10 +634,12 @@ bool LZ_encoder::encode_member( const long long member_size )
if( range_encoder.member_position() >= member_size_limit )
{
if( !matchfinder.dec_pos( ahead ) ) return false;
- full_flush( state );
+ full_flush( matchfinder.data_position(), state );
return true;
}
if( ahead <= 0 ) break;
}
}
+ full_flush( matchfinder.data_position(), state );
+ return true;
}