0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017
0018
0019
0020
0021
0022
0023
0024
0025
0026
0027
0028
0029
0030
0031
0032
0033
0034
0035
0036
0037 #include <linux/zutil.h>
0038 #include <linux/bitrev.h>
0039 #include "defutil.h"
0040
0041 #ifdef DEBUG_ZLIB
0042 # include <ctype.h>
0043 #endif
0044
0045
0046
0047
0048
0049 #define MAX_BL_BITS 7
0050
0051
0052 #define END_BLOCK 256
0053
0054
0055 #define REP_3_6 16
0056
0057
0058 #define REPZ_3_10 17
0059
0060
0061 #define REPZ_11_138 18
0062
0063
0064 static const int extra_lbits[LENGTH_CODES]
0065 = {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};
0066
0067 static const int extra_dbits[D_CODES]
0068 = {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};
0069
0070 static const int extra_blbits[BL_CODES]
0071 = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7};
0072
0073 static const uch bl_order[BL_CODES]
0074 = {16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15};
0075
0076
0077
0078
0079
0080
0081
0082
0083 static ct_data static_ltree[L_CODES+2];
0084
0085
0086
0087
0088
0089
0090 static ct_data static_dtree[D_CODES];
0091
0092
0093
0094
0095 static uch dist_code[512];
0096
0097
0098
0099
0100
0101 static uch length_code[MAX_MATCH-MIN_MATCH+1];
0102
0103
0104 static int base_length[LENGTH_CODES];
0105
0106
0107 static int base_dist[D_CODES];
0108
0109
0110 struct static_tree_desc_s {
0111 const ct_data *static_tree;
0112 const int *extra_bits;
0113 int extra_base;
0114 int elems;
0115 int max_length;
0116 };
0117
0118 static static_tree_desc static_l_desc =
0119 {static_ltree, extra_lbits, LITERALS+1, L_CODES, MAX_BITS};
0120
0121 static static_tree_desc static_d_desc =
0122 {static_dtree, extra_dbits, 0, D_CODES, MAX_BITS};
0123
0124 static static_tree_desc static_bl_desc =
0125 {(const ct_data *)0, extra_blbits, 0, BL_CODES, MAX_BL_BITS};
0126
0127
0128
0129
0130
0131 static void tr_static_init (void);
0132 static void init_block (deflate_state *s);
0133 static void pqdownheap (deflate_state *s, ct_data *tree, int k);
0134 static void gen_bitlen (deflate_state *s, tree_desc *desc);
0135 static void gen_codes (ct_data *tree, int max_code, ush *bl_count);
0136 static void build_tree (deflate_state *s, tree_desc *desc);
0137 static void scan_tree (deflate_state *s, ct_data *tree, int max_code);
0138 static void send_tree (deflate_state *s, ct_data *tree, int max_code);
0139 static int build_bl_tree (deflate_state *s);
0140 static void send_all_trees (deflate_state *s, int lcodes, int dcodes,
0141 int blcodes);
0142 static void compress_block (deflate_state *s, ct_data *ltree,
0143 ct_data *dtree);
0144 static void set_data_type (deflate_state *s);
0145 static void bi_flush (deflate_state *s);
0146 static void copy_block (deflate_state *s, char *buf, unsigned len,
0147 int header);
0148
0149 #ifndef DEBUG_ZLIB
0150 # define send_code(s, c, tree) send_bits(s, tree[c].Code, tree[c].Len)
0151
0152
0153 #else
0154 # define send_code(s, c, tree) \
0155 { if (z_verbose>2) fprintf(stderr,"\ncd %3d ",(c)); \
0156 send_bits(s, tree[c].Code, tree[c].Len); }
0157 #endif
0158
0159 #define d_code(dist) \
0160 ((dist) < 256 ? dist_code[dist] : dist_code[256+((dist)>>7)])
0161
0162
0163
0164
0165
0166
0167
0168
0169
0170
0171 static void tr_static_init(void)
0172 {
0173 static int static_init_done;
0174 int n;
0175 int bits;
0176 int length;
0177 int code;
0178 int dist;
0179 ush bl_count[MAX_BITS+1];
0180
0181
0182 if (static_init_done) return;
0183
0184
0185 length = 0;
0186 for (code = 0; code < LENGTH_CODES-1; code++) {
0187 base_length[code] = length;
0188 for (n = 0; n < (1<<extra_lbits[code]); n++) {
0189 length_code[length++] = (uch)code;
0190 }
0191 }
0192 Assert (length == 256, "tr_static_init: length != 256");
0193
0194
0195
0196
0197 length_code[length-1] = (uch)code;
0198
0199
0200 dist = 0;
0201 for (code = 0 ; code < 16; code++) {
0202 base_dist[code] = dist;
0203 for (n = 0; n < (1<<extra_dbits[code]); n++) {
0204 dist_code[dist++] = (uch)code;
0205 }
0206 }
0207 Assert (dist == 256, "tr_static_init: dist != 256");
0208 dist >>= 7;
0209 for ( ; code < D_CODES; code++) {
0210 base_dist[code] = dist << 7;
0211 for (n = 0; n < (1<<(extra_dbits[code]-7)); n++) {
0212 dist_code[256 + dist++] = (uch)code;
0213 }
0214 }
0215 Assert (dist == 256, "tr_static_init: 256+dist != 512");
0216
0217
0218 for (bits = 0; bits <= MAX_BITS; bits++) bl_count[bits] = 0;
0219 n = 0;
0220 while (n <= 143) static_ltree[n++].Len = 8, bl_count[8]++;
0221 while (n <= 255) static_ltree[n++].Len = 9, bl_count[9]++;
0222 while (n <= 279) static_ltree[n++].Len = 7, bl_count[7]++;
0223 while (n <= 287) static_ltree[n++].Len = 8, bl_count[8]++;
0224
0225
0226
0227
0228 gen_codes((ct_data *)static_ltree, L_CODES+1, bl_count);
0229
0230
0231 for (n = 0; n < D_CODES; n++) {
0232 static_dtree[n].Len = 5;
0233 static_dtree[n].Code = bitrev32((u32)n) >> (32 - 5);
0234 }
0235 static_init_done = 1;
0236 }
0237
0238
0239
0240
0241 void zlib_tr_init(
0242 deflate_state *s
0243 )
0244 {
0245 tr_static_init();
0246
0247 s->compressed_len = 0L;
0248
0249 s->l_desc.dyn_tree = s->dyn_ltree;
0250 s->l_desc.stat_desc = &static_l_desc;
0251
0252 s->d_desc.dyn_tree = s->dyn_dtree;
0253 s->d_desc.stat_desc = &static_d_desc;
0254
0255 s->bl_desc.dyn_tree = s->bl_tree;
0256 s->bl_desc.stat_desc = &static_bl_desc;
0257
0258 s->bi_buf = 0;
0259 s->bi_valid = 0;
0260 s->last_eob_len = 8;
0261 #ifdef DEBUG_ZLIB
0262 s->bits_sent = 0L;
0263 #endif
0264
0265
0266 init_block(s);
0267 }
0268
0269
0270
0271
0272 static void init_block(
0273 deflate_state *s
0274 )
0275 {
0276 int n;
0277
0278
0279 for (n = 0; n < L_CODES; n++) s->dyn_ltree[n].Freq = 0;
0280 for (n = 0; n < D_CODES; n++) s->dyn_dtree[n].Freq = 0;
0281 for (n = 0; n < BL_CODES; n++) s->bl_tree[n].Freq = 0;
0282
0283 s->dyn_ltree[END_BLOCK].Freq = 1;
0284 s->opt_len = s->static_len = 0L;
0285 s->last_lit = s->matches = 0;
0286 }
0287
0288 #define SMALLEST 1
0289
0290
0291
0292
0293
0294
0295
0296 #define pqremove(s, tree, top) \
0297 {\
0298 top = s->heap[SMALLEST]; \
0299 s->heap[SMALLEST] = s->heap[s->heap_len--]; \
0300 pqdownheap(s, tree, SMALLEST); \
0301 }
0302
0303
0304
0305
0306
0307 #define smaller(tree, n, m, depth) \
0308 (tree[n].Freq < tree[m].Freq || \
0309 (tree[n].Freq == tree[m].Freq && depth[n] <= depth[m]))
0310
0311
0312
0313
0314
0315
0316
0317 static void pqdownheap(
0318 deflate_state *s,
0319 ct_data *tree,
0320 int k
0321 )
0322 {
0323 int v = s->heap[k];
0324 int j = k << 1;
0325 while (j <= s->heap_len) {
0326
0327 if (j < s->heap_len &&
0328 smaller(tree, s->heap[j+1], s->heap[j], s->depth)) {
0329 j++;
0330 }
0331
0332 if (smaller(tree, v, s->heap[j], s->depth)) break;
0333
0334
0335 s->heap[k] = s->heap[j]; k = j;
0336
0337
0338 j <<= 1;
0339 }
0340 s->heap[k] = v;
0341 }
0342
0343
0344
0345
0346
0347
0348
0349
0350
0351
0352
0353 static void gen_bitlen(
0354 deflate_state *s,
0355 tree_desc *desc
0356 )
0357 {
0358 ct_data *tree = desc->dyn_tree;
0359 int max_code = desc->max_code;
0360 const ct_data *stree = desc->stat_desc->static_tree;
0361 const int *extra = desc->stat_desc->extra_bits;
0362 int base = desc->stat_desc->extra_base;
0363 int max_length = desc->stat_desc->max_length;
0364 int h;
0365 int n, m;
0366 int bits;
0367 int xbits;
0368 ush f;
0369 int overflow = 0;
0370
0371 for (bits = 0; bits <= MAX_BITS; bits++) s->bl_count[bits] = 0;
0372
0373
0374
0375
0376 tree[s->heap[s->heap_max]].Len = 0;
0377
0378 for (h = s->heap_max+1; h < HEAP_SIZE; h++) {
0379 n = s->heap[h];
0380 bits = tree[tree[n].Dad].Len + 1;
0381 if (bits > max_length) bits = max_length, overflow++;
0382 tree[n].Len = (ush)bits;
0383
0384
0385 if (n > max_code) continue;
0386
0387 s->bl_count[bits]++;
0388 xbits = 0;
0389 if (n >= base) xbits = extra[n-base];
0390 f = tree[n].Freq;
0391 s->opt_len += (ulg)f * (bits + xbits);
0392 if (stree) s->static_len += (ulg)f * (stree[n].Len + xbits);
0393 }
0394 if (overflow == 0) return;
0395
0396 Trace((stderr,"\nbit length overflow\n"));
0397
0398
0399
0400 do {
0401 bits = max_length-1;
0402 while (s->bl_count[bits] == 0) bits--;
0403 s->bl_count[bits]--;
0404 s->bl_count[bits+1] += 2;
0405 s->bl_count[max_length]--;
0406
0407
0408
0409 overflow -= 2;
0410 } while (overflow > 0);
0411
0412
0413
0414
0415
0416
0417 for (bits = max_length; bits != 0; bits--) {
0418 n = s->bl_count[bits];
0419 while (n != 0) {
0420 m = s->heap[--h];
0421 if (m > max_code) continue;
0422 if (tree[m].Len != (unsigned) bits) {
0423 Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
0424 s->opt_len += ((long)bits - (long)tree[m].Len)
0425 *(long)tree[m].Freq;
0426 tree[m].Len = (ush)bits;
0427 }
0428 n--;
0429 }
0430 }
0431 }
0432
0433
0434
0435
0436
0437
0438
0439
0440
0441 static void gen_codes(
0442 ct_data *tree,
0443 int max_code,
0444 ush *bl_count
0445 )
0446 {
0447 ush next_code[MAX_BITS+1];
0448 ush code = 0;
0449 int bits;
0450 int n;
0451
0452
0453
0454
0455 for (bits = 1; bits <= MAX_BITS; bits++) {
0456 next_code[bits] = code = (code + bl_count[bits-1]) << 1;
0457 }
0458
0459
0460
0461 Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
0462 "inconsistent bit counts");
0463 Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
0464
0465 for (n = 0; n <= max_code; n++) {
0466 int len = tree[n].Len;
0467 if (len == 0) continue;
0468
0469 tree[n].Code = bitrev32((u32)(next_code[len]++)) >> (32 - len);
0470
0471 Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
0472 n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
0473 }
0474 }
0475
0476
0477
0478
0479
0480
0481
0482
0483
0484 static void build_tree(
0485 deflate_state *s,
0486 tree_desc *desc
0487 )
0488 {
0489 ct_data *tree = desc->dyn_tree;
0490 const ct_data *stree = desc->stat_desc->static_tree;
0491 int elems = desc->stat_desc->elems;
0492 int n, m;
0493 int max_code = -1;
0494 int node;
0495
0496
0497
0498
0499
0500 s->heap_len = 0, s->heap_max = HEAP_SIZE;
0501
0502 for (n = 0; n < elems; n++) {
0503 if (tree[n].Freq != 0) {
0504 s->heap[++(s->heap_len)] = max_code = n;
0505 s->depth[n] = 0;
0506 } else {
0507 tree[n].Len = 0;
0508 }
0509 }
0510
0511
0512
0513
0514
0515
0516 while (s->heap_len < 2) {
0517 node = s->heap[++(s->heap_len)] = (max_code < 2 ? ++max_code : 0);
0518 tree[node].Freq = 1;
0519 s->depth[node] = 0;
0520 s->opt_len--; if (stree) s->static_len -= stree[node].Len;
0521
0522 }
0523 desc->max_code = max_code;
0524
0525
0526
0527
0528 for (n = s->heap_len/2; n >= 1; n--) pqdownheap(s, tree, n);
0529
0530
0531
0532
0533 node = elems;
0534 do {
0535 pqremove(s, tree, n);
0536 m = s->heap[SMALLEST];
0537
0538 s->heap[--(s->heap_max)] = n;
0539 s->heap[--(s->heap_max)] = m;
0540
0541
0542 tree[node].Freq = tree[n].Freq + tree[m].Freq;
0543 s->depth[node] = (uch) (max(s->depth[n], s->depth[m]) + 1);
0544 tree[n].Dad = tree[m].Dad = (ush)node;
0545 #ifdef DUMP_BL_TREE
0546 if (tree == s->bl_tree) {
0547 fprintf(stderr,"\nnode %d(%d), sons %d(%d) %d(%d)",
0548 node, tree[node].Freq, n, tree[n].Freq, m, tree[m].Freq);
0549 }
0550 #endif
0551
0552 s->heap[SMALLEST] = node++;
0553 pqdownheap(s, tree, SMALLEST);
0554
0555 } while (s->heap_len >= 2);
0556
0557 s->heap[--(s->heap_max)] = s->heap[SMALLEST];
0558
0559
0560
0561
0562 gen_bitlen(s, (tree_desc *)desc);
0563
0564
0565 gen_codes ((ct_data *)tree, max_code, s->bl_count);
0566 }
0567
0568
0569
0570
0571
0572 static void scan_tree(
0573 deflate_state *s,
0574 ct_data *tree,
0575 int max_code
0576 )
0577 {
0578 int n;
0579 int prevlen = -1;
0580 int curlen;
0581 int nextlen = tree[0].Len;
0582 int count = 0;
0583 int max_count = 7;
0584 int min_count = 4;
0585
0586 if (nextlen == 0) max_count = 138, min_count = 3;
0587 tree[max_code+1].Len = (ush)0xffff;
0588
0589 for (n = 0; n <= max_code; n++) {
0590 curlen = nextlen; nextlen = tree[n+1].Len;
0591 if (++count < max_count && curlen == nextlen) {
0592 continue;
0593 } else if (count < min_count) {
0594 s->bl_tree[curlen].Freq += count;
0595 } else if (curlen != 0) {
0596 if (curlen != prevlen) s->bl_tree[curlen].Freq++;
0597 s->bl_tree[REP_3_6].Freq++;
0598 } else if (count <= 10) {
0599 s->bl_tree[REPZ_3_10].Freq++;
0600 } else {
0601 s->bl_tree[REPZ_11_138].Freq++;
0602 }
0603 count = 0; prevlen = curlen;
0604 if (nextlen == 0) {
0605 max_count = 138, min_count = 3;
0606 } else if (curlen == nextlen) {
0607 max_count = 6, min_count = 3;
0608 } else {
0609 max_count = 7, min_count = 4;
0610 }
0611 }
0612 }
0613
0614
0615
0616
0617
0618 static void send_tree(
0619 deflate_state *s,
0620 ct_data *tree,
0621 int max_code
0622 )
0623 {
0624 int n;
0625 int prevlen = -1;
0626 int curlen;
0627 int nextlen = tree[0].Len;
0628 int count = 0;
0629 int max_count = 7;
0630 int min_count = 4;
0631
0632
0633 if (nextlen == 0) max_count = 138, min_count = 3;
0634
0635 for (n = 0; n <= max_code; n++) {
0636 curlen = nextlen; nextlen = tree[n+1].Len;
0637 if (++count < max_count && curlen == nextlen) {
0638 continue;
0639 } else if (count < min_count) {
0640 do { send_code(s, curlen, s->bl_tree); } while (--count != 0);
0641
0642 } else if (curlen != 0) {
0643 if (curlen != prevlen) {
0644 send_code(s, curlen, s->bl_tree); count--;
0645 }
0646 Assert(count >= 3 && count <= 6, " 3_6?");
0647 send_code(s, REP_3_6, s->bl_tree); send_bits(s, count-3, 2);
0648
0649 } else if (count <= 10) {
0650 send_code(s, REPZ_3_10, s->bl_tree); send_bits(s, count-3, 3);
0651
0652 } else {
0653 send_code(s, REPZ_11_138, s->bl_tree); send_bits(s, count-11, 7);
0654 }
0655 count = 0; prevlen = curlen;
0656 if (nextlen == 0) {
0657 max_count = 138, min_count = 3;
0658 } else if (curlen == nextlen) {
0659 max_count = 6, min_count = 3;
0660 } else {
0661 max_count = 7, min_count = 4;
0662 }
0663 }
0664 }
0665
0666
0667
0668
0669
0670 static int build_bl_tree(
0671 deflate_state *s
0672 )
0673 {
0674 int max_blindex;
0675
0676
0677 scan_tree(s, (ct_data *)s->dyn_ltree, s->l_desc.max_code);
0678 scan_tree(s, (ct_data *)s->dyn_dtree, s->d_desc.max_code);
0679
0680
0681 build_tree(s, (tree_desc *)(&(s->bl_desc)));
0682
0683
0684
0685
0686
0687
0688
0689
0690 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) {
0691 if (s->bl_tree[bl_order[max_blindex]].Len != 0) break;
0692 }
0693
0694 s->opt_len += 3*(max_blindex+1) + 5+5+4;
0695 Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
0696 s->opt_len, s->static_len));
0697
0698 return max_blindex;
0699 }
0700
0701
0702
0703
0704
0705
0706 static void send_all_trees(
0707 deflate_state *s,
0708 int lcodes,
0709 int dcodes,
0710 int blcodes
0711 )
0712 {
0713 int rank;
0714
0715 Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
0716 Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
0717 "too many codes");
0718 Tracev((stderr, "\nbl counts: "));
0719 send_bits(s, lcodes-257, 5);
0720 send_bits(s, dcodes-1, 5);
0721 send_bits(s, blcodes-4, 4);
0722 for (rank = 0; rank < blcodes; rank++) {
0723 Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
0724 send_bits(s, s->bl_tree[bl_order[rank]].Len, 3);
0725 }
0726 Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
0727
0728 send_tree(s, (ct_data *)s->dyn_ltree, lcodes-1);
0729 Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
0730
0731 send_tree(s, (ct_data *)s->dyn_dtree, dcodes-1);
0732 Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
0733 }
0734
0735
0736
0737
0738 void zlib_tr_stored_block(
0739 deflate_state *s,
0740 char *buf,
0741 ulg stored_len,
0742 int eof
0743 )
0744 {
0745 send_bits(s, (STORED_BLOCK<<1)+eof, 3);
0746 s->compressed_len = (s->compressed_len + 3 + 7) & (ulg)~7L;
0747 s->compressed_len += (stored_len + 4) << 3;
0748
0749 copy_block(s, buf, (unsigned)stored_len, 1);
0750 }
0751
0752
0753
0754 void zlib_tr_stored_type_only(
0755 deflate_state *s
0756 )
0757 {
0758 send_bits(s, (STORED_BLOCK << 1), 3);
0759 bi_windup(s);
0760 s->compressed_len = (s->compressed_len + 3) & ~7L;
0761 }
0762
0763
0764
0765
0766
0767
0768
0769
0770
0771
0772
0773
0774
0775 void zlib_tr_align(
0776 deflate_state *s
0777 )
0778 {
0779 send_bits(s, STATIC_TREES<<1, 3);
0780 send_code(s, END_BLOCK, static_ltree);
0781 s->compressed_len += 10L;
0782 bi_flush(s);
0783
0784
0785
0786
0787
0788 if (1 + s->last_eob_len + 10 - s->bi_valid < 9) {
0789 send_bits(s, STATIC_TREES<<1, 3);
0790 send_code(s, END_BLOCK, static_ltree);
0791 s->compressed_len += 10L;
0792 bi_flush(s);
0793 }
0794 s->last_eob_len = 7;
0795 }
0796
0797
0798
0799
0800
0801
0802 ulg zlib_tr_flush_block(
0803 deflate_state *s,
0804 char *buf,
0805 ulg stored_len,
0806 int eof
0807 )
0808 {
0809 ulg opt_lenb, static_lenb;
0810 int max_blindex = 0;
0811
0812
0813 if (s->level > 0) {
0814
0815
0816 if (s->data_type == Z_UNKNOWN) set_data_type(s);
0817
0818
0819 build_tree(s, (tree_desc *)(&(s->l_desc)));
0820 Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
0821 s->static_len));
0822
0823 build_tree(s, (tree_desc *)(&(s->d_desc)));
0824 Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
0825 s->static_len));
0826
0827
0828
0829
0830
0831
0832
0833 max_blindex = build_bl_tree(s);
0834
0835
0836 opt_lenb = (s->opt_len+3+7)>>3;
0837 static_lenb = (s->static_len+3+7)>>3;
0838
0839 Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
0840 opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
0841 s->last_lit));
0842
0843 if (static_lenb <= opt_lenb) opt_lenb = static_lenb;
0844
0845 } else {
0846 Assert(buf != (char*)0, "lost buf");
0847 opt_lenb = static_lenb = stored_len + 5;
0848 }
0849
0850
0851
0852
0853
0854 #ifdef STORED_FILE_OK
0855 # ifdef FORCE_STORED_FILE
0856 if (eof && s->compressed_len == 0L) {
0857 # else
0858 if (stored_len <= opt_lenb && eof && s->compressed_len==0L && seekable()) {
0859 # endif
0860
0861 if (buf == (char*)0) error ("block vanished");
0862
0863 copy_block(s, buf, (unsigned)stored_len, 0);
0864 s->compressed_len = stored_len << 3;
0865 s->method = STORED;
0866 } else
0867 #endif
0868
0869 #ifdef FORCE_STORED
0870 if (buf != (char*)0) {
0871 #else
0872 if (stored_len+4 <= opt_lenb && buf != (char*)0) {
0873
0874 #endif
0875
0876
0877
0878
0879
0880
0881 zlib_tr_stored_block(s, buf, stored_len, eof);
0882
0883 #ifdef FORCE_STATIC
0884 } else if (static_lenb >= 0) {
0885 #else
0886 } else if (static_lenb == opt_lenb) {
0887 #endif
0888 send_bits(s, (STATIC_TREES<<1)+eof, 3);
0889 compress_block(s, (ct_data *)static_ltree, (ct_data *)static_dtree);
0890 s->compressed_len += 3 + s->static_len;
0891 } else {
0892 send_bits(s, (DYN_TREES<<1)+eof, 3);
0893 send_all_trees(s, s->l_desc.max_code+1, s->d_desc.max_code+1,
0894 max_blindex+1);
0895 compress_block(s, (ct_data *)s->dyn_ltree, (ct_data *)s->dyn_dtree);
0896 s->compressed_len += 3 + s->opt_len;
0897 }
0898 Assert (s->compressed_len == s->bits_sent, "bad compressed size");
0899 init_block(s);
0900
0901 if (eof) {
0902 bi_windup(s);
0903 s->compressed_len += 7;
0904 }
0905 Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
0906 s->compressed_len-7*eof));
0907
0908 return s->compressed_len >> 3;
0909 }
0910
0911
0912
0913
0914
0915 int zlib_tr_tally(
0916 deflate_state *s,
0917 unsigned dist,
0918 unsigned lc
0919 )
0920 {
0921 s->d_buf[s->last_lit] = (ush)dist;
0922 s->l_buf[s->last_lit++] = (uch)lc;
0923 if (dist == 0) {
0924
0925 s->dyn_ltree[lc].Freq++;
0926 } else {
0927 s->matches++;
0928
0929 dist--;
0930 Assert((ush)dist < (ush)MAX_DIST(s) &&
0931 (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
0932 (ush)d_code(dist) < (ush)D_CODES, "zlib_tr_tally: bad match");
0933
0934 s->dyn_ltree[length_code[lc]+LITERALS+1].Freq++;
0935 s->dyn_dtree[d_code(dist)].Freq++;
0936 }
0937
0938
0939 if ((s->last_lit & 0xfff) == 0 && s->level > 2) {
0940
0941 ulg out_length = (ulg)s->last_lit*8L;
0942 ulg in_length = (ulg)((long)s->strstart - s->block_start);
0943 int dcode;
0944 for (dcode = 0; dcode < D_CODES; dcode++) {
0945 out_length += (ulg)s->dyn_dtree[dcode].Freq *
0946 (5L+extra_dbits[dcode]);
0947 }
0948 out_length >>= 3;
0949 Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
0950 s->last_lit, in_length, out_length,
0951 100L - out_length*100L/in_length));
0952 if (s->matches < s->last_lit/2 && out_length < in_length/2) return 1;
0953 }
0954 return (s->last_lit == s->lit_bufsize-1);
0955
0956
0957
0958
0959 }
0960
0961
0962
0963
0964 static void compress_block(
0965 deflate_state *s,
0966 ct_data *ltree,
0967 ct_data *dtree
0968 )
0969 {
0970 unsigned dist;
0971 int lc;
0972 unsigned lx = 0;
0973 unsigned code;
0974 int extra;
0975
0976 if (s->last_lit != 0) do {
0977 dist = s->d_buf[lx];
0978 lc = s->l_buf[lx++];
0979 if (dist == 0) {
0980 send_code(s, lc, ltree);
0981 Tracecv(isgraph(lc), (stderr," '%c' ", lc));
0982 } else {
0983
0984 code = length_code[lc];
0985 send_code(s, code+LITERALS+1, ltree);
0986 extra = extra_lbits[code];
0987 if (extra != 0) {
0988 lc -= base_length[code];
0989 send_bits(s, lc, extra);
0990 }
0991 dist--;
0992 code = d_code(dist);
0993 Assert (code < D_CODES, "bad d_code");
0994
0995 send_code(s, code, dtree);
0996 extra = extra_dbits[code];
0997 if (extra != 0) {
0998 dist -= base_dist[code];
0999 send_bits(s, dist, extra);
1000 }
1001 }
1002
1003
1004 Assert(s->pending < s->lit_bufsize + 2*lx, "pendingBuf overflow");
1005
1006 } while (lx < s->last_lit);
1007
1008 send_code(s, END_BLOCK, ltree);
1009 s->last_eob_len = ltree[END_BLOCK].Len;
1010 }
1011
1012
1013
1014
1015
1016
1017
1018 static void set_data_type(
1019 deflate_state *s
1020 )
1021 {
1022 int n = 0;
1023 unsigned ascii_freq = 0;
1024 unsigned bin_freq = 0;
1025 while (n < 7) bin_freq += s->dyn_ltree[n++].Freq;
1026 while (n < 128) ascii_freq += s->dyn_ltree[n++].Freq;
1027 while (n < LITERALS) bin_freq += s->dyn_ltree[n++].Freq;
1028 s->data_type = (Byte)(bin_freq > (ascii_freq >> 2) ? Z_BINARY : Z_ASCII);
1029 }
1030
1031
1032
1033
1034
1035 static void copy_block(
1036 deflate_state *s,
1037 char *buf,
1038 unsigned len,
1039 int header
1040 )
1041 {
1042 bi_windup(s);
1043 s->last_eob_len = 8;
1044
1045 if (header) {
1046 put_short(s, (ush)len);
1047 put_short(s, (ush)~len);
1048 #ifdef DEBUG_ZLIB
1049 s->bits_sent += 2*16;
1050 #endif
1051 }
1052 #ifdef DEBUG_ZLIB
1053 s->bits_sent += (ulg)len<<3;
1054 #endif
1055
1056 memcpy(&s->pending_buf[s->pending], buf, len);
1057 s->pending += len;
1058 }
1059