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