diff options
Diffstat (limited to '')
| -rw-r--r-- | encoder.c | 1334 | ||||
| -rw-r--r-- | encoder.cc | 663 |
2 files changed, 1334 insertions, 663 deletions
diff --git a/encoder.c b/encoder.c new file mode 100644 index 0000000..bf0dafa --- /dev/null +++ b/encoder.c @@ -0,0 +1,1334 @@ +/* Lzlib - A compression library for lzip files + Copyright (C) 2009, 2010, 2011, 2012 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 + the Free Software Foundation, either version 3 of the License, or + (at your option) any later version. + + This library is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this library. If not, see <http://www.gnu.org/licenses/>. + + As a special exception, you may use this file as part of a free + software library without restriction. Specifically, if other files + instantiate templates or use macros or inline functions from this + file, or you compile this file and link it with other files to + produce an executable, this file does not by itself cause the + resulting executable to be covered by the GNU General Public + License. This exception does not however invalidate any other + reasons why the executable file might be covered by the GNU General + 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 ) + { mf->pos = mf->stream_pos; return false; } + if( !mf->at_stream_end ) + { + int i; + const int offset = mf->pos - mf->dictionary_size - before_size; + const int size = mf->stream_pos - offset; + memmove( mf->buffer, mf->buffer + offset, size ); + mf->partial_data_pos += offset; + mf->pos -= offset; + mf->stream_pos -= offset; + for( i = 0; i < num_prev_positions; ++i ) + if( mf->prev_positions[i] >= 0 ) mf->prev_positions[i] -= offset; + for( i = 0; i < 2 * mf->dictionary_size; ++i ) + if( mf->prev_pos_tree[i] >= 0 ) mf->prev_pos_tree[i] -= offset; + } + return true; + } + + +static bool Mf_init( struct Matchfinder * const mf, + const int dict_size, const int len_limit ) + { + int i; + 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->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->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; + return true; + } + + +static inline void Mf_free( 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; + } + + +static void Mf_reset( struct Matchfinder * const mf ) + { + int i; + const int size = mf->stream_pos - mf->pos; + if( size > 0 ) memmove( mf->buffer, mf->buffer + mf->pos, size ); + mf->partial_data_pos = 0; + mf->stream_pos -= mf->pos; + mf->pos = 0; + 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; + } + + +static int Mf_longest_match_len( struct Matchfinder * const mf, + int * const distances ) + { + 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; + const uint8_t * const data = mf->buffer + mf->pos; + int count, delta, key2, key3, key4, newpos, tmp; + int len_limit = mf->match_len_limit; + + if( len_limit > Mf_available_bytes( mf ) ) + { + mf->been_flushed = true; + len_limit = Mf_available_bytes( 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 ) ); + + if( distances ) + { + 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; + } + + mf->prev_positions[key2] = mf->pos; + mf->prev_positions[key3] = mf->pos; + newpos = mf->prev_positions[key4]; + mf->prev_positions[key4] = mf->pos; + + 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; + + 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 ) + { + if( newdata[len] < data[len] ) + { + *ptr0 = newpos; + ptr0 = newptr + 1; + newpos = *ptr0; + len0 = len; if( len1 < len ) len = len1; + } + else + { + *ptr1 = newpos; + ptr1 = newptr; + newpos = *ptr1; + len1 = len; if( len0 < len ) len = len0; + } + } + else + { + *ptr0 = newptr[0]; + *ptr1 = newptr[1]; + break; + } + } + 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 ) + { + while( --i >= 0 ) + { + bit = ( symbol >> i ) & 1; + Re_encode_bit( renc, &bm[model], bit ); + model = ( model << 1 ) | bit; + } + break; + } + } + } + + +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 ); + } + + +static void Lee_encode( struct Len_encoder * const len_encoder, + struct Range_encoder * const renc, + int symbol, const int pos_state ) + { + symbol -= min_match_len; + if( symbol < len_low_symbols ) + { + Re_encode_bit( renc, &len_encoder->choice1, 0 ); + Re_encode_tree( renc, len_encoder->bm_low[pos_state], symbol, len_low_bits ); + } + else + { + Re_encode_bit( renc, &len_encoder->choice1, 1 ); + if( symbol < len_low_symbols + len_mid_symbols ) + { + Re_encode_bit( renc, &len_encoder->choice2, 0 ); + Re_encode_tree( renc, len_encoder->bm_mid[pos_state], + symbol - len_low_symbols, len_mid_bits ); + } + else + { + Re_encode_bit( renc, &len_encoder->choice2, 1 ); + Re_encode_tree( renc, len_encoder->bm_high, + symbol - len_low_symbols - len_mid_symbols, len_high_bits ); + } + } + if( --len_encoder->counters[pos_state] <= 0 ) + Lee_update_prices( len_encoder, pos_state ); + } + + +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 ) + { + if( pr < trial->price ) + { trial->dis = d; trial->prev_index = p_i; trial->price = pr; } + } + + +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 ) + { + return ( encoder->member_finished && + !Cb_used_bytes( &encoder->range_encoder.cb ) ); + } + + +static void LZe_fill_align_prices( struct LZ_encoder * const encoder ) + { + int i; + for( i = 0; i < dis_align_size; ++i ) + encoder->align_prices[i] = + price_symbol_reversed( encoder->bm_align, i, dis_align_bits ); + encoder->align_price_count = dis_align_size; + } + + +static void LZe_fill_distance_prices( struct LZ_encoder * const encoder ) + { + int dis, dis_state; + for( dis = start_dis_model; dis < modeled_distances; ++dis ) + { + const int dis_slot = dis_slots[dis]; + 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, + dis - base, direct_bits ); + for( dis_state = 0; dis_state < max_dis_states; ++dis_state ) + encoder->dis_prices[dis_state][dis] = price; + } + + for( dis_state = 0; dis_state < max_dis_states; ++dis_state ) + { + int * const dsp = encoder->dis_slot_prices[dis_state]; + int * const dp = encoder->dis_prices[dis_state]; + const Bit_model * const bmds = encoder->bm_dis_slot[dis_state]; + int slot = 0; + for( ; slot < end_dis_model && slot < encoder->num_dis_slots; ++slot ) + 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 ); + + for( dis = 0; dis < start_dis_model; ++dis ) + dp[dis] = dsp[dis]; + for( ; dis < modeled_distances; ++dis ) + dp[dis] += dsp[dis_slots[dis]]; + } + } + + +static bool LZe_init( struct LZ_encoder * const encoder, + struct Matchfinder * const mf, + const File_header header, const long long member_size ) + { + int i, j; + encoder->member_size_limit = member_size - Ft_size - max_marker_size; + encoder->longest_match_found = 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] ); + + 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->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. +*/ +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 replens[num_rep_distances]; + int rep_index = 0; + + if( encoder->longest_match_found > 0 ) /* from previous call */ + { + main_len = encoder->longest_match_found; + encoder->longest_match_found = 0; + } + else main_len = LZe_read_match_distances( encoder ); + + for( i = 0; i < num_rep_distances; ++i ) + { + replens[i] = + Mf_true_match_len( encoder->matchfinder, 0, reps[i] + 1, max_match_len ); + if( replens[i] > replens[rep_index] ) rep_index = i; + } + if( replens[rep_index] >= encoder->matchfinder->match_len_limit ) + { + encoder->trials[0].dis = rep_index; + encoder->trials[0].price = replens[rep_index]; + if( !LZe_move_pos( encoder, replens[rep_index] ) ) return 0; + return replens[rep_index]; + } + + 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].price = main_len; + if( !LZe_move_pos( encoder, main_len ) ) return 0; + return main_len; + } + + { + const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask; + const int match_price = price1( encoder->bm_match[state][pos_state] ); + const int rep_match_price = match_price + price1( encoder->bm_rep[state] ); + const uint8_t prev_byte = Mf_peek( encoder->matchfinder, -1 ); + const uint8_t cur_byte = Mf_peek( encoder->matchfinder, 0 ); + 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 ); + else + encoder->trials[1].price += + Lie_price_matched( &encoder->literal_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 ) ); + + if( main_len < min_match_len ) + { + encoder->trials[0].dis = encoder->trials[1].dis; + encoder->trials[0].price = 1; + if( !Mf_move_pos( encoder->matchfinder ) ) return 0; + return 1; + } + + if( main_len <= replens[rep_index] ) + { + int len; + main_len = replens[rep_index]; + for( len = min_match_len; len <= main_len; ++len ) + encoder->trials[len].price = infinite_price; + } + else + { + int len; + const int normal_match_price = match_price + price0( encoder->bm_rep[state] ); + for( len = min_match_len; len <= main_len; ++len ) + { + 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 ); + } + } + + 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 ) + { + struct Trial *cur_trial, *next_trial; + int newlen, pos_state, prev_index, len_limit; + int next_price, match_price, rep_match_price; + uint8_t prev_byte, cur_byte, match_byte; + + if( ++cur >= num_trials ) /* no more initialized trials */ + { + LZe_backward( encoder, cur ); + return cur; + } + newlen = LZe_read_match_distances( encoder ); + if( newlen >= encoder->matchfinder->match_len_limit ) + { + encoder->longest_match_found = newlen; + LZe_backward( encoder, cur ); + return cur; + } + + cur_trial = &encoder->trials[cur]; + prev_index = cur_trial->prev_index; + + 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_index == cur - 1 ) + { + if( cur_trial->dis == 0 ) St_set_short_rep( &cur_trial->state ); + else St_set_char( &cur_trial->state ); + } + 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 ); + } + + pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask; + prev_byte = Mf_peek( encoder->matchfinder, -1 ); + cur_byte = Mf_peek( encoder->matchfinder, 0 ); + 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 ); + else + next_price += Lie_price_matched( &encoder->literal_encoder, + prev_byte, cur_byte, match_byte ); + if( !Mf_move_pos( encoder->matchfinder ) ) return 0; + + next_trial = &encoder->trials[cur+1]; + + Tr_update( next_trial, -1, cur, next_price ); + + 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] ); + + 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 ) ); + + 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; + + for( rep = 0; rep < num_rep_distances; ++rep ) + { + 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 price = rep_match_price + + LZe_price_rep( encoder, rep, cur_trial->state, pos_state ); + while( num_trials < cur + 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 ) ); + } + } + + if( newlen <= len_limit && + ( newlen > min_match_len || + ( newlen == min_match_len && + encoder->match_distances[min_match_len] < modeled_distances ) ) ) + { + 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; + + 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 ) + { + if( dis != encoder->match_distances[len] || + dis_state < max_dis_states - 1 ) + { + dis = encoder->match_distances[len]; + dis_state = get_dis_state( len ); + dis_price = LZe_price_dis( encoder, dis, dis_state ); + } + Tr_update( &encoder->trials[cur+len], dis + num_rep_distances, cur, + normal_match_price + dis_price + + Lee_price( &encoder->len_encoder, len, pos_state ) ); + } + } + } + } + + +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; + int ahead, i; + State * const state = &encoder->state; + if( encoder->member_finished ) return true; + if( Re_member_position( &encoder->range_encoder ) >= encoder->member_size_limit ) + { + if( LZe_full_flush( encoder, *state ) ) encoder->member_finished = true; + return true; + } + + /* encode first byte */ + if( Mf_data_position( encoder->matchfinder ) == 0 && + !Mf_finished( encoder->matchfinder ) ) + { + 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 ); + Re_encode_bit( &encoder->range_encoder, &encoder->bm_match[*state][0], 0 ); + Lie_encode( &encoder->literal_encoder, &encoder->range_encoder, prev_byte, cur_byte ); + CRC32_update_byte( &encoder->crc, cur_byte ); + Mf_longest_match_len( encoder->matchfinder, 0 ); + if( !Mf_move_pos( encoder->matchfinder ) ) return false; + } + + while( !Mf_finished( encoder->matchfinder ) ) + { + 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; } + + ahead = LZe_sequence_optimizer( encoder, encoder->rep_distances, *state ); + if( ahead <= 0 ) return false; /* can't happen */ + encoder->fill_counter -= ahead; + + for( i = 0; ; ) + { + const int pos_state = + ( Mf_data_position( encoder->matchfinder ) - ahead ) & pos_state_mask; + const int dis = encoder->trials[i].dis; + const int len = encoder->trials[i].price; + + bool bit = ( dis < 0 && len == 1 ); + Re_encode_bit( &encoder->range_encoder, + &encoder->bm_match[*state][pos_state], !bit ); + if( bit ) /* literal byte */ + { + const uint8_t prev_byte = Mf_peek( encoder->matchfinder, -ahead-1 ); + 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 ); + 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 ); + } + St_set_char( state ); + } + else /* match or repeated match */ + { + CRC32_update_buf( &encoder->crc, Mf_ptr_to_current_pos( encoder->matchfinder ) - ahead, len ); + LZe_mtf_reps( dis, encoder->rep_distances ); + bit = ( dis < num_rep_distances ); + Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep[*state], bit ); + if( bit ) + { + bit = ( dis == 0 ); + Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep0[*state], !bit ); + if( bit ) + Re_encode_bit( &encoder->range_encoder, &encoder->bm_len[*state][pos_state], len > 1 ); + else + { + Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep1[*state], dis > 1 ); + if( dis > 1 ) + Re_encode_bit( &encoder->range_encoder, &encoder->bm_rep2[*state], dis > 2 ); + } + if( len == 1 ) St_set_short_rep( state ); + else + { + Lee_encode( &encoder->rep_match_len_encoder, &encoder->range_encoder, len, pos_state ); + St_set_rep( state ); + } + } + else + { + LZe_encode_pair( encoder, dis - num_rep_distances, len, pos_state ); + St_set_match( state ); + } + } + ahead -= len; i += len; + if( Re_member_position( &encoder->range_encoder ) >= encoder->member_size_limit ) + { + if( !Mf_dec_pos( encoder->matchfinder, ahead ) ) return false; + if( LZe_full_flush( encoder, *state ) ) encoder->member_finished = true; + return true; + } + if( ahead <= 0 ) break; + } + } + if( finish && LZe_full_flush( encoder, *state ) ) + encoder->member_finished = true; + return true; + } diff --git a/encoder.cc b/encoder.cc deleted file mode 100644 index fb7e65e..0000000 --- a/encoder.cc +++ /dev/null @@ -1,663 +0,0 @@ -/* Lzlib - A compression library for lzip files - Copyright (C) 2009, 2010, 2011 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 - the Free Software Foundation, either version 3 of the License, or - (at your option) any later version. - - This library is distributed in the hope that it will be useful, - but WITHOUT ANY WARRANTY; without even the implied warranty of - MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - GNU General Public License for more details. - - You should have received a copy of the GNU General Public License - along with this library. If not, see <http://www.gnu.org/licenses/>. - - As a special exception, you may use this file as part of a free - software library without restriction. Specifically, if other files - instantiate templates or use macros or inline functions from this - file, or you compile this file and link it with other files to - produce an executable, this file does not by itself cause the - resulting executable to be covered by the GNU General Public - License. This exception does not however invalidate any other - reasons why the executable file might be covered by the GNU General - Public License. -*/ - -#define _FILE_OFFSET_BITS 64 - -#include <algorithm> -#include <cerrno> -#include <cstdlib> -#include <cstring> -#include <stdint.h> - -#include "lzlib.h" -#include "lzip.h" -#include "encoder.h" - - -namespace Lzlib { - -const Dis_slots dis_slots; -const Prob_prices prob_prices; - - -int Matchfinder::write_data( const uint8_t * const in_buffer, const int in_size ) throw() - { - if( at_stream_end_ || in_size < 0 ) return 0; - const int size = std::min( buffer_size - stream_pos, in_size ); - if( size > 0 ) - { - std::memcpy( buffer + stream_pos, in_buffer, size ); - stream_pos += size; - } - return size; - } - - -Matchfinder::Matchfinder( const int dict_size, const int len_limit ) - : - partial_data_pos( 0 ), - dictionary_size_( dict_size ), - buffer_size( ( 2 * std::max( 65536, dictionary_size_ ) ) + - before_size + after_size ), - buffer( new( std::nothrow ) uint8_t[buffer_size] ), - prev_positions( new( std::nothrow ) int32_t[num_prev_positions] ), - prev_pos_tree( new( std::nothrow ) int32_t[2*dictionary_size_] ), - pos( 0 ), - cyclic_pos( 0 ), - stream_pos( 0 ), - pos_limit( buffer_size - after_size ), - match_len_limit_( len_limit ), - cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 ), - at_stream_end_( false ), - been_flushed( false ) - { - if( !buffer || !prev_positions || !prev_pos_tree ) - { - if( prev_pos_tree ) delete[] prev_pos_tree; - if( prev_positions ) delete[] prev_positions; - if( buffer ) delete[] buffer; - throw std::bad_alloc(); - } - for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1; - } - - -void Matchfinder::reset() throw() - { - const int size = stream_pos - pos; - if( size > 0 ) std::memmove( buffer, buffer + pos, size ); - partial_data_pos = 0; - stream_pos -= pos; - pos = 0; - cyclic_pos = 0; - at_stream_end_ = false; - been_flushed = false; - for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1; - } - - -bool Matchfinder::move_pos() throw() - { - if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0; - if( ++pos >= pos_limit ) - { - if( pos > stream_pos ) - { pos = stream_pos; return false; } - else - { - 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; - } - } - return true; - } - - -int Matchfinder::longest_match_len( int * const distances ) throw() - { - int32_t * ptr0 = prev_pos_tree + ( cyclic_pos << 1 ); - int32_t * ptr1 = ptr0 + 1; - int len_limit = match_len_limit_; - if( len_limit > available_bytes() ) - { - been_flushed = true; - len_limit = available_bytes(); - if( len_limit < 4 ) { *ptr0 = *ptr1 = -1; return 0; } - } - - int maxlen = min_match_len - 1; - const int min_pos = (pos >= dictionary_size_) ? - (pos - dictionary_size_ + 1) : 0; - const uint8_t * const data = buffer + pos; - const int key2 = num_prev_positions4 + num_prev_positions3 + - ( ( (int)data[0] << 8 ) | data[1] ); - const uint32_t tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 ); - const int key3 = num_prev_positions4 + - (int)( tmp & ( num_prev_positions3 - 1 ) ); - const int key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) & - ( num_prev_positions4 - 1 ) ); - - if( distances ) - { - int np = prev_positions[key2]; - if( np >= min_pos ) - { distances[2] = pos - np - 1; maxlen = 2; } - else distances[2] = 0x7FFFFFFF; - np = prev_positions[key3]; - if( np >= min_pos && buffer[np] == data[0] ) - { distances[3] = pos - np - 1; maxlen = 3; } - else distances[3] = 0x7FFFFFFF; - distances[4] = 0x7FFFFFFF; - } - - prev_positions[key2] = pos; - prev_positions[key3] = pos; - int newpos = prev_positions[key4]; - prev_positions[key4] = pos; - - int len = 0, len0 = 0, len1 = 0; - - for( int count = cycles; ; ) - { - if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; } - const uint8_t * const newdata = buffer + newpos; - if( been_flushed ) len = 0; - while( len < len_limit && newdata[len] == data[len] ) ++len; - - const int delta = pos - newpos; - if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1; - - int32_t * const newptr = prev_pos_tree + - ( ( cyclic_pos - delta + - ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) ) << 1 ); - - if( len < len_limit ) - { - if( newdata[len] < data[len] ) - { - *ptr0 = newpos; - ptr0 = newptr + 1; - newpos = *ptr0; - len0 = len; if( len1 < len ) len = len1; - } - else - { - *ptr1 = newpos; - ptr1 = newptr; - newpos = *ptr1; - len1 = len; if( len0 < len ) len = len0; - } - } - else - { - *ptr0 = newptr[0]; - *ptr1 = newptr[1]; - break; - } - } - if( distances ) - { - if( distances[3] > distances[4] ) distances[3] = distances[4]; - if( distances[2] > distances[3] ) distances[2] = distances[3]; - } - return maxlen; - } - - -void Len_encoder::encode( Range_encoder & range_encoder, int symbol, - const int pos_state ) - { - symbol -= min_match_len; - if( symbol < len_low_symbols ) - { - range_encoder.encode_bit( choice1, 0 ); - range_encoder.encode_tree( bm_low[pos_state], symbol, len_low_bits ); - } - else - { - range_encoder.encode_bit( choice1, 1 ); - if( symbol < len_low_symbols + len_mid_symbols ) - { - range_encoder.encode_bit( choice2, 0 ); - range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols, len_mid_bits ); - } - else - { - range_encoder.encode_bit( choice2, 1 ); - range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols, len_high_bits ); - } - } - if( --counters[pos_state] <= 0 ) update_prices( pos_state ); - } - - -void LZ_encoder::fill_align_prices() throw() - { - for( int i = 0; i < dis_align_size; ++i ) - align_prices[i] = price_symbol_reversed( bm_align, i, dis_align_bits ); - align_price_count = dis_align_size; - } - - -void LZ_encoder::fill_distance_prices() throw() - { - for( int dis = start_dis_model; dis < modeled_distances; ++dis ) - { - const int dis_slot = dis_slots.table( dis ); - const int direct_bits = ( dis_slot >> 1 ) - 1; - const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits; - const int price = - price_symbol_reversed( bm_dis + base - dis_slot, dis - base, direct_bits ); - for( int dis_state = 0; dis_state < max_dis_states; ++dis_state ) - dis_prices[dis_state][dis] = price; - } - - for( int dis_state = 0; dis_state < max_dis_states; ++dis_state ) - { - int * const dsp = dis_slot_prices[dis_state]; - const Bit_model * const bmds = bm_dis_slot[dis_state]; - int slot = 0; - for( ; slot < end_dis_model && slot < num_dis_slots; ++slot ) - dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ); - for( ; slot < num_dis_slots; ++slot ) - dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) + - (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift ); - - int * const dp = dis_prices[dis_state]; - int dis = 0; - for( ; dis < start_dis_model; ++dis ) - dp[dis] = dsp[dis]; - for( ; dis < modeled_distances; ++dis ) - dp[dis] += dsp[dis_slots.table( dis )]; - } - } - - -// 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. -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 - { - main_len = longest_match_found; - longest_match_found = 0; - } - else main_len = read_match_distances(); - - int replens[num_rep_distances]; - int rep_index = 0; - for( int i = 0; i < num_rep_distances; ++i ) - { - replens[i] = matchfinder.true_match_len( 0, reps[i] + 1, max_match_len ); - if( replens[i] > replens[rep_index] ) rep_index = i; - } - if( replens[rep_index] >= matchfinder.match_len_limit() ) - { - trials[0].dis = rep_index; - trials[0].price = replens[rep_index]; - if( !move_pos( replens[rep_index], true ) ) return 0; - return replens[rep_index]; - } - - if( main_len >= matchfinder.match_len_limit() ) - { - trials[0].dis = match_distances[matchfinder.match_len_limit()] + - num_rep_distances; - trials[0].price = main_len; - if( !move_pos( main_len, true ) ) return 0; - return main_len; - } - - { - const int pos_state = matchfinder.data_position() & pos_state_mask; - const uint8_t prev_byte = matchfinder[-1]; - const uint8_t cur_byte = matchfinder[0]; - const uint8_t match_byte = matchfinder[-reps[0]-1]; - - trials[0].state = state; - for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i]; - trials[1].dis = -1; - trials[1].prev_index = 0; - trials[1].price = price0( bm_match[state()][pos_state] ); - if( state.is_char() ) - trials[1].price += literal_encoder.price_symbol( prev_byte, cur_byte ); - else - trials[1].price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte ); - - const int match_price = price1( bm_match[state()][pos_state] ); - const int rep_match_price = match_price + price1( bm_rep[state()] ); - - if( match_byte == cur_byte ) - trials[1].update( 0, 0, rep_match_price + price_rep_len1( state, pos_state ) ); - - if( main_len < min_match_len ) - { - trials[0].dis = trials[1].dis; - trials[0].price = 1; - if( !matchfinder.move_pos() ) return 0; - return 1; - } - - if( main_len <= replens[rep_index] ) - { - main_len = replens[rep_index]; - for( int len = min_match_len; len <= main_len; ++len ) - trials[len].price = infinite_price; - } - else - { - const int normal_match_price = match_price + price0( bm_rep[state()] ); - for( int len = min_match_len; len <= main_len; ++len ) - { - trials[len].dis = match_distances[len] + num_rep_distances; - trials[len].prev_index = 0; - trials[len].price = normal_match_price + - price_pair( match_distances[len], len, pos_state ); - } - } - - for( int rep = 0; rep < num_rep_distances; ++rep ) - { - const int price = rep_match_price + - price_rep( rep, state, pos_state ); - for( int len = min_match_len; len <= replens[rep]; ++len ) - trials[len].update( rep, 0, price + - rep_match_len_encoder.price( len, pos_state ) ); - } - } - - int cur = 0; - int num_trials = main_len; - if( !matchfinder.move_pos() ) return 0; - - while( true ) - { - if( ++cur >= num_trials ) // no more initialized trials - { - backward( cur ); - return cur; - } - const int newlen = read_match_distances(); - if( newlen >= matchfinder.match_len_limit() ) - { - longest_match_found = newlen; - backward( cur ); - return cur; - } - - Trial & cur_trial = trials[cur]; - const int prev_index = cur_trial.prev_index; - - cur_trial.state = trials[prev_index].state; - - 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(); - else cur_trial.state.set_char(); - } - else - { - if( cur_trial.dis < num_rep_distances ) cur_trial.state.set_rep(); - else cur_trial.state.set_match(); - mtf_reps( cur_trial.dis, cur_trial.reps ); - } - - const int pos_state = matchfinder.data_position() & pos_state_mask; - const uint8_t prev_byte = matchfinder[-1]; - const uint8_t cur_byte = matchfinder[0]; - const uint8_t match_byte = matchfinder[-cur_trial.reps[0]-1]; - - int next_price = cur_trial.price + - price0( bm_match[cur_trial.state()][pos_state] ); - if( cur_trial.state.is_char() ) - next_price += literal_encoder.price_symbol( prev_byte, cur_byte ); - else - next_price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte ); - if( !matchfinder.move_pos() ) return 0; - - Trial & next_trial = trials[cur+1]; - - next_trial.update( -1, cur, next_price ); - - const int match_price = cur_trial.price + price1( bm_match[cur_trial.state()][pos_state] ); - const int rep_match_price = match_price + price1( bm_rep[cur_trial.state()] ); - - if( match_byte == cur_byte && next_trial.dis != 0 ) - next_trial.update( 0, cur, rep_match_price + - price_rep_len1( cur_trial.state, pos_state ) ); - - const int len_limit = std::min( std::min( max_num_trials - 1 - cur, - matchfinder.available_bytes() ), matchfinder.match_len_limit() ); - if( len_limit < min_match_len ) continue; - - for( int rep = 0; rep < num_rep_distances; ++rep ) - { - const int dis = cur_trial.reps[rep] + 1; - int len = 0; - const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1; - while( len < len_limit && data[len] == data[len-dis] ) ++len; - if( len >= min_match_len ) - { - const int price = rep_match_price + - price_rep( rep, cur_trial.state, pos_state ); - while( num_trials < cur + len ) - trials[++num_trials].price = infinite_price; - for( ; len >= min_match_len; --len ) - trials[cur+len].update( rep, cur, price + - rep_match_len_encoder.price( len, pos_state ) ); - } - } - - if( newlen <= len_limit && - ( newlen > min_match_len || - ( newlen == min_match_len && - match_distances[min_match_len] < modeled_distances ) ) ) - { - const int normal_match_price = match_price + - price0( bm_rep[cur_trial.state()] ); - while( num_trials < cur + newlen ) - trials[++num_trials].price = infinite_price; - - int dis = match_distances[min_match_len]; - int dis_state = get_dis_state( min_match_len ); - int dis_price = infinite_price; - if( dis < modeled_distances ) - trials[cur+min_match_len].update( dis + num_rep_distances, cur, - normal_match_price + dis_prices[dis_state][dis] + - len_encoder.price( min_match_len, pos_state ) ); - for( int len = min_match_len + 1; len <= newlen; ++len ) - { - if( dis != match_distances[len] || dis_state < max_dis_states - 1 ) - { - dis = match_distances[len]; - dis_state = get_dis_state( len ); - dis_price = price_dis( dis, dis_state ); - } - trials[cur+len].update( dis + num_rep_distances, cur, - normal_match_price + dis_price + - len_encoder.price( len, pos_state ) ); - } - } - } - } - - - // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) -bool LZ_encoder::full_flush( const State & state ) - { - if( member_finished_ || - range_encoder.free_bytes() < File_trailer::size() + max_marker_size ) - return false; - 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] ); - return true; - } - - - // Sync Flush mark => (dis == 0xFFFFFFFFU, len == min_match_len + 1) -bool LZ_encoder::sync_flush() - { - if( member_finished_ || range_encoder.free_bytes() < max_marker_size ) - return false; - const State & state = main_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 + 1, pos_state ); - range_encoder.flush(); - return true; - } - - -LZ_encoder::LZ_encoder( Matchfinder & mf, const File_header & header, - const long long member_size ) - : - member_size_limit( member_size - File_trailer::size() - max_marker_size ), - longest_match_found( 0 ), - crc_( 0xFFFFFFFFU ), - matchfinder( mf ), - 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_counter( 0 ), - member_finished_( false ) - { - for( int i = 0; i < num_rep_distances; ++i ) rep_distances[i] = 0; - 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 bool finish ) - { - const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 512 : 2048; - State & state = main_state; - if( member_finished_ ) return true; - if( range_encoder.member_position() >= member_size_limit ) - { if( full_flush( state ) ) { member_finished_ = true; } return true; } - - // encode first byte - if( matchfinder.data_position() == 0 && !matchfinder.finished() ) - { - if( matchfinder.available_bytes() < 4 && !matchfinder.at_stream_end() ) - return true; - const uint8_t prev_byte = 0; - const uint8_t cur_byte = matchfinder[0]; - range_encoder.encode_bit( bm_match[state()][0], 0 ); - literal_encoder.encode( range_encoder, prev_byte, cur_byte ); - crc32.update( crc_, cur_byte ); - if( !move_pos( 1 ) ) return false; - } - - while( true ) - { - if( matchfinder.finished() ) - { - if( finish && full_flush( state ) ) member_finished_ = true; - return true; - } - if( !matchfinder.enough_available_bytes() || - !range_encoder.enough_free_bytes() ) 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; - fill_counter -= ahead; - - for( int i = 0; ; ) - { - const int pos_state = - ( matchfinder.data_position() - ahead ) & pos_state_mask; - const int dis = trials[i].dis; - const int len = trials[i].price; - - bool bit = ( dis < 0 && len == 1 ); - range_encoder.encode_bit( bm_match[state()][pos_state], !bit ); - if( bit ) // literal byte - { - const uint8_t prev_byte = matchfinder[-ahead-1]; - const uint8_t cur_byte = matchfinder[-ahead]; - crc32.update( crc_, cur_byte ); - if( state.is_char() ) - literal_encoder.encode( range_encoder, prev_byte, cur_byte ); - else - { - const uint8_t match_byte = matchfinder[-ahead-rep_distances[0]-1]; - literal_encoder.encode_matched( range_encoder, - prev_byte, cur_byte, match_byte ); - } - state.set_char(); - } - else // match or repeated match - { - crc32.update( crc_, matchfinder.ptr_to_current_pos() - ahead, len ); - mtf_reps( dis, rep_distances ); - bit = ( dis < num_rep_distances ); - range_encoder.encode_bit( bm_rep[state()], bit ); - if( bit ) - { - bit = ( dis == 0 ); - range_encoder.encode_bit( bm_rep0[state()], !bit ); - if( bit ) - range_encoder.encode_bit( bm_len[state()][pos_state], len > 1 ); - else - { - range_encoder.encode_bit( bm_rep1[state()], dis > 1 ); - if( dis > 1 ) - range_encoder.encode_bit( bm_rep2[state()], dis > 2 ); - } - if( len == 1 ) state.set_short_rep(); - else - { - rep_match_len_encoder.encode( range_encoder, len, pos_state ); - state.set_rep(); - } - } - else - { - encode_pair( dis - num_rep_distances, len, pos_state ); - state.set_match(); - } - } - ahead -= len; i += len; - if( range_encoder.member_position() >= member_size_limit ) - { - if( !matchfinder.dec_pos( ahead ) ) return false; - if( full_flush( state ) ) member_finished_ = true; - return true; - } - if( ahead <= 0 ) break; - } - } - } - -} // end namespace Lzlib |