Debian Codegraph @

polyfills/zlib-lib/trees.js

raw
1 'use strict';
2
3 import {arraySet} from './utils';
4
5 /* Public constants ==========================================================*/
6 /* ===========================================================================*/
7
8
9 //var Z_FILTERED = 1;
10 //var Z_HUFFMAN_ONLY = 2;
11 //var Z_RLE = 3;
12 var Z_FIXED = 4;
13 //var Z_DEFAULT_STRATEGY = 0;
14
15 /* Possible values of the data_type field (though see inflate()) */
16 var Z_BINARY = 0;
17 var Z_TEXT = 1;
18 //var Z_ASCII = 1; // = Z_TEXT
19 var Z_UNKNOWN = 2;
20
21 /*============================================================================*/
22
23
24 function zero(buf) {
25 var len = buf.length;
26 while (--len >= 0) {
27 buf[len] = 0;
28 }
29 }
30
31 // From zutil.h
32
33 var STORED_BLOCK = 0;
34 var STATIC_TREES = 1;
35 var DYN_TREES = 2;
36 /* The three kinds of block type */
37
38 var MIN_MATCH = 3;
39 var MAX_MATCH = 258;
40 /* The minimum and maximum match lengths */
41
42 // From deflate.h
43 /* ===========================================================================
44 * Internal compression state.
45 */
46
47 var LENGTH_CODES = 29;
48 /* number of length codes, not counting the special END_BLOCK code */
49
50 var LITERALS = 256;
51 /* number of literal bytes 0..255 */
52
53 var L_CODES = LITERALS + 1 + LENGTH_CODES;
54 /* number of Literal or Length codes, including the END_BLOCK code */
55
56 var D_CODES = 30;
57 /* number of distance codes */
58
59 var BL_CODES = 19;
60 /* number of codes used to transfer the bit lengths */
61
62 var HEAP_SIZE = 2 * L_CODES + 1;
63 /* maximum heap size */
64
65 var MAX_BITS = 15;
66 /* All codes must not exceed MAX_BITS bits */
67
68 var Buf_size = 16;
69 /* size of bit buffer in bi_buf */
70
71
72 /* ===========================================================================
73 * Constants
74 */
75
76 var MAX_BL_BITS = 7;
77 /* Bit length codes must not exceed MAX_BL_BITS bits */
78
79 var END_BLOCK = 256;
80 /* end of block literal code */
81
82 var REP_3_6 = 16;
83 /* repeat previous bit length 3-6 times (2 bits of repeat count) */
84
85 var REPZ_3_10 = 17;
86 /* repeat a zero length 3-10 times (3 bits of repeat count) */
87
88 var REPZ_11_138 = 18;
89 /* repeat a zero length 11-138 times (7 bits of repeat count) */
90
91 /* eslint-disable comma-spacing,array-bracket-spacing */
92 var extra_lbits = /* extra bits for each length code */ [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];
93
94 var extra_dbits = /* extra bits for each distance code */ [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];
95
96 var extra_blbits = /* extra bits for each bit length code */ [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 3, 7];
97
98 var bl_order = [16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15];
99 /* eslint-enable comma-spacing,array-bracket-spacing */
100
101 /* The lengths of the bit length codes are sent in order of decreasing
102 * probability, to avoid transmitting the lengths for unused bit length codes.
103 */
104
105 /* ===========================================================================
106 * Local data. These are initialized only once.
107 */
108
109 // We pre-fill arrays with 0 to avoid uninitialized gaps
110
111 var DIST_CODE_LEN = 512; /* see definition of array dist_code below */
112
113 // !!!! Use flat array insdead of structure, Freq = i*2, Len = i*2+1
114 var static_ltree = new Array((L_CODES + 2) * 2);
115 zero(static_ltree);
116 /* The static literal tree. Since the bit lengths are imposed, there is no
117 * need for the L_CODES extra codes used during heap construction. However
118 * The codes 286 and 287 are needed to build a canonical tree (see _tr_init
119 * below).
120 */
121
122 var static_dtree = new Array(D_CODES * 2);
123 zero(static_dtree);
124 /* The static distance tree. (Actually a trivial tree since all codes use
125 * 5 bits.)
126 */
127
128 var _dist_code = new Array(DIST_CODE_LEN);
129 zero(_dist_code);
130 /* Distance codes. The first 256 values correspond to the distances
131 * 3 .. 258, the last 256 values correspond to the top 8 bits of
132 * the 15 bit distances.
133 */
134
135 var _length_code = new Array(MAX_MATCH - MIN_MATCH + 1);
136 zero(_length_code);
137 /* length code for each normalized match length (0 == MIN_MATCH) */
138
139 var base_length = new Array(LENGTH_CODES);
140 zero(base_length);
141 /* First normalized length for each code (0 = MIN_MATCH) */
142
143 var base_dist = new Array(D_CODES);
144 zero(base_dist);
145 /* First normalized distance for each code (0 = distance of 1) */
146
147
148 function StaticTreeDesc(static_tree, extra_bits, extra_base, elems, max_length) {
149
150 this.static_tree = static_tree; /* static tree or NULL */
151 this.extra_bits = extra_bits; /* extra bits for each code or NULL */
152 this.extra_base = extra_base; /* base index for extra_bits */
153 this.elems = elems; /* max number of elements in the tree */
154 this.max_length = max_length; /* max bit length for the codes */
155
156 // show if `static_tree` has data or dummy - needed for monomorphic objects
157 this.has_stree = static_tree && static_tree.length;
158 }
159
160
161 var static_l_desc;
162 var static_d_desc;
163 var static_bl_desc;
164
165
166 function TreeDesc(dyn_tree, stat_desc) {
167 this.dyn_tree = dyn_tree; /* the dynamic tree */
168 this.max_code = 0; /* largest code with non zero frequency */
169 this.stat_desc = stat_desc; /* the corresponding static tree */
170 }
171
172
173
174 function d_code(dist) {
175 return dist < 256 ? _dist_code[dist] : _dist_code[256 + (dist >>> 7)];
176 }
177
178
179 /* ===========================================================================
180 * Output a short LSB first on the stream.
181 * IN assertion: there is enough room in pendingBuf.
182 */
183 function put_short(s, w) {
184 // put_byte(s, (uch)((w) & 0xff));
185 // put_byte(s, (uch)((ush)(w) >> 8));
186 s.pending_buf[s.pending++] = (w) & 0xff;
187 s.pending_buf[s.pending++] = (w >>> 8) & 0xff;
188 }
189
190
191 /* ===========================================================================
192 * Send a value on a given number of bits.
193 * IN assertion: length <= 16 and value fits in length bits.
194 */
195 function send_bits(s, value, length) {
196 if (s.bi_valid > (Buf_size - length)) {
197 s.bi_buf |= (value << s.bi_valid) & 0xffff;
198 put_short(s, s.bi_buf);
199 s.bi_buf = value >> (Buf_size - s.bi_valid);
200 s.bi_valid += length - Buf_size;
201 } else {
202 s.bi_buf |= (value << s.bi_valid) & 0xffff;
203 s.bi_valid += length;
204 }
205 }
206
207
208 function send_code(s, c, tree) {
209 send_bits(s, tree[c * 2] /*.Code*/ , tree[c * 2 + 1] /*.Len*/ );
210 }
211
212
213 /* ===========================================================================
214 * Reverse the first len bits of a code, using straightforward code (a faster
215 * method would use a table)
216 * IN assertion: 1 <= len <= 15
217 */
218 function bi_reverse(code, len) {
219 var res = 0;
220 do {
221 res |= code & 1;
222 code >>>= 1;
223 res <<= 1;
224 } while (--len > 0);
225 return res >>> 1;
226 }
227
228
229 /* ===========================================================================
230 * Flush the bit buffer, keeping at most 7 bits in it.
231 */
232 function bi_flush(s) {
233 if (s.bi_valid === 16) {
234 put_short(s, s.bi_buf);
235 s.bi_buf = 0;
236 s.bi_valid = 0;
237
238 } else if (s.bi_valid >= 8) {
239 s.pending_buf[s.pending++] = s.bi_buf & 0xff;
240 s.bi_buf >>= 8;
241 s.bi_valid -= 8;
242 }
243 }
244
245
246 /* ===========================================================================
247 * Compute the optimal bit lengths for a tree and update the total bit length
248 * for the current block.
249 * IN assertion: the fields freq and dad are set, heap[heap_max] and
250 * above are the tree nodes sorted by increasing frequency.
251 * OUT assertions: the field len is set to the optimal bit length, the
252 * array bl_count contains the frequencies for each bit length.
253 * The length opt_len is updated; static_len is also updated if stree is
254 * not null.
255 */
256 function gen_bitlen(s, desc) {
257 // deflate_state *s;
258 // tree_desc *desc; /* the tree descriptor */
259 var tree = desc.dyn_tree;
260 var max_code = desc.max_code;
261 var stree = desc.stat_desc.static_tree;
262 var has_stree = desc.stat_desc.has_stree;
263 var extra = desc.stat_desc.extra_bits;
264 var base = desc.stat_desc.extra_base;
265 var max_length = desc.stat_desc.max_length;
266 var h; /* heap index */
267 var n, m; /* iterate over the tree elements */
268 var bits; /* bit length */
269 var xbits; /* extra bits */
270 var f; /* frequency */
271 var overflow = 0; /* number of elements with bit length too large */
272
273 for (bits = 0; bits <= MAX_BITS; bits++) {
274 s.bl_count[bits] = 0;
275 }
276
277 /* In a first pass, compute the optimal bit lengths (which may
278 * overflow in the case of the bit length tree).
279 */
280 tree[s.heap[s.heap_max] * 2 + 1] /*.Len*/ = 0; /* root of the heap */
281
282 for (h = s.heap_max + 1; h < HEAP_SIZE; h++) {
283 n = s.heap[h];
284 bits = tree[tree[n * 2 + 1] /*.Dad*/ * 2 + 1] /*.Len*/ + 1;
285 if (bits > max_length) {
286 bits = max_length;
287 overflow++;
288 }
289 tree[n * 2 + 1] /*.Len*/ = bits;
290 /* We overwrite tree[n].Dad which is no longer needed */
291
292 if (n > max_code) {
293 continue;
294 } /* not a leaf node */
295
296 s.bl_count[bits]++;
297 xbits = 0;
298 if (n >= base) {
299 xbits = extra[n - base];
300 }
301 f = tree[n * 2] /*.Freq*/ ;
302 s.opt_len += f * (bits + xbits);
303 if (has_stree) {
304 s.static_len += f * (stree[n * 2 + 1] /*.Len*/ + xbits);
305 }
306 }
307 if (overflow === 0) {
308 return;
309 }
310
311 // Trace((stderr,"\nbit length overflow\n"));
312 /* This happens for example on obj2 and pic of the Calgary corpus */
313
314 /* Find the first bit length which could increase: */
315 do {
316 bits = max_length - 1;
317 while (s.bl_count[bits] === 0) {
318 bits--;
319 }
320 s.bl_count[bits]--; /* move one leaf down the tree */
321 s.bl_count[bits + 1] += 2; /* move one overflow item as its brother */
322 s.bl_count[max_length]--;
323 /* The brother of the overflow item also moves one step up,
324 * but this does not affect bl_count[max_length]
325 */
326 overflow -= 2;
327 } while (overflow > 0);
328
329 /* Now recompute all bit lengths, scanning in increasing frequency.
330 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all
331 * lengths instead of fixing only the wrong ones. This idea is taken
332 * from 'ar' written by Haruhiko Okumura.)
333 */
334 for (bits = max_length; bits !== 0; bits--) {
335 n = s.bl_count[bits];
336 while (n !== 0) {
337 m = s.heap[--h];
338 if (m > max_code) {
339 continue;
340 }
341 if (tree[m * 2 + 1] /*.Len*/ !== bits) {
342 // Trace((stderr,"code %d bits %d->%d\n", m, tree[m].Len, bits));
343 s.opt_len += (bits - tree[m * 2 + 1] /*.Len*/ ) * tree[m * 2] /*.Freq*/ ;
344 tree[m * 2 + 1] /*.Len*/ = bits;
345 }
346 n--;
347 }
348 }
349 }
350
351
352 /* ===========================================================================
353 * Generate the codes for a given tree and bit counts (which need not be
354 * optimal).
355 * IN assertion: the array bl_count contains the bit length statistics for
356 * the given tree and the field len is set for all tree elements.
357 * OUT assertion: the field code is set for all tree elements of non
358 * zero code length.
359 */
360 function gen_codes(tree, max_code, bl_count) {
361 // ct_data *tree; /* the tree to decorate */
362 // int max_code; /* largest code with non zero frequency */
363 // ushf *bl_count; /* number of codes at each bit length */
364
365 var next_code = new Array(MAX_BITS + 1); /* next code value for each bit length */
366 var code = 0; /* running code value */
367 var bits; /* bit index */
368 var n; /* code index */
369
370 /* The distribution counts are first used to generate the code values
371 * without bit reversal.
372 */
373 for (bits = 1; bits <= MAX_BITS; bits++) {
374 next_code[bits] = code = (code + bl_count[bits - 1]) << 1;
375 }
376 /* Check that the bit counts in bl_count are consistent. The last code
377 * must be all ones.
378 */
379 //Assert (code + bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1,
380 // "inconsistent bit counts");
381 //Tracev((stderr,"\ngen_codes: max_code %d ", max_code));
382
383 for (n = 0; n <= max_code; n++) {
384 var len = tree[n * 2 + 1] /*.Len*/ ;
385 if (len === 0) {
386 continue;
387 }
388 /* Now reverse the bits */
389 tree[n * 2] /*.Code*/ = bi_reverse(next_code[len]++, len);
390
391 //Tracecv(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ",
392 // n, (isgraph(n) ? n : ' '), len, tree[n].Code, next_code[len]-1));
393 }
394 }
395
396
397 /* ===========================================================================
398 * Initialize the various 'constant' tables.
399 */
400 function tr_static_init() {
401 var n; /* iterates over tree elements */
402 var bits; /* bit counter */
403 var length; /* length value */
404 var code; /* code value */
405 var dist; /* distance index */
406 var bl_count = new Array(MAX_BITS + 1);
407 /* number of codes at each bit length for an optimal tree */
408
409 // do check in _tr_init()
410 //if (static_init_done) return;
411
412 /* For some embedded targets, global variables are not initialized: */
413 /*#ifdef NO_INIT_GLOBAL_POINTERS
414 static_l_desc.static_tree = static_ltree;
415 static_l_desc.extra_bits = extra_lbits;
416 static_d_desc.static_tree = static_dtree;
417 static_d_desc.extra_bits = extra_dbits;
418 static_bl_desc.extra_bits = extra_blbits;
419 #endif*/
420
421 /* Initialize the mapping length (0..255) -> length code (0..28) */
422 length = 0;
423 for (code = 0; code < LENGTH_CODES - 1; code++) {
424 base_length[code] = length;
425 for (n = 0; n < (1 << extra_lbits[code]); n++) {
426 _length_code[length++] = code;
427 }
428 }
429 //Assert (length == 256, "tr_static_init: length != 256");
430 /* Note that the length 255 (match length 258) can be represented
431 * in two different ways: code 284 + 5 bits or code 285, so we
432 * overwrite length_code[255] to use the best encoding:
433 */
434 _length_code[length - 1] = code;
435
436 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */
437 dist = 0;
438 for (code = 0; code < 16; code++) {
439 base_dist[code] = dist;
440 for (n = 0; n < (1 << extra_dbits[code]); n++) {
441 _dist_code[dist++] = code;
442 }
443 }
444 //Assert (dist == 256, "tr_static_init: dist != 256");
445 dist >>= 7; /* from now on, all distances are divided by 128 */
446 for (; code < D_CODES; code++) {
447 base_dist[code] = dist << 7;
448 for (n = 0; n < (1 << (extra_dbits[code] - 7)); n++) {
449 _dist_code[256 + dist++] = code;
450 }
451 }
452 //Assert (dist == 256, "tr_static_init: 256+dist != 512");
453
454 /* Construct the codes of the static literal tree */
455 for (bits = 0; bits <= MAX_BITS; bits++) {
456 bl_count[bits] = 0;
457 }
458
459 n = 0;
460 while (n <= 143) {
461 static_ltree[n * 2 + 1] /*.Len*/ = 8;
462 n++;
463 bl_count[8]++;
464 }
465 while (n <= 255) {
466 static_ltree[n * 2 + 1] /*.Len*/ = 9;
467 n++;
468 bl_count[9]++;
469 }
470 while (n <= 279) {
471 static_ltree[n * 2 + 1] /*.Len*/ = 7;
472 n++;
473 bl_count[7]++;
474 }
475 while (n <= 287) {
476 static_ltree[n * 2 + 1] /*.Len*/ = 8;
477 n++;
478 bl_count[8]++;
479 }
480 /* Codes 286 and 287 do not exist, but we must include them in the
481 * tree construction to get a canonical Huffman tree (longest code
482 * all ones)
483 */
484 gen_codes(static_ltree, L_CODES + 1, bl_count);
485
486 /* The static distance tree is trivial: */
487 for (n = 0; n < D_CODES; n++) {
488 static_dtree[n * 2 + 1] /*.Len*/ = 5;
489 static_dtree[n * 2] /*.Code*/ = bi_reverse(n, 5);
490 }
491
492 // Now data ready and we can init static trees
493 static_l_desc = new StaticTreeDesc(static_ltree, extra_lbits, LITERALS + 1, L_CODES, MAX_BITS);
494 static_d_desc = new StaticTreeDesc(static_dtree, extra_dbits, 0, D_CODES, MAX_BITS);
495 static_bl_desc = new StaticTreeDesc(new Array(0), extra_blbits, 0, BL_CODES, MAX_BL_BITS);
496
497 //static_init_done = true;
498 }
499
500
501 /* ===========================================================================
502 * Initialize a new block.
503 */
504 function init_block(s) {
505 var n; /* iterates over tree elements */
506
507 /* Initialize the trees. */
508 for (n = 0; n < L_CODES; n++) {
509 s.dyn_ltree[n * 2] /*.Freq*/ = 0;
510 }
511 for (n = 0; n < D_CODES; n++) {
512 s.dyn_dtree[n * 2] /*.Freq*/ = 0;
513 }
514 for (n = 0; n < BL_CODES; n++) {
515 s.bl_tree[n * 2] /*.Freq*/ = 0;
516 }
517
518 s.dyn_ltree[END_BLOCK * 2] /*.Freq*/ = 1;
519 s.opt_len = s.static_len = 0;
520 s.last_lit = s.matches = 0;
521 }
522
523
524 /* ===========================================================================
525 * Flush the bit buffer and align the output on a byte boundary
526 */
527 function bi_windup(s) {
528 if (s.bi_valid > 8) {
529 put_short(s, s.bi_buf);
530 } else if (s.bi_valid > 0) {
531 //put_byte(s, (Byte)s->bi_buf);
532 s.pending_buf[s.pending++] = s.bi_buf;
533 }
534 s.bi_buf = 0;
535 s.bi_valid = 0;
536 }
537
538 /* ===========================================================================
539 * Copy a stored block, storing first the length and its
540 * one's complement if requested.
541 */
542 function copy_block(s, buf, len, header) {
543 //DeflateState *s;
544 //charf *buf; /* the input data */
545 //unsigned len; /* its length */
546 //int header; /* true if block header must be written */
547
548 bi_windup(s); /* align on byte boundary */
549
550 if (header) {
551 put_short(s, len);
552 put_short(s, ~len);
553 }
554 // while (len--) {
555 // put_byte(s, *buf++);
556 // }
557 arraySet(s.pending_buf, s.window, buf, len, s.pending);
558 s.pending += len;
559 }
560
561 /* ===========================================================================
562 * Compares to subtrees, using the tree depth as tie breaker when
563 * the subtrees have equal frequency. This minimizes the worst case length.
564 */
565 function smaller(tree, n, m, depth) {
566 var _n2 = n * 2;
567 var _m2 = m * 2;
568 return (tree[_n2] /*.Freq*/ < tree[_m2] /*.Freq*/ ||
569 (tree[_n2] /*.Freq*/ === tree[_m2] /*.Freq*/ && depth[n] <= depth[m]));
570 }
571
572 /* ===========================================================================
573 * Restore the heap property by moving down the tree starting at node k,
574 * exchanging a node with the smallest of its two sons if necessary, stopping
575 * when the heap property is re-established (each father smaller than its
576 * two sons).
577 */
578 function pqdownheap(s, tree, k)
579 // deflate_state *s;
580 // ct_data *tree; /* the tree to restore */
581 // int k; /* node to move down */
582 {
583 var v = s.heap[k];
584 var j = k << 1; /* left son of k */
585 while (j <= s.heap_len) {
586 /* Set j to the smallest of the two sons: */
587 if (j < s.heap_len &&
588 smaller(tree, s.heap[j + 1], s.heap[j], s.depth)) {
589 j++;
590 }
591 /* Exit if v is smaller than both sons */
592 if (smaller(tree, v, s.heap[j], s.depth)) {
593 break;
594 }
595
596 /* Exchange v with the smallest son */
597 s.heap[k] = s.heap[j];
598 k = j;
599
600 /* And continue down the tree, setting j to the left son of k */
601 j <<= 1;
602 }
603 s.heap[k] = v;
604 }
605
606
607 // inlined manually
608 // var SMALLEST = 1;
609
610 /* ===========================================================================
611 * Send the block data compressed using the given Huffman trees
612 */
613 function compress_block(s, ltree, dtree)
614 // deflate_state *s;
615 // const ct_data *ltree; /* literal tree */
616 // const ct_data *dtree; /* distance tree */
617 {
618 var dist; /* distance of matched string */
619 var lc; /* match length or unmatched char (if dist == 0) */
620 var lx = 0; /* running index in l_buf */
621 var code; /* the code to send */
622 var extra; /* number of extra bits to send */
623
624 if (s.last_lit !== 0) {
625 do {
626 dist = (s.pending_buf[s.d_buf + lx * 2] << 8) | (s.pending_buf[s.d_buf + lx * 2 + 1]);
627 lc = s.pending_buf[s.l_buf + lx];
628 lx++;
629
630 if (dist === 0) {
631 send_code(s, lc, ltree); /* send a literal byte */
632 //Tracecv(isgraph(lc), (stderr," '%c' ", lc));
633 } else {
634 /* Here, lc is the match length - MIN_MATCH */
635 code = _length_code[lc];
636 send_code(s, code + LITERALS + 1, ltree); /* send the length code */
637 extra = extra_lbits[code];
638 if (extra !== 0) {
639 lc -= base_length[code];
640 send_bits(s, lc, extra); /* send the extra length bits */
641 }
642 dist--; /* dist is now the match distance - 1 */
643 code = d_code(dist);
644 //Assert (code < D_CODES, "bad d_code");
645
646 send_code(s, code, dtree); /* send the distance code */
647 extra = extra_dbits[code];
648 if (extra !== 0) {
649 dist -= base_dist[code];
650 send_bits(s, dist, extra); /* send the extra distance bits */
651 }
652 } /* literal or match pair ? */
653
654 /* Check that the overlay between pending_buf and d_buf+l_buf is ok: */
655 //Assert((uInt)(s->pending) < s->lit_bufsize + 2*lx,
656 // "pendingBuf overflow");
657
658 } while (lx < s.last_lit);
659 }
660
661 send_code(s, END_BLOCK, ltree);
662 }
663
664
665 /* ===========================================================================
666 * Construct one Huffman tree and assigns the code bit strings and lengths.
667 * Update the total bit length for the current block.
668 * IN assertion: the field freq is set for all tree elements.
669 * OUT assertions: the fields len and code are set to the optimal bit length
670 * and corresponding code. The length opt_len is updated; static_len is
671 * also updated if stree is not null. The field max_code is set.
672 */
673 function build_tree(s, desc)
674 // deflate_state *s;
675 // tree_desc *desc; /* the tree descriptor */
676 {
677 var tree = desc.dyn_tree;
678 var stree = desc.stat_desc.static_tree;
679 var has_stree = desc.stat_desc.has_stree;
680 var elems = desc.stat_desc.elems;
681 var n, m; /* iterate over heap elements */
682 var max_code = -1; /* largest code with non zero frequency */
683 var node; /* new node being created */
684
685 /* Construct the initial heap, with least frequent element in
686 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1].
687 * heap[0] is not used.
688 */
689 s.heap_len = 0;
690 s.heap_max = HEAP_SIZE;
691
692 for (n = 0; n < elems; n++) {
693 if (tree[n * 2] /*.Freq*/ !== 0) {
694 s.heap[++s.heap_len] = max_code = n;
695 s.depth[n] = 0;
696
697 } else {
698 tree[n * 2 + 1] /*.Len*/ = 0;
699 }
700 }
701
702 /* The pkzip format requires that at least one distance code exists,
703 * and that at least one bit should be sent even if there is only one
704 * possible code. So to avoid special checks later on we force at least
705 * two codes of non zero frequency.
706 */
707 while (s.heap_len < 2) {
708 node = s.heap[++s.heap_len] = (max_code < 2 ? ++max_code : 0);
709 tree[node * 2] /*.Freq*/ = 1;
710 s.depth[node] = 0;
711 s.opt_len--;
712
713 if (has_stree) {
714 s.static_len -= stree[node * 2 + 1] /*.Len*/ ;
715 }
716 /* node is 0 or 1 so it does not have extra bits */
717 }
718 desc.max_code = max_code;
719
720 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree,
721 * establish sub-heaps of increasing lengths:
722 */
723 for (n = (s.heap_len >> 1 /*int /2*/ ); n >= 1; n--) {
724 pqdownheap(s, tree, n);
725 }
726
727 /* Construct the Huffman tree by repeatedly combining the least two
728 * frequent nodes.
729 */
730 node = elems; /* next internal node of the tree */
731 do {
732 //pqremove(s, tree, n); /* n = node of least frequency */
733 /*** pqremove ***/
734 n = s.heap[1 /*SMALLEST*/ ];
735 s.heap[1 /*SMALLEST*/ ] = s.heap[s.heap_len--];
736 pqdownheap(s, tree, 1 /*SMALLEST*/ );
737 /***/
738
739 m = s.heap[1 /*SMALLEST*/ ]; /* m = node of next least frequency */
740
741 s.heap[--s.heap_max] = n; /* keep the nodes sorted by frequency */
742 s.heap[--s.heap_max] = m;
743
744 /* Create a new node father of n and m */
745 tree[node * 2] /*.Freq*/ = tree[n * 2] /*.Freq*/ + tree[m * 2] /*.Freq*/ ;
746 s.depth[node] = (s.depth[n] >= s.depth[m] ? s.depth[n] : s.depth[m]) + 1;
747 tree[n * 2 + 1] /*.Dad*/ = tree[m * 2 + 1] /*.Dad*/ = node;
748
749 /* and insert the new node in the heap */
750 s.heap[1 /*SMALLEST*/ ] = node++;
751 pqdownheap(s, tree, 1 /*SMALLEST*/ );
752
753 } while (s.heap_len >= 2);
754
755 s.heap[--s.heap_max] = s.heap[1 /*SMALLEST*/ ];
756
757 /* At this point, the fields freq and dad are set. We can now
758 * generate the bit lengths.
759 */
760 gen_bitlen(s, desc);
761
762 /* The field len is now set, we can generate the bit codes */
763 gen_codes(tree, max_code, s.bl_count);
764 }
765
766
767 /* ===========================================================================
768 * Scan a literal or distance tree to determine the frequencies of the codes
769 * in the bit length tree.
770 */
771 function scan_tree(s, tree, max_code)
772 // deflate_state *s;
773 // ct_data *tree; /* the tree to be scanned */
774 // int max_code; /* and its largest code of non zero frequency */
775 {
776 var n; /* iterates over all tree elements */
777 var prevlen = -1; /* last emitted length */
778 var curlen; /* length of current code */
779
780 var nextlen = tree[0 * 2 + 1] /*.Len*/ ; /* length of next code */
781
782 var count = 0; /* repeat count of the current code */
783 var max_count = 7; /* max repeat count */
784 var min_count = 4; /* min repeat count */
785
786 if (nextlen === 0) {
787 max_count = 138;
788 min_count = 3;
789 }
790 tree[(max_code + 1) * 2 + 1] /*.Len*/ = 0xffff; /* guard */
791
792 for (n = 0; n <= max_code; n++) {
793 curlen = nextlen;
794 nextlen = tree[(n + 1) * 2 + 1] /*.Len*/ ;
795
796 if (++count < max_count && curlen === nextlen) {
797 continue;
798
799 } else if (count < min_count) {
800 s.bl_tree[curlen * 2] /*.Freq*/ += count;
801
802 } else if (curlen !== 0) {
803
804 if (curlen !== prevlen) {
805 s.bl_tree[curlen * 2] /*.Freq*/ ++;
806 }
807 s.bl_tree[REP_3_6 * 2] /*.Freq*/ ++;
808
809 } else if (count <= 10) {
810 s.bl_tree[REPZ_3_10 * 2] /*.Freq*/ ++;
811
812 } else {
813 s.bl_tree[REPZ_11_138 * 2] /*.Freq*/ ++;
814 }
815
816 count = 0;
817 prevlen = curlen;
818
819 if (nextlen === 0) {
820 max_count = 138;
821 min_count = 3;
822
823 } else if (curlen === nextlen) {
824 max_count = 6;
825 min_count = 3;
826
827 } else {
828 max_count = 7;
829 min_count = 4;
830 }
831 }
832 }
833
834
835 /* ===========================================================================
836 * Send a literal or distance tree in compressed form, using the codes in
837 * bl_tree.
838 */
839 function send_tree(s, tree, max_code)
840 // deflate_state *s;
841 // ct_data *tree; /* the tree to be scanned */
842 // int max_code; /* and its largest code of non zero frequency */
843 {
844 var n; /* iterates over all tree elements */
845 var prevlen = -1; /* last emitted length */
846 var curlen; /* length of current code */
847
848 var nextlen = tree[0 * 2 + 1] /*.Len*/ ; /* length of next code */
849
850 var count = 0; /* repeat count of the current code */
851 var max_count = 7; /* max repeat count */
852 var min_count = 4; /* min repeat count */
853
854 /* tree[max_code+1].Len = -1; */
855 /* guard already set */
856 if (nextlen === 0) {
857 max_count = 138;
858 min_count = 3;
859 }
860
861 for (n = 0; n <= max_code; n++) {
862 curlen = nextlen;
863 nextlen = tree[(n + 1) * 2 + 1] /*.Len*/ ;
864
865 if (++count < max_count && curlen === nextlen) {
866 continue;
867
868 } else if (count < min_count) {
869 do {
870 send_code(s, curlen, s.bl_tree);
871 } while (--count !== 0);
872
873 } else if (curlen !== 0) {
874 if (curlen !== prevlen) {
875 send_code(s, curlen, s.bl_tree);
876 count--;
877 }
878 //Assert(count >= 3 && count <= 6, " 3_6?");
879 send_code(s, REP_3_6, s.bl_tree);
880 send_bits(s, count - 3, 2);
881
882 } else if (count <= 10) {
883 send_code(s, REPZ_3_10, s.bl_tree);
884 send_bits(s, count - 3, 3);
885
886 } else {
887 send_code(s, REPZ_11_138, s.bl_tree);
888 send_bits(s, count - 11, 7);
889 }
890
891 count = 0;
892 prevlen = curlen;
893 if (nextlen === 0) {
894 max_count = 138;
895 min_count = 3;
896
897 } else if (curlen === nextlen) {
898 max_count = 6;
899 min_count = 3;
900
901 } else {
902 max_count = 7;
903 min_count = 4;
904 }
905 }
906 }
907
908
909 /* ===========================================================================
910 * Construct the Huffman tree for the bit lengths and return the index in
911 * bl_order of the last bit length code to send.
912 */
913 function build_bl_tree(s) {
914 var max_blindex; /* index of last bit length code of non zero freq */
915
916 /* Determine the bit length frequencies for literal and distance trees */
917 scan_tree(s, s.dyn_ltree, s.l_desc.max_code);
918 scan_tree(s, s.dyn_dtree, s.d_desc.max_code);
919
920 /* Build the bit length tree: */
921 build_tree(s, s.bl_desc);
922 /* opt_len now includes the length of the tree representations, except
923 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts.
924 */
925
926 /* Determine the number of bit length codes to send. The pkzip format
927 * requires that at least 4 bit length codes be sent. (appnote.txt says
928 * 3 but the actual value used is 4.)
929 */
930 for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
931 if (s.bl_tree[bl_order[max_blindex] * 2 + 1] /*.Len*/ !== 0) {
932 break;
933 }
934 }
935 /* Update opt_len to include the bit length tree and counts */
936 s.opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;
937 //Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld",
938 // s->opt_len, s->static_len));
939
940 return max_blindex;
941 }
942
943
944 /* ===========================================================================
945 * Send the header for a block using dynamic Huffman trees: the counts, the
946 * lengths of the bit length codes, the literal tree and the distance tree.
947 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
948 */
949 function send_all_trees(s, lcodes, dcodes, blcodes)
950 // deflate_state *s;
951 // int lcodes, dcodes, blcodes; /* number of codes for each tree */
952 {
953 var rank; /* index in bl_order */
954
955 //Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes");
956 //Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES,
957 // "too many codes");
958 //Tracev((stderr, "\nbl counts: "));
959 send_bits(s, lcodes - 257, 5); /* not +255 as stated in appnote.txt */
960 send_bits(s, dcodes - 1, 5);
961 send_bits(s, blcodes - 4, 4); /* not -3 as stated in appnote.txt */
962 for (rank = 0; rank < blcodes; rank++) {
963 //Tracev((stderr, "\nbl code %2d ", bl_order[rank]));
964 send_bits(s, s.bl_tree[bl_order[rank] * 2 + 1] /*.Len*/ , 3);
965 }
966 //Tracev((stderr, "\nbl tree: sent %ld", s->bits_sent));
967
968 send_tree(s, s.dyn_ltree, lcodes - 1); /* literal tree */
969 //Tracev((stderr, "\nlit tree: sent %ld", s->bits_sent));
970
971 send_tree(s, s.dyn_dtree, dcodes - 1); /* distance tree */
972 //Tracev((stderr, "\ndist tree: sent %ld", s->bits_sent));
973 }
974
975
976 /* ===========================================================================
977 * Check if the data type is TEXT or BINARY, using the following algorithm:
978 * - TEXT if the two conditions below are satisfied:
979 * a) There are no non-portable control characters belonging to the
980 * "black list" (0..6, 14..25, 28..31).
981 * b) There is at least one printable character belonging to the
982 * "white list" (9 {TAB}, 10 {LF}, 13 {CR}, 32..255).
983 * - BINARY otherwise.
984 * - The following partially-portable control characters form a
985 * "gray list" that is ignored in this detection algorithm:
986 * (7 {BEL}, 8 {BS}, 11 {VT}, 12 {FF}, 26 {SUB}, 27 {ESC}).
987 * IN assertion: the fields Freq of dyn_ltree are set.
988 */
989 function detect_data_type(s) {
990 /* black_mask is the bit mask of black-listed bytes
991 * set bits 0..6, 14..25, and 28..31
992 * 0xf3ffc07f = binary 11110011111111111100000001111111
993 */
994 var black_mask = 0xf3ffc07f;
995 var n;
996
997 /* Check for non-textual ("black-listed") bytes. */
998 for (n = 0; n <= 31; n++, black_mask >>>= 1) {
999 if ((black_mask & 1) && (s.dyn_ltree[n * 2] /*.Freq*/ !== 0)) {
1000 return Z_BINARY;
1001 }
1002 }
1003
1004 /* Check for textual ("white-listed") bytes. */
1005 if (s.dyn_ltree[9 * 2] /*.Freq*/ !== 0 || s.dyn_ltree[10 * 2] /*.Freq*/ !== 0 ||
1006 s.dyn_ltree[13 * 2] /*.Freq*/ !== 0) {
1007 return Z_TEXT;
1008 }
1009 for (n = 32; n < LITERALS; n++) {
1010 if (s.dyn_ltree[n * 2] /*.Freq*/ !== 0) {
1011 return Z_TEXT;
1012 }
1013 }
1014
1015 /* There are no "black-listed" or "white-listed" bytes:
1016 * this stream either is empty or has tolerated ("gray-listed") bytes only.
1017 */
1018 return Z_BINARY;
1019 }
1020
1021
1022 var static_init_done = false;
1023
1024 /* ===========================================================================
1025 * Initialize the tree data structures for a new zlib stream.
1026 */
1027 export function _tr_init(s) {
1028
1029 if (!static_init_done) {
1030 tr_static_init();
1031 static_init_done = true;
1032 }
1033
1034 s.l_desc = new TreeDesc(s.dyn_ltree, static_l_desc);
1035 s.d_desc = new TreeDesc(s.dyn_dtree, static_d_desc);
1036 s.bl_desc = new TreeDesc(s.bl_tree, static_bl_desc);
1037
1038 s.bi_buf = 0;
1039 s.bi_valid = 0;
1040
1041 /* Initialize the first block of the first file: */
1042 init_block(s);
1043 }
1044
1045
1046 /* ===========================================================================
1047 * Send a stored block
1048 */
1049 export function _tr_stored_block(s, buf, stored_len, last)
1050 //DeflateState *s;
1051 //charf *buf; /* input block */
1052 //ulg stored_len; /* length of input block */
1053 //int last; /* one if this is the last block for a file */
1054 {
1055 send_bits(s, (STORED_BLOCK << 1) + (last ? 1 : 0), 3); /* send block type */
1056 copy_block(s, buf, stored_len, true); /* with header */
1057 }
1058
1059
1060 /* ===========================================================================
1061 * Send one empty static block to give enough lookahead for inflate.
1062 * This takes 10 bits, of which 7 may remain in the bit buffer.
1063 */
1064 export function _tr_align(s) {
1065 send_bits(s, STATIC_TREES << 1, 3);
1066 send_code(s, END_BLOCK, static_ltree);
1067 bi_flush(s);
1068 }
1069
1070
1071 /* ===========================================================================
1072 * Determine the best encoding for the current block: dynamic trees, static
1073 * trees or store, and output the encoded block to the zip file.
1074 */
1075 export function _tr_flush_block(s, buf, stored_len, last)
1076 //DeflateState *s;
1077 //charf *buf; /* input block, or NULL if too old */
1078 //ulg stored_len; /* length of input block */
1079 //int last; /* one if this is the last block for a file */
1080 {
1081 var opt_lenb, static_lenb; /* opt_len and static_len in bytes */
1082 var max_blindex = 0; /* index of last bit length code of non zero freq */
1083
1084 /* Build the Huffman trees unless a stored block is forced */
1085 if (s.level > 0) {
1086
1087 /* Check if the file is binary or text */
1088 if (s.strm.data_type === Z_UNKNOWN) {
1089 s.strm.data_type = detect_data_type(s);
1090 }
1091
1092 /* Construct the literal and distance trees */
1093 build_tree(s, s.l_desc);
1094 // Tracev((stderr, "\nlit data: dyn %ld, stat %ld", s->opt_len,
1095 // s->static_len));
1096
1097 build_tree(s, s.d_desc);
1098 // Tracev((stderr, "\ndist data: dyn %ld, stat %ld", s->opt_len,
1099 // s->static_len));
1100 /* At this point, opt_len and static_len are the total bit lengths of
1101 * the compressed block data, excluding the tree representations.
1102 */
1103
1104 /* Build the bit length tree for the above two trees, and get the index
1105 * in bl_order of the last bit length code to send.
1106 */
1107 max_blindex = build_bl_tree(s);
1108
1109 /* Determine the best encoding. Compute the block lengths in bytes. */
1110 opt_lenb = (s.opt_len + 3 + 7) >>> 3;
1111 static_lenb = (s.static_len + 3 + 7) >>> 3;
1112
1113 // Tracev((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u ",
1114 // opt_lenb, s->opt_len, static_lenb, s->static_len, stored_len,
1115 // s->last_lit));
1116
1117 if (static_lenb <= opt_lenb) {
1118 opt_lenb = static_lenb;
1119 }
1120
1121 } else {
1122 // Assert(buf != (char*)0, "lost buf");
1123 opt_lenb = static_lenb = stored_len + 5; /* force a stored block */
1124 }
1125
1126 if ((stored_len + 4 <= opt_lenb) && (buf !== -1)) {
1127 /* 4: two words for the lengths */
1128
1129 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
1130 * Otherwise we can't have processed more than WSIZE input bytes since
1131 * the last block flush, because compression would have been
1132 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
1133 * transform a block into a stored block.
1134 */
1135 _tr_stored_block(s, buf, stored_len, last);
1136
1137 } else if (s.strategy === Z_FIXED || static_lenb === opt_lenb) {
1138
1139 send_bits(s, (STATIC_TREES << 1) + (last ? 1 : 0), 3);
1140 compress_block(s, static_ltree, static_dtree);
1141
1142 } else {
1143 send_bits(s, (DYN_TREES << 1) + (last ? 1 : 0), 3);
1144 send_all_trees(s, s.l_desc.max_code + 1, s.d_desc.max_code + 1, max_blindex + 1);
1145 compress_block(s, s.dyn_ltree, s.dyn_dtree);
1146 }
1147 // Assert (s->compressed_len == s->bits_sent, "bad compressed size");
1148 /* The above check is made mod 2^32, for files larger than 512 MB
1149 * and uLong implemented on 32 bits.
1150 */
1151 init_block(s);
1152
1153 if (last) {
1154 bi_windup(s);
1155 }
1156 // Tracev((stderr,"\ncomprlen %lu(%lu) ", s->compressed_len>>3,
1157 // s->compressed_len-7*last));
1158 }
1159
1160 /* ===========================================================================
1161 * Save the match info and tally the frequency counts. Return true if
1162 * the current block must be flushed.
1163 */
1164 export function _tr_tally(s, dist, lc)
1165 // deflate_state *s;
1166 // unsigned dist; /* distance of matched string */
1167 // unsigned lc; /* match length-MIN_MATCH or unmatched char (if dist==0) */
1168 {
1169 //var out_length, in_length, dcode;
1170
1171 s.pending_buf[s.d_buf + s.last_lit * 2] = (dist >>> 8) & 0xff;
1172 s.pending_buf[s.d_buf + s.last_lit * 2 + 1] = dist & 0xff;
1173
1174 s.pending_buf[s.l_buf + s.last_lit] = lc & 0xff;
1175 s.last_lit++;
1176
1177 if (dist === 0) {
1178 /* lc is the unmatched char */
1179 s.dyn_ltree[lc * 2] /*.Freq*/ ++;
1180 } else {
1181 s.matches++;
1182 /* Here, lc is the match length - MIN_MATCH */
1183 dist--; /* dist = match distance - 1 */
1184 //Assert((ush)dist < (ush)MAX_DIST(s) &&
1185 // (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) &&
1186 // (ush)d_code(dist) < (ush)D_CODES, "_tr_tally: bad match");
1187
1188 s.dyn_ltree[(_length_code[lc] + LITERALS + 1) * 2] /*.Freq*/ ++;
1189 s.dyn_dtree[d_code(dist) * 2] /*.Freq*/ ++;
1190 }
1191
1192 // (!) This block is disabled in zlib defailts,
1193 // don't enable it for binary compatibility
1194
1195 //#ifdef TRUNCATE_BLOCK
1196 // /* Try to guess if it is profitable to stop the current block here */
1197 // if ((s.last_lit & 0x1fff) === 0 && s.level > 2) {
1198 // /* Compute an upper bound for the compressed length */
1199 // out_length = s.last_lit*8;
1200 // in_length = s.strstart - s.block_start;
1201 //
1202 // for (dcode = 0; dcode < D_CODES; dcode++) {
1203 // out_length += s.dyn_dtree[dcode*2]/*.Freq*/ * (5 + extra_dbits[dcode]);
1204 // }
1205 // out_length >>>= 3;
1206 // //Tracev((stderr,"\nlast_lit %u, in %ld, out ~%ld(%ld%%) ",
1207 // // s->last_lit, in_length, out_length,
1208 // // 100L - out_length*100L/in_length));
1209 // if (s.matches < (s.last_lit>>1)/*int /2*/ && out_length < (in_length>>1)/*int /2*/) {
1210 // return true;
1211 // }
1212 // }
1213 //#endif
1214
1215 return (s.last_lit === s.lit_bufsize - 1);
1216 /* We avoid equality with lit_bufsize because of wraparound at 64K
1217 * on 16 bit machines and because stored blocks are restricted to
1218 * 64K-1 bytes.
1219 */
1220 }