aboutsummaryrefslogtreecommitdiff
path: root/trees.c
diff options
context:
space:
mode:
authorMark Adler <madler@alumni.caltech.edu>2011-09-09 23:08:07 -0700
committerMark Adler <madler@alumni.caltech.edu>2011-09-09 23:08:07 -0700
commitbdde4e09d21edff02ea5093b7f6eccbf166b272f (patch)
treea64632a98a6bea6e5df864d6e5b6f2e51ea69c1c /trees.c
parent1c71d8b13b54f91ddec361d3053ecce26e6ff761 (diff)
downloadzlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.tar.gz
zlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.tar.bz2
zlib-bdde4e09d21edff02ea5093b7f6eccbf166b272f.zip
zlib 0.92v0.92
Diffstat (limited to 'trees.c')
-rw-r--r--trees.c42
1 files changed, 21 insertions, 21 deletions
diff --git a/trees.c b/trees.c
index eb69d49..f85716e 100644
--- a/trees.c
+++ b/trees.c
@@ -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));
139local void send_tree __P((deflate_state *s, ct_data *tree, int max_code)); 139local void send_tree __P((deflate_state *s, ct_data *tree, int max_code));
140local int build_bl_tree __P((deflate_state *s)); 140local int build_bl_tree __P((deflate_state *s));
141local void send_all_trees __P((deflate_state *s, int lcodes, int dcodes, 141local void send_all_trees __P((deflate_state *s, int lcodes, int dcodes,
142 int blcodes)); 142 int blcodes));
143local void compress_block __P((deflate_state *s, ct_data *ltree, 143local void compress_block __P((deflate_state *s, ct_data *ltree,
144 ct_data *dtree)); 144 ct_data *dtree));
145local void set_data_type __P((deflate_state *s)); 145local void set_data_type __P((deflate_state *s));
146local void send_bits __P((deflate_state *s, int value, int length)); 146local void send_bits __P((deflate_state *s, int value, int length));
147local unsigned bi_reverse __P((unsigned value, int length)); 147local unsigned bi_reverse __P((unsigned value, int length));
148local void bi_windup __P((deflate_state *s)); 148local void bi_windup __P((deflate_state *s));
149local void copy_block __P((deflate_state *s, char *buf, unsigned len, 149local 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}