Lines Matching refs:tree
351 ush dad; /* father node in Huffman tree */
364 ct_data *dyn_tree; /* the dynamic tree */
366 static_tree_desc *stat_desc; /* the corresponding static tree */
474 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
475 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
476 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
478 struct tree_desc_s l_desc; /* desc. for literal tree */
479 struct tree_desc_s d_desc; /* desc. for distance tree */
480 struct tree_desc_s bl_desc; /* desc. for bit length tree */
483 /* number of codes at each bit length for an optimal tree */
1960 * Each code tree is stored in a compressed form which is itself
2037 /* The static literal tree. Since the bit lengths are imposed, there is no
2039 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
2044 /* The static distance tree. (Actually a trivial tree since all codes use
2197 const ct_data *static_tree; /* static tree or NULL */
2200 int elems; /* max number of elements in the tree */
2219 static void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
2221 static void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
2223 static void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
2224 static void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
2242 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
2243 /* Send a code of the given tree. c and tree must not have side effects */
2246 # define send_code(s, c, tree) \
2248 send_bits(s, tree[c].Code, tree[c].Len); }
2331 int n; /* iterates over tree elements */
2337 /* number of codes at each bit length for an optimal tree */
2395 /* Construct the codes of the static literal tree */
2403 * tree construction to get a canonical Huffman tree (longest code
2408 /* The static distance tree is trivial: */
2484 * Initialize the tree data structures for a new zlib stream.
2518 int n; /* iterates over tree elements */
2531 /* Index within the heap array of least frequent node in the Huffman tree */
2538 #define pqremove(s, tree, top) \
2542 pqdownheap(s, tree, SMALLEST); \
2546 * Compares to subtrees, using the tree depth as tie breaker when
2549 #define smaller(tree, n, m, depth) \
2550 (tree[n].Freq < tree[m].Freq || \
2551 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
2554 * Restore the heap property by moving down the tree starting at node k,
2558 * ct_data *tree; the tree to restore
2562 pqdownheap(deflate_state *s, ct_data *tree, int k)
2569 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
2573 if (smaller(tree, v, s->heap[j], s->depth)) break;
2578 /* And continue down the tree, setting j to the left son of k */
2585 * Compute the optimal bit lengths for a tree and update the total bit length
2588 * above are the tree nodes sorted by increasing frequency.
2597 ct_data *tree = desc->dyn_tree;
2604 int n, m; /* iterate over the tree elements */
2613 * overflow in the case of the bit length tree).
2615 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
2619 bits = tree[tree[n].Dad].Len + 1;
2621 tree[n].Len = (ush)bits;
2622 /* We overwrite tree[n].Dad which is no longer needed */
2629 f = tree[n].Freq;
2642 s->bl_count[bits]--; /* move one leaf down the tree */
2661 if (tree[m].Len != (unsigned) bits) {
2662 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
2663 s->opt_len += ((long)bits - (long)tree[m].Len)
2664 *(long)tree[m].Freq;
2665 tree[m].Len = (ush)bits;
2673 * Generate the codes for a given tree and bit counts (which need not be
2676 * the given tree and the field len is set for all tree elements.
2677 * OUT assertion: the field code is set for all tree elements of non
2680 * ct_data *tree; the tree to decorate
2685 gen_codes(ct_data *tree, int max_code, ushf *bl_count)
2706 int len = tree[n].Len;
2709 tree[n].Code = bi_reverse(next_code[len]++, len);
2711 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
2712 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
2717 * Construct one Huffman tree and assigns the code bit strings and lengths.
2719 * IN assertion: the field freq is set for all tree elements.
2727 ct_data *tree = desc->dyn_tree;
2741 if (tree[n].Freq != 0) {
2745 tree[n].Len = 0;
2756 tree[node].Freq = 1;
2763 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2766 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2768 /* Construct the Huffman tree by repeatedly combining the least two
2771 node = elems; /* next internal node of the tree */
2773 pqremove(s, tree, n); /* n = node of least frequency */
2780 tree[node].Freq = tree[n].Freq + tree[m].Freq;
2782 tree[n].Dad = tree[m].Dad = (ush)node;
2784 if (tree == s->bl_tree) {
2786 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
2791 pqdownheap(s, tree, SMALLEST);
2803 gen_codes ((ct_data *)tree, max_code, s->bl_count);
2807 * Scan a literal or distance tree to determine the frequencies of the codes
2808 * in the bit length tree.
2810 * ct_data *tree; the tree to be scanned
2814 scan_tree(deflate_state *s, ct_data *tree, int max_code)
2816 int n; /* iterates over all tree elements */
2819 int nextlen = tree[0].Len; /* length of next code */
2825 tree[max_code+1].Len = (ush)0xffff; /* guard */
2828 curlen = nextlen; nextlen = tree[n+1].Len;
2853 * Send a literal or distance tree in compressed form, using the codes in
2856 * ct_data *tree; the tree to be scanned
2860 send_tree(deflate_state *s, ct_data *tree, int max_code)
2862 int n; /* iterates over all tree elements */
2865 int nextlen = tree[0].Len; /* length of next code */
2870 /* tree[max_code+1].Len = -1; */ /* guard already set */
2874 curlen = nextlen; nextlen = tree[n+1].Len;
2905 * Construct the Huffman tree for the bit lengths and return the index in
2917 /* Build the bit length tree: */
2919 /* opt_len now includes the length of the tree representations, except
2930 /* Update opt_len to include the bit length tree and counts */
2940 * lengths of the bit length codes, the literal tree and the distance tree.
2959 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
2961 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
2962 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
2964 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
2965 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
3051 * the compressed block data, excluding the tree representations.
3054 /* Build the bit length tree for the above two trees, and get the index
3178 * ct_data *ltree; literal tree
3179 * ct_data *dtree; distance tree
3781 /* Maximum size of dynamic tree. The maximum found in a long but non-
3790 uIntf *, /* bits tree desired/actual depth */
3791 inflate_huft * FAR *, /* bits tree result */
3801 inflate_huft * FAR *, /* literal/length tree result */
3802 inflate_huft * FAR *, /* distance tree result */
3809 inflate_huft * FAR *, /* literal/length tree result */
3810 inflate_huft * FAR *, /* distance tree result */
3863 BTREE, /* get bit lengths tree for a dynamic block */
3884 uInt bb; /* bit length tree depth */
3885 inflate_huft *tb; /* bit length decoding tree */
3897 inflate_huft *hufts; /* single malloc for tree space */
3982 end-of-block. Note however that the static length tree defines
3996 10. In the tree reconstruction algorithm, Code = Code + Increment
4203 Tracev((stderr, "inflate: bits tree ok\n"));
4652 uIntf *bb; /* bits tree desired/actual depth */
4653 inflate_huft * FAR *tb; /* bits tree result */
4666 z->msg = (char*)"oversubscribed dynamic bit lengths tree";
4669 z->msg = (char*)"incomplete dynamic bit lengths tree";
4683 inflate_huft * FAR *tl; /* literal/length tree result */
4684 inflate_huft * FAR *td; /* distance tree result */
4696 /* build literal/length tree */
4701 z->msg = (char*)"oversubscribed literal/length tree";
4704 z->msg = (char*)"incomplete literal/length tree";
4711 /* build distance tree */
4716 z->msg = (char*)"oversubscribed distance tree";
4722 z->msg = (char*)"incomplete distance tree";
4727 z->msg = (char*)"empty distance tree with lengths";
4910 inflate_huft * FAR *tl; /* literal/length tree result */
4911 inflate_huft * FAR *td; /* distance tree result */
5032 inflate_huft *tree; /* pointer into tree */
5034 } code; /* if LEN or DIST, where in tree */
5045 inflate_huft *ltree; /* literal/length/eob tree */
5046 inflate_huft *dtree; /* distance tree */
5111 c->sub.code.tree = c->ltree;
5116 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
5138 c->sub.code.tree = t + t->base;
5157 c->sub.code.tree = c->dtree;
5163 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
5176 c->sub.code.tree = t + t->base;
5375 uInt ml; /* mask for literal/length tree */
5376 uInt md; /* mask for distance tree */