diff options
Diffstat (limited to '')
| -rw-r--r-- | trees.c | 42 |
1 files changed, 21 insertions, 21 deletions
| @@ -29,7 +29,7 @@ | |||
| 29 | * Addison-Wesley, 1983. ISBN 0-201-06672-6. | 29 | * Addison-Wesley, 1983. ISBN 0-201-06672-6. |
| 30 | */ | 30 | */ |
| 31 | 31 | ||
| 32 | /* $Id: trees.c,v 1.4 1995/05/01 16:53:44 jloup Exp $ */ | 32 | /* $Id: trees.c,v 1.5 1995/05/03 17:27:12 jloup Exp $ */ |
| 33 | 33 | ||
| 34 | #include "deflate.h" | 34 | #include "deflate.h" |
| 35 | 35 | ||
| @@ -139,15 +139,15 @@ local void scan_tree __P((deflate_state *s, ct_data *tree, int max_code)); | |||
| 139 | local void send_tree __P((deflate_state *s, ct_data *tree, int max_code)); | 139 | local void send_tree __P((deflate_state *s, ct_data *tree, int max_code)); |
| 140 | local int build_bl_tree __P((deflate_state *s)); | 140 | local int build_bl_tree __P((deflate_state *s)); |
| 141 | local void send_all_trees __P((deflate_state *s, int lcodes, int dcodes, | 141 | local void send_all_trees __P((deflate_state *s, int lcodes, int dcodes, |
| 142 | int blcodes)); | 142 | int blcodes)); |
| 143 | local void compress_block __P((deflate_state *s, ct_data *ltree, | 143 | local void compress_block __P((deflate_state *s, ct_data *ltree, |
| 144 | ct_data *dtree)); | 144 | ct_data *dtree)); |
| 145 | local void set_data_type __P((deflate_state *s)); | 145 | local void set_data_type __P((deflate_state *s)); |
| 146 | local void send_bits __P((deflate_state *s, int value, int length)); | 146 | local void send_bits __P((deflate_state *s, int value, int length)); |
| 147 | local unsigned bi_reverse __P((unsigned value, int length)); | 147 | local unsigned bi_reverse __P((unsigned value, int length)); |
| 148 | local void bi_windup __P((deflate_state *s)); | 148 | local void bi_windup __P((deflate_state *s)); |
| 149 | local void copy_block __P((deflate_state *s, char *buf, unsigned len, | 149 | local void copy_block __P((deflate_state *s, char *buf, unsigned len, |
| 150 | int header)); | 150 | int header)); |
| 151 | 151 | ||
| 152 | #ifndef DEBUG | 152 | #ifndef DEBUG |
| 153 | # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) | 153 | # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) |
| @@ -243,7 +243,7 @@ void ct_init(s) | |||
| 243 | deflate_state *s; | 243 | deflate_state *s; |
| 244 | { | 244 | { |
| 245 | if (static_dtree[0].Len == 0) { | 245 | if (static_dtree[0].Len == 0) { |
| 246 | ct_static_init(); /* To do: at compile time */ | 246 | ct_static_init(); /* To do: at compile time */ |
| 247 | } | 247 | } |
| 248 | 248 | ||
| 249 | s->compressed_len = 0L; | 249 | s->compressed_len = 0L; |
| @@ -324,9 +324,9 @@ local void pqdownheap(s, tree, k) | |||
| 324 | while (j <= s->heap_len) { | 324 | while (j <= s->heap_len) { |
| 325 | /* Set j to the smallest of the two sons: */ | 325 | /* Set j to the smallest of the two sons: */ |
| 326 | if (j < s->heap_len && | 326 | if (j < s->heap_len && |
| 327 | smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { | 327 | smaller(tree, s->heap[j+1], s->heap[j], s->depth)) { |
| 328 | j++; | 328 | j++; |
| 329 | } | 329 | } |
| 330 | /* Exit if v is smaller than both sons */ | 330 | /* Exit if v is smaller than both sons */ |
| 331 | if (smaller(tree, v, s->heap[j], s->depth)) break; | 331 | if (smaller(tree, v, s->heap[j], s->depth)) break; |
| 332 | 332 | ||
| @@ -420,7 +420,7 @@ local void gen_bitlen(s, desc) | |||
| 420 | if (tree[m].Len != (unsigned) bits) { | 420 | if (tree[m].Len != (unsigned) bits) { |
| 421 | Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); | 421 | Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); |
| 422 | s->opt_len += ((long)bits - (long)tree[m].Len) | 422 | s->opt_len += ((long)bits - (long)tree[m].Len) |
| 423 | *(long)tree[m].Freq; | 423 | *(long)tree[m].Freq; |
| 424 | tree[m].Len = (ush)bits; | 424 | tree[m].Len = (ush)bits; |
| 425 | } | 425 | } |
| 426 | n--; | 426 | n--; |
| @@ -686,7 +686,7 @@ local int build_bl_tree(s) | |||
| 686 | /* Update opt_len to include the bit length tree and counts */ | 686 | /* Update opt_len to include the bit length tree and counts */ |
| 687 | s->opt_len += 3*(max_blindex+1) + 5+5+4; | 687 | s->opt_len += 3*(max_blindex+1) + 5+5+4; |
| 688 | Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", | 688 | Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", |
| 689 | s->opt_len, s->static_len)); | 689 | s->opt_len, s->static_len)); |
| 690 | 690 | ||
| 691 | return max_blindex; | 691 | return max_blindex; |
| 692 | } | 692 | } |
| @@ -758,11 +758,11 @@ ulg ct_flush_block(s, buf, stored_len, eof) | |||
| 758 | /* Construct the literal and distance trees */ | 758 | /* Construct the literal and distance trees */ |
| 759 | build_tree(s, (tree_desc *)(&(s->l_desc))); | 759 | build_tree(s, (tree_desc *)(&(s->l_desc))); |
| 760 | Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, | 760 | Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len, |
| 761 | s->static_len)); | 761 | s->static_len)); |
| 762 | 762 | ||
| 763 | build_tree(s, (tree_desc *)(&(s->d_desc))); | 763 | build_tree(s, (tree_desc *)(&(s->d_desc))); |
| 764 | Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, | 764 | Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len, |
| 765 | s->static_len)); | 765 | s->static_len)); |
| 766 | /* At this point, opt_len and static_len are the total bit lengths of | 766 | /* At this point, opt_len and static_len are the total bit lengths of |
| 767 | * the compressed block data, excluding the tree representations. | 767 | * the compressed block data, excluding the tree representations. |
| 768 | */ | 768 | */ |
| @@ -813,7 +813,7 @@ ulg ct_flush_block(s, buf, stored_len, eof) | |||
| 813 | * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to | 813 | * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to |
| 814 | * transform a block into a stored block. | 814 | * transform a block into a stored block. |
| 815 | */ | 815 | */ |
| 816 | ct_stored_block(s, buf, stored_len, eof); | 816 | ct_stored_block(s, buf, stored_len, eof); |
| 817 | 817 | ||
| 818 | #ifdef FORCE_STATIC | 818 | #ifdef FORCE_STATIC |
| 819 | } else if (static_lenb >= 0) { /* force static trees */ | 819 | } else if (static_lenb >= 0) { /* force static trees */ |
| @@ -826,7 +826,7 @@ ulg ct_flush_block(s, buf, stored_len, eof) | |||
| 826 | } else { | 826 | } else { |
| 827 | send_bits(s, (DYN_TREES<<1)+eof, 3); | 827 | send_bits(s, (DYN_TREES<<1)+eof, 3); |
| 828 | send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, | 828 | send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1, |
| 829 | max_blindex+1); | 829 | max_blindex+1); |
| 830 | compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); | 830 | compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree); |
| 831 | s->compressed_len += 3 + s->opt_len; | 831 | s->compressed_len += 3 + s->opt_len; |
| 832 | } | 832 | } |
| @@ -858,7 +858,7 @@ int ct_tally (s, dist, lc) | |||
| 858 | /* lc is the unmatched char */ | 858 | /* lc is the unmatched char */ |
| 859 | s->dyn_ltree[lc].Freq++; | 859 | s->dyn_ltree[lc].Freq++; |
| 860 | } else { | 860 | } else { |
| 861 | s->matches++; | 861 | s->matches++; |
| 862 | /* Here, lc is the match length - MIN_MATCH */ | 862 | /* Here, lc is the match length - MIN_MATCH */ |
| 863 | dist--; /* dist = match distance - 1 */ | 863 | dist--; /* dist = match distance - 1 */ |
| 864 | Assert((ush)dist < (ush)MAX_DIST(s) && | 864 | Assert((ush)dist < (ush)MAX_DIST(s) && |
| @@ -877,7 +877,7 @@ int ct_tally (s, dist, lc) | |||
| 877 | int dcode; | 877 | int dcode; |
| 878 | for (dcode = 0; dcode < D_CODES; dcode++) { | 878 | for (dcode = 0; dcode < D_CODES; dcode++) { |
| 879 | out_length += (ulg)s->dyn_dtree[dcode].Freq * | 879 | out_length += (ulg)s->dyn_dtree[dcode].Freq * |
| 880 | (5L+extra_dbits[dcode]); | 880 | (5L+extra_dbits[dcode]); |
| 881 | } | 881 | } |
| 882 | out_length >>= 3; | 882 | out_length >>= 3; |
| 883 | Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", | 883 | Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ", |
| @@ -907,7 +907,7 @@ local void compress_block(s, ltree, dtree) | |||
| 907 | int extra; /* number of extra bits to send */ | 907 | int extra; /* number of extra bits to send */ |
| 908 | 908 | ||
| 909 | if (s->last_lit != 0) do { | 909 | if (s->last_lit != 0) do { |
| 910 | dist = s->d_buf[lx]; | 910 | dist = s->d_buf[lx]; |
| 911 | lc = s->l_buf[lx++]; | 911 | lc = s->l_buf[lx++]; |
| 912 | if (dist == 0) { | 912 | if (dist == 0) { |
| 913 | send_code(s, lc, ltree); /* send a literal byte */ | 913 | send_code(s, lc, ltree); /* send a literal byte */ |
| @@ -921,7 +921,7 @@ local void compress_block(s, ltree, dtree) | |||
| 921 | lc -= base_length[code]; | 921 | lc -= base_length[code]; |
| 922 | send_bits(s, lc, extra); /* send the extra length bits */ | 922 | send_bits(s, lc, extra); /* send the extra length bits */ |
| 923 | } | 923 | } |
| 924 | dist--; /* dist is now the match distance - 1 */ | 924 | dist--; /* dist is now the match distance - 1 */ |
| 925 | code = d_code(dist); | 925 | code = d_code(dist); |
| 926 | Assert (code < D_CODES, "bad d_code"); | 926 | Assert (code < D_CODES, "bad d_code"); |
| 927 | 927 | ||
| @@ -933,8 +933,8 @@ local void compress_block(s, ltree, dtree) | |||
| 933 | } | 933 | } |
| 934 | } /* literal or match pair ? */ | 934 | } /* literal or match pair ? */ |
| 935 | 935 | ||
| 936 | /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ | 936 | /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */ |
| 937 | Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); | 937 | Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow"); |
| 938 | 938 | ||
| 939 | } while (lx < s->last_lit); | 939 | } while (lx < s->last_lit); |
| 940 | 940 | ||
| @@ -1055,6 +1055,6 @@ local void copy_block(s, buf, len, header) | |||
| 1055 | s->bits_sent += (ulg)len<<3; | 1055 | s->bits_sent += (ulg)len<<3; |
| 1056 | #endif | 1056 | #endif |
| 1057 | while (len--) { | 1057 | while (len--) { |
| 1058 | put_byte(s, *buf++); | 1058 | put_byte(s, *buf++); |
| 1059 | } | 1059 | } |
| 1060 | } | 1060 | } |
