diff options
Diffstat (limited to 'src/trees.c')
-rw-r--r-- | src/trees.c | 99 |
1 files changed, 61 insertions, 38 deletions
diff --git a/src/trees.c b/src/trees.c index 50cf4b4..1fd7759 100644 --- a/src/trees.c +++ b/src/trees.c @@ -1,5 +1,5 @@ /* trees.c -- output deflated data using Huffman coding - * Copyright (C) 1995-2017 Jean-loup Gailly + * Copyright (C) 1995-2012 Jean-loup Gailly * detect_data_type() function provided freely by Cosmin Truta, 2006 * For conditions of distribution and use, see copyright notice in zlib.h */ @@ -36,7 +36,7 @@ #include "deflate.h" -#ifdef ZLIB_DEBUG +#ifdef DEBUG # include <ctype.h> #endif @@ -122,13 +122,13 @@ struct static_tree_desc_s { int max_length; /* max bit length for the codes */ }; -local const static_tree_desc static_l_desc = +local static_tree_desc static_l_desc = {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS}; -local const static_tree_desc static_d_desc = +local static_tree_desc static_d_desc = {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS}; -local const static_tree_desc static_bl_desc = +local static_tree_desc static_bl_desc = {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS}; /* =========================================================================== @@ -152,16 +152,18 @@ local int detect_data_type OF((deflate_state *s)); local unsigned bi_reverse OF((unsigned value, int length)); local void bi_windup OF((deflate_state *s)); local void bi_flush OF((deflate_state *s)); +local void copy_block OF((deflate_state *s, charf *buf, unsigned len, + int header)); #ifdef GEN_TREES_H local void gen_trees_header OF((void)); #endif -#ifndef ZLIB_DEBUG +#ifndef DEBUG # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len) /* Send a code of the given tree. c and tree must not have side effects */ -#else /* !ZLIB_DEBUG */ +#else /* DEBUG */ # define send_code(s, c, tree) \ { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \ send_bits(s, tree[c].Code, tree[c].Len); } @@ -180,7 +182,7 @@ local void gen_trees_header OF((void)); * Send a value on a given number of bits. * IN assertion: length <= 16 and value fits in length bits. */ -#ifdef ZLIB_DEBUG +#ifdef DEBUG local void send_bits OF((deflate_state *s, int value, int length)); local void send_bits(s, value, length) @@ -206,12 +208,12 @@ local void send_bits(s, value, length) s->bi_valid += length; } } -#else /* !ZLIB_DEBUG */ +#else /* !DEBUG */ #define send_bits(s, value, length) \ { int len = length;\ if (s->bi_valid > (int)Buf_size - len) {\ - int val = (int)value;\ + int val = value;\ s->bi_buf |= (ush)val << s->bi_valid;\ put_short(s, s->bi_buf);\ s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\ @@ -221,7 +223,7 @@ local void send_bits(s, value, length) s->bi_valid += len;\ }\ } -#endif /* ZLIB_DEBUG */ +#endif /* DEBUG */ /* the arguments must not have side effects */ @@ -315,7 +317,7 @@ local void tr_static_init() * Genererate the file trees.h describing the static trees. */ #ifdef GEN_TREES_H -# ifndef ZLIB_DEBUG +# ifndef DEBUG # include <stdio.h> # endif @@ -392,7 +394,7 @@ void ZLIB_INTERNAL _tr_init(s) s->bi_buf = 0; s->bi_valid = 0; -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len = 0L; s->bits_sent = 0L; #endif @@ -520,12 +522,12 @@ local void gen_bitlen(s, desc) xbits = 0; if (n >= base) xbits = extra[n-base]; f = tree[n].Freq; - s->opt_len += (ulg)f * (unsigned)(bits + xbits); - if (stree) s->static_len += (ulg)f * (unsigned)(stree[n].Len + xbits); + s->opt_len += (ulg)f * (bits + xbits); + if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits); } if (overflow == 0) return; - Tracev((stderr,"\nbit length overflow\n")); + Trace((stderr,"\nbit length overflow\n")); /* This happens for example on obj2 and pic of the Calgary corpus */ /* Find the first bit length which could increase: */ @@ -552,8 +554,9 @@ local void gen_bitlen(s, desc) m = s->heap[--h]; if (m > max_code) continue; if ((unsigned) tree[m].Len != (unsigned) bits) { - Tracev((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); - s->opt_len += ((ulg)bits - tree[m].Len) * tree[m].Freq; + Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits)); + s->opt_len += ((long)bits - (long)tree[m].Len) + *(long)tree[m].Freq; tree[m].Len = (ush)bits; } n--; @@ -575,7 +578,7 @@ local void gen_codes (tree, max_code, bl_count) ushf *bl_count; /* number of codes at each bit length */ { ush next_code[MAX_BITS+1]; /* next code value for each bit length */ - unsigned code = 0; /* running code value */ + ush code = 0; /* running code value */ int bits; /* bit index */ int n; /* code index */ @@ -583,8 +586,7 @@ local void gen_codes (tree, max_code, bl_count) * without bit reversal. */ for (bits = 1; bits <= MAX_BITS; bits++) { - code = (code + bl_count[bits-1]) << 1; - next_code[bits] = (ush)code; + next_code[bits] = code = (code + bl_count[bits-1]) << 1; } /* Check that the bit counts in bl_count are consistent. The last code * must be all ones. @@ -597,7 +599,7 @@ local void gen_codes (tree, max_code, bl_count) int len = tree[n].Len; if (len == 0) continue; /* Now reverse the bits */ - tree[n].Code = (ush)bi_reverse(next_code[len]++, len); + tree[n].Code = bi_reverse(next_code[len]++, len); Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1)); @@ -819,7 +821,7 @@ local int build_bl_tree(s) if (s->bl_tree[bl_order[max_blindex]].Len != 0) break; } /* Update opt_len to include the bit length tree and counts */ - s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4; + s->opt_len += 3*(max_blindex+1) + 5+5+4; Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", s->opt_len, s->static_len)); @@ -867,17 +869,11 @@ void ZLIB_INTERNAL _tr_stored_block(s, buf, stored_len, last) int last; /* one if this is the last block for a file */ { send_bits(s, (STORED_BLOCK<<1)+last, 3); /* send block type */ - bi_windup(s); /* align on byte boundary */ - put_short(s, (ush)stored_len); - put_short(s, (ush)~stored_len); - zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len); - s->pending += stored_len; -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L; s->compressed_len += (stored_len + 4) << 3; - s->bits_sent += 2*16; - s->bits_sent += stored_len<<3; #endif + copy_block(s, buf, (unsigned)stored_len, 1); /* with header */ } /* =========================================================================== @@ -898,7 +894,7 @@ void ZLIB_INTERNAL _tr_align(s) { send_bits(s, STATIC_TREES<<1, 3); send_code(s, END_BLOCK, static_ltree); -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len += 10L; /* 3 for block type, 7 for EOB */ #endif bi_flush(s); @@ -906,7 +902,7 @@ void ZLIB_INTERNAL _tr_align(s) /* =========================================================================== * Determine the best encoding for the current block: dynamic trees, static - * trees or store, and write out the encoded block. + * trees or store, and output the encoded block to the zip file. */ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) deflate_state *s; @@ -978,7 +974,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) send_bits(s, (STATIC_TREES<<1)+last, 3); compress_block(s, (const ct_data *)static_ltree, (const ct_data *)static_dtree); -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len += 3 + s->static_len; #endif } else { @@ -987,7 +983,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) max_blindex+1); compress_block(s, (const ct_data *)s->dyn_ltree, (const ct_data *)s->dyn_dtree); -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len += 3 + s->opt_len; #endif } @@ -999,7 +995,7 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last) if (last) { bi_windup(s); -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->compressed_len += 7; /* align on byte boundary */ #endif } @@ -1094,7 +1090,7 @@ local void compress_block(s, ltree, dtree) send_code(s, code, dtree); /* send the distance code */ extra = extra_dbits[code]; if (extra != 0) { - dist -= (unsigned)base_dist[code]; + dist -= base_dist[code]; send_bits(s, dist, extra); /* send the extra distance bits */ } } /* literal or match pair ? */ @@ -1197,7 +1193,34 @@ local void bi_windup(s) } s->bi_buf = 0; s->bi_valid = 0; -#ifdef ZLIB_DEBUG +#ifdef DEBUG s->bits_sent = (s->bits_sent+7) & ~7; #endif } + +/* =========================================================================== + * Copy a stored block, storing first the length and its + * one's complement if requested. + */ +local void copy_block(s, buf, len, header) + deflate_state *s; + charf *buf; /* the input data */ + unsigned len; /* its length */ + int header; /* true if block header must be written */ +{ + bi_windup(s); /* align on byte boundary */ + + if (header) { + put_short(s, (ush)len); + put_short(s, (ush)~len); +#ifdef DEBUG + s->bits_sent += 2*16; +#endif + } +#ifdef DEBUG + s->bits_sent += (ulg)len<<3; +#endif + while (len--) { + put_byte(s, *buf++); + } +} |