1 /* Lzlib - Compression library for the lzip format
2    Copyright (C) 2009-2021 Antonio Diaz Diaz.
3 
4    This library is free software. Redistribution and use in source and
5    binary forms, with or without modification, are permitted provided
6    that the following conditions are met:
7 
8    1. Redistributions of source code must retain the above copyright
9    notice, this list of conditions, and the following disclaimer.
10 
11    2. Redistributions in binary form must reproduce the above copyright
12    notice, this list of conditions, and the following disclaimer in the
13    documentation and/or other materials provided with the distribution.
14 
15    This library is distributed in the hope that it will be useful,
16    but WITHOUT ANY WARRANTY; without even the implied warranty of
17    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
18 */
19 
LZe_get_match_pairs(struct LZ_encoder * const e,struct Pair * pairs)20 static int LZe_get_match_pairs( struct LZ_encoder * const e, struct Pair * pairs )
21   {
22   int32_t * ptr0 = e->eb.mb.pos_array + ( e->eb.mb.cyclic_pos << 1 );
23   int32_t * ptr1 = ptr0 + 1;
24   int32_t * newptr;
25   int len = 0, len0 = 0, len1 = 0;
26   int maxlen = 3;			/* only used if pairs != 0 */
27   int num_pairs = 0;
28   const int pos1 = e->eb.mb.pos + 1;
29   const int min_pos = ( e->eb.mb.pos > e->eb.mb.dictionary_size ) ?
30                         e->eb.mb.pos - e->eb.mb.dictionary_size : 0;
31   const uint8_t * const data = Mb_ptr_to_current_pos( &e->eb.mb );
32   int count, key2, key3, key4, newpos1;
33   unsigned tmp;
34   int len_limit = e->match_len_limit;
35 
36   if( len_limit > Mb_available_bytes( &e->eb.mb ) )
37     {
38     e->been_flushed = true;
39     len_limit = Mb_available_bytes( &e->eb.mb );
40     if( len_limit < 4 ) { *ptr0 = *ptr1 = 0; return 0; }
41     }
42 
43   tmp = crc32[data[0]] ^ data[1];
44   key2 = tmp & ( num_prev_positions2 - 1 );
45   tmp ^= (unsigned)data[2] << 8;
46   key3 = num_prev_positions2 + ( tmp & ( num_prev_positions3 - 1 ) );
47   key4 = num_prev_positions2 + num_prev_positions3 +
48          ( ( tmp ^ ( crc32[data[3]] << 5 ) ) & e->eb.mb.key4_mask );
49 
50   if( pairs )
51     {
52     const int np2 = e->eb.mb.prev_positions[key2];
53     const int np3 = e->eb.mb.prev_positions[key3];
54     if( np2 > min_pos && e->eb.mb.buffer[np2-1] == data[0] )
55       {
56       pairs[0].dis = e->eb.mb.pos - np2;
57       pairs[0].len = maxlen = 2;
58       num_pairs = 1;
59       }
60     if( np2 != np3 && np3 > min_pos && e->eb.mb.buffer[np3-1] == data[0] )
61       {
62       maxlen = 3;
63       pairs[num_pairs++].dis = e->eb.mb.pos - np3;
64       }
65     if( num_pairs > 0 )
66       {
67       const int delta = pairs[num_pairs-1].dis + 1;
68       while( maxlen < len_limit && data[maxlen-delta] == data[maxlen] )
69         ++maxlen;
70       pairs[num_pairs-1].len = maxlen;
71       if( maxlen < 3 ) maxlen = 3;
72       if( maxlen >= len_limit ) pairs = 0;	/* done. now just skip */
73       }
74     }
75 
76   e->eb.mb.prev_positions[key2] = pos1;
77   e->eb.mb.prev_positions[key3] = pos1;
78   newpos1 = e->eb.mb.prev_positions[key4];
79   e->eb.mb.prev_positions[key4] = pos1;
80 
81   for( count = e->cycles; ; )
82     {
83     int delta;
84     if( newpos1 <= min_pos || --count < 0 ) { *ptr0 = *ptr1 = 0; break; }
85 
86     if( e->been_flushed ) len = 0;
87     delta = pos1 - newpos1;
88     newptr = e->eb.mb.pos_array +
89       ( ( e->eb.mb.cyclic_pos - delta +
90           ( (e->eb.mb.cyclic_pos >= delta) ? 0 : e->eb.mb.dictionary_size + 1 ) ) << 1 );
91     if( data[len-delta] == data[len] )
92       {
93       while( ++len < len_limit && data[len-delta] == data[len] ) {}
94       if( pairs && maxlen < len )
95         {
96         pairs[num_pairs].dis = delta - 1;
97         pairs[num_pairs].len = maxlen = len;
98         ++num_pairs;
99         }
100       if( len >= len_limit )
101         {
102         *ptr0 = newptr[0];
103         *ptr1 = newptr[1];
104         break;
105         }
106       }
107     if( data[len-delta] < data[len] )
108       {
109       *ptr0 = newpos1;
110       ptr0 = newptr + 1;
111       newpos1 = *ptr0;
112       len0 = len; if( len1 < len ) len = len1;
113       }
114     else
115       {
116       *ptr1 = newpos1;
117       ptr1 = newptr;
118       newpos1 = *ptr1;
119       len1 = len; if( len0 < len ) len = len0;
120       }
121     }
122   return num_pairs;
123   }
124 
125 
LZe_update_distance_prices(struct LZ_encoder * const e)126 static void LZe_update_distance_prices( struct LZ_encoder * const e )
127   {
128   int dis, len_state;
129   for( dis = start_dis_model; dis < modeled_distances; ++dis )
130     {
131     const int dis_slot = dis_slots[dis];
132     const int direct_bits = ( dis_slot >> 1 ) - 1;
133     const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
134     const int price = price_symbol_reversed( e->eb.bm_dis + ( base - dis_slot ),
135                                              dis - base, direct_bits );
136     for( len_state = 0; len_state < len_states; ++len_state )
137       e->dis_prices[len_state][dis] = price;
138     }
139 
140   for( len_state = 0; len_state < len_states; ++len_state )
141     {
142     int * const dsp = e->dis_slot_prices[len_state];
143     int * const dp = e->dis_prices[len_state];
144     const Bit_model * const bmds = e->eb.bm_dis_slot[len_state];
145     int slot = 0;
146     for( ; slot < end_dis_model; ++slot )
147       dsp[slot] = price_symbol6( bmds, slot );
148     for( ; slot < e->num_dis_slots; ++slot )
149       dsp[slot] = price_symbol6( bmds, slot ) +
150                   (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift_bits );
151 
152     for( dis = 0; dis < start_dis_model; ++dis )
153       dp[dis] = dsp[dis];
154     for( ; dis < modeled_distances; ++dis )
155       dp[dis] += dsp[dis_slots[dis]];
156     }
157   }
158 
159 
160 /* Returns the number of bytes advanced (ahead).
161    trials[0]..trials[ahead-1] contain the steps to encode.
162    ( trials[0].dis4 == -1 ) means literal.
163    A match/rep longer or equal than match_len_limit finishes the sequence.
164 */
LZe_sequence_optimizer(struct LZ_encoder * const e,const int reps[num_rep_distances],const State state)165 static int LZe_sequence_optimizer( struct LZ_encoder * const e,
166                                    const int reps[num_rep_distances],
167                                    const State state )
168   {
169   int main_len, num_pairs, i, rep, num_trials, len;
170   int rep_index = 0, cur = 0;
171   int replens[num_rep_distances];
172 
173   if( e->pending_num_pairs > 0 )		/* from previous call */
174     {
175     num_pairs = e->pending_num_pairs;
176     e->pending_num_pairs = 0;
177     }
178   else
179     num_pairs = LZe_read_match_distances( e );
180   main_len = ( num_pairs > 0 ) ? e->pairs[num_pairs-1].len : 0;
181 
182   for( i = 0; i < num_rep_distances; ++i )
183     {
184     replens[i] = Mb_true_match_len( &e->eb.mb, 0, reps[i] + 1 );
185     if( replens[i] > replens[rep_index] ) rep_index = i;
186     }
187   if( replens[rep_index] >= e->match_len_limit )
188     {
189     e->trials[0].price = replens[rep_index];
190     e->trials[0].dis4 = rep_index;
191     if( !LZe_move_and_update( e, replens[rep_index] ) ) return 0;
192     return replens[rep_index];
193     }
194 
195   if( main_len >= e->match_len_limit )
196     {
197     e->trials[0].price = main_len;
198     e->trials[0].dis4 = e->pairs[num_pairs-1].dis + num_rep_distances;
199     if( !LZe_move_and_update( e, main_len ) ) return 0;
200     return main_len;
201     }
202 
203   {
204   const int pos_state = Mb_data_position( &e->eb.mb ) & pos_state_mask;
205   const int match_price = price1( e->eb.bm_match[state][pos_state] );
206   const int rep_match_price = match_price + price1( e->eb.bm_rep[state] );
207   const uint8_t prev_byte = Mb_peek( &e->eb.mb, 1 );
208   const uint8_t cur_byte = Mb_peek( &e->eb.mb, 0 );
209   const uint8_t match_byte = Mb_peek( &e->eb.mb, reps[0] + 1 );
210 
211   e->trials[1].price = price0( e->eb.bm_match[state][pos_state] );
212   if( St_is_char( state ) )
213     e->trials[1].price += LZeb_price_literal( &e->eb, prev_byte, cur_byte );
214   else
215     e->trials[1].price += LZeb_price_matched( &e->eb, prev_byte, cur_byte, match_byte );
216   e->trials[1].dis4 = -1;				/* literal */
217 
218   if( match_byte == cur_byte )
219     Tr_update( &e->trials[1], rep_match_price +
220                LZeb_price_shortrep( &e->eb, state, pos_state ), 0, 0 );
221 
222   num_trials = max( main_len, replens[rep_index] );
223 
224   if( num_trials < min_match_len )
225     {
226     e->trials[0].price = 1;
227     e->trials[0].dis4 = e->trials[1].dis4;
228     if( !Mb_move_pos( &e->eb.mb ) ) return 0;
229     return 1;
230     }
231 
232   e->trials[0].state = state;
233   for( i = 0; i < num_rep_distances; ++i )
234     e->trials[0].reps[i] = reps[i];
235 
236   for( len = min_match_len; len <= num_trials; ++len )
237     e->trials[len].price = infinite_price;
238 
239   for( rep = 0; rep < num_rep_distances; ++rep )
240     {
241     int price;
242     if( replens[rep] < min_match_len ) continue;
243     price = rep_match_price + LZeb_price_rep( &e->eb, rep, state, pos_state );
244     for( len = min_match_len; len <= replens[rep]; ++len )
245       Tr_update( &e->trials[len], price +
246                  Lp_price( &e->rep_len_prices, len, pos_state ), rep, 0 );
247     }
248 
249   if( main_len > replens[0] )
250     {
251     const int normal_match_price = match_price + price0( e->eb.bm_rep[state] );
252     int i = 0, len = max( replens[0] + 1, min_match_len );
253     while( len > e->pairs[i].len ) ++i;
254     while( true )
255       {
256       const int dis = e->pairs[i].dis;
257       Tr_update( &e->trials[len], normal_match_price +
258                  LZe_price_pair( e, dis, len, pos_state ),
259                  dis + num_rep_distances, 0 );
260       if( ++len > e->pairs[i].len && ++i >= num_pairs ) break;
261       }
262     }
263   }
264 
265   while( true )				/* price optimization loop */
266     {
267     struct Trial *cur_trial, *next_trial;
268     int newlen, pos_state, triable_bytes, len_limit;
269     int start_len = min_match_len;
270     int next_price, match_price, rep_match_price;
271     State cur_state;
272     uint8_t prev_byte, cur_byte, match_byte;
273 
274     if( !Mb_move_pos( &e->eb.mb ) ) return 0;
275     if( ++cur >= num_trials )		/* no more initialized trials */
276       {
277       LZe_backward( e, cur );
278       return cur;
279       }
280 
281     num_pairs = LZe_read_match_distances( e );
282     newlen = ( num_pairs > 0 ) ? e->pairs[num_pairs-1].len : 0;
283     if( newlen >= e->match_len_limit )
284       {
285       e->pending_num_pairs = num_pairs;
286       LZe_backward( e, cur );
287       return cur;
288       }
289 
290     /* give final values to current trial */
291     cur_trial = &e->trials[cur];
292     {
293     const int dis4 = cur_trial->dis4;
294     int prev_index = cur_trial->prev_index;
295     const int prev_index2 = cur_trial->prev_index2;
296 
297     if( prev_index2 == single_step_trial )
298       {
299       cur_state = e->trials[prev_index].state;
300       if( prev_index + 1 == cur )			/* len == 1 */
301         {
302         if( dis4 == 0 ) cur_state = St_set_short_rep( cur_state );
303         else cur_state = St_set_char( cur_state );	/* literal */
304         }
305       else if( dis4 < num_rep_distances ) cur_state = St_set_rep( cur_state );
306       else cur_state = St_set_match( cur_state );
307       }
308     else
309       {
310       if( prev_index2 == dual_step_trial )	/* dis4 == 0 (rep0) */
311         --prev_index;
312       else					/* prev_index2 >= 0 */
313         prev_index = prev_index2;
314       cur_state = St_set_char_rep();
315       }
316     cur_trial->state = cur_state;
317     for( i = 0; i < num_rep_distances; ++i )
318       cur_trial->reps[i] = e->trials[prev_index].reps[i];
319     mtf_reps( dis4, cur_trial->reps );		/* literal is ignored */
320     }
321 
322     pos_state = Mb_data_position( &e->eb.mb ) & pos_state_mask;
323     prev_byte = Mb_peek( &e->eb.mb, 1 );
324     cur_byte = Mb_peek( &e->eb.mb, 0 );
325     match_byte = Mb_peek( &e->eb.mb, cur_trial->reps[0] + 1 );
326 
327     next_price = cur_trial->price +
328                  price0( e->eb.bm_match[cur_state][pos_state] );
329     if( St_is_char( cur_state ) )
330       next_price += LZeb_price_literal( &e->eb, prev_byte, cur_byte );
331     else
332       next_price += LZeb_price_matched( &e->eb, prev_byte, cur_byte, match_byte );
333 
334     /* try last updates to next trial */
335     next_trial = &e->trials[cur+1];
336 
337     Tr_update( next_trial, next_price, -1, cur );	/* literal */
338 
339     match_price = cur_trial->price + price1( e->eb.bm_match[cur_state][pos_state] );
340     rep_match_price = match_price + price1( e->eb.bm_rep[cur_state] );
341 
342     if( match_byte == cur_byte && next_trial->dis4 != 0 &&
343         next_trial->prev_index2 == single_step_trial )
344       {
345       const int price = rep_match_price +
346                         LZeb_price_shortrep( &e->eb, cur_state, pos_state );
347       if( price <= next_trial->price )
348         {
349         next_trial->price = price;
350         next_trial->dis4 = 0;				/* rep0 */
351         next_trial->prev_index = cur;
352         }
353       }
354 
355     triable_bytes =
356       min( Mb_available_bytes( &e->eb.mb ), max_num_trials - 1 - cur );
357     if( triable_bytes < min_match_len ) continue;
358 
359     len_limit = min( e->match_len_limit, triable_bytes );
360 
361     /* try literal + rep0 */
362     if( match_byte != cur_byte && next_trial->prev_index != cur )
363       {
364       const uint8_t * const data = Mb_ptr_to_current_pos( &e->eb.mb );
365       const int dis = cur_trial->reps[0] + 1;
366       const int limit = min( e->match_len_limit + 1, triable_bytes );
367       int len = 1;
368       while( len < limit && data[len-dis] == data[len] ) ++len;
369       if( --len >= min_match_len )
370         {
371         const int pos_state2 = ( pos_state + 1 ) & pos_state_mask;
372         const State state2 = St_set_char( cur_state );
373         const int price = next_price +
374                           price1( e->eb.bm_match[state2][pos_state2] ) +
375                           price1( e->eb.bm_rep[state2] ) +
376                           LZe_price_rep0_len( e, len, state2, pos_state2 );
377         while( num_trials < cur + 1 + len )
378           e->trials[++num_trials].price = infinite_price;
379         Tr_update2( &e->trials[cur+1+len], price, cur + 1 );
380         }
381       }
382 
383     /* try rep distances */
384     for( rep = 0; rep < num_rep_distances; ++rep )
385       {
386       const uint8_t * const data = Mb_ptr_to_current_pos( &e->eb.mb );
387       const int dis = cur_trial->reps[rep] + 1;
388       int price;
389 
390       if( data[0-dis] != data[0] || data[1-dis] != data[1] ) continue;
391       for( len = min_match_len; len < len_limit; ++len )
392         if( data[len-dis] != data[len] ) break;
393       while( num_trials < cur + len )
394         e->trials[++num_trials].price = infinite_price;
395       price = rep_match_price + LZeb_price_rep( &e->eb, rep, cur_state, pos_state );
396       for( i = min_match_len; i <= len; ++i )
397         Tr_update( &e->trials[cur+i], price +
398                    Lp_price( &e->rep_len_prices, i, pos_state ), rep, cur );
399 
400       if( rep == 0 ) start_len = len + 1;	/* discard shorter matches */
401 
402       /* try rep + literal + rep0 */
403       {
404       int len2 = len + 1;
405       const int limit = min( e->match_len_limit + len2, triable_bytes );
406       int pos_state2;
407       State state2;
408       while( len2 < limit && data[len2-dis] == data[len2] ) ++len2;
409       len2 -= len + 1;
410       if( len2 < min_match_len ) continue;
411 
412       pos_state2 = ( pos_state + len ) & pos_state_mask;
413       state2 = St_set_rep( cur_state );
414       price += Lp_price( &e->rep_len_prices, len, pos_state ) +
415                price0( e->eb.bm_match[state2][pos_state2] ) +
416                LZeb_price_matched( &e->eb, data[len-1], data[len], data[len-dis] );
417       pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
418       state2 = St_set_char( state2 );
419       price += price1( e->eb.bm_match[state2][pos_state2] ) +
420                price1( e->eb.bm_rep[state2] ) +
421                LZe_price_rep0_len( e, len2, state2, pos_state2 );
422       while( num_trials < cur + len + 1 + len2 )
423         e->trials[++num_trials].price = infinite_price;
424       Tr_update3( &e->trials[cur+len+1+len2], price, rep, cur + len + 1, cur );
425       }
426       }
427 
428     /* try matches */
429     if( newlen >= start_len && newlen <= len_limit )
430       {
431       int dis;
432       const int normal_match_price = match_price +
433                                      price0( e->eb.bm_rep[cur_state] );
434 
435       while( num_trials < cur + newlen )
436         e->trials[++num_trials].price = infinite_price;
437 
438       i = 0;
439       while( e->pairs[i].len < start_len ) ++i;
440       dis = e->pairs[i].dis;
441       for( len = start_len; ; ++len )
442         {
443         int price = normal_match_price + LZe_price_pair( e, dis, len, pos_state );
444         Tr_update( &e->trials[cur+len], price, dis + num_rep_distances, cur );
445 
446         /* try match + literal + rep0 */
447         if( len == e->pairs[i].len )
448           {
449           const uint8_t * const data = Mb_ptr_to_current_pos( &e->eb.mb );
450           const int dis2 = dis + 1;
451           int len2 = len + 1;
452           const int limit = min( e->match_len_limit + len2, triable_bytes );
453           while( len2 < limit && data[len2-dis2] == data[len2] ) ++len2;
454           len2 -= len + 1;
455           if( len2 >= min_match_len )
456             {
457             int pos_state2 = ( pos_state + len ) & pos_state_mask;
458             State state2 = St_set_match( cur_state );
459             price += price0( e->eb.bm_match[state2][pos_state2] ) +
460                      LZeb_price_matched( &e->eb, data[len-1], data[len], data[len-dis2] );
461             pos_state2 = ( pos_state2 + 1 ) & pos_state_mask;
462             state2 = St_set_char( state2 );
463             price += price1( e->eb.bm_match[state2][pos_state2] ) +
464                      price1( e->eb.bm_rep[state2] ) +
465                      LZe_price_rep0_len( e, len2, state2, pos_state2 );
466 
467             while( num_trials < cur + len + 1 + len2 )
468               e->trials[++num_trials].price = infinite_price;
469             Tr_update3( &e->trials[cur+len+1+len2], price,
470                         dis + num_rep_distances, cur + len + 1, cur );
471             }
472           if( ++i >= num_pairs ) break;
473           dis = e->pairs[i].dis;
474           }
475         }
476       }
477     }
478   }
479 
480 
LZe_encode_member(struct LZ_encoder * const e)481 static bool LZe_encode_member( struct LZ_encoder * const e )
482   {
483   const bool best = ( e->match_len_limit > 12 );
484   const int dis_price_count = best ? 1 : 512;
485   const int align_price_count = best ? 1 : dis_align_size;
486   const int price_count = ( e->match_len_limit > 36 ) ? 1013 : 4093;
487   int ahead, i;
488   State * const state = &e->eb.state;
489 
490   if( e->eb.member_finished ) return true;
491   if( Re_member_position( &e->eb.renc ) >= e->eb.member_size_limit )
492     { LZeb_try_full_flush( &e->eb ); return true; }
493 
494   if( Mb_data_position( &e->eb.mb ) == 0 &&
495       !Mb_data_finished( &e->eb.mb ) )		/* encode first byte */
496     {
497     const uint8_t prev_byte = 0;
498     uint8_t cur_byte;
499     if( !Mb_enough_available_bytes( &e->eb.mb ) ||
500         !Re_enough_free_bytes( &e->eb.renc ) ) return true;
501     cur_byte = Mb_peek( &e->eb.mb, 0 );
502     Re_encode_bit( &e->eb.renc, &e->eb.bm_match[*state][0], 0 );
503     LZeb_encode_literal( &e->eb, prev_byte, cur_byte );
504     CRC32_update_byte( &e->eb.crc, cur_byte );
505     LZe_get_match_pairs( e, 0 );
506     if( !Mb_move_pos( &e->eb.mb ) ) return false;
507     }
508 
509   while( !Mb_data_finished( &e->eb.mb ) )
510     {
511     if( !Mb_enough_available_bytes( &e->eb.mb ) ||
512         !Re_enough_free_bytes( &e->eb.renc ) ) return true;
513     if( e->price_counter <= 0 && e->pending_num_pairs == 0 )
514       {
515       e->price_counter = price_count;	/* recalculate prices every these bytes */
516       if( e->dis_price_counter <= 0 )
517         { e->dis_price_counter = dis_price_count; LZe_update_distance_prices( e ); }
518       if( e->align_price_counter <= 0 )
519         {
520         e->align_price_counter = align_price_count;
521         for( i = 0; i < dis_align_size; ++i )
522           e->align_prices[i] = price_symbol_reversed( e->eb.bm_align, i, dis_align_bits );
523         }
524       Lp_update_prices( &e->match_len_prices );
525       Lp_update_prices( &e->rep_len_prices );
526       }
527 
528     ahead = LZe_sequence_optimizer( e, e->eb.reps, *state );
529     e->price_counter -= ahead;
530 
531     for( i = 0; ahead > 0; )
532       {
533       const int pos_state =
534         ( Mb_data_position( &e->eb.mb ) - ahead ) & pos_state_mask;
535       const int len = e->trials[i].price;
536       int dis = e->trials[i].dis4;
537 
538       bool bit = ( dis < 0 );
539       Re_encode_bit( &e->eb.renc, &e->eb.bm_match[*state][pos_state], !bit );
540       if( bit )					/* literal byte */
541         {
542         const uint8_t prev_byte = Mb_peek( &e->eb.mb, ahead + 1 );
543         const uint8_t cur_byte = Mb_peek( &e->eb.mb, ahead );
544         CRC32_update_byte( &e->eb.crc, cur_byte );
545         if( St_is_char( *state ) )
546           LZeb_encode_literal( &e->eb, prev_byte, cur_byte );
547         else
548           {
549           const uint8_t match_byte = Mb_peek( &e->eb.mb, ahead + e->eb.reps[0] + 1 );
550           LZeb_encode_matched( &e->eb, prev_byte, cur_byte, match_byte );
551           }
552         *state = St_set_char( *state );
553         }
554       else					/* match or repeated match */
555         {
556         CRC32_update_buf( &e->eb.crc, Mb_ptr_to_current_pos( &e->eb.mb ) - ahead, len );
557         mtf_reps( dis, e->eb.reps );
558         bit = ( dis < num_rep_distances );
559         Re_encode_bit( &e->eb.renc, &e->eb.bm_rep[*state], bit );
560         if( bit )				/* repeated match */
561           {
562           bit = ( dis == 0 );
563           Re_encode_bit( &e->eb.renc, &e->eb.bm_rep0[*state], !bit );
564           if( bit )
565             Re_encode_bit( &e->eb.renc, &e->eb.bm_len[*state][pos_state], len > 1 );
566           else
567             {
568             Re_encode_bit( &e->eb.renc, &e->eb.bm_rep1[*state], dis > 1 );
569             if( dis > 1 )
570               Re_encode_bit( &e->eb.renc, &e->eb.bm_rep2[*state], dis > 2 );
571             }
572           if( len == 1 ) *state = St_set_short_rep( *state );
573           else
574             {
575             Re_encode_len( &e->eb.renc, &e->eb.rep_len_model, len, pos_state );
576             Lp_decrement_counter( &e->rep_len_prices, pos_state );
577             *state = St_set_rep( *state );
578             }
579           }
580         else					/* match */
581           {
582           dis -= num_rep_distances;
583           LZeb_encode_pair( &e->eb, dis, len, pos_state );
584           if( dis >= modeled_distances ) --e->align_price_counter;
585           --e->dis_price_counter;
586           Lp_decrement_counter( &e->match_len_prices, pos_state );
587           *state = St_set_match( *state );
588           }
589         }
590       ahead -= len; i += len;
591       if( Re_member_position( &e->eb.renc ) >= e->eb.member_size_limit )
592         {
593         if( !Mb_dec_pos( &e->eb.mb, ahead ) ) return false;
594         LZeb_try_full_flush( &e->eb );
595         return true;
596         }
597       }
598     }
599   LZeb_try_full_flush( &e->eb );
600   return true;
601   }
602