Context Navigation

source: bootcd/isolinux/syslinux-6.03/memdisk/inflate.c

Last change on this file was e16e8f2, checked in by Edwin Eefting <edwin@datux.nl>, 3 years ago
bootstuff
Property mode set to `100644`
File size: 31.9 KB

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

Note: See TracBrowser for help on using the repository browser.

Download in other formats: