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
) 86 local ct_data static_ltree[L_CODES+2];
93 local ct_data static_dtree[D_CODES];
98 uch _dist_code[DIST_CODE_LEN];
104 uch _length_code[MAX_MATCH-MIN_MATCH+1];
107 local
int base_length[LENGTH_CODES];
110 local
int base_dist[D_CODES];
139 local void init_block
OF((deflate_state *s));
140 local void pqdownheap
OF((deflate_state *s, ct_data *tree,
int k));
141 local void gen_bitlen
OF((deflate_state *s, tree_desc *desc));
142 local void gen_codes
OF((ct_data *tree,
int max_code,
ushf *bl_count));
143 local void build_tree
OF((deflate_state *s, tree_desc *desc));
144 local void scan_tree
OF((deflate_state *s, ct_data *tree,
int max_code));
145 local void send_tree
OF((deflate_state *s, ct_data *tree,
int max_code));
146 local int build_bl_tree
OF((deflate_state *s));
147 local void send_all_trees
OF((deflate_state *s,
int lcodes,
int dcodes,
149 local void compress_block
OF((deflate_state *s,
const ct_data *ltree,
150 const ct_data *dtree));
151 local int detect_data_type
OF((deflate_state *s));
152 local unsigned bi_reverse
OF((
unsigned value,
int length));
153 local void bi_windup
OF((deflate_state *s));
154 local void bi_flush
OF((deflate_state *s));
157 local
void gen_trees_header OF((
void));
165 # define send_code(s, c, tree) 166 { if (z_verbose>2
) fprintf(stderr,"\ncd %3d ",(c)); 167 send_bits(s, tree[c].Code, tree[c].Len); } 174 #define put_short(s, w) { 176 put_byte(s, (uch)((ush)(w) >> 8
)); \ 184 local
void send_bits OF((deflate_state *s,
int value,
int length));
186 local
void send_bits(s, value, length)
191 Tracevv((stderr,
" l %2d v %4x ", length, value));
192 Assert(length > 0 && length <= 15,
"invalid length");
193 s->bits_sent += (ulg)length;
199 if (s->bi_valid > (
int)Buf_size - length) {
200 s->bi_buf |= (ush)value << s->bi_valid;
201 put_short(s, s->bi_buf);
202 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
203 s->bi_valid += length - Buf_size;
205 s->bi_buf |= (ush)value << s->bi_valid;
206 s->bi_valid += length;
211 #define send_bits(s, value, length) \ 213 if (s->bi_valid > (int)Buf_size - len) { 214 int val = (int)value; 215 s->bi_buf |= (ush)val << s->bi_valid; 217 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid); 220 s->bi_buf |= (ush)(value) << s->bi_valid; 234 #if defined(GEN_TREES_H) || !defined(STDC
) 235 static int static_init_done = 0;
241 ush bl_count[MAX_BITS+1];
244 if (static_init_done)
return;
247 #ifdef NO_INIT_GLOBAL_POINTERS 248 static_l_desc.static_tree = static_ltree;
249 static_l_desc.extra_bits = extra_lbits;
250 static_d_desc.static_tree = static_dtree;
251 static_d_desc.extra_bits = extra_dbits;
252 static_bl_desc.extra_bits = extra_blbits;
257 for (code = 0; code < LENGTH_CODES-1; code++) {
258 base_length[code] = length;
259 for (n = 0; n < (1<<extra_lbits[code]); n++) {
260 _length_code[length++] = (uch)code;
263 Assert (length == 256,
"tr_static_init: length != 256");
268 _length_code[length-1] = (uch)code;
272 for (code = 0 ; code < 16; code++) {
273 base_dist[code] = dist;
274 for (n = 0; n < (1<<extra_dbits[code]); n++) {
275 _dist_code[dist++] = (uch)code;
278 Assert (dist == 256,
"tr_static_init: dist != 256");
280 for ( ; code < D_CODES; code++) {
281 base_dist[code] = dist << 7;
282 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
283 _dist_code[256 + dist++] = (uch)code;
286 Assert (dist == 256,
"tr_static_init: 256+dist != 512");
289 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
291 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
292 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
293 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
294 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
299 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
302 for (n = 0; n < D_CODES; n++) {
303 static_dtree[n].Len = 5;
304 static_dtree[n].Code = bi_reverse((
unsigned)n, 5);
306 static_init_done = 1;
322 # define SEPARATOR(i, last, width) 323 ((i) == (last)? "\n};\n\n" : 324 ((i) % (width) == (width)-1
? ",\n" : ", ")) 326 void gen_trees_header()
328 FILE *header = fopen(
"trees.h",
"w");
331 Assert (header != NULL,
"Can't open trees.h");
333 "/* header created automatically with -DGEN_TREES_H */\n\n");
335 fprintf(header,
"local const ct_data static_ltree[L_CODES+2] = {\n");
336 for (i = 0; i < L_CODES+2; i++) {
337 fprintf(header,
"{{%3u},{%3u}}%s", static_ltree[i].Code,
338 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
341 fprintf(header,
"local const ct_data static_dtree[D_CODES] = {\n");
342 for (i = 0; i < D_CODES; i++) {
343 fprintf(header,
"{{%2u},{%2u}}%s", static_dtree[i].Code,
344 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
347 fprintf(header,
"const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
348 for (i = 0; i < DIST_CODE_LEN; i++) {
349 fprintf(header,
"%2u%s", _dist_code[i],
350 SEPARATOR(i, DIST_CODE_LEN-1, 20));
354 "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
355 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
356 fprintf(header,
"%2u%s", _length_code[i],
357 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
360 fprintf(header,
"local const int base_length[LENGTH_CODES] = {\n");
361 for (i = 0; i < LENGTH_CODES; i++) {
362 fprintf(header,
"%1u%s", base_length[i],
363 SEPARATOR(i, LENGTH_CODES-1, 20));
366 fprintf(header,
"local const int base_dist[D_CODES] = {\n");
367 for (i = 0; i < D_CODES; i++) {
368 fprintf(header,
"%5u%s", base_dist[i],
369 SEPARATOR(i, D_CODES-1, 10));
384 s->l_desc.dyn_tree = s->dyn_ltree;
385 s->l_desc.stat_desc = &static_l_desc;
387 s->d_desc.dyn_tree = s->dyn_dtree;
388 s->d_desc.stat_desc = &static_d_desc;
390 s->bl_desc.dyn_tree = s->bl_tree;
391 s->bl_desc.stat_desc = &static_bl_desc;
396 s->compressed_len = 0L;
413 for (n = 0; n <
L_CODES; n++) s->dyn_ltree[n].
Freq = 0;
414 for (n = 0; n <
D_CODES; n++) s->dyn_dtree[n].
Freq = 0;
418 s->opt_len = s->static_len = 0L;
419 s->last_lit = s->matches = 0;
430 #define pqremove(s, tree, top) \ 433 s->heap[SMALLEST] = s->heap[s->heap_len--]; 441 #define smaller(tree, n, m, depth) 443 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m])) 458 while (j <= s->heap_len) {
460 if (j < s->heap_len &&
461 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
465 if (
smaller(tree, v, s->heap[j], s->depth))
break;
468 s->heap[k] = s->heap[j]; k = j;
490 ct_data *tree = desc->dyn_tree;
491 int max_code = desc->max_code;
492 const ct_data *stree = desc->stat_desc->static_tree;
493 const intf *extra = desc->stat_desc->extra_bits;
494 int base = desc->stat_desc->extra_base;
495 int max_length = desc->stat_desc->max_length;
503 for (bits = 0; bits <=
MAX_BITS; bits++) s->bl_count[bits] = 0;
508 tree[s->heap[s->heap_max]].
Len = 0;
510 for (h = s->heap_max+1; h <
HEAP_SIZE; h++) {
512 bits = tree[tree[n].
Dad].
Len + 1;
513 if (bits > max_length) bits = max_length, overflow++;
514 tree[n].
Len = (ush)bits;
517 if (n > max_code)
continue;
521 if (n >= base) xbits = extra[n-base];
523 s->opt_len += (ulg)f * (
unsigned)(bits + xbits);
524 if (stree) s->static_len += (ulg)f * (
unsigned)(stree[n].
Len + xbits);
526 if (overflow == 0)
return;
528 Tracev((stderr,
"\nbit length overflow\n"));
534 while (s->bl_count[bits] == 0) bits--;
536 s->bl_count[bits+1] += 2;
537 s->bl_count[max_length]--;
542 }
while (overflow > 0);
549 for (bits = max_length; bits != 0; bits--) {
550 n = s->bl_count[bits];
553 if (m > max_code)
continue;
554 if ((
unsigned) tree[m].
Len != (
unsigned) bits) {
555 Tracev((stderr,
"code %d bits %d->%d\n", m, tree[m].Len, bits));
556 s->opt_len += ((ulg)bits - tree[m].
Len) * tree[m].
Freq;
557 tree[m].
Len = (ush)bits;
585 for (bits = 1; bits <=
MAX_BITS; bits++) {
586 code = (code + bl_count[bits-1]) << 1;
587 next_code[bits] = (ush)code;
592 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
593 "inconsistent bit counts");
594 Tracev((stderr,
"\ngen_codes: max_code %d ", max_code));
596 for (n = 0; n <= max_code; n++) {
597 int len = tree[n].
Len;
598 if (len == 0)
continue;
600 tree[n].
Code = (ush)bi_reverse(next_code[len]++, len);
602 Tracecv(tree != static_ltree, (stderr,
"\nn %3d %c l %2d c %4x (%x) ",
603 n, (isgraph(n) ? n :
' '), len, tree[n].Code, next_code[len]-1));
619 ct_data *tree = desc->dyn_tree;
620 const ct_data *stree = desc->stat_desc->static_tree;
621 int elems = desc->stat_desc->elems;
630 s->heap_len = 0, s->heap_max =
HEAP_SIZE;
632 for (n = 0; n < elems; n++) {
633 if (tree[n].
Freq != 0) {
634 s->heap[++(s->heap_len)] = max_code = n;
646 while (s->heap_len < 2) {
647 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
650 s->opt_len--;
if (stree) s->static_len -= stree[node].
Len;
653 desc->max_code = max_code;
658 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
668 s->heap[--(s->heap_max)] = n;
669 s->heap[--(s->heap_max)] = m;
673 s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
674 s->depth[n] : s->depth[m]) + 1);
675 tree[n].
Dad = tree[m].
Dad = (ush)node;
677 if (tree == s->bl_tree) {
678 fprintf(stderr,
"\nnode %d(%d), sons %d(%d) %d(%d)",
679 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
686 }
while (s->heap_len >= 2);
688 s->heap[--(s->heap_max)] = s->heap[
SMALLEST];
693 gen_bitlen(s, (tree_desc *)desc);
696 gen_codes ((ct_data *)tree, max_code, s->bl_count);
711 int nextlen = tree[0].
Len;
716 if (nextlen == 0) max_count = 138, min_count = 3;
717 tree[max_code+1].
Len = (ush)0xffff;
719 for (n = 0; n <= max_code; n++) {
720 curlen = nextlen; nextlen = tree[n+1].
Len;
721 if (++count < max_count && curlen == nextlen) {
723 }
else if (count < min_count) {
724 s->bl_tree[curlen].
Freq += count;
725 }
else if (curlen != 0) {
726 if (curlen != prevlen) s->bl_tree[curlen].
Freq++;
728 }
else if (count <= 10) {
733 count = 0; prevlen = curlen;
735 max_count = 138, min_count = 3;
736 }
else if (curlen == nextlen) {
737 max_count = 6, min_count = 3;
739 max_count = 7, min_count = 4;
756 int nextlen = tree[0].
Len;
762 if (nextlen == 0) max_count = 138, min_count = 3;
764 for (n = 0; n <= max_code; n++) {
765 curlen = nextlen; nextlen = tree[n+1].
Len;
766 if (++count < max_count && curlen == nextlen) {
768 }
else if (count < min_count) {
769 do {
send_code(s, curlen, s->bl_tree); }
while (--count != 0);
771 }
else if (curlen != 0) {
772 if (curlen != prevlen) {
773 send_code(s, curlen, s->bl_tree); count--;
775 Assert(count >= 3 && count <= 6,
" 3_6?");
778 }
else if (count <= 10) {
784 count = 0; prevlen = curlen;
786 max_count = 138, min_count = 3;
787 }
else if (curlen == nextlen) {
788 max_count = 6, min_count = 3;
790 max_count = 7, min_count = 4;
805 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
806 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
809 build_tree(s, (tree_desc *)(&(s->bl_desc)));
818 for (max_blindex =
BL_CODES-1; max_blindex >= 3; max_blindex--) {
819 if (s->bl_tree[bl_order[max_blindex]].
Len != 0)
break;
822 s->opt_len += 3*((ulg)max_blindex+1) + 5+5+4;
823 Tracev((stderr,
"\ndyn trees: dyn %ld, stat %ld",
824 s->opt_len, s->static_len));
836 int lcodes, dcodes, blcodes;
840 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
"not enough codes");
841 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
843 Tracev((stderr,
"\nbl counts: "));
847 for (rank = 0; rank < blcodes; rank++) {
848 Tracev((stderr,
"\nbl code %2d ", bl_order[rank]));
851 Tracev((stderr,
"\nbl tree: sent %ld", s->bits_sent));
853 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
854 Tracev((stderr,
"\nlit tree: sent %ld", s->bits_sent));
856 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
857 Tracev((stderr,
"\ndist tree: sent %ld", s->bits_sent));
873 zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
874 s->pending += stored_len;
876 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
877 s->compressed_len += (stored_len + 4) << 3;
878 s->bits_sent += 2*16;
879 s->bits_sent += stored_len<<3;
902 s->compressed_len += 10L;
917 ulg opt_lenb, static_lenb;
925 s->strm->data_type = detect_data_type(s);
928 build_tree(s, (tree_desc *)(&(s->l_desc)));
929 Tracev((stderr,
"\nlit data: dyn %ld, stat %ld", s->opt_len,
932 build_tree(s, (tree_desc *)(&(s->d_desc)));
933 Tracev((stderr,
"\ndist data: dyn %ld, stat %ld", s->opt_len,
942 max_blindex = build_bl_tree(s);
945 opt_lenb = (s->opt_len+3+7)>>3;
946 static_lenb = (s->static_len+3+7)>>3;
948 Tracev((stderr,
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
949 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
952 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
955 Assert(buf != (
char*)0,
"lost buf");
956 opt_lenb = static_lenb = stored_len + 5;
960 if (buf != (
char*)0) {
962 if (stored_len+4 <= opt_lenb && buf != (
char*)0) {
971 _tr_stored_block(s, buf, stored_len, last);
974 }
else if (static_lenb >= 0) {
976 }
else if (s->strategy ==
Z_FIXED || static_lenb == opt_lenb) {
979 compress_block(s, (
const ct_data *)static_ltree,
980 (
const ct_data *)static_dtree);
982 s->compressed_len += 3 + s->static_len;
986 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
988 compress_block(s, (
const ct_data *)s->dyn_ltree,
989 (
const ct_data *)s->dyn_dtree);
991 s->compressed_len += 3 + s->opt_len;
994 Assert (s->compressed_len == s->bits_sent,
"bad compressed size");
1003 s->compressed_len += 7;
1006 Tracev((stderr,
"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1007 s->compressed_len-7*last));
1019 s->d_buf[s->last_lit] = (ush)dist;
1020 s->l_buf[s->last_lit++] = (uch)lc;
1023 s->dyn_ltree[lc].
Freq++;
1028 Assert((ush)dist < (ush)MAX_DIST(s) &&
1029 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1030 (ush)d_code(dist) < (ush)D_CODES,
"_tr_tally: bad match");
1036 #ifdef TRUNCATE_BLOCK 1038 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1040 ulg out_length = (ulg)s->last_lit*8L;
1041 ulg in_length = (ulg)((
long)s->strstart - s->block_start);
1043 for (dcode = 0; dcode < D_CODES; dcode++) {
1044 out_length += (ulg)s->dyn_dtree[dcode].Freq *
1045 (5L+extra_dbits[dcode]);
1048 Tracev((stderr,
"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1049 s->last_lit, in_length, out_length,
1050 100L - out_length*100L/in_length));
1051 if (s->matches < s->last_lit/2 && out_length < in_length/2)
return 1;
1054 return (s->last_lit == s->lit_bufsize-1);
1066 const ct_data *ltree;
1067 const ct_data *dtree;
1075 if (s->last_lit != 0)
do {
1076 dist = s->d_buf[lx];
1077 lc = s->l_buf[lx++];
1080 Tracecv(isgraph(lc), (stderr,
" '%c' ", lc));
1083 code = _length_code[lc];
1085 extra = extra_lbits[code];
1087 lc -= base_length[code];
1092 Assert (code < D_CODES,
"bad d_code");
1095 extra = extra_dbits[code];
1097 dist -= (
unsigned)base_dist[code];
1103 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1104 "pendingBuf overflow");
1106 }
while (lx < s->last_lit);
1131 unsigned long black_mask = 0xf3ffc07fUL;
1135 for (n = 0; n <= 31; n++, black_mask >>= 1)
1136 if ((black_mask & 1) && (s->dyn_ltree[n].
Freq != 0))
1140 if (s->dyn_ltree[9].
Freq != 0 || s->dyn_ltree[10].
Freq != 0
1141 || s->dyn_ltree[13].
Freq != 0)
1144 if (s->dyn_ltree[n].
Freq != 0)
1162 register unsigned res = 0;
1165 code >>= 1, res <<= 1;
1166 }
while (--len > 0);
1176 if (s->bi_valid == 16) {
1180 }
else if (s->bi_valid >= 8) {
1193 if (s->bi_valid > 8) {
1195 }
else if (s->bi_valid > 0) {
1201 s->bits_sent = (s->bits_sent+7) & ~7;
local void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree)
local const int extra_dbits[D_CODES]
struct static_tree_desc_s static_tree_desc
local int detect_data_type(deflate_state *s)
void ZLIB_INTERNAL _tr_align(deflate_state *s)
#define Assert(cond, msg)
local void pqdownheap(deflate_state *s, ct_data *tree, int k)
local void gen_codes(ct_data *tree, int max_code, ushf *bl_count)
local void init_block(deflate_state *s)
#define smaller(tree, n, m, depth)
local void gen_bitlen(deflate_state *s, tree_desc *desc)
local unsigned bi_reverse(unsigned code, int len)
local void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
local const static_tree_desc static_l_desc
void ZLIB_INTERNAL _tr_init(deflate_state *s)
#define send_bits(s, value, length)
void ZLIB_INTERNAL _tr_flush_bits(deflate_state *s)
local const int extra_lbits[LENGTH_CODES]
local void tr_static_init()
local const uch bl_order[BL_CODES]
local void send_tree(deflate_state *s, ct_data *tree, int max_code)
void ZLIB_INTERNAL _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int last)
#define pqremove(s, tree, top)
int ZLIB_INTERNAL _tr_tally(deflate_state *s, unsigned dist, unsigned lc)
local void scan_tree(deflate_state *s, ct_data *tree, int max_code)
local void bi_windup(deflate_state *s)
local void build_tree(deflate_state *s, tree_desc *desc)
local int build_bl_tree(deflate_state *s)
local const static_tree_desc static_bl_desc
void ZLIB_INTERNAL _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int last)
const ct_data * static_tree
local const static_tree_desc static_d_desc
local const int extra_blbits[BL_CODES]
#define send_code(s, c, tree)
local void bi_flush(deflate_state *s)