summaryrefslogtreecommitdiffstats
path: root/encoder.h
diff options
context:
space:
mode:
authorDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 10:03:36 +0000
committerDaniel Baumann <mail@daniel-baumann.ch>2015-11-07 10:03:36 +0000
commite43c45c952bb5d273724bfc6dd69e4c2de1aa190 (patch)
treebca9bb3d2f16f3edb5ab0d6f6b209be3f4fabb92 /encoder.h
parentAdding upstream version 1.16~pre1. (diff)
downloadlzip-e43c45c952bb5d273724bfc6dd69e4c2de1aa190.tar.xz
lzip-e43c45c952bb5d273724bfc6dd69e4c2de1aa190.zip
Adding upstream version 1.16~pre2.upstream/1.16_pre2
Signed-off-by: Daniel Baumann <mail@daniel-baumann.ch>
Diffstat (limited to 'encoder.h')
-rw-r--r--encoder.h123
1 files changed, 79 insertions, 44 deletions
diff --git a/encoder.h b/encoder.h
index 4139484..5df34c6 100644
--- a/encoder.h
+++ b/encoder.h
@@ -16,7 +16,7 @@
along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
-enum { max_num_trials = 1 << 12,
+enum { max_num_trials = 1 << 13,
price_shift_bits = 6,
price_step_bits = 2,
price_step = 1 << price_step_bits };
@@ -59,19 +59,18 @@ class Prob_prices
public:
void init()
{
- for( int i = price_step / 2; i < bit_model_total; i += price_step )
+ for( int i = 0; i < bit_model_total >> price_step_bits; ++i )
{
- unsigned val = i;
- int bits = 0; // base 2 logarithm of val
+ unsigned val = ( i * price_step ) + ( price_step / 2 );
+ int bits = 0; // base 2 logarithm of val
for( int j = 0; j < price_shift_bits; ++j )
{
val = val * val;
bits <<= 1;
while( val >= 1 << 16 ) { val >>= 1; ++bits; }
}
- bits += 15; // remaining bits in val
- data[i >> price_step_bits] =
- ( bit_model_total_bits << price_shift_bits ) - bits;
+ bits += 15; // remaining bits in val
+ data[i] = ( bit_model_total_bits << price_shift_bits ) - bits;
}
}
@@ -268,7 +267,7 @@ public:
}
int match_len_limit() const { return match_len_limit_; }
- int get_match_pairs( struct Pair * pairs = 0 );
+ int get_match_pairs( Pair * pairs = 0 );
};
@@ -419,42 +418,80 @@ public:
}
while( symbol < 0x10000 );
}
+
+ void encode_len( Len_model & lm, int symbol, const int pos_state )
+ {
+ symbol -= min_match_len;
+ bool bit = ( symbol >= len_low_symbols );
+ encode_bit( lm.choice1, bit );
+ if( !bit )
+ encode_tree3( lm.bm_low[pos_state], symbol );
+ else
+ {
+ bit = ( symbol >= len_low_symbols + len_mid_symbols );
+ encode_bit( lm.choice2, bit );
+ if( !bit )
+ encode_tree3( lm.bm_mid[pos_state], symbol - len_low_symbols );
+ else
+ encode_tree8( lm.bm_high, symbol - len_low_symbols - len_mid_symbols );
+ }
+ }
};
-class Len_encoder : public Len_model
+class Len_prices
{
- int prices[pos_states][max_len_symbols];
+ const Len_model & lm;
const int len_symbols;
+ const int count;
+ int prices[pos_states][max_len_symbols];
int counters[pos_states];
- void update_prices( const int pos_state )
+ void update_low_mid_prices( const int pos_state )
{
+ counters[pos_state] = count;
int * const pps = prices[pos_state];
- int tmp = price0( choice1 );
+ int tmp = price0( lm.choice1 );
int len = 0;
for( ; len < len_low_symbols && len < len_symbols; ++len )
- pps[len] = tmp + price_symbol3( bm_low[pos_state], len );
- tmp = price1( choice1 );
+ pps[len] = tmp + price_symbol3( lm.bm_low[pos_state], len );
+ if( len >= len_symbols ) return;
+ tmp = price1( lm.choice1 ) + price0( lm.choice2 );
for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len )
- pps[len] = tmp + price0( choice2 ) +
- price_symbol3( bm_mid[pos_state], len - len_low_symbols );
- for( ; len < len_symbols; ++len )
+ pps[len] = tmp +
+ price_symbol3( lm.bm_mid[pos_state], len - len_low_symbols );
+ }
+
+ void update_high_prices()
+ {
+ const int tmp = price1( lm.choice1 ) + price1( lm.choice2 );
+ for( int len = len_low_symbols + len_mid_symbols; len < len_symbols; ++len )
// using 4 slots per value makes "price" faster
- prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] =
- tmp + price1( choice2 ) +
- price_symbol8( bm_high, len - len_low_symbols - len_mid_symbols );
- counters[pos_state] = len_symbols;
+ prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] = tmp +
+ price_symbol8( lm.bm_high, len - len_low_symbols - len_mid_symbols );
}
public:
- explicit Len_encoder( const int match_len_limit )
- : len_symbols( match_len_limit + 1 - min_match_len )
+ Len_prices( const Len_model & m, const int match_len_limit )
+ :
+ lm( m ),
+ len_symbols( match_len_limit + 1 - min_match_len ),
+ count( ( match_len_limit > 12 ) ? 1 : len_symbols )
{
- for( int i = 0; i < pos_states; ++i ) update_prices( i );
+ for( int i = 0; i < pos_states; ++i ) counters[i] = 0;
}
- void encode( Range_encoder & renc, int symbol, const int pos_state );
+ void decrement_counter( const int pos_state ) { --counters[pos_state]; }
+
+ void update_prices()
+ {
+ bool high_pending = false;
+ for( int pos_state = 0; pos_state < pos_states; ++pos_state )
+ if( counters[pos_state] <= 0 )
+ { update_low_mid_prices( pos_state ); high_pending = true; }
+ if( high_pending && len_symbols > len_low_symbols + len_mid_symbols )
+ update_high_prices();
+ }
int price( const int symbol, const int pos_state ) const
{ return prices[pos_state][symbol - min_match_len]; }
@@ -481,18 +518,15 @@ protected:
Bit_model bm_align[dis_align_size];
Range_encoder renc;
- Len_encoder match_len_encoder;
- Len_encoder rep_len_encoder;
+ Len_model match_len_model;
+ Len_model rep_len_model;
unsigned crc() const { return crc_ ^ 0xFFFFFFFFU; }
- LZ_encoder_base( const File_header & header, const int match_len_limit,
- const int outfd )
+ LZ_encoder_base( const File_header & header, const int outfd )
:
crc_( 0xFFFFFFFFU ),
- renc( outfd ),
- match_len_encoder( match_len_limit ),
- rep_len_encoder( match_len_limit )
+ renc( outfd )
{
for( int i = 0; i < File_header::size; ++i )
renc.put_byte( header.data[i] );
@@ -503,8 +537,8 @@ protected:
int price_matched( const uint8_t prev_byte, const uint8_t symbol,
const uint8_t match_byte ) const
- { return ::price_matched( bm_literal[get_lit_state(prev_byte)],
- symbol, match_byte ); }
+ { return ::price_matched( bm_literal[get_lit_state(prev_byte)], symbol,
+ match_byte ); }
void encode_literal( const uint8_t prev_byte, const uint8_t symbol )
{ renc.encode_tree8( bm_literal[get_lit_state(prev_byte)], symbol ); }
@@ -516,7 +550,7 @@ protected:
void encode_pair( const unsigned dis, const int len, const int pos_state )
{
- match_len_encoder.encode( renc, len, pos_state );
+ renc.encode_len( match_len_model, len, pos_state );
const int dis_slot = get_slot( dis );
renc.encode_tree6( bm_dis_slot[get_len_state(len)], dis_slot );
@@ -584,18 +618,18 @@ class LZ_encoder : public LZ_encoder_base
};
Matchfinder & matchfinder;
+ Len_prices match_len_prices;
+ Len_prices rep_len_prices;
int pending_num_pairs;
- struct Pair pairs[max_match_len+1];
+ Pair pairs[max_match_len+1];
Trial trials[max_num_trials];
- int dis_prices[len_states][modeled_distances];
int dis_slot_prices[len_states][2*max_dictionary_bits];
+ int dis_prices[len_states][modeled_distances];
int align_prices[dis_align_size];
- int align_price_count;
const int num_dis_slots;
- void fill_align_prices();
- void fill_distance_prices();
+ void update_distance_prices();
// move-to-front dis in/into reps if( dis > 0 )
static void mtf_reps( const int dis, int reps[num_rep_distances] )
@@ -636,12 +670,12 @@ class LZ_encoder : public LZ_encoder_base
int price_rep0_len( const int len, const State state, const int pos_state ) const
{
return price_rep( 0, state, pos_state ) +
- rep_len_encoder.price( len, pos_state );
+ rep_len_prices.price( len, pos_state );
}
int price_pair( const int dis, const int len, const int pos_state ) const
{
- const int price = match_len_encoder.price( len, pos_state );
+ const int price = match_len_prices.price( len, pos_state );
const int len_state = get_len_state( len );
if( dis < modeled_distances )
return price + dis_prices[len_state][dis];
@@ -709,10 +743,11 @@ class LZ_encoder : public LZ_encoder_base
public:
LZ_encoder( Matchfinder & mf, const File_header & header, const int outfd )
:
- LZ_encoder_base( header, mf.match_len_limit(), outfd ),
+ LZ_encoder_base( header, outfd ),
matchfinder( mf ),
+ match_len_prices( match_len_model, mf.match_len_limit() ),
+ rep_len_prices( rep_len_model, mf.match_len_limit() ),
pending_num_pairs( 0 ),
- align_price_count( 0 ),
num_dis_slots( 2 * real_bits( mf.dictionary_size() - 1 ) )
{}