summaryrefslogtreecommitdiffstats
path: root/encoder.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--encoder.c1271
1 files changed, 398 insertions, 873 deletions
diff --git a/encoder.c b/encoder.c
index bf0dafa..7b417ba 100644
--- a/encoder.c
+++ b/encoder.c
@@ -1,5 +1,5 @@
/* Lzlib - A compression library for lzip files
- Copyright (C) 2009, 2010, 2011, 2012 Antonio Diaz Diaz.
+ Copyright (C) 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
This library is free software: you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
@@ -25,121 +25,6 @@
Public License.
*/
-enum { max_num_trials = 1 << 12,
- price_shift = 6 };
-
-static inline int price0( const Bit_model probability )
- { return get_price( probability ); }
-
-static inline int price1( const Bit_model probability )
- { return get_price( bit_model_total-probability ); }
-
-static inline int price_bit( const Bit_model bm, const int bit )
- { if( bit ) return price1( bm ); else return price0( bm ); }
-
-
-static inline int price_symbol( const Bit_model bm[], int symbol,
- const int num_bits )
- {
- int price = 0;
- symbol |= ( 1 << num_bits );
- while( symbol > 1 )
- {
- const int bit = symbol & 1;
- symbol >>= 1;
- price += price_bit( bm[symbol], bit );
- }
- return price;
- }
-
-
-static inline int price_symbol_reversed( const Bit_model bm[], int symbol,
- const int num_bits )
- {
- int price = 0;
- int model = 1;
- int i;
- for( i = num_bits; i > 0; --i )
- {
- const int bit = symbol & 1;
- symbol >>= 1;
- price += price_bit( bm[model], bit );
- model = ( model << 1 ) | bit;
- }
- return price;
- }
-
-
-static inline int price_matched( const Bit_model bm[], const int symbol,
- const int match_byte )
- {
- int price = 0;
- int model = 1;
- int i;
-
- for( i = 7; i >= 0; --i )
- {
- const int match_bit = ( match_byte >> i ) & 1;
- int bit = ( symbol >> i ) & 1;
- price += price_bit( bm[(match_bit<<8)+model+0x100], bit );
- model = ( model << 1 ) | bit;
- if( match_bit != bit )
- {
- while( --i >= 0 )
- {
- bit = ( symbol >> i ) & 1;
- price += price_bit( bm[model], bit );
- model = ( model << 1 ) | bit;
- }
- break;
- }
- }
- return price;
- }
-
-
-enum { /* bytes to keep in buffer before dictionary */
- before_size = max_num_trials + 1,
- /* bytes to keep in buffer after pos */
- after_size = max_num_trials + max_match_len,
- num_prev_positions4 = 1 << 20,
- num_prev_positions3 = 1 << 18,
- num_prev_positions2 = 1 << 16,
- num_prev_positions = num_prev_positions4 + num_prev_positions3 +
- num_prev_positions2 };
-
-struct Matchfinder
- {
- long long partial_data_pos;
- uint8_t * buffer; /* input buffer */
- int32_t * prev_positions; /* last seen position of key */
- int32_t * prev_pos_tree;
- int dictionary_size; /* bytes to keep in buffer before pos */
- int buffer_size;
- int pos; /* current pos in buffer */
- int cyclic_pos; /* current pos in dictionary */
- int stream_pos; /* first byte not yet read from file */
- int pos_limit; /* when reached, a new block must be read */
- int match_len_limit;
- int cycles;
- bool at_stream_end; /* stream_pos shows real end of file */
- bool been_flushed;
- };
-
-
-static int Mf_write_data( struct Matchfinder * const mf,
- const uint8_t * const inbuf, const int size )
- {
- const int sz = min( mf->buffer_size - mf->stream_pos, size );
- if( !mf->at_stream_end && sz > 0 )
- {
- memcpy( mf->buffer + mf->stream_pos, inbuf, sz );
- mf->stream_pos += sz;
- }
- return sz;
- }
-
-
static bool Mf_normalize_pos( struct Matchfinder * const mf )
{
if( mf->pos > mf->stream_pos )
@@ -153,9 +38,9 @@ static bool Mf_normalize_pos( struct Matchfinder * const mf )
mf->partial_data_pos += offset;
mf->pos -= offset;
mf->stream_pos -= offset;
- for( i = 0; i < num_prev_positions; ++i )
+ for( i = 0; i < mf->num_prev_positions; ++i )
if( mf->prev_positions[i] >= 0 ) mf->prev_positions[i] -= offset;
- for( i = 0; i < 2 * mf->dictionary_size; ++i )
+ for( i = 0; i < 2 * ( mf->dictionary_size + 1 ); ++i )
if( mf->prev_pos_tree[i] >= 0 ) mf->prev_pos_tree[i] -= offset;
}
return true;
@@ -163,101 +48,60 @@ static bool Mf_normalize_pos( struct Matchfinder * const mf )
static bool Mf_init( struct Matchfinder * const mf,
- const int dict_size, const int len_limit )
+ const int dict_size, const int match_len_limit )
{
- int i;
+ const int buffer_size_limit = ( 2 * dict_size ) + before_size + after_size;
+ int i, size;
+
mf->partial_data_pos = 0;
- mf->dictionary_size = dict_size;
- mf->buffer_size = ( 2 * max( 65536, dict_size ) ) + before_size + after_size;
- mf->buffer = (uint8_t *)malloc( mf->buffer_size );
- mf->prev_positions = (int32_t *)malloc( num_prev_positions * sizeof (int32_t) );
- mf->prev_pos_tree = (int32_t *)malloc( 2 * dict_size * sizeof (int32_t) );
+ mf->match_len_limit = match_len_limit;
mf->pos = 0;
mf->cyclic_pos = 0;
mf->stream_pos = 0;
- mf->pos_limit = mf->buffer_size - after_size;
- mf->match_len_limit = len_limit;
- mf->cycles = ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256;
+ mf->cycles = ( match_len_limit < max_match_len ) ?
+ 16 + ( match_len_limit / 2 ) : 256;
mf->at_stream_end = false;
mf->been_flushed = false;
- if( !mf->buffer || !mf->prev_positions || !mf->prev_pos_tree )
- {
- if( mf->prev_pos_tree )
- { free( mf->prev_pos_tree ); mf->prev_pos_tree = 0; }
- if( mf->prev_positions )
- { free( mf->prev_positions ); mf->prev_positions = 0; }
- if( mf->buffer ) { free( mf->buffer ); mf->buffer = 0; }
- return false;
- }
- for( i = 0; i < num_prev_positions; ++i ) mf->prev_positions[i] = -1;
+ mf->buffer_size = max( 65536, buffer_size_limit );
+ mf->buffer = (uint8_t *)malloc( mf->buffer_size );
+ if( !mf->buffer ) return false;
+ mf->dictionary_size = dict_size;
+ mf->pos_limit = mf->buffer_size - after_size;
+ size = 1 << max( 16, real_bits( mf->dictionary_size - 1 ) - 2 );
+ if( mf->dictionary_size > 1 << 26 )
+ size >>= 1;
+ mf->key4_mask = size - 1;
+ size += num_prev_positions2;
+ size += num_prev_positions3;
+
+ mf->num_prev_positions = size;
+ size += ( 2 * ( mf->dictionary_size + 1 ) );
+ mf->prev_positions = (int32_t *)malloc( size * sizeof (int32_t) );
+ if( !mf->prev_positions ) { free( mf->buffer ); return false; }
+ mf->prev_pos_tree = mf->prev_positions + mf->num_prev_positions;
+ for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
return true;
}
-static inline void Mf_free( struct Matchfinder * const mf )
+static void Mf_adjust_distionary_size( struct Matchfinder * const mf )
{
- free( mf->prev_pos_tree ); mf->prev_pos_tree = 0;
- free( mf->prev_positions ); mf->prev_positions = 0;
- free( mf->buffer ); mf->buffer = 0;
- }
-
-static inline uint8_t Mf_peek( const struct Matchfinder * const mf, const int i )
- { return mf->buffer[mf->pos+i]; }
-
-static inline int Mf_available_bytes( const struct Matchfinder * const mf )
- { return mf->stream_pos - mf->pos; }
-
-static inline long long Mf_data_position( const struct Matchfinder * const mf )
- { return mf->partial_data_pos + mf->pos; }
-
-static inline bool Mf_finished( const struct Matchfinder * const mf )
- { return mf->at_stream_end && mf->pos >= mf->stream_pos; }
-
-static inline const uint8_t * Mf_ptr_to_current_pos( const struct Matchfinder * const mf )
- { return mf->buffer + mf->pos; }
-
-static inline void Mf_set_flushing( struct Matchfinder * const mf,
- const bool flushing )
- { mf->at_stream_end = flushing; }
-
-static inline int Mf_free_bytes( const struct Matchfinder * const mf )
- { if( mf->at_stream_end ) return 0; return mf->buffer_size - mf->stream_pos; }
-
-static inline bool Mf_enough_available_bytes( const struct Matchfinder * const mf )
- {
- return ( mf->pos + after_size <= mf->stream_pos ||
- ( mf->at_stream_end && mf->pos < mf->stream_pos ) );
- }
-
-static inline bool Mf_dec_pos( struct Matchfinder * const mf,
- const int ahead )
- {
- if( ahead < 0 || mf->pos < ahead ) return false;
- mf->pos -= ahead;
- mf->cyclic_pos -= ahead;
- if( mf->cyclic_pos < 0 ) mf->cyclic_pos += mf->dictionary_size;
- return true;
- }
-
-static inline int Mf_true_match_len( const struct Matchfinder * const mf,
- const int index, const int distance,
- int len_limit )
- {
- const uint8_t * const data = mf->buffer + mf->pos + index;
- int i = 0;
-
- if( index + len_limit > Mf_available_bytes( mf ) )
- len_limit = Mf_available_bytes( mf ) - index;
- while( i < len_limit && data[i-distance] == data[i] ) ++i;
- return i;
- }
-
-static inline bool Mf_move_pos( struct Matchfinder * const mf )
- {
- if( ++mf->cyclic_pos >= mf->dictionary_size ) mf->cyclic_pos = 0;
- if( ++mf->pos >= mf->pos_limit ) return Mf_normalize_pos( mf );
- return true;
+ if( mf->stream_pos < mf->dictionary_size )
+ {
+ int size;
+ mf->buffer_size =
+ mf->dictionary_size =
+ mf->pos_limit = max( min_dictionary_size, mf->stream_pos );
+ size = 1 << max( 16, real_bits( mf->dictionary_size - 1 ) - 2 );
+ if( mf->dictionary_size > 1 << 26 )
+ size >>= 1;
+ mf->key4_mask = size - 1;
+ size += num_prev_positions2;
+ size += num_prev_positions3;
+ mf->num_prev_positions = size;
+ mf->prev_pos_tree = mf->prev_positions + mf->num_prev_positions;
+ }
}
@@ -272,23 +116,23 @@ static void Mf_reset( struct Matchfinder * const mf )
mf->cyclic_pos = 0;
mf->at_stream_end = false;
mf->been_flushed = false;
- for( i = 0; i < num_prev_positions; ++i ) mf->prev_positions[i] = -1;
+ for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
}
-static int Mf_longest_match_len( struct Matchfinder * const mf,
- int * const distances )
+static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pairs )
{
int32_t * ptr0 = mf->prev_pos_tree + ( mf->cyclic_pos << 1 );
int32_t * ptr1 = ptr0 + 1;
int32_t * newptr;
- const uint8_t * newdata;
int len = 0, len0 = 0, len1 = 0;
int maxlen = min_match_len - 1;
- const int min_pos = (mf->pos >= mf->dictionary_size) ?
- (mf->pos - mf->dictionary_size + 1) : 0;
+ int num_pairs = 0;
+ const int min_pos = (mf->pos > mf->dictionary_size) ?
+ mf->pos - mf->dictionary_size : 0;
const uint8_t * const data = mf->buffer + mf->pos;
- int count, delta, key2, key3, key4, newpos, tmp;
+ int count, delta, key2, key3, key4, newpos;
+ unsigned tmp;
int len_limit = mf->match_len_limit;
if( len_limit > Mf_available_bytes( mf ) )
@@ -298,24 +142,39 @@ static int Mf_longest_match_len( struct Matchfinder * const mf,
if( len_limit < 4 ) { *ptr0 = *ptr1 = -1; return 0; }
}
- key2 = num_prev_positions4 + num_prev_positions3 +
- ( ( (int)data[0] << 8 ) | data[1] );
- tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 );
- key3 = num_prev_positions4 + (int)( tmp & ( num_prev_positions3 - 1 ) );
- key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) &
- ( num_prev_positions4 - 1 ) );
+ tmp = crc32[data[0]] ^ data[1];
+ key2 = tmp & ( num_prev_positions2 - 1 );
+ tmp ^= (uint32_t)data[2] << 8;
+ key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) );
+ key4 = num_prev_positions2 + num_prev_positions3 +
+ ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & mf->key4_mask );
- if( distances )
+ if( pairs )
{
- int np = mf->prev_positions[key2];
- if( np >= min_pos )
- { distances[2] = mf->pos - np - 1; maxlen = 2; }
- else distances[2] = 0x7FFFFFFF;
- np = mf->prev_positions[key3];
- if( np >= min_pos && mf->buffer[np] == data[0] )
- { distances[3] = mf->pos - np - 1; maxlen = 3; }
- else distances[3] = 0x7FFFFFFF;
- distances[4] = 0x7FFFFFFF;
+ int np2 = mf->prev_positions[key2];
+ int np3 = mf->prev_positions[key3];
+ if( np2 >= min_pos && mf->buffer[np2] == data[0] )
+ {
+ pairs[0].dis = mf->pos - np2 - 1;
+ pairs[0].len = maxlen = 2;
+ num_pairs = 1;
+ }
+ if( np2 != np3 && np3 >= min_pos && mf->buffer[np3] == data[0] )
+ {
+ maxlen = 3;
+ pairs[num_pairs].dis = mf->pos - np3 - 1;
+ ++num_pairs;
+ np2 = np3;
+ }
+ if( num_pairs > 0 )
+ {
+ delta = mf->pos - np2;
+ while( maxlen < len_limit && data[maxlen-delta] == data[maxlen] )
+ ++maxlen;
+ pairs[num_pairs-1].len = maxlen;
+ if( maxlen >= len_limit ) pairs = 0;
+ }
+ if( maxlen < 3 ) maxlen = 3;
}
mf->prev_positions[key2] = mf->pos;
@@ -326,249 +185,44 @@ static int Mf_longest_match_len( struct Matchfinder * const mf,
for( count = mf->cycles; ; )
{
if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; }
- newdata = mf->buffer + newpos;
- if( mf->been_flushed ) len = 0;
- while( len < len_limit && newdata[len] == data[len] ) ++len;
+ if( mf->been_flushed ) len = 0;
delta = mf->pos - newpos;
- if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1;
-
newptr = mf->prev_pos_tree +
( ( mf->cyclic_pos - delta +
- ( ( mf->cyclic_pos >= delta ) ? 0 : mf->dictionary_size ) ) << 1 );
-
- if( len < len_limit )
+ ( (mf->cyclic_pos >= delta) ? 0 : mf->dictionary_size + 1 ) ) << 1 );
+ if( data[len-delta] == data[len] )
{
- if( newdata[len] < data[len] )
+ while( ++len < len_limit && data[len-delta] == data[len] ) {}
+ if( pairs && maxlen < len )
{
- *ptr0 = newpos;
- ptr0 = newptr + 1;
- newpos = *ptr0;
- len0 = len; if( len1 < len ) len = len1;
+ pairs[num_pairs].dis = delta - 1;
+ pairs[num_pairs].len = maxlen = len;
+ ++num_pairs;
}
- else
+ if( len >= len_limit )
{
- *ptr1 = newpos;
- ptr1 = newptr;
- newpos = *ptr1;
- len1 = len; if( len0 < len ) len = len0;
+ *ptr0 = newptr[0];
+ *ptr1 = newptr[1];
+ break;
}
}
- else
+ if( data[len-delta] < data[len] )
{
- *ptr0 = newptr[0];
- *ptr1 = newptr[1];
- break;
+ *ptr0 = newpos;
+ ptr0 = newptr + 1;
+ newpos = *ptr0;
+ len0 = len; if( len1 < len ) len = len1;
}
- }
- if( distances )
- {
- if( distances[3] > distances[4] ) distances[3] = distances[4];
- if( distances[2] > distances[3] ) distances[2] = distances[3];
- }
- return maxlen;
- }
-
-
-enum { re_min_free_bytes = 2 * max_num_trials };
-
-struct Range_encoder
- {
- struct Circular_buffer cb;
- uint64_t low;
- long long partial_member_pos;
- uint32_t range;
- int ff_count;
- uint8_t cache;
- };
-
-static inline void Re_shift_low( struct Range_encoder * const renc )
- {
- const bool carry = ( renc->low > 0xFFFFFFFFU );
- if( carry || renc->low < 0xFF000000U )
- {
- Cb_put_byte( &renc->cb, renc->cache + carry );
- for( ; renc->ff_count > 0; --renc->ff_count )
- Cb_put_byte( &renc->cb, 0xFF + carry );
- renc->cache = renc->low >> 24;
- }
- else ++renc->ff_count;
- renc->low = ( renc->low & 0x00FFFFFFU ) << 8;
- }
-
-static inline bool Re_init( struct Range_encoder * const renc )
- {
- if( !Cb_init( &renc->cb, 65536 + re_min_free_bytes ) ) return false;
- renc->low = 0;
- renc->partial_member_pos = 0;
- renc->range = 0xFFFFFFFFU;
- renc->ff_count = 0;
- renc->cache = 0;
- return true;
- }
-
-static inline void Re_free( struct Range_encoder * const renc )
- { Cb_free( &renc->cb ); }
-
-static inline long long Re_member_position( const struct Range_encoder * const renc )
- { return renc->partial_member_pos + Cb_used_bytes( &renc->cb ) + renc->ff_count; }
-
-static inline bool Re_enough_free_bytes( const struct Range_encoder * const renc )
- { return Cb_free_bytes( &renc->cb ) >= re_min_free_bytes; }
-
-static inline int Re_read_data( struct Range_encoder * const renc,
- uint8_t * const out_buffer, const int out_size )
- {
- const int size = Cb_read_data( &renc->cb, out_buffer, out_size );
- if( size > 0 ) renc->partial_member_pos += size;
- return size;
- }
-
-static inline void Re_flush( struct Range_encoder * const renc )
- {
- int i; for( i = 0; i < 5; ++i ) Re_shift_low( renc );
- renc->low = 0;
- renc->range = 0xFFFFFFFFU;
- renc->ff_count = 0;
- renc->cache = 0;
- }
-
-static inline void Re_encode( struct Range_encoder * const renc,
- const int symbol, const int num_bits )
- {
- int i;
- for( i = num_bits - 1; i >= 0; --i )
- {
- renc->range >>= 1;
- if( (symbol >> i) & 1 ) renc->low += renc->range;
- if( renc->range <= 0x00FFFFFFU )
- { renc->range <<= 8; Re_shift_low( renc ); }
- }
- }
-
-static inline void Re_encode_bit( struct Range_encoder * const renc,
- Bit_model * const probability, const int bit )
- {
- const uint32_t bound = ( renc->range >> bit_model_total_bits ) * *probability;
- if( !bit )
- {
- renc->range = bound;
- *probability += (bit_model_total - *probability) >> bit_model_move_bits;
- }
- else
- {
- renc->low += bound;
- renc->range -= bound;
- *probability -= *probability >> bit_model_move_bits;
- }
- if( renc->range <= 0x00FFFFFFU )
- { renc->range <<= 8; Re_shift_low( renc ); }
- }
-
-static inline void Re_encode_tree( struct Range_encoder * const renc,
- Bit_model bm[], const int symbol, const int num_bits )
- {
- int mask = ( 1 << ( num_bits - 1 ) );
- int model = 1;
- int i;
- for( i = num_bits; i > 0; --i, mask >>= 1 )
- {
- const int bit = ( symbol & mask );
- Re_encode_bit( renc, &bm[model], bit );
- model <<= 1;
- if( bit ) model |= 1;
- }
- }
-
-static inline void Re_encode_tree_reversed( struct Range_encoder * const renc,
- Bit_model bm[], int symbol, const int num_bits )
- {
- int model = 1;
- int i;
- for( i = num_bits; i > 0; --i )
- {
- const int bit = symbol & 1;
- Re_encode_bit( renc, &bm[model], bit );
- model = ( model << 1 ) | bit;
- symbol >>= 1;
- }
- }
-
-static inline void Re_encode_matched( struct Range_encoder * const renc,
- Bit_model bm[], int symbol, int match_byte )
- {
- int model = 1;
- int i;
- for( i = 7; i >= 0; --i )
- {
- const int match_bit = ( match_byte >> i ) & 1;
- int bit = ( symbol >> i ) & 1;
- Re_encode_bit( renc, &bm[(match_bit<<8)+model+0x100], bit );
- model = ( model << 1 ) | bit;
- if( match_bit != bit )
+ else
{
- while( --i >= 0 )
- {
- bit = ( symbol >> i ) & 1;
- Re_encode_bit( renc, &bm[model], bit );
- model = ( model << 1 ) | bit;
- }
- break;
+ *ptr1 = newpos;
+ ptr1 = newptr;
+ newpos = *ptr1;
+ len1 = len; if( len0 < len ) len = len0;
}
}
- }
-
-
-struct Len_encoder
- {
- Bit_model choice1;
- Bit_model choice2;
- Bit_model bm_low[pos_states][len_low_symbols];
- Bit_model bm_mid[pos_states][len_mid_symbols];
- Bit_model bm_high[len_high_symbols];
- int prices[pos_states][max_len_symbols];
- int len_symbols;
- int counters[pos_states];
- };
-
-static void Lee_update_prices( struct Len_encoder * const len_encoder,
- const int pos_state )
- {
- int * const pps = len_encoder->prices[pos_state];
- int tmp = price0( len_encoder->choice1 );
- int len = 0;
- for( ; len < len_low_symbols && len < len_encoder->len_symbols; ++len )
- pps[len] = tmp +
- price_symbol( len_encoder->bm_low[pos_state], len, len_low_bits );
- tmp = price1( len_encoder->choice1 );
- for( ; len < len_low_symbols + len_mid_symbols && len < len_encoder->len_symbols; ++len )
- pps[len] = tmp + price0( len_encoder->choice2 ) +
- price_symbol( len_encoder->bm_mid[pos_state], len - len_low_symbols, len_mid_bits );
- for( ; len < len_encoder->len_symbols; ++len )
- /* using 4 slots per value makes "Lee_price" faster */
- len_encoder->prices[3][len] = len_encoder->prices[2][len] =
- len_encoder->prices[1][len] = len_encoder->prices[0][len] =
- tmp + price1( len_encoder->choice2 ) +
- price_symbol( len_encoder->bm_high, len - len_low_symbols - len_mid_symbols, len_high_bits );
- len_encoder->counters[pos_state] = len_encoder->len_symbols;
- }
-
-static void Lee_init( struct Len_encoder * const len_encoder,
- const int len_limit )
- {
- int i, j;
- Bm_init( &len_encoder->choice1 );
- Bm_init( &len_encoder->choice2 );
- for( i = 0; i < pos_states; ++i )
- for( j = 0; j < len_low_symbols; ++j )
- Bm_init( &len_encoder->bm_low[i][j] );
- for( i = 0; i < pos_states; ++i )
- for( j = 0; j < len_mid_symbols; ++j )
- Bm_init( &len_encoder->bm_mid[i][j] );
- for( i = 0; i < len_high_symbols; ++i )
- Bm_init( &len_encoder->bm_high[i] );
- len_encoder->len_symbols = len_limit + 1 - min_match_len;
- for( i = 0; i < pos_states; ++i ) Lee_update_prices( len_encoder, i );
+ return num_pairs;
}
@@ -603,112 +257,42 @@ static void Lee_encode( struct Len_encoder * const len_encoder,
}
-static inline int Lee_price( const struct Len_encoder * const len_encoder,
- const int symbol, const int pos_state )
- { return len_encoder->prices[pos_state][symbol - min_match_len]; }
-
-
-struct Literal_encoder
- {
- Bit_model bm_literal[1<<literal_context_bits][0x300];
- };
-
-static inline void Lie_init( struct Literal_encoder * const lienc )
- {
- int i, j;
- for( i = 0; i < 1<<literal_context_bits; ++i )
- for( j = 0; j < 0x300; ++j )
- Bm_init( &lienc->bm_literal[i][j] );
- }
-
-static inline int Lie_state( const uint8_t prev_byte )
- { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
-
-static inline void Lie_encode( struct Literal_encoder * const lienc,
- struct Range_encoder * const renc,
- uint8_t prev_byte, uint8_t symbol )
- { Re_encode_tree( renc, lienc->bm_literal[Lie_state(prev_byte)], symbol, 8 ); }
-
-static inline void Lie_encode_matched( struct Literal_encoder * const lienc,
- struct Range_encoder * const renc,
- uint8_t prev_byte, uint8_t symbol,
- uint8_t match_byte )
- { Re_encode_matched( renc, lienc->bm_literal[Lie_state(prev_byte)],
- symbol, match_byte ); }
-
-static inline int Lie_price_symbol( const struct Literal_encoder * const lienc,
- uint8_t prev_byte, uint8_t symbol )
- { return price_symbol( lienc->bm_literal[Lie_state(prev_byte)], symbol, 8 ); }
-
-static inline int Lie_price_matched( const struct Literal_encoder * const lienc,
- uint8_t prev_byte, uint8_t symbol,
- uint8_t match_byte )
- { return price_matched( lienc->bm_literal[Lie_state(prev_byte)],
- symbol, match_byte ); }
-
-
-enum { infinite_price = 0x0FFFFFFF,
- max_marker_size = 16,
- num_rep_distances = 4 }; /* must be 4 */
-
-struct Trial
- {
- State state;
- int dis;
- int prev_index; /* index of prev trial in trials[] */
- int price; /* dual use var; cumulative price, match length */
- int reps[num_rep_distances];
- };
-
-static inline void Tr_update( struct Trial * const trial,
- const int d, const int p_i, const int pr )
+ /* End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) */
+static bool LZe_full_flush( struct LZ_encoder * const encoder, const State state )
{
- if( pr < trial->price )
- { trial->dis = d; trial->prev_index = p_i; trial->price = pr; }
+ int i;
+ const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
+ File_trailer trailer;
+ if( encoder->member_finished ||
+ Cb_free_bytes( &encoder->range_encoder.cb ) < max_marker_size + Ft_size )
+ return false;
+ Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[state][pos_state], 1 );
+ Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep[state], 0 );
+ LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len, pos_state );
+ Re_flush( &encoder->range_encoder );
+ Ft_set_data_crc( trailer, LZe_crc( encoder ) );
+ Ft_set_data_size( trailer, Mf_data_position( encoder->matchfinder ) );
+ Ft_set_member_size( trailer, Re_member_position( &encoder->range_encoder ) +
+ Ft_size );
+ for( i = 0; i < Ft_size; ++i )
+ Cb_put_byte( &encoder->range_encoder.cb, trailer[i] );
+ return true;
}
-struct LZ_encoder
- {
- long long member_size_limit;
- int longest_match_found;
- uint32_t crc;
-
- Bit_model bm_match[states][pos_states];
- Bit_model bm_rep[states];
- Bit_model bm_rep0[states];
- Bit_model bm_rep1[states];
- Bit_model bm_rep2[states];
- Bit_model bm_len[states][pos_states];
- Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
- Bit_model bm_dis[modeled_distances-end_dis_model+1];
- Bit_model bm_align[dis_align_size];
-
- struct Matchfinder * matchfinder;
- struct Range_encoder range_encoder;
- struct Len_encoder len_encoder;
- struct Len_encoder rep_match_len_encoder;
- struct Literal_encoder literal_encoder;
-
- int num_dis_slots;
- int rep_distances[num_rep_distances];
- int match_distances[max_match_len+1];
- struct Trial trials[max_num_trials];
-
- int dis_slot_prices[max_dis_states][2*max_dictionary_bits];
- int dis_prices[max_dis_states][modeled_distances];
- int align_prices[dis_align_size];
- int align_price_count;
- int fill_counter;
- State state;
- bool member_finished;
- };
-
-
-static inline bool LZe_member_finished( const struct LZ_encoder * const encoder )
+ /* Sync Flush mark => (dis == 0xFFFFFFFFU, len == min_match_len + 1) */
+static bool LZe_sync_flush( struct LZ_encoder * const encoder )
{
- return ( encoder->member_finished &&
- !Cb_used_bytes( &encoder->range_encoder.cb ) );
+ const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
+ const State state = encoder->state;
+ if( encoder->member_finished ||
+ Cb_free_bytes( &encoder->range_encoder.cb ) < max_marker_size )
+ return false;
+ Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[state][pos_state], 1 );
+ Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep[state], 0 );
+ LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len + 1, pos_state );
+ Re_flush( &encoder->range_encoder );
+ return true;
}
@@ -731,7 +315,7 @@ static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
const int direct_bits = ( dis_slot >> 1 ) - 1;
const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
const int price =
- price_symbol_reversed( encoder->bm_dis + base - dis_slot,
+ price_symbol_reversed( encoder->bm_dis + base - dis_slot - 1,
dis - base, direct_bits );
for( dis_state = 0; dis_state < max_dis_states; ++dis_state )
encoder->dis_prices[dis_state][dis] = price;
@@ -747,7 +331,7 @@ static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits );
for( ; slot < encoder->num_dis_slots; ++slot )
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) +
- (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift );
+ (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift_bits );
for( dis = 0; dis < start_dis_model; ++dis )
dp[dis] = dsp[dis];
@@ -759,229 +343,44 @@ static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
static bool LZe_init( struct LZ_encoder * const encoder,
struct Matchfinder * const mf,
- const File_header header, const long long member_size )
+ const File_header header,
+ const unsigned long long member_size )
{
- int i, j;
+ int i;
encoder->member_size_limit = member_size - Ft_size - max_marker_size;
- encoder->longest_match_found = 0;
+ encoder->pending_num_pairs = 0;
encoder->crc = 0xFFFFFFFFU;
- for( i = 0; i < states; ++i )
- {
- for( j = 0; j < pos_states; ++j )
- {
- Bm_init( &encoder->bm_match[i][j] );
- Bm_init( &encoder->bm_len[i][j] );
- }
- Bm_init( &encoder->bm_rep[i] );
- Bm_init( &encoder->bm_rep0[i] );
- Bm_init( &encoder->bm_rep1[i] );
- Bm_init( &encoder->bm_rep2[i] );
- }
- for( i = 0; i < max_dis_states; ++i )
- for( j = 0; j < 1<<dis_slot_bits; ++j )
- Bm_init( &encoder->bm_dis_slot[i][j] );
- for( i = 0; i < modeled_distances-end_dis_model+1; ++i )
- Bm_init( &encoder->bm_dis[i] );
- for( i = 0; i < dis_align_size; ++i )
- Bm_init( &encoder->bm_align[i] );
+ Bm_array_init( encoder->bm_literal[0], (1 << literal_context_bits) * 0x300 );
+ Bm_array_init( encoder->bm_match[0], states * pos_states );
+ Bm_array_init( encoder->bm_rep, states );
+ Bm_array_init( encoder->bm_rep0, states );
+ Bm_array_init( encoder->bm_rep1, states );
+ Bm_array_init( encoder->bm_rep2, states );
+ Bm_array_init( encoder->bm_len[0], states * pos_states );
+ Bm_array_init( encoder->bm_dis_slot[0], max_dis_states * (1 << dis_slot_bits) );
+ Bm_array_init( encoder->bm_dis, modeled_distances - end_dis_model );
+ Bm_array_init( encoder->bm_align, dis_align_size );
encoder->matchfinder = mf;
if( !Re_init( &encoder->range_encoder ) ) return false;
Lee_init( &encoder->len_encoder, encoder->matchfinder->match_len_limit );
Lee_init( &encoder->rep_match_len_encoder, encoder->matchfinder->match_len_limit );
- Lie_init( &encoder->literal_encoder );
encoder->num_dis_slots =
2 * real_bits( encoder->matchfinder->dictionary_size - 1 );
+
for( i = 0; i < num_rep_distances; ++i ) encoder->rep_distances[i] = 0;
+ encoder->align_price_count = 0;
encoder->fill_counter = 0;
encoder->state = 0;
encoder->member_finished = false;
- LZe_fill_align_prices( encoder );
-
for( i = 0; i < Fh_size; ++i )
Cb_put_byte( &encoder->range_encoder.cb, header[i] );
return true;
}
-static inline void LZe_free( struct LZ_encoder * const encoder )
- {
- Re_free( &encoder->range_encoder );
- }
-
-static inline uint32_t LZe_crc( const struct LZ_encoder * const encoder )
- { return encoder->crc ^ 0xFFFFFFFFU; }
-
- /* move-to-front dis in/into reps */
-static inline void LZe_mtf_reps( const int dis, int reps[num_rep_distances] )
- {
- int i;
- if( dis >= num_rep_distances )
- {
- for( i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1];
- reps[0] = dis - num_rep_distances;
- }
- else if( dis > 0 )
- {
- const int distance = reps[dis];
- for( i = dis; i > 0; --i ) reps[i] = reps[i-1];
- reps[0] = distance;
- }
- }
-
-static inline int LZe_price_rep_len1( const struct LZ_encoder * const encoder,
- const State state, const int pos_state )
- {
- return price0( encoder->bm_rep0[state] ) +
- price0( encoder->bm_len[state][pos_state] );
- }
-
-static inline int LZe_price_rep( const struct LZ_encoder * const encoder,
- const int rep,
- const State state, const int pos_state )
- {
- int price;
- if( rep == 0 ) return price0( encoder->bm_rep0[state] ) +
- price1( encoder->bm_len[state][pos_state] );
- price = price1( encoder->bm_rep0[state] );
- if( rep == 1 )
- price += price0( encoder->bm_rep1[state] );
- else
- {
- price += price1( encoder->bm_rep1[state] );
- price += price_bit( encoder->bm_rep2[state], rep - 2 );
- }
- return price;
- }
-
-static inline int LZe_price_dis( const struct LZ_encoder * const encoder,
- const int dis, const int dis_state )
- {
- if( dis < modeled_distances )
- return encoder->dis_prices[dis_state][dis];
- else
- return encoder->dis_slot_prices[dis_state][get_slot( dis )] +
- encoder->align_prices[dis & (dis_align_size - 1)];
- }
-
-static inline int LZe_price_pair( const struct LZ_encoder * const encoder,
- const int dis, const int len,
- const int pos_state )
- {
- if( len <= min_match_len && dis >= modeled_distances )
- return infinite_price;
- return Lee_price( &encoder->len_encoder, len, pos_state ) +
- LZe_price_dis( encoder, dis, get_dis_state( len ) );
- }
-
-static inline void LZe_encode_pair( struct LZ_encoder * const encoder,
- const uint32_t dis, const int len,
- const int pos_state )
- {
- const int dis_slot = get_slot( dis );
- Lee_encode( &encoder->len_encoder, &encoder->range_encoder, len, pos_state );
- Re_encode_tree( &encoder->range_encoder,
- encoder->bm_dis_slot[get_dis_state(len)],
- dis_slot, dis_slot_bits );
-
- if( dis_slot >= start_dis_model )
- {
- const int direct_bits = ( dis_slot >> 1 ) - 1;
- const uint32_t base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
- const uint32_t direct_dis = dis - base;
-
- if( dis_slot < end_dis_model )
- Re_encode_tree_reversed( &encoder->range_encoder,
- encoder->bm_dis + base - dis_slot,
- direct_dis, direct_bits );
- else
- {
- Re_encode( &encoder->range_encoder, direct_dis >> dis_align_bits,
- direct_bits - dis_align_bits );
- Re_encode_tree_reversed( &encoder->range_encoder, encoder->bm_align,
- direct_dis, dis_align_bits );
- if( --encoder->align_price_count <= 0 ) LZe_fill_align_prices( encoder );
- }
- }
- }
-
- /* End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) */
-static bool LZe_full_flush( struct LZ_encoder * const encoder, const State state )
- {
- int i;
- const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
- File_trailer trailer;
- if( encoder->member_finished ||
- Cb_free_bytes( &encoder->range_encoder.cb ) < Ft_size + max_marker_size )
- return false;
- Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[state][pos_state], 1 );
- Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep[state], 0 );
- LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len, pos_state );
- Re_flush( &encoder->range_encoder );
- Ft_set_data_crc( trailer, LZe_crc( encoder ) );
- Ft_set_data_size( trailer, Mf_data_position( encoder->matchfinder ) );
- Ft_set_member_size( trailer, Re_member_position( &encoder->range_encoder ) +
- Ft_size );
- for( i = 0; i < Ft_size; ++i )
- Cb_put_byte( &encoder->range_encoder.cb, trailer[i] );
- return true;
- }
-
-
- /* Sync Flush mark => (dis == 0xFFFFFFFFU, len == min_match_len + 1) */
-static bool LZe_sync_flush( struct LZ_encoder * const encoder )
- {
- const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
- const State state = encoder->state;
- if( encoder->member_finished ||
- Cb_free_bytes( &encoder->range_encoder.cb ) < max_marker_size )
- return false;
- Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[state][pos_state], 1 );
- Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep[state], 0 );
- LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len + 1, pos_state );
- Re_flush( &encoder->range_encoder );
- return true;
- }
-
-
-static inline int LZe_read_match_distances( struct LZ_encoder * const encoder )
- {
- int len = Mf_longest_match_len( encoder->matchfinder,
- encoder->match_distances );
- if( len == encoder->matchfinder->match_len_limit && len < max_match_len )
- len += Mf_true_match_len( encoder->matchfinder, len,
- encoder->match_distances[len] + 1,
- max_match_len - len );
- return len;
- }
-
-static inline bool LZe_move_pos( struct LZ_encoder * const encoder, int n )
- {
- if( --n >= 0 && !Mf_move_pos( encoder->matchfinder ) ) return false;
- while( --n >= 0 )
- {
- Mf_longest_match_len( encoder->matchfinder, 0 );
- if( !Mf_move_pos( encoder->matchfinder ) ) return false;
- }
- return true;
- }
-
-static inline void LZe_backward( struct LZ_encoder * const encoder, int cur )
- {
- int * const dis = &encoder->trials[cur].dis;
- while( cur > 0 )
- {
- const int prev_index = encoder->trials[cur].prev_index;
- struct Trial * const prev_trial = &encoder->trials[prev_index];
- prev_trial->price = cur - prev_index; /* len */
- cur = *dis; *dis = prev_trial->dis; prev_trial->dis = cur;
- cur = prev_index;
- }
- }
-
-
/* Return value == number of bytes advanced (ahead).
trials[0]..trials[retval-1] contain the steps to encode.
( trials[0].dis == -1 && trials[0].price == 1 ) means literal.
@@ -990,16 +389,18 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
const int reps[num_rep_distances],
const State state )
{
- int main_len, i, rep, cur = 0, num_trials;
+ int main_len, num_pairs, i, rep, cur = 0, num_trials, len;
int replens[num_rep_distances];
int rep_index = 0;
- if( encoder->longest_match_found > 0 ) /* from previous call */
+ if( encoder->pending_num_pairs > 0 ) /* from previous call */
{
- main_len = encoder->longest_match_found;
- encoder->longest_match_found = 0;
+ num_pairs = encoder->pending_num_pairs;
+ encoder->pending_num_pairs = 0;
}
- else main_len = LZe_read_match_distances( encoder );
+ else
+ num_pairs = LZe_read_match_distances( encoder );
+ main_len = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
for( i = 0; i < num_rep_distances; ++i )
{
@@ -1017,9 +418,7 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
if( main_len >= encoder->matchfinder->match_len_limit )
{
- encoder->trials[0].dis =
- encoder->match_distances[encoder->matchfinder->match_len_limit] +
- num_rep_distances;
+ encoder->trials[0].dis = encoder->pairs[num_pairs-1].dis + num_rep_distances;
encoder->trials[0].price = main_len;
if( !LZe_move_pos( encoder, main_len ) ) return 0;
return main_len;
@@ -1034,23 +433,22 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
const uint8_t match_byte = Mf_peek( encoder->matchfinder, -reps[0]-1 );
encoder->trials[0].state = state;
- for( i = 0; i < num_rep_distances; ++i )
- encoder->trials[0].reps[i] = reps[i];
encoder->trials[1].dis = -1;
- encoder->trials[1].prev_index = 0;
encoder->trials[1].price = price0( encoder->bm_match[state][pos_state] );
if( St_is_char( state ) )
encoder->trials[1].price +=
- Lie_price_symbol( &encoder->literal_encoder, prev_byte, cur_byte );
+ LZe_price_literal( encoder, prev_byte, cur_byte );
else
encoder->trials[1].price +=
- Lie_price_matched( &encoder->literal_encoder, prev_byte, cur_byte, match_byte );
+ LZe_price_matched( encoder, prev_byte, cur_byte, match_byte );
if( match_byte == cur_byte )
- Tr_update( &encoder->trials[1], 0, 0, rep_match_price +
- LZe_price_rep_len1( encoder, state, pos_state ) );
+ Tr_update( &encoder->trials[1], rep_match_price +
+ LZe_price_rep_len1( encoder, state, pos_state ), 0, 0 );
- if( main_len < min_match_len )
+ num_trials = max( main_len, replens[rep_index] );
+
+ if( num_trials < min_match_len )
{
encoder->trials[0].dis = encoder->trials[1].dis;
encoder->trials[0].price = 1;
@@ -1058,45 +456,51 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
return 1;
}
- if( main_len <= replens[rep_index] )
+ for( i = 0; i < num_rep_distances; ++i )
+ encoder->trials[0].reps[i] = reps[i];
+ encoder->trials[1].prev_index = 0;
+ encoder->trials[1].prev_index2 = single_step_trial;
+
+ for( len = min_match_len; len <= num_trials; ++len )
+ encoder->trials[len].price = infinite_price;
+
+ for( rep = 0; rep < num_rep_distances; ++rep )
{
- int len;
- main_len = replens[rep_index];
- for( len = min_match_len; len <= main_len; ++len )
- encoder->trials[len].price = infinite_price;
+ int price;
+ if( replens[rep] < min_match_len ) continue;
+ price = rep_match_price + LZe_price_rep( encoder, rep, state, pos_state );
+
+ for( len = min_match_len; len <= replens[rep]; ++len )
+ Tr_update( &encoder->trials[len], price +
+ Lee_price( &encoder->rep_match_len_encoder, len, pos_state ),
+ rep, 0 );
}
- else
+
+ if( main_len > replens[0] )
{
- int len;
const int normal_match_price = match_price + price0( encoder->bm_rep[state] );
- for( len = min_match_len; len <= main_len; ++len )
+ i = 0, len = max( replens[0] + 1, min_match_len );
+ while( len > encoder->pairs[i].len ) ++i;
+ while( true )
{
- encoder->trials[len].dis = encoder->match_distances[len] + num_rep_distances;
- encoder->trials[len].prev_index = 0;
- encoder->trials[len].price = normal_match_price +
- LZe_price_pair( encoder, encoder->match_distances[len], len, pos_state );
+ const int dis = encoder->pairs[i].dis;
+ Tr_update( &encoder->trials[len], normal_match_price +
+ LZe_price_pair( encoder, dis, len, pos_state ),
+ dis + num_rep_distances, 0 );
+ if( ++len > encoder->pairs[i].len && ++i >= num_pairs ) break;
}
}
-
- for( rep = 0; rep < num_rep_distances; ++rep )
- {
- const int price = rep_match_price +
- LZe_price_rep( encoder, rep, state, pos_state );
- int len;
- for( len = min_match_len; len <= replens[rep]; ++len )
- Tr_update( &encoder->trials[len], rep, 0, price +
- Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) );
- }
}
- num_trials = main_len;
if( !Mf_move_pos( encoder->matchfinder ) ) return 0;
- while( true )
+ while( true ) /* price optimization loop */
{
struct Trial *cur_trial, *next_trial;
- int newlen, pos_state, prev_index, len_limit;
+ int newlen, pos_state, prev_index, prev_index2, available_bytes, len_limit;
+ int start_len = min_match_len;
int next_price, match_price, rep_match_price;
+ State cur_state;
uint8_t prev_byte, cur_byte, match_byte;
if( ++cur >= num_trials ) /* no more initialized trials */
@@ -1104,33 +508,70 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
LZe_backward( encoder, cur );
return cur;
}
- newlen = LZe_read_match_distances( encoder );
+
+ num_pairs = LZe_read_match_distances( encoder );
+ newlen = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
if( newlen >= encoder->matchfinder->match_len_limit )
{
- encoder->longest_match_found = newlen;
+ encoder->pending_num_pairs = num_pairs;
LZe_backward( encoder, cur );
return cur;
}
+ /* give final values to current trial */
cur_trial = &encoder->trials[cur];
prev_index = cur_trial->prev_index;
+ prev_index2 = cur_trial->prev_index2;
- cur_trial->state = encoder->trials[prev_index].state;
-
- for( i = 0; i < num_rep_distances; ++i )
- cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
+ if( prev_index2 != single_step_trial )
+ {
+ --prev_index;
+ if( prev_index2 >= 0 )
+ {
+ cur_state = encoder->trials[prev_index2].state;
+ if( cur_trial->dis2 < num_rep_distances )
+ cur_state = St_set_rep( cur_state );
+ else
+ cur_state = St_set_match( cur_state );
+ }
+ else
+ cur_state = encoder->trials[prev_index].state;
+ cur_state = St_set_char( cur_state );
+ }
+ else
+ cur_state = encoder->trials[prev_index].state;
if( prev_index == cur - 1 )
{
- if( cur_trial->dis == 0 ) St_set_short_rep( &cur_trial->state );
- else St_set_char( &cur_trial->state );
+ if( cur_trial->dis == 0 )
+ cur_state = St_set_short_rep( cur_state );
+ else
+ cur_state = St_set_char( cur_state );
+ for( i = 0; i < num_rep_distances; ++i )
+ cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
}
else
{
- if( cur_trial->dis < num_rep_distances ) St_set_rep( &cur_trial->state );
- else St_set_match( &cur_trial->state );
- LZe_mtf_reps( cur_trial->dis, cur_trial->reps );
+ int dis;
+ if( prev_index2 >= 0 )
+ {
+ dis = cur_trial->dis2;
+ prev_index = prev_index2;
+ cur_state = St_set_rep( cur_state );
+ }
+ else
+ {
+ dis = cur_trial->dis;
+ if( dis < num_rep_distances )
+ cur_state = St_set_rep( cur_state );
+ else
+ cur_state = St_set_match( cur_state );
+ }
+ for( i = 0; i < num_rep_distances; ++i )
+ cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
+ LZe_mtf_reps( dis, cur_trial->reps );
}
+ cur_trial->state = cur_state;
pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
prev_byte = Mf_peek( encoder->matchfinder, -1 );
@@ -1138,81 +579,162 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
match_byte = Mf_peek( encoder->matchfinder, -cur_trial->reps[0]-1 );
next_price = cur_trial->price +
- price0( encoder->bm_match[cur_trial->state][pos_state] );
- if( St_is_char( cur_trial->state ) )
- next_price += Lie_price_symbol( &encoder->literal_encoder,
- prev_byte, cur_byte );
+ price0( encoder->bm_match[cur_state][pos_state] );
+ if( St_is_char( cur_state ) )
+ next_price += LZe_price_literal( encoder, prev_byte, cur_byte );
else
- next_price += Lie_price_matched( &encoder->literal_encoder,
+ next_price += LZe_price_matched( encoder,
prev_byte, cur_byte, match_byte );
if( !Mf_move_pos( encoder->matchfinder ) ) return 0;
+ /* try last updates to next trial */
next_trial = &encoder->trials[cur+1];
- Tr_update( next_trial, -1, cur, next_price );
+ Tr_update( next_trial, next_price, -1, cur );
- match_price = cur_trial->price + price1( encoder->bm_match[cur_trial->state][pos_state] );
- rep_match_price = match_price + price1( encoder->bm_rep[cur_trial->state] );
+ match_price = cur_trial->price + price1( encoder->bm_match[cur_state][pos_state] );
+ rep_match_price = match_price + price1( encoder->bm_rep[cur_state] );
if( match_byte == cur_byte && next_trial->dis != 0 )
- Tr_update( next_trial, 0, cur, rep_match_price +
- LZe_price_rep_len1( encoder, cur_trial->state, pos_state ) );
+ {
+ const int price = rep_match_price +
+ LZe_price_rep_len1( encoder, cur_state, pos_state );
+ if( price <= next_trial->price )
+ {
+ next_trial->price = price;
+ next_trial->dis = 0;
+ next_trial->prev_index = cur;
+ next_trial->prev_index2 = single_step_trial;
+ }
+ }
- len_limit = min( min( max_num_trials - 1 - cur,
- Mf_available_bytes( encoder->matchfinder ) ),
- encoder->matchfinder->match_len_limit );
- if( len_limit < min_match_len ) continue;
+ available_bytes = min( Mf_available_bytes( encoder->matchfinder ) + 1,
+ max_num_trials - 1 - cur );
+ if( available_bytes < min_match_len ) continue;
- for( rep = 0; rep < num_rep_distances; ++rep )
+ len_limit = min( encoder->matchfinder->match_len_limit, available_bytes );
+
+ /* try literal + rep0 */
+ if( match_byte != cur_byte && next_trial->prev_index != cur )
{
- const int dis = cur_trial->reps[rep] + 1;
- int len = 0;
const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
- while( len < len_limit && data[len] == data[len-dis] ) ++len;
- if( len >= min_match_len )
+ const int dis = cur_trial->reps[0] + 1;
+ const int limit = min( encoder->matchfinder->match_len_limit + 1,
+ available_bytes );
+ len = 1;
+ while( len < limit && data[len-dis] == data[len] ) ++len;
+ if( --len >= min_match_len )
{
- const int price = rep_match_price +
- LZe_price_rep( encoder, rep, cur_trial->state, pos_state );
- while( num_trials < cur + len )
+ const int pos_state2 = ( pos_state + 1 ) & pos_state_mask;
+ const State state2 = St_set_char( cur_state );
+ const int price = next_price +
+ price1( encoder->bm_match[state2][pos_state2] ) +
+ price1( encoder->bm_rep[state2] ) +
+ LZe_price_rep0_len( encoder, len, state2, pos_state2 );
+ while( num_trials < cur + 1 + len )
encoder->trials[++num_trials].price = infinite_price;
- for( ; len >= min_match_len; --len )
- Tr_update( &encoder->trials[cur+len], rep, cur, price +
- Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) );
+ Tr_update2( &encoder->trials[cur+1+len], price, 0, cur + 1 );
}
}
- if( newlen <= len_limit &&
- ( newlen > min_match_len ||
- ( newlen == min_match_len &&
- encoder->match_distances[min_match_len] < modeled_distances ) ) )
+ /* try rep distances */
+ for( rep = 0; rep < num_rep_distances; ++rep )
{
+ const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+ int price;
+ const int dis = cur_trial->reps[rep] + 1;
+
+ if( data[-dis] != data[0] || data[1-dis] != data[1] ) continue;
+ for( len = min_match_len; len < len_limit; ++len )
+ if( data[len-dis] != data[len] ) break;
+ while( num_trials < cur + len )
+ encoder->trials[++num_trials].price = infinite_price;
+ price = rep_match_price +
+ LZe_price_rep( encoder, rep, cur_state, pos_state );
+ for( i = min_match_len; i <= len; ++i )
+ Tr_update( &encoder->trials[cur+i], price +
+ Lee_price( &encoder->rep_match_len_encoder, i, pos_state ),
+ rep, cur );
+
+ if( rep == 0 ) start_len = len + 1; /* discard shorter matches */
+
+ /* try rep + literal + rep0 */
+ {
+ int len2 = len + 1, pos_state2;
+ const int limit = min( encoder->matchfinder->match_len_limit + len2,
+ available_bytes );
+ State state2;
+ while( len2 < limit && data[len2-dis] == data[len2] ) ++len2;
+ len2 -= len + 1;
+ if( len2 < min_match_len ) continue;
+
+ pos_state2 = ( pos_state + len ) & pos_state_mask;
+ state2 = St_set_rep( cur_state );
+ price += Lee_price( &encoder->rep_match_len_encoder, len, pos_state ) +
+ price0( encoder->bm_match[state2][pos_state2] ) +
+ LZe_price_matched( encoder, data[len-1], data[len], data[len-dis] );
+ pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
+ state2 = St_set_char( state2 );
+ price += price1( encoder->bm_match[state2][pos_state2] ) +
+ price1( encoder->bm_rep[state2] ) +
+ LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+ while( num_trials < cur + len + 1 + len2 )
+ encoder->trials[++num_trials].price = infinite_price;
+ Tr_update3( &encoder->trials[cur+len+1+len2], price, 0, cur + len + 1,
+ rep, cur );
+ }
+ }
+
+ /* try matches */
+ if( newlen >= start_len && newlen <= len_limit )
+ {
+ int dis;
const int normal_match_price = match_price +
- price0( encoder->bm_rep[cur_trial->state] );
- int len;
- int dis = encoder->match_distances[min_match_len];
- int dis_state = get_dis_state( min_match_len );
- int dis_price = infinite_price;
+ price0( encoder->bm_rep[cur_state] );
while( num_trials < cur + newlen )
encoder->trials[++num_trials].price = infinite_price;
- if( dis < modeled_distances )
- Tr_update( &encoder->trials[cur+min_match_len], dis + num_rep_distances,
- cur, normal_match_price + encoder->dis_prices[dis_state][dis] +
- Lee_price( &encoder->len_encoder, min_match_len, pos_state ) );
-
- for( len = min_match_len + 1; len <= newlen; ++len )
+ i = 0;
+ while( start_len > encoder->pairs[i].len ) ++i;
+ dis = encoder->pairs[i].dis;
+ for( len = start_len; ; ++len )
{
- if( dis != encoder->match_distances[len] ||
- dis_state < max_dis_states - 1 )
+ int price = normal_match_price +
+ LZe_price_pair( encoder, dis, len, pos_state );
+
+ Tr_update( &encoder->trials[cur+len], price, dis + num_rep_distances, cur );
+
+ /* try match + literal + rep0 */
+ if( len == encoder->pairs[i].len )
{
- dis = encoder->match_distances[len];
- dis_state = get_dis_state( len );
- dis_price = LZe_price_dis( encoder, dis, dis_state );
+ const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+ const int dis2 = dis + 1;
+ int len2 = len + 1;
+ const int limit = min( encoder->matchfinder->match_len_limit + len2,
+ available_bytes );
+ while( len2 < limit && data[len2-dis2] == data[len2] ) ++len2;
+ len2 -= len + 1;
+ if( len2 >= min_match_len )
+ {
+ int pos_state2 = ( pos_state + len ) & pos_state_mask;
+ State state2 = St_set_match( cur_state );
+ price += price0( encoder->bm_match[state2][pos_state2] ) +
+ LZe_price_matched( encoder, data[len-1], data[len], data[len-dis2] );
+ pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
+ state2 = St_set_char( state2 );
+ price += price1( encoder->bm_match[state2][pos_state2] ) +
+ price1( encoder->bm_rep[state2] ) +
+ LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+
+ while( num_trials < cur + len + 1 + len2 )
+ encoder->trials[++num_trials].price = infinite_price;
+ Tr_update3( &encoder->trials[cur+len+1+len2], price, 0,
+ cur + len + 1, dis + num_rep_distances, cur );
+ }
+ if( ++i >= num_pairs ) break;
+ dis = encoder->pairs[i].dis;
}
- Tr_update( &encoder->trials[cur+len], dis + num_rep_distances, cur,
- normal_match_price + dis_price +
- Lee_price( &encoder->len_encoder, len, pos_state ) );
}
}
}
@@ -1223,7 +745,7 @@ static bool LZe_encode_member( struct LZ_encoder * const encoder,
const bool finish )
{
const int fill_count =
- ( encoder->matchfinder->match_len_limit > 12 ) ? 512 : 2048;
+ ( encoder->matchfinder->match_len_limit > 12 ) ? 128 : 512;
int ahead, i;
State * const state = &encoder->state;
if( encoder->member_finished ) return true;
@@ -1233,19 +755,19 @@ static bool LZe_encode_member( struct LZ_encoder * const encoder,
return true;
}
- /* encode first byte */
if( Mf_data_position( encoder->matchfinder ) == 0 &&
- !Mf_finished( encoder->matchfinder ) )
+ !Mf_finished( encoder->matchfinder ) ) /* encode first byte */
{
+ const uint8_t prev_byte = 0;
+ uint8_t cur_byte;
if( Mf_available_bytes( encoder->matchfinder ) < max_match_len &&
!encoder->matchfinder->at_stream_end )
return true;
- const uint8_t prev_byte = 0;
- const uint8_t cur_byte = Mf_peek( encoder->matchfinder, 0 );
+ cur_byte = Mf_peek( encoder->matchfinder, 0 );
Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[*state][0], 0 );
- Lie_encode( &encoder->literal_encoder, &encoder->range_encoder, prev_byte, cur_byte );
+ LZe_encode_literal( encoder, prev_byte, cur_byte );
CRC32_update_byte( &encoder->crc, cur_byte );
- Mf_longest_match_len( encoder->matchfinder, 0 );
+ Mf_get_match_pairs( encoder->matchfinder, 0 );
if( !Mf_move_pos( encoder->matchfinder ) ) return false;
}
@@ -1253,12 +775,16 @@ static bool LZe_encode_member( struct LZ_encoder * const encoder,
{
if( !Mf_enough_available_bytes( encoder->matchfinder ) ||
!Re_enough_free_bytes( &encoder->range_encoder ) ) return true;
- if( encoder->fill_counter <= 0 )
- { LZe_fill_distance_prices( encoder ); encoder->fill_counter = fill_count; }
+ if( encoder->pending_num_pairs == 0 )
+ {
+ if( encoder->fill_counter <= 0 )
+ { LZe_fill_distance_prices( encoder ); encoder->fill_counter = fill_count; }
+ if( encoder->align_price_count <= 0 )
+ LZe_fill_align_prices( encoder );
+ }
ahead = LZe_sequence_optimizer( encoder, encoder->rep_distances, *state );
if( ahead <= 0 ) return false; /* can't happen */
- encoder->fill_counter -= ahead;
for( i = 0; ; )
{
@@ -1276,16 +802,14 @@ static bool LZe_encode_member( struct LZ_encoder * const encoder,
const uint8_t cur_byte = Mf_peek( encoder->matchfinder, -ahead );
CRC32_update_byte( &encoder->crc, cur_byte );
if( St_is_char( *state ) )
- Lie_encode( &encoder->literal_encoder, &encoder->range_encoder,
- prev_byte, cur_byte );
+ LZe_encode_literal( encoder, prev_byte, cur_byte );
else
{
const uint8_t match_byte =
Mf_peek( encoder->matchfinder, -ahead-encoder->rep_distances[0]-1 );
- Lie_encode_matched( &encoder->literal_encoder, &encoder->range_encoder,
- prev_byte, cur_byte, match_byte );
+ LZe_encode_matched( encoder, prev_byte, cur_byte, match_byte );
}
- St_set_char( state );
+ *state = St_set_char( *state );
}
else /* match or repeated match */
{
@@ -1305,17 +829,18 @@ static bool LZe_encode_member( struct LZ_encoder * const encoder,
if( dis > 1 )
Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep2[*state], dis > 2 );
}
- if( len == 1 ) St_set_short_rep( state );
+ if( len == 1 ) *state = St_set_short_rep( *state );
else
{
Lee_encode( &encoder->rep_match_len_encoder, &encoder->range_encoder, len, pos_state );
- St_set_rep( state );
+ *state = St_set_rep( *state );
}
}
else
{
LZe_encode_pair( encoder, dis - num_rep_distances, len, pos_state );
- St_set_match( state );
+ --encoder->fill_counter;
+ *state = St_set_match( *state );
}
}
ahead -= len; i += len;