Python code coverage for Modules/zlib/inflate.c

#	count	content
1	n/a	/* inflate.c -- zlib decompression
2	n/a	* Copyright (C) 1995-2016 Mark Adler
3	n/a	* For conditions of distribution and use, see copyright notice in zlib.h
4	n/a	*/
5	n/a
6	n/a	/*
7	n/a	* Change history:
8	n/a	*
9	n/a	* 1.2.beta0 24 Nov 2002
10	n/a	* - First version -- complete rewrite of inflate to simplify code, avoid
11	n/a	* creation of window when not needed, minimize use of window when it is
12	n/a	* needed, make inffast.c even faster, implement gzip decoding, and to
13	n/a	* improve code readability and style over the previous zlib inflate code
14	n/a	*
15	n/a	* 1.2.beta1 25 Nov 2002
16	n/a	* - Use pointers for available input and output checking in inffast.c
17	n/a	* - Remove input and output counters in inffast.c
18	n/a	* - Change inffast.c entry and loop from avail_in >= 7 to >= 6
19	n/a	* - Remove unnecessary second byte pull from length extra in inffast.c
20	n/a	* - Unroll direct copy to three copies per loop in inffast.c
21	n/a	*
22	n/a	* 1.2.beta2 4 Dec 2002
23	n/a	* - Change external routine names to reduce potential conflicts
24	n/a	* - Correct filename to inffixed.h for fixed tables in inflate.c
25	n/a	* - Make hbuf[] unsigned char to match parameter type in inflate.c
26	n/a	* - Change strm->next_out[-state->offset] to *(strm->next_out - state->offset)
27	n/a	* to avoid negation problem on Alphas (64 bit) in inflate.c
28	n/a	*
29	n/a	* 1.2.beta3 22 Dec 2002
30	n/a	* - Add comments on state->bits assertion in inffast.c
31	n/a	* - Add comments on op field in inftrees.h
32	n/a	* - Fix bug in reuse of allocated window after inflateReset()
33	n/a	* - Remove bit fields--back to byte structure for speed
34	n/a	* - Remove distance extra == 0 check in inflate_fast()--only helps for lengths
35	n/a	* - Change post-increments to pre-increments in inflate_fast(), PPC biased?
36	n/a	* - Add compile time option, POSTINC, to use post-increments instead (Intel?)
37	n/a	* - Make MATCH copy in inflate() much faster for when inflate_fast() not used
38	n/a	* - Use local copies of stream next and avail values, as well as local bit
39	n/a	* buffer and bit count in inflate()--for speed when inflate_fast() not used
40	n/a	*
41	n/a	* 1.2.beta4 1 Jan 2003
42	n/a	* - Split ptr - 257 statements in inflate_table() to avoid compiler warnings
43	n/a	* - Move a comment on output buffer sizes from inffast.c to inflate.c
44	n/a	* - Add comments in inffast.c to introduce the inflate_fast() routine
45	n/a	* - Rearrange window copies in inflate_fast() for speed and simplification
46	n/a	* - Unroll last copy for window match in inflate_fast()
47	n/a	* - Use local copies of window variables in inflate_fast() for speed
48	n/a	* - Pull out common wnext == 0 case for speed in inflate_fast()
49	n/a	* - Make op and len in inflate_fast() unsigned for consistency
50	n/a	* - Add FAR to lcode and dcode declarations in inflate_fast()
51	n/a	* - Simplified bad distance check in inflate_fast()
52	n/a	* - Added inflateBackInit(), inflateBack(), and inflateBackEnd() in new
53	n/a	* source file infback.c to provide a call-back interface to inflate for
54	n/a	* programs like gzip and unzip -- uses window as output buffer to avoid
55	n/a	* window copying
56	n/a	*
57	n/a	* 1.2.beta5 1 Jan 2003
58	n/a	* - Improved inflateBack() interface to allow the caller to provide initial
59	n/a	* input in strm.
60	n/a	* - Fixed stored blocks bug in inflateBack()
61	n/a	*
62	n/a	* 1.2.beta6 4 Jan 2003
63	n/a	* - Added comments in inffast.c on effectiveness of POSTINC
64	n/a	* - Typecasting all around to reduce compiler warnings
65	n/a	* - Changed loops from while (1) or do {} while (1) to for (;;), again to
66	n/a	* make compilers happy
67	n/a	* - Changed type of window in inflateBackInit() to unsigned char *
68	n/a	*
69	n/a	* 1.2.beta7 27 Jan 2003
70	n/a	* - Changed many types to unsigned or unsigned short to avoid warnings
71	n/a	* - Added inflateCopy() function
72	n/a	*
73	n/a	* 1.2.0 9 Mar 2003
74	n/a	* - Changed inflateBack() interface to provide separate opaque descriptors
75	n/a	* for the in() and out() functions
76	n/a	* - Changed inflateBack() argument and in_func typedef to swap the length
77	n/a	* and buffer address return values for the input function
78	n/a	* - Check next_in and next_out for Z_NULL on entry to inflate()
79	n/a	*
80	n/a	* The history for versions after 1.2.0 are in ChangeLog in zlib distribution.
81	n/a	*/
82	n/a
83	n/a	#include "zutil.h"
84	n/a	#include "inftrees.h"
85	n/a	#include "inflate.h"
86	n/a	#include "inffast.h"
87	n/a
88	n/a	#ifdef MAKEFIXED
89	n/a	# ifndef BUILDFIXED
90	n/a	# define BUILDFIXED
91	n/a	# endif
92	n/a	#endif
93	n/a
94	n/a	/* function prototypes */
95	n/a	local int inflateStateCheck OF((z_streamp strm));
96	n/a	local void fixedtables OF((struct inflate_state FAR *state));
97	n/a	local int updatewindow OF((z_streamp strm, const unsigned char FAR *end,
98	n/a	unsigned copy));
99	n/a	#ifdef BUILDFIXED
100	n/a	void makefixed OF((void));
101	n/a	#endif
102	n/a	local unsigned syncsearch OF((unsigned FAR have, const unsigned char FAR buf,
103	n/a	unsigned len));
104	n/a
105	n/a	local int inflateStateCheck(strm)
106	n/a	z_streamp strm;
107	n/a	{
108	n/a	struct inflate_state FAR *state;
109	n/a	if (strm == Z_NULL \|\|
110	n/a	strm->zalloc == (alloc_func)0 \|\| strm->zfree == (free_func)0)
111	n/a	return 1;
112	n/a	state = (struct inflate_state FAR *)strm->state;
113	n/a	if (state == Z_NULL \|\| state->strm != strm \|\|
114	n/a	state->mode < HEAD \|\| state->mode > SYNC)
115	n/a	return 1;
116	n/a	return 0;
117	n/a	}
118	n/a
119	n/a	int ZEXPORT inflateResetKeep(strm)
120	n/a	z_streamp strm;
121	n/a	{
122	n/a	struct inflate_state FAR *state;
123	n/a
124	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
125	n/a	state = (struct inflate_state FAR *)strm->state;
126	n/a	strm->total_in = strm->total_out = state->total = 0;
127	n/a	strm->msg = Z_NULL;
128	n/a	if (state->wrap) /* to support ill-conceived Java test suite */
129	n/a	strm->adler = state->wrap & 1;
130	n/a	state->mode = HEAD;
131	n/a	state->last = 0;
132	n/a	state->havedict = 0;
133	n/a	state->dmax = 32768U;
134	n/a	state->head = Z_NULL;
135	n/a	state->hold = 0;
136	n/a	state->bits = 0;
137	n/a	state->lencode = state->distcode = state->next = state->codes;
138	n/a	state->sane = 1;
139	n/a	state->back = -1;
140	n/a	Tracev((stderr, "inflate: reset\n"));
141	n/a	return Z_OK;
142	n/a	}
143	n/a
144	n/a	int ZEXPORT inflateReset(strm)
145	n/a	z_streamp strm;
146	n/a	{
147	n/a	struct inflate_state FAR *state;
148	n/a
149	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
150	n/a	state = (struct inflate_state FAR *)strm->state;
151	n/a	state->wsize = 0;
152	n/a	state->whave = 0;
153	n/a	state->wnext = 0;
154	n/a	return inflateResetKeep(strm);
155	n/a	}
156	n/a
157	n/a	int ZEXPORT inflateReset2(strm, windowBits)
158	n/a	z_streamp strm;
159	n/a	int windowBits;
160	n/a	{
161	n/a	int wrap;
162	n/a	struct inflate_state FAR *state;
163	n/a
164	n/a	/* get the state */
165	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
166	n/a	state = (struct inflate_state FAR *)strm->state;
167	n/a
168	n/a	/* extract wrap request from windowBits parameter */
169	n/a	if (windowBits < 0) {
170	n/a	wrap = 0;
171	n/a	windowBits = -windowBits;
172	n/a	}
173	n/a	else {
174	n/a	wrap = (windowBits >> 4) + 5;
175	n/a	#ifdef GUNZIP
176	n/a	if (windowBits < 48)
177	n/a	windowBits &= 15;
178	n/a	#endif
179	n/a	}
180	n/a
181	n/a	/* set number of window bits, free window if different */
182	n/a	if (windowBits && (windowBits < 8 \|\| windowBits > 15))
183	n/a	return Z_STREAM_ERROR;
184	n/a	if (state->window != Z_NULL && state->wbits != (unsigned)windowBits) {
185	n/a	ZFREE(strm, state->window);
186	n/a	state->window = Z_NULL;
187	n/a	}
188	n/a
189	n/a	/* update state and reset the rest of it */
190	n/a	state->wrap = wrap;
191	n/a	state->wbits = (unsigned)windowBits;
192	n/a	return inflateReset(strm);
193	n/a	}
194	n/a
195	n/a	int ZEXPORT inflateInit2_(strm, windowBits, version, stream_size)
196	n/a	z_streamp strm;
197	n/a	int windowBits;
198	n/a	const char *version;
199	n/a	int stream_size;
200	n/a	{
201	n/a	int ret;
202	n/a	struct inflate_state FAR *state;
203	n/a
204	n/a	if (version == Z_NULL \|\| version[0] != ZLIB_VERSION[0] \|\|
205	n/a	stream_size != (int)(sizeof(z_stream)))
206	n/a	return Z_VERSION_ERROR;
207	n/a	if (strm == Z_NULL) return Z_STREAM_ERROR;
208	n/a	strm->msg = Z_NULL; /* in case we return an error */
209	n/a	if (strm->zalloc == (alloc_func)0) {
210	n/a	#ifdef Z_SOLO
211	n/a	return Z_STREAM_ERROR;
212	n/a	#else
213	n/a	strm->zalloc = zcalloc;
214	n/a	strm->opaque = (voidpf)0;
215	n/a	#endif
216	n/a	}
217	n/a	if (strm->zfree == (free_func)0)
218	n/a	#ifdef Z_SOLO
219	n/a	return Z_STREAM_ERROR;
220	n/a	#else
221	n/a	strm->zfree = zcfree;
222	n/a	#endif
223	n/a	state = (struct inflate_state FAR *)
224	n/a	ZALLOC(strm, 1, sizeof(struct inflate_state));
225	n/a	if (state == Z_NULL) return Z_MEM_ERROR;
226	n/a	Tracev((stderr, "inflate: allocated\n"));
227	n/a	strm->state = (struct internal_state FAR *)state;
228	n/a	state->strm = strm;
229	n/a	state->window = Z_NULL;
230	n/a	state->mode = HEAD; /* to pass state test in inflateReset2() */
231	n/a	ret = inflateReset2(strm, windowBits);
232	n/a	if (ret != Z_OK) {
233	n/a	ZFREE(strm, state);
234	n/a	strm->state = Z_NULL;
235	n/a	}
236	n/a	return ret;
237	n/a	}
238	n/a
239	n/a	int ZEXPORT inflateInit_(strm, version, stream_size)
240	n/a	z_streamp strm;
241	n/a	const char *version;
242	n/a	int stream_size;
243	n/a	{
244	n/a	return inflateInit2_(strm, DEF_WBITS, version, stream_size);
245	n/a	}
246	n/a
247	n/a	int ZEXPORT inflatePrime(strm, bits, value)
248	n/a	z_streamp strm;
249	n/a	int bits;
250	n/a	int value;
251	n/a	{
252	n/a	struct inflate_state FAR *state;
253	n/a
254	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
255	n/a	state = (struct inflate_state FAR *)strm->state;
256	n/a	if (bits < 0) {
257	n/a	state->hold = 0;
258	n/a	state->bits = 0;
259	n/a	return Z_OK;
260	n/a	}
261	n/a	if (bits > 16 \|\| state->bits + (uInt)bits > 32) return Z_STREAM_ERROR;
262	n/a	value &= (1L << bits) - 1;
263	n/a	state->hold += (unsigned)value << state->bits;
264	n/a	state->bits += (uInt)bits;
265	n/a	return Z_OK;
266	n/a	}
267	n/a
268	n/a	/*
269	n/a	Return state with length and distance decoding tables and index sizes set to
270	n/a	fixed code decoding. Normally this returns fixed tables from inffixed.h.
271	n/a	If BUILDFIXED is defined, then instead this routine builds the tables the
272	n/a	first time it's called, and returns those tables the first time and
273	n/a	thereafter. This reduces the size of the code by about 2K bytes, in
274	n/a	exchange for a little execution time. However, BUILDFIXED should not be
275	n/a	used for threaded applications, since the rewriting of the tables and virgin
276	n/a	may not be thread-safe.
277	n/a	*/
278	n/a	local void fixedtables(state)
279	n/a	struct inflate_state FAR *state;
280	n/a	{
281	n/a	#ifdef BUILDFIXED
282	n/a	static int virgin = 1;
283	n/a	static code lenfix, distfix;
284	n/a	static code fixed[544];
285	n/a
286	n/a	/* build fixed huffman tables if first call (may not be thread safe) */
287	n/a	if (virgin) {
288	n/a	unsigned sym, bits;
289	n/a	static code *next;
290	n/a
291	n/a	/* literal/length table */
292	n/a	sym = 0;
293	n/a	while (sym < 144) state->lens[sym++] = 8;
294	n/a	while (sym < 256) state->lens[sym++] = 9;
295	n/a	while (sym < 280) state->lens[sym++] = 7;
296	n/a	while (sym < 288) state->lens[sym++] = 8;
297	n/a	next = fixed;
298	n/a	lenfix = next;
299	n/a	bits = 9;
300	n/a	inflate_table(LENS, state->lens, 288, &(next), &(bits), state->work);
301	n/a
302	n/a	/* distance table */
303	n/a	sym = 0;
304	n/a	while (sym < 32) state->lens[sym++] = 5;
305	n/a	distfix = next;
306	n/a	bits = 5;
307	n/a	inflate_table(DISTS, state->lens, 32, &(next), &(bits), state->work);
308	n/a
309	n/a	/* do this just once */
310	n/a	virgin = 0;
311	n/a	}
312	n/a	#else /* !BUILDFIXED */
313	n/a	# include "inffixed.h"
314	n/a	#endif /* BUILDFIXED */
315	n/a	state->lencode = lenfix;
316	n/a	state->lenbits = 9;
317	n/a	state->distcode = distfix;
318	n/a	state->distbits = 5;
319	n/a	}
320	n/a
321	n/a	#ifdef MAKEFIXED
322	n/a	#include <stdio.h>
323	n/a
324	n/a	/*
325	n/a	Write out the inffixed.h that is #include'd above. Defining MAKEFIXED also
326	n/a	defines BUILDFIXED, so the tables are built on the fly. makefixed() writes
327	n/a	those tables to stdout, which would be piped to inffixed.h. A small program
328	n/a	can simply call makefixed to do this:
329	n/a
330	n/a	void makefixed(void);
331	n/a
332	n/a	int main(void)
333	n/a	{
334	n/a	makefixed();
335	n/a	return 0;
336	n/a	}
337	n/a
338	n/a	Then that can be linked with zlib built with MAKEFIXED defined and run:
339	n/a
340	n/a	a.out > inffixed.h
341	n/a	*/
342	n/a	void makefixed()
343	n/a	{
344	n/a	unsigned low, size;
345	n/a	struct inflate_state state;
346	n/a
347	n/a	fixedtables(&state);
348	n/a	puts(" /* inffixed.h -- table for decoding fixed codes");
349	n/a	puts(" * Generated automatically by makefixed().");
350	n/a	puts(" */");
351	n/a	puts("");
352	n/a	puts(" /* WARNING: this file should not be used by applications.");
353	n/a	puts(" It is part of the implementation of this library and is");
354	n/a	puts(" subject to change. Applications should only use zlib.h.");
355	n/a	puts(" */");
356	n/a	puts("");
357	n/a	size = 1U << 9;
358	n/a	printf(" static const code lenfix[%u] = {", size);
359	n/a	low = 0;
360	n/a	for (;;) {
361	n/a	if ((low % 7) == 0) printf("\n ");
362	n/a	printf("{%u,%u,%d}", (low & 127) == 99 ? 64 : state.lencode[low].op,
363	n/a	state.lencode[low].bits, state.lencode[low].val);
364	n/a	if (++low == size) break;
365	n/a	putchar(',');
366	n/a	}
367	n/a	puts("\n };");
368	n/a	size = 1U << 5;
369	n/a	printf("\n static const code distfix[%u] = {", size);
370	n/a	low = 0;
371	n/a	for (;;) {
372	n/a	if ((low % 6) == 0) printf("\n ");
373	n/a	printf("{%u,%u,%d}", state.distcode[low].op, state.distcode[low].bits,
374	n/a	state.distcode[low].val);
375	n/a	if (++low == size) break;
376	n/a	putchar(',');
377	n/a	}
378	n/a	puts("\n };");
379	n/a	}
380	n/a	#endif /* MAKEFIXED */
381	n/a
382	n/a	/*
383	n/a	Update the window with the last wsize (normally 32K) bytes written before
384	n/a	returning. If window does not exist yet, create it. This is only called
385	n/a	when a window is already in use, or when output has been written during this
386	n/a	inflate call, but the end of the deflate stream has not been reached yet.
387	n/a	It is also called to create a window for dictionary data when a dictionary
388	n/a	is loaded.
389	n/a
390	n/a	Providing output buffers larger than 32K to inflate() should provide a speed
391	n/a	advantage, since only the last 32K of output is copied to the sliding window
392	n/a	upon return from inflate(), and since all distances after the first 32K of
393	n/a	output will fall in the output data, making match copies simpler and faster.
394	n/a	The advantage may be dependent on the size of the processor's data caches.
395	n/a	*/
396	n/a	local int updatewindow(strm, end, copy)
397	n/a	z_streamp strm;
398	n/a	const Bytef *end;
399	n/a	unsigned copy;
400	n/a	{
401	n/a	struct inflate_state FAR *state;
402	n/a	unsigned dist;
403	n/a
404	n/a	state = (struct inflate_state FAR *)strm->state;
405	n/a
406	n/a	/* if it hasn't been done already, allocate space for the window */
407	n/a	if (state->window == Z_NULL) {
408	n/a	state->window = (unsigned char FAR *)
409	n/a	ZALLOC(strm, 1U << state->wbits,
410	n/a	sizeof(unsigned char));
411	n/a	if (state->window == Z_NULL) return 1;
412	n/a	}
413	n/a
414	n/a	/* if window not in use yet, initialize */
415	n/a	if (state->wsize == 0) {
416	n/a	state->wsize = 1U << state->wbits;
417	n/a	state->wnext = 0;
418	n/a	state->whave = 0;
419	n/a	}
420	n/a
421	n/a	/* copy state->wsize or less output bytes into the circular window */
422	n/a	if (copy >= state->wsize) {
423	n/a	zmemcpy(state->window, end - state->wsize, state->wsize);
424	n/a	state->wnext = 0;
425	n/a	state->whave = state->wsize;
426	n/a	}
427	n/a	else {
428	n/a	dist = state->wsize - state->wnext;
429	n/a	if (dist > copy) dist = copy;
430	n/a	zmemcpy(state->window + state->wnext, end - copy, dist);
431	n/a	copy -= dist;
432	n/a	if (copy) {
433	n/a	zmemcpy(state->window, end - copy, copy);
434	n/a	state->wnext = copy;
435	n/a	state->whave = state->wsize;
436	n/a	}
437	n/a	else {
438	n/a	state->wnext += dist;
439	n/a	if (state->wnext == state->wsize) state->wnext = 0;
440	n/a	if (state->whave < state->wsize) state->whave += dist;
441	n/a	}
442	n/a	}
443	n/a	return 0;
444	n/a	}
445	n/a
446	n/a	/* Macros for inflate(): */
447	n/a
448	n/a	/* check function to use adler32() for zlib or crc32() for gzip */
449	n/a	#ifdef GUNZIP
450	n/a	# define UPDATE(check, buf, len) \
451	n/a	(state->flags ? crc32(check, buf, len) : adler32(check, buf, len))
452	n/a	#else
453	n/a	# define UPDATE(check, buf, len) adler32(check, buf, len)
454	n/a	#endif
455	n/a
456	n/a	/* check macros for header crc */
457	n/a	#ifdef GUNZIP
458	n/a	# define CRC2(check, word) \
459	n/a	do { \
460	n/a	hbuf[0] = (unsigned char)(word); \
461	n/a	hbuf[1] = (unsigned char)((word) >> 8); \
462	n/a	check = crc32(check, hbuf, 2); \
463	n/a	} while (0)
464	n/a
465	n/a	# define CRC4(check, word) \
466	n/a	do { \
467	n/a	hbuf[0] = (unsigned char)(word); \
468	n/a	hbuf[1] = (unsigned char)((word) >> 8); \
469	n/a	hbuf[2] = (unsigned char)((word) >> 16); \
470	n/a	hbuf[3] = (unsigned char)((word) >> 24); \
471	n/a	check = crc32(check, hbuf, 4); \
472	n/a	} while (0)
473	n/a	#endif
474	n/a
475	n/a	/* Load registers with state in inflate() for speed */
476	n/a	#define LOAD() \
477	n/a	do { \
478	n/a	put = strm->next_out; \
479	n/a	left = strm->avail_out; \
480	n/a	next = strm->next_in; \
481	n/a	have = strm->avail_in; \
482	n/a	hold = state->hold; \
483	n/a	bits = state->bits; \
484	n/a	} while (0)
485	n/a
486	n/a	/* Restore state from registers in inflate() */
487	n/a	#define RESTORE() \
488	n/a	do { \
489	n/a	strm->next_out = put; \
490	n/a	strm->avail_out = left; \
491	n/a	strm->next_in = next; \
492	n/a	strm->avail_in = have; \
493	n/a	state->hold = hold; \
494	n/a	state->bits = bits; \
495	n/a	} while (0)
496	n/a
497	n/a	/* Clear the input bit accumulator */
498	n/a	#define INITBITS() \
499	n/a	do { \
500	n/a	hold = 0; \
501	n/a	bits = 0; \
502	n/a	} while (0)
503	n/a
504	n/a	/* Get a byte of input into the bit accumulator, or return from inflate()
505	n/a	if there is no input available. */
506	n/a	#define PULLBYTE() \
507	n/a	do { \
508	n/a	if (have == 0) goto inf_leave; \
509	n/a	have--; \
510	n/a	hold += (unsigned long)(*next++) << bits; \
511	n/a	bits += 8; \
512	n/a	} while (0)
513	n/a
514	n/a	/* Assure that there are at least n bits in the bit accumulator. If there is
515	n/a	not enough available input to do that, then return from inflate(). */
516	n/a	#define NEEDBITS(n) \
517	n/a	do { \
518	n/a	while (bits < (unsigned)(n)) \
519	n/a	PULLBYTE(); \
520	n/a	} while (0)
521	n/a
522	n/a	/* Return the low n bits of the bit accumulator (n < 16) */
523	n/a	#define BITS(n) \
524	n/a	((unsigned)hold & ((1U << (n)) - 1))
525	n/a
526	n/a	/* Remove n bits from the bit accumulator */
527	n/a	#define DROPBITS(n) \
528	n/a	do { \
529	n/a	hold >>= (n); \
530	n/a	bits -= (unsigned)(n); \
531	n/a	} while (0)
532	n/a
533	n/a	/* Remove zero to seven bits as needed to go to a byte boundary */
534	n/a	#define BYTEBITS() \
535	n/a	do { \
536	n/a	hold >>= bits & 7; \
537	n/a	bits -= bits & 7; \
538	n/a	} while (0)
539	n/a
540	n/a	/*
541	n/a	inflate() uses a state machine to process as much input data and generate as
542	n/a	much output data as possible before returning. The state machine is
543	n/a	structured roughly as follows:
544	n/a
545	n/a	for (;;) switch (state) {
546	n/a	...
547	n/a	case STATEn:
548	n/a	if (not enough input data or output space to make progress)
549	n/a	return;
550	n/a	... make progress ...
551	n/a	state = STATEm;
552	n/a	break;
553	n/a	...
554	n/a	}
555	n/a
556	n/a	so when inflate() is called again, the same case is attempted again, and
557	n/a	if the appropriate resources are provided, the machine proceeds to the
558	n/a	next state. The NEEDBITS() macro is usually the way the state evaluates
559	n/a	whether it can proceed or should return. NEEDBITS() does the return if
560	n/a	the requested bits are not available. The typical use of the BITS macros
561	n/a	is:
562	n/a
563	n/a	NEEDBITS(n);
564	n/a	... do something with BITS(n) ...
565	n/a	DROPBITS(n);
566	n/a
567	n/a	where NEEDBITS(n) either returns from inflate() if there isn't enough
568	n/a	input left to load n bits into the accumulator, or it continues. BITS(n)
569	n/a	gives the low n bits in the accumulator. When done, DROPBITS(n) drops
570	n/a	the low n bits off the accumulator. INITBITS() clears the accumulator
571	n/a	and sets the number of available bits to zero. BYTEBITS() discards just
572	n/a	enough bits to put the accumulator on a byte boundary. After BYTEBITS()
573	n/a	and a NEEDBITS(8), then BITS(8) would return the next byte in the stream.
574	n/a
575	n/a	NEEDBITS(n) uses PULLBYTE() to get an available byte of input, or to return
576	n/a	if there is no input available. The decoding of variable length codes uses
577	n/a	PULLBYTE() directly in order to pull just enough bytes to decode the next
578	n/a	code, and no more.
579	n/a
580	n/a	Some states loop until they get enough input, making sure that enough
581	n/a	state information is maintained to continue the loop where it left off
582	n/a	if NEEDBITS() returns in the loop. For example, want, need, and keep
583	n/a	would all have to actually be part of the saved state in case NEEDBITS()
584	n/a	returns:
585	n/a
586	n/a	case STATEw:
587	n/a	while (want < need) {
588	n/a	NEEDBITS(n);
589	n/a	keep[want++] = BITS(n);
590	n/a	DROPBITS(n);
591	n/a	}
592	n/a	state = STATEx;
593	n/a	case STATEx:
594	n/a
595	n/a	As shown above, if the next state is also the next case, then the break
596	n/a	is omitted.
597	n/a
598	n/a	A state may also return if there is not enough output space available to
599	n/a	complete that state. Those states are copying stored data, writing a
600	n/a	literal byte, and copying a matching string.
601	n/a
602	n/a	When returning, a "goto inf_leave" is used to update the total counters,
603	n/a	update the check value, and determine whether any progress has been made
604	n/a	during that inflate() call in order to return the proper return code.
605	n/a	Progress is defined as a change in either strm->avail_in or strm->avail_out.
606	n/a	When there is a window, goto inf_leave will update the window with the last
607	n/a	output written. If a goto inf_leave occurs in the middle of decompression
608	n/a	and there is no window currently, goto inf_leave will create one and copy
609	n/a	output to the window for the next call of inflate().
610	n/a
611	n/a	In this implementation, the flush parameter of inflate() only affects the
612	n/a	return code (per zlib.h). inflate() always writes as much as possible to
613	n/a	strm->next_out, given the space available and the provided input--the effect
614	n/a	documented in zlib.h of Z_SYNC_FLUSH. Furthermore, inflate() always defers
615	n/a	the allocation of and copying into a sliding window until necessary, which
616	n/a	provides the effect documented in zlib.h for Z_FINISH when the entire input
617	n/a	stream available. So the only thing the flush parameter actually does is:
618	n/a	when flush is set to Z_FINISH, inflate() cannot return Z_OK. Instead it
619	n/a	will return Z_BUF_ERROR if it has not reached the end of the stream.
620	n/a	*/
621	n/a
622	n/a	int ZEXPORT inflate(strm, flush)
623	n/a	z_streamp strm;
624	n/a	int flush;
625	n/a	{
626	n/a	struct inflate_state FAR *state;
627	n/a	z_const unsigned char FAR next; / next input */
628	n/a	unsigned char FAR put; / next output */
629	n/a	unsigned have, left; /* available input and output */
630	n/a	unsigned long hold; /* bit buffer */
631	n/a	unsigned bits; /* bits in bit buffer */
632	n/a	unsigned in, out; /* save starting available input and output */
633	n/a	unsigned copy; /* number of stored or match bytes to copy */
634	n/a	unsigned char FAR from; / where to copy match bytes from */
635	n/a	code here; /* current decoding table entry */
636	n/a	code last; /* parent table entry */
637	n/a	unsigned len; /* length to copy for repeats, bits to drop */
638	n/a	int ret; /* return code */
639	n/a	#ifdef GUNZIP
640	n/a	unsigned char hbuf[4]; /* buffer for gzip header crc calculation */
641	n/a	#endif
642	n/a	static const unsigned short order[19] = /* permutation of code lengths */
643	n/a	{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
644	n/a
645	n/a	if (inflateStateCheck(strm) \|\| strm->next_out == Z_NULL \|\|
646	n/a	(strm->next_in == Z_NULL && strm->avail_in != 0))
647	n/a	return Z_STREAM_ERROR;
648	n/a
649	n/a	state = (struct inflate_state FAR *)strm->state;
650	n/a	if (state->mode == TYPE) state->mode = TYPEDO; /* skip check */
651	n/a	LOAD();
652	n/a	in = have;
653	n/a	out = left;
654	n/a	ret = Z_OK;
655	n/a	for (;;)
656	n/a	switch (state->mode) {
657	n/a	case HEAD:
658	n/a	if (state->wrap == 0) {
659	n/a	state->mode = TYPEDO;
660	n/a	break;
661	n/a	}
662	n/a	NEEDBITS(16);
663	n/a	#ifdef GUNZIP
664	n/a	if ((state->wrap & 2) && hold == 0x8b1f) { /* gzip header */
665	n/a	if (state->wbits == 0)
666	n/a	state->wbits = 15;
667	n/a	state->check = crc32(0L, Z_NULL, 0);
668	n/a	CRC2(state->check, hold);
669	n/a	INITBITS();
670	n/a	state->mode = FLAGS;
671	n/a	break;
672	n/a	}
673	n/a	state->flags = 0; /* expect zlib header */
674	n/a	if (state->head != Z_NULL)
675	n/a	state->head->done = -1;
676	n/a	if (!(state->wrap & 1) \|\| /* check if zlib header allowed */
677	n/a	#else
678	n/a	if (
679	n/a	#endif
680	n/a	((BITS(8) << 8) + (hold >> 8)) % 31) {
681	n/a	strm->msg = (char *)"incorrect header check";
682	n/a	state->mode = BAD;
683	n/a	break;
684	n/a	}
685	n/a	if (BITS(4) != Z_DEFLATED) {
686	n/a	strm->msg = (char *)"unknown compression method";
687	n/a	state->mode = BAD;
688	n/a	break;
689	n/a	}
690	n/a	DROPBITS(4);
691	n/a	len = BITS(4) + 8;
692	n/a	if (state->wbits == 0)
693	n/a	state->wbits = len;
694	n/a	if (len > 15 \|\| len > state->wbits) {
695	n/a	strm->msg = (char *)"invalid window size";
696	n/a	state->mode = BAD;
697	n/a	break;
698	n/a	}
699	n/a	state->dmax = 1U << len;
700	n/a	Tracev((stderr, "inflate: zlib header ok\n"));
701	n/a	strm->adler = state->check = adler32(0L, Z_NULL, 0);
702	n/a	state->mode = hold & 0x200 ? DICTID : TYPE;
703	n/a	INITBITS();
704	n/a	break;
705	n/a	#ifdef GUNZIP
706	n/a	case FLAGS:
707	n/a	NEEDBITS(16);
708	n/a	state->flags = (int)(hold);
709	n/a	if ((state->flags & 0xff) != Z_DEFLATED) {
710	n/a	strm->msg = (char *)"unknown compression method";
711	n/a	state->mode = BAD;
712	n/a	break;
713	n/a	}
714	n/a	if (state->flags & 0xe000) {
715	n/a	strm->msg = (char *)"unknown header flags set";
716	n/a	state->mode = BAD;
717	n/a	break;
718	n/a	}
719	n/a	if (state->head != Z_NULL)
720	n/a	state->head->text = (int)((hold >> 8) & 1);
721	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
722	n/a	CRC2(state->check, hold);
723	n/a	INITBITS();
724	n/a	state->mode = TIME;
725	n/a	case TIME:
726	n/a	NEEDBITS(32);
727	n/a	if (state->head != Z_NULL)
728	n/a	state->head->time = hold;
729	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
730	n/a	CRC4(state->check, hold);
731	n/a	INITBITS();
732	n/a	state->mode = OS;
733	n/a	case OS:
734	n/a	NEEDBITS(16);
735	n/a	if (state->head != Z_NULL) {
736	n/a	state->head->xflags = (int)(hold & 0xff);
737	n/a	state->head->os = (int)(hold >> 8);
738	n/a	}
739	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
740	n/a	CRC2(state->check, hold);
741	n/a	INITBITS();
742	n/a	state->mode = EXLEN;
743	n/a	case EXLEN:
744	n/a	if (state->flags & 0x0400) {
745	n/a	NEEDBITS(16);
746	n/a	state->length = (unsigned)(hold);
747	n/a	if (state->head != Z_NULL)
748	n/a	state->head->extra_len = (unsigned)hold;
749	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
750	n/a	CRC2(state->check, hold);
751	n/a	INITBITS();
752	n/a	}
753	n/a	else if (state->head != Z_NULL)
754	n/a	state->head->extra = Z_NULL;
755	n/a	state->mode = EXTRA;
756	n/a	case EXTRA:
757	n/a	if (state->flags & 0x0400) {
758	n/a	copy = state->length;
759	n/a	if (copy > have) copy = have;
760	n/a	if (copy) {
761	n/a	if (state->head != Z_NULL &&
762	n/a	state->head->extra != Z_NULL) {
763	n/a	len = state->head->extra_len - state->length;
764	n/a	zmemcpy(state->head->extra + len, next,
765	n/a	len + copy > state->head->extra_max ?
766	n/a	state->head->extra_max - len : copy);
767	n/a	}
768	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
769	n/a	state->check = crc32(state->check, next, copy);
770	n/a	have -= copy;
771	n/a	next += copy;
772	n/a	state->length -= copy;
773	n/a	}
774	n/a	if (state->length) goto inf_leave;
775	n/a	}
776	n/a	state->length = 0;
777	n/a	state->mode = NAME;
778	n/a	case NAME:
779	n/a	if (state->flags & 0x0800) {
780	n/a	if (have == 0) goto inf_leave;
781	n/a	copy = 0;
782	n/a	do {
783	n/a	len = (unsigned)(next[copy++]);
784	n/a	if (state->head != Z_NULL &&
785	n/a	state->head->name != Z_NULL &&
786	n/a	state->length < state->head->name_max)
787	n/a	state->head->name[state->length++] = (Bytef)len;
788	n/a	} while (len && copy < have);
789	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
790	n/a	state->check = crc32(state->check, next, copy);
791	n/a	have -= copy;
792	n/a	next += copy;
793	n/a	if (len) goto inf_leave;
794	n/a	}
795	n/a	else if (state->head != Z_NULL)
796	n/a	state->head->name = Z_NULL;
797	n/a	state->length = 0;
798	n/a	state->mode = COMMENT;
799	n/a	case COMMENT:
800	n/a	if (state->flags & 0x1000) {
801	n/a	if (have == 0) goto inf_leave;
802	n/a	copy = 0;
803	n/a	do {
804	n/a	len = (unsigned)(next[copy++]);
805	n/a	if (state->head != Z_NULL &&
806	n/a	state->head->comment != Z_NULL &&
807	n/a	state->length < state->head->comm_max)
808	n/a	state->head->comment[state->length++] = (Bytef)len;
809	n/a	} while (len && copy < have);
810	n/a	if ((state->flags & 0x0200) && (state->wrap & 4))
811	n/a	state->check = crc32(state->check, next, copy);
812	n/a	have -= copy;
813	n/a	next += copy;
814	n/a	if (len) goto inf_leave;
815	n/a	}
816	n/a	else if (state->head != Z_NULL)
817	n/a	state->head->comment = Z_NULL;
818	n/a	state->mode = HCRC;
819	n/a	case HCRC:
820	n/a	if (state->flags & 0x0200) {
821	n/a	NEEDBITS(16);
822	n/a	if ((state->wrap & 4) && hold != (state->check & 0xffff)) {
823	n/a	strm->msg = (char *)"header crc mismatch";
824	n/a	state->mode = BAD;
825	n/a	break;
826	n/a	}
827	n/a	INITBITS();
828	n/a	}
829	n/a	if (state->head != Z_NULL) {
830	n/a	state->head->hcrc = (int)((state->flags >> 9) & 1);
831	n/a	state->head->done = 1;
832	n/a	}
833	n/a	strm->adler = state->check = crc32(0L, Z_NULL, 0);
834	n/a	state->mode = TYPE;
835	n/a	break;
836	n/a	#endif
837	n/a	case DICTID:
838	n/a	NEEDBITS(32);
839	n/a	strm->adler = state->check = ZSWAP32(hold);
840	n/a	INITBITS();
841	n/a	state->mode = DICT;
842	n/a	case DICT:
843	n/a	if (state->havedict == 0) {
844	n/a	RESTORE();
845	n/a	return Z_NEED_DICT;
846	n/a	}
847	n/a	strm->adler = state->check = adler32(0L, Z_NULL, 0);
848	n/a	state->mode = TYPE;
849	n/a	case TYPE:
850	n/a	if (flush == Z_BLOCK \|\| flush == Z_TREES) goto inf_leave;
851	n/a	case TYPEDO:
852	n/a	if (state->last) {
853	n/a	BYTEBITS();
854	n/a	state->mode = CHECK;
855	n/a	break;
856	n/a	}
857	n/a	NEEDBITS(3);
858	n/a	state->last = BITS(1);
859	n/a	DROPBITS(1);
860	n/a	switch (BITS(2)) {
861	n/a	case 0: /* stored block */
862	n/a	Tracev((stderr, "inflate: stored block%s\n",
863	n/a	state->last ? " (last)" : ""));
864	n/a	state->mode = STORED;
865	n/a	break;
866	n/a	case 1: /* fixed block */
867	n/a	fixedtables(state);
868	n/a	Tracev((stderr, "inflate: fixed codes block%s\n",
869	n/a	state->last ? " (last)" : ""));
870	n/a	state->mode = LEN_; /* decode codes */
871	n/a	if (flush == Z_TREES) {
872	n/a	DROPBITS(2);
873	n/a	goto inf_leave;
874	n/a	}
875	n/a	break;
876	n/a	case 2: /* dynamic block */
877	n/a	Tracev((stderr, "inflate: dynamic codes block%s\n",
878	n/a	state->last ? " (last)" : ""));
879	n/a	state->mode = TABLE;
880	n/a	break;
881	n/a	case 3:
882	n/a	strm->msg = (char *)"invalid block type";
883	n/a	state->mode = BAD;
884	n/a	}
885	n/a	DROPBITS(2);
886	n/a	break;
887	n/a	case STORED:
888	n/a	BYTEBITS(); /* go to byte boundary */
889	n/a	NEEDBITS(32);
890	n/a	if ((hold & 0xffff) != ((hold >> 16) ^ 0xffff)) {
891	n/a	strm->msg = (char *)"invalid stored block lengths";
892	n/a	state->mode = BAD;
893	n/a	break;
894	n/a	}
895	n/a	state->length = (unsigned)hold & 0xffff;
896	n/a	Tracev((stderr, "inflate: stored length %u\n",
897	n/a	state->length));
898	n/a	INITBITS();
899	n/a	state->mode = COPY_;
900	n/a	if (flush == Z_TREES) goto inf_leave;
901	n/a	case COPY_:
902	n/a	state->mode = COPY;
903	n/a	case COPY:
904	n/a	copy = state->length;
905	n/a	if (copy) {
906	n/a	if (copy > have) copy = have;
907	n/a	if (copy > left) copy = left;
908	n/a	if (copy == 0) goto inf_leave;
909	n/a	zmemcpy(put, next, copy);
910	n/a	have -= copy;
911	n/a	next += copy;
912	n/a	left -= copy;
913	n/a	put += copy;
914	n/a	state->length -= copy;
915	n/a	break;
916	n/a	}
917	n/a	Tracev((stderr, "inflate: stored end\n"));
918	n/a	state->mode = TYPE;
919	n/a	break;
920	n/a	case TABLE:
921	n/a	NEEDBITS(14);
922	n/a	state->nlen = BITS(5) + 257;
923	n/a	DROPBITS(5);
924	n/a	state->ndist = BITS(5) + 1;
925	n/a	DROPBITS(5);
926	n/a	state->ncode = BITS(4) + 4;
927	n/a	DROPBITS(4);
928	n/a	#ifndef PKZIP_BUG_WORKAROUND
929	n/a	if (state->nlen > 286 \|\| state->ndist > 30) {
930	n/a	strm->msg = (char *)"too many length or distance symbols";
931	n/a	state->mode = BAD;
932	n/a	break;
933	n/a	}
934	n/a	#endif
935	n/a	Tracev((stderr, "inflate: table sizes ok\n"));
936	n/a	state->have = 0;
937	n/a	state->mode = LENLENS;
938	n/a	case LENLENS:
939	n/a	while (state->have < state->ncode) {
940	n/a	NEEDBITS(3);
941	n/a	state->lens[order[state->have++]] = (unsigned short)BITS(3);
942	n/a	DROPBITS(3);
943	n/a	}
944	n/a	while (state->have < 19)
945	n/a	state->lens[order[state->have++]] = 0;
946	n/a	state->next = state->codes;
947	n/a	state->lencode = (const code FAR *)(state->next);
948	n/a	state->lenbits = 7;
949	n/a	ret = inflate_table(CODES, state->lens, 19, &(state->next),
950	n/a	&(state->lenbits), state->work);
951	n/a	if (ret) {
952	n/a	strm->msg = (char *)"invalid code lengths set";
953	n/a	state->mode = BAD;
954	n/a	break;
955	n/a	}
956	n/a	Tracev((stderr, "inflate: code lengths ok\n"));
957	n/a	state->have = 0;
958	n/a	state->mode = CODELENS;
959	n/a	case CODELENS:
960	n/a	while (state->have < state->nlen + state->ndist) {
961	n/a	for (;;) {
962	n/a	here = state->lencode[BITS(state->lenbits)];
963	n/a	if ((unsigned)(here.bits) <= bits) break;
964	n/a	PULLBYTE();
965	n/a	}
966	n/a	if (here.val < 16) {
967	n/a	DROPBITS(here.bits);
968	n/a	state->lens[state->have++] = here.val;
969	n/a	}
970	n/a	else {
971	n/a	if (here.val == 16) {
972	n/a	NEEDBITS(here.bits + 2);
973	n/a	DROPBITS(here.bits);
974	n/a	if (state->have == 0) {
975	n/a	strm->msg = (char *)"invalid bit length repeat";
976	n/a	state->mode = BAD;
977	n/a	break;
978	n/a	}
979	n/a	len = state->lens[state->have - 1];
980	n/a	copy = 3 + BITS(2);
981	n/a	DROPBITS(2);
982	n/a	}
983	n/a	else if (here.val == 17) {
984	n/a	NEEDBITS(here.bits + 3);
985	n/a	DROPBITS(here.bits);
986	n/a	len = 0;
987	n/a	copy = 3 + BITS(3);
988	n/a	DROPBITS(3);
989	n/a	}
990	n/a	else {
991	n/a	NEEDBITS(here.bits + 7);
992	n/a	DROPBITS(here.bits);
993	n/a	len = 0;
994	n/a	copy = 11 + BITS(7);
995	n/a	DROPBITS(7);
996	n/a	}
997	n/a	if (state->have + copy > state->nlen + state->ndist) {
998	n/a	strm->msg = (char *)"invalid bit length repeat";
999	n/a	state->mode = BAD;
1000	n/a	break;
1001	n/a	}
1002	n/a	while (copy--)
1003	n/a	state->lens[state->have++] = (unsigned short)len;
1004	n/a	}
1005	n/a	}
1006	n/a
1007	n/a	/* handle error breaks in while */
1008	n/a	if (state->mode == BAD) break;
1009	n/a
1010	n/a	/* check for end-of-block code (better have one) */
1011	n/a	if (state->lens[256] == 0) {
1012	n/a	strm->msg = (char *)"invalid code -- missing end-of-block";
1013	n/a	state->mode = BAD;
1014	n/a	break;
1015	n/a	}
1016	n/a
1017	n/a	/* build code tables -- note: do not change the lenbits or distbits
1018	n/a	values here (9 and 6) without reading the comments in inftrees.h
1019	n/a	concerning the ENOUGH constants, which depend on those values */
1020	n/a	state->next = state->codes;
1021	n/a	state->lencode = (const code FAR *)(state->next);
1022	n/a	state->lenbits = 9;
1023	n/a	ret = inflate_table(LENS, state->lens, state->nlen, &(state->next),
1024	n/a	&(state->lenbits), state->work);
1025	n/a	if (ret) {
1026	n/a	strm->msg = (char *)"invalid literal/lengths set";
1027	n/a	state->mode = BAD;
1028	n/a	break;
1029	n/a	}
1030	n/a	state->distcode = (const code FAR *)(state->next);
1031	n/a	state->distbits = 6;
1032	n/a	ret = inflate_table(DISTS, state->lens + state->nlen, state->ndist,
1033	n/a	&(state->next), &(state->distbits), state->work);
1034	n/a	if (ret) {
1035	n/a	strm->msg = (char *)"invalid distances set";
1036	n/a	state->mode = BAD;
1037	n/a	break;
1038	n/a	}
1039	n/a	Tracev((stderr, "inflate: codes ok\n"));
1040	n/a	state->mode = LEN_;
1041	n/a	if (flush == Z_TREES) goto inf_leave;
1042	n/a	case LEN_:
1043	n/a	state->mode = LEN;
1044	n/a	case LEN:
1045	n/a	if (have >= 6 && left >= 258) {
1046	n/a	RESTORE();
1047	n/a	inflate_fast(strm, out);
1048	n/a	LOAD();
1049	n/a	if (state->mode == TYPE)
1050	n/a	state->back = -1;
1051	n/a	break;
1052	n/a	}
1053	n/a	state->back = 0;
1054	n/a	for (;;) {
1055	n/a	here = state->lencode[BITS(state->lenbits)];
1056	n/a	if ((unsigned)(here.bits) <= bits) break;
1057	n/a	PULLBYTE();
1058	n/a	}
1059	n/a	if (here.op && (here.op & 0xf0) == 0) {
1060	n/a	last = here;
1061	n/a	for (;;) {
1062	n/a	here = state->lencode[last.val +
1063	n/a	(BITS(last.bits + last.op) >> last.bits)];
1064	n/a	if ((unsigned)(last.bits + here.bits) <= bits) break;
1065	n/a	PULLBYTE();
1066	n/a	}
1067	n/a	DROPBITS(last.bits);
1068	n/a	state->back += last.bits;
1069	n/a	}
1070	n/a	DROPBITS(here.bits);
1071	n/a	state->back += here.bits;
1072	n/a	state->length = (unsigned)here.val;
1073	n/a	if ((int)(here.op) == 0) {
1074	n/a	Tracevv((stderr, here.val >= 0x20 && here.val < 0x7f ?
1075	n/a	"inflate: literal '%c'\n" :
1076	n/a	"inflate: literal 0x%02x\n", here.val));
1077	n/a	state->mode = LIT;
1078	n/a	break;
1079	n/a	}
1080	n/a	if (here.op & 32) {
1081	n/a	Tracevv((stderr, "inflate: end of block\n"));
1082	n/a	state->back = -1;
1083	n/a	state->mode = TYPE;
1084	n/a	break;
1085	n/a	}
1086	n/a	if (here.op & 64) {
1087	n/a	strm->msg = (char *)"invalid literal/length code";
1088	n/a	state->mode = BAD;
1089	n/a	break;
1090	n/a	}
1091	n/a	state->extra = (unsigned)(here.op) & 15;
1092	n/a	state->mode = LENEXT;
1093	n/a	case LENEXT:
1094	n/a	if (state->extra) {
1095	n/a	NEEDBITS(state->extra);
1096	n/a	state->length += BITS(state->extra);
1097	n/a	DROPBITS(state->extra);
1098	n/a	state->back += state->extra;
1099	n/a	}
1100	n/a	Tracevv((stderr, "inflate: length %u\n", state->length));
1101	n/a	state->was = state->length;
1102	n/a	state->mode = DIST;
1103	n/a	case DIST:
1104	n/a	for (;;) {
1105	n/a	here = state->distcode[BITS(state->distbits)];
1106	n/a	if ((unsigned)(here.bits) <= bits) break;
1107	n/a	PULLBYTE();
1108	n/a	}
1109	n/a	if ((here.op & 0xf0) == 0) {
1110	n/a	last = here;
1111	n/a	for (;;) {
1112	n/a	here = state->distcode[last.val +
1113	n/a	(BITS(last.bits + last.op) >> last.bits)];
1114	n/a	if ((unsigned)(last.bits + here.bits) <= bits) break;
1115	n/a	PULLBYTE();
1116	n/a	}
1117	n/a	DROPBITS(last.bits);
1118	n/a	state->back += last.bits;
1119	n/a	}
1120	n/a	DROPBITS(here.bits);
1121	n/a	state->back += here.bits;
1122	n/a	if (here.op & 64) {
1123	n/a	strm->msg = (char *)"invalid distance code";
1124	n/a	state->mode = BAD;
1125	n/a	break;
1126	n/a	}
1127	n/a	state->offset = (unsigned)here.val;
1128	n/a	state->extra = (unsigned)(here.op) & 15;
1129	n/a	state->mode = DISTEXT;
1130	n/a	case DISTEXT:
1131	n/a	if (state->extra) {
1132	n/a	NEEDBITS(state->extra);
1133	n/a	state->offset += BITS(state->extra);
1134	n/a	DROPBITS(state->extra);
1135	n/a	state->back += state->extra;
1136	n/a	}
1137	n/a	#ifdef INFLATE_STRICT
1138	n/a	if (state->offset > state->dmax) {
1139	n/a	strm->msg = (char *)"invalid distance too far back";
1140	n/a	state->mode = BAD;
1141	n/a	break;
1142	n/a	}
1143	n/a	#endif
1144	n/a	Tracevv((stderr, "inflate: distance %u\n", state->offset));
1145	n/a	state->mode = MATCH;
1146	n/a	case MATCH:
1147	n/a	if (left == 0) goto inf_leave;
1148	n/a	copy = out - left;
1149	n/a	if (state->offset > copy) { /* copy from window */
1150	n/a	copy = state->offset - copy;
1151	n/a	if (copy > state->whave) {
1152	n/a	if (state->sane) {
1153	n/a	strm->msg = (char *)"invalid distance too far back";
1154	n/a	state->mode = BAD;
1155	n/a	break;
1156	n/a	}
1157	n/a	#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1158	n/a	Trace((stderr, "inflate.c too far\n"));
1159	n/a	copy -= state->whave;
1160	n/a	if (copy > state->length) copy = state->length;
1161	n/a	if (copy > left) copy = left;
1162	n/a	left -= copy;
1163	n/a	state->length -= copy;
1164	n/a	do {
1165	n/a	*put++ = 0;
1166	n/a	} while (--copy);
1167	n/a	if (state->length == 0) state->mode = LEN;
1168	n/a	break;
1169	n/a	#endif
1170	n/a	}
1171	n/a	if (copy > state->wnext) {
1172	n/a	copy -= state->wnext;
1173	n/a	from = state->window + (state->wsize - copy);
1174	n/a	}
1175	n/a	else
1176	n/a	from = state->window + (state->wnext - copy);
1177	n/a	if (copy > state->length) copy = state->length;
1178	n/a	}
1179	n/a	else { /* copy from output */
1180	n/a	from = put - state->offset;
1181	n/a	copy = state->length;
1182	n/a	}
1183	n/a	if (copy > left) copy = left;
1184	n/a	left -= copy;
1185	n/a	state->length -= copy;
1186	n/a	do {
1187	n/a	put++ = from++;
1188	n/a	} while (--copy);
1189	n/a	if (state->length == 0) state->mode = LEN;
1190	n/a	break;
1191	n/a	case LIT:
1192	n/a	if (left == 0) goto inf_leave;
1193	n/a	*put++ = (unsigned char)(state->length);
1194	n/a	left--;
1195	n/a	state->mode = LEN;
1196	n/a	break;
1197	n/a	case CHECK:
1198	n/a	if (state->wrap) {
1199	n/a	NEEDBITS(32);
1200	n/a	out -= left;
1201	n/a	strm->total_out += out;
1202	n/a	state->total += out;
1203	n/a	if ((state->wrap & 4) && out)
1204	n/a	strm->adler = state->check =
1205	n/a	UPDATE(state->check, put - out, out);
1206	n/a	out = left;
1207	n/a	if ((state->wrap & 4) && (
1208	n/a	#ifdef GUNZIP
1209	n/a	state->flags ? hold :
1210	n/a	#endif
1211	n/a	ZSWAP32(hold)) != state->check) {
1212	n/a	strm->msg = (char *)"incorrect data check";
1213	n/a	state->mode = BAD;
1214	n/a	break;
1215	n/a	}
1216	n/a	INITBITS();
1217	n/a	Tracev((stderr, "inflate: check matches trailer\n"));
1218	n/a	}
1219	n/a	#ifdef GUNZIP
1220	n/a	state->mode = LENGTH;
1221	n/a	case LENGTH:
1222	n/a	if (state->wrap && state->flags) {
1223	n/a	NEEDBITS(32);
1224	n/a	if (hold != (state->total & 0xffffffffUL)) {
1225	n/a	strm->msg = (char *)"incorrect length check";
1226	n/a	state->mode = BAD;
1227	n/a	break;
1228	n/a	}
1229	n/a	INITBITS();
1230	n/a	Tracev((stderr, "inflate: length matches trailer\n"));
1231	n/a	}
1232	n/a	#endif
1233	n/a	state->mode = DONE;
1234	n/a	case DONE:
1235	n/a	ret = Z_STREAM_END;
1236	n/a	goto inf_leave;
1237	n/a	case BAD:
1238	n/a	ret = Z_DATA_ERROR;
1239	n/a	goto inf_leave;
1240	n/a	case MEM:
1241	n/a	return Z_MEM_ERROR;
1242	n/a	case SYNC:
1243	n/a	default:
1244	n/a	return Z_STREAM_ERROR;
1245	n/a	}
1246	n/a
1247	n/a	/*
1248	n/a	Return from inflate(), updating the total counts and the check value.
1249	n/a	If there was no progress during the inflate() call, return a buffer
1250	n/a	error. Call updatewindow() to create and/or update the window state.
1251	n/a	Note: a memory error from inflate() is non-recoverable.
1252	n/a	*/
1253	n/a	inf_leave:
1254	n/a	RESTORE();
1255	n/a	if (state->wsize \|\| (out != strm->avail_out && state->mode < BAD &&
1256	n/a	(state->mode < CHECK \|\| flush != Z_FINISH)))
1257	n/a	if (updatewindow(strm, strm->next_out, out - strm->avail_out)) {
1258	n/a	state->mode = MEM;
1259	n/a	return Z_MEM_ERROR;
1260	n/a	}
1261	n/a	in -= strm->avail_in;
1262	n/a	out -= strm->avail_out;
1263	n/a	strm->total_in += in;
1264	n/a	strm->total_out += out;
1265	n/a	state->total += out;
1266	n/a	if ((state->wrap & 4) && out)
1267	n/a	strm->adler = state->check =
1268	n/a	UPDATE(state->check, strm->next_out - out, out);
1269	n/a	strm->data_type = (int)state->bits + (state->last ? 64 : 0) +
1270	n/a	(state->mode == TYPE ? 128 : 0) +
1271	n/a	(state->mode == LEN_ \|\| state->mode == COPY_ ? 256 : 0);
1272	n/a	if (((in == 0 && out == 0) \|\| flush == Z_FINISH) && ret == Z_OK)
1273	n/a	ret = Z_BUF_ERROR;
1274	n/a	return ret;
1275	n/a	}
1276	n/a
1277	n/a	int ZEXPORT inflateEnd(strm)
1278	n/a	z_streamp strm;
1279	n/a	{
1280	n/a	struct inflate_state FAR *state;
1281	n/a	if (inflateStateCheck(strm))
1282	n/a	return Z_STREAM_ERROR;
1283	n/a	state = (struct inflate_state FAR *)strm->state;
1284	n/a	if (state->window != Z_NULL) ZFREE(strm, state->window);
1285	n/a	ZFREE(strm, strm->state);
1286	n/a	strm->state = Z_NULL;
1287	n/a	Tracev((stderr, "inflate: end\n"));
1288	n/a	return Z_OK;
1289	n/a	}
1290	n/a
1291	n/a	int ZEXPORT inflateGetDictionary(strm, dictionary, dictLength)
1292	n/a	z_streamp strm;
1293	n/a	Bytef *dictionary;
1294	n/a	uInt *dictLength;
1295	n/a	{
1296	n/a	struct inflate_state FAR *state;
1297	n/a
1298	n/a	/* check state */
1299	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1300	n/a	state = (struct inflate_state FAR *)strm->state;
1301	n/a
1302	n/a	/* copy dictionary */
1303	n/a	if (state->whave && dictionary != Z_NULL) {
1304	n/a	zmemcpy(dictionary, state->window + state->wnext,
1305	n/a	state->whave - state->wnext);
1306	n/a	zmemcpy(dictionary + state->whave - state->wnext,
1307	n/a	state->window, state->wnext);
1308	n/a	}
1309	n/a	if (dictLength != Z_NULL)
1310	n/a	*dictLength = state->whave;
1311	n/a	return Z_OK;
1312	n/a	}
1313	n/a
1314	n/a	int ZEXPORT inflateSetDictionary(strm, dictionary, dictLength)
1315	n/a	z_streamp strm;
1316	n/a	const Bytef *dictionary;
1317	n/a	uInt dictLength;
1318	n/a	{
1319	n/a	struct inflate_state FAR *state;
1320	n/a	unsigned long dictid;
1321	n/a	int ret;
1322	n/a
1323	n/a	/* check state */
1324	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1325	n/a	state = (struct inflate_state FAR *)strm->state;
1326	n/a	if (state->wrap != 0 && state->mode != DICT)
1327	n/a	return Z_STREAM_ERROR;
1328	n/a
1329	n/a	/* check for correct dictionary identifier */
1330	n/a	if (state->mode == DICT) {
1331	n/a	dictid = adler32(0L, Z_NULL, 0);
1332	n/a	dictid = adler32(dictid, dictionary, dictLength);
1333	n/a	if (dictid != state->check)
1334	n/a	return Z_DATA_ERROR;
1335	n/a	}
1336	n/a
1337	n/a	/* copy dictionary to window using updatewindow(), which will amend the
1338	n/a	existing dictionary if appropriate */
1339	n/a	ret = updatewindow(strm, dictionary + dictLength, dictLength);
1340	n/a	if (ret) {
1341	n/a	state->mode = MEM;
1342	n/a	return Z_MEM_ERROR;
1343	n/a	}
1344	n/a	state->havedict = 1;
1345	n/a	Tracev((stderr, "inflate: dictionary set\n"));
1346	n/a	return Z_OK;
1347	n/a	}
1348	n/a
1349	n/a	int ZEXPORT inflateGetHeader(strm, head)
1350	n/a	z_streamp strm;
1351	n/a	gz_headerp head;
1352	n/a	{
1353	n/a	struct inflate_state FAR *state;
1354	n/a
1355	n/a	/* check state */
1356	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1357	n/a	state = (struct inflate_state FAR *)strm->state;
1358	n/a	if ((state->wrap & 2) == 0) return Z_STREAM_ERROR;
1359	n/a
1360	n/a	/* save header structure */
1361	n/a	state->head = head;
1362	n/a	head->done = 0;
1363	n/a	return Z_OK;
1364	n/a	}
1365	n/a
1366	n/a	/*
1367	n/a	Search buf[0..len-1] for the pattern: 0, 0, 0xff, 0xff. Return when found
1368	n/a	or when out of input. When called, *have is the number of pattern bytes
1369	n/a	found in order so far, in 0..3. On return *have is updated to the new
1370	n/a	state. If on return *have equals four, then the pattern was found and the
1371	n/a	return value is how many bytes were read including the last byte of the
1372	n/a	pattern. If *have is less than four, then the pattern has not been found
1373	n/a	yet and the return value is len. In the latter case, syncsearch() can be
1374	n/a	called again with more data and the have state. have is initialized to
1375	n/a	zero for the first call.
1376	n/a	*/
1377	n/a	local unsigned syncsearch(have, buf, len)
1378	n/a	unsigned FAR *have;
1379	n/a	const unsigned char FAR *buf;
1380	n/a	unsigned len;
1381	n/a	{
1382	n/a	unsigned got;
1383	n/a	unsigned next;
1384	n/a
1385	n/a	got = *have;
1386	n/a	next = 0;
1387	n/a	while (next < len && got < 4) {
1388	n/a	if ((int)(buf[next]) == (got < 2 ? 0 : 0xff))
1389	n/a	got++;
1390	n/a	else if (buf[next])
1391	n/a	got = 0;
1392	n/a	else
1393	n/a	got = 4 - got;
1394	n/a	next++;
1395	n/a	}
1396	n/a	*have = got;
1397	n/a	return next;
1398	n/a	}
1399	n/a
1400	n/a	int ZEXPORT inflateSync(strm)
1401	n/a	z_streamp strm;
1402	n/a	{
1403	n/a	unsigned len; /* number of bytes to look at or looked at */
1404	n/a	unsigned long in, out; /* temporary to save total_in and total_out */
1405	n/a	unsigned char buf[4]; /* to restore bit buffer to byte string */
1406	n/a	struct inflate_state FAR *state;
1407	n/a
1408	n/a	/* check parameters */
1409	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1410	n/a	state = (struct inflate_state FAR *)strm->state;
1411	n/a	if (strm->avail_in == 0 && state->bits < 8) return Z_BUF_ERROR;
1412	n/a
1413	n/a	/* if first time, start search in bit buffer */
1414	n/a	if (state->mode != SYNC) {
1415	n/a	state->mode = SYNC;
1416	n/a	state->hold <<= state->bits & 7;
1417	n/a	state->bits -= state->bits & 7;
1418	n/a	len = 0;
1419	n/a	while (state->bits >= 8) {
1420	n/a	buf[len++] = (unsigned char)(state->hold);
1421	n/a	state->hold >>= 8;
1422	n/a	state->bits -= 8;
1423	n/a	}
1424	n/a	state->have = 0;
1425	n/a	syncsearch(&(state->have), buf, len);
1426	n/a	}
1427	n/a
1428	n/a	/* search available input */
1429	n/a	len = syncsearch(&(state->have), strm->next_in, strm->avail_in);
1430	n/a	strm->avail_in -= len;
1431	n/a	strm->next_in += len;
1432	n/a	strm->total_in += len;
1433	n/a
1434	n/a	/* return no joy or set up to restart inflate() on a new block */
1435	n/a	if (state->have != 4) return Z_DATA_ERROR;
1436	n/a	in = strm->total_in; out = strm->total_out;
1437	n/a	inflateReset(strm);
1438	n/a	strm->total_in = in; strm->total_out = out;
1439	n/a	state->mode = TYPE;
1440	n/a	return Z_OK;
1441	n/a	}
1442	n/a
1443	n/a	/*
1444	n/a	Returns true if inflate is currently at the end of a block generated by
1445	n/a	Z_SYNC_FLUSH or Z_FULL_FLUSH. This function is used by one PPP
1446	n/a	implementation to provide an additional safety check. PPP uses
1447	n/a	Z_SYNC_FLUSH but removes the length bytes of the resulting empty stored
1448	n/a	block. When decompressing, PPP checks that at the end of input packet,
1449	n/a	inflate is waiting for these length bytes.
1450	n/a	*/
1451	n/a	int ZEXPORT inflateSyncPoint(strm)
1452	n/a	z_streamp strm;
1453	n/a	{
1454	n/a	struct inflate_state FAR *state;
1455	n/a
1456	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1457	n/a	state = (struct inflate_state FAR *)strm->state;
1458	n/a	return state->mode == STORED && state->bits == 0;
1459	n/a	}
1460	n/a
1461	n/a	int ZEXPORT inflateCopy(dest, source)
1462	n/a	z_streamp dest;
1463	n/a	z_streamp source;
1464	n/a	{
1465	n/a	struct inflate_state FAR *state;
1466	n/a	struct inflate_state FAR *copy;
1467	n/a	unsigned char FAR *window;
1468	n/a	unsigned wsize;
1469	n/a
1470	n/a	/* check input */
1471	n/a	if (inflateStateCheck(source) \|\| dest == Z_NULL)
1472	n/a	return Z_STREAM_ERROR;
1473	n/a	state = (struct inflate_state FAR *)source->state;
1474	n/a
1475	n/a	/* allocate space */
1476	n/a	copy = (struct inflate_state FAR *)
1477	n/a	ZALLOC(source, 1, sizeof(struct inflate_state));
1478	n/a	if (copy == Z_NULL) return Z_MEM_ERROR;
1479	n/a	window = Z_NULL;
1480	n/a	if (state->window != Z_NULL) {
1481	n/a	window = (unsigned char FAR *)
1482	n/a	ZALLOC(source, 1U << state->wbits, sizeof(unsigned char));
1483	n/a	if (window == Z_NULL) {
1484	n/a	ZFREE(source, copy);
1485	n/a	return Z_MEM_ERROR;
1486	n/a	}
1487	n/a	}
1488	n/a
1489	n/a	/* copy state */
1490	n/a	zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1491	n/a	zmemcpy((voidpf)copy, (voidpf)state, sizeof(struct inflate_state));
1492	n/a	copy->strm = dest;
1493	n/a	if (state->lencode >= state->codes &&
1494	n/a	state->lencode <= state->codes + ENOUGH - 1) {
1495	n/a	copy->lencode = copy->codes + (state->lencode - state->codes);
1496	n/a	copy->distcode = copy->codes + (state->distcode - state->codes);
1497	n/a	}
1498	n/a	copy->next = copy->codes + (state->next - state->codes);
1499	n/a	if (window != Z_NULL) {
1500	n/a	wsize = 1U << state->wbits;
1501	n/a	zmemcpy(window, state->window, wsize);
1502	n/a	}
1503	n/a	copy->window = window;
1504	n/a	dest->state = (struct internal_state FAR *)copy;
1505	n/a	return Z_OK;
1506	n/a	}
1507	n/a
1508	n/a	int ZEXPORT inflateUndermine(strm, subvert)
1509	n/a	z_streamp strm;
1510	n/a	int subvert;
1511	n/a	{
1512	n/a	struct inflate_state FAR *state;
1513	n/a
1514	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1515	n/a	state = (struct inflate_state FAR *)strm->state;
1516	n/a	#ifdef INFLATE_ALLOW_INVALID_DISTANCE_TOOFAR_ARRR
1517	n/a	state->sane = !subvert;
1518	n/a	return Z_OK;
1519	n/a	#else
1520	n/a	(void)subvert;
1521	n/a	state->sane = 1;
1522	n/a	return Z_DATA_ERROR;
1523	n/a	#endif
1524	n/a	}
1525	n/a
1526	n/a	int ZEXPORT inflateValidate(strm, check)
1527	n/a	z_streamp strm;
1528	n/a	int check;
1529	n/a	{
1530	n/a	struct inflate_state FAR *state;
1531	n/a
1532	n/a	if (inflateStateCheck(strm)) return Z_STREAM_ERROR;
1533	n/a	state = (struct inflate_state FAR *)strm->state;
1534	n/a	if (check)
1535	n/a	state->wrap \|= 4;
1536	n/a	else
1537	n/a	state->wrap &= ~4;
1538	n/a	return Z_OK;
1539	n/a	}
1540	n/a
1541	n/a	long ZEXPORT inflateMark(strm)
1542	n/a	z_streamp strm;
1543	n/a	{
1544	n/a	struct inflate_state FAR *state;
1545	n/a
1546	n/a	if (inflateStateCheck(strm))
1547	n/a	return -(1L << 16);
1548	n/a	state = (struct inflate_state FAR *)strm->state;
1549	n/a	return (long)(((unsigned long)((long)state->back)) << 16) +
1550	n/a	(state->mode == COPY ? state->length :
1551	n/a	(state->mode == MATCH ? state->was - state->length : 0));
1552	n/a	}
1553	n/a
1554	n/a	unsigned long ZEXPORT inflateCodesUsed(strm)
1555	n/a	z_streamp strm;
1556	n/a	{
1557	n/a	struct inflate_state FAR *state;
1558	n/a	if (inflateStateCheck(strm)) return (unsigned long)-1;
1559	n/a	state = (struct inflate_state FAR *)strm->state;
1560	n/a	return (unsigned long)(state->next - state->codes);
1561	n/a	}