00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036 #include "deflate.h"
00037
00038 #ifdef DEBUG
00039 # include <ctype.h>
00040 #endif
00041
00042
00043
00044
00045
00046 #define MAX_BL_BITS 7
00047
00048
00049 #define END_BLOCK 256
00050
00051
00052 #define REP_3_6 16
00053
00054
00055 #define REPZ_3_10 17
00056
00057
00058 #define REPZ_11_138 18
00059
00060
00061 local const int extra_lbits[LENGTH_CODES]
00062 = {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};
00063
00064 local const int extra_dbits[D_CODES]
00065 = {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};
00066
00067 local const int extra_blbits[BL_CODES]
00068 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
00069
00070 local const uch bl_order[BL_CODES]
00071 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
00072
00073
00074
00075
00076 #define Buf_size (8 * 2*sizeof(char))
00077
00078
00079
00080
00081
00082
00083
00084
00085 #define DIST_CODE_LEN 512
00086
00087 #if defined(GEN_TREES_H) || !defined(STDC)
00088
00089
00090 local ct_data static_ltree[L_CODES+2];
00091
00092
00093
00094
00095
00096
00097 local ct_data static_dtree[D_CODES];
00098
00099
00100
00101
00102 uch _dist_code[DIST_CODE_LEN];
00103
00104
00105
00106
00107
00108 uch _length_code[MAX_MATCH-MIN_MATCH+1];
00109
00110
00111 local int base_length[LENGTH_CODES];
00112
00113
00114 local int base_dist[D_CODES];
00115
00116
00117 #else
00118 # include "trees.h"
00119 #endif
00120
00121 struct static_tree_desc_s {
00122 const ct_data *static_tree;
00123 const intf *extra_bits;
00124 int extra_base;
00125 int elems;
00126 int max_length;
00127 };
00128
00129 local static_tree_desc static_l_desc =
00130 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
00131
00132 local static_tree_desc static_d_desc =
00133 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
00134
00135 local static_tree_desc static_bl_desc =
00136 {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
00137
00138
00139
00140
00141
00142 local void tr_static_init OF((void));
00143 local void init_block OF((deflate_state *s));
00144 local void pqdownheap OF((deflate_state *s, ct_data *tree, int k));
00145 local void gen_bitlen OF((deflate_state *s, tree_desc *desc));
00146 local void gen_codes OF((ct_data *tree, int max_code, ushf *bl_count));
00147 local void build_tree OF((deflate_state *s, tree_desc *desc));
00148 local void scan_tree OF((deflate_state *s, ct_data *tree, int max_code));
00149 local void send_tree OF((deflate_state *s, ct_data *tree, int max_code));
00150 local int build_bl_tree OF((deflate_state *s));
00151 local void send_all_trees OF((deflate_state *s, int lcodes, int dcodes,
00152 int blcodes));
00153 local void compress_block OF((deflate_state *s, ct_data *ltree,
00154 ct_data *dtree));
00155 local void set_data_type OF((deflate_state *s));
00156 local unsigned bi_reverse OF((unsigned value, int length));
00157 local void bi_windup OF((deflate_state *s));
00158 local void bi_flush OF((deflate_state *s));
00159 local void copy_block OF((deflate_state *s, charf *buf, unsigned len,
00160 int header));
00161
00162 #ifdef GEN_TREES_H
00163 local void gen_trees_header OF((void));
00164 #endif
00165
00166 #ifndef DEBUG
00167 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
00168
00169
00170 #else
00171 # define send_code(s, c, tree) \
00172 { if (z_verbose>2) fprintf(stderr,(char*)"\ncd %3d ",(c)); \
00173 send_bits(s, tree[c].Code, tree[c].Len); }
00174 #endif
00175
00176
00177
00178
00179
00180 #define put_short(s, w) { \
00181 put_byte(s, (uch)((w) & 0xff)); \
00182 put_byte(s, (uch)((ush)(w) >> 8)); \
00183 }
00184
00185
00186
00187
00188
00189 #ifdef DEBUG
00190 local void send_bits OF((deflate_state *s, int value, int length));
00191
00192 local void send_bits(deflate_state *s, int value, int length)
00193 {
00194 Tracevv((stderr,(char*)" l %2d v %4x ", length, value));
00195 Assert(length > 0 && length <= 15, (char*)"invalid length");
00196 s->bits_sent += (ulg)length;
00197
00198
00199
00200
00201
00202 if (s->bi_valid > (int)Buf_size - length) {
00203 s->bi_buf |= (value << s->bi_valid);
00204 put_short(s, s->bi_buf);
00205 s->bi_buf = (ush)value >> (Buf_size - s->bi_valid);
00206 s->bi_valid += length - Buf_size;
00207 } else {
00208 s->bi_buf |= value << s->bi_valid;
00209 s->bi_valid += length;
00210 }
00211 }
00212 #else
00213
00214 #define send_bits(s, value, length) \
00215 { int len = length;\
00216 if (s->bi_valid > (int)Buf_size - len) {\
00217 int val = value;\
00218 s->bi_buf |= (val << s->bi_valid);\
00219 put_short(s, s->bi_buf);\
00220 s->bi_buf = (ush)val >> (Buf_size - s->bi_valid);\
00221 s->bi_valid += len - Buf_size;\
00222 } else {\
00223 s->bi_buf |= (value) << s->bi_valid;\
00224 s->bi_valid += len;\
00225 }\
00226 }
00227 #endif
00228
00229
00230
00231
00232
00233
00234
00235 local void tr_static_init()
00236 {
00237 #if defined(GEN_TREES_H) || !defined(STDC)
00238 static int static_init_done = 0;
00239 int n;
00240 int bits;
00241 int length;
00242 int code;
00243 int dist;
00244 ush bl_count[MAX_BITS+1];
00245
00246
00247 if (static_init_done) return;
00248
00249
00250 static_l_desc.static_tree = static_ltree;
00251 static_l_desc.extra_bits = extra_lbits;
00252 static_d_desc.static_tree = static_dtree;
00253 static_d_desc.extra_bits = extra_dbits;
00254 static_bl_desc.extra_bits = extra_blbits;
00255
00256
00257 length = 0;
00258 for (code = 0; code < LENGTH_CODES-1; code++) {
00259 base_length[code] = length;
00260 for (n = 0; n < (1<<extra_lbits[code]); n++) {
00261 _length_code[length++] = (uch)code;
00262 }
00263 }
00264 Assert (length == 256, (char*)"tr_static_init: length != 256");
00265
00266
00267
00268
00269 _length_code[length-1] = (uch)code;
00270
00271
00272 dist = 0;
00273 for (code = 0 ; code < 16; code++) {
00274 base_dist[code] = dist;
00275 for (n = 0; n < (1<<extra_dbits[code]); n++) {
00276 _dist_code[dist++] = (uch)code;
00277 }
00278 }
00279 Assert (dist == 256, (char*)"tr_static_init: dist != 256");
00280 dist >>= 7;
00281 for ( ; code < D_CODES; code++) {
00282 base_dist[code] = dist << 7;
00283 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
00284 _dist_code[256 + dist++] = (uch)code;
00285 }
00286 }
00287 Assert (dist == 256, (char*)"tr_static_init: 256+dist != 512");
00288
00289
00290 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
00291 n = 0;
00292 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
00293 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
00294 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
00295 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
00296
00297
00298
00299
00300 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
00301
00302
00303 for (n = 0; n < D_CODES; n++) {
00304 static_dtree[n].Len = 5;
00305 static_dtree[n].Code = bi_reverse((unsigned)n, 5);
00306 }
00307 static_init_done = 1;
00308
00309 # ifdef GEN_TREES_H
00310 gen_trees_header();
00311 # endif
00312 #endif
00313 }
00314
00315
00316
00317
00318 #ifdef GEN_TREES_H
00319 # ifndef DEBUG
00320 # include <stdio.h>
00321 # endif
00322
00323 # define SEPARATOR(i, last, width) \
00324 ((i) == (last)? (char*)"\n};\n\n" : \
00325 ((i) % (width) == (width)-1 ? (char*)",\n" : ", "))
00326
00327 void gen_trees_header()
00328 {
00329 FILE *header = fopen((char*)"trees.h", (char*)"w");
00330 int i;
00331
00332 Assert (header != NULL, (char*)"Can't open trees.h");
00333 fprintf(header,
00334 (char*)"/* header created automatically with -DGEN_TREES_H */\n\n");
00335
00336 fprintf(header, (char*)"local const ct_data static_ltree[L_CODES+2] = {\n");
00337 for (i = 0; i < L_CODES+2; i++) {
00338 fprintf(header, (char*)"{{%3u},{%3u}}%s", static_ltree[i].Code,
00339 static_ltree[i].Len, SEPARATOR(i, L_CODES+1, 5));
00340 }
00341
00342 fprintf(header, (char*)"local const ct_data static_dtree[D_CODES] = {\n");
00343 for (i = 0; i < D_CODES; i++) {
00344 fprintf(header, (char*)"{{%2u},{%2u}}%s", static_dtree[i].Code,
00345 static_dtree[i].Len, SEPARATOR(i, D_CODES-1, 5));
00346 }
00347
00348 fprintf(header, (char*)"const uch _dist_code[DIST_CODE_LEN] = {\n");
00349 for (i = 0; i < DIST_CODE_LEN; i++) {
00350 fprintf(header, (char*)"%2u%s", _dist_code[i],
00351 SEPARATOR(i, DIST_CODE_LEN-1, 20));
00352 }
00353
00354 fprintf(header, (char*)"const uch _length_code[MAX_MATCH-MIN_MATCH+1]= {\n");
00355 for (i = 0; i < MAX_MATCH-MIN_MATCH+1; i++) {
00356 fprintf(header, (char*)"%2u%s", _length_code[i],
00357 SEPARATOR(i, MAX_MATCH-MIN_MATCH, 20));
00358 }
00359
00360 fprintf(header, (char*)"local const int base_length[LENGTH_CODES] = {\n");
00361 for (i = 0; i < LENGTH_CODES; i++) {
00362 fprintf(header, (char*)"%1u%s", base_length[i],
00363 SEPARATOR(i, LENGTH_CODES-1, 20));
00364 }
00365
00366 fprintf(header, (char*)"local const int base_dist[D_CODES] = {\n");
00367 for (i = 0; i < D_CODES; i++) {
00368 fprintf(header, (char*)"%5u%s", base_dist[i],
00369 SEPARATOR(i, D_CODES-1, 10));
00370 }
00371
00372 fclose(header);
00373 }
00374 #endif
00375
00376
00377
00378
00379 void _tr_init(deflate_state *s)
00380 {
00381 tr_static_init();
00382
00383 s->l_desc.dyn_tree = s->dyn_ltree;
00384 s->l_desc.stat_desc = &static_l_desc;
00385
00386 s->d_desc.dyn_tree = s->dyn_dtree;
00387 s->d_desc.stat_desc = &static_d_desc;
00388
00389 s->bl_desc.dyn_tree = s->bl_tree;
00390 s->bl_desc.stat_desc = &static_bl_desc;
00391
00392 s->bi_buf = 0;
00393 s->bi_valid = 0;
00394 s->last_eob_len = 8;
00395 #ifdef DEBUG
00396 s->compressed_len = 0L;
00397 s->bits_sent = 0L;
00398 #endif
00399
00400
00401 init_block(s);
00402 }
00403
00404
00405
00406
00407 local void init_block(deflate_state *s)
00408 {
00409 int n;
00410
00411
00412 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
00413 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
00414 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
00415
00416 s->dyn_ltree[END_BLOCK].Freq = 1;
00417 s->opt_len = s->static_len = 0L;
00418 s->last_lit = s->matches = 0;
00419 }
00420
00421 #define SMALLEST 1
00422
00423
00424
00425
00426
00427
00428
00429 #define pqremove(s, tree, top) \
00430 {\
00431 top = s->heap[SMALLEST]; \
00432 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
00433 pqdownheap(s, tree, SMALLEST); \
00434 }
00435
00436
00437
00438
00439
00440 #define smaller(tree, n, m, depth) \
00441 (tree[n].Freq < tree[m].Freq || \
00442 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
00443
00444
00445
00446
00447
00448
00449
00450 local void pqdownheap(deflate_state *s, ct_data *tree, int k)
00451 {
00452 int v = s->heap[k];
00453 int j = k << 1;
00454 while (j <= s->heap_len) {
00455
00456 if (j < s->heap_len &&
00457 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
00458 j++;
00459 }
00460
00461 if (smaller(tree, v, s->heap[j], s->depth)) break;
00462
00463
00464 s->heap[k] = s->heap[j]; k = j;
00465
00466
00467 j <<= 1;
00468 }
00469 s->heap[k] = v;
00470 }
00471
00472
00473
00474
00475
00476
00477
00478
00479
00480
00481
00482 local void gen_bitlen(deflate_state *s, tree_desc *desc)
00483 {
00484 ct_data *tree = desc->dyn_tree;
00485 int max_code = desc->max_code;
00486 const ct_data *stree = desc->stat_desc->static_tree;
00487 const intf *extra = desc->stat_desc->extra_bits;
00488 int base = desc->stat_desc->extra_base;
00489 int max_length = desc->stat_desc->max_length;
00490 int h;
00491 int n, m;
00492 int bits;
00493 int xbits;
00494 ush f;
00495 int overflow = 0;
00496
00497 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
00498
00499
00500
00501
00502 tree[s->heap[s->heap_max]].Len = 0;
00503
00504 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
00505 n = s->heap[h];
00506 bits = tree[tree[n].Dad].Len + 1;
00507 if (bits > max_length) bits = max_length, overflow++;
00508 tree[n].Len = (ush)bits;
00509
00510
00511 if (n > max_code) continue;
00512
00513 s->bl_count[bits]++;
00514 xbits = 0;
00515 if (n >= base) xbits = extra[n-base];
00516 f = tree[n].Freq;
00517 s->opt_len += (ulg)f * (bits + xbits);
00518 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
00519 }
00520 if (overflow == 0) return;
00521
00522 Trace((stderr,(char*)"\nbit length overflow\n"));
00523
00524
00525
00526 do {
00527 bits = max_length-1;
00528 while (s->bl_count[bits] == 0) bits--;
00529 s->bl_count[bits]--;
00530 s->bl_count[bits+1] += 2;
00531 s->bl_count[max_length]--;
00532
00533
00534
00535 overflow -= 2;
00536 } while (overflow > 0);
00537
00538
00539
00540
00541
00542
00543 for (bits = max_length; bits != 0; bits--) {
00544 n = s->bl_count[bits];
00545 while (n != 0) {
00546 m = s->heap[--h];
00547 if (m > max_code) continue;
00548 if (tree[m].Len != (unsigned) bits) {
00549 Trace((stderr,(char*)"code %d bits %d->%d\n", m, tree[m].Len, bits));
00550 s->opt_len += ((long)bits - (long)tree[m].Len)
00551 *(long)tree[m].Freq;
00552 tree[m].Len = (ush)bits;
00553 }
00554 n--;
00555 }
00556 }
00557 }
00558
00559
00560
00561
00562
00563
00564
00565
00566
00567 local void gen_codes (ct_data *tree, int max_code, ushf *bl_count)
00568 {
00569 ush next_code[MAX_BITS+1];
00570 ush code = 0;
00571 int bits;
00572 int n;
00573
00574
00575
00576
00577 for (bits = 1; bits <= MAX_BITS; bits++) {
00578 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
00579 }
00580
00581
00582
00583 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
00584 (char*)"inconsistent bit counts");
00585 Tracev((stderr,(char*)"\ngen_codes: max_code %d ", max_code));
00586
00587 for (n = 0; n <= max_code; n++) {
00588 int len = tree[n].Len;
00589 if (len == 0) continue;
00590
00591 tree[n].Code = bi_reverse(next_code[len]++, len);
00592
00593 Tracecv(tree != static_ltree, (stderr,(char*)"\nn %3d %c l %2d c %4x (%x) ",
00594 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
00595 }
00596 }
00597
00598
00599
00600
00601
00602
00603
00604
00605
00606 local void build_tree(deflate_state *s, tree_desc *desc)
00607 {
00608 ct_data *tree = desc->dyn_tree;
00609 const ct_data *stree = desc->stat_desc->static_tree;
00610 int elems = desc->stat_desc->elems;
00611 int n, m;
00612 int max_code = -1;
00613 int node;
00614
00615
00616
00617
00618
00619 s->heap_len = 0, s->heap_max = HEAP_SIZE;
00620
00621 for (n = 0; n < elems; n++) {
00622 if (tree[n].Freq != 0) {
00623 s->heap[++(s->heap_len)] = max_code = n;
00624 s->depth[n] = 0;
00625 } else {
00626 tree[n].Len = 0;
00627 }
00628 }
00629
00630
00631
00632
00633
00634
00635 while (s->heap_len < 2) {
00636 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
00637 tree[node].Freq = 1;
00638 s->depth[node] = 0;
00639 s->opt_len--; if (stree) s->static_len -= stree[node].Len;
00640
00641 }
00642 desc->max_code = max_code;
00643
00644
00645
00646
00647 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
00648
00649
00650
00651
00652 node = elems;
00653 do {
00654 pqremove(s, tree, n);
00655 m = s->heap[SMALLEST];
00656
00657 s->heap[--(s->heap_max)] = n;
00658 s->heap[--(s->heap_max)] = m;
00659
00660
00661 tree[node].Freq = tree[n].Freq + tree[m].Freq;
00662 s->depth[node] = (uch)((s->depth[n] >= s->depth[m] ?
00663 s->depth[n] : s->depth[m]) + 1);
00664 tree[n].Dad = tree[m].Dad = (ush)node;
00665 #ifdef DUMP_BL_TREE
00666 if (tree == s->bl_tree) {
00667 fprintf(stderr,(char*)"\nnode %d(%d), sons %d(%d) %d(%d)",
00668 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
00669 }
00670 #endif
00671
00672 s->heap[SMALLEST] = node++;
00673 pqdownheap(s, tree, SMALLEST);
00674
00675 } while (s->heap_len >= 2);
00676
00677 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
00678
00679
00680
00681
00682 gen_bitlen(s, (tree_desc *)desc);
00683
00684
00685 gen_codes ((ct_data *)tree, max_code, s->bl_count);
00686 }
00687
00688
00689
00690
00691
00692 local void scan_tree (deflate_state *s, ct_data *tree, int max_code)
00693 {
00694 int n;
00695 int prevlen = -1;
00696 int curlen;
00697 int nextlen = tree[0].Len;
00698 int count = 0;
00699 int max_count = 7;
00700 int min_count = 4;
00701
00702 if (nextlen == 0) max_count = 138, min_count = 3;
00703 tree[max_code+1].Len = (ush)0xffff;
00704
00705 for (n = 0; n <= max_code; n++) {
00706 curlen = nextlen; nextlen = tree[n+1].Len;
00707 if (++count < max_count && curlen == nextlen) {
00708 continue;
00709 } else if (count < min_count) {
00710 s->bl_tree[curlen].Freq += count;
00711 } else if (curlen != 0) {
00712 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
00713 s->bl_tree[REP_3_6].Freq++;
00714 } else if (count <= 10) {
00715 s->bl_tree[REPZ_3_10].Freq++;
00716 } else {
00717 s->bl_tree[REPZ_11_138].Freq++;
00718 }
00719 count = 0; prevlen = curlen;
00720 if (nextlen == 0) {
00721 max_count = 138, min_count = 3;
00722 } else if (curlen == nextlen) {
00723 max_count = 6, min_count = 3;
00724 } else {
00725 max_count = 7, min_count = 4;
00726 }
00727 }
00728 }
00729
00730
00731
00732
00733
00734 local void send_tree (deflate_state *s, ct_data *tree, int max_code)
00735 {
00736 int n;
00737 int prevlen = -1;
00738 int curlen;
00739 int nextlen = tree[0].Len;
00740 int count = 0;
00741 int max_count = 7;
00742 int min_count = 4;
00743
00744
00745 if (nextlen == 0) max_count = 138, min_count = 3;
00746
00747 for (n = 0; n <= max_code; n++) {
00748 curlen = nextlen; nextlen = tree[n+1].Len;
00749 if (++count < max_count && curlen == nextlen) {
00750 continue;
00751 } else if (count < min_count) {
00752 do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
00753
00754 } else if (curlen != 0) {
00755 if (curlen != prevlen) {
00756 send_code(s, curlen, s->bl_tree); count--;
00757 }
00758 Assert(count >= 3 && count <= 6, (char*)" 3_6?");
00759 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
00760
00761 } else if (count <= 10) {
00762 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
00763
00764 } else {
00765 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
00766 }
00767 count = 0; prevlen = curlen;
00768 if (nextlen == 0) {
00769 max_count = 138, min_count = 3;
00770 } else if (curlen == nextlen) {
00771 max_count = 6, min_count = 3;
00772 } else {
00773 max_count = 7, min_count = 4;
00774 }
00775 }
00776 }
00777
00778
00779
00780
00781
00782 local int build_bl_tree(deflate_state *s)
00783 {
00784 int max_blindex;
00785
00786
00787 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
00788 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
00789
00790
00791 build_tree(s, (tree_desc *)(&(s->bl_desc)));
00792
00793
00794
00795
00796
00797
00798
00799
00800 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
00801 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
00802 }
00803
00804 s->opt_len += 3*(max_blindex+1) + 5+5+4;
00805 Tracev((stderr, (char*)"\ndyn trees: dyn %ld, stat %ld",
00806 s->opt_len, s->static_len));
00807
00808 return max_blindex;
00809 }
00810
00811
00812
00813
00814
00815
00816 local void send_all_trees(deflate_state *s, int lcodes, int dcodes, int blcodes)
00817 {
00818 int rank;
00819
00820 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, (char*)"not enough codes");
00821 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
00822 (char*)"too many codes");
00823 Tracev((stderr, (char*)"\nbl counts: "));
00824 send_bits(s, lcodes-257, 5);
00825 send_bits(s, dcodes-1, 5);
00826 send_bits(s, blcodes-4, 4);
00827 for (rank = 0; rank < blcodes; rank++) {
00828 Tracev((stderr, (char*)"\nbl code %2d ", bl_order[rank]));
00829 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
00830 }
00831 Tracev((stderr, (char*)"\nbl tree: sent %ld", s->bits_sent));
00832
00833 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
00834 Tracev((stderr, (char*)"\nlit tree: sent %ld", s->bits_sent));
00835
00836 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
00837 Tracev((stderr, (char*)"\ndist tree: sent %ld", s->bits_sent));
00838 }
00839
00840
00841
00842
00843 void _tr_stored_block(deflate_state *s, charf *buf, ulg stored_len, int eof)
00844 {
00845 send_bits(s, (STORED_BLOCK<<1)+eof, 3);
00846 #ifdef DEBUG
00847 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
00848 s->compressed_len += (stored_len + 4) << 3;
00849 #endif
00850 copy_block(s, buf, (unsigned)stored_len, 1);
00851 }
00852
00853
00854
00855
00856
00857
00858
00859
00860
00861
00862
00863
00864 void _tr_align(deflate_state *s)
00865 {
00866 send_bits(s, STATIC_TREES<<1, 3);
00867 send_code(s, END_BLOCK, static_ltree);
00868 #ifdef DEBUG
00869 s->compressed_len += 10L;
00870 #endif
00871 bi_flush(s);
00872
00873
00874
00875
00876
00877 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
00878 send_bits(s, STATIC_TREES<<1, 3);
00879 send_code(s, END_BLOCK, static_ltree);
00880 #ifdef DEBUG
00881 s->compressed_len += 10L;
00882 #endif
00883 bi_flush(s);
00884 }
00885 s->last_eob_len = 7;
00886 }
00887
00888
00889
00890
00891
00892 void _tr_flush_block(deflate_state *s, charf *buf, ulg stored_len, int eof)
00893 {
00894 ulg opt_lenb, static_lenb;
00895 int max_blindex = 0;
00896
00897
00898 if (s->level > 0) {
00899
00900
00901 if (s->strm->data_type == Z_UNKNOWN) set_data_type(s);
00902
00903
00904 build_tree(s, (tree_desc *)(&(s->l_desc)));
00905 Tracev((stderr, (char*)"\nlit data: dyn %ld, stat %ld", s->opt_len,
00906 s->static_len));
00907
00908 build_tree(s, (tree_desc *)(&(s->d_desc)));
00909 Tracev((stderr, (char*)"\ndist data: dyn %ld, stat %ld", s->opt_len,
00910 s->static_len));
00911
00912
00913
00914
00915
00916
00917
00918 max_blindex = build_bl_tree(s);
00919
00920
00921 opt_lenb = (s->opt_len+3+7)>>3;
00922 static_lenb = (s->static_len+3+7)>>3;
00923
00924 Tracev((stderr, (char*)"\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
00925 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
00926 s->last_lit));
00927
00928 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
00929
00930 } else {
00931 Assert(buf != (char*)0, (char*)"lost buf");
00932 opt_lenb = static_lenb = stored_len + 5;
00933 }
00934
00935 #ifdef FORCE_STORED
00936 if (buf != (char*)0) {
00937 #else
00938 if (stored_len+4 <= opt_lenb && buf != (char*)0) {
00939
00940 #endif
00941
00942
00943
00944
00945
00946
00947 _tr_stored_block(s, buf, stored_len, eof);
00948
00949 #ifdef FORCE_STATIC
00950 } else if (static_lenb >= 0) {
00951 #else
00952 } else if (static_lenb == opt_lenb) {
00953 #endif
00954 send_bits(s, (STATIC_TREES<<1)+eof, 3);
00955 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
00956 #ifdef DEBUG
00957 s->compressed_len += 3 + s->static_len;
00958 #endif
00959 } else {
00960 send_bits(s, (DYN_TREES<<1)+eof, 3);
00961 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
00962 max_blindex+1);
00963 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
00964 #ifdef DEBUG
00965 s->compressed_len += 3 + s->opt_len;
00966 #endif
00967 }
00968 Assert (s->compressed_len == s->bits_sent, (char*)"bad compressed size");
00969
00970
00971
00972 init_block(s);
00973
00974 if (eof) {
00975 bi_windup(s);
00976 #ifdef DEBUG
00977 s->compressed_len += 7;
00978 #endif
00979 }
00980 Tracev((stderr,(char*)"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
00981 s->compressed_len-7*eof));
00982 }
00983
00984
00985
00986
00987
00988 int _tr_tally (deflate_state *s, unsigned dist, unsigned lc)
00989 {
00990 s->d_buf[s->last_lit] = (ush)dist;
00991 s->l_buf[s->last_lit++] = (uch)lc;
00992 if (dist == 0) {
00993
00994 s->dyn_ltree[lc].Freq++;
00995 } else {
00996 s->matches++;
00997
00998 dist--;
00999 Assert((ush)dist < (ush)MAX_DIST(s) &&
01000 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
01001 (ush)d_code(dist) < (ush)D_CODES, (char*)"_tr_tally: bad match");
01002
01003 s->dyn_ltree[_length_code[lc]+LITERALS+1].Freq++;
01004 s->dyn_dtree[d_code(dist)].Freq++;
01005 }
01006
01007 #ifdef TRUNCATE_BLOCK
01008
01009 if ((s->last_lit & 0x1fff) == 0 && s->level > 2) {
01010
01011 ulg out_length = (ulg)s->last_lit*8L;
01012 ulg in_length = (ulg)((long)s->strstart - s->block_start);
01013 int dcode;
01014 for (dcode = 0; dcode < D_CODES; dcode++) {
01015 out_length += (ulg)s->dyn_dtree[dcode].Freq *
01016 (5L+extra_dbits[dcode]);
01017 }
01018 out_length >>= 3;
01019 Tracev((stderr,(char*)"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
01020 s->last_lit, in_length, out_length,
01021 100L - out_length*100L/in_length));
01022 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
01023 }
01024 #endif
01025 return (s->last_lit == s->lit_bufsize-1);
01026
01027
01028
01029
01030 }
01031
01032
01033
01034
01035 local void compress_block(deflate_state *s, ct_data *ltree, ct_data *dtree)
01036 {
01037 unsigned dist;
01038 int lc;
01039 unsigned lx = 0;
01040 unsigned code;
01041 int extra;
01042
01043 if (s->last_lit != 0) do {
01044 dist = s->d_buf[lx];
01045 lc = s->l_buf[lx++];
01046 if (dist == 0) {
01047 send_code(s, lc, ltree);
01048 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
01049 } else {
01050
01051 code = _length_code[lc];
01052 send_code(s, code+LITERALS+1, ltree);
01053 extra = extra_lbits[code];
01054 if (extra != 0) {
01055 lc -= base_length[code];
01056 send_bits(s, lc, extra);
01057 }
01058 dist--;
01059 code = d_code(dist);
01060 Assert (code < D_CODES, (char*)"bad d_code");
01061
01062 send_code(s, code, dtree);
01063 extra = extra_dbits[code];
01064 if (extra != 0) {
01065 dist -= base_dist[code];
01066 send_bits(s, dist, extra);
01067 }
01068 }
01069
01070
01071 Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
01072 (char*)"pendingBuf overflow");
01073
01074 } while (lx < s->last_lit);
01075
01076 send_code(s, END_BLOCK, ltree);
01077 s->last_eob_len = ltree[END_BLOCK].Len;
01078 }
01079
01080
01081
01082
01083
01084
01085
01086 local void set_data_type(deflate_state *s)
01087 {
01088 int n = 0;
01089 unsigned ascii_freq = 0;
01090 unsigned bin_freq = 0;
01091 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
01092 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
01093 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
01094 s->strm->data_type = bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII;
01095 }
01096
01097
01098
01099
01100
01101
01102 local unsigned bi_reverse(unsigned code, int len)
01103 {
01104 register unsigned res = 0;
01105 do {
01106 res |= code & 1;
01107 code >>= 1, res <<= 1;
01108 } while (--len > 0);
01109 return res >> 1;
01110 }
01111
01112
01113
01114
01115 local void bi_flush(deflate_state *s)
01116 {
01117 if (s->bi_valid == 16) {
01118 put_short(s, s->bi_buf);
01119 s->bi_buf = 0;
01120 s->bi_valid = 0;
01121 } else if (s->bi_valid >= 8) {
01122 put_byte(s, (Byte)s->bi_buf);
01123 s->bi_buf >>= 8;
01124 s->bi_valid -= 8;
01125 }
01126 }
01127
01128
01129
01130
01131 local void bi_windup(deflate_state *s)
01132 {
01133 if (s->bi_valid > 8) {
01134 put_short(s, s->bi_buf);
01135 } else if (s->bi_valid > 0) {
01136 put_byte(s, (Byte)s->bi_buf);
01137 }
01138 s->bi_buf = 0;
01139 s->bi_valid = 0;
01140 #ifdef DEBUG
01141 s->bits_sent = (s->bits_sent+7) & ~7;
01142 #endif
01143 }
01144
01145
01146
01147
01148
01149 local void copy_block(deflate_state *s, charf *buf, unsigned len, int header)
01150 {
01151 bi_windup(s);
01152 s->last_eob_len = 8;
01153
01154 if (header) {
01155 put_short(s, (ush)len);
01156 put_short(s, (ush)~len);
01157 #ifdef DEBUG
01158 s->bits_sent += 2*16;
01159 #endif
01160 }
01161 #ifdef DEBUG
01162 s->bits_sent += (ulg)len<<3;
01163 #endif
01164 while (len--) {
01165 put_byte(s, *buf++);
01166 }
01167 }