include cleanup: Update gfp.h and slab.h includes to prepare for breaking implicit...
[linux-3.10.git] / lib / inflate.c
1 #define DEBG(x)
2 #define DEBG1(x)
3 /* inflate.c -- Not copyrighted 1992 by Mark Adler
4    version c10p1, 10 January 1993 */
5
6 /* 
7  * Adapted for booting Linux by Hannu Savolainen 1993
8  * based on gzip-1.0.3 
9  *
10  * Nicolas Pitre <nico@fluxnic.net>, 1999/04/14 :
11  *   Little mods for all variable to reside either into rodata or bss segments
12  *   by marking constant variables with 'const' and initializing all the others
13  *   at run-time only.  This allows for the kernel uncompressor to run
14  *   directly from Flash or ROM memory on embedded systems.
15  */
16
17 /*
18    Inflate deflated (PKZIP's method 8 compressed) data.  The compression
19    method searches for as much of the current string of bytes (up to a
20    length of 258) in the previous 32 K bytes.  If it doesn't find any
21    matches (of at least length 3), it codes the next byte.  Otherwise, it
22    codes the length of the matched string and its distance backwards from
23    the current position.  There is a single Huffman code that codes both
24    single bytes (called "literals") and match lengths.  A second Huffman
25    code codes the distance information, which follows a length code.  Each
26    length or distance code actually represents a base value and a number
27    of "extra" (sometimes zero) bits to get to add to the base value.  At
28    the end of each deflated block is a special end-of-block (EOB) literal/
29    length code.  The decoding process is basically: get a literal/length
30    code; if EOB then done; if a literal, emit the decoded byte; if a
31    length then get the distance and emit the referred-to bytes from the
32    sliding window of previously emitted data.
33
34    There are (currently) three kinds of inflate blocks: stored, fixed, and
35    dynamic.  The compressor deals with some chunk of data at a time, and
36    decides which method to use on a chunk-by-chunk basis.  A chunk might
37    typically be 32 K or 64 K.  If the chunk is incompressible, then the
38    "stored" method is used.  In this case, the bytes are simply stored as
39    is, eight bits per byte, with none of the above coding.  The bytes are
40    preceded by a count, since there is no longer an EOB code.
41
42    If the data is compressible, then either the fixed or dynamic methods
43    are used.  In the dynamic method, the compressed data is preceded by
44    an encoding of the literal/length and distance Huffman codes that are
45    to be used to decode this block.  The representation is itself Huffman
46    coded, and so is preceded by a description of that code.  These code
47    descriptions take up a little space, and so for small blocks, there is
48    a predefined set of codes, called the fixed codes.  The fixed method is
49    used if the block codes up smaller that way (usually for quite small
50    chunks), otherwise the dynamic method is used.  In the latter case, the
51    codes are customized to the probabilities in the current block, and so
52    can code it much better than the pre-determined fixed codes.
53  
54    The Huffman codes themselves are decoded using a multi-level table
55    lookup, in order to maximize the speed of decoding plus the speed of
56    building the decoding tables.  See the comments below that precede the
57    lbits and dbits tuning parameters.
58  */
59
60
61 /*
62    Notes beyond the 1.93a appnote.txt:
63
64    1. Distance pointers never point before the beginning of the output
65       stream.
66    2. Distance pointers can point back across blocks, up to 32k away.
67    3. There is an implied maximum of 7 bits for the bit length table and
68       15 bits for the actual data.
69    4. If only one code exists, then it is encoded using one bit.  (Zero
70       would be more efficient, but perhaps a little confusing.)  If two
71       codes exist, they are coded using one bit each (0 and 1).
72    5. There is no way of sending zero distance codes--a dummy must be
73       sent if there are none.  (History: a pre 2.0 version of PKZIP would
74       store blocks with no distance codes, but this was discovered to be
75       too harsh a criterion.)  Valid only for 1.93a.  2.04c does allow
76       zero distance codes, which is sent as one code of zero bits in
77       length.
78    6. There are up to 286 literal/length codes.  Code 256 represents the
79       end-of-block.  Note however that the static length tree defines
80       288 codes just to fill out the Huffman codes.  Codes 286 and 287
81       cannot be used though, since there is no length base or extra bits
82       defined for them.  Similarly, there are up to 30 distance codes.
83       However, static trees define 32 codes (all 5 bits) to fill out the
84       Huffman codes, but the last two had better not show up in the data.
85    7. Unzip can check dynamic Huffman blocks for complete code sets.
86       The exception is that a single code would not be complete (see #4).
87    8. The five bits following the block type is really the number of
88       literal codes sent minus 257.
89    9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
90       (1+6+6).  Therefore, to output three times the length, you output
91       three codes (1+1+1), whereas to output four times the same length,
92       you only need two codes (1+3).  Hmm.
93   10. In the tree reconstruction algorithm, Code = Code + Increment
94       only if BitLength(i) is not zero.  (Pretty obvious.)
95   11. Correction: 4 Bits: # of Bit Length codes - 4     (4 - 19)
96   12. Note: length code 284 can represent 227-258, but length code 285
97       really is 258.  The last length deserves its own, short code
98       since it gets used a lot in very redundant files.  The length
99       258 is special since 258 - 3 (the min match length) is 255.
100   13. The literal/length and distance code bit lengths are read as a
101       single stream of lengths.  It is possible (and advantageous) for
102       a repeat code (16, 17, or 18) to go across the boundary between
103       the two sets of lengths.
104  */
105 #include <linux/compiler.h>
106 #include <linux/slab.h>
107
108 #ifdef RCSID
109 static char rcsid[] = "#Id: inflate.c,v 0.14 1993/06/10 13:27:04 jloup Exp #";
110 #endif
111
112 #ifndef STATIC
113
114 #if defined(STDC_HEADERS) || defined(HAVE_STDLIB_H)
115 #  include <sys/types.h>
116 #  include <stdlib.h>
117 #endif
118
119 #include "gzip.h"
120 #define STATIC
121 #endif /* !STATIC */
122
123 #ifndef INIT
124 #define INIT
125 #endif
126         
127 #define slide window
128
129 /* Huffman code lookup table entry--this entry is four bytes for machines
130    that have 16-bit pointers (e.g. PC's in the small or medium model).
131    Valid extra bits are 0..13.  e == 15 is EOB (end of block), e == 16
132    means that v is a literal, 16 < e < 32 means that v is a pointer to
133    the next table, which codes e - 16 bits, and lastly e == 99 indicates
134    an unused code.  If a code with e == 99 is looked up, this implies an
135    error in the data. */
136 struct huft {
137   uch e;                /* number of extra bits or operation */
138   uch b;                /* number of bits in this code or subcode */
139   union {
140     ush n;              /* literal, length base, or distance base */
141     struct huft *t;     /* pointer to next level of table */
142   } v;
143 };
144
145
146 /* Function prototypes */
147 STATIC int INIT huft_build OF((unsigned *, unsigned, unsigned, 
148                 const ush *, const ush *, struct huft **, int *));
149 STATIC int INIT huft_free OF((struct huft *));
150 STATIC int INIT inflate_codes OF((struct huft *, struct huft *, int, int));
151 STATIC int INIT inflate_stored OF((void));
152 STATIC int INIT inflate_fixed OF((void));
153 STATIC int INIT inflate_dynamic OF((void));
154 STATIC int INIT inflate_block OF((int *));
155 STATIC int INIT inflate OF((void));
156
157
158 /* The inflate algorithm uses a sliding 32 K byte window on the uncompressed
159    stream to find repeated byte strings.  This is implemented here as a
160    circular buffer.  The index is updated simply by incrementing and then
161    ANDing with 0x7fff (32K-1). */
162 /* It is left to other modules to supply the 32 K area.  It is assumed
163    to be usable as if it were declared "uch slide[32768];" or as just
164    "uch *slide;" and then malloc'ed in the latter case.  The definition
165    must be in unzip.h, included above. */
166 /* unsigned wp;             current position in slide */
167 #define wp outcnt
168 #define flush_output(w) (wp=(w),flush_window())
169
170 /* Tables for deflate from PKZIP's appnote.txt. */
171 static const unsigned border[] = {    /* Order of the bit length code lengths */
172         16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
173 static const ush cplens[] = {         /* Copy lengths for literal codes 257..285 */
174         3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
175         35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
176         /* note: see note #13 above about the 258 in this list. */
177 static const ush cplext[] = {         /* Extra bits for literal codes 257..285 */
178         0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
179         3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
180 static const ush cpdist[] = {         /* Copy offsets for distance codes 0..29 */
181         1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
182         257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
183         8193, 12289, 16385, 24577};
184 static const ush cpdext[] = {         /* Extra bits for distance codes */
185         0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
186         7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
187         12, 12, 13, 13};
188
189
190
191 /* Macros for inflate() bit peeking and grabbing.
192    The usage is:
193    
194         NEEDBITS(j)
195         x = b & mask_bits[j];
196         DUMPBITS(j)
197
198    where NEEDBITS makes sure that b has at least j bits in it, and
199    DUMPBITS removes the bits from b.  The macros use the variable k
200    for the number of bits in b.  Normally, b and k are register
201    variables for speed, and are initialized at the beginning of a
202    routine that uses these macros from a global bit buffer and count.
203
204    If we assume that EOB will be the longest code, then we will never
205    ask for bits with NEEDBITS that are beyond the end of the stream.
206    So, NEEDBITS should not read any more bytes than are needed to
207    meet the request.  Then no bytes need to be "returned" to the buffer
208    at the end of the last block.
209
210    However, this assumption is not true for fixed blocks--the EOB code
211    is 7 bits, but the other literal/length codes can be 8 or 9 bits.
212    (The EOB code is shorter than other codes because fixed blocks are
213    generally short.  So, while a block always has an EOB, many other
214    literal/length codes have a significantly lower probability of
215    showing up at all.)  However, by making the first table have a
216    lookup of seven bits, the EOB code will be found in that first
217    lookup, and so will not require that too many bits be pulled from
218    the stream.
219  */
220
221 STATIC ulg bb;                         /* bit buffer */
222 STATIC unsigned bk;                    /* bits in bit buffer */
223
224 STATIC const ush mask_bits[] = {
225     0x0000,
226     0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
227     0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
228 };
229
230 #define NEXTBYTE()  ({ int v = get_byte(); if (v < 0) goto underrun; (uch)v; })
231 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
232 #define DUMPBITS(n) {b>>=(n);k-=(n);}
233
234 #ifndef NO_INFLATE_MALLOC
235 /* A trivial malloc implementation, adapted from
236  *  malloc by Hannu Savolainen 1993 and Matthias Urlichs 1994
237  */
238
239 static unsigned long malloc_ptr;
240 static int malloc_count;
241
242 static void *malloc(int size)
243 {
244        void *p;
245
246        if (size < 0)
247                 error("Malloc error");
248        if (!malloc_ptr)
249                 malloc_ptr = free_mem_ptr;
250
251        malloc_ptr = (malloc_ptr + 3) & ~3;     /* Align */
252
253        p = (void *)malloc_ptr;
254        malloc_ptr += size;
255
256        if (free_mem_end_ptr && malloc_ptr >= free_mem_end_ptr)
257                 error("Out of memory");
258
259        malloc_count++;
260        return p;
261 }
262
263 static void free(void *where)
264 {
265        malloc_count--;
266        if (!malloc_count)
267                 malloc_ptr = free_mem_ptr;
268 }
269 #else
270 #define malloc(a) kmalloc(a, GFP_KERNEL)
271 #define free(a) kfree(a)
272 #endif
273
274 /*
275    Huffman code decoding is performed using a multi-level table lookup.
276    The fastest way to decode is to simply build a lookup table whose
277    size is determined by the longest code.  However, the time it takes
278    to build this table can also be a factor if the data being decoded
279    is not very long.  The most common codes are necessarily the
280    shortest codes, so those codes dominate the decoding time, and hence
281    the speed.  The idea is you can have a shorter table that decodes the
282    shorter, more probable codes, and then point to subsidiary tables for
283    the longer codes.  The time it costs to decode the longer codes is
284    then traded against the time it takes to make longer tables.
285
286    This results of this trade are in the variables lbits and dbits
287    below.  lbits is the number of bits the first level table for literal/
288    length codes can decode in one step, and dbits is the same thing for
289    the distance codes.  Subsequent tables are also less than or equal to
290    those sizes.  These values may be adjusted either when all of the
291    codes are shorter than that, in which case the longest code length in
292    bits is used, or when the shortest code is *longer* than the requested
293    table size, in which case the length of the shortest code in bits is
294    used.
295
296    There are two different values for the two tables, since they code a
297    different number of possibilities each.  The literal/length table
298    codes 286 possible values, or in a flat code, a little over eight
299    bits.  The distance table codes 30 possible values, or a little less
300    than five bits, flat.  The optimum values for speed end up being
301    about one bit more than those, so lbits is 8+1 and dbits is 5+1.
302    The optimum values may differ though from machine to machine, and
303    possibly even between compilers.  Your mileage may vary.
304  */
305
306
307 STATIC const int lbits = 9;          /* bits in base literal/length lookup table */
308 STATIC const int dbits = 6;          /* bits in base distance lookup table */
309
310
311 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
312 #define BMAX 16         /* maximum bit length of any code (16 for explode) */
313 #define N_MAX 288       /* maximum number of codes in any set */
314
315
316 STATIC unsigned hufts;         /* track memory usage */
317
318
319 STATIC int INIT huft_build(
320         unsigned *b,            /* code lengths in bits (all assumed <= BMAX) */
321         unsigned n,             /* number of codes (assumed <= N_MAX) */
322         unsigned s,             /* number of simple-valued codes (0..s-1) */
323         const ush *d,           /* list of base values for non-simple codes */
324         const ush *e,           /* list of extra bits for non-simple codes */
325         struct huft **t,        /* result: starting table */
326         int *m                  /* maximum lookup bits, returns actual */
327         )
328 /* Given a list of code lengths and a maximum table size, make a set of
329    tables to decode that set of codes.  Return zero on success, one if
330    the given code set is incomplete (the tables are still built in this
331    case), two if the input is invalid (all zero length codes or an
332    oversubscribed set of lengths), and three if not enough memory. */
333 {
334   unsigned a;                   /* counter for codes of length k */
335   unsigned f;                   /* i repeats in table every f entries */
336   int g;                        /* maximum code length */
337   int h;                        /* table level */
338   register unsigned i;          /* counter, current code */
339   register unsigned j;          /* counter */
340   register int k;               /* number of bits in current code */
341   int l;                        /* bits per table (returned in m) */
342   register unsigned *p;         /* pointer into c[], b[], or v[] */
343   register struct huft *q;      /* points to current table */
344   struct huft r;                /* table entry for structure assignment */
345   register int w;               /* bits before this table == (l * h) */
346   unsigned *xp;                 /* pointer into x */
347   int y;                        /* number of dummy codes added */
348   unsigned z;                   /* number of entries in current table */
349   struct {
350     unsigned c[BMAX+1];           /* bit length count table */
351     struct huft *u[BMAX];         /* table stack */
352     unsigned v[N_MAX];            /* values in order of bit length */
353     unsigned x[BMAX+1];           /* bit offsets, then code stack */
354   } *stk;
355   unsigned *c, *v, *x;
356   struct huft **u;
357   int ret;
358
359 DEBG("huft1 ");
360
361   stk = malloc(sizeof(*stk));
362   if (stk == NULL)
363     return 3;                   /* out of memory */
364
365   c = stk->c;
366   v = stk->v;
367   x = stk->x;
368   u = stk->u;
369
370   /* Generate counts for each bit length */
371   memzero(stk->c, sizeof(stk->c));
372   p = b;  i = n;
373   do {
374     Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"), 
375             n-i, *p));
376     c[*p]++;                    /* assume all entries <= BMAX */
377     p++;                      /* Can't combine with above line (Solaris bug) */
378   } while (--i);
379   if (c[0] == n)                /* null input--all zero length codes */
380   {
381     *t = (struct huft *)NULL;
382     *m = 0;
383     ret = 2;
384     goto out;
385   }
386
387 DEBG("huft2 ");
388
389   /* Find minimum and maximum length, bound *m by those */
390   l = *m;
391   for (j = 1; j <= BMAX; j++)
392     if (c[j])
393       break;
394   k = j;                        /* minimum code length */
395   if ((unsigned)l < j)
396     l = j;
397   for (i = BMAX; i; i--)
398     if (c[i])
399       break;
400   g = i;                        /* maximum code length */
401   if ((unsigned)l > i)
402     l = i;
403   *m = l;
404
405 DEBG("huft3 ");
406
407   /* Adjust last length count to fill out codes, if needed */
408   for (y = 1 << j; j < i; j++, y <<= 1)
409     if ((y -= c[j]) < 0) {
410       ret = 2;                 /* bad input: more codes than bits */
411       goto out;
412     }
413   if ((y -= c[i]) < 0) {
414     ret = 2;
415     goto out;
416   }
417   c[i] += y;
418
419 DEBG("huft4 ");
420
421   /* Generate starting offsets into the value table for each length */
422   x[1] = j = 0;
423   p = c + 1;  xp = x + 2;
424   while (--i) {                 /* note that i == g from above */
425     *xp++ = (j += *p++);
426   }
427
428 DEBG("huft5 ");
429
430   /* Make a table of values in order of bit lengths */
431   p = b;  i = 0;
432   do {
433     if ((j = *p++) != 0)
434       v[x[j]++] = i;
435   } while (++i < n);
436   n = x[g];                   /* set n to length of v */
437
438 DEBG("h6 ");
439
440   /* Generate the Huffman codes and for each, make the table entries */
441   x[0] = i = 0;                 /* first Huffman code is zero */
442   p = v;                        /* grab values in bit order */
443   h = -1;                       /* no tables yet--level -1 */
444   w = -l;                       /* bits decoded == (l * h) */
445   u[0] = (struct huft *)NULL;   /* just to keep compilers happy */
446   q = (struct huft *)NULL;      /* ditto */
447   z = 0;                        /* ditto */
448 DEBG("h6a ");
449
450   /* go through the bit lengths (k already is bits in shortest code) */
451   for (; k <= g; k++)
452   {
453 DEBG("h6b ");
454     a = c[k];
455     while (a--)
456     {
457 DEBG("h6b1 ");
458       /* here i is the Huffman code of length k bits for value *p */
459       /* make tables up to required level */
460       while (k > w + l)
461       {
462 DEBG1("1 ");
463         h++;
464         w += l;                 /* previous table always l bits */
465
466         /* compute minimum size table less than or equal to l bits */
467         z = (z = g - w) > (unsigned)l ? l : z;  /* upper limit on table size */
468         if ((f = 1 << (j = k - w)) > a + 1)     /* try a k-w bit table */
469         {                       /* too few codes for k-w bit table */
470 DEBG1("2 ");
471           f -= a + 1;           /* deduct codes from patterns left */
472           xp = c + k;
473           if (j < z)
474             while (++j < z)       /* try smaller tables up to z bits */
475             {
476               if ((f <<= 1) <= *++xp)
477                 break;            /* enough codes to use up j bits */
478               f -= *xp;           /* else deduct codes from patterns */
479             }
480         }
481 DEBG1("3 ");
482         z = 1 << j;             /* table entries for j-bit table */
483
484         /* allocate and link in new table */
485         if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
486             (struct huft *)NULL)
487         {
488           if (h)
489             huft_free(u[0]);
490           ret = 3;             /* not enough memory */
491           goto out;
492         }
493 DEBG1("4 ");
494         hufts += z + 1;         /* track memory usage */
495         *t = q + 1;             /* link to list for huft_free() */
496         *(t = &(q->v.t)) = (struct huft *)NULL;
497         u[h] = ++q;             /* table starts after link */
498
499 DEBG1("5 ");
500         /* connect to last table, if there is one */
501         if (h)
502         {
503           x[h] = i;             /* save pattern for backing up */
504           r.b = (uch)l;         /* bits to dump before this table */
505           r.e = (uch)(16 + j);  /* bits in this table */
506           r.v.t = q;            /* pointer to this table */
507           j = i >> (w - l);     /* (get around Turbo C bug) */
508           u[h-1][j] = r;        /* connect to last table */
509         }
510 DEBG1("6 ");
511       }
512 DEBG("h6c ");
513
514       /* set up table entry in r */
515       r.b = (uch)(k - w);
516       if (p >= v + n)
517         r.e = 99;               /* out of values--invalid code */
518       else if (*p < s)
519       {
520         r.e = (uch)(*p < 256 ? 16 : 15);    /* 256 is end-of-block code */
521         r.v.n = (ush)(*p);             /* simple code is just the value */
522         p++;                           /* one compiler does not like *p++ */
523       }
524       else
525       {
526         r.e = (uch)e[*p - s];   /* non-simple--look up in lists */
527         r.v.n = d[*p++ - s];
528       }
529 DEBG("h6d ");
530
531       /* fill code-like entries with r */
532       f = 1 << (k - w);
533       for (j = i >> w; j < z; j += f)
534         q[j] = r;
535
536       /* backwards increment the k-bit code i */
537       for (j = 1 << (k - 1); i & j; j >>= 1)
538         i ^= j;
539       i ^= j;
540
541       /* backup over finished tables */
542       while ((i & ((1 << w) - 1)) != x[h])
543       {
544         h--;                    /* don't need to update q */
545         w -= l;
546       }
547 DEBG("h6e ");
548     }
549 DEBG("h6f ");
550   }
551
552 DEBG("huft7 ");
553
554   /* Return true (1) if we were given an incomplete table */
555   ret = y != 0 && g != 1;
556
557   out:
558   free(stk);
559   return ret;
560 }
561
562
563
564 STATIC int INIT huft_free(
565         struct huft *t         /* table to free */
566         )
567 /* Free the malloc'ed tables built by huft_build(), which makes a linked
568    list of the tables it made, with the links in a dummy first entry of
569    each table. */
570 {
571   register struct huft *p, *q;
572
573
574   /* Go through linked list, freeing from the malloced (t[-1]) address. */
575   p = t;
576   while (p != (struct huft *)NULL)
577   {
578     q = (--p)->v.t;
579     free((char*)p);
580     p = q;
581   } 
582   return 0;
583 }
584
585
586 STATIC int INIT inflate_codes(
587         struct huft *tl,    /* literal/length decoder tables */
588         struct huft *td,    /* distance decoder tables */
589         int bl,             /* number of bits decoded by tl[] */
590         int bd              /* number of bits decoded by td[] */
591         )
592 /* inflate (decompress) the codes in a deflated (compressed) block.
593    Return an error code or zero if it all goes ok. */
594 {
595   register unsigned e;  /* table entry flag/number of extra bits */
596   unsigned n, d;        /* length and index for copy */
597   unsigned w;           /* current window position */
598   struct huft *t;       /* pointer to table entry */
599   unsigned ml, md;      /* masks for bl and bd bits */
600   register ulg b;       /* bit buffer */
601   register unsigned k;  /* number of bits in bit buffer */
602
603
604   /* make local copies of globals */
605   b = bb;                       /* initialize bit buffer */
606   k = bk;
607   w = wp;                       /* initialize window position */
608
609   /* inflate the coded data */
610   ml = mask_bits[bl];           /* precompute masks for speed */
611   md = mask_bits[bd];
612   for (;;)                      /* do until end of block */
613   {
614     NEEDBITS((unsigned)bl)
615     if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
616       do {
617         if (e == 99)
618           return 1;
619         DUMPBITS(t->b)
620         e -= 16;
621         NEEDBITS(e)
622       } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
623     DUMPBITS(t->b)
624     if (e == 16)                /* then it's a literal */
625     {
626       slide[w++] = (uch)t->v.n;
627       Tracevv((stderr, "%c", slide[w-1]));
628       if (w == WSIZE)
629       {
630         flush_output(w);
631         w = 0;
632       }
633     }
634     else                        /* it's an EOB or a length */
635     {
636       /* exit if end of block */
637       if (e == 15)
638         break;
639
640       /* get length of block to copy */
641       NEEDBITS(e)
642       n = t->v.n + ((unsigned)b & mask_bits[e]);
643       DUMPBITS(e);
644
645       /* decode distance of block to copy */
646       NEEDBITS((unsigned)bd)
647       if ((e = (t = td + ((unsigned)b & md))->e) > 16)
648         do {
649           if (e == 99)
650             return 1;
651           DUMPBITS(t->b)
652           e -= 16;
653           NEEDBITS(e)
654         } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
655       DUMPBITS(t->b)
656       NEEDBITS(e)
657       d = w - t->v.n - ((unsigned)b & mask_bits[e]);
658       DUMPBITS(e)
659       Tracevv((stderr,"\\[%d,%d]", w-d, n));
660
661       /* do the copy */
662       do {
663         n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
664 #if !defined(NOMEMCPY) && !defined(DEBUG)
665         if (w - d >= e)         /* (this test assumes unsigned comparison) */
666         {
667           memcpy(slide + w, slide + d, e);
668           w += e;
669           d += e;
670         }
671         else                      /* do it slow to avoid memcpy() overlap */
672 #endif /* !NOMEMCPY */
673           do {
674             slide[w++] = slide[d++];
675             Tracevv((stderr, "%c", slide[w-1]));
676           } while (--e);
677         if (w == WSIZE)
678         {
679           flush_output(w);
680           w = 0;
681         }
682       } while (n);
683     }
684   }
685
686
687   /* restore the globals from the locals */
688   wp = w;                       /* restore global window pointer */
689   bb = b;                       /* restore global bit buffer */
690   bk = k;
691
692   /* done */
693   return 0;
694
695  underrun:
696   return 4;                     /* Input underrun */
697 }
698
699
700
701 STATIC int INIT inflate_stored(void)
702 /* "decompress" an inflated type 0 (stored) block. */
703 {
704   unsigned n;           /* number of bytes in block */
705   unsigned w;           /* current window position */
706   register ulg b;       /* bit buffer */
707   register unsigned k;  /* number of bits in bit buffer */
708
709 DEBG("<stor");
710
711   /* make local copies of globals */
712   b = bb;                       /* initialize bit buffer */
713   k = bk;
714   w = wp;                       /* initialize window position */
715
716
717   /* go to byte boundary */
718   n = k & 7;
719   DUMPBITS(n);
720
721
722   /* get the length and its complement */
723   NEEDBITS(16)
724   n = ((unsigned)b & 0xffff);
725   DUMPBITS(16)
726   NEEDBITS(16)
727   if (n != (unsigned)((~b) & 0xffff))
728     return 1;                   /* error in compressed data */
729   DUMPBITS(16)
730
731
732   /* read and output the compressed data */
733   while (n--)
734   {
735     NEEDBITS(8)
736     slide[w++] = (uch)b;
737     if (w == WSIZE)
738     {
739       flush_output(w);
740       w = 0;
741     }
742     DUMPBITS(8)
743   }
744
745
746   /* restore the globals from the locals */
747   wp = w;                       /* restore global window pointer */
748   bb = b;                       /* restore global bit buffer */
749   bk = k;
750
751   DEBG(">");
752   return 0;
753
754  underrun:
755   return 4;                     /* Input underrun */
756 }
757
758
759 /*
760  * We use `noinline' here to prevent gcc-3.5 from using too much stack space
761  */
762 STATIC int noinline INIT inflate_fixed(void)
763 /* decompress an inflated type 1 (fixed Huffman codes) block.  We should
764    either replace this with a custom decoder, or at least precompute the
765    Huffman tables. */
766 {
767   int i;                /* temporary variable */
768   struct huft *tl;      /* literal/length code table */
769   struct huft *td;      /* distance code table */
770   int bl;               /* lookup bits for tl */
771   int bd;               /* lookup bits for td */
772   unsigned *l;          /* length list for huft_build */
773
774 DEBG("<fix");
775
776   l = malloc(sizeof(*l) * 288);
777   if (l == NULL)
778     return 3;                   /* out of memory */
779
780   /* set up literal table */
781   for (i = 0; i < 144; i++)
782     l[i] = 8;
783   for (; i < 256; i++)
784     l[i] = 9;
785   for (; i < 280; i++)
786     l[i] = 7;
787   for (; i < 288; i++)          /* make a complete, but wrong code set */
788     l[i] = 8;
789   bl = 7;
790   if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0) {
791     free(l);
792     return i;
793   }
794
795   /* set up distance table */
796   for (i = 0; i < 30; i++)      /* make an incomplete code set */
797     l[i] = 5;
798   bd = 5;
799   if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
800   {
801     huft_free(tl);
802     free(l);
803
804     DEBG(">");
805     return i;
806   }
807
808
809   /* decompress until an end-of-block code */
810   if (inflate_codes(tl, td, bl, bd)) {
811     free(l);
812     return 1;
813   }
814
815   /* free the decoding tables, return */
816   free(l);
817   huft_free(tl);
818   huft_free(td);
819   return 0;
820 }
821
822
823 /*
824  * We use `noinline' here to prevent gcc-3.5 from using too much stack space
825  */
826 STATIC int noinline INIT inflate_dynamic(void)
827 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
828 {
829   int i;                /* temporary variables */
830   unsigned j;
831   unsigned l;           /* last length */
832   unsigned m;           /* mask for bit lengths table */
833   unsigned n;           /* number of lengths to get */
834   struct huft *tl;      /* literal/length code table */
835   struct huft *td;      /* distance code table */
836   int bl;               /* lookup bits for tl */
837   int bd;               /* lookup bits for td */
838   unsigned nb;          /* number of bit length codes */
839   unsigned nl;          /* number of literal/length codes */
840   unsigned nd;          /* number of distance codes */
841   unsigned *ll;         /* literal/length and distance code lengths */
842   register ulg b;       /* bit buffer */
843   register unsigned k;  /* number of bits in bit buffer */
844   int ret;
845
846 DEBG("<dyn");
847
848 #ifdef PKZIP_BUG_WORKAROUND
849   ll = malloc(sizeof(*ll) * (288+32));  /* literal/length and distance code lengths */
850 #else
851   ll = malloc(sizeof(*ll) * (286+30));  /* literal/length and distance code lengths */
852 #endif
853
854   if (ll == NULL)
855     return 1;
856
857   /* make local bit buffer */
858   b = bb;
859   k = bk;
860
861
862   /* read in table lengths */
863   NEEDBITS(5)
864   nl = 257 + ((unsigned)b & 0x1f);      /* number of literal/length codes */
865   DUMPBITS(5)
866   NEEDBITS(5)
867   nd = 1 + ((unsigned)b & 0x1f);        /* number of distance codes */
868   DUMPBITS(5)
869   NEEDBITS(4)
870   nb = 4 + ((unsigned)b & 0xf);         /* number of bit length codes */
871   DUMPBITS(4)
872 #ifdef PKZIP_BUG_WORKAROUND
873   if (nl > 288 || nd > 32)
874 #else
875   if (nl > 286 || nd > 30)
876 #endif
877   {
878     ret = 1;             /* bad lengths */
879     goto out;
880   }
881
882 DEBG("dyn1 ");
883
884   /* read in bit-length-code lengths */
885   for (j = 0; j < nb; j++)
886   {
887     NEEDBITS(3)
888     ll[border[j]] = (unsigned)b & 7;
889     DUMPBITS(3)
890   }
891   for (; j < 19; j++)
892     ll[border[j]] = 0;
893
894 DEBG("dyn2 ");
895
896   /* build decoding table for trees--single level, 7 bit lookup */
897   bl = 7;
898   if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
899   {
900     if (i == 1)
901       huft_free(tl);
902     ret = i;                   /* incomplete code set */
903     goto out;
904   }
905
906 DEBG("dyn3 ");
907
908   /* read in literal and distance code lengths */
909   n = nl + nd;
910   m = mask_bits[bl];
911   i = l = 0;
912   while ((unsigned)i < n)
913   {
914     NEEDBITS((unsigned)bl)
915     j = (td = tl + ((unsigned)b & m))->b;
916     DUMPBITS(j)
917     j = td->v.n;
918     if (j < 16)                 /* length of code in bits (0..15) */
919       ll[i++] = l = j;          /* save last length in l */
920     else if (j == 16)           /* repeat last length 3 to 6 times */
921     {
922       NEEDBITS(2)
923       j = 3 + ((unsigned)b & 3);
924       DUMPBITS(2)
925       if ((unsigned)i + j > n) {
926         ret = 1;
927         goto out;
928       }
929       while (j--)
930         ll[i++] = l;
931     }
932     else if (j == 17)           /* 3 to 10 zero length codes */
933     {
934       NEEDBITS(3)
935       j = 3 + ((unsigned)b & 7);
936       DUMPBITS(3)
937       if ((unsigned)i + j > n) {
938         ret = 1;
939         goto out;
940       }
941       while (j--)
942         ll[i++] = 0;
943       l = 0;
944     }
945     else                        /* j == 18: 11 to 138 zero length codes */
946     {
947       NEEDBITS(7)
948       j = 11 + ((unsigned)b & 0x7f);
949       DUMPBITS(7)
950       if ((unsigned)i + j > n) {
951         ret = 1;
952         goto out;
953       }
954       while (j--)
955         ll[i++] = 0;
956       l = 0;
957     }
958   }
959
960 DEBG("dyn4 ");
961
962   /* free decoding table for trees */
963   huft_free(tl);
964
965 DEBG("dyn5 ");
966
967   /* restore the global bit buffer */
968   bb = b;
969   bk = k;
970
971 DEBG("dyn5a ");
972
973   /* build the decoding tables for literal/length and distance codes */
974   bl = lbits;
975   if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
976   {
977 DEBG("dyn5b ");
978     if (i == 1) {
979       error("incomplete literal tree");
980       huft_free(tl);
981     }
982     ret = i;                   /* incomplete code set */
983     goto out;
984   }
985 DEBG("dyn5c ");
986   bd = dbits;
987   if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
988   {
989 DEBG("dyn5d ");
990     if (i == 1) {
991       error("incomplete distance tree");
992 #ifdef PKZIP_BUG_WORKAROUND
993       i = 0;
994     }
995 #else
996       huft_free(td);
997     }
998     huft_free(tl);
999     ret = i;                   /* incomplete code set */
1000     goto out;
1001 #endif
1002   }
1003
1004 DEBG("dyn6 ");
1005
1006   /* decompress until an end-of-block code */
1007   if (inflate_codes(tl, td, bl, bd)) {
1008     ret = 1;
1009     goto out;
1010   }
1011
1012 DEBG("dyn7 ");
1013
1014   /* free the decoding tables, return */
1015   huft_free(tl);
1016   huft_free(td);
1017
1018   DEBG(">");
1019   ret = 0;
1020 out:
1021   free(ll);
1022   return ret;
1023
1024 underrun:
1025   ret = 4;                      /* Input underrun */
1026   goto out;
1027 }
1028
1029
1030
1031 STATIC int INIT inflate_block(
1032         int *e                  /* last block flag */
1033         )
1034 /* decompress an inflated block */
1035 {
1036   unsigned t;           /* block type */
1037   register ulg b;       /* bit buffer */
1038   register unsigned k;  /* number of bits in bit buffer */
1039
1040   DEBG("<blk");
1041
1042   /* make local bit buffer */
1043   b = bb;
1044   k = bk;
1045
1046
1047   /* read in last block bit */
1048   NEEDBITS(1)
1049   *e = (int)b & 1;
1050   DUMPBITS(1)
1051
1052
1053   /* read in block type */
1054   NEEDBITS(2)
1055   t = (unsigned)b & 3;
1056   DUMPBITS(2)
1057
1058
1059   /* restore the global bit buffer */
1060   bb = b;
1061   bk = k;
1062
1063   /* inflate that block type */
1064   if (t == 2)
1065     return inflate_dynamic();
1066   if (t == 0)
1067     return inflate_stored();
1068   if (t == 1)
1069     return inflate_fixed();
1070
1071   DEBG(">");
1072
1073   /* bad block type */
1074   return 2;
1075
1076  underrun:
1077   return 4;                     /* Input underrun */
1078 }
1079
1080
1081
1082 STATIC int INIT inflate(void)
1083 /* decompress an inflated entry */
1084 {
1085   int e;                /* last block flag */
1086   int r;                /* result code */
1087   unsigned h;           /* maximum struct huft's malloc'ed */
1088
1089   /* initialize window, bit buffer */
1090   wp = 0;
1091   bk = 0;
1092   bb = 0;
1093
1094
1095   /* decompress until the last block */
1096   h = 0;
1097   do {
1098     hufts = 0;
1099 #ifdef ARCH_HAS_DECOMP_WDOG
1100     arch_decomp_wdog();
1101 #endif
1102     r = inflate_block(&e);
1103     if (r)
1104             return r;
1105     if (hufts > h)
1106       h = hufts;
1107   } while (!e);
1108
1109   /* Undo too much lookahead. The next read will be byte aligned so we
1110    * can discard unused bits in the last meaningful byte.
1111    */
1112   while (bk >= 8) {
1113     bk -= 8;
1114     inptr--;
1115   }
1116
1117   /* flush out slide */
1118   flush_output(wp);
1119
1120
1121   /* return success */
1122 #ifdef DEBUG
1123   fprintf(stderr, "<%u> ", h);
1124 #endif /* DEBUG */
1125   return 0;
1126 }
1127
1128 /**********************************************************************
1129  *
1130  * The following are support routines for inflate.c
1131  *
1132  **********************************************************************/
1133
1134 static ulg crc_32_tab[256];
1135 static ulg crc;         /* initialized in makecrc() so it'll reside in bss */
1136 #define CRC_VALUE (crc ^ 0xffffffffUL)
1137
1138 /*
1139  * Code to compute the CRC-32 table. Borrowed from 
1140  * gzip-1.0.3/makecrc.c.
1141  */
1142
1143 static void INIT
1144 makecrc(void)
1145 {
1146 /* Not copyrighted 1990 Mark Adler      */
1147
1148   unsigned long c;      /* crc shift register */
1149   unsigned long e;      /* polynomial exclusive-or pattern */
1150   int i;                /* counter for all possible eight bit values */
1151   int k;                /* byte being shifted into crc apparatus */
1152
1153   /* terms of polynomial defining this crc (except x^32): */
1154   static const int p[] = {0,1,2,4,5,7,8,10,11,12,16,22,23,26};
1155
1156   /* Make exclusive-or pattern from polynomial */
1157   e = 0;
1158   for (i = 0; i < sizeof(p)/sizeof(int); i++)
1159     e |= 1L << (31 - p[i]);
1160
1161   crc_32_tab[0] = 0;
1162
1163   for (i = 1; i < 256; i++)
1164   {
1165     c = 0;
1166     for (k = i | 256; k != 1; k >>= 1)
1167     {
1168       c = c & 1 ? (c >> 1) ^ e : c >> 1;
1169       if (k & 1)
1170         c ^= e;
1171     }
1172     crc_32_tab[i] = c;
1173   }
1174
1175   /* this is initialized here so this code could reside in ROM */
1176   crc = (ulg)0xffffffffUL; /* shift register contents */
1177 }
1178
1179 /* gzip flag byte */
1180 #define ASCII_FLAG   0x01 /* bit 0 set: file probably ASCII text */
1181 #define CONTINUATION 0x02 /* bit 1 set: continuation of multi-part gzip file */
1182 #define EXTRA_FIELD  0x04 /* bit 2 set: extra field present */
1183 #define ORIG_NAME    0x08 /* bit 3 set: original file name present */
1184 #define COMMENT      0x10 /* bit 4 set: file comment present */
1185 #define ENCRYPTED    0x20 /* bit 5 set: file is encrypted */
1186 #define RESERVED     0xC0 /* bit 6,7:   reserved */
1187
1188 /*
1189  * Do the uncompression!
1190  */
1191 static int INIT gunzip(void)
1192 {
1193     uch flags;
1194     unsigned char magic[2]; /* magic header */
1195     char method;
1196     ulg orig_crc = 0;       /* original crc */
1197     ulg orig_len = 0;       /* original uncompressed length */
1198     int res;
1199
1200     magic[0] = NEXTBYTE();
1201     magic[1] = NEXTBYTE();
1202     method   = NEXTBYTE();
1203
1204     if (magic[0] != 037 ||
1205         ((magic[1] != 0213) && (magic[1] != 0236))) {
1206             error("bad gzip magic numbers");
1207             return -1;
1208     }
1209
1210     /* We only support method #8, DEFLATED */
1211     if (method != 8)  {
1212             error("internal error, invalid method");
1213             return -1;
1214     }
1215
1216     flags  = (uch)get_byte();
1217     if ((flags & ENCRYPTED) != 0) {
1218             error("Input is encrypted");
1219             return -1;
1220     }
1221     if ((flags & CONTINUATION) != 0) {
1222             error("Multi part input");
1223             return -1;
1224     }
1225     if ((flags & RESERVED) != 0) {
1226             error("Input has invalid flags");
1227             return -1;
1228     }
1229     NEXTBYTE(); /* Get timestamp */
1230     NEXTBYTE();
1231     NEXTBYTE();
1232     NEXTBYTE();
1233
1234     (void)NEXTBYTE();  /* Ignore extra flags for the moment */
1235     (void)NEXTBYTE();  /* Ignore OS type for the moment */
1236
1237     if ((flags & EXTRA_FIELD) != 0) {
1238             unsigned len = (unsigned)NEXTBYTE();
1239             len |= ((unsigned)NEXTBYTE())<<8;
1240             while (len--) (void)NEXTBYTE();
1241     }
1242
1243     /* Get original file name if it was truncated */
1244     if ((flags & ORIG_NAME) != 0) {
1245             /* Discard the old name */
1246             while (NEXTBYTE() != 0) /* null */ ;
1247     } 
1248
1249     /* Discard file comment if any */
1250     if ((flags & COMMENT) != 0) {
1251             while (NEXTBYTE() != 0) /* null */ ;
1252     }
1253
1254     /* Decompress */
1255     if ((res = inflate())) {
1256             switch (res) {
1257             case 0:
1258                     break;
1259             case 1:
1260                     error("invalid compressed format (err=1)");
1261                     break;
1262             case 2:
1263                     error("invalid compressed format (err=2)");
1264                     break;
1265             case 3:
1266                     error("out of memory");
1267                     break;
1268             case 4:
1269                     error("out of input data");
1270                     break;
1271             default:
1272                     error("invalid compressed format (other)");
1273             }
1274             return -1;
1275     }
1276             
1277     /* Get the crc and original length */
1278     /* crc32  (see algorithm.doc)
1279      * uncompressed input size modulo 2^32
1280      */
1281     orig_crc = (ulg) NEXTBYTE();
1282     orig_crc |= (ulg) NEXTBYTE() << 8;
1283     orig_crc |= (ulg) NEXTBYTE() << 16;
1284     orig_crc |= (ulg) NEXTBYTE() << 24;
1285     
1286     orig_len = (ulg) NEXTBYTE();
1287     orig_len |= (ulg) NEXTBYTE() << 8;
1288     orig_len |= (ulg) NEXTBYTE() << 16;
1289     orig_len |= (ulg) NEXTBYTE() << 24;
1290     
1291     /* Validate decompression */
1292     if (orig_crc != CRC_VALUE) {
1293             error("crc error");
1294             return -1;
1295     }
1296     if (orig_len != bytes_out) {
1297             error("length error");
1298             return -1;
1299     }
1300     return 0;
1301
1302  underrun:                      /* NEXTBYTE() goto's here if needed */
1303     error("out of input data");
1304     return -1;
1305 }
1306
1307