← 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.h

  • 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.h
 
1
/*  Lzip - Data compressor based on the LZMA algorithm
 
2
    Copyright (C) 2008, 2009, 2010, 2011 Antonio Diaz Diaz.
 
3
 
 
4
    This program is free software: you can redistribute it and/or modify
 
5
    it under the terms of the GNU General Public License as published by
 
6
    the Free Software Foundation, either version 3 of the License, or
 
7
    (at your option) any later version.
 
8
 
 
9
    This program is distributed in the hope that it will be useful,
 
10
    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
11
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
12
    GNU General Public License for more details.
 
13
 
 
14
    You should have received a copy of the GNU General Public License
 
15
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
16
*/
 
17
 
 
18
enum { max_num_trials = 1 << 12,
 
19
       price_shift = 6 };
 
20
 
 
21
class Dis_slots
 
22
  {
 
23
  unsigned char data[1<<12];
 
24
 
 
25
public:
 
26
  void init() throw()
 
27
    {
 
28
    for( int slot = 0; slot < 4; ++slot ) data[slot] = slot;
 
29
    for( int i = 4, size = 2, slot = 4; slot < 24; slot += 2 )
 
30
      {
 
31
      memset( &data[i], slot, size );
 
32
      memset( &data[i+size], slot + 1, size );
 
33
      size <<= 1;
 
34
      i += size;
 
35
      }
 
36
    }
 
37
 
 
38
  unsigned char table( const int dis ) const throw() { return data[dis]; }
 
39
 
 
40
  int operator[]( const uint32_t dis ) const throw()
 
41
    {
 
42
    if( dis < (1 << 12) ) return data[dis];
 
43
    if( dis < (1 << 23) ) return data[dis>>11] + 22;
 
44
    return data[dis>>22] + 44;
 
45
    }
 
46
  };
 
47
 
 
48
extern Dis_slots dis_slots;
 
49
 
 
50
 
 
51
class Prob_prices
 
52
  {
 
53
  int data[bit_model_total >> 2];
 
54
 
 
55
public:
 
56
  void init() throw()
 
57
    {
 
58
    const int num_bits = ( bit_model_total_bits - 2 );
 
59
    int j = 1, end = 2;
 
60
    data[0] = bit_model_total_bits << price_shift;
 
61
    for( int i = num_bits - 1; i >= 0; --i, end <<= 1 )
 
62
      {
 
63
      for( ; j < end; ++j )
 
64
        data[j] = ( i << price_shift ) +
 
65
                  ( ( (end - j) << price_shift ) >> ( num_bits - i - 1 ) );
 
66
      }
 
67
    }
 
68
 
 
69
  int operator[]( const int probability ) const throw()
 
70
    { return data[probability >> 2]; }
 
71
  };
 
72
 
 
73
extern Prob_prices prob_prices;
 
74
 
 
75
 
 
76
inline int price0( const Bit_model & bm ) throw()
 
77
  { return prob_prices[bm.probability]; }
 
78
 
 
79
inline int price1( const Bit_model & bm ) throw()
 
80
  { return prob_prices[bit_model_total-bm.probability]; }
 
81
 
 
82
inline int price_bit( const Bit_model & bm, const int bit ) throw()
 
83
  { if( bit ) return price1( bm ); else return price0( bm ); }
 
84
 
 
85
 
 
86
inline int price_symbol( const Bit_model bm[], int symbol, const int num_bits ) throw()
 
87
  {
 
88
  int price = 0;
 
89
  symbol |= ( 1 << num_bits );
 
90
  while( symbol > 1 )
 
91
    {
 
92
    const int bit = symbol & 1;
 
93
    symbol >>= 1;
 
94
    price += price_bit( bm[symbol], bit );
 
95
    }
 
96
  return price;
 
97
  }
 
98
 
 
99
 
 
100
inline int price_symbol_reversed( const Bit_model bm[], int symbol,
 
101
                                  const int num_bits ) throw()
 
102
  {
 
103
  int price = 0;
 
104
  int model = 1;
 
105
  for( int i = num_bits; i > 0; --i )
 
106
    {
 
107
    const int bit = symbol & 1;
 
108
    symbol >>= 1;
 
109
    price += price_bit( bm[model], bit );
 
110
    model = ( model << 1 ) | bit;
 
111
    }
 
112
  return price;
 
113
  }
 
114
 
 
115
 
 
116
inline int price_matched( const Bit_model bm[], const int symbol,
 
117
                          const int match_byte ) throw()
 
118
  {
 
119
  int price = 0;
 
120
  int model = 1;
 
121
 
 
122
  for( int i = 7; i >= 0; --i )
 
123
    {
 
124
    const int match_bit = ( match_byte >> i ) & 1;
 
125
    int bit = ( symbol >> i ) & 1;
 
126
    price += price_bit( bm[(match_bit<<8)+model+0x100], bit );
 
127
    model = ( model << 1 ) | bit;
 
128
    if( match_bit != bit )
 
129
      {
 
130
      while( --i >= 0 )
 
131
        {
 
132
        bit = ( symbol >> i ) & 1;
 
133
        price += price_bit( bm[model], bit );
 
134
        model = ( model << 1 ) | bit;
 
135
        }
 
136
      break;
 
137
      }
 
138
    }
 
139
  return price;
 
140
  }
 
141
 
 
142
 
 
143
class Matchfinder
 
144
  {
 
145
  enum { // bytes to keep in buffer before dictionary
 
146
         before_size = max_num_trials + 1,
 
147
         // bytes to keep in buffer after pos
 
148
         after_size = max_match_len,
 
149
         num_prev_positions4 = 1 << 20,
 
150
         num_prev_positions3 = 1 << 18,
 
151
         num_prev_positions2 = 1 << 16,
 
152
         num_prev_positions = num_prev_positions4 + num_prev_positions3 +
 
153
                              num_prev_positions2 };
 
154
 
 
155
  long long partial_data_pos;
 
156
  uint8_t * buffer;             // input buffer
 
157
  int32_t * const prev_positions;       // last seen position of key
 
158
  int32_t * prev_pos_tree;
 
159
  int dictionary_size_;         // bytes to keep in buffer before pos
 
160
  int buffer_size;
 
161
  int pos;                      // current pos in buffer
 
162
  int cyclic_pos;               // current pos in dictionary
 
163
  int stream_pos;               // first byte not yet read from file
 
164
  int pos_limit;                // when reached, a new block must be read
 
165
  const int match_len_limit_;
 
166
  const int cycles;
 
167
  const int infd;               // input file descriptor
 
168
  bool at_stream_end;           // stream_pos shows real end of file
 
169
 
 
170
  bool read_block();
 
171
 
 
172
public:
 
173
  Matchfinder( const int dict_size, const int len_limit, const int ifd );
 
174
 
 
175
  ~Matchfinder()
 
176
    { delete[] prev_pos_tree; delete[] prev_positions; free( buffer ); }
 
177
 
 
178
  uint8_t operator[]( const int i ) const throw() { return buffer[pos+i]; }
 
179
  int available_bytes() const throw() { return stream_pos - pos; }
 
180
  long long data_position() const throw() { return partial_data_pos + pos; }
 
181
  int dictionary_size() const throw() { return dictionary_size_; }
 
182
  bool finished() const throw() { return at_stream_end && pos >= stream_pos; }
 
183
  int match_len_limit() const throw() { return match_len_limit_; }
 
184
  const uint8_t * ptr_to_current_pos() const throw() { return buffer + pos; }
 
185
 
 
186
  bool dec_pos( const int ahead ) throw()
 
187
    {
 
188
    if( ahead < 0 || pos < ahead ) return false;
 
189
    pos -= ahead;
 
190
    cyclic_pos -= ahead;
 
191
    if( cyclic_pos < 0 ) cyclic_pos += dictionary_size_;
 
192
    return true;
 
193
    }
 
194
 
 
195
  int true_match_len( const int index, const int distance, int len_limit ) const throw()
 
196
    {
 
197
    if( index + len_limit > available_bytes() )
 
198
      len_limit = available_bytes() - index;
 
199
    const uint8_t * const data = buffer + pos + index - distance;
 
200
    int i = 0;
 
201
    while( i < len_limit && data[i] == data[i+distance] ) ++i;
 
202
    return i;
 
203
    }
 
204
 
 
205
  void reset();
 
206
  void move_pos();
 
207
  int longest_match_len( int * const distances = 0 ) throw();
 
208
  };
 
209
 
 
210
 
 
211
class Range_encoder
 
212
  {
 
213
  enum { buffer_size = 65536 };
 
214
  uint64_t low;
 
215
  long long partial_member_pos;
 
216
  uint8_t * const buffer;       // output buffer
 
217
  int pos;                      // current pos in buffer
 
218
  uint32_t range;
 
219
  int ff_count;
 
220
  const int outfd;              // output file descriptor
 
221
  uint8_t cache;
 
222
 
 
223
  void shift_low()
 
224
    {
 
225
    const uint32_t carry = low >> 32;
 
226
    if( low < 0xFF000000U || carry == 1 )
 
227
      {
 
228
      put_byte( cache + carry );
 
229
      for( ; ff_count > 0; --ff_count ) put_byte( 0xFF + carry );
 
230
      cache = low >> 24;
 
231
      }
 
232
    else ++ff_count;
 
233
    low = ( low & 0x00FFFFFFU ) << 8;
 
234
    }
 
235
 
 
236
public:
 
237
  Range_encoder( const int ofd )
 
238
    :
 
239
    low( 0 ),
 
240
    partial_member_pos( 0 ),
 
241
    buffer( new uint8_t[buffer_size] ),
 
242
    pos( 0 ),
 
243
    range( 0xFFFFFFFFU ),
 
244
    ff_count( 0 ),
 
245
    outfd( ofd ),
 
246
    cache( 0 ) {}
 
247
 
 
248
  ~Range_encoder() { delete[] buffer; }
 
249
 
 
250
  long long member_position() const throw()
 
251
    { return partial_member_pos + pos + ff_count; }
 
252
 
 
253
  void flush() { for( int i = 0; i < 5; ++i ) shift_low(); }
 
254
  void flush_data();
 
255
 
 
256
  void put_byte( const uint8_t b )
 
257
    {
 
258
    buffer[pos] = b;
 
259
    if( ++pos >= buffer_size ) flush_data();
 
260
    }
 
261
 
 
262
  void encode( const int symbol, const int num_bits )
 
263
    {
 
264
    for( int i = num_bits - 1; i >= 0; --i )
 
265
      {
 
266
      range >>= 1;
 
267
      if( (symbol >> i) & 1 ) low += range;
 
268
      if( range <= 0x00FFFFFFU ) { range <<= 8; shift_low(); }
 
269
      }
 
270
    }
 
271
 
 
272
  void encode_bit( Bit_model & bm, const int bit )
 
273
    {
 
274
    const uint32_t bound = ( range >> bit_model_total_bits ) * bm.probability;
 
275
    if( !bit )
 
276
      {
 
277
      range = bound;
 
278
      bm.probability += (bit_model_total - bm.probability) >> bit_model_move_bits;
 
279
      }
 
280
    else
 
281
      {
 
282
      low += bound;
 
283
      range -= bound;
 
284
      bm.probability -= bm.probability >> bit_model_move_bits;
 
285
      }
 
286
    if( range <= 0x00FFFFFFU ) { range <<= 8; shift_low(); }
 
287
    }
 
288
 
 
289
  void encode_tree( Bit_model bm[], const int symbol, const int num_bits )
 
290
    {
 
291
    int mask = ( 1 << ( num_bits - 1 ) );
 
292
    int model = 1;
 
293
    for( int i = num_bits; i > 0; --i, mask >>= 1 )
 
294
      {
 
295
      const int bit = ( symbol & mask );
 
296
      encode_bit( bm[model], bit );
 
297
      model <<= 1;
 
298
      if( bit ) model |= 1;
 
299
      }
 
300
    }
 
301
 
 
302
  void encode_tree_reversed( Bit_model bm[], int symbol, const int num_bits )
 
303
    {
 
304
    int model = 1;
 
305
    for( int i = num_bits; i > 0; --i )
 
306
      {
 
307
      const int bit = symbol & 1;
 
308
      encode_bit( bm[model], bit );
 
309
      model = ( model << 1 ) | bit;
 
310
      symbol >>= 1;
 
311
      }
 
312
    }
 
313
 
 
314
  void encode_matched( Bit_model bm[], int symbol, int match_byte )
 
315
    {
 
316
    int model = 1;
 
317
    for( int i = 7; i >= 0; --i )
 
318
      {
 
319
      const int match_bit = ( match_byte >> i ) & 1;
 
320
      int bit = ( symbol >> i ) & 1;
 
321
      encode_bit( bm[(match_bit<<8)+model+0x100], bit );
 
322
      model = ( model << 1 ) | bit;
 
323
      if( match_bit != bit )
 
324
        {
 
325
        while( --i >= 0 )
 
326
          {
 
327
          bit = ( symbol >> i ) & 1;
 
328
          encode_bit( bm[model], bit );
 
329
          model = ( model << 1 ) | bit;
 
330
          }
 
331
        break;
 
332
        }
 
333
      }
 
334
    }
 
335
  };
 
336
 
 
337
 
 
338
class Len_encoder
 
339
  {
 
340
  Bit_model choice1;
 
341
  Bit_model choice2;
 
342
  Bit_model bm_low[pos_states][len_low_symbols];
 
343
  Bit_model bm_mid[pos_states][len_mid_symbols];
 
344
  Bit_model bm_high[len_high_symbols];
 
345
  int prices[pos_states][max_len_symbols];
 
346
  const int len_symbols;
 
347
  int counters[pos_states];
 
348
 
 
349
  void update_prices( const int pos_state ) throw()
 
350
    {
 
351
    int * const pps = prices[pos_state];
 
352
    int tmp = price0( choice1 );
 
353
    int len = 0;
 
354
    for( ; len < len_low_symbols && len < len_symbols; ++len )
 
355
      pps[len] = tmp +
 
356
                 price_symbol( bm_low[pos_state], len, len_low_bits );
 
357
    tmp = price1( choice1 );
 
358
    for( ; len < len_low_symbols + len_mid_symbols && len < len_symbols; ++len )
 
359
      pps[len] = tmp + price0( choice2 ) +
 
360
                 price_symbol( bm_mid[pos_state], len - len_low_symbols, len_mid_bits );
 
361
    for( ; len < len_symbols; ++len )
 
362
      // using 4 slots per value makes "price" faster
 
363
      prices[3][len] = prices[2][len] = prices[1][len] = prices[0][len] =
 
364
                 tmp + price1( choice2 ) +
 
365
                 price_symbol( bm_high, len - len_low_symbols - len_mid_symbols, len_high_bits );
 
366
    counters[pos_state] = len_symbols;
 
367
    }
 
368
 
 
369
public:
 
370
  Len_encoder( const int len_limit )
 
371
    : len_symbols( len_limit + 1 - min_match_len )
 
372
    {
 
373
    for( int i = 0; i < pos_states; ++i ) update_prices( i );
 
374
    }
 
375
 
 
376
  void encode( Range_encoder & range_encoder, int symbol,
 
377
               const int pos_state );
 
378
 
 
379
  int price( const int symbol, const int pos_state ) const throw()
 
380
    { return prices[pos_state][symbol - min_match_len]; }
 
381
  };
 
382
 
 
383
 
 
384
class Literal_encoder
 
385
  {
 
386
  Bit_model bm_literal[1<<literal_context_bits][0x300];
 
387
 
 
388
  int lstate( const uint8_t prev_byte ) const throw()
 
389
    { return ( prev_byte >> ( 8 - literal_context_bits ) ); }
 
390
 
 
391
public:
 
392
  void encode( Range_encoder & range_encoder,
 
393
               uint8_t prev_byte, uint8_t symbol )
 
394
    { range_encoder.encode_tree( bm_literal[lstate(prev_byte)], symbol, 8 ); }
 
395
 
 
396
  void encode_matched( Range_encoder & range_encoder,
 
397
                       uint8_t prev_byte, uint8_t symbol, uint8_t match_byte )
 
398
    { range_encoder.encode_matched( bm_literal[lstate(prev_byte)],
 
399
                                    symbol, match_byte ); }
 
400
 
 
401
  int price_symbol( uint8_t prev_byte, uint8_t symbol ) const throw()
 
402
    { return ::price_symbol( bm_literal[lstate(prev_byte)], symbol, 8 ); }
 
403
 
 
404
  int price_matched( uint8_t prev_byte, uint8_t symbol,
 
405
                     uint8_t match_byte ) const throw()
 
406
    { return ::price_matched( bm_literal[lstate(prev_byte)],
 
407
                              symbol, match_byte ); }
 
408
  };
 
409
 
 
410
 
 
411
class LZ_encoder
 
412
  {
 
413
  enum { infinite_price = 0x0FFFFFFF,
 
414
         max_marker_size = 16,
 
415
         num_rep_distances = 4 };       // must be 4
 
416
 
 
417
  struct Trial
 
418
    {
 
419
    State state;
 
420
    int dis;
 
421
    int prev_index;     // index of prev trial in trials[]
 
422
    int price;          // dual use var; cumulative price, match length
 
423
    int reps[num_rep_distances];
 
424
    void update( const int d, const int p_i, const int pr ) throw()
 
425
      { if( pr < price ) { dis = d; prev_index = p_i; price = pr; } }
 
426
    };
 
427
 
 
428
  int longest_match_found;
 
429
  uint32_t crc_;
 
430
 
 
431
  Bit_model bm_match[State::states][pos_states];
 
432
  Bit_model bm_rep[State::states];
 
433
  Bit_model bm_rep0[State::states];
 
434
  Bit_model bm_rep1[State::states];
 
435
  Bit_model bm_rep2[State::states];
 
436
  Bit_model bm_len[State::states][pos_states];
 
437
  Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
 
438
  Bit_model bm_dis[modeled_distances-end_dis_model+1];
 
439
  Bit_model bm_align[dis_align_size];
 
440
 
 
441
  Matchfinder & matchfinder;
 
442
  Range_encoder range_encoder;
 
443
  Len_encoder len_encoder;
 
444
  Len_encoder rep_match_len_encoder;
 
445
  Literal_encoder literal_encoder;
 
446
 
 
447
  const int num_dis_slots;
 
448
  int match_distances[max_match_len+1];
 
449
  Trial trials[max_num_trials];
 
450
 
 
451
  int dis_slot_prices[max_dis_states][2*max_dictionary_bits];
 
452
  int dis_prices[max_dis_states][modeled_distances];
 
453
  int align_prices[dis_align_size];
 
454
  int align_price_count;
 
455
 
 
456
  void fill_align_prices() throw();
 
457
  void fill_distance_prices() throw();
 
458
 
 
459
  uint32_t crc() const throw() { return crc_ ^ 0xFFFFFFFFU; }
 
460
 
 
461
       // move-to-front dis in/into reps
 
462
  void mtf_reps( const int dis, int reps[num_rep_distances] ) throw()
 
463
    {
 
464
    if( dis >= num_rep_distances )
 
465
      {
 
466
      for( int i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1];
 
467
      reps[0] = dis - num_rep_distances;
 
468
      }
 
469
    else if( dis > 0 )
 
470
      {
 
471
      const int distance = reps[dis];
 
472
      for( int i = dis; i > 0; --i ) reps[i] = reps[i-1];
 
473
      reps[0] = distance;
 
474
      }
 
475
    }
 
476
 
 
477
  int price_rep_len1( const State & state, const int pos_state ) const throw()
 
478
    {
 
479
    return price0( bm_rep0[state()] ) + price0( bm_len[state()][pos_state] );
 
480
    }
 
481
 
 
482
  int price_rep( const int rep, const State & state,
 
483
                 const int pos_state ) const throw()
 
484
    {
 
485
    if( rep == 0 ) return price0( bm_rep0[state()] ) +
 
486
                          price1( bm_len[state()][pos_state] );
 
487
    int price = price1( bm_rep0[state()] );
 
488
    if( rep == 1 )
 
489
      price += price0( bm_rep1[state()] );
 
490
    else
 
491
      {
 
492
      price += price1( bm_rep1[state()] );
 
493
      price += price_bit( bm_rep2[state()], rep - 2 );
 
494
      }
 
495
    return price;
 
496
    }
 
497
 
 
498
  int price_dis( const int dis, const int dis_state ) const throw()
 
499
    {
 
500
    if( dis < modeled_distances )
 
501
      return dis_prices[dis_state][dis];
 
502
    else
 
503
      return dis_slot_prices[dis_state][dis_slots[dis]] +
 
504
             align_prices[dis & (dis_align_size - 1)];
 
505
    }
 
506
 
 
507
  int price_pair( const int dis, const int len, const int pos_state ) const throw()
 
508
    {
 
509
    if( len <= min_match_len && dis >= modeled_distances )
 
510
      return infinite_price;
 
511
    return len_encoder.price( len, pos_state ) +
 
512
           price_dis( dis, get_dis_state( len ) );
 
513
    }
 
514
 
 
515
  void encode_pair( const uint32_t dis, const int len, const int pos_state ) throw()
 
516
    {
 
517
    len_encoder.encode( range_encoder, len, pos_state );
 
518
    const int dis_slot = dis_slots[dis];
 
519
    range_encoder.encode_tree( bm_dis_slot[get_dis_state(len)], dis_slot, dis_slot_bits );
 
520
 
 
521
    if( dis_slot >= start_dis_model )
 
522
      {
 
523
      const int direct_bits = ( dis_slot >> 1 ) - 1;
 
524
      const uint32_t base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
 
525
      const uint32_t direct_dis = dis - base;
 
526
 
 
527
      if( dis_slot < end_dis_model )
 
528
        range_encoder.encode_tree_reversed( bm_dis + base - dis_slot,
 
529
                                            direct_dis, direct_bits );
 
530
      else
 
531
        {
 
532
        range_encoder.encode( direct_dis >> dis_align_bits, direct_bits - dis_align_bits );
 
533
        range_encoder.encode_tree_reversed( bm_align, direct_dis, dis_align_bits );
 
534
        if( --align_price_count <= 0 ) fill_align_prices();
 
535
        }
 
536
      }
 
537
    }
 
538
 
 
539
  int read_match_distances() throw()
 
540
    {
 
541
    int len = matchfinder.longest_match_len( match_distances );
 
542
    if( len == matchfinder.match_len_limit() )
 
543
      len += matchfinder.true_match_len( len, match_distances[len] + 1, max_match_len - len );
 
544
    return len;
 
545
    }
 
546
 
 
547
  void move_pos( int n, bool skip = false )
 
548
    {
 
549
    while( --n >= 0 )
 
550
      {
 
551
      if( skip ) skip = false;
 
552
      else matchfinder.longest_match_len();
 
553
      matchfinder.move_pos();
 
554
      }
 
555
    }
 
556
 
 
557
  void backward( int cur )
 
558
    {
 
559
    int & dis = trials[cur].dis;
 
560
    while( cur > 0 )
 
561
      {
 
562
      const int prev_index = trials[cur].prev_index;
 
563
      Trial & prev_trial = trials[prev_index];
 
564
      prev_trial.price = cur - prev_index;                      // len
 
565
      cur = dis; dis = prev_trial.dis; prev_trial.dis = cur;
 
566
      cur = prev_index;
 
567
      }
 
568
    }
 
569
 
 
570
  int sequence_optimizer( const int reps[num_rep_distances],
 
571
                          const State & state );
 
572
 
 
573
  void full_flush( const State & state );
 
574
 
 
575
public:
 
576
  LZ_encoder( Matchfinder & mf, const File_header & header, const int outfd );
 
577
 
 
578
  bool encode_member( const long long member_size );
 
579
 
 
580
  long long member_position() const throw()
 
581
    { return range_encoder.member_position(); }
 
582
  };