Python code coverage for Modules/zlib/deflate.c

#	count	content
1	n/a	/* deflate.c -- compress data using the deflation algorithm
2	n/a	* Copyright (C) 1995-2017 Jean-loup Gailly and 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	* ALGORITHM
8	n/a	*
9	n/a	* The "deflation" process depends on being able to identify portions
10	n/a	* of the input text which are identical to earlier input (within a
11	n/a	* sliding window trailing behind the input currently being processed).
12	n/a	*
13	n/a	* The most straightforward technique turns out to be the fastest for
14	n/a	* most input files: try all possible matches and select the longest.
15	n/a	* The key feature of this algorithm is that insertions into the string
16	n/a	* dictionary are very simple and thus fast, and deletions are avoided
17	n/a	* completely. Insertions are performed at each input character, whereas
18	n/a	* string matches are performed only when the previous match ends. So it
19	n/a	* is preferable to spend more time in matches to allow very fast string
20	n/a	* insertions and avoid deletions. The matching algorithm for small
21	n/a	* strings is inspired from that of Rabin & Karp. A brute force approach
22	n/a	* is used to find longer strings when a small match has been found.
23	n/a	* A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
24	n/a	* (by Leonid Broukhis).
25	n/a	* A previous version of this file used a more sophisticated algorithm
26	n/a	* (by Fiala and Greene) which is guaranteed to run in linear amortized
27	n/a	* time, but has a larger average cost, uses more memory and is patented.
28	n/a	* However the F&G algorithm may be faster for some highly redundant
29	n/a	* files if the parameter max_chain_length (described below) is too large.
30	n/a	*
31	n/a	* ACKNOWLEDGEMENTS
32	n/a	*
33	n/a	* The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
34	n/a	* I found it in 'freeze' written by Leonid Broukhis.
35	n/a	* Thanks to many people for bug reports and testing.
36	n/a	*
37	n/a	* REFERENCES
38	n/a	*
39	n/a	* Deutsch, L.P.,"DEFLATE Compressed Data Format Specification".
40	n/a	* Available in http://tools.ietf.org/html/rfc1951
41	n/a	*
42	n/a	* A description of the Rabin and Karp algorithm is given in the book
43	n/a	* "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
44	n/a	*
45	n/a	* Fiala,E.R., and Greene,D.H.
46	n/a	* Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
47	n/a	*
48	n/a	*/
49	n/a
50	n/a	/* @(#) $Id$ */
51	n/a
52	n/a	#include "deflate.h"
53	n/a
54	n/a	const char deflate_copyright[] =
55	n/a	" deflate 1.2.11 Copyright 1995-2017 Jean-loup Gailly and Mark Adler ";
56	n/a	/*
57	n/a	If you use the zlib library in a product, an acknowledgment is welcome
58	n/a	in the documentation of your product. If for some reason you cannot
59	n/a	include such an acknowledgment, I would appreciate that you keep this
60	n/a	copyright string in the executable of your product.
61	n/a	*/
62	n/a
63	n/a	/* ===========================================================================
64	n/a	* Function prototypes.
65	n/a	*/
66	n/a	typedef enum {
67	n/a	need_more, /* block not completed, need more input or more output */
68	n/a	block_done, /* block flush performed */
69	n/a	finish_started, /* finish started, need only more output at next deflate */
70	n/a	finish_done /* finish done, accept no more input or output */
71	n/a	} block_state;
72	n/a
73	n/a	typedef block_state (compress_func) OF((deflate_state s, int flush));
74	n/a	/* Compression function. Returns the block state after the call. */
75	n/a
76	n/a	local int deflateStateCheck OF((z_streamp strm));
77	n/a	local void slide_hash OF((deflate_state *s));
78	n/a	local void fill_window OF((deflate_state *s));
79	n/a	local block_state deflate_stored OF((deflate_state *s, int flush));
80	n/a	local block_state deflate_fast OF((deflate_state *s, int flush));
81	n/a	#ifndef FASTEST
82	n/a	local block_state deflate_slow OF((deflate_state *s, int flush));
83	n/a	#endif
84	n/a	local block_state deflate_rle OF((deflate_state *s, int flush));
85	n/a	local block_state deflate_huff OF((deflate_state *s, int flush));
86	n/a	local void lm_init OF((deflate_state *s));
87	n/a	local void putShortMSB OF((deflate_state *s, uInt b));
88	n/a	local void flush_pending OF((z_streamp strm));
89	n/a	local unsigned read_buf OF((z_streamp strm, Bytef *buf, unsigned size));
90	n/a	#ifdef ASMV
91	n/a	# pragma message("Assembler code may have bugs -- use at your own risk")
92	n/a	void match_init OF((void)); /* asm code initialization */
93	n/a	uInt longest_match OF((deflate_state *s, IPos cur_match));
94	n/a	#else
95	n/a	local uInt longest_match OF((deflate_state *s, IPos cur_match));
96	n/a	#endif
97	n/a
98	n/a	#ifdef ZLIB_DEBUG
99	n/a	local void check_match OF((deflate_state *s, IPos start, IPos match,
100	n/a	int length));
101	n/a	#endif
102	n/a
103	n/a	/* ===========================================================================
104	n/a	* Local data
105	n/a	*/
106	n/a
107	n/a	#define NIL 0
108	n/a	/* Tail of hash chains */
109	n/a
110	n/a	#ifndef TOO_FAR
111	n/a	# define TOO_FAR 4096
112	n/a	#endif
113	n/a	/* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
114	n/a
115	n/a	/* Values for max_lazy_match, good_match and max_chain_length, depending on
116	n/a	* the desired pack level (0..9). The values given below have been tuned to
117	n/a	* exclude worst case performance for pathological files. Better values may be
118	n/a	* found for specific files.
119	n/a	*/
120	n/a	typedef struct config_s {
121	n/a	ush good_length; /* reduce lazy search above this match length */
122	n/a	ush max_lazy; /* do not perform lazy search above this match length */
123	n/a	ush nice_length; /* quit search above this match length */
124	n/a	ush max_chain;
125	n/a	compress_func func;
126	n/a	} config;
127	n/a
128	n/a	#ifdef FASTEST
129	n/a	local const config configuration_table[2] = {
130	n/a	/* good lazy nice chain */
131	n/a	/* 0 / {0, 0, 0, 0, deflate_stored}, / store only */
132	n/a	/* 1 / {4, 4, 8, 4, deflate_fast}}; / max speed, no lazy matches */
133	n/a	#else
134	n/a	local const config configuration_table[10] = {
135	n/a	/* good lazy nice chain */
136	n/a	/* 0 / {0, 0, 0, 0, deflate_stored}, / store only */
137	n/a	/* 1 / {4, 4, 8, 4, deflate_fast}, / max speed, no lazy matches */
138	n/a	/* 2 */ {4, 5, 16, 8, deflate_fast},
139	n/a	/* 3 */ {4, 6, 32, 32, deflate_fast},
140	n/a
141	n/a	/* 4 / {4, 4, 16, 16, deflate_slow}, / lazy matches */
142	n/a	/* 5 */ {8, 16, 32, 32, deflate_slow},
143	n/a	/* 6 */ {8, 16, 128, 128, deflate_slow},
144	n/a	/* 7 */ {8, 32, 128, 256, deflate_slow},
145	n/a	/* 8 */ {32, 128, 258, 1024, deflate_slow},
146	n/a	/* 9 / {32, 258, 258, 4096, deflate_slow}}; / max compression */
147	n/a	#endif
148	n/a
149	n/a	/* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
150	n/a	* For deflate_fast() (levels <= 3) good is ignored and lazy has a different
151	n/a	* meaning.
152	n/a	*/
153	n/a
154	n/a	/* rank Z_BLOCK between Z_NO_FLUSH and Z_PARTIAL_FLUSH */
155	n/a	#define RANK(f) (((f) * 2) - ((f) > 4 ? 9 : 0))
156	n/a
157	n/a	/* ===========================================================================
158	n/a	* Update a hash value with the given input byte
159	n/a	* IN assertion: all calls to UPDATE_HASH are made with consecutive input
160	n/a	* characters, so that a running hash key can be computed from the previous
161	n/a	* key instead of complete recalculation each time.
162	n/a	*/
163	n/a	#define UPDATE_HASH(s,h,c) (h = (((h)<<s->hash_shift) ^ (c)) & s->hash_mask)
164	n/a
165	n/a
166	n/a	/* ===========================================================================
167	n/a	* Insert string str in the dictionary and set match_head to the previous head
168	n/a	* of the hash chain (the most recent string with same hash key). Return
169	n/a	* the previous length of the hash chain.
170	n/a	* If this file is compiled with -DFASTEST, the compression level is forced
171	n/a	* to 1, and no hash chains are maintained.
172	n/a	* IN assertion: all calls to INSERT_STRING are made with consecutive input
173	n/a	* characters and the first MIN_MATCH bytes of str are valid (except for
174	n/a	* the last MIN_MATCH-1 bytes of the input file).
175	n/a	*/
176	n/a	#ifdef FASTEST
177	n/a	#define INSERT_STRING(s, str, match_head) \
178	n/a	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
179	n/a	match_head = s->head[s->ins_h], \
180	n/a	s->head[s->ins_h] = (Pos)(str))
181	n/a	#else
182	n/a	#define INSERT_STRING(s, str, match_head) \
183	n/a	(UPDATE_HASH(s, s->ins_h, s->window[(str) + (MIN_MATCH-1)]), \
184	n/a	match_head = s->prev[(str) & s->w_mask] = s->head[s->ins_h], \
185	n/a	s->head[s->ins_h] = (Pos)(str))
186	n/a	#endif
187	n/a
188	n/a	/* ===========================================================================
189	n/a	* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
190	n/a	* prev[] will be initialized on the fly.
191	n/a	*/
192	n/a	#define CLEAR_HASH(s) \
193	n/a	s->head[s->hash_size-1] = NIL; \
194	n/a	zmemzero((Bytef )s->head, (unsigned)(s->hash_size-1)sizeof(*s->head));
195	n/a
196	n/a	/* ===========================================================================
197	n/a	* Slide the hash table when sliding the window down (could be avoided with 32
198	n/a	* bit values at the expense of memory usage). We slide even when level == 0 to
199	n/a	* keep the hash table consistent if we switch back to level > 0 later.
200	n/a	*/
201	n/a	local void slide_hash(s)
202	n/a	deflate_state *s;
203	n/a	{
204	n/a	unsigned n, m;
205	n/a	Posf *p;
206	n/a	uInt wsize = s->w_size;
207	n/a
208	n/a	n = s->hash_size;
209	n/a	p = &s->head[n];
210	n/a	do {
211	n/a	m = *--p;
212	n/a	*p = (Pos)(m >= wsize ? m - wsize : NIL);
213	n/a	} while (--n);
214	n/a	n = wsize;
215	n/a	#ifndef FASTEST
216	n/a	p = &s->prev[n];
217	n/a	do {
218	n/a	m = *--p;
219	n/a	*p = (Pos)(m >= wsize ? m - wsize : NIL);
220	n/a	/* If n is not on any hash chain, prev[n] is garbage but
221	n/a	* its value will never be used.
222	n/a	*/
223	n/a	} while (--n);
224	n/a	#endif
225	n/a	}
226	n/a
227	n/a	/* ========================================================================= */
228	n/a	int ZEXPORT deflateInit_(strm, level, version, stream_size)
229	n/a	z_streamp strm;
230	n/a	int level;
231	n/a	const char *version;
232	n/a	int stream_size;
233	n/a	{
234	n/a	return deflateInit2_(strm, level, Z_DEFLATED, MAX_WBITS, DEF_MEM_LEVEL,
235	n/a	Z_DEFAULT_STRATEGY, version, stream_size);
236	n/a	/* To do: ignore strm->next_in if we use it as window */
237	n/a	}
238	n/a
239	n/a	/* ========================================================================= */
240	n/a	int ZEXPORT deflateInit2_(strm, level, method, windowBits, memLevel, strategy,
241	n/a	version, stream_size)
242	n/a	z_streamp strm;
243	n/a	int level;
244	n/a	int method;
245	n/a	int windowBits;
246	n/a	int memLevel;
247	n/a	int strategy;
248	n/a	const char *version;
249	n/a	int stream_size;
250	n/a	{
251	n/a	deflate_state *s;
252	n/a	int wrap = 1;
253	n/a	static const char my_version[] = ZLIB_VERSION;
254	n/a
255	n/a	ushf *overlay;
256	n/a	/* We overlay pending_buf and d_buf+l_buf. This works since the average
257	n/a	* output size for (length,distance) codes is <= 24 bits.
258	n/a	*/
259	n/a
260	n/a	if (version == Z_NULL \|\| version[0] != my_version[0] \|\|
261	n/a	stream_size != sizeof(z_stream)) {
262	n/a	return Z_VERSION_ERROR;
263	n/a	}
264	n/a	if (strm == Z_NULL) return Z_STREAM_ERROR;
265	n/a
266	n/a	strm->msg = Z_NULL;
267	n/a	if (strm->zalloc == (alloc_func)0) {
268	n/a	#ifdef Z_SOLO
269	n/a	return Z_STREAM_ERROR;
270	n/a	#else
271	n/a	strm->zalloc = zcalloc;
272	n/a	strm->opaque = (voidpf)0;
273	n/a	#endif
274	n/a	}
275	n/a	if (strm->zfree == (free_func)0)
276	n/a	#ifdef Z_SOLO
277	n/a	return Z_STREAM_ERROR;
278	n/a	#else
279	n/a	strm->zfree = zcfree;
280	n/a	#endif
281	n/a
282	n/a	#ifdef FASTEST
283	n/a	if (level != 0) level = 1;
284	n/a	#else
285	n/a	if (level == Z_DEFAULT_COMPRESSION) level = 6;
286	n/a	#endif
287	n/a
288	n/a	if (windowBits < 0) { /* suppress zlib wrapper */
289	n/a	wrap = 0;
290	n/a	windowBits = -windowBits;
291	n/a	}
292	n/a	#ifdef GZIP
293	n/a	else if (windowBits > 15) {
294	n/a	wrap = 2; /* write gzip wrapper instead */
295	n/a	windowBits -= 16;
296	n/a	}
297	n/a	#endif
298	n/a	if (memLevel < 1 \|\| memLevel > MAX_MEM_LEVEL \|\| method != Z_DEFLATED \|\|
299	n/a	windowBits < 8 \|\| windowBits > 15 \|\| level < 0 \|\| level > 9 \|\|
300	n/a	strategy < 0 \|\| strategy > Z_FIXED \|\| (windowBits == 8 && wrap != 1)) {
301	n/a	return Z_STREAM_ERROR;
302	n/a	}
303	n/a	if (windowBits == 8) windowBits = 9; /* until 256-byte window bug fixed */
304	n/a	s = (deflate_state *) ZALLOC(strm, 1, sizeof(deflate_state));
305	n/a	if (s == Z_NULL) return Z_MEM_ERROR;
306	n/a	strm->state = (struct internal_state FAR *)s;
307	n/a	s->strm = strm;
308	n/a	s->status = INIT_STATE; /* to pass state test in deflateReset() */
309	n/a
310	n/a	s->wrap = wrap;
311	n/a	s->gzhead = Z_NULL;
312	n/a	s->w_bits = (uInt)windowBits;
313	n/a	s->w_size = 1 << s->w_bits;
314	n/a	s->w_mask = s->w_size - 1;
315	n/a
316	n/a	s->hash_bits = (uInt)memLevel + 7;
317	n/a	s->hash_size = 1 << s->hash_bits;
318	n/a	s->hash_mask = s->hash_size - 1;
319	n/a	s->hash_shift = ((s->hash_bits+MIN_MATCH-1)/MIN_MATCH);
320	n/a
321	n/a	s->window = (Bytef ) ZALLOC(strm, s->w_size, 2sizeof(Byte));
322	n/a	s->prev = (Posf *) ZALLOC(strm, s->w_size, sizeof(Pos));
323	n/a	s->head = (Posf *) ZALLOC(strm, s->hash_size, sizeof(Pos));
324	n/a
325	n/a	s->high_water = 0; /* nothing written to s->window yet */
326	n/a
327	n/a	s->lit_bufsize = 1 << (memLevel + 6); /* 16K elements by default */
328	n/a
329	n/a	overlay = (ushf *) ZALLOC(strm, s->lit_bufsize, sizeof(ush)+2);
330	n/a	s->pending_buf = (uchf *) overlay;
331	n/a	s->pending_buf_size = (ulg)s->lit_bufsize * (sizeof(ush)+2L);
332	n/a
333	n/a	if (s->window == Z_NULL \|\| s->prev == Z_NULL \|\| s->head == Z_NULL \|\|
334	n/a	s->pending_buf == Z_NULL) {
335	n/a	s->status = FINISH_STATE;
336	n/a	strm->msg = ERR_MSG(Z_MEM_ERROR);
337	n/a	deflateEnd (strm);
338	n/a	return Z_MEM_ERROR;
339	n/a	}
340	n/a	s->d_buf = overlay + s->lit_bufsize/sizeof(ush);
341	n/a	s->l_buf = s->pending_buf + (1+sizeof(ush))*s->lit_bufsize;
342	n/a
343	n/a	s->level = level;
344	n/a	s->strategy = strategy;
345	n/a	s->method = (Byte)method;
346	n/a
347	n/a	return deflateReset(strm);
348	n/a	}
349	n/a
350	n/a	/* =========================================================================
351	n/a	* Check for a valid deflate stream state. Return 0 if ok, 1 if not.
352	n/a	*/
353	n/a	local int deflateStateCheck (strm)
354	n/a	z_streamp strm;
355	n/a	{
356	n/a	deflate_state *s;
357	n/a	if (strm == Z_NULL \|\|
358	n/a	strm->zalloc == (alloc_func)0 \|\| strm->zfree == (free_func)0)
359	n/a	return 1;
360	n/a	s = strm->state;
361	n/a	if (s == Z_NULL \|\| s->strm != strm \|\| (s->status != INIT_STATE &&
362	n/a	#ifdef GZIP
363	n/a	s->status != GZIP_STATE &&
364	n/a	#endif
365	n/a	s->status != EXTRA_STATE &&
366	n/a	s->status != NAME_STATE &&
367	n/a	s->status != COMMENT_STATE &&
368	n/a	s->status != HCRC_STATE &&
369	n/a	s->status != BUSY_STATE &&
370	n/a	s->status != FINISH_STATE))
371	n/a	return 1;
372	n/a	return 0;
373	n/a	}
374	n/a
375	n/a	/* ========================================================================= */
376	n/a	int ZEXPORT deflateSetDictionary (strm, dictionary, dictLength)
377	n/a	z_streamp strm;
378	n/a	const Bytef *dictionary;
379	n/a	uInt dictLength;
380	n/a	{
381	n/a	deflate_state *s;
382	n/a	uInt str, n;
383	n/a	int wrap;
384	n/a	unsigned avail;
385	n/a	z_const unsigned char *next;
386	n/a
387	n/a	if (deflateStateCheck(strm) \|\| dictionary == Z_NULL)
388	n/a	return Z_STREAM_ERROR;
389	n/a	s = strm->state;
390	n/a	wrap = s->wrap;
391	n/a	if (wrap == 2 \|\| (wrap == 1 && s->status != INIT_STATE) \|\| s->lookahead)
392	n/a	return Z_STREAM_ERROR;
393	n/a
394	n/a	/* when using zlib wrappers, compute Adler-32 for provided dictionary */
395	n/a	if (wrap == 1)
396	n/a	strm->adler = adler32(strm->adler, dictionary, dictLength);
397	n/a	s->wrap = 0; /* avoid computing Adler-32 in read_buf */
398	n/a
399	n/a	/* if dictionary would fill window, just replace the history */
400	n/a	if (dictLength >= s->w_size) {
401	n/a	if (wrap == 0) { /* already empty otherwise */
402	n/a	CLEAR_HASH(s);
403	n/a	s->strstart = 0;
404	n/a	s->block_start = 0L;
405	n/a	s->insert = 0;
406	n/a	}
407	n/a	dictionary += dictLength - s->w_size; /* use the tail */
408	n/a	dictLength = s->w_size;
409	n/a	}
410	n/a
411	n/a	/* insert dictionary into window and hash */
412	n/a	avail = strm->avail_in;
413	n/a	next = strm->next_in;
414	n/a	strm->avail_in = dictLength;
415	n/a	strm->next_in = (z_const Bytef *)dictionary;
416	n/a	fill_window(s);
417	n/a	while (s->lookahead >= MIN_MATCH) {
418	n/a	str = s->strstart;
419	n/a	n = s->lookahead - (MIN_MATCH-1);
420	n/a	do {
421	n/a	UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
422	n/a	#ifndef FASTEST
423	n/a	s->prev[str & s->w_mask] = s->head[s->ins_h];
424	n/a	#endif
425	n/a	s->head[s->ins_h] = (Pos)str;
426	n/a	str++;
427	n/a	} while (--n);
428	n/a	s->strstart = str;
429	n/a	s->lookahead = MIN_MATCH-1;
430	n/a	fill_window(s);
431	n/a	}
432	n/a	s->strstart += s->lookahead;
433	n/a	s->block_start = (long)s->strstart;
434	n/a	s->insert = s->lookahead;
435	n/a	s->lookahead = 0;
436	n/a	s->match_length = s->prev_length = MIN_MATCH-1;
437	n/a	s->match_available = 0;
438	n/a	strm->next_in = next;
439	n/a	strm->avail_in = avail;
440	n/a	s->wrap = wrap;
441	n/a	return Z_OK;
442	n/a	}
443	n/a
444	n/a	/* ========================================================================= */
445	n/a	int ZEXPORT deflateGetDictionary (strm, dictionary, dictLength)
446	n/a	z_streamp strm;
447	n/a	Bytef *dictionary;
448	n/a	uInt *dictLength;
449	n/a	{
450	n/a	deflate_state *s;
451	n/a	uInt len;
452	n/a
453	n/a	if (deflateStateCheck(strm))
454	n/a	return Z_STREAM_ERROR;
455	n/a	s = strm->state;
456	n/a	len = s->strstart + s->lookahead;
457	n/a	if (len > s->w_size)
458	n/a	len = s->w_size;
459	n/a	if (dictionary != Z_NULL && len)
460	n/a	zmemcpy(dictionary, s->window + s->strstart + s->lookahead - len, len);
461	n/a	if (dictLength != Z_NULL)
462	n/a	*dictLength = len;
463	n/a	return Z_OK;
464	n/a	}
465	n/a
466	n/a	/* ========================================================================= */
467	n/a	int ZEXPORT deflateResetKeep (strm)
468	n/a	z_streamp strm;
469	n/a	{
470	n/a	deflate_state *s;
471	n/a
472	n/a	if (deflateStateCheck(strm)) {
473	n/a	return Z_STREAM_ERROR;
474	n/a	}
475	n/a
476	n/a	strm->total_in = strm->total_out = 0;
477	n/a	strm->msg = Z_NULL; /* use zfree if we ever allocate msg dynamically */
478	n/a	strm->data_type = Z_UNKNOWN;
479	n/a
480	n/a	s = (deflate_state *)strm->state;
481	n/a	s->pending = 0;
482	n/a	s->pending_out = s->pending_buf;
483	n/a
484	n/a	if (s->wrap < 0) {
485	n/a	s->wrap = -s->wrap; /* was made negative by deflate(..., Z_FINISH); */
486	n/a	}
487	n/a	s->status =
488	n/a	#ifdef GZIP
489	n/a	s->wrap == 2 ? GZIP_STATE :
490	n/a	#endif
491	n/a	s->wrap ? INIT_STATE : BUSY_STATE;
492	n/a	strm->adler =
493	n/a	#ifdef GZIP
494	n/a	s->wrap == 2 ? crc32(0L, Z_NULL, 0) :
495	n/a	#endif
496	n/a	adler32(0L, Z_NULL, 0);
497	n/a	s->last_flush = Z_NO_FLUSH;
498	n/a
499	n/a	_tr_init(s);
500	n/a
501	n/a	return Z_OK;
502	n/a	}
503	n/a
504	n/a	/* ========================================================================= */
505	n/a	int ZEXPORT deflateReset (strm)
506	n/a	z_streamp strm;
507	n/a	{
508	n/a	int ret;
509	n/a
510	n/a	ret = deflateResetKeep(strm);
511	n/a	if (ret == Z_OK)
512	n/a	lm_init(strm->state);
513	n/a	return ret;
514	n/a	}
515	n/a
516	n/a	/* ========================================================================= */
517	n/a	int ZEXPORT deflateSetHeader (strm, head)
518	n/a	z_streamp strm;
519	n/a	gz_headerp head;
520	n/a	{
521	n/a	if (deflateStateCheck(strm) \|\| strm->state->wrap != 2)
522	n/a	return Z_STREAM_ERROR;
523	n/a	strm->state->gzhead = head;
524	n/a	return Z_OK;
525	n/a	}
526	n/a
527	n/a	/* ========================================================================= */
528	n/a	int ZEXPORT deflatePending (strm, pending, bits)
529	n/a	unsigned *pending;
530	n/a	int *bits;
531	n/a	z_streamp strm;
532	n/a	{
533	n/a	if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
534	n/a	if (pending != Z_NULL)
535	n/a	*pending = strm->state->pending;
536	n/a	if (bits != Z_NULL)
537	n/a	*bits = strm->state->bi_valid;
538	n/a	return Z_OK;
539	n/a	}
540	n/a
541	n/a	/* ========================================================================= */
542	n/a	int ZEXPORT deflatePrime (strm, bits, value)
543	n/a	z_streamp strm;
544	n/a	int bits;
545	n/a	int value;
546	n/a	{
547	n/a	deflate_state *s;
548	n/a	int put;
549	n/a
550	n/a	if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
551	n/a	s = strm->state;
552	n/a	if ((Bytef *)(s->d_buf) < s->pending_out + ((Buf_size + 7) >> 3))
553	n/a	return Z_BUF_ERROR;
554	n/a	do {
555	n/a	put = Buf_size - s->bi_valid;
556	n/a	if (put > bits)
557	n/a	put = bits;
558	n/a	s->bi_buf \|= (ush)((value & ((1 << put) - 1)) << s->bi_valid);
559	n/a	s->bi_valid += put;
560	n/a	_tr_flush_bits(s);
561	n/a	value >>= put;
562	n/a	bits -= put;
563	n/a	} while (bits);
564	n/a	return Z_OK;
565	n/a	}
566	n/a
567	n/a	/* ========================================================================= */
568	n/a	int ZEXPORT deflateParams(strm, level, strategy)
569	n/a	z_streamp strm;
570	n/a	int level;
571	n/a	int strategy;
572	n/a	{
573	n/a	deflate_state *s;
574	n/a	compress_func func;
575	n/a
576	n/a	if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
577	n/a	s = strm->state;
578	n/a
579	n/a	#ifdef FASTEST
580	n/a	if (level != 0) level = 1;
581	n/a	#else
582	n/a	if (level == Z_DEFAULT_COMPRESSION) level = 6;
583	n/a	#endif
584	n/a	if (level < 0 \|\| level > 9 \|\| strategy < 0 \|\| strategy > Z_FIXED) {
585	n/a	return Z_STREAM_ERROR;
586	n/a	}
587	n/a	func = configuration_table[s->level].func;
588	n/a
589	n/a	if ((strategy != s->strategy \|\| func != configuration_table[level].func) &&
590	n/a	s->high_water) {
591	n/a	/* Flush the last buffer: */
592	n/a	int err = deflate(strm, Z_BLOCK);
593	n/a	if (err == Z_STREAM_ERROR)
594	n/a	return err;
595	n/a	if (strm->avail_out == 0)
596	n/a	return Z_BUF_ERROR;
597	n/a	}
598	n/a	if (s->level != level) {
599	n/a	if (s->level == 0 && s->matches != 0) {
600	n/a	if (s->matches == 1)
601	n/a	slide_hash(s);
602	n/a	else
603	n/a	CLEAR_HASH(s);
604	n/a	s->matches = 0;
605	n/a	}
606	n/a	s->level = level;
607	n/a	s->max_lazy_match = configuration_table[level].max_lazy;
608	n/a	s->good_match = configuration_table[level].good_length;
609	n/a	s->nice_match = configuration_table[level].nice_length;
610	n/a	s->max_chain_length = configuration_table[level].max_chain;
611	n/a	}
612	n/a	s->strategy = strategy;
613	n/a	return Z_OK;
614	n/a	}
615	n/a
616	n/a	/* ========================================================================= */
617	n/a	int ZEXPORT deflateTune(strm, good_length, max_lazy, nice_length, max_chain)
618	n/a	z_streamp strm;
619	n/a	int good_length;
620	n/a	int max_lazy;
621	n/a	int nice_length;
622	n/a	int max_chain;
623	n/a	{
624	n/a	deflate_state *s;
625	n/a
626	n/a	if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
627	n/a	s = strm->state;
628	n/a	s->good_match = (uInt)good_length;
629	n/a	s->max_lazy_match = (uInt)max_lazy;
630	n/a	s->nice_match = nice_length;
631	n/a	s->max_chain_length = (uInt)max_chain;
632	n/a	return Z_OK;
633	n/a	}
634	n/a
635	n/a	/* =========================================================================
636	n/a	* For the default windowBits of 15 and memLevel of 8, this function returns
637	n/a	* a close to exact, as well as small, upper bound on the compressed size.
638	n/a	* They are coded as constants here for a reason--if the #define's are
639	n/a	* changed, then this function needs to be changed as well. The return
640	n/a	* value for 15 and 8 only works for those exact settings.
641	n/a	*
642	n/a	* For any setting other than those defaults for windowBits and memLevel,
643	n/a	* the value returned is a conservative worst case for the maximum expansion
644	n/a	* resulting from using fixed blocks instead of stored blocks, which deflate
645	n/a	* can emit on compressed data for some combinations of the parameters.
646	n/a	*
647	n/a	* This function could be more sophisticated to provide closer upper bounds for
648	n/a	* every combination of windowBits and memLevel. But even the conservative
649	n/a	* upper bound of about 14% expansion does not seem onerous for output buffer
650	n/a	* allocation.
651	n/a	*/
652	n/a	uLong ZEXPORT deflateBound(strm, sourceLen)
653	n/a	z_streamp strm;
654	n/a	uLong sourceLen;
655	n/a	{
656	n/a	deflate_state *s;
657	n/a	uLong complen, wraplen;
658	n/a
659	n/a	/* conservative upper bound for compressed data */
660	n/a	complen = sourceLen +
661	n/a	((sourceLen + 7) >> 3) + ((sourceLen + 63) >> 6) + 5;
662	n/a
663	n/a	/* if can't get parameters, return conservative bound plus zlib wrapper */
664	n/a	if (deflateStateCheck(strm))
665	n/a	return complen + 6;
666	n/a
667	n/a	/* compute wrapper length */
668	n/a	s = strm->state;
669	n/a	switch (s->wrap) {
670	n/a	case 0: /* raw deflate */
671	n/a	wraplen = 0;
672	n/a	break;
673	n/a	case 1: /* zlib wrapper */
674	n/a	wraplen = 6 + (s->strstart ? 4 : 0);
675	n/a	break;
676	n/a	#ifdef GZIP
677	n/a	case 2: /* gzip wrapper */
678	n/a	wraplen = 18;
679	n/a	if (s->gzhead != Z_NULL) { /* user-supplied gzip header */
680	n/a	Bytef *str;
681	n/a	if (s->gzhead->extra != Z_NULL)
682	n/a	wraplen += 2 + s->gzhead->extra_len;
683	n/a	str = s->gzhead->name;
684	n/a	if (str != Z_NULL)
685	n/a	do {
686	n/a	wraplen++;
687	n/a	} while (*str++);
688	n/a	str = s->gzhead->comment;
689	n/a	if (str != Z_NULL)
690	n/a	do {
691	n/a	wraplen++;
692	n/a	} while (*str++);
693	n/a	if (s->gzhead->hcrc)
694	n/a	wraplen += 2;
695	n/a	}
696	n/a	break;
697	n/a	#endif
698	n/a	default: /* for compiler happiness */
699	n/a	wraplen = 6;
700	n/a	}
701	n/a
702	n/a	/* if not default parameters, return conservative bound */
703	n/a	if (s->w_bits != 15 \|\| s->hash_bits != 8 + 7)
704	n/a	return complen + wraplen;
705	n/a
706	n/a	/* default settings: return tight bound for that case */
707	n/a	return sourceLen + (sourceLen >> 12) + (sourceLen >> 14) +
708	n/a	(sourceLen >> 25) + 13 - 6 + wraplen;
709	n/a	}
710	n/a
711	n/a	/* =========================================================================
712	n/a	* Put a short in the pending buffer. The 16-bit value is put in MSB order.
713	n/a	* IN assertion: the stream state is correct and there is enough room in
714	n/a	* pending_buf.
715	n/a	*/
716	n/a	local void putShortMSB (s, b)
717	n/a	deflate_state *s;
718	n/a	uInt b;
719	n/a	{
720	n/a	put_byte(s, (Byte)(b >> 8));
721	n/a	put_byte(s, (Byte)(b & 0xff));
722	n/a	}
723	n/a
724	n/a	/* =========================================================================
725	n/a	* Flush as much pending output as possible. All deflate() output, except for
726	n/a	* some deflate_stored() output, goes through this function so some
727	n/a	* applications may wish to modify it to avoid allocating a large
728	n/a	* strm->next_out buffer and copying into it. (See also read_buf()).
729	n/a	*/
730	n/a	local void flush_pending(strm)
731	n/a	z_streamp strm;
732	n/a	{
733	n/a	unsigned len;
734	n/a	deflate_state *s = strm->state;
735	n/a
736	n/a	_tr_flush_bits(s);
737	n/a	len = s->pending;
738	n/a	if (len > strm->avail_out) len = strm->avail_out;
739	n/a	if (len == 0) return;
740	n/a
741	n/a	zmemcpy(strm->next_out, s->pending_out, len);
742	n/a	strm->next_out += len;
743	n/a	s->pending_out += len;
744	n/a	strm->total_out += len;
745	n/a	strm->avail_out -= len;
746	n/a	s->pending -= len;
747	n/a	if (s->pending == 0) {
748	n/a	s->pending_out = s->pending_buf;
749	n/a	}
750	n/a	}
751	n/a
752	n/a	/* ===========================================================================
753	n/a	* Update the header CRC with the bytes s->pending_buf[beg..s->pending - 1].
754	n/a	*/
755	n/a	#define HCRC_UPDATE(beg) \
756	n/a	do { \
757	n/a	if (s->gzhead->hcrc && s->pending > (beg)) \
758	n/a	strm->adler = crc32(strm->adler, s->pending_buf + (beg), \
759	n/a	s->pending - (beg)); \
760	n/a	} while (0)
761	n/a
762	n/a	/* ========================================================================= */
763	n/a	int ZEXPORT deflate (strm, flush)
764	n/a	z_streamp strm;
765	n/a	int flush;
766	n/a	{
767	n/a	int old_flush; /* value of flush param for previous deflate call */
768	n/a	deflate_state *s;
769	n/a
770	n/a	if (deflateStateCheck(strm) \|\| flush > Z_BLOCK \|\| flush < 0) {
771	n/a	return Z_STREAM_ERROR;
772	n/a	}
773	n/a	s = strm->state;
774	n/a
775	n/a	if (strm->next_out == Z_NULL \|\|
776	n/a	(strm->avail_in != 0 && strm->next_in == Z_NULL) \|\|
777	n/a	(s->status == FINISH_STATE && flush != Z_FINISH)) {
778	n/a	ERR_RETURN(strm, Z_STREAM_ERROR);
779	n/a	}
780	n/a	if (strm->avail_out == 0) ERR_RETURN(strm, Z_BUF_ERROR);
781	n/a
782	n/a	old_flush = s->last_flush;
783	n/a	s->last_flush = flush;
784	n/a
785	n/a	/* Flush as much pending output as possible */
786	n/a	if (s->pending != 0) {
787	n/a	flush_pending(strm);
788	n/a	if (strm->avail_out == 0) {
789	n/a	/* Since avail_out is 0, deflate will be called again with
790	n/a	* more output space, but possibly with both pending and
791	n/a	* avail_in equal to zero. There won't be anything to do,
792	n/a	* but this is not an error situation so make sure we
793	n/a	* return OK instead of BUF_ERROR at next call of deflate:
794	n/a	*/
795	n/a	s->last_flush = -1;
796	n/a	return Z_OK;
797	n/a	}
798	n/a
799	n/a	/* Make sure there is something to do and avoid duplicate consecutive
800	n/a	* flushes. For repeated and useless calls with Z_FINISH, we keep
801	n/a	* returning Z_STREAM_END instead of Z_BUF_ERROR.
802	n/a	*/
803	n/a	} else if (strm->avail_in == 0 && RANK(flush) <= RANK(old_flush) &&
804	n/a	flush != Z_FINISH) {
805	n/a	ERR_RETURN(strm, Z_BUF_ERROR);
806	n/a	}
807	n/a
808	n/a	/* User must not provide more input after the first FINISH: */
809	n/a	if (s->status == FINISH_STATE && strm->avail_in != 0) {
810	n/a	ERR_RETURN(strm, Z_BUF_ERROR);
811	n/a	}
812	n/a
813	n/a	/* Write the header */
814	n/a	if (s->status == INIT_STATE) {
815	n/a	/* zlib header */
816	n/a	uInt header = (Z_DEFLATED + ((s->w_bits-8)<<4)) << 8;
817	n/a	uInt level_flags;
818	n/a
819	n/a	if (s->strategy >= Z_HUFFMAN_ONLY \|\| s->level < 2)
820	n/a	level_flags = 0;
821	n/a	else if (s->level < 6)
822	n/a	level_flags = 1;
823	n/a	else if (s->level == 6)
824	n/a	level_flags = 2;
825	n/a	else
826	n/a	level_flags = 3;
827	n/a	header \|= (level_flags << 6);
828	n/a	if (s->strstart != 0) header \|= PRESET_DICT;
829	n/a	header += 31 - (header % 31);
830	n/a
831	n/a	putShortMSB(s, header);
832	n/a
833	n/a	/* Save the adler32 of the preset dictionary: */
834	n/a	if (s->strstart != 0) {
835	n/a	putShortMSB(s, (uInt)(strm->adler >> 16));
836	n/a	putShortMSB(s, (uInt)(strm->adler & 0xffff));
837	n/a	}
838	n/a	strm->adler = adler32(0L, Z_NULL, 0);
839	n/a	s->status = BUSY_STATE;
840	n/a
841	n/a	/* Compression must start with an empty pending buffer */
842	n/a	flush_pending(strm);
843	n/a	if (s->pending != 0) {
844	n/a	s->last_flush = -1;
845	n/a	return Z_OK;
846	n/a	}
847	n/a	}
848	n/a	#ifdef GZIP
849	n/a	if (s->status == GZIP_STATE) {
850	n/a	/* gzip header */
851	n/a	strm->adler = crc32(0L, Z_NULL, 0);
852	n/a	put_byte(s, 31);
853	n/a	put_byte(s, 139);
854	n/a	put_byte(s, 8);
855	n/a	if (s->gzhead == Z_NULL) {
856	n/a	put_byte(s, 0);
857	n/a	put_byte(s, 0);
858	n/a	put_byte(s, 0);
859	n/a	put_byte(s, 0);
860	n/a	put_byte(s, 0);
861	n/a	put_byte(s, s->level == 9 ? 2 :
862	n/a	(s->strategy >= Z_HUFFMAN_ONLY \|\| s->level < 2 ?
863	n/a	4 : 0));
864	n/a	put_byte(s, OS_CODE);
865	n/a	s->status = BUSY_STATE;
866	n/a
867	n/a	/* Compression must start with an empty pending buffer */
868	n/a	flush_pending(strm);
869	n/a	if (s->pending != 0) {
870	n/a	s->last_flush = -1;
871	n/a	return Z_OK;
872	n/a	}
873	n/a	}
874	n/a	else {
875	n/a	put_byte(s, (s->gzhead->text ? 1 : 0) +
876	n/a	(s->gzhead->hcrc ? 2 : 0) +
877	n/a	(s->gzhead->extra == Z_NULL ? 0 : 4) +
878	n/a	(s->gzhead->name == Z_NULL ? 0 : 8) +
879	n/a	(s->gzhead->comment == Z_NULL ? 0 : 16)
880	n/a	);
881	n/a	put_byte(s, (Byte)(s->gzhead->time & 0xff));
882	n/a	put_byte(s, (Byte)((s->gzhead->time >> 8) & 0xff));
883	n/a	put_byte(s, (Byte)((s->gzhead->time >> 16) & 0xff));
884	n/a	put_byte(s, (Byte)((s->gzhead->time >> 24) & 0xff));
885	n/a	put_byte(s, s->level == 9 ? 2 :
886	n/a	(s->strategy >= Z_HUFFMAN_ONLY \|\| s->level < 2 ?
887	n/a	4 : 0));
888	n/a	put_byte(s, s->gzhead->os & 0xff);
889	n/a	if (s->gzhead->extra != Z_NULL) {
890	n/a	put_byte(s, s->gzhead->extra_len & 0xff);
891	n/a	put_byte(s, (s->gzhead->extra_len >> 8) & 0xff);
892	n/a	}
893	n/a	if (s->gzhead->hcrc)
894	n/a	strm->adler = crc32(strm->adler, s->pending_buf,
895	n/a	s->pending);
896	n/a	s->gzindex = 0;
897	n/a	s->status = EXTRA_STATE;
898	n/a	}
899	n/a	}
900	n/a	if (s->status == EXTRA_STATE) {
901	n/a	if (s->gzhead->extra != Z_NULL) {
902	n/a	ulg beg = s->pending; /* start of bytes to update crc */
903	n/a	uInt left = (s->gzhead->extra_len & 0xffff) - s->gzindex;
904	n/a	while (s->pending + left > s->pending_buf_size) {
905	n/a	uInt copy = s->pending_buf_size - s->pending;
906	n/a	zmemcpy(s->pending_buf + s->pending,
907	n/a	s->gzhead->extra + s->gzindex, copy);
908	n/a	s->pending = s->pending_buf_size;
909	n/a	HCRC_UPDATE(beg);
910	n/a	s->gzindex += copy;
911	n/a	flush_pending(strm);
912	n/a	if (s->pending != 0) {
913	n/a	s->last_flush = -1;
914	n/a	return Z_OK;
915	n/a	}
916	n/a	beg = 0;
917	n/a	left -= copy;
918	n/a	}
919	n/a	zmemcpy(s->pending_buf + s->pending,
920	n/a	s->gzhead->extra + s->gzindex, left);
921	n/a	s->pending += left;
922	n/a	HCRC_UPDATE(beg);
923	n/a	s->gzindex = 0;
924	n/a	}
925	n/a	s->status = NAME_STATE;
926	n/a	}
927	n/a	if (s->status == NAME_STATE) {
928	n/a	if (s->gzhead->name != Z_NULL) {
929	n/a	ulg beg = s->pending; /* start of bytes to update crc */
930	n/a	int val;
931	n/a	do {
932	n/a	if (s->pending == s->pending_buf_size) {
933	n/a	HCRC_UPDATE(beg);
934	n/a	flush_pending(strm);
935	n/a	if (s->pending != 0) {
936	n/a	s->last_flush = -1;
937	n/a	return Z_OK;
938	n/a	}
939	n/a	beg = 0;
940	n/a	}
941	n/a	val = s->gzhead->name[s->gzindex++];
942	n/a	put_byte(s, val);
943	n/a	} while (val != 0);
944	n/a	HCRC_UPDATE(beg);
945	n/a	s->gzindex = 0;
946	n/a	}
947	n/a	s->status = COMMENT_STATE;
948	n/a	}
949	n/a	if (s->status == COMMENT_STATE) {
950	n/a	if (s->gzhead->comment != Z_NULL) {
951	n/a	ulg beg = s->pending; /* start of bytes to update crc */
952	n/a	int val;
953	n/a	do {
954	n/a	if (s->pending == s->pending_buf_size) {
955	n/a	HCRC_UPDATE(beg);
956	n/a	flush_pending(strm);
957	n/a	if (s->pending != 0) {
958	n/a	s->last_flush = -1;
959	n/a	return Z_OK;
960	n/a	}
961	n/a	beg = 0;
962	n/a	}
963	n/a	val = s->gzhead->comment[s->gzindex++];
964	n/a	put_byte(s, val);
965	n/a	} while (val != 0);
966	n/a	HCRC_UPDATE(beg);
967	n/a	}
968	n/a	s->status = HCRC_STATE;
969	n/a	}
970	n/a	if (s->status == HCRC_STATE) {
971	n/a	if (s->gzhead->hcrc) {
972	n/a	if (s->pending + 2 > s->pending_buf_size) {
973	n/a	flush_pending(strm);
974	n/a	if (s->pending != 0) {
975	n/a	s->last_flush = -1;
976	n/a	return Z_OK;
977	n/a	}
978	n/a	}
979	n/a	put_byte(s, (Byte)(strm->adler & 0xff));
980	n/a	put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
981	n/a	strm->adler = crc32(0L, Z_NULL, 0);
982	n/a	}
983	n/a	s->status = BUSY_STATE;
984	n/a
985	n/a	/* Compression must start with an empty pending buffer */
986	n/a	flush_pending(strm);
987	n/a	if (s->pending != 0) {
988	n/a	s->last_flush = -1;
989	n/a	return Z_OK;
990	n/a	}
991	n/a	}
992	n/a	#endif
993	n/a
994	n/a	/* Start a new block or continue the current one.
995	n/a	*/
996	n/a	if (strm->avail_in != 0 \|\| s->lookahead != 0 \|\|
997	n/a	(flush != Z_NO_FLUSH && s->status != FINISH_STATE)) {
998	n/a	block_state bstate;
999	n/a
1000	n/a	bstate = s->level == 0 ? deflate_stored(s, flush) :
1001	n/a	s->strategy == Z_HUFFMAN_ONLY ? deflate_huff(s, flush) :
1002	n/a	s->strategy == Z_RLE ? deflate_rle(s, flush) :
1003	n/a	(*(configuration_table[s->level].func))(s, flush);
1004	n/a
1005	n/a	if (bstate == finish_started \|\| bstate == finish_done) {
1006	n/a	s->status = FINISH_STATE;
1007	n/a	}
1008	n/a	if (bstate == need_more \|\| bstate == finish_started) {
1009	n/a	if (strm->avail_out == 0) {
1010	n/a	s->last_flush = -1; /* avoid BUF_ERROR next call, see above */
1011	n/a	}
1012	n/a	return Z_OK;
1013	n/a	/* If flush != Z_NO_FLUSH && avail_out == 0, the next call
1014	n/a	* of deflate should use the same flush parameter to make sure
1015	n/a	* that the flush is complete. So we don't have to output an
1016	n/a	* empty block here, this will be done at next call. This also
1017	n/a	* ensures that for a very small output buffer, we emit at most
1018	n/a	* one empty block.
1019	n/a	*/
1020	n/a	}
1021	n/a	if (bstate == block_done) {
1022	n/a	if (flush == Z_PARTIAL_FLUSH) {
1023	n/a	_tr_align(s);
1024	n/a	} else if (flush != Z_BLOCK) { /* FULL_FLUSH or SYNC_FLUSH */
1025	n/a	_tr_stored_block(s, (char*)0, 0L, 0);
1026	n/a	/* For a full flush, this empty block will be recognized
1027	n/a	* as a special marker by inflate_sync().
1028	n/a	*/
1029	n/a	if (flush == Z_FULL_FLUSH) {
1030	n/a	CLEAR_HASH(s); /* forget history */
1031	n/a	if (s->lookahead == 0) {
1032	n/a	s->strstart = 0;
1033	n/a	s->block_start = 0L;
1034	n/a	s->insert = 0;
1035	n/a	}
1036	n/a	}
1037	n/a	}
1038	n/a	flush_pending(strm);
1039	n/a	if (strm->avail_out == 0) {
1040	n/a	s->last_flush = -1; /* avoid BUF_ERROR at next call, see above */
1041	n/a	return Z_OK;
1042	n/a	}
1043	n/a	}
1044	n/a	}
1045	n/a
1046	n/a	if (flush != Z_FINISH) return Z_OK;
1047	n/a	if (s->wrap <= 0) return Z_STREAM_END;
1048	n/a
1049	n/a	/* Write the trailer */
1050	n/a	#ifdef GZIP
1051	n/a	if (s->wrap == 2) {
1052	n/a	put_byte(s, (Byte)(strm->adler & 0xff));
1053	n/a	put_byte(s, (Byte)((strm->adler >> 8) & 0xff));
1054	n/a	put_byte(s, (Byte)((strm->adler >> 16) & 0xff));
1055	n/a	put_byte(s, (Byte)((strm->adler >> 24) & 0xff));
1056	n/a	put_byte(s, (Byte)(strm->total_in & 0xff));
1057	n/a	put_byte(s, (Byte)((strm->total_in >> 8) & 0xff));
1058	n/a	put_byte(s, (Byte)((strm->total_in >> 16) & 0xff));
1059	n/a	put_byte(s, (Byte)((strm->total_in >> 24) & 0xff));
1060	n/a	}
1061	n/a	else
1062	n/a	#endif
1063	n/a	{
1064	n/a	putShortMSB(s, (uInt)(strm->adler >> 16));
1065	n/a	putShortMSB(s, (uInt)(strm->adler & 0xffff));
1066	n/a	}
1067	n/a	flush_pending(strm);
1068	n/a	/* If avail_out is zero, the application will call deflate again
1069	n/a	* to flush the rest.
1070	n/a	*/
1071	n/a	if (s->wrap > 0) s->wrap = -s->wrap; /* write the trailer only once! */
1072	n/a	return s->pending != 0 ? Z_OK : Z_STREAM_END;
1073	n/a	}
1074	n/a
1075	n/a	/* ========================================================================= */
1076	n/a	int ZEXPORT deflateEnd (strm)
1077	n/a	z_streamp strm;
1078	n/a	{
1079	n/a	int status;
1080	n/a
1081	n/a	if (deflateStateCheck(strm)) return Z_STREAM_ERROR;
1082	n/a
1083	n/a	status = strm->state->status;
1084	n/a
1085	n/a	/* Deallocate in reverse order of allocations: */
1086	n/a	TRY_FREE(strm, strm->state->pending_buf);
1087	n/a	TRY_FREE(strm, strm->state->head);
1088	n/a	TRY_FREE(strm, strm->state->prev);
1089	n/a	TRY_FREE(strm, strm->state->window);
1090	n/a
1091	n/a	ZFREE(strm, strm->state);
1092	n/a	strm->state = Z_NULL;
1093	n/a
1094	n/a	return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK;
1095	n/a	}
1096	n/a
1097	n/a	/* =========================================================================
1098	n/a	* Copy the source state to the destination state.
1099	n/a	* To simplify the source, this is not supported for 16-bit MSDOS (which
1100	n/a	* doesn't have enough memory anyway to duplicate compression states).
1101	n/a	*/
1102	n/a	int ZEXPORT deflateCopy (dest, source)
1103	n/a	z_streamp dest;
1104	n/a	z_streamp source;
1105	n/a	{
1106	n/a	#ifdef MAXSEG_64K
1107	n/a	return Z_STREAM_ERROR;
1108	n/a	#else
1109	n/a	deflate_state *ds;
1110	n/a	deflate_state *ss;
1111	n/a	ushf *overlay;
1112	n/a
1113	n/a
1114	n/a	if (deflateStateCheck(source) \|\| dest == Z_NULL) {
1115	n/a	return Z_STREAM_ERROR;
1116	n/a	}
1117	n/a
1118	n/a	ss = source->state;
1119	n/a
1120	n/a	zmemcpy((voidpf)dest, (voidpf)source, sizeof(z_stream));
1121	n/a
1122	n/a	ds = (deflate_state *) ZALLOC(dest, 1, sizeof(deflate_state));
1123	n/a	if (ds == Z_NULL) return Z_MEM_ERROR;
1124	n/a	dest->state = (struct internal_state FAR *) ds;
1125	n/a	zmemcpy((voidpf)ds, (voidpf)ss, sizeof(deflate_state));
1126	n/a	ds->strm = dest;
1127	n/a
1128	n/a	ds->window = (Bytef ) ZALLOC(dest, ds->w_size, 2sizeof(Byte));
1129	n/a	ds->prev = (Posf *) ZALLOC(dest, ds->w_size, sizeof(Pos));
1130	n/a	ds->head = (Posf *) ZALLOC(dest, ds->hash_size, sizeof(Pos));
1131	n/a	overlay = (ushf *) ZALLOC(dest, ds->lit_bufsize, sizeof(ush)+2);
1132	n/a	ds->pending_buf = (uchf *) overlay;
1133	n/a
1134	n/a	if (ds->window == Z_NULL \|\| ds->prev == Z_NULL \|\| ds->head == Z_NULL \|\|
1135	n/a	ds->pending_buf == Z_NULL) {
1136	n/a	deflateEnd (dest);
1137	n/a	return Z_MEM_ERROR;
1138	n/a	}
1139	n/a	/* following zmemcpy do not work for 16-bit MSDOS */
1140	n/a	zmemcpy(ds->window, ss->window, ds->w_size * 2 * sizeof(Byte));
1141	n/a	zmemcpy((voidpf)ds->prev, (voidpf)ss->prev, ds->w_size * sizeof(Pos));
1142	n/a	zmemcpy((voidpf)ds->head, (voidpf)ss->head, ds->hash_size * sizeof(Pos));
1143	n/a	zmemcpy(ds->pending_buf, ss->pending_buf, (uInt)ds->pending_buf_size);
1144	n/a
1145	n/a	ds->pending_out = ds->pending_buf + (ss->pending_out - ss->pending_buf);
1146	n/a	ds->d_buf = overlay + ds->lit_bufsize/sizeof(ush);
1147	n/a	ds->l_buf = ds->pending_buf + (1+sizeof(ush))*ds->lit_bufsize;
1148	n/a
1149	n/a	ds->l_desc.dyn_tree = ds->dyn_ltree;
1150	n/a	ds->d_desc.dyn_tree = ds->dyn_dtree;
1151	n/a	ds->bl_desc.dyn_tree = ds->bl_tree;
1152	n/a
1153	n/a	return Z_OK;
1154	n/a	#endif /* MAXSEG_64K */
1155	n/a	}
1156	n/a
1157	n/a	/* ===========================================================================
1158	n/a	* Read a new buffer from the current input stream, update the adler32
1159	n/a	* and total number of bytes read. All deflate() input goes through
1160	n/a	* this function so some applications may wish to modify it to avoid
1161	n/a	* allocating a large strm->next_in buffer and copying from it.
1162	n/a	* (See also flush_pending()).
1163	n/a	*/
1164	n/a	local unsigned read_buf(strm, buf, size)
1165	n/a	z_streamp strm;
1166	n/a	Bytef *buf;
1167	n/a	unsigned size;
1168	n/a	{
1169	n/a	unsigned len = strm->avail_in;
1170	n/a
1171	n/a	if (len > size) len = size;
1172	n/a	if (len == 0) return 0;
1173	n/a
1174	n/a	strm->avail_in -= len;
1175	n/a
1176	n/a	zmemcpy(buf, strm->next_in, len);
1177	n/a	if (strm->state->wrap == 1) {
1178	n/a	strm->adler = adler32(strm->adler, buf, len);
1179	n/a	}
1180	n/a	#ifdef GZIP
1181	n/a	else if (strm->state->wrap == 2) {
1182	n/a	strm->adler = crc32(strm->adler, buf, len);
1183	n/a	}
1184	n/a	#endif
1185	n/a	strm->next_in += len;
1186	n/a	strm->total_in += len;
1187	n/a
1188	n/a	return len;
1189	n/a	}
1190	n/a
1191	n/a	/* ===========================================================================
1192	n/a	* Initialize the "longest match" routines for a new zlib stream
1193	n/a	*/
1194	n/a	local void lm_init (s)
1195	n/a	deflate_state *s;
1196	n/a	{
1197	n/a	s->window_size = (ulg)2L*s->w_size;
1198	n/a
1199	n/a	CLEAR_HASH(s);
1200	n/a
1201	n/a	/* Set the default configuration parameters:
1202	n/a	*/
1203	n/a	s->max_lazy_match = configuration_table[s->level].max_lazy;
1204	n/a	s->good_match = configuration_table[s->level].good_length;
1205	n/a	s->nice_match = configuration_table[s->level].nice_length;
1206	n/a	s->max_chain_length = configuration_table[s->level].max_chain;
1207	n/a
1208	n/a	s->strstart = 0;
1209	n/a	s->block_start = 0L;
1210	n/a	s->lookahead = 0;
1211	n/a	s->insert = 0;
1212	n/a	s->match_length = s->prev_length = MIN_MATCH-1;
1213	n/a	s->match_available = 0;
1214	n/a	s->ins_h = 0;
1215	n/a	#ifndef FASTEST
1216	n/a	#ifdef ASMV
1217	n/a	match_init(); /* initialize the asm code */
1218	n/a	#endif
1219	n/a	#endif
1220	n/a	}
1221	n/a
1222	n/a	#ifndef FASTEST
1223	n/a	/* ===========================================================================
1224	n/a	* Set match_start to the longest match starting at the given string and
1225	n/a	* return its length. Matches shorter or equal to prev_length are discarded,
1226	n/a	* in which case the result is equal to prev_length and match_start is
1227	n/a	* garbage.
1228	n/a	* IN assertions: cur_match is the head of the hash chain for the current
1229	n/a	* string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
1230	n/a	* OUT assertion: the match length is not greater than s->lookahead.
1231	n/a	*/
1232	n/a	#ifndef ASMV
1233	n/a	/* For 80x86 and 680x0, an optimized version will be provided in match.asm or
1234	n/a	* match.S. The code will be functionally equivalent.
1235	n/a	*/
1236	n/a	local uInt longest_match(s, cur_match)
1237	n/a	deflate_state *s;
1238	n/a	IPos cur_match; /* current match */
1239	n/a	{
1240	n/a	unsigned chain_length = s->max_chain_length;/* max hash chain length */
1241	n/a	register Bytef scan = s->window + s->strstart; / current string */
1242	n/a	register Bytef match; / matched string */
1243	n/a	register int len; /* length of current match */
1244	n/a	int best_len = (int)s->prev_length; /* best match length so far */
1245	n/a	int nice_match = s->nice_match; /* stop if match long enough */
1246	n/a	IPos limit = s->strstart > (IPos)MAX_DIST(s) ?
1247	n/a	s->strstart - (IPos)MAX_DIST(s) : NIL;
1248	n/a	/* Stop when cur_match becomes <= limit. To simplify the code,
1249	n/a	* we prevent matches with the string of window index 0.
1250	n/a	*/
1251	n/a	Posf *prev = s->prev;
1252	n/a	uInt wmask = s->w_mask;
1253	n/a
1254	n/a	#ifdef UNALIGNED_OK
1255	n/a	/* Compare two bytes at a time. Note: this is not always beneficial.
1256	n/a	* Try with and without -DUNALIGNED_OK to check.
1257	n/a	*/
1258	n/a	register Bytef *strend = s->window + s->strstart + MAX_MATCH - 1;
1259	n/a	register ush scan_start = (ushf)scan;
1260	n/a	register ush scan_end = (ushf)(scan+best_len-1);
1261	n/a	#else
1262	n/a	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1263	n/a	register Byte scan_end1 = scan[best_len-1];
1264	n/a	register Byte scan_end = scan[best_len];
1265	n/a	#endif
1266	n/a
1267	n/a	/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1268	n/a	* It is easy to get rid of this optimization if necessary.
1269	n/a	*/
1270	n/a	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1271	n/a
1272	n/a	/* Do not waste too much time if we already have a good match: */
1273	n/a	if (s->prev_length >= s->good_match) {
1274	n/a	chain_length >>= 2;
1275	n/a	}
1276	n/a	/* Do not look for matches beyond the end of the input. This is necessary
1277	n/a	* to make deflate deterministic.
1278	n/a	*/
1279	n/a	if ((uInt)nice_match > s->lookahead) nice_match = (int)s->lookahead;
1280	n/a
1281	n/a	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1282	n/a
1283	n/a	do {
1284	n/a	Assert(cur_match < s->strstart, "no future");
1285	n/a	match = s->window + cur_match;
1286	n/a
1287	n/a	/* Skip to next match if the match length cannot increase
1288	n/a	* or if the match length is less than 2. Note that the checks below
1289	n/a	* for insufficient lookahead only occur occasionally for performance
1290	n/a	* reasons. Therefore uninitialized memory will be accessed, and
1291	n/a	* conditional jumps will be made that depend on those values.
1292	n/a	* However the length of the match is limited to the lookahead, so
1293	n/a	* the output of deflate is not affected by the uninitialized values.
1294	n/a	*/
1295	n/a	#if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
1296	n/a	/* This code assumes sizeof(unsigned short) == 2. Do not use
1297	n/a	* UNALIGNED_OK if your compiler uses a different size.
1298	n/a	*/
1299	n/a	if ((ushf)(match+best_len-1) != scan_end \|\|
1300	n/a	(ushf)match != scan_start) continue;
1301	n/a
1302	n/a	/* It is not necessary to compare scan[2] and match[2] since they are
1303	n/a	* always equal when the other bytes match, given that the hash keys
1304	n/a	* are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
1305	n/a	* strstart+3, +5, ... up to strstart+257. We check for insufficient
1306	n/a	* lookahead only every 4th comparison; the 128th check will be made
1307	n/a	* at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
1308	n/a	* necessary to put more guard bytes at the end of the window, or
1309	n/a	* to check more often for insufficient lookahead.
1310	n/a	*/
1311	n/a	Assert(scan[2] == match[2], "scan[2]?");
1312	n/a	scan++, match++;
1313	n/a	do {
1314	n/a	} while ((ushf)(scan+=2) == (ushf)(match+=2) &&
1315	n/a	(ushf)(scan+=2) == (ushf)(match+=2) &&
1316	n/a	(ushf)(scan+=2) == (ushf)(match+=2) &&
1317	n/a	(ushf)(scan+=2) == (ushf)(match+=2) &&
1318	n/a	scan < strend);
1319	n/a	/* The funny "do {}" generates better code on most compilers */
1320	n/a
1321	n/a	/* Here, scan <= window+strstart+257 */
1322	n/a	Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1323	n/a	if (scan == match) scan++;
1324	n/a
1325	n/a	len = (MAX_MATCH - 1) - (int)(strend-scan);
1326	n/a	scan = strend - (MAX_MATCH-1);
1327	n/a
1328	n/a	#else /* UNALIGNED_OK */
1329	n/a
1330	n/a	if (match[best_len] != scan_end \|\|
1331	n/a	match[best_len-1] != scan_end1 \|\|
1332	n/a	match != scan \|\|
1333	n/a	*++match != scan[1]) continue;
1334	n/a
1335	n/a	/* The check at best_len-1 can be removed because it will be made
1336	n/a	* again later. (This heuristic is not always a win.)
1337	n/a	* It is not necessary to compare scan[2] and match[2] since they
1338	n/a	* are always equal when the other bytes match, given that
1339	n/a	* the hash keys are equal and that HASH_BITS >= 8.
1340	n/a	*/
1341	n/a	scan += 2, match++;
1342	n/a	Assert(scan == match, "match[2]?");
1343	n/a
1344	n/a	/* We check for insufficient lookahead only every 8th comparison;
1345	n/a	* the 256th check will be made at strstart+258.
1346	n/a	*/
1347	n/a	do {
1348	n/a	} while (++scan == ++match && ++scan == ++match &&
1349	n/a	++scan == ++match && ++scan == ++match &&
1350	n/a	++scan == ++match && ++scan == ++match &&
1351	n/a	++scan == ++match && ++scan == ++match &&
1352	n/a	scan < strend);
1353	n/a
1354	n/a	Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1355	n/a
1356	n/a	len = MAX_MATCH - (int)(strend - scan);
1357	n/a	scan = strend - MAX_MATCH;
1358	n/a
1359	n/a	#endif /* UNALIGNED_OK */
1360	n/a
1361	n/a	if (len > best_len) {
1362	n/a	s->match_start = cur_match;
1363	n/a	best_len = len;
1364	n/a	if (len >= nice_match) break;
1365	n/a	#ifdef UNALIGNED_OK
1366	n/a	scan_end = (ushf)(scan+best_len-1);
1367	n/a	#else
1368	n/a	scan_end1 = scan[best_len-1];
1369	n/a	scan_end = scan[best_len];
1370	n/a	#endif
1371	n/a	}
1372	n/a	} while ((cur_match = prev[cur_match & wmask]) > limit
1373	n/a	&& --chain_length != 0);
1374	n/a
1375	n/a	if ((uInt)best_len <= s->lookahead) return (uInt)best_len;
1376	n/a	return s->lookahead;
1377	n/a	}
1378	n/a	#endif /* ASMV */
1379	n/a
1380	n/a	#else /* FASTEST */
1381	n/a
1382	n/a	/* ---------------------------------------------------------------------------
1383	n/a	* Optimized version for FASTEST only
1384	n/a	*/
1385	n/a	local uInt longest_match(s, cur_match)
1386	n/a	deflate_state *s;
1387	n/a	IPos cur_match; /* current match */
1388	n/a	{
1389	n/a	register Bytef scan = s->window + s->strstart; / current string */
1390	n/a	register Bytef match; / matched string */
1391	n/a	register int len; /* length of current match */
1392	n/a	register Bytef *strend = s->window + s->strstart + MAX_MATCH;
1393	n/a
1394	n/a	/* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
1395	n/a	* It is easy to get rid of this optimization if necessary.
1396	n/a	*/
1397	n/a	Assert(s->hash_bits >= 8 && MAX_MATCH == 258, "Code too clever");
1398	n/a
1399	n/a	Assert((ulg)s->strstart <= s->window_size-MIN_LOOKAHEAD, "need lookahead");
1400	n/a
1401	n/a	Assert(cur_match < s->strstart, "no future");
1402	n/a
1403	n/a	match = s->window + cur_match;
1404	n/a
1405	n/a	/* Return failure if the match length is less than 2:
1406	n/a	*/
1407	n/a	if (match[0] != scan[0] \|\| match[1] != scan[1]) return MIN_MATCH-1;
1408	n/a
1409	n/a	/* The check at best_len-1 can be removed because it will be made
1410	n/a	* again later. (This heuristic is not always a win.)
1411	n/a	* It is not necessary to compare scan[2] and match[2] since they
1412	n/a	* are always equal when the other bytes match, given that
1413	n/a	* the hash keys are equal and that HASH_BITS >= 8.
1414	n/a	*/
1415	n/a	scan += 2, match += 2;
1416	n/a	Assert(scan == match, "match[2]?");
1417	n/a
1418	n/a	/* We check for insufficient lookahead only every 8th comparison;
1419	n/a	* the 256th check will be made at strstart+258.
1420	n/a	*/
1421	n/a	do {
1422	n/a	} while (++scan == ++match && ++scan == ++match &&
1423	n/a	++scan == ++match && ++scan == ++match &&
1424	n/a	++scan == ++match && ++scan == ++match &&
1425	n/a	++scan == ++match && ++scan == ++match &&
1426	n/a	scan < strend);
1427	n/a
1428	n/a	Assert(scan <= s->window+(unsigned)(s->window_size-1), "wild scan");
1429	n/a
1430	n/a	len = MAX_MATCH - (int)(strend - scan);
1431	n/a
1432	n/a	if (len < MIN_MATCH) return MIN_MATCH - 1;
1433	n/a
1434	n/a	s->match_start = cur_match;
1435	n/a	return (uInt)len <= s->lookahead ? (uInt)len : s->lookahead;
1436	n/a	}
1437	n/a
1438	n/a	#endif /* FASTEST */
1439	n/a
1440	n/a	#ifdef ZLIB_DEBUG
1441	n/a
1442	n/a	#define EQUAL 0
1443	n/a	/* result of memcmp for equal strings */
1444	n/a
1445	n/a	/* ===========================================================================
1446	n/a	* Check that the match at match_start is indeed a match.
1447	n/a	*/
1448	n/a	local void check_match(s, start, match, length)
1449	n/a	deflate_state *s;
1450	n/a	IPos start, match;
1451	n/a	int length;
1452	n/a	{
1453	n/a	/* check that the match is indeed a match */
1454	n/a	if (zmemcmp(s->window + match,
1455	n/a	s->window + start, length) != EQUAL) {
1456	n/a	fprintf(stderr, " start %u, match %u, length %d\n",
1457	n/a	start, match, length);
1458	n/a	do {
1459	n/a	fprintf(stderr, "%c%c", s->window[match++], s->window[start++]);
1460	n/a	} while (--length != 0);
1461	n/a	z_error("invalid match");
1462	n/a	}
1463	n/a	if (z_verbose > 1) {
1464	n/a	fprintf(stderr,"\\[%d,%d]", start-match, length);
1465	n/a	do { putc(s->window[start++], stderr); } while (--length != 0);
1466	n/a	}
1467	n/a	}
1468	n/a	#else
1469	n/a	# define check_match(s, start, match, length)
1470	n/a	#endif /* ZLIB_DEBUG */
1471	n/a
1472	n/a	/* ===========================================================================
1473	n/a	* Fill the window when the lookahead becomes insufficient.
1474	n/a	* Updates strstart and lookahead.
1475	n/a	*
1476	n/a	* IN assertion: lookahead < MIN_LOOKAHEAD
1477	n/a	* OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
1478	n/a	* At least one byte has been read, or avail_in == 0; reads are
1479	n/a	* performed for at least two bytes (required for the zip translate_eol
1480	n/a	* option -- not supported here).
1481	n/a	*/
1482	n/a	local void fill_window(s)
1483	n/a	deflate_state *s;
1484	n/a	{
1485	n/a	unsigned n;
1486	n/a	unsigned more; /* Amount of free space at the end of the window. */
1487	n/a	uInt wsize = s->w_size;
1488	n/a
1489	n/a	Assert(s->lookahead < MIN_LOOKAHEAD, "already enough lookahead");
1490	n/a
1491	n/a	do {
1492	n/a	more = (unsigned)(s->window_size -(ulg)s->lookahead -(ulg)s->strstart);
1493	n/a
1494	n/a	/* Deal with !@#$% 64K limit: */
1495	n/a	if (sizeof(int) <= 2) {
1496	n/a	if (more == 0 && s->strstart == 0 && s->lookahead == 0) {
1497	n/a	more = wsize;
1498	n/a
1499	n/a	} else if (more == (unsigned)(-1)) {
1500	n/a	/* Very unlikely, but possible on 16 bit machine if
1501	n/a	* strstart == 0 && lookahead == 1 (input done a byte at time)
1502	n/a	*/
1503	n/a	more--;
1504	n/a	}
1505	n/a	}
1506	n/a
1507	n/a	/* If the window is almost full and there is insufficient lookahead,
1508	n/a	* move the upper half to the lower one to make room in the upper half.
1509	n/a	*/
1510	n/a	if (s->strstart >= wsize+MAX_DIST(s)) {
1511	n/a
1512	n/a	zmemcpy(s->window, s->window+wsize, (unsigned)wsize - more);
1513	n/a	s->match_start -= wsize;
1514	n/a	s->strstart -= wsize; /* we now have strstart >= MAX_DIST */
1515	n/a	s->block_start -= (long) wsize;
1516	n/a	slide_hash(s);
1517	n/a	more += wsize;
1518	n/a	}
1519	n/a	if (s->strm->avail_in == 0) break;
1520	n/a
1521	n/a	/* If there was no sliding:
1522	n/a	* strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
1523	n/a	* more == window_size - lookahead - strstart
1524	n/a	* => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
1525	n/a	* => more >= window_size - 2*WSIZE + 2
1526	n/a	* In the BIG_MEM or MMAP case (not yet supported),
1527	n/a	* window_size == input_size + MIN_LOOKAHEAD &&
1528	n/a	* strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
1529	n/a	* Otherwise, window_size == 2*WSIZE so more >= 2.
1530	n/a	* If there was sliding, more >= WSIZE. So in all cases, more >= 2.
1531	n/a	*/
1532	n/a	Assert(more >= 2, "more < 2");
1533	n/a
1534	n/a	n = read_buf(s->strm, s->window + s->strstart + s->lookahead, more);
1535	n/a	s->lookahead += n;
1536	n/a
1537	n/a	/* Initialize the hash value now that we have some input: */
1538	n/a	if (s->lookahead + s->insert >= MIN_MATCH) {
1539	n/a	uInt str = s->strstart - s->insert;
1540	n/a	s->ins_h = s->window[str];
1541	n/a	UPDATE_HASH(s, s->ins_h, s->window[str + 1]);
1542	n/a	#if MIN_MATCH != 3
1543	n/a	Call UPDATE_HASH() MIN_MATCH-3 more times
1544	n/a	#endif
1545	n/a	while (s->insert) {
1546	n/a	UPDATE_HASH(s, s->ins_h, s->window[str + MIN_MATCH-1]);
1547	n/a	#ifndef FASTEST
1548	n/a	s->prev[str & s->w_mask] = s->head[s->ins_h];
1549	n/a	#endif
1550	n/a	s->head[s->ins_h] = (Pos)str;
1551	n/a	str++;
1552	n/a	s->insert--;
1553	n/a	if (s->lookahead + s->insert < MIN_MATCH)
1554	n/a	break;
1555	n/a	}
1556	n/a	}
1557	n/a	/* If the whole input has less than MIN_MATCH bytes, ins_h is garbage,
1558	n/a	* but this is not important since only literal bytes will be emitted.
1559	n/a	*/
1560	n/a
1561	n/a	} while (s->lookahead < MIN_LOOKAHEAD && s->strm->avail_in != 0);
1562	n/a
1563	n/a	/* If the WIN_INIT bytes after the end of the current data have never been
1564	n/a	* written, then zero those bytes in order to avoid memory check reports of
1565	n/a	* the use of uninitialized (or uninitialised as Julian writes) bytes by
1566	n/a	* the longest match routines. Update the high water mark for the next
1567	n/a	* time through here. WIN_INIT is set to MAX_MATCH since the longest match
1568	n/a	* routines allow scanning to strstart + MAX_MATCH, ignoring lookahead.
1569	n/a	*/
1570	n/a	if (s->high_water < s->window_size) {
1571	n/a	ulg curr = s->strstart + (ulg)(s->lookahead);
1572	n/a	ulg init;
1573	n/a
1574	n/a	if (s->high_water < curr) {
1575	n/a	/* Previous high water mark below current data -- zero WIN_INIT
1576	n/a	* bytes or up to end of window, whichever is less.
1577	n/a	*/
1578	n/a	init = s->window_size - curr;
1579	n/a	if (init > WIN_INIT)
1580	n/a	init = WIN_INIT;
1581	n/a	zmemzero(s->window + curr, (unsigned)init);
1582	n/a	s->high_water = curr + init;
1583	n/a	}
1584	n/a	else if (s->high_water < (ulg)curr + WIN_INIT) {
1585	n/a	/* High water mark at or above current data, but below current data
1586	n/a	* plus WIN_INIT -- zero out to current data plus WIN_INIT, or up
1587	n/a	* to end of window, whichever is less.
1588	n/a	*/
1589	n/a	init = (ulg)curr + WIN_INIT - s->high_water;
1590	n/a	if (init > s->window_size - s->high_water)
1591	n/a	init = s->window_size - s->high_water;
1592	n/a	zmemzero(s->window + s->high_water, (unsigned)init);
1593	n/a	s->high_water += init;
1594	n/a	}
1595	n/a	}
1596	n/a
1597	n/a	Assert((ulg)s->strstart <= s->window_size - MIN_LOOKAHEAD,
1598	n/a	"not enough room for search");
1599	n/a	}
1600	n/a
1601	n/a	/* ===========================================================================
1602	n/a	* Flush the current block, with given end-of-file flag.
1603	n/a	* IN assertion: strstart is set to the end of the current match.
1604	n/a	*/
1605	n/a	#define FLUSH_BLOCK_ONLY(s, last) { \
1606	n/a	_tr_flush_block(s, (s->block_start >= 0L ? \
1607	n/a	(charf *)&s->window[(unsigned)s->block_start] : \
1608	n/a	(charf *)Z_NULL), \
1609	n/a	(ulg)((long)s->strstart - s->block_start), \
1610	n/a	(last)); \
1611	n/a	s->block_start = s->strstart; \
1612	n/a	flush_pending(s->strm); \
1613	n/a	Tracev((stderr,"[FLUSH]")); \
1614	n/a	}
1615	n/a
1616	n/a	/* Same but force premature exit if necessary. */
1617	n/a	#define FLUSH_BLOCK(s, last) { \
1618	n/a	FLUSH_BLOCK_ONLY(s, last); \
1619	n/a	if (s->strm->avail_out == 0) return (last) ? finish_started : need_more; \
1620	n/a	}
1621	n/a
1622	n/a	/* Maximum stored block length in deflate format (not including header). */
1623	n/a	#define MAX_STORED 65535
1624	n/a
1625	n/a	/* Minimum of a and b. */
1626	n/a	#define MIN(a, b) ((a) > (b) ? (b) : (a))
1627	n/a
1628	n/a	/* ===========================================================================
1629	n/a	* Copy without compression as much as possible from the input stream, return
1630	n/a	* the current block state.
1631	n/a	*
1632	n/a	* In case deflateParams() is used to later switch to a non-zero compression
1633	n/a	* level, s->matches (otherwise unused when storing) keeps track of the number
1634	n/a	* of hash table slides to perform. If s->matches is 1, then one hash table
1635	n/a	* slide will be done when switching. If s->matches is 2, the maximum value
1636	n/a	* allowed here, then the hash table will be cleared, since two or more slides
1637	n/a	* is the same as a clear.
1638	n/a	*
1639	n/a	* deflate_stored() is written to minimize the number of times an input byte is
1640	n/a	* copied. It is most efficient with large input and output buffers, which
1641	n/a	* maximizes the opportunites to have a single copy from next_in to next_out.
1642	n/a	*/
1643	n/a	local block_state deflate_stored(s, flush)
1644	n/a	deflate_state *s;
1645	n/a	int flush;
1646	n/a	{
1647	n/a	/* Smallest worthy block size when not flushing or finishing. By default
1648	n/a	* this is 32K. This can be as small as 507 bytes for memLevel == 1. For
1649	n/a	* large input and output buffers, the stored block size will be larger.
1650	n/a	*/
1651	n/a	unsigned min_block = MIN(s->pending_buf_size - 5, s->w_size);
1652	n/a
1653	n/a	/* Copy as many min_block or larger stored blocks directly to next_out as
1654	n/a	* possible. If flushing, copy the remaining available input to next_out as
1655	n/a	* stored blocks, if there is enough space.
1656	n/a	*/
1657	n/a	unsigned len, left, have, last = 0;
1658	n/a	unsigned used = s->strm->avail_in;
1659	n/a	do {
1660	n/a	/* Set len to the maximum size block that we can copy directly with the
1661	n/a	* available input data and output space. Set left to how much of that
1662	n/a	* would be copied from what's left in the window.
1663	n/a	*/
1664	n/a	len = MAX_STORED; /* maximum deflate stored block length */
1665	n/a	have = (s->bi_valid + 42) >> 3; /* number of header bytes */
1666	n/a	if (s->strm->avail_out < have) /* need room for header */
1667	n/a	break;
1668	n/a	/* maximum stored block length that will fit in avail_out: */
1669	n/a	have = s->strm->avail_out - have;
1670	n/a	left = s->strstart - s->block_start; /* bytes left in window */
1671	n/a	if (len > (ulg)left + s->strm->avail_in)
1672	n/a	len = left + s->strm->avail_in; /* limit len to the input */
1673	n/a	if (len > have)
1674	n/a	len = have; /* limit len to the output */
1675	n/a
1676	n/a	/* If the stored block would be less than min_block in length, or if
1677	n/a	* unable to copy all of the available input when flushing, then try
1678	n/a	* copying to the window and the pending buffer instead. Also don't
1679	n/a	* write an empty block when flushing -- deflate() does that.
1680	n/a	*/
1681	n/a	if (len < min_block && ((len == 0 && flush != Z_FINISH) \|\|
1682	n/a	flush == Z_NO_FLUSH \|\|
1683	n/a	len != left + s->strm->avail_in))
1684	n/a	break;
1685	n/a
1686	n/a	/* Make a dummy stored block in pending to get the header bytes,
1687	n/a	* including any pending bits. This also updates the debugging counts.
1688	n/a	*/
1689	n/a	last = flush == Z_FINISH && len == left + s->strm->avail_in ? 1 : 0;
1690	n/a	_tr_stored_block(s, (char *)0, 0L, last);
1691	n/a
1692	n/a	/* Replace the lengths in the dummy stored block with len. */
1693	n/a	s->pending_buf[s->pending - 4] = len;
1694	n/a	s->pending_buf[s->pending - 3] = len >> 8;
1695	n/a	s->pending_buf[s->pending - 2] = ~len;
1696	n/a	s->pending_buf[s->pending - 1] = ~len >> 8;
1697	n/a
1698	n/a	/* Write the stored block header bytes. */
1699	n/a	flush_pending(s->strm);
1700	n/a
1701	n/a	#ifdef ZLIB_DEBUG
1702	n/a	/* Update debugging counts for the data about to be copied. */
1703	n/a	s->compressed_len += len << 3;
1704	n/a	s->bits_sent += len << 3;
1705	n/a	#endif
1706	n/a
1707	n/a	/* Copy uncompressed bytes from the window to next_out. */
1708	n/a	if (left) {
1709	n/a	if (left > len)
1710	n/a	left = len;
1711	n/a	zmemcpy(s->strm->next_out, s->window + s->block_start, left);
1712	n/a	s->strm->next_out += left;
1713	n/a	s->strm->avail_out -= left;
1714	n/a	s->strm->total_out += left;
1715	n/a	s->block_start += left;
1716	n/a	len -= left;
1717	n/a	}
1718	n/a
1719	n/a	/* Copy uncompressed bytes directly from next_in to next_out, updating
1720	n/a	* the check value.
1721	n/a	*/
1722	n/a	if (len) {
1723	n/a	read_buf(s->strm, s->strm->next_out, len);
1724	n/a	s->strm->next_out += len;
1725	n/a	s->strm->avail_out -= len;
1726	n/a	s->strm->total_out += len;
1727	n/a	}
1728	n/a	} while (last == 0);
1729	n/a
1730	n/a	/* Update the sliding window with the last s->w_size bytes of the copied
1731	n/a	* data, or append all of the copied data to the existing window if less
1732	n/a	* than s->w_size bytes were copied. Also update the number of bytes to
1733	n/a	* insert in the hash tables, in the event that deflateParams() switches to
1734	n/a	* a non-zero compression level.
1735	n/a	*/
1736	n/a	used -= s->strm->avail_in; /* number of input bytes directly copied */
1737	n/a	if (used) {
1738	n/a	/* If any input was used, then no unused input remains in the window,
1739	n/a	* therefore s->block_start == s->strstart.
1740	n/a	*/
1741	n/a	if (used >= s->w_size) { /* supplant the previous history */
1742	n/a	s->matches = 2; /* clear hash */
1743	n/a	zmemcpy(s->window, s->strm->next_in - s->w_size, s->w_size);
1744	n/a	s->strstart = s->w_size;
1745	n/a	}
1746	n/a	else {
1747	n/a	if (s->window_size - s->strstart <= used) {
1748	n/a	/* Slide the window down. */
1749	n/a	s->strstart -= s->w_size;
1750	n/a	zmemcpy(s->window, s->window + s->w_size, s->strstart);
1751	n/a	if (s->matches < 2)
1752	n/a	s->matches++; /* add a pending slide_hash() */
1753	n/a	}
1754	n/a	zmemcpy(s->window + s->strstart, s->strm->next_in - used, used);
1755	n/a	s->strstart += used;
1756	n/a	}
1757	n/a	s->block_start = s->strstart;
1758	n/a	s->insert += MIN(used, s->w_size - s->insert);
1759	n/a	}
1760	n/a	if (s->high_water < s->strstart)
1761	n/a	s->high_water = s->strstart;
1762	n/a
1763	n/a	/* If the last block was written to next_out, then done. */
1764	n/a	if (last)
1765	n/a	return finish_done;
1766	n/a
1767	n/a	/* If flushing and all input has been consumed, then done. */
1768	n/a	if (flush != Z_NO_FLUSH && flush != Z_FINISH &&
1769	n/a	s->strm->avail_in == 0 && (long)s->strstart == s->block_start)
1770	n/a	return block_done;
1771	n/a
1772	n/a	/* Fill the window with any remaining input. */
1773	n/a	have = s->window_size - s->strstart - 1;
1774	n/a	if (s->strm->avail_in > have && s->block_start >= (long)s->w_size) {
1775	n/a	/* Slide the window down. */
1776	n/a	s->block_start -= s->w_size;
1777	n/a	s->strstart -= s->w_size;
1778	n/a	zmemcpy(s->window, s->window + s->w_size, s->strstart);
1779	n/a	if (s->matches < 2)
1780	n/a	s->matches++; /* add a pending slide_hash() */
1781	n/a	have += s->w_size; /* more space now */
1782	n/a	}
1783	n/a	if (have > s->strm->avail_in)
1784	n/a	have = s->strm->avail_in;
1785	n/a	if (have) {
1786	n/a	read_buf(s->strm, s->window + s->strstart, have);
1787	n/a	s->strstart += have;
1788	n/a	}
1789	n/a	if (s->high_water < s->strstart)
1790	n/a	s->high_water = s->strstart;
1791	n/a
1792	n/a	/* There was not enough avail_out to write a complete worthy or flushed
1793	n/a	* stored block to next_out. Write a stored block to pending instead, if we
1794	n/a	* have enough input for a worthy block, or if flushing and there is enough
1795	n/a	* room for the remaining input as a stored block in the pending buffer.
1796	n/a	*/
1797	n/a	have = (s->bi_valid + 42) >> 3; /* number of header bytes */
1798	n/a	/* maximum stored block length that will fit in pending: */
1799	n/a	have = MIN(s->pending_buf_size - have, MAX_STORED);
1800	n/a	min_block = MIN(have, s->w_size);
1801	n/a	left = s->strstart - s->block_start;
1802	n/a	if (left >= min_block \|\|
1803	n/a	((left \|\| flush == Z_FINISH) && flush != Z_NO_FLUSH &&
1804	n/a	s->strm->avail_in == 0 && left <= have)) {
1805	n/a	len = MIN(left, have);
1806	n/a	last = flush == Z_FINISH && s->strm->avail_in == 0 &&
1807	n/a	len == left ? 1 : 0;
1808	n/a	_tr_stored_block(s, (charf *)s->window + s->block_start, len, last);
1809	n/a	s->block_start += len;
1810	n/a	flush_pending(s->strm);
1811	n/a	}
1812	n/a
1813	n/a	/* We've done all we can with the available input and output. */
1814	n/a	return last ? finish_started : need_more;
1815	n/a	}
1816	n/a
1817	n/a	/* ===========================================================================
1818	n/a	* Compress as much as possible from the input stream, return the current
1819	n/a	* block state.
1820	n/a	* This function does not perform lazy evaluation of matches and inserts
1821	n/a	* new strings in the dictionary only for unmatched strings or for short
1822	n/a	* matches. It is used only for the fast compression options.
1823	n/a	*/
1824	n/a	local block_state deflate_fast(s, flush)
1825	n/a	deflate_state *s;
1826	n/a	int flush;
1827	n/a	{
1828	n/a	IPos hash_head; /* head of the hash chain */
1829	n/a	int bflush; /* set if current block must be flushed */
1830	n/a
1831	n/a	for (;;) {
1832	n/a	/* Make sure that we always have enough lookahead, except
1833	n/a	* at the end of the input file. We need MAX_MATCH bytes
1834	n/a	* for the next match, plus MIN_MATCH bytes to insert the
1835	n/a	* string following the next match.
1836	n/a	*/
1837	n/a	if (s->lookahead < MIN_LOOKAHEAD) {
1838	n/a	fill_window(s);
1839	n/a	if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1840	n/a	return need_more;
1841	n/a	}
1842	n/a	if (s->lookahead == 0) break; /* flush the current block */
1843	n/a	}
1844	n/a
1845	n/a	/* Insert the string window[strstart .. strstart+2] in the
1846	n/a	* dictionary, and set hash_head to the head of the hash chain:
1847	n/a	*/
1848	n/a	hash_head = NIL;
1849	n/a	if (s->lookahead >= MIN_MATCH) {
1850	n/a	INSERT_STRING(s, s->strstart, hash_head);
1851	n/a	}
1852	n/a
1853	n/a	/* Find the longest match, discarding those <= prev_length.
1854	n/a	* At this point we have always match_length < MIN_MATCH
1855	n/a	*/
1856	n/a	if (hash_head != NIL && s->strstart - hash_head <= MAX_DIST(s)) {
1857	n/a	/* To simplify the code, we prevent matches with the string
1858	n/a	* of window index 0 (in particular we have to avoid a match
1859	n/a	* of the string with itself at the start of the input file).
1860	n/a	*/
1861	n/a	s->match_length = longest_match (s, hash_head);
1862	n/a	/* longest_match() sets match_start */
1863	n/a	}
1864	n/a	if (s->match_length >= MIN_MATCH) {
1865	n/a	check_match(s, s->strstart, s->match_start, s->match_length);
1866	n/a
1867	n/a	_tr_tally_dist(s, s->strstart - s->match_start,
1868	n/a	s->match_length - MIN_MATCH, bflush);
1869	n/a
1870	n/a	s->lookahead -= s->match_length;
1871	n/a
1872	n/a	/* Insert new strings in the hash table only if the match length
1873	n/a	* is not too large. This saves time but degrades compression.
1874	n/a	*/
1875	n/a	#ifndef FASTEST
1876	n/a	if (s->match_length <= s->max_insert_length &&
1877	n/a	s->lookahead >= MIN_MATCH) {
1878	n/a	s->match_length--; /* string at strstart already in table */
1879	n/a	do {
1880	n/a	s->strstart++;
1881	n/a	INSERT_STRING(s, s->strstart, hash_head);
1882	n/a	/* strstart never exceeds WSIZE-MAX_MATCH, so there are
1883	n/a	* always MIN_MATCH bytes ahead.
1884	n/a	*/
1885	n/a	} while (--s->match_length != 0);
1886	n/a	s->strstart++;
1887	n/a	} else
1888	n/a	#endif
1889	n/a	{
1890	n/a	s->strstart += s->match_length;
1891	n/a	s->match_length = 0;
1892	n/a	s->ins_h = s->window[s->strstart];
1893	n/a	UPDATE_HASH(s, s->ins_h, s->window[s->strstart+1]);
1894	n/a	#if MIN_MATCH != 3
1895	n/a	Call UPDATE_HASH() MIN_MATCH-3 more times
1896	n/a	#endif
1897	n/a	/* If lookahead < MIN_MATCH, ins_h is garbage, but it does not
1898	n/a	* matter since it will be recomputed at next deflate call.
1899	n/a	*/
1900	n/a	}
1901	n/a	} else {
1902	n/a	/* No match, output a literal byte */
1903	n/a	Tracevv((stderr,"%c", s->window[s->strstart]));
1904	n/a	_tr_tally_lit (s, s->window[s->strstart], bflush);
1905	n/a	s->lookahead--;
1906	n/a	s->strstart++;
1907	n/a	}
1908	n/a	if (bflush) FLUSH_BLOCK(s, 0);
1909	n/a	}
1910	n/a	s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
1911	n/a	if (flush == Z_FINISH) {
1912	n/a	FLUSH_BLOCK(s, 1);
1913	n/a	return finish_done;
1914	n/a	}
1915	n/a	if (s->last_lit)
1916	n/a	FLUSH_BLOCK(s, 0);
1917	n/a	return block_done;
1918	n/a	}
1919	n/a
1920	n/a	#ifndef FASTEST
1921	n/a	/* ===========================================================================
1922	n/a	* Same as above, but achieves better compression. We use a lazy
1923	n/a	* evaluation for matches: a match is finally adopted only if there is
1924	n/a	* no better match at the next window position.
1925	n/a	*/
1926	n/a	local block_state deflate_slow(s, flush)
1927	n/a	deflate_state *s;
1928	n/a	int flush;
1929	n/a	{
1930	n/a	IPos hash_head; /* head of hash chain */
1931	n/a	int bflush; /* set if current block must be flushed */
1932	n/a
1933	n/a	/* Process the input block. */
1934	n/a	for (;;) {
1935	n/a	/* Make sure that we always have enough lookahead, except
1936	n/a	* at the end of the input file. We need MAX_MATCH bytes
1937	n/a	* for the next match, plus MIN_MATCH bytes to insert the
1938	n/a	* string following the next match.
1939	n/a	*/
1940	n/a	if (s->lookahead < MIN_LOOKAHEAD) {
1941	n/a	fill_window(s);
1942	n/a	if (s->lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
1943	n/a	return need_more;
1944	n/a	}
1945	n/a	if (s->lookahead == 0) break; /* flush the current block */
1946	n/a	}
1947	n/a
1948	n/a	/* Insert the string window[strstart .. strstart+2] in the
1949	n/a	* dictionary, and set hash_head to the head of the hash chain:
1950	n/a	*/
1951	n/a	hash_head = NIL;
1952	n/a	if (s->lookahead >= MIN_MATCH) {
1953	n/a	INSERT_STRING(s, s->strstart, hash_head);
1954	n/a	}
1955	n/a
1956	n/a	/* Find the longest match, discarding those <= prev_length.
1957	n/a	*/
1958	n/a	s->prev_length = s->match_length, s->prev_match = s->match_start;
1959	n/a	s->match_length = MIN_MATCH-1;
1960	n/a
1961	n/a	if (hash_head != NIL && s->prev_length < s->max_lazy_match &&
1962	n/a	s->strstart - hash_head <= MAX_DIST(s)) {
1963	n/a	/* To simplify the code, we prevent matches with the string
1964	n/a	* of window index 0 (in particular we have to avoid a match
1965	n/a	* of the string with itself at the start of the input file).
1966	n/a	*/
1967	n/a	s->match_length = longest_match (s, hash_head);
1968	n/a	/* longest_match() sets match_start */
1969	n/a
1970	n/a	if (s->match_length <= 5 && (s->strategy == Z_FILTERED
1971	n/a	#if TOO_FAR <= 32767
1972	n/a	\|\| (s->match_length == MIN_MATCH &&
1973	n/a	s->strstart - s->match_start > TOO_FAR)
1974	n/a	#endif
1975	n/a	)) {
1976	n/a
1977	n/a	/* If prev_match is also MIN_MATCH, match_start is garbage
1978	n/a	* but we will ignore the current match anyway.
1979	n/a	*/
1980	n/a	s->match_length = MIN_MATCH-1;
1981	n/a	}
1982	n/a	}
1983	n/a	/* If there was a match at the previous step and the current
1984	n/a	* match is not better, output the previous match:
1985	n/a	*/
1986	n/a	if (s->prev_length >= MIN_MATCH && s->match_length <= s->prev_length) {
1987	n/a	uInt max_insert = s->strstart + s->lookahead - MIN_MATCH;
1988	n/a	/* Do not insert strings in hash table beyond this. */
1989	n/a
1990	n/a	check_match(s, s->strstart-1, s->prev_match, s->prev_length);
1991	n/a
1992	n/a	_tr_tally_dist(s, s->strstart -1 - s->prev_match,
1993	n/a	s->prev_length - MIN_MATCH, bflush);
1994	n/a
1995	n/a	/* Insert in hash table all strings up to the end of the match.
1996	n/a	* strstart-1 and strstart are already inserted. If there is not
1997	n/a	* enough lookahead, the last two strings are not inserted in
1998	n/a	* the hash table.
1999	n/a	*/
2000	n/a	s->lookahead -= s->prev_length-1;
2001	n/a	s->prev_length -= 2;
2002	n/a	do {
2003	n/a	if (++s->strstart <= max_insert) {
2004	n/a	INSERT_STRING(s, s->strstart, hash_head);
2005	n/a	}
2006	n/a	} while (--s->prev_length != 0);
2007	n/a	s->match_available = 0;
2008	n/a	s->match_length = MIN_MATCH-1;
2009	n/a	s->strstart++;
2010	n/a
2011	n/a	if (bflush) FLUSH_BLOCK(s, 0);
2012	n/a
2013	n/a	} else if (s->match_available) {
2014	n/a	/* If there was no match at the previous position, output a
2015	n/a	* single literal. If there was a match but the current match
2016	n/a	* is longer, truncate the previous match to a single literal.
2017	n/a	*/
2018	n/a	Tracevv((stderr,"%c", s->window[s->strstart-1]));
2019	n/a	_tr_tally_lit(s, s->window[s->strstart-1], bflush);
2020	n/a	if (bflush) {
2021	n/a	FLUSH_BLOCK_ONLY(s, 0);
2022	n/a	}
2023	n/a	s->strstart++;
2024	n/a	s->lookahead--;
2025	n/a	if (s->strm->avail_out == 0) return need_more;
2026	n/a	} else {
2027	n/a	/* There is no previous match to compare with, wait for
2028	n/a	* the next step to decide.
2029	n/a	*/
2030	n/a	s->match_available = 1;
2031	n/a	s->strstart++;
2032	n/a	s->lookahead--;
2033	n/a	}
2034	n/a	}
2035	n/a	Assert (flush != Z_NO_FLUSH, "no flush?");
2036	n/a	if (s->match_available) {
2037	n/a	Tracevv((stderr,"%c", s->window[s->strstart-1]));
2038	n/a	_tr_tally_lit(s, s->window[s->strstart-1], bflush);
2039	n/a	s->match_available = 0;
2040	n/a	}
2041	n/a	s->insert = s->strstart < MIN_MATCH-1 ? s->strstart : MIN_MATCH-1;
2042	n/a	if (flush == Z_FINISH) {
2043	n/a	FLUSH_BLOCK(s, 1);
2044	n/a	return finish_done;
2045	n/a	}
2046	n/a	if (s->last_lit)
2047	n/a	FLUSH_BLOCK(s, 0);
2048	n/a	return block_done;
2049	n/a	}
2050	n/a	#endif /* FASTEST */
2051	n/a
2052	n/a	/* ===========================================================================
2053	n/a	* For Z_RLE, simply look for runs of bytes, generate matches only of distance
2054	n/a	* one. Do not maintain a hash table. (It will be regenerated if this run of
2055	n/a	* deflate switches away from Z_RLE.)
2056	n/a	*/
2057	n/a	local block_state deflate_rle(s, flush)
2058	n/a	deflate_state *s;
2059	n/a	int flush;
2060	n/a	{
2061	n/a	int bflush; /* set if current block must be flushed */
2062	n/a	uInt prev; /* byte at distance one to match */
2063	n/a	Bytef scan, strend; /* scan goes up to strend for length of run */
2064	n/a
2065	n/a	for (;;) {
2066	n/a	/* Make sure that we always have enough lookahead, except
2067	n/a	* at the end of the input file. We need MAX_MATCH bytes
2068	n/a	* for the longest run, plus one for the unrolled loop.
2069	n/a	*/
2070	n/a	if (s->lookahead <= MAX_MATCH) {
2071	n/a	fill_window(s);
2072	n/a	if (s->lookahead <= MAX_MATCH && flush == Z_NO_FLUSH) {
2073	n/a	return need_more;
2074	n/a	}
2075	n/a	if (s->lookahead == 0) break; /* flush the current block */
2076	n/a	}
2077	n/a
2078	n/a	/* See how many times the previous byte repeats */
2079	n/a	s->match_length = 0;
2080	n/a	if (s->lookahead >= MIN_MATCH && s->strstart > 0) {
2081	n/a	scan = s->window + s->strstart - 1;
2082	n/a	prev = *scan;
2083	n/a	if (prev == ++scan && prev == ++scan && prev == *++scan) {
2084	n/a	strend = s->window + s->strstart + MAX_MATCH;
2085	n/a	do {
2086	n/a	} while (prev == ++scan && prev == ++scan &&
2087	n/a	prev == ++scan && prev == ++scan &&
2088	n/a	prev == ++scan && prev == ++scan &&
2089	n/a	prev == ++scan && prev == ++scan &&
2090	n/a	scan < strend);
2091	n/a	s->match_length = MAX_MATCH - (uInt)(strend - scan);
2092	n/a	if (s->match_length > s->lookahead)
2093	n/a	s->match_length = s->lookahead;
2094	n/a	}
2095	n/a	Assert(scan <= s->window+(uInt)(s->window_size-1), "wild scan");
2096	n/a	}
2097	n/a
2098	n/a	/* Emit match if have run of MIN_MATCH or longer, else emit literal */
2099	n/a	if (s->match_length >= MIN_MATCH) {
2100	n/a	check_match(s, s->strstart, s->strstart - 1, s->match_length);
2101	n/a
2102	n/a	_tr_tally_dist(s, 1, s->match_length - MIN_MATCH, bflush);
2103	n/a
2104	n/a	s->lookahead -= s->match_length;
2105	n/a	s->strstart += s->match_length;
2106	n/a	s->match_length = 0;
2107	n/a	} else {
2108	n/a	/* No match, output a literal byte */
2109	n/a	Tracevv((stderr,"%c", s->window[s->strstart]));
2110	n/a	_tr_tally_lit (s, s->window[s->strstart], bflush);
2111	n/a	s->lookahead--;
2112	n/a	s->strstart++;
2113	n/a	}
2114	n/a	if (bflush) FLUSH_BLOCK(s, 0);
2115	n/a	}
2116	n/a	s->insert = 0;
2117	n/a	if (flush == Z_FINISH) {
2118	n/a	FLUSH_BLOCK(s, 1);
2119	n/a	return finish_done;
2120	n/a	}
2121	n/a	if (s->last_lit)
2122	n/a	FLUSH_BLOCK(s, 0);
2123	n/a	return block_done;
2124	n/a	}
2125	n/a
2126	n/a	/* ===========================================================================
2127	n/a	* For Z_HUFFMAN_ONLY, do not look for matches. Do not maintain a hash table.
2128	n/a	* (It will be regenerated if this run of deflate switches away from Huffman.)
2129	n/a	*/
2130	n/a	local block_state deflate_huff(s, flush)
2131	n/a	deflate_state *s;
2132	n/a	int flush;
2133	n/a	{
2134	n/a	int bflush; /* set if current block must be flushed */
2135	n/a
2136	n/a	for (;;) {
2137	n/a	/* Make sure that we have a literal to write. */
2138	n/a	if (s->lookahead == 0) {
2139	n/a	fill_window(s);
2140	n/a	if (s->lookahead == 0) {
2141	n/a	if (flush == Z_NO_FLUSH)
2142	n/a	return need_more;
2143	n/a	break; /* flush the current block */
2144	n/a	}
2145	n/a	}
2146	n/a
2147	n/a	/* Output a literal byte */
2148	n/a	s->match_length = 0;
2149	n/a	Tracevv((stderr,"%c", s->window[s->strstart]));
2150	n/a	_tr_tally_lit (s, s->window[s->strstart], bflush);
2151	n/a	s->lookahead--;
2152	n/a	s->strstart++;
2153	n/a	if (bflush) FLUSH_BLOCK(s, 0);
2154	n/a	}
2155	n/a	s->insert = 0;
2156	n/a	if (flush == Z_FINISH) {
2157	n/a	FLUSH_BLOCK(s, 1);
2158	n/a	return finish_done;
2159	n/a	}
2160	n/a	if (s->last_lit)
2161	n/a	FLUSH_BLOCK(s, 0);
2162	n/a	return block_done;
2163	n/a	}