blob: 8da9b5cb990a3fd02879a1b14f58213bb211582f [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 Andersendb930942001-12-06 08:20:14 +000010 * Adjusted further by Erik Andersen <andersee@debian.org> to support
11 * 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>
16 *
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 McGrathcc616922003-02-09 04:46:34 +000086static unsigned 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 McGrathcc616922003-02-09 04:46:34 +000095static unsigned 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 */
106#define BYTEBUFFER_MAX 0x8000
107static 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
Glenn L McGrathf3faf412002-12-01 21:52:40 +0000147static void fill_bytebuffer(void)
Glenn L McGratheda4f532002-11-24 06:01:20 +0000148{
149 if (bytebuffer_offset >= bytebuffer_size) {
150 /* Leave the first 4 bytes empty so we can always unwind the bitbuffer
151 * to the front of the bytebuffer, leave 4 bytes free at end of tail
152 * so we can easily top up buffer in check_trailer_gzip() */
153 bytebuffer_size = 4 + xread(gunzip_src_fd, &bytebuffer[4], BYTEBUFFER_MAX - 8);
154 bytebuffer_offset = 4;
155 }
156}
157
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000158static unsigned int fill_bitbuffer(unsigned int bitbuffer, unsigned int *current, const unsigned int required)
159{
160 while (*current < required) {
Glenn L McGratheda4f532002-11-24 06:01:20 +0000161 fill_bytebuffer();
162 bitbuffer |= ((unsigned int) bytebuffer[bytebuffer_offset]) << *current;
163 bytebuffer_offset++;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000164 *current += 8;
165 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000166 return(bitbuffer);
167}
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000168
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000169static void make_gunzip_crc_table(void)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000170{
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000171 const unsigned int poly = 0xedb88320; /* polynomial exclusive-or pattern */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000172 unsigned short i; /* counter for all possible eight bit values */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000173
Eric Andersen89de1e72002-03-20 13:30:40 +0000174 /* initial shift register value */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000175 gunzip_crc = 0xffffffffL;
176 gunzip_crc_table = (unsigned int *) malloc(256 * sizeof(unsigned int));
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000177
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000178 /* Compute and print table of CRC's, five per line */
179 for (i = 0; i < 256; i++) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000180 unsigned int table_entry; /* crc shift register */
181 unsigned char k; /* byte being shifted into crc apparatus */
Glenn L McGrathef03dbc2001-12-05 13:08:03 +0000182
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000183 table_entry = i;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000184 /* The idea to initialize the register with the byte instead of
185 * zero was stolen from Haruhiko Okumura's ar002
186 */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000187 for (k = 8; k; k--) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000188 if (table_entry & 1) {
189 table_entry = (table_entry >> 1) ^ poly;
190 } else {
191 table_entry >>= 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000192 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000193 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000194 gunzip_crc_table[i] = table_entry;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000195 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000196}
197
198/*
199 * Free the malloc'ed tables built by huft_build(), which makes a linked
200 * list of the tables it made, with the links in a dummy first entry of
201 * each table.
202 * t: table to free
203 */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000204static int huft_free(huft_t * t)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000205{
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000206 huft_t *p;
207 huft_t *q;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000208
209 /* Go through linked list, freeing from the malloced (t[-1]) address. */
210 p = t;
211 while (p != (huft_t *) NULL) {
212 q = (--p)->v.t;
213 free((char *) p);
214 p = q;
215 }
216 return 0;
217}
218
219/* Given a list of code lengths and a maximum table size, make a set of
220 * tables to decode that set of codes. Return zero on success, one if
221 * the given code set is incomplete (the tables are still built in this
222 * case), two if the input is invalid (all zero length codes or an
223 * oversubscribed set of lengths), and three if not enough memory.
224 *
225 * b: code lengths in bits (all assumed <= BMAX)
226 * n: number of codes (assumed <= N_MAX)
227 * s: number of simple-valued codes (0..s-1)
228 * d: list of base values for non-simple codes
229 * e: list of extra bits for non-simple codes
230 * t: result: starting table
231 * m: maximum lookup bits, returns actual
232 */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000233static int huft_build(unsigned int *b, const unsigned int n,
234 const unsigned int s, const unsigned short *d,
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000235 const unsigned char *e, huft_t ** t, int *m)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000236{
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000237 unsigned a; /* counter for codes of length k */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000238 unsigned c[BMAX + 1]; /* bit length count table */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000239 unsigned f; /* i repeats in table every f entries */
240 int g; /* maximum code length */
241 int h; /* table level */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000242 register unsigned i; /* counter, current code */
243 register unsigned j; /* counter */
244 register int k; /* number of bits in current code */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000245 int l; /* bits per table (returned in m) */
246 register unsigned *p; /* pointer into c[], b[], or v[] */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000247 register huft_t *q; /* points to current table */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000248 huft_t r; /* table entry for structure assignment */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000249 huft_t *u[BMAX]; /* table stack */
250 unsigned v[N_MAX]; /* values in order of bit length */
251 register int w; /* bits before this table == (l * h) */
252 unsigned x[BMAX + 1]; /* bit offsets, then code stack */
253 unsigned *xp; /* pointer into x */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000254 int y; /* number of dummy codes added */
255 unsigned z; /* number of entries in current table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000256
257 /* Generate counts for each bit length */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000258 memset((void *) (c), 0, sizeof(c));
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000259 p = b;
260 i = n;
261 do {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000262 c[*p]++; /* assume all entries <= BMAX */
263 p++; /* Can't combine with above line (Solaris bug) */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000264 } while (--i);
265 if (c[0] == n) { /* null input--all zero length codes */
266 *t = (huft_t *) NULL;
267 *m = 0;
268 return 0;
269 }
270
271 /* Find minimum and maximum length, bound *m by those */
272 l = *m;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000273 for (j = 1; j <= BMAX; j++) {
274 if (c[j]) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000275 break;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000276 }
277 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000278 k = j; /* minimum code length */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000279 if ((unsigned) l < j) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000280 l = j;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000281 }
282 for (i = BMAX; i; i--) {
283 if (c[i]) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000284 break;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000285 }
286 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000287 g = i; /* maximum code length */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000288 if ((unsigned) l > i) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000289 l = i;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000290 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000291 *m = l;
292
293 /* Adjust last length count to fill out codes, if needed */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000294 for (y = 1 << j; j < i; j++, y <<= 1) {
295 if ((y -= c[j]) < 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000296 return 2; /* bad input: more codes than bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000297 }
298 }
299 if ((y -= c[i]) < 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000300 return 2;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000301 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000302 c[i] += y;
303
304 /* Generate starting offsets into the value table for each length */
305 x[1] = j = 0;
306 p = c + 1;
307 xp = x + 2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000308 while (--i) { /* note that i == g from above */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000309 *xp++ = (j += *p++);
310 }
311
312 /* Make a table of values in order of bit lengths */
313 p = b;
314 i = 0;
315 do {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000316 if ((j = *p++) != 0) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000317 v[x[j]++] = i;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000318 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000319 } while (++i < n);
320
321 /* Generate the Huffman codes and for each, make the table entries */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000322 x[0] = i = 0; /* first Huffman code is zero */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000323 p = v; /* grab values in bit order */
324 h = -1; /* no tables yet--level -1 */
325 w = -l; /* bits decoded == (l * h) */
326 u[0] = (huft_t *) NULL; /* just to keep compilers happy */
327 q = (huft_t *) NULL; /* ditto */
328 z = 0; /* ditto */
329
330 /* go through the bit lengths (k already is bits in shortest code) */
331 for (; k <= g; k++) {
332 a = c[k];
333 while (a--) {
334 /* here i is the Huffman code of length k bits for value *p */
335 /* make tables up to required level */
336 while (k > w + l) {
337 h++;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000338 w += l; /* previous table always l bits */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000339
340 /* compute minimum size table less than or equal to l bits */
341 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
342 if ((f = 1 << (j = k - w)) > a + 1) { /* try a k-w bit table *//* too few codes for k-w bit table */
343 f -= a + 1; /* deduct codes from patterns left */
344 xp = c + k;
345 while (++j < z) { /* try smaller tables up to z bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000346 if ((f <<= 1) <= *++xp) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000347 break; /* enough codes to use up j bits */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000348 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000349 f -= *xp; /* else deduct codes from patterns */
350 }
351 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000352 z = 1 << j; /* table entries for j-bit table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000353
354 /* allocate and link in new table */
Glenn L McGrath249f39a2001-12-05 16:01:02 +0000355 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
356
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000357 *t = q + 1; /* link to list for huft_free() */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000358 *(t = &(q->v.t)) = NULL;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000359 u[h] = ++q; /* table starts after link */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000360
361 /* connect to last table, if there is one */
362 if (h) {
363 x[h] = i; /* save pattern for backing up */
364 r.b = (unsigned char) l; /* bits to dump before this table */
365 r.e = (unsigned char) (16 + j); /* bits in this table */
366 r.v.t = q; /* pointer to this table */
367 j = i >> (w - l); /* (get around Turbo C bug) */
368 u[h - 1][j] = r; /* connect to last table */
369 }
370 }
371
372 /* set up table entry in r */
373 r.b = (unsigned char) (k - w);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000374 if (p >= v + n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000375 r.e = 99; /* out of values--invalid code */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000376 } else if (*p < s) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000377 r.e = (unsigned char) (*p < 256 ? 16 : 15); /* 256 is end-of-block code */
378 r.v.n = (unsigned short) (*p); /* simple code is just the value */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000379 p++; /* one compiler does not like *p++ */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000380 } else {
381 r.e = (unsigned char) e[*p - s]; /* non-simple--look up in lists */
382 r.v.n = d[*p++ - s];
383 }
384
385 /* fill code-like entries with r */
386 f = 1 << (k - w);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000387 for (j = i >> w; j < z; j += f) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000388 q[j] = r;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000389 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000390
391 /* backwards increment the k-bit code i */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000392 for (j = 1 << (k - 1); i & j; j >>= 1) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000393 i ^= j;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000394 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000395 i ^= j;
396
397 /* backup over finished tables */
398 while ((i & ((1 << w) - 1)) != x[h]) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000399 h--; /* don't need to update q */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000400 w -= l;
401 }
402 }
403 }
404 /* Return true (1) if we were given an incomplete table */
405 return y != 0 && g != 1;
406}
407
408/*
409 * inflate (decompress) the codes in a deflated (compressed) block.
410 * Return an error code or zero if it all goes ok.
411 *
412 * tl, td: literal/length and distance decoder tables
413 * bl, bd: number of bits decoded by tl[] and td[]
414 */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000415static 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 +0000416{
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000417 static unsigned int e; /* table entry flag/number of extra bits */
418 static unsigned int n, d; /* length and index for copy */
419 static unsigned int w; /* current gunzip_window position */
420 static huft_t *t; /* pointer to table entry */
421 static unsigned int ml, md; /* masks for bl and bd bits */
422 static unsigned int b; /* bit buffer */
423 static unsigned int k; /* number of bits in bit buffer */
424 static huft_t *tl, *td;
425 static unsigned int bl, bd;
426 static int resumeCopy = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000427
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000428 if (setup) { // 1st time we are called, copy in variables
429 tl = my_tl;
430 td = my_td;
431 bl = my_bl;
432 bd = my_bd;
433 /* make local copies of globals */
434 b = gunzip_bb; /* initialize bit buffer */
435 k = gunzip_bk;
436 w = gunzip_outbuf_count; /* initialize gunzip_window position */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000437
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000438 /* inflate the coded data */
439 ml = mask_bits[bl]; /* precompute masks for speed */
440 md = mask_bits[bd];
441 return 0; // Don't actually do anything the first time
442 }
443
444 if (resumeCopy) goto do_copy;
445
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000446 while (1) { /* do until end of block */
447 b = fill_bitbuffer(b, &k, bl);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000448 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000449 do {
450 if (e == 99) {
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000451 error_msg_and_die("inflate_codes error 1");;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000452 }
453 b >>= t->b;
454 k -= t->b;
455 e -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000456 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000457 } while ((e =
458 (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000459 b >>= t->b;
460 k -= t->b;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000461 if (e == 16) { /* then it's a literal */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000462 gunzip_window[w++] = (unsigned char) t->v.n;
463 if (w == gunzip_wsize) {
464 gunzip_outbuf_count = (w);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000465 //flush_gunzip_window();
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000466 w = 0;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000467 return 1; // We have a block to read
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000468 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000469 } else { /* it's an EOB or a length */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000470
471 /* exit if end of block */
472 if (e == 15) {
473 break;
474 }
475
476 /* get length of block to copy */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000477 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000478 n = t->v.n + ((unsigned) b & mask_bits[e]);
479 b >>= e;
480 k -= e;
481
482 /* decode distance of block to copy */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000483 b = fill_bitbuffer(b, &k, bd);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000484 if ((e = (t = td + ((unsigned) b & md))->e) > 16)
485 do {
486 if (e == 99)
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000487 error_msg_and_die("inflate_codes error 2");;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000488 b >>= t->b;
489 k -= t->b;
490 e -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000491 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000492 } while ((e =
493 (t =
494 t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000495 b >>= t->b;
496 k -= t->b;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000497 b = fill_bitbuffer(b, &k, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000498 d = w - t->v.n - ((unsigned) b & mask_bits[e]);
499 b >>= e;
500 k -= e;
501
502 /* do the copy */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000503do_copy: do {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000504 n -= (e =
505 (e =
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000506 gunzip_wsize - ((d &= gunzip_wsize - 1) > w ? d : w)) > n ? n : e);
507 /* copy to new buffer to prevent possible overwrite */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000508 if (w - d >= e) { /* (this test assumes unsigned comparison) */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000509 memcpy(gunzip_window + w, gunzip_window + d, e);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000510 w += e;
511 d += e;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000512 } else {
513 /* do it slow to avoid memcpy() overlap */
514 /* !NOMEMCPY */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000515 do {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000516 gunzip_window[w++] = gunzip_window[d++];
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000517 } while (--e);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000518 }
519 if (w == gunzip_wsize) {
520 gunzip_outbuf_count = (w);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000521 if (n) resumeCopy = 1;
522 else resumeCopy = 0;
523 //flush_gunzip_window();
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000524 w = 0;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000525 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000526 }
527 } while (n);
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000528 resumeCopy = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000529 }
530 }
531
532 /* restore the globals from the locals */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000533 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
534 gunzip_bb = b; /* restore global bit buffer */
535 gunzip_bk = k;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000536
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000537 /* normally just after call to inflate_codes, but save code by putting it here */
538 /* free the decoding tables, return */
539 huft_free(tl);
540 huft_free(td);
541
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000542 /* done */
543 return 0;
544}
545
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000546static int inflate_stored(int my_n, int my_b_stored, int my_k_stored, int setup)
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000547{
548 static int n, b_stored, k_stored, w;
549 if (setup) {
550 n = my_n;
551 b_stored = my_b_stored;
552 k_stored = my_k_stored;
553 w = gunzip_outbuf_count; /* initialize gunzip_window position */
554 return 0; // Don't do anything first time
555 }
556
557 /* read and output the compressed data */
558 while (n--) {
559 b_stored = fill_bitbuffer(b_stored, &k_stored, 8);
560 gunzip_window[w++] = (unsigned char) b_stored;
561 if (w == (unsigned int) gunzip_wsize) {
562 gunzip_outbuf_count = (w);
563 //flush_gunzip_window();
564 w = 0;
565 b_stored >>= 8;
566 k_stored -= 8;
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000567 return 1; // We have a block
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000568 }
569 b_stored >>= 8;
570 k_stored -= 8;
571 }
572
573 /* restore the globals from the locals */
574 gunzip_outbuf_count = w; /* restore global gunzip_window pointer */
575 gunzip_bb = b_stored; /* restore global bit buffer */
576 gunzip_bk = k_stored;
577 return 0; // Finished
578}
579
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000580/*
581 * decompress an inflated block
582 * e: last block flag
583 *
584 * GLOBAL VARIABLES: bb, kk,
585 */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000586 // Return values: -1 = inflate_stored, -2 = inflate_codes
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000587static int inflate_block(int *e)
588{
589 unsigned t; /* block type */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000590 register unsigned int b; /* bit buffer */
591 unsigned int k; /* number of bits in bit buffer */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000592
593 /* make local bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000594
595 b = gunzip_bb;
596 k = gunzip_bk;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000597
598 /* read in last block bit */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000599 b = fill_bitbuffer(b, &k, 1);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000600 *e = (int) b & 1;
601 b >>= 1;
602 k -= 1;
603
604 /* read in block type */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000605 b = fill_bitbuffer(b, &k, 2);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000606 t = (unsigned) b & 3;
607 b >>= 2;
608 k -= 2;
609
610 /* restore the global bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000611 gunzip_bb = b;
612 gunzip_bk = k;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000613
614 /* inflate that block type */
615 switch (t) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000616 case 0: /* Inflate stored */
617 {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000618 unsigned int n; /* number of bytes in block */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000619 unsigned int b_stored; /* bit buffer */
620 unsigned int k_stored; /* number of bits in bit buffer */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000621
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000622 /* make local copies of globals */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000623 b_stored = gunzip_bb; /* initialize bit buffer */
624 k_stored = gunzip_bk;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000625
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000626 /* go to byte boundary */
627 n = k_stored & 7;
628 b_stored >>= n;
629 k_stored -= n;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000630
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000631 /* get the length and its complement */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000632 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000633 n = ((unsigned) b_stored & 0xffff);
634 b_stored >>= 16;
635 k_stored -= 16;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000636
637 b_stored = fill_bitbuffer(b_stored, &k_stored, 16);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000638 if (n != (unsigned) ((~b_stored) & 0xffff)) {
639 return 1; /* error in compressed data */
640 }
641 b_stored >>= 16;
642 k_stored -= 16;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000643
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000644 inflate_stored(n, b_stored, k_stored, 1); // Setup inflate_stored
645 return -1;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000646 }
647 case 1: /* Inflate fixed
648 * decompress an inflated type 1 (fixed Huffman codes) block. We should
649 * either replace this with a custom decoder, or at least precompute the
650 * Huffman tables.
651 */
652 {
653 int i; /* temporary variable */
654 huft_t *tl; /* literal/length code table */
655 huft_t *td; /* distance code table */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000656 unsigned int bl; /* lookup bits for tl */
657 unsigned int bd; /* lookup bits for td */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000658 unsigned int l[288]; /* length list for huft_build */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000659
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000660 /* set up literal table */
661 for (i = 0; i < 144; i++) {
662 l[i] = 8;
663 }
664 for (; i < 256; i++) {
665 l[i] = 9;
666 }
667 for (; i < 280; i++) {
668 l[i] = 7;
669 }
670 for (; i < 288; i++) { /* make a complete, but wrong code set */
671 l[i] = 8;
672 }
673 bl = 7;
674 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
675 return i;
676 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000677
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000678 /* set up distance table */
679 for (i = 0; i < 30; i++) { /* make an incomplete code set */
680 l[i] = 5;
681 }
682 bd = 5;
683 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000684 huft_free(tl);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000685 return i;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000686 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000687
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000688 /* decompress until an end-of-block code */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000689 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
690
691 /* huft_free code moved into inflate_codes */
692
693 return -2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000694 }
695 case 2: /* Inflate dynamic */
696 {
697 const int dbits = 6; /* bits in base distance lookup table */
698 const int lbits = 9; /* bits in base literal/length lookup table */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000699
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000700 huft_t *tl; /* literal/length code table */
701 huft_t *td; /* distance code table */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000702 unsigned int i; /* temporary variables */
703 unsigned int j;
704 unsigned int l; /* last length */
705 unsigned int m; /* mask for bit lengths table */
706 unsigned int n; /* number of lengths to get */
707 unsigned int bl; /* lookup bits for tl */
708 unsigned int bd; /* lookup bits for td */
709 unsigned int nb; /* number of bit length codes */
710 unsigned int nl; /* number of literal/length codes */
711 unsigned int nd; /* number of distance codes */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000712
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000713 unsigned int ll[286 + 30]; /* literal/length and distance code lengths */
714 unsigned int b_dynamic; /* bit buffer */
715 unsigned int k_dynamic; /* number of bits in bit buffer */
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000716
717 /* make local bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000718 b_dynamic = gunzip_bb;
719 k_dynamic = gunzip_bk;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000720
721 /* read in table lengths */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000722 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 5);
723 nl = 257 + ((unsigned int) b_dynamic & 0x1f); /* number of literal/length 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, 5);
728 nd = 1 + ((unsigned int) b_dynamic & 0x1f); /* number of distance codes */
729
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000730 b_dynamic >>= 5;
731 k_dynamic -= 5;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000732 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 4);
733 nb = 4 + ((unsigned int) b_dynamic & 0xf); /* number of bit length codes */
734
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000735 b_dynamic >>= 4;
736 k_dynamic -= 4;
737 if (nl > 286 || nd > 30) {
738 return 1; /* bad lengths */
739 }
740
741 /* read in bit-length-code lengths */
742 for (j = 0; j < nb; j++) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000743 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
744 ll[border[j]] = (unsigned int) b_dynamic & 7;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000745 b_dynamic >>= 3;
746 k_dynamic -= 3;
747 }
748 for (; j < 19; j++) {
749 ll[border[j]] = 0;
750 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000751
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000752 /* build decoding table for trees--single level, 7 bit lookup */
753 bl = 7;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000754 i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl);
755 if (i != 0) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000756 if (i == 1) {
757 huft_free(tl);
758 }
759 return i; /* incomplete code set */
760 }
761
762 /* read in literal and distance code lengths */
763 n = nl + nd;
764 m = mask_bits[bl];
765 i = l = 0;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000766 while ((unsigned int) i < n) {
767 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, (unsigned int)bl);
768 j = (td = tl + ((unsigned int) b_dynamic & m))->b;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000769 b_dynamic >>= j;
770 k_dynamic -= j;
771 j = td->v.n;
772 if (j < 16) { /* length of code in bits (0..15) */
773 ll[i++] = l = j; /* save last length in l */
774 } else if (j == 16) { /* repeat last length 3 to 6 times */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000775 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 2);
776 j = 3 + ((unsigned int) b_dynamic & 3);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000777 b_dynamic >>= 2;
778 k_dynamic -= 2;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000779 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000780 return 1;
781 }
782 while (j--) {
783 ll[i++] = l;
784 }
785 } else if (j == 17) { /* 3 to 10 zero length codes */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000786 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 3);
787 j = 3 + ((unsigned int) b_dynamic & 7);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000788 b_dynamic >>= 3;
789 k_dynamic -= 3;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000790 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000791 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000792 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000793 while (j--) {
794 ll[i++] = 0;
795 }
796 l = 0;
797 } else { /* j == 18: 11 to 138 zero length codes */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000798 b_dynamic = fill_bitbuffer(b_dynamic, &k_dynamic, 7);
799 j = 11 + ((unsigned int) b_dynamic & 0x7f);
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000800 b_dynamic >>= 7;
801 k_dynamic -= 7;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000802 if ((unsigned int) i + j > n) {
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000803 return 1;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000804 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000805 while (j--) {
806 ll[i++] = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000807 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000808 l = 0;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000809 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000810 }
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000811
812 /* free decoding table for trees */
813 huft_free(tl);
814
815 /* restore the global bit buffer */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000816 gunzip_bb = b_dynamic;
817 gunzip_bk = k_dynamic;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000818
819 /* build the decoding tables for literal/length and distance codes */
820 bl = lbits;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000821
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000822 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
823 if (i == 1) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000824 error_msg_and_die("Incomplete literal tree");
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000825 huft_free(tl);
826 }
827 return i; /* incomplete code set */
828 }
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000829
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000830 bd = dbits;
831 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
832 if (i == 1) {
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000833 error_msg_and_die("incomplete distance tree");
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000834 huft_free(td);
835 }
836 huft_free(tl);
837 return i; /* incomplete code set */
838 }
839
840 /* decompress until an end-of-block code */
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000841 inflate_codes(tl, td, bl, bd, 1); // Setup inflate_codes
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000842
Glenn L McGrath0126fda2002-11-20 06:46:46 +0000843 /* huft_free code moved into inflate_codes */
844
845 return -2;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000846 }
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000847 default:
848 /* bad block type */
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000849 error_msg_and_die("bad block type %d\n", t);
850 }
851}
852
853static void calculate_gunzip_crc(void)
854{
855 int n;
856 for (n = 0; n < gunzip_outbuf_count; n++) {
857 gunzip_crc = gunzip_crc_table[((int) gunzip_crc ^ (gunzip_window[n])) & 0xff] ^ (gunzip_crc >> 8);
858 }
859 gunzip_bytes_out += gunzip_outbuf_count;
860}
861
862static int inflate_get_next_window(void)
863{
864 static int needAnotherBlock = 1;
865 static int method = -1; // Method == -1 for stored, -2 for codes
866 static int e = 0;
867
868 gunzip_outbuf_count = 0;
869
870 while(1) {
871 int ret;
872
873 if (needAnotherBlock) {
Glenn L McGratheda4f532002-11-24 06:01:20 +0000874 if(e) {
875 calculate_gunzip_crc();
876 return 0;
877 } // Last block
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000878 method = inflate_block(&e);
879 needAnotherBlock = 0;
880 }
881
882 switch (method) {
883 case -1: ret = inflate_stored(0,0,0,0);
884 break;
885 case -2: ret = inflate_codes(0,0,0,0,0);
886 break;
887 default: error_msg_and_die("inflate error %d", method);
888 }
889
890 if (ret == 1) {
891 calculate_gunzip_crc();
892 return 1; // More data left
893 } else needAnotherBlock = 1; // End of that block
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000894 }
Glenn L McGratheda4f532002-11-24 06:01:20 +0000895 /* Doesnt get here */
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000896}
897
898/*
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000899 * User functions
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000900 *
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000901 * read_gz, GZ_gzReadOpen, GZ_gzReadClose, inflate
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000902 */
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000903
904extern ssize_t read_gz(int fd, void *buf, size_t count)
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000905{
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000906 static int morebytes = 0, finished = 0;
907
908 if (morebytes) {
909 int bytesRead = morebytes > count ? count : morebytes;
910 memcpy(buf, gunzip_window + (gunzip_outbuf_count - morebytes), bytesRead);
911 morebytes -= bytesRead;
912 return bytesRead;
913 } else if (finished) {
914 return 0;
915 } else if (count >= 0x8000) { // We can decompress direcly to the buffer, 32k at a time
916 // Could decompress to larger buffer, but it must be a power of 2, and calculating that is probably more expensive than the benefit
917 unsigned char *old_gunzip_window = gunzip_window; // Save old window
918 gunzip_window = buf;
919 if (inflate_get_next_window() == 0) finished = 1;
920 gunzip_window = old_gunzip_window; // Restore old window
921 return gunzip_outbuf_count;
922 } else { // Oh well, need to split up the gunzip_window
923 int bytesRead;
924 if (inflate_get_next_window() == 0) finished = 1;
925 morebytes = gunzip_outbuf_count;
926 bytesRead = morebytes > count ? count : morebytes;
927 memcpy(buf, gunzip_window, bytesRead);
928 morebytes -= bytesRead;
929 return bytesRead;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000930 }
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000931
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000932}
933
934extern void GZ_gzReadOpen(int fd, void *unused, int nUnused)
935{
936 typedef void (*sig_type) (int);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000937
Glenn L McGrath87ac7022002-01-02 13:52:26 +0000938 /* Allocate all global buffers (for DYN_ALLOC option) */
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000939 gunzip_window = xmalloc(gunzip_wsize);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000940 gunzip_outbuf_count = 0;
941 gunzip_bytes_out = 0;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000942 gunzip_src_fd = fd;
Glenn L McGrath249f39a2001-12-05 16:01:02 +0000943
Glenn L McGratheda4f532002-11-24 06:01:20 +0000944 /* Input buffer */
945 bytebuffer = xmalloc(BYTEBUFFER_MAX);
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000946
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000947 /* initialize gunzip_window, bit buffer */
948 gunzip_bk = 0;
949 gunzip_bb = 0;
Glenn L McGrath9fef17d2002-08-22 18:41:20 +0000950
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000951 /* Create the crc table */
952 make_gunzip_crc_table();
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000953}
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000954
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000955extern void GZ_gzReadClose(void)
956{
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000957 /* Cleanup */
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000958 free(gunzip_window);
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000959 free(gunzip_crc_table);
960
961 /* Store unused bytes in a global buffer so calling applets can access it */
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000962 if (gunzip_bk >= 8) {
963 /* Undo too much lookahead. The next read will be byte aligned
964 * so we can discard unused bits in the last meaningful byte. */
Glenn L McGratheda4f532002-11-24 06:01:20 +0000965 bytebuffer_offset--;
966 bytebuffer[bytebuffer_offset] = gunzip_bb & 0xff;
Glenn L McGrath7ca04f32002-09-25 02:47:48 +0000967 gunzip_bb >>= 8;
968 gunzip_bk -= 8;
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000969 }
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000970}
Glenn L McGrath7fd92942001-04-11 03:11:33 +0000971
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000972/*extern int inflate(int in, int out) // Useful for testing read_gz
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000973{
974 char buf[8192];
975 ssize_t nread, nwrote;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +0000976
977 GZ_gzReadOpen(in, 0, 0);
978 while(1) { // Robbed from copyfd.c
979 nread = read_gz(in, buf, sizeof(buf));
980 if (nread == 0) break; // no data to write
981 else if (nread == -1) {
982 perror_msg("read");
983 return -1;
984 }
985 nwrote = full_write(out, buf, nread);
986 if (nwrote == -1) {
987 perror_msg("write");
988 return -1;
989 }
Glenn L McGrath83bf47c2002-11-20 22:00:31 +0000990 }
991 GZ_gzReadClose();
992 return 0;
993}*/
994
995extern int inflate(int in, int out)
996{
997 ssize_t nwrote;
998 GZ_gzReadOpen(in, 0, 0);
999 while(1) {
1000 int ret = inflate_get_next_window();
1001 nwrote = full_write(out, gunzip_window, gunzip_outbuf_count);
1002 if (nwrote == -1) {
1003 perror_msg("write");
1004 return -1;
1005 }
1006 if (ret == 0) break;
Glenn L McGrathfd73b8c2002-11-17 21:33:30 +00001007 }
1008 GZ_gzReadClose();
Glenn L McGrath7fd92942001-04-11 03:11:33 +00001009 return 0;
1010}
Glenn L McGrathcc616922003-02-09 04:46:34 +00001011
1012extern void check_trailer_gzip(int src_fd)
1013{
1014 unsigned int stored_crc = 0;
1015 unsigned char count;
1016
1017 /* top up the input buffer with the rest of the trailer */
1018 count = bytebuffer_size - bytebuffer_offset;
1019 if (count < 8) {
1020 xread_all(src_fd, &bytebuffer[bytebuffer_size], 8 - count);
1021 bytebuffer_size += 8 - count;
1022 }
1023 for (count = 0; count != 4; count++) {
1024 stored_crc |= (bytebuffer[bytebuffer_offset] << (count * 8));
1025 bytebuffer_offset++;
1026 }
1027
1028 /* Validate decompression - crc */
1029 if (stored_crc != (gunzip_crc ^ 0xffffffffL)) {
1030 error_msg_and_die("crc error");
1031 }
1032
1033 /* Validate decompression - size */
1034 if (gunzip_bytes_out !=
1035 (bytebuffer[bytebuffer_offset] | (bytebuffer[bytebuffer_offset+1] << 8) |
1036 (bytebuffer[bytebuffer_offset+2] << 16) | (bytebuffer[bytebuffer_offset+3] << 24))) {
1037 error_msg_and_die("Incorrect length, but crc is correct");
1038 }
1039
1040}