1 /* vi: set sw=4 ts=4: */
3 * gunzip implementation for busybox
5 * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
7 * Originally adjusted for busybox by Sven Rudolph <sr1@inf.tu-dresden.de>
8 * based on gzip sources
10 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
11 * files as well as stdin/stdout, and to generally behave itself wrt
12 * command line handling.
14 * General cleanup to better adhere to the style guide and make use of standard
15 * busybox functions by Glenn McGrath
17 * read_gz interface + associated hacking by Laurence Anderson
19 * Fixed huft_build() so decoding end-of-block code does not grab more bits
20 * than necessary (this is required by unzip applet), added inflate_cleanup()
21 * to free leaked bytebuffer memory (used in unzip.c), and some minor style
22 * guide cleanups by Ed Clark
24 * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
25 * Copyright (C) 1992-1993 Jean-loup Gailly
26 * The unzip code was written and put in the public domain by Mark Adler.
27 * Portions of the lzw code are derived from the public domain 'compress'
28 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
29 * Ken Turkowski, Dave Mack and Peter Jannesen.
31 * See the file algorithm.doc for the compression algorithms and file formats.
33 * Licensed under GPLv2 or later, see file LICENSE in this tarball for details.
38 #include "unarchive.h"
40 typedef struct huft_t {
41 unsigned char e; /* number of extra bits or operation */
42 unsigned char b; /* number of bits in this code or subcode */
44 unsigned short n; /* literal, length base, or distance base */
45 struct huft_t *t; /* pointer to next level of table */
50 /* gunzip_window size--must be a power of two, and
51 * at least 32K for zip's deflate method */
52 GUNZIP_WSIZE = 0x8000,
53 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
54 BMAX = 16, /* maximum bit length of any code (16 for explode) */
55 N_MAX = 288, /* maximum number of codes in any set */
59 /* This is somewhat complex-looking arrangement, but it allows
60 * to place decompressor state either in bss or in
61 * malloc'ed space simply by changing #defines below.
63 * text data bss dec hex
64 * 5256 0 108 5364 14f4 - bss
65 * 4915 0 0 4915 1333 - malloc
67 #define STATE_IN_BSS 0
68 #define STATE_IN_MALLOC 1
71 typedef struct state_t {
72 off_t gunzip_bytes_out; /* number of output bytes */
76 unsigned gunzip_outbuf_count; /* bytes in output buffer */
78 unsigned char *gunzip_window;
80 uint32_t *gunzip_crc_table;
83 unsigned gunzip_bb; /* bit buffer */
84 unsigned char gunzip_bk; /* bits in bit buffer */
86 /* input (compressed) data */
87 unsigned char *bytebuffer; /* buffer itself */
88 unsigned bytebuffer_max; /* buffer size */
89 unsigned bytebuffer_offset; /* buffer position */
90 unsigned bytebuffer_size; /* how much data is there (size <= max) */
92 /* private data of inflate_codes() */
93 unsigned inflate_codes_ml; /* masks for bl and bd bits */
94 unsigned inflate_codes_md; /* masks for bl and bd bits */
95 unsigned inflate_codes_bb; /* bit buffer */
96 unsigned inflate_codes_k; /* number of bits in bit buffer */
97 unsigned inflate_codes_w; /* current gunzip_window position */
98 huft_t *inflate_codes_tl;
99 huft_t *inflate_codes_td;
100 unsigned inflate_codes_bl;
101 unsigned inflate_codes_bd;
102 unsigned inflate_codes_nn; /* length and index for copy */
103 unsigned inflate_codes_dd;
105 smallint resume_copy;
107 /* private data of inflate_get_next_window() */
108 smallint method; /* method == -1 for stored, -2 for codes */
109 smallint need_another_block;
110 smallint end_reached;
112 /* private data of inflate_stored() */
113 unsigned inflate_stored_n;
114 unsigned inflate_stored_b;
115 unsigned inflate_stored_k;
116 unsigned inflate_stored_w;
118 const char *error_msg;
121 #define gunzip_bytes_out (S()gunzip_bytes_out )
122 #define gunzip_crc (S()gunzip_crc )
123 #define gunzip_src_fd (S()gunzip_src_fd )
124 #define gunzip_outbuf_count (S()gunzip_outbuf_count)
125 #define gunzip_window (S()gunzip_window )
126 #define gunzip_crc_table (S()gunzip_crc_table )
127 #define gunzip_bb (S()gunzip_bb )
128 #define gunzip_bk (S()gunzip_bk )
129 #define bytebuffer_max (S()bytebuffer_max )
130 #define bytebuffer (S()bytebuffer )
131 #define bytebuffer_offset (S()bytebuffer_offset )
132 #define bytebuffer_size (S()bytebuffer_size )
133 #define inflate_codes_ml (S()inflate_codes_ml )
134 #define inflate_codes_md (S()inflate_codes_md )
135 #define inflate_codes_bb (S()inflate_codes_bb )
136 #define inflate_codes_k (S()inflate_codes_k )
137 #define inflate_codes_w (S()inflate_codes_w )
138 #define inflate_codes_tl (S()inflate_codes_tl )
139 #define inflate_codes_td (S()inflate_codes_td )
140 #define inflate_codes_bl (S()inflate_codes_bl )
141 #define inflate_codes_bd (S()inflate_codes_bd )
142 #define inflate_codes_nn (S()inflate_codes_nn )
143 #define inflate_codes_dd (S()inflate_codes_dd )
144 #define resume_copy (S()resume_copy )
145 #define method (S()method )
146 #define need_another_block (S()need_another_block )
147 #define end_reached (S()end_reached )
148 #define inflate_stored_n (S()inflate_stored_n )
149 #define inflate_stored_b (S()inflate_stored_b )
150 #define inflate_stored_k (S()inflate_stored_k )
151 #define inflate_stored_w (S()inflate_stored_w )
152 #define error_msg (S()error_msg )
153 #define error_jmp (S()error_jmp )
155 /* This is a generic part */
156 #if STATE_IN_BSS /* Use global data segment */
157 #define DECLARE_STATE /*nothing*/
158 #define ALLOC_STATE /*nothing*/
159 #define DEALLOC_STATE ((void)0)
161 #define PASS_STATE /*nothing*/
162 #define PASS_STATE_ONLY /*nothing*/
163 #define STATE_PARAM /*nothing*/
164 #define STATE_PARAM_ONLY void
165 static state_t state;
168 #if STATE_IN_MALLOC /* Use malloc space */
169 #define DECLARE_STATE state_t *state
170 #define ALLOC_STATE (state = xzalloc(sizeof(*state)))
171 #define DEALLOC_STATE free(state)
173 #define PASS_STATE state,
174 #define PASS_STATE_ONLY state
175 #define STATE_PARAM state_t *state,
176 #define STATE_PARAM_ONLY state_t *state
180 static const uint16_t mask_bits[] ALIGN2 = {
181 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
182 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
185 /* Copy lengths for literal codes 257..285 */
186 static const uint16_t cplens[] ALIGN2 = {
187 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
188 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
191 /* note: see note #13 above about the 258 in this list. */
192 /* Extra bits for literal codes 257..285 */
193 static const uint8_t cplext[] ALIGN1 = {
194 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5,
196 }; /* 99 == invalid */
198 /* Copy offsets for distance codes 0..29 */
199 static const uint16_t cpdist[] ALIGN2 = {
200 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
201 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
204 /* Extra bits for distance codes */
205 static const uint8_t cpdext[] ALIGN1 = {
206 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
207 11, 11, 12, 12, 13, 13
210 /* Tables for deflate from PKZIP's appnote.txt. */
211 /* Order of the bit length code lengths */
212 static const uint8_t border[] ALIGN1 = {
213 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
218 * Free the malloc'ed tables built by huft_build(), which makes a linked
219 * list of the tables it made, with the links in a dummy first entry of
223 static void huft_free(huft_t *p)
227 /* Go through linked list, freeing from the malloced (t[-1]) address. */
235 static void huft_free_all(STATE_PARAM_ONLY)
237 huft_free(inflate_codes_tl);
238 huft_free(inflate_codes_td);
239 inflate_codes_tl = NULL;
240 inflate_codes_td = NULL;
243 static void abort_unzip(STATE_PARAM_ONLY) ATTRIBUTE_NORETURN;
244 static void abort_unzip(STATE_PARAM_ONLY)
246 huft_free_all(PASS_STATE_ONLY);
247 longjmp(error_jmp, 1);
250 static unsigned fill_bitbuffer(STATE_PARAM unsigned bitbuffer, unsigned *current, const unsigned required)
252 while (*current < required) {
253 if (bytebuffer_offset >= bytebuffer_size) {
254 /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
255 * to the front of the bytebuffer */
256 bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 4);
257 if ((int)bytebuffer_size < 1) {
258 error_msg = "unexpected end of file";
259 abort_unzip(PASS_STATE_ONLY);
261 bytebuffer_size += 4;
262 bytebuffer_offset = 4;
264 bitbuffer |= ((unsigned) bytebuffer[bytebuffer_offset]) << *current;
272 /* Given a list of code lengths and a maximum table size, make a set of
273 * tables to decode that set of codes. Return zero on success, one if
274 * the given code set is incomplete (the tables are still built in this
275 * case), two if the input is invalid (all zero length codes or an
276 * oversubscribed set of lengths) - in this case stores NULL in *t.
278 * b: code lengths in bits (all assumed <= BMAX)
279 * n: number of codes (assumed <= N_MAX)
280 * s: number of simple-valued codes (0..s-1)
281 * d: list of base values for non-simple codes
282 * e: list of extra bits for non-simple codes
283 * t: result: starting table
284 * m: maximum lookup bits, returns actual
286 static int huft_build(const unsigned *b, const unsigned n,
287 const unsigned s, const unsigned short *d,
288 const unsigned char *e, huft_t **t, unsigned *m)
290 unsigned a; /* counter for codes of length k */
291 unsigned c[BMAX + 1]; /* bit length count table */
292 unsigned eob_len; /* length of end-of-block code (value 256) */
293 unsigned f; /* i repeats in table every f entries */
294 int g; /* maximum code length */
295 int htl; /* table level */
296 unsigned i; /* counter, current code */
297 unsigned j; /* counter */
298 int k; /* number of bits in current code */
299 unsigned *p; /* pointer into c[], b[], or v[] */
300 huft_t *q; /* points to current table */
301 huft_t r; /* table entry for structure assignment */
302 huft_t *u[BMAX]; /* table stack */
303 unsigned v[N_MAX]; /* values in order of bit length */
304 int ws[BMAX + 1]; /* bits decoded stack */
305 int w; /* bits decoded */
306 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
307 unsigned *xp; /* pointer into x */
308 int y; /* number of dummy codes added */
309 unsigned z; /* number of entries in current table */
311 /* Length of EOB code, if any */
312 eob_len = n > 256 ? b[256] : BMAX;
316 /* Generate counts for each bit length */
317 memset(c, 0, sizeof(c));
318 p = (unsigned *) b; /* cast allows us to reuse p for pointing to b */
321 c[*p]++; /* assume all entries <= BMAX */
322 p++; /* can't combine with above line (Solaris bug) */
324 if (c[0] == n) { /* null input - all zero length codes */
329 /* Find minimum and maximum length, bound *m by those */
330 for (j = 1; (c[j] == 0) && (j <= BMAX); j++)
332 k = j; /* minimum code length */
333 for (i = BMAX; (c[i] == 0) && i; i--)
335 g = i; /* maximum code length */
336 *m = (*m < j) ? j : ((*m > i) ? i : *m);
338 /* Adjust last length count to fill out codes, if needed */
339 for (y = 1 << j; j < i; j++, y <<= 1) {
342 return 2; /* bad input: more codes than bits */
349 /* Generate starting offsets into the value table for each length */
353 while (--i) { /* note that i == g from above */
358 /* Make a table of values in order of bit lengths */
368 /* Generate the Huffman codes and for each, make the table entries */
369 x[0] = i = 0; /* first Huffman code is zero */
370 p = v; /* grab values in bit order */
371 htl = -1; /* no tables yet--level -1 */
372 w = ws[0] = 0; /* bits decoded */
373 u[0] = NULL; /* just to keep compilers happy */
374 q = NULL; /* ditto */
377 /* go through the bit lengths (k already is bits in shortest code) */
378 for (; k <= g; k++) {
381 /* here i is the Huffman code of length k bits for value *p */
382 /* make tables up to required level */
383 while (k > ws[htl + 1]) {
386 /* compute minimum size table less than or equal to *m bits */
388 z = z > *m ? *m : z; /* upper limit on table size */
391 if (f > a + 1) { /* try a k-w bit table */
392 /* too few codes for k-w bit table */
393 f -= a + 1; /* deduct codes from patterns left */
395 while (++j < z) { /* try smaller tables up to z bits */
398 break; /* enough codes to use up j bits */
400 f -= *xp; /* else deduct codes from patterns */
403 j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
404 z = 1 << j; /* table entries for j-bit table */
405 ws[htl+1] = w + j; /* set bits decoded in stack */
407 /* allocate and link in new table */
408 q = xzalloc((z + 1) * sizeof(huft_t));
409 *t = q + 1; /* link to list for huft_free() */
411 u[htl] = ++q; /* table starts after link */
413 /* connect to last table, if there is one */
415 x[htl] = i; /* save pattern for backing up */
416 r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
417 r.e = (unsigned char) (16 + j); /* bits in this table */
418 r.v.t = q; /* pointer to this table */
419 j = (i & ((1 << w) - 1)) >> ws[htl - 1];
420 u[htl - 1][j] = r; /* connect to last table */
424 /* set up table entry in r */
425 r.b = (unsigned char) (k - w);
427 r.e = 99; /* out of values--invalid code */
429 r.e = (unsigned char) (*p < 256 ? 16 : 15); /* 256 is EOB code */
430 r.v.n = (unsigned short) (*p++); /* simple code is just the value */
432 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
436 /* fill code-like entries with r */
438 for (j = i >> w; j < z; j += f) {
442 /* backwards increment the k-bit code i */
443 for (j = 1 << (k - 1); i & j; j >>= 1) {
448 /* backup over finished tables */
449 while ((i & ((1 << w) - 1)) != x[htl]) {
455 /* return actual size of base table */
458 /* Return 1 if we were given an incomplete table */
459 return y != 0 && g != 1;
464 * inflate (decompress) the codes in a deflated (compressed) block.
465 * Return an error code or zero if it all goes ok.
467 * tl, td: literal/length and distance decoder tables
468 * bl, bd: number of bits decoded by tl[] and td[]
470 /* called once from inflate_block */
472 /* map formerly local static variables to globals */
473 #define ml inflate_codes_ml
474 #define md inflate_codes_md
475 #define bb inflate_codes_bb
476 #define k inflate_codes_k
477 #define w inflate_codes_w
478 #define tl inflate_codes_tl
479 #define td inflate_codes_td
480 #define bl inflate_codes_bl
481 #define bd inflate_codes_bd
482 #define nn inflate_codes_nn
483 #define dd inflate_codes_dd
484 static void inflate_codes_setup(STATE_PARAM unsigned my_bl, unsigned my_bd)
488 /* make local copies of globals */
489 bb = gunzip_bb; /* initialize bit buffer */
491 w = gunzip_outbuf_count; /* initialize gunzip_window position */
492 /* inflate the coded data */
493 ml = mask_bits[bl]; /* precompute masks for speed */
496 /* called once from inflate_get_next_window */
497 static int inflate_codes(STATE_PARAM_ONLY)
499 unsigned e; /* table entry flag/number of extra bits */
500 huft_t *t; /* pointer to table entry */
505 while (1) { /* do until end of block */
506 bb = fill_bitbuffer(PASS_STATE bb, &k, bl);
507 t = tl + ((unsigned) bb & ml);
512 abort_unzip(PASS_STATE_ONLY);;
516 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
517 t = t->v.t + ((unsigned) bb & mask_bits[e]);
522 if (e == 16) { /* then it's a literal */
523 gunzip_window[w++] = (unsigned char) t->v.n;
524 if (w == GUNZIP_WSIZE) {
525 gunzip_outbuf_count = w;
526 //flush_gunzip_window();
528 return 1; // We have a block to read
530 } else { /* it's an EOB or a length */
531 /* exit if end of block */
536 /* get length of block to copy */
537 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
538 nn = t->v.n + ((unsigned) bb & mask_bits[e]);
542 /* decode distance of block to copy */
543 bb = fill_bitbuffer(PASS_STATE bb, &k, bd);
544 t = td + ((unsigned) bb & md);
549 abort_unzip(PASS_STATE_ONLY);
553 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
554 t = t->v.t + ((unsigned) bb & mask_bits[e]);
559 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
560 dd = w - t->v.n - ((unsigned) bb & mask_bits[e]);
567 /* Was: nn -= (e = (e = GUNZIP_WSIZE - ((dd &= GUNZIP_WSIZE - 1) > w ? dd : w)) > nn ? nn : e); */
568 /* Who wrote THAT?? rewritten as: */
569 dd &= GUNZIP_WSIZE - 1;
570 e = GUNZIP_WSIZE - (dd > w ? dd : w);
574 /* copy to new buffer to prevent possible overwrite */
575 if (w - dd >= e) { /* (this test assumes unsigned comparison) */
576 memcpy(gunzip_window + w, gunzip_window + dd, e);
580 /* do it slow to avoid memcpy() overlap */
583 gunzip_window[w++] = gunzip_window[dd++];
586 if (w == GUNZIP_WSIZE) {
587 gunzip_outbuf_count = w;
588 resume_copy = (nn != 0);
589 //flush_gunzip_window();
598 /* restore the globals from the locals */
599 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
600 gunzip_bb = bb; /* restore global bit buffer */
603 /* normally just after call to inflate_codes, but save code by putting it here */
604 /* free the decoding tables (tl and td), return */
605 huft_free_all(PASS_STATE_ONLY);
623 /* called once from inflate_block */
624 static void inflate_stored_setup(STATE_PARAM int my_n, int my_b, int my_k)
626 inflate_stored_n = my_n;
627 inflate_stored_b = my_b;
628 inflate_stored_k = my_k;
629 /* initialize gunzip_window position */
630 inflate_stored_w = gunzip_outbuf_count;
632 /* called once from inflate_get_next_window */
633 static int inflate_stored(STATE_PARAM_ONLY)
635 /* read and output the compressed data */
636 while (inflate_stored_n--) {
637 inflate_stored_b = fill_bitbuffer(PASS_STATE inflate_stored_b, &inflate_stored_k, 8);
638 gunzip_window[inflate_stored_w++] = (unsigned char) inflate_stored_b;
639 if (inflate_stored_w == GUNZIP_WSIZE) {
640 gunzip_outbuf_count = inflate_stored_w;
641 //flush_gunzip_window();
642 inflate_stored_w = 0;
643 inflate_stored_b >>= 8;
644 inflate_stored_k -= 8;
645 return 1; /* We have a block */
647 inflate_stored_b >>= 8;
648 inflate_stored_k -= 8;
651 /* restore the globals from the locals */
652 gunzip_outbuf_count = inflate_stored_w; /* restore global gunzip_window pointer */
653 gunzip_bb = inflate_stored_b; /* restore global bit buffer */
654 gunzip_bk = inflate_stored_k;
655 return 0; /* Finished */
660 * decompress an inflated block
663 * GLOBAL VARIABLES: bb, kk,
665 /* Return values: -1 = inflate_stored, -2 = inflate_codes */
666 /* One callsite in inflate_get_next_window */
667 static int inflate_block(STATE_PARAM smallint *e)
669 unsigned ll[286 + 30]; /* literal/length and distance code lengths */
670 unsigned t; /* block type */
671 unsigned b; /* bit buffer */
672 unsigned k; /* number of bits in bit buffer */
674 /* make local bit buffer */
679 /* read in last block bit */
680 b = fill_bitbuffer(PASS_STATE b, &k, 1);
685 /* read in block type */
686 b = fill_bitbuffer(PASS_STATE b, &k, 2);
687 t = (unsigned) b & 3;
691 /* restore the global bit buffer */
695 /* Do we see block type 1 often? Yes!
696 * TODO: fix performance problem (see below) */
697 //bb_error_msg("blktype %d", t);
699 /* inflate that block type */
701 case 0: /* Inflate stored */
703 unsigned n; /* number of bytes in block */
704 unsigned b_stored; /* bit buffer */
705 unsigned k_stored; /* number of bits in bit buffer */
707 /* make local copies of globals */
708 b_stored = gunzip_bb; /* initialize bit buffer */
709 k_stored = gunzip_bk;
711 /* go to byte boundary */
716 /* get the length and its complement */
717 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
718 n = ((unsigned) b_stored & 0xffff);
722 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
723 if (n != (unsigned) ((~b_stored) & 0xffff)) {
724 abort_unzip(PASS_STATE_ONLY); /* error in compressed data */
729 inflate_stored_setup(PASS_STATE n, b_stored, k_stored);
735 * decompress an inflated type 1 (fixed Huffman codes) block. We should
736 * either replace this with a custom decoder, or at least precompute the
737 * Huffman tables. TODO */
739 int i; /* temporary variable */
740 unsigned bl; /* lookup bits for tl */
741 unsigned bd; /* lookup bits for td */
742 /* gcc 4.2.1 is too dumb to reuse stackspace. Moved up... */
743 //unsigned ll[288]; /* length list for huft_build */
745 /* set up literal table */
746 for (i = 0; i < 144; i++)
752 for (; i < 288; i++) /* make a complete, but wrong code set */
755 huft_build(ll, 288, 257, cplens, cplext, &inflate_codes_tl, &bl);
756 /* huft_build() never return nonzero - we use known data */
758 /* set up distance table */
759 for (i = 0; i < 30; i++) /* make an incomplete code set */
762 huft_build(ll, 30, 0, cpdist, cpdext, &inflate_codes_td, &bd);
764 /* set up data for inflate_codes() */
765 inflate_codes_setup(PASS_STATE bl, bd);
767 /* huft_free code moved into inflate_codes */
771 case 2: /* Inflate dynamic */
773 enum { dbits = 6 }; /* bits in base distance lookup table */
774 enum { lbits = 9 }; /* bits in base literal/length lookup table */
776 huft_t *td; /* distance code table */
777 unsigned i; /* temporary variables */
779 unsigned l; /* last length */
780 unsigned m; /* mask for bit lengths table */
781 unsigned n; /* number of lengths to get */
782 unsigned bl; /* lookup bits for tl */
783 unsigned bd; /* lookup bits for td */
784 unsigned nb; /* number of bit length codes */
785 unsigned nl; /* number of literal/length codes */
786 unsigned nd; /* number of distance codes */
788 //unsigned ll[286 + 30];/* literal/length and distance code lengths */
789 unsigned b_dynamic; /* bit buffer */
790 unsigned k_dynamic; /* number of bits in bit buffer */
792 /* make local bit buffer */
793 b_dynamic = gunzip_bb;
794 k_dynamic = gunzip_bk;
796 /* read in table lengths */
797 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
798 nl = 257 + ((unsigned) b_dynamic & 0x1f); /* number of literal/length codes */
802 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
803 nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
807 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 4);
808 nb = 4 + ((unsigned) b_dynamic & 0xf); /* number of bit length codes */
812 if (nl > 286 || nd > 30)
813 abort_unzip(PASS_STATE_ONLY); /* bad lengths */
815 /* read in bit-length-code lengths */
816 for (j = 0; j < nb; j++) {
817 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
818 ll[border[j]] = (unsigned) b_dynamic & 7;
825 /* build decoding table for trees - single level, 7 bit lookup */
827 i = huft_build(ll, 19, 19, NULL, NULL, &inflate_codes_tl, &bl);
829 abort_unzip(PASS_STATE_ONLY); //return i; /* incomplete code set */
832 /* read in literal and distance code lengths */
836 while ((unsigned) i < n) {
837 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, (unsigned)bl);
838 td = inflate_codes_tl + ((unsigned) b_dynamic & m);
843 if (j < 16) { /* length of code in bits (0..15) */
844 ll[i++] = l = j; /* save last length in l */
845 } else if (j == 16) { /* repeat last length 3 to 6 times */
846 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 2);
847 j = 3 + ((unsigned) b_dynamic & 3);
850 if ((unsigned) i + j > n) {
851 abort_unzip(PASS_STATE_ONLY); //return 1;
856 } else if (j == 17) { /* 3 to 10 zero length codes */
857 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
858 j = 3 + ((unsigned) b_dynamic & 7);
861 if ((unsigned) i + j > n) {
862 abort_unzip(PASS_STATE_ONLY); //return 1;
868 } else { /* j == 18: 11 to 138 zero length codes */
869 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 7);
870 j = 11 + ((unsigned) b_dynamic & 0x7f);
873 if ((unsigned) i + j > n) {
874 abort_unzip(PASS_STATE_ONLY); //return 1;
883 /* free decoding table for trees */
884 huft_free(inflate_codes_tl);
886 /* restore the global bit buffer */
887 gunzip_bb = b_dynamic;
888 gunzip_bk = k_dynamic;
890 /* build the decoding tables for literal/length and distance codes */
893 i = huft_build(ll, nl, 257, cplens, cplext, &inflate_codes_tl, &bl);
895 abort_unzip(PASS_STATE_ONLY);
897 i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &inflate_codes_td, &bd);
899 abort_unzip(PASS_STATE_ONLY);
901 /* set up data for inflate_codes() */
902 inflate_codes_setup(PASS_STATE bl, bd);
904 /* huft_free code moved into inflate_codes */
909 abort_unzip(PASS_STATE_ONLY);
913 /* Two callsites, both in inflate_get_next_window */
914 static void calculate_gunzip_crc(STATE_PARAM_ONLY)
917 for (n = 0; n < gunzip_outbuf_count; n++) {
918 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
920 gunzip_bytes_out += gunzip_outbuf_count;
923 /* One callsite in inflate_unzip_internal */
924 static int inflate_get_next_window(STATE_PARAM_ONLY)
926 gunzip_outbuf_count = 0;
931 if (need_another_block) {
933 calculate_gunzip_crc(PASS_STATE_ONLY);
935 /* NB: need_another_block is still set */
936 return 0; /* Last block */
938 method = inflate_block(PASS_STATE &end_reached);
939 need_another_block = 0;
944 ret = inflate_stored(PASS_STATE_ONLY);
947 ret = inflate_codes(PASS_STATE_ONLY);
949 default: /* cannot happen */
950 abort_unzip(PASS_STATE_ONLY);
954 calculate_gunzip_crc(PASS_STATE_ONLY);
955 return 1; /* more data left */
957 need_another_block = 1; /* end of that block */
959 /* Doesnt get here */
963 /* Called from unpack_gz_stream() and inflate_unzip() */
964 static USE_DESKTOP(long long) int
965 inflate_unzip_internal(STATE_PARAM int in, int out)
967 USE_DESKTOP(long long) int n = 0;
970 /* Allocate all global buffers (for DYN_ALLOC option) */
971 gunzip_window = xmalloc(GUNZIP_WSIZE);
972 gunzip_outbuf_count = 0;
973 gunzip_bytes_out = 0;
976 /* (re) initialize state */
978 need_another_block = 1;
983 /* Create the crc table */
984 gunzip_crc_table = crc32_filltable(NULL, 0);
987 error_msg = "corrupted data";
988 if (setjmp(error_jmp)) {
989 /* Error from deep inside zip machinery */
995 int r = inflate_get_next_window(PASS_STATE_ONLY);
996 nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
997 if (nwrote != gunzip_outbuf_count) {
998 bb_perror_msg("write");
1002 USE_DESKTOP(n += nwrote;)
1006 /* Store unused bytes in a global buffer so calling applets can access it */
1007 if (gunzip_bk >= 8) {
1008 /* Undo too much lookahead. The next read will be byte aligned
1009 * so we can discard unused bits in the last meaningful byte. */
1010 bytebuffer_offset--;
1011 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
1017 free(gunzip_window);
1018 free(gunzip_crc_table);
1023 /* External entry points */
1027 USE_DESKTOP(long long) int
1028 inflate_unzip(inflate_unzip_result *res, unsigned bufsize, int in, int out)
1030 USE_DESKTOP(long long) int n;
1035 bytebuffer_max = bufsize + 4;
1036 bytebuffer_offset = 4;
1037 bytebuffer = xmalloc(bytebuffer_max);
1038 n = inflate_unzip_internal(PASS_STATE in, out);
1041 res->crc = gunzip_crc;
1042 res->bytes_out = gunzip_bytes_out;
1052 /* Top up the input buffer with at least n bytes. */
1053 static int top_up(STATE_PARAM unsigned n)
1055 int count = bytebuffer_size - bytebuffer_offset;
1058 memmove(bytebuffer, &bytebuffer[bytebuffer_offset], count);
1059 bytebuffer_offset = 0;
1060 bytebuffer_size = full_read(gunzip_src_fd, &bytebuffer[count], bytebuffer_max - count);
1061 if ((int)bytebuffer_size < 0) {
1062 bb_error_msg("read error");
1065 bytebuffer_size += count;
1066 if (bytebuffer_size < n)
1072 static uint16_t buffer_read_le_u16(STATE_PARAM_ONLY)
1075 #if BB_LITTLE_ENDIAN
1076 /* gcc 4.2.1 is very clever */
1077 memcpy(&res, &bytebuffer[bytebuffer_offset], 2);
1079 res = bytebuffer[bytebuffer_offset];
1080 res |= bytebuffer[bytebuffer_offset + 1] << 8;
1082 bytebuffer_offset += 2;
1086 static uint32_t buffer_read_le_u32(STATE_PARAM_ONLY)
1089 #if BB_LITTLE_ENDIAN
1090 memcpy(&res, &bytebuffer[bytebuffer_offset], 4);
1092 res = bytebuffer[bytebuffer_offset];
1093 res |= bytebuffer[bytebuffer_offset + 1] << 8;
1094 res |= bytebuffer[bytebuffer_offset + 2] << 16;
1095 res |= bytebuffer[bytebuffer_offset + 3] << 24;
1097 bytebuffer_offset += 4;
1101 static int check_header_gzip(STATE_PARAM_ONLY)
1104 unsigned char raw[8];
1108 //uint32_t mtime; - unused fields
1109 //uint8_t xtra_flags;
1111 } formatted; /* packed */
1115 * Rewind bytebuffer. We use the beginning because the header has 8
1116 * bytes, leaving enough for unwinding afterwards.
1118 bytebuffer_size -= bytebuffer_offset;
1119 memmove(bytebuffer, &bytebuffer[bytebuffer_offset], bytebuffer_size);
1120 bytebuffer_offset = 0;
1122 if (!top_up(PASS_STATE 8))
1124 memcpy(header.raw, &bytebuffer[bytebuffer_offset], 8);
1125 bytebuffer_offset += 8;
1127 /* Check the compression method */
1128 if (header.formatted.gz_method != 8) {
1132 if (header.formatted.flags & 0x04) {
1133 /* bit 2 set: extra field present */
1134 unsigned extra_short;
1136 if (!top_up(PASS_STATE 2))
1138 extra_short = buffer_read_le_u16(PASS_STATE_ONLY);
1139 if (!top_up(PASS_STATE extra_short))
1141 /* Ignore extra field */
1142 bytebuffer_offset += extra_short;
1145 /* Discard original name and file comment if any */
1146 /* bit 3 set: original file name present */
1147 /* bit 4 set: file comment present */
1148 if (header.formatted.flags & 0x18) {
1151 if (!top_up(PASS_STATE 1))
1153 } while (bytebuffer[bytebuffer_offset++] != 0);
1154 if ((header.formatted.flags & 0x18) != 0x18)
1156 header.formatted.flags &= ~0x18;
1160 /* Read the header checksum */
1161 if (header.formatted.flags & 0x02) {
1162 if (!top_up(PASS_STATE 2))
1164 bytebuffer_offset += 2;
1169 USE_DESKTOP(long long) int
1170 unpack_gz_stream(int in, int out)
1173 USE_DESKTOP(long long) int n;
1179 bytebuffer_max = 0x8000;
1180 bytebuffer = xmalloc(bytebuffer_max);
1184 if (!check_header_gzip(PASS_STATE_ONLY)) {
1185 bb_error_msg("corrupted data");
1189 n += inflate_unzip_internal(PASS_STATE in, out);
1193 if (!top_up(PASS_STATE 8)) {
1194 bb_error_msg("corrupted data");
1199 /* Validate decompression - crc */
1200 v32 = buffer_read_le_u32(PASS_STATE_ONLY);
1201 if ((~gunzip_crc) != v32) {
1202 bb_error_msg("crc error");
1207 /* Validate decompression - size */
1208 v32 = buffer_read_le_u32(PASS_STATE_ONLY);
1209 if ((uint32_t)gunzip_bytes_out != v32) {
1210 bb_error_msg("incorrect length");
1214 if (!top_up(PASS_STATE 2))
1217 if (bytebuffer[bytebuffer_offset] == 0x1f
1218 && bytebuffer[bytebuffer_offset + 1] == 0x8b
1220 bytebuffer_offset += 2;
1223 /* GNU gzip says: */
1224 /*bb_error_msg("decompression OK, trailing garbage ignored");*/