aboutsummaryrefslogtreecommitdiff
path: root/src/zlib/trees.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/zlib/trees.c')
-rw-r--r--src/zlib/trees.c151
1 files changed, 96 insertions, 55 deletions
diff --git a/src/zlib/trees.c b/src/zlib/trees.c
index 50cf4b4..56e9bb1 100644
--- a/src/zlib/trees.c
+++ b/src/zlib/trees.c
@@ -1,5 +1,5 @@
/* trees.c -- output deflated data using Huffman coding
- * Copyright (C) 1995-2017 Jean-loup Gailly
+ * Copyright (C) 1995-2010 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
@@ -74,6 +74,11 @@ local const uch bl_order[BL_CODES]
* probability, to avoid transmitting the lengths for unused bit length codes.
*/
+#define Buf_size (8 * 2*sizeof(char))
+/* Number of bits used within bi_buf. (bi_buf might be implemented on
+ * more than 16 bits on some systems.)
+ */
+
/* ===========================================================================
* Local data. These are initialized only once.
*/
@@ -122,13 +127,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};
/* ===========================================================================
@@ -146,22 +151,24 @@ local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
local int build_bl_tree OF((deflate_state *s));
local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
int blcodes));
-local void compress_block OF((deflate_state *s, const ct_data *ltree,
- const ct_data *dtree));
+local void compress_block OF((deflate_state *s, ct_data *ltree,
+ ct_data *dtree));
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 +187,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 +213,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 +228,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 +322,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 +399,8 @@ void ZLIB_INTERNAL _tr_init(s)
s->bi_buf = 0;
s->bi_valid = 0;
-#ifdef ZLIB_DEBUG
+ s->last_eob_len = 8; /* enough lookahead for inflate */
+#ifdef DEBUG
s->compressed_len = 0L;
s->bits_sent = 0L;
#endif
@@ -520,12 +528,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 +560,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 +584,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 +592,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 +605,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 +827,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,46 +875,52 @@ 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
-}
-
-/* ===========================================================================
- * Flush the bits in the bit buffer to pending output (leaves at most 7 bits)
- */
-void ZLIB_INTERNAL _tr_flush_bits(s)
- deflate_state *s;
-{
- bi_flush(s);
+ copy_block(s, buf, (unsigned)stored_len, 1); /* with header */
}
/* ===========================================================================
* Send one empty static block to give enough lookahead for inflate.
* This takes 10 bits, of which 7 may remain in the bit buffer.
+ * The current inflate code requires 9 bits of lookahead. If the
+ * last two codes for the previous block (real code plus EOB) were coded
+ * on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
+ * the last real code. In this case we send two empty static blocks instead
+ * of one. (There are no problems if the previous block is stored or fixed.)
+ * To simplify the code, we assume the worst case of last real code encoded
+ * on one bit only.
*/
void ZLIB_INTERNAL _tr_align(s)
deflate_state *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);
+ /* Of the 10 bits for the empty block, we have already sent
+ * (10 - bi_valid) bits. The lookahead for the last real code (before
+ * the EOB of the previous block) was thus at least one plus the length
+ * of the EOB plus what we have just sent of the empty static block.
+ */
+ if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
+ send_bits(s, STATIC_TREES<<1, 3);
+ send_code(s, END_BLOCK, static_ltree);
+#ifdef DEBUG
+ s->compressed_len += 10L;
+#endif
+ bi_flush(s);
+ }
+ s->last_eob_len = 7;
}
/* ===========================================================================
* 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;
@@ -976,18 +990,16 @@ void ZLIB_INTERNAL _tr_flush_block(s, buf, stored_len, last)
} else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
#endif
send_bits(s, (STATIC_TREES<<1)+last, 3);
- compress_block(s, (const ct_data *)static_ltree,
- (const ct_data *)static_dtree);
-#ifdef ZLIB_DEBUG
+ compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
+#ifdef DEBUG
s->compressed_len += 3 + s->static_len;
#endif
} else {
send_bits(s, (DYN_TREES<<1)+last, 3);
send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
max_blindex+1);
- compress_block(s, (const ct_data *)s->dyn_ltree,
- (const ct_data *)s->dyn_dtree);
-#ifdef ZLIB_DEBUG
+ compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
+#ifdef DEBUG
s->compressed_len += 3 + s->opt_len;
#endif
}
@@ -999,7 +1011,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
}
@@ -1063,8 +1075,8 @@ int ZLIB_INTERNAL _tr_tally (s, dist, lc)
*/
local void compress_block(s, ltree, dtree)
deflate_state *s;
- const ct_data *ltree; /* literal tree */
- const ct_data *dtree; /* distance tree */
+ ct_data *ltree; /* literal tree */
+ ct_data *dtree; /* distance tree */
{
unsigned dist; /* distance of matched string */
int lc; /* match length or unmatched char (if dist == 0) */
@@ -1094,7 +1106,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 ? */
@@ -1106,6 +1118,7 @@ local void compress_block(s, ltree, dtree)
} while (lx < s->last_lit);
send_code(s, END_BLOCK, ltree);
+ s->last_eob_len = ltree[END_BLOCK].Len;
}
/* ===========================================================================
@@ -1197,7 +1210,35 @@ 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 */
+ s->last_eob_len = 8; /* enough lookahead for inflate */
+
+ 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++);
+ }
+}