Lines Matching +defs:copy +defs:tree
9 * compliance with the License. Please obtain a copy of the License at
212 ush dad; /* father node in Huffman tree */
225 ct_data *dyn_tree; /* the dynamic tree */
227 static_tree_desc *stat_desc; /* the corresponding static tree */
335 struct ct_data_s dyn_ltree[HEAP_SIZE]; /* literal and length tree */
336 struct ct_data_s dyn_dtree[2*D_CODES+1]; /* distance tree */
337 struct ct_data_s bl_tree[2*BL_CODES+1]; /* Huffman tree for bit lengths */
339 struct tree_desc_s l_desc; /* desc. for literal tree */
340 struct tree_desc_s d_desc; /* desc. for distance tree */
341 struct tree_desc_s bl_desc; /* desc. for bit length tree */
344 /* number of codes at each bit length for an optimal tree */
1473 * Each code tree is stored in a compressed form which is itself
1544 /* The static literal tree. Since the bit lengths are imposed, there is no
1546 * The codes 286 and 287 are needed to build a canonical tree (see ct_init
1551 /* The static distance tree. (Actually a trivial tree since all codes use
1571 ct_data *static_tree; /* static tree or NULL */
1574 int elems; /* max number of elements in the tree */
1593 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
1595 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
1597 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
1598 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
1612 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
1613 /* Send a code of the given tree. c and tree must not have side effects */
1616 # define send_code(s, c, tree) \
1618 send_bits(s, tree[c].Code, tree[c].Len); }
1694 int n; /* iterates over tree elements */
1700 /* number of codes at each bit length for an optimal tree */
1735 /* Construct the codes of the static literal tree */
1743 * tree construction to get a canonical Huffman tree (longest code
1748 /* The static distance tree is trivial: */
1756 * Initialize the tree data structures for a new zlib stream.
1794 int n; /* iterates over tree elements */
1807 /* Index within the heap array of least frequent node in the Huffman tree */
1814 #define pqremove(s, tree, top) \
1818 pqdownheap(s, tree, SMALLEST); \
1822 * Compares to subtrees, using the tree depth as tie breaker when
1825 #define smaller(tree, n, m, depth) \
1826 (tree[n].Freq < tree[m].Freq || \
1827 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
1830 * Restore the heap property by moving down the tree starting at node k,
1835 local void pqdownheap(s, tree, k)
1837 ct_data *tree; /* the tree to restore */
1845 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
1849 if (smaller(tree, v, s->heap[j], s->depth)) break;
1854 /* And continue down the tree, setting j to the left son of k */
1861 * Compute the optimal bit lengths for a tree and update the total bit length
1864 * above are the tree nodes sorted by increasing frequency.
1872 tree_desc *desc; /* the tree descriptor */
1874 ct_data *tree = desc->dyn_tree;
1881 int n, m; /* iterate over the tree elements */
1890 * overflow in the case of the bit length tree).
1892 tree[s->heap[s->heap_max]].Len = 0; /* root of the heap */
1896 bits = tree[tree[n].Dad].Len + 1;
1898 tree[n].Len = (ush)bits;
1899 /* We overwrite tree[n].Dad which is no longer needed */
1906 f = tree[n].Freq;
1919 s->bl_count[bits]--; /* move one leaf down the tree */
1938 if (tree[m].Len != (unsigned) bits) {
1939 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
1940 s->opt_len += ((long)bits - (long)tree[m].Len)
1941 *(long)tree[m].Freq;
1942 tree[m].Len = (ush)bits;
1950 * Generate the codes for a given tree and bit counts (which need not be
1953 * the given tree and the field len is set for all tree elements.
1954 * OUT assertion: the field code is set for all tree elements of non
1957 local void gen_codes (tree, max_code, bl_count)
1958 ct_data *tree; /* the tree to decorate */
1981 int len = tree[n].Len;
1984 tree[n].Code = bi_reverse(next_code[len]++, len);
1986 Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
1987 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
1992 * Construct one Huffman tree and assigns the code bit strings and lengths.
1994 * IN assertion: the field freq is set for all tree elements.
2001 tree_desc *desc; /* the tree descriptor */
2003 ct_data *tree = desc->dyn_tree;
2017 if (tree[n].Freq != 0) {
2021 tree[n].Len = 0;
2032 tree[node].Freq = 1;
2039 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
2042 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
2044 /* Construct the Huffman tree by repeatedly combining the least two
2047 node = elems; /* next internal node of the tree */
2049 pqremove(s, tree, n); /* n = node of least frequency */
2056 tree[node].Freq = tree[n].Freq + tree[m].Freq;
2058 tree[n].Dad = tree[m].Dad = (ush)node;
2060 if (tree == s->bl_tree) {
2062 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
2067 pqdownheap(s, tree, SMALLEST);
2079 gen_codes ((ct_data *)tree, max_code, s->bl_count);
2083 * Scan a literal or distance tree to determine the frequencies of the codes
2084 * in the bit length tree.
2086 local void scan_tree (s, tree, max_code)
2088 ct_data *tree; /* the tree to be scanned */
2091 int n; /* iterates over all tree elements */
2094 int nextlen = tree[0].Len; /* length of next code */
2100 tree[max_code+1].Len = (ush)0xffff; /* guard */
2103 curlen = nextlen; nextlen = tree[n+1].Len;
2128 * Send a literal or distance tree in compressed form, using the codes in
2131 local void send_tree (s, tree, max_code)
2133 ct_data *tree; /* the tree to be scanned */
2136 int n; /* iterates over all tree elements */
2139 int nextlen = tree[0].Len; /* length of next code */
2144 /* tree[max_code+1].Len = -1; */ /* guard already set */
2148 curlen = nextlen; nextlen = tree[n+1].Len;
2179 * Construct the Huffman tree for the bit lengths and return the index in
2191 /* Build the bit length tree: */
2193 /* opt_len now includes the length of the tree representations, except
2204 /* Update opt_len to include the bit length tree and counts */
2214 * lengths of the bit length codes, the literal tree and the distance tree.
2219 int lcodes, dcodes, blcodes; /* number of codes for each tree */
2234 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
2236 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1); /* literal tree */
2237 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
2239 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1); /* distance tree */
2240 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
2327 * the compressed block data, excluding the tree representations.
2330 /* Build the bit length tree for the above two trees, and get the index
2475 ct_data *ltree; /* literal tree */
2476 ct_data *dtree; /* distance tree */
2697 uIntf *, /* bits tree desired/actual depth */
2698 inflate_huft * FAR *, /* bits tree result */
2707 inflate_huft * FAR *, /* literal/length tree result */
2708 inflate_huft * FAR *, /* distance tree result */
2714 inflate_huft * FAR *, /* literal/length tree result */
2715 inflate_huft * FAR *)); /* distance tree result */
3078 BTREE, /* get bit lengths tree for a dynamic block */
3088 uInt left; /* if STORED, bytes left to copy */
3093 uInt bb; /* bit length tree depth */
3094 inflate_huft *tb; /* bit length decoding tree */
3148 /* copy as much as possible from the sliding window to the output area */
3202 end-of-block. Note however that the static length tree defines
3216 10. In the tree reconstruction algorithm, Code = Code + Increment
3292 /* copy input/output information to locals (UPDATE macro restores) */
3422 Tracev((stderr, "inflate: bits tree ok\n"));
3581 /* while there is input ready, copy to output buffer, moving
3918 uIntf *bb; /* bits tree desired/actual depth */
3919 inflate_huft * FAR *tb; /* bits tree result */
3926 z->msg = "oversubscribed dynamic bit lengths tree";
3930 z->msg = "incomplete dynamic bit lengths tree";
3943 inflate_huft * FAR *tl; /* literal/length tree result */
3944 inflate_huft * FAR *td; /* distance tree result */
3949 /* build literal/length tree */
3953 z->msg = "oversubscribed literal/length tree";
3957 z->msg = "incomplete literal/length tree";
3963 /* build distance tree */
3967 z->msg = "oversubscribed literal/length tree";
3974 z->msg = "incomplete literal/length tree";
4025 inflate_huft * FAR *tl; /* literal/length tree result */
4026 inflate_huft * FAR *td; /* distance tree result */
4125 inflate_huft *tree; /* pointer into tree */
4127 } code; /* if LEN or DIST, where in tree */
4131 uInt dist; /* distance back to copy from */
4132 } copy; /* if EXT or COPY, where and how much */
4138 inflate_huft *ltree; /* literal/length/eob tree */
4139 inflate_huft *dtree; /* distance tree */
4179 Bytef *f; /* pointer to copy strings from */
4182 /* copy input/output information to locals (UPDATE macro restores) */
4203 c->sub.code.tree = c->ltree;
4208 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4222 c->sub.copy.get = e & 15;
4230 c->sub.code.tree = t->next;
4244 j = c->sub.copy.get;
4249 c->sub.code.tree = c->dtree;
4255 t = c->sub.code.tree + ((uInt)b & inflate_mask[j]);
4260 c->sub.copy.get = e & 15;
4261 c->sub.copy.dist = t->base;
4268 c->sub.code.tree = t->next;
4276 j = c->sub.copy.get;
4278 c->sub.copy.dist += (uInt)b & inflate_mask[j];
4280 Tracevv((stderr, "inflate: distance %u\n", c->sub.copy.dist));
4284 f = (uInt)(q - s->window) < c->sub.copy.dist ?
4285 s->end - (c->sub.copy.dist - (q - s->window)) :
4286 q - c->sub.copy.dist;
4288 f = q - c->sub.copy.dist;
4289 if ((uInt)(q - s->window) < c->sub.copy.dist)
4290 f = s->end - (c->sub.copy.dist - (q - s->window));
4339 /* copy as much as possible from the sliding window to the output area */
4352 /* compute number of bytes to copy as far as end of window */
4365 /* copy as far as end of window */
4372 /* see if more to copy at beginning of window */
4380 /* compute bytes to copy */
4393 /* copy */
4445 uInt ml; /* mask for literal/length tree */
4446 uInt md; /* mask for distance tree */
4447 uInt c; /* bytes to copy */
4448 uInt d; /* distance back to copy from */
4449 Bytef *r; /* copy source pointer */
4482 /* decode distance base of block to copy */
4496 /* do the copy */
4499 { /* just copy */
4510 c -= e; /* copy to end of window */
4514 r = s->window; /* copy rest from start of window */
4517 do { /* copy all or what's left */