58 #define REPZ_11_138 18
62 = {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};
65 = {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};
68 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
71 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
80 #define DIST_CODE_LEN 512
82 #if defined(GEN_TREES_H) || !defined(STDC)
156 local void gen_trees_header
OF((
void));
160 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
164 # define send_code(s, c, tree) \
165 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
166 send_bits(s, tree[c].Code, tree[c].Len); }
173 #define put_short(s, w) { \
174 put_byte(s, (uch)((w) & 0xff)); \
175 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;
199 s->bi_buf |= (
ush)value << s->bi_valid;
201 s->bi_buf = (
ush)value >> (
Buf_size - s->bi_valid);
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) {\
213 int val = (int)value;\
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;
243 if (static_init_done)
return;
246 #ifdef NO_INIT_GLOBAL_POINTERS
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++) {
340 fprintf(header,
"local const ct_data static_dtree[D_CODES] = {\n");
341 for (i = 0; i <
D_CODES; i++) {
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");
359 fprintf(header,
"local const int base_length[LENGTH_CODES] = {\n");
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));
383 s->l_desc.dyn_tree = s->dyn_ltree;
386 s->d_desc.dyn_tree = s->dyn_dtree;
389 s->bl_desc.dyn_tree = s->bl_tree;
395 s->compressed_len = 0
L;
412 for (n = 0; n <
L_CODES; n++) s->dyn_ltree[n].Freq = 0;
413 for (n = 0; n <
D_CODES; n++) s->dyn_dtree[n].Freq = 0;
414 for (n = 0; n <
BL_CODES; n++) s->bl_tree[n].Freq = 0;
417 s->opt_len = s->static_len = 0
L;
418 s->last_lit = s->matches = 0;
429 #define pqremove(s, tree, top) \
431 top = s->heap[SMALLEST]; \
432 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
433 pqdownheap(s, tree, SMALLEST); \
440 #define smaller(tree, n, m, depth) \
441 (tree[n].Freq < tree[m].Freq || \
442 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
457 while (j <= s->heap_len) {
459 if (j < s->heap_len &&
460 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
464 if (
smaller(tree, v, s->heap[j], s->depth))
break;
467 s->heap[
k] = s->heap[j]; k = j;
502 for (bits = 0; bits <=
MAX_BITS; bits++) s->bl_count[bits] = 0;
507 tree[s->heap[s->heap_max]].Len = 0;
511 bits = tree[tree[
n].Dad].Len + 1;
512 if (bits > max_length) bits = max_length, overflow++;
513 tree[
n].Len = (
ush)bits;
516 if (n > max_code)
continue;
520 if (n >= base) xbits = extra[n-
base];
522 s->opt_len += (
ulg)f * (
unsigned)(bits + xbits);
523 if (stree) s->static_len += (
ulg)f * (
unsigned)(stree[
n].Len + xbits);
525 if (overflow == 0)
return;
527 Tracev((stderr,
"\nbit length overflow\n"));
533 while (s->bl_count[bits] == 0) bits--;
535 s->bl_count[bits+1] += 2;
536 s->bl_count[max_length]--;
541 }
while (overflow > 0);
548 for (bits = max_length; bits != 0; bits--) {
549 n = s->bl_count[bits];
552 if (m > max_code)
continue;
553 if ((
unsigned) tree[m].
Len != (
unsigned) bits) {
554 Tracev((stderr,
"code %d bits %d->%d\n", m, tree[m].
Len, bits));
555 s->opt_len += ((
ulg)bits - tree[m].Len) * tree[
m].Freq;
556 tree[
m].Len = (
ush)bits;
584 for (bits = 1; bits <=
MAX_BITS; bits++) {
585 code = (code + bl_count[bits-1]) << 1;
586 next_code[bits] = (
ush)code;
592 "inconsistent bit counts");
593 Tracev((stderr,
"\ngen_codes: max_code %d ", max_code));
595 for (n = 0; n <= max_code; n++) {
596 int len = tree[
n].Len;
597 if (len == 0)
continue;
602 n, (isgraph(n) ? n :
' '), len, tree[n].
Code, next_code[len]-1));
629 s->heap_len = 0, s->heap_max =
HEAP_SIZE;
631 for (n = 0; n < elems; n++) {
632 if (tree[n].
Freq != 0) {
633 s->heap[++(s->heap_len)] = max_code = n;
645 while (s->heap_len < 2) {
646 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
649 s->opt_len--;
if (stree) s->static_len -= stree[node].Len;
657 for (n = s->heap_len/2; n >= 1; n--)
pqdownheap(s, tree, n);
667 s->heap[--(s->heap_max)] = n;
668 s->heap[--(s->heap_max)] = m;
671 tree[node].Freq = tree[
n].Freq + tree[
m].Freq;
672 s->depth[node] = (
uch)((s->depth[n] >= s->depth[m] ?
673 s->depth[n] : s->depth[m]) + 1);
674 tree[
n].Dad = tree[
m].Dad = (
ush)node;
676 if (tree == s->bl_tree) {
677 fprintf(stderr,
"\nnode %d(%d), sons %d(%d) %d(%d)",
678 node, tree[node].
Freq, n, tree[n].Freq, m, tree[m].Freq);
685 }
while (s->heap_len >= 2);
687 s->heap[--(s->heap_max)] = s->heap[
SMALLEST];
710 int nextlen = tree[0].Len;
715 if (nextlen == 0) max_count = 138, min_count = 3;
716 tree[max_code+1].Len = (
ush)0xffff;
718 for (n = 0; n <= max_code; n++) {
719 curlen = nextlen; nextlen = tree[n+1].Len;
720 if (++count < max_count && curlen == nextlen) {
722 }
else if (count < min_count) {
723 s->bl_tree[curlen].Freq += count;
724 }
else if (curlen != 0) {
725 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
727 }
else if (count <= 10) {
732 count = 0; prevlen = curlen;
734 max_count = 138, min_count = 3;
735 }
else if (curlen == nextlen) {
736 max_count = 6, min_count = 3;
738 max_count = 7, min_count = 4;
755 int nextlen = tree[0].Len;
761 if (nextlen == 0) max_count = 138, min_count = 3;
763 for (n = 0; n <= max_code; n++) {
764 curlen = nextlen; nextlen = tree[n+1].Len;
765 if (++count < max_count && curlen == nextlen) {
767 }
else if (count < min_count) {
768 do {
send_code(s, curlen, s->bl_tree); }
while (--count != 0);
770 }
else if (curlen != 0) {
771 if (curlen != prevlen) {
772 send_code(s, curlen, s->bl_tree); count--;
774 Assert(count >= 3 && count <= 6,
" 3_6?");
777 }
else if (count <= 10) {
783 count = 0; prevlen = curlen;
785 max_count = 138, min_count = 3;
786 }
else if (curlen == nextlen) {
787 max_count = 6, min_count = 3;
789 max_count = 7, min_count = 4;
817 for (max_blindex =
BL_CODES-1; max_blindex >= 3; max_blindex--) {
818 if (s->bl_tree[
bl_order[max_blindex]].Len != 0)
break;
821 s->opt_len += 3*((
ulg)max_blindex+1) + 5+5+4;
822 Tracev((stderr,
"\ndyn trees: dyn %ld, stat %ld",
823 s->opt_len, s->static_len));
835 int lcodes, dcodes, blcodes;
839 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
"not enough codes");
840 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <=
BL_CODES,
842 Tracev((stderr,
"\nbl counts: "));
846 for (rank = 0; rank < blcodes; rank++) {
850 Tracev((stderr,
"\nbl tree: sent %ld", s->bits_sent));
853 Tracev((stderr,
"\nlit tree: sent %ld", s->bits_sent));
856 Tracev((stderr,
"\ndist tree: sent %ld", s->bits_sent));
872 zmemcpy(s->pending_buf + s->pending, (Bytef *)buf, stored_len);
873 s->pending += stored_len;
875 s->compressed_len = (s->compressed_len + 3 + 7) & (
ulg)~7
L;
876 s->compressed_len += (stored_len + 4) << 3;
877 s->bits_sent += 2*16;
878 s->bits_sent += stored_len<<3;
901 s->compressed_len += 10
L;
916 ulg opt_lenb, static_lenb;
928 Tracev((stderr,
"\nlit data: dyn %ld, stat %ld", s->opt_len,
932 Tracev((stderr,
"\ndist data: dyn %ld, stat %ld", s->opt_len,
944 opt_lenb = (s->opt_len+3+7)>>3;
945 static_lenb = (s->static_len+3+7)>>3;
947 Tracev((stderr,
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
948 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
951 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
954 Assert(buf != (
char*)0,
"lost buf");
955 opt_lenb = static_lenb = stored_len + 5;
959 if (buf != (
char*)0) {
961 if (stored_len+4 <= opt_lenb && buf != (
char*)0) {
973 }
else if (static_lenb >= 0) {
975 }
else if (s->strategy ==
Z_FIXED || static_lenb == opt_lenb) {
981 s->compressed_len += 3 + s->static_len;
988 (
const ct_data *)s->dyn_dtree);
990 s->compressed_len += 3 + s->opt_len;
993 Assert (s->compressed_len == s->bits_sent,
"bad compressed size");
1002 s->compressed_len += 7;
1005 Tracev((stderr,
"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1006 s->compressed_len-7*last));
1018 s->d_buf[s->last_lit] = (
ush)dist;
1019 s->l_buf[s->last_lit++] = (
uch)lc;
1022 s->dyn_ltree[
lc].Freq++;
1029 (
ush)
d_code(dist) < (
ush)D_CODES,
"_tr_tally: bad match");
1032 s->dyn_dtree[
d_code(dist)].Freq++;
1035 #ifdef TRUNCATE_BLOCK
1037 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
1039 ulg out_length = (
ulg)s->last_lit*8
L;
1040 ulg in_length = (
ulg)((long)s->strstart - s->block_start);
1042 for (dcode = 0; dcode <
D_CODES; dcode++) {
1043 out_length += (
ulg)s->dyn_dtree[dcode].Freq *
1047 Tracev((stderr,
"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1048 s->last_lit, in_length, out_length,
1049 100
L - out_length*100
L/in_length));
1050 if (s->matches < s->last_lit/2 && out_length < in_length/2)
return 1;
1053 return (s->last_lit == s->lit_bufsize-1);
1074 if (s->last_lit != 0)
do {
1075 dist = s->d_buf[lx];
1076 lc = s->l_buf[lx++];
1079 Tracecv(isgraph(lc), (stderr,
" '%c' ", lc));
1091 Assert (code < D_CODES,
"bad d_code");
1102 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
1103 "pendingBuf overflow");
1105 }
while (lx < s->last_lit);
1130 unsigned long black_mask = 0xf3ffc07fUL;
1134 for (n = 0; n <= 31; n++, black_mask >>= 1)
1135 if ((black_mask & 1) && (s->dyn_ltree[n].Freq != 0))
1139 if (s->dyn_ltree[9].Freq != 0 || s->dyn_ltree[10].Freq != 0
1140 || s->dyn_ltree[13].Freq != 0)
1143 if (s->dyn_ltree[n].Freq != 0)
1161 register unsigned res = 0;
1164 code >>= 1, res <<= 1;
1165 }
while (--len > 0);
1175 if (s->bi_valid == 16) {
1179 }
else if (s->bi_valid >= 8) {
1192 if (s->bi_valid > 8) {
1194 }
else if (s->bi_valid > 0) {
1200 s->bits_sent = (s->bits_sent+7) & ~7;