KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > jcraft > jzlib > Deflate


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