Lines Matching full:tree
13 * Each code tree is stored in a compressed form which is itself
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
111 const ct_data *static_tree; /* static tree or NULL */
114 int elems; /* max number of elements in the tree */
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); }
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()
217 /* Construct the codes of the static literal tree */ 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()
239 * Initialize the tree data structures for a new zlib stream.
276 int n; /* iterates over tree elements */ in init_block()
289 /* Index within the heap array of least frequent node in the Huffman tree */
296 #define pqremove(s, tree, top) \ argument
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,
319 ct_data *tree, /* the tree to restore */ in pqdownheap() argument
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()
337 /* And continue down the tree, setting j to the left son of k */ in pqdownheap()
344 * Compute the optimal bit lengths for a tree and update the total bit length
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
365 int n, m; /* iterate over the tree elements */ 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()
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()
390 f = tree[n].Freq; in gen_bitlen()
403 s->bl_count[bits]--; /* move one leaf down the tree */ 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()
434 * Generate the codes for a given tree and bit counts (which need not be
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
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
503 if (tree[n].Freq != 0) { in build_tree()
507 tree[n].Len = 0; in build_tree()
518 tree[node].Freq = 1; in build_tree()
525 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 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()
542 tree[node].Freq = tree[n].Freq + tree[m].Freq; 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()
553 pqdownheap(s, tree, 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()
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()
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()
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()
667 * Construct the Huffman tree for the bit lengths and return the index in
680 /* Build the bit length tree: */ in build_bl_tree()
682 /* opt_len now includes the length of the tree representations, except in build_bl_tree()
693 /* Update opt_len to include the bit length tree and counts */ in build_bl_tree()
703 * lengths of the bit length codes, the literal tree and the distance tree.
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()
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()
827 * the compressed block data, excluding the tree representations.
830 /* Build the bit length tree for the above two trees, and get the index
966 ct_data *ltree, /* literal tree */
967 ct_data *dtree /* distance tree */