| 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 |
} |