summaryrefslogtreecommitdiffstats
path: root/encoder.c
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--encoder.c605
1 files changed, 286 insertions, 319 deletions
diff --git a/encoder.c b/encoder.c
index 84cf760..3a22a25 100644
--- a/encoder.c
+++ b/encoder.c
@@ -1,5 +1,5 @@
/* Lzlib - Compression library for lzip files
- Copyright (C) 2009, 2010, 2011, 2012, 2013 Antonio Diaz Diaz.
+ Copyright (C) 2009, 2010, 2011, 2012, 2013, 2014 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
@@ -39,16 +39,16 @@ static bool Mf_normalize_pos( struct Matchfinder * const mf )
mf->pos -= offset;
mf->stream_pos -= offset;
for( i = 0; i < mf->num_prev_positions; ++i )
- if( mf->prev_positions[i] >= 0 ) mf->prev_positions[i] -= offset;
+ mf->prev_positions[i] -= min( mf->prev_positions[i], offset );
for( i = 0; i < 2 * ( mf->dictionary_size + 1 ); ++i )
- if( mf->prev_pos_tree[i] >= 0 ) mf->prev_pos_tree[i] -= offset;
+ mf->prev_pos_tree[i] -= min( mf->prev_pos_tree[i], offset );
}
return true;
}
-static bool Mf_init( struct Matchfinder * const mf,
- const int dict_size, const int match_len_limit )
+static bool Mf_init( struct Matchfinder * const mf, const int dict_size,
+ const int match_len_limit )
{
const int buffer_size_limit = ( 2 * dict_size ) + before_size + after_size;
unsigned size;
@@ -83,7 +83,7 @@ static bool Mf_init( struct Matchfinder * const mf,
else mf->prev_positions = (int32_t *)malloc( size * sizeof (int32_t) );
if( !mf->prev_positions ) { free( mf->buffer ); return false; }
mf->prev_pos_tree = mf->prev_positions + mf->num_prev_positions;
- for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
+ for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = 0;
return true;
}
@@ -111,8 +111,8 @@ static void Mf_adjust_distionary_size( struct Matchfinder * const mf )
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 );
+ if( mf->stream_pos > mf->pos )
+ memmove( mf->buffer, mf->buffer + mf->pos, mf->stream_pos - mf->pos );
mf->partial_data_pos = 0;
mf->stream_pos -= mf->pos;
mf->pos = 0;
@@ -120,7 +120,7 @@ static void Mf_reset( struct Matchfinder * const mf )
mf->at_stream_end = false;
mf->been_flushed = false;
mf->flushing = false;
- for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = -1;
+ for( i = 0; i < mf->num_prev_positions; ++i ) mf->prev_positions[i] = 0;
}
@@ -130,10 +130,11 @@ static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pair
int32_t * ptr1 = ptr0 + 1;
int32_t * newptr;
int len = 0, len0 = 0, len1 = 0;
- int maxlen = min_match_len - 1;
+ int maxlen = 0;
int num_pairs = 0;
- const int min_pos = (mf->pos > mf->dictionary_size) ?
- mf->pos - mf->dictionary_size : 0;
+ const int pos1 = mf->pos + 1;
+ const int min_pos =
+ ( mf->pos > mf->dictionary_size ) ? mf->pos - mf->dictionary_size : 0;
const uint8_t * const data = mf->buffer + mf->pos;
int count, delta, key2, key3, key4, newpos;
unsigned tmp;
@@ -143,12 +144,12 @@ static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pair
{
mf->been_flushed = true;
len_limit = Mf_available_bytes( mf );
- if( len_limit < 4 ) { *ptr0 = *ptr1 = -1; return 0; }
+ if( len_limit < 4 ) { *ptr0 = *ptr1 = 0; return 0; }
}
tmp = crc32[data[0]] ^ data[1];
key2 = tmp & ( num_prev_positions2 - 1 );
- tmp ^= (uint32_t)data[2] << 8;
+ tmp ^= (unsigned)data[2] << 8;
key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) );
key4 = num_prev_positions2 + num_prev_positions3 +
( ( tmp ^ ( crc32[data[3]] << 5 ) ) & mf->key4_mask );
@@ -157,41 +158,41 @@ static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pair
{
int np2 = mf->prev_positions[key2];
int np3 = mf->prev_positions[key3];
- if( np2 >= min_pos && mf->buffer[np2] == data[0] )
+ if( np2 > min_pos && mf->buffer[np2-1] == data[0] )
{
- pairs[0].dis = mf->pos - np2 - 1;
+ pairs[0].dis = mf->pos - np2;
pairs[0].len = maxlen = 2;
num_pairs = 1;
}
- if( np2 != np3 && np3 >= min_pos && mf->buffer[np3] == data[0] )
+ if( np2 != np3 && np3 > min_pos && mf->buffer[np3-1] == data[0] )
{
maxlen = 3;
- pairs[num_pairs].dis = mf->pos - np3 - 1;
- ++num_pairs;
np2 = np3;
+ pairs[num_pairs].dis = mf->pos - np2;
+ ++num_pairs;
}
if( num_pairs > 0 )
{
- delta = mf->pos - np2;
+ delta = pos1 - np2;
while( maxlen < len_limit && data[maxlen-delta] == data[maxlen] )
++maxlen;
pairs[num_pairs-1].len = maxlen;
- if( maxlen >= len_limit ) pairs = 0;
+ if( maxlen >= len_limit ) pairs = 0; /* done. now just skip */
}
if( maxlen < 3 ) maxlen = 3;
}
- mf->prev_positions[key2] = mf->pos;
- mf->prev_positions[key3] = mf->pos;
+ mf->prev_positions[key2] = pos1;
+ mf->prev_positions[key3] = pos1;
newpos = mf->prev_positions[key4];
- mf->prev_positions[key4] = mf->pos;
+ mf->prev_positions[key4] = pos1;
for( count = mf->cycles; ; )
{
- if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; }
+ if( newpos <= min_pos || --count < 0 ) { *ptr0 = *ptr1 = 0; break; }
if( mf->been_flushed ) len = 0;
- delta = mf->pos - newpos;
+ delta = pos1 - newpos;
newptr = mf->prev_pos_tree +
( ( mf->cyclic_pos - delta +
( (mf->cyclic_pos >= delta) ? 0 : mf->dictionary_size + 1 ) ) << 1 );
@@ -230,86 +231,83 @@ static int Mf_get_match_pairs( struct Matchfinder * const mf, struct Pair * pair
}
-static void Lee_encode( struct Len_encoder * const len_encoder,
+static void Lee_encode( struct Len_encoder * const le,
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->lm.choice1, 0 );
- Re_encode_tree( renc, len_encoder->lm.bm_low[pos_state], symbol, len_low_bits );
+ Re_encode_bit( renc, &le->lm.choice1, 0 );
+ Re_encode_tree( renc, le->lm.bm_low[pos_state], symbol, len_low_bits );
}
else
{
- Re_encode_bit( renc, &len_encoder->lm.choice1, 1 );
+ Re_encode_bit( renc, &le->lm.choice1, 1 );
if( symbol < len_low_symbols + len_mid_symbols )
{
- Re_encode_bit( renc, &len_encoder->lm.choice2, 0 );
- Re_encode_tree( renc, len_encoder->lm.bm_mid[pos_state],
+ Re_encode_bit( renc, &le->lm.choice2, 0 );
+ Re_encode_tree( renc, le->lm.bm_mid[pos_state],
symbol - len_low_symbols, len_mid_bits );
}
else
{
- Re_encode_bit( renc, &len_encoder->lm.choice2, 1 );
- Re_encode_tree( renc, len_encoder->lm.bm_high,
+ Re_encode_bit( renc, &le->lm.choice2, 1 );
+ Re_encode_tree( renc, le->lm.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 );
+ if( --le->counters[pos_state] <= 0 ) Lee_update_prices( le, pos_state );
}
/* End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len) */
-static bool LZe_full_flush( struct LZ_encoder * const encoder, const State state )
+static bool LZe_full_flush( struct LZ_encoder * const e, const State state )
{
int i;
- const int pos_state = Mf_data_position( encoder->matchfinder ) & pos_state_mask;
+ const int pos_state = Mf_data_position( e->matchfinder ) & pos_state_mask;
File_trailer trailer;
- if( encoder->member_finished ||
- Cb_free_bytes( &encoder->renc.cb ) < max_marker_size + Ft_size )
+ if( e->member_finished ||
+ Cb_free_bytes( &e->renc.cb ) < max_marker_size + Ft_size )
return false;
- Re_encode_bit( &encoder->renc, &encoder->bm_match[state][pos_state], 1 );
- Re_encode_bit( &encoder->renc, &encoder->bm_rep[state], 0 );
- LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len, pos_state );
- Re_flush( &encoder->renc );
- 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->renc ) + Ft_size );
+ Re_encode_bit( &e->renc, &e->bm_match[state][pos_state], 1 );
+ Re_encode_bit( &e->renc, &e->bm_rep[state], 0 );
+ LZe_encode_pair( e, 0xFFFFFFFFU, min_match_len, pos_state );
+ Re_flush( &e->renc );
+ Ft_set_data_crc( trailer, LZe_crc( e ) );
+ Ft_set_data_size( trailer, Mf_data_position( e->matchfinder ) );
+ Ft_set_member_size( trailer, Re_member_position( &e->renc ) + Ft_size );
for( i = 0; i < Ft_size; ++i )
- Cb_put_byte( &encoder->renc.cb, trailer[i] );
+ Cb_put_byte( &e->renc.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 )
+static bool LZe_sync_flush( struct LZ_encoder * const e )
{
- 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->renc.cb ) < max_marker_size )
+ const int pos_state = Mf_data_position( e->matchfinder ) & pos_state_mask;
+ const State state = e->state;
+ if( e->member_finished || Cb_free_bytes( &e->renc.cb ) < max_marker_size )
return false;
- Re_encode_bit( &encoder->renc, &encoder->bm_match[state][pos_state], 1 );
- Re_encode_bit( &encoder->renc, &encoder->bm_rep[state], 0 );
- LZe_encode_pair( encoder, 0xFFFFFFFFU, min_match_len + 1, pos_state );
- Re_flush( &encoder->renc );
+ Re_encode_bit( &e->renc, &e->bm_match[state][pos_state], 1 );
+ Re_encode_bit( &e->renc, &e->bm_rep[state], 0 );
+ LZe_encode_pair( e, 0xFFFFFFFFU, min_match_len + 1, pos_state );
+ Re_flush( &e->renc );
return true;
}
-static void LZe_fill_align_prices( struct LZ_encoder * const encoder )
+static void LZe_fill_align_prices( struct LZ_encoder * const e )
{
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;
+ e->align_prices[i] = price_symbol_reversed( e->bm_align, i, dis_align_bits );
+ e->align_price_count = dis_align_size;
}
-static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
+static void LZe_fill_distance_prices( struct LZ_encoder * const e )
{
int dis, len_state;
for( dis = start_dis_model; dis < modeled_distances; ++dis )
@@ -317,22 +315,21 @@ static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
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 - 1,
- dis - base, direct_bits );
+ const int price = price_symbol_reversed( e->bm_dis + base - dis_slot - 1,
+ dis - base, direct_bits );
for( len_state = 0; len_state < len_states; ++len_state )
- encoder->dis_prices[len_state][dis] = price;
+ e->dis_prices[len_state][dis] = price;
}
for( len_state = 0; len_state < len_states; ++len_state )
{
- int * const dsp = encoder->dis_slot_prices[len_state];
- int * const dp = encoder->dis_prices[len_state];
- const Bit_model * const bmds = encoder->bm_dis_slot[len_state];
+ int * const dsp = e->dis_slot_prices[len_state];
+ int * const dp = e->dis_prices[len_state];
+ const Bit_model * const bmds = e->bm_dis_slot[len_state];
int slot = 0;
- for( ; slot < end_dis_model && slot < encoder->num_dis_slots; ++slot )
+ for( ; slot < end_dis_model; ++slot )
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits );
- for( ; slot < encoder->num_dis_slots; ++slot )
+ for( ; slot < e->num_dis_slots; ++slot )
dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) +
(((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift_bits );
@@ -344,51 +341,49 @@ static void LZe_fill_distance_prices( struct LZ_encoder * const encoder )
}
-static bool LZe_init( struct LZ_encoder * const encoder,
+static bool LZe_init( struct LZ_encoder * const e,
struct Matchfinder * const mf,
const File_header header,
const unsigned long long member_size )
{
int i;
- encoder->member_size_limit = member_size - Ft_size - max_marker_size;
- encoder->pending_num_pairs = 0;
- encoder->crc = 0xFFFFFFFFU;
-
- Bm_array_init( encoder->bm_literal[0], (1 << literal_context_bits) * 0x300 );
- Bm_array_init( encoder->bm_match[0], states * pos_states );
- Bm_array_init( encoder->bm_rep, states );
- Bm_array_init( encoder->bm_rep0, states );
- Bm_array_init( encoder->bm_rep1, states );
- Bm_array_init( encoder->bm_rep2, states );
- Bm_array_init( encoder->bm_len[0], states * pos_states );
- Bm_array_init( encoder->bm_dis_slot[0], len_states * (1 << dis_slot_bits) );
- Bm_array_init( encoder->bm_dis, modeled_distances - end_dis_model );
- Bm_array_init( encoder->bm_align, dis_align_size );
-
- encoder->matchfinder = mf;
- if( !Re_init( &encoder->renc ) ) return false;
- Lee_init( &encoder->match_len_encoder, encoder->matchfinder->match_len_limit );
- Lee_init( &encoder->rep_len_encoder, encoder->matchfinder->match_len_limit );
- encoder->num_dis_slots =
- 2 * real_bits( encoder->matchfinder->dictionary_size - 1 );
-
- for( i = 0; i < num_rep_distances; ++i ) encoder->rep_distances[i] = 0;
- encoder->align_price_count = 0;
- encoder->fill_counter = 0;
- encoder->state = 0;
- encoder->member_finished = false;
+ e->member_size_limit = member_size - Ft_size - max_marker_size;
+ e->pending_num_pairs = 0;
+ e->crc = 0xFFFFFFFFU;
+
+ Bm_array_init( e->bm_literal[0], (1 << literal_context_bits) * 0x300 );
+ Bm_array_init( e->bm_match[0], states * pos_states );
+ Bm_array_init( e->bm_rep, states );
+ Bm_array_init( e->bm_rep0, states );
+ Bm_array_init( e->bm_rep1, states );
+ Bm_array_init( e->bm_rep2, states );
+ Bm_array_init( e->bm_len[0], states * pos_states );
+ Bm_array_init( e->bm_dis_slot[0], len_states * (1 << dis_slot_bits) );
+ Bm_array_init( e->bm_dis, modeled_distances - end_dis_model );
+ Bm_array_init( e->bm_align, dis_align_size );
+
+ e->matchfinder = mf;
+ if( !Re_init( &e->renc ) ) return false;
+ Lee_init( &e->match_len_encoder, mf->match_len_limit );
+ Lee_init( &e->rep_len_encoder, mf->match_len_limit );
+ for( i = 0; i < num_rep_distances; ++i ) e->reps[i] = 0;
+ e->align_price_count = 0;
+ e->num_dis_slots = 2 * real_bits( mf->dictionary_size - 1 );
+ e->fill_counter = 0;
+ e->state = 0;
+ e->member_finished = false;
for( i = 0; i < Fh_size; ++i )
- Cb_put_byte( &encoder->renc.cb, header[i] );
+ Cb_put_byte( &e->renc.cb, header[i] );
return true;
}
/* Return value == number of bytes advanced (ahead).
trials[0]..trials[ahead-1] contain the steps to encode.
- ( trials[0].dis == -1 && trials[0].price == 1 ) means literal.
+ ( trials[0].dis == -1 ) means literal.
*/
-static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
+static int LZe_sequence_optimizer( struct LZ_encoder * const e,
const int reps[num_rep_distances],
const State state )
{
@@ -396,111 +391,108 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
int replens[num_rep_distances];
int rep_index = 0;
- if( encoder->pending_num_pairs > 0 ) /* from previous call */
+ if( e->pending_num_pairs > 0 ) /* from previous call */
{
- num_pairs = encoder->pending_num_pairs;
- encoder->pending_num_pairs = 0;
+ num_pairs = e->pending_num_pairs;
+ e->pending_num_pairs = 0;
}
else
- num_pairs = LZe_read_match_distances( encoder );
- main_len = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
+ num_pairs = LZe_read_match_distances( e );
+ main_len = ( num_pairs > 0 ) ? e->pairs[num_pairs-1].len : 0;
for( i = 0; i < num_rep_distances; ++i )
{
replens[i] =
- Mf_true_match_len( encoder->matchfinder, 0, reps[i] + 1, max_match_len );
+ Mf_true_match_len( e->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 )
+ if( replens[rep_index] >= e->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;
+ e->trials[0].dis = rep_index;
+ e->trials[0].price = replens[rep_index];
+ if( !LZe_move_pos( e, replens[rep_index] ) ) return 0;
return replens[rep_index];
}
- if( main_len >= encoder->matchfinder->match_len_limit )
+ if( main_len >= e->matchfinder->match_len_limit )
{
- encoder->trials[0].dis = encoder->pairs[num_pairs-1].dis + num_rep_distances;
- encoder->trials[0].price = main_len;
- if( !LZe_move_pos( encoder, main_len ) ) return 0;
+ e->trials[0].dis = e->pairs[num_pairs-1].dis + num_rep_distances;
+ e->trials[0].price = main_len;
+ if( !LZe_move_pos( e, 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;
- encoder->trials[1].dis = -1;
- encoder->trials[1].price = price0( encoder->bm_match[state][pos_state] );
+ const int pos_state = Mf_data_position( e->matchfinder ) & pos_state_mask;
+ const int match_price = price1( e->bm_match[state][pos_state] );
+ const int rep_match_price = match_price + price1( e->bm_rep[state] );
+ const uint8_t prev_byte = Mf_peek( e->matchfinder, 1 );
+ const uint8_t cur_byte = Mf_peek( e->matchfinder, 0 );
+ const uint8_t match_byte = Mf_peek( e->matchfinder, reps[0] + 1 );
+
+ e->trials[0].state = state;
+ e->trials[1].dis = -1; /* literal */
+ e->trials[1].price = price0( e->bm_match[state][pos_state] );
if( St_is_char( state ) )
- encoder->trials[1].price +=
- LZe_price_literal( encoder, prev_byte, cur_byte );
+ e->trials[1].price += LZe_price_literal( e, prev_byte, cur_byte );
else
- encoder->trials[1].price +=
- LZe_price_matched( encoder, prev_byte, cur_byte, match_byte );
+ e->trials[1].price += LZe_price_matched( e, prev_byte, cur_byte, match_byte );
if( match_byte == cur_byte )
- Tr_update( &encoder->trials[1], rep_match_price +
- LZe_price_rep_len1( encoder, state, pos_state ), 0, 0 );
+ Tr_update( &e->trials[1], rep_match_price +
+ LZe_price_shortrep( e, state, pos_state ), 0, 0 );
num_trials = max( main_len, replens[rep_index] );
if( num_trials < min_match_len )
{
- encoder->trials[0].dis = encoder->trials[1].dis;
- encoder->trials[0].price = 1;
- if( !Mf_move_pos( encoder->matchfinder ) ) return 0;
+ e->trials[0].dis = e->trials[1].dis;
+ e->trials[0].price = 1;
+ if( !Mf_move_pos( e->matchfinder ) ) return 0;
return 1;
}
for( i = 0; i < num_rep_distances; ++i )
- encoder->trials[0].reps[i] = reps[i];
- encoder->trials[1].prev_index = 0;
- encoder->trials[1].prev_index2 = single_step_trial;
+ e->trials[0].reps[i] = reps[i];
+ e->trials[1].prev_index = 0;
+ e->trials[1].prev_index2 = single_step_trial;
for( len = min_match_len; len <= num_trials; ++len )
- encoder->trials[len].price = infinite_price;
+ e->trials[len].price = infinite_price;
for( rep = 0; rep < num_rep_distances; ++rep )
{
int price;
if( replens[rep] < min_match_len ) continue;
- price = rep_match_price + LZe_price_rep( encoder, rep, state, pos_state );
+ price = rep_match_price + LZe_price_rep( e, rep, state, pos_state );
for( len = min_match_len; len <= replens[rep]; ++len )
- Tr_update( &encoder->trials[len], price +
- Lee_price( &encoder->rep_len_encoder, len, pos_state ),
- rep, 0 );
+ Tr_update( &e->trials[len], price +
+ Lee_price( &e->rep_len_encoder, len, pos_state ), rep, 0 );
}
if( main_len > replens[0] )
{
- const int normal_match_price = match_price + price0( encoder->bm_rep[state] );
+ const int normal_match_price = match_price + price0( e->bm_rep[state] );
i = 0, len = max( replens[0] + 1, min_match_len );
- while( len > encoder->pairs[i].len ) ++i;
+ while( len > e->pairs[i].len ) ++i;
while( true )
{
- const int dis = encoder->pairs[i].dis;
- Tr_update( &encoder->trials[len], normal_match_price +
- LZe_price_pair( encoder, dis, len, pos_state ),
+ const int dis = e->pairs[i].dis;
+ Tr_update( &e->trials[len], normal_match_price +
+ LZe_price_pair( e, dis, len, pos_state ),
dis + num_rep_distances, 0 );
- if( ++len > encoder->pairs[i].len && ++i >= num_pairs ) break;
+ if( ++len > e->pairs[i].len && ++i >= num_pairs ) break;
}
}
}
- if( !Mf_move_pos( encoder->matchfinder ) ) return 0;
+ if( !Mf_move_pos( e->matchfinder ) ) return 0;
while( true ) /* price optimization loop */
{
struct Trial *cur_trial, *next_trial;
- int newlen, pos_state, prev_index, prev_index2, available_bytes, len_limit;
+ int newlen, pos_state, available_bytes, len_limit;
int start_len = min_match_len;
int next_price, match_price, rep_match_price;
State cur_state;
@@ -508,120 +500,105 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
if( ++cur >= num_trials ) /* no more initialized trials */
{
- LZe_backward( encoder, cur );
+ LZe_backward( e, cur );
return cur;
}
- num_pairs = LZe_read_match_distances( encoder );
- newlen = ( num_pairs > 0 ) ? encoder->pairs[num_pairs-1].len : 0;
- if( newlen >= encoder->matchfinder->match_len_limit )
+ num_pairs = LZe_read_match_distances( e );
+ newlen = ( num_pairs > 0 ) ? e->pairs[num_pairs-1].len : 0;
+ if( newlen >= e->matchfinder->match_len_limit )
{
- encoder->pending_num_pairs = num_pairs;
- LZe_backward( encoder, cur );
+ e->pending_num_pairs = num_pairs;
+ LZe_backward( e, cur );
return cur;
}
/* give final values to current trial */
- cur_trial = &encoder->trials[cur];
- prev_index = cur_trial->prev_index;
- prev_index2 = cur_trial->prev_index2;
+ cur_trial = &e->trials[cur];
+ {
+ int dis = cur_trial->dis;
+ int prev_index = cur_trial->prev_index;
+ const int prev_index2 = cur_trial->prev_index2;
- if( prev_index2 != single_step_trial )
+ if( prev_index2 == single_step_trial )
{
- --prev_index;
- if( prev_index2 >= 0 )
+ cur_state = e->trials[prev_index].state;
+ if( prev_index + 1 == cur ) /* len == 1 */
{
- cur_state = encoder->trials[prev_index2].state;
- if( cur_trial->dis2 < num_rep_distances )
- cur_state = St_set_rep( cur_state );
- else
- cur_state = St_set_match( cur_state );
+ if( dis == 0 ) cur_state = St_set_short_rep( cur_state );
+ else cur_state = St_set_char( cur_state ); /* literal */
}
- else
- cur_state = encoder->trials[prev_index].state;
- cur_state = St_set_char( cur_state );
+ else if( dis < num_rep_distances ) cur_state = St_set_rep( cur_state );
+ else cur_state = St_set_match( cur_state );
}
- else
- cur_state = encoder->trials[prev_index].state;
-
- if( prev_index == cur - 1 )
+ else if( prev_index2 == dual_step_trial ) /* dis == 0 */
{
- if( cur_trial->dis == 0 )
- cur_state = St_set_short_rep( cur_state );
- else
- cur_state = St_set_char( cur_state );
- for( i = 0; i < num_rep_distances; ++i )
- cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
+ --prev_index;
+ cur_state = e->trials[prev_index].state;
+ cur_state = St_set_char( cur_state );
+ cur_state = St_set_rep( cur_state );
}
- else
+ else /* if( prev_index2 >= 0 ) */
{
- int dis;
- if( prev_index2 >= 0 )
- {
- dis = cur_trial->dis2;
- prev_index = prev_index2;
- cur_state = St_set_rep( cur_state );
- }
- else
- {
- dis = cur_trial->dis;
- if( dis < num_rep_distances )
- cur_state = St_set_rep( cur_state );
- else
- cur_state = St_set_match( cur_state );
- }
- for( i = 0; i < num_rep_distances; ++i )
- cur_trial->reps[i] = encoder->trials[prev_index].reps[i];
- LZe_mtf_reps( dis, cur_trial->reps );
+ prev_index = prev_index2;
+ cur_state = e->trials[prev_index].state;
+ if( dis < num_rep_distances ) cur_state = St_set_rep( cur_state );
+ else cur_state = St_set_match( cur_state );
+ cur_state = St_set_char( cur_state );
+ cur_state = St_set_rep( cur_state );
}
cur_trial->state = cur_state;
+ for( i = 0; i < num_rep_distances; ++i )
+ cur_trial->reps[i] = e->trials[prev_index].reps[i];
+ mtf_reps( 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 );
+ pos_state = Mf_data_position( e->matchfinder ) & pos_state_mask;
+ prev_byte = Mf_peek( e->matchfinder, 1 );
+ cur_byte = Mf_peek( e->matchfinder, 0 );
+ match_byte = Mf_peek( e->matchfinder, cur_trial->reps[0] + 1 );
+ if( !Mf_move_pos( e->matchfinder ) ) return 0;
next_price = cur_trial->price +
- price0( encoder->bm_match[cur_state][pos_state] );
+ price0( e->bm_match[cur_state][pos_state] );
if( St_is_char( cur_state ) )
- next_price += LZe_price_literal( encoder, prev_byte, cur_byte );
+ next_price += LZe_price_literal( e, prev_byte, cur_byte );
else
- next_price += LZe_price_matched( encoder, prev_byte, cur_byte, match_byte );
- if( !Mf_move_pos( encoder->matchfinder ) ) return 0;
+ next_price += LZe_price_matched( e, prev_byte, cur_byte, match_byte );
/* try last updates to next trial */
- next_trial = &encoder->trials[cur+1];
+ next_trial = &e->trials[cur+1];
- Tr_update( next_trial, next_price, -1, cur );
+ Tr_update( next_trial, next_price, -1, cur ); /* literal */
- match_price = cur_trial->price + price1( encoder->bm_match[cur_state][pos_state] );
- rep_match_price = match_price + price1( encoder->bm_rep[cur_state] );
+ match_price = cur_trial->price + price1( e->bm_match[cur_state][pos_state] );
+ rep_match_price = match_price + price1( e->bm_rep[cur_state] );
- if( match_byte == cur_byte && next_trial->dis != 0 )
+ if( match_byte == cur_byte && next_trial->dis != 0 &&
+ next_trial->prev_index2 == single_step_trial )
{
const int price = rep_match_price +
- LZe_price_rep_len1( encoder, cur_state, pos_state );
+ LZe_price_shortrep( e, cur_state, pos_state );
if( price <= next_trial->price )
{
next_trial->price = price;
next_trial->dis = 0;
next_trial->prev_index = cur;
- next_trial->prev_index2 = single_step_trial;
}
}
- available_bytes = min( Mf_available_bytes( encoder->matchfinder ) + 1,
+ available_bytes = min( Mf_available_bytes( e->matchfinder ) + 1,
max_num_trials - 1 - cur );
if( available_bytes < min_match_len ) continue;
- len_limit = min( encoder->matchfinder->match_len_limit, available_bytes );
+ len_limit = min( e->matchfinder->match_len_limit, available_bytes );
/* try literal + rep0 */
if( match_byte != cur_byte && next_trial->prev_index != cur )
{
- const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+ const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1;
const int dis = cur_trial->reps[0] + 1;
- const int limit = min( encoder->matchfinder->match_len_limit + 1,
+ const int limit = min( e->matchfinder->match_len_limit + 1,
available_bytes );
len = 1;
while( len < limit && data[len-dis] == data[len] ) ++len;
@@ -630,40 +607,38 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
const int pos_state2 = ( pos_state + 1 ) & pos_state_mask;
const State state2 = St_set_char( cur_state );
const int price = next_price +
- price1( encoder->bm_match[state2][pos_state2] ) +
- price1( encoder->bm_rep[state2] ) +
- LZe_price_rep0_len( encoder, len, state2, pos_state2 );
+ price1( e->bm_match[state2][pos_state2] ) +
+ price1( e->bm_rep[state2] ) +
+ LZe_price_rep0_len( e, len, state2, pos_state2 );
while( num_trials < cur + 1 + len )
- encoder->trials[++num_trials].price = infinite_price;
- Tr_update2( &encoder->trials[cur+1+len], price, 0, cur + 1 );
+ e->trials[++num_trials].price = infinite_price;
+ Tr_update2( &e->trials[cur+1+len], price, cur + 1 );
}
}
/* try rep distances */
for( rep = 0; rep < num_rep_distances; ++rep )
{
- const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+ const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1;
int price;
const int dis = cur_trial->reps[rep] + 1;
- if( data[-dis] != data[0] || data[1-dis] != data[1] ) continue;
+ if( data[0-dis] != data[0] || data[1-dis] != data[1] ) continue;
for( len = min_match_len; len < len_limit; ++len )
if( data[len-dis] != data[len] ) break;
while( num_trials < cur + len )
- encoder->trials[++num_trials].price = infinite_price;
- price = rep_match_price +
- LZe_price_rep( encoder, rep, cur_state, pos_state );
+ e->trials[++num_trials].price = infinite_price;
+ price = rep_match_price + LZe_price_rep( e, rep, cur_state, pos_state );
for( i = min_match_len; i <= len; ++i )
- Tr_update( &encoder->trials[cur+i], price +
- Lee_price( &encoder->rep_len_encoder, i, pos_state ),
- rep, cur );
+ Tr_update( &e->trials[cur+i], price +
+ Lee_price( &e->rep_len_encoder, i, pos_state ), rep, cur );
if( rep == 0 ) start_len = len + 1; /* discard shorter matches */
/* try rep + literal + rep0 */
{
int len2 = len + 1, pos_state2;
- const int limit = min( encoder->matchfinder->match_len_limit + len2,
+ const int limit = min( e->matchfinder->match_len_limit + len2,
available_bytes );
State state2;
while( len2 < limit && data[len2-dis] == data[len2] ) ++len2;
@@ -672,18 +647,17 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
pos_state2 = ( pos_state + len ) & pos_state_mask;
state2 = St_set_rep( cur_state );
- price += Lee_price( &encoder->rep_len_encoder, len, pos_state ) +
- price0( encoder->bm_match[state2][pos_state2] ) +
- LZe_price_matched( encoder, data[len-1], data[len], data[len-dis] );
+ price += Lee_price( &e->rep_len_encoder, len, pos_state ) +
+ price0( e->bm_match[state2][pos_state2] ) +
+ LZe_price_matched( e, data[len-1], data[len], data[len-dis] );
pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
state2 = St_set_char( state2 );
- price += price1( encoder->bm_match[state2][pos_state2] ) +
- price1( encoder->bm_rep[state2] ) +
- LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+ price += price1( e->bm_match[state2][pos_state2] ) +
+ price1( e->bm_rep[state2] ) +
+ LZe_price_rep0_len( e, len2, state2, pos_state2 );
while( num_trials < cur + len + 1 + len2 )
- encoder->trials[++num_trials].price = infinite_price;
- Tr_update3( &encoder->trials[cur+len+1+len2], price, 0, cur + len + 1,
- rep, cur );
+ e->trials[++num_trials].price = infinite_price;
+ Tr_update3( &e->trials[cur+len+1+len2], price, rep, cur + len + 1, cur );
}
}
@@ -692,28 +666,27 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
{
int dis;
const int normal_match_price = match_price +
- price0( encoder->bm_rep[cur_state] );
+ price0( e->bm_rep[cur_state] );
while( num_trials < cur + newlen )
- encoder->trials[++num_trials].price = infinite_price;
+ e->trials[++num_trials].price = infinite_price;
i = 0;
- while( start_len > encoder->pairs[i].len ) ++i;
- dis = encoder->pairs[i].dis;
+ while( start_len > e->pairs[i].len ) ++i;
+ dis = e->pairs[i].dis;
for( len = start_len; ; ++len )
{
- int price = normal_match_price +
- LZe_price_pair( encoder, dis, len, pos_state );
+ int price = normal_match_price + LZe_price_pair( e, dis, len, pos_state );
- Tr_update( &encoder->trials[cur+len], price, dis + num_rep_distances, cur );
+ Tr_update( &e->trials[cur+len], price, dis + num_rep_distances, cur );
/* try match + literal + rep0 */
- if( len == encoder->pairs[i].len )
+ if( len == e->pairs[i].len )
{
- const uint8_t * const data = Mf_ptr_to_current_pos( encoder->matchfinder ) - 1;
+ const uint8_t * const data = Mf_ptr_to_current_pos( e->matchfinder ) - 1;
const int dis2 = dis + 1;
int len2 = len + 1;
- const int limit = min( encoder->matchfinder->match_len_limit + len2,
+ const int limit = min( e->matchfinder->match_len_limit + len2,
available_bytes );
while( len2 < limit && data[len2-dis2] == data[len2] ) ++len2;
len2 -= len + 1;
@@ -721,21 +694,21 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
{
int pos_state2 = ( pos_state + len ) & pos_state_mask;
State state2 = St_set_match( cur_state );
- price += price0( encoder->bm_match[state2][pos_state2] ) +
- LZe_price_matched( encoder, data[len-1], data[len], data[len-dis2] );
+ price += price0( e->bm_match[state2][pos_state2] ) +
+ LZe_price_matched( e, data[len-1], data[len], data[len-dis2] );
pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
state2 = St_set_char( state2 );
- price += price1( encoder->bm_match[state2][pos_state2] ) +
- price1( encoder->bm_rep[state2] ) +
- LZe_price_rep0_len( encoder, len2, state2, pos_state2 );
+ price += price1( e->bm_match[state2][pos_state2] ) +
+ price1( e->bm_rep[state2] ) +
+ LZe_price_rep0_len( e, len2, state2, pos_state2 );
while( num_trials < cur + len + 1 + len2 )
- encoder->trials[++num_trials].price = infinite_price;
- Tr_update3( &encoder->trials[cur+len+1+len2], price, 0,
- cur + len + 1, dis + num_rep_distances, cur );
+ e->trials[++num_trials].price = infinite_price;
+ Tr_update3( &e->trials[cur+len+1+len2], price,
+ dis + num_rep_distances, cur + len + 1, cur );
}
if( ++i >= num_pairs ) break;
- dis = encoder->pairs[i].dis;
+ dis = e->pairs[i].dis;
}
}
}
@@ -743,118 +716,112 @@ static int LZe_sequence_optimizer( struct LZ_encoder * const encoder,
}
-static bool LZe_encode_member( struct LZ_encoder * const encoder )
+static bool LZe_encode_member( struct LZ_encoder * const e )
{
- const int fill_count =
- ( encoder->matchfinder->match_len_limit > 12 ) ? 128 : 512;
+ const int fill_count = ( e->matchfinder->match_len_limit > 12 ) ? 128 : 512;
int ahead, i;
- State * const state = &encoder->state;
+ State * const state = &e->state;
- if( encoder->member_finished ) return true;
- if( Re_member_position( &encoder->renc ) >= encoder->member_size_limit )
+ if( e->member_finished ) return true;
+ if( Re_member_position( &e->renc ) >= e->member_size_limit )
{
- if( LZe_full_flush( encoder, *state ) ) encoder->member_finished = true;
+ if( LZe_full_flush( e, *state ) ) e->member_finished = true;
return true;
}
- if( Mf_data_position( encoder->matchfinder ) == 0 &&
- !Mf_finished( encoder->matchfinder ) ) /* encode first byte */
+ if( Mf_data_position( e->matchfinder ) == 0 &&
+ !Mf_finished( e->matchfinder ) ) /* encode first byte */
{
const uint8_t prev_byte = 0;
- uint8_t cur_byte;
- if( Mf_available_bytes( encoder->matchfinder ) < max_match_len &&
- !Mf_flushing_or_end( encoder->matchfinder ) )
- return true;
- cur_byte = Mf_peek( encoder->matchfinder, 0 );
- Re_encode_bit( &encoder->renc, &encoder->bm_match[*state][0], 0 );
- LZe_encode_literal( encoder, prev_byte, cur_byte );
- CRC32_update_byte( &encoder->crc, cur_byte );
- Mf_get_match_pairs( encoder->matchfinder, 0 );
- if( !Mf_move_pos( encoder->matchfinder ) ) return false;
+ const uint8_t cur_byte = Mf_peek( e->matchfinder, 0 );
+ if( !Mf_enough_available_bytes( e->matchfinder ) ||
+ !Re_enough_free_bytes( &e->renc ) ) return true;
+ CRC32_update_byte( &e->crc, cur_byte );
+ Re_encode_bit( &e->renc, &e->bm_match[*state][0], 0 );
+ LZe_encode_literal( e, prev_byte, cur_byte );
+ Mf_get_match_pairs( e->matchfinder, 0 );
+ if( !Mf_move_pos( e->matchfinder ) ) return false;
}
- while( !Mf_finished( encoder->matchfinder ) )
+ while( !Mf_finished( e->matchfinder ) )
{
- if( !Mf_enough_available_bytes( encoder->matchfinder ) ||
- !Re_enough_free_bytes( &encoder->renc ) ) return true;
- if( encoder->pending_num_pairs == 0 )
+ if( !Mf_enough_available_bytes( e->matchfinder ) ||
+ !Re_enough_free_bytes( &e->renc ) ) return true;
+ if( e->pending_num_pairs == 0 )
{
- if( encoder->fill_counter <= 0 )
- { LZe_fill_distance_prices( encoder ); encoder->fill_counter = fill_count; }
- if( encoder->align_price_count <= 0 )
- LZe_fill_align_prices( encoder );
+ if( e->fill_counter <= 0 )
+ { LZe_fill_distance_prices( e ); e->fill_counter = fill_count; }
+ if( e->align_price_count <= 0 ) LZe_fill_align_prices( e );
}
- ahead = LZe_sequence_optimizer( encoder, encoder->rep_distances, *state );
+ ahead = LZe_sequence_optimizer( e, e->reps, *state );
if( ahead <= 0 ) return false; /* can't happen */
- for( i = 0; ; )
+ for( i = 0; ahead > 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;
+ ( Mf_data_position( e->matchfinder ) - ahead ) & pos_state_mask;
+ const int dis = e->trials[i].dis;
+ const int len = e->trials[i].price;
- bool bit = ( dis < 0 && len == 1 );
- Re_encode_bit( &encoder->renc,
- &encoder->bm_match[*state][pos_state], !bit );
+ bool bit = ( dis < 0 );
+ Re_encode_bit( &e->renc, &e->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 );
+ const uint8_t prev_byte = Mf_peek( e->matchfinder, ahead + 1 );
+ const uint8_t cur_byte = Mf_peek( e->matchfinder, ahead );
+ CRC32_update_byte( &e->crc, cur_byte );
if( St_is_char( *state ) )
- LZe_encode_literal( encoder, prev_byte, cur_byte );
+ LZe_encode_literal( e, prev_byte, cur_byte );
else
{
const uint8_t match_byte =
- Mf_peek( encoder->matchfinder, -ahead-encoder->rep_distances[0]-1 );
- LZe_encode_matched( encoder, prev_byte, cur_byte, match_byte );
+ Mf_peek( e->matchfinder, ahead + e->reps[0] + 1 );
+ LZe_encode_matched( e, prev_byte, cur_byte, match_byte );
}
*state = 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 );
+ CRC32_update_buf( &e->crc, Mf_ptr_to_current_pos( e->matchfinder ) - ahead, len );
+ mtf_reps( dis, e->reps );
bit = ( dis < num_rep_distances );
- Re_encode_bit( &encoder->renc, &encoder->bm_rep[*state], bit );
- if( bit )
+ Re_encode_bit( &e->renc, &e->bm_rep[*state], bit );
+ if( bit ) /* repeated match */
{
bit = ( dis == 0 );
- Re_encode_bit( &encoder->renc, &encoder->bm_rep0[*state], !bit );
+ Re_encode_bit( &e->renc, &e->bm_rep0[*state], !bit );
if( bit )
- Re_encode_bit( &encoder->renc, &encoder->bm_len[*state][pos_state], len > 1 );
+ Re_encode_bit( &e->renc, &e->bm_len[*state][pos_state], len > 1 );
else
{
- Re_encode_bit( &encoder->renc, &encoder->bm_rep1[*state], dis > 1 );
+ Re_encode_bit( &e->renc, &e->bm_rep1[*state], dis > 1 );
if( dis > 1 )
- Re_encode_bit( &encoder->renc, &encoder->bm_rep2[*state], dis > 2 );
+ Re_encode_bit( &e->renc, &e->bm_rep2[*state], dis > 2 );
}
if( len == 1 ) *state = St_set_short_rep( *state );
else
{
- Lee_encode( &encoder->rep_len_encoder, &encoder->renc, len, pos_state );
+ Lee_encode( &e->rep_len_encoder, &e->renc, len, pos_state );
*state = St_set_rep( *state );
}
}
- else
+ else /* match */
{
- LZe_encode_pair( encoder, dis - num_rep_distances, len, pos_state );
- --encoder->fill_counter;
+ LZe_encode_pair( e, dis - num_rep_distances, len, pos_state );
+ --e->fill_counter;
*state = St_set_match( *state );
}
}
ahead -= len; i += len;
- if( Re_member_position( &encoder->renc ) >= encoder->member_size_limit )
+ if( Re_member_position( &e->renc ) >= e->member_size_limit )
{
- if( !Mf_dec_pos( encoder->matchfinder, ahead ) ) return false;
- if( LZe_full_flush( encoder, *state ) ) encoder->member_finished = true;
+ if( !Mf_dec_pos( e->matchfinder, ahead ) ) return false;
+ if( LZe_full_flush( e, *state ) ) e->member_finished = true;
return true;
}
- if( ahead <= 0 ) break;
}
}
- if( LZe_full_flush( encoder, *state ) ) encoder->member_finished = true;
+ if( LZe_full_flush( e, *state ) ) e->member_finished = true;
return true;
}