← 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/fast_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/fast_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
class Fmatchfinder
 
19
  {
 
20
  enum { // bytes to keep in buffer before dictionary
 
21
         before_size = max_match_len + 1,
 
22
         // bytes to keep in buffer after pos
 
23
         after_size = max_match_len,
 
24
         num_prev_positions = 1 << 16 };
 
25
 
 
26
  long long partial_data_pos;
 
27
  uint8_t * buffer;             // input buffer
 
28
  int32_t * const prev_positions;       // last seen position of key
 
29
  int32_t * prev_pos_chain;
 
30
  int dictionary_size_;         // bytes to keep in buffer before pos
 
31
  int buffer_size;
 
32
  int pos;                      // current pos in buffer
 
33
  int cyclic_pos;               // current pos in dictionary
 
34
  int key4;                     // key made from latest 4 bytes
 
35
  int stream_pos;               // first byte not yet read from file
 
36
  int pos_limit;                // when reached, a new block must be read
 
37
  const int match_len_limit_;
 
38
  const int infd;               // input file descriptor
 
39
  bool at_stream_end;           // stream_pos shows real end of file
 
40
 
 
41
  bool read_block();
 
42
 
 
43
public:
 
44
  Fmatchfinder( const int ifd );
 
45
 
 
46
  ~Fmatchfinder()
 
47
    { delete[] prev_pos_chain; delete[] prev_positions; free( buffer ); }
 
48
 
 
49
  uint8_t operator[]( const int i ) const { return buffer[pos+i]; }
 
50
  int available_bytes() const { return stream_pos - pos; }
 
51
  long long data_position() const { return partial_data_pos + pos; }
 
52
  int dictionary_size() const { return dictionary_size_; }
 
53
  bool finished() const { return at_stream_end && pos >= stream_pos; }
 
54
  int match_len_limit() const { return match_len_limit_; }
 
55
  const uint8_t * ptr_to_current_pos() const { return buffer + pos; }
 
56
 
 
57
  int true_match_len( const int index, const int distance, int len_limit ) const
 
58
    {
 
59
    if( index + len_limit > available_bytes() )
 
60
      len_limit = available_bytes() - index;
 
61
    const uint8_t * const data = buffer + pos + index - distance;
 
62
    int i = 0;
 
63
    while( i < len_limit && data[i] == data[i+distance] ) ++i;
 
64
    return i;
 
65
    }
 
66
 
 
67
  void reset();
 
68
  void move_pos();
 
69
  int longest_match_len( int * const distance );
 
70
  void longest_match_len();
 
71
  };
 
72
 
 
73
 
 
74
class FLZ_encoder
 
75
  {
 
76
  enum { max_marker_size = 16,
 
77
         num_rep_distances = 4 };       // must be 4
 
78
 
 
79
  uint32_t crc_;
 
80
 
 
81
  Bit_model bm_match[State::states][pos_states];
 
82
  Bit_model bm_rep[State::states];
 
83
  Bit_model bm_rep0[State::states];
 
84
  Bit_model bm_rep1[State::states];
 
85
  Bit_model bm_rep2[State::states];
 
86
  Bit_model bm_len[State::states][pos_states];
 
87
  Bit_model bm_dis_slot[max_dis_states][1<<dis_slot_bits];
 
88
  Bit_model bm_dis[modeled_distances-end_dis_model+1];
 
89
  Bit_model bm_align[dis_align_size];
 
90
 
 
91
  Fmatchfinder & fmatchfinder;
 
92
  Range_encoder range_encoder;
 
93
  Len_encoder len_encoder;
 
94
  Len_encoder rep_match_len_encoder;
 
95
  Literal_encoder literal_encoder;
 
96
 
 
97
  const int num_dis_slots;
 
98
  int match_distance;
 
99
 
 
100
  uint32_t crc() const { return crc_ ^ 0xFFFFFFFFU; }
 
101
 
 
102
       // move-to-front dis in/into reps
 
103
  void mtf_reps( const int dis, int reps[num_rep_distances] )
 
104
    {
 
105
    if( dis >= num_rep_distances )
 
106
      {
 
107
      for( int i = num_rep_distances - 1; i > 0; --i ) reps[i] = reps[i-1];
 
108
      reps[0] = dis - num_rep_distances;
 
109
      }
 
110
    else if( dis > 0 )
 
111
      {
 
112
      const int distance = reps[dis];
 
113
      for( int i = dis; i > 0; --i ) reps[i] = reps[i-1];
 
114
      reps[0] = distance;
 
115
      }
 
116
    }
 
117
 
 
118
  void encode_pair( const uint32_t dis, const int len, const int pos_state )
 
119
    {
 
120
    len_encoder.encode( range_encoder, len, pos_state );
 
121
    const int dis_slot = dis_slots[dis];
 
122
    range_encoder.encode_tree( bm_dis_slot[get_dis_state(len)], dis_slot, dis_slot_bits );
 
123
 
 
124
    if( dis_slot >= start_dis_model )
 
125
      {
 
126
      const int direct_bits = ( dis_slot >> 1 ) - 1;
 
127
      const uint32_t base = ( 2 | ( dis_slot & 1 ) ) << direct_bits;
 
128
      const uint32_t direct_dis = dis - base;
 
129
 
 
130
      if( dis_slot < end_dis_model )
 
131
        range_encoder.encode_tree_reversed( bm_dis + base - dis_slot,
 
132
                                            direct_dis, direct_bits );
 
133
      else
 
134
        {
 
135
        range_encoder.encode( direct_dis >> dis_align_bits, direct_bits - dis_align_bits );
 
136
        range_encoder.encode_tree_reversed( bm_align, direct_dis, dis_align_bits );
 
137
        }
 
138
      }
 
139
    }
 
140
 
 
141
  int read_match_distances()
 
142
    {
 
143
    int len = fmatchfinder.longest_match_len( &match_distance );
 
144
    if( len == fmatchfinder.match_len_limit() )
 
145
      len += fmatchfinder.true_match_len( len, match_distance + 1, max_match_len - len );
 
146
    return len;
 
147
    }
 
148
 
 
149
  void move_pos( int n, bool skip = false )
 
150
    {
 
151
    while( --n >= 0 )
 
152
      {
 
153
      if( skip ) skip = false;
 
154
      else fmatchfinder.longest_match_len();
 
155
      fmatchfinder.move_pos();
 
156
      }
 
157
    }
 
158
 
 
159
  int sequence_optimizer( const int reps[num_rep_distances],
 
160
                          int * const disp, const State & state );
 
161
 
 
162
  void full_flush( const State & state );
 
163
 
 
164
public:
 
165
  FLZ_encoder( Fmatchfinder & mf, const File_header & header, const int outfd );
 
166
 
 
167
  bool encode_member( const long long member_size );
 
168
 
 
169
  long long member_position() const
 
170
    { return range_encoder.member_position(); }
 
171
  };