← 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/lzip.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/lzip.h
 
1
#define max(a,b) \
 
2
  ({ __typeof__ (a) _a = (a); \
 
3
      __typeof__ (b) _b = (b); \
 
4
    _a > _b ? _a : _b; })
 
5
 
 
6
#define min(a,b) \
 
7
  ({ __typeof__ (a) _a = (a); \
 
8
      __typeof__ (b) _b = (b); \
 
9
    _a < _b ? _a : _b; })
 
10
 
 
11
/*  Lzip - Data compressor based on the LZMA algorithm
 
12
    Copyright (C) 2008, 2009, 2010, 2011 Antonio Diaz Diaz.
 
13
 
 
14
    This program is free software: you can redistribute it and/or modify
 
15
    it under the terms of the GNU General Public License as published by
 
16
    the Free Software Foundation, either version 3 of the License, or
 
17
    (at your option) any later version.
 
18
 
 
19
    This program is distributed in the hope that it will be useful,
 
20
    but WITHOUT ANY WARRANTY; without even the implied warranty of
 
21
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
22
    GNU General Public License for more details.
 
23
 
 
24
    You should have received a copy of the GNU General Public License
 
25
    along with this program.  If not, see <http://www.gnu.org/licenses/>.
 
26
*/
 
27
 
 
28
class State
 
29
  {
 
30
  unsigned char st;
 
31
 
 
32
public:
 
33
  enum { states = 12 };
 
34
  State() : st( 0 ) {}
 
35
  unsigned char operator()() const { return st; }
 
36
  bool is_char() const { return st < 7; }
 
37
 
 
38
  void set_char()
 
39
    {
 
40
    static const unsigned char next[states] =
 
41
      { 0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 4, 5 };
 
42
    st = next[st];
 
43
    }
 
44
 
 
45
  void set_match()
 
46
    {
 
47
    static const unsigned char next[states] =
 
48
      { 7, 7, 7, 7, 7, 7, 7, 10, 10, 10, 10, 10 };
 
49
    st = next[st];
 
50
    }
 
51
 
 
52
  void set_rep()
 
53
    {
 
54
    static const unsigned char next[states] =
 
55
      { 8, 8, 8, 8, 8, 8, 8, 11, 11, 11, 11, 11 };
 
56
    st = next[st];
 
57
    }
 
58
 
 
59
  void set_short_rep()
 
60
    {
 
61
    static const unsigned char next[states] =
 
62
      { 9, 9, 9, 9, 9, 9, 9, 11, 11, 11, 11, 11 };
 
63
    st = next[st];
 
64
    }
 
65
  };
 
66
 
 
67
 
 
68
enum {
 
69
  min_dictionary_bits = 12,
 
70
  min_dictionary_size = 1 << min_dictionary_bits,
 
71
  max_dictionary_bits = 29,
 
72
  max_dictionary_size = 1 << max_dictionary_bits,
 
73
  literal_context_bits = 3,
 
74
  pos_state_bits = 2,
 
75
  pos_states = 1 << pos_state_bits,
 
76
  pos_state_mask = pos_states - 1,
 
77
 
 
78
  dis_slot_bits = 6,
 
79
  start_dis_model = 4,
 
80
  end_dis_model = 14,
 
81
  modeled_distances = 1 << (end_dis_model / 2),
 
82
  dis_align_bits = 4,
 
83
  dis_align_size = 1 << dis_align_bits,
 
84
 
 
85
  len_low_bits = 3,
 
86
  len_mid_bits = 3,
 
87
  len_high_bits = 8,
 
88
  len_low_symbols = 1 << len_low_bits,
 
89
  len_mid_symbols = 1 << len_mid_bits,
 
90
  len_high_symbols = 1 << len_high_bits,
 
91
  max_len_symbols = len_low_symbols + len_mid_symbols + len_high_symbols,
 
92
 
 
93
  min_match_len = 2,                                    // must be 2
 
94
  max_match_len = min_match_len + max_len_symbols - 1,  // 273
 
95
  min_match_len_limit = 5,
 
96
 
 
97
  max_dis_states = 4 };
 
98
 
 
99
inline int get_dis_state( int len )
 
100
  {
 
101
  len -= min_match_len;
 
102
  if( len >= max_dis_states ) len = max_dis_states - 1;
 
103
  return len;
 
104
  }
 
105
 
 
106
 
 
107
enum { bit_model_move_bits = 5,
 
108
       bit_model_total_bits = 11,
 
109
       bit_model_total = 1 << bit_model_total_bits };
 
110
 
 
111
struct Bit_model
 
112
  {
 
113
  unsigned int probability;
 
114
  Bit_model() : probability( bit_model_total / 2 ) {}
 
115
  };
 
116
 
 
117
 
 
118
class CRC32
 
119
  {
 
120
  uint32_t data[256];           // Table of CRCs of all 8-bit messages.
 
121
 
 
122
public:
 
123
  CRC32()
 
124
    {
 
125
    for( unsigned int n = 0; n < 256; ++n )
 
126
      {
 
127
      unsigned int c = n;
 
128
      for( int k = 0; k < 8; ++k )
 
129
        { if( c & 1 ) c = 0xEDB88320U ^ ( c >> 1 ); else c >>= 1; }
 
130
      data[n] = c;
 
131
      }
 
132
    }
 
133
 
 
134
  uint32_t operator[]( const uint8_t byte ) const { return data[byte]; }
 
135
  void update( uint32_t & crc, const uint8_t byte ) const
 
136
    { crc = data[(crc^byte)&0xFF] ^ ( crc >> 8 ); }
 
137
  void update( uint32_t & crc, const uint8_t * const buffer, const int size ) const
 
138
    {
 
139
    for( int i = 0; i < size; ++i )
 
140
      crc = data[(crc^buffer[i])&0xFF] ^ ( crc >> 8 );
 
141
    }
 
142
  };
 
143
 
 
144
extern const CRC32 crc32;
 
145
 
 
146
 
 
147
inline int real_bits( const int value )
 
148
  {
 
149
  int bits = 0;
 
150
  for( int i = 1, mask = 1; mask > 0; ++i, mask <<= 1 )
 
151
    if( value & mask ) bits = i;
 
152
  return bits;
 
153
  }
 
154
 
 
155
const uint8_t magic_string[4] = { 'L', 'Z', 'I', 'P' };
 
156
 
 
157
struct File_header
 
158
  {
 
159
  uint8_t data[6];                      // 0-3 magic bytes
 
160
                                        //   4 version
 
161
                                        //   5 coded_dict_size
 
162
  enum { size = 6 };
 
163
 
 
164
  void set_magic()
 
165
    { memcpy( data, magic_string, 4 ); data[4] = 1; }
 
166
 
 
167
  bool verify_magic() const
 
168
    { return ( memcmp( data, magic_string, 4 ) == 0 ); }
 
169
 
 
170
  uint8_t version() const { return data[4]; }
 
171
  bool verify_version() const { return ( data[4] <= 1 ); }
 
172
 
 
173
  int dictionary_size() const
 
174
    {
 
175
    int sz = ( 1 << ( data[5] & 0x1F ) );
 
176
    if( sz > min_dictionary_size && sz <= max_dictionary_size )
 
177
      sz -= ( sz / 16 ) * ( ( data[5] >> 5 ) & 0x07 );
 
178
    return sz;
 
179
    }
 
180
 
 
181
  bool dictionary_size( const int sz )
 
182
    {
 
183
    if( sz >= min_dictionary_size && sz <= max_dictionary_size )
 
184
      {
 
185
      data[5] = real_bits( sz - 1 );
 
186
      if( sz > min_dictionary_size )
 
187
        {
 
188
        const int base_size = 1 << data[5];
 
189
        const int wedge = base_size / 16;
 
190
        for( int i = 7; i >= 1; --i )
 
191
          if( base_size - ( i * wedge ) >= sz )
 
192
            { data[5] |= ( i << 5 ); break; }
 
193
        }
 
194
      return true;
 
195
      }
 
196
    return false;
 
197
    }
 
198
  };
 
199
 
 
200
 
 
201
struct File_trailer
 
202
  {
 
203
  uint8_t data[20];     //  0-3  CRC32 of the uncompressed data
 
204
                        //  4-11 size of the uncompressed data
 
205
                        // 12-19 member size including header and trailer
 
206
 
 
207
  static int size( const int version = 1 )
 
208
    { return ( ( version >= 1 ) ? 20 : 12 ); }
 
209
 
 
210
  uint32_t data_crc() const
 
211
    {
 
212
    uint32_t tmp = 0;
 
213
    for( int i = 3; i >= 0; --i ) { tmp <<= 8; tmp += data[i]; }
 
214
    return tmp;
 
215
    }
 
216
 
 
217
  void data_crc( uint32_t crc )
 
218
    { for( int i = 0; i <= 3; ++i ) { data[i] = (uint8_t)crc; crc >>= 8; } }
 
219
 
 
220
  long long data_size() const
 
221
    {
 
222
    long long tmp = 0;
 
223
    for( int i = 11; i >= 4; --i ) { tmp <<= 8; tmp += data[i]; }
 
224
    return tmp;
 
225
    }
 
226
 
 
227
  void data_size( long long sz )
 
228
    {
 
229
    for( int i = 4; i <= 11; ++i ) { data[i] = (uint8_t)sz; sz >>= 8; }
 
230
    }
 
231
 
 
232
  long long member_size() const
 
233
    {
 
234
    long long tmp = 0;
 
235
    for( int i = 19; i >= 12; --i ) { tmp <<= 8; tmp += data[i]; }
 
236
    return tmp;
 
237
    }
 
238
 
 
239
  void member_size( long long sz )
 
240
    {
 
241
    for( int i = 12; i <= 19; ++i ) { data[i] = (uint8_t)sz; sz >>= 8; }
 
242
    }
 
243
  };
 
244
 
 
245
 
 
246
struct Error
 
247
  {
 
248
  const char * const msg;
 
249
  Error( const char * const s ) : msg( s ) {}
 
250
  };
 
251
 
 
252
 
 
253
// defined in main.cc lziprecover.cc
 
254
void show_error( const char * const msg, const int errcode = 0,
 
255
                 const bool help = false );
 
256
void internal_error( const char * const msg );
 
257
 
 
258
// defined in decoder.cc
 
259
int readblock( const int fd, uint8_t * const buf, const int size );
 
260
int writeblock( const int fd, const uint8_t * const buf, const int size );
 
261
 
 
262
// XXX
 
263
extern void pp(const char *p=NULL);
 
264