summaryrefslogtreecommitdiff
path: root/rbutil/rbutilqt/mspack/lzxd.c
diff options
context:
space:
mode:
Diffstat (limited to 'rbutil/rbutilqt/mspack/lzxd.c')
-rw-r--r--rbutil/rbutilqt/mspack/lzxd.c738
1 files changed, 738 insertions, 0 deletions
diff --git a/rbutil/rbutilqt/mspack/lzxd.c b/rbutil/rbutilqt/mspack/lzxd.c
new file mode 100644
index 0000000000..cebc4c23d3
--- /dev/null
+++ b/rbutil/rbutilqt/mspack/lzxd.c
@@ -0,0 +1,738 @@
1/* This file is part of libmspack.
2 * (C) 2003-2004 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 <system.h>
16#include <lzx.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 * The format now allows for "reference data", supplied by the caller.
74 * If match offsets go further back than the number of bytes
75 * decompressed so far, that is them accessing the reference data.
76 */
77
78/* import bit-reading macros and code */
79#define BITS_TYPE struct lzxd_stream
80#define BITS_VAR lzx
81#define BITS_ORDER_MSB
82#define READ_BYTES do { \
83 unsigned char b0, b1; \
84 READ_IF_NEEDED; b0 = *i_ptr++; \
85 READ_IF_NEEDED; b1 = *i_ptr++; \
86 INJECT_BITS((b1 << 8) | b0, 16); \
87} while (0)
88#include <readbits.h>
89
90/* import huffman-reading macros and code */
91#define TABLEBITS(tbl) LZX_##tbl##_TABLEBITS
92#define MAXSYMBOLS(tbl) LZX_##tbl##_MAXSYMBOLS
93#define HUFF_TABLE(tbl,idx) lzx->tbl##_table[idx]
94#define HUFF_LEN(tbl,idx) lzx->tbl##_len[idx]
95#define HUFF_ERROR return lzx->error = MSPACK_ERR_DECRUNCH
96#include <readhuff.h>
97
98/* BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */
99#define BUILD_TABLE(tbl) \
100 if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \
101 &HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \
102 { \
103 D(("failed to build %s table", #tbl)) \
104 return lzx->error = MSPACK_ERR_DECRUNCH; \
105 }
106
107#define BUILD_TABLE_MAYBE_EMPTY(tbl) do { \
108 lzx->tbl##_empty = 0; \
109 if (make_decode_table(MAXSYMBOLS(tbl), TABLEBITS(tbl), \
110 &HUFF_LEN(tbl,0), &HUFF_TABLE(tbl,0))) \
111 { \
112 for (i = 0; i < MAXSYMBOLS(tbl); i++) { \
113 if (HUFF_LEN(tbl, i) > 0) { \
114 D(("failed to build %s table", #tbl)) \
115 return lzx->error = MSPACK_ERR_DECRUNCH; \
116 } \
117 } \
118 /* empty tree - allow it, but don't decode symbols with it */ \
119 lzx->tbl##_empty = 1; \
120 } \
121} while (0)
122
123/* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
124 * first to last in the given table. The code lengths are stored in their
125 * own special LZX way.
126 */
127#define READ_LENGTHS(tbl, first, last) do { \
128 STORE_BITS; \
129 if (lzxd_read_lens(lzx, &HUFF_LEN(tbl, 0), (first), \
130 (unsigned int)(last))) return lzx->error; \
131 RESTORE_BITS; \
132} while (0)
133
134static int lzxd_read_lens(struct lzxd_stream *lzx, unsigned char *lens,
135 unsigned int first, unsigned int last)
136{
137 /* bit buffer and huffman symbol decode variables */
138 register unsigned int bit_buffer;
139 register int bits_left, i;
140 register unsigned short sym;
141 unsigned char *i_ptr, *i_end;
142
143 unsigned int x, y;
144 int z;
145
146 RESTORE_BITS;
147
148 /* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */
149 for (x = 0; x < 20; x++) {
150 READ_BITS(y, 4);
151 lzx->PRETREE_len[x] = y;
152 }
153 BUILD_TABLE(PRETREE);
154
155 for (x = first; x < last; ) {
156 READ_HUFFSYM(PRETREE, z);
157 if (z == 17) {
158 /* code = 17, run of ([read 4 bits]+4) zeros */
159 READ_BITS(y, 4); y += 4;
160 while (y--) lens[x++] = 0;
161 }
162 else if (z == 18) {
163 /* code = 18, run of ([read 5 bits]+20) zeros */
164 READ_BITS(y, 5); y += 20;
165 while (y--) lens[x++] = 0;
166 }
167 else if (z == 19) {
168 /* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */
169 READ_BITS(y, 1); y += 4;
170 READ_HUFFSYM(PRETREE, z);
171 z = lens[x] - z; if (z < 0) z += 17;
172 while (y--) lens[x++] = z;
173 }
174 else {
175 /* code = 0 to 16, delta current length entry */
176 z = lens[x] - z; if (z < 0) z += 17;
177 lens[x++] = z;
178 }
179 }
180
181 STORE_BITS;
182
183 return MSPACK_ERR_OK;
184}
185
186/* LZX static data tables:
187 *
188 * LZX uses 'position slots' to represent match offsets. For every match,
189 * a small 'position slot' number and a small offset from that slot are
190 * encoded instead of one large offset.
191 *
192 * position_base[] is an index to the position slot bases
193 *
194 * extra_bits[] states how many bits of offset-from-base data is needed.
195 *
196 * They are generated like so:
197 * for (i = 0; i < 4; i++) extra_bits[i] = 0;
198 * for (i = 4, j = 0; i < 36; i+=2) extra_bits[i] = extra_bits[i+1] = j++;
199 * for (i = 36; i < 51; i++) extra_bits[i] = 17;
200 * for (i = 0, j = 0; i < 51; j += 1 << extra_bits[i++]) position_base[i] = j;
201 */
202static const unsigned int position_base[51] = {
203 0, 1, 2, 3, 4, 6, 8, 12, 16, 24, 32, 48, 64, 96, 128, 192, 256,
204 384, 512, 768, 1024, 1536, 2048, 3072, 4096, 6144, 8192, 12288,
205 16384, 24576, 32768, 49152, 65536, 98304, 131072, 196608, 262144,
206 393216, 524288, 655360, 786432, 917504, 1048576, 1179648, 1310720,
207 1441792, 1572864, 1703936, 1835008, 1966080, 2097152
208};
209static const unsigned char extra_bits[51] = {
210 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
211 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16,
212 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17
213};
214
215static void lzxd_reset_state(struct lzxd_stream *lzx) {
216 int i;
217
218 lzx->R0 = 1;
219 lzx->R1 = 1;
220 lzx->R2 = 1;
221 lzx->header_read = 0;
222 lzx->block_remaining = 0;
223 lzx->block_type = LZX_BLOCKTYPE_INVALID;
224
225 /* initialise tables to 0 (because deltas will be applied to them) */
226 for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0;
227 for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0;
228}
229
230/*-------- main LZX code --------*/
231
232struct lzxd_stream *lzxd_init(struct mspack_system *system,
233 struct mspack_file *input,
234 struct mspack_file *output,
235 int window_bits,
236 int reset_interval,
237 int input_buffer_size,
238 off_t output_length)
239{
240 unsigned int window_size = 1 << window_bits;
241 struct lzxd_stream *lzx;
242
243 if (!system) return NULL;
244
245 /* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
246 if (window_bits < 15 || window_bits > 21) return NULL;
247
248 input_buffer_size = (input_buffer_size + 1) & -2;
249 if (!input_buffer_size) return NULL;
250
251 /* allocate decompression state */
252 if (!(lzx = (struct lzxd_stream *) system->alloc(system, sizeof(struct lzxd_stream)))) {
253 return NULL;
254 }
255
256 /* allocate decompression window and input buffer */
257 lzx->window = (unsigned char *) system->alloc(system, (size_t) window_size);
258 lzx->inbuf = (unsigned char *) system->alloc(system, (size_t) input_buffer_size);
259 if (!lzx->window || !lzx->inbuf) {
260 system->free(lzx->window);
261 system->free(lzx->inbuf);
262 system->free(lzx);
263 return NULL;
264 }
265
266 /* initialise decompression state */
267 lzx->sys = system;
268 lzx->input = input;
269 lzx->output = output;
270 lzx->offset = 0;
271 lzx->length = output_length;
272
273 lzx->inbuf_size = input_buffer_size;
274 lzx->window_size = 1 << window_bits;
275 lzx->window_posn = 0;
276 lzx->frame_posn = 0;
277 lzx->frame = 0;
278 lzx->reset_interval = reset_interval;
279 lzx->intel_filesize = 0;
280 lzx->intel_curpos = 0;
281 lzx->intel_started = 0;
282 lzx->error = MSPACK_ERR_OK;
283
284 /* window bits: 15 16 17 18 19 20 21
285 * position slots: 30 32 34 36 38 42 50 */
286 lzx->posn_slots = ((window_bits == 21) ? 50 :
287 ((window_bits == 20) ? 42 : (window_bits << 1)));
288
289 lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0];
290 lzxd_reset_state(lzx);
291 INIT_BITS;
292 return lzx;
293}
294
295void lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) {
296 if (lzx) lzx->length = out_bytes;
297}
298
299int lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes) {
300 /* bitstream and huffman reading variables */
301 register unsigned int bit_buffer;
302 register int bits_left, i=0;
303 unsigned char *i_ptr, *i_end;
304 register unsigned short sym;
305
306 int match_length, length_footer, extra, verbatim_bits, bytes_todo;
307 int this_run, main_element, aligned_bits, j;
308 unsigned char *window, *runsrc, *rundest, buf[12];
309 unsigned int frame_size=0, end_frame, match_offset, window_posn;
310 unsigned int R0, R1, R2;
311
312 /* easy answers */
313 if (!lzx || (out_bytes < 0)) return MSPACK_ERR_ARGS;
314 if (lzx->error) return lzx->error;
315
316 /* flush out any stored-up bytes before we begin */
317 i = lzx->o_end - lzx->o_ptr;
318 if ((off_t) i > out_bytes) i = (int) out_bytes;
319 if (i) {
320 if (lzx->sys->write(lzx->output, lzx->o_ptr, i) != i) {
321 return lzx->error = MSPACK_ERR_WRITE;
322 }
323 lzx->o_ptr += i;
324 lzx->offset += i;
325 out_bytes -= i;
326 }
327 if (out_bytes == 0) return MSPACK_ERR_OK;
328
329 /* restore local state */
330 RESTORE_BITS;
331 window = lzx->window;
332 window_posn = lzx->window_posn;
333 R0 = lzx->R0;
334 R1 = lzx->R1;
335 R2 = lzx->R2;
336
337 end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1;
338
339 while (lzx->frame < end_frame) {
340 /* have we reached the reset interval? (if there is one?) */
341 if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) {
342 if (lzx->block_remaining) {
343 D(("%d bytes remaining at reset interval", lzx->block_remaining))
344 return lzx->error = MSPACK_ERR_DECRUNCH;
345 }
346
347 /* re-read the intel header and reset the huffman lengths */
348 lzxd_reset_state(lzx);
349 R0 = lzx->R0;
350 R1 = lzx->R1;
351 R2 = lzx->R2;
352 }
353
354 /* read header if necessary */
355 if (!lzx->header_read) {
356 /* read 1 bit. if bit=0, intel filesize = 0.
357 * if bit=1, read intel filesize (32 bits) */
358 j = 0; READ_BITS(i, 1); if (i) { READ_BITS(i, 16); READ_BITS(j, 16); }
359 lzx->intel_filesize = (i << 16) | j;
360 lzx->header_read = 1;
361 }
362
363 /* calculate size of frame: all frames are 32k except the final frame
364 * which is 32kb or less. this can only be calculated when lzx->length
365 * has been filled in. */
366 frame_size = LZX_FRAME_SIZE;
367 if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) {
368 frame_size = lzx->length - lzx->offset;
369 }
370
371 /* decode until one more frame is available */
372 bytes_todo = lzx->frame_posn + frame_size - window_posn;
373 while (bytes_todo > 0) {
374 /* initialise new block, if one is needed */
375 if (lzx->block_remaining == 0) {
376 /* realign if previous block was an odd-sized UNCOMPRESSED block */
377 if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) &&
378 (lzx->block_length & 1))
379 {
380 READ_IF_NEEDED;
381 i_ptr++;
382 }
383
384 /* read block type (3 bits) and block length (24 bits) */
385 READ_BITS(lzx->block_type, 3);
386 READ_BITS(i, 16); READ_BITS(j, 8);
387 lzx->block_remaining = lzx->block_length = (i << 8) | j;
388 /*D(("new block t%d len %u", lzx->block_type, lzx->block_length))*/
389
390 /* read individual block headers */
391 switch (lzx->block_type) {
392 case LZX_BLOCKTYPE_ALIGNED:
393 /* read lengths of and build aligned huffman decoding tree */
394 for (i = 0; i < 8; i++) { READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; }
395 BUILD_TABLE(ALIGNED);
396 /* no break -- rest of aligned header is same as verbatim */
397 case LZX_BLOCKTYPE_VERBATIM:
398 /* read lengths of and build main huffman decoding tree */
399 READ_LENGTHS(MAINTREE, 0, 256);
400 READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + (lzx->posn_slots << 3));
401 BUILD_TABLE(MAINTREE);
402 /* if the literal 0xE8 is anywhere in the block... */
403 if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1;
404 /* read lengths of and build lengths huffman decoding tree */
405 READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
406 BUILD_TABLE_MAYBE_EMPTY(LENGTH);
407 break;
408
409 case LZX_BLOCKTYPE_UNCOMPRESSED:
410 /* because we can't assume otherwise */
411 lzx->intel_started = 1;
412
413 /* read 1-16 (not 0-15) bits to align to bytes */
414 ENSURE_BITS(16);
415 if (bits_left > 16) i_ptr -= 2;
416 bits_left = 0; bit_buffer = 0;
417
418 /* read 12 bytes of stored R0 / R1 / R2 values */
419 for (rundest = &buf[0], i = 0; i < 12; i++) {
420 READ_IF_NEEDED;
421 *rundest++ = *i_ptr++;
422 }
423 R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24);
424 R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24);
425 R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24);
426 break;
427
428 default:
429 D(("bad block type"))
430 return lzx->error = MSPACK_ERR_DECRUNCH;
431 }
432 }
433
434 /* decode more of the block:
435 * run = min(what's available, what's needed) */
436 this_run = lzx->block_remaining;
437 if (this_run > bytes_todo) this_run = bytes_todo;
438
439 /* assume we decode exactly this_run bytes, for now */
440 bytes_todo -= this_run;
441 lzx->block_remaining -= this_run;
442
443 /* decode at least this_run bytes */
444 switch (lzx->block_type) {
445 case LZX_BLOCKTYPE_VERBATIM:
446 while (this_run > 0) {
447 READ_HUFFSYM(MAINTREE, main_element);
448 if (main_element < LZX_NUM_CHARS) {
449 /* literal: 0 to LZX_NUM_CHARS-1 */
450 window[window_posn++] = main_element;
451 this_run--;
452 }
453 else {
454 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
455 main_element -= LZX_NUM_CHARS;
456
457 /* get match length */
458 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
459 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
460 if (lzx->LENGTH_empty) {
461 D(("LENGTH symbol needed but tree is empty"))
462 return lzx->error = MSPACK_ERR_DECRUNCH;
463 }
464 READ_HUFFSYM(LENGTH, length_footer);
465 match_length += length_footer;
466 }
467 match_length += LZX_MIN_MATCH;
468
469 /* get match offset */
470 switch ((match_offset = (main_element >> 3))) {
471 case 0: match_offset = R0; break;
472 case 1: match_offset = R1; R1=R0; R0 = match_offset; break;
473 case 2: match_offset = R2; R2=R0; R0 = match_offset; break;
474 case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break;
475 default:
476 extra = extra_bits[match_offset];
477 READ_BITS(verbatim_bits, extra);
478 match_offset = position_base[match_offset] - 2 + verbatim_bits;
479 R2 = R1; R1 = R0; R0 = match_offset;
480 }
481
482 if ((window_posn + match_length) > lzx->window_size) {
483 D(("match ran over window wrap"))
484 return lzx->error = MSPACK_ERR_DECRUNCH;
485 }
486
487 /* copy match */
488 rundest = &window[window_posn];
489 i = match_length;
490 /* does match offset wrap the window? */
491 if (match_offset > window_posn) {
492 /* j = length from match offset to end of window */
493 j = match_offset - window_posn;
494 if (j > (int) lzx->window_size) {
495 D(("match offset beyond window boundaries"))
496 return lzx->error = MSPACK_ERR_DECRUNCH;
497 }
498 runsrc = &window[lzx->window_size - j];
499 if (j < i) {
500 /* if match goes over the window edge, do two copy runs */
501 i -= j; while (j-- > 0) *rundest++ = *runsrc++;
502 runsrc = window;
503 }
504 while (i-- > 0) *rundest++ = *runsrc++;
505 }
506 else {
507 runsrc = rundest - match_offset;
508 while (i-- > 0) *rundest++ = *runsrc++;
509 }
510
511 this_run -= match_length;
512 window_posn += match_length;
513 }
514 } /* while (this_run > 0) */
515 break;
516
517 case LZX_BLOCKTYPE_ALIGNED:
518 while (this_run > 0) {
519 READ_HUFFSYM(MAINTREE, main_element);
520 if (main_element < LZX_NUM_CHARS) {
521 /* literal: 0 to LZX_NUM_CHARS-1 */
522 window[window_posn++] = main_element;
523 this_run--;
524 }
525 else {
526 /* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
527 main_element -= LZX_NUM_CHARS;
528
529 /* get match length */
530 match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
531 if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
532 if (lzx->LENGTH_empty) {
533 D(("LENGTH symbol needed but tree is empty"))
534 return lzx->error = MSPACK_ERR_DECRUNCH;
535 }
536 READ_HUFFSYM(LENGTH, length_footer);
537 match_length += length_footer;
538 }
539 match_length += LZX_MIN_MATCH;
540
541 /* get match offset */
542 switch ((match_offset = (main_element >> 3))) {
543 case 0: match_offset = R0; break;
544 case 1: match_offset = R1; R1 = R0; R0 = match_offset; break;
545 case 2: match_offset = R2; R2 = R0; R0 = match_offset; break;
546 default:
547 extra = extra_bits[match_offset];
548 match_offset = position_base[match_offset] - 2;
549 if (extra > 3) {
550 /* verbatim and aligned bits */
551 extra -= 3;
552 READ_BITS(verbatim_bits, extra);
553 match_offset += (verbatim_bits << 3);
554 READ_HUFFSYM(ALIGNED, aligned_bits);
555 match_offset += aligned_bits;
556 }
557 else if (extra == 3) {
558 /* aligned bits only */
559 READ_HUFFSYM(ALIGNED, aligned_bits);
560 match_offset += aligned_bits;
561 }
562 else if (extra > 0) { /* extra==1, extra==2 */
563 /* verbatim bits only */
564 READ_BITS(verbatim_bits, extra);
565 match_offset += verbatim_bits;
566 }
567 else /* extra == 0 */ {
568 /* ??? not defined in LZX specification! */
569 match_offset = 1;
570 }
571 /* update repeated offset LRU queue */
572 R2 = R1; R1 = R0; R0 = match_offset;
573 }
574
575 if ((window_posn + match_length) > lzx->window_size) {
576 D(("match ran over window wrap"))
577 return lzx->error = MSPACK_ERR_DECRUNCH;
578 }
579
580 /* copy match */
581 rundest = &window[window_posn];
582 i = match_length;
583 /* does match offset wrap the window? */
584 if (match_offset > window_posn) {
585 /* j = length from match offset to end of window */
586 j = match_offset - window_posn;
587 if (j > (int) lzx->window_size) {
588 D(("match offset beyond window boundaries"))
589 return lzx->error = MSPACK_ERR_DECRUNCH;
590 }
591 runsrc = &window[lzx->window_size - j];
592 if (j < i) {
593 /* if match goes over the window edge, do two copy runs */
594 i -= j; while (j-- > 0) *rundest++ = *runsrc++;
595 runsrc = window;
596 }
597 while (i-- > 0) *rundest++ = *runsrc++;
598 }
599 else {
600 runsrc = rundest - match_offset;
601 while (i-- > 0) *rundest++ = *runsrc++;
602 }
603
604 this_run -= match_length;
605 window_posn += match_length;
606 }
607 } /* while (this_run > 0) */
608 break;
609
610 case LZX_BLOCKTYPE_UNCOMPRESSED:
611 /* as this_run is limited not to wrap a frame, this also means it
612 * won't wrap the window (as the window is a multiple of 32k) */
613 rundest = &window[window_posn];
614 window_posn += this_run;
615 while (this_run > 0) {
616 if ((i = i_end - i_ptr) == 0) {
617 READ_IF_NEEDED;
618 }
619 else {
620 if (i > this_run) i = this_run;
621 lzx->sys->copy(i_ptr, rundest, (size_t) i);
622 rundest += i;
623 i_ptr += i;
624 this_run -= i;
625 }
626 }
627 break;
628
629 default:
630 return lzx->error = MSPACK_ERR_DECRUNCH; /* might as well */
631 }
632
633 /* did the final match overrun our desired this_run length? */
634 if (this_run < 0) {
635 if ((unsigned int)(-this_run) > lzx->block_remaining) {
636 D(("overrun went past end of block by %d (%d remaining)",
637 -this_run, lzx->block_remaining ))
638 return lzx->error = MSPACK_ERR_DECRUNCH;
639 }
640 lzx->block_remaining -= -this_run;
641 }
642 } /* while (bytes_todo > 0) */
643
644 /* streams don't extend over frame boundaries */
645 if ((window_posn - lzx->frame_posn) != frame_size) {
646 D(("decode beyond output frame limits! %d != %d",
647 window_posn - lzx->frame_posn, frame_size))
648 return lzx->error = MSPACK_ERR_DECRUNCH;
649 }
650
651 /* re-align input bitstream */
652 if (bits_left > 0) ENSURE_BITS(16);
653 if (bits_left & 15) REMOVE_BITS(bits_left & 15);
654
655 /* check that we've used all of the previous frame first */
656 if (lzx->o_ptr != lzx->o_end) {
657 D(("%ld avail bytes, new %d frame", lzx->o_end-lzx->o_ptr, frame_size))
658 return lzx->error = MSPACK_ERR_DECRUNCH;
659 }
660
661 /* does this intel block _really_ need decoding? */
662 if (lzx->intel_started && lzx->intel_filesize &&
663 (lzx->frame <= 32768) && (frame_size > 10))
664 {
665 unsigned char *data = &lzx->e8_buf[0];
666 unsigned char *dataend = &lzx->e8_buf[frame_size - 10];
667 signed int curpos = lzx->intel_curpos;
668 signed int filesize = lzx->intel_filesize;
669 signed int abs_off, rel_off;
670
671 /* copy e8 block to the e8 buffer and tweak if needed */
672 lzx->o_ptr = data;
673 lzx->sys->copy(&lzx->window[lzx->frame_posn], data, frame_size);
674
675 while (data < dataend) {
676 if (*data++ != 0xE8) { curpos++; continue; }
677 abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
678 if ((abs_off >= -curpos) && (abs_off < filesize)) {
679 rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
680 data[0] = (unsigned char) rel_off;
681 data[1] = (unsigned char) (rel_off >> 8);
682 data[2] = (unsigned char) (rel_off >> 16);
683 data[3] = (unsigned char) (rel_off >> 24);
684 }
685 data += 4;
686 curpos += 5;
687 }
688 lzx->intel_curpos += frame_size;
689 }
690 else {
691 lzx->o_ptr = &lzx->window[lzx->frame_posn];
692 if (lzx->intel_filesize) lzx->intel_curpos += frame_size;
693 }
694 lzx->o_end = &lzx->o_ptr[frame_size];
695
696 /* write a frame */
697 i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size;
698 if (lzx->sys->write(lzx->output, lzx->o_ptr, i) != i) {
699 return lzx->error = MSPACK_ERR_WRITE;
700 }
701 lzx->o_ptr += i;
702 lzx->offset += i;
703 out_bytes -= i;
704
705 /* advance frame start position */
706 lzx->frame_posn += frame_size;
707 lzx->frame++;
708
709 /* wrap window / frame position pointers */
710 if (window_posn == lzx->window_size) window_posn = 0;
711 if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0;
712
713 } /* while (lzx->frame < end_frame) */
714
715 if (out_bytes) {
716 D(("bytes left to output"))
717 return lzx->error = MSPACK_ERR_DECRUNCH;
718 }
719
720 /* store local state */
721 STORE_BITS;
722 lzx->window_posn = window_posn;
723 lzx->R0 = R0;
724 lzx->R1 = R1;
725 lzx->R2 = R2;
726
727 return MSPACK_ERR_OK;
728}
729
730void lzxd_free(struct lzxd_stream *lzx) {
731 struct mspack_system *sys;
732 if (lzx) {
733 sys = lzx->sys;
734 sys->free(lzx->inbuf);
735 sys->free(lzx->window);
736 sys->free(lzx);
737 }
738}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-19 08:31:39 +0000