deflate.java

著名的zlib 压缩解压缩库的JAVA语言实现。

			// negative and the data will be gone:
			if (strstart - block_start >= w_size - MIN_LOOKAHEAD) {
				flush_block_only(false);
				if (strm.avail_out == 0)
					return NeedMore;
			}
		}

		flush_block_only(flush == Z_FINISH);
		if (strm.avail_out == 0)
			return (flush == Z_FINISH) ? FinishStarted : NeedMore;

		return flush == Z_FINISH ? FinishDone : BlockDone;
	}

	// Send a stored block
	void _tr_stored_block(int buf, // input block
			int stored_len, // length of input block
			boolean eof // true if this is the last block for a file
	) {
		send_bits((STORED_BLOCK << 1) + (eof ? 1 : 0), 3); // send block type
		copy_block(buf, stored_len, true); // with header
	}

	// Determine the best encoding for the current block: dynamic trees, static
	// trees or store, and output the encoded block to the zip file.
	void _tr_flush_block(int buf, // input block, or NULL if too old
			int stored_len, // length of input block
			boolean eof // true if this is the last block for a file
	) {
		int opt_lenb, static_lenb;// opt_len and static_len in bytes
		int max_blindex = 0; // index of last bit length code of non zero
								// freq

		// Build the Huffman trees unless a stored block is forced
		if (level > 0) {
			// Check if the file is ascii or binary
			if (data_type == Z_UNKNOWN)
				set_data_type();

			// Construct the literal and distance trees
			l_desc.build_tree(this);

			d_desc.build_tree(this);

			// At this point, opt_len and static_len are the total bit lengths
			// of
			// the compressed block data, excluding the tree representations.

			// Build the bit length tree for the above two trees, and get the
			// index
			// in bl_order of the last bit length code to send.
			max_blindex = build_bl_tree();

			// Determine the best encoding. Compute first the block length in
			// bytes
			opt_lenb = (opt_len + 3 + 7) >>> 3;
			static_lenb = (static_len + 3 + 7) >>> 3;

			if (static_lenb <= opt_lenb)
				opt_lenb = static_lenb;
		} else {
			opt_lenb = static_lenb = stored_len + 5; // force a stored block
		}

		if (stored_len + 4 <= opt_lenb && buf != -1) {
			// 4: two words for the lengths
			// The test buf != NULL is only necessary if LIT_BUFSIZE > WSIZE.
			// Otherwise we can't have processed more than WSIZE input bytes
			// since
			// the last block flush, because compression would have been
			// successful. If LIT_BUFSIZE <= WSIZE, it is never too late to
			// transform a block into a stored block.
			_tr_stored_block(buf, stored_len, eof);
		} else if (static_lenb == opt_lenb) {
			send_bits((STATIC_TREES << 1) + (eof ? 1 : 0), 3);
			compress_block(StaticTree.static_ltree, StaticTree.static_dtree);
		} else {
			send_bits((DYN_TREES << 1) + (eof ? 1 : 0), 3);
			send_all_trees(l_desc.max_code + 1, d_desc.max_code + 1,
					max_blindex + 1);
			compress_block(dyn_ltree, dyn_dtree);
		}

		// The above check is made mod 2^32, for files larger than 512 MB
		// and uLong implemented on 32 bits.

		init_block();

		if (eof) {
			bi_windup();
		}
	}

	// Fill the window when the lookahead becomes insufficient.
	// Updates strstart and lookahead.
	//
	// IN assertion: lookahead < MIN_LOOKAHEAD
	// OUT assertions: strstart <= window_size-MIN_LOOKAHEAD
	// At least one byte has been read, or avail_in == 0; reads are
	// performed for at least two bytes (required for the zip translate_eol
	// option -- not supported here).
	void fill_window() {
		int n, m;
		int p;
		int more; // Amount of free space at the end of the window.

		do {
			more = (window_size - lookahead - strstart);

			// Deal with !@#$% 64K limit:
			if (more == 0 && strstart == 0 && lookahead == 0) {
				more = w_size;
			} else if (more == -1) {
				// Very unlikely, but possible on 16 bit machine if strstart ==
				// 0
				// and lookahead == 1 (input done one byte at time)
				more--;

				// If the window is almost full and there is insufficient
				// lookahead,
				// move the upper half to the lower one to make room in the
				// upper half.
			} else if (strstart >= w_size + w_size - MIN_LOOKAHEAD) {
				System.arraycopy(window, w_size, window, 0, w_size);
				match_start -= w_size;
				strstart -= w_size; // we now have strstart >= MAX_DIST
				block_start -= w_size;

				// Slide the hash table (could be avoided with 32 bit values
				// at the expense of memory usage). We slide even when level ==
				// 0
				// to keep the hash table consistent if we switch back to level
				// > 0
				// later. (Using level 0 permanently is not an optimal usage of
				// zlib, so we don't care about this pathological case.)

				n = hash_size;
				p = n;
				do {
					m = (head[--p] & 0xffff);
					head[p] = (m >= w_size ? (short) (m - w_size) : 0);
				} while (--n != 0);

				n = w_size;
				p = n;
				do {
					m = (prev[--p] & 0xffff);
					prev[p] = (m >= w_size ? (short) (m - w_size) : 0);
					// If n is not on any hash chain, prev[n] is garbage but
					// its value will never be used.
				} while (--n != 0);
				more += w_size;
			}

			if (strm.avail_in == 0)
				return;

			// If there was no sliding:
			// strstart <= WSIZE+MAX_DIST-1 && lookahead <= MIN_LOOKAHEAD - 1 &&
			// more == window_size - lookahead - strstart
			// => more >= window_size - (MIN_LOOKAHEAD-1 + WSIZE + MAX_DIST-1)
			// => more >= window_size - 2*WSIZE + 2
			// In the BIG_MEM or MMAP case (not yet supported),
			// window_size == input_size + MIN_LOOKAHEAD &&
			// strstart + s->lookahead <= input_size => more >= MIN_LOOKAHEAD.
			// Otherwise, window_size == 2*WSIZE so more >= 2.
			// If there was sliding, more >= WSIZE. So in all cases, more >= 2.

			n = strm.read_buf(window, strstart + lookahead, more);
			lookahead += n;

			// Initialize the hash value now that we have some input:
			if (lookahead >= MIN_MATCH) {
				ins_h = window[strstart] & 0xff;
				ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff))
						& hash_mask;
			}
			// If the whole input has less than MIN_MATCH bytes, ins_h is
			// garbage,
			// but this is not important since only literal bytes will be
			// emitted.
		} while (lookahead < MIN_LOOKAHEAD && strm.avail_in != 0);
	}

	// Compress as much as possible from the input stream, return the current
	// block state.
	// This function does not perform lazy evaluation of matches and inserts
	// new strings in the dictionary only for unmatched strings or for short
	// matches. It is used only for the fast compression options.
	int deflate_fast(int flush) {
		// short hash_head = 0; // head of the hash chain
		int hash_head = 0; // head of the hash chain
		boolean bflush; // set if current block must be flushed

		while (true) {
			// Make sure that we always have enough lookahead, except
			// at the end of the input file. We need MAX_MATCH bytes
			// for the next match, plus MIN_MATCH bytes to insert the
			// string following the next match.
			if (lookahead < MIN_LOOKAHEAD) {
				fill_window();
				if (lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
					return NeedMore;
				}
				if (lookahead == 0)
					break; // flush the current block
			}

			// Insert the string window[strstart .. strstart+2] in the
			// dictionary, and set hash_head to the head of the hash chain:
			if (lookahead >= MIN_MATCH) {
				ins_h = (((ins_h) << hash_shift) ^ (window[(strstart)
						+ (MIN_MATCH - 1)] & 0xff))
						& hash_mask;

				// prev[strstart&w_mask]=hash_head=head[ins_h];
				hash_head = (head[ins_h] & 0xffff);
				prev[strstart & w_mask] = head[ins_h];
				head[ins_h] = (short) strstart;
			}

			// Find the longest match, discarding those <= prev_length.
			// At this point we have always match_length < MIN_MATCH

			if (hash_head != 0L
					&& ((strstart - hash_head) & 0xffff) <= w_size
							- MIN_LOOKAHEAD) {
				// To simplify the code, we prevent matches with the string
				// of window index 0 (in particular we have to avoid a match
				// of the string with itself at the start of the input file).
				if (strategy != Z_HUFFMAN_ONLY) {
					match_length = longest_match(hash_head);
				}
				// longest_match() sets match_start
			}
			if (match_length >= MIN_MATCH) {
				// check_match(strstart, match_start, match_length);

				bflush = _tr_tally(strstart - match_start, match_length
						- MIN_MATCH);

				lookahead -= match_length;

				// Insert new strings in the hash table only if the match length
				// is not too large. This saves time but degrades compression.
				if (match_length <= max_lazy_match && lookahead >= MIN_MATCH) {
					match_length--; // string at strstart already in hash table
					do {
						strstart++;

						ins_h = ((ins_h << hash_shift) ^ (window[(strstart)
								+ (MIN_MATCH - 1)] & 0xff))
								& hash_mask;
						// prev[strstart&w_mask]=hash_head=head[ins_h];
						hash_head = (head[ins_h] & 0xffff);
						prev[strstart & w_mask] = head[ins_h];
						head[ins_h] = (short) strstart;

						// strstart never exceeds WSIZE-MAX_MATCH, so there are
						// always MIN_MATCH bytes ahead.
					} while (--match_length != 0);
					strstart++;
				} else {
					strstart += match_length;
					match_length = 0;
					ins_h = window[strstart] & 0xff;

					ins_h = (((ins_h) << hash_shift) ^ (window[strstart + 1] & 0xff))
							& hash_mask;
					// If lookahead < MIN_MATCH, ins_h is garbage, but it does
					// not
					// matter since it will be recomputed at next deflate call.
				}
			} else {
				// No match, output a literal byte

				bflush = _tr_tally(0, window[strstart] & 0xff);
				lookahead--;
				strstart++;
			}
			if (bflush) {

				flush_block_only(false);
				if (strm.avail_out == 0)
					return NeedMore;
			}
		}

		flush_block_only(flush == Z_FINISH);
		if (strm.avail_out == 0) {
			if (flush == Z_FINISH)
				return FinishStarted;
			else
				return NeedMore;
		}
		return flush == Z_FINISH ? FinishDone : BlockDone;
	}

	// Same as above, but achieves better compression. We use a lazy
	// evaluation for matches: a match is finally adopted only if there is
	// no better match at the next window position.
	int deflate_slow(int flush) {
		// short hash_head = 0; // head of hash chain
		int hash_head = 0; // head of hash chain
		boolean bflush; // set if current block must be flushed

		// Process the input block.
		while (true) {
			// Make sure that we always have enough lookahead, except
			// at the end of the input file. We need MAX_MATCH bytes
			// for the next match, plus MIN_MATCH bytes to insert the
			// string following the next match.

			if (lookahead < MIN_LOOKAHEAD) {
				fill_window();
				if (lookahead < MIN_LOOKAHEAD && flush == Z_NO_FLUSH) {
					return NeedMore;
				}
				if (lookahead == 0)
					break; // flush the current block
			}

			// Insert the string window[strstart .. strstart+2] in the
			// dictionary, and set hash_head to the head of the hash chain:

			if (lookahead >= MIN_MATCH) {
				ins_h = (((ins_h) << hash_shift) ^ (window[(strstart)
						+ (MIN_MATCH - 1)] & 0xff))
						& hash_mask;
				// prev[strstart&w_mask]=hash_head=head[ins_h];
				hash_head = (head[ins_h] & 0xffff);
				prev[strstart & w_mask] = head[ins_h];
				head[ins_h] = (short) strstart;
			}

			// Find the longest match, discarding those <= prev_length.
			prev_length = match_length;
			prev_match = match_start;
			match_length = MIN_MATCH - 1;

			if (hash_head != 0
					&& prev_length < max_lazy_match
					&& ((strstart - hash_head) & 0xffff) <= w_size
							- MIN_LOOKAHEAD) {
				// To simplify the code, we prevent matches with the string
				// of window index 0 (in particular we have to avoid a match
				// of the string with itself at the start of the input file).

				if (strategy != Z_HUFFMAN_ONLY) {
					match_length = longest_match(hash_head);
				}
				// longest_match() sets match_start

				if (match_length <= 5
						&& (strategy == Z_FILTERED || (match_length == MIN_MATCH && strstart
								- match_start > 4096))) {

					// If prev_match is also MIN_MATCH, match_start is garbage
					// but we will ignore the current match anyway.
					match_length = MIN_MATCH - 1;
				}
			}

			// If there was a match at the previous step and the current
			// match is not better, output the previous match:
			if (prev_length >= MIN_MATCH && match_length <= prev_length) {
				int max_insert = strstart + lookahead - MIN_MATCH;
				// Do not insert strings in hash table beyond this.

				// check_match(strstart-1, prev_match, prev_length);

				bflush = _tr_tally(strstart - 1 - prev_match, prev_length
						- MIN_MATCH);

				// Insert in hash table all strings up to the end of the match.
				// strstart-1 and strstart are already inserted. If there is not
				// enough lookahead, the last two strings are not inserted in
				// the hash table.
				lookahead -= prev_length - 1;
				prev_length -= 2;
				do {
					if (++strstart <= max_insert) {
						ins_h = (((ins_h) << hash_shift) ^ (window[(strstart)
								+ (MIN_MATCH - 1)] & 0xff))
								& hash_mask;
						// prev[strstart&w_mask]=hash_head=head[ins_h];
						hash_head = (head[ins_h] & 0xffff);
						prev[strstart & w_mask] = head[ins_h];
						head[ins_h] = (short) strstart;
					}
				} while (--prev_length != 0);
				match_available = 0;
				match_length = MIN_MATCH - 1;
				strstart++;

				if (bflush) {
					flush_block_only(false);
					if (strm.avail_out == 0)
						return NeedMore;
				}
			} else if (match_available != 0) {

				// If there was no match at the previous position, output a
				// single literal. If there was a match but the current match
				// is longer, truncate the previous match to a single literal.

				bflush = _tr_tally(0, window[strstart - 1] & 0xff);

				if (bflush) {
					flush_block_only(false);
				}
				strstart++;
				lookahead--;
				if (strm.avail_out == 0)
					return NeedMore;
			} else {
				// There is no previous match to compare with, wait for
				// the next step to decide.

				match_available = 1;
				strstart++;
				lookahead--;
			}