1 /* Inflate deflated data
3 Copyright (C) 1997, 1998, 1999, 2002, 2006 Free Software
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 3, or (at your option)
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License
17 along with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 /* Not copyrighted 1992 by Mark Adler
21 version c10p1, 10 January 1993 */
23 /* You can do whatever you like with this source file, though I would
24 prefer that if you modify it and redistribute it that you include
25 comments to that effect with your name and the date. Thank you.
26 [The history has been moved to the file ChangeLog.]
30 Inflate deflated (PKZIP's method 8 compressed) data. The compression
31 method searches for as much of the current string of bytes (up to a
32 length of 258) in the previous 32K bytes. If it doesn't find any
33 matches (of at least length 3), it codes the next byte. Otherwise, it
34 codes the length of the matched string and its distance backwards from
35 the current position. There is a single Huffman code that codes both
36 single bytes (called "literals") and match lengths. A second Huffman
37 code codes the distance information, which follows a length code. Each
38 length or distance code actually represents a base value and a number
39 of "extra" (sometimes zero) bits to get to add to the base value. At
40 the end of each deflated block is a special end-of-block (EOB) literal/
41 length code. The decoding process is basically: get a literal/length
42 code; if EOB then done; if a literal, emit the decoded byte; if a
43 length then get the distance and emit the referred-to bytes from the
44 sliding window of previously emitted data.
46 There are (currently) three kinds of inflate blocks: stored, fixed, and
47 dynamic. The compressor deals with some chunk of data at a time, and
48 decides which method to use on a chunk-by-chunk basis. A chunk might
49 typically be 32K or 64K. If the chunk is uncompressible, then the
50 "stored" method is used. In this case, the bytes are simply stored as
51 is, eight bits per byte, with none of the above coding. The bytes are
52 preceded by a count, since there is no longer an EOB code.
54 If the data is compressible, then either the fixed or dynamic methods
55 are used. In the dynamic method, the compressed data is preceded by
56 an encoding of the literal/length and distance Huffman codes that are
57 to be used to decode this block. The representation is itself Huffman
58 coded, and so is preceded by a description of that code. These code
59 descriptions take up a little space, and so for small blocks, there is
60 a predefined set of codes, called the fixed codes. The fixed method is
61 used if the block codes up smaller that way (usually for quite small
62 chunks), otherwise the dynamic method is used. In the latter case, the
63 codes are customized to the probabilities in the current block, and so
64 can code it much better than the pre-determined fixed codes.
66 The Huffman codes themselves are decoded using a multi-level table
67 lookup, in order to maximize the speed of decoding plus the speed of
68 building the decoding tables. See the comments below that precede the
69 lbits and dbits tuning parameters.
74 Notes beyond the 1.93a appnote.txt:
76 1. Distance pointers never point before the beginning of the output
78 2. Distance pointers can point back across blocks, up to 32k away.
79 3. There is an implied maximum of 7 bits for the bit length table and
80 15 bits for the actual data.
81 4. If only one code exists, then it is encoded using one bit. (Zero
82 would be more efficient, but perhaps a little confusing.) If two
83 codes exist, they are coded using one bit each (0 and 1).
84 5. There is no way of sending zero distance codes--a dummy must be
85 sent if there are none. (History: a pre 2.0 version of PKZIP would
86 store blocks with no distance codes, but this was discovered to be
87 too harsh a criterion.) Valid only for 1.93a. 2.04c does allow
88 zero distance codes, which is sent as one code of zero bits in
90 6. There are up to 286 literal/length codes. Code 256 represents the
91 end-of-block. Note however that the static length tree defines
92 288 codes just to fill out the Huffman codes. Codes 286 and 287
93 cannot be used though, since there is no length base or extra bits
94 defined for them. Similarly, there are up to 30 distance codes.
95 However, static trees define 32 codes (all 5 bits) to fill out the
96 Huffman codes, but the last two had better not show up in the data.
97 7. Unzip can check dynamic Huffman blocks for complete code sets.
98 The exception is that a single code would not be complete (see #4).
99 8. The five bits following the block type is really the number of
100 literal codes sent minus 257.
101 9. Length codes 8,16,16 are interpreted as 13 length codes of 8 bits
102 (1+6+6). Therefore, to output three times the length, you output
103 three codes (1+1+1), whereas to output four times the same length,
104 you only need two codes (1+3). Hmm.
105 10. In the tree reconstruction algorithm, Code = Code + Increment
106 only if BitLength(i) is not zero. (Pretty obvious.)
107 11. Correction: 4 Bits: # of Bit Length codes - 4 (4 - 19)
108 12. Note: length code 284 can represent 227-258, but length code 285
109 really is 258. The last length deserves its own, short code
110 since it gets used a lot in very redundant files. The length
111 258 is special since 258 - 3 (the min match length) is 255.
112 13. The literal/length and distance code bit lengths are read as a
113 single stream of lengths. It is possible (and advantageous) for
114 a repeat code (16, 17, or 18) to go across the boundary between
115 the two sets of lengths.
121 #if defined STDC_HEADERS || defined HAVE_STDLIB_H
128 /* Huffman code lookup table entry--this entry is four bytes for machines
129 that have 16-bit pointers (e.g. PC's in the small or medium model).
130 Valid extra bits are 0..13. e == 15 is EOB (end of block), e == 16
131 means that v is a literal, 16 < e < 32 means that v is a pointer to
132 the next table, which codes e - 16 bits, and lastly e == 99 indicates
133 an unused code. If a code with e == 99 is looked up, this implies an
134 error in the data. */
136 uch e; /* number of extra bits or operation */
137 uch b; /* number of bits in this code or subcode */
139 ush n; /* literal, length base, or distance base */
140 struct huft *t; /* pointer to next level of table */
145 /* Function prototypes */
146 int huft_build OF((unsigned *, unsigned, unsigned, ush *, ush *,
147 struct huft **, int *));
148 int huft_free OF((struct huft *));
149 int inflate_codes OF((struct huft *, struct huft *, int, int));
150 int inflate_stored OF((void));
151 int inflate_fixed OF((void));
152 int inflate_dynamic OF((void));
153 int inflate_block OF((int *));
154 int inflate OF((void));
157 /* The inflate algorithm uses a sliding 32K byte window on the uncompressed
158 stream to find repeated byte strings. This is implemented here as a
159 circular buffer. The index is updated simply by incrementing and then
160 and'ing with 0x7fff (32K-1). */
161 /* It is left to other modules to supply the 32K area. It is assumed
162 to be usable as if it were declared "uch slide[32768];" or as just
163 "uch *slide;" and then malloc'ed in the latter case. The definition
164 must be in unzip.h, included above. */
165 /* unsigned wp; current position in slide */
167 #define flush_output(w) (wp=(w),flush_window())
169 /* Tables for deflate from PKZIP's appnote.txt. */
170 static unsigned border[] = { /* Order of the bit length code lengths */
171 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
172 static ush cplens[] = { /* Copy lengths for literal codes 257..285 */
173 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31,
174 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258, 0, 0};
175 /* note: see note #13 above about the 258 in this list. */
176 static ush cplext[] = { /* Extra bits for literal codes 257..285 */
177 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2,
178 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0, 99, 99}; /* 99==invalid */
179 static ush cpdist[] = { /* Copy offsets for distance codes 0..29 */
180 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193,
181 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145,
182 8193, 12289, 16385, 24577};
183 static ush cpdext[] = { /* Extra bits for distance codes */
184 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6,
185 7, 7, 8, 8, 9, 9, 10, 10, 11, 11,
190 /* Macros for inflate() bit peeking and grabbing.
194 x = b & mask_bits[j];
197 where NEEDBITS makes sure that b has at least j bits in it, and
198 DUMPBITS removes the bits from b. The macros use the variable k
199 for the number of bits in b. Normally, b and k are register
200 variables for speed, and are initialized at the beginning of a
201 routine that uses these macros from a global bit buffer and count.
202 The macros also use the variable w, which is a cached copy of wp.
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.
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
221 ulg bb; /* bit buffer */
222 unsigned bk; /* bits in bit buffer */
226 0x0001, 0x0003, 0x0007, 0x000f, 0x001f, 0x003f, 0x007f, 0x00ff,
227 0x01ff, 0x03ff, 0x07ff, 0x0fff, 0x1fff, 0x3fff, 0x7fff, 0xffff
230 #define GETBYTE() (inptr < insize ? inbuf[inptr++] : (wp = w, fill_inbuf(0)))
234 # define NEXTBYTE() \
235 (decrypt ? (cc = GETBYTE(), zdecode(cc), cc) : GETBYTE())
237 # define NEXTBYTE() (uch)GETBYTE()
239 #define NEEDBITS(n) {while(k<(n)){b|=((ulg)NEXTBYTE())<<k;k+=8;}}
240 #define DUMPBITS(n) {b>>=(n);k-=(n);}
244 Huffman code decoding is performed using a multi-level table lookup.
245 The fastest way to decode is to simply build a lookup table whose
246 size is determined by the longest code. However, the time it takes
247 to build this table can also be a factor if the data being decoded
248 is not very long. The most common codes are necessarily the
249 shortest codes, so those codes dominate the decoding time, and hence
250 the speed. The idea is you can have a shorter table that decodes the
251 shorter, more probable codes, and then point to subsidiary tables for
252 the longer codes. The time it costs to decode the longer codes is
253 then traded against the time it takes to make longer tables.
255 This results of this trade are in the variables lbits and dbits
256 below. lbits is the number of bits the first level table for literal/
257 length codes can decode in one step, and dbits is the same thing for
258 the distance codes. Subsequent tables are also less than or equal to
259 those sizes. These values may be adjusted either when all of the
260 codes are shorter than that, in which case the longest code length in
261 bits is used, or when the shortest code is *longer* than the requested
262 table size, in which case the length of the shortest code in bits is
265 There are two different values for the two tables, since they code a
266 different number of possibilities each. The literal/length table
267 codes 286 possible values, or in a flat code, a little over eight
268 bits. The distance table codes 30 possible values, or a little less
269 than five bits, flat. The optimum values for speed end up being
270 about one bit more than those, so lbits is 8+1 and dbits is 5+1.
271 The optimum values may differ though from machine to machine, and
272 possibly even between compilers. Your mileage may vary.
276 int lbits = 9; /* bits in base literal/length lookup table */
277 int dbits = 6; /* bits in base distance lookup table */
280 /* If BMAX needs to be larger than 16, then h and x[] should be ulg. */
281 #define BMAX 16 /* maximum bit length of any code (16 for explode) */
282 #define N_MAX 288 /* maximum number of codes in any set */
285 unsigned hufts; /* track memory usage */
288 int huft_build(b, n, s, d, e, t, m)
289 unsigned *b; /* code lengths in bits (all assumed <= BMAX) */
290 unsigned n; /* number of codes (assumed <= N_MAX) */
291 unsigned s; /* number of simple-valued codes (0..s-1) */
292 ush *d; /* list of base values for non-simple codes */
293 ush *e; /* list of extra bits for non-simple codes */
294 struct huft **t; /* result: starting table */
295 int *m; /* maximum lookup bits, returns actual */
296 /* Given a list of code lengths and a maximum table size, make a set of
297 tables to decode that set of codes. Return zero on success, one if
298 the given code set is incomplete (the tables are still built in this
299 case), two if the input is invalid (all zero length codes or an
300 oversubscribed set of lengths), and three if not enough memory. */
302 unsigned a; /* counter for codes of length k */
303 unsigned c[BMAX+1]; /* bit length count table */
304 unsigned f; /* i repeats in table every f entries */
305 int g; /* maximum code length */
306 int h; /* table level */
307 register unsigned i; /* counter, current code */
308 register unsigned j; /* counter */
309 register int k; /* number of bits in current code */
310 int l; /* bits per table (returned in m) */
311 register unsigned *p; /* pointer into c[], b[], or v[] */
312 register struct huft *q; /* points to current table */
313 struct huft r; /* table entry for structure assignment */
314 struct huft *u[BMAX]; /* table stack */
315 unsigned v[N_MAX]; /* values in order of bit length */
316 register int w; /* bits before this table == (l * h) */
317 unsigned x[BMAX+1]; /* bit offsets, then code stack */
318 unsigned *xp; /* pointer into x */
319 int y; /* number of dummy codes added */
320 unsigned z; /* number of entries in current table */
323 /* Generate counts for each bit length */
324 memzero(c, sizeof(c));
327 Tracecv(*p, (stderr, (n-i >= ' ' && n-i <= '~' ? "%c %d\n" : "0x%x %d\n"),
329 c[*p]++; /* assume all entries <= BMAX */
330 p++; /* Can't combine with above line (Solaris bug) */
332 if (c[0] == n) /* null input--all zero length codes */
334 q = (struct huft *) malloc (3 * sizeof *q);
338 q[0].v.t = (struct huft *) NULL;
339 q[1].e = 99; /* invalid code marker */
341 q[2].e = 99; /* invalid code marker */
349 /* Find minimum and maximum length, bound *m by those */
351 for (j = 1; j <= BMAX; j++)
354 k = j; /* minimum code length */
357 for (i = BMAX; i; i--)
360 g = i; /* maximum code length */
366 /* Adjust last length count to fill out codes, if needed */
367 for (y = 1 << j; j < i; j++, y <<= 1)
369 return 2; /* bad input: more codes than bits */
375 /* Generate starting offsets into the value table for each length */
377 p = c + 1; xp = x + 2;
378 while (--i) { /* note that i == g from above */
383 /* Make a table of values in order of bit lengths */
389 n = x[g]; /* set n to length of v */
392 /* Generate the Huffman codes and for each, make the table entries */
393 x[0] = i = 0; /* first Huffman code is zero */
394 p = v; /* grab values in bit order */
395 h = -1; /* no tables yet--level -1 */
396 w = -l; /* bits decoded == (l * h) */
397 u[0] = (struct huft *)NULL; /* just to keep compilers happy */
398 q = (struct huft *)NULL; /* ditto */
401 /* go through the bit lengths (k already is bits in shortest code) */
407 /* here i is the Huffman code of length k bits for value *p */
408 /* make tables up to required level */
412 w += l; /* previous table always l bits */
414 /* compute minimum size table less than or equal to l bits */
415 z = (z = g - w) > (unsigned)l ? l : z; /* upper limit on table size */
416 if ((f = 1 << (j = k - w)) > a + 1) /* try a k-w bit table */
417 { /* too few codes for k-w bit table */
418 f -= a + 1; /* deduct codes from patterns left */
421 while (++j < z) /* try smaller tables up to z bits */
423 if ((f <<= 1) <= *++xp)
424 break; /* enough codes to use up j bits */
425 f -= *xp; /* else deduct codes from patterns */
428 z = 1 << j; /* table entries for j-bit table */
430 /* allocate and link in new table */
431 if ((q = (struct huft *)malloc((z + 1)*sizeof(struct huft))) ==
436 return 3; /* not enough memory */
438 hufts += z + 1; /* track memory usage */
439 *t = q + 1; /* link to list for huft_free() */
440 *(t = &(q->v.t)) = (struct huft *)NULL;
441 u[h] = ++q; /* table starts after link */
443 /* connect to last table, if there is one */
446 x[h] = i; /* save pattern for backing up */
447 r.b = (uch)l; /* bits to dump before this table */
448 r.e = (uch)(16 + j); /* bits in this table */
449 r.v.t = q; /* pointer to this table */
450 j = i >> (w - l); /* (get around Turbo C bug) */
451 u[h-1][j] = r; /* connect to last table */
455 /* set up table entry in r */
458 r.e = 99; /* out of values--invalid code */
461 r.e = (uch)(*p < 256 ? 16 : 15); /* 256 is end-of-block code */
462 r.v.n = (ush)(*p); /* simple code is just the value */
463 p++; /* one compiler does not like *p++ */
467 r.e = (uch)e[*p - s]; /* non-simple--look up in lists */
471 /* fill code-like entries with r */
473 for (j = i >> w; j < z; j += f)
476 /* backwards increment the k-bit code i */
477 for (j = 1 << (k - 1); i & j; j >>= 1)
481 /* backup over finished tables */
482 while ((i & ((1 << w) - 1)) != x[h])
484 h--; /* don't need to update q */
491 /* Return true (1) if we were given an incomplete table */
492 return y != 0 && g != 1;
498 struct huft *t; /* table to free */
499 /* Free the malloc'ed tables built by huft_build(), which makes a linked
500 list of the tables it made, with the links in a dummy first entry of
503 register struct huft *p, *q;
506 /* Go through linked list, freeing from the malloced (t[-1]) address. */
508 while (p != (struct huft *)NULL)
518 int inflate_codes(tl, td, bl, bd)
519 struct huft *tl, *td; /* literal/length and distance decoder tables */
520 int bl, bd; /* number of bits decoded by tl[] and td[] */
521 /* inflate (decompress) the codes in a deflated (compressed) block.
522 Return an error code or zero if it all goes ok. */
524 register unsigned e; /* table entry flag/number of extra bits */
525 unsigned n, d; /* length and index for copy */
526 unsigned w; /* current window position */
527 struct huft *t; /* pointer to table entry */
528 unsigned ml, md; /* masks for bl and bd bits */
529 register ulg b; /* bit buffer */
530 register unsigned k; /* number of bits in bit buffer */
533 /* make local copies of globals */
534 b = bb; /* initialize bit buffer */
536 w = wp; /* initialize window position */
538 /* inflate the coded data */
539 ml = mask_bits[bl]; /* precompute masks for speed */
541 for (;;) /* do until end of block */
543 NEEDBITS((unsigned)bl)
544 if ((e = (t = tl + ((unsigned)b & ml))->e) > 16)
551 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
553 if (e == 16) /* then it's a literal */
555 slide[w++] = (uch)t->v.n;
556 Tracevv((stderr, "%c", slide[w-1]));
563 else /* it's an EOB or a length */
565 /* exit if end of block */
569 /* get length of block to copy */
571 n = t->v.n + ((unsigned)b & mask_bits[e]);
574 /* decode distance of block to copy */
575 NEEDBITS((unsigned)bd)
576 if ((e = (t = td + ((unsigned)b & md))->e) > 16)
583 } while ((e = (t = t->v.t + ((unsigned)b & mask_bits[e]))->e) > 16);
586 d = w - t->v.n - ((unsigned)b & mask_bits[e]);
588 Tracevv((stderr,"\\[%d,%d]", w-d, n));
592 n -= (e = (e = WSIZE - ((d &= WSIZE-1) > w ? d : w)) > n ? n : e);
593 #if !defined(NOMEMCPY) && !defined(DEBUG)
594 if (w - d >= e) /* (this test assumes unsigned comparison) */
596 memcpy(slide + w, slide + d, e);
600 else /* do it slow to avoid memcpy() overlap */
601 #endif /* !NOMEMCPY */
603 slide[w++] = slide[d++];
604 Tracevv((stderr, "%c", slide[w-1]));
616 /* restore the globals from the locals */
617 wp = w; /* restore global window pointer */
618 bb = b; /* restore global bit buffer */
628 /* "decompress" an inflated type 0 (stored) block. */
630 unsigned n; /* number of bytes in block */
631 unsigned w; /* current window position */
632 register ulg b; /* bit buffer */
633 register unsigned k; /* number of bits in bit buffer */
636 /* make local copies of globals */
637 b = bb; /* initialize bit buffer */
639 w = wp; /* initialize window position */
642 /* go to byte boundary */
647 /* get the length and its complement */
649 n = ((unsigned)b & 0xffff);
652 if (n != (unsigned)((~b) & 0xffff))
653 return 1; /* error in compressed data */
657 /* read and output the compressed data */
671 /* restore the globals from the locals */
672 wp = w; /* restore global window pointer */
673 bb = b; /* restore global bit buffer */
681 /* decompress an inflated type 1 (fixed Huffman codes) block. We should
682 either replace this with a custom decoder, or at least precompute the
685 int i; /* temporary variable */
686 struct huft *tl; /* literal/length code table */
687 struct huft *td; /* distance code table */
688 int bl; /* lookup bits for tl */
689 int bd; /* lookup bits for td */
690 unsigned l[288]; /* length list for huft_build */
693 /* set up literal table */
694 for (i = 0; i < 144; i++)
700 for (; i < 288; i++) /* make a complete, but wrong code set */
703 if ((i = huft_build(l, 288, 257, cplens, cplext, &tl, &bl)) != 0)
707 /* set up distance table */
708 for (i = 0; i < 30; i++) /* make an incomplete code set */
711 if ((i = huft_build(l, 30, 0, cpdist, cpdext, &td, &bd)) > 1)
718 /* decompress until an end-of-block code */
719 if (inflate_codes(tl, td, bl, bd))
723 /* free the decoding tables, return */
731 int inflate_dynamic()
732 /* decompress an inflated type 2 (dynamic Huffman codes) block. */
734 int i; /* temporary variables */
736 unsigned l; /* last length */
737 unsigned m; /* mask for bit lengths table */
738 unsigned n; /* number of lengths to get */
739 unsigned w; /* current window position */
740 struct huft *tl; /* literal/length code table */
741 struct huft *td; /* distance code table */
742 int bl; /* lookup bits for tl */
743 int bd; /* lookup bits for td */
744 unsigned nb; /* number of bit length codes */
745 unsigned nl; /* number of literal/length codes */
746 unsigned nd; /* number of distance codes */
747 #ifdef PKZIP_BUG_WORKAROUND
748 unsigned ll[288+32]; /* literal/length and distance code lengths */
750 unsigned ll[286+30]; /* literal/length and distance code lengths */
752 register ulg b; /* bit buffer */
753 register unsigned k; /* number of bits in bit buffer */
756 /* make local bit buffer */
762 /* read in table lengths */
764 nl = 257 + ((unsigned)b & 0x1f); /* number of literal/length codes */
767 nd = 1 + ((unsigned)b & 0x1f); /* number of distance codes */
770 nb = 4 + ((unsigned)b & 0xf); /* number of bit length codes */
772 #ifdef PKZIP_BUG_WORKAROUND
773 if (nl > 288 || nd > 32)
775 if (nl > 286 || nd > 30)
777 return 1; /* bad lengths */
780 /* read in bit-length-code lengths */
781 for (j = 0; j < nb; j++)
784 ll[border[j]] = (unsigned)b & 7;
791 /* build decoding table for trees--single level, 7 bit lookup */
793 if ((i = huft_build(ll, 19, 19, NULL, NULL, &tl, &bl)) != 0)
797 return i; /* incomplete code set */
800 if (tl == NULL) /* Grrrhhh */
803 /* read in literal and distance code lengths */
807 while ((unsigned)i < n)
809 NEEDBITS((unsigned)bl)
810 j = (td = tl + ((unsigned)b & m))->b;
813 if (j < 16) /* length of code in bits (0..15) */
814 ll[i++] = l = j; /* save last length in l */
815 else if (j == 16) /* repeat last length 3 to 6 times */
818 j = 3 + ((unsigned)b & 3);
820 if ((unsigned)i + j > n)
825 else if (j == 17) /* 3 to 10 zero length codes */
828 j = 3 + ((unsigned)b & 7);
830 if ((unsigned)i + j > n)
836 else /* j == 18: 11 to 138 zero length codes */
839 j = 11 + ((unsigned)b & 0x7f);
841 if ((unsigned)i + j > n)
850 /* free decoding table for trees */
854 /* restore the global bit buffer */
859 /* build the decoding tables for literal/length and distance codes */
861 if ((i = huft_build(ll, nl, 257, cplens, cplext, &tl, &bl)) != 0)
864 Trace ((stderr, " incomplete literal tree\n"));
867 return i; /* incomplete code set */
870 if ((i = huft_build(ll + nl, nd, 0, cpdist, cpdext, &td, &bd)) != 0)
873 Trace ((stderr, " incomplete distance tree\n"));
874 #ifdef PKZIP_BUG_WORKAROUND
881 return i; /* incomplete code set */
887 /* decompress until an end-of-block code */
888 int err = inflate_codes(tl, td, bl, bd) ? 1 : 0;
890 /* free the decoding tables */
901 int *e; /* last block flag */
902 /* decompress an inflated block */
904 unsigned t; /* block type */
905 unsigned w; /* current window position */
906 register ulg b; /* bit buffer */
907 register unsigned k; /* number of bits in bit buffer */
910 /* make local bit buffer */
916 /* read in last block bit */
922 /* read in block type */
928 /* restore the global bit buffer */
933 /* inflate that block type */
935 return inflate_dynamic();
937 return inflate_stored();
939 return inflate_fixed();
949 /* decompress an inflated entry */
951 int e; /* last block flag */
952 int r; /* result code */
953 unsigned h; /* maximum struct huft's malloc'ed */
956 /* initialize window, bit buffer */
962 /* decompress until the last block */
966 if ((r = inflate_block(&e)) != 0)
972 /* Undo too much lookahead. The next read will be byte aligned so we
973 * can discard unused bits in the last meaningful byte.
980 /* flush out slide */
985 Trace ((stderr, "<%u> ", h));