/* trees.c -- output deflated data using Huffman coding
- * Copyright (C) 1995-1998 Jean-loup Gailly
- * For conditions of distribution and use, see copyright notice in zlib.h
+ * Copyright (C) 1995-2003 Jean-loup Gailly
+ * For conditions of distribution and use, see copyright notice in zlib.h
*/
/*
#endif /* DEBUG */
-#ifndef MAX
-#define MAX(a,b) ((a) >= (b) ? (a) : (b))
-#endif
/* the arguments must not have side effects */
/* ===========================================================================
Assert (header != NULL, "Can't open trees.h");
fprintf(header,
- "/* header created automatically with -DGEN_TREES_H */\n\n");
+ "/* header created automatically with -DGEN_TREES_H */\n\n");
fprintf(header, "local const ct_data static_ltree[L_CODES+2] = {\n");
for (i = 0; i < L_CODES+2; i++) {
- fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
- static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
+ fprintf(header, "{{%3u},{%3u}}%s", static_ltree[i].Code,
+ static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
}
fprintf(header, "local const ct_data static_dtree[D_CODES] = {\n");
for (i = 0; i < D_CODES; i++) {
- fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
- static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
+ fprintf(header, "{{%2u},{%2u}}%s", static_dtree[i].Code,
+ static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
}
fprintf(header, "const uch _dist_code[DIST_CODE_LEN] = {\n");
for (i = 0; i < DIST_CODE_LEN; i++) {
- fprintf(header, "%2u%s", _dist_code[i],
- SEPARATOR(i, DIST_CODE_LEN-1, 20));
+ fprintf(header, "%2u%s", _dist_code[i],
+ SEPARATOR(i, DIST_CODE_LEN-1, 20));
}
fprintf(header, "const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
- fprintf(header, "%2u%s", _length_code[i],
- SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
+ fprintf(header, "%2u%s", _length_code[i],
+ SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
}
fprintf(header, "local const int base_length[LENGTH_CODES] = {\n");
for (i = 0; i < LENGTH_CODES; i++) {
- fprintf(header, "%1u%s", base_length[i],
- SEPARATOR(i, LENGTH_CODES-1, 20));
+ fprintf(header, "%1u%s", base_length[i],
+ SEPARATOR(i, LENGTH_CODES-1, 20));
}
fprintf(header, "local const int base_dist[D_CODES] = {\n");
for (i = 0; i < D_CODES; i++) {
- fprintf(header, "%5u%s", base_dist[i],
- SEPARATOR(i, D_CODES-1, 10));
+ fprintf(header, "%5u%s", base_dist[i],
+ SEPARATOR(i, D_CODES-1, 10));
}
fclose(header);
int bits; /* bit length */
int xbits; /* extra bits */
ush f; /* frequency */
- int Overflow = 0; /* number of elements with bit length too large */
+ int overflow = 0; /* number of elements with bit length too large */
for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
n = s->heap[h];
bits = tree[tree[n].Dad].Len + 1;
- if (bits > max_length) bits = max_length, Overflow++;
+ if (bits > max_length) bits = max_length, overflow++;
tree[n].Len = (ush)bits;
/* We overwrite tree[n].Dad which is no longer needed */
s->opt_len += (ulg)f * (bits + xbits);
if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
}
- if (Overflow == 0) return;
+ if (overflow == 0) return;
Trace((stderr,"\nbit length overflow\n"));
/* This happens for example on obj2 and pic of the Calgary corpus */
/* The brother of the overflow item also moves one step up,
* but this does not affect bl_count[max_length]
*/
- Overflow -= 2;
- } while (Overflow > 0);
+ overflow -= 2;
+ } while (overflow > 0);
/* Now recompute all bit lengths, scanning in increasing frequency.
* h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
/* Create a new node father of n and m */
tree[node].Freq = tree[n].Freq + tree[m].Freq;
- s->depth[node] = (uch) (MAX(s->depth[n], s->depth[m]) + 1);
+ s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
+ s->depth[n] : s->depth[m]) + 1);
tree[n].Dad = tree[m].Dad = (ush)node;
#ifdef DUMP_BL_TREE
if (tree == s->bl_tree) {
/* Build the Huffman trees unless a stored block is forced */
if (s->level > 0) {
- /* Check if the file is ascii or binary */
- if (s->data_type == Z_UNKNOWN) set_data_type(s);
+ /* Check if the file is ascii or binary */
+ if (s->strm->data_type == Z_UNKNOWN) set_data_type(s);
- /* Construct the literal and distance trees */
- build_tree(s, (tree_desc *)(&(s->l_desc)));
- Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
- s->static_len));
+ /* Construct the literal and distance trees */
+ build_tree(s, (tree_desc *)(&(s->l_desc)));
+ Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
+ s->static_len));
- build_tree(s, (tree_desc *)(&(s->d_desc)));
- Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
- s->static_len));
- /* At this point, opt_len and static_len are the total bit lengths of
- * the compressed block data, excluding the tree representations.
- */
+ build_tree(s, (tree_desc *)(&(s->d_desc)));
+ Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
+ s->static_len));
+ /* At this point, opt_len and static_len are the total bit lengths of
+ * the compressed block data, excluding the tree representations.
+ */
- /* Build the bit length tree for the above two trees, and get the index
- * in bl_order of the last bit length code to send.
- */
- max_blindex = build_bl_tree(s);
+ /* Build the bit length tree for the above two trees, and get the index
+ * in bl_order of the last bit length code to send.
+ */
+ max_blindex = build_bl_tree(s);
- /* Determine the best encoding. Compute first the block length in bytes*/
- opt_lenb = (s->opt_len+3+7)>>3;
- static_lenb = (s->static_len+3+7)>>3;
+ /* Determine the best encoding. Compute the block lengths in bytes. */
+ opt_lenb = (s->opt_len+3+7)>>3;
+ static_lenb = (s->static_len+3+7)>>3;
- Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
- opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
- s->last_lit));
+ Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
+ opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
+ s->last_lit));
- if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
+ if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
} else {
Assert(buf != (char*)0, "lost buf");
- opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
+ opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
}
#ifdef FORCE_STORED
} /* literal or match pair ? */
/* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
- Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
+ Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
+ "pendingBuf overflow");
} while (lx < s->last_lit);
while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
- s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
+ s->strm->data_type = bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII;
}
/* ===========================================================================
s->last_eob_len = 8; /* enough lookahead for inflate */
if (header) {
- put_short(s, (ush)len);
+ put_short(s, (ush)len);
put_short(s, (ush)~len);
#ifdef DEBUG
s->bits_sent += 2*16;