1 /* This file is part of libmspack.
2 * (C) 2003-2010 Stuart Caie.
3 *
4 * The deflate method was created by Phil Katz. MSZIP is equivalent to the
5 * deflate method.
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 /* MS-ZIP decompression implementation. */
14
15 #include "system.h"
16 #include "mszip.h"
17
18 /* import bit-reading macros and code */
19 #define BITS_TYPE struct mszipd_stream
20 #define BITS_VAR zip
21 #define BITS_ORDER_LSB
22 #define BITS_LSB_TABLE
23 #define READ_BYTES do { \
24 READ_IF_NEEDED; \
25 INJECT_BITS(*i_ptr++, 8); \
26 } while (0)
27 #include "readbits.h"
28
29 /* import huffman macros and code */
30 #define TABLEBITS(tbl) MSZIP_##tbl##_TABLEBITS
31 #define MAXSYMBOLS(tbl) MSZIP_##tbl##_MAXSYMBOLS
32 #define HUFF_TABLE(tbl,idx) zip->tbl##_table[idx]
33 #define HUFF_LEN(tbl,idx) zip->tbl##_len[idx]
34 #define HUFF_ERROR return INF_ERR_HUFFSYM
35 #include "readhuff.h"
36
37 #define FLUSH_IF_NEEDED do { \
38 if (zip->window_posn == MSZIP_FRAME_SIZE) { \
39 if (zip->flush_window(zip, MSZIP_FRAME_SIZE)) { \
40 return INF_ERR_FLUSH; \
41 } \
42 zip->window_posn = 0; \
43 } \
44 } while (0)
45
46 /* match lengths for literal codes 257.. 285 */
47 static const unsigned short lit_lengths[29] = {
48 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27,
49 31, 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258
50 };
51
52 /* match offsets for distance codes 0 .. 29 */
53 static const unsigned short dist_offsets[30] = {
54 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385,
55 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
56 };
57
58 /* extra bits required for literal codes 257.. 285 */
59 static const unsigned char lit_extrabits[29] = {
60 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2,
61 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0
62 };
63
64 /* extra bits required for distance codes 0 .. 29 */
65 static const unsigned char dist_extrabits[30] = {
66 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6,
67 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13
68 };
69
70 /* the order of the bit length Huffman code lengths */
71 static const unsigned char bitlen_order[19] = {
72 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
73 };
74
75 /* inflate() error codes */
76 #define INF_ERR_BLOCKTYPE (-1) /* unknown block type */
77 #define INF_ERR_COMPLEMENT (-2) /* block size complement mismatch */
78 #define INF_ERR_FLUSH (-3) /* error from flush_window() callback */
79 #define INF_ERR_BITBUF (-4) /* too many bits in bit buffer */
80 #define INF_ERR_SYMLENS (-5) /* too many symbols in blocktype 2 header */
81 #define INF_ERR_BITLENTBL (-6) /* failed to build bitlens huffman table */
82 #define INF_ERR_LITERALTBL (-7) /* failed to build literals huffman table */
83 #define INF_ERR_DISTANCETBL (-8) /* failed to build distance huffman table */
84 #define INF_ERR_BITOVERRUN (-9) /* bitlen RLE code goes over table size */
85 #define INF_ERR_BADBITLEN (-10) /* invalid bit-length code */
86 #define INF_ERR_LITCODE (-11) /* out-of-range literal code */
87 #define INF_ERR_DISTCODE (-12) /* out-of-range distance code */
88 #define INF_ERR_DISTANCE (-13) /* somehow, distance is beyond 32k */
89 #define INF_ERR_HUFFSYM (-14) /* out of bits decoding huffman symbol */
90
zip_read_lens(struct mszipd_stream * zip)91 static int zip_read_lens(struct mszipd_stream *zip) {
92 /* for the bit buffer and huffman decoding */
93 register unsigned int bit_buffer;
94 register int bits_left;
95 unsigned char *i_ptr, *i_end;
96
97 /* bitlen Huffman codes -- immediate lookup, 7 bit max code length */
98 unsigned short bl_table[(1 << 7)];
99 unsigned char bl_len[19];
100
101 unsigned char lens[MSZIP_LITERAL_MAXSYMBOLS + MSZIP_DISTANCE_MAXSYMBOLS];
102 unsigned int lit_codes, dist_codes, code, last_code=0, bitlen_codes, i, run;
103
104 RESTORE_BITS;
105
106 /* read the number of codes */
107 READ_BITS(lit_codes, 5); lit_codes += 257;
108 READ_BITS(dist_codes, 5); dist_codes += 1;
109 READ_BITS(bitlen_codes, 4); bitlen_codes += 4;
110 if (lit_codes > MSZIP_LITERAL_MAXSYMBOLS) return INF_ERR_SYMLENS;
111 if (dist_codes > MSZIP_DISTANCE_MAXSYMBOLS) return INF_ERR_SYMLENS;
112
113 /* read in the bit lengths in their unusual order */
114 for (i = 0; i < bitlen_codes; i++) READ_BITS(bl_len[bitlen_order[i]], 3);
115 while (i < 19) bl_len[bitlen_order[i++]] = 0;
116
117 /* create decoding table with an immediate lookup */
118 if (make_decode_table(19, 7, &bl_len[0], &bl_table[0])) {
119 return INF_ERR_BITLENTBL;
120 }
121
122 /* read literal / distance code lengths */
123 for (i = 0; i < (lit_codes + dist_codes); i++) {
124 /* single-level huffman lookup */
125 ENSURE_BITS(7);
126 code = bl_table[PEEK_BITS(7)];
127 REMOVE_BITS(bl_len[code]);
128
129 if (code < 16) lens[i] = last_code = code;
130 else {
131 switch (code) {
132 case 16: READ_BITS(run, 2); run += 3; code = last_code; break;
133 case 17: READ_BITS(run, 3); run += 3; code = 0; break;
134 case 18: READ_BITS(run, 7); run += 11; code = 0; break;
135 default: D(("bad code!: %u", code)) return INF_ERR_BADBITLEN;
136 }
137 if ((i + run) > (lit_codes + dist_codes)) return INF_ERR_BITOVERRUN;
138 while (run--) lens[i++] = code;
139 i--;
140 }
141 }
142
143 /* copy LITERAL code lengths and clear any remaining */
144 i = lit_codes;
145 zip->sys->copy(&lens[0], &zip->LITERAL_len[0], i);
146 while (i < MSZIP_LITERAL_MAXSYMBOLS) zip->LITERAL_len[i++] = 0;
147
148 i = dist_codes;
149 zip->sys->copy(&lens[lit_codes], &zip->DISTANCE_len[0], i);
150 while (i < MSZIP_DISTANCE_MAXSYMBOLS) zip->DISTANCE_len[i++] = 0;
151
152 STORE_BITS;
153 return 0;
154 }
155
156 /* a clean implementation of RFC 1951 / inflate */
inflate(struct mszipd_stream * zip)157 static int inflate(struct mszipd_stream *zip) {
158 unsigned int last_block, block_type, distance, length, this_run, i;
159
160 /* for the bit buffer and huffman decoding */
161 register unsigned int bit_buffer;
162 register int bits_left;
163 register unsigned short sym;
164 unsigned char *i_ptr, *i_end;
165
166 RESTORE_BITS;
167
168 do {
169 /* read in last block bit */
170 READ_BITS(last_block, 1);
171
172 /* read in block type */
173 READ_BITS(block_type, 2);
174
175 if (block_type == 0) {
176 /* uncompressed block */
177 unsigned char lens_buf[4];
178
179 /* go to byte boundary */
180 i = bits_left & 7; REMOVE_BITS(i);
181
182 /* read 4 bytes of data, emptying the bit-buffer if necessary */
183 for (i = 0; (bits_left >= 8); i++) {
184 if (i == 4) return INF_ERR_BITBUF;
185 lens_buf[i] = PEEK_BITS(8);
186 REMOVE_BITS(8);
187 }
188 if (bits_left != 0) return INF_ERR_BITBUF;
189 while (i < 4) {
190 READ_IF_NEEDED;
191 lens_buf[i++] = *i_ptr++;
192 }
193
194 /* get the length and its complement */
195 length = lens_buf[0] | (lens_buf[1] << 8);
196 i = lens_buf[2] | (lens_buf[3] << 8);
197 if (length != (~i & 0xFFFF)) return INF_ERR_COMPLEMENT;
198
199 /* read and copy the uncompressed data into the window */
200 while (length > 0) {
201 READ_IF_NEEDED;
202
203 this_run = length;
204 if (this_run > (unsigned int)(i_end - i_ptr)) this_run = i_end - i_ptr;
205 if (this_run > (MSZIP_FRAME_SIZE - zip->window_posn))
206 this_run = MSZIP_FRAME_SIZE - zip->window_posn;
207
208 zip->sys->copy(i_ptr, &zip->window[zip->window_posn], this_run);
209 zip->window_posn += this_run;
210 i_ptr += this_run;
211 length -= this_run;
212 FLUSH_IF_NEEDED;
213 }
214 }
215 else if ((block_type == 1) || (block_type == 2)) {
216 /* Huffman-compressed LZ77 block */
217 unsigned int match_posn, code;
218
219 if (block_type == 1) {
220 /* block with fixed Huffman codes */
221 i = 0;
222 while (i < 144) zip->LITERAL_len[i++] = 8;
223 while (i < 256) zip->LITERAL_len[i++] = 9;
224 while (i < 280) zip->LITERAL_len[i++] = 7;
225 while (i < 288) zip->LITERAL_len[i++] = 8;
226 for (i = 0; i < 32; i++) zip->DISTANCE_len[i] = 5;
227 }
228 else {
229 /* block with dynamic Huffman codes */
230 STORE_BITS;
231 if ((i = zip_read_lens(zip))) return i;
232 RESTORE_BITS;
233 }
234
235 /* now huffman lengths are read for either kind of block,
236 * create huffman decoding tables */
237 if (make_decode_table(MSZIP_LITERAL_MAXSYMBOLS, MSZIP_LITERAL_TABLEBITS,
238 &zip->LITERAL_len[0], &zip->LITERAL_table[0]))
239 {
240 return INF_ERR_LITERALTBL;
241 }
242
243 if (make_decode_table(MSZIP_DISTANCE_MAXSYMBOLS,MSZIP_DISTANCE_TABLEBITS,
244 &zip->DISTANCE_len[0], &zip->DISTANCE_table[0]))
245 {
246 return INF_ERR_DISTANCETBL;
247 }
248
249 /* decode forever until end of block code */
250 for (;;) {
251 READ_HUFFSYM(LITERAL, code);
252 if (code < 256) {
253 zip->window[zip->window_posn++] = (unsigned char) code;
254 FLUSH_IF_NEEDED;
255 }
256 else if (code == 256) {
257 /* END OF BLOCK CODE: loop break point */
258 break;
259 }
260 else {
261 code -= 257; /* codes 257-285 are matches */
262 if (code >= 29) return INF_ERR_LITCODE; /* codes 286-287 are illegal */
263 READ_BITS_T(length, lit_extrabits[code]);
264 length += lit_lengths[code];
265
266 READ_HUFFSYM(DISTANCE, code);
267 if (code >= 30) return INF_ERR_DISTCODE;
268 READ_BITS_T(distance, dist_extrabits[code]);
269 distance += dist_offsets[code];
270
271 /* match position is window position minus distance. If distance
272 * is more than window position numerically, it must 'wrap
273 * around' the frame size. */
274 match_posn = ((distance > zip->window_posn) ? MSZIP_FRAME_SIZE : 0)
275 + zip->window_posn - distance;
276
277 /* copy match */
278 if (length < 12) {
279 /* short match, use slower loop but no loop setup code */
280 while (length--) {
281 zip->window[zip->window_posn++] = zip->window[match_posn++];
282 match_posn &= MSZIP_FRAME_SIZE - 1;
283 FLUSH_IF_NEEDED;
284 }
285 }
286 else {
287 /* longer match, use faster loop but with setup expense */
288 unsigned char *runsrc, *rundest;
289 do {
290 this_run = length;
291 if ((match_posn + this_run) > MSZIP_FRAME_SIZE)
292 this_run = MSZIP_FRAME_SIZE - match_posn;
293 if ((zip->window_posn + this_run) > MSZIP_FRAME_SIZE)
294 this_run = MSZIP_FRAME_SIZE - zip->window_posn;
295
296 rundest = &zip->window[zip->window_posn]; zip->window_posn += this_run;
297 runsrc = &zip->window[match_posn]; match_posn += this_run;
298 length -= this_run;
299 while (this_run--) *rundest++ = *runsrc++;
300 if (match_posn == MSZIP_FRAME_SIZE) match_posn = 0;
301 FLUSH_IF_NEEDED;
302 } while (length > 0);
303 }
304
305 } /* else (code >= 257) */
306
307 } /* for(;;) -- break point at 'code == 256' */
308 }
309 else {
310 /* block_type == 3 -- bad block type */
311 return INF_ERR_BLOCKTYPE;
312 }
313 } while (!last_block);
314
315 /* flush the remaining data */
316 if (zip->window_posn) {
317 if (zip->flush_window(zip, zip->window_posn)) return INF_ERR_FLUSH;
318 }
319 STORE_BITS;
320
321 /* return success */
322 return 0;
323 }
324
325 /* inflate() calls this whenever the window should be flushed. As
326 * MSZIP only expands to the size of the window, the implementation used
327 * simply keeps track of the amount of data flushed, and if more than 32k
328 * is flushed, an error is raised.
329 */
mszipd_flush_window(struct mszipd_stream * zip,unsigned int data_flushed)330 static int mszipd_flush_window(struct mszipd_stream *zip,
331 unsigned int data_flushed)
332 {
333 zip->bytes_output += data_flushed;
334 if (zip->bytes_output > MSZIP_FRAME_SIZE) {
335 D(("overflow: %u bytes flushed, total is now %u",
336 data_flushed, zip->bytes_output))
337 return 1;
338 }
339 return 0;
340 }
341
mszipd_init(struct mspack_system * system,struct mspack_file * input,struct mspack_file * output,int input_buffer_size,int repair_mode)342 struct mszipd_stream *mszipd_init(struct mspack_system *system,
343 struct mspack_file *input,
344 struct mspack_file *output,
345 int input_buffer_size,
346 int repair_mode)
347 {
348 struct mszipd_stream *zip;
349
350 if (!system) return NULL;
351
352 /* round up input buffer size to multiple of two */
353 input_buffer_size = (input_buffer_size + 1) & -2;
354 if (input_buffer_size < 2) return NULL;
355
356 /* allocate decompression state */
357 if (!(zip = (struct mszipd_stream *) system->alloc(system, sizeof(struct mszipd_stream)))) {
358 return NULL;
359 }
360
361 /* allocate input buffer */
362 zip->inbuf = (unsigned char *) system->alloc(system, (size_t) input_buffer_size);
363 if (!zip->inbuf) {
364 system->free(zip);
365 return NULL;
366 }
367
368 /* initialise decompression state */
369 zip->sys = system;
370 zip->input = input;
371 zip->output = output;
372 zip->inbuf_size = input_buffer_size;
373 zip->input_end = 0;
374 zip->error = MSPACK_ERR_OK;
375 zip->repair_mode = repair_mode;
376 zip->flush_window = &mszipd_flush_window;
377
378 zip->i_ptr = zip->i_end = &zip->inbuf[0];
379 zip->o_ptr = zip->o_end = NULL;
380 zip->bit_buffer = 0; zip->bits_left = 0;
381 return zip;
382 }
383
mszipd_decompress(struct mszipd_stream * zip,off_t out_bytes)384 int mszipd_decompress(struct mszipd_stream *zip, off_t out_bytes) {
385 /* for the bit buffer */
386 register unsigned int bit_buffer;
387 register int bits_left;
388 unsigned char *i_ptr, *i_end;
389
390 int i, state, error;
391
392 /* easy answers */
393 if (!zip || (out_bytes < 0)) return MSPACK_ERR_ARGS;
394 if (zip->error) return zip->error;
395
396 /* flush out any stored-up bytes before we begin */
397 i = zip->o_end - zip->o_ptr;
398 if ((off_t) i > out_bytes) i = (int) out_bytes;
399 if (i) {
400 if (zip->sys->write(zip->output, zip->o_ptr, i) != i) {
401 return zip->error = MSPACK_ERR_WRITE;
402 }
403 zip->o_ptr += i;
404 out_bytes -= i;
405 }
406 if (out_bytes == 0) return MSPACK_ERR_OK;
407
408
409 while (out_bytes > 0) {
410 /* unpack another block */
411 RESTORE_BITS;
412
413 /* skip to next read 'CK' header */
414 i = bits_left & 7; REMOVE_BITS(i); /* align to bytestream */
415 state = 0;
416 do {
417 READ_BITS(i, 8);
418 if (i == 'C') state = 1;
419 else if ((state == 1) && (i == 'K')) state = 2;
420 else state = 0;
421 } while (state != 2);
422
423 /* inflate a block, repair and realign if necessary */
424 zip->window_posn = 0;
425 zip->bytes_output = 0;
426 STORE_BITS;
427 if ((error = inflate(zip))) {
428 D(("inflate error %d", error))
429 if (zip->repair_mode) {
430 /* recover partially-inflated buffers */
431 if (zip->bytes_output == 0 && zip->window_posn > 0) {
432 zip->flush_window(zip, zip->window_posn);
433 }
434 zip->sys->message(NULL, "MSZIP error, %u bytes of data lost.",
435 MSZIP_FRAME_SIZE - zip->bytes_output);
436 for (i = zip->bytes_output; i < MSZIP_FRAME_SIZE; i++) {
437 zip->window[i] = '\0';
438 }
439 zip->bytes_output = MSZIP_FRAME_SIZE;
440 }
441 else {
442 return zip->error = (error > 0) ? error : MSPACK_ERR_DECRUNCH;
443 }
444 }
445 zip->o_ptr = &zip->window[0];
446 zip->o_end = &zip->o_ptr[zip->bytes_output];
447
448 /* write a frame */
449 i = (out_bytes < (off_t)zip->bytes_output) ?
450 (int)out_bytes : zip->bytes_output;
451 if (zip->sys->write(zip->output, zip->o_ptr, i) != i) {
452 return zip->error = MSPACK_ERR_WRITE;
453 }
454
455 /* mspack errors (i.e. read errors) are fatal and can't be recovered */
456 if ((error > 0) && zip->repair_mode) return error;
457
458 zip->o_ptr += i;
459 out_bytes -= i;
460 }
461
462 if (out_bytes) {
463 D(("bytes left to output"))
464 return zip->error = MSPACK_ERR_DECRUNCH;
465 }
466 return MSPACK_ERR_OK;
467 }
468
mszipd_decompress_kwaj(struct mszipd_stream * zip)469 int mszipd_decompress_kwaj(struct mszipd_stream *zip) {
470 /* for the bit buffer */
471 register unsigned int bit_buffer;
472 register int bits_left;
473 unsigned char *i_ptr, *i_end;
474
475 int i, error, block_len;
476
477 /* unpack blocks until block_len == 0 */
478 for (;;) {
479 RESTORE_BITS;
480
481 /* align to bytestream, read block_len */
482 i = bits_left & 7; REMOVE_BITS(i);
483 READ_BITS(block_len, 8);
484 READ_BITS(i, 8); block_len |= i << 8;
485
486 if (block_len == 0) break;
487
488 /* read "CK" header */
489 READ_BITS(i, 8); if (i != 'C') return MSPACK_ERR_DATAFORMAT;
490 READ_BITS(i, 8); if (i != 'K') return MSPACK_ERR_DATAFORMAT;
491
492 /* inflate block */
493 zip->window_posn = 0;
494 zip->bytes_output = 0;
495 STORE_BITS;
496 if ((error = inflate(zip))) {
497 D(("inflate error %d", error))
498 return zip->error = (error > 0) ? error : MSPACK_ERR_DECRUNCH;
499 }
500
501 /* write inflated block */
502 if (zip->sys->write(zip->output, &zip->window[0], zip->bytes_output)
503 != zip->bytes_output) return zip->error = MSPACK_ERR_WRITE;
504 }
505 return MSPACK_ERR_OK;
506 }
507
mszipd_free(struct mszipd_stream * zip)508 void mszipd_free(struct mszipd_stream *zip) {
509 struct mspack_system *sys;
510 if (zip) {
511 sys = zip->sys;
512 sys->free(zip->inbuf);
513 sys->free(zip);
514 }
515 }
516