37 #if defined( INC_ALL )
42 #if defined( _MSC_VER )
43 #pragma warning( disable: 4267 )
66 #define REPZ_11_138 18
70 = {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};
73 = {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};
76 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
79 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
84 #define Buf_size (8 * 2*sizeof(char))
93 #define DIST_CODE_LEN 512
95 #if defined(GEN_TREES_H) || !defined(STDC)
171 local void gen_trees_header
OF((
void));
175 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
179 # define send_code(s, c, tree) \
180 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
181 send_bits(s, tree[c].Code, tree[c].Len); }
188 #define put_short(s, w) { \
189 put_byte(s, (uch)((w) & 0xff)); \
190 put_byte(s, (uch)((ush)(w) >> 8)); \
205 Tracevv((stderr,
" l %2d v %4x ", length, value));
206 Assert(length > 0 && length <= 15,
"invalid length");
207 s->bits_sent += (
ulg)length;
214 s->bi_buf |= (
ush)value << s->bi_valid;
216 s->bi_buf = (
ush)value >> (
Buf_size - s->bi_valid);
219 s->bi_buf |= (
ush)value << s->bi_valid;
220 s->bi_valid += length;
225 #define send_bits(s, value, length) \
227 if (s->bi_valid > (int)Buf_size - len) {\
229 s->bi_buf |= (ush)val << s->bi_valid;\
230 put_short(s, s->bi_buf);\
231 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
232 s->bi_valid += len - Buf_size;\
234 s->bi_buf |= (ush)(value) << s->bi_valid;\
248 #if defined(GEN_TREES_H) || !defined(STDC)
249 static int static_init_done = 0;
258 if (static_init_done)
return;
261 #ifdef NO_INIT_GLOBAL_POINTERS
277 Assert (length == 256,
"tr_static_init: length != 256");
286 for (code = 0 ; code < 16; code++) {
292 Assert (dist == 256,
"tr_static_init: dist != 256");
294 for ( ; code <
D_CODES; code++) {
300 Assert (dist == 256,
"tr_static_init: 256+dist != 512");
303 for (bits = 0; bits <=
MAX_BITS; bits++) bl_count[bits] = 0;
305 while (n <= 143)
static_ltree[n++].Len = 8, bl_count[8]++;
306 while (n <= 255)
static_ltree[n++].Len = 9, bl_count[9]++;
307 while (n <= 279)
static_ltree[n++].Len = 7, bl_count[7]++;
308 while (n <= 287)
static_ltree[n++].Len = 8, bl_count[8]++;
316 for (n = 0; n <
D_CODES; n++) {
320 static_init_done = 1;
336 # define SEPARATOR(i, last, width) \
337 ((i) == (last)? "\n};\n\n" : \
338 ((i) % (width) == (width)-1 ? ",\n" : ", "))
340 void gen_trees_header()
342 FILE *header = fopen(
"trees.h",
"w");
345 Assert (header != NULL,
"Can't open trees.h");
347 "/* header created automatically with -DGEN_TREES_H */\n\n");
349 fprintf(header,
"local const ct_data static_ltree[L_CODES+2] = {\n");
350 for (i = 0; i <
L_CODES+2; i++) {
355 fprintf(header,
"local const ct_data static_dtree[D_CODES] = {\n");
356 for (i = 0; i <
D_CODES; i++) {
361 fprintf(header,
"const uch _dist_code[DIST_CODE_LEN] = {\n");
364 SEPARATOR(i, DIST_CODE_LEN-1, 20));
367 fprintf(header,
"const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
373 fprintf(header,
"local const int base_length[LENGTH_CODES] = {\n");
376 SEPARATOR(i, LENGTH_CODES-1, 20));
379 fprintf(header,
"local const int base_dist[D_CODES] = {\n");
380 for (i = 0; i <
D_CODES; i++) {
382 SEPARATOR(i, D_CODES-1, 10));
409 s->compressed_len = 0L;
442 #define pqremove(s, tree, top) \
444 top = s->heap[SMALLEST]; \
445 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
446 pqdownheap(s, tree, SMALLEST); \
453 #define smaller(tree, n, m, depth) \
454 (tree[n].Freq < tree[m].Freq || \
455 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
469 while (j <= s->heap_len) {
471 if (j < s->heap_len &&
522 bits = tree[tree[
n].Dad].Len + 1;
523 if (bits > max_length) bits = max_length, overflow++;
524 tree[
n].Len = (
ush)bits;
527 if (n > max_code)
continue;
531 if (n >= base) xbits = extra[n-base];
536 if (overflow == 0)
return;
538 Trace((stderr,
"\nbit length overflow\n"));
544 while (s->
bl_count[bits] == 0) bits--;
552 }
while (overflow > 0);
559 for (bits = max_length; bits != 0; bits--) {
563 if (m > max_code)
continue;
564 if ((
unsigned) tree[m].
Len != (
unsigned) bits) {
565 Trace((stderr,
"code %d bits %d->%d\n", m, tree[m].
Len, bits));
566 s->
opt_len += ((long)bits - (
long)tree[m].Len)
568 tree[m].Len = (
ush)bits;
595 for (bits = 1; bits <=
MAX_BITS; bits++) {
596 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
602 "inconsistent bit counts");
603 Tracev((stderr,
"\ngen_codes: max_code %d ", max_code));
605 for (n = 0; n <= max_code; n++) {
606 int len = tree[
n].Len;
607 if (len == 0)
continue;
612 n, (isgraph(n) ? n :
' '), len, tree[n].
Code, next_code[len]-1));
640 for (n = 0; n < elems; n++) {
641 if (tree[n].
Freq != 0) {
655 node = s->
heap[++(s->
heap_len)] = (max_code < 2 ? ++max_code : 0);
680 tree[node].Freq = tree[
n].Freq + tree[m].Freq;
683 tree[
n].Dad = tree[m].Dad = (
ush)node;
686 fprintf(stderr,
"\nnode %d(%d), sons %d(%d) %d(%d)",
687 node, tree[node].
Freq, n, tree[n].Freq, m, tree[m].Freq);
718 int nextlen = tree[0].Len;
723 if (nextlen == 0) max_count = 138, min_count = 3;
724 tree[max_code+1].Len = (
ush)0xffff;
726 for (n = 0; n <= max_code; n++) {
727 curlen = nextlen; nextlen = tree[n+1].Len;
728 if (++count < max_count && curlen == nextlen) {
730 }
else if (count < min_count) {
731 s->
bl_tree[curlen].Freq += count;
732 }
else if (curlen != 0) {
733 if (curlen != prevlen) s->
bl_tree[curlen].Freq++;
735 }
else if (count <= 10) {
740 count = 0; prevlen = curlen;
742 max_count = 138, min_count = 3;
743 }
else if (curlen == nextlen) {
744 max_count = 6, min_count = 3;
746 max_count = 7, min_count = 4;
762 int nextlen = tree[0].Len;
768 if (nextlen == 0) max_count = 138, min_count = 3;
770 for (n = 0; n <= max_code; n++) {
771 curlen = nextlen; nextlen = tree[n+1].Len;
772 if (++count < max_count && curlen == nextlen) {
774 }
else if (count < min_count) {
777 }
else if (curlen != 0) {
778 if (curlen != prevlen) {
781 Assert(count >= 3 && count <= 6,
" 3_6?");
784 }
else if (count <= 10) {
790 count = 0; prevlen = curlen;
792 max_count = 138, min_count = 3;
793 }
else if (curlen == nextlen) {
794 max_count = 6, min_count = 3;
796 max_count = 7, min_count = 4;
823 for (max_blindex =
BL_CODES-1; max_blindex >= 3; max_blindex--) {
827 s->
opt_len += 3*(max_blindex+1) + 5+5+4;
828 Tracev((stderr,
"\ndyn trees: dyn %ld, stat %ld",
840 int lcodes,
int dcodes,
int blcodes)
844 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
"not enough codes");
845 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <=
BL_CODES,
847 Tracev((stderr,
"\nbl counts: "));
851 for (rank = 0; rank < blcodes; rank++) {
855 Tracev((stderr,
"\nbl tree: sent %ld", s->bits_sent));
858 Tracev((stderr,
"\nlit tree: sent %ld", s->bits_sent));
861 Tracev((stderr,
"\ndist tree: sent %ld", s->bits_sent));
874 s->compressed_len = (s->compressed_len + 3 + 7) & (
ulg)~7L;
875 s->compressed_len += (stored_len + 4) << 3;
896 s->compressed_len += 10L;
908 s->compressed_len += 10L;
924 ulg opt_lenb, static_lenb;
940 Tracev((stderr,
"\ndist data: dyn %ld, stat %ld", s->
opt_len,
952 opt_lenb = (s->
opt_len+3+7)>>3;
955 Tracev((stderr,
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
959 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
962 Assert(buf != (
char*)0,
"lost buf");
963 opt_lenb = static_lenb = stored_len + 5;
967 if (buf != (
char*)0) {
969 if (stored_len+4 <= opt_lenb && buf != (
char*)0) {
981 }
else if (static_lenb >= 0) {
996 s->compressed_len += 3 + s->
opt_len;
999 Assert (s->compressed_len == s->bits_sent,
"bad compressed size");
1008 s->compressed_len += 7;
1011 Tracev((stderr,
"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1012 s->compressed_len-7*last));
1034 (
ush)
d_code(dist) < (
ush)D_CODES,
"_tr_tally: bad match");
1040 #ifdef TRUNCATE_BLOCK
1047 for (dcode = 0; dcode <
D_CODES; dcode++) {
1052 Tracev((stderr,
"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1053 s->
last_lit, in_length, out_length,
1054 100L - out_length*100L/in_length));
1079 dist = s->
d_buf[lx];
1080 lc = s->
l_buf[lx++];
1083 Tracecv(isgraph(lc), (stderr,
" '%c' ", lc));
1095 Assert (code < D_CODES,
"bad d_code");
1107 "pendingBuf overflow");
1109 }
while (lx < s->last_lit);
1134 unsigned long black_mask = 0xf3ffc07fUL;
1138 for (n = 0; n <= 31; n++, black_mask >>= 1)
1139 if ((black_mask & 1) && (s->
dyn_ltree[n].Freq != 0))
1164 register unsigned res = 0;
1167 code >>= 1, res <<= 1;
1168 }
while (--len > 0);
1201 s->bits_sent = (s->bits_sent+7) & ~7;
1221 s->bits_sent += 2*16;
1225 s->bits_sent += (
ulg)len<<3;