← Back to branch summary

~ubuntu-branches/ubuntu/vivid/emscripten/vivid

« back to all changes in this revision

Viewing changes to third_party/lzma.js/lzip/encoder.cc

  • Committer: Package Import Robot
  • Author(s): Sylvestre Ledru
  • Date: 2013-05-02 13:11:51 UTC
  • Revision ID: package-import@ubuntu.com-20130502131151-q8dvteqr1ef2x7xz
Tags: upstream-1.4.1~20130504~adb56cb
Import upstream version 1.4.1~20130504~adb56cb

Show diffs side-by-side

added added

removed removed

Lines of Context:
third_party/lzma.js/lzip/encoder.cc
 
1
#if !DECODER_ONLY
 
2
 
 
3
/*  Lzip - Data compressor based on the LZMA algorithm
 
4
    Copyright (C) 2008, 2009, 2010, 2011 Antonio Diaz Diaz.
 
5
 
 
6
    This program is free software: you can redistribute it and/or modify
 
7
    it under the terms of the GNU General Public License as published by
 
8
    the Free Software Foundation, either version 3 of the License, or
 
9
    (at your option) any later version.
 
10
 
 
11
    This program is distributed in the hope that it will be useful,
 
12
    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
13
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
14
    GNU General Public License for more details.
 
15
 
 
16
    You should have received a copy of the GNU General Public License
 
17
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
18
*/
 
19
 
 
20
#define _FILE_OFFSET_BITS 64
 
21
 
 
22
#include <errno.h>
 
23
#include <stdlib.h>
 
24
#include <string.h>
 
25
#include <stdint.h>
 
26
 
 
27
#include "lzip.h"
 
28
#include "encoder.h"
 
29
 
 
30
 
 
31
Dis_slots dis_slots;
 
32
Prob_prices prob_prices;
 
33
 
 
34
 
 
35
bool Matchfinder::read_block()
 
36
  {
 
37
  if( !at_stream_end && stream_pos < buffer_size )
 
38
    {
 
39
    const int size = buffer_size - stream_pos;
 
40
    const int rd = readblock( infd, buffer + stream_pos, size );
 
41
    stream_pos += rd;
 
42
    if( rd != size && errno ) throw Error( "Read error" );
 
43
    at_stream_end = ( rd < size );
 
44
    }
 
45
  return pos < stream_pos;
 
46
  }
 
47
 
 
48
 
 
49
Matchfinder::Matchfinder( const int dict_size, const int len_limit,
 
50
                          const int ifd )
 
51
  :
 
52
  partial_data_pos( 0 ),
 
53
  prev_positions( new int32_t[num_prev_positions] ),
 
54
  pos( 0 ),
 
55
  cyclic_pos( 0 ),
 
56
  stream_pos( 0 ),
 
57
  match_len_limit_( len_limit ),
 
58
  cycles( ( len_limit < max_match_len ) ? 16 + ( len_limit / 2 ) : 256 ),
 
59
  infd( ifd ),
 
60
  at_stream_end( false )
 
61
  {
 
62
  const int buffer_size_limit = ( 2 * dict_size ) + before_size + after_size;
 
63
  buffer_size = max( 65536, dict_size );
 
64
  buffer = (uint8_t *)malloc( buffer_size );
 
65
  if( !buffer ) exit(-1);
 
66
  if( read_block() && !at_stream_end && buffer_size < buffer_size_limit )
 
67
    {
 
68
    buffer_size = buffer_size_limit;
 
69
    buffer = (uint8_t *)realloc( buffer, buffer_size );
 
70
    if( !buffer ) exit(-1);
 
71
    read_block();
 
72
    }
 
73
  if( at_stream_end && stream_pos < dict_size )
 
74
    dictionary_size_ = max( (int)min_dictionary_size, stream_pos );
 
75
  else dictionary_size_ = dict_size;
 
76
  pos_limit = buffer_size;
 
77
  if( !at_stream_end ) pos_limit -= after_size;
 
78
  prev_pos_tree = new int32_t[2*dictionary_size_];
 
79
  for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
 
80
  }
 
81
 
 
82
 
 
83
void Matchfinder::reset()
 
84
  {
 
85
  const int size = stream_pos - pos;
 
86
  if( size > 0 ) memmove( buffer, buffer + pos, size );
 
87
  partial_data_pos = 0;
 
88
  stream_pos -= pos;
 
89
  pos = 0;
 
90
  cyclic_pos = 0;
 
91
  for( int i = 0; i < num_prev_positions; ++i ) prev_positions[i] = -1;
 
92
  read_block();
 
93
  }
 
94
 
 
95
 
 
96
void Matchfinder::move_pos()
 
97
  {
 
98
  if( ++cyclic_pos >= dictionary_size_ ) cyclic_pos = 0;
 
99
  if( ++pos >= pos_limit )
 
100
    {
 
101
    if( pos > stream_pos )
 
102
      internal_error( "pos > stream_pos in Matchfinder::move_pos" );
 
103
    if( !at_stream_end )
 
104
      {
 
105
      const int offset = pos - dictionary_size_ - before_size;
 
106
      const int size = stream_pos - offset;
 
107
      memmove( buffer, buffer + offset, size );
 
108
      partial_data_pos += offset;
 
109
      pos -= offset;
 
110
      stream_pos -= offset;
 
111
      for( int i = 0; i < num_prev_positions; ++i )
 
112
        if( prev_positions[i] >= 0 ) prev_positions[i] -= offset;
 
113
      for( int i = 0; i < 2 * dictionary_size_; ++i )
 
114
        if( prev_pos_tree[i] >= 0 ) prev_pos_tree[i] -= offset;
 
115
      read_block();
 
116
      }
 
117
    }
 
118
  }
 
119
 
 
120
 
 
121
int Matchfinder::longest_match_len( int * const distances ) throw()
 
122
  {
 
123
  int len_limit = match_len_limit_;
 
124
  if( len_limit > available_bytes() )
 
125
    {
 
126
    len_limit = available_bytes();
 
127
    if( len_limit < 4 ) return 0;
 
128
    }
 
129
 
 
130
  int maxlen = min_match_len - 1;
 
131
  const int min_pos = (pos >= dictionary_size_) ?
 
132
                      (pos - dictionary_size_ + 1) : 0;
 
133
  const uint8_t * const data = buffer + pos;
 
134
  const int key2 = num_prev_positions4 + num_prev_positions3 +
 
135
                   ( ( (int)data[0] << 8 ) | data[1] );
 
136
  const uint32_t tmp = crc32[data[0]] ^ data[1] ^ ( (uint32_t)data[2] << 8 );
 
137
  const int key3 = num_prev_positions4 +
 
138
                   (int)( tmp & ( num_prev_positions3 - 1 ) );
 
139
  const int key4 = (int)( ( tmp ^ ( crc32[data[3]] << 5 ) ) &
 
140
                          ( num_prev_positions4 - 1 ) );
 
141
 
 
142
  if( distances )
 
143
    {
 
144
    int np = prev_positions[key2];
 
145
    if( np >= min_pos )
 
146
      { distances[2] = pos - np - 1; maxlen = 2; }
 
147
    else distances[2] = 0x7FFFFFFF;
 
148
    np = prev_positions[key3];
 
149
    if( np >= min_pos && buffer[np] == data[0] )
 
150
      { distances[3] = pos - np - 1; maxlen = 3; }
 
151
    else distances[3] = 0x7FFFFFFF;
 
152
    distances[4] = 0x7FFFFFFF;
 
153
    }
 
154
 
 
155
  prev_positions[key2] = pos;
 
156
  prev_positions[key3] = pos;
 
157
  int newpos = prev_positions[key4];
 
158
  prev_positions[key4] = pos;
 
159
 
 
160
  int32_t * ptr0 = prev_pos_tree + ( cyclic_pos << 1 );
 
161
  int32_t * ptr1 = ptr0 + 1;
 
162
  int len = 0, len0 = 0, len1 = 0;
 
163
 
 
164
  for( int count = cycles; ; )
 
165
    {
 
166
    if( newpos < min_pos || --count < 0 ) { *ptr0 = *ptr1 = -1; break; }
 
167
    const uint8_t * const newdata = buffer + newpos;
 
168
    while( len < len_limit && newdata[len] == data[len] ) ++len;
 
169
 
 
170
    const int delta = pos - newpos;
 
171
    if( distances ) while( maxlen < len ) distances[++maxlen] = delta - 1;
 
172
 
 
173
    int32_t * const newptr = prev_pos_tree +
 
174
      ( ( cyclic_pos - delta +
 
175
          ( ( cyclic_pos >= delta ) ? 0 : dictionary_size_ ) ) << 1 );
 
176
 
 
177
    if( len < len_limit )
 
178
      {
 
179
      if( newdata[len] < data[len] )
 
180
        {
 
181
        *ptr0 = newpos;
 
182
        ptr0 = newptr + 1;
 
183
        newpos = *ptr0;
 
184
        len0 = len; if( len1 < len ) len = len1;
 
185
        }
 
186
      else
 
187
        {
 
188
        *ptr1 = newpos;
 
189
        ptr1 = newptr;
 
190
        newpos = *ptr1;
 
191
        len1 = len; if( len0 < len ) len = len0;
 
192
        }
 
193
      }
 
194
    else
 
195
      {
 
196
      *ptr0 = newptr[0];
 
197
      *ptr1 = newptr[1];
 
198
      break;
 
199
      }
 
200
    }
 
201
  if( distances )
 
202
    {
 
203
    if( distances[3] > distances[4] ) distances[3] = distances[4];
 
204
    if( distances[2] > distances[3] ) distances[2] = distances[3];
 
205
    }
 
206
  return maxlen;
 
207
  }
 
208
 
 
209
 
 
210
void Range_encoder::flush_data()
 
211
  {
 
212
  if( pos > 0 )
 
213
    {
 
214
    if( outfd >= 0 && writeblock( outfd, buffer, pos ) != pos )
 
215
      throw Error( "Write error" );
 
216
    partial_member_pos += pos;
 
217
    pos = 0;
 
218
    }
 
219
  }
 
220
 
 
221
 
 
222
void Len_encoder::encode( Range_encoder & range_encoder, int symbol,
 
223
                          const int pos_state )
 
224
  {
 
225
  symbol -= min_match_len;
 
226
  if( symbol < len_low_symbols )
 
227
    {
 
228
    range_encoder.encode_bit( choice1, 0 );
 
229
    range_encoder.encode_tree( bm_low[pos_state], symbol, len_low_bits );
 
230
    }
 
231
  else
 
232
    {
 
233
    range_encoder.encode_bit( choice1, 1 );
 
234
    if( symbol < len_low_symbols + len_mid_symbols )
 
235
      {
 
236
      range_encoder.encode_bit( choice2, 0 );
 
237
      range_encoder.encode_tree( bm_mid[pos_state], symbol - len_low_symbols, len_mid_bits );
 
238
      }
 
239
    else
 
240
      {
 
241
      range_encoder.encode_bit( choice2, 1 );
 
242
      range_encoder.encode_tree( bm_high, symbol - len_low_symbols - len_mid_symbols, len_high_bits );
 
243
      }
 
244
    }
 
245
  if( --counters[pos_state] <= 0 ) update_prices( pos_state );
 
246
  }
 
247
 
 
248
 
 
249
void LZ_encoder::fill_align_prices() throw()
 
250
  {
 
251
  for( int i = 0; i < dis_align_size; ++i )
 
252
    align_prices[i] = price_symbol_reversed( bm_align, i, dis_align_bits );
 
253
  align_price_count = dis_align_size;
 
254
  }
 
255
 
 
256
 
 
257
void LZ_encoder::fill_distance_prices() throw()
 
258
  {
 
259
  for( int dis = start_dis_model; dis < modeled_distances; ++dis )
 
260
    {
 
261
    const int dis_slot = dis_slots.table( dis );
 
262
    const int direct_bits = ( dis_slot >> 1 ) - 1;
 
263
    const int base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
 
264
    const int price =
 
265
      price_symbol_reversed( bm_dis + base - dis_slot, dis - base, direct_bits );
 
266
    for( int dis_state = 0; dis_state < max_dis_states; ++dis_state )
 
267
      dis_prices[dis_state][dis] = price;
 
268
    }
 
269
 
 
270
  for( int dis_state = 0; dis_state < max_dis_states; ++dis_state )
 
271
    {
 
272
    int * const dsp = dis_slot_prices[dis_state];
 
273
    const Bit_model * const bmds = bm_dis_slot[dis_state];
 
274
    int slot = 0;
 
275
    for( ; slot < end_dis_model && slot < num_dis_slots; ++slot )
 
276
      dsp[slot] = price_symbol( bmds, slot, dis_slot_bits );
 
277
    for( ; slot < num_dis_slots; ++slot )
 
278
      dsp[slot] = price_symbol( bmds, slot, dis_slot_bits ) +
 
279
                  (((( slot >> 1 ) - 1 ) - dis_align_bits ) << price_shift );
 
280
 
 
281
    int * const dp = dis_prices[dis_state];
 
282
    int dis = 0;
 
283
    for( ; dis < start_dis_model; ++dis )
 
284
      dp[dis] = dsp[dis];
 
285
    for( ; dis < modeled_distances; ++dis )
 
286
      dp[dis] += dsp[dis_slots.table( dis )];
 
287
    }
 
288
  }
 
289
 
 
290
 
 
291
// Return value == number of bytes advanced (ahead).
 
292
// trials[0]..trials[retval-1] contain the steps to encode.
 
293
// ( trials[0].dis == -1 && trials[0].price == 1 ) means literal.
 
294
int LZ_encoder::sequence_optimizer( const int reps[num_rep_distances],
 
295
                                    const State & state )
 
296
  {
 
297
  int main_len;
 
298
  if( longest_match_found > 0 )         // from previous call
 
299
    {
 
300
    main_len = longest_match_found;
 
301
    longest_match_found = 0;
 
302
    }
 
303
  else main_len = read_match_distances();
 
304
 
 
305
  int replens[num_rep_distances];
 
306
  int rep_index = 0;
 
307
  for( int i = 0; i < num_rep_distances; ++i )
 
308
    {
 
309
    replens[i] = matchfinder.true_match_len( 0, reps[i] + 1, max_match_len );
 
310
    if( replens[i] > replens[rep_index] ) rep_index = i;
 
311
    }
 
312
  if( replens[rep_index] >= matchfinder.match_len_limit() )
 
313
    {
 
314
    trials[0].dis = rep_index;
 
315
    trials[0].price = replens[rep_index];
 
316
    move_pos( replens[rep_index], true );
 
317
    return replens[rep_index];
 
318
    }
 
319
 
 
320
  if( main_len >= matchfinder.match_len_limit() )
 
321
    {
 
322
    trials[0].dis = match_distances[matchfinder.match_len_limit()] +
 
323
                    num_rep_distances;
 
324
    trials[0].price = main_len;
 
325
    move_pos( main_len, true );
 
326
    return main_len;
 
327
    }
 
328
 
 
329
  {
 
330
  const int pos_state = matchfinder.data_position() & pos_state_mask;
 
331
  const uint8_t prev_byte = matchfinder[-1];
 
332
  const uint8_t cur_byte = matchfinder[0];
 
333
  const uint8_t match_byte = matchfinder[-reps[0]-1];
 
334
 
 
335
  trials[0].state = state;
 
336
  for( int i = 0; i < num_rep_distances; ++i ) trials[0].reps[i] = reps[i];
 
337
  trials[1].dis = -1;
 
338
  trials[1].prev_index = 0;
 
339
  trials[1].price = price0( bm_match[state()][pos_state] );
 
340
  if( state.is_char() )
 
341
    trials[1].price += literal_encoder.price_symbol( prev_byte, cur_byte );
 
342
  else
 
343
    trials[1].price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte );
 
344
 
 
345
  const int match_price = price1( bm_match[state()][pos_state] );
 
346
  const int rep_match_price = match_price + price1( bm_rep[state()] );
 
347
 
 
348
  if( match_byte == cur_byte )
 
349
    trials[1].update( 0, 0, rep_match_price + price_rep_len1( state, pos_state ) );
 
350
 
 
351
  if( main_len < min_match_len )
 
352
    {
 
353
    trials[0].dis = trials[1].dis;
 
354
    trials[0].price = 1;
 
355
    matchfinder.move_pos();
 
356
    return 1;
 
357
    }
 
358
 
 
359
  if( main_len <= replens[rep_index] )
 
360
    {
 
361
    main_len = replens[rep_index];
 
362
    for( int len = min_match_len; len <= main_len; ++len )
 
363
      trials[len].price = infinite_price;
 
364
    }
 
365
  else
 
366
    {
 
367
    const int normal_match_price = match_price + price0( bm_rep[state()] );
 
368
    for( int len = min_match_len; len <= main_len; ++len )
 
369
      {
 
370
      trials[len].dis = match_distances[len] + num_rep_distances;
 
371
      trials[len].prev_index = 0;
 
372
      trials[len].price = normal_match_price +
 
373
                          price_pair( match_distances[len], len, pos_state );
 
374
      }
 
375
    }
 
376
 
 
377
  for( int rep = 0; rep < num_rep_distances; ++rep )
 
378
    {
 
379
    const int price = rep_match_price +
 
380
                      price_rep( rep, state, pos_state );
 
381
    for( int len = min_match_len; len <= replens[rep]; ++len )
 
382
      trials[len].update( rep, 0, price +
 
383
                                  rep_match_len_encoder.price( len, pos_state ) );
 
384
    }
 
385
  }
 
386
 
 
387
  int cur = 0;
 
388
  int num_trials = main_len;
 
389
  matchfinder.move_pos();
 
390
 
 
391
  while( true )
 
392
    {
 
393
    if( ++cur >= num_trials )           // no more initialized trials
 
394
      {
 
395
      backward( cur );
 
396
      return cur;
 
397
      }
 
398
    const int newlen = read_match_distances();
 
399
    if( newlen >= matchfinder.match_len_limit() )
 
400
      {
 
401
      longest_match_found = newlen;
 
402
      backward( cur );
 
403
      return cur;
 
404
      }
 
405
 
 
406
    Trial & cur_trial = trials[cur];
 
407
    const int prev_index = cur_trial.prev_index;
 
408
 
 
409
    cur_trial.state = trials[prev_index].state;
 
410
 
 
411
    for( int i = 0; i < num_rep_distances; ++i )
 
412
      cur_trial.reps[i] = trials[prev_index].reps[i];
 
413
    if( prev_index == cur - 1 )
 
414
      {
 
415
      if( cur_trial.dis == 0 ) cur_trial.state.set_short_rep();
 
416
      else cur_trial.state.set_char();
 
417
      }
 
418
    else
 
419
      {
 
420
      if( cur_trial.dis < num_rep_distances ) cur_trial.state.set_rep();
 
421
      else cur_trial.state.set_match();
 
422
      mtf_reps( cur_trial.dis, cur_trial.reps );
 
423
      }
 
424
 
 
425
    const int pos_state = matchfinder.data_position() & pos_state_mask;
 
426
    const uint8_t prev_byte = matchfinder[-1];
 
427
    const uint8_t cur_byte = matchfinder[0];
 
428
    const uint8_t match_byte = matchfinder[-cur_trial.reps[0]-1];
 
429
 
 
430
    int next_price = cur_trial.price +
 
431
                     price0( bm_match[cur_trial.state()][pos_state] );
 
432
    if( cur_trial.state.is_char() )
 
433
      next_price += literal_encoder.price_symbol( prev_byte, cur_byte );
 
434
    else
 
435
      next_price += literal_encoder.price_matched( prev_byte, cur_byte, match_byte );
 
436
    matchfinder.move_pos();
 
437
 
 
438
    Trial & next_trial = trials[cur+1];
 
439
 
 
440
    next_trial.update( -1, cur, next_price );
 
441
 
 
442
    const int match_price = cur_trial.price + price1( bm_match[cur_trial.state()][pos_state] );
 
443
    const int rep_match_price = match_price + price1( bm_rep[cur_trial.state()] );
 
444
 
 
445
    if( match_byte == cur_byte && next_trial.dis != 0 )
 
446
      next_trial.update( 0, cur, rep_match_price +
 
447
                                 price_rep_len1( cur_trial.state, pos_state ) );
 
448
 
 
449
    const int len_limit = min( min( max_num_trials - 1 - cur,
 
450
              matchfinder.available_bytes() ), matchfinder.match_len_limit() );
 
451
    if( len_limit < min_match_len ) continue;
 
452
 
 
453
    for( int rep = 0; rep < num_rep_distances; ++rep )
 
454
      {
 
455
      const int dis = cur_trial.reps[rep] + 1;
 
456
      int len = 0;
 
457
      const uint8_t * const data = matchfinder.ptr_to_current_pos() - 1;
 
458
      while( len < len_limit && data[len] == data[len-dis] ) ++len;
 
459
      if( len >= min_match_len )
 
460
        {
 
461
        const int price = rep_match_price +
 
462
                          price_rep( rep, cur_trial.state, pos_state );
 
463
        while( num_trials < cur + len )
 
464
          trials[++num_trials].price = infinite_price;
 
465
        for( ; len >= min_match_len; --len )
 
466
          trials[cur+len].update( rep, cur, price +
 
467
                                  rep_match_len_encoder.price( len, pos_state ) );
 
468
        }
 
469
      }
 
470
 
 
471
    if( newlen <= len_limit &&
 
472
        ( newlen > min_match_len ||
 
473
          ( newlen == min_match_len &&
 
474
            match_distances[min_match_len] < modeled_distances ) ) )
 
475
      {
 
476
      const int normal_match_price = match_price +
 
477
                                     price0( bm_rep[cur_trial.state()] );
 
478
      while( num_trials < cur + newlen )
 
479
        trials[++num_trials].price = infinite_price;
 
480
 
 
481
      int dis = match_distances[min_match_len];
 
482
      int dis_state = get_dis_state( min_match_len );
 
483
      int dis_price = infinite_price;
 
484
      if( dis < modeled_distances )
 
485
        trials[cur+min_match_len].update( dis + num_rep_distances, cur,
 
486
                   normal_match_price + dis_prices[dis_state][dis] +
 
487
                   len_encoder.price( min_match_len, pos_state ) );
 
488
      for( int len = min_match_len + 1; len <= newlen; ++len )
 
489
        {
 
490
        if( dis != match_distances[len] || dis_state < max_dis_states - 1 )
 
491
          {
 
492
          dis = match_distances[len];
 
493
          dis_state = get_dis_state( len );
 
494
          dis_price = price_dis( dis, dis_state );
 
495
          }
 
496
        trials[cur+len].update( dis + num_rep_distances, cur,
 
497
                                normal_match_price + dis_price +
 
498
                                len_encoder.price( len, pos_state ) );
 
499
        }
 
500
      }
 
501
    }
 
502
  }
 
503
 
 
504
 
 
505
     // End Of Stream mark => (dis == 0xFFFFFFFFU, len == min_match_len)
 
506
void LZ_encoder::full_flush( const State & state )
 
507
  {
 
508
  const int pos_state = matchfinder.data_position() & pos_state_mask;
 
509
  range_encoder.encode_bit( bm_match[state()][pos_state], 1 );
 
510
  range_encoder.encode_bit( bm_rep[state()], 0 );
 
511
  encode_pair( 0xFFFFFFFFU, min_match_len, pos_state );
 
512
  range_encoder.flush();
 
513
  File_trailer trailer;
 
514
  trailer.data_crc( crc() );
 
515
  trailer.data_size( matchfinder.data_position() );
 
516
  trailer.member_size( range_encoder.member_position() + File_trailer::size() );
 
517
  for( int i = 0; i < File_trailer::size(); ++i )
 
518
    range_encoder.put_byte( trailer.data[i] );
 
519
  range_encoder.flush_data();
 
520
  }
 
521
 
 
522
 
 
523
LZ_encoder::LZ_encoder( Matchfinder & mf, const File_header & header,
 
524
                        const int outfd )
 
525
  :
 
526
  longest_match_found( 0 ),
 
527
  crc_( 0xFFFFFFFFU ),
 
528
  matchfinder( mf ),
 
529
  range_encoder( outfd ),
 
530
  len_encoder( matchfinder.match_len_limit() ),
 
531
  rep_match_len_encoder( matchfinder.match_len_limit() ),
 
532
  num_dis_slots( 2 * real_bits( matchfinder.dictionary_size() - 1 ) )
 
533
  {
 
534
  fill_align_prices();
 
535
 
 
536
  for( int i = 0; i < File_header::size; ++i )
 
537
    range_encoder.put_byte( header.data[i] );
 
538
  }
 
539
 
 
540
 
 
541
bool LZ_encoder::encode_member( const long long member_size )
 
542
  {
 
543
  const long long member_size_limit =
 
544
    member_size - File_trailer::size() - max_marker_size;
 
545
  const int fill_count = ( matchfinder.match_len_limit() > 12 ) ? 512 : 2048;
 
546
  int fill_counter = 0;
 
547
  int rep_distances[num_rep_distances];
 
548
  State state;
 
549
  for( int i = 0; i < num_rep_distances; ++i ) rep_distances[i] = 0;
 
550
 
 
551
  if( matchfinder.data_position() != 0 ||
 
552
      range_encoder.member_position() != File_header::size )
 
553
    return false;                       // can be called only once
 
554
 
 
555
  if( !matchfinder.finished() )         // encode first byte
 
556
    {
 
557
    const uint8_t prev_byte = 0;
 
558
    const uint8_t cur_byte = matchfinder[0];
 
559
    range_encoder.encode_bit( bm_match[state()][0], 0 );
 
560
    literal_encoder.encode( range_encoder, prev_byte, cur_byte );
 
561
    crc32.update( crc_, cur_byte );
 
562
    move_pos( 1 );
 
563
    }
 
564
 
 
565
  while( true )
 
566
    {
 
567
    if( matchfinder.finished() ) { full_flush( state ); return true; }
 
568
    if( fill_counter <= 0 )
 
569
      { fill_distance_prices(); fill_counter = fill_count; }
 
570
 
 
571
    int ahead = sequence_optimizer( rep_distances, state );
 
572
    if( ahead <= 0 ) return false;
 
573
    fill_counter -= ahead;
 
574
 
 
575
    for( int i = 0; ; )
 
576
      {
 
577
      const int pos_state =
 
578
        ( matchfinder.data_position() - ahead ) & pos_state_mask;
 
579
      const int dis = trials[i].dis;
 
580
      const int len = trials[i].price;
 
581
 
 
582
      bool bit = ( dis < 0 && len == 1 );
 
583
      range_encoder.encode_bit( bm_match[state()][pos_state], !bit );
 
584
      if( bit )                         // literal byte
 
585
        {
 
586
        const uint8_t prev_byte = matchfinder[-ahead-1];
 
587
        const uint8_t cur_byte = matchfinder[-ahead];
 
588
        crc32.update( crc_, cur_byte );
 
589
        if( state.is_char() )
 
590
          literal_encoder.encode( range_encoder, prev_byte, cur_byte );
 
591
        else
 
592
          {
 
593
          const uint8_t match_byte = matchfinder[-ahead-rep_distances[0]-1];
 
594
          literal_encoder.encode_matched( range_encoder,
 
595
                                          prev_byte, cur_byte, match_byte );
 
596
          }
 
597
        state.set_char();
 
598
        }
 
599
      else                              // match or repeated match
 
600
        {
 
601
        crc32.update( crc_, matchfinder.ptr_to_current_pos() - ahead, len );
 
602
        mtf_reps( dis, rep_distances );
 
603
        bit = ( dis < num_rep_distances );
 
604
        range_encoder.encode_bit( bm_rep[state()], bit );
 
605
        if( bit )
 
606
          {
 
607
          bit = ( dis == 0 );
 
608
          range_encoder.encode_bit( bm_rep0[state()], !bit );
 
609
          if( bit )
 
610
            range_encoder.encode_bit( bm_len[state()][pos_state], len > 1 );
 
611
          else
 
612
            {
 
613
            range_encoder.encode_bit( bm_rep1[state()], dis > 1 );
 
614
            if( dis > 1 )
 
615
              range_encoder.encode_bit( bm_rep2[state()], dis > 2 );
 
616
            }
 
617
          if( len == 1 ) state.set_short_rep();
 
618
          else
 
619
            {
 
620
            rep_match_len_encoder.encode( range_encoder, len, pos_state );
 
621
            state.set_rep();
 
622
            }
 
623
          }
 
624
        else
 
625
          {
 
626
          encode_pair( dis - num_rep_distances, len, pos_state );
 
627
          state.set_match();
 
628
          }
 
629
        }
 
630
      ahead -= len; i += len;
 
631
      if( range_encoder.member_position() >= member_size_limit )
 
632
        {
 
633
        if( !matchfinder.dec_pos( ahead ) ) return false;
 
634
        full_flush( state );
 
635
        return true;
 
636
        }
 
637
      if( ahead <= 0 ) break;
 
638
      }
 
639
    }
 
640
  }
 
641
 
 
642
#endif
 
643