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)
125 #ifdef NO_INIT_GLOBAL_POINTERS
128 # define TCONST const
144 #define put_short(s, w) { \
145 put_byte(s, (uch)((w) & 0xff)); \
146 put_byte(s, (uch)((ush)(w) >> 8)); \
155 register unsigned res = 0;
158 code >>= 1, res <<= 1;
190 s->bits_sent = (s->bits_sent + 7) & ~7;
211 for (bits = 1; bits <=
MAX_BITS; bits++) {
212 code = (code + bl_count[bits - 1]) << 1;
213 next_code[bits] = (
ush)code;
219 "inconsistent bit counts");
220 Tracev((stderr,
"\ngen_codes: max_code %d ", max_code));
222 for (n = 0; n <= max_code; n++) {
223 int len = tree[n].Len;
224 if (len == 0)
continue;
229 n, (isgraph(n) ? n :
' '), len, tree[n].
Code, next_code[len] - 1));
234 local void gen_trees_header(
void);
238 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
242 # define send_code(s, c, tree) \
243 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
244 send_bits(s, tree[c].Code, tree[c].Len); }
253 Tracevv((stderr,
" l %2d v %4x ", length, value));
254 Assert(length > 0 && length <= 15,
"invalid length");
255 s->bits_sent += (
ulg)length;
273 #define send_bits(s, value, length) \
275 if (s->bi_valid > (int)Buf_size - len) {\
276 int val = (int)value;\
277 s->bi_buf |= (ush)val << s->bi_valid;\
278 put_short(s, s->bi_buf);\
279 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
280 s->bi_valid += len - Buf_size;\
282 s->bi_buf |= (ush)(value) << s->bi_valid;\
295 #if defined(GEN_TREES_H) || !defined(STDC)
296 static int static_init_done = 0;
305 if (static_init_done)
return;
308 #ifdef NO_INIT_GLOBAL_POINTERS
324 Assert (length == 256,
"tr_static_init: length != 256");
333 for (code = 0 ; code < 16; code++) {
339 Assert (dist == 256,
"tr_static_init: dist != 256");
341 for ( ; code <
D_CODES; code++) {
343 for (n = 0; n < (1 << (
extra_dbits[code] - 7)); n++) {
347 Assert (dist == 256,
"tr_static_init: 256 + dist != 512");
350 for (bits = 0; bits <=
MAX_BITS; bits++) bl_count[bits] = 0;
352 while (n <= 143)
static_ltree[n++].Len = 8, bl_count[8]++;
353 while (n <= 255)
static_ltree[n++].Len = 9, bl_count[9]++;
354 while (n <= 279)
static_ltree[n++].Len = 7, bl_count[7]++;
355 while (n <= 287)
static_ltree[n++].Len = 8, bl_count[8]++;
363 for (n = 0; n <
D_CODES; n++) {
367 static_init_done = 1;
383 # define SEPARATOR(i, last, width) \
384 ((i) == (last)? "\n};\n\n" : \
385 ((i) % (width) == (width) - 1 ? ",\n" : ", "))
387 void gen_trees_header(
void) {
388 FILE *header = fopen(
"trees.h",
"w");
391 Assert (header != NULL,
"Can't open trees.h");
393 "/* header created automatically with -DGEN_TREES_H */\n\n");
395 fprintf(header,
"local const ct_data static_ltree[L_CODES+2] = {\n");
396 for (i = 0; i <
L_CODES+2; i++) {
401 fprintf(header,
"local const ct_data static_dtree[D_CODES] = {\n");
402 for (i = 0; i <
D_CODES; i++) {
407 fprintf(header,
"const uch ZLIB_INTERNAL _dist_code[DIST_CODE_LEN] = {\n");
410 SEPARATOR(i, DIST_CODE_LEN-1, 20));
414 "const uch ZLIB_INTERNAL _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
420 fprintf(header,
"local const int base_length[LENGTH_CODES] = {\n");
423 SEPARATOR(i, LENGTH_CODES-1, 20));
426 fprintf(header,
"local const int base_dist[D_CODES] = {\n");
427 for (i = 0; i <
D_CODES; i++) {
429 SEPARATOR(i, D_CODES-1, 10));
470 s->compressed_len = 0L;
486 #define pqremove(s, tree, top) \
488 top = s->heap[SMALLEST]; \
489 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
490 pqdownheap(s, tree, SMALLEST); \
497 #define smaller(tree, n, m, depth) \
498 (tree[n].Freq < tree[m].Freq || \
499 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
510 while (j <= s->heap_len) {
512 if (j < s->heap_len &&
561 bits = tree[tree[n].Dad].Len + 1;
562 if (bits > max_length) bits =
max_length, overflow++;
563 tree[n].Len = (
ush)bits;
566 if (n > max_code)
continue;
570 if (n >= base) xbits = extra[n - base];
572 s->
opt_len += (
ulg)f * (
unsigned)(bits + xbits);
573 if (stree) s->
static_len += (
ulg)f * (
unsigned)(stree[n].Len + xbits);
575 if (overflow == 0)
return;
577 Tracev((stderr,
"\nbit length overflow\n"));
582 bits = max_length - 1;
583 while (s->
bl_count[bits] == 0) bits--;
591 }
while (overflow > 0);
598 for (bits = max_length; bits != 0; bits--) {
602 if (m > max_code)
continue;
603 if ((
unsigned) tree[m].
Len != (
unsigned) bits) {
604 Tracev((stderr,
"code %d bits %d->%d\n", m, tree[m].
Len, bits));
605 s->
opt_len += ((
ulg)bits - tree[m].Len) * tree[m].Freq;
606 tree[m].Len = (
ush)bits;
639 for (n = 0; n < elems; n++) {
640 if (tree[n].
Freq != 0) {
654 node = s->
heap[++(s->
heap_len)] = (max_code < 2 ? ++max_code : 0);
679 tree[node].Freq = tree[n].Freq + tree[m].Freq;
682 tree[n].Dad = tree[m].Dad = (
ush)node;
685 fprintf(stderr,
"\nnode %d(%d), sons %d(%d) %d(%d)",
686 node, tree[node].
Freq, n, tree[n].Freq, m, tree[m].Freq);
714 int nextlen = tree[0].Len;
719 if (nextlen == 0) max_count = 138, min_count = 3;
720 tree[max_code + 1].Len = (
ush)0xffff;
722 for (n = 0; n <= max_code; n++) {
723 curlen = nextlen; nextlen = tree[n + 1].Len;
724 if (++count < max_count && curlen == nextlen) {
726 }
else if (count < min_count) {
727 s->
bl_tree[curlen].Freq += count;
728 }
else if (curlen != 0) {
729 if (curlen != prevlen) s->
bl_tree[curlen].Freq++;
731 }
else if (count <= 10) {
736 count = 0; prevlen = curlen;
738 max_count = 138, min_count = 3;
739 }
else if (curlen == nextlen) {
740 max_count = 6, min_count = 3;
742 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) {
770 }
else if (curlen != 0) {
771 if (curlen != prevlen) {
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;
815 for (max_blindex =
BL_CODES-1; max_blindex >= 3; max_blindex--) {
819 s->
opt_len += 3*((
ulg)max_blindex + 1) + 5 + 5 + 4;
820 Tracev((stderr,
"\ndyn trees: dyn %ld, stat %ld",
835 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4,
"not enough codes");
836 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <=
BL_CODES,
838 Tracev((stderr,
"\nbl counts: "));
842 for (rank = 0; rank < blcodes; rank++) {
846 Tracev((stderr,
"\nbl tree: sent %ld", s->bits_sent));
849 Tracev((stderr,
"\nlit tree: sent %ld", s->bits_sent));
852 Tracev((stderr,
"\ndist tree: sent %ld", s->bits_sent));
859 ulg stored_len,
int last) {
868 s->compressed_len = (s->compressed_len + 3 + 7) & (
ulg)~7L;
869 s->compressed_len += (stored_len + 4) << 3;
870 s->bits_sent += 2*16;
871 s->bits_sent += stored_len << 3;
890 s->compressed_len += 10L;
911 dist = s->
sym_buf[sx++] & 0xff;
912 dist += (unsigned)(s->
sym_buf[sx++] & 0xff) << 8;
917 Tracecv(isgraph(lc), (stderr,
" '%c' ", lc));
929 Assert (code < D_CODES,
"bad d_code");
946 }
while (sx < s->sym_next);
969 unsigned long block_mask = 0xf3ffc07fUL;
973 for (n = 0; n <= 31; n++, block_mask >>= 1)
974 if ((block_mask & 1) && (s->
dyn_ltree[n].Freq != 0))
996 ulg stored_len,
int last) {
997 ulg opt_lenb, static_lenb;
1009 Tracev((stderr,
"\nlit data: dyn %ld, stat %ld", s->
opt_len,
1013 Tracev((stderr,
"\ndist data: dyn %ld, stat %ld", s->
opt_len,
1025 opt_lenb = (s->
opt_len + 3 + 7) >> 3;
1028 Tracev((stderr,
"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
1032 #ifndef FORCE_STATIC
1033 if (static_lenb <= opt_lenb || s->strategy ==
Z_FIXED)
1035 opt_lenb = static_lenb;
1038 Assert(buf != (
char*)0,
"lost buf");
1039 opt_lenb = static_lenb = stored_len + 5;
1043 if (buf != (
char*)0) {
1045 if (stored_len + 4 <= opt_lenb && buf != (
char*)0) {
1056 }
else if (static_lenb == opt_lenb) {
1070 s->compressed_len += 3 + s->
opt_len;
1073 Assert (s->compressed_len == s->bits_sent,
"bad compressed size");
1082 s->compressed_len += 7;
1085 Tracev((stderr,
"\ncomprlen %lu(%lu) ", s->compressed_len >> 3,
1086 s->compressed_len - 7*last));
1111 (
ush)
d_code(dist) < (
ush)D_CODES,
"_tr_tally: bad match");
local void compress_block(deflate_state *s, const ct_data *ltree, const ct_data *dtree)
local const int extra_dbits[D_CODES]
local ct_data static_dtree[D_CODES]
local TCONST static_tree_desc static_l_desc
local int detect_data_type(deflate_state *s)
void ZLIB_INTERNAL _tr_align(deflate_state *s)
#define Assert(cond, msg)
local int base_dist[D_CODES]
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)
struct ct_data_s dyn_ltree[HEAP_SIZE]
local void tr_static_init(void)
local int base_length[LENGTH_CODES]
#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 TCONST static_tree_desc static_bl_desc
local void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
struct tree_desc_s bl_desc
struct tree_desc_s d_desc
local TCONST static_tree_desc static_d_desc
void ZLIB_INTERNAL _tr_init(deflate_state *s)
const static_tree_desc * stat_desc
#define send_bits(s, value, length)
void ZLIB_INTERNAL _tr_flush_bits(deflate_state *s)
local const int extra_lbits[LENGTH_CODES]
void ZLIB_INTERNAL zmemcpy(Bytef *dest, const Bytef *source, uInt len)
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)
struct ct_data_s dyn_dtree[2 *D_CODES+1]
uch _dist_code[DIST_CODE_LEN]
struct tree_desc_s l_desc
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)
uch _length_code[MAX_MATCH-MIN_MATCH+1]
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)
void ZLIB_INTERNAL _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int last)
const ct_data * static_tree
local ct_data static_ltree[L_CODES+2]
local const int extra_blbits[BL_CODES]
struct ct_data_s bl_tree[2 *BL_CODES+1]
#define send_code(s, c, tree)
local void bi_flush(deflate_state *s)