diff options
Diffstat (limited to 'rbutil/rbutilqt/mspack/lzxd.c')
-rw-r--r-- | rbutil/rbutilqt/mspack/lzxd.c | 738 |
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 | |||
134 | static 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 | */ | ||
202 | static 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 | }; | ||
209 | static 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 | |||
215 | static 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 | |||
232 | struct 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 | |||
295 | void lzxd_set_output_length(struct lzxd_stream *lzx, off_t out_bytes) { | ||
296 | if (lzx) lzx->length = out_bytes; | ||
297 | } | ||
298 | |||
299 | int 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 | |||
730 | void 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 | } | ||