Lines Matching +full:in +full:- +full:tree
2 /* trees.c -- output deflated data using Huffman coding
3 * Copyright (C) 1995-1996 Jean-loup Gailly
4 * For conditions of distribution and use, see copyright notice in zlib.h
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
16 * reconstructed from the lengths in the inflate process, as described
17 * in the deflate specification.
22 * Available in ftp.uu.net:/pub/archiving/zip/doc/deflate-1.1.doc
25 * Data Compression: Methods and Theory, pp. 49-50.
26 * Computer Science Press, 1988. ISBN 0-7167-8156-5.
30 * Addison-Wesley, 1983. ISBN 0-201-06672-6.
56 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
59 /* repeat a zero length 3-10 times (3 bits of repeat count) */
62 /* repeat a zero length 11-138 times (7 bits of repeat count) */
75 /* The lengths of the bit length codes are sent in order of decreasing
84 /* The static literal tree. Since the bit lengths are imposed, there is no
86 * The codes 286 and 287 are needed to build a canonical tree (see zlib_tr_init
91 /* The static distance tree. (Actually a trivial tree since all codes use
101 static uch length_code[MAX_MATCH-MIN_MATCH+1];
111 const ct_data *static_tree; /* static tree or NULL */
114 int elems; /* max number of elements in the tree */
128 * Local (static) routines in this file.
133 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
135 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
137 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
138 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
150 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) argument
151 /* Send a code of the given tree. c and tree must not have side effects */
154 # define send_code(s, c, tree) \ argument
156 send_bits(s, tree[c].Code, tree[c].Len); }
161 /* Mapping from a distance to a distance code. dist is the distance - 1 and
167 * Initialize the various 'constant' tables. In a multi-threaded environment,
174 int n; /* iterates over tree elements */ in tr_static_init()
180 /* number of codes at each bit length for an optimal tree */ in tr_static_init()
184 /* Initialize the mapping length (0..255) -> length code (0..28) */ in tr_static_init()
186 for (code = 0; code < LENGTH_CODES-1; code++) { in tr_static_init()
194 * in two different ways: code 284 + 5 bits or code 285, so we in tr_static_init()
197 length_code[length-1] = (uch)code; in tr_static_init()
199 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ in tr_static_init()
211 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) { in tr_static_init()
217 /* Construct the codes of the static literal tree */ in tr_static_init()
224 /* Codes 286 and 287 do not exist, but we must include them in the in tr_static_init()
225 * tree construction to get a canonical Huffman tree (longest code in tr_static_init()
230 /* The static distance tree is trivial: */ in tr_static_init()
233 static_dtree[n].Code = bitrev32((u32)n) >> (32 - 5); in tr_static_init()
239 * Initialize the tree data structures for a new zlib stream.
247 s->compressed_len = 0L; in zlib_tr_init()
249 s->l_desc.dyn_tree = s->dyn_ltree; in zlib_tr_init()
250 s->l_desc.stat_desc = &static_l_desc; in zlib_tr_init()
252 s->d_desc.dyn_tree = s->dyn_dtree; in zlib_tr_init()
253 s->d_desc.stat_desc = &static_d_desc; in zlib_tr_init()
255 s->bl_desc.dyn_tree = s->bl_tree; in zlib_tr_init()
256 s->bl_desc.stat_desc = &static_bl_desc; in zlib_tr_init()
258 s->bi_buf = 0; in zlib_tr_init()
259 s->bi_valid = 0; in zlib_tr_init()
260 s->last_eob_len = 8; /* enough lookahead for inflate */ in zlib_tr_init()
262 s->bits_sent = 0L; in zlib_tr_init()
276 int n; /* iterates over tree elements */ in init_block()
279 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0; in init_block()
280 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0; in init_block()
281 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0; in init_block()
283 s->dyn_ltree[END_BLOCK].Freq = 1; in init_block()
284 s->opt_len = s->static_len = 0L; in init_block()
285 s->last_lit = s->matches = 0; in init_block()
289 /* Index within the heap array of least frequent node in the Huffman tree */
296 #define pqremove(s, tree, top) \ argument
298 top = s->heap[SMALLEST]; \
299 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
300 pqdownheap(s, tree, SMALLEST); \
304 * Compares to subtrees, using the tree depth as tie breaker when
307 #define smaller(tree, n, m, depth) \ argument
308 (tree[n].Freq < tree[m].Freq || \
309 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
312 * Restore the heap property by moving down the tree starting at node k,
314 * when the heap property is re-established (each father smaller than its
319 ct_data *tree, /* the tree to restore */ in pqdownheap() argument
323 int v = s->heap[k]; in pqdownheap()
325 while (j <= s->heap_len) { in pqdownheap()
327 if (j < s->heap_len && in pqdownheap()
328 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { in pqdownheap()
332 if (smaller(tree, v, s->heap[j], s->depth)) break; in pqdownheap()
335 s->heap[k] = s->heap[j]; k = j; in pqdownheap()
337 /* And continue down the tree, setting j to the left son of k */ in pqdownheap()
340 s->heap[k] = v; in pqdownheap()
344 * Compute the optimal bit lengths for a tree and update the total bit length
346 * IN assertion: the fields freq and dad are set, heap[heap_max] and
347 * above are the tree nodes sorted by increasing frequency.
355 tree_desc *desc /* the tree descriptor */ in gen_bitlen()
358 ct_data *tree = desc->dyn_tree; in gen_bitlen() local
359 int max_code = desc->max_code; in gen_bitlen()
360 const ct_data *stree = desc->stat_desc->static_tree; in gen_bitlen()
361 const int *extra = desc->stat_desc->extra_bits; in gen_bitlen()
362 int base = desc->stat_desc->extra_base; in gen_bitlen()
363 int max_length = desc->stat_desc->max_length; in gen_bitlen()
365 int n, m; /* iterate over the tree elements */ in gen_bitlen()
371 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0; in gen_bitlen()
373 /* In a first pass, compute the optimal bit lengths (which may in gen_bitlen()
374 * overflow in the case of the bit length tree). in gen_bitlen()
376 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */ in gen_bitlen()
378 for (h = s->heap_max+1; h < HEAP_SIZE; h++) { in gen_bitlen()
379 n = s->heap[h]; in gen_bitlen()
380 bits = tree[tree[n].Dad].Len + 1; in gen_bitlen()
382 tree[n].Len = (ush)bits; in gen_bitlen()
383 /* We overwrite tree[n].Dad which is no longer needed */ in gen_bitlen()
387 s->bl_count[bits]++; in gen_bitlen()
389 if (n >= base) xbits = extra[n-base]; in gen_bitlen()
390 f = tree[n].Freq; in gen_bitlen()
391 s->opt_len += (ulg)f * (bits + xbits); in gen_bitlen()
392 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); in gen_bitlen()
401 bits = max_length-1; in gen_bitlen()
402 while (s->bl_count[bits] == 0) bits--; in gen_bitlen()
403 s->bl_count[bits]--; /* move one leaf down the tree */ in gen_bitlen()
404 s->bl_count[bits+1] += 2; /* move one overflow item as its brother */ in gen_bitlen()
405 s->bl_count[max_length]--; in gen_bitlen()
409 overflow -= 2; in gen_bitlen()
412 /* Now recompute all bit lengths, scanning in increasing frequency. in gen_bitlen()
417 for (bits = max_length; bits != 0; bits--) { in gen_bitlen()
418 n = s->bl_count[bits]; in gen_bitlen()
420 m = s->heap[--h]; in gen_bitlen()
422 if (tree[m].Len != (unsigned) bits) { in gen_bitlen()
423 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); in gen_bitlen()
424 s->opt_len += ((long)bits - (long)tree[m].Len) in gen_bitlen()
425 *(long)tree[m].Freq; in gen_bitlen()
426 tree[m].Len = (ush)bits; in gen_bitlen()
428 n--; in gen_bitlen()
434 * Generate the codes for a given tree and bit counts (which need not be
436 * IN assertion: the array bl_count contains the bit length statistics for
437 * the given tree and the field len is set for all tree elements.
438 * OUT assertion: the field code is set for all tree elements of non
442 ct_data *tree, /* the tree to decorate */ in gen_codes() argument
456 next_code[bits] = code = (code + bl_count[bits-1]) << 1; in gen_codes()
458 /* Check that the bit counts in bl_count are consistent. The last code in gen_codes()
461 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, in gen_codes()
466 int len = tree[n].Len; in gen_codes()
469 tree[n].Code = bitrev32((u32)(next_code[len]++)) >> (32 - len); in gen_codes()
471 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", in gen_codes()
472 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); in gen_codes()
477 * Construct one Huffman tree and assigns the code bit strings and lengths.
479 * IN assertion: the field freq is set for all tree elements.
486 tree_desc *desc /* the tree descriptor */ in build_tree()
489 ct_data *tree = desc->dyn_tree; in build_tree() local
490 const ct_data *stree = desc->stat_desc->static_tree; in build_tree()
491 int elems = desc->stat_desc->elems; in build_tree()
493 int max_code = -1; /* largest code with non zero frequency */ in build_tree()
496 /* Construct the initial heap, with least frequent element in in build_tree()
500 s->heap_len = 0, s->heap_max = HEAP_SIZE; in build_tree()
503 if (tree[n].Freq != 0) { in build_tree()
504 s->heap[++(s->heap_len)] = max_code = n; in build_tree()
505 s->depth[n] = 0; in build_tree()
507 tree[n].Len = 0; in build_tree()
516 while (s->heap_len < 2) { in build_tree()
517 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0); in build_tree()
518 tree[node].Freq = 1; in build_tree()
519 s->depth[node] = 0; in build_tree()
520 s->opt_len--; if (stree) s->static_len -= stree[node].Len; in build_tree()
523 desc->max_code = max_code; in build_tree()
525 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, in build_tree()
526 * establish sub-heaps of increasing lengths: in build_tree()
528 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n); in build_tree()
530 /* Construct the Huffman tree by repeatedly combining the least two in build_tree()
533 node = elems; /* next internal node of the tree */ in build_tree()
535 pqremove(s, tree, n); /* n = node of least frequency */ in build_tree()
536 m = s->heap[SMALLEST]; /* m = node of next least frequency */ in build_tree()
538 s->heap[--(s->heap_max)] = n; /* keep the nodes sorted by frequency */ in build_tree()
539 s->heap[--(s->heap_max)] = m; in build_tree()
542 tree[node].Freq = tree[n].Freq + tree[m].Freq; in build_tree()
543 s->depth[node] = (uch) (max(s->depth[n], s->depth[m]) + 1); in build_tree()
544 tree[n].Dad = tree[m].Dad = (ush)node; in build_tree()
546 if (tree == s->bl_tree) { in build_tree()
548 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq); in build_tree()
551 /* and insert the new node in the heap */ in build_tree()
552 s->heap[SMALLEST] = node++; in build_tree()
553 pqdownheap(s, tree, SMALLEST); in build_tree()
555 } while (s->heap_len >= 2); in build_tree()
557 s->heap[--(s->heap_max)] = s->heap[SMALLEST]; in build_tree()
565 gen_codes ((ct_data *)tree, max_code, s->bl_count); in build_tree()
569 * Scan a literal or distance tree to determine the frequencies of the codes
570 * in the bit length tree.
574 ct_data *tree, /* the tree to be scanned */ in scan_tree() argument
578 int n; /* iterates over all tree elements */ in scan_tree()
579 int prevlen = -1; /* last emitted length */ in scan_tree()
581 int nextlen = tree[0].Len; /* length of next code */ in scan_tree()
587 tree[max_code+1].Len = (ush)0xffff; /* guard */ in scan_tree()
590 curlen = nextlen; nextlen = tree[n+1].Len; in scan_tree()
594 s->bl_tree[curlen].Freq += count; in scan_tree()
596 if (curlen != prevlen) s->bl_tree[curlen].Freq++; in scan_tree()
597 s->bl_tree[REP_3_6].Freq++; in scan_tree()
599 s->bl_tree[REPZ_3_10].Freq++; in scan_tree()
601 s->bl_tree[REPZ_11_138].Freq++; in scan_tree()
615 * Send a literal or distance tree in compressed form, using the codes in
620 ct_data *tree, /* the tree to be scanned */ in send_tree() argument
624 int n; /* iterates over all tree elements */ in send_tree()
625 int prevlen = -1; /* last emitted length */ in send_tree()
627 int nextlen = tree[0].Len; /* length of next code */ in send_tree()
632 /* tree[max_code+1].Len = -1; */ /* guard already set */ in send_tree()
636 curlen = nextlen; nextlen = tree[n+1].Len; in send_tree()
640 do { send_code(s, curlen, s->bl_tree); } while (--count != 0); in send_tree()
644 send_code(s, curlen, s->bl_tree); count--; in send_tree()
647 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2); in send_tree()
650 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3); in send_tree()
653 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7); in send_tree()
667 * Construct the Huffman tree for the bit lengths and return the index in
677 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code); in build_bl_tree()
678 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code); in build_bl_tree()
680 /* Build the bit length tree: */ in build_bl_tree()
681 build_tree(s, (tree_desc *)(&(s->bl_desc))); in build_bl_tree()
682 /* opt_len now includes the length of the tree representations, except in build_bl_tree()
690 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { in build_bl_tree()
691 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; in build_bl_tree()
693 /* Update opt_len to include the bit length tree and counts */ in build_bl_tree()
694 s->opt_len += 3*(max_blindex+1) + 5+5+4; in build_bl_tree()
696 s->opt_len, s->static_len)); in build_bl_tree()
703 * lengths of the bit length codes, the literal tree and the distance tree.
704 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
708 int lcodes, /* number of codes for each tree */ in send_all_trees()
709 int dcodes, /* number of codes for each tree */ in send_all_trees()
710 int blcodes /* number of codes for each tree */ in send_all_trees()
713 int rank; /* index in bl_order */ in send_all_trees()
719 send_bits(s, lcodes-257, 5); /* not +255 as stated in appnote.txt */ in send_all_trees()
720 send_bits(s, dcodes-1, 5); in send_all_trees()
721 send_bits(s, blcodes-4, 4); /* not -3 as stated in appnote.txt */ in send_all_trees()
724 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3); in send_all_trees()
726 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent)); in send_all_trees()
728 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */ in send_all_trees()
729 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent)); in send_all_trees()
731 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */ in send_all_trees()
732 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent)); in send_all_trees()
746 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; in zlib_tr_stored_block()
747 s->compressed_len += (stored_len + 4) << 3; in zlib_tr_stored_block()
760 s->compressed_len = (s->compressed_len + 3) & ~7L; in zlib_tr_stored_type_only()
766 * This takes 10 bits, of which 7 may remain in the bit buffer.
770 * the last real code. In this case we send two empty static blocks instead
781 s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ in zlib_tr_align()
784 * (10 - bi_valid) bits. The lookahead for the last real code (before in zlib_tr_align()
788 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) { in zlib_tr_align()
791 s->compressed_len += 10L; in zlib_tr_align()
794 s->last_eob_len = 7; in zlib_tr_align()
809 ulg opt_lenb, static_lenb; /* opt_len and static_len in bytes */
813 if (s->level > 0) {
816 if (s->data_type == Z_UNKNOWN) set_data_type(s);
819 build_tree(s, (tree_desc *)(&(s->l_desc)));
820 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
821 s->static_len));
823 build_tree(s, (tree_desc *)(&(s->d_desc)));
824 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
825 s->static_len));
827 * the compressed block data, excluding the tree representations.
830 /* Build the bit length tree for the above two trees, and get the index
831 * in bl_order of the last bit length code to send.
835 /* Determine the best encoding. Compute first the block length in bytes*/
836 opt_lenb = (s->opt_len+3+7)>>3;
837 static_lenb = (s->static_len+3+7)>>3;
840 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
841 s->last_lit));
856 if (eof && s->compressed_len == 0L) { /* force stored file */
858 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
864 s->compressed_len = stored_len << 3;
865 s->method = STORED;
890 s->compressed_len += 3 + s->static_len;
893 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
895 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
896 s->compressed_len += 3 + s->opt_len;
898 Assert (s->compressed_len == s->bits_sent, "bad compressed size");
903 s->compressed_len += 7; /* align on byte boundary */
905 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
906 s->compressed_len-7*eof));
908 return s->compressed_len >> 3;
918 unsigned lc /* match length-MIN_MATCH or unmatched char (if dist==0) */
921 s->d_buf[s->last_lit] = (ush)dist;
922 s->l_buf[s->last_lit++] = (uch)lc;
925 s->dyn_ltree[lc].Freq++;
927 s->matches++;
928 /* Here, lc is the match length - MIN_MATCH */
929 dist--; /* dist = match distance - 1 */
931 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
934 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
935 s->dyn_dtree[d_code(dist)].Freq++;
939 if ((s->last_lit & 0xfff) == 0 && s->level > 2) {
941 ulg out_length = (ulg)s->last_lit*8L;
942 ulg in_length = (ulg)((long)s->strstart - s->block_start);
945 out_length += (ulg)s->dyn_dtree[dcode].Freq *
949 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
950 s->last_lit, in_length, out_length,
951 100L - out_length*100L/in_length));
952 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
954 return (s->last_lit == s->lit_bufsize-1);
957 * 64K-1 bytes.
966 ct_data *ltree, /* literal tree */
967 ct_data *dtree /* distance tree */
972 unsigned lx = 0; /* running index in l_buf */
976 if (s->last_lit != 0) do {
977 dist = s->d_buf[lx];
978 lc = s->l_buf[lx++];
983 /* Here, lc is the match length - MIN_MATCH */
988 lc -= base_length[code];
991 dist--; /* dist is now the match distance - 1 */
998 dist -= base_dist[code];
1004 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
1006 } while (lx < s->last_lit);
1009 s->last_eob_len = ltree[END_BLOCK].Len;
1015 * IN assertion: the fields freq of dyn_ltree are set and the total of all
1016 * frequencies does not exceed 64K (to fit in an int on 16 bit machines).
1025 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
1026 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
1027 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
1028 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
1043 s->last_eob_len = 8; /* enough lookahead for inflate */
1049 s->bits_sent += 2*16;
1053 s->bits_sent += (ulg)len<<3;
1056 memcpy(&s->pending_buf[s->pending], buf, len);
1057 s->pending += len;