/* -*-mode:java; c-basic-offset:2; -*- *//* Copyright (c) 2000,2001,2002,2003 ymnk, JCraft,Inc. All rights reserved. Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer. 2. Redistributions in binary form must reproduce the above copyright  notice, this list of conditions and the following disclaimer in  the documentation and/or other materials provided with the distribution. 3. The names of the authors may not be used to endorse or promote products derived from this software without specific prior written permission. THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JCRAFT, INC. OR ANY CONTRIBUTORS TO THIS SOFTWARE BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *//* * This program is based on zlib-1.1.3, so all credit should go authors * Jean-loup Gailly(jloup@gzip.org) and Mark Adler(madler@alumni.caltech.edu) * and contributors of zlib. */package com.jcraft.jzlib;public final class Deflate {	static final private int MAX_MEM_LEVEL = 9;	static final private int Z_DEFAULT_COMPRESSION = -1;	static final private int MAX_WBITS = 15; // 32K LZ77 window	static final private int DEF_MEM_LEVEL = 8;	static class Config {		int good_length; // reduce lazy search above this match length		int max_lazy; // do not perform lazy search above this match length		int nice_length; // quit search above this match length		int max_chain;		int func;		Config(int good_length, int max_lazy, int nice_length, int max_chain,				int func) {			this.good_length = good_length;			this.max_lazy = max_lazy;			this.nice_length = nice_length;			this.max_chain = max_chain;			this.func = func;		}	}	static final private int STORED = 0;	static final private int FAST = 1;	static final private int SLOW = 2;	static final private Config[] config_table;	static {		config_table = new Config[10];		// good lazy nice chain		config_table[0] = new Config(0, 0, 0, 0, STORED);		config_table[1] = new Config(4, 4, 8, 4, FAST);		config_table[2] = new Config(4, 5, 16, 8, FAST);		config_table[3] = new Config(4, 6, 32, 32, FAST);		config_table[4] = new Config(4, 4, 16, 16, SLOW);		config_table[5] = new Config(8, 16, 32, 32, SLOW);		config_table[6] = new Config(8, 16, 128, 128, SLOW);		config_table[7] = new Config(8, 32, 128, 256, SLOW);		config_table[8] = new Config(32, 128, 258, 1024, SLOW);		config_table[9] = new Config(32, 258, 258, 4096, SLOW);	}	static final private String[] z_errmsg = { "need dictionary", // Z_NEED_DICT																	// 2			"stream end", // Z_STREAM_END 1			"", // Z_OK 0			"file error", // Z_ERRNO (-1)			"stream error", // Z_STREAM_ERROR (-2)			"data error", // Z_DATA_ERROR (-3)			"insufficient memory", // Z_MEM_ERROR (-4)			"buffer error", // Z_BUF_ERROR (-5)			"incompatible version",// Z_VERSION_ERROR (-6)			"" };	// block not completed, need more input or more output	static final private int NeedMore = 0;	// block flush performed	static final private int BlockDone = 1;	// finish started, need only more output at next deflate	static final private int FinishStarted = 2;	// finish done, accept no more input or output	static final private int FinishDone = 3;	// preset dictionary flag in zlib header	static final private int PRESET_DICT = 0x20;	static final private int Z_FILTERED = 1;	static final private int Z_HUFFMAN_ONLY = 2;	static final private int Z_DEFAULT_STRATEGY = 0;	static final private int Z_NO_FLUSH = 0;	static final private int Z_PARTIAL_FLUSH = 1;	static final private int Z_SYNC_FLUSH = 2;	static final private int Z_FULL_FLUSH = 3;	static final private int Z_FINISH = 4;	static final private int Z_OK = 0;	static final private int Z_STREAM_END = 1;	static final private int Z_NEED_DICT = 2;	static final private int Z_ERRNO = -1;	static final private int Z_STREAM_ERROR = -2;	static final private int Z_DATA_ERROR = -3;	static final private int Z_MEM_ERROR = -4;	static final private int Z_BUF_ERROR = -5;	static final private int Z_VERSION_ERROR = -6;	static final private int INIT_STATE = 42;	static final private int BUSY_STATE = 113;	static final private int FINISH_STATE = 666;	// The deflate compression method	static final private int Z_DEFLATED = 8;	static final private int STORED_BLOCK = 0;	static final private int STATIC_TREES = 1;	static final private int DYN_TREES = 2;	// The three kinds of block type	static final private int Z_BINARY = 0;	static final private int Z_ASCII = 1;	static final private int Z_UNKNOWN = 2;	static final private int Buf_size = 8 * 2;	// repeat previous bit length 3-6 times (2 bits of repeat count)	static final private int REP_3_6 = 16;	// repeat a zero length 3-10 times (3 bits of repeat count)	static final private int REPZ_3_10 = 17;	// repeat a zero length 11-138 times (7 bits of repeat count)	static final private int REPZ_11_138 = 18;	static final private int MIN_MATCH = 3;	static final private int MAX_MATCH = 258;	static final private int MIN_LOOKAHEAD = (MAX_MATCH + MIN_MATCH + 1);	static final private int MAX_BITS = 15;	static final private int D_CODES = 30;	static final private int BL_CODES = 19;	static final private int LENGTH_CODES = 29;	static final private int LITERALS = 256;	static final private int L_CODES = (LITERALS + 1 + LENGTH_CODES);	static final private int HEAP_SIZE = (2 * L_CODES + 1);	static final private int END_BLOCK = 256;	ZStream strm; // pointer back to this zlib stream	int status; // as the name implies	byte[] pending_buf; // output still pending	int pending_buf_size; // size of pending_buf	int pending_out; // next pending byte to output to the stream	int pending; // nb of bytes in the pending buffer	int noheader; // suppress zlib header and adler32	byte data_type; // UNKNOWN, BINARY or ASCII	byte method; // STORED (for zip only) or DEFLATED	int last_flush; // value of flush param for previous deflate call	int w_size; // LZ77 window size (32K by default)	int w_bits; // log2(w_size) (8..16)	int w_mask; // w_size - 1	byte[] window;	// Sliding window. Input bytes are read into the second half of the window,	// and move to the first half later to keep a dictionary of at least wSize	// bytes. With this organization, matches are limited to a distance of	// wSize-MAX_MATCH bytes, but this ensures that IO is always	// performed with a length multiple of the block size. Also, it limits	// the window size to 64K, which is quite useful on MSDOS.	// To do: use the user input buffer as sliding window.	int window_size;	// Actual size of window: 2*wSize, except when the user input buffer	// is directly used as sliding window.	short[] prev;	// Link to older string with same hash index. To limit the size of this	// array to 64K, this link is maintained only for the last 32K strings.	// An index in this array is thus a window index modulo 32K.	short[] head; // Heads of the hash chains or NIL.	int ins_h; // hash index of string to be inserted	int hash_size; // number of elements in hash table	int hash_bits; // log2(hash_size)	int hash_mask; // hash_size-1	// Number of bits by which ins_h must be shifted at each input	// step. It must be such that after MIN_MATCH steps, the oldest	// byte no longer takes part in the hash key, that is:	// hash_shift * MIN_MATCH >= hash_bits	int hash_shift;	// Window position at the beginning of the current output block. Gets	// negative when the window is moved backwards.	int block_start;	int match_length; // length of best match	int prev_match; // previous match	int match_available; // set if previous match exists	int strstart; // start of string to insert	int match_start; // start of matching string	int lookahead; // number of valid bytes ahead in window	// Length of the best match at previous step. Matches not greater than this	// are discarded. This is used in the lazy match evaluation.	int prev_length;	// To speed up deflation, hash chains are never searched beyond this	// length. A higher limit improves compression ratio but degrades the speed.	int max_chain_length;	// Attempt to find a better match only when the current match is strictly	// smaller than this value. This mechanism is used only for compression	// levels >= 4.	int max_lazy_match;	// Insert new strings in the hash table only if the match length is not	// greater than this length. This saves time but degrades compression.	// max_insert_length is used only for compression levels <= 3.	int level; // compression level (1..9)	int strategy; // favor or force Huffman coding	// Use a faster search when the previous match is longer than this	int good_match;	// Stop searching when current match exceeds this	int nice_match;	short[] dyn_ltree; // literal and length tree	short[] dyn_dtree; // distance tree	short[] bl_tree; // Huffman tree for bit lengths	Tree l_desc = new Tree(); // desc for literal tree	Tree d_desc = new Tree(); // desc for distance tree	Tree bl_desc = new Tree(); // desc for bit length tree	// number of codes at each bit length for an optimal tree	short[] bl_count = new short[MAX_BITS + 1];	// heap used to build the Huffman trees	int[] heap = new int[2 * L_CODES + 1];	int heap_len; // number of elements in the heap	int heap_max; // element of largest frequency	// The sons of heap[n] are heap[2*n] and heap[2*n+1]. heap[0] is not used.	// The same heap array is used to build all trees.	// Depth of each subtree used as tie breaker for trees of equal frequency	byte[] depth = new byte[2 * L_CODES + 1];	int l_buf; // index for literals or lengths */	// Size of match buffer for literals/lengths. There are 4 reasons for	// limiting lit_bufsize to 64K:	// - frequencies can be kept in 16 bit counters	// - if compression is not successful for the first block, all input	// data is still in the window so we can still emit a stored block even	// when input comes from standard input. (This can also be done for	// all blocks if lit_bufsize is not greater than 32K.)	// - if compression is not successful for a file smaller than 64K, we can	// even emit a stored file instead of a stored block (saving 5 bytes).	// This is applicable only for zip (not gzip or zlib).	// - creating new Huffman trees less frequently may not provide fast	// adaptation to changes in the input data statistics. (Take for	// example a binary file with poorly compressible code followed by	// a highly compressible string table.) Smaller buffer sizes give	// fast adaptation but have of course the overhead of transmitting	// trees more frequently.	// - I can't count above 4	int lit_bufsize;	int last_lit; // running index in l_buf	// Buffer for distances. To simplify the code, d_buf and l_buf have	// the same number of elements. To use different lengths, an extra flag	// array would be necessary.	int d_buf; // index of pendig_buf	int opt_len; // bit length of current block with optimal trees	int static_len; // bit length of current block with static trees	int matches; // number of string matches in current block	int last_eob_len; // bit length of EOB code for last block	// Output buffer. bits are inserted starting at the bottom (least	// significant bits).	short bi_buf;	// Number of valid bits in bi_buf. All bits above the last valid bit	// are always zero.	int bi_valid;	Deflate() {		dyn_ltree = new short[HEAP_SIZE * 2];		dyn_dtree = new short[(2 * D_CODES + 1) * 2]; // distance tree		bl_tree = new short[(2 * BL_CODES + 1) * 2]; // Huffman tree for bit														// lengths	}	void lm_init() {		window_size = 2 * w_size;		head[hash_size - 1] = 0;		for (int i = 0; i < hash_size - 1; i++) {			head[i] = 0;		}		// Set the default configuration parameters:		max_lazy_match = Deflate.config_table[level].max_lazy;		good_match = Deflate.config_table[level].good_length;		nice_match = Deflate.config_table[level].nice_length;		max_chain_length = Deflate.config_table[level].max_chain;		strstart = 0;		block_start = 0;		lookahead = 0;		match_length = prev_length = MIN_MATCH - 1;		match_available = 0;		ins_h = 0;	}	// Initialize the tree data structures for a new zlib stream.	void tr_init() {		l_desc.dyn_tree = dyn_ltree;		l_desc.stat_desc = StaticTree.static_l_desc;		d_desc.dyn_tree = dyn_dtree;		d_desc.stat_desc = StaticTree.static_d_desc;		bl_desc.dyn_tree = bl_tree;		bl_desc.stat_desc = StaticTree.static_bl_desc;		bi_buf = 0;		bi_valid = 0;		last_eob_len = 8; // enough lookahead for inflate		// Initialize the first block of the first file:		init_block();	}	void init_block() {		// Initialize the trees.		for (int i = 0; i < L_CODES; i++)			dyn_ltree[i * 2] = 0;		for (int i = 0; i < D_CODES; i++)			dyn_dtree[i * 2] = 0;		for (int i = 0; i < BL_CODES; i++)			bl_tree[i * 2] = 0;		dyn_ltree[END_BLOCK * 2] = 1;		opt_len = static_len = 0;		last_lit = matches = 0;	}	// Restore the heap property by moving down the tree starting at node k,	// exchanging a node with the smallest of its two sons if necessary,	// stopping	// when the heap property is re-established (each father smaller than its	// two sons).	void pqdownheap(short[] tree, // the tree to restore			int k // node to move down	) {		int v = heap[k];		int j = k << 1; // left son of k		while (j <= heap_len) {			// Set j to the smallest of the two sons:			if (j < heap_len && smaller(tree, heap[j + 1], heap[j], depth)) {				j++;			}			// Exit if v is smaller than both sons			if (smaller(tree, v, heap[j], depth))				break;			// Exchange v with the smallest son			heap[k] = heap[j];			k = j;			// And continue down the tree, setting j to the left son of k			j <<= 1;		}		heap[k] = v;	}	static boolean smaller(short[] tree, int n, int m, byte[] depth) {		short tn2 = tree[n * 2];		short tm2 = tree[m * 2];		return (tn2 < tm2 || (tn2 == tm2 && depth[n] <= depth[m]));	}	// Scan a literal or distance tree to determine the frequencies of the codes	// in the bit length tree.	void scan_tree(short[] tree,// the tree to be scanned			int max_code // and its largest code of non zero frequency	) {		int n; // iterates over all tree elements		int prevlen = -1; // last emitted length		int curlen; // length of current code		int nextlen = tree[0 * 2 + 1]; // length of next code