Python code coverage for Modules/zlib/trees.c

#	count	content
1	n/a	/* trees.c -- output deflated data using Huffman coding
2	n/a	* Copyright (C) 1995-2017 Jean-loup Gailly
3	n/a	* detect_data_type() function provided freely by Cosmin Truta, 2006
4	n/a	* For conditions of distribution and use, see copyright notice in zlib.h
5	n/a	*/
6	n/a
7	n/a	/*
8	n/a	* ALGORITHM
9	n/a	*
10	n/a	* The "deflation" process uses several Huffman trees. The more
11	n/a	* common source values are represented by shorter bit sequences.
12	n/a	*
13	n/a	* Each code tree is stored in a compressed form which is itself
14	n/a	* a Huffman encoding of the lengths of all the code strings (in
15	n/a	* ascending order by source values). The actual code strings are
16	n/a	* reconstructed from the lengths in the inflate process, as described
17	n/a	* in the deflate specification.
18	n/a	*
19	n/a	* REFERENCES
20	n/a	*
21	n/a	* Deutsch, L.P.,"'Deflate' Compressed Data Format Specification".
22	n/a	* Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
23	n/a	*
24	n/a	* Storer, James A.
25	n/a	* Data Compression: Methods and Theory, pp. 49-50.
26	n/a	* Computer Science Press, 1988. ISBN 0-7167-8156-5.
27	n/a	*
28	n/a	* Sedgewick, R.
29	n/a	* Algorithms, p290.
30	n/a	* Addison-Wesley, 1983. ISBN 0-201-06672-6.
31	n/a	*/
32	n/a
33	n/a	/* @(#) $Id$ */
34	n/a
35	n/a	/* #define GEN_TREES_H */
36	n/a
37	n/a	#include "deflate.h"
38	n/a
39	n/a	#ifdef ZLIB_DEBUG
40	n/a	# include <ctype.h>
41	n/a	#endif
42	n/a
43	n/a	/* ===========================================================================
44	n/a	* Constants
45	n/a	*/
46	n/a
47	n/a	#define MAX_BL_BITS 7
48	n/a	/* Bit length codes must not exceed MAX_BL_BITS bits */
49	n/a
50	n/a	#define END_BLOCK 256
51	n/a	/* end of block literal code */
52	n/a
53	n/a	#define REP_3_6 16
54	n/a	/* repeat previous bit length 3-6 times (2 bits of repeat count) */
55	n/a
56	n/a	#define REPZ_3_10 17
57	n/a	/* repeat a zero length 3-10 times (3 bits of repeat count) */
58	n/a
59	n/a	#define REPZ_11_138 18
60	n/a	/* repeat a zero length 11-138 times (7 bits of repeat count) */
61	n/a
62	n/a	local const int extra_lbits[LENGTH_CODES] /* extra bits for each length code */
63	n/a	= {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
64	n/a
65	n/a	local const int extra_dbits[D_CODES] /* extra bits for each distance code */
66	n/a	= {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
67	n/a
68	n/a	local const int extra_blbits[BL_CODES]/* extra bits for each bit length code */
69	n/a	= {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
70	n/a
71	n/a	local const uch bl_order[BL_CODES]
72	n/a	= {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
73	n/a	/* The lengths of the bit length codes are sent in order of decreasing
74	n/a	* probability, to avoid transmitting the lengths for unused bit length codes.
75	n/a	*/
76	n/a
77	n/a	/* ===========================================================================
78	n/a	* Local data. These are initialized only once.
79	n/a	*/
80	n/a
81	n/a	#define DIST_CODE_LEN 512 /* see definition of array dist_code below */
82	n/a
83	n/a	#if defined(GEN_TREES_H) \|\| !defined(STDC)
84	n/a	/* non ANSI compilers may not accept trees.h */
85	n/a
86	n/a	local ct_data static_ltree[L_CODES+2];
87	n/a	/* The static literal tree. Since the bit lengths are imposed, there is no
88	n/a	* need for the L_CODES extra codes used during heap construction. However
89	n/a	* The codes 286 and 287 are needed to build a canonical tree (see _tr_init
90	n/a	* below).
91	n/a	*/
92	n/a
93	n/a	local ct_data static_dtree[D_CODES];
94	n/a	/* The static distance tree. (Actually a trivial tree since all codes use
95	n/a	* 5 bits.)
96	n/a	*/
97	n/a
98	n/a	uch _dist_code[DIST_CODE_LEN];
99	n/a	/* Distance codes. The first 256 values correspond to the distances
100	n/a	* 3 .. 258, the last 256 values correspond to the top 8 bits of
101	n/a	* the 15 bit distances.
102	n/a	*/
103	n/a
104	n/a	uch _length_code[MAX_MATCH-MIN_MATCH+1];
105	n/a	/* length code for each normalized match length (0 == MIN_MATCH) */
106	n/a
107	n/a	local int base_length[LENGTH_CODES];
108	n/a	/* First normalized length for each code (0 = MIN_MATCH) */
109	n/a
110	n/a	local int base_dist[D_CODES];
111	n/a	/* First normalized distance for each code (0 = distance of 1) */
112	n/a
113	n/a	#else
114	n/a	# include "trees.h"
115	n/a	#endif /* GEN_TREES_H */
116	n/a
117	n/a	struct static_tree_desc_s {
118	n/a	const ct_data static_tree; / static tree or NULL */
119	n/a	const intf extra_bits; / extra bits for each code or NULL */
120	n/a	int extra_base; /* base index for extra_bits */
121	n/a	int elems; /* max number of elements in the tree */
122	n/a	int max_length; /* max bit length for the codes */
123	n/a	};
124	n/a
125	n/a	local const static_tree_desc static_l_desc =
126	n/a	{static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
127	n/a
128	n/a	local const static_tree_desc static_d_desc =
129	n/a	{static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
130	n/a
131	n/a	local const static_tree_desc static_bl_desc =
132	n/a	{(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
133	n/a
134	n/a	/* ===========================================================================
135	n/a	* Local (static) routines in this file.
136	n/a	*/
137	n/a
138	n/a	local void tr_static_init OF((void));
139	n/a	local void init_block OF((deflate_state *s));
140	n/a	local void pqdownheap OF((deflate_state s, ct_data tree, int k));
141	n/a	local void gen_bitlen OF((deflate_state s, tree_desc desc));
142	n/a	local void gen_codes OF((ct_data tree, int max_code, ushf bl_count));
143	n/a	local void build_tree OF((deflate_state s, tree_desc desc));
144	n/a	local void scan_tree OF((deflate_state s, ct_data tree, int max_code));
145	n/a	local void send_tree OF((deflate_state s, ct_data tree, int max_code));
146	n/a	local int build_bl_tree OF((deflate_state *s));
147	n/a	local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
148	n/a	int blcodes));
149	n/a	local void compress_block OF((deflate_state s, const ct_data ltree,
150	n/a	const ct_data *dtree));
151	n/a	local int detect_data_type OF((deflate_state *s));
152	n/a	local unsigned bi_reverse OF((unsigned value, int length));
153	n/a	local void bi_windup OF((deflate_state *s));
154	n/a	local void bi_flush OF((deflate_state *s));
155	n/a
156	n/a	#ifdef GEN_TREES_H
157	n/a	local void gen_trees_header OF((void));
158	n/a	#endif
159	n/a
160	n/a	#ifndef ZLIB_DEBUG
161	n/a	# define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
162	n/a	/* Send a code of the given tree. c and tree must not have side effects */
163	n/a
164	n/a	#else /* !ZLIB_DEBUG */
165	n/a	# define send_code(s, c, tree) \
166	n/a	{ if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
167	n/a	send_bits(s, tree[c].Code, tree[c].Len); }
168	n/a	#endif
169	n/a
170	n/a	/* ===========================================================================
171	n/a	* Output a short LSB first on the stream.
172	n/a	* IN assertion: there is enough room in pendingBuf.
173	n/a	*/
174	n/a	#define put_short(s, w) { \
175	n/a	put_byte(s, (uch)((w) & 0xff)); \
176	n/a	put_byte(s, (uch)((ush)(w) >> 8)); \
177	n/a	}
178	n/a
179	n/a	/* ===========================================================================
180	n/a	* Send a value on a given number of bits.
181	n/a	* IN assertion: length <= 16 and value fits in length bits.
182	n/a	*/
183	n/a	#ifdef ZLIB_DEBUG
184	n/a	local void send_bits OF((deflate_state *s, int value, int length));
185	n/a
186	n/a	local void send_bits(s, value, length)
187	n/a	deflate_state *s;
188	n/a	int value; /* value to send */
189	n/a	int length; /* number of bits */
190	n/a	{
191	n/a	Tracevv((stderr," l %2d v %4x ", length, value));
192	n/a	Assert(length > 0 && length <= 15, "invalid length");
193	n/a	s->bits_sent += (ulg)length;
194	n/a
195	n/a	/* If not enough room in bi_buf, use (valid) bits from bi_buf and
196	n/a	* (16 - bi_valid) bits from value, leaving (width - (16-bi_valid))
197	n/a	* unused bits in value.
198	n/a	*/
199	n/a	if (s->bi_valid > (int)Buf_size - length) {
200	n/a	s->bi_buf \|= (ush)value << s->bi_valid;
201	n/a	put_short(s, s->bi_buf);
202	n/a	s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
203	n/a	s->bi_valid += length - Buf_size;
204	n/a	} else {
205	n/a	s->bi_buf \|= (ush)value << s->bi_valid;
206	n/a	s->bi_valid += length;
207	n/a	}
208	n/a	}
209	n/a	#else /* !ZLIB_DEBUG */
210	n/a
211	n/a	#define send_bits(s, value, length) \
212	n/a	{ int len = length;\
213	n/a	if (s->bi_valid > (int)Buf_size - len) {\
214	n/a	int val = (int)value;\
215	n/a	s->bi_buf \|= (ush)val << s->bi_valid;\
216	n/a	put_short(s, s->bi_buf);\
217	n/a	s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
218	n/a	s->bi_valid += len - Buf_size;\
219	n/a	} else {\
220	n/a	s->bi_buf \|= (ush)(value) << s->bi_valid;\
221	n/a	s->bi_valid += len;\
222	n/a	}\
223	n/a	}
224	n/a	#endif /* ZLIB_DEBUG */
225	n/a
226	n/a
227	n/a	/* the arguments must not have side effects */
228	n/a
229	n/a	/* ===========================================================================
230	n/a	* Initialize the various 'constant' tables.
231	n/a	*/
232	n/a	local void tr_static_init()
233	n/a	{
234	n/a	#if defined(GEN_TREES_H) \|\| !defined(STDC)
235	n/a	static int static_init_done = 0;
236	n/a	int n; /* iterates over tree elements */
237	n/a	int bits; /* bit counter */
238	n/a	int length; /* length value */
239	n/a	int code; /* code value */
240	n/a	int dist; /* distance index */
241	n/a	ush bl_count[MAX_BITS+1];
242	n/a	/* number of codes at each bit length for an optimal tree */
243	n/a
244	n/a	if (static_init_done) return;
245	n/a
246	n/a	/* For some embedded targets, global variables are not initialized: */
247	n/a	#ifdef NO_INIT_GLOBAL_POINTERS
248	n/a	static_l_desc.static_tree = static_ltree;
249	n/a	static_l_desc.extra_bits = extra_lbits;
250	n/a	static_d_desc.static_tree = static_dtree;
251	n/a	static_d_desc.extra_bits = extra_dbits;
252	n/a	static_bl_desc.extra_bits = extra_blbits;
253	n/a	#endif
254	n/a
255	n/a	/* Initialize the mapping length (0..255) -> length code (0..28) */
256	n/a	length = 0;
257	n/a	for (code = 0; code < LENGTH_CODES-1; code++) {
258	n/a	base_length[code] = length;
259	n/a	for (n = 0; n < (1<<extra_lbits[code]); n++) {
260	n/a	_length_code[length++] = (uch)code;
261	n/a	}
262	n/a	}
263	n/a	Assert (length == 256, "tr_static_init: length != 256");
264	n/a	/* Note that the length 255 (match length 258) can be represented
265	n/a	* in two different ways: code 284 + 5 bits or code 285, so we
266	n/a	* overwrite length_code[255] to use the best encoding:
267	n/a	*/
268	n/a	_length_code[length-1] = (uch)code;
269	n/a
270	n/a	/* Initialize the mapping dist (0..32K) -> dist code (0..29) */
271	n/a	dist = 0;
272	n/a	for (code = 0 ; code < 16; code++) {
273	n/a	base_dist[code] = dist;
274	n/a	for (n = 0; n < (1<<extra_dbits[code]); n++) {
275	n/a	_dist_code[dist++] = (uch)code;
276	n/a	}
277	n/a	}
278	n/a	Assert (dist == 256, "tr_static_init: dist != 256");
279	n/a	dist >>= 7; /* from now on, all distances are divided by 128 */
280	n/a	for ( ; code < D_CODES; code++) {
281	n/a	base_dist[code] = dist << 7;
282	n/a	for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
283	n/a	_dist_code[256 + dist++] = (uch)code;
284	n/a	}
285	n/a	}
286	n/a	Assert (dist == 256, "tr_static_init: 256+dist != 512");
287	n/a
288	n/a	/* Construct the codes of the static literal tree */
289	n/a	for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
290	n/a	n = 0;
291	n/a	while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
292	n/a	while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
293	n/a	while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
294	n/a	while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
295	n/a	/* Codes 286 and 287 do not exist, but we must include them in the
296	n/a	* tree construction to get a canonical Huffman tree (longest code
297	n/a	* all ones)
298	n/a	*/
299	n/a	gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
300	n/a
301	n/a	/* The static distance tree is trivial: */
302	n/a	for (n = 0; n < D_CODES; n++) {
303	n/a	static_dtree[n].Len = 5;
304	n/a	static_dtree[n].Code = bi_reverse((unsigned)n, 5);
305	n/a	}
306	n/a	static_init_done = 1;
307	n/a
308	n/a	# ifdef GEN_TREES_H
309	n/a	gen_trees_header();
310	n/a	# endif
311	n/a	#endif /* defined(GEN_TREES_H) \|\| !defined(STDC) */
312	n/a	}
313	n/a
314	n/a	/* ===========================================================================
315	n/a	* Genererate the file trees.h describing the static trees.
316	n/a	*/
317	n/a	#ifdef GEN_TREES_H
318	n/a	# ifndef ZLIB_DEBUG
319	n/a	# include <stdio.h>
320	n/a	# endif
321	n/a
322	n/a	# define SEPARATOR(i, last, width) \
323	n/a	((i) == (last)? "\n};\n\n" : \
324	n/a	((i) % (width) == (width)-1 ? ",\n" : ", "))
325	n/a
326	n/a	void gen_trees_header()
327	n/a	{
328	n/a	FILE *header = fopen("trees.h", "w");
329	n/a	int i;
330	n/a
331	n/a	Assert (header != NULL, "Can't open trees.h");
332	n/a	fprintf(header,
333	n/a	"/* header created automatically with -DGEN_TREES_H */\n\n");
334	n/a
335	n/a	fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
336	n/a	for (i = 0; i < L_CODES+2; i++) {
337	n/a	fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
338	n/a	static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
339	n/a	}
340	n/a
341	n/a	fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
342	n/a	for (i = 0; i < D_CODES; i++) {
343	n/a	fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
344	n/a	static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
345	n/a	}
346	n/a
347	n/a	fprintf(header, "const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
348	n/a	for (i = 0; i < DIST_CODE_LEN; i++) {
349	n/a	fprintf(header, "%2u%s", _dist_code[i],
350	n/a	SEPARATOR(i, DIST_CODE_LEN-1, 20));
351	n/a	}
352	n/a
353	n/a	fprintf(header,
354	n/a	"const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
355	n/a	for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
356	n/a	fprintf(header, "%2u%s", _length_code[i],
357	n/a	SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
358	n/a	}
359	n/a
360	n/a	fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
361	n/a	for (i = 0; i < LENGTH_CODES; i++) {
362	n/a	fprintf(header, "%1u%s", base_length[i],
363	n/a	SEPARATOR(i, LENGTH_CODES-1, 20));
364	n/a	}
365	n/a
366	n/a	fprintf(header, "local const int base_dist[D_CODES] = {\n");
367	n/a	for (i = 0; i < D_CODES; i++) {
368	n/a	fprintf(header, "%5u%s", base_dist[i],
369	n/a	SEPARATOR(i, D_CODES-1, 10));
370	n/a	}
371	n/a
372	n/a	fclose(header);
373	n/a	}
374	n/a	#endif /* GEN_TREES_H */
375	n/a
376	n/a	/* ===========================================================================
377	n/a	* Initialize the tree data structures for a new zlib stream.
378	n/a	*/
379	n/a	void ZLIB_INTERNAL _tr_init(s)
380	n/a	deflate_state *s;
381	n/a	{
382	n/a	tr_static_init();
383	n/a
384	n/a	s->l_desc.dyn_tree = s->dyn_ltree;
385	n/a	s->l_desc.stat_desc = &static_l_desc;
386	n/a
387	n/a	s->d_desc.dyn_tree = s->dyn_dtree;
388	n/a	s->d_desc.stat_desc = &static_d_desc;
389	n/a
390	n/a	s->bl_desc.dyn_tree = s->bl_tree;
391	n/a	s->bl_desc.stat_desc = &static_bl_desc;
392	n/a
393	n/a	s->bi_buf = 0;
394	n/a	s->bi_valid = 0;
395	n/a	#ifdef ZLIB_DEBUG
396	n/a	s->compressed_len = 0L;
397	n/a	s->bits_sent = 0L;
398	n/a	#endif
399	n/a
400	n/a	/* Initialize the first block of the first file: */
401	n/a	init_block(s);
402	n/a	}
403	n/a
404	n/a	/* ===========================================================================
405	n/a	* Initialize a new block.
406	n/a	*/
407	n/a	local void init_block(s)
408	n/a	deflate_state *s;
409	n/a	{
410	n/a	int n; /* iterates over tree elements */
411	n/a
412	n/a	/* Initialize the trees. */
413	n/a	for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
414	n/a	for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
415	n/a	for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
416	n/a
417	n/a	s->dyn_ltree[END_BLOCK].Freq = 1;
418	n/a	s->opt_len = s->static_len = 0L;
419	n/a	s->last_lit = s->matches = 0;
420	n/a	}
421	n/a
422	n/a	#define SMALLEST 1
423	n/a	/* Index within the heap array of least frequent node in the Huffman tree */
424	n/a
425	n/a
426	n/a	/* ===========================================================================
427	n/a	* Remove the smallest element from the heap and recreate the heap with
428	n/a	* one less element. Updates heap and heap_len.
429	n/a	*/
430	n/a	#define pqremove(s, tree, top) \
431	n/a	{\
432	n/a	top = s->heap[SMALLEST]; \
433	n/a	s->heap[SMALLEST] = s->heap[s->heap_len--]; \
434	n/a	pqdownheap(s, tree, SMALLEST); \
435	n/a	}
436	n/a
437	n/a	/* ===========================================================================
438	n/a	* Compares to subtrees, using the tree depth as tie breaker when
439	n/a	* the subtrees have equal frequency. This minimizes the worst case length.
440	n/a	*/
441	n/a	#define smaller(tree, n, m, depth) \
442	n/a	(tree[n].Freq < tree[m].Freq \|\| \
443	n/a	(tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
444	n/a
445	n/a	/* ===========================================================================
446	n/a	* Restore the heap property by moving down the tree starting at node k,
447	n/a	* exchanging a node with the smallest of its two sons if necessary, stopping
448	n/a	* when the heap property is re-established (each father smaller than its
449	n/a	* two sons).
450	n/a	*/
451	n/a	local void pqdownheap(s, tree, k)
452	n/a	deflate_state *s;
453	n/a	ct_data tree; / the tree to restore */
454	n/a	int k; /* node to move down */
455	n/a	{
456	n/a	int v = s->heap[k];
457	n/a	int j = k << 1; /* left son of k */
458	n/a	while (j <= s->heap_len) {
459	n/a	/* Set j to the smallest of the two sons: */
460	n/a	if (j < s->heap_len &&
461	n/a	smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
462	n/a	j++;
463	n/a	}
464	n/a	/* Exit if v is smaller than both sons */
465	n/a	if (smaller(tree, v, s->heap[j], s->depth)) break;
466	n/a
467	n/a	/* Exchange v with the smallest son */
468	n/a	s->heap[k] = s->heap[j]; k = j;
469	n/a
470	n/a	/* And continue down the tree, setting j to the left son of k */
471	n/a	j <<= 1;
472	n/a	}
473	n/a	s->heap[k] = v;
474	n/a	}
475	n/a
476	n/a	/* ===========================================================================
477	n/a	* Compute the optimal bit lengths for a tree and update the total bit length
478	n/a	* for the current block.
479	n/a	* IN assertion: the fields freq and dad are set, heap[heap_max] and
480	n/a	* above are the tree nodes sorted by increasing frequency.
481	n/a	* OUT assertions: the field len is set to the optimal bit length, the
482	n/a	* array bl_count contains the frequencies for each bit length.
483	n/a	* The length opt_len is updated; static_len is also updated if stree is
484	n/a	* not null.
485	n/a	*/
486	n/a	local void gen_bitlen(s, desc)
487	n/a	deflate_state *s;
488	n/a	tree_desc desc; / the tree descriptor */
489	n/a	{
490	n/a	ct_data *tree = desc->dyn_tree;
491	n/a	int max_code = desc->max_code;
492	n/a	const ct_data *stree = desc->stat_desc->static_tree;
493	n/a	const intf *extra = desc->stat_desc->extra_bits;
494	n/a	int base = desc->stat_desc->extra_base;
495	n/a	int max_length = desc->stat_desc->max_length;
496	n/a	int h; /* heap index */
497	n/a	int n, m; /* iterate over the tree elements */
498	n/a	int bits; /* bit length */
499	n/a	int xbits; /* extra bits */
500	n/a	ush f; /* frequency */
501	n/a	int overflow = 0; /* number of elements with bit length too large */
502	n/a
503	n/a	for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
504	n/a
505	n/a	/* In a first pass, compute the optimal bit lengths (which may
506	n/a	* overflow in the case of the bit length tree).
507	n/a	*/
508	n/a	tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
509	n/a
510	n/a	for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
511	n/a	n = s->heap[h];
512	n/a	bits = tree[tree[n].Dad].Len + 1;
513	n/a	if (bits > max_length) bits = max_length, overflow++;
514	n/a	tree[n].Len = (ush)bits;
515	n/a	/* We overwrite tree[n].Dad which is no longer needed */
516	n/a
517	n/a	if (n > max_code) continue; /* not a leaf node */
518	n/a
519	n/a	s->bl_count[bits]++;
520	n/a	xbits = 0;
521	n/a	if (n >= base) xbits = extra[n-base];
522	n/a	f = tree[n].Freq;
523	n/a	s->opt_len += (ulg)f * (unsigned)(bits + xbits);
524	n/a	if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits);
525	n/a	}
526	n/a	if (overflow == 0) return;
527	n/a
528	n/a	Tracev((stderr,"\nbit length overflow\n"));
529	n/a	/* This happens for example on obj2 and pic of the Calgary corpus */
530	n/a
531	n/a	/* Find the first bit length which could increase: */
532	n/a	do {
533	n/a	bits = max_length-1;
534	n/a	while (s->bl_count[bits] == 0) bits--;
535	n/a	s->bl_count[bits]--; /* move one leaf down the tree */
536	n/a	s->bl_count[bits+1] += 2; /* move one overflow item as its brother */
537	n/a	s->bl_count[max_length]--;
538	n/a	/* The brother of the overflow item also moves one step up,
539	n/a	* but this does not affect bl_count[max_length]
540	n/a	*/
541	n/a	overflow -= 2;
542	n/a	} while (overflow > 0);
543	n/a
544	n/a	/* Now recompute all bit lengths, scanning in increasing frequency.
545	n/a	* h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
546	n/a	* lengths instead of fixing only the wrong ones. This idea is taken
547	n/a	* from 'ar' written by Haruhiko Okumura.)
548	n/a	*/
549	n/a	for (bits = max_length; bits != 0; bits--) {
550	n/a	n = s->bl_count[bits];
551	n/a	while (n != 0) {
552	n/a	m = s->heap[--h];
553	n/a	if (m > max_code) continue;
554	n/a	if ((unsigned) tree[m].Len != (unsigned) bits) {
555	n/a	Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
556	n/a	s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq;
557	n/a	tree[m].Len = (ush)bits;
558	n/a	}
559	n/a	n--;
560	n/a	}
561	n/a	}
562	n/a	}
563	n/a
564	n/a	/* ===========================================================================
565	n/a	* Generate the codes for a given tree and bit counts (which need not be
566	n/a	* optimal).
567	n/a	* IN assertion: the array bl_count contains the bit length statistics for
568	n/a	* the given tree and the field len is set for all tree elements.
569	n/a	* OUT assertion: the field code is set for all tree elements of non
570	n/a	* zero code length.
571	n/a	*/
572	n/a	local void gen_codes (tree, max_code, bl_count)
573	n/a	ct_data tree; / the tree to decorate */
574	n/a	int max_code; /* largest code with non zero frequency */
575	n/a	ushf bl_count; / number of codes at each bit length */
576	n/a	{
577	n/a	ush next_code[MAX_BITS+1]; /* next code value for each bit length */
578	n/a	unsigned code = 0; /* running code value */
579	n/a	int bits; /* bit index */
580	n/a	int n; /* code index */
581	n/a
582	n/a	/* The distribution counts are first used to generate the code values
583	n/a	* without bit reversal.
584	n/a	*/
585	n/a	for (bits = 1; bits <= MAX_BITS; bits++) {
586	n/a	code = (code + bl_count[bits-1]) << 1;
587	n/a	next_code[bits] = (ush)code;
588	n/a	}
589	n/a	/* Check that the bit counts in bl_count are consistent. The last code
590	n/a	* must be all ones.
591	n/a	*/
592	n/a	Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
593	n/a	"inconsistent bit counts");
594	n/a	Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
595	n/a
596	n/a	for (n = 0; n <= max_code; n++) {
597	n/a	int len = tree[n].Len;
598	n/a	if (len == 0) continue;
599	n/a	/* Now reverse the bits */
600	n/a	tree[n].Code = (ush)bi_reverse(next_code[len]++, len);
601	n/a
602	n/a	Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
603	n/a	n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
604	n/a	}
605	n/a	}
606	n/a
607	n/a	/* ===========================================================================
608	n/a	* Construct one Huffman tree and assigns the code bit strings and lengths.
609	n/a	* Update the total bit length for the current block.
610	n/a	* IN assertion: the field freq is set for all tree elements.
611	n/a	* OUT assertions: the fields len and code are set to the optimal bit length
612	n/a	* and corresponding code. The length opt_len is updated; static_len is
613	n/a	* also updated if stree is not null. The field max_code is set.
614	n/a	*/
615	n/a	local void build_tree(s, desc)
616	n/a	deflate_state *s;
617	n/a	tree_desc desc; / the tree descriptor */
618	n/a	{
619	n/a	ct_data *tree = desc->dyn_tree;
620	n/a	const ct_data *stree = desc->stat_desc->static_tree;
621	n/a	int elems = desc->stat_desc->elems;
622	n/a	int n, m; /* iterate over heap elements */
623	n/a	int max_code = -1; /* largest code with non zero frequency */
624	n/a	int node; /* new node being created */
625	n/a
626	n/a	/* Construct the initial heap, with least frequent element in
627	n/a	* heap[SMALLEST]. The sons of heap[n] are heap[2n] and heap[2n+1].
628	n/a	* heap[0] is not used.
629	n/a	*/
630	n/a	s->heap_len = 0, s->heap_max = HEAP_SIZE;
631	n/a
632	n/a	for (n = 0; n < elems; n++) {
633	n/a	if (tree[n].Freq != 0) {
634	n/a	s->heap[++(s->heap_len)] = max_code = n;
635	n/a	s->depth[n] = 0;
636	n/a	} else {
637	n/a	tree[n].Len = 0;
638	n/a	}
639	n/a	}
640	n/a
641	n/a	/* The pkzip format requires that at least one distance code exists,
642	n/a	* and that at least one bit should be sent even if there is only one
643	n/a	* possible code. So to avoid special checks later on we force at least
644	n/a	* two codes of non zero frequency.
645	n/a	*/
646	n/a	while (s->heap_len < 2) {
647	n/a	node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
648	n/a	tree[node].Freq = 1;
649	n/a	s->depth[node] = 0;
650	n/a	s->opt_len--; if (stree) s->static_len -= stree[node].Len;
651	n/a	/* node is 0 or 1 so it does not have extra bits */
652	n/a	}
653	n/a	desc->max_code = max_code;
654	n/a
655	n/a	/* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
656	n/a	* establish sub-heaps of increasing lengths:
657	n/a	*/
658	n/a	for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
659	n/a
660	n/a	/* Construct the Huffman tree by repeatedly combining the least two
661	n/a	* frequent nodes.
662	n/a	*/
663	n/a	node = elems; /* next internal node of the tree */
664	n/a	do {
665	n/a	pqremove(s, tree, n); /* n = node of least frequency */
666	n/a	m = s->heap[SMALLEST]; /* m = node of next least frequency */
667	n/a
668	n/a	s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */
669	n/a	s->heap[--(s->heap_max)] = m;
670	n/a
671	n/a	/* Create a new node father of n and m */
672	n/a	tree[node].Freq = tree[n].Freq + tree[m].Freq;
673	n/a	s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
674	n/a	s->depth[n] : s->depth[m]) + 1);
675	n/a	tree[n].Dad = tree[m].Dad = (ush)node;
676	n/a	#ifdef DUMP_BL_TREE
677	n/a	if (tree == s->bl_tree) {
678	n/a	fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
679	n/a	node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
680	n/a	}
681	n/a	#endif
682	n/a	/* and insert the new node in the heap */
683	n/a	s->heap[SMALLEST] = node++;
684	n/a	pqdownheap(s, tree, SMALLEST);
685	n/a
686	n/a	} while (s->heap_len >= 2);
687	n/a
688	n/a	s->heap[--(s->heap_max)] = s->heap[SMALLEST];
689	n/a
690	n/a	/* At this point, the fields freq and dad are set. We can now
691	n/a	* generate the bit lengths.
692	n/a	*/
693	n/a	gen_bitlen(s, (tree_desc *)desc);
694	n/a
695	n/a	/* The field len is now set, we can generate the bit codes */
696	n/a	gen_codes ((ct_data *)tree, max_code, s->bl_count);
697	n/a	}
698	n/a
699	n/a	/* ===========================================================================
700	n/a	* Scan a literal or distance tree to determine the frequencies of the codes
701	n/a	* in the bit length tree.
702	n/a	*/
703	n/a	local void scan_tree (s, tree, max_code)
704	n/a	deflate_state *s;
705	n/a	ct_data tree; / the tree to be scanned */
706	n/a	int max_code; /* and its largest code of non zero frequency */
707	n/a	{
708	n/a	int n; /* iterates over all tree elements */
709	n/a	int prevlen = -1; /* last emitted length */
710	n/a	int curlen; /* length of current code */
711	n/a	int nextlen = tree[0].Len; /* length of next code */
712	n/a	int count = 0; /* repeat count of the current code */
713	n/a	int max_count = 7; /* max repeat count */
714	n/a	int min_count = 4; /* min repeat count */
715	n/a
716	n/a	if (nextlen == 0) max_count = 138, min_count = 3;
717	n/a	tree[max_code+1].Len = (ush)0xffff; /* guard */
718	n/a
719	n/a	for (n = 0; n <= max_code; n++) {
720	n/a	curlen = nextlen; nextlen = tree[n+1].Len;
721	n/a	if (++count < max_count && curlen == nextlen) {
722	n/a	continue;
723	n/a	} else if (count < min_count) {
724	n/a	s->bl_tree[curlen].Freq += count;
725	n/a	} else if (curlen != 0) {
726	n/a	if (curlen != prevlen) s->bl_tree[curlen].Freq++;
727	n/a	s->bl_tree[REP_3_6].Freq++;
728	n/a	} else if (count <= 10) {
729	n/a	s->bl_tree[REPZ_3_10].Freq++;
730	n/a	} else {
731	n/a	s->bl_tree[REPZ_11_138].Freq++;
732	n/a	}
733	n/a	count = 0; prevlen = curlen;
734	n/a	if (nextlen == 0) {
735	n/a	max_count = 138, min_count = 3;
736	n/a	} else if (curlen == nextlen) {
737	n/a	max_count = 6, min_count = 3;
738	n/a	} else {
739	n/a	max_count = 7, min_count = 4;
740	n/a	}
741	n/a	}
742	n/a	}
743	n/a
744	n/a	/* ===========================================================================
745	n/a	* Send a literal or distance tree in compressed form, using the codes in
746	n/a	* bl_tree.
747	n/a	*/
748	n/a	local void send_tree (s, tree, max_code)
749	n/a	deflate_state *s;
750	n/a	ct_data tree; / the tree to be scanned */
751	n/a	int max_code; /* and its largest code of non zero frequency */
752	n/a	{
753	n/a	int n; /* iterates over all tree elements */
754	n/a	int prevlen = -1; /* last emitted length */
755	n/a	int curlen; /* length of current code */
756	n/a	int nextlen = tree[0].Len; /* length of next code */
757	n/a	int count = 0; /* repeat count of the current code */
758	n/a	int max_count = 7; /* max repeat count */
759	n/a	int min_count = 4; /* min repeat count */
760	n/a
761	n/a	/* tree[max_code+1].Len = -1; / / guard already set */
762	n/a	if (nextlen == 0) max_count = 138, min_count = 3;
763	n/a
764	n/a	for (n = 0; n <= max_code; n++) {
765	n/a	curlen = nextlen; nextlen = tree[n+1].Len;
766	n/a	if (++count < max_count && curlen == nextlen) {
767	n/a	continue;
768	n/a	} else if (count < min_count) {
769	n/a	do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
770	n/a
771	n/a	} else if (curlen != 0) {
772	n/a	if (curlen != prevlen) {
773	n/a	send_code(s, curlen, s->bl_tree); count--;
774	n/a	}
775	n/a	Assert(count >= 3 && count <= 6, " 3_6?");
776	n/a	send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
777	n/a
778	n/a	} else if (count <= 10) {
779	n/a	send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
780	n/a
781	n/a	} else {
782	n/a	send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
783	n/a	}
784	n/a	count = 0; prevlen = curlen;
785	n/a	if (nextlen == 0) {
786	n/a	max_count = 138, min_count = 3;
787	n/a	} else if (curlen == nextlen) {
788	n/a	max_count = 6, min_count = 3;
789	n/a	} else {
790	n/a	max_count = 7, min_count = 4;
791	n/a	}
792	n/a	}
793	n/a	}
794	n/a
795	n/a	/* ===========================================================================
796	n/a	* Construct the Huffman tree for the bit lengths and return the index in
797	n/a	* bl_order of the last bit length code to send.
798	n/a	*/
799	n/a	local int build_bl_tree(s)
800	n/a	deflate_state *s;
801	n/a	{
802	n/a	int max_blindex; /* index of last bit length code of non zero freq */
803	n/a
804	n/a	/* Determine the bit length frequencies for literal and distance trees */
805	n/a	scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
806	n/a	scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
807	n/a
808	n/a	/* Build the bit length tree: */
809	n/a	build_tree(s, (tree_desc *)(&(s->bl_desc)));
810	n/a	/* opt_len now includes the length of the tree representations, except
811	n/a	* the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
812	n/a	*/
813	n/a
814	n/a	/* Determine the number of bit length codes to send. The pkzip format
815	n/a	* requires that at least 4 bit length codes be sent. (appnote.txt says
816	n/a	* 3 but the actual value used is 4.)
817	n/a	*/
818	n/a	for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
819	n/a	if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
820	n/a	}
821	n/a	/* Update opt_len to include the bit length tree and counts */
822	n/a	s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4;
823	n/a	Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
824	n/a	s->opt_len, s->static_len));
825	n/a
826	n/a	return max_blindex;
827	n/a	}
828	n/a
829	n/a	/* ===========================================================================
830	n/a	* Send the header for a block using dynamic Huffman trees: the counts, the
831	n/a	* lengths of the bit length codes, the literal tree and the distance tree.
832	n/a	* IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
833	n/a	*/
834	n/a	local void send_all_trees(s, lcodes, dcodes, blcodes)
835	n/a	deflate_state *s;
836	n/a	int lcodes, dcodes, blcodes; /* number of codes for each tree */
837	n/a	{
838	n/a	int rank; /* index in bl_order */
839	n/a
840	n/a	Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
841	n/a	Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
842	n/a	"too many codes");
843	n/a	Tracev((stderr, "\nbl counts: "));
844	n/a	send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */
845	n/a	send_bits(s, dcodes-1, 5);
846	n/a	send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */
847	n/a	for (rank = 0; rank < blcodes; rank++) {
848	n/a	Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
849	n/a	send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
850	n/a	}
851	n/a	Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
852	n/a
853	n/a	send_tree(s, (ct_data )s->dyn_ltree, lcodes-1); / literal tree */
854	n/a	Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
855	n/a
856	n/a	send_tree(s, (ct_data )s->dyn_dtree, dcodes-1); / distance tree */
857	n/a	Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
858	n/a	}
859	n/a
860	n/a	/* ===========================================================================
861	n/a	* Send a stored block
862	n/a	*/
863	n/a	void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last)
864	n/a	deflate_state *s;
865	n/a	charf buf; / input block */
866	n/a	ulg stored_len; /* length of input block */
867	n/a	int last; /* one if this is the last block for a file */
868	n/a	{
869	n/a	send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */
870	n/a	bi_windup(s); /* align on byte boundary */
871	n/a	put_short(s, (ush)stored_len);
872	n/a	put_short(s, (ush)~stored_len);
873	n/a	zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
874	n/a	s->pending += stored_len;
875	n/a	#ifdef ZLIB_DEBUG
876	n/a	s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
877	n/a	s->compressed_len += (stored_len + 4) << 3;
878	n/a	s->bits_sent += 2*16;
879	n/a	s->bits_sent += stored_len<<3;
880	n/a	#endif
881	n/a	}
882	n/a
883	n/a	/* ===========================================================================
884	n/a	* Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
885	n/a	*/
886	n/a	void ZLIB_INTERNAL _tr_flush_bits(s)
887	n/a	deflate_state *s;
888	n/a	{
889	n/a	bi_flush(s);
890	n/a	}
891	n/a
892	n/a	/* ===========================================================================
893	n/a	* Send one empty static block to give enough lookahead for inflate.
894	n/a	* This takes 10 bits, of which 7 may remain in the bit buffer.
895	n/a	*/
896	n/a	void ZLIB_INTERNAL _tr_align(s)
897	n/a	deflate_state *s;
898	n/a	{
899	n/a	send_bits(s, STATIC_TREES<<1, 3);
900	n/a	send_code(s, END_BLOCK, static_ltree);
901	n/a	#ifdef ZLIB_DEBUG
902	n/a	s->compressed_len += 10L; /* 3 for block type, 7 for EOB */
903	n/a	#endif
904	n/a	bi_flush(s);
905	n/a	}
906	n/a
907	n/a	/* ===========================================================================
908	n/a	* Determine the best encoding for the current block: dynamic trees, static
909	n/a	* trees or store, and write out the encoded block.
910	n/a	*/
911	n/a	void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
912	n/a	deflate_state *s;
913	n/a	charf buf; / input block, or NULL if too old */
914	n/a	ulg stored_len; /* length of input block */
915	n/a	int last; /* one if this is the last block for a file */
916	n/a	{
917	n/a	ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
918	n/a	int max_blindex = 0; /* index of last bit length code of non zero freq */
919	n/a
920	n/a	/* Build the Huffman trees unless a stored block is forced */
921	n/a	if (s->level > 0) {
922	n/a
923	n/a	/* Check if the file is binary or text */
924	n/a	if (s->strm->data_type == Z_UNKNOWN)
925	n/a	s->strm->data_type = detect_data_type(s);
926	n/a
927	n/a	/* Construct the literal and distance trees */
928	n/a	build_tree(s, (tree_desc *)(&(s->l_desc)));
929	n/a	Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
930	n/a	s->static_len));
931	n/a
932	n/a	build_tree(s, (tree_desc *)(&(s->d_desc)));
933	n/a	Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
934	n/a	s->static_len));
935	n/a	/* At this point, opt_len and static_len are the total bit lengths of
936	n/a	* the compressed block data, excluding the tree representations.
937	n/a	*/
938	n/a
939	n/a	/* Build the bit length tree for the above two trees, and get the index
940	n/a	* in bl_order of the last bit length code to send.
941	n/a	*/
942	n/a	max_blindex = build_bl_tree(s);
943	n/a
944	n/a	/* Determine the best encoding. Compute the block lengths in bytes. */
945	n/a	opt_lenb = (s->opt_len+3+7)>>3;
946	n/a	static_lenb = (s->static_len+3+7)>>3;
947	n/a
948	n/a	Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
949	n/a	opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
950	n/a	s->last_lit));
951	n/a
952	n/a	if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
953	n/a
954	n/a	} else {
955	n/a	Assert(buf != (char*)0, "lost buf");
956	n/a	opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
957	n/a	}
958	n/a
959	n/a	#ifdef FORCE_STORED
960	n/a	if (buf != (char)0) { / force stored block */
961	n/a	#else
962	n/a	if (stored_len+4 <= opt_lenb && buf != (char*)0) {
963	n/a	/* 4: two words for the lengths */
964	n/a	#endif
965	n/a	/* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
966	n/a	* Otherwise we can't have processed more than WSIZE input bytes since
967	n/a	* the last block flush, because compression would have been
968	n/a	* successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
969	n/a	* transform a block into a stored block.
970	n/a	*/
971	n/a	_tr_stored_block(s, buf, stored_len, last);
972	n/a
973	n/a	#ifdef FORCE_STATIC
974	n/a	} else if (static_lenb >= 0) { /* force static trees */
975	n/a	#else
976	n/a	} else if (s->strategy == Z_FIXED \|\| static_lenb == opt_lenb) {
977	n/a	#endif
978	n/a	send_bits(s, (STATIC_TREES<<1)+last, 3);
979	n/a	compress_block(s, (const ct_data *)static_ltree,
980	n/a	(const ct_data *)static_dtree);
981	n/a	#ifdef ZLIB_DEBUG
982	n/a	s->compressed_len += 3 + s->static_len;
983	n/a	#endif
984	n/a	} else {
985	n/a	send_bits(s, (DYN_TREES<<1)+last, 3);
986	n/a	send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
987	n/a	max_blindex+1);
988	n/a	compress_block(s, (const ct_data *)s->dyn_ltree,
989	n/a	(const ct_data *)s->dyn_dtree);
990	n/a	#ifdef ZLIB_DEBUG
991	n/a	s->compressed_len += 3 + s->opt_len;
992	n/a	#endif
993	n/a	}
994	n/a	Assert (s->compressed_len == s->bits_sent, "bad compressed size");
995	n/a	/* The above check is made mod 2^32, for files larger than 512 MB
996	n/a	* and uLong implemented on 32 bits.
997	n/a	*/
998	n/a	init_block(s);
999	n/a
1000	n/a	if (last) {
1001	n/a	bi_windup(s);
1002	n/a	#ifdef ZLIB_DEBUG
1003	n/a	s->compressed_len += 7; /* align on byte boundary */
1004	n/a	#endif
1005	n/a	}
1006	n/a	Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1007	n/a	s->compressed_len-7*last));
1008	n/a	}
1009	n/a
1010	n/a	/* ===========================================================================
1011	n/a	* Save the match info and tally the frequency counts. Return true if
1012	n/a	* the current block must be flushed.
1013	n/a	*/
1014	n/a	int ZLIB_INTERNAL _tr_tally (s, dist, lc)
1015	n/a	deflate_state *s;
1016	n/a	unsigned dist; /* distance of matched string */
1017	n/a	unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
1018	n/a	{
1019	n/a	s->d_buf[s->last_lit] = (ush)dist;
1020	n/a	s->l_buf[s->last_lit++] = (uch)lc;
1021	n/a	if (dist == 0) {
1022	n/a	/* lc is the unmatched char */
1023	n/a	s->dyn_ltree[lc].Freq++;
1024	n/a	} else {
1025	n/a	s->matches++;
1026	n/a	/* Here, lc is the match length - MIN_MATCH */
1027	n/a	dist--; /* dist = match distance - 1 */
1028	n/a	Assert((ush)dist < (ush)MAX_DIST(s) &&
1029	n/a	(ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1030	n/a	(ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1031	n/a
1032	n/a	s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
1033	n/a	s->dyn_dtree[d_code(dist)].Freq++;
1034	n/a	}
1035	n/a
1036	n/a	#ifdef TRUNCATE_BLOCK
1037	n/a	/* Try to guess if it is profitable to stop the current block here */
1038	n/a	if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1039	n/a	/* Compute an upper bound for the compressed length */
1040	n/a	ulg out_length = (ulg)s->last_lit*8L;
1041	n/a	ulg in_length = (ulg)((long)s->strstart - s->block_start);
1042	n/a	int dcode;
1043	n/a	for (dcode = 0; dcode < D_CODES; dcode++) {
1044	n/a	out_length += (ulg)s->dyn_dtree[dcode].Freq *
1045	n/a	(5L+extra_dbits[dcode]);
1046	n/a	}
1047	n/a	out_length >>= 3;
1048	n/a	Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1049	n/a	s->last_lit, in_length, out_length,
1050	n/a	100L - out_length*100L/in_length));
1051	n/a	if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
1052	n/a	}
1053	n/a	#endif
1054	n/a	return (s->last_lit == s->lit_bufsize-1);
1055	n/a	/* We avoid equality with lit_bufsize because of wraparound at 64K
1056	n/a	* on 16 bit machines and because stored blocks are restricted to
1057	n/a	* 64K-1 bytes.
1058	n/a	*/
1059	n/a	}
1060	n/a
1061	n/a	/* ===========================================================================
1062	n/a	* Send the block data compressed using the given Huffman trees
1063	n/a	*/
1064	n/a	local void compress_block(s, ltree, dtree)
1065	n/a	deflate_state *s;
1066	n/a	const ct_data ltree; / literal tree */
1067	n/a	const ct_data dtree; / distance tree */
1068	n/a	{
1069	n/a	unsigned dist; /* distance of matched string */
1070	n/a	int lc; /* match length or unmatched char (if dist == 0) */
1071	n/a	unsigned lx = 0; /* running index in l_buf */
1072	n/a	unsigned code; /* the code to send */
1073	n/a	int extra; /* number of extra bits to send */
1074	n/a
1075	n/a	if (s->last_lit != 0) do {
1076	n/a	dist = s->d_buf[lx];
1077	n/a	lc = s->l_buf[lx++];
1078	n/a	if (dist == 0) {
1079	n/a	send_code(s, lc, ltree); /* send a literal byte */
1080	n/a	Tracecv(isgraph(lc), (stderr," '%c' ", lc));
1081	n/a	} else {
1082	n/a	/* Here, lc is the match length - MIN_MATCH */
1083	n/a	code = _length_code[lc];
1084	n/a	send_code(s, code+LITERALS+1, ltree); /* send the length code */
1085	n/a	extra = extra_lbits[code];
1086	n/a	if (extra != 0) {
1087	n/a	lc -= base_length[code];
1088	n/a	send_bits(s, lc, extra); /* send the extra length bits */
1089	n/a	}
1090	n/a	dist--; /* dist is now the match distance - 1 */
1091	n/a	code = d_code(dist);
1092	n/a	Assert (code < D_CODES, "bad d_code");
1093	n/a
1094	n/a	send_code(s, code, dtree); /* send the distance code */
1095	n/a	extra = extra_dbits[code];
1096	n/a	if (extra != 0) {
1097	n/a	dist -= (unsigned)base_dist[code];
1098	n/a	send_bits(s, dist, extra); /* send the extra distance bits */
1099	n/a	}
1100	n/a	} /* literal or match pair ? */
1101	n/a
1102	n/a	/* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
1103	n/a	Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1104	n/a	"pendingBuf overflow");
1105	n/a
1106	n/a	} while (lx < s->last_lit);
1107	n/a
1108	n/a	send_code(s, END_BLOCK, ltree);
1109	n/a	}
1110	n/a
1111	n/a	/* ===========================================================================
1112	n/a	* Check if the data type is TEXT or BINARY, using the following algorithm:
1113	n/a	* - TEXT if the two conditions below are satisfied:
1114	n/a	* a) There are no non-portable control characters belonging to the
1115	n/a	* "black list" (0..6, 14..25, 28..31).
1116	n/a	* b) There is at least one printable character belonging to the
1117	n/a	* "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
1118	n/a	* - BINARY otherwise.
1119	n/a	* - The following partially-portable control characters form a
1120	n/a	* "gray list" that is ignored in this detection algorithm:
1121	n/a	* (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
1122	n/a	* IN assertion: the fields Freq of dyn_ltree are set.
1123	n/a	*/
1124	n/a	local int detect_data_type(s)
1125	n/a	deflate_state *s;
1126	n/a	{
1127	n/a	/* black_mask is the bit mask of black-listed bytes
1128	n/a	* set bits 0..6, 14..25, and 28..31
1129	n/a	* 0xf3ffc07f = binary 11110011111111111100000001111111
1130	n/a	*/
1131	n/a	unsigned long black_mask = 0xf3ffc07fUL;
1132	n/a	int n;
1133	n/a
1134	n/a	/* Check for non-textual ("black-listed") bytes. */
1135	n/a	for (n = 0; n <= 31; n++, black_mask >>= 1)
1136	n/a	if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1137	n/a	return Z_BINARY;
1138	n/a
1139	n/a	/* Check for textual ("white-listed") bytes. */
1140	n/a	if (s->dyn_ltree[9].Freq != 0 \|\| s->dyn_ltree[10].Freq != 0
1141	n/a	\|\| s->dyn_ltree[13].Freq != 0)
1142	n/a	return Z_TEXT;
1143	n/a	for (n = 32; n < LITERALS; n++)
1144	n/a	if (s->dyn_ltree[n].Freq != 0)
1145	n/a	return Z_TEXT;
1146	n/a
1147	n/a	/* There are no "black-listed" or "white-listed" bytes:
1148	n/a	* this stream either is empty or has tolerated ("gray-listed") bytes only.
1149	n/a	*/
1150	n/a	return Z_BINARY;
1151	n/a	}
1152	n/a
1153	n/a	/* ===========================================================================
1154	n/a	* Reverse the first len bits of a code, using straightforward code (a faster
1155	n/a	* method would use a table)
1156	n/a	* IN assertion: 1 <= len <= 15
1157	n/a	*/
1158	n/a	local unsigned bi_reverse(code, len)
1159	n/a	unsigned code; /* the value to invert */
1160	n/a	int len; /* its bit length */
1161	n/a	{
1162	n/a	register unsigned res = 0;
1163	n/a	do {
1164	n/a	res \|= code & 1;
1165	n/a	code >>= 1, res <<= 1;
1166	n/a	} while (--len > 0);
1167	n/a	return res >> 1;
1168	n/a	}
1169	n/a
1170	n/a	/* ===========================================================================
1171	n/a	* Flush the bit buffer, keeping at most 7 bits in it.
1172	n/a	*/
1173	n/a	local void bi_flush(s)
1174	n/a	deflate_state *s;
1175	n/a	{
1176	n/a	if (s->bi_valid == 16) {
1177	n/a	put_short(s, s->bi_buf);
1178	n/a	s->bi_buf = 0;
1179	n/a	s->bi_valid = 0;
1180	n/a	} else if (s->bi_valid >= 8) {
1181	n/a	put_byte(s, (Byte)s->bi_buf);
1182	n/a	s->bi_buf >>= 8;
1183	n/a	s->bi_valid -= 8;
1184	n/a	}
1185	n/a	}
1186	n/a
1187	n/a	/* ===========================================================================
1188	n/a	* Flush the bit buffer and align the output on a byte boundary
1189	n/a	*/
1190	n/a	local void bi_windup(s)
1191	n/a	deflate_state *s;
1192	n/a	{
1193	n/a	if (s->bi_valid > 8) {
1194	n/a	put_short(s, s->bi_buf);
1195	n/a	} else if (s->bi_valid > 0) {
1196	n/a	put_byte(s, (Byte)s->bi_buf);
1197	n/a	}
1198	n/a	s->bi_buf = 0;
1199	n/a	s->bi_valid = 0;
1200	n/a	#ifdef ZLIB_DEBUG
1201	n/a	s->bits_sent = (s->bits_sent+7) & ~7;
1202	n/a	#endif
1203	n/a	}