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