zenilib: zenilib/jni/external/zlib/trees.c Source File

zenilib 0.5.3.0

- Main Page
- Modules
- Namespaces
- Classes
- Files

- File List
- File Members

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