Debian Codegraph @

src/EWS/addressbook/mspack/lzxd.c

raw
1 /* This file is part of libmspack.
2 * (C) 2003-2013 Stuart Caie.
3 *
4 * The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted
5 * by Microsoft Corporation.
6 *
7 * libmspack is free software; you can redistribute it and/or modify it under
8 * the terms of the GNU Lesser General Public License (LGPL) version 2.1
9 *
10 * For further details, see the file COPYING.LIB distributed with libmspack
11 */
12
13 /* LZX decompression implementation */
14
15 #include "lzx.h"
16 #include <glib.h>
17
18 /* Microsoft's LZX document (in cab-sdk.exe) and their implementation
19 * of the com.ms.util.cab Java package do not concur.
20 *
21 * In the LZX document, there is a table showing the correlation between
22 * window size and the number of position slots. It states that the 1MB
23 * window = 40 slots and the 2MB window = 42 slots. In the implementation,
24 * 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
25 * first slot whose position base is equal to or more than the required
26 * window size'. This would explain why other tables in the document refer
27 * to 50 slots rather than 42.
28 *
29 * The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
30 * is not defined in the specification.
31 *
32 * The LZX document does not state the uncompressed block has an
33 * uncompressed length field. Where does this length field come from, so
34 * we can know how large the block is? The implementation has it as the 24
35 * bits following after the 3 blocktype bits, before the alignment
36 * padding.
37 *
38 * The LZX document states that aligned offset blocks have their aligned
39 * offset huffman tree AFTER the main and length trees. The implementation
40 * suggests that the aligned offset tree is BEFORE the main and length
41 * trees.
42 *
43 * The LZX document decoding algorithm states that, in an aligned offset
44 * block, if an extra_bits value is 1, 2 or 3, then that number of bits
45 * should be read and the result added to the match offset. This is
46 * correct for 1 and 2, but not 3, where just a huffman symbol (using the
47 * aligned tree) should be read.
48 *
49 * Regarding the E8 preprocessing, the LZX document states 'No translation
50 * may be performed on the last 6 bytes of the input block'. This is
51 * correct. However, the pseudocode provided checks for the *E8 leader*
52 * up to the last 6 bytes. If the leader appears between -10 and -7 bytes
53 * from the end, this would cause the next four bytes to be modified, at
54 * least one of which would be in the last 6 bytes, which is not allowed
55 * according to the spec.
56 *
57 * The specification states that the huffman trees must always contain at
58 * least one element. However, many CAB files contain blocks where the
59 * length tree is completely empty (because there are no matches), and
60 * this is expected to succeed.
61 *
62 * The errors in LZX documentation appear have been corrected in the
63 * new documentation for the LZX DELTA format.
64 *
65 * http://msdn.microsoft.com/en-us/library/cc483133.aspx
66 *
67 * However, this is a different format, an extension of regular LZX.
68 * I have noticed the following differences, there may be more:
69 *
70 * The maximum window size has increased from 2MB to 32MB. This also
71 * increases the maximum number of position slots, etc.
72 *
73 * If the match length is 257 (the maximum possible), this signals
74 * a further length decoding step, that allows for matches up to
75 * 33024 bytes long.
76 *
77 * The format now allows for "reference data", supplied by the caller.
78 * If match offsets go further back than the number of bytes
79 * decompressed so far, that is them accessing the reference data.
80 */
81
82 /* import bit-reading macros and code */
83 #define BITS_TYPE struct lzxd_stream
84 #define BITS_VAR lzx
85 #define BITS_ORDER_MSB
86 #define READ_BYTES do { \
87 unsigned char b0, b1; \
88 READ_IF_NEEDED; b0 = *i_ptr++; \
89 READ_IF_NEEDED; b1 = *i_ptr++; \
90 INJECT_BITS((b1 << 8) | b0, 16); \
91 } while (0)
92 #include "readbits.h"
93
94 /* import huffman-reading macros and code */
95 #define TABLEBITS(tbl) LZX_##tbl##_TABLEBITS
96 #define MAXSYMBOLS(tbl) LZX_##tbl##_MAXSYMBOLS
97 #define HUFF_TABLE(tbl,idx) lzx->tbl##_table[idx]
98 #define HUFF_LEN(tbl,idx) lzx->tbl##_len[idx]
99 #define HUFF_ERROR return lzx->error = LZX_ERR_DECRUNCH
100 #include "readhuff.h"
101
102 /* BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */
103 #define BUILD_TABLE(tbl) \
104 if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \
105 &HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \
106 { \
107 D(("failed to build %s table", #tbl)) \
108 return lzx->error = LZX_ERR_DECRUNCH; \
109 }
110
111 #define BUILD_TABLE_MAYBE_EMPTY(tbl) do { \
112 lzx->tbl##_empty = 0; \
113 if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \
114 &HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \
115 { \
116 for (i = 0; i < MAXSYMBOLS(tbl); i++) { \
117 if (HUFF_LEN(tbl, i) > 0) { \
118 D(("failed to build %s table", #tbl)) \
119 return lzx->error = LZX_ERR_DECRUNCH; \
120 } \
121 } \
122 /* empty tree - allow it, but don't decode symbols with it */ \
123 lzx->tbl##_empty = 1; \
124 } \
125 } while (0)
126
127 /* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
128 * first to last in the given table. The code lengths are stored in their
129 * own special LZX way.
130 */
131 #define READ_LENGTHS(tbl, first, last) do { \
132 STORE_BITS; \
133 if (lzxd_read_lens(lzx, &HUFF_LEN(tbl, 0), (first), \
134 (unsigned int)(last))) return lzx->error; \
135 RESTORE_BITS; \
136 } while (0)
137
138 static int lzxd_read_lens(struct lzxd_stream *lzx, unsigned char *lens,
139 unsigned int first, unsigned int last)
140 {
141 /* bit buffer and huffman symbol decode variables */
142 register unsigned int bit_buffer;
143 register int bits_left, i;
144 register unsigned short sym;
145 unsigned char *i_ptr, *i_end;
146
147 unsigned int x, y;
148 int z;
149
150 RESTORE_BITS;
151
152 /* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */
153 for (x = 0; x < 20; x++) {
154 READ_BITS(y, 4);
155 lzx->PRETREE_len[x] = y;
156 }
157 BUILD_TABLE(PRETREE);
158
159 for (x = first; x < last; ) {
160 READ_HUFFSYM(PRETREE, z);
161 if (z == 17) {
162 /* code = 17, run of ([read 4 bits]+4) zeros */
163 READ_BITS(y, 4); y += 4;
164 while (y--) lens[x++] = 0;
165 }
166 else if (z == 18) {
167 /* code = 18, run of ([read 5 bits]+20) zeros */
168 READ_BITS(y, 5); y += 20;
169 while (y--) lens[x++] = 0;
170 }
171 else if (z == 19) {
172 /* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */
173 READ_BITS(y, 1); y += 4;
174 READ_HUFFSYM(PRETREE, z);
175 z = lens[x] - z; if (z < 0) z += 17;
176 while (y--) lens[x++] = z;
177 }
178 else {
179 /* code = 0 to 16, delta current length entry */
180 z = lens[x] - z; if (z < 0) z += 17;
181 lens[x++] = z;
182 }
183 }
184
185 STORE_BITS;
186
187 return LZX_ERR_OK;
188 }
189
190 /* LZX static data tables:
191 *
192 * LZX uses 'position slots' to represent match offsets. For every match,
193 * a small 'position slot' number and a small offset from that slot are
194 * encoded instead of one large offset.
195 *
196 * The number of slots is decided by how many are needed to encode the
197 * largest offset for a given window size. This is easy when the gap between
198 * slots is less than 128Kb, it's a linear relationship. But when extra_bits
199 * reaches its limit of 17 (because LZX can only ensure reading 17 bits of
200 * data at a time), we can only jump 128Kb at a time and have to start
201 * using more and more position slots as each window size doubles.
202 *
203 * position_base[] is an index to the position slot bases
204 *
205 * extra_bits[] states how many bits of offset-from-base data is needed.
206 *
207 * They are calculated as follows:
208 * extra_bits[i] = 0 where i < 4
209 * extra_bits[i] = floor(i/2)-1 where i >= 4 && i < 36
210 * extra_bits[i] = 17 where i >= 36
211 * position_base[0] = 0
212 * position_base[i] = position_base[i-1] + (1 << extra_bits[i-1])
213 */
214 static const unsigned int position_slots[11] = {
215 30, 32, 34, 36, 38, 42, 50, 66, 98, 162, 290
216 };
217 static const unsigned char extra_bits[36] = {
218 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
219 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16
220 };
221 static const unsigned int position_base[290] = {
222 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256, 384, 512,
223 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288, 16384, 24576, 32768,
224 49152, 65536, 98304, 131072, 196608, 262144, 393216, 524288, 655360,
225 786432, 917504, 1048576, 1179648, 1310720, 1441792, 1572864, 1703936,
226 1835008, 1966080, 2097152, 2228224, 2359296, 2490368, 2621440, 2752512,
227 2883584, 3014656, 3145728, 3276800, 3407872, 3538944, 3670016, 3801088,
228 3932160, 4063232, 4194304, 4325376, 4456448, 4587520, 4718592, 4849664,
229 4980736, 5111808, 5242880, 5373952, 5505024, 5636096, 5767168, 5898240,
230 6029312, 6160384, 6291456, 6422528, 6553600, 6684672, 6815744, 6946816,
231 7077888, 7208960, 7340032, 7471104, 7602176, 7733248, 7864320, 7995392,
232 8126464, 8257536, 8388608, 8519680, 8650752, 8781824, 8912896, 9043968,
233 9175040, 9306112, 9437184, 9568256, 9699328, 9830400, 9961472, 10092544,
234 10223616, 10354688, 10485760, 10616832, 10747904, 10878976, 11010048,
235 11141120, 11272192, 11403264, 11534336, 11665408, 11796480, 11927552,
236 12058624, 12189696, 12320768, 12451840, 12582912, 12713984, 12845056,
237 12976128, 13107200, 13238272, 13369344, 13500416, 13631488, 13762560,
238 13893632, 14024704, 14155776, 14286848, 14417920, 14548992, 14680064,
239 14811136, 14942208, 15073280, 15204352, 15335424, 15466496, 15597568,
240 15728640, 15859712, 15990784, 16121856, 16252928, 16384000, 16515072,
241 16646144, 16777216, 16908288, 17039360, 17170432, 17301504, 17432576,
242 17563648, 17694720, 17825792, 17956864, 18087936, 18219008, 18350080,
243 18481152, 18612224, 18743296, 18874368, 19005440, 19136512, 19267584,
244 19398656, 19529728, 19660800, 19791872, 19922944, 20054016, 20185088,
245 20316160, 20447232, 20578304, 20709376, 20840448, 20971520, 21102592,
246 21233664, 21364736, 21495808, 21626880, 21757952, 21889024, 22020096,
247 22151168, 22282240, 22413312, 22544384, 22675456, 22806528, 22937600,
248 23068672, 23199744, 23330816, 23461888, 23592960, 23724032, 23855104,
249 23986176, 24117248, 24248320, 24379392, 24510464, 24641536, 24772608,
250 24903680, 25034752, 25165824, 25296896, 25427968, 25559040, 25690112,
251 25821184, 25952256, 26083328, 26214400, 26345472, 26476544, 26607616,
252 26738688, 26869760, 27000832, 27131904, 27262976, 27394048, 27525120,
253 27656192, 27787264, 27918336, 28049408, 28180480, 28311552, 28442624,
254 28573696, 28704768, 28835840, 28966912, 29097984, 29229056, 29360128,
255 29491200, 29622272, 29753344, 29884416, 30015488, 30146560, 30277632,
256 30408704, 30539776, 30670848, 30801920, 30932992, 31064064, 31195136,
257 31326208, 31457280, 31588352, 31719424, 31850496, 31981568, 32112640,
258 32243712, 32374784, 32505856, 32636928, 32768000, 32899072, 33030144,
259 33161216, 33292288, 33423360
260 };
261
262 static void lzxd_reset_state(struct lzxd_stream *lzx) {
263 int i;
264
265 lzx->R0 = 1;
266 lzx->R1 = 1;
267 lzx->R2 = 1;
268 lzx->header_read = 0;
269 lzx->block_remaining = 0;
270 lzx->block_type = LZX_BLOCKTYPE_INVALID;
271
272 /* initialise tables to 0 (because deltas will be applied to them) */
273 for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0;
274 for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0;
275 }
276
277 /*-------- main LZX code --------*/
278
279 struct lzxd_stream *ews_lzxd_init(FILE *input,
280 FILE *output,
281 int window_bits,
282 int reset_interval,
283 int input_buffer_size,
284 off_t output_length,
285 char is_delta)
286 {
287 unsigned int window_size = 1 << window_bits;
288 struct lzxd_stream *lzx;
289
290 /* LZX DELTA window sizes are between 2^17 (128KiB) and 2^25 (32MiB),
291 * regular LZX windows are between 2^15 (32KiB) and 2^21 (2MiB)
292 */
293 if (is_delta) {
294 if (window_bits < 17 || window_bits > 25) return NULL;
295 }
296 else {
297 if (window_bits < 15 || window_bits > 21) return NULL;
298 }
299
300 input_buffer_size = (input_buffer_size + 1) & -2;
301 if (!input_buffer_size) return NULL;
302
303 /* allocate decompression state */
304 if (!(lzx = (struct lzxd_stream *) malloc(sizeof(struct lzxd_stream)))) {
305 return NULL;
306 }
307
308 /* allocate decompression window and input buffer */
309 lzx->window = (unsigned char *) malloc((size_t) window_size);
310 lzx->inbuf = (unsigned char *) malloc((size_t) input_buffer_size);
311 if (!lzx->window || !lzx->inbuf) {
312 free(lzx->window);
313 free(lzx->inbuf);
314 free(lzx);
315 return NULL;
316 }
317
318 /* initialise decompression state */
319 lzx->input = input;
320 lzx->output = output;
321 lzx->offset = 0;
322 lzx->length = output_length;
323
324 lzx->inbuf_size = input_buffer_size;
325 lzx->window_size = 1 << window_bits;
326 lzx->ref_data_size = 0;
327 lzx->window_posn = 0;
328 lzx->frame_posn = 0;
329 lzx->frame = 0;
330 lzx->reset_interval = reset_interval;
331 lzx->intel_filesize = 0;
332 lzx->intel_curpos = 0;
333 lzx->intel_started = 0;
334 lzx->error = LZX_ERR_OK;
335 lzx->num_offsets = position_slots[window_bits - 15] << 3;
336 lzx->is_delta = is_delta;
337
338 lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0];
339 lzxd_reset_state(lzx);
340 INIT_BITS;
341 return lzx;
342 }
343
344 int ews_lzxd_set_reference_data(struct lzxd_stream *lzx,
345 FILE *input,
346 unsigned int length)
347 {
348 if (!lzx) return LZX_ERR_ARGS;
349
350 if (!lzx->is_delta) {
351 D(("only LZX DELTA streams support reference data"))
352 return LZX_ERR_ARGS;
353 }
354 if (lzx->offset) {
355 D(("too late to set reference data after decoding starts"))
356 return LZX_ERR_ARGS;
357 }
358 if (length > lzx->window_size) {
359 D(("reference length (%u) is longer than the window", length))
360 return LZX_ERR_ARGS;
361 }
362 if (length > 0 && (!input)) {
363 D(("length > 0 but no input"))
364 return LZX_ERR_ARGS;
365 }
366
367 lzx->ref_data_size = length;
368 if (length > 0) {
369 /* copy reference data */
370 unsigned char *pos = &lzx->window[lzx->window_size - length];
371 int bytes = fread(pos, 1, length, input);
372 if (bytes < length) return LZX_ERR_READ;
373 }
374 lzx->ref_data_size = length;
375 return LZX_ERR_OK;
376 }
377
378 void ews_lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) {
379 if (lzx) lzx->length = out_bytes;
380 }
381
382 int ews_lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes) {
383 /* bitstream and huffman reading variables */
384 register unsigned int bit_buffer;
385 register int bits_left, i=0;
386 unsigned char *i_ptr, *i_end;
387 register unsigned short sym;
388
389 int match_length, length_footer, extra, verbatim_bits, bytes_todo;
390 int this_run, main_element, aligned_bits, j;
391 unsigned char *window, *runsrc, *rundest, buf[12];
392 unsigned int frame_size=0, end_frame, match_offset, window_posn;
393 unsigned int R0, R1, R2;
394
395 /* easy answers */
396 if (!lzx || (out_bytes < 0)) return LZX_ERR_ARGS;
397 if (lzx->error) return lzx->error;
398
399 /* flush out any stored-up bytes before we begin */
400 i = lzx->o_end - lzx->o_ptr;
401 if ((off_t) i > out_bytes) i = (int) out_bytes;
402 if (i) {
403 if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) {
404 return lzx->error = LZX_ERR_WRITE;
405 }
406 lzx->o_ptr += i;
407 lzx->offset += i;
408 out_bytes -= i;
409 }
410 if (out_bytes == 0) return LZX_ERR_OK;
411
412 /* restore local state */
413 RESTORE_BITS;
414 window = lzx->window;
415 window_posn = lzx->window_posn;
416 R0 = lzx->R0;
417 R1 = lzx->R1;
418 R2 = lzx->R2;
419
420 end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1;
421
422 while (lzx->frame < end_frame) {
423 /* have we reached the reset interval? (if there is one?) */
424 if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) {
425 if (lzx->block_remaining) {
426 D(("%d bytes remaining at reset interval", lzx->block_remaining))
427 return lzx->error = LZX_ERR_DECRUNCH;
428 }
429
430 /* re-read the intel header and reset the huffman lengths */
431 lzxd_reset_state(lzx);
432 R0 = lzx->R0;
433 R1 = lzx->R1;
434 R2 = lzx->R2;
435 }
436
437 /* LZX DELTA format has chunk_size, not present in LZX format */
438 if (lzx->is_delta) {
439 ENSURE_BITS(16);
440 REMOVE_BITS(16);
441 }
442
443 /* read header if necessary */
444 if (!lzx->header_read) {
445 /* read 1 bit. if bit=0, intel filesize = 0.
446 * if bit=1, read intel filesize (32 bits) */
447 j = 0; READ_BITS(i, 1); if (i) { READ_BITS(i, 16); READ_BITS(j, 16); }
448 lzx->intel_filesize = (i << 16) | j;
449 lzx->header_read = 1;
450 }
451
452 /* calculate size of frame: all frames are 32k except the final frame
453 * which is 32kb or less. this can only be calculated when lzx->length
454 * has been filled in. */
455 frame_size = LZX_FRAME_SIZE;
456 if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) {
457 frame_size = lzx->length - lzx->offset;
458 }
459
460 /* decode until one more frame is available */
461 bytes_todo = lzx->frame_posn + frame_size - window_posn;
462 while (bytes_todo > 0) {
463 /* initialise new block, if one is needed */
464 if (lzx->block_remaining == 0) {
465 /* realign if previous block was an odd-sized UNCOMPRESSED block */
466 if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) &&
467 (lzx->block_length & 1))
468 {
469 READ_IF_NEEDED;
470 i_ptr++;
471 }
472
473 /* read block type (3 bits) and block length (24 bits) */
474 READ_BITS(lzx->block_type, 3);
475 READ_BITS(i, 16); READ_BITS(j, 8);
476 lzx->block_remaining = lzx->block_length = (i << 8) | j;
477 /*D(("new block t%d len %u", lzx->block_type, lzx->block_length))*/
478
479 /* read individual block headers */
480 switch (lzx->block_type) {
481 case LZX_BLOCKTYPE_ALIGNED:
482 /* read lengths of and build aligned huffman decoding tree */
483 for (i = 0; i < 8; i++) { READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; }
484 BUILD_TABLE(ALIGNED);
485 /* no break -- rest of aligned header is same as verbatim */
486 case LZX_BLOCKTYPE_VERBATIM:
487 /* read lengths of and build main huffman decoding tree */
488 READ_LENGTHS(MAINTREE, 0, 256);
489 READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + lzx->num_offsets);
490 BUILD_TABLE(MAINTREE);
491 /* if the literal 0xE8 is anywhere in the block... */
492 if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1;
493 /* read lengths of and build lengths huffman decoding tree */
494 READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
495 BUILD_TABLE_MAYBE_EMPTY(LENGTH);
496 break;
497
498 case LZX_BLOCKTYPE_UNCOMPRESSED:
499 /* because we can't assume otherwise */
500 lzx->intel_started = 1;
501
502 /* read 1-16 (not 0-15) bits to align to bytes */
503 ENSURE_BITS(16);
504 if (bits_left > 16) i_ptr -= 2;
505 bits_left = 0; bit_buffer = 0;
506
507 /* read 12 bytes of stored R0 / R1 / R2 values */
508 for (rundest = &buf[0], i = 0; i < 12; i++) {
509 READ_IF_NEEDED;
510 *rundest++ = *i_ptr++;
511 }
512 R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24);
513 R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24);
514 R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24);
515 break;
516
517 default:
518 D(("bad block type"))
519 return lzx->error = LZX_ERR_DECRUNCH;
520 }
521 }
522
523 /* decode more of the block:
524 * run = min(what's available, what's needed) */
525 this_run = lzx->block_remaining;
526 if (this_run > bytes_todo) this_run = bytes_todo;
527
528 /* assume we decode exactly this_run bytes, for now */
529 bytes_todo -= this_run;
530 lzx->block_remaining -= this_run;
531
532 /* decode at least this_run bytes */
533 switch (lzx->block_type) {
534 case LZX_BLOCKTYPE_VERBATIM:
535 while (this_run > 0) {
536 READ_HUFFSYM(MAINTREE, main_element);
537 if (main_element < LZX_NUM_CHARS) {
538 /* literal: 0 to LZX_NUM_CHARS-1 */
539 window[window_posn++] = main_element;
540 this_run--;
541 }
542 else {
543 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
544 main_element -= LZX_NUM_CHARS;
545
546 /* get match length */
547 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
548 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
549 if (lzx->LENGTH_empty) {
550 D(("LENGTH symbol needed but tree is empty"))
551 return lzx->error = LZX_ERR_DECRUNCH;
552 }
553 READ_HUFFSYM(LENGTH, length_footer);
554 match_length += length_footer;
555 }
556 match_length += LZX_MIN_MATCH;
557
558 /* get match offset */
559 switch ((match_offset = (main_element >> 3))) {
560 case 0: match_offset = R0; break;
561 case 1: match_offset = R1; R1=R0; R0 = match_offset; break;
562 case 2: match_offset = R2; R2=R0; R0 = match_offset; break;
563 case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break;
564 default:
565 extra = (match_offset >= 36) ? 17 : extra_bits[match_offset];
566 READ_BITS(verbatim_bits, extra);
567 match_offset = position_base[match_offset] - 2 + verbatim_bits;
568 R2 = R1; R1 = R0; R0 = match_offset;
569 }
570
571 /* LZX DELTA uses max match length to signal even longer match */
572 if (match_length == LZX_MAX_MATCH && lzx->is_delta) {
573 int extra_len = 0;
574 ENSURE_BITS(3); /* 4 entry huffman tree */
575 if (PEEK_BITS(1) == 0) {
576 REMOVE_BITS(1); /* '0' -> 8 extra length bits */
577 READ_BITS(extra_len, 8);
578 }
579 else if (PEEK_BITS(2) == 2) {
580 REMOVE_BITS(2); /* '10' -> 10 extra length bits + 0x100 */
581 READ_BITS(extra_len, 10);
582 extra_len += 0x100;
583 }
584 else if (PEEK_BITS(3) == 6) {
585 REMOVE_BITS(3); /* '110' -> 12 extra length bits + 0x500 */
586 READ_BITS(extra_len, 12);
587 extra_len += 0x500;
588 }
589 else {
590 REMOVE_BITS(3); /* '111' -> 15 extra length bits */
591 READ_BITS(extra_len, 15);
592 }
593 match_length += extra_len;
594 }
595
596 if ((window_posn + match_length) > lzx->window_size) {
597 D(("match ran over window wrap"))
598 return lzx->error = LZX_ERR_DECRUNCH;
599 }
600
601 /* copy match */
602 rundest = &window[window_posn];
603 i = match_length;
604 /* does match offset wrap the window? */
605 if (match_offset > window_posn) {
606 if (match_offset > lzx->offset &&
607 (match_offset - window_posn) > lzx->ref_data_size)
608 {
609 D(("match offset beyond LZX stream"))
610 return lzx->error = LZX_ERR_DECRUNCH;
611 }
612 /* j = length from match offset to end of window */
613 j = match_offset - window_posn;
614 if (j > (int) lzx->window_size) {
615 D(("match offset beyond window boundaries"))
616 return lzx->error = LZX_ERR_DECRUNCH;
617 }
618 runsrc = &window[lzx->window_size - j];
619 if (j < i) {
620 /* if match goes over the window edge, do two copy runs */
621 i -= j; while (j-- > 0) *rundest++ = *runsrc++;
622 runsrc = window;
623 }
624 while (i-- > 0) *rundest++ = *runsrc++;
625 }
626 else {
627 runsrc = rundest - match_offset;
628 while (i-- > 0) *rundest++ = *runsrc++;
629 }
630
631 this_run -= match_length;
632 window_posn += match_length;
633 }
634 } /* while (this_run > 0) */
635 break;
636
637 case LZX_BLOCKTYPE_ALIGNED:
638 while (this_run > 0) {
639 READ_HUFFSYM(MAINTREE, main_element);
640 if (main_element < LZX_NUM_CHARS) {
641 /* literal: 0 to LZX_NUM_CHARS-1 */
642 window[window_posn++] = main_element;
643 this_run--;
644 }
645 else {
646 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
647 main_element -= LZX_NUM_CHARS;
648
649 /* get match length */
650 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
651 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
652 if (lzx->LENGTH_empty) {
653 D(("LENGTH symbol needed but tree is empty"))
654 return lzx->error = LZX_ERR_DECRUNCH;
655 }
656 READ_HUFFSYM(LENGTH, length_footer);
657 match_length += length_footer;
658 }
659 match_length += LZX_MIN_MATCH;
660
661 /* get match offset */
662 switch ((match_offset = (main_element >> 3))) {
663 case 0: match_offset = R0; break;
664 case 1: match_offset = R1; R1 = R0; R0 = match_offset; break;
665 case 2: match_offset = R2; R2 = R0; R0 = match_offset; break;
666 default:
667 extra = (match_offset >= 36) ? 17 : extra_bits[match_offset];
668 match_offset = position_base[match_offset] - 2;
669 if (extra > 3) {
670 /* verbatim and aligned bits */
671 extra -= 3;
672 READ_BITS(verbatim_bits, extra);
673 match_offset += (verbatim_bits << 3);
674 READ_HUFFSYM(ALIGNED, aligned_bits);
675 match_offset += aligned_bits;
676 }
677 else if (extra == 3) {
678 /* aligned bits only */
679 READ_HUFFSYM(ALIGNED, aligned_bits);
680 match_offset += aligned_bits;
681 }
682 else if (extra > 0) { /* extra==1, extra==2 */
683 /* verbatim bits only */
684 READ_BITS(verbatim_bits, extra);
685 match_offset += verbatim_bits;
686 }
687 else /* extra == 0 */ {
688 /* ??? not defined in LZX specification! */
689 match_offset = 1;
690 }
691 /* update repeated offset LRU queue */
692 R2 = R1; R1 = R0; R0 = match_offset;
693 }
694
695 /* LZX DELTA uses max match length to signal even longer match */
696 if (match_length == LZX_MAX_MATCH && lzx->is_delta) {
697 int extra_len = 0;
698 ENSURE_BITS(3); /* 4 entry huffman tree */
699 if (PEEK_BITS(1) == 0) {
700 REMOVE_BITS(1); /* '0' -> 8 extra length bits */
701 READ_BITS(extra_len, 8);
702 }
703 else if (PEEK_BITS(2) == 2) {
704 REMOVE_BITS(2); /* '10' -> 10 extra length bits + 0x100 */
705 READ_BITS(extra_len, 10);
706 extra_len += 0x100;
707 }
708 else if (PEEK_BITS(3) == 6) {
709 REMOVE_BITS(3); /* '110' -> 12 extra length bits + 0x500 */
710 READ_BITS(extra_len, 12);
711 extra_len += 0x500;
712 }
713 else {
714 REMOVE_BITS(3); /* '111' -> 15 extra length bits */
715 READ_BITS(extra_len, 15);
716 }
717 match_length += extra_len;
718 }
719
720 if ((window_posn + match_length) > lzx->window_size) {
721 D(("match ran over window wrap"))
722 return lzx->error = LZX_ERR_DECRUNCH;
723 }
724
725 /* copy match */
726 rundest = &window[window_posn];
727 i = match_length;
728 /* does match offset wrap the window? */
729 if (match_offset > window_posn) {
730 if (match_offset > lzx->offset &&
731 (match_offset - window_posn) > lzx->ref_data_size)
732 {
733 D(("match offset beyond LZX stream"))
734 return lzx->error = LZX_ERR_DECRUNCH;
735 }
736 /* j = length from match offset to end of window */
737 j = match_offset - window_posn;
738 if (j > (int) lzx->window_size) {
739 D(("match offset beyond window boundaries"))
740 return lzx->error = LZX_ERR_DECRUNCH;
741 }
742 runsrc = &window[lzx->window_size - j];
743 if (j < i) {
744 /* if match goes over the window edge, do two copy runs */
745 i -= j; while (j-- > 0) *rundest++ = *runsrc++;
746 runsrc = window;
747 }
748 while (i-- > 0) *rundest++ = *runsrc++;
749 }
750 else {
751 runsrc = rundest - match_offset;
752 while (i-- > 0) *rundest++ = *runsrc++;
753 }
754
755 this_run -= match_length;
756 window_posn += match_length;
757 }
758 } /* while (this_run > 0) */
759 break;
760
761 case LZX_BLOCKTYPE_UNCOMPRESSED:
762 /* as this_run is limited not to wrap a frame, this also means it
763 * won't wrap the window (as the window is a multiple of 32k) */
764 rundest = &window[window_posn];
765 window_posn += this_run;
766 while (this_run > 0) {
767 if ((i = i_end - i_ptr) == 0) {
768 READ_IF_NEEDED;
769 }
770 else {
771 if (i > this_run) i = this_run;
772 memcpy(rundest, i_ptr, (size_t) i);
773 rundest += i;
774 i_ptr += i;
775 this_run -= i;
776 }
777 }
778 break;
779
780 default:
781 return lzx->error = LZX_ERR_DECRUNCH; /* might as well */
782 }
783
784 /* did the final match overrun our desired this_run length? */
785 if (this_run < 0) {
786 if ((unsigned int)(-this_run) > lzx->block_remaining) {
787 D(("overrun went past end of block by %d (%d remaining)",
788 -this_run, lzx->block_remaining ))
789 return lzx->error = LZX_ERR_DECRUNCH;
790 }
791 lzx->block_remaining -= -this_run;
792 }
793 } /* while (bytes_todo > 0) */
794
795 /* streams don't extend over frame boundaries */
796 if ((window_posn - lzx->frame_posn) != frame_size) {
797 D(("decode beyond output frame limits! %d != %d",
798 window_posn - lzx->frame_posn, frame_size))
799 return lzx->error = LZX_ERR_DECRUNCH;
800 }
801
802 /* re-align input bitstream */
803 if (bits_left > 0) ENSURE_BITS(16);
804 if (bits_left & 15) REMOVE_BITS(bits_left & 15);
805
806 /* check that we've used all of the previous frame first */
807 if (lzx->o_ptr != lzx->o_end) {
808 D(("%" G_GINT64_FORMAT " avail bytes, new %d frame", (gint64) (lzx->o_end - lzx->o_ptr), frame_size))
809 return lzx->error = LZX_ERR_DECRUNCH;
810 }
811
812 /* does this intel block _really_ need decoding? */
813 if (lzx->intel_started && lzx->intel_filesize &&
814 (lzx->frame <= 32768) && (frame_size > 10))
815 {
816 unsigned char *data = &lzx->e8_buf[0];
817 unsigned char *dataend = &lzx->e8_buf[frame_size - 10];
818 signed int curpos = lzx->intel_curpos;
819 signed int filesize = lzx->intel_filesize;
820 signed int abs_off, rel_off;
821
822 /* copy e8 block to the e8 buffer and tweak if needed */
823 lzx->o_ptr = data;
824 memcpy(data, &lzx->window[lzx->frame_posn], frame_size);
825
826 while (data < dataend) {
827 if (*data++ != 0xE8) { curpos++; continue; }
828 abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
829 if ((abs_off >= -curpos) && (abs_off < filesize)) {
830 rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
831 data[0] = (unsigned char) rel_off;
832 data[1] = (unsigned char) (rel_off >> 8);
833 data[2] = (unsigned char) (rel_off >> 16);
834 data[3] = (unsigned char) (rel_off >> 24);
835 }
836 data += 4;
837 curpos += 5;
838 }
839 lzx->intel_curpos += frame_size;
840 }
841 else {
842 lzx->o_ptr = &lzx->window[lzx->frame_posn];
843 if (lzx->intel_filesize) lzx->intel_curpos += frame_size;
844 }
845 lzx->o_end = &lzx->o_ptr[frame_size];
846
847 /* write a frame */
848 i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size;
849 if (fwrite(lzx->o_ptr, 1, i, lzx->output) != i) {
850 return lzx->error = LZX_ERR_WRITE;
851 }
852 lzx->o_ptr += i;
853 lzx->offset += i;
854 out_bytes -= i;
855
856 /* advance frame start position */
857 lzx->frame_posn += frame_size;
858 lzx->frame++;
859
860 /* wrap window / frame position pointers */
861 if (window_posn == lzx->window_size) window_posn = 0;
862 if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0;
863
864 } /* while (lzx->frame < end_frame) */
865
866 if (out_bytes) {
867 D(("bytes left to output"))
868 return lzx->error = LZX_ERR_DECRUNCH;
869 }
870
871 /* store local state */
872 STORE_BITS;
873 lzx->window_posn = window_posn;
874 lzx->R0 = R0;
875 lzx->R1 = R1;
876 lzx->R2 = R2;
877
878 return LZX_ERR_OK;
879 }
880
881 void ews_lzxd_free(struct lzxd_stream *lzx) {
882 if (lzx) {
883 free(lzx->inbuf);
884 free(lzx->window);
885 free(lzx);
886 }
887 }