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