1
/* This file is part of libmspack.
2
* (C) 2003-2004 Stuart Caie.
4
* The LZX method was created by Jonathan Forbes and Tomi Poutanen, adapted
5
* by Microsoft Corporation.
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
10
* For further details, see the file COPYING.LIB distributed with libmspack
13
/* LZX decompression implementation */
16
#include "clamav-config.h"
23
/* Microsoft's LZX document and their implementation of the
24
* com.ms.util.cab Java package do not concur.
26
* In the LZX document, there is a table showing the correlation between
27
* window size and the number of position slots. It states that the 1MB
28
* window = 40 slots and the 2MB window = 42 slots. In the implementation,
29
* 1MB = 42 slots, 2MB = 50 slots. The actual calculation is 'find the
30
* first slot whose position base is equal to or more than the required
31
* window size'. This would explain why other tables in the document refer
32
* to 50 slots rather than 42.
34
* The constant NUM_PRIMARY_LENGTHS used in the decompression pseudocode
35
* is not defined in the specification.
37
* The LZX document does not state the uncompressed block has an
38
* uncompressed length field. Where does this length field come from, so
39
* we can know how large the block is? The implementation has it as the 24
40
* bits following after the 3 blocktype bits, before the alignment
43
* The LZX document states that aligned offset blocks have their aligned
44
* offset huffman tree AFTER the main and length trees. The implementation
45
* suggests that the aligned offset tree is BEFORE the main and length
48
* The LZX document decoding algorithm states that, in an aligned offset
49
* block, if an extra_bits value is 1, 2 or 3, then that number of bits
50
* should be read and the result added to the match offset. This is
51
* correct for 1 and 2, but not 3, where just a huffman symbol (using the
52
* aligned tree) should be read.
54
* Regarding the E8 preprocessing, the LZX document states 'No translation
55
* may be performed on the last 6 bytes of the input block'. This is
56
* correct. However, the pseudocode provided checks for the *E8 leader*
57
* up to the last 6 bytes. If the leader appears between -10 and -7 bytes
58
* from the end, this would cause the next four bytes to be modified, at
59
* least one of which would be in the last 6 bytes, which is not allowed
60
* according to the spec.
62
* The specification states that the huffman trees must always contain at
63
* least one element. However, many CAB files contain blocks where the
64
* length tree is completely empty (because there are no matches), and
65
* this is expected to succeed.
69
/* LZX decompressor input macros
71
* STORE_BITS stores bitstream state in lzxd_stream structure
72
* RESTORE_BITS restores bitstream state from lzxd_stream structure
73
* READ_BITS(var,n) takes N bits from the buffer and puts them in var
74
* ENSURE_BITS(n) ensures there are at least N bits in the bit buffer.
75
* PEEK_BITS(n) extracts without removing N bits from the bit buffer
76
* REMOVE_BITS(n) removes N bits from the bit buffer
78
* These bit access routines work by using the area beyond the MSB and the
79
* LSB as a free source of zeroes when shifting. This avoids having to
80
* mask any bits. So we have to know the bit width of the bit buffer
83
* The bit buffer datatype should be at least 32 bits wide: it must be
84
* possible to ENSURE_BITS(16), so it must be possible to add 16 new bits
85
* to the bit buffer when the bit buffer already has 1 to 15 bits left.
94
#define BITBUF_WIDTH (sizeof(bit_buffer) * CHAR_BIT)
96
#define STORE_BITS do { \
99
lzx->bit_buffer = bit_buffer; \
100
lzx->bits_left = bits_left; \
103
#define RESTORE_BITS do { \
104
i_ptr = lzx->i_ptr; \
105
i_end = lzx->i_end; \
106
bit_buffer = lzx->bit_buffer; \
107
bits_left = lzx->bits_left; \
110
#define ENSURE_BITS(nbits) \
111
while (bits_left < (nbits)) { \
112
if (i_ptr >= i_end) { \
113
if (lzxd_read_input(lzx)) return lzx->error; \
114
i_ptr = lzx->i_ptr; \
115
i_end = lzx->i_end; \
117
bit_buffer |= ((i_ptr[1] << 8) | i_ptr[0]) \
118
<< (BITBUF_WIDTH - 16 - bits_left); \
123
#define PEEK_BITS(nbits) (bit_buffer >> (BITBUF_WIDTH - (nbits)))
125
#define REMOVE_BITS(nbits) ((bit_buffer <<= (nbits)), (bits_left -= (nbits)))
127
#define READ_BITS(val, nbits) do { \
128
ENSURE_BITS(nbits); \
129
(val) = PEEK_BITS(nbits); \
130
REMOVE_BITS(nbits); \
133
static int lzxd_read_input(struct lzxd_stream *lzx) {
134
int read = lzx->sys->read(lzx->input, &lzx->inbuf[0], (int)lzx->inbuf_size);
135
if (read < 0) return lzx->error = MSPACK_ERR_READ;
137
/* huff decode's ENSURE_BYTES(16) might overrun the input stream, even
138
* if those bits aren't used, so fake 2 more bytes */
140
if (lzx->input_end) {
141
D(("out of input bytes"))
142
return lzx->error = MSPACK_ERR_READ;
146
lzx->inbuf[0] = lzx->inbuf[1] = 0;
151
lzx->i_ptr = &lzx->inbuf[0];
152
lzx->i_end = &lzx->inbuf[read];
154
return MSPACK_ERR_OK;
157
/* Huffman decoding macros */
159
/* READ_HUFFSYM(tablename, var) decodes one huffman symbol from the
160
* bitstream using the stated table and puts it in var.
162
#define READ_HUFFSYM(tbl, var) do { \
163
/* huffman symbols can be up to 16 bits long */ \
165
/* immediate table lookup of [tablebits] bits of the code */ \
166
sym = lzx->tbl##_table[PEEK_BITS(LZX_##tbl##_TABLEBITS)]; \
167
/* is the symbol is longer than [tablebits] bits? (i=node index) */ \
168
if (sym >= LZX_##tbl##_MAXSYMBOLS) { \
169
/* decode remaining bits by tree traversal */ \
170
i = 1 << (BITBUF_WIDTH - LZX_##tbl##_TABLEBITS); \
172
/* one less bit. error if we run out of bits before decode */ \
175
D(("out of bits in huffman decode")) \
176
return lzx->error = MSPACK_ERR_DECRUNCH; \
178
/* double node index and add 0 (left branch) or 1 (right) */ \
179
sym <<= 1; sym |= (bit_buffer & i) ? 1 : 0; \
180
/* hop to next node index / decoded symbol */ \
181
sym = lzx->tbl##_table[sym]; \
182
/* while we are still in node indicies, not decoded symbols */ \
183
} while (sym >= LZX_##tbl##_MAXSYMBOLS); \
187
/* look up the code length of that symbol and discard those bits */ \
188
i = lzx->tbl##_len[sym]; \
192
/* BUILD_TABLE(tbl) builds a huffman lookup table from code lengths */
193
#define BUILD_TABLE(tbl) \
194
if (make_decode_table(LZX_##tbl##_MAXSYMBOLS, LZX_##tbl##_TABLEBITS, \
195
&lzx->tbl##_len[0], &lzx->tbl##_table[0])) \
197
D(("failed to build %s table", #tbl)) \
198
return lzx->error = MSPACK_ERR_DECRUNCH; \
201
/* make_decode_table(nsyms, nbits, length[], table[])
203
* This function was coded by David Tritscher. It builds a fast huffman
204
* decoding table from a canonical huffman code lengths table.
206
* nsyms = total number of symbols in this huffman tree.
207
* nbits = any symbols with a code length of nbits or less can be decoded
208
* in one lookup of the table.
209
* length = A table to get code lengths from [0 to syms-1]
210
* table = The table to fill up with decoded symbols and pointers.
212
* Returns 0 for OK or 1 for error
215
static int make_decode_table(unsigned int nsyms, unsigned int nbits,
216
unsigned char *length, unsigned short *table)
218
register unsigned short sym;
219
register unsigned int leaf, fill;
220
register unsigned char bit_num;
221
unsigned int pos = 0; /* the current position in the decode table */
222
unsigned int table_mask = 1 << nbits;
223
unsigned int bit_mask = table_mask >> 1; /* don't do 0 length codes */
224
unsigned int next_symbol = bit_mask; /* base of allocation for long codes */
226
/* fill entries for codes short enough for a direct mapping */
227
for (bit_num = 1; bit_num <= nbits; bit_num++) {
228
for (sym = 0; sym < nsyms; sym++) {
229
if (length[sym] != bit_num) continue;
231
if((pos += bit_mask) > table_mask) return 1; /* table overrun */
232
/* fill all possible lookups of this symbol with the symbol itself */
233
for (fill = bit_mask; fill-- > 0;) table[leaf++] = sym;
238
/* full table already? */
239
if (pos == table_mask) return 0;
241
/* clear the remainder of the table */
242
for (sym = pos; sym < table_mask; sym++) table[sym] = 0xFFFF;
244
/* allow codes to be up to nbits+16 long, instead of nbits */
249
for (bit_num = nbits+1; bit_num <= 16; bit_num++) {
250
for (sym = 0; sym < nsyms; sym++) {
251
if (length[sym] != bit_num) continue;
254
for (fill = 0; fill < bit_num - nbits; fill++) {
255
/* if this path hasn't been taken yet, 'allocate' two entries */
256
if (table[leaf] == 0xFFFF) {
257
table[(next_symbol << 1)] = 0xFFFF;
258
table[(next_symbol << 1) + 1] = 0xFFFF;
259
table[leaf] = next_symbol++;
261
/* follow the path and select either left or right for next bit */
262
leaf = table[leaf] << 1;
263
if ((pos >> (15-fill)) & 1) leaf++;
267
if ((pos += bit_mask) > table_mask) return 1; /* table overflow */
273
if (pos == table_mask) return 0;
275
/* either erroneous table, or all elements are 0 - let's find out. */
276
for (sym = 0; sym < nsyms; sym++) if (length[sym]) return 1;
281
/* READ_LENGTHS(tablename, first, last) reads in code lengths for symbols
282
* first to last in the given table. The code lengths are stored in their
283
* own special LZX way.
285
#define READ_LENGTHS(tbl, first, last) do { \
287
if (lzxd_read_lens(lzx, &lzx->tbl##_len[0], (first), \
288
(unsigned int)(last))) return lzx->error; \
292
static int lzxd_read_lens(struct lzxd_stream *lzx, unsigned char *lens,
293
unsigned int first, unsigned int last)
295
/* bit buffer and huffman symbol decode variables */
296
register unsigned int bit_buffer;
297
register int bits_left, i;
298
register unsigned short sym;
299
unsigned char *i_ptr, *i_end;
306
/* read lengths for pretree (20 symbols, lengths stored in fixed 4 bits) */
307
for (x = 0; x < 20; x++) {
309
lzx->PRETREE_len[x] = y;
311
BUILD_TABLE(PRETREE);
313
for (x = first; x < last; ) {
314
READ_HUFFSYM(PRETREE, z);
316
/* code = 17, run of ([read 4 bits]+4) zeros */
317
READ_BITS(y, 4); y += 4;
318
while (y--) lens[x++] = 0;
321
/* code = 18, run of ([read 5 bits]+20) zeros */
322
READ_BITS(y, 5); y += 20;
323
while (y--) lens[x++] = 0;
326
/* code = 19, run of ([read 1 bit]+4) [read huffman symbol] */
327
READ_BITS(y, 1); y += 4;
328
READ_HUFFSYM(PRETREE, z);
329
z = lens[x] - z; if (z < 0) z += 17;
330
while (y--) lens[x++] = z;
333
/* code = 0 to 16, delta current length entry */
334
z = lens[x] - z; if (z < 0) z += 17;
341
return MSPACK_ERR_OK;
344
/* LZX static data tables:
346
* LZX uses 'position slots' to represent match offsets. For every match,
347
* a small 'position slot' number and a small offset from that slot are
348
* encoded instead of one large offset.
350
* position_base[] is an index to the position slot bases
352
* extra_bits[] states how many bits of offset-from-base data is needed.
354
static unsigned int position_base[51];
355
static unsigned char extra_bits[51];
357
static void lzxd_static_init() {
360
for (i = 0, j = 0; i < 51; i += 2) {
361
extra_bits[i] = j; /* 0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7... */
364
if ((i != 0) && (j < 17)) j++; /* 0,0,1,2,3,4...15,16,17,17,17,17... */
367
for (i = 0, j = 0; i < 51; i++) {
368
position_base[i] = j; /* 0,1,2,3,4,6,8,12,16,24,32,... */
369
j += 1 << extra_bits[i]; /* 1,1,1,1,2,2,4,4,8,8,16,16,32,32,... */
373
static void lzxd_reset_state(struct lzxd_stream *lzx) {
379
lzx->header_read = 0;
380
lzx->block_remaining = 0;
381
lzx->block_type = LZX_BLOCKTYPE_INVALID;
383
/* initialise tables to 0 (because deltas will be applied to them) */
384
for (i = 0; i < LZX_MAINTREE_MAXSYMBOLS; i++) lzx->MAINTREE_len[i] = 0;
385
for (i = 0; i < LZX_LENGTH_MAXSYMBOLS; i++) lzx->LENGTH_len[i] = 0;
388
/*-------- main LZX code --------*/
390
struct lzxd_stream *lzxd_init(struct mspack_system *system,
391
struct mspack_file *input,
392
struct mspack_file *output,
395
int input_buffer_size,
398
unsigned int window_size = 1 << window_bits;
399
struct lzxd_stream *lzx;
401
if (!system) return NULL;
403
/* LZX supports window sizes of 2^15 (32Kb) through 2^21 (2Mb) */
404
if (window_bits < 15 || window_bits > 21) return NULL;
406
input_buffer_size = (input_buffer_size + 1) & -2;
407
if (!input_buffer_size) return NULL;
409
/* initialise static data */
412
/* allocate decompression state */
413
if (!(lzx = system->alloc(system, sizeof(struct lzxd_stream)))) {
417
/* allocate decompression window and input buffer */
418
lzx->window = system->alloc(system, (size_t) window_size);
419
lzx->inbuf = system->alloc(system, (size_t) input_buffer_size);
420
if (!lzx->window || !lzx->inbuf) {
421
system->free(lzx->window);
422
system->free(lzx->inbuf);
427
/* initialise decompression state */
430
lzx->output = output;
432
lzx->length = output_length;
434
lzx->inbuf_size = input_buffer_size;
435
lzx->window_size = 1 << window_bits;
436
lzx->window_posn = 0;
439
lzx->reset_interval = reset_interval;
440
lzx->intel_filesize = 0;
441
lzx->intel_curpos = 0;
443
/* window bits: 15 16 17 18 19 20 21
444
* position slots: 30 32 34 36 38 42 50 */
445
lzx->posn_slots = ((window_bits == 21) ? 50 :
446
((window_bits == 20) ? 42 : (window_bits << 1)));
447
lzx->intel_started = 0;
450
lzx->error = MSPACK_ERR_OK;
452
lzx->i_ptr = lzx->i_end = &lzx->inbuf[0];
453
lzx->o_ptr = lzx->o_end = &lzx->e8_buf[0];
454
lzx->bit_buffer = lzx->bits_left = 0;
456
lzxd_reset_state(lzx);
460
void lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) {
461
if (lzx) lzx->length = out_bytes;
464
int lzxd_decompress(struct lzxd_stream *lzx, off_t out_bytes) {
465
/* bitstream reading and huffman variables */
466
register unsigned int bit_buffer;
467
register int bits_left, i=0;
468
register unsigned short sym;
469
unsigned char *i_ptr, *i_end;
471
int match_length, length_footer, extra, verbatim_bits, bytes_todo;
472
int this_run, main_element, aligned_bits, j;
473
unsigned char *window, *runsrc, *rundest, buf[12];
474
unsigned int frame_size=0, end_frame, match_offset, window_posn;
475
unsigned int R0, R1, R2;
478
if (!lzx || (out_bytes < 0)) return MSPACK_ERR_ARGS;
479
if (lzx->error) return lzx->error;
481
/* flush out any stored-up bytes before we begin */
482
i = lzx->o_end - lzx->o_ptr;
483
if ((off_t) i > out_bytes) i = (int) out_bytes;
485
if (lzx->sys->write(lzx->output, lzx->o_ptr, i) != i) {
486
return lzx->error = MSPACK_ERR_WRITE;
492
if (out_bytes == 0) return MSPACK_ERR_OK;
494
/* restore local state */
496
window = lzx->window;
497
window_posn = lzx->window_posn;
502
end_frame = (unsigned int)((lzx->offset + out_bytes) / LZX_FRAME_SIZE) + 1;
504
while (lzx->frame < end_frame) {
505
/* have we reached the reset interval? (if there is one?) */
506
if (lzx->reset_interval && ((lzx->frame % lzx->reset_interval) == 0)) {
507
if (lzx->block_remaining) {
508
D(("%d bytes remaining at reset interval", lzx->block_remaining))
509
return lzx->error = MSPACK_ERR_DECRUNCH;
512
/* re-read the intel header and reset the huffman lengths */
513
lzxd_reset_state(lzx);
516
/* read header if necessary */
517
if (!lzx->header_read) {
518
/* read 1 bit. if bit=0, intel filesize = 0.
519
* if bit=1, read intel filesize (32 bits) */
520
j = 0; READ_BITS(i, 1); if (i) { READ_BITS(i, 16); READ_BITS(j, 16); }
521
lzx->intel_filesize = (i << 16) | j;
522
lzx->header_read = 1;
525
/* calculate size of frame: all frames are 32k except the final frame
526
* which is 32kb or less. this can only be calculated when lzx->length
527
* has been filled in. */
528
frame_size = LZX_FRAME_SIZE;
529
if (lzx->length && (lzx->length - lzx->offset) < (off_t)frame_size) {
530
frame_size = lzx->length - lzx->offset;
533
/* decode until one more frame is available */
534
bytes_todo = lzx->frame_posn + frame_size - window_posn;
535
while (bytes_todo > 0) {
536
/* initialise new block, if one is needed */
537
if (lzx->block_remaining == 0) {
538
/* realign if previous block was an odd-sized UNCOMPRESSED block */
539
if ((lzx->block_type == LZX_BLOCKTYPE_UNCOMPRESSED) &&
540
(lzx->block_length & 1))
542
if (i_ptr == i_end) {
543
if (lzxd_read_input(lzx)) return lzx->error;
550
/* read block type (3 bits) and block length (24 bits) */
551
READ_BITS(lzx->block_type, 3);
552
READ_BITS(i, 16); READ_BITS(j, 8);
553
lzx->block_remaining = lzx->block_length = (i << 8) | j;
554
/*D(("new block t%d len %u", lzx->block_type, lzx->block_length))*/
556
/* read individual block headers */
557
switch (lzx->block_type) {
558
case LZX_BLOCKTYPE_ALIGNED:
559
/* read lengths of and build aligned huffman decoding tree */
560
for (i = 0; i < 8; i++) { READ_BITS(j, 3); lzx->ALIGNED_len[i] = j; }
561
BUILD_TABLE(ALIGNED);
562
/* no break -- rest of aligned header is same as verbatim */
563
case LZX_BLOCKTYPE_VERBATIM:
564
/* read lengths of and build main huffman decoding tree */
565
READ_LENGTHS(MAINTREE, 0, 256);
566
READ_LENGTHS(MAINTREE, 256, LZX_NUM_CHARS + (lzx->posn_slots << 3));
567
BUILD_TABLE(MAINTREE);
568
/* if the literal 0xE8 is anywhere in the block... */
569
if (lzx->MAINTREE_len[0xE8] != 0) lzx->intel_started = 1;
570
/* read lengths of and build lengths huffman decoding tree */
571
READ_LENGTHS(LENGTH, 0, LZX_NUM_SECONDARY_LENGTHS);
575
case LZX_BLOCKTYPE_UNCOMPRESSED:
576
/* because we can't assume otherwise */
577
lzx->intel_started = 1;
579
/* read 1-16 (not 0-15) bits to align to bytes */
581
if (bits_left > 16) i_ptr -= 2;
582
bits_left = 0; bit_buffer = 0;
584
/* read 12 bytes of stored R0 / R1 / R2 values */
585
for (rundest = &buf[0], i = 0; i < 12; i++) {
586
if (i_ptr == i_end) {
587
if (lzxd_read_input(lzx)) return lzx->error;
591
*rundest++ = *i_ptr++;
593
R0 = buf[0] | (buf[1] << 8) | (buf[2] << 16) | (buf[3] << 24);
594
R1 = buf[4] | (buf[5] << 8) | (buf[6] << 16) | (buf[7] << 24);
595
R2 = buf[8] | (buf[9] << 8) | (buf[10] << 16) | (buf[11] << 24);
599
D(("bad block type"))
600
return lzx->error = MSPACK_ERR_DECRUNCH;
604
/* decode more of the block:
605
* run = min(what's available, what's needed) */
606
this_run = lzx->block_remaining;
607
if (this_run > bytes_todo) this_run = bytes_todo;
609
/* assume we decode exactly this_run bytes, for now */
610
bytes_todo -= this_run;
611
lzx->block_remaining -= this_run;
613
/* decode at least this_run bytes */
614
switch (lzx->block_type) {
615
case LZX_BLOCKTYPE_VERBATIM:
616
while (this_run > 0) {
617
READ_HUFFSYM(MAINTREE, main_element);
618
if (main_element < LZX_NUM_CHARS) {
619
/* literal: 0 to LZX_NUM_CHARS-1 */
620
window[window_posn++] = main_element;
624
/* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
625
main_element -= LZX_NUM_CHARS;
627
/* get match length */
628
match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
629
if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
630
READ_HUFFSYM(LENGTH, length_footer);
631
match_length += length_footer;
633
match_length += LZX_MIN_MATCH;
635
/* get match offset */
636
switch ((match_offset = (main_element >> 3))) {
637
case 0: match_offset = R0; break;
638
case 1: match_offset = R1; R1=R0; R0 = match_offset; break;
639
case 2: match_offset = R2; R2=R0; R0 = match_offset; break;
640
case 3: match_offset = 1; R2=R1; R1=R0; R0 = match_offset; break;
642
extra = extra_bits[match_offset];
643
READ_BITS(verbatim_bits, extra);
644
match_offset = position_base[match_offset] - 2 + verbatim_bits;
645
R2 = R1; R1 = R0; R0 = match_offset;
648
if ((window_posn + match_length) > lzx->window_size) {
649
D(("match ran over window wrap"))
650
return lzx->error = MSPACK_ERR_DECRUNCH;
654
rundest = &window[window_posn];
656
/* does match offset wrap the window? */
657
if (match_offset > window_posn) {
658
/* j = length from match offset to end of window */
659
j = match_offset - window_posn;
660
if (j > (int) lzx->window_size) {
661
D(("match offset beyond window boundaries"))
662
return lzx->error = MSPACK_ERR_DECRUNCH;
664
runsrc = &window[lzx->window_size - j];
666
/* if match goes over the window edge, do two copy runs */
667
i -= j; while (j-- > 0) *rundest++ = *runsrc++;
670
while (i-- > 0) *rundest++ = *runsrc++;
673
runsrc = rundest - match_offset;
674
while (i-- > 0) *rundest++ = *runsrc++;
677
this_run -= match_length;
678
window_posn += match_length;
680
} /* while (this_run > 0) */
683
case LZX_BLOCKTYPE_ALIGNED:
684
while (this_run > 0) {
685
READ_HUFFSYM(MAINTREE, main_element);
686
if (main_element < LZX_NUM_CHARS) {
687
/* literal: 0 to LZX_NUM_CHARS-1 */
688
window[window_posn++] = main_element;
692
/* match: LZX_NUM_CHARS + ((slot<<3) | length_header (3 bits)) */
693
main_element -= LZX_NUM_CHARS;
695
/* get match length */
696
match_length = main_element & LZX_NUM_PRIMARY_LENGTHS;
697
if (match_length == LZX_NUM_PRIMARY_LENGTHS) {
698
READ_HUFFSYM(LENGTH, length_footer);
699
match_length += length_footer;
701
match_length += LZX_MIN_MATCH;
703
/* get match offset */
704
switch ((match_offset = (main_element >> 3))) {
705
case 0: match_offset = R0; break;
706
case 1: match_offset = R1; R1 = R0; R0 = match_offset; break;
707
case 2: match_offset = R2; R2 = R0; R0 = match_offset; break;
709
extra = extra_bits[match_offset];
710
match_offset = position_base[match_offset] - 2;
712
/* verbatim and aligned bits */
714
READ_BITS(verbatim_bits, extra);
715
match_offset += (verbatim_bits << 3);
716
READ_HUFFSYM(ALIGNED, aligned_bits);
717
match_offset += aligned_bits;
719
else if (extra == 3) {
720
/* aligned bits only */
721
READ_HUFFSYM(ALIGNED, aligned_bits);
722
match_offset += aligned_bits;
724
else if (extra > 0) { /* extra==1, extra==2 */
725
/* verbatim bits only */
726
READ_BITS(verbatim_bits, extra);
727
match_offset += verbatim_bits;
729
else /* extra == 0 */ {
730
/* ??? not defined in LZX specification! */
733
/* update repeated offset LRU queue */
734
R2 = R1; R1 = R0; R0 = match_offset;
737
if ((window_posn + match_length) > lzx->window_size) {
738
D(("match ran over window wrap"))
739
return lzx->error = MSPACK_ERR_DECRUNCH;
743
rundest = &window[window_posn];
745
/* does match offset wrap the window? */
746
if (match_offset > window_posn) {
747
/* j = length from match offset to end of window */
748
j = match_offset - window_posn;
749
if (j > (int) lzx->window_size) {
750
D(("match offset beyond window boundaries"))
751
return lzx->error = MSPACK_ERR_DECRUNCH;
753
runsrc = &window[lzx->window_size - j];
755
/* if match goes over the window edge, do two copy runs */
756
i -= j; while (j-- > 0) *rundest++ = *runsrc++;
759
while (i-- > 0) *rundest++ = *runsrc++;
762
runsrc = rundest - match_offset;
763
while (i-- > 0) *rundest++ = *runsrc++;
766
this_run -= match_length;
767
window_posn += match_length;
769
} /* while (this_run > 0) */
772
case LZX_BLOCKTYPE_UNCOMPRESSED:
773
/* as this_run is limited not to wrap a frame, this also means it
774
* won't wrap the window (as the window is a multiple of 32k) */
775
rundest = &window[window_posn];
776
window_posn += this_run;
777
while (this_run > 0) {
778
if ((i = i_end - i_ptr)) {
779
if (i > this_run) i = this_run;
780
lzx->sys->copy(i_ptr, rundest, (size_t) i);
786
if (lzxd_read_input(lzx)) return lzx->error;
794
return lzx->error = MSPACK_ERR_DECRUNCH; /* might as well */
797
/* did the final match overrun our desired this_run length? */
799
if ((unsigned int)(-this_run) > lzx->block_remaining) {
800
D(("overrun went past end of block by %d (%d remaining)",
801
-this_run, lzx->block_remaining ))
802
return lzx->error = MSPACK_ERR_DECRUNCH;
804
lzx->block_remaining -= -this_run;
806
} /* while (bytes_todo > 0) */
808
/* streams don't extend over frame boundaries */
809
if ((window_posn - lzx->frame_posn) != frame_size) {
810
D(("decode beyond output frame limits! %d != %d",
811
window_posn - lzx->frame_posn, frame_size))
812
return lzx->error = MSPACK_ERR_DECRUNCH;
815
/* re-align input bitstream */
816
if (bits_left > 0) ENSURE_BITS(16);
817
if (bits_left & 15) REMOVE_BITS(bits_left & 15);
819
/* check that we've used all of the previous frame first */
820
if (lzx->o_ptr != lzx->o_end) {
821
D(("%d avail bytes, new %d frame", lzx->o_end-lzx->o_ptr, frame_size))
822
return lzx->error = MSPACK_ERR_DECRUNCH;
825
/* does this intel block _really_ need decoding? */
826
if (lzx->intel_started && lzx->intel_filesize &&
827
(lzx->frame <= 32768) && (frame_size > 10))
829
unsigned char *data = &lzx->e8_buf[0];
830
unsigned char *dataend = &lzx->e8_buf[frame_size - 10];
831
signed int curpos = lzx->intel_curpos;
832
signed int filesize = lzx->intel_filesize;
833
signed int abs_off, rel_off;
835
/* copy e8 block to the e8 buffer and tweak if needed */
837
lzx->sys->copy(&lzx->window[lzx->frame_posn], data, frame_size);
839
while (data < dataend) {
840
if (*data++ != 0xE8) { curpos++; continue; }
841
abs_off = data[0] | (data[1]<<8) | (data[2]<<16) | (data[3]<<24);
842
if ((abs_off >= -curpos) && (abs_off < filesize)) {
843
rel_off = (abs_off >= 0) ? abs_off - curpos : abs_off + filesize;
844
data[0] = (unsigned char) rel_off;
845
data[1] = (unsigned char) (rel_off >> 8);
846
data[2] = (unsigned char) (rel_off >> 16);
847
data[3] = (unsigned char) (rel_off >> 24);
852
lzx->intel_curpos += frame_size;
855
lzx->o_ptr = &lzx->window[lzx->frame_posn];
856
if (lzx->intel_filesize) lzx->intel_curpos += frame_size;
858
lzx->o_end = &lzx->o_ptr[frame_size];
861
i = (out_bytes < (off_t)frame_size) ? (unsigned int)out_bytes : frame_size;
862
if (lzx->sys->write(lzx->output, lzx->o_ptr, i) != i) {
863
return lzx->error = MSPACK_ERR_WRITE;
869
/* advance frame start position */
870
lzx->frame_posn += frame_size;
873
/* wrap window / frame position pointers */
874
if (window_posn == lzx->window_size) window_posn = 0;
875
if (lzx->frame_posn == lzx->window_size) lzx->frame_posn = 0;
877
} /* while (lzx->frame < end_frame) */
880
D(("bytes left to output"))
881
return lzx->error = MSPACK_ERR_DECRUNCH;
884
/* store local state */
886
lzx->window_posn = window_posn;
891
return MSPACK_ERR_OK;
894
void lzxd_free(struct lzxd_stream *lzx) {
895
struct mspack_system *sys;
898
sys->free(lzx->inbuf);
899
sys->free(lzx->window);