blob: a436db1916b440374eed4a0225d394ddd89ea34c [file] [log] [blame]
Glenn L McGrath7fd92942001-04-11 03:11:33 +00001/* vi: set sw=4 ts=4: */
2/*
3 * gunzip implementation for busybox
4 *
5 * Based on GNU gzip v1.2.4 Copyright (C) 1992-1993 Jean-loup Gailly.
6 *
7 * Originally adjusted for busybox by Sven Rudolph <sr1@inf.tu-dresden.de>
8 * based on gzip sources
9 *
Eric Andersencb81e642003-07-14 21:21:08 +000010 * Adjusted further by Erik Andersen <andersen@codepoet.org> to support
Eric Andersendb930942001-12-06 08:20:14 +000011 * files as well as stdin/stdout, and to generally behave itself wrt
Glenn L McGrath7fd92942001-04-11 03:11:33 +000012 * command line handling.
13 *
14 * General cleanup to better adhere to the style guide and make use of standard
15 * busybox functions by Glenn McGrath <bug1@optushome.com.au>
Eric Andersenc7bda1c2004-03-15 08:29:22 +000016 *
Glenn L McGrath83bf47c2002-11-20 22:00:31 +000017 * read_gz interface + associated hacking by Laurence Anderson
18 *
Glenn L McGrath7fd92942001-04-11 03:11:33 +000019 * This program is free software; you can redistribute it and/or modify
20 * it under the terms of the GNU General Public License as published by
21 * the Free Software Foundation; either version 2 of the License, or
22 * (at your option) any later version.
23 *
24 * This program is distributed in the hope that it will be useful,
25 * but WITHOUT ANY WARRANTY; without even the implied warranty of
26 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
27 * General Public License for more details.
28 *
29 * You should have received a copy of the GNU General Public License
30 * along with this program; if not, write to the Free Software
31 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
32 *
33 *
34 * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
35 * Copyright (C) 1992-1993 Jean-loup Gailly
36 * The unzip code was written and put in the public domain by Mark Adler.
37 * Portions of the lzw code are derived from the public domain 'compress'
38 * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
39 * Ken Turkowski, Dave Mack and Peter Jannesen.
40 *
41 * See the license_msg below and the file COPYING for the software license.
42 * See the file algorithm.doc for the compression algorithms and file formats.
43 */
44
45#if 0
46static char *license_msg[] = {
47 " Copyright (C) 1992-1993 Jean-loup Gailly",
48 " This program is free software; you can redistribute it and/or modify",
49 " it under the terms of the GNU General Public License as published by",
50 " the Free Software Foundation; either version 2, or (at your option)",
51 " any later version.",
52 "",
53 " This program is distributed in the hope that it will be useful,",
54 " but WITHOUT ANY WARRANTY; without even the implied warranty of",
55 " MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the",
56 " GNU General Public License for more details.",
57 "",
58 " You should have received a copy of the GNU General Public License",
59 " along with this program; if not, write to the Free Software",
60 " Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.",
61 0
62};
63#endif
64
65#include <sys/types.h>
66#include <sys/wait.h>
67#include <signal.h>
68#include <stdlib.h>
Manuel Novoa III a2949aa2001-06-29 18:59:32 +000069#include <string.h>
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000070#include <unistd.h>
71#include <fcntl.h>
Robert Grieblf6495eb2002-05-15 22:13:47 +000072#include "config.h"
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000073#include "busybox.h"
74#include "unarchive.h"
Glenn L McGrath7fd92942001-04-11 03:11:33 +000075
76typedef struct huft_s {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +000077 unsigned char e; /* number of extra bits or operation */
78 unsigned char b; /* number of bits in this code or subcode */
Glenn L McGrath7fd92942001-04-11 03:11:33 +000079 union {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +000080 unsigned short n; /* literal, length base, or distance base */
Glenn L McGrath7fd92942001-04-11 03:11:33 +000081 struct huft_s *t; /* pointer to next level of table */
82 } v;
83} huft_t;
84
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000085static int gunzip_src_fd;
Glenn L McGrath826b48b2003-02-09 12:00:17 +000086unsigned int gunzip_bytes_out; /* number of output bytes */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000087static unsigned int gunzip_outbuf_count; /* bytes in output buffer */
88
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000089/* gunzip_window size--must be a power of two, and
90 * at least 32K for zip's deflate method */
91static const int gunzip_wsize = 0x8000;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000092static unsigned char *gunzip_window;
Glenn L McGrathcc616922003-02-09 04:46:34 +000093
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000094static unsigned int *gunzip_crc_table;
Glenn L McGrath826b48b2003-02-09 12:00:17 +000095unsigned int gunzip_crc;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +000096
97/* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
98#define BMAX 16 /* maximum bit length of any code (16 for explode) */
99#define N_MAX 288 /* maximum number of codes in any set */
100
Glenn L McGrathcc616922003-02-09 04:46:34 +0000101/* bitbuffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000102static unsigned int gunzip_bb; /* bit buffer */
103static unsigned char gunzip_bk; /* bits in bit buffer */
104
Glenn L McGrathcc616922003-02-09 04:46:34 +0000105/* These control the size of the bytebuffer */
Glenn L McGrath5699b852003-11-15 23:19:05 +0000106static unsigned int bytebuffer_max = 0x8000;
Glenn L McGrathcc616922003-02-09 04:46:34 +0000107static unsigned char *bytebuffer = NULL;
108static unsigned int bytebuffer_offset = 0;
109static unsigned int bytebuffer_size = 0;
110
Eric Andersen044228d2001-07-17 01:12:36 +0000111static const unsigned short mask_bits[] = {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000112 0x0000, 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000113 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
114};
115
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000116/* Copy lengths for literal codes 257..285 */
117static const unsigned short cplens[] = {
118 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 35, 43, 51, 59,
119 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
120};
121
122/* note: see note #13 above about the 258 in this list. */
123/* Extra bits for literal codes 257..285 */
124static const unsigned char cplext[] = {
125 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,
126 5, 5, 5, 0, 99, 99
127}; /* 99==invalid */
128
129/* Copy offsets for distance codes 0..29 */
130static const unsigned short cpdist[] = {
131 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 257, 385, 513,
132 769, 1025, 1537, 2049, 3073, 4097, 6145, 8193, 12289, 16385, 24577
133};
134
135/* Extra bits for distance codes */
136static const unsigned char cpdext[] = {
137 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10,
138 11, 11, 12, 12, 13, 13
139};
140
141/* Tables for deflate from PKZIP's appnote.txt. */
142/* Order of the bit length code lengths */
143static const unsigned char border[] = {
144 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
145};
146
147static unsigned int fill_bitbuffer(unsigned int bitbuffer, unsigned int *current, const unsigned int required)
148{
149 while (*current < required) {
Glenn L McGrath5699b852003-11-15 23:19:05 +0000150 if (bytebuffer_offset >= bytebuffer_size) {
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000151 /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
Glenn L McGrath5699b852003-11-15 23:19:05 +0000152 * to the front of the bytebuffer, leave 4 bytes free at end of tail
153 * so we can easily top up buffer in check_trailer_gzip() */
154 bytebuffer_size = 4 + bb_xread(gunzip_src_fd, &bytebuffer[4], bytebuffer_max - 8);
155 bytebuffer_offset = 4;
156 }
Glenn L McGratheda4f532002-11-24 06:01:20 +0000157 bitbuffer |= ((unsigned int) bytebuffer[bytebuffer_offset]) << *current;
158 bytebuffer_offset++;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000159 *current += 8;
160 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000161 return(bitbuffer);
162}
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000163
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000164static void make_gunzip_crc_table(void)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000165{
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000166 const unsigned int poly = 0xedb88320; /* polynomial exclusive-or pattern */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000167 unsigned short i; /* counter for all possible eight bit values */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000168
Eric Andersen89de1e72002-03-20 13:30:40 +0000169 /* initial shift register value */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000170 gunzip_crc = 0xffffffffL;
171 gunzip_crc_table = (unsigned int *) malloc(256 * sizeof(unsigned int));
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000172
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000173 /* Compute and print table of CRC's, five per line */
174 for (i = 0; i < 256; i++) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000175 unsigned int table_entry; /* crc shift register */
176 unsigned char k; /* byte being shifted into crc apparatus */
Glenn L McGrathef03dbc2001-12-05 13:08:03 +0000177
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000178 table_entry = i;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000179 /* The idea to initialize the register with the byte instead of
180 * zero was stolen from Haruhiko Okumura's ar002
181 */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000182 for (k = 8; k; k--) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000183 if (table_entry & 1) {
184 table_entry = (table_entry >> 1) ^ poly;
185 } else {
186 table_entry >>= 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000187 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000188 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000189 gunzip_crc_table[i] = table_entry;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000190 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000191}
192
193/*
194 * Free the malloc'ed tables built by huft_build(), which makes a linked
195 * list of the tables it made, with the links in a dummy first entry of
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000196 * each table.
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000197 * t: table to free
198 */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000199static int huft_free(huft_t * t)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000200{
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000201 huft_t *p;
202 huft_t *q;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000203
204 /* Go through linked list, freeing from the malloced (t[-1]) address. */
205 p = t;
206 while (p != (huft_t *) NULL) {
207 q = (--p)->v.t;
208 free((char *) p);
209 p = q;
210 }
211 return 0;
212}
213
214/* Given a list of code lengths and a maximum table size, make a set of
215 * tables to decode that set of codes. Return zero on success, one if
216 * the given code set is incomplete (the tables are still built in this
217 * case), two if the input is invalid (all zero length codes or an
218 * oversubscribed set of lengths), and three if not enough memory.
219 *
220 * b: code lengths in bits (all assumed <= BMAX)
221 * n: number of codes (assumed <= N_MAX)
222 * s: number of simple-valued codes (0..s-1)
223 * d: list of base values for non-simple codes
224 * e: list of extra bits for non-simple codes
225 * t: result: starting table
226 * m: maximum lookup bits, returns actual
227 */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000228static int huft_build(unsigned int *b, const unsigned int n,
229 const unsigned int s, const unsigned short *d,
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000230 const unsigned char *e, huft_t ** t, int *m)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000231{
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000232 unsigned a; /* counter for codes of length k */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000233 unsigned c[BMAX + 1]; /* bit length count table */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000234 unsigned f; /* i repeats in table every f entries */
235 int g; /* maximum code length */
236 int h; /* table level */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000237 register unsigned i; /* counter, current code */
238 register unsigned j; /* counter */
239 register int k; /* number of bits in current code */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000240 int l; /* bits per table (returned in m) */
241 register unsigned *p; /* pointer into c[], b[], or v[] */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000242 register huft_t *q; /* points to current table */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000243 huft_t r; /* table entry for structure assignment */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000244 huft_t *u[BMAX]; /* table stack */
245 unsigned v[N_MAX]; /* values in order of bit length */
246 register int w; /* bits before this table == (l * h) */
247 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
248 unsigned *xp; /* pointer into x */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000249 int y; /* number of dummy codes added */
250 unsigned z; /* number of entries in current table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000251
252 /* Generate counts for each bit length */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000253 memset((void *) (c), 0, sizeof(c));
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000254 p = b;
255 i = n;
256 do {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000257 c[*p]++; /* assume all entries <= BMAX */
258 p++; /* Can't combine with above line (Solaris bug) */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000259 } while (--i);
260 if (c[0] == n) { /* null input--all zero length codes */
261 *t = (huft_t *) NULL;
262 *m = 0;
263 return 0;
264 }
265
266 /* Find minimum and maximum length, bound *m by those */
267 l = *m;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000268 for (j = 1; j <= BMAX; j++) {
269 if (c[j]) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000270 break;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000271 }
272 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000273 k = j; /* minimum code length */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000274 if ((unsigned) l < j) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000275 l = j;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000276 }
277 for (i = BMAX; i; i--) {
278 if (c[i]) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000279 break;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000280 }
281 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000282 g = i; /* maximum code length */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000283 if ((unsigned) l > i) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000284 l = i;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000285 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000286 *m = l;
287
288 /* Adjust last length count to fill out codes, if needed */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000289 for (y = 1 << j; j < i; j++, y <<= 1) {
290 if ((y -= c[j]) < 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000291 return 2; /* bad input: more codes than bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000292 }
293 }
294 if ((y -= c[i]) < 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000295 return 2;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000296 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000297 c[i] += y;
298
299 /* Generate starting offsets into the value table for each length */
300 x[1] = j = 0;
301 p = c + 1;
302 xp = x + 2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000303 while (--i) { /* note that i == g from above */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000304 *xp++ = (j += *p++);
305 }
306
307 /* Make a table of values in order of bit lengths */
308 p = b;
309 i = 0;
310 do {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000311 if ((j = *p++) != 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000312 v[x[j]++] = i;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000313 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000314 } while (++i < n);
315
316 /* Generate the Huffman codes and for each, make the table entries */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000317 x[0] = i = 0; /* first Huffman code is zero */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000318 p = v; /* grab values in bit order */
319 h = -1; /* no tables yet--level -1 */
320 w = -l; /* bits decoded == (l * h) */
321 u[0] = (huft_t *) NULL; /* just to keep compilers happy */
322 q = (huft_t *) NULL; /* ditto */
323 z = 0; /* ditto */
324
325 /* go through the bit lengths (k already is bits in shortest code) */
326 for (; k <= g; k++) {
327 a = c[k];
328 while (a--) {
329 /* here i is the Huffman code of length k bits for value *p */
330 /* make tables up to required level */
331 while (k > w + l) {
332 h++;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000333 w += l; /* previous table always l bits */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000334
335 /* compute minimum size table less than or equal to l bits */
336 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
337 if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* too few codes for k-w bit table */
338 f -= a + 1; /* deduct codes from patterns left */
339 xp = c + k;
340 while (++j < z) { /* try smaller tables up to z bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000341 if ((f <<= 1) <= *++xp) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000342 break; /* enough codes to use up j bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000343 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000344 f -= *xp; /* else deduct codes from patterns */
345 }
346 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000347 z = 1 << j; /* table entries for j-bit table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000348
349 /* allocate and link in new table */
Glenn L McGrath249f39a2001-12-05 16:01:02 +0000350 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
351
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000352 *t = q + 1; /* link to list for huft_free() */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000353 *(t = &(q->v.t)) = NULL;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000354 u[h] = ++q; /* table starts after link */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000355
356 /* connect to last table, if there is one */
357 if (h) {
358 x[h] = i; /* save pattern for backing up */
359 r.b = (unsigned char) l; /* bits to dump before this table */
360 r.e = (unsigned char) (16 + j); /* bits in this table */
361 r.v.t = q; /* pointer to this table */
362 j = i >> (w - l); /* (get around Turbo C bug) */
363 u[h - 1][j] = r; /* connect to last table */
364 }
365 }
366
367 /* set up table entry in r */
368 r.b = (unsigned char) (k - w);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000369 if (p >= v + n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000370 r.e = 99; /* out of values--invalid code */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000371 } else if (*p < s) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000372 r.e = (unsigned char) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
373 r.v.n = (unsigned short) (*p); /* simple code is just the value */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000374 p++; /* one compiler does not like *p++ */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000375 } else {
376 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
377 r.v.n = d[*p++ - s];
378 }
379
380 /* fill code-like entries with r */
381 f = 1 << (k - w);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000382 for (j = i >> w; j < z; j += f) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000383 q[j] = r;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000384 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000385
386 /* backwards increment the k-bit code i */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000387 for (j = 1 << (k - 1); i & j; j >>= 1) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000388 i ^= j;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000389 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000390 i ^= j;
391
392 /* backup over finished tables */
393 while ((i & ((1 << w) - 1)) != x[h]) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000394 h--; /* don't need to update q */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000395 w -= l;
396 }
397 }
398 }
399 /* Return true (1) if we were given an incomplete table */
400 return y != 0 && g != 1;
401}
402
403/*
404 * inflate (decompress) the codes in a deflated (compressed) block.
405 * Return an error code or zero if it all goes ok.
406 *
407 * tl, td: literal/length and distance decoder tables
408 * bl, bd: number of bits decoded by tl[] and td[]
409 */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000410static int inflate_codes(huft_t * my_tl, huft_t * my_td, const unsigned int my_bl, const unsigned int my_bd, int setup)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000411{
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000412 static unsigned int e; /* table entry flag/number of extra bits */
413 static unsigned int n, d; /* length and index for copy */
414 static unsigned int w; /* current gunzip_window position */
415 static huft_t *t; /* pointer to table entry */
416 static unsigned int ml, md; /* masks for bl and bd bits */
417 static unsigned int b; /* bit buffer */
418 static unsigned int k; /* number of bits in bit buffer */
419 static huft_t *tl, *td;
420 static unsigned int bl, bd;
421 static int resumeCopy = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000422
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000423 if (setup) { // 1st time we are called, copy in variables
424 tl = my_tl;
425 td = my_td;
426 bl = my_bl;
427 bd = my_bd;
428 /* make local copies of globals */
429 b = gunzip_bb; /* initialize bit buffer */
430 k = gunzip_bk;
431 w = gunzip_outbuf_count; /* initialize gunzip_window position */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000432
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000433 /* inflate the coded data */
434 ml = mask_bits[bl]; /* precompute masks for speed */
435 md = mask_bits[bd];
436 return 0; // Don't actually do anything the first time
437 }
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000438
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000439 if (resumeCopy) goto do_copy;
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000440
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000441 while (1) { /* do until end of block */
442 b = fill_bitbuffer(b, &k, bl);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000443 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000444 do {
445 if (e == 99) {
Manuel Novoa III cad53642003-03-19 09:13:01 +0000446 bb_error_msg_and_die("inflate_codes error 1");;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000447 }
448 b >>= t->b;
449 k -= t->b;
450 e -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000451 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000452 } while ((e =
453 (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000454 b >>= t->b;
455 k -= t->b;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000456 if (e == 16) { /* then it's a literal */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000457 gunzip_window[w++] = (unsigned char) t->v.n;
458 if (w == gunzip_wsize) {
459 gunzip_outbuf_count = (w);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000460 //flush_gunzip_window();
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000461 w = 0;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000462 return 1; // We have a block to read
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000463 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000464 } else { /* it's an EOB or a length */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000465
466 /* exit if end of block */
467 if (e == 15) {
468 break;
469 }
470
471 /* get length of block to copy */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000472 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000473 n = t->v.n + ((unsigned) b & mask_bits[e]);
474 b >>= e;
475 k -= e;
476
477 /* decode distance of block to copy */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000478 b = fill_bitbuffer(b, &k, bd);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000479 if ((e = (t = td + ((unsigned) b & md))->e) > 16)
480 do {
481 if (e == 99)
Manuel Novoa III cad53642003-03-19 09:13:01 +0000482 bb_error_msg_and_die("inflate_codes error 2");;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000483 b >>= t->b;
484 k -= t->b;
485 e -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000486 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000487 } while ((e =
488 (t =
489 t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000490 b >>= t->b;
491 k -= t->b;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000492 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000493 d = w - t->v.n - ((unsigned) b & mask_bits[e]);
494 b >>= e;
495 k -= e;
496
497 /* do the copy */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000498do_copy: do {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000499 n -= (e =
500 (e =
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000501 gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e);
502 /* copy to new buffer to prevent possible overwrite */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000503 if (w - d >= e) { /* (this test assumes unsigned comparison) */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000504 memcpy(gunzip_window + w, gunzip_window + d, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000505 w += e;
506 d += e;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000507 } else {
508 /* do it slow to avoid memcpy() overlap */
509 /* !NOMEMCPY */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000510 do {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000511 gunzip_window[w++] = gunzip_window[d++];
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000512 } while (--e);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000513 }
514 if (w == gunzip_wsize) {
515 gunzip_outbuf_count = (w);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000516 if (n) resumeCopy = 1;
517 else resumeCopy = 0;
518 //flush_gunzip_window();
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000519 w = 0;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000520 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000521 }
522 } while (n);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000523 resumeCopy = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000524 }
525 }
526
527 /* restore the globals from the locals */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000528 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
529 gunzip_bb = b; /* restore global bit buffer */
530 gunzip_bk = k;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000531
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000532 /* normally just after call to inflate_codes, but save code by putting it here */
533 /* free the decoding tables, return */
534 huft_free(tl);
535 huft_free(td);
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000536
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000537 /* done */
538 return 0;
539}
540
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000541static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000542{
543 static int n, b_stored, k_stored, w;
544 if (setup) {
545 n = my_n;
546 b_stored = my_b_stored;
547 k_stored = my_k_stored;
548 w = gunzip_outbuf_count; /* initialize gunzip_window position */
549 return 0; // Don't do anything first time
550 }
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000551
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000552 /* read and output the compressed data */
553 while (n--) {
554 b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
555 gunzip_window[w++] = (unsigned char) b_stored;
556 if (w == (unsigned int) gunzip_wsize) {
557 gunzip_outbuf_count = (w);
558 //flush_gunzip_window();
559 w = 0;
560 b_stored >>= 8;
561 k_stored -= 8;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000562 return 1; // We have a block
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000563 }
564 b_stored >>= 8;
565 k_stored -= 8;
566 }
567
568 /* restore the globals from the locals */
569 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
570 gunzip_bb = b_stored; /* restore global bit buffer */
571 gunzip_bk = k_stored;
572 return 0; // Finished
573}
574
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000575/*
576 * decompress an inflated block
577 * e: last block flag
578 *
579 * GLOBAL VARIABLES: bb, kk,
580 */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000581 // Return values: -1 = inflate_stored, -2 = inflate_codes
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000582static int inflate_block(int *e)
583{
584 unsigned t; /* block type */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000585 register unsigned int b; /* bit buffer */
586 unsigned int k; /* number of bits in bit buffer */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000587
588 /* make local bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000589
590 b = gunzip_bb;
591 k = gunzip_bk;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000592
593 /* read in last block bit */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000594 b = fill_bitbuffer(b, &k, 1);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000595 *e = (int) b & 1;
596 b >>= 1;
597 k -= 1;
598
599 /* read in block type */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000600 b = fill_bitbuffer(b, &k, 2);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000601 t = (unsigned) b & 3;
602 b >>= 2;
603 k -= 2;
604
605 /* restore the global bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000606 gunzip_bb = b;
607 gunzip_bk = k;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000608
609 /* inflate that block type */
610 switch (t) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000611 case 0: /* Inflate stored */
612 {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000613 unsigned int n; /* number of bytes in block */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000614 unsigned int b_stored; /* bit buffer */
615 unsigned int k_stored; /* number of bits in bit buffer */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000616
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000617 /* make local copies of globals */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000618 b_stored = gunzip_bb; /* initialize bit buffer */
619 k_stored = gunzip_bk;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000620
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000621 /* go to byte boundary */
622 n = k_stored & 7;
623 b_stored >>= n;
624 k_stored -= n;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000625
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000626 /* get the length and its complement */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000627 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000628 n = ((unsigned) b_stored & 0xffff);
629 b_stored >>= 16;
630 k_stored -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000631
632 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000633 if (n != (unsigned) ((~b_stored) & 0xffff)) {
634 return 1; /* error in compressed data */
635 }
636 b_stored >>= 16;
637 k_stored -= 16;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000638
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000639 inflate_stored(n, b_stored, k_stored, 1); // Setup inflate_stored
640 return -1;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000641 }
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000642 case 1: /* Inflate fixed
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000643 * decompress an inflated type 1 (fixed Huffman codes) block. We should
644 * either replace this with a custom decoder, or at least precompute the
645 * Huffman tables.
646 */
647 {
648 int i; /* temporary variable */
649 huft_t *tl; /* literal/length code table */
650 huft_t *td; /* distance code table */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000651 unsigned int bl; /* lookup bits for tl */
652 unsigned int bd; /* lookup bits for td */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000653 unsigned int l[288]; /* length list for huft_build */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000654
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000655 /* set up literal table */
656 for (i = 0; i < 144; i++) {
657 l[i] = 8;
658 }
659 for (; i < 256; i++) {
660 l[i] = 9;
661 }
662 for (; i < 280; i++) {
663 l[i] = 7;
664 }
665 for (; i < 288; i++) { /* make a complete, but wrong code set */
666 l[i] = 8;
667 }
668 bl = 7;
669 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
670 return i;
671 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000672
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000673 /* set up distance table */
674 for (i = 0; i < 30; i++) { /* make an incomplete code set */
675 l[i] = 5;
676 }
677 bd = 5;
678 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000679 huft_free(tl);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000680 return i;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000681 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000682
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000683 /* decompress until an end-of-block code */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000684 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000685
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000686 /* huft_free code moved into inflate_codes */
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000687
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000688 return -2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000689 }
690 case 2: /* Inflate dynamic */
691 {
692 const int dbits = 6; /* bits in base distance lookup table */
693 const int lbits = 9; /* bits in base literal/length lookup table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000694
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000695 huft_t *tl; /* literal/length code table */
696 huft_t *td; /* distance code table */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000697 unsigned int i; /* temporary variables */
698 unsigned int j;
699 unsigned int l; /* last length */
700 unsigned int m; /* mask for bit lengths table */
701 unsigned int n; /* number of lengths to get */
702 unsigned int bl; /* lookup bits for tl */
703 unsigned int bd; /* lookup bits for td */
704 unsigned int nb; /* number of bit length codes */
705 unsigned int nl; /* number of literal/length codes */
706 unsigned int nd; /* number of distance codes */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000707
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000708 unsigned int ll[286 + 30]; /* literal/length and distance code lengths */
709 unsigned int b_dynamic; /* bit buffer */
710 unsigned int k_dynamic; /* number of bits in bit buffer */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000711
712 /* make local bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000713 b_dynamic = gunzip_bb;
714 k_dynamic = gunzip_bk;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000715
716 /* read in table lengths */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000717 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
718 nl = 257 + ((unsigned int) b_dynamic & 0x1f); /* number of literal/length codes */
719
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000720 b_dynamic >>= 5;
721 k_dynamic -= 5;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000722 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
723 nd = 1 + ((unsigned int) b_dynamic & 0x1f); /* number of distance codes */
724
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000725 b_dynamic >>= 5;
726 k_dynamic -= 5;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000727 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
728 nb = 4 + ((unsigned int) b_dynamic & 0xf); /* number of bit length codes */
729
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000730 b_dynamic >>= 4;
731 k_dynamic -= 4;
732 if (nl > 286 || nd > 30) {
733 return 1; /* bad lengths */
734 }
735
736 /* read in bit-length-code lengths */
737 for (j = 0; j < nb; j++) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000738 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
739 ll[border[j]] = (unsigned int) b_dynamic & 7;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000740 b_dynamic >>= 3;
741 k_dynamic -= 3;
742 }
743 for (; j < 19; j++) {
744 ll[border[j]] = 0;
745 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000746
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000747 /* build decoding table for trees--single level, 7 bit lookup */
748 bl = 7;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000749 i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
750 if (i != 0) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000751 if (i == 1) {
752 huft_free(tl);
753 }
754 return i; /* incomplete code set */
755 }
756
757 /* read in literal and distance code lengths */
758 n = nl + nd;
759 m = mask_bits[bl];
760 i = l = 0;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000761 while ((unsigned int) i < n) {
762 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned int)bl);
763 j = (td = tl + ((unsigned int) b_dynamic & m))->b;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000764 b_dynamic >>= j;
765 k_dynamic -= j;
766 j = td->v.n;
767 if (j < 16) { /* length of code in bits (0..15) */
768 ll[i++] = l = j; /* save last length in l */
769 } else if (j == 16) { /* repeat last length 3 to 6 times */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000770 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
771 j = 3 + ((unsigned int) b_dynamic & 3);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000772 b_dynamic >>= 2;
773 k_dynamic -= 2;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000774 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000775 return 1;
776 }
777 while (j--) {
778 ll[i++] = l;
779 }
780 } else if (j == 17) { /* 3 to 10 zero length codes */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000781 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
782 j = 3 + ((unsigned int) b_dynamic & 7);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000783 b_dynamic >>= 3;
784 k_dynamic -= 3;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000785 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000786 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000787 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000788 while (j--) {
789 ll[i++] = 0;
790 }
791 l = 0;
792 } else { /* j == 18: 11 to 138 zero length codes */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000793 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
794 j = 11 + ((unsigned int) b_dynamic & 0x7f);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000795 b_dynamic >>= 7;
796 k_dynamic -= 7;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000797 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000798 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000799 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000800 while (j--) {
801 ll[i++] = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000802 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000803 l = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000804 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000805 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000806
807 /* free decoding table for trees */
808 huft_free(tl);
809
810 /* restore the global bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000811 gunzip_bb = b_dynamic;
812 gunzip_bk = k_dynamic;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000813
814 /* build the decoding tables for literal/length and distance codes */
815 bl = lbits;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000816
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000817 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
818 if (i == 1) {
Manuel Novoa III cad53642003-03-19 09:13:01 +0000819 bb_error_msg_and_die("Incomplete literal tree");
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000820 huft_free(tl);
821 }
822 return i; /* incomplete code set */
823 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000824
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000825 bd = dbits;
826 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
827 if (i == 1) {
Manuel Novoa III cad53642003-03-19 09:13:01 +0000828 bb_error_msg_and_die("incomplete distance tree");
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000829 huft_free(td);
830 }
831 huft_free(tl);
832 return i; /* incomplete code set */
833 }
834
835 /* decompress until an end-of-block code */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000836 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000837
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000838 /* huft_free code moved into inflate_codes */
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000839
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000840 return -2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000841 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000842 default:
843 /* bad block type */
Manuel Novoa III cad53642003-03-19 09:13:01 +0000844 bb_error_msg_and_die("bad block type %d\n", t);
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000845 }
846}
847
848static void calculate_gunzip_crc(void)
849{
850 int n;
851 for (n = 0; n < gunzip_outbuf_count; n++) {
852 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
853 }
854 gunzip_bytes_out += gunzip_outbuf_count;
855}
856
857static int inflate_get_next_window(void)
858{
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000859 static int method = -1; // Method == -1 for stored, -2 for codes
860 static int e = 0;
Glenn L McGrath5699b852003-11-15 23:19:05 +0000861 static int needAnotherBlock = 1;
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000862
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000863 gunzip_outbuf_count = 0;
864
865 while(1) {
866 int ret;
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000867
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000868 if (needAnotherBlock) {
Glenn L McGratheda4f532002-11-24 06:01:20 +0000869 if(e) {
870 calculate_gunzip_crc();
Glenn L McGrath5699b852003-11-15 23:19:05 +0000871 e = 0;
872 needAnotherBlock = 1;
Glenn L McGratheda4f532002-11-24 06:01:20 +0000873 return 0;
874 } // Last block
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000875 method = inflate_block(&e);
876 needAnotherBlock = 0;
877 }
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000878
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000879 switch (method) {
880 case -1: ret = inflate_stored(0,0,0,0);
881 break;
882 case -2: ret = inflate_codes(0,0,0,0,0);
883 break;
Manuel Novoa III cad53642003-03-19 09:13:01 +0000884 default: bb_error_msg_and_die("inflate error %d", method);
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000885 }
886
887 if (ret == 1) {
888 calculate_gunzip_crc();
889 return 1; // More data left
890 } else needAnotherBlock = 1; // End of that block
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000891 }
Glenn L McGratheda4f532002-11-24 06:01:20 +0000892 /* Doesnt get here */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000893}
894
Glenn L McGrath5699b852003-11-15 23:19:05 +0000895/* Initialise bytebuffer, be carefull not to overfill the buffer */
896extern void inflate_init(unsigned int bufsize)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000897{
Glenn L McGrath5699b852003-11-15 23:19:05 +0000898 /* Set the bytebuffer size, default is same as gunzip_wsize */
899 bytebuffer_max = bufsize + 8;
900 bytebuffer_offset = 4;
901 bytebuffer_size = 0;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000902}
903
Glenn L McGrath5699b852003-11-15 23:19:05 +0000904extern int inflate_unzip(int in, int out)
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000905{
Glenn L McGrath5699b852003-11-15 23:19:05 +0000906 ssize_t nwrote;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000907 typedef void (*sig_type) (int);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000908
Glenn L McGrath87ac7022002-01-02 13:52:26 +0000909 /* Allocate all global buffers (for DYN_ALLOC option) */
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000910 gunzip_window = xmalloc(gunzip_wsize);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000911 gunzip_outbuf_count = 0;
912 gunzip_bytes_out = 0;
Glenn L McGrath5699b852003-11-15 23:19:05 +0000913 gunzip_src_fd = in;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000914
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000915 /* initialize gunzip_window, bit buffer */
916 gunzip_bk = 0;
917 gunzip_bb = 0;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000918
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000919 /* Create the crc table */
920 make_gunzip_crc_table();
921
Glenn L McGrath5699b852003-11-15 23:19:05 +0000922 /* Allocate space for buffer */
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000923 bytebuffer = xmalloc(bytebuffer_max);
Glenn L McGrath5699b852003-11-15 23:19:05 +0000924
925 while(1) {
926 int ret = inflate_get_next_window();
927 nwrote = bb_full_write(out, gunzip_window, gunzip_outbuf_count);
928 if (nwrote == -1) {
929 bb_perror_msg("write");
930 return -1;
931 }
932 if (ret == 0) break;
933 }
934
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000935 /* Cleanup */
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000936 free(gunzip_window);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000937 free(gunzip_crc_table);
938
939 /* Store unused bytes in a global buffer so calling applets can access it */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000940 if (gunzip_bk >= 8) {
941 /* Undo too much lookahead. The next read will be byte aligned
942 * so we can discard unused bits in the last meaningful byte. */
Glenn L McGratheda4f532002-11-24 06:01:20 +0000943 bytebuffer_offset--;
944 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000945 gunzip_bb >>= 8;
946 gunzip_bk -= 8;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000947 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000948 return 0;
949}
Glenn L McGrathcc616922003-02-09 04:46:34 +0000950
Glenn L McGrath5699b852003-11-15 23:19:05 +0000951extern int inflate_gunzip(int in, int out)
Glenn L McGrathcc616922003-02-09 04:46:34 +0000952{
953 unsigned int stored_crc = 0;
954 unsigned char count;
955
Glenn L McGrath5699b852003-11-15 23:19:05 +0000956 inflate_unzip(in, out);
957
Glenn L McGrathcc616922003-02-09 04:46:34 +0000958 /* top up the input buffer with the rest of the trailer */
959 count = bytebuffer_size - bytebuffer_offset;
960 if (count < 8) {
Glenn L McGrath5699b852003-11-15 23:19:05 +0000961 bb_xread_all(in, &bytebuffer[bytebuffer_size], 8 - count);
Glenn L McGrathcc616922003-02-09 04:46:34 +0000962 bytebuffer_size += 8 - count;
963 }
964 for (count = 0; count != 4; count++) {
965 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
966 bytebuffer_offset++;
967 }
968
969 /* Validate decompression - crc */
970 if (stored_crc != (gunzip_crc ^ 0xffffffffL)) {
Glenn L McGrath5699b852003-11-15 23:19:05 +0000971 bb_error_msg("crc error");
Glenn L McGrathcc616922003-02-09 04:46:34 +0000972 }
973
974 /* Validate decompression - size */
975 if (gunzip_bytes_out !=
976 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
977 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
Glenn L McGrath5699b852003-11-15 23:19:05 +0000978 bb_error_msg("Incorrect length");
Glenn L McGrathcc616922003-02-09 04:46:34 +0000979 }
Eric Andersenc7bda1c2004-03-15 08:29:22 +0000980
Glenn L McGrath5699b852003-11-15 23:19:05 +0000981 return 0;
Glenn L McGrathcc616922003-02-09 04:46:34 +0000982}