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 source tree.
38 #include "bb_archive.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 off_t to_read; /* compressed bytes to read (unzip only, -1 for gunzip) */
89 // unsigned bytebuffer_max; /* buffer size */
90 unsigned bytebuffer_offset; /* buffer position */
91 unsigned bytebuffer_size; /* how much data is there (size <= max) */
93 /* private data of inflate_codes() */
94 unsigned inflate_codes_ml; /* masks for bl and bd bits */
95 unsigned inflate_codes_md; /* masks for bl and bd bits */
96 unsigned inflate_codes_bb; /* bit buffer */
97 unsigned inflate_codes_k; /* number of bits in bit buffer */
98 unsigned inflate_codes_w; /* current gunzip_window position */
99 huft_t *inflate_codes_tl;
100 huft_t *inflate_codes_td;
101 unsigned inflate_codes_bl;
102 unsigned inflate_codes_bd;
103 unsigned inflate_codes_nn; /* length and index for copy */
104 unsigned inflate_codes_dd;
106 smallint resume_copy;
108 /* private data of inflate_get_next_window() */
109 smallint method; /* method == -1 for stored, -2 for codes */
110 smallint need_another_block;
111 smallint end_reached;
113 /* private data of inflate_stored() */
114 unsigned inflate_stored_n;
115 unsigned inflate_stored_b;
116 unsigned inflate_stored_k;
117 unsigned inflate_stored_w;
119 const char *error_msg;
122 #define gunzip_bytes_out (S()gunzip_bytes_out )
123 #define gunzip_crc (S()gunzip_crc )
124 #define gunzip_src_fd (S()gunzip_src_fd )
125 #define gunzip_outbuf_count (S()gunzip_outbuf_count)
126 #define gunzip_window (S()gunzip_window )
127 #define gunzip_crc_table (S()gunzip_crc_table )
128 #define gunzip_bb (S()gunzip_bb )
129 #define gunzip_bk (S()gunzip_bk )
130 #define to_read (S()to_read )
131 // #define bytebuffer_max (S()bytebuffer_max )
132 // Both gunzip and unzip can use constant buffer size now (16k):
133 #define bytebuffer_max 0x4000
134 #define bytebuffer (S()bytebuffer )
135 #define bytebuffer_offset (S()bytebuffer_offset )
136 #define bytebuffer_size (S()bytebuffer_size )
137 #define inflate_codes_ml (S()inflate_codes_ml )
138 #define inflate_codes_md (S()inflate_codes_md )
139 #define inflate_codes_bb (S()inflate_codes_bb )
140 #define inflate_codes_k (S()inflate_codes_k )
141 #define inflate_codes_w (S()inflate_codes_w )
142 #define inflate_codes_tl (S()inflate_codes_tl )
143 #define inflate_codes_td (S()inflate_codes_td )
144 #define inflate_codes_bl (S()inflate_codes_bl )
145 #define inflate_codes_bd (S()inflate_codes_bd )
146 #define inflate_codes_nn (S()inflate_codes_nn )
147 #define inflate_codes_dd (S()inflate_codes_dd )
148 #define resume_copy (S()resume_copy )
149 #define method (S()method )
150 #define need_another_block (S()need_another_block )
151 #define end_reached (S()end_reached )
152 #define inflate_stored_n (S()inflate_stored_n )
153 #define inflate_stored_b (S()inflate_stored_b )
154 #define inflate_stored_k (S()inflate_stored_k )
155 #define inflate_stored_w (S()inflate_stored_w )
156 #define error_msg (S()error_msg )
157 #define error_jmp (S()error_jmp )
159 /* This is a generic part */
160 #if STATE_IN_BSS /* Use global data segment */
161 #define DECLARE_STATE /*nothing*/
162 #define ALLOC_STATE /*nothing*/
163 #define DEALLOC_STATE ((void)0)
165 #define PASS_STATE /*nothing*/
166 #define PASS_STATE_ONLY /*nothing*/
167 #define STATE_PARAM /*nothing*/
168 #define STATE_PARAM_ONLY void
169 static state_t state;
172 #if STATE_IN_MALLOC /* Use malloc space */
173 #define DECLARE_STATE state_t *state
174 #define ALLOC_STATE (state = xzalloc(sizeof(*state)))
175 #define DEALLOC_STATE free(state)
177 #define PASS_STATE state,
178 #define PASS_STATE_ONLY state
179 #define STATE_PARAM state_t *state,
180 #define STATE_PARAM_ONLY state_t *state
184 static const uint16_t mask_bits[] ALIGN2 = {
185 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
186 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
189 /* Copy lengths for literal codes 257..285 */
190 static const uint16_t cplens[] ALIGN2 = {
191 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
192 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
195 /* note: see note #13 above about the 258 in this list. */
196 /* Extra bits for literal codes 257..285 */
197 static const uint8_t cplext[] ALIGN1 = {
198 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,
200 }; /* 99 == invalid */
202 /* Copy offsets for distance codes 0..29 */
203 static const uint16_t cpdist[] ALIGN2 = {
204 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
205 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
208 /* Extra bits for distance codes */
209 static const uint8_t cpdext[] ALIGN1 = {
210 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
211 11, 11, 12, 12, 13, 13
214 /* Tables for deflate from PKZIP's appnote.txt. */
215 /* Order of the bit length code lengths */
216 static const uint8_t border[] ALIGN1 = {
217 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
222 * Free the malloc'ed tables built by huft_build(), which makes a linked
223 * list of the tables it made, with the links in a dummy first entry of
227 static void huft_free(huft_t *p)
231 /* Go through linked list, freeing from the malloced (t[-1]) address. */
239 static void huft_free_all(STATE_PARAM_ONLY)
241 huft_free(inflate_codes_tl);
242 huft_free(inflate_codes_td);
243 inflate_codes_tl = NULL;
244 inflate_codes_td = NULL;
247 static void abort_unzip(STATE_PARAM_ONLY) NORETURN;
248 static void abort_unzip(STATE_PARAM_ONLY)
250 huft_free_all(PASS_STATE_ONLY);
251 longjmp(error_jmp, 1);
254 static unsigned fill_bitbuffer(STATE_PARAM unsigned bitbuffer, unsigned *current, const unsigned required)
256 while (*current < required) {
257 if (bytebuffer_offset >= bytebuffer_size) {
258 unsigned sz = bytebuffer_max - 4;
259 if (to_read >= 0 && to_read < sz) /* unzip only */
261 /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
262 * to the front of the bytebuffer */
263 bytebuffer_size = safe_read(gunzip_src_fd, &bytebuffer[4], sz);
264 if ((int)bytebuffer_size < 1) {
265 error_msg = "unexpected end of file";
266 abort_unzip(PASS_STATE_ONLY);
268 if (to_read >= 0) /* unzip only */
269 to_read -= bytebuffer_size;
270 bytebuffer_size += 4;
271 bytebuffer_offset = 4;
273 bitbuffer |= ((unsigned) bytebuffer[bytebuffer_offset]) << *current;
281 /* Given a list of code lengths and a maximum table size, make a set of
282 * tables to decode that set of codes. Return zero on success, one if
283 * the given code set is incomplete (the tables are still built in this
284 * case), two if the input is invalid (all zero length codes or an
285 * oversubscribed set of lengths) - in this case stores NULL in *t.
287 * b: code lengths in bits (all assumed <= BMAX)
288 * n: number of codes (assumed <= N_MAX)
289 * s: number of simple-valued codes (0..s-1)
290 * d: list of base values for non-simple codes
291 * e: list of extra bits for non-simple codes
292 * t: result: starting table
293 * m: maximum lookup bits, returns actual
295 static int huft_build(const unsigned *b, const unsigned n,
296 const unsigned s, const unsigned short *d,
297 const unsigned char *e, huft_t **t, unsigned *m)
299 unsigned a; /* counter for codes of length k */
300 unsigned c[BMAX + 1]; /* bit length count table */
301 unsigned eob_len; /* length of end-of-block code (value 256) */
302 unsigned f; /* i repeats in table every f entries */
303 int g; /* maximum code length */
304 int htl; /* table level */
305 unsigned i; /* counter, current code */
306 unsigned j; /* counter */
307 int k; /* number of bits in current code */
308 const unsigned *p; /* pointer into c[], b[], or v[] */
309 huft_t *q; /* points to current table */
310 huft_t r; /* table entry for structure assignment */
311 huft_t *u[BMAX]; /* table stack */
312 unsigned v[N_MAX]; /* values in order of bit length */
314 int ws[BMAX + 1]; /* bits decoded stack */
315 int w; /* bits decoded */
316 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
317 unsigned *xp; /* pointer into x */
318 int y; /* number of dummy codes added */
319 unsigned z; /* number of entries in current table */
321 /* Length of EOB code, if any */
322 eob_len = n > 256 ? b[256] : BMAX;
326 /* Generate counts for each bit length */
327 memset(c, 0, sizeof(c));
331 c[*p]++; /* assume all entries <= BMAX */
332 p++; /* can't combine with above line (Solaris bug) */
334 if (c[0] == n) { /* null input - all zero length codes */
339 /* Find minimum and maximum length, bound *m by those */
340 for (j = 1; (j <= BMAX) && (c[j] == 0); j++)
342 k = j; /* minimum code length */
343 for (i = BMAX; (c[i] == 0) && i; i--)
345 g = i; /* maximum code length */
346 *m = (*m < j) ? j : ((*m > i) ? i : *m);
348 /* Adjust last length count to fill out codes, if needed */
349 for (y = 1 << j; j < i; j++, y <<= 1) {
352 return 2; /* bad input: more codes than bits */
359 /* Generate starting offsets into the value table for each length */
363 while (--i) { /* note that i == g from above */
368 /* Make a table of values in order of bit lengths */
380 /* Generate the Huffman codes and for each, make the table entries */
381 x[0] = i = 0; /* first Huffman code is zero */
382 p = v; /* grab values in bit order */
383 htl = -1; /* no tables yet--level -1 */
384 w = ws[0] = 0; /* bits decoded */
385 u[0] = NULL; /* just to keep compilers happy */
386 q = NULL; /* ditto */
389 /* go through the bit lengths (k already is bits in shortest code) */
390 for (; k <= g; k++) {
393 /* here i is the Huffman code of length k bits for value *p */
394 /* make tables up to required level */
395 while (k > ws[htl + 1]) {
398 /* compute minimum size table less than or equal to *m bits */
400 z = z > *m ? *m : z; /* upper limit on table size */
403 if (f > a + 1) { /* try a k-w bit table */
404 /* too few codes for k-w bit table */
405 f -= a + 1; /* deduct codes from patterns left */
407 while (++j < z) { /* try smaller tables up to z bits */
410 break; /* enough codes to use up j bits */
412 f -= *xp; /* else deduct codes from patterns */
415 j = (w + j > eob_len && w < eob_len) ? eob_len - w : j; /* make EOB code end at table */
416 z = 1 << j; /* table entries for j-bit table */
417 ws[htl+1] = w + j; /* set bits decoded in stack */
419 /* allocate and link in new table */
420 q = xzalloc((z + 1) * sizeof(huft_t));
421 *t = q + 1; /* link to list for huft_free() */
423 u[htl] = ++q; /* table starts after link */
425 /* connect to last table, if there is one */
427 x[htl] = i; /* save pattern for backing up */
428 r.b = (unsigned char) (w - ws[htl - 1]); /* bits to dump before this table */
429 r.e = (unsigned char) (16 + j); /* bits in this table */
430 r.v.t = q; /* pointer to this table */
431 j = (i & ((1 << w) - 1)) >> ws[htl - 1];
432 u[htl - 1][j] = r; /* connect to last table */
436 /* set up table entry in r */
437 r.b = (unsigned char) (k - w);
438 if (p >= v + v_end) { // Was "if (p >= v + n)" but v[] can be shorter!
439 r.e = 99; /* out of values--invalid code */
441 r.e = (unsigned char) (*p < 256 ? 16 : 15); /* 256 is EOB code */
442 r.v.n = (unsigned short) (*p++); /* simple code is just the value */
444 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
448 /* fill code-like entries with r */
450 for (j = i >> w; j < z; j += f) {
454 /* backwards increment the k-bit code i */
455 for (j = 1 << (k - 1); i & j; j >>= 1) {
460 /* backup over finished tables */
461 while ((i & ((1 << w) - 1)) != x[htl]) {
467 /* return actual size of base table */
470 /* Return 1 if we were given an incomplete table */
471 return y != 0 && g != 1;
476 * inflate (decompress) the codes in a deflated (compressed) block.
477 * Return an error code or zero if it all goes ok.
479 * tl, td: literal/length and distance decoder tables
480 * bl, bd: number of bits decoded by tl[] and td[]
482 /* called once from inflate_block */
484 /* map formerly local static variables to globals */
485 #define ml inflate_codes_ml
486 #define md inflate_codes_md
487 #define bb inflate_codes_bb
488 #define k inflate_codes_k
489 #define w inflate_codes_w
490 #define tl inflate_codes_tl
491 #define td inflate_codes_td
492 #define bl inflate_codes_bl
493 #define bd inflate_codes_bd
494 #define nn inflate_codes_nn
495 #define dd inflate_codes_dd
496 static void inflate_codes_setup(STATE_PARAM unsigned my_bl, unsigned my_bd)
500 /* make local copies of globals */
501 bb = gunzip_bb; /* initialize bit buffer */
503 w = gunzip_outbuf_count; /* initialize gunzip_window position */
504 /* inflate the coded data */
505 ml = mask_bits[bl]; /* precompute masks for speed */
508 /* called once from inflate_get_next_window */
509 static NOINLINE int inflate_codes(STATE_PARAM_ONLY)
511 unsigned e; /* table entry flag/number of extra bits */
512 huft_t *t; /* pointer to table entry */
517 while (1) { /* do until end of block */
518 bb = fill_bitbuffer(PASS_STATE bb, &k, bl);
519 t = tl + ((unsigned) bb & ml);
524 abort_unzip(PASS_STATE_ONLY);;
528 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
529 t = t->v.t + ((unsigned) bb & mask_bits[e]);
534 if (e == 16) { /* then it's a literal */
535 gunzip_window[w++] = (unsigned char) t->v.n;
536 if (w == GUNZIP_WSIZE) {
537 gunzip_outbuf_count = w;
538 //flush_gunzip_window();
540 return 1; // We have a block to read
542 } else { /* it's an EOB or a length */
543 /* exit if end of block */
548 /* get length of block to copy */
549 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
550 nn = t->v.n + ((unsigned) bb & mask_bits[e]);
554 /* decode distance of block to copy */
555 bb = fill_bitbuffer(PASS_STATE bb, &k, bd);
556 t = td + ((unsigned) bb & md);
561 abort_unzip(PASS_STATE_ONLY);
565 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
566 t = t->v.t + ((unsigned) bb & mask_bits[e]);
571 bb = fill_bitbuffer(PASS_STATE bb, &k, e);
572 dd = w - t->v.n - ((unsigned) bb & mask_bits[e]);
579 /* Was: nn -= (e = (e = GUNZIP_WSIZE - ((dd &= GUNZIP_WSIZE - 1) > w ? dd : w)) > nn ? nn : e); */
580 /* Who wrote THAT?? rewritten as: */
583 dd &= GUNZIP_WSIZE - 1;
584 e = GUNZIP_WSIZE - (dd > w ? dd : w);
585 delta = w > dd ? w - dd : dd - w;
589 /* copy to new buffer to prevent possible overwrite */
591 memcpy(gunzip_window + w, gunzip_window + dd, e);
595 /* do it slow to avoid memcpy() overlap */
598 gunzip_window[w++] = gunzip_window[dd++];
601 if (w == GUNZIP_WSIZE) {
602 gunzip_outbuf_count = w;
603 resume_copy = (nn != 0);
604 //flush_gunzip_window();
613 /* restore the globals from the locals */
614 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
615 gunzip_bb = bb; /* restore global bit buffer */
618 /* normally just after call to inflate_codes, but save code by putting it here */
619 /* free the decoding tables (tl and td), return */
620 huft_free_all(PASS_STATE_ONLY);
638 /* called once from inflate_block */
639 static void inflate_stored_setup(STATE_PARAM int my_n, int my_b, int my_k)
641 inflate_stored_n = my_n;
642 inflate_stored_b = my_b;
643 inflate_stored_k = my_k;
644 /* initialize gunzip_window position */
645 inflate_stored_w = gunzip_outbuf_count;
647 /* called once from inflate_get_next_window */
648 static int inflate_stored(STATE_PARAM_ONLY)
650 /* read and output the compressed data */
651 while (inflate_stored_n--) {
652 inflate_stored_b = fill_bitbuffer(PASS_STATE inflate_stored_b, &inflate_stored_k, 8);
653 gunzip_window[inflate_stored_w++] = (unsigned char) inflate_stored_b;
654 if (inflate_stored_w == GUNZIP_WSIZE) {
655 gunzip_outbuf_count = inflate_stored_w;
656 //flush_gunzip_window();
657 inflate_stored_w = 0;
658 inflate_stored_b >>= 8;
659 inflate_stored_k -= 8;
660 return 1; /* We have a block */
662 inflate_stored_b >>= 8;
663 inflate_stored_k -= 8;
666 /* restore the globals from the locals */
667 gunzip_outbuf_count = inflate_stored_w; /* restore global gunzip_window pointer */
668 gunzip_bb = inflate_stored_b; /* restore global bit buffer */
669 gunzip_bk = inflate_stored_k;
670 return 0; /* Finished */
675 * decompress an inflated block
678 * GLOBAL VARIABLES: bb, kk,
680 /* Return values: -1 = inflate_stored, -2 = inflate_codes */
681 /* One callsite in inflate_get_next_window */
682 static int inflate_block(STATE_PARAM smallint *e)
684 unsigned ll[286 + 30]; /* literal/length and distance code lengths */
685 unsigned t; /* block type */
686 unsigned b; /* bit buffer */
687 unsigned k; /* number of bits in bit buffer */
689 /* make local bit buffer */
694 /* read in last block bit */
695 b = fill_bitbuffer(PASS_STATE b, &k, 1);
700 /* read in block type */
701 b = fill_bitbuffer(PASS_STATE b, &k, 2);
702 t = (unsigned) b & 3;
706 /* restore the global bit buffer */
710 /* Do we see block type 1 often? Yes!
711 * TODO: fix performance problem (see below) */
712 //bb_error_msg("blktype %d", t);
714 /* inflate that block type */
716 case 0: /* Inflate stored */
718 unsigned n; /* number of bytes in block */
719 unsigned b_stored; /* bit buffer */
720 unsigned k_stored; /* number of bits in bit buffer */
722 /* make local copies of globals */
723 b_stored = gunzip_bb; /* initialize bit buffer */
724 k_stored = gunzip_bk;
726 /* go to byte boundary */
731 /* get the length and its complement */
732 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
733 n = ((unsigned) b_stored & 0xffff);
737 b_stored = fill_bitbuffer(PASS_STATE b_stored, &k_stored, 16);
738 if (n != (unsigned) ((~b_stored) & 0xffff)) {
739 abort_unzip(PASS_STATE_ONLY); /* error in compressed data */
744 inflate_stored_setup(PASS_STATE n, b_stored, k_stored);
750 * decompress an inflated type 1 (fixed Huffman codes) block. We should
751 * either replace this with a custom decoder, or at least precompute the
752 * Huffman tables. TODO */
754 int i; /* temporary variable */
755 unsigned bl; /* lookup bits for tl */
756 unsigned bd; /* lookup bits for td */
757 /* gcc 4.2.1 is too dumb to reuse stackspace. Moved up... */
758 //unsigned ll[288]; /* length list for huft_build */
760 /* set up literal table */
761 for (i = 0; i < 144; i++)
767 for (; i < 288; i++) /* make a complete, but wrong code set */
770 huft_build(ll, 288, 257, cplens, cplext, &inflate_codes_tl, &bl);
771 /* huft_build() never return nonzero - we use known data */
773 /* set up distance table */
774 for (i = 0; i < 30; i++) /* make an incomplete code set */
777 huft_build(ll, 30, 0, cpdist, cpdext, &inflate_codes_td, &bd);
779 /* set up data for inflate_codes() */
780 inflate_codes_setup(PASS_STATE bl, bd);
782 /* huft_free code moved into inflate_codes */
786 case 2: /* Inflate dynamic */
788 enum { dbits = 6 }; /* bits in base distance lookup table */
789 enum { lbits = 9 }; /* bits in base literal/length lookup table */
791 huft_t *td; /* distance code table */
792 unsigned i; /* temporary variables */
794 unsigned l; /* last length */
795 unsigned m; /* mask for bit lengths table */
796 unsigned n; /* number of lengths to get */
797 unsigned bl; /* lookup bits for tl */
798 unsigned bd; /* lookup bits for td */
799 unsigned nb; /* number of bit length codes */
800 unsigned nl; /* number of literal/length codes */
801 unsigned nd; /* number of distance codes */
803 //unsigned ll[286 + 30];/* literal/length and distance code lengths */
804 unsigned b_dynamic; /* bit buffer */
805 unsigned k_dynamic; /* number of bits in bit buffer */
807 /* make local bit buffer */
808 b_dynamic = gunzip_bb;
809 k_dynamic = gunzip_bk;
811 /* read in table lengths */
812 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
813 nl = 257 + ((unsigned) b_dynamic & 0x1f); /* number of literal/length codes */
817 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 5);
818 nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
822 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 4);
823 nb = 4 + ((unsigned) b_dynamic & 0xf); /* number of bit length codes */
827 if (nl > 286 || nd > 30)
828 abort_unzip(PASS_STATE_ONLY); /* bad lengths */
830 /* read in bit-length-code lengths */
831 for (j = 0; j < nb; j++) {
832 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
833 ll[border[j]] = (unsigned) b_dynamic & 7;
840 /* build decoding table for trees - single level, 7 bit lookup */
842 i = huft_build(ll, 19, 19, NULL, NULL, &inflate_codes_tl, &bl);
844 abort_unzip(PASS_STATE_ONLY); //return i; /* incomplete code set */
847 /* read in literal and distance code lengths */
851 while ((unsigned) i < n) {
852 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, (unsigned)bl);
853 td = inflate_codes_tl + ((unsigned) b_dynamic & m);
858 if (j < 16) { /* length of code in bits (0..15) */
859 ll[i++] = l = j; /* save last length in l */
860 } else if (j == 16) { /* repeat last length 3 to 6 times */
861 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 2);
862 j = 3 + ((unsigned) b_dynamic & 3);
865 if ((unsigned) i + j > n) {
866 abort_unzip(PASS_STATE_ONLY); //return 1;
871 } else if (j == 17) { /* 3 to 10 zero length codes */
872 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 3);
873 j = 3 + ((unsigned) b_dynamic & 7);
876 if ((unsigned) i + j > n) {
877 abort_unzip(PASS_STATE_ONLY); //return 1;
883 } else { /* j == 18: 11 to 138 zero length codes */
884 b_dynamic = fill_bitbuffer(PASS_STATE b_dynamic, &k_dynamic, 7);
885 j = 11 + ((unsigned) b_dynamic & 0x7f);
888 if ((unsigned) i + j > n) {
889 abort_unzip(PASS_STATE_ONLY); //return 1;
898 /* free decoding table for trees */
899 huft_free(inflate_codes_tl);
901 /* restore the global bit buffer */
902 gunzip_bb = b_dynamic;
903 gunzip_bk = k_dynamic;
905 /* build the decoding tables for literal/length and distance codes */
908 i = huft_build(ll, nl, 257, cplens, cplext, &inflate_codes_tl, &bl);
910 abort_unzip(PASS_STATE_ONLY);
912 i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &inflate_codes_td, &bd);
914 abort_unzip(PASS_STATE_ONLY);
916 /* set up data for inflate_codes() */
917 inflate_codes_setup(PASS_STATE bl, bd);
919 /* huft_free code moved into inflate_codes */
924 abort_unzip(PASS_STATE_ONLY);
928 /* Two callsites, both in inflate_get_next_window */
929 static void calculate_gunzip_crc(STATE_PARAM_ONLY)
931 gunzip_crc = crc32_block_endian0(gunzip_crc, gunzip_window, gunzip_outbuf_count, gunzip_crc_table);
932 gunzip_bytes_out += gunzip_outbuf_count;
935 /* One callsite in inflate_unzip_internal */
936 static int inflate_get_next_window(STATE_PARAM_ONLY)
938 gunzip_outbuf_count = 0;
943 if (need_another_block) {
945 calculate_gunzip_crc(PASS_STATE_ONLY);
947 /* NB: need_another_block is still set */
948 return 0; /* Last block */
950 method = inflate_block(PASS_STATE &end_reached);
951 need_another_block = 0;
956 ret = inflate_stored(PASS_STATE_ONLY);
959 ret = inflate_codes(PASS_STATE_ONLY);
961 default: /* cannot happen */
962 abort_unzip(PASS_STATE_ONLY);
966 calculate_gunzip_crc(PASS_STATE_ONLY);
967 return 1; /* more data left */
969 need_another_block = 1; /* end of that block */
971 /* Doesnt get here */
975 /* Called from unpack_gz_stream() and inflate_unzip() */
976 static IF_DESKTOP(long long) int
977 inflate_unzip_internal(STATE_PARAM transformer_state_t *xstate)
979 IF_DESKTOP(long long) int n = 0;
982 /* Allocate all global buffers (for DYN_ALLOC option) */
983 gunzip_window = xmalloc(GUNZIP_WSIZE);
984 gunzip_outbuf_count = 0;
985 gunzip_bytes_out = 0;
986 gunzip_src_fd = xstate->src_fd;
988 /* (re) initialize state */
990 need_another_block = 1;
995 /* Create the crc table */
996 gunzip_crc_table = crc32_filltable(NULL, 0);
999 error_msg = "corrupted data";
1000 if (setjmp(error_jmp)) {
1001 /* Error from deep inside zip machinery */
1007 int r = inflate_get_next_window(PASS_STATE_ONLY);
1008 nwrote = transformer_write(xstate, gunzip_window, gunzip_outbuf_count);
1009 if (nwrote == (ssize_t)-1) {
1013 IF_DESKTOP(n += nwrote;)
1017 /* Store unused bytes in a global buffer so calling applets can access it */
1018 if (gunzip_bk >= 8) {
1019 /* Undo too much lookahead. The next read will be byte aligned
1020 * so we can discard unused bits in the last meaningful byte. */
1021 bytebuffer_offset--;
1022 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
1028 free(gunzip_window);
1029 free(gunzip_crc_table);
1034 /* External entry points */
1038 IF_DESKTOP(long long) int FAST_FUNC
1039 inflate_unzip(transformer_state_t *xstate)
1041 IF_DESKTOP(long long) int n;
1046 to_read = xstate->bytes_in;
1047 // bytebuffer_max = 0x8000;
1048 bytebuffer_offset = 4;
1049 bytebuffer = xmalloc(bytebuffer_max);
1050 n = inflate_unzip_internal(PASS_STATE xstate);
1053 xstate->crc32 = gunzip_crc;
1054 xstate->bytes_out = gunzip_bytes_out;
1064 /* Top up the input buffer with at least n bytes. */
1065 static int top_up(STATE_PARAM unsigned n)
1067 int count = bytebuffer_size - bytebuffer_offset;
1069 if (count < (int)n) {
1070 memmove(bytebuffer, &bytebuffer[bytebuffer_offset], count);
1071 bytebuffer_offset = 0;
1072 bytebuffer_size = full_read(gunzip_src_fd, &bytebuffer[count], bytebuffer_max - count);
1073 if ((int)bytebuffer_size < 0) {
1074 bb_error_msg(bb_msg_read_error);
1077 bytebuffer_size += count;
1078 if (bytebuffer_size < n)
1084 static uint16_t buffer_read_le_u16(STATE_PARAM_ONLY)
1087 #if BB_LITTLE_ENDIAN
1088 move_from_unaligned16(res, &bytebuffer[bytebuffer_offset]);
1090 res = bytebuffer[bytebuffer_offset];
1091 res |= bytebuffer[bytebuffer_offset + 1] << 8;
1093 bytebuffer_offset += 2;
1097 static uint32_t buffer_read_le_u32(STATE_PARAM_ONLY)
1100 #if BB_LITTLE_ENDIAN
1101 move_from_unaligned32(res, &bytebuffer[bytebuffer_offset]);
1103 res = bytebuffer[bytebuffer_offset];
1104 res |= bytebuffer[bytebuffer_offset + 1] << 8;
1105 res |= bytebuffer[bytebuffer_offset + 2] << 16;
1106 res |= bytebuffer[bytebuffer_offset + 3] << 24;
1108 bytebuffer_offset += 4;
1112 static int check_header_gzip(STATE_PARAM transformer_state_t *xstate)
1115 unsigned char raw[8];
1120 uint8_t xtra_flags_UNUSED;
1121 uint8_t os_flags_UNUSED;
1125 BUILD_BUG_ON(sizeof(header) != 8);
1128 * Rewind bytebuffer. We use the beginning because the header has 8
1129 * bytes, leaving enough for unwinding afterwards.
1131 bytebuffer_size -= bytebuffer_offset;
1132 memmove(bytebuffer, &bytebuffer[bytebuffer_offset], bytebuffer_size);
1133 bytebuffer_offset = 0;
1135 if (!top_up(PASS_STATE 8))
1137 memcpy(header.raw, &bytebuffer[bytebuffer_offset], 8);
1138 bytebuffer_offset += 8;
1140 /* Check the compression method */
1141 if (header.formatted.gz_method != 8) {
1145 if (header.formatted.flags & 0x04) {
1146 /* bit 2 set: extra field present */
1147 unsigned extra_short;
1149 if (!top_up(PASS_STATE 2))
1151 extra_short = buffer_read_le_u16(PASS_STATE_ONLY);
1152 if (!top_up(PASS_STATE extra_short))
1154 /* Ignore extra field */
1155 bytebuffer_offset += extra_short;
1158 /* Discard original name and file comment if any */
1159 /* bit 3 set: original file name present */
1160 /* bit 4 set: file comment present */
1161 if (header.formatted.flags & 0x18) {
1164 if (!top_up(PASS_STATE 1))
1166 } while (bytebuffer[bytebuffer_offset++] != 0);
1167 if ((header.formatted.flags & 0x18) != 0x18)
1169 header.formatted.flags &= ~0x18;
1173 xstate->mtime = SWAP_LE32(header.formatted.mtime);
1175 /* Read the header checksum */
1176 if (header.formatted.flags & 0x02) {
1177 if (!top_up(PASS_STATE 2))
1179 bytebuffer_offset += 2;
1184 IF_DESKTOP(long long) int FAST_FUNC
1185 unpack_gz_stream(transformer_state_t *xstate)
1188 IF_DESKTOP(long long) int total, n;
1191 #if !ENABLE_FEATURE_SEAMLESS_Z
1192 if (check_signature16(xstate, GZIP_MAGIC))
1195 if (xstate->check_signature) {
1198 if (full_read(xstate->src_fd, &magic2, 2) != 2) {
1200 bb_error_msg("invalid magic");
1203 if (magic2 == COMPRESS_MAGIC) {
1204 xstate->check_signature = 0;
1205 return unpack_Z_stream(xstate);
1207 if (magic2 != GZIP_MAGIC)
1216 // bytebuffer_max = 0x8000;
1217 bytebuffer = xmalloc(bytebuffer_max);
1218 gunzip_src_fd = xstate->src_fd;
1221 if (!check_header_gzip(PASS_STATE xstate)) {
1222 bb_error_msg("corrupted data");
1227 n = inflate_unzip_internal(PASS_STATE xstate);
1234 if (!top_up(PASS_STATE 8)) {
1235 bb_error_msg("corrupted data");
1240 /* Validate decompression - crc */
1241 v32 = buffer_read_le_u32(PASS_STATE_ONLY);
1242 if ((~gunzip_crc) != v32) {
1243 bb_error_msg("crc error");
1248 /* Validate decompression - size */
1249 v32 = buffer_read_le_u32(PASS_STATE_ONLY);
1250 if ((uint32_t)gunzip_bytes_out != v32) {
1251 bb_error_msg("incorrect length");
1255 if (!top_up(PASS_STATE 2))
1258 if (bytebuffer[bytebuffer_offset] == 0x1f
1259 && bytebuffer[bytebuffer_offset + 1] == 0x8b
1261 bytebuffer_offset += 2;
1264 /* GNU gzip says: */
1265 /*bb_error_msg("decompression OK, trailing garbage ignored");*/