View Javadoc

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