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         //    byte[] my_version=ZLIB_VERSION;
    1310
    1311         //
    1312         //  if (version == null || version[0] != my_version[0]
    1313         //  || stream_size != sizeof(z_stream)) {
    1314         //  return Z_VERSION_ERROR;
    1315         //  }
    1316
    1317         strm.msg = null;
    1318
    1319         if (level == JZlib.Z_DEFAULT_COMPRESSION) {
    1320             level = 6;
    1321         }
    1322
    1323         if (windowBits < 0) { // undocumented feature: suppress zlib header
    1324             throw new IllegalArgumentException("windowBits: " + windowBits);
    1325         }
    1326
    1327         if (memLevel < 1 || memLevel > JZlib.MAX_MEM_LEVEL ||
    1328                 method != JZlib.Z_DEFLATED || windowBits < 9 ||
    1329                 windowBits > 15 || level < 0 || level > 9 || strategy < 0 ||
    1330                 strategy > JZlib.Z_HUFFMAN_ONLY) {
    1331             return JZlib.Z_STREAM_ERROR;
    1332         }
    1333
    1334         strm.dstate = this;
    1335
    1336         this.wrapperType = wrapperType;
    1337         w_bits = windowBits;
    1338         w_size = 1 << w_bits;
    1339         w_mask = w_size - 1;
    1340
    1341         hash_bits = memLevel + 7;
    1342         hash_size = 1 << hash_bits;
    1343         hash_mask = hash_size - 1;
    1344         hash_shift = (hash_bits + MIN_MATCH - 1) / MIN_MATCH;
    1345
    1346         window = new byte[w_size * 2];
    1347         prev = new short[w_size];
    1348         head = new short[hash_size];
    1349
    1350         lit_bufsize = 1 << memLevel + 6; // 16K elements by default
    1351
    1352         // We overlay pending_buf and d_buf+l_buf. This works since the average
    1353         // output size for (length,distance) codes is <= 24 bits.
    1354         pending_buf = new byte[lit_bufsize * 4];
    1355         pending_buf_size = lit_bufsize * 4;
    1356
    1357         d_buf = lit_bufsize / 2;
    1358         l_buf = (1 + 2) * lit_bufsize;
    1359
    1360         this.level = level;
    1361
    1362         //System.out.println("level="+level);
    1363
    1364         this.strategy = strategy;
    1365
    1366         return deflateReset(strm);
    1367     }
    1368
    1369     private int deflateReset(ZStream strm) {
    1370         strm.total_in = strm.total_out = 0;
    1371         strm.msg = null; //
    1372
    1373         pending = 0;
    1374         pending_out = 0;
    1375
    1376         wroteTrailer = false;
    1377         status = wrapperType == WrapperType.NONE? BUSY_STATE : INIT_STATE;
    1378         strm.adler = Adler32.adler32(0, null, 0, 0);
    1379         strm.crc32 = 0;
    1380         gzipUncompressedBytes = 0;
    1381
    1382         last_flush = JZlib.Z_NO_FLUSH;
    1383
    1384         tr_init();
    1385         lm_init();
    1386         return JZlib.Z_OK;
    1387     }
    1388
    1389     int deflateEnd() {
    1390         if (status != INIT_STATE && status != BUSY_STATE &&
    1391                 status != FINISH_STATE) {
    1392             return JZlib.Z_STREAM_ERROR;
    1393         }
    1394         // Deallocate in reverse order of allocations:
    1395         pending_buf = null;
    1396         head = null;
    1397         prev = null;
    1398         window = null;
    1399         // free
    1400         // dstate=null;
    1401         return status == BUSY_STATE? JZlib.Z_DATA_ERROR : JZlib.Z_OK;
    1402     }
    1403
    1404     int deflateParams(ZStream strm, int _level, int _strategy) {
    1405         int err = JZlib.Z_OK;
    1406
    1407         if (_level == JZlib.Z_DEFAULT_COMPRESSION) {
    1408             _level = 6;
    1409         }
    1410         if (_level < 0 || _level > 9 || _strategy < 0 ||
    1411                 _strategy > JZlib.Z_HUFFMAN_ONLY) {
    1412             return JZlib.Z_STREAM_ERROR;
    1413         }
    1414
    1415         if (config_table[level].func != config_table[_level].func &&
    1416                 strm.total_in != 0) {
    1417             // Flush the last buffer:
    1418             err = strm.deflate(JZlib.Z_PARTIAL_FLUSH);
    1419         }
    1420
    1421         if (level != _level) {
    1422             level = _level;
    1423             max_lazy_match = config_table[level].max_lazy;
    1424             good_match = config_table[level].good_length;
    1425             nice_match = config_table[level].nice_length;
    1426             max_chain_length = config_table[level].max_chain;
    1427         }
    1428         strategy = _strategy;
    1429         return err;
    1430     }
    1431
    1432     int deflateSetDictionary(ZStream strm, byte[] dictionary, int dictLength) {
    1433         int length = dictLength;
    1434         int index = 0;
    1435
    1436         if (dictionary == null || status != INIT_STATE) {
    1437             return JZlib.Z_STREAM_ERROR;
    1438         }
    1439
    1440         strm.adler = Adler32.adler32(strm.adler, dictionary, 0, dictLength);
    1441
    1442         if (length < MIN_MATCH) {
    1443             return JZlib.Z_OK;
    1444         }
    1445         if (length > w_size - MIN_LOOKAHEAD) {
    1446             length = w_size - MIN_LOOKAHEAD;
    1447             index = dictLength - length; // use the tail of the dictionary
    1448         }
    1449         System.arraycopy(dictionary, index, window, 0, length);
    1450         strstart = length;
    1451         block_start = length;
    1452
    1453         // Insert all strings in the hash table (except for the last two bytes).
    1454         // s->lookahead stays null, so s->ins_h will be recomputed at the next
    1455         // call of fill_window.
    1456
    1457         ins_h = window[0] & 0xff;
    1458         ins_h = (ins_h << hash_shift ^ window[1] & 0xff) & hash_mask;
    1459
    1460         for (int n = 0; n <= length - MIN_MATCH; n ++) {
    1461             ins_h = (ins_h << hash_shift ^ window[n + MIN_MATCH - 1] & 0xff) &
    1462                     hash_mask;
    1463             prev[n & w_mask] = head[ins_h];
    1464             head[ins_h] = (short) n;
    1465         }
    1466         return JZlib.Z_OK;
    1467     }
    1468
    1469     int deflate(ZStream strm, int flush) {
    1470         int old_flush;
    1471
    1472         if (flush > JZlib.Z_FINISH || flush < 0) {
    1473             return JZlib.Z_STREAM_ERROR;
    1474         }
    1475
    1476         if (strm.next_out == null || strm.next_in == null &&
    1477                 strm.avail_in != 0 || status == FINISH_STATE &&
    1478                 flush != JZlib.Z_FINISH) {
    1479             strm.msg = z_errmsg[JZlib.Z_NEED_DICT - JZlib.Z_STREAM_ERROR];
    1480             return JZlib.Z_STREAM_ERROR;
    1481         }
    1482         if (strm.avail_out == 0) {
    1483             strm.msg = z_errmsg[JZlib.Z_NEED_DICT - JZlib.Z_BUF_ERROR];
    1484             return JZlib.Z_BUF_ERROR;
    1485         }
    1486
    1487         this.strm = strm; // just in case
    1488         old_flush = last_flush;
    1489         last_flush = flush;
    1490
    1491         // Write the zlib header
    1492         if (status == INIT_STATE) {
    1493             switch (wrapperType) {
    1494             case ZLIB:
    1495                 int header = JZlib.Z_DEFLATED + (w_bits - 8 << 4) << 8;
    1496                 int level_flags = (level - 1 & 0xff) >> 1;
    1497
    1498                 if (level_flags > 3) {
    1499                     level_flags = 3;
    1500                 }
    1501                 header |= level_flags << 6;
    1502                 if (strstart != 0) {
    1503                     header |= JZlib.PRESET_DICT;
    1504                 }
    1505                 header += 31 - header % 31;
    1506
    1507                 putShortMSB(header);
    1508
    1509                 // Save the adler32 of the preset dictionary:
    1510                 if (strstart != 0) {
    1511                     putShortMSB((int) (strm.adler >>> 16));
    1512                     putShortMSB((int) (strm.adler & 0xffff));
    1513                 }
    1514                 strm.adler = Adler32.adler32(0, null, 0, 0);
    1515                 break;
    1516             case GZIP:
    1517                 // Identification
    1518                 put_byte((byte) 0x1f);
    1519                 put_byte((byte) 0x8b);
    1520                 // Compression method: DEFLATE
    1521                 put_byte((byte) 8);
    1522                 // Flags
    1523                 put_byte((byte) 0);
    1524                 // MTIME
    1525                 put_byte((byte) 0);
    1526                 put_byte((byte) 0);
    1527                 put_byte((byte) 0);
    1528                 put_byte((byte) 0);
    1529                 // XFL
    1530                 switch (config_table[level].func) {
    1531                 case FAST:
    1532                     put_byte((byte) 4);
    1533                     break;
    1534                 case SLOW:
    1535                     put_byte((byte) 2);
    1536                     break;
    1537                 default:
    1538                     put_byte((byte) 0);
    1539                     break;
    1540                 }
    1541                 // OS
    1542                 put_byte((byte) 255);
    1543
    1544                 strm.crc32 = 0;
    1545                 break;
    1546             }
    1547
    1548             status = BUSY_STATE;
    1549         }
    1550
    1551         // Flush as much pending output as possible
    1552         if (pending != 0) {
    1553             strm.flush_pending();
    1554             if (strm.avail_out == 0) {
    1555                 //System.out.println("  avail_out==0");
    1556                 // Since avail_out is 0, deflate will be called again with
    1557                 // more output space, but possibly with both pending and
    1558                 // avail_in equal to zero. There won't be anything to do,
    1559                 // but this is not an error situation so make sure we
    1560                 // return OK instead of BUF_ERROR at next call of deflate:
    1561                 last_flush = -1;
    1562                 return JZlib.Z_OK;
    1563             }
    1564
    1565             // Make sure there is something to do and avoid duplicate consecutive
    1566             // flushes. For repeated and useless calls with Z_FINISH, we keep
    1567             // returning Z_STREAM_END instead of Z_BUFF_ERROR.
    1568         } else if (strm.avail_in == 0 && flush <= old_flush &&
    1569                 flush != JZlib.Z_FINISH) {
    1570             strm.msg = z_errmsg[JZlib.Z_NEED_DICT - JZlib.Z_BUF_ERROR];
    1571             return JZlib.Z_BUF_ERROR;
    1572         }
    1573
    1574         // User must not provide more input after the first FINISH:
    1575         if (status == FINISH_STATE && strm.avail_in != 0) {
    1576             strm.msg = z_errmsg[JZlib.Z_NEED_DICT - JZlib.Z_BUF_ERROR];
    1577             return JZlib.Z_BUF_ERROR;
    1578         }
    1579
    1580         // Start a new block or continue the current one.
    1581         int old_next_in_index = strm.next_in_index;
    1582         try {
    1583             if (strm.avail_in != 0 || lookahead != 0 || flush != JZlib.Z_NO_FLUSH &&
    1584                     status != FINISH_STATE) {
    1585                 int bstate = -1;
    1586                 switch (config_table[level].func) {
    1587                 case STORED:
    1588                     bstate = deflate_stored(flush);
    1589                     break;
    1590                 case FAST:
    1591                     bstate = deflate_fast(flush);
    1592                     break;
    1593                 case SLOW:
    1594                     bstate = deflate_slow(flush);
    1595                     break;
    1596                 default:
    1597                 }
    1598
    1599                 if (bstate == FinishStarted || bstate == FinishDone) {
    1600                     status = FINISH_STATE;
    1601                 }
    1602                 if (bstate == NeedMore || bstate == FinishStarted) {
    1603                     if (strm.avail_out == 0) {
    1604                         last_flush = -1; // avoid BUF_ERROR next call, see above
    1605                     }
    1606                     return JZlib.Z_OK;
    1607                     // If flush != Z_NO_FLUSH && avail_out == 0, the next call
    1608                     // of deflate should use the same flush parameter to make sure
    1609                     // that the flush is complete. So we don't have to output an
    1610                     // empty block here, this will be done at next call. This also
    1611                     // ensures that for a very small output buffer, we emit at most
    1612                     // one empty block.
    1613                 }
    1614
    1615                 if (bstate == BlockDone) {
    1616                     if (flush == JZlib.Z_PARTIAL_FLUSH) {
    1617                         _tr_align();
    1618                     } else { // FULL_FLUSH or SYNC_FLUSH
    1619                         _tr_stored_block(0, 0, false);
    1620                         // For a full flush, this empty block will be recognized
    1621                         // as a special marker by inflate_sync().
    1622                         if (flush == JZlib.Z_FULL_FLUSH) {
    1623                             //state.head[s.hash_size-1]=0;
    1624                             for (int i = 0; i < hash_size/*-1*/; i ++) {
    1625                                 head[i] = 0;
    1626                             }
    1627                         }
    1628                     }
    1629                     strm.flush_pending();
    1630                     if (strm.avail_out == 0) {
    1631                         last_flush = -1; // avoid BUF_ERROR at next call, see above
    1632                         return JZlib.Z_OK;
    1633                     }
    1634                 }
    1635             }
    1636         } finally {
    1637             gzipUncompressedBytes += strm.next_in_index - old_next_in_index;
    1638         }
    1639
    1640         if (flush != JZlib.Z_FINISH) {
    1641             return JZlib.Z_OK;
    1642         }
    1643
    1644         if (wrapperType == WrapperType.NONE || wroteTrailer) {
    1645             return JZlib.Z_STREAM_END;
    1646         }
    1647
    1648         switch (wrapperType) {
    1649         case ZLIB:
    1650             // Write the zlib trailer (adler32)
    1651             putShortMSB((int) (strm.adler >>> 16));
    1652             putShortMSB((int) (strm.adler & 0xffff));
    1653             break;
    1654         case GZIP:
    1655             // Write the gzip trailer (CRC32 & ISIZE)
    1656             put_byte((byte) (strm.crc32 & 0xFF));
    1657             put_byte((byte) (strm.crc32 >>> 8 & 0xFF));
    1658             put_byte((byte) (strm.crc32 >>> 16 & 0xFF));
    1659             put_byte((byte) (strm.crc32 >>> 24 & 0xFF));
    1660             put_byte((byte) (gzipUncompressedBytes & 0xFF));
    1661             put_byte((byte) (gzipUncompressedBytes >>> 8 & 0xFF));
    1662             put_byte((byte) (gzipUncompressedBytes >>> 16 & 0xFF));
    1663             put_byte((byte) (gzipUncompressedBytes >>> 24 & 0xFF));
    1664             break;
    1665         }
    1666
    1667         strm.flush_pending();
    1668         // If avail_out is zero, the application will call deflate again
    1669         // to flush the rest.
    1670         wroteTrailer = true; // write the trailer only once!
    1671         return pending != 0? JZlib.Z_OK : JZlib.Z_STREAM_END;
    1672     }
    1673 }