From 4b2126b14346d29e15ddd4867930e96c857e168c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sat, 7 Nov 2015 14:46:00 +0100 Subject: Merging upstream version 1.3. Signed-off-by: Daniel Baumann --- encoder.c | 1334 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 1334 insertions(+) create mode 100644 encoder.c (limited to 'encoder.c') 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 . + + 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<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<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<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; + } -- cgit v1.2.3