deflate.java

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

		int count = 0; // repeat count of the current code
		int max_count = 7; // max repeat count
		int min_count = 4; // min repeat count

		if (nextlen == 0) {
			max_count = 138;
			min_count = 3;
		}
		tree[(max_code + 1) * 2 + 1] = (short) 0xffff; // guard

		for (n = 0; n <= max_code; n++) {
			curlen = nextlen;
			nextlen = tree[(n + 1) * 2 + 1];
			if (++count < max_count && curlen == nextlen) {
				continue;
			} else if (count < min_count) {
				bl_tree[curlen * 2] += count;
			} else if (curlen != 0) {
				if (curlen != prevlen)
					bl_tree[curlen * 2]++;
				bl_tree[REP_3_6 * 2]++;
			} else if (count <= 10) {
				bl_tree[REPZ_3_10 * 2]++;
			} else {
				bl_tree[REPZ_11_138 * 2]++;
			}
			count = 0;
			prevlen = curlen;
			if (nextlen == 0) {
				max_count = 138;
				min_count = 3;
			} else if (curlen == nextlen) {
				max_count = 6;
				min_count = 3;
			} else {
				max_count = 7;
				min_count = 4;
			}
		}
	}

	// Construct the Huffman tree for the bit lengths and return the index in
	// bl_order of the last bit length code to send.
	int build_bl_tree() {
		int max_blindex; // index of last bit length code of non zero freq

		// Determine the bit length frequencies for literal and distance trees
		scan_tree(dyn_ltree, l_desc.max_code);
		scan_tree(dyn_dtree, d_desc.max_code);

		// Build the bit length tree:
		bl_desc.build_tree(this);
		// opt_len now includes the length of the tree representations, except
		// the lengths of the bit lengths codes and the 5+5+4 bits for the
		// counts.

		// Determine the number of bit length codes to send. The pkzip format
		// requires that at least 4 bit length codes be sent. (appnote.txt says
		// 3 but the actual value used is 4.)
		for (max_blindex = BL_CODES - 1; max_blindex >= 3; max_blindex--) {
			if (bl_tree[Tree.bl_order[max_blindex] * 2 + 1] != 0)
				break;
		}
		// Update opt_len to include the bit length tree and counts
		opt_len += 3 * (max_blindex + 1) + 5 + 5 + 4;

		return max_blindex;
	}

	// Send the header for a block using dynamic Huffman trees: the counts, the
	// lengths of the bit length codes, the literal tree and the distance tree.
	// IN assertion: lcodes >= 257, dcodes >= 1, blcodes >= 4.
	void send_all_trees(int lcodes, int dcodes, int blcodes) {
		int rank; // index in bl_order

		send_bits(lcodes - 257, 5); // not +255 as stated in appnote.txt
		send_bits(dcodes - 1, 5);
		send_bits(blcodes - 4, 4); // not -3 as stated in appnote.txt
		for (rank = 0; rank < blcodes; rank++) {
			send_bits(bl_tree[Tree.bl_order[rank] * 2 + 1], 3);
		}
		send_tree(dyn_ltree, lcodes - 1); // literal tree
		send_tree(dyn_dtree, dcodes - 1); // distance tree
	}

	// Send a literal or distance tree in compressed form, using the codes in
	// bl_tree.
	void send_tree(short[] tree,// the tree to be sent
			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
		int count = 0; // repeat count of the current code
		int max_count = 7; // max repeat count
		int min_count = 4; // min repeat count

		if (nextlen == 0) {
			max_count = 138;
			min_count = 3;
		}

		for (n = 0; n <= max_code; n++) {
			curlen = nextlen;
			nextlen = tree[(n + 1) * 2 + 1];
			if (++count < max_count && curlen == nextlen) {
				continue;
			} else if (count < min_count) {
				do {
					send_code(curlen, bl_tree);
				} while (--count != 0);
			} else if (curlen != 0) {
				if (curlen != prevlen) {
					send_code(curlen, bl_tree);
					count--;
				}
				send_code(REP_3_6, bl_tree);
				send_bits(count - 3, 2);
			} else if (count <= 10) {
				send_code(REPZ_3_10, bl_tree);
				send_bits(count - 3, 3);
			} else {
				send_code(REPZ_11_138, bl_tree);
				send_bits(count - 11, 7);
			}
			count = 0;
			prevlen = curlen;
			if (nextlen == 0) {
				max_count = 138;
				min_count = 3;
			} else if (curlen == nextlen) {
				max_count = 6;
				min_count = 3;
			} else {
				max_count = 7;
				min_count = 4;
			}
		}
	}

	// Output a byte on the stream.
	// IN assertion: there is enough room in pending_buf.
	final void put_byte(byte[] p, int start, int len) {
		System.arraycopy(p, start, pending_buf, pending, len);
		pending += len;
	}

	final void put_byte(byte c) {
		pending_buf[pending++] = c;
	}

	final void put_short(int w) {
		put_byte((byte) (w/* &0xff */));
		put_byte((byte) (w >>> 8));
	}

	final void putShortMSB(int b) {
		put_byte((byte) (b >> 8));
		put_byte((byte) (b/* &0xff */));
	}

	final void send_code(int c, short[] tree) {
		int c2 = c * 2;
		send_bits((tree[c2] & 0xffff), (tree[c2 + 1] & 0xffff));
	}

	void send_bits(int value, int length) {
		int len = length;
		if (bi_valid > (int) Buf_size - len) {
			int val = value;
			// bi_buf |= (val << bi_valid);
			bi_buf |= ((val << bi_valid) & 0xffff);
			put_short(bi_buf);
			bi_buf = (short) (val >>> (Buf_size - bi_valid));
			bi_valid += len - Buf_size;
		} else {
			// bi_buf |= (value) << bi_valid;
			bi_buf |= (((value) << bi_valid) & 0xffff);
			bi_valid += len;
		}
	}

	// Send one empty static block to give enough lookahead for inflate.
	// This takes 10 bits, of which 7 may remain in the bit buffer.
	// The current inflate code requires 9 bits of lookahead. If the
	// last two codes for the previous block (real code plus EOB) were coded
	// on 5 bits or less, inflate may have only 5+3 bits of lookahead to decode
	// the last real code. In this case we send two empty static blocks instead
	// of one. (There are no problems if the previous block is stored or fixed.)
	// To simplify the code, we assume the worst case of last real code encoded
	// on one bit only.
	void _tr_align() {
		send_bits(STATIC_TREES << 1, 3);
		send_code(END_BLOCK, StaticTree.static_ltree);

		bi_flush();

		// Of the 10 bits for the empty block, we have already sent
		// (10 - bi_valid) bits. The lookahead for the last real code (before
		// the EOB of the previous block) was thus at least one plus the length
		// of the EOB plus what we have just sent of the empty static block.
		if (1 + last_eob_len + 10 - bi_valid < 9) {
			send_bits(STATIC_TREES << 1, 3);
			send_code(END_BLOCK, StaticTree.static_ltree);
			bi_flush();
		}
		last_eob_len = 7;
	}

	// Save the match info and tally the frequency counts. Return true if
	// the current block must be flushed.
	boolean _tr_tally(int dist, // distance of matched string
			int lc // match length-MIN_MATCH or unmatched char (if dist==0)
	) {

		pending_buf[d_buf + last_lit * 2] = (byte) (dist >>> 8);
		pending_buf[d_buf + last_lit * 2 + 1] = (byte) dist;

		pending_buf[l_buf + last_lit] = (byte) lc;
		last_lit++;

		if (dist == 0) {
			// lc is the unmatched char
			dyn_ltree[lc * 2]++;
		} else {
			matches++;
			// Here, lc is the match length - MIN_MATCH
			dist--; // dist = match distance - 1
			dyn_ltree[(Tree._length_code[lc] + LITERALS + 1) * 2]++;
			dyn_dtree[Tree.d_code(dist) * 2]++;
		}

		if ((last_lit & 0x1fff) == 0 && level > 2) {
			// Compute an upper bound for the compressed length
			int out_length = last_lit * 8;
			int in_length = strstart - block_start;
			int dcode;
			for (dcode = 0; dcode < D_CODES; dcode++) {
				out_length += (int) dyn_dtree[dcode * 2]
						* (5L + Tree.extra_dbits[dcode]);
			}
			out_length >>>= 3;
			if ((matches < (last_lit / 2)) && out_length < in_length / 2)
				return true;
		}

		return (last_lit == lit_bufsize - 1);
		// We avoid equality with lit_bufsize because of wraparound at 64K
		// on 16 bit machines and because stored blocks are restricted to
		// 64K-1 bytes.
	}

	// Send the block data compressed using the given Huffman trees
	void compress_block(short[] ltree, short[] dtree) {
		int dist; // distance of matched string
		int lc; // match length or unmatched char (if dist == 0)
		int lx = 0; // running index in l_buf
		int code; // the code to send
		int extra; // number of extra bits to send

		if (last_lit != 0) {
			do {
				dist = ((pending_buf[d_buf + lx * 2] << 8) & 0xff00)
						| (pending_buf[d_buf + lx * 2 + 1] & 0xff);
				lc = (pending_buf[l_buf + lx]) & 0xff;
				lx++;

				if (dist == 0) {
					send_code(lc, ltree); // send a literal byte
				} else {
					// Here, lc is the match length - MIN_MATCH
					code = Tree._length_code[lc];

					send_code(code + LITERALS + 1, ltree); // send the length
															// code
					extra = Tree.extra_lbits[code];
					if (extra != 0) {
						lc -= Tree.base_length[code];
						send_bits(lc, extra); // send the extra length bits
					}
					dist--; // dist is now the match distance - 1
					code = Tree.d_code(dist);

					send_code(code, dtree); // send the distance code
					extra = Tree.extra_dbits[code];
					if (extra != 0) {
						dist -= Tree.base_dist[code];
						send_bits(dist, extra); // send the extra distance bits
					}
				} // literal or match pair ?

				// Check that the overlay between pending_buf and d_buf+l_buf is
				// ok:
			} while (lx < last_lit);
		}

		send_code(END_BLOCK, ltree);
		last_eob_len = ltree[END_BLOCK * 2 + 1];
	}

	// Set the data type to ASCII or BINARY, using a crude approximation:
	// binary if more than 20% of the bytes are <= 6 or >= 128, ascii otherwise.
	// IN assertion: the fields freq of dyn_ltree are set and the total of all
	// frequencies does not exceed 64K (to fit in an int on 16 bit machines).
	void set_data_type() {
		int n = 0;
		int ascii_freq = 0;
		int bin_freq = 0;
		while (n < 7) {
			bin_freq += dyn_ltree[n * 2];
			n++;
		}
		while (n < 128) {
			ascii_freq += dyn_ltree[n * 2];
			n++;
		}
		while (n < LITERALS) {
			bin_freq += dyn_ltree[n * 2];
			n++;
		}
		data_type = (byte) (bin_freq > (ascii_freq >>> 2) ? Z_BINARY : Z_ASCII);
	}

	// Flush the bit buffer, keeping at most 7 bits in it.
	void bi_flush() {
		if (bi_valid == 16) {
			put_short(bi_buf);
			bi_buf = 0;
			bi_valid = 0;
		} else if (bi_valid >= 8) {
			put_byte((byte) bi_buf);
			bi_buf >>>= 8;
			bi_valid -= 8;
		}
	}

	// Flush the bit buffer and align the output on a byte boundary
	void bi_windup() {
		if (bi_valid > 8) {
			put_short(bi_buf);
		} else if (bi_valid > 0) {
			put_byte((byte) bi_buf);
		}
		bi_buf = 0;
		bi_valid = 0;
	}

	// Copy a stored block, storing first the length and its
	// one's complement if requested.
	void copy_block(int buf, // the input data
			int len, // its length
			boolean header // true if block header must be written
	) {
		int index = 0;
		bi_windup(); // align on byte boundary
		last_eob_len = 8; // enough lookahead for inflate

		if (header) {
			put_short((short) len);
			put_short((short) ~len);
		}

		// while(len--!=0) {
		// put_byte(window[buf+index]);
		// index++;
		// }
		put_byte(window, buf, len);
	}

	void flush_block_only(boolean eof) {
		_tr_flush_block(block_start >= 0 ? block_start : -1, strstart
				- block_start, eof);
		block_start = strstart;
		strm.flush_pending();
	}

	// Copy without compression as much as possible from the input stream,
	// return
	// the current block state.
	// This function does not insert new strings in the dictionary since
	// uncompressible data is probably not useful. This function is used
	// only for the level=0 compression option.
	// NOTE: this function should be optimized to avoid extra copying from
	// window to pending_buf.
	int deflate_stored(int flush) {
		// Stored blocks are limited to 0xffff bytes, pending_buf is limited
		// to pending_buf_size, and each stored block has a 5 byte header:

		int max_block_size = 0xffff;
		int max_start;

		if (max_block_size > pending_buf_size - 5) {
			max_block_size = pending_buf_size - 5;
		}

		// Copy as much as possible from input to output:
		while (true) {
			// Fill the window as much as possible:
			if (lookahead <= 1) {
				fill_window();
				if (lookahead == 0 && flush == Z_NO_FLUSH)
					return NeedMore;
				if (lookahead == 0)
					break; // flush the current block
			}

			strstart += lookahead;
			lookahead = 0;

			// Emit a stored block if pending_buf will be full:
			max_start = block_start + max_block_size;
			if (strstart == 0 || strstart >= max_start) {
				// strstart == 0 is possible when wraparound on 16-bit machine
				lookahead = (int) (strstart - max_start);
				strstart = (int) max_start;

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

			}

			// Flush if we may have to slide, otherwise block_start may become