59 #define REPZ_11_138 18
63 = {0,0,0,0,0,0,0,0,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,0};
66 = {0,0,0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9,10,10,11,11,12,12,13,13};
69 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
72 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
81 #define DIST_CODE_LEN 512
83 #if defined(GEN_TREES_H) || !defined(STDC)
150 const ct_data *dtree));
159 local void gen_trees_header
OF((
void));
163 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
167 # define send_code(s, c, tree) \
168 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
169 send_bits(s, tree[c].Code, tree[c].Len); }
176 #define put_short(s, w) { \
177 put_byte(s, (uch)((w) & 0xff)); \
178 put_byte(s, (uch)((ush)(w) >> 8)); \
190 Tracevv((stderr,
" l %2d v %4x ", length, value));
191 Assert(length > 0 && length <= 15,
"invalid length");
192 s->bits_sent += (
ulg)length;
198 if (s->bi_valid > (
int)Buf_size - length) {
199 s->bi_buf |= (
ush)value << s->bi_valid;
201 s->bi_buf = (
ush)value >> (Buf_size - s->bi_valid);
202 s->bi_valid += length - Buf_size;
204 s->bi_buf |= (
ush)value << s->bi_valid;
205 s->bi_valid += length;
210 #define send_bits(s, value, length) \
212 if (s->bi_valid > (int)Buf_size - len) {\
214 s->bi_buf |= (ush)val << s->bi_valid;\
215 put_short(s, s->bi_buf);\
216 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
217 s->bi_valid += len - Buf_size;\
219 s->bi_buf |= (ush)(value) << s->bi_valid;\
233 #if defined(GEN_TREES_H) || !defined(STDC)
234 static int static_init_done = 0;
240 ush bl_count[MAX_BITS+1];
243 if (static_init_done)
return;
246 #ifdef NO_INIT_GLOBAL_POINTERS
256 for (code = 0; code < LENGTH_CODES-1; code++) {
262 Assert (length == 256,
"tr_static_init: length != 256");
271 for (code = 0 ; code < 16; code++) {
277 Assert (dist == 256,
"tr_static_init: dist != 256");
279 for ( ; code < D_CODES; code++) {
285 Assert (dist == 256,
"tr_static_init: 256+dist != 512");
288 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
290 while (n <= 143)
static_ltree[n++].Len = 8, bl_count[8]++;
291 while (n <= 255)
static_ltree[n++].Len = 9, bl_count[9]++;
292 while (n <= 279)
static_ltree[n++].Len = 7, bl_count[7]++;
293 while (n <= 287)
static_ltree[n++].Len = 8, bl_count[8]++;
301 for (n = 0; n < D_CODES; n++) {
305 static_init_done = 1;
321 # define SEPARATOR(i, last, width) \
322 ((i) == (last)? "\n};\n\n" : \
323 ((i) % (width) == (width)-1 ? ",\n" : ", "))
325 void gen_trees_header()
327 FILE *header = fopen(
"trees.h",
"w");
330 Assert (header != NULL,
"Can't open trees.h");
332 "/* header created automatically with -DGEN_TREES_H */\n\n");
334 fprintf(header,
"local const ct_data static_ltree[L_CODES+2] = {\n");
335 for (i = 0; i < L_CODES+2; i++) {
336 fprintf(header,
"{{%3u},{%3u}}%s",
static_ltree[i].Code,
340 fprintf(header,
"local const ct_data static_dtree[D_CODES] = {\n");
341 for (i = 0; i < D_CODES; i++) {
342 fprintf(header,
"{{%2u},{%2u}}%s",
static_dtree[i].Code,
346 fprintf(header,
"const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
349 SEPARATOR(i, DIST_CODE_LEN-1, 20));
353 "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
354 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
356 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
359 fprintf(header,
"local const int base_length[LENGTH_CODES] = {\n");
360 for (i = 0; i < LENGTH_CODES; i++) {
362 SEPARATOR(i, LENGTH_CODES-1, 20));
365 fprintf(header,
"local const int base_dist[D_CODES] = {\n");
366 for (i = 0; i < D_CODES; i++) {
368 SEPARATOR(i, D_CODES-1, 10));
382 s->l_desc.dyn_tree = s->dyn_ltree;
385 s->d_desc.dyn_tree = s->dyn_dtree;
388 s->bl_desc.dyn_tree = s->bl_tree;
394 s->compressed_len = 0
L;
410 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
411 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
412 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
415 s->opt_len = s->static_len = 0
L;
416 s->last_lit = s->matches = 0;
427 #define pqremove(s, tree, top) \
429 top = s->heap[SMALLEST]; \
430 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
431 pqdownheap(s, tree, SMALLEST); \
438 #define smaller(tree, n, m, depth) \
439 (tree[n].Freq < tree[m].Freq || \
440 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
452 while (j <= s->heap_len) {
454 if (j < s->heap_len &&
455 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
459 if (
smaller(tree, v, s->heap[j], s->depth))
break;
462 s->heap[k] = s->heap[j]; k = j;
482 ct_data *tree = desc->dyn_tree;
483 int max_code = desc->max_code;
484 const ct_data *stree = desc->stat_desc->static_tree;
485 const intf *extra = desc->stat_desc->extra_bits;
486 int base = desc->stat_desc->extra_base;
487 int max_length = desc->stat_desc->max_length;
495 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
500 tree[s->heap[s->heap_max]].Len = 0;
502 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
504 bits = tree[tree[
n].Dad].Len + 1;
505 if (bits > max_length) bits = max_length, overflow++;
506 tree[
n].Len = (
ush)bits;
509 if (n > max_code)
continue;
513 if (n >= base) xbits = extra[n-base];
515 s->opt_len += (
ulg)f * (bits + xbits);
516 if (stree) s->static_len += (
ulg)f * (stree[n].Len + xbits);
518 if (overflow == 0)
return;
520 Trace((stderr,
"\nbit length overflow\n"));
526 while (s->bl_count[bits] == 0) bits--;
528 s->bl_count[bits+1] += 2;
529 s->bl_count[max_length]--;
534 }
while (overflow > 0);
541 for (bits = max_length; bits != 0; bits--) {
542 n = s->bl_count[bits];
545 if (m > max_code)
continue;
546 if ((
unsigned) tree[m].Len != (
unsigned) bits) {
547 Trace((stderr,
"code %d bits %d->%d\n", m, tree[m].Len, bits));
548 s->opt_len += ((long)bits - (
long)tree[
m].Len)
550 tree[
m].Len = (
ush)bits;
567 ush next_code[MAX_BITS+1];
575 for (bits = 1; bits <= MAX_BITS; bits++) {
576 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
581 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
582 "inconsistent bit counts");
583 Tracev((stderr,
"\ngen_codes: max_code %d ", max_code));
585 for (n = 0; n <= max_code; n++) {
586 int len = tree[
n].Len;
587 if (len == 0)
continue;
591 Tracecv(tree !=
static_ltree, (stderr,
"\nn %3d %c l %2d c %4x (%x) ",
592 n, (isgraph(n) ? n :
' '), len, tree[n].Code, next_code[len]-1));
606 ct_data *tree = desc->dyn_tree;
607 const ct_data *stree = desc->stat_desc->static_tree;
608 int elems = desc->stat_desc->elems;
617 s->heap_len = 0, s->heap_max = HEAP_SIZE;
619 for (n = 0; n < elems; n++) {
620 if (tree[n].Freq != 0) {
621 s->heap[++(s->heap_len)] = max_code = n;
633 while (s->heap_len < 2) {
634 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
637 s->opt_len--;
if (stree) s->static_len -= stree[node].Len;
640 desc->max_code = max_code;
645 for (n = s->heap_len/2; n >= 1; n--)
pqdownheap(s, tree, n);
655 s->heap[--(s->heap_max)] = n;
656 s->heap[--(s->heap_max)] = m;
659 tree[node].Freq = tree[
n].Freq + tree[
m].Freq;
660 s->depth[node] = (
uch)((s->depth[n] >= s->depth[m] ?
661 s->depth[n] : s->depth[m]) + 1);
662 tree[
n].Dad = tree[
m].Dad = (
ush)node;
664 if (tree == s->bl_tree) {
665 fprintf(stderr,
"\nnode %d(%d), sons %d(%d) %d(%d)",
666 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
673 }
while (s->heap_len >= 2);
675 s->heap[--(s->heap_max)] = s->heap[
SMALLEST];
683 gen_codes ((ct_data *)tree, max_code, s->bl_count);
695 int nextlen = tree[0].Len;
700 if (nextlen == 0) max_count = 138, min_count = 3;
701 tree[max_code+1].Len = (
ush)0xffff;
703 for (n = 0; n <= max_code; n++) {
704 curlen = nextlen; nextlen = tree[n+1].Len;
705 if (++count < max_count && curlen == nextlen) {
707 }
else if (count < min_count) {
708 s->bl_tree[curlen].Freq += count;
709 }
else if (curlen != 0) {
710 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
712 }
else if (count <= 10) {
717 count = 0; prevlen = curlen;
719 max_count = 138, min_count = 3;
720 }
else if (curlen == nextlen) {
721 max_count = 6, min_count = 3;
723 max_count = 7, min_count = 4;
737 int nextlen = tree[0].Len;
743 if (nextlen == 0) max_count = 138, min_count = 3;
745 for (n = 0; n <= max_code; n++) {
746 curlen = nextlen; nextlen = tree[n+1].Len;
747 if (++count < max_count && curlen == nextlen) {
749 }
else if (count < min_count) {
750 do {
send_code(s, curlen, s->bl_tree); }
while (--count != 0);
752 }
else if (curlen != 0) {
753 if (curlen != prevlen) {
754 send_code(s, curlen, s->bl_tree); count--;
756 Assert(count >= 3 && count <= 6,
" 3_6?");
759 }
else if (count <= 10) {
765 count = 0; prevlen = curlen;
767 max_count = 138, min_count = 3;
768 }
else if (curlen == nextlen) {
769 max_count = 6, min_count = 3;
771 max_count = 7, min_count = 4;
785 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
786 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
798 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
799 if (s->bl_tree[
bl_order[max_blindex]].Len != 0)
break;
802 s->opt_len += 3*(max_blindex+1) + 5+5+4;
803 Tracev((stderr,
"\ndyn trees: dyn %ld, stat %ld",
804 s->opt_len, s->static_len));
818 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
"not enough codes");
819 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
821 Tracev((stderr,
"\nbl counts: "));
825 for (rank = 0; rank < blcodes; rank++) {
826 Tracev((stderr,
"\nbl code %2d ",
bl_order[rank]));
829 Tracev((stderr,
"\nbl tree: sent %ld", s->bits_sent));
831 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
832 Tracev((stderr,
"\nlit tree: sent %ld", s->bits_sent));
834 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
835 Tracev((stderr,
"\ndist tree: sent %ld", s->bits_sent));
845 s->compressed_len = (s->compressed_len + 3 + 7) & (
ulg)~7
L;
846 s->compressed_len += (stored_len + 4) << 3;
868 s->compressed_len += 10
L;
879 ulg opt_lenb, static_lenb;
886 if (s->strm->data_type == Z_UNKNOWN)
891 Tracev((stderr,
"\nlit data: dyn %ld, stat %ld", s->opt_len,
895 Tracev((stderr,
"\ndist data: dyn %ld, stat %ld", s->opt_len,
907 opt_lenb = (s->opt_len+3+7)>>3;
908 static_lenb = (s->static_len+3+7)>>3;
910 Tracev((stderr,
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
911 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
914 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
917 Assert(buf != (
char*)0,
"lost buf");
918 opt_lenb = static_lenb = stored_len + 5;
922 if (buf != (
char*)0) {
924 if (stored_len+4 <= opt_lenb && buf != (
char*)0) {
936 }
else if (static_lenb >= 0) {
938 }
else if (s->strategy == Z_FIXED || static_lenb == opt_lenb) {
944 s->compressed_len += 3 + s->static_len;
951 (
const ct_data *)s->dyn_dtree);
953 s->compressed_len += 3 + s->opt_len;
956 Assert (s->compressed_len == s->bits_sent,
"bad compressed size");
965 s->compressed_len += 7;
968 Tracev((stderr,
"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
969 s->compressed_len-7*last));
978 s->d_buf[s->last_lit] = (
ush)dist;
979 s->l_buf[s->last_lit++] = (
uch)lc;
982 s->dyn_ltree[lc].Freq++;
987 Assert((
ush)dist < (
ush)MAX_DIST(s) &&
988 (
ush)lc <= (
ush)(MAX_MATCH-MIN_MATCH) &&
989 (
ush)d_code(dist) < (
ush)D_CODES,
"_tr_tally: bad match");
992 s->dyn_dtree[d_code(dist)].Freq++;
995 #ifdef TRUNCATE_BLOCK
997 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
999 ulg out_length = (
ulg)s->last_lit*8
L;
1000 ulg in_length = (
ulg)((long)s->strstart - s->block_start);
1002 for (dcode = 0; dcode < D_CODES; dcode++) {
1003 out_length += (
ulg)s->dyn_dtree[dcode].Freq *
1007 Tracev((stderr,
"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1008 s->last_lit, in_length, out_length,
1009 100
L - out_length*100
L/in_length));
1010 if (s->matches < s->last_lit/2 && out_length < in_length/2)
return 1;
1013 return (s->last_lit == s->lit_bufsize-1);
1031 if (s->last_lit != 0)
do {
1032 dist = s->d_buf[lx];
1033 lc = s->l_buf[lx++];
1036 Tracecv(isgraph(lc), (stderr,
" '%c' ", lc));
1047 code = d_code(dist);
1048 Assert (code < D_CODES,
"bad d_code");
1059 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1060 "pendingBuf overflow");
1062 }
while (lx < s->last_lit);
1086 unsigned long black_mask = 0xf3ffc07fUL;
1090 for (n = 0; n <= 31; n++, black_mask >>= 1)
1091 if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1095 if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
1096 || s->dyn_ltree[13].Freq != 0)
1098 for (n = 32; n < LITERALS; n++)
1099 if (s->dyn_ltree[n].Freq != 0)
1118 code >>= 1, res <<= 1;
1119 }
while (--len > 0);
1128 if (s->bi_valid == 16) {
1132 }
else if (s->bi_valid >= 8) {
1133 put_byte(s, (Byte)s->bi_buf);
1144 if (s->bi_valid > 8) {
1146 }
else if (s->bi_valid > 0) {
1147 put_byte(s, (Byte)s->bi_buf);
1152 s->bits_sent = (s->bits_sent+7) & ~7;
1168 s->bits_sent += 2*16;
1172 s->bits_sent += (
ulg)len<<3;
1175 put_byte(s, *buf++);
int ZLIB_INTERNAL _tr_tally(deflate_state *s, unsigned dist, unsigned lc)
local const uch bl_order[BL_CODES]
local static_tree_desc static_l_desc
uch _dist_code[DIST_CODE_LEN]
void ZLIB_INTERNAL _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int last)
local void bi_windup(deflate_state *s)
local static_tree_desc static_bl_desc
local static_tree_desc static_d_desc
void ZLIB_INTERNAL _tr_init(deflate_state *s)
local const int extra_blbits[BL_CODES]
#define smaller(tree, n, m, depth)
local ct_data static_dtree[D_CODES]
void ZLIB_INTERNAL _tr_align(deflate_state *s)
local void pqdownheap(deflate_state *s, ct_data *tree, int k)
local void send_tree(deflate_state *s, ct_data *tree, int max_code)
local void scan_tree(deflate_state *s, ct_data *tree, int max_code)
local void bi_flush(deflate_state *s)
local void build_tree(deflate_state *s, tree_desc *desc)
local int base_length[LENGTH_CODES]
local ct_data static_ltree[L_CODES+2]
local int build_bl_tree(deflate_state *s)
local const int extra_dbits[D_CODES]
local void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
local unsigned bi_reverse(unsigned code, int len)
#define pqremove(s, tree, top)
uch _length_code[MAX_MATCH-MIN_MATCH+1]
local const int extra_lbits[LENGTH_CODES]
local int base_dist[D_CODES]
local void copy_block(deflate_state *s, charf *buf, unsigned len, int header)
void ZLIB_INTERNAL _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int last)
local void tr_static_init()
void ZLIB_INTERNAL _tr_flush_bits(deflate_state *s)
local void gen_bitlen(deflate_state *s, tree_desc *desc)
local void tr_static_init OF((void))
const ct_data * static_tree
local void init_block(deflate_state *s)
local void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree)
#define send_code(s, c, tree)
#define send_bits(s, value, length)
local void gen_codes(ct_data *tree, int max_code, ushf *bl_count)
local int detect_data_type(deflate_state *s)