From efe11df4b26426c3db4f96592e899b1f005a878e Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 May 2017 17:50:01 +0200 Subject: Merging upstream version 1.9. Signed-off-by: Daniel Baumann --- encoder_base.h | 217 +++++++++++++++++++++++++++++++++------------------------ 1 file changed, 127 insertions(+), 90 deletions(-) (limited to 'encoder_base.h') diff --git a/encoder_base.h b/encoder_base.h index 54fecd1..b2985f1 100644 --- a/encoder_base.h +++ b/encoder_base.h @@ -1,5 +1,5 @@ /* Clzip - LZMA lossless data compressor - Copyright (C) 2010-2016 Antonio Diaz Diaz. + Copyright (C) 2010-2017 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 @@ -77,22 +77,48 @@ static inline int price0( const Bit_model 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_bit( const Bit_model bm, const bool bit ) + { return ( bit ? price1( bm ) : price0( bm ) ); } -static inline int price_symbol( const Bit_model bm[], int symbol, - const int num_bits ) +static inline int price_symbol3( const Bit_model bm[], int symbol ) { - 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; + int price; + bool bit = symbol & 1; + symbol |= 8; symbol >>= 1; + price = price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + return price + price_bit( bm[1], symbol & 1 ); + } + + +static inline int price_symbol6( const Bit_model bm[], unsigned symbol ) + { + int price; + bool bit = symbol & 1; + symbol |= 64; symbol >>= 1; + price = price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + return price + price_bit( bm[1], symbol & 1 ); + } + + +static inline int price_symbol8( const Bit_model bm[], int symbol ) + { + int price; + bool bit = symbol & 1; + symbol |= 0x100; symbol >>= 1; + price = price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + bit = symbol & 1; symbol >>= 1; price += price_bit( bm[symbol], bit ); + return price + price_bit( bm[1], symbol & 1 ); } @@ -104,32 +130,29 @@ static inline int price_symbol_reversed( const Bit_model bm[], int symbol, int i; for( i = num_bits; i > 0; --i ) { - const int bit = symbol & 1; + const bool bit = symbol & 1; + symbol >>= 1; price += price_bit( bm[model], bit ); model = ( model << 1 ) | bit; - symbol >>= 1; } return price; } -static inline int price_matched( const Bit_model bm[], int symbol, int match_byte ) +static inline int price_matched( const Bit_model bm[], unsigned symbol, + unsigned match_byte ) { int price = 0; - int mask = 0x100; + unsigned mask = 0x100; symbol |= mask; - - do { - int match_bit, bit; - match_byte <<= 1; - match_bit = match_byte & mask; - symbol <<= 1; - bit = symbol & 0x100; - price += price_bit( bm[match_bit+(symbol>>9)+mask], bit ); - mask &= ~(match_byte ^ symbol); /* if( match_bit != bit ) mask = 0; */ + while( true ) + { + const unsigned match_bit = ( match_byte <<= 1 ) & mask; + const bool bit = ( symbol <<= 1 ) & 0x100; + price += price_bit( bm[(symbol>>9)+match_bit+mask], bit ); + if( symbol >= 0x10000 ) return price; + mask &= ~(match_bit ^ symbol); /* if( match_bit != bit ) mask = 0; */ } - while( symbol < 0x10000 ); - return price; } @@ -156,10 +179,9 @@ struct Matchfinder_base bool Mb_read_block( struct Matchfinder_base * const mb ); void Mb_normalize_pos( struct Matchfinder_base * const mb ); -bool Mb_init( struct Matchfinder_base * const mb, - const int before, const int dict_size, - const int after_size, const int dict_factor, - const int num_prev_positions23, +bool Mb_init( struct Matchfinder_base * const mb, const int before, + const int dict_size, const int after_size, + const int dict_factor, const int num_prev_positions23, const int pos_array_factor, const int ifd ); static inline void Mb_free( struct Matchfinder_base * const mb ) @@ -184,13 +206,11 @@ Mb_ptr_to_current_pos( const struct Matchfinder_base * const mb ) { return mb->buffer + mb->pos; } static inline int Mb_true_match_len( const struct Matchfinder_base * const mb, - const int index, const int distance, - int len_limit ) + const int index, const int distance ) { - const uint8_t * const data = mb->buffer + mb->pos + index; - int i = 0; - if( index + len_limit > Mb_available_bytes( mb ) ) - len_limit = Mb_available_bytes( mb ) - index; + const uint8_t * const data = mb->buffer + mb->pos; + int i = index; + const int len_limit = min( Mb_available_bytes( mb ), max_match_len ); while( i < len_limit && data[i-distance] == data[i] ) ++i; return i; } @@ -230,9 +250,9 @@ static inline void Re_put_byte( struct Range_encoder * const renc, static inline void Re_shift_low( struct Range_encoder * const renc ) { - const bool carry = ( renc->low > 0xFFFFFFFFU ); - if( carry || renc->low < 0xFF000000U ) + if( renc->low >> 24 != 0xFF ) { + const bool carry = ( renc->low > 0xFFFFFFFFU ); Re_put_byte( renc, renc->cache + carry ); for( ; renc->ff_count > 0; --renc->ff_count ) Re_put_byte( renc, 0xFF + carry ); @@ -280,18 +300,18 @@ static inline void Re_flush( struct Range_encoder * const renc ) 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 ) + unsigned mask; + for( mask = 1 << ( num_bits - 1 ); mask > 0; mask >>= 1 ) { renc->range >>= 1; - if( (symbol >> i) & 1 ) renc->low += renc->range; + if( symbol & mask ) 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 ) + Bit_model * const probability, const bool bit ) { const uint32_t bound = ( renc->range >> bit_model_total_bits ) * *probability; if( !bit ) @@ -305,56 +325,78 @@ static inline void Re_encode_bit( struct Range_encoder * const renc, renc->range -= bound; *probability -= *probability >> bit_model_move_bits; } - if( renc->range <= 0x00FFFFFFU ) - { renc->range <<= 8; Re_shift_low( renc ); } + if( renc->range <= 0x00FFFFFFU ) { renc->range <<= 8; Re_shift_low( renc ); } + } + +static inline void Re_encode_tree3( struct Range_encoder * const renc, + Bit_model bm[], const int symbol ) + { + int model = 1; + bool bit = ( symbol >> 2 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + bit = ( symbol >> 1 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + Re_encode_bit( renc, &bm[model], symbol & 1 ); + } + +static inline void Re_encode_tree6( struct Range_encoder * const renc, + Bit_model bm[], const unsigned symbol ) + { + int model = 1; + bool bit = ( symbol >> 5 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + bit = ( symbol >> 4 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + bit = ( symbol >> 3 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + bit = ( symbol >> 2 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + bit = ( symbol >> 1 ) & 1; + Re_encode_bit( renc, &bm[model], bit ); model = ( model << 1 ) | bit; + Re_encode_bit( renc, &bm[model], symbol & 1 ); } -static inline void Re_encode_tree( struct Range_encoder * const renc, - Bit_model bm[], const int symbol, const int num_bits ) +static inline void Re_encode_tree8( struct Range_encoder * const renc, + Bit_model bm[], const int symbol ) { - int mask = ( 1 << ( num_bits - 1 ) ); int model = 1; int i; - for( i = num_bits; i > 0; --i, mask >>= 1 ) + for( i = 7; i >= 0; --i ) { - const int bit = ( symbol & mask ); + const bool bit = ( symbol >> i ) & 1; Re_encode_bit( renc, &bm[model], bit ); - model <<= 1; - if( bit ) model |= 1; + model = ( model << 1 ) | bit; } } static inline void Re_encode_tree_reversed( struct Range_encoder * const renc, - Bit_model bm[], int symbol, const int num_bits ) + 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; + const bool bit = symbol & 1; + 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 ) + Bit_model bm[], unsigned symbol, + unsigned match_byte ) { - int mask = 0x100; + unsigned mask = 0x100; symbol |= mask; - - do { - int match_bit, bit; - match_byte <<= 1; - match_bit = match_byte & mask; - symbol <<= 1; - bit = symbol & 0x100; - Re_encode_bit( renc, &bm[match_bit+(symbol>>9)+mask], bit ); - mask &= ~(match_byte ^ symbol); /* if( match_bit != bit ) mask = 0; */ + while( true ) + { + const unsigned match_bit = ( match_byte <<= 1 ) & mask; + const bool bit = ( symbol <<= 1 ) & 0x100; + Re_encode_bit( renc, &bm[(symbol>>9)+match_bit+mask], bit ); + if( symbol >= 0x10000 ) break; + mask &= ~(match_bit ^ symbol); /* if( match_bit != bit ) mask = 0; */ } - while( symbol < 0x10000 ); } static inline void Re_encode_len( struct Range_encoder * const renc, @@ -364,17 +406,15 @@ static inline void Re_encode_len( struct Range_encoder * const renc, bool bit = ( ( symbol -= min_match_len ) >= len_low_symbols ); Re_encode_bit( renc, &lm->choice1, bit ); if( !bit ) - Re_encode_tree( renc, lm->bm_low[pos_state], symbol, len_low_bits ); + Re_encode_tree3( renc, lm->bm_low[pos_state], symbol ); else { - bit = ( symbol >= len_low_symbols + len_mid_symbols ); + bit = ( ( symbol -= len_low_symbols ) >= len_mid_symbols ); Re_encode_bit( renc, &lm->choice2, bit ); if( !bit ) - Re_encode_tree( renc, lm->bm_mid[pos_state], - symbol - len_low_symbols, len_mid_bits ); + Re_encode_tree3( renc, lm->bm_mid[pos_state], symbol ); else - Re_encode_tree( renc, lm->bm_high, - symbol - len_low_symbols - len_mid_symbols, len_high_bits ); + Re_encode_tree8( renc, lm->bm_high, symbol - len_mid_symbols ); } } @@ -395,7 +435,7 @@ struct LZ_encoder_base Bit_model bm_rep2[states]; Bit_model bm_len[states][pos_states]; Bit_model bm_dis_slot[len_states][1<crc ^ 0xFFFFFFFFU; } static inline int LZeb_price_literal( const struct LZ_encoder_base * const eb, - uint8_t prev_byte, uint8_t symbol ) - { return price_symbol( eb->bm_literal[get_lit_state(prev_byte)], symbol, 8 ); } + const uint8_t prev_byte, const uint8_t symbol ) + { return price_symbol8( eb->bm_literal[get_lit_state(prev_byte)], symbol ); } static inline int LZeb_price_matched( const struct LZ_encoder_base * const eb, - uint8_t prev_byte, uint8_t symbol, - uint8_t match_byte ) + const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte ) { return price_matched( eb->bm_literal[get_lit_state(prev_byte)], symbol, match_byte ); } static inline void LZeb_encode_literal( struct LZ_encoder_base * const eb, - uint8_t prev_byte, uint8_t symbol ) - { Re_encode_tree( &eb->renc, - eb->bm_literal[get_lit_state(prev_byte)], symbol, 8 ); } + const uint8_t prev_byte, const uint8_t symbol ) + { Re_encode_tree8( &eb->renc, eb->bm_literal[get_lit_state(prev_byte)], + symbol ); } static inline void LZeb_encode_matched( struct LZ_encoder_base * const eb, - uint8_t prev_byte, uint8_t symbol, - uint8_t match_byte ) + const uint8_t prev_byte, const uint8_t symbol, const uint8_t match_byte ) { Re_encode_matched( &eb->renc, eb->bm_literal[get_lit_state(prev_byte)], symbol, match_byte ); } @@ -449,10 +487,9 @@ static inline void LZeb_encode_pair( struct LZ_encoder_base * const eb, const unsigned dis, const int len, const int pos_state ) { - const int dis_slot = get_slot( dis ); + const unsigned dis_slot = get_slot( dis ); Re_encode_len( &eb->renc, &eb->match_len_model, len, pos_state ); - Re_encode_tree( &eb->renc, eb->bm_dis_slot[get_len_state(len)], dis_slot, - dis_slot_bits ); + Re_encode_tree6( &eb->renc, eb->bm_dis_slot[get_len_state(len)], dis_slot ); if( dis_slot >= start_dis_model ) { @@ -461,7 +498,7 @@ static inline void LZeb_encode_pair( struct LZ_encoder_base * const eb, const unsigned direct_dis = dis - base; if( dis_slot < end_dis_model ) - Re_encode_tree_reversed( &eb->renc, eb->bm_dis + base - dis_slot - 1, + Re_encode_tree_reversed( &eb->renc, eb->bm_dis + ( base - dis_slot ), direct_dis, direct_bits ); else { -- cgit v1.2.3