Apply vodz' last_patch52
[oweals/busybox.git] / libbb / unzip.c
1 /* 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  *
10  * Adjusted further by Erik Andersen <andersee@debian.org> to support
11  * files as well as stdin/stdout, and to generally behave itself wrt
12  * 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  * 
17  * This program is free software; you can redistribute it and/or modify
18  * it under the terms of the GNU General Public License as published by
19  * the Free Software Foundation; either version 2 of the License, or
20  * (at your option) any later version.
21  *
22  * This program is distributed in the hope that it will be useful,
23  * but WITHOUT ANY WARRANTY; without even the implied warranty of
24  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
25  * General Public License for more details.
26  *
27  * You should have received a copy of the GNU General Public License
28  * along with this program; if not, write to the Free Software
29  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
30  *
31  *
32  * gzip (GNU zip) -- compress files with zip algorithm and 'compress' interface
33  * Copyright (C) 1992-1993 Jean-loup Gailly
34  * The unzip code was written and put in the public domain by Mark Adler.
35  * Portions of the lzw code are derived from the public domain 'compress'
36  * written by Spencer Thomas, Joe Orost, James Woods, Jim McKie, Steve Davies,
37  * Ken Turkowski, Dave Mack and Peter Jannesen.
38  *
39  * See the license_msg below and the file COPYING for the software license.
40  * See the file algorithm.doc for the compression algorithms and file formats.
41  */
42
43 #if 0
44 static char *license_msg[] = {
45         "   Copyright (C) 1992-1993 Jean-loup Gailly",
46         "   This program is free software; you can redistribute it and/or modify",
47         "   it under the terms of the GNU General Public License as published by",
48         "   the Free Software Foundation; either version 2, or (at your option)",
49         "   any later version.",
50         "",
51         "   This program is distributed in the hope that it will be useful,",
52         "   but WITHOUT ANY WARRANTY; without even the implied warranty of",
53         "   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the",
54         "   GNU General Public License for more details.",
55         "",
56         "   You should have received a copy of the GNU General Public License",
57         "   along with this program; if not, write to the Free Software",
58         "   Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.",
59         0
60 };
61 #endif
62
63 #include <sys/types.h>
64 #include <sys/wait.h>
65 #include <signal.h>
66 #include <stdlib.h>
67 #include <string.h>
68 #include "config.h"
69 #include "libbb.h"
70
71 #ifdef CONFIG_FEATURE_UNCOMPRESS
72 int uncompress(FILE * in, FILE * out);
73 #endif
74
75 static FILE *in_file, *out_file;
76
77 /* these are freed by gz_close */
78 static unsigned char *window;
79 static unsigned long *crc_table;
80
81 static unsigned long crc;       /* shift register contents */
82
83 /* Return codes from gzip */
84 #define ERROR 1
85
86 /*
87  * window size--must be a power of two, and
88  *  at least 32K for zip's deflate method
89  */
90 #define WSIZE 0x8000
91
92 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
93 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
94 #define N_MAX 288       /* maximum number of codes in any set */
95
96 static long bytes_out;  /* number of output bytes */
97 static unsigned long outcnt;    /* bytes in output buffer */
98
99 static unsigned hufts;  /* track memory usage */
100 static unsigned long bb;        /* bit buffer */
101 static unsigned bk;             /* bits in bit buffer */
102
103 typedef struct huft_s {
104         unsigned char e;        /* number of extra bits or operation */
105         unsigned char b;        /* number of bits in this code or subcode */
106         union {
107                 unsigned short n;       /* literal, length base, or distance base */
108                 struct huft_s *t;       /* pointer to next level of table */
109         } v;
110 } huft_t;
111
112 static const unsigned short mask_bits[] = {
113         0x0000,
114         0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
115         0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
116 };
117
118 /* static int error_number = 0; */
119 /* ========================================================================
120  * Signal and error handler.
121  */
122
123 static void abort_gzip(void)
124 {
125         error_msg("gzip aborted\n");
126         exit(ERROR);
127 }
128
129 static void make_crc_table(void)
130 {
131         const unsigned long poly = 0xedb88320;  /* polynomial exclusive-or pattern */
132         unsigned short i;       /* counter for all possible eight bit values */
133
134         /* initial shift register value */
135         crc = 0xffffffffL;
136         crc_table = (unsigned long *) malloc(256 * sizeof(unsigned long));
137
138         /* Compute and print table of CRC's, five per line */
139         for (i = 0; i < 256; i++) {
140                 unsigned long table_entry;      /* crc shift register */
141                 char k;                 /* byte being shifted into crc apparatus */
142
143                 table_entry = i;
144                 /* The idea to initialize the register with the byte instead of
145                    * zero was stolen from Haruhiko Okumura's ar002
146                  */
147                 for (k = 8; k; k--) {
148                         table_entry =
149                                 table_entry & 1 ? (table_entry >> 1) ^ poly : table_entry >>
150                                 1;
151                 }
152                 crc_table[i] = table_entry;
153         }
154 }
155
156 /* ===========================================================================
157  * Write the output window window[0..outcnt-1] and update crc and bytes_out.
158  * (Used for the decompressed data only.)
159  */
160 static void flush_window(void)
161 {
162         int n;
163
164         if (outcnt == 0)
165                 return;
166
167         for (n = 0; n < outcnt; n++) {
168                 crc = crc_table[((int) crc ^ (window[n])) & 0xff] ^ (crc >> 8);
169         }
170
171         if (fwrite(window, 1, outcnt, out_file) != outcnt) {
172                 error_msg_and_die("Couldnt write");
173         }
174         bytes_out += (unsigned long) outcnt;
175         outcnt = 0;
176 }
177
178 /*
179  * Free the malloc'ed tables built by huft_build(), which makes a linked
180  * list of the tables it made, with the links in a dummy first entry of
181  * each table. 
182  * t: table to free
183  */
184 static int huft_free(huft_t * t)
185 {
186         huft_t *p, *q;
187
188         /* Go through linked list, freeing from the malloced (t[-1]) address. */
189         p = t;
190         while (p != (huft_t *) NULL) {
191                 q = (--p)->v.t;
192                 free((char *) p);
193                 p = q;
194         }
195         return 0;
196 }
197
198 typedef unsigned char extra_bits_t;
199
200 /* Given a list of code lengths and a maximum table size, make a set of
201  * tables to decode that set of codes.  Return zero on success, one if
202  * the given code set is incomplete (the tables are still built in this
203  * case), two if the input is invalid (all zero length codes or an
204  * oversubscribed set of lengths), and three if not enough memory.
205  *
206  * b:   code lengths in bits (all assumed <= BMAX)
207  * n:   number of codes (assumed <= N_MAX)
208  * s:   number of simple-valued codes (0..s-1)
209  * d:   list of base values for non-simple codes
210  * e:   list of extra bits for non-simple codes
211  * t:   result: starting table
212  * m:   maximum lookup bits, returns actual
213  */
214 static int huft_build(unsigned int *b, const unsigned int n,
215                                           const unsigned int s, const unsigned short *d,
216                                           const extra_bits_t * e, huft_t ** t, int *m)
217 {
218         unsigned a;                     /* counter for codes of length k */
219         unsigned c[BMAX + 1];   /* bit length count table */
220         unsigned f;                     /* i repeats in table every f entries */
221         int g;                          /* maximum code length */
222         int h;                          /* table level */
223         register unsigned i;    /* counter, current code */
224         register unsigned j;    /* counter */
225         register int k;         /* number of bits in current code */
226         int l;                          /* bits per table (returned in m) */
227         register unsigned *p;   /* pointer into c[], b[], or v[] */
228         register huft_t *q;     /* points to current table */
229         huft_t r;                       /* table entry for structure assignment */
230         huft_t *u[BMAX];        /* table stack */
231         unsigned v[N_MAX];      /* values in order of bit length */
232         register int w;         /* bits before this table == (l * h) */
233         unsigned x[BMAX + 1];   /* bit offsets, then code stack */
234         unsigned *xp;           /* pointer into x */
235         int y;                          /* number of dummy codes added */
236         unsigned z;                     /* number of entries in current table */
237
238         /* Generate counts for each bit length */
239         memset((void *) (c), 0, sizeof(c));
240         p = b;
241         i = n;
242         do {
243                 c[*p]++;                /* assume all entries <= BMAX */
244                 p++;                    /* Can't combine with above line (Solaris bug) */
245         } while (--i);
246         if (c[0] == n) {        /* null input--all zero length codes */
247                 *t = (huft_t *) NULL;
248                 *m = 0;
249                 return 0;
250         }
251
252         /* Find minimum and maximum length, bound *m by those */
253         l = *m;
254         for (j = 1; j <= BMAX; j++)
255                 if (c[j])
256                         break;
257         k = j;                          /* minimum code length */
258         if ((unsigned) l < j)
259                 l = j;
260         for (i = BMAX; i; i--)
261                 if (c[i])
262                         break;
263         g = i;                          /* maximum code length */
264         if ((unsigned) l > i)
265                 l = i;
266         *m = l;
267
268         /* Adjust last length count to fill out codes, if needed */
269         for (y = 1 << j; j < i; j++, y <<= 1)
270                 if ((y -= c[j]) < 0)
271                         return 2;       /* bad input: more codes than bits */
272         if ((y -= c[i]) < 0)
273                 return 2;
274         c[i] += y;
275
276         /* Generate starting offsets into the value table for each length */
277         x[1] = j = 0;
278         p = c + 1;
279         xp = x + 2;
280         while (--i) {           /* note that i == g from above */
281                 *xp++ = (j += *p++);
282         }
283
284         /* Make a table of values in order of bit lengths */
285         p = b;
286         i = 0;
287         do {
288                 if ((j = *p++) != 0)
289                         v[x[j]++] = i;
290         } while (++i < n);
291
292         /* Generate the Huffman codes and for each, make the table entries */
293         x[0] = i = 0;           /* first Huffman code is zero */
294         p = v;                          /* grab values in bit order */
295         h = -1;                         /* no tables yet--level -1 */
296         w = -l;                         /* bits decoded == (l * h) */
297         u[0] = (huft_t *) NULL; /* just to keep compilers happy */
298         q = (huft_t *) NULL;    /* ditto */
299         z = 0;                          /* ditto */
300
301         /* go through the bit lengths (k already is bits in shortest code) */
302         for (; k <= g; k++) {
303                 a = c[k];
304                 while (a--) {
305                         /* here i is the Huffman code of length k bits for value *p */
306                         /* make tables up to required level */
307                         while (k > w + l) {
308                                 h++;
309                                 w += l; /* previous table always l bits */
310
311                                 /* compute minimum size table less than or equal to l bits */
312                                 z = (z = g - w) > (unsigned) l ? l : z; /* upper limit on table size */
313                                 if ((f = 1 << (j = k - w)) > a + 1) {   /* try a k-w bit table *//* too few codes for k-w bit table */
314                                         f -= a + 1;     /* deduct codes from patterns left */
315                                         xp = c + k;
316                                         while (++j < z) {       /* try smaller tables up to z bits */
317                                                 if ((f <<= 1) <= *++xp)
318                                                         break;  /* enough codes to use up j bits */
319                                                 f -= *xp;       /* else deduct codes from patterns */
320                                         }
321                                 }
322                                 z = 1 << j;     /* table entries for j-bit table */
323
324                                 /* allocate and link in new table */
325                                 q = (huft_t *) xmalloc((z + 1) * sizeof(huft_t));
326
327                                 hufts += z + 1; /* track memory usage */
328                                 *t = q + 1;     /* link to list for huft_free() */
329                                 *(t = &(q->v.t)) = NULL;
330                                 u[h] = ++q;     /* table starts after link */
331
332                                 /* connect to last table, if there is one */
333                                 if (h) {
334                                         x[h] = i;       /* save pattern for backing up */
335                                         r.b = (unsigned char) l;        /* bits to dump before this table */
336                                         r.e = (unsigned char) (16 + j); /* bits in this table */
337                                         r.v.t = q;      /* pointer to this table */
338                                         j = i >> (w - l);       /* (get around Turbo C bug) */
339                                         u[h - 1][j] = r;        /* connect to last table */
340                                 }
341                         }
342
343                         /* set up table entry in r */
344                         r.b = (unsigned char) (k - w);
345                         if (p >= v + n)
346                                 r.e = 99;       /* out of values--invalid code */
347                         else if (*p < s) {
348                                 r.e = (unsigned char) (*p < 256 ? 16 : 15);     /* 256 is end-of-block code */
349                                 r.v.n = (unsigned short) (*p);  /* simple code is just the value */
350                                 p++;    /* one compiler does not like *p++ */
351                         } else {
352                                 r.e = (unsigned char) e[*p - s];        /* non-simple--look up in lists */
353                                 r.v.n = d[*p++ - s];
354                         }
355
356                         /* fill code-like entries with r */
357                         f = 1 << (k - w);
358                         for (j = i >> w; j < z; j += f)
359                                 q[j] = r;
360
361                         /* backwards increment the k-bit code i */
362                         for (j = 1 << (k - 1); i & j; j >>= 1)
363                                 i ^= j;
364                         i ^= j;
365
366                         /* backup over finished tables */
367                         while ((i & ((1 << w) - 1)) != x[h]) {
368                                 h--;    /* don't need to update q */
369                                 w -= l;
370                         }
371                 }
372         }
373         /* Return true (1) if we were given an incomplete table */
374         return y != 0 && g != 1;
375 }
376
377 /*
378  * inflate (decompress) the codes in a deflated (compressed) block.
379  * Return an error code or zero if it all goes ok.
380  *
381  * tl, td: literal/length and distance decoder tables
382  * bl, bd: number of bits decoded by tl[] and td[]
383  */
384 static int inflate_codes(huft_t * tl, huft_t * td, int bl, int bd)
385 {
386         register unsigned long e;       /* table entry flag/number of extra bits */
387         unsigned long n, d;     /* length and index for copy */
388         unsigned long w;        /* current window position */
389         huft_t *t;                      /* pointer to table entry */
390         unsigned ml, md;        /* masks for bl and bd bits */
391         register unsigned long b;       /* bit buffer */
392         register unsigned k;    /* number of bits in bit buffer */
393
394         /* make local copies of globals */
395         b = bb;                         /* initialize bit buffer */
396         k = bk;
397         w = outcnt;                     /* initialize window position */
398
399         /* inflate the coded data */
400         ml = mask_bits[bl];     /* precompute masks for speed */
401         md = mask_bits[bd];
402         for (;;) {                      /* do until end of block */
403                 while (k < (unsigned) bl) {
404                         b |= ((unsigned long) fgetc(in_file)) << k;
405                         k += 8;
406                 }
407                 if ((e = (t = tl + ((unsigned) b & ml))->e) > 16)
408                         do {
409                                 if (e == 99) {
410                                         return 1;
411                                 }
412                                 b >>= t->b;
413                                 k -= t->b;
414                                 e -= 16;
415                                 while (k < e) {
416                                         b |= ((unsigned long) fgetc(in_file)) << k;
417                                         k += 8;
418                                 }
419                         } while ((e =
420                                           (t = t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
421                 b >>= t->b;
422                 k -= t->b;
423                 if (e == 16) {  /* then it's a literal */
424                         window[w++] = (unsigned char) t->v.n;
425                         if (w == WSIZE) {
426                                 outcnt = (w), flush_window();
427                                 w = 0;
428                         }
429                 } else {                /* it's an EOB or a length */
430
431                         /* exit if end of block */
432                         if (e == 15) {
433                                 break;
434                         }
435
436                         /* get length of block to copy */
437                         while (k < e) {
438                                 b |= ((unsigned long) fgetc(in_file)) << k;
439                                 k += 8;
440                         }
441                         n = t->v.n + ((unsigned) b & mask_bits[e]);
442                         b >>= e;
443                         k -= e;
444
445                         /* decode distance of block to copy */
446                         while (k < (unsigned) bd) {
447                                 b |= ((unsigned long) fgetc(in_file)) << k;
448                                 k += 8;
449                         }
450
451                         if ((e = (t = td + ((unsigned) b & md))->e) > 16)
452                                 do {
453                                         if (e == 99)
454                                                 return 1;
455                                         b >>= t->b;
456                                         k -= t->b;
457                                         e -= 16;
458                                         while (k < e) {
459                                                 b |= ((unsigned long) fgetc(in_file)) << k;
460                                                 k += 8;
461                                         }
462                                 } while ((e =
463                                                   (t =
464                                                    t->v.t + ((unsigned) b & mask_bits[e]))->e) > 16);
465                         b >>= t->b;
466                         k -= t->b;
467                         while (k < e) {
468                                 b |= ((unsigned long) fgetc(in_file)) << k;
469                                 k += 8;
470                         }
471                         d = w - t->v.n - ((unsigned) b & mask_bits[e]);
472                         b >>= e;
473                         k -= e;
474
475                         /* do the copy */
476                         do {
477                                 n -= (e =
478                                           (e =
479                                            WSIZE - ((d &= WSIZE - 1) > w ? d : w)) > n ? n : e);
480 #if !defined(NOMEMCPY) && !defined(DEBUG)
481                                 if (w - d >= e) {       /* (this test assumes unsigned comparison) */
482                                         memcpy(window + w, window + d, e);
483                                         w += e;
484                                         d += e;
485                                 } else  /* do it slow to avoid memcpy() overlap */
486 #endif                                                  /* !NOMEMCPY */
487                                         do {
488                                                 window[w++] = window[d++];
489                                         } while (--e);
490                                 if (w == WSIZE) {
491                                         outcnt = (w), flush_window();
492                                         w = 0;
493                                 }
494                         } while (n);
495                 }
496         }
497
498         /* restore the globals from the locals */
499         outcnt = w;                     /* restore global window pointer */
500         bb = b;                         /* restore global bit buffer */
501         bk = k;
502
503         /* done */
504         return 0;
505 }
506
507 static const unsigned short cplens[] = {        /* Copy lengths for literal codes 257..285 */
508         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
509         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0
510 };
511
512 /* note: see note #13 above about the 258 in this list. */
513 static const extra_bits_t cplext[] = {  /* Extra bits for literal codes 257..285 */
514         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
515         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99
516 };                                              /* 99==invalid */
517 static const unsigned short cpdist[] = {        /* Copy offsets for distance codes 0..29 */
518         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
519         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
520         8193, 12289, 16385, 24577
521 };
522 static const extra_bits_t cpdext[] = {  /* Extra bits for distance codes */
523         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
524         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
525         12, 12, 13, 13
526 };
527
528 /* Tables for deflate from PKZIP's appnote.txt. */
529 static const extra_bits_t border[] = {  /* Order of the bit length code lengths */
530         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
531 };
532
533 /*
534  * decompress an inflated block
535  * e: last block flag
536  *
537  * GLOBAL VARIABLES: bb, kk,
538  */
539 static int inflate_block(int *e)
540 {
541         unsigned t;                     /* block type */
542         register unsigned long b;       /* bit buffer */
543         register unsigned k;    /* number of bits in bit buffer */
544
545         /* make local bit buffer */
546         b = bb;
547         k = bk;
548
549         /* read in last block bit */
550         while (k < 1) {
551                 b |= ((unsigned long) fgetc(in_file)) << k;
552                 k += 8;
553         }
554         *e = (int) b & 1;
555         b >>= 1;
556         k -= 1;
557
558         /* read in block type */
559         while (k < 2) {
560                 b |= ((unsigned long) fgetc(in_file)) << k;
561                 k += 8;
562         }
563         t = (unsigned) b & 3;
564         b >>= 2;
565         k -= 2;
566
567         /* restore the global bit buffer */
568         bb = b;
569         bk = k;
570
571         /* inflate that block type */
572         switch (t) {
573         case 0:                 /* Inflate stored */
574         {
575                 unsigned long n;        /* number of bytes in block */
576                 unsigned long w;        /* current window position */
577                 register unsigned long b_stored;        /* bit buffer */
578                 register unsigned long k_stored;        /* number of bits in bit buffer */
579
580                 /* make local copies of globals */
581                 b_stored = bb;  /* initialize bit buffer */
582                 k_stored = bk;
583                 w = outcnt;             /* initialize window position */
584
585                 /* go to byte boundary */
586                 n = k_stored & 7;
587                 b_stored >>= n;
588                 k_stored -= n;
589
590                 /* get the length and its complement */
591                 while (k_stored < 16) {
592                         b_stored |= ((unsigned long) fgetc(in_file)) << k_stored;
593                         k_stored += 8;
594                 }
595                 n = ((unsigned) b_stored & 0xffff);
596                 b_stored >>= 16;
597                 k_stored -= 16;
598                 while (k_stored < 16) {
599                         b_stored |= ((unsigned long) fgetc(in_file)) << k_stored;
600                         k_stored += 8;
601                 }
602                 if (n != (unsigned) ((~b_stored) & 0xffff)) {
603                         return 1;       /* error in compressed data */
604                 }
605                 b_stored >>= 16;
606                 k_stored -= 16;
607
608                 /* read and output the compressed data */
609                 while (n--) {
610                         while (k_stored < 8) {
611                                 b_stored |= ((unsigned long) fgetc(in_file)) << k_stored;
612                                 k_stored += 8;
613                         }
614                         window[w++] = (unsigned char) b_stored;
615                         if (w == (unsigned long) WSIZE) {
616                                 outcnt = (w), flush_window();
617                                 w = 0;
618                         }
619                         b_stored >>= 8;
620                         k_stored -= 8;
621                 }
622
623                 /* restore the globals from the locals */
624                 outcnt = w;             /* restore global window pointer */
625                 bb = b_stored;  /* restore global bit buffer */
626                 bk = k_stored;
627                 return 0;
628         }
629         case 1:                 /* Inflate fixed 
630                                                    * decompress an inflated type 1 (fixed Huffman codes) block.  We should
631                                                    * either replace this with a custom decoder, or at least precompute the
632                                                    * Huffman tables.
633                                                  */
634         {
635                 int i;                  /* temporary variable */
636                 huft_t *tl;             /* literal/length code table */
637                 huft_t *td;             /* distance code table */
638                 int bl;                 /* lookup bits for tl */
639                 int bd;                 /* lookup bits for td */
640                 unsigned int l[288];    /* length list for huft_build */
641
642                 /* set up literal table */
643                 for (i = 0; i < 144; i++) {
644                         l[i] = 8;
645                 }
646                 for (; i < 256; i++) {
647                         l[i] = 9;
648                 }
649                 for (; i < 280; i++) {
650                         l[i] = 7;
651                 }
652                 for (; i < 288; i++) {  /* make a complete, but wrong code set */
653                         l[i] = 8;
654                 }
655                 bl = 7;
656                 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
657                         return i;
658                 }
659
660                 /* set up distance table */
661                 for (i = 0; i < 30; i++) {      /* make an incomplete code set */
662                         l[i] = 5;
663                 }
664                 bd = 5;
665                 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1) {
666                         huft_free(tl);
667                         return i;
668                 }
669
670                 /* decompress until an end-of-block code */
671                 if (inflate_codes(tl, td, bl, bd))
672                         return 1;
673
674                 /* free the decoding tables, return */
675                 huft_free(tl);
676                 huft_free(td);
677                 return 0;
678         }
679         case 2:                 /* Inflate dynamic */
680         {
681                 const int dbits = 6;    /* bits in base distance lookup table */
682                 const int lbits = 9;    /* bits in base literal/length lookup table */
683
684                 int i;                  /* temporary variables */
685                 unsigned j;
686                 unsigned l;             /* last length */
687                 unsigned m;             /* mask for bit lengths table */
688                 unsigned n;             /* number of lengths to get */
689                 huft_t *tl;             /* literal/length code table */
690                 huft_t *td;             /* distance code table */
691                 int bl;                 /* lookup bits for tl */
692                 int bd;                 /* lookup bits for td */
693                 unsigned nb;    /* number of bit length codes */
694                 unsigned nl;    /* number of literal/length codes */
695                 unsigned nd;    /* number of distance codes */
696
697                 unsigned ll[286 + 30];  /* literal/length and distance code lengths */
698                 register unsigned long b_dynamic;       /* bit buffer */
699                 register unsigned k_dynamic;    /* number of bits in bit buffer */
700
701                 /* make local bit buffer */
702                 b_dynamic = bb;
703                 k_dynamic = bk;
704
705                 /* read in table lengths */
706                 while (k_dynamic < 5) {
707                         b_dynamic |= ((unsigned long) fgetc(in_file)) << k_dynamic;
708                         k_dynamic += 8;
709                 }
710                 nl = 257 + ((unsigned) b_dynamic & 0x1f);       /* number of literal/length codes */
711                 b_dynamic >>= 5;
712                 k_dynamic -= 5;
713                 while (k_dynamic < 5) {
714                         b_dynamic |= ((unsigned long) fgetc(in_file)) << k_dynamic;
715                         k_dynamic += 8;
716                 }
717                 nd = 1 + ((unsigned) b_dynamic & 0x1f); /* number of distance codes */
718                 b_dynamic >>= 5;
719                 k_dynamic -= 5;
720                 while (k_dynamic < 4) {
721                         b_dynamic |= ((unsigned long) fgetc(in_file)) << k_dynamic;
722                         k_dynamic += 8;
723                 }
724                 nb = 4 + ((unsigned) b_dynamic & 0xf);  /* number of bit length codes */
725                 b_dynamic >>= 4;
726                 k_dynamic -= 4;
727                 if (nl > 286 || nd > 30) {
728                         return 1;       /* bad lengths */
729                 }
730
731                 /* read in bit-length-code lengths */
732                 for (j = 0; j < nb; j++) {
733                         while (k_dynamic < 3) {
734                                 b_dynamic |= ((unsigned long) fgetc(in_file)) << k_dynamic;
735                                 k_dynamic += 8;
736                         }
737                         ll[border[j]] = (unsigned) b_dynamic & 7;
738                         b_dynamic >>= 3;
739                         k_dynamic -= 3;
740                 }
741                 for (; j < 19; j++) {
742                         ll[border[j]] = 0;
743                 }
744
745                 /* build decoding table for trees--single level, 7 bit lookup */
746                 bl = 7;
747                 if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0) {
748                         if (i == 1) {
749                                 huft_free(tl);
750                         }
751                         return i;       /* incomplete code set */
752                 }
753
754                 /* read in literal and distance code lengths */
755                 n = nl + nd;
756                 m = mask_bits[bl];
757                 i = l = 0;
758                 while ((unsigned) i < n) {
759                         while (k_dynamic < (unsigned) bl) {
760                                 b_dynamic |= ((unsigned long) fgetc(in_file)) << k_dynamic;
761                                 k_dynamic += 8;
762                         }
763                         j = (td = tl + ((unsigned) b_dynamic & m))->b;
764                         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 */
770                                 while (k_dynamic < 2) {
771                                         b_dynamic |=
772                                                 ((unsigned long) fgetc(in_file)) << k_dynamic;
773                                         k_dynamic += 8;
774                                 }
775                                 j = 3 + ((unsigned) b_dynamic & 3);
776                                 b_dynamic >>= 2;
777                                 k_dynamic -= 2;
778                                 if ((unsigned) i + j > n) {
779                                         return 1;
780                                 }
781                                 while (j--) {
782                                         ll[i++] = l;
783                                 }
784                         } else if (j == 17) {   /* 3 to 10 zero length codes */
785                                 while (k_dynamic < 3) {
786                                         b_dynamic |=
787                                                 ((unsigned long) fgetc(in_file)) << k_dynamic;
788                                         k_dynamic += 8;
789                                 }
790                                 j = 3 + ((unsigned) b_dynamic & 7);
791                                 b_dynamic >>= 3;
792                                 k_dynamic -= 3;
793                                 if ((unsigned) i + j > n) {
794                                         return 1;
795                                 }
796                                 while (j--) {
797                                         ll[i++] = 0;
798                                 }
799                                 l = 0;
800                         } else {        /* j == 18: 11 to 138 zero length codes */
801                                 while (k_dynamic < 7) {
802                                         b_dynamic |=
803                                                 ((unsigned long) fgetc(in_file)) << k_dynamic;
804                                         k_dynamic += 8;
805                                 }
806                                 j = 11 + ((unsigned) b_dynamic & 0x7f);
807                                 b_dynamic >>= 7;
808                                 k_dynamic -= 7;
809                                 if ((unsigned) i + j > n) {
810                                         return 1;
811                                 }
812                                 while (j--) {
813                                         ll[i++] = 0;
814                                 }
815                                 l = 0;
816                         }
817                 }
818
819                 /* free decoding table for trees */
820                 huft_free(tl);
821
822                 /* restore the global bit buffer */
823                 bb = b_dynamic;
824                 bk = k_dynamic;
825
826                 /* build the decoding tables for literal/length and distance codes */
827                 bl = lbits;
828                 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0) {
829                         if (i == 1) {
830                                 error_msg("Incomplete literal tree");
831                                 huft_free(tl);
832                         }
833                         return i;       /* incomplete code set */
834                 }
835                 bd = dbits;
836                 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0) {
837                         if (i == 1) {
838                                 error_msg("incomplete distance tree");
839                                 huft_free(td);
840                         }
841                         huft_free(tl);
842                         return i;       /* incomplete code set */
843                 }
844
845                 /* decompress until an end-of-block code */
846                 if (inflate_codes(tl, td, bl, bd))
847                         return 1;
848
849                 /* free the decoding tables, return */
850                 huft_free(tl);
851                 huft_free(td);
852                 return 0;
853         }
854         default:
855                 /* bad block type */
856                 return 2;
857         }
858 }
859
860 /*
861  * decompress an inflated entry
862  *
863  * GLOBAL VARIABLES: outcnt, bk, bb, hufts, inptr
864  */
865 extern int inflate(FILE * in, FILE * out)
866 {
867         int e;                          /* last block flag */
868         int r;                          /* result code */
869         unsigned h = 0;         /* maximum struct huft's malloc'ed */
870
871         /* initialize window, bit buffer */
872         outcnt = 0;
873         bk = 0;
874         bb = 0;
875
876         in_file = in;
877         out_file = out;
878
879         /* Allocate all global buffers (for DYN_ALLOC option) */
880         window = xmalloc((size_t) (((2L * WSIZE) + 1L) * sizeof(unsigned char)));
881         bytes_out = 0L;
882
883         /* Create the crc table */
884         make_crc_table();
885
886         /* decompress until the last block */
887         do {
888                 hufts = 0;
889                 if ((r = inflate_block(&e)) != 0) {
890                         return r;
891                 }
892                 if (hufts > h) {
893                         h = hufts;
894                 }
895         } while (!e);
896
897         /* Undo too much lookahead. The next read will be byte aligned so we
898          * can discard unused bits in the last meaningful byte.
899          */
900         while (bk >= 8) {
901                 bk -= 8;
902                 ungetc((bb << bk), in_file);
903         }
904
905         /* flush out window */
906         flush_window();
907         free(window);
908         free(crc_table);
909
910         /* return success */
911         return 0;
912 }
913
914 /* ===========================================================================
915  * Unzip in to out.  This routine works on gzip files only.
916  *
917  * IN assertions: the buffer inbuf contains already the beginning of
918  *   the compressed data, from offsets inptr to insize-1 included.
919  *   The magic header has already been checked. The output buffer is cleared.
920  * in, out: input and output file descriptors
921  */
922 extern int unzip(FILE * l_in_file, FILE * l_out_file)
923 {
924         unsigned char buf[8];   /* extended local header */
925         unsigned char flags;    /* compression flags */
926         typedef void (*sig_type) (int);
927         unsigned short i;
928         unsigned char magic[2];
929
930         if (signal(SIGINT, SIG_IGN) != SIG_IGN) {
931                 (void) signal(SIGINT, (sig_type) abort_gzip);
932         }
933 #ifdef SIGHUP
934         if (signal(SIGHUP, SIG_IGN) != SIG_IGN) {
935                 (void) signal(SIGHUP, (sig_type) abort_gzip);
936         }
937 #endif
938
939         magic[0] = fgetc(l_in_file);
940         magic[1] = fgetc(l_in_file);
941
942 #ifdef CONFIG_FEATURE_UNCOMPRESS
943         /* Magic header for compress files, 1F 9d = \037\235 */
944         if ((magic[0] == 0x1F) && (magic[1] == 0x9d)) {
945                 return uncompress(l_in_file, l_out_file);
946         }
947 #endif
948
949         /* Magic header for gzip files, 1F 8B = \037\213 */
950         if ((magic[0] != 0x1F) || (magic[1] != 0x8b)) {
951                 error_msg("Invalid gzip magic");
952                 return EXIT_FAILURE;
953         }
954
955         /* Check the compression method */
956         if (fgetc(l_in_file) != 8) {
957                 error_msg("Unknown compression method");
958                 return (-1);
959         }
960
961         flags = (unsigned char) fgetc(l_in_file);
962
963         /* Ignore time stamp(4), extra flags(1), OS type(1) */
964         for (i = 0; i < 6; i++) {
965                 fgetc(l_in_file);
966         }
967
968         if (flags & 0x04) {
969                 /* bit 2 set: extra field present */
970                 const unsigned short extra =
971                         fgetc(l_in_file) + (fgetc(l_in_file) << 8);
972
973                 for (i = 0; i < extra; i++) {
974                         fgetc(l_in_file);
975                 }
976         }
977
978         /* Discard original name if any */
979         if (flags & 0x08) {
980                 /* bit 3 set: original file name present */
981                 while (fgetc(l_in_file) != 0);  /* null */
982         }
983
984         /* Discard file comment if any */
985         if (flags & 0x10) {
986                 /* bit 4 set: file comment present */
987                 while (fgetc(l_in_file) != 0);  /* null */
988         }
989
990         /* Decompress */
991         if (inflate(l_in_file, l_out_file) != 0) {
992                 error_msg("invalid compressed data--format violated");
993         }
994
995         /* Get the crc and original length
996          * crc32  (see algorithm.doc)
997          * uncompressed input size modulo 2^32
998          */
999         fread(buf, 1, 8, l_in_file);
1000
1001         /* Validate decompression - crc */
1002         if ((unsigned int) ((buf[0] | (buf[1] << 8)) |
1003                                                 ((buf[2] | (buf[3] << 8)) << 16)) !=
1004                 (crc ^ 0xffffffffL)) {
1005                 error_msg("invalid compressed data--crc error");
1006         }
1007         /* Validate decompression - size */
1008         if (((buf[4] | (buf[5] << 8)) | ((buf[6] | (buf[7] << 8)) << 16)) !=
1009                 (unsigned long) bytes_out) {
1010                 error_msg("invalid compressed data--length error");
1011         }
1012
1013         return 0;
1014 }
1015
1016 /*
1017  * This needs access to global variables window and crc_table, so its not in its own file.
1018  */
1019 extern void gz_close(int gunzip_pid)
1020 {
1021         if (kill(gunzip_pid, SIGTERM) == -1) {
1022                 error_msg_and_die
1023                         ("***  Couldnt kill old gunzip process *** aborting");
1024         }
1025
1026         if (waitpid(gunzip_pid, NULL, 0) == -1) {
1027                 printf("Couldnt wait ?");
1028         }
1029
1030         free(window);
1031         free(crc_table);
1032 }