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