1/* 2 * $Id: rawdeflate.js,v 0.5 2013/04/09 14:25:38 dankogai Exp dankogai $ 3 * 4 * GNU General Public License, version 2 (GPL-2.0) 5 * http://opensource.org/licenses/GPL-2.0 6 * Original: 7 * http://www.onicos.com/staff/iz/amuse/javascript/expert/deflate.txt 8 */ 9 10(function(ctx){ 11 12/* Copyright (C) 1999 Masanao Izumo <[email protected]> 13 * Version: 1.0.1 14 * LastModified: Dec 25 1999 15 */ 16 17/* Interface: 18 * data = zip_deflate(src); 19 */ 20 21/* constant parameters */ 22var zip_WSIZE = 32768; // Sliding Window size 23var zip_STORED_BLOCK = 0; 24var zip_STATIC_TREES = 1; 25var zip_DYN_TREES = 2; 26 27/* for deflate */ 28var zip_DEFAULT_LEVEL = 6; 29var zip_FULL_SEARCH = true; 30var zip_INBUFSIZ = 32768; // Input buffer size 31var zip_INBUF_EXTRA = 64; // Extra buffer 32var zip_OUTBUFSIZ = 1024 * 8; 33var zip_window_size = 2 * zip_WSIZE; 34var zip_MIN_MATCH = 3; 35var zip_MAX_MATCH = 258; 36var zip_BITS = 16; 37// for SMALL_MEM 38var zip_LIT_BUFSIZE = 0x2000; 39var zip_HASH_BITS = 13; 40// for MEDIUM_MEM 41// var zip_LIT_BUFSIZE = 0x4000; 42// var zip_HASH_BITS = 14; 43// for BIG_MEM 44// var zip_LIT_BUFSIZE = 0x8000; 45// var zip_HASH_BITS = 15; 46if(zip_LIT_BUFSIZE > zip_INBUFSIZ) 47 alert("error: zip_INBUFSIZ is too small"); 48if((zip_WSIZE<<1) > (1<<zip_BITS)) 49 alert("error: zip_WSIZE is too large"); 50if(zip_HASH_BITS > zip_BITS-1) 51 alert("error: zip_HASH_BITS is too large"); 52if(zip_HASH_BITS < 8 || zip_MAX_MATCH != 258) 53 alert("error: Code too clever"); 54var zip_DIST_BUFSIZE = zip_LIT_BUFSIZE; 55var zip_HASH_SIZE = 1 << zip_HASH_BITS; 56var zip_HASH_MASK = zip_HASH_SIZE - 1; 57var zip_WMASK = zip_WSIZE - 1; 58var zip_NIL = 0; // Tail of hash chains 59var zip_TOO_FAR = 4096; 60var zip_MIN_LOOKAHEAD = zip_MAX_MATCH + zip_MIN_MATCH + 1; 61var zip_MAX_DIST = zip_WSIZE - zip_MIN_LOOKAHEAD; 62var zip_SMALLEST = 1; 63var zip_MAX_BITS = 15; 64var zip_MAX_BL_BITS = 7; 65var zip_LENGTH_CODES = 29; 66var zip_LITERALS =256; 67var zip_END_BLOCK = 256; 68var zip_L_CODES = zip_LITERALS + 1 + zip_LENGTH_CODES; 69var zip_D_CODES = 30; 70var zip_BL_CODES = 19; 71var zip_REP_3_6 = 16; 72var zip_REPZ_3_10 = 17; 73var zip_REPZ_11_138 = 18; 74var zip_HEAP_SIZE = 2 * zip_L_CODES + 1; 75var zip_H_SHIFT = parseInt((zip_HASH_BITS + zip_MIN_MATCH - 1) / 76 zip_MIN_MATCH); 77 78/* variables */ 79var zip_free_queue; 80var zip_qhead, zip_qtail; 81var zip_initflag; 82var zip_outbuf = null; 83var zip_outcnt, zip_outoff; 84var zip_complete; 85var zip_window; 86var zip_d_buf; 87var zip_l_buf; 88var zip_prev; 89var zip_bi_buf; 90var zip_bi_valid; 91var zip_block_start; 92var zip_ins_h; 93var zip_hash_head; 94var zip_prev_match; 95var zip_match_available; 96var zip_match_length; 97var zip_prev_length; 98var zip_strstart; 99var zip_match_start; 100var zip_eofile; 101var zip_lookahead; 102var zip_max_chain_length; 103var zip_max_lazy_match; 104var zip_compr_level; 105var zip_good_match; 106var zip_nice_match; 107var zip_dyn_ltree; 108var zip_dyn_dtree; 109var zip_static_ltree; 110var zip_static_dtree; 111var zip_bl_tree; 112var zip_l_desc; 113var zip_d_desc; 114var zip_bl_desc; 115var zip_bl_count; 116var zip_heap; 117var zip_heap_len; 118var zip_heap_max; 119var zip_depth; 120var zip_length_code; 121var zip_dist_code; 122var zip_base_length; 123var zip_base_dist; 124var zip_flag_buf; 125var zip_last_lit; 126var zip_last_dist; 127var zip_last_flags; 128var zip_flags; 129var zip_flag_bit; 130var zip_opt_len; 131var zip_static_len; 132var zip_deflate_data; 133var zip_deflate_pos; 134 135/* objects (deflate) */ 136 137var zip_DeflateCT = function() { 138 this.fc = 0; // frequency count or bit string 139 this.dl = 0; // father node in Huffman tree or length of bit string 140} 141 142var zip_DeflateTreeDesc = function() { 143 this.dyn_tree = null; // the dynamic tree 144 this.static_tree = null; // corresponding static tree or NULL 145 this.extra_bits = null; // extra bits for each code or NULL 146 this.extra_base = 0; // base index for extra_bits 147 this.elems = 0; // max number of elements in the tree 148 this.max_length = 0; // max bit length for the codes 149 this.max_code = 0; // largest code with non zero frequency 150} 151 152/* Values for max_lazy_match, good_match and max_chain_length, depending on 153 * the desired pack level (0..9). The values given below have been tuned to 154 * exclude worst case performance for pathological files. Better values may be 155 * found for specific files. 156 */ 157var zip_DeflateConfiguration = function(a, b, c, d) { 158 this.good_length = a; // reduce lazy search above this match length 159 this.max_lazy = b; // do not perform lazy search above this match length 160 this.nice_length = c; // quit search above this match length 161 this.max_chain = d; 162} 163 164var zip_DeflateBuffer = function() { 165 this.next = null; 166 this.len = 0; 167 this.ptr = new Array(zip_OUTBUFSIZ); 168 this.off = 0; 169} 170 171/* constant tables */ 172var zip_extra_lbits = new Array( 173 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); 174var zip_extra_dbits = new Array( 175 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); 176var zip_extra_blbits = new Array( 177 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,3,7); 178var zip_bl_order = new Array( 179 16,17,18,0,8,7,9,6,10,5,11,4,12,3,13,2,14,1,15); 180var zip_configuration_table = new Array( 181 new zip_DeflateConfiguration(0, 0, 0, 0), 182 new zip_DeflateConfiguration(4, 4, 8, 4), 183 new zip_DeflateConfiguration(4, 5, 16, 8), 184 new zip_DeflateConfiguration(4, 6, 32, 32), 185 new zip_DeflateConfiguration(4, 4, 16, 16), 186 new zip_DeflateConfiguration(8, 16, 32, 32), 187 new zip_DeflateConfiguration(8, 16, 128, 128), 188 new zip_DeflateConfiguration(8, 32, 128, 256),
189 new zip_DeflateConfiguration(32, 128, 258, 1024), 190 new zip_DeflateConfiguration(32, 258, 258, 4096)); 191 192 193/* routines (deflate) */ 194 195var zip_deflate_start = function(level) { 196 var i; 197 198 if(!level) 199 level = zip_DEFAULT_LEVEL; 200 else if(level < 1) 201 level = 1; 202 else if(level > 9) 203 level = 9; 204 205 zip_compr_level = level; 206 zip_initflag = false; 207 zip_eofile = false; 208 if(zip_outbuf != null) 209 return; 210 211 zip_free_queue = zip_qhead = zip_qtail = null; 212 zip_outbuf = new Array(zip_OUTBUFSIZ); 213 zip_window = new Array(zip_window_size); 214 zip_d_buf = new Array(zip_DIST_BUFSIZE); 215 zip_l_buf = new Array(zip_INBUFSIZ + zip_INBUF_EXTRA); 216 zip_prev = new Array(1 << zip_BITS); 217 zip_dyn_ltree = new Array(zip_HEAP_SIZE); 218 for(i = 0; i < zip_HEAP_SIZE; i++) 219 zip_dyn_ltree[i] = new zip_DeflateCT(); 220 zip_dyn_dtree = new Array(2*zip_D_CODES+1); 221 for(i = 0; i < 2*zip_D_CODES+1; i++) 222 zip_dyn_dtree[i] = new zip_DeflateCT(); 223 zip_static_ltree = new Array(zip_L_CODES+2); 224 for(i = 0; i < zip_L_CODES+2; i++) 225 zip_static_ltree[i] = new zip_DeflateCT(); 226 zip_static_dtree = new Array(zip_D_CODES); 227 for(i = 0; i < zip_D_CODES; i++) 228 zip_static_dtree[i] = new zip_DeflateCT(); 229 zip_bl_tree = new Array(2*zip_BL_CODES+1); 230 for(i = 0; i < 2*zip_BL_CODES+1; i++) 231 zip_bl_tree[i] = new zip_DeflateCT(); 232 zip_l_desc = new zip_DeflateTreeDesc(); 233 zip_d_desc = new zip_DeflateTreeDesc(); 234 zip_bl_desc = new zip_DeflateTreeDesc(); 235 zip_bl_count = new Array(zip_MAX_BITS+1); 236 zip_heap = new Array(2*zip_L_CODES+1); 237 zip_depth = new Array(2*zip_L_CODES+1); 238 zip_length_code = new Array(zip_MAX_MATCH-zip_MIN_MATCH+1); 239 zip_dist_code = new Array(512); 240 zip_base_length = new Array(zip_LENGTH_CODES); 241 zip_base_dist = new Array(zip_D_CODES); 242 zip_flag_buf = new Array(parseInt(zip_LIT_BUFSIZE / 8)); 243} 244 245var zip_deflate_end = function() { 246 zip_free_queue = zip_qhead = zip_qtail = null; 247 zip_outbuf = null; 248 zip_window = null; 249 zip_d_buf = null; 250 zip_l_buf = null; 251 zip_prev = null; 252 zip_dyn_ltree = null; 253 zip_dyn_dtree = null; 254 zip_static_ltree = null; 255 zip_static_dtree = null; 256 zip_bl_tree = null; 257 zip_l_desc = null; 258 zip_d_desc = null; 259 zip_bl_desc = null; 260 zip_bl_count = null; 261 zip_heap = null; 262 zip_depth = null; 263 zip_length_code = null; 264 zip_dist_code = null; 265 zip_base_length = null; 266 zip_base_dist = null; 267 zip_flag_buf = null; 268} 269 270var zip_reuse_queue = function(p) { 271 p.next = zip_free_queue; 272 zip_free_queue = p; 273} 274 275var zip_new_queue = function() { 276 var p; 277 278 if(zip_free_queue != null) 279 { 280 p = zip_free_queue; 281 zip_free_queue = zip_free_queue.next; 282 } 283 else 284 p = new zip_DeflateBuffer(); 285 p.next = null; 286 p.len = p.off = 0; 287 288 return p; 289} 290 291var zip_head1 = function(i) { 292 return zip_prev[zip_WSIZE + i]; 293} 294 295var zip_head2 = function(i, val) { 296 return zip_prev[zip_WSIZE + i] = val; 297} 298 299/* put_byte is used for the compressed output, put_ubyte for the 300 * uncompressed output. However unlzw() uses window for its 301 * suffix table instead of its output buffer, so it does not use put_ubyte 302 * (to be cleaned up). 303 */ 304var zip_put_byte = function(c) { 305 zip_outbuf[zip_outoff + zip_outcnt++] = c; 306 if(zip_outoff + zip_outcnt == zip_OUTBUFSIZ) 307 zip_qoutbuf(); 308} 309 310/* Output a 16 bit value, lsb first */ 311var zip_put_short = function(w) { 312 w &= 0xffff; 313 if(zip_outoff + zip_outcnt < zip_OUTBUFSIZ - 2) { 314 zip_outbuf[zip_outoff + zip_outcnt++] = (w & 0xff); 315 zip_outbuf[zip_outoff + zip_outcnt++] = (w >>> 8); 316 } else { 317 zip_put_byte(w & 0xff); 318 zip_put_byte(w >>> 8); 319 } 320} 321 322/* ========================================================================== 323 * Insert string s in the dictionary and set match_head to the previous head 324 * of the hash chain (the most recent string with same hash key). Return 325 * the previous length of the hash chain. 326 * IN assertion: all calls to to INSERT_STRING are made with consecutive 327 * input characters and the first MIN_MATCH bytes of s are valid 328 * (except for the last MIN_MATCH-1 bytes of the input file). 329 */ 330var zip_INSERT_STRING = function() { 331 zip_ins_h = ((zip_ins_h << zip_H_SHIFT) 332 ^ (zip_window[zip_strstart + zip_MIN_MATCH - 1] & 0xff)) 333 & zip_HASH_MASK; 334 zip_hash_head = zip_head1(zip_ins_h); 335 zip_prev[zip_strstart & zip_WMASK] = zip_hash_head; 336 zip_head2(zip_ins_h, zip_strstart); 337} 338 339/* Send a code of the given tree. c and tree must not have side effects */ 340var zip_SEND_CODE = function(c, tree) { 341 zip_send_bits(tree[c].fc, tree[c].dl); 342} 343 344/* Mapping from a distance to a distance code. dist is the distance - 1 and 345 * must not have side effects. dist_code[256] and dist_code[257] are never 346 * used. 347 */ 348var zip_D_CODE = function(dist) { 349 return (dist < 256 ? zip_dist_code[dist] 350 : zip_dist_code[256 + (dist>>7)]) & 0xff;
351} 352 353/* ========================================================================== 354 * Compares to subtrees, using the tree depth as tie breaker when 355 * the subtrees have equal frequency. This minimizes the worst case length. 356 */ 357var zip_SMALLER = function(tree, n, m) { 358 return tree[n].fc < tree[m].fc || 359 (tree[n].fc == tree[m].fc && zip_depth[n] <= zip_depth[m]); 360} 361 362/* ========================================================================== 363 * read string data 364 */ 365var zip_read_buff = function(buff, offset, n) { 366 var i; 367 for(i = 0; i < n && zip_deflate_pos < zip_deflate_data.length; i++) 368 buff[offset + i] = 369 zip_deflate_data.charCodeAt(zip_deflate_pos++) & 0xff; 370 return i; 371} 372 373/* ========================================================================== 374 * Initialize the "longest match" routines for a new file 375 */ 376var zip_lm_init = function() { 377 var j; 378 379 /* Initialize the hash table. */ 380 for(j = 0; j < zip_HASH_SIZE; j++) 381// zip_head2(j, zip_NIL); 382 zip_prev[zip_WSIZE + j] = 0; 383 /* prev will be initialized on the fly */ 384 385 /* Set the default configuration parameters: 386 */ 387 zip_max_lazy_match = zip_configuration_table[zip_compr_level].max_lazy; 388 zip_good_match = zip_configuration_table[zip_compr_level].good_length; 389 if(!zip_FULL_SEARCH) 390 zip_nice_match = zip_configuration_table[zip_compr_level].nice_length; 391 zip_max_chain_length = zip_configuration_table[zip_compr_level].max_chain; 392 393 zip_strstart = 0; 394 zip_block_start = 0; 395 396 zip_lookahead = zip_read_buff(zip_window, 0, 2 * zip_WSIZE); 397 if(zip_lookahead <= 0) { 398 zip_eofile = true; 399 zip_lookahead = 0; 400 return; 401 } 402 zip_eofile = false; 403 /* Make sure that we always have enough lookahead. This is important 404 * if input comes from a device such as a tty. 405 */ 406 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile) 407 zip_fill_window(); 408 409 /* If lookahead < MIN_MATCH, ins_h is garbage, but this is 410 * not important since only literal bytes will be emitted. 411 */ 412 zip_ins_h = 0; 413 for(j = 0; j < zip_MIN_MATCH - 1; j++) { 414// UPDATE_HASH(ins_h, window[j]); 415 zip_ins_h = ((zip_ins_h << zip_H_SHIFT) ^ (zip_window[j] & 0xff)) & zip_HASH_MASK; 416 } 417} 418 419/* ========================================================================== 420 * Set match_start to the longest match starting at the given string and 421 * return its length. Matches shorter or equal to prev_length are discarded, 422 * in which case the result is equal to prev_length and match_start is 423 * garbage. 424 * IN assertions: cur_match is the head of the hash chain for the current 425 * string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1 426 */ 427var zip_longest_match = function(cur_match) { 428 var chain_length = zip_max_chain_length; // max hash chain length 429 var scanp = zip_strstart; // current string 430 var matchp; // matched string 431 var len; // length of current match 432 var best_len = zip_prev_length; // best match length so far 433 434 /* Stop when cur_match becomes <= limit. To simplify the code, 435 * we prevent matches with the string of window index 0. 436 */ 437 var limit = (zip_strstart > zip_MAX_DIST ? zip_strstart - zip_MAX_DIST : zip_NIL); 438 439 var strendp = zip_strstart + zip_MAX_MATCH; 440 var scan_end1 = zip_window[scanp + best_len - 1]; 441 var scan_end = zip_window[scanp + best_len]; 442 443 /* Do not waste too much time if we already have a good match: */ 444 if(zip_prev_length >= zip_good_match) 445 chain_length >>= 2; 446 447// Assert(encoder->strstart <= window_size-MIN_LOOKAHEAD, "insufficient lookahead"); 448 449 do { 450// Assert(cur_match < encoder->strstart, "no future"); 451 matchp = cur_match; 452 453 /* Skip to next match if the match length cannot increase 454 * or if the match length is less than 2: 455 */ 456 if(zip_window[matchp + best_len] != scan_end || 457 zip_window[matchp + best_len - 1] != scan_end1 || 458 zip_window[matchp] != zip_window[scanp] || 459 zip_window[++matchp] != zip_window[scanp + 1]) { 460 continue; 461 } 462 463 /* The check at best_len-1 can be removed because it will be made 464 * again later. (This heuristic is not always a win.) 465 * It is not necessary to compare scan[2] and match[2] since they 466 * are always equal when the other bytes match, given that 467 * the hash keys are equal and that HASH_BITS >= 8. 468 */ 469 scanp += 2; 470 matchp++; 471 472 /* We check for insufficient lookahead only every 8th comparison; 473 * the 256th check will be made at strstart+258. 474 */ 475 do { 476 } while(zip_window[++scanp] == zip_window[++matchp] && 477 zip_window[++scanp] == zip_window[++matchp] && 478 zip_window[++scanp] == zip_window[++matchp] && 479 zip_window[++scanp] == zip_window[++matchp] && 480 zip_window[++scanp] == zip_window[++matchp] && 481 zip_window[++scanp] == zip_window[++matchp] && 482 zip_window[++scanp] == zip_window[++matchp] && 483 zip_window[++scanp] == zip_window[++matchp] && 484 scanp < strendp); 485 486 len = zip_MAX_MATCH - (strendp - scanp); 487 scanp = strendp - zip_MAX_MATCH; 488 489 if(len > best_len) { 490 zip_match_start = cur_match; 491 best_len = len; 492 if(zip_FULL_SEARCH) { 493 if(len >= zip_MAX_MATCH) break; 494 } else { 495 if(len >= zip_nice_match) break; 496 } 497 498 scan_end1 = zip_window[scanp + best_len-1]; 499 scan_end = zip_window[scanp + best_len]; 500 } 501 } while((cur_match = zip_prev[cur_match & zip_WMASK]) > limit 502 && --chain_length != 0); 503 504 return best_len; 505} 506 507/* ========================================================================== 508 * Fill the window when the lookahead becomes insufficient. 509 * Updates strstart and lookahead, and sets eofile if end of input file. 510 * IN assertion: lookahead < MIN_LOOKAHEAD && strstart + lookahead > 0 511 * OUT assertions: at least one byte has been read, or eofile is set; 512 * file reads are performed for at least two bytes (required for the 513 * translate_eol option). 514 */ 515var zip_fill_window = function() { 516 var n, m; 517 518 // Amount of free space at the end of the window. 519 var more = zip_window_size - zip_lookahead - zip_strstart; 520 521 /* If the window is almost full and there is insufficient lookahead, 522 * move the upper half to the lower one to make room in the upper half. 523 */ 524 if(more == -1) { 525 /* Very unlikely, but possible on 16 bit machine if strstart == 0 526 * and lookahead == 1 (input done one byte at time) 527 */ 528 more--; 529 } else if(zip_strstart >= zip_WSIZE + zip_MAX_DIST) { 530 /* By the IN assertion, the window is not empty so we can't confuse 531 * more == 0 with more == 64K on a 16 bit machine. 532 */ 533// Assert(window_size == (ulg)2*WSIZE, "no sliding with BIG_MEM"); 534 535// System.arraycopy(window, WSIZE, window, 0, WSIZE); 536 for(n = 0; n < zip_WSIZE; n++) 537 zip_window[n] = zip_window[n + zip_WSIZE]; 538 539 zip_match_start -= zip_WSIZE; 540 zip_strstart -= zip_WSIZE; /* we now have strstart >= MAX_DIST: */ 541 zip_block_start -= zip_WSIZE; 542 543 for(n = 0; n < zip_HASH_SIZE; n++) { 544 m = zip_head1(n); 545 zip_head2(n, m >= zip_WSIZE ? m - zip_WSIZE : zip_NIL); 546 } 547 for(n = 0; n < zip_WSIZE; n++) { 548 /* If n is not on any hash chain, prev[n] is garbage but 549 * its value will never be used. 550 */ 551 m = zip_prev[n]; 552 zip_prev[n] = (m >= zip_WSIZE ? m - zip_WSIZE : zip_NIL); 553 } 554 more += zip_WSIZE; 555 } 556 // At this point, more >= 2 557 if(!zip_eofile) { 558 n = zip_read_buff(zip_window, zip_strstart + zip_lookahead, more); 559 if(n <= 0) 560 zip_eofile = true; 561 else 562 zip_lookahead += n; 563 } 564} 565 566/* ========================================================================== 567 * Processes a new input file and return its compressed length. This 568 * function does not perform lazy evaluationof matches and inserts 569 * new strings in the dictionary only for unmatched strings or for short
570 * matches. It is used only for the fast compression options. 571 */ 572var zip_deflate_fast = function() { 573 while(zip_lookahead != 0 && zip_qhead == null) { 574 var flush; // set if current block must be flushed 575 576 /* Insert the string window[strstart .. strstart+2] in the 577 * dictionary, and set hash_head to the head of the hash chain: 578 */ 579 zip_INSERT_STRING(); 580 581 /* Find the longest match, discarding those <= prev_length. 582 * At this point we have always match_length < MIN_MATCH 583 */ 584 if(zip_hash_head != zip_NIL && 585 zip_strstart - zip_hash_head <= zip_MAX_DIST) { 586 /* To simplify the code, we prevent matches with the string 587 * of window index 0 (in particular we have to avoid a match 588 * of the string with itself at the start of the input file). 589 */ 590 zip_match_length = zip_longest_match(zip_hash_head); 591 /* longest_match() sets match_start */ 592 if(zip_match_length > zip_lookahead) 593 zip_match_length = zip_lookahead; 594 } 595 if(zip_match_length >= zip_MIN_MATCH) { 596// check_match(strstart, match_start, match_length); 597 598 flush = zip_ct_tally(zip_strstart - zip_match_start, 599 zip_match_length - zip_MIN_MATCH); 600 zip_lookahead -= zip_match_length; 601 602 /* Insert new strings in the hash table only if the match length 603 * is not too large. This saves time but degrades compression. 604 */ 605 if(zip_match_length <= zip_max_lazy_match) { 606 zip_match_length--; // string at strstart already in hash table 607 do { 608 zip_strstart++; 609 zip_INSERT_STRING(); 610 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 611 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH 612 * these bytes are garbage, but it does not matter since 613 * the next lookahead bytes will be emitted as literals. 614 */ 615 } while(--zip_match_length != 0); 616 zip_strstart++; 617 } else { 618 zip_strstart += zip_match_length; 619 zip_match_length = 0; 620 zip_ins_h = zip_window[zip_strstart] & 0xff; 621// UPDATE_HASH(ins_h, window[strstart + 1]); 622 zip_ins_h = ((zip_ins_h<<zip_H_SHIFT) ^ (zip_window[zip_strstart + 1] & 0xff)) & zip_HASH_MASK; 623 624//#if MIN_MATCH != 3 625// Call UPDATE_HASH() MIN_MATCH-3 more times 626//#endif 627 628 } 629 } else { 630 /* No match, output a literal byte */ 631 flush = zip_ct_tally(0, zip_window[zip_strstart] & 0xff); 632 zip_lookahead--; 633 zip_strstart++; 634 } 635 if(flush) { 636 zip_flush_block(0); 637 zip_block_start = zip_strstart; 638 } 639 640 /* Make sure that we always have enough lookahead, except 641 * at the end of the input file. We need MAX_MATCH bytes 642 * for the next match, plus MIN_MATCH bytes to insert the 643 * string following the next match. 644 */ 645 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile) 646 zip_fill_window(); 647 } 648} 649 650var zip_deflate_better = function() { 651 /* Process the input block. */ 652 while(zip_lookahead != 0 && zip_qhead == null) { 653 /* Insert the string window[strstart .. strstart+2] in the 654 * dictionary, and set hash_head to the head of the hash chain: 655 */ 656 zip_INSERT_STRING(); 657 658 /* Find the longest match, discarding those <= prev_length. 659 */ 660 zip_prev_length = zip_match_length; 661 zip_prev_match = zip_match_start; 662 zip_match_length = zip_MIN_MATCH - 1; 663 664 if(zip_hash_head != zip_NIL && 665 zip_prev_length < zip_max_lazy_match && 666 zip_strstart - zip_hash_head <= zip_MAX_DIST) { 667 /* To simplify the code, we prevent matches with the string 668 * of window index 0 (in particular we have to avoid a match 669 * of the string with itself at the start of the input file). 670 */ 671 zip_match_length = zip_longest_match(zip_hash_head); 672 /* longest_match() sets match_start */ 673 if(zip_match_length > zip_lookahead) 674 zip_match_length = zip_lookahead; 675 676 /* Ignore a length 3 match if it is too distant: */ 677 if(zip_match_length == zip_MIN_MATCH && 678 zip_strstart - zip_match_start > zip_TOO_FAR) { 679 /* If prev_match is also MIN_MATCH, match_start is garbage 680 * but we will ignore the current match anyway. 681 */ 682 zip_match_length--; 683 } 684 } 685 /* If there was a match at the previous step and the current 686 * match is not better, output the previous match: 687 */ 688 if(zip_prev_length >= zip_MIN_MATCH && 689 zip_match_length <= zip_prev_length) { 690 var flush; // set if current block must be flushed 691
692// check_match(strstart - 1, prev_match, prev_length); 693 flush = zip_ct_tally(zip_strstart - 1 - zip_prev_match, 694 zip_prev_length - zip_MIN_MATCH); 695 696 /* Insert in hash table all strings up to the end of the match. 697 * strstart-1 and strstart are already inserted. 698 */ 699 zip_lookahead -= zip_prev_length - 1; 700 zip_prev_length -= 2; 701 do { 702 zip_strstart++; 703 zip_INSERT_STRING(); 704 /* strstart never exceeds WSIZE-MAX_MATCH, so there are 705 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH 706 * these bytes are garbage, but it does not matter since the 707 * next lookahead bytes will always be emitted as literals. 708 */ 709 } while(--zip_prev_length != 0); 710 zip_match_available = 0; 711 zip_match_length = zip_MIN_MATCH - 1; 712 zip_strstart++; 713 if(flush) { 714 zip_flush_block(0); 715 zip_block_start = zip_strstart; 716 } 717 } else if(zip_match_available != 0) { 718 /* If there was no match at the previous position, output a 719 * single literal. If there was a match but the current match 720 * is longer, truncate the previous match to a single literal. 721 */ 722 if(zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff)) { 723 zip_flush_block(0); 724 zip_block_start = zip_strstart; 725 } 726 zip_strstart++; 727 zip_lookahead--; 728 } else { 729 /* There is no previous match to compare with, wait for 730 * the next step to decide. 731 */ 732 zip_match_available = 1; 733 zip_strstart++; 734 zip_lookahead--; 735 } 736 737 /* Make sure that we always have enough lookahead, except 738 * at the end of the input file. We need MAX_MATCH bytes 739 * for the next match, plus MIN_MATCH bytes to insert the 740 * string following the next match. 741 */ 742 while(zip_lookahead < zip_MIN_LOOKAHEAD && !zip_eofile) 743 zip_fill_window(); 744 } 745} 746 747var zip_init_deflate = function() { 748 if(zip_eofile) 749 return; 750 zip_bi_buf = 0; 751 zip_bi_valid = 0; 752 zip_ct_init(); 753 zip_lm_init(); 754 755 zip_qhead = null; 756 zip_outcnt = 0; 757 zip_outoff = 0; 758 zip_match_available = 0; 759 760 if(zip_compr_level <= 3) 761 { 762 zip_prev_length = zip_MIN_MATCH - 1; 763 zip_match_length = 0; 764 } 765 else 766 { 767 zip_match_length = zip_MIN_MATCH - 1; 768 zip_match_available = 0; 769 zip_match_available = 0; 770 } 771 772 zip_complete = false; 773} 774 775/* ========================================================================== 776 * Same as above, but achieves better compression. We use a lazy 777 * evaluation for matches: a match is finally adopted only if there is 778 * no better match at the next window position. 779 */ 780var zip_deflate_internal = function(buff, off, buff_size) { 781 var n; 782 783 if(!zip_initflag) 784 { 785 zip_init_deflate(); 786 zip_initflag = true; 787 if(zip_lookahead == 0) { // empty 788 zip_complete = true; 789 return 0; 790 } 791 } 792 793 if((n = zip_qcopy(buff, off, buff_size)) == buff_size) 794 return buff_size; 795 796 if(zip_complete) 797 return n; 798 799 if(zip_compr_level <= 3) // optimized for speed 800 zip_deflate_fast(); 801 else 802 zip_deflate_better(); 803 if(zip_lookahead == 0) { 804 if(zip_match_available != 0) 805 zip_ct_tally(0, zip_window[zip_strstart - 1] & 0xff); 806 zip_flush_block(1); 807 zip_complete = true; 808 } 809 return n + zip_qcopy(buff, n + off, buff_size - n); 810} 811 812var zip_qcopy = function(buff, off, buff_size) { 813 var n, i, j; 814 815 n = 0; 816 while(zip_qhead != null && n < buff_size) 817 { 818 i = buff_size - n; 819 if(i > zip_qhead.len) 820 i = zip_qhead.len; 821// System.arraycopy(qhead.ptr, qhead.off, buff, off + n, i); 822 for(j = 0; j < i; j++) 823 buff[off + n + j] = zip_qhead.ptr[zip_qhead.off + j]; 824 825 zip_qhead.off += i; 826 zip_qhead.len -= i; 827 n += i; 828 if(zip_qhead.len == 0) { 829 var p; 830 p = zip_qhead; 831 zip_qhead = zip_qhead.next; 832 zip_reuse_queue(p); 833 } 834 } 835 836 if(n == buff_size) 837 return n; 838 839 if(zip_outoff < zip_outcnt) { 840 i = buff_size - n; 841 if(i > zip_outcnt - zip_outoff) 842 i = zip_outcnt - zip_outoff; 843 // System.arraycopy(outbuf, outoff, buff, off + n, i); 844 for(j = 0; j < i; j++) 845 buff[off + n + j] = zip_outbuf[zip_outoff + j]; 846 zip_outoff += i; 847 n += i; 848 if(zip_outcnt == zip_outoff) 849 zip_outcnt = zip_outoff = 0; 850 } 851 return n; 852} 853 854/* ========================================================================== 855 * Allocate the match buffer, initialize the various tables and save the 856 * location of the internal file attribute (ascii/binary) and method 857 * (DEFLATE/STORE). 858 */ 859var zip_ct_init = function() { 860 var n; // iterates over tree elements 861 var bits; // bit counter 862 var length; // length value 863 var code; // code value 864 var dist; // distance index 865 866 if(zip_static_dtree[0].dl != 0) return; // ct_init already called 867 868 zip_l_desc.dyn_tree = zip_dyn_ltree; 869 zip_l_desc.static_tree = zip_static_ltree; 870 zip_l_desc.extra_bits = zip_extra_lbits;
871 zip_l_desc.extra_base = zip_LITERALS + 1; 872 zip_l_desc.elems = zip_L_CODES; 873 zip_l_desc.max_length = zip_MAX_BITS; 874 zip_l_desc.max_code = 0; 875 876 zip_d_desc.dyn_tree = zip_dyn_dtree; 877 zip_d_desc.static_tree = zip_static_dtree; 878 zip_d_desc.extra_bits = zip_extra_dbits; 879 zip_d_desc.extra_base = 0; 880 zip_d_desc.elems = zip_D_CODES; 881 zip_d_desc.max_length = zip_MAX_BITS; 882 zip_d_desc.max_code = 0; 883 884 zip_bl_desc.dyn_tree = zip_bl_tree; 885 zip_bl_desc.static_tree = null; 886 zip_bl_desc.extra_bits = zip_extra_blbits; 887 zip_bl_desc.extra_base = 0; 888 zip_bl_desc.elems = zip_BL_CODES; 889 zip_bl_desc.max_length = zip_MAX_BL_BITS; 890 zip_bl_desc.max_code = 0; 891 892 // Initialize the mapping length (0..255) -> length code (0..28) 893 length = 0; 894 for(code = 0; code < zip_LENGTH_CODES-1; code++) { 895 zip_base_length[code] = length; 896 for(n = 0; n < (1<<zip_extra_lbits[code]); n++) 897 zip_length_code[length++] = code; 898 } 899 // Assert (length == 256, "ct_init: length != 256"); 900 901 /* Note that the length 255 (match length 258) can be represented 902 * in two different ways: code 284 + 5 bits or code 285, so we 903 * overwrite length_code[255] to use the best encoding: 904 */ 905 zip_length_code[length-1] = code; 906 907 /* Initialize the mapping dist (0..32K) -> dist code (0..29) */ 908 dist = 0; 909 for(code = 0 ; code < 16; code++) { 910 zip_base_dist[code] = dist; 911 for(n = 0; n < (1<<zip_extra_dbits[code]); n++) { 912 zip_dist_code[dist++] = code; 913 } 914 } 915 // Assert (dist == 256, "ct_init: dist != 256"); 916 dist >>= 7; // from now on, all distances are divided by 128 917 for( ; code < zip_D_CODES; code++) { 918 zip_base_dist[code] = dist << 7; 919 for(n = 0; n < (1<<(zip_extra_dbits[code]-7)); n++) 920 zip_dist_code[256 + dist++] = code; 921 } 922 // Assert (dist == 256, "ct_init: 256+dist != 512"); 923 924 // Construct the codes of the static literal tree 925 for(bits = 0; bits <= zip_MAX_BITS; bits++) 926 zip_bl_count[bits] = 0; 927 n = 0; 928 while(n <= 143) { zip_static_ltree[n++].dl = 8; zip_bl_count[8]++; } 929 while(n <= 255) { zip_static_ltree[n++].dl = 9; zip_bl_count[9]++; } 930 while(n <= 279) { zip_static_ltree[n++].dl = 7; zip_bl_count[7]++; } 931 while(n <= 287) { zip_static_ltree[n++].dl = 8; zip_bl_count[8]++; } 932 /* Codes 286 and 287 do not exist, but we must include them in the 933 * tree construction to get a canonical Huffman tree (longest code 934 * all ones) 935 */ 936 zip_gen_codes(zip_static_ltree, zip_L_CODES + 1); 937 938 /* The static distance tree is trivial: */ 939 for(n = 0; n < zip_D_CODES; n++) { 940 zip_static_dtree[n].dl = 5; 941 zip_static_dtree[n].fc = zip_bi_reverse(n, 5); 942 } 943 944 // Initialize the first block of the first file: 945 zip_init_block(); 946} 947 948/* ========================================================================== 949 * Initialize a new block. 950 */ 951var zip_init_block = function() { 952 var n; // iterates over tree elements 953 954 // Initialize the trees. 955 for(n = 0; n < zip_L_CODES; n++) zip_dyn_ltree[n].fc = 0; 956 for(n = 0; n < zip_D_CODES; n++) zip_dyn_dtree[n].fc = 0; 957 for(n = 0; n < zip_BL_CODES; n++) zip_bl_tree[n].fc = 0; 958 959 zip_dyn_ltree[zip_END_BLOCK].fc = 1; 960 zip_opt_len = zip_static_len = 0; 961 zip_last_lit = zip_last_dist = zip_last_flags = 0; 962 zip_flags = 0; 963 zip_flag_bit = 1; 964} 965 966/* ========================================================================== 967 * Restore the heap property by moving down the tree starting at node k, 968 * exchanging a node with the smallest of its two sons if necessary, stopping 969 * when the heap property is re-established (each father smaller than its 970 * two sons). 971 */ 972var zip_pqdownheap = function( 973 tree, // the tree to restore 974 k) { // node to move down 975 var v = zip_heap[k]; 976 var j = k << 1; // left son of k 977 978 while(j <= zip_heap_len) { 979 // Set j to the smallest of the two sons: 980 if(j < zip_heap_len && 981 zip_SMALLER(tree, zip_heap[j + 1], zip_heap[j])) 982 j++; 983 984 // Exit if v is smaller than both sons 985 if(zip_SMALLER(tree, v, zip_heap[j])) 986 break; 987 988 // Exchange v with the smallest son 989 zip_heap[k] = zip_heap[j]; 990 k = j; 991 992 // And continue down the tree, setting j to the left son of k 993 j <<= 1; 994 } 995 zip_heap[k] = v; 996} 997
998/* ========================================================================== 999 * Compute the optimal bit lengths for a tree and update the total bit length 1000 * for the current block. 1001 * IN assertion: the fields freq and dad are set, heap[heap_max] and 1002 * above are the tree nodes sorted by increasing frequency. 1003 * OUT assertions: the field len is set to the optimal bit length, the 1004 * array bl_count contains the frequencies for each bit length. 1005 * The length opt_len is updated; static_len is also updated if stree is 1006 * not null. 1007 */ 1008var zip_gen_bitlen = function(desc) { // the tree descriptor 1009 var tree = desc.dyn_tree; 1010 var extra = desc.extra_bits; 1011 var base = desc.extra_base; 1012 var max_code = desc.max_code; 1013 var max_length = desc.max_length; 1014 var stree = desc.static_tree; 1015 var h; // heap index 1016 var n, m; // iterate over the tree elements 1017 var bits; // bit length 1018 var xbits; // extra bits 1019 var f; // frequency 1020 var overflow = 0; // number of elements with bit length too large 1021 1022 for(bits = 0; bits <= zip_MAX_BITS; bits++) 1023 zip_bl_count[bits] = 0; 1024 1025 /* In a first pass, compute the optimal bit lengths (which may 1026 * overflow in the case of the bit length tree). 1027 */ 1028 tree[zip_heap[zip_heap_max]].dl = 0; // root of the heap 1029 1030 for(h = zip_heap_max + 1; h < zip_HEAP_SIZE; h++) { 1031 n = zip_heap[h]; 1032 bits = tree[tree[n].dl].dl + 1; 1033 if(bits > max_length) { 1034 bits = max_length; 1035 overflow++; 1036 } 1037 tree[n].dl = bits; 1038 // We overwrite tree[n].dl which is no longer needed 1039 1040 if(n > max_code) 1041 continue; // not a leaf node 1042 1043 zip_bl_count[bits]++; 1044 xbits = 0; 1045 if(n >= base) 1046 xbits = extra[n - base]; 1047 f = tree[n].fc; 1048 zip_opt_len += f * (bits + xbits); 1049 if(stree != null) 1050 zip_static_len += f * (stree[n].dl + xbits); 1051 } 1052 if(overflow == 0) 1053 return; 1054 1055 // This happens for example on obj2 and pic of the Calgary corpus 1056 1057 // Find the first bit length which could increase: 1058 do { 1059 bits = max_length - 1; 1060 while(zip_bl_count[bits] == 0) 1061 bits--; 1062 zip_bl_count[bits]--; // move one leaf down the tree 1063 zip_bl_count[bits + 1] += 2; // move one overflow item as its brother 1064 zip_bl_count[max_length]--; 1065 /* The brother of the overflow item also moves one step up, 1066 * but this does not affect bl_count[max_length] 1067 */ 1068 overflow -= 2; 1069 } while(overflow > 0); 1070 1071 /* Now recompute all bit lengths, scanning in increasing frequency. 1072 * h is still equal to HEAP_SIZE. (It is simpler to reconstruct all 1073 * lengths instead of fixing only the wrong ones. This idea is taken 1074 * from 'ar' written by Haruhiko Okumura.) 1075 */ 1076 for(bits = max_length; bits != 0; bits--) { 1077 n = zip_bl_count[bits]; 1078 while(n != 0) { 1079 m = zip_heap[--h]; 1080 if(m > max_code) 1081 continue; 1082 if(tree[m].dl != bits) { 1083 zip_opt_len += (bits - tree[m].dl) * tree[m].fc; 1084 tree[m].fc = bits; 1085 } 1086 n--; 1087 } 1088 } 1089} 1090 1091 /* ========================================================================== 1092 * Generate the codes for a given tree and bit counts (which need not be 1093 * optimal). 1094 * IN assertion: the array bl_count contains the bit length statistics for 1095 * the given tree and the field len is set for all tree elements. 1096 * OUT assertion: the field code is set for all tree elements of non 1097 * zero code length. 1098 */ 1099var zip_gen_codes = function(tree, // the tree to decorate 1100 max_code) { // largest code with non zero frequency 1101 var next_code = new Array(zip_MAX_BITS+1); // next code value for each bit length 1102 var code = 0; // running code value 1103 var bits; // bit index 1104 var n; // code index 1105 1106 /* The distribution counts are first used to generate the code values 1107 * without bit reversal. 1108 */ 1109 for(bits = 1; bits <= zip_MAX_BITS; bits++) { 1110 code = ((code + zip_bl_count[bits-1]) << 1); 1111 next_code[bits] = code; 1112 } 1113 1114 /* Check that the bit counts in bl_count are consistent. The last code 1115 * must be all ones. 1116 */ 1117// Assert (code + encoder->bl_count[MAX_BITS]-1 == (1<<MAX_BITS)-1, 1118// "inconsistent bit counts"); 1119// Tracev((stderr,"\ngen_codes: max_code %d ", max_code)); 1120 1121 for(n = 0; n <= max_code; n++) { 1122 var len = tree[n].dl; 1123 if(len == 0) 1124 continue; 1125 // Now reverse the bits 1126 tree[n].fc = zip_bi_reverse(next_code[len]++, len); 1127 1128// Tracec(tree != static_ltree, (stderr,"\nn %3d %c l %2d c %4x (%x) ", 1129// n, (isgraph(n) ? n : ' '), len, tree[n].fc, next_code[len]-1)); 1130 } 1131} 1132 1133/* ========================================================================== 1134 * Construct one Huffman tree and assigns the code bit strings and lengths. 1135 * Update the total bit length for the current block. 1136 * IN assertion: the field freq is set for all tree elements. 1137 * OUT assertions: the fields len and code are set to the optimal bit length 1138 * and corresponding code. The length opt_len is updated; static_len is 1139 * also updated if stree is not null. The field max_code is set. 1140 */ 1141var zip_build_tree = function(desc) { // the tree descriptor 1142 var tree = desc.dyn_tree; 1143 var stree = desc.static_tree; 1144 var elems = desc.elems; 1145 var n, m; // iterate over heap elements 1146 var max_code = -1; // largest code with non zero frequency 1147 var node = elems; // next internal node of the tree 1148 1149 /* Construct the initial heap, with least frequent element in 1150 * heap[SMALLEST]. The sons of heap[n] are heap[2*n] and heap[2*n+1]. 1151 * heap[0] is not used. 1152 */ 1153 zip_heap_len = 0; 1154 zip_heap_max = zip_HEAP_SIZE; 1155 1156 for(n = 0; n < elems; n++) { 1157 if(tree[n].fc != 0) { 1158 zip_heap[++zip_heap_len] = max_code = n; 1159 zip_depth[n] = 0; 1160 } else 1161 tree[n].dl = 0; 1162 } 1163 1164 /* The pkzip format requires that at least one distance code exists, 1165 * and that at least one bit should be sent even if there is only one 1166 * possible code. So to avoid special checks later on we force at least 1167 * two codes of non zero frequency. 1168 */ 1169 while(zip_heap_len < 2) { 1170 var xnew = zip_heap[++zip_heap_len] = (max_code < 2 ? ++max_code : 0); 1171 tree[xnew].fc = 1; 1172 zip_depth[xnew] = 0; 1173 zip_opt_len--; 1174 if(stree != null) 1175 zip_static_len -= stree[xnew].dl; 1176 // new is 0 or 1 so it does not have extra bits 1177 } 1178 desc.max_code = max_code; 1179 1180 /* The elements heap[heap_len/2+1 .. heap_len] are leaves of the tree, 1181 * establish sub-heaps of increasing lengths: 1182 */ 1183 for(n = zip_heap_len >> 1; n >= 1; n--) 1184 zip_pqdownheap(tree, n); 1185 1186 /* Construct the Huffman tree by repeatedly combining the least two 1187 * frequent nodes. 1188 */ 1189 do { 1190 n = zip_heap[zip_SMALLEST]; 1191 zip_heap[zip_SMALLEST] = zip_heap[zip_heap_len--]; 1192 zip_pqdownheap(tree, zip_SMALLEST); 1193 1194 m = zip_heap[zip_SMALLEST]; // m = node of next least frequency 1195 1196 // keep the nodes sorted by frequency 1197 zip_heap[--zip_heap_max] = n; 1198 zip_heap[--zip_heap_max] = m; 1199 1200 // Create a new node father of n and m 1201 tree[node].fc = tree[n].fc + tree[m].fc; 1202// depth[node] = (char)(MAX(depth[n], depth[m]) + 1); 1203 if(zip_depth[n] > zip_depth[m] + 1) 1204 zip_depth[node] = zip_depth[n]; 1205 else 1206 zip_depth[node] = zip_depth[m] + 1; 1207 tree[n].dl = tree[m].dl = node; 1208 1209 // and insert the new node in the heap 1210 zip_heap[zip_SMALLEST] = node++; 1211 zip_pqdownheap(tree, zip_SMALLEST); 1212 1213 } while(zip_heap_len >= 2); 1214 1215 zip_heap[--zip_heap_max] = zip_heap[zip_SMALLEST]; 1216 1217 /* At this point, the fields freq and dad are set. We can now 1218 * generate the bit lengths. 1219 */ 1220 zip_gen_bitlen(desc); 1221 1222 // The field len is now set, we can generate the bit codes 1223 zip_gen_codes(tree, max_code); 1224} 1225 1226/* ========================================================================== 1227 * Scan a literal or distance tree to determine the frequencies of the codes 1228 * in the bit length tree. Updates opt_len to take into account the repeat 1229 * counts. (The contribution of the bit length codes will be added later 1230 * during the construction of bl_tree.) 1231 */ 1232var zip_scan_tree = function(tree,// the tree to be scanned 1233 max_code) { // and its largest code of non zero frequency 1234 var n; // iterates over all tree elements 1235 var prevlen = -1; // last emitted length 1236 var curlen; // length of current code 1237 var nextlen = tree[0].dl; // length of next code 1238 var count = 0; // repeat count of the current code 1239 var max_count = 7; // max repeat count 1240 var min_count = 4; // min repeat count 1241 1242 if(nextlen == 0) { 1243 max_count = 138; 1244 min_count = 3; 1245 } 1246 tree[max_code + 1].dl = 0xffff; // guard 1247 1248 for(n = 0; n <= max_code; n++) { 1249 curlen = nextlen; 1250 nextlen = tree[n + 1].dl; 1251 if(++count < max_count && curlen == nextlen) 1252 continue; 1253 else if(count < min_count) 1254 zip_bl_tree[curlen].fc += count; 1255 else if(curlen != 0) { 1256 if(curlen != prevlen) 1257 zip_bl_tree[curlen].fc++; 1258 zip_bl_tree[zip_REP_3_6].fc++; 1259 } else if(count <= 10) 1260 zip_bl_tree[zip_REPZ_3_10].fc++; 1261 else 1262 zip_bl_tree[zip_REPZ_11_138].fc++; 1263 count = 0; prevlen = curlen; 1264 if(nextlen == 0) { 1265 max_count = 138; 1266 min_count = 3; 1267 } else if(curlen == nextlen) { 1268 max_count = 6; 1269 min_count = 3; 1270 } else { 1271 max_count = 7; 1272 min_count = 4; 1273 } 1274 } 1275} 1276 1277 /* ========================================================================== 1278 * Send a literal or distance tree in compressed form, using the codes in 1279 * bl_tree. 1280 */ 1281var zip_send_tree = function(tree, // the tree to be scanned 1282 max_code) { // and its largest code of non zero frequency 1283 var n; // iterates over all tree elements 1284 var prevlen = -1; // last emitted length 1285 var curlen; // length of current code 1286 var nextlen = tree[0].dl; // length of next code 1287 var count = 0; // repeat count of the current code 1288 var max_count = 7; // max repeat count 1289 var min_count = 4; // min repeat count 1290 1291 /* tree[max_code+1].dl = -1; */ /* guard already set */ 1292 if(nextlen == 0) { 1293 max_count = 138; 1294 min_count = 3; 1295 } 1296 1297 for(n = 0; n <= max_code; n++) { 1298 curlen = nextlen; 1299 nextlen = tree[n+1].dl; 1300 if(++count < max_count && curlen == nextlen) { 1301 continue; 1302 } else if(count < min_count) { 1303 do { zip_SEND_CODE(curlen, zip_bl_tree); } while(--count != 0); 1304 } else if(curlen != 0) { 1305 if(curlen != prevlen) { 1306 zip_SEND_CODE(curlen, zip_bl_tree); 1307 count--; 1308 } 1309 // Assert(count >= 3 && count <= 6, " 3_6?"); 1310 zip_SEND_CODE(zip_REP_3_6, zip_bl_tree); 1311 zip_send_bits(count - 3, 2); 1312 } else if(count <= 10) { 1313 zip_SEND_CODE(zip_REPZ_3_10, zip_bl_tree); 1314 zip_send_bits(count-3, 3); 1315 } else { 1316 zip_SEND_CODE(zip_REPZ_11_138, zip_bl_tree); 1317 zip_send_bits(count-11, 7); 1318 } 1319 count = 0; 1320 prevlen = curlen; 1321 if(nextlen == 0) { 1322 max_count = 138; 1323 min_count = 3; 1324 } else if(curlen == nextlen) { 1325 max_count = 6; 1326 min_count = 3; 1327 } else { 1328 max_count = 7; 1329 min_count = 4; 1330 } 1331 } 1332} 1333 1334/* ========================================================================== 1335 * Construct the Huffman tree for the bit lengths and return the index in 1336 * bl_order of the last bit length code to send. 1337 */ 1338var zip_build_bl_tree = function() { 1339 var max_blindex; // index of last bit length code of non zero freq 1340 1341 // Determine the bit length frequencies for literal and distance trees 1342 zip_scan_tree(zip_dyn_ltree, zip_l_desc.max_code); 1343 zip_scan_tree(zip_dyn_dtree, zip_d_desc.max_code); 1344 1345 // Build the bit length tree: 1346 zip_build_tree(zip_bl_desc); 1347 /* opt_len now includes the length of the tree representations, except 1348 * the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 1349 */ 1350 1351 /* Determine the number of bit length codes to send. The pkzip format 1352 * requires that at least 4 bit length codes be sent. (appnote.txt says 1353 * 3 but the actual value used is 4.) 1354 */ 1355 for(max_blindex = zip_BL_CODES-1; max_blindex >= 3; max_blindex--) { 1356 if(zip_bl_tree[zip_bl_order[max_blindex]].dl != 0) break; 1357 }
1358 /* Update opt_len to include the bit length tree and counts */ 1359 zip_opt_len += 3*(max_blindex+1) + 5+5+4; 1360// Tracev((stderr, "\ndyn trees: dyn %ld, stat %ld", 1361// encoder->opt_len, encoder->static_len)); 1362 1363 return max_blindex; 1364} 1365 1366/* ========================================================================== 1367 * Send the header for a block using dynamic Huffman trees: the counts, the 1368 * lengths of the bit length codes, the literal tree and the distance tree. 1369 * IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. 1370 */ 1371var zip_send_all_trees = function(lcodes, dcodes, blcodes) { // number of codes for each tree 1372 var rank; // index in bl_order 1373 1374// Assert (lcodes >= 257 && dcodes >= 1 && blcodes >= 4, "not enough codes"); 1375// Assert (lcodes <= L_CODES && dcodes <= D_CODES && blcodes <= BL_CODES, 1376// "too many codes"); 1377// Tracev((stderr, "\nbl counts: ")); 1378 zip_send_bits(lcodes-257, 5); // not +255 as stated in appnote.txt 1379 zip_send_bits(dcodes-1, 5); 1380 zip_send_bits(blcodes-4, 4); // not -3 as stated in appnote.txt 1381 for(rank = 0; rank < blcodes; rank++) { 1382// Tracev((stderr, "\nbl code %2d ", bl_order[rank])); 1383 zip_send_bits(zip_bl_tree[zip_bl_order[rank]].dl, 3); 1384 } 1385 1386 // send the literal tree 1387 zip_send_tree(zip_dyn_ltree,lcodes-1); 1388 1389 // send the distance tree 1390 zip_send_tree(zip_dyn_dtree,dcodes-1); 1391} 1392 1393/* ========================================================================== 1394 * Determine the best encoding for the current block: dynamic trees, static 1395 * trees or store, and output the encoded block to the zip file. 1396 */ 1397var zip_flush_block = function(eof) { // true if this is the last block for a file 1398 var opt_lenb, static_lenb; // opt_len and static_len in bytes 1399 var max_blindex; // index of last bit length code of non zero freq 1400 var stored_len; // length of input block 1401 1402 stored_len = zip_strstart - zip_block_start; 1403 zip_flag_buf[zip_last_flags] = zip_flags; // Save the flags for the last 8 items 1404 1405 // Construct the literal and distance trees 1406 zip_build_tree(zip_l_desc); 1407// Tracev((stderr, "\nlit data: dyn %ld, stat %ld", 1408// encoder->opt_len, encoder->static_len)); 1409 1410 zip_build_tree(zip_d_desc); 1411// Tracev((stderr, "\ndist data: dyn %ld, stat %ld", 1412// encoder->opt_len, encoder->static_len)); 1413 /* At this point, opt_len and static_len are the total bit lengths of 1414 * the compressed block data, excluding the tree representations. 1415 */ 1416 1417 /* Build the bit length tree for the above two trees, and get the index 1418 * in bl_order of the last bit length code to send. 1419 */ 1420 max_blindex = zip_build_bl_tree(); 1421 1422 // Determine the best encoding. Compute first the block length in bytes 1423 opt_lenb = (zip_opt_len +3+7)>>3; 1424 static_lenb = (zip_static_len+3+7)>>3; 1425 1426// Trace((stderr, "\nopt %lu(%lu) stat %lu(%lu) stored %lu lit %u dist %u ", 1427// opt_lenb, encoder->opt_len, 1428// static_lenb, encoder->static_len, stored_len, 1429// encoder->last_lit, encoder->last_dist)); 1430 1431 if(static_lenb <= opt_lenb) 1432 opt_lenb = static_lenb; 1433 if(stored_len + 4 <= opt_lenb // 4: two words for the lengths 1434 && zip_block_start >= 0) { 1435 var i; 1436 1437 /* The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 1438 * Otherwise we can't have processed more than WSIZE input bytes since 1439 * the last block flush, because compression would have been 1440 * successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 1441 * transform a block into a stored block. 1442 */ 1443 zip_send_bits((zip_STORED_BLOCK<<1)+eof, 3); /* send block type */ 1444 zip_bi_windup(); /* align on byte boundary */ 1445 zip_put_short(stored_len); 1446 zip_put_short(~stored_len); 1447 1448 // copy block 1449/* 1450 p = &window[block_start]; 1451 for(i = 0; i < stored_len; i++) 1452 put_byte(p[i]); 1453*/ 1454 for(i = 0; i < stored_len; i++) 1455 zip_put_byte(zip_window[zip_block_start + i]); 1456 1457 } else if(static_lenb == opt_lenb) { 1458 zip_send_bits((zip_STATIC_TREES<<1)+eof, 3); 1459 zip_compress_block(zip_static_ltree, zip_static_dtree); 1460 } else { 1461 zip_send_bits((zip_DYN_TREES<<1)+eof, 3); 1462 zip_send_all_trees(zip_l_desc.max_code+1, 1463 zip_d_desc.max_code+1, 1464 max_blindex+1); 1465 zip_compress_block(zip_dyn_ltree, zip_dyn_dtree); 1466 } 1467 1468 zip_init_block(); 1469 1470 if(eof != 0) 1471 zip_bi_windup(); 1472} 1473 1474/* ========================================================================== 1475 * Save the match info and tally the frequency counts. Return true if 1476 * the current block must be flushed. 1477 */ 1478var zip_ct_tally = function( 1479 dist, // distance of matched string
1480 lc) { // match length-MIN_MATCH or unmatched char (if dist==0) 1481 zip_l_buf[zip_last_lit++] = lc; 1482 if(dist == 0) { 1483 // lc is the unmatched char 1484 zip_dyn_ltree[lc].fc++; 1485 } else { 1486 // Here, lc is the match length - MIN_MATCH 1487 dist--; // dist = match distance - 1 1488// Assert((ush)dist < (ush)MAX_DIST && 1489// (ush)lc <= (ush)(MAX_MATCH-MIN_MATCH) && 1490// (ush)D_CODE(dist) < (ush)D_CODES, "ct_tally: bad match"); 1491 1492 zip_dyn_ltree[zip_length_code[lc]+zip_LITERALS+1].fc++; 1493 zip_dyn_dtree[zip_D_CODE(dist)].fc++; 1494 1495 zip_d_buf[zip_last_dist++] = dist; 1496 zip_flags |= zip_flag_bit; 1497 } 1498 zip_flag_bit <<= 1; 1499 1500 // Output the flags if they fill a byte 1501 if((zip_last_lit & 7) == 0) { 1502 zip_flag_buf[zip_last_flags++] = zip_flags; 1503 zip_flags = 0; 1504 zip_flag_bit = 1; 1505 } 1506 // Try to guess if it is profitable to stop the current block here 1507 if(zip_compr_level > 2 && (zip_last_lit & 0xfff) == 0) { 1508 // Compute an upper bound for the compressed length 1509 var out_length = zip_last_lit * 8; 1510 var in_length = zip_strstart - zip_block_start; 1511 var dcode; 1512 1513 for(dcode = 0; dcode < zip_D_CODES; dcode++) { 1514 out_length += zip_dyn_dtree[dcode].fc * (5 + zip_extra_dbits[dcode]); 1515 } 1516 out_length >>= 3; 1517// Trace((stderr,"\nlast_lit %u, last_dist %u, in %ld, out ~%ld(%ld%%) ", 1518// encoder->last_lit, encoder->last_dist, in_length, out_length, 1519// 100L - out_length*100L/in_length)); 1520 if(zip_last_dist < parseInt(zip_last_lit/2) && 1521 out_length < parseInt(in_length/2)) 1522 return true; 1523 } 1524 return (zip_last_lit == zip_LIT_BUFSIZE-1 || 1525 zip_last_dist == zip_DIST_BUFSIZE); 1526 /* We avoid equality with LIT_BUFSIZE because of wraparound at 64K 1527 * on 16 bit machines and because stored blocks are restricted to 1528 * 64K-1 bytes. 1529 */ 1530} 1531 1532 /* ========================================================================== 1533 * Send the block data compressed using the given Huffman trees 1534 */ 1535var zip_compress_block = function( 1536 ltree, // literal tree 1537 dtree) { // distance tree 1538 var dist; // distance of matched string 1539 var lc; // match length or unmatched char (if dist == 0) 1540 var lx = 0; // running index in l_buf 1541 var dx = 0; // running index in d_buf 1542 var fx = 0; // running index in flag_buf 1543 var flag = 0; // current flags 1544 var code; // the code to send 1545 var extra; // number of extra bits to send 1546 1547 if(zip_last_lit != 0) do { 1548 if((lx & 7) == 0) 1549 flag = zip_flag_buf[fx++]; 1550 lc = zip_l_buf[lx++] & 0xff; 1551 if((flag & 1) == 0) { 1552 zip_SEND_CODE(lc, ltree); /* send a literal byte */ 1553// Tracecv(isgraph(lc), (stderr," '%c' ", lc)); 1554 } else { 1555 // Here, lc is the match length - MIN_MATCH 1556 code = zip_length_code[lc]; 1557 zip_SEND_CODE(code+zip_LITERALS+1, ltree); // send the length code 1558 extra = zip_extra_lbits[code]; 1559 if(extra != 0) { 1560 lc -= zip_base_length[code]; 1561 zip_send_bits(lc, extra); // send the extra length bits 1562 } 1563 dist = zip_d_buf[dx++]; 1564 // Here, dist is the match distance - 1 1565 code = zip_D_CODE(dist); 1566// Assert (code < D_CODES, "bad d_code"); 1567 1568 zip_SEND_CODE(code, dtree); // send the distance code 1569 extra = zip_extra_dbits[code]; 1570 if(extra != 0) { 1571 dist -= zip_base_dist[code]; 1572 zip_send_bits(dist, extra); // send the extra distance bits 1573 } 1574 } // literal or match pair ? 1575 flag >>= 1; 1576 } while(lx < zip_last_lit); 1577 1578 zip_SEND_CODE(zip_END_BLOCK, ltree); 1579} 1580 1581/* ========================================================================== 1582 * Send a value on a given number of bits. 1583 * IN assertion: length <= 16 and value fits in length bits. 1584 */ 1585var zip_Buf_size = 16; // bit size of bi_buf 1586var zip_send_bits = function( 1587 value, // value to send 1588 length) { // number of bits 1589 /* If not enough room in bi_buf, use (valid) bits from bi_buf and 1590 * (16 - bi_valid) bits from value, leaving (width - (16-bi_valid)) 1591 * unused bits in value. 1592 */ 1593 if(zip_bi_valid > zip_Buf_size - length) { 1594 zip_bi_buf |= (value << zip_bi_valid); 1595 zip_put_short(zip_bi_buf); 1596 zip_bi_buf = (value >>
1596 (zip_Buf_size - zip_bi_valid)); 1597 zip_bi_valid += length - zip_Buf_size; 1598 } else { 1599 zip_bi_buf |= value << zip_bi_valid; 1600 zip_bi_valid += length; 1601 } 1602} 1603 1604/* ========================================================================== 1605 * Reverse the first len bits of a code, using straightforward code (a faster 1606 * method would use a table) 1607 * IN assertion: 1 <= len <= 15 1608 */ 1609var zip_bi_reverse = function( 1610 code, // the value to invert 1611 len) { // its bit length 1612 var res = 0; 1613 do { 1614 res |= code & 1; 1615 code >>= 1; 1616 res <<= 1; 1617 } while(--len > 0); 1618 return res >> 1; 1619} 1620 1621/* ========================================================================== 1622 * Write out any remaining bits in an incomplete byte. 1623 */ 1624var zip_bi_windup = function() { 1625 if(zip_bi_valid > 8) { 1626 zip_put_short(zip_bi_buf); 1627 } else if(zip_bi_valid > 0) { 1628 zip_put_byte(zip_bi_buf); 1629 } 1630 zip_bi_buf = 0; 1631 zip_bi_valid = 0; 1632} 1633 1634var zip_qoutbuf = function() { 1635 if(zip_outcnt != 0) { 1636 var q, i; 1637 q = zip_new_queue(); 1638 if(zip_qhead == null) 1639 zip_qhead = zip_qtail = q; 1640 else 1641 zip_qtail = zip_qtail.next = q; 1642 q.len = zip_outcnt - zip_outoff; 1643// System.arraycopy(zip_outbuf, zip_outoff, q.ptr, 0, q.len); 1644 for(i = 0; i < q.len; i++) 1645 q.ptr[i] = zip_outbuf[zip_outoff + i]; 1646 zip_outcnt = zip_outoff = 0; 1647 } 1648} 1649 1650var zip_deflate = function(str, level) { 1651 var i, j; 1652 1653 zip_deflate_data = str; 1654 zip_deflate_pos = 0; 1655 if(typeof level == "undefined") 1656 level = zip_DEFAULT_LEVEL; 1657 zip_deflate_start(level); 1658 1659 var buff = new Array(1024); 1660 var aout = []; 1661 while((i = zip_deflate_internal(buff, 0, buff.length)) > 0) { 1662 var cbuf = new Array(i); 1663 for(j = 0; j < i; j++){ 1664 cbuf[j] = String.fromCharCode(buff[j]); 1665 } 1666 aout[aout.length] = cbuf.join(""); 1667 } 1668 zip_deflate_data = null; // G.C. 1669 return aout.join(""); 1670} 1671 1672if (! ctx.RawDeflate) ctx.RawDeflate = {}; 1673ctx.RawDeflate.deflate = zip_deflate; 1674 1675})(this);
Line numbers count LF bytes from the start of the resource, as the search results do. Vendor segments are library code the classifier recognised; they are stored but not indexed. Bytes are shown as Latin1 characters, one per byte.