diff options
author | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:08:07 -0700 |
---|---|---|
committer | Mark Adler <madler@alumni.caltech.edu> | 2011-09-09 23:08:07 -0700 |
commit | bdde4e09d21edff02ea5093b7f6eccbf166b272f (patch) | |
tree | a64632a98a6bea6e5df864d6e5b6f2e51ea69c1c /trees.c | |
parent | 1c71d8b13b54f91ddec361d3053ecce26e6ff761 (diff) | |
download | zlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.tar.gz zlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.tar.bz2 zlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.zip |
zlib 0.92v0.92
Diffstat (limited to 'trees.c')
-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 | } |