1 /* -*-mode:java; c-basic-offset:2; -*- */ 2 /* 3 Copyright (c) 2000-2011 ymnk, JCraft,Inc. All rights reserved. 4 5 Redistribution and use in source and binary forms, with or without 6 modification, are permitted provided that the following conditions are met: 7 8 1. Redistributions of source code must retain the above copyright notice, 9 this list of conditions and the following disclaimer. 10 11 2. Redistributions in binary form must reproduce the above copyright 12 notice, this list of conditions and the following disclaimer in 13 the documentation and/or other materials provided with the distribution. 14 15 3. The names of the authors may not be used to endorse or promote products 16 derived from this software without specific prior written permission. 17 18 THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, 19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND 20 FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT, 21 INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT, 22 INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, 24 OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 25 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 26 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, 27 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 /* 30 * This program is based on zlib-1.1.3, so all credit should go authors 31 * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu) 32 * and contributors of zlib. 33 */ 34 35 package com.jcraft.jzlib; 36 37 public 38 final class Deflate implements Cloneable { 39 40 static final private int MAX_MEM_LEVEL=9; 41 42 static final private int Z_DEFAULT_COMPRESSION=-1; 43 44 static final private int MAX_WBITS=15; // 32K LZ77 window 45 static final private int DEF_MEM_LEVEL=8; 46 47 static class Config{ 48 int good_length; // reduce lazy search above this match length 49 int max_lazy; // do not perform lazy search above this match length 50 int nice_length; // quit search above this match length 51 int max_chain; 52 int func; Config(int good_length, int max_lazy, int nice_length, int max_chain, int func)53 Config(int good_length, int max_lazy, 54 int nice_length, int max_chain, int func){ 55 this.good_length=good_length; 56 this.max_lazy=max_lazy; 57 this.nice_length=nice_length; 58 this.max_chain=max_chain; 59 this.func=func; 60 } 61 } 62 63 static final private int STORED=0; 64 static final private int FAST=1; 65 static final private int SLOW=2; 66 static final private Config[] config_table; 67 static{ 68 config_table=new Config[10]; 69 // good lazy nice chain 70 config_table[0]=new Config(0, 0, 0, 0, STORED); 71 config_table[1]=new Config(4, 4, 8, 4, FAST); 72 config_table[2]=new Config(4, 5, 16, 8, FAST); 73 config_table[3]=new Config(4, 6, 32, 32, FAST); 74 75 config_table[4]=new Config(4, 4, 16, 16, SLOW); 76 config_table[5]=new Config(8, 16, 32, 32, SLOW); 77 config_table[6]=new Config(8, 16, 128, 128, SLOW); 78 config_table[7]=new Config(8, 32, 128, 256, SLOW); 79 config_table[8]=new Config(32, 128, 258, 1024, SLOW); 80 config_table[9]=new Config(32, 258, 258, 4096, SLOW); 81 } 82 83 static final private String[] z_errmsg = { 84 "need dictionary", // Z_NEED_DICT 2 85 "stream end", // Z_STREAM_END 1 86 "", // Z_OK 0 87 "file error", // Z_ERRNO (-1) 88 "stream error", // Z_STREAM_ERROR (-2) 89 "data error", // Z_DATA_ERROR (-3) 90 "insufficient memory", // Z_MEM_ERROR (-4) 91 "buffer error", // Z_BUF_ERROR (-5) 92 "incompatible version",// Z_VERSION_ERROR (-6) 93 "" 94 }; 95 96 // block not completed, need more input or more output 97 static final private int NeedMore=0; 98 99 // block flush performed 100 static final private int BlockDone=1; 101 102 // finish started, need only more output at next deflate 103 static final private int FinishStarted=2; 104 105 // finish done, accept no more input or output 106 static final private int FinishDone=3; 107 108 // preset dictionary flag in zlib header 109 static final private int PRESET_DICT=0x20; 110 111 static final private int Z_FILTERED=1; 112 static final private int Z_HUFFMAN_ONLY=2; 113 static final private int Z_DEFAULT_STRATEGY=0; 114 115 static final private int Z_NO_FLUSH=0; 116 static final private int Z_PARTIAL_FLUSH=1; 117 static final private int Z_SYNC_FLUSH=2; 118 static final private int Z_FULL_FLUSH=3; 119 static final private int Z_FINISH=4; 120 121 static final private int Z_OK=0; 122 static final private int Z_STREAM_END=1; 123 static final private int Z_NEED_DICT=2; 124 static final private int Z_ERRNO=-1; 125 static final private int Z_STREAM_ERROR=-2; 126 static final private int Z_DATA_ERROR=-3; 127 static final private int Z_MEM_ERROR=-4; 128 static final private int Z_BUF_ERROR=-5; 129 static final private int Z_VERSION_ERROR=-6; 130 131 static final private int INIT_STATE=42; 132 static final private int BUSY_STATE=113; 133 static final private int FINISH_STATE=666; 134 135 // The deflate compression method 136 static final private int Z_DEFLATED=8; 137 138 static final private int STORED_BLOCK=0; 139 static final private int STATIC_TREES=1; 140 static final private int DYN_TREES=2; 141 142 // The three kinds of block type 143 static final private int Z_BINARY=0; 144 static final private int Z_ASCII=1; 145 static final private int Z_UNKNOWN=2; 146 147 static final private int Buf_size=8*2; 148 149 // repeat previous bit length 3-6 times (2 bits of repeat count) 150 static final private int REP_3_6=16; 151 152 // repeat a zero length 3-10 times (3 bits of repeat count) 153 static final private int REPZ_3_10=17; 154 155 // repeat a zero length 11-138 times (7 bits of repeat count) 156 static final private int REPZ_11_138=18; 157 158 static final private int MIN_MATCH=3; 159 static final private int MAX_MATCH=258; 160 static final private int MIN_LOOKAHEAD=(MAX_MATCH+MIN_MATCH+1); 161 162 static final private int MAX_BITS=15; 163 static final private int D_CODES=30; 164 static final private int BL_CODES=19; 165 static final private int LENGTH_CODES=29; 166 static final private int LITERALS=256; 167 static final private int L_CODES=(LITERALS+1+LENGTH_CODES); 168 static final private int HEAP_SIZE=(2*L_CODES+1); 169 170 static final private int END_BLOCK=256; 171 172 ZStream strm; // pointer back to this zlib stream 173 int status; // as the name implies 174 byte[] pending_buf; // output still pending 175 int pending_buf_size; // size of pending_buf 176 int pending_out; // next pending byte to output to the stream 177 int pending; // nb of bytes in the pending buffer 178 int wrap = 1; 179 byte data_type; // UNKNOWN, BINARY or ASCII 180 byte method; // STORED (for zip only) or DEFLATED 181 int last_flush; // value of flush param for previous deflate call 182 183 int w_size; // LZ77 window size (32K by default) 184 int w_bits; // log2(w_size) (8..16) 185 int w_mask; // w_size - 1 186 187 byte[] window; 188 // Sliding window. Input bytes are read into the second half of the window, 189 // and move to the first half later to keep a dictionary of at least wSize 190 // bytes. With this organization, matches are limited to a distance of 191 // wSize-MAX_MATCH bytes, but this ensures that IO is always 192 // performed with a length multiple of the block size. Also, it limits 193 // the window size to 64K, which is quite useful on MSDOS. 194 // To do: use the user input buffer as sliding window. 195 196 int window_size; 197 // Actual size of window: 2*wSize, except when the user input buffer 198 // is directly used as sliding window. 199 200 short[] prev; 201 // Link to older string with same hash index. To limit the size of this 202 // array to 64K, this link is maintained only for the last 32K strings. 203 // An index in this array is thus a window index modulo 32K. 204 205 short[] head; // Heads of the hash chains or NIL. 206 207 int ins_h; // hash index of string to be inserted 208 int hash_size; // number of elements in hash table 209 int hash_bits; // log2(hash_size) 210 int hash_mask; // hash_size-1 211 212 // Number of bits by which ins_h must be shifted at each input 213 // step. It must be such that after MIN_MATCH steps, the oldest 214 // byte no longer takes part in the hash key, that is: 215 // hash_shift * MIN_MATCH >= hash_bits 216 int hash_shift; 217 218 // Window position at the beginning of the current output block. Gets 219 // negative when the window is moved backwards. 220 221 int block_start; 222 223 int match_length; // length of best match 224 int prev_match; // previous match 225 int match_available; // set if previous match exists 226 int strstart; // start of string to insert 227 int match_start; // start of matching string 228 int lookahead; // number of valid bytes ahead in window 229 230 // Length of the best match at previous step. Matches not greater than this 231 // are discarded. This is used in the lazy match evaluation. 232 int prev_length; 233 234 // To speed up deflation, hash chains are never searched beyond this 235 // length. A higher limit improves compression ratio but degrades the speed. 236 int max_chain_length; 237 238 // Attempt to find a better match only when the current match is strictly 239 // smaller than this value. This mechanism is used only for compression 240 // levels >= 4. 241 int max_lazy_match; 242 243 // Insert new strings in the hash table only if the match length is not 244 // greater than this length. This saves time but degrades compression. 245 // max_insert_length is used only for compression levels <= 3. 246 247 int level; // compression level (1..9) 248 int strategy; // favor or force Huffman coding 249 250 // Use a faster search when the previous match is longer than this 251 int good_match; 252 253 // Stop searching when current match exceeds this 254 int nice_match; 255 256 short[] dyn_ltree; // literal and length tree 257 short[] dyn_dtree; // distance tree 258 short[] bl_tree; // Huffman tree for bit lengths 259 260 Tree l_desc=new Tree(); // desc for literal tree 261 Tree d_desc=new Tree(); // desc for distance tree 262 Tree bl_desc=new Tree(); // desc for bit length tree 263 264 // number of codes at each bit length for an optimal tree 265 short[] bl_count=new short[MAX_BITS+1]; 266 267 // heap used to build the Huffman trees 268 int[] heap=new int[2*L_CODES+1]; 269 270 int heap_len; // number of elements in the heap 271 int heap_max; // element of largest frequency 272 // The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used. 273 // The same heap array is used to build all trees. 274 275 // Depth of each subtree used as tie breaker for trees of equal frequency 276 byte[] depth=new byte[2*L_CODES+1]; 277 278 int l_buf; // index for literals or lengths */ 279 280 // Size of match buffer for literals/lengths. There are 4 reasons for 281 // limiting lit_bufsize to 64K: 282 // - frequencies can be kept in 16 bit counters 283 // - if compression is not successful for the first block, all input 284 // data is still in the window so we can still emit a stored block even 285 // when input comes from standard input. (This can also be done for 286 // all blocks if lit_bufsize is not greater than 32K.) 287 // - if compression is not successful for a file smaller than 64K, we can 288 // even emit a stored file instead of a stored block (saving 5 bytes). 289 // This is applicable only for zip (not gzip or zlib). 290 // - creating new Huffman trees less frequently may not provide fast 291 // adaptation to changes in the input data statistics. (Take for 292 // example a binary file with poorly compressible code followed by 293 // a highly compressible string table.) Smaller buffer sizes give 294 // fast adaptation but have of course the overhead of transmitting 295 // trees more frequently. 296 // - I can't count above 4 297 int lit_bufsize; 298 299 int last_lit; // running index in l_buf 300 301 // Buffer for distances. To simplify the code, d_buf and l_buf have 302 // the same number of elements. To use different lengths, an extra flag 303 // array would be necessary. 304 305 int d_buf; // index of pendig_buf 306 307 int opt_len; // bit length of current block with optimal trees 308 int static_len; // bit length of current block with static trees 309 int matches; // number of string matches in current block 310 int last_eob_len; // bit length of EOB code for last block 311 312 // Output buffer. bits are inserted starting at the bottom (least 313 // significant bits). 314 short bi_buf; 315 316 // Number of valid bits in bi_buf. All bits above the last valid bit 317 // are always zero. 318 int bi_valid; 319 320 GZIPHeader gheader = null; 321 Deflate(ZStream strm)322 Deflate(ZStream strm){ 323 this.strm=strm; 324 dyn_ltree=new short[HEAP_SIZE*2]; 325 dyn_dtree=new short[(2*D_CODES+1)*2]; // distance tree 326 bl_tree=new short[(2*BL_CODES+1)*2]; // Huffman tree for bit lengths 327 } 328 lm_init()329 void lm_init() { 330 window_size=2*w_size; 331 332 head[hash_size-1]=0; 333 for(int i=0; i<hash_size-1; i++){ 334 head[i]=0; 335 } 336 337 // Set the default configuration parameters: 338 max_lazy_match = Deflate.config_table[level].max_lazy; 339 good_match = Deflate.config_table[level].good_length; 340 nice_match = Deflate.config_table[level].nice_length; 341 max_chain_length = Deflate.config_table[level].max_chain; 342 343 strstart = 0; 344 block_start = 0; 345 lookahead = 0; 346 match_length = prev_length = MIN_MATCH-1; 347 match_available = 0; 348 ins_h = 0; 349 } 350 351 // Initialize the tree data structures for a new zlib stream. tr_init()352 void tr_init(){ 353 354 l_desc.dyn_tree = dyn_ltree; 355 l_desc.stat_desc = StaticTree.static_l_desc; 356 357 d_desc.dyn_tree = dyn_dtree; 358 d_desc.stat_desc = StaticTree.static_d_desc; 359 360 bl_desc.dyn_tree = bl_tree; 361 bl_desc.stat_desc = StaticTree.static_bl_desc; 362 363 bi_buf = 0; 364 bi_valid = 0; 365 last_eob_len = 8; // enough lookahead for inflate 366 367 // Initialize the first block of the first file: 368 init_block(); 369 } 370 init_block()371 void init_block(){ 372 // Initialize the trees. 373 for(int i = 0; i < L_CODES; i++) dyn_ltree[i*2] = 0; 374 for(int i= 0; i < D_CODES; i++) dyn_dtree[i*2] = 0; 375 for(int i= 0; i < BL_CODES; i++) bl_tree[i*2] = 0; 376 377 dyn_ltree[END_BLOCK*2] = 1; 378 opt_len = static_len = 0; 379 last_lit = matches = 0; 380 } 381 382 // Restore the heap property by moving down the tree starting at node k, 383 // exchanging a node with the smallest of its two sons if necessary, stopping 384 // when the heap property is re-established (each father smaller than its 385 // two sons). pqdownheap(short[] tree, int k )386 void pqdownheap(short[] tree, // the tree to restore 387 int k // node to move down 388 ){ 389 int v = heap[k]; 390 int j = k << 1; // left son of k 391 while (j <= heap_len) { 392 // Set j to the smallest of the two sons: 393 if (j < heap_len && 394 smaller(tree, heap[j+1], heap[j], depth)){ 395 j++; 396 } 397 // Exit if v is smaller than both sons 398 if(smaller(tree, v, heap[j], depth)) break; 399 400 // Exchange v with the smallest son 401 heap[k]=heap[j]; k = j; 402 // And continue down the tree, setting j to the left son of k 403 j <<= 1; 404 } 405 heap[k] = v; 406 } 407 smaller(short[] tree, int n, int m, byte[] depth)408 static boolean smaller(short[] tree, int n, int m, byte[] depth){ 409 short tn2=tree[n*2]; 410 short tm2=tree[m*2]; 411 return (tn2<tm2 || 412 (tn2==tm2 && depth[n] <= depth[m])); 413 } 414 415 // Scan a literal or distance tree to determine the frequencies of the codes 416 // in the bit length tree. scan_tree(short[] tree, int max_code )417 void scan_tree (short[] tree,// the tree to be scanned 418 int max_code // and its largest code of non zero frequency 419 ){ 420 int n; // iterates over all tree elements 421 int prevlen = -1; // last emitted length 422 int curlen; // length of current code 423 int nextlen = tree[0*2+1]; // length of next code 424 int count = 0; // repeat count of the current code 425 int max_count = 7; // max repeat count 426 int min_count = 4; // min repeat count 427 428 if (nextlen == 0){ max_count = 138; min_count = 3; } 429 tree[(max_code+1)*2+1] = (short)0xffff; // guard 430 431 for(n = 0; n <= max_code; n++) { 432 curlen = nextlen; nextlen = tree[(n+1)*2+1]; 433 if(++count < max_count && curlen == nextlen) { 434 continue; 435 } 436 else if(count < min_count) { 437 bl_tree[curlen*2] += count; 438 } 439 else if(curlen != 0) { 440 if(curlen != prevlen) bl_tree[curlen*2]++; 441 bl_tree[REP_3_6*2]++; 442 } 443 else if(count <= 10) { 444 bl_tree[REPZ_3_10*2]++; 445 } 446 else{ 447 bl_tree[REPZ_11_138*2]++; 448 } 449 count = 0; prevlen = curlen; 450 if(nextlen == 0) { 451 max_count = 138; min_count = 3; 452 } 453 else if(curlen == nextlen) { 454 max_count = 6; min_count = 3; 455 } 456 else{ 457 max_count = 7; min_count = 4; 458 } 459 } 460 } 461 462 // Construct the Huffman tree for the bit lengths and return the index in 463 // bl_order of the last bit length code to send. build_bl_tree()464 int build_bl_tree(){ 465 int max_blindex; // index of last bit length code of non zero freq 466 467 // Determine the bit length frequencies for literal and distance trees 468 scan_tree(dyn_ltree, l_desc.max_code); 469 scan_tree(dyn_dtree, d_desc.max_code); 470 471 // Build the bit length tree: 472 bl_desc.build_tree(this); 473 // opt_len now includes the length of the tree representations, except 474 // the lengths of the bit lengths codes and the 5+5+4 bits for the counts. 475 476 // Determine the number of bit length codes to send. The pkzip format 477 // requires that at least 4 bit length codes be sent. (appnote.txt says 478 // 3 but the actual value used is 4.) 479 for (max_blindex = BL_CODES-1; max_blindex >= 3; max_blindex--) { 480 if (bl_tree[Tree.bl_order[max_blindex]*2+1] != 0) break; 481 } 482 // Update opt_len to include the bit length tree and counts 483 opt_len += 3*(max_blindex+1) + 5+5+4; 484 485 return max_blindex; 486 } 487 488 489 // Send the header for a block using dynamic Huffman trees: the counts, the 490 // lengths of the bit length codes, the literal tree and the distance tree. 491 // IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4. send_all_trees(int lcodes, int dcodes, int blcodes)492 void send_all_trees(int lcodes, int dcodes, int blcodes){ 493 int rank; // index in bl_order 494 495 send_bits(lcodes-257, 5); // not +255 as stated in appnote.txt 496 send_bits(dcodes-1, 5); 497 send_bits(blcodes-4, 4); // not -3 as stated in appnote.txt 498 for (rank = 0; rank < blcodes; rank++) { 499 send_bits(bl_tree[Tree.bl_order[rank]*2+1], 3); 500 } 501 send_tree(dyn_ltree, lcodes-1); // literal tree 502 send_tree(dyn_dtree, dcodes-1); // distance tree 503 } 504 505 // Send a literal or distance tree in compressed form, using the codes in 506 // bl_tree. send_tree(short[] tree, int max_code )507 void send_tree (short[] tree,// the tree to be sent 508 int max_code // and its largest code of non zero frequency 509 ){ 510 int n; // iterates over all tree elements 511 int prevlen = -1; // last emitted length 512 int curlen; // length of current code 513 int nextlen = tree[0*2+1]; // length of next code 514 int count = 0; // repeat count of the current code 515 int max_count = 7; // max repeat count 516 int min_count = 4; // min repeat count 517 518 if (nextlen == 0){ max_count = 138; min_count = 3; } 519 520 for (n = 0; n <= max_code; n++) { 521 curlen = nextlen; nextlen = tree[(n+1)*2+1]; 522 if(++count < max_count && curlen == nextlen) { 523 continue; 524 } 525 else if(count < min_count) { 526 do { send_code(curlen, bl_tree); } while (--count != 0); 527 } 528 else if(curlen != 0){ 529 if(curlen != prevlen){ 530 send_code(curlen, bl_tree); count--; 531 } 532 send_code(REP_3_6, bl_tree); 533 send_bits(count-3, 2); 534 } 535 else if(count <= 10){ 536 send_code(REPZ_3_10, bl_tree); 537 send_bits(count-3, 3); 538 } 539 else{ 540 send_code(REPZ_11_138, bl_tree); 541 send_bits(count-11, 7); 542 } 543 count = 0; prevlen = curlen; 544 if(nextlen == 0){ 545 max_count = 138; min_count = 3; 546 } 547 else if(curlen == nextlen){ 548 max_count = 6; min_count = 3; 549 } 550 else{ 551 max_count = 7; min_count = 4; 552 } 553 } 554 } 555 556 // Output a byte on the stream. 557 // IN assertion: there is enough room in pending_buf. put_byte(byte[] p, int start, int len)558 final void put_byte(byte[] p, int start, int len){ 559 System.arraycopy(p, start, pending_buf, pending, len); 560 pending+=len; 561 } 562 put_byte(byte c)563 final void put_byte(byte c){ 564 pending_buf[pending++]=c; 565 } put_short(int w)566 final void put_short(int w) { 567 put_byte((byte)(w/*&0xff*/)); 568 put_byte((byte)(w>>>8)); 569 } putShortMSB(int b)570 final void putShortMSB(int b){ 571 put_byte((byte)(b>>8)); 572 put_byte((byte)(b/*&0xff*/)); 573 } 574 send_code(int c, short[] tree)575 final void send_code(int c, short[] tree){ 576 int c2=c*2; 577 send_bits((tree[c2]&0xffff), (tree[c2+1]&0xffff)); 578 } 579 send_bits(int value, int length)580 void send_bits(int value, int length){ 581 int len = length; 582 if (bi_valid > (int)Buf_size - len) { 583 int val = value; 584 // bi_buf |= (val << bi_valid); 585 bi_buf |= ((val << bi_valid)&0xffff); 586 put_short(bi_buf); 587 bi_buf = (short)(val >>> (Buf_size - bi_valid)); 588 bi_valid += len - Buf_size; 589 } else { 590 // bi_buf |= (value) << bi_valid; 591 bi_buf |= (((value) << bi_valid)&0xffff); 592 bi_valid += len; 593 } 594 } 595 596 // Send one empty static block to give enough lookahead for inflate. 597 // This takes 10 bits, of which 7 may remain in the bit buffer. 598 // The current inflate code requires 9 bits of lookahead. If the 599 // last two codes for the previous block (real code plus EOB) were coded 600 // on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode 601 // the last real code. In this case we send two empty static blocks instead 602 // of one. (There are no problems if the previous block is stored or fixed.) 603 // To simplify the code, we assume the worst case of last real code encoded 604 // on one bit only. _tr_align()605 void _tr_align(){ 606 send_bits(STATIC_TREES<<1, 3); 607 send_code(END_BLOCK, StaticTree.static_ltree); 608 609 bi_flush(); 610 611 // Of the 10 bits for the empty block, we have already sent 612 // (10 - bi_valid) bits. The lookahead for the last real code (before 613 // the EOB of the previous block) was thus at least one plus the length 614 // of the EOB plus what we have just sent of the empty static block. 615 if (1 + last_eob_len + 10 - bi_valid < 9) { 616 send_bits(STATIC_TREES<<1, 3); 617 send_code(END_BLOCK, StaticTree.static_ltree); 618 bi_flush(); 619 } 620 last_eob_len = 7; 621 } 622 623 624 // Save the match info and tally the frequency counts. Return true if 625 // the current block must be flushed. _tr_tally(int dist, int lc )626 boolean _tr_tally (int dist, // distance of matched string 627 int lc // match length-MIN_MATCH or unmatched char (if dist==0) 628 ){ 629 630 pending_buf[d_buf+last_lit*2] = (byte)(dist>>>8); 631 pending_buf[d_buf+last_lit*2+1] = (byte)dist; 632 633 pending_buf[l_buf+last_lit] = (byte)lc; last_lit++; 634 635 if (dist == 0) { 636 // lc is the unmatched char 637 dyn_ltree[lc*2]++; 638 } 639 else { 640 matches++; 641 // Here, lc is the match length - MIN_MATCH 642 dist--; // dist = match distance - 1 643 dyn_ltree[(Tree._length_code[lc]+LITERALS+1)*2]++; 644 dyn_dtree[Tree.d_code(dist)*2]++; 645 } 646 647 if ((last_lit & 0x1fff) == 0 && level > 2) { 648 // Compute an upper bound for the compressed length 649 int out_length = last_lit*8; 650 int in_length = strstart - block_start; 651 int dcode; 652 for (dcode = 0; dcode < D_CODES; dcode++) { 653 out_length += (int)dyn_dtree[dcode*2] * 654 (5L+Tree.extra_dbits[dcode]); 655 } 656 out_length >>>= 3; 657 if ((matches < (last_lit/2)) && out_length < in_length/2) return true; 658 } 659 660 return (last_lit == lit_bufsize-1); 661 // We avoid equality with lit_bufsize because of wraparound at 64K 662 // on 16 bit machines and because stored blocks are restricted to 663 // 64K-1 bytes. 664 } 665 666 // Send the block data compressed using the given Huffman trees compress_block(short[] ltree, short[] dtree)667 void compress_block(short[] ltree, short[] dtree){ 668 int dist; // distance of matched string 669 int lc; // match length or unmatched char (if dist == 0) 670 int lx = 0; // running index in l_buf 671 int code; // the code to send 672 int extra; // number of extra bits to send 673 674 if (last_lit != 0){ 675 do{ 676 dist=((pending_buf[d_buf+lx*2]<<8)&0xff00)| 677 (pending_buf[d_buf+lx*2+1]&0xff); 678 lc=(pending_buf[l_buf+lx])&0xff; lx++; 679 680 if(dist == 0){ 681 send_code(lc, ltree); // send a literal byte 682 } 683 else{ 684 // Here, lc is the match length - MIN_MATCH 685 code = Tree._length_code[lc]; 686 687 send_code(code+LITERALS+1, ltree); // send the length code 688 extra = Tree.extra_lbits[code]; 689 if(extra != 0){ 690 lc -= Tree.base_length[code]; 691 send_bits(lc, extra); // send the extra length bits 692 } 693 dist--; // dist is now the match distance - 1 694 code = Tree.d_code(dist); 695 696 send_code(code, dtree); // send the distance code 697 extra = Tree.extra_dbits[code]; 698 if (extra != 0) { 699 dist -= Tree.base_dist[code]; 700 send_bits(dist, extra); // send the extra distance bits 701 } 702 } // literal or match pair ? 703 704 // Check that the overlay between pending_buf and d_buf+l_buf is ok: 705 } 706 while (lx < last_lit); 707 } 708 709 send_code(END_BLOCK, ltree); 710 last_eob_len = ltree[END_BLOCK*2+1]; 711 } 712 713 // Set the data type to ASCII or BINARY, using a crude approximation: 714 // binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise. 715 // IN assertion: the fields freq of dyn_ltree are set and the total of all 716 // frequencies does not exceed 64K (to fit in an int on 16 bit machines). set_data_type()717 void set_data_type(){ 718 int n = 0; 719 int ascii_freq = 0; 720 int bin_freq = 0; 721 while(n<7){ bin_freq += dyn_ltree[n*2]; n++;} 722 while(n<128){ ascii_freq += dyn_ltree[n*2]; n++;} 723 while(n<LITERALS){ bin_freq += dyn_ltree[n*2]; n++;} 724 data_type=(byte)(bin_freq > (ascii_freq >>> 2) ? Z_BINARY : Z_ASCII); 725 } 726 727 // Flush the bit buffer, keeping at most 7 bits in it. bi_flush()728 void bi_flush(){ 729 if (bi_valid == 16) { 730 put_short(bi_buf); 731 bi_buf=0; 732 bi_valid=0; 733 } 734 else if (bi_valid >= 8) { 735 put_byte((byte)bi_buf); 736 bi_buf>>>=8; 737 bi_valid-=8; 738 } 739 } 740 741 // Flush the bit buffer and align the output on a byte boundary bi_windup()742 void bi_windup(){ 743 if (bi_valid > 8) { 744 put_short(bi_buf); 745 } else if (bi_valid > 0) { 746 put_byte((byte)bi_buf); 747 } 748 bi_buf = 0; 749 bi_valid = 0; 750 } 751 752 // Copy a stored block, storing first the length and its 753 // one's complement if requested. copy_block(int buf, int len, boolean header )754 void copy_block(int buf, // the input data 755 int len, // its length 756 boolean header // true if block header must be written 757 ){ 758 int index=0; 759 bi_windup(); // align on byte boundary 760 last_eob_len = 8; // enough lookahead for inflate 761 762 if (header) { 763 put_short((short)len); 764 put_short((short)~len); 765 } 766 767 // while(len--!=0) { 768 // put_byte(window[buf+index]); 769 // index++; 770 // } 771 put_byte(window, buf, len); 772 } 773 flush_block_only(boolean eof)774 void flush_block_only(boolean eof){ 775 _tr_flush_block(block_start>=0 ? block_start : -1, 776 strstart-block_start, 777 eof); 778 block_start=strstart; 779 strm.flush_pending(); 780 } 781 782 // Copy without compression as much as possible from the input stream, return 783 // the current block state. 784 // This function does not insert new strings in the dictionary since 785 // uncompressible data is probably not useful. This function is used 786 // only for the level=0 compression option. 787 // NOTE: this function should be optimized to avoid extra copying from 788 // window to pending_buf. deflate_stored(int flush)789 int deflate_stored(int flush){ 790 // Stored blocks are limited to 0xffff bytes, pending_buf is limited 791 // to pending_buf_size, and each stored block has a 5 byte header: 792 793 int max_block_size = 0xffff; 794 int max_start; 795 796 if(max_block_size > pending_buf_size - 5) { 797 max_block_size = pending_buf_size - 5; 798 } 799 800 // Copy as much as possible from input to output: 801 while(true){ 802 // Fill the window as much as possible: 803 if(lookahead<=1){ 804 fill_window(); 805 if(lookahead==0 && flush==Z_NO_FLUSH) return NeedMore; 806 if(lookahead==0) break; // flush the current block 807 } 808 809 strstart+=lookahead; 810 lookahead=0; 811 812 // Emit a stored block if pending_buf will be full: 813 max_start=block_start+max_block_size; 814 if(strstart==0|| strstart>=max_start) { 815 // strstart == 0 is possible when wraparound on 16-bit machine 816 lookahead = (int)(strstart-max_start); 817 strstart = (int)max_start; 818 819 flush_block_only(false); 820 if(strm.avail_out==0) return NeedMore; 821 822 } 823 824 // Flush if we may have to slide, otherwise block_start may become 825 // negative and the data will be gone: 826 if(strstart-block_start >= w_size-MIN_LOOKAHEAD) { 827 flush_block_only(false); 828 if(strm.avail_out==0) return NeedMore; 829 } 830 } 831 832 flush_block_only(flush == Z_FINISH); 833 if(strm.avail_out==0) 834 return (flush == Z_FINISH) ? FinishStarted : NeedMore; 835 836 return flush == Z_FINISH ? FinishDone : BlockDone; 837 } 838 839 // Send a stored block _tr_stored_block(int buf, int stored_len, boolean eof )840 void _tr_stored_block(int buf, // input block 841 int stored_len, // length of input block 842 boolean eof // true if this is the last block for a file 843 ){ 844 send_bits((STORED_BLOCK<<1)+(eof?1:0), 3); // send block type 845 copy_block(buf, stored_len, true); // with header 846 } 847 848 // Determine the best encoding for the current block: dynamic trees, static 849 // trees or store, and output the encoded block to the zip file. _tr_flush_block(int buf, int stored_len, boolean eof )850 void _tr_flush_block(int buf, // input block, or NULL if too old 851 int stored_len, // length of input block 852 boolean eof // true if this is the last block for a file 853 ) { 854 int opt_lenb, static_lenb;// opt_len and static_len in bytes 855 int max_blindex = 0; // index of last bit length code of non zero freq 856 857 // Build the Huffman trees unless a stored block is forced 858 if(level > 0) { 859 // Check if the file is ascii or binary 860 if(data_type == Z_UNKNOWN) set_data_type(); 861 862 // Construct the literal and distance trees 863 l_desc.build_tree(this); 864 865 d_desc.build_tree(this); 866 867 // At this point, opt_len and static_len are the total bit lengths of 868 // the compressed block data, excluding the tree representations. 869 870 // Build the bit length tree for the above two trees, and get the index 871 // in bl_order of the last bit length code to send. 872 max_blindex=build_bl_tree(); 873 874 // Determine the best encoding. Compute first the block length in bytes 875 opt_lenb=(opt_len+3+7)>>>3; 876 static_lenb=(static_len+3+7)>>>3; 877 878 if(static_lenb<=opt_lenb) opt_lenb=static_lenb; 879 } 880 else { 881 opt_lenb=static_lenb=stored_len+5; // force a stored block 882 } 883 884 if(stored_len+4<=opt_lenb && buf != -1){ 885 // 4: two words for the lengths 886 // The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE. 887 // Otherwise we can't have processed more than WSIZE input bytes since 888 // the last block flush, because compression would have been 889 // successful. If LIT_BUFSIZE <= WSIZE, it is never too late to 890 // transform a block into a stored block. 891 _tr_stored_block(buf, stored_len, eof); 892 } 893 else if(static_lenb == opt_lenb){ 894 send_bits((STATIC_TREES<<1)+(eof?1:0), 3); 895 compress_block(StaticTree.static_ltree, StaticTree.static_dtree); 896 } 897 else{ 898 send_bits((DYN_TREES<<1)+(eof?1:0), 3); 899 send_all_trees(l_desc.max_code+1, d_desc.max_code+1, max_blindex+1); 900 compress_block(dyn_ltree, dyn_dtree); 901 } 902 903 // The above check is made mod 2^32, for files larger than 512 MB 904 // and uLong implemented on 32 bits. 905 906 init_block(); 907 908 if(eof){ 909 bi_windup(); 910 } 911 } 912 913 // Fill the window when the lookahead becomes insufficient. 914 // Updates strstart and lookahead. 915 // 916 // IN assertion: lookahead < MIN_LOOKAHEAD 917 // OUT assertions: strstart <= window_size-MIN_LOOKAHEAD 918 // At least one byte has been read, or avail_in == 0; reads are 919 // performed for at least two bytes (required for the zip translate_eol 920 // option -- not supported here). fill_window()921 void fill_window(){ 922 int n, m; 923 int p; 924 int more; // Amount of free space at the end of the window. 925 926 do{ 927 more = (window_size-lookahead-strstart); 928 929 // Deal with !@#$% 64K limit: 930 if(more==0 && strstart==0 && lookahead==0){ 931 more = w_size; 932 } 933 else if(more==-1) { 934 // Very unlikely, but possible on 16 bit machine if strstart == 0 935 // and lookahead == 1 (input done one byte at time) 936 more--; 937 938 // If the window is almost full and there is insufficient lookahead, 939 // move the upper half to the lower one to make room in the upper half. 940 } 941 else if(strstart >= w_size+ w_size-MIN_LOOKAHEAD) { 942 System.arraycopy(window, w_size, window, 0, w_size); 943 match_start-=w_size; 944 strstart-=w_size; // we now have strstart >= MAX_DIST 945 block_start-=w_size; 946 947 // Slide the hash table (could be avoided with 32 bit values 948 // at the expense of memory usage). We slide even when level == 0 949 // to keep the hash table consistent if we switch back to level > 0 950 // later. (Using level 0 permanently is not an optimal usage of 951 // zlib, so we don't care about this pathological case.) 952 953 n = hash_size; 954 p=n; 955 do { 956 m = (head[--p]&0xffff); 957 head[p]=(m>=w_size ? (short)(m-w_size) : 0); 958 } 959 while (--n != 0); 960 961 n = w_size; 962 p = n; 963 do { 964 m = (prev[--p]&0xffff); 965 prev[p] = (m >= w_size ? (short)(m-w_size) : 0); 966 // If n is not on any hash chain, prev[n] is garbage but 967 // its value will never be used. 968 } 969 while (--n!=0); 970 more += w_size; 971 } 972 973 if (strm.avail_in == 0) return; 974 975 // If there was no sliding: 976 // strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 && 977 // more == window_size - lookahead - strstart 978 // => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1) 979 // => more >= window_size - 2*WSIZE + 2 980 // In the BIG_MEM or MMAP case (not yet supported), 981 // window_size == input_size + MIN_LOOKAHEAD && 982 // strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD. 983 // Otherwise, window_size == 2*WSIZE so more >= 2. 984 // If there was sliding, more >= WSIZE. So in all cases, more >= 2. 985 986 n = strm.read_buf(window, strstart + lookahead, more); 987 lookahead += n; 988 989 // Initialize the hash value now that we have some input: 990 if(lookahead >= MIN_MATCH) { 991 ins_h = window[strstart]&0xff; 992 ins_h=(((ins_h)<<hash_shift)^(window[strstart+1]&0xff))&hash_mask; 993 } 994 // If the whole input has less than MIN_MATCH bytes, ins_h is garbage, 995 // but this is not important since only literal bytes will be emitted. 996 } 997 while (lookahead < MIN_LOOKAHEAD && strm.avail_in != 0); 998 } 999 1000 // Compress as much as possible from the input stream, return the current 1001 // block state. 1002 // This function does not perform lazy evaluation of matches and inserts 1003 // new strings in the dictionary only for unmatched strings or for short 1004 // matches. It is used only for the fast compression options. deflate_fast(int flush)1005 int deflate_fast(int flush){ 1006 // short hash_head = 0; // head of the hash chain 1007 int hash_head = 0; // head of the hash chain 1008 boolean bflush; // set if current block must be flushed 1009 1010 while(true){ 1011 // Make sure that we always have enough lookahead, except 1012 // at the end of the input file. We need MAX_MATCH bytes 1013 // for the next match, plus MIN_MATCH bytes to insert the 1014 // string following the next match. 1015 if(lookahead < MIN_LOOKAHEAD){ 1016 fill_window(); 1017 if(lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH){ 1018 return NeedMore; 1019 } 1020 if(lookahead == 0) break; // flush the current block 1021 } 1022 1023 // Insert the string window[strstart .. strstart+2] in the 1024 // dictionary, and set hash_head to the head of the hash chain: 1025 if(lookahead >= MIN_MATCH){ 1026 ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask; 1027 1028 // prev[strstart&w_mask]=hash_head=head[ins_h]; 1029 hash_head=(head[ins_h]&0xffff); 1030 prev[strstart&w_mask]=head[ins_h]; 1031 head[ins_h]=(short)strstart; 1032 } 1033 1034 // Find the longest match, discarding those <= prev_length. 1035 // At this point we have always match_length < MIN_MATCH 1036 1037 if(hash_head!=0L && 1038 ((strstart-hash_head)&0xffff) <= w_size-MIN_LOOKAHEAD 1039 ){ 1040 // To simplify the code, we prevent matches with the string 1041 // of window index 0 (in particular we have to avoid a match 1042 // of the string with itself at the start of the input file). 1043 if(strategy != Z_HUFFMAN_ONLY){ 1044 match_length=longest_match (hash_head); 1045 } 1046 // longest_match() sets match_start 1047 } 1048 if(match_length>=MIN_MATCH){ 1049 // check_match(strstart, match_start, match_length); 1050 1051 bflush=_tr_tally(strstart-match_start, match_length-MIN_MATCH); 1052 1053 lookahead -= match_length; 1054 1055 // Insert new strings in the hash table only if the match length 1056 // is not too large. This saves time but degrades compression. 1057 if(match_length <= max_lazy_match && 1058 lookahead >= MIN_MATCH) { 1059 match_length--; // string at strstart already in hash table 1060 do{ 1061 strstart++; 1062 1063 ins_h=((ins_h<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask; 1064 // prev[strstart&w_mask]=hash_head=head[ins_h]; 1065 hash_head=(head[ins_h]&0xffff); 1066 prev[strstart&w_mask]=head[ins_h]; 1067 head[ins_h]=(short)strstart; 1068 1069 // strstart never exceeds WSIZE-MAX_MATCH, so there are 1070 // always MIN_MATCH bytes ahead. 1071 } 1072 while (--match_length != 0); 1073 strstart++; 1074 } 1075 else{ 1076 strstart += match_length; 1077 match_length = 0; 1078 ins_h = window[strstart]&0xff; 1079 1080 ins_h=(((ins_h)<<hash_shift)^(window[strstart+1]&0xff))&hash_mask; 1081 // If lookahead < MIN_MATCH, ins_h is garbage, but it does not 1082 // matter since it will be recomputed at next deflate call. 1083 } 1084 } 1085 else { 1086 // No match, output a literal byte 1087 1088 bflush=_tr_tally(0, window[strstart]&0xff); 1089 lookahead--; 1090 strstart++; 1091 } 1092 if (bflush){ 1093 1094 flush_block_only(false); 1095 if(strm.avail_out==0) return NeedMore; 1096 } 1097 } 1098 1099 flush_block_only(flush == Z_FINISH); 1100 if(strm.avail_out==0){ 1101 if(flush == Z_FINISH) return FinishStarted; 1102 else return NeedMore; 1103 } 1104 return flush==Z_FINISH ? FinishDone : BlockDone; 1105 } 1106 1107 // Same as above, but achieves better compression. We use a lazy 1108 // evaluation for matches: a match is finally adopted only if there is 1109 // no better match at the next window position. deflate_slow(int flush)1110 int deflate_slow(int flush){ 1111 // short hash_head = 0; // head of hash chain 1112 int hash_head = 0; // head of hash chain 1113 boolean bflush; // set if current block must be flushed 1114 1115 // Process the input block. 1116 while(true){ 1117 // Make sure that we always have enough lookahead, except 1118 // at the end of the input file. We need MAX_MATCH bytes 1119 // for the next match, plus MIN_MATCH bytes to insert the 1120 // string following the next match. 1121 1122 if (lookahead < MIN_LOOKAHEAD) { 1123 fill_window(); 1124 if(lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) { 1125 return NeedMore; 1126 } 1127 if(lookahead == 0) break; // flush the current block 1128 } 1129 1130 // Insert the string window[strstart .. strstart+2] in the 1131 // dictionary, and set hash_head to the head of the hash chain: 1132 1133 if(lookahead >= MIN_MATCH) { 1134 ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff)) & hash_mask; 1135 // prev[strstart&w_mask]=hash_head=head[ins_h]; 1136 hash_head=(head[ins_h]&0xffff); 1137 prev[strstart&w_mask]=head[ins_h]; 1138 head[ins_h]=(short)strstart; 1139 } 1140 1141 // Find the longest match, discarding those <= prev_length. 1142 prev_length = match_length; prev_match = match_start; 1143 match_length = MIN_MATCH-1; 1144 1145 if (hash_head != 0 && prev_length < max_lazy_match && 1146 ((strstart-hash_head)&0xffff) <= w_size-MIN_LOOKAHEAD 1147 ){ 1148 // To simplify the code, we prevent matches with the string 1149 // of window index 0 (in particular we have to avoid a match 1150 // of the string with itself at the start of the input file). 1151 1152 if(strategy != Z_HUFFMAN_ONLY) { 1153 match_length = longest_match(hash_head); 1154 } 1155 // longest_match() sets match_start 1156 1157 if (match_length <= 5 && (strategy == Z_FILTERED || 1158 (match_length == MIN_MATCH && 1159 strstart - match_start > 4096))) { 1160 1161 // If prev_match is also MIN_MATCH, match_start is garbage 1162 // but we will ignore the current match anyway. 1163 match_length = MIN_MATCH-1; 1164 } 1165 } 1166 1167 // If there was a match at the previous step and the current 1168 // match is not better, output the previous match: 1169 if(prev_length >= MIN_MATCH && match_length <= prev_length) { 1170 int max_insert = strstart + lookahead - MIN_MATCH; 1171 // Do not insert strings in hash table beyond this. 1172 1173 // check_match(strstart-1, prev_match, prev_length); 1174 1175 bflush=_tr_tally(strstart-1-prev_match, prev_length - MIN_MATCH); 1176 1177 // Insert in hash table all strings up to the end of the match. 1178 // strstart-1 and strstart are already inserted. If there is not 1179 // enough lookahead, the last two strings are not inserted in 1180 // the hash table. 1181 lookahead -= prev_length-1; 1182 prev_length -= 2; 1183 do{ 1184 if(++strstart <= max_insert) { 1185 ins_h=(((ins_h)<<hash_shift)^(window[(strstart)+(MIN_MATCH-1)]&0xff))&hash_mask; 1186 //prev[strstart&w_mask]=hash_head=head[ins_h]; 1187 hash_head=(head[ins_h]&0xffff); 1188 prev[strstart&w_mask]=head[ins_h]; 1189 head[ins_h]=(short)strstart; 1190 } 1191 } 1192 while(--prev_length != 0); 1193 match_available = 0; 1194 match_length = MIN_MATCH-1; 1195 strstart++; 1196 1197 if (bflush){ 1198 flush_block_only(false); 1199 if(strm.avail_out==0) return NeedMore; 1200 } 1201 } else if (match_available!=0) { 1202 1203 // If there was no match at the previous position, output a 1204 // single literal. If there was a match but the current match 1205 // is longer, truncate the previous match to a single literal. 1206 1207 bflush=_tr_tally(0, window[strstart-1]&0xff); 1208 1209 if (bflush) { 1210 flush_block_only(false); 1211 } 1212 strstart++; 1213 lookahead--; 1214 if(strm.avail_out == 0) return NeedMore; 1215 } else { 1216 // There is no previous match to compare with, wait for 1217 // the next step to decide. 1218 1219 match_available = 1; 1220 strstart++; 1221 lookahead--; 1222 } 1223 } 1224 1225 if(match_available!=0) { 1226 bflush=_tr_tally(0, window[strstart-1]&0xff); 1227 match_available = 0; 1228 } 1229 flush_block_only(flush == Z_FINISH); 1230 1231 if(strm.avail_out==0){ 1232 if(flush == Z_FINISH) return FinishStarted; 1233 else return NeedMore; 1234 } 1235 1236 return flush == Z_FINISH ? FinishDone : BlockDone; 1237 } 1238 longest_match(int cur_match)1239 int longest_match(int cur_match){ 1240 int chain_length = max_chain_length; // max hash chain length 1241 int scan = strstart; // current string 1242 int match; // matched string 1243 int len; // length of current match 1244 int best_len = prev_length; // best match length so far 1245 int limit = strstart>(w_size-MIN_LOOKAHEAD) ? 1246 strstart-(w_size-MIN_LOOKAHEAD) : 0; 1247 int nice_match=this.nice_match; 1248 1249 // Stop when cur_match becomes <= limit. To simplify the code, 1250 // we prevent matches with the string of window index 0. 1251 1252 int wmask = w_mask; 1253 1254 int strend = strstart + MAX_MATCH; 1255 byte scan_end1 = window[scan+best_len-1]; 1256 byte scan_end = window[scan+best_len]; 1257 1258 // The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16. 1259 // It is easy to get rid of this optimization if necessary. 1260 1261 // Do not waste too much time if we already have a good match: 1262 if (prev_length >= good_match) { 1263 chain_length >>= 2; 1264 } 1265 1266 // Do not look for matches beyond the end of the input. This is necessary 1267 // to make deflate deterministic. 1268 if (nice_match > lookahead) nice_match = lookahead; 1269 1270 do { 1271 match = cur_match; 1272 1273 // Skip to next match if the match length cannot increase 1274 // or if the match length is less than 2: 1275 if (window[match+best_len] != scan_end || 1276 window[match+best_len-1] != scan_end1 || 1277 window[match] != window[scan] || 1278 window[++match] != window[scan+1]) continue; 1279 1280 // The check at best_len-1 can be removed because it will be made 1281 // again later. (This heuristic is not always a win.) 1282 // It is not necessary to compare scan[2] and match[2] since they 1283 // are always equal when the other bytes match, given that 1284 // the hash keys are equal and that HASH_BITS >= 8. 1285 scan += 2; match++; 1286 1287 // We check for insufficient lookahead only every 8th comparison; 1288 // the 256th check will be made at strstart+258. 1289 do { 1290 } while (window[++scan] == window[++match] && 1291 window[++scan] == window[++match] && 1292 window[++scan] == window[++match] && 1293 window[++scan] == window[++match] && 1294 window[++scan] == window[++match] && 1295 window[++scan] == window[++match] && 1296 window[++scan] == window[++match] && 1297 window[++scan] == window[++match] && 1298 scan < strend); 1299 1300 len = MAX_MATCH - (int)(strend - scan); 1301 scan = strend - MAX_MATCH; 1302 1303 if(len>best_len) { 1304 match_start = cur_match; 1305 best_len = len; 1306 if (len >= nice_match) break; 1307 scan_end1 = window[scan+best_len-1]; 1308 scan_end = window[scan+best_len]; 1309 } 1310 1311 } while ((cur_match = (prev[cur_match & wmask]&0xffff)) > limit 1312 && --chain_length != 0); 1313 1314 if (best_len <= lookahead) return best_len; 1315 return lookahead; 1316 } 1317 deflateInit(int level, int bits, int memlevel)1318 int deflateInit(int level, int bits, int memlevel){ 1319 return deflateInit(level, Z_DEFLATED, bits, memlevel, 1320 Z_DEFAULT_STRATEGY); 1321 } 1322 deflateInit(int level, int bits)1323 int deflateInit(int level, int bits){ 1324 return deflateInit(level, Z_DEFLATED, bits, DEF_MEM_LEVEL, 1325 Z_DEFAULT_STRATEGY); 1326 } deflateInit(int level)1327 int deflateInit(int level){ 1328 return deflateInit(level, MAX_WBITS); 1329 } deflateInit(int level, int method, int windowBits, int memLevel, int strategy)1330 private int deflateInit(int level, int method, int windowBits, 1331 int memLevel, int strategy){ 1332 int wrap = 1; 1333 // byte[] my_version=ZLIB_VERSION; 1334 1335 // 1336 // if (version == null || version[0] != my_version[0] 1337 // || stream_size != sizeof(z_stream)) { 1338 // return Z_VERSION_ERROR; 1339 // } 1340 1341 strm.msg = null; 1342 1343 if (level == Z_DEFAULT_COMPRESSION) level = 6; 1344 1345 if (windowBits < 0) { // undocumented feature: suppress zlib header 1346 wrap = 0; 1347 windowBits = -windowBits; 1348 } 1349 else if(windowBits > 15){ 1350 wrap = 2; 1351 windowBits -= 16; 1352 strm.adler=new CRC32(); 1353 } 1354 1355 if (memLevel < 1 || memLevel > MAX_MEM_LEVEL || 1356 method != Z_DEFLATED || 1357 windowBits < 9 || windowBits > 15 || level < 0 || level > 9 || 1358 strategy < 0 || strategy > Z_HUFFMAN_ONLY) { 1359 return Z_STREAM_ERROR; 1360 } 1361 1362 strm.dstate = (Deflate)this; 1363 1364 this.wrap = wrap; 1365 w_bits = windowBits; 1366 w_size = 1 << w_bits; 1367 w_mask = w_size - 1; 1368 1369 hash_bits = memLevel + 7; 1370 hash_size = 1 << hash_bits; 1371 hash_mask = hash_size - 1; 1372 hash_shift = ((hash_bits+MIN_MATCH-1)/MIN_MATCH); 1373 1374 window = new byte[w_size*2]; 1375 prev = new short[w_size]; 1376 head = new short[hash_size]; 1377 1378 lit_bufsize = 1 << (memLevel + 6); // 16K elements by default 1379 1380 // We overlay pending_buf and d_buf+l_buf. This works since the average 1381 // output size for (length,distance) codes is <= 24 bits. 1382 pending_buf = new byte[lit_bufsize*4]; 1383 pending_buf_size = lit_bufsize*4; 1384 1385 d_buf = lit_bufsize/2; 1386 l_buf = (1+2)*lit_bufsize; 1387 1388 this.level = level; 1389 1390 this.strategy = strategy; 1391 this.method = (byte)method; 1392 1393 return deflateReset(); 1394 } 1395 deflateReset()1396 int deflateReset(){ 1397 strm.total_in = strm.total_out = 0; 1398 strm.msg = null; // 1399 strm.data_type = Z_UNKNOWN; 1400 1401 pending = 0; 1402 pending_out = 0; 1403 1404 if(wrap < 0){ 1405 wrap = -wrap; 1406 } 1407 status = (wrap==0) ? BUSY_STATE : INIT_STATE; 1408 strm.adler.reset(); 1409 1410 last_flush = Z_NO_FLUSH; 1411 1412 tr_init(); 1413 lm_init(); 1414 return Z_OK; 1415 } 1416 deflateEnd()1417 int deflateEnd(){ 1418 if(status!=INIT_STATE && status!=BUSY_STATE && status!=FINISH_STATE){ 1419 return Z_STREAM_ERROR; 1420 } 1421 // Deallocate in reverse order of allocations: 1422 pending_buf=null; 1423 head=null; 1424 prev=null; 1425 window=null; 1426 // free 1427 // dstate=null; 1428 return status == BUSY_STATE ? Z_DATA_ERROR : Z_OK; 1429 } 1430 deflateParams(int _level, int _strategy)1431 int deflateParams(int _level, int _strategy){ 1432 int err=Z_OK; 1433 1434 if(_level == Z_DEFAULT_COMPRESSION){ 1435 _level = 6; 1436 } 1437 if(_level < 0 || _level > 9 || 1438 _strategy < 0 || _strategy > Z_HUFFMAN_ONLY) { 1439 return Z_STREAM_ERROR; 1440 } 1441 1442 if(config_table[level].func!=config_table[_level].func && 1443 strm.total_in != 0) { 1444 // Flush the last buffer: 1445 err = strm.deflate(Z_PARTIAL_FLUSH); 1446 } 1447 1448 if(level != _level) { 1449 level = _level; 1450 max_lazy_match = config_table[level].max_lazy; 1451 good_match = config_table[level].good_length; 1452 nice_match = config_table[level].nice_length; 1453 max_chain_length = config_table[level].max_chain; 1454 } 1455 strategy = _strategy; 1456 return err; 1457 } 1458 deflateSetDictionary(byte[] dictionary, int dictLength)1459 int deflateSetDictionary (byte[] dictionary, int dictLength){ 1460 int length = dictLength; 1461 int index=0; 1462 1463 if(dictionary == null || status != INIT_STATE) 1464 return Z_STREAM_ERROR; 1465 1466 strm.adler.update(dictionary, 0, dictLength); 1467 1468 if(length < MIN_MATCH) return Z_OK; 1469 if(length > w_size-MIN_LOOKAHEAD){ 1470 length = w_size-MIN_LOOKAHEAD; 1471 index=dictLength-length; // use the tail of the dictionary 1472 } 1473 System.arraycopy(dictionary, index, window, 0, length); 1474 strstart = length; 1475 block_start = length; 1476 1477 // Insert all strings in the hash table (except for the last two bytes). 1478 // s->lookahead stays null, so s->ins_h will be recomputed at the next 1479 // call of fill_window. 1480 1481 ins_h = window[0]&0xff; 1482 ins_h=(((ins_h)<<hash_shift)^(window[1]&0xff))&hash_mask; 1483 1484 for(int n=0; n<=length-MIN_MATCH; n++){ 1485 ins_h=(((ins_h)<<hash_shift)^(window[(n)+(MIN_MATCH-1)]&0xff))&hash_mask; 1486 prev[n&w_mask]=head[ins_h]; 1487 head[ins_h]=(short)n; 1488 } 1489 return Z_OK; 1490 } 1491 deflate(int flush)1492 int deflate(int flush){ 1493 int old_flush; 1494 1495 if(flush>Z_FINISH || flush<0){ 1496 return Z_STREAM_ERROR; 1497 } 1498 1499 if(strm.next_out == null || 1500 (strm.next_in == null && strm.avail_in != 0) || 1501 (status == FINISH_STATE && flush != Z_FINISH)) { 1502 strm.msg=z_errmsg[Z_NEED_DICT-(Z_STREAM_ERROR)]; 1503 return Z_STREAM_ERROR; 1504 } 1505 if(strm.avail_out == 0){ 1506 strm.msg=z_errmsg[Z_NEED_DICT-(Z_BUF_ERROR)]; 1507 return Z_BUF_ERROR; 1508 } 1509 1510 old_flush = last_flush; 1511 last_flush = flush; 1512 1513 // Write the zlib header 1514 if(status == INIT_STATE) { 1515 if(wrap == 2){ 1516 getGZIPHeader().put(this); 1517 status=BUSY_STATE; 1518 strm.adler.reset(); 1519 } 1520 else{ 1521 int header = (Z_DEFLATED+((w_bits-8)<<4))<<8; 1522 int level_flags=((level-1)&0xff)>>1; 1523 1524 if(level_flags>3) level_flags=3; 1525 header |= (level_flags<<6); 1526 if(strstart!=0) header |= PRESET_DICT; 1527 header+=31-(header % 31); 1528 1529 status=BUSY_STATE; 1530 putShortMSB(header); 1531 1532 1533 // Save the adler32 of the preset dictionary: 1534 if(strstart!=0){ 1535 long adler=strm.adler.getValue(); 1536 putShortMSB((int)(adler>>>16)); 1537 putShortMSB((int)(adler&0xffff)); 1538 } 1539 strm.adler.reset(); 1540 } 1541 } 1542 1543 // Flush as much pending output as possible 1544 if(pending != 0) { 1545 strm.flush_pending(); 1546 if(strm.avail_out == 0) { 1547 // Since avail_out is 0, deflate will be called again with 1548 // more output space, but possibly with both pending and 1549 // avail_in equal to zero. There won't be anything to do, 1550 // but this is not an error situation so make sure we 1551 // return OK instead of BUF_ERROR at next call of deflate: 1552 last_flush = -1; 1553 return Z_OK; 1554 } 1555 1556 // Make sure there is something to do and avoid duplicate consecutive 1557 // flushes. For repeated and useless calls with Z_FINISH, we keep 1558 // returning Z_STREAM_END instead of Z_BUFF_ERROR. 1559 } 1560 else if(strm.avail_in==0 && flush <= old_flush && 1561 flush != Z_FINISH) { 1562 strm.msg=z_errmsg[Z_NEED_DICT-(Z_BUF_ERROR)]; 1563 return Z_BUF_ERROR; 1564 } 1565 1566 // User must not provide more input after the first FINISH: 1567 if(status == FINISH_STATE && strm.avail_in != 0) { 1568 strm.msg=z_errmsg[Z_NEED_DICT-(Z_BUF_ERROR)]; 1569 return Z_BUF_ERROR; 1570 } 1571 1572 // Start a new block or continue the current one. 1573 if(strm.avail_in!=0 || lookahead!=0 || 1574 (flush != Z_NO_FLUSH && status != FINISH_STATE)) { 1575 int bstate=-1; 1576 switch(config_table[level].func){ 1577 case STORED: 1578 bstate = deflate_stored(flush); 1579 break; 1580 case FAST: 1581 bstate = deflate_fast(flush); 1582 break; 1583 case SLOW: 1584 bstate = deflate_slow(flush); 1585 break; 1586 default: 1587 } 1588 1589 if (bstate==FinishStarted || bstate==FinishDone) { 1590 status = FINISH_STATE; 1591 } 1592 if (bstate==NeedMore || bstate==FinishStarted) { 1593 if(strm.avail_out == 0) { 1594 last_flush = -1; // avoid BUF_ERROR next call, see above 1595 } 1596 return Z_OK; 1597 // If flush != Z_NO_FLUSH && avail_out == 0, the next call 1598 // of deflate should use the same flush parameter to make sure 1599 // that the flush is complete. So we don't have to output an 1600 // empty block here, this will be done at next call. This also 1601 // ensures that for a very small output buffer, we emit at most 1602 // one empty block. 1603 } 1604 1605 if (bstate==BlockDone) { 1606 if(flush == Z_PARTIAL_FLUSH) { 1607 _tr_align(); 1608 } 1609 else { // FULL_FLUSH or SYNC_FLUSH 1610 _tr_stored_block(0, 0, false); 1611 // For a full flush, this empty block will be recognized 1612 // as a special marker by inflate_sync(). 1613 if(flush == Z_FULL_FLUSH) { 1614 //state.head[s.hash_size-1]=0; 1615 for(int i=0; i<hash_size/*-1*/; i++) // forget history 1616 head[i]=0; 1617 } 1618 } 1619 strm.flush_pending(); 1620 if(strm.avail_out == 0) { 1621 last_flush = -1; // avoid BUF_ERROR at next call, see above 1622 return Z_OK; 1623 } 1624 } 1625 } 1626 1627 if(flush!=Z_FINISH) return Z_OK; 1628 if(wrap<=0) return Z_STREAM_END; 1629 1630 if(wrap==2){ 1631 long adler=strm.adler.getValue(); 1632 put_byte((byte)(adler&0xff)); 1633 put_byte((byte)((adler>>8)&0xff)); 1634 put_byte((byte)((adler>>16)&0xff)); 1635 put_byte((byte)((adler>>24)&0xff)); 1636 put_byte((byte)(strm.total_in&0xff)); 1637 put_byte((byte)((strm.total_in>>8)&0xff)); 1638 put_byte((byte)((strm.total_in>>16)&0xff)); 1639 put_byte((byte)((strm.total_in>>24)&0xff)); 1640 1641 getGZIPHeader().setCRC(adler); 1642 } 1643 else{ 1644 // Write the zlib trailer (adler32) 1645 long adler=strm.adler.getValue(); 1646 putShortMSB((int)(adler>>>16)); 1647 putShortMSB((int)(adler&0xffff)); 1648 } 1649 1650 strm.flush_pending(); 1651 1652 // If avail_out is zero, the application will call deflate again 1653 // to flush the rest. 1654 1655 if(wrap > 0) wrap = -wrap; // write the trailer only once! 1656 return pending != 0 ? Z_OK : Z_STREAM_END; 1657 } 1658 deflateCopy(ZStream dest, ZStream src)1659 static int deflateCopy(ZStream dest, ZStream src){ 1660 1661 if(src.dstate == null){ 1662 return Z_STREAM_ERROR; 1663 } 1664 1665 if(src.next_in!=null){ 1666 dest.next_in = new byte[src.next_in.length]; 1667 System.arraycopy(src.next_in, 0, dest.next_in, 0, src.next_in.length); 1668 } 1669 dest.next_in_index = src.next_in_index; 1670 dest.avail_in = src.avail_in; 1671 dest.total_in = src.total_in; 1672 1673 if(src.next_out!=null){ 1674 dest.next_out = new byte[src.next_out.length]; 1675 System.arraycopy(src.next_out, 0, dest.next_out ,0 , src.next_out.length); 1676 } 1677 1678 dest.next_out_index = src.next_out_index; 1679 dest.avail_out = src.avail_out; 1680 dest.total_out = src.total_out; 1681 1682 dest.msg = src.msg; 1683 dest.data_type = src.data_type; 1684 dest.adler = src.adler.copy(); 1685 1686 try{ 1687 dest.dstate = (Deflate)src.dstate.clone(); 1688 dest.dstate.strm = dest; 1689 } 1690 catch(CloneNotSupportedException e){ 1691 // 1692 } 1693 return Z_OK; 1694 } 1695 clone()1696 public Object clone() throws CloneNotSupportedException { 1697 Deflate dest = (Deflate)super.clone(); 1698 1699 dest.pending_buf = dup(dest.pending_buf); 1700 dest.window = dup(dest.window); 1701 1702 dest.prev = dup(dest.prev); 1703 dest.head = dup(dest.head); 1704 dest.dyn_ltree = dup(dest.dyn_ltree); 1705 dest.dyn_dtree = dup(dest.dyn_dtree); 1706 dest.bl_tree = dup(dest.bl_tree); 1707 1708 dest.bl_count = dup(dest.bl_count); 1709 dest.heap = dup(dest.heap); 1710 dest.depth = dup(dest.depth); 1711 1712 dest.l_desc.dyn_tree = dest.dyn_ltree; 1713 dest.d_desc.dyn_tree = dest.dyn_dtree; 1714 dest.bl_desc.dyn_tree = dest.bl_tree; 1715 1716 /* 1717 dest.l_desc.stat_desc = StaticTree.static_l_desc; 1718 dest.d_desc.stat_desc = StaticTree.static_d_desc; 1719 dest.bl_desc.stat_desc = StaticTree.static_bl_desc; 1720 */ 1721 1722 if(dest.gheader!=null){ 1723 dest.gheader = (GZIPHeader)dest.gheader.clone(); 1724 } 1725 1726 return dest; 1727 } 1728 dup(byte[] buf)1729 private byte[] dup(byte[] buf){ 1730 byte[] foo = new byte[buf.length]; 1731 System.arraycopy(buf, 0, foo, 0, foo.length); 1732 return foo; 1733 } dup(short[] buf)1734 private short[] dup(short[] buf){ 1735 short[] foo = new short[buf.length]; 1736 System.arraycopy(buf, 0, foo, 0, foo.length); 1737 return foo; 1738 } dup(int[] buf)1739 private int[] dup(int[] buf){ 1740 int[] foo = new int[buf.length]; 1741 System.arraycopy(buf, 0, foo, 0, foo.length); 1742 return foo; 1743 } 1744 getGZIPHeader()1745 synchronized GZIPHeader getGZIPHeader(){ 1746 if(gheader==null){ 1747 gheader = new GZIPHeader(); 1748 } 1749 return gheader; 1750 } 1751 } 1752