Google Git
Sign in
eclipse / mat / org.eclipse.mat / c190072e03364b07d9e1309acbe749949066e221 / . / plugins / org.eclipse.mat.hprof / src / io / nayuki / deflate / InflaterInputStream.java
blob: e83094f5427253a010fc3c80fb9623d4dee67004 [file] [log] [blame]
/*
* DEFLATE library (Java)
* Copyright (c) Project Nayuki
*
* https://www.nayuki.io/page/deflate-library-java
* https://github.com/nayuki/DEFLATE-library-Java
* Modified for Eclipse Memory Analyzer for:
* cloning of inflator
* pass-through mode for multi-chunk zips
* mark/reset
* merge of output buffer and dictionary
*/
package io.nayuki.deflate;
import java.io.EOFException;
import java.io.FilterInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.Objects;
/**
* Decompresses a DEFLATE data stream (raw format without zlib or gzip headers or footers) into a byte stream.
*/
public final class InflaterInputStream extends FilterInputStream {
/*---- Fields ----*/
/* Data buffers */
// Buffer of bytes read from in.read() (the underlying input stream)
private byte[] inputBuffer; // Can have any positive length (but longer means less overhead)
private int inputBufferLength; // Number of valid prefix bytes, at least 0
private int inputBufferIndex; // Index of next byte to consume
// Buffer of bits packed from the bytes in 'inputBuffer'
private long inputBitBuffer; // 0 <= value < 2^inputBitBufferLength
private int inputBitBufferLength; // Always in the range [0, 63]
// Queued bytes to yield first when this.read() is called
private int outputBufferLength; // Number of valid prefix bytes, at least 0
private int outputBufferIndex; // Index of next byte to produce, in the range [0, outputBufferLength]
// Buffer of last 32 KiB of decoded data, for LZ77 decompression
private byte[] dictionary;
private int dictionaryIndex;
// Generally speaking, the overall data flow of this decompressor looks like this:
// in (the underlying input stream, declared in the superclass) -> in.read()
// -> inputBuffer -> packing logic in readBits()
// -> inputBitBuffer -> readBit() or equivalent
// -> various literal and length-distance symbols -> LZ77 decoding logic
// -> dictionary, sometimes also outputBuffer -> copying to the caller's array
// -> b (the array passed into this.read(byte[],int,int)).
/* Configuration */
// Indicates whether mark() should be called when the underlying
// input stream is read, and whether calling detach() is allowed.
private final boolean isDetachable;
/* State */
// The state of the decompressor:
// -4: The decompressor is in pass-through mode, indefinite uncompressed
// -3: This decompressor stream has been closed. Equivalent to in == null.
// -2: A data format exception has been thrown. Equivalent to exception != null.
// -1: Currently processing a Huffman-compressed block.
// 0: Initial state, or a block just ended.
// 1 to 65535: Currently processing an uncompressed block, number of bytes remaining.
private int state;
// A saved exception that is thrown on every read() or detach().
private IOException exception;
// Indicates whether a block header with the "bfinal" flag has been seen.
// This starts as false, should eventually become true, and never changes back to false.
// except for the Eclipse MAT changes when a new segment is attached
private boolean isLastBlock;
// Current code trees for when state == -1. When state != -1, both must be null.
private short[] literalLengthCodeTree; // When state == -1, this must be not null
private short[] literalLengthCodeTable; // Derived from literalLengthCodeTree; same nullness
private short[] distanceCodeTree; // When state == -1, this can be null or not null
private short[] distanceCodeTable; // Derived from distanceCodeTree; same nullness
/*
* For marking.
* markPos >= 0 is position of mark in buffer [dictionary]
* markPos = -1 not set
* markPos = -2 has been set, but nothing has been read
* markPos = -3 has been set but too much has been read
*/
private int markPos = -1;
/*---- Constructors ----*/
/**
* Constructs an inflater input stream over the specified underlying input stream, and with the
* specified option for detachability. The underlying stream must contain DEFLATE-compressed data with
* no headers or footers (e.g. must be unwrapped from the zlib or gzip container formats). Detachability
* allows {@link #detach()} to be called, and requires the specified input stream to support marking.
* @param in the underlying input stream of raw DEFLATE-compressed data
* @param detachable whether {@code detach()} can be called later
* @throws NullPointerException if the input stream is {@code null}
* @throws IllegalArgumentException if {@code detach == true} but {@code in.markSupported() == false}
*/
public InflaterInputStream(InputStream in, boolean detachable) {
this(in, detachable, 16 * 1024); // Use a reasonable default input buffer size
}
/**
* Constructs an inflater input stream over the specified underlying input stream, with the
* specified options for detachability and input buffer size. The underlying stream must
* contain DEFLATE-compressed data with no headers or footers (e.g. must be unwrapped from
* the zlib or gzip container formats). Detachability allows {@link #detach()} to be called,
* and requires the specified input stream to support marking.
* @param in the underlying input stream of raw DEFLATE-compressed data
* @param detachable whether {@code detach()} can be called later
* @param inBufLen the size of the internal read buffer, which must be positive
* @throws NullPointerException if the input stream is {@code null}
* @throws IllegalArgumentException if {@code inBufLen < 1}
* @throws IllegalArgumentException if {@code detach == true} but {@code in.markSupported() == false}
*/
public InflaterInputStream(InputStream in, boolean detachable, int inBufLen) {
// Handle the input stream and detachability
super(in);
if (inBufLen <= 0)
throw new IllegalArgumentException("Input buffer size must be positive");
isDetachable = detachable;
if (detachable) {
if (in.markSupported())
in.mark(0);
else
throw new IllegalArgumentException("Input stream not markable, cannot support detachment");
}
// Initialize data buffers
inputBuffer = new byte[inBufLen];
inputBufferLength = 0;
inputBufferIndex = 0;
inputBitBuffer = 0;
inputBitBufferLength = 0;
outputBufferLength = 0;
outputBufferIndex = 0;
dictionary = new byte[DICTIONARY_LENGTH];
dictionaryIndex = 0;
// Initialize state
state = 0;
exception = null;
isLastBlock = false;
literalLengthCodeTree = null;
literalLengthCodeTable = null;
distanceCodeTree = null;
distanceCodeTable = null;
}
/**
* Extra constructor added for org.eclipse.mat.hprof
*
* Only safe to use copy or original once the underlying stream
* has been positioned to the appropriate location.
* Added by Eclipse MAT.
* @param copy the original stream
*/
public InflaterInputStream(InflaterInputStream copy)
{
this(copy.in, copy.isDetachable);
if (copy.inputBuffer != null)
inputBuffer = Arrays.copyOf(copy.inputBuffer, copy.inputBuffer.length);
inputBufferLength = copy.inputBufferLength;
inputBufferIndex = copy.inputBufferIndex;
inputBitBuffer = copy.inputBitBuffer;
inputBitBufferLength = copy.inputBitBufferLength;
outputBufferLength = copy.outputBufferLength;
outputBufferIndex = copy.outputBufferIndex;
if (copy.dictionary != null)
dictionary = Arrays.copyOf(copy.dictionary, copy.dictionary.length);
else
dictionary = null;
dictionaryIndex = copy.dictionaryIndex;
markPos = copy.markPos;
// Initialize state
state = copy.state;
if (copy.exception != null)
exception = new IOException(copy.exception.toString());
isLastBlock = copy.isLastBlock;
if (copy.literalLengthCodeTree != null)
literalLengthCodeTree = Arrays.copyOf(copy.literalLengthCodeTree, copy.literalLengthCodeTree.length);
if (copy.literalLengthCodeTable != null)
literalLengthCodeTable = Arrays.copyOf(copy.literalLengthCodeTable, copy.literalLengthCodeTable.length);
if (copy.distanceCodeTree != null)
distanceCodeTree = Arrays.copyOf(copy.distanceCodeTree, copy.distanceCodeTree.length);
if (copy.distanceCodeTable != null)
distanceCodeTable = Arrays.copyOf(copy.distanceCodeTable, copy.distanceCodeTable.length);
}
/*---- Public API methods ----*/
/**
* Reads the next byte of decompressed data from this stream. If data is available
* then a number in the range [0, 255] is returned (blocking if necessary);
* otherwise &minus;1 is returned if the end of stream is reached.
* @return the next unsigned byte of data, or &minus;1 for the end of stream
* @throws IOException if an I/O exception occurred in the underlying input stream, the end of
* stream was encountered at an unexpected position, or the compressed data has a format error
* @throws IllegalStateException if the stream has already been closed
*/
public int read() throws IOException {
// In theory this method for reading a single byte could be implemented somewhat faster.
// We could take the logic of read(byte[],int,int) and simplify it for the special case
// of handling one byte. But if the caller chose to use this read() method instead of
// the bulk read(byte[]) method, then they have already chosen to not care about speed.
// Therefore speeding up this method would result in needless complexity. Instead,
// we chose to optimize this method for simplicity and ease of verifying correctness.
while (true) {
byte[] b = new byte[1];
switch (read(b)) {
case 1:
return (b[0] & 0xFF);
case 0:
continue;
case -1:
return -1;
default:
throw new AssertionError();
}
}
}
/**
* Reads some bytes from the decompressed data of this stream into the specified array's subrange.
* This returns the number of data bytes that were stored into the array, and is in the range
* [&minus;1, len]. Note that 0 can be returned even if the end of stream hasn't been reached yet.
* @throws NullPointerException if the array is {@code null}
* @throws ArrayIndexOutOfBoundsException if the array subrange is out of bounds
* @throws IOException if an I/O exception occurred in the underlying input stream, the end of
* stream was encountered at an unexpected position, or the compressed data has a format error
* @throws IllegalStateException if the stream has already been closed
*/
public int read(byte[] b, int off, int len) throws IOException {
// Check arguments and state
Objects.requireNonNull(b);
if (off < 0 || off > b.length || len < 0 || b.length - off < len)
throw new ArrayIndexOutOfBoundsException();
if (in == null)
throw new IllegalStateException("Stream already closed");
if (exception != null)
throw exception;
// Special handling for empty read request
if (len == 0)
return (outputBufferLength > 0 || state != 0 || !isLastBlock) ? 0 : -1;
assert len > 0;
int result = 0; // Number of bytes filled in the array 'b'
// First move bytes (if any) from the output buffer [which is actually in the dictionary]
if (outputBufferLength > 0) {
// There could be a new mark while we are re-reading data, or reading duplicated bytes.
if (markPos == -2)
markPos = (dictionaryIndex - (outputBufferLength - outputBufferIndex)) & DICTIONARY_MASK;
int n = Math.min(outputBufferLength - outputBufferIndex, len);
// Move up to end of dictionary array
int i = (dictionaryIndex - (outputBufferLength - outputBufferIndex)) & DICTIONARY_MASK;
int n1 = Math.min(n, DICTIONARY_LENGTH - i);
System.arraycopy(dictionary, i, b, off + result, n1);
result = n1;
outputBufferIndex += n1;
// Move the remainder
if (n1 < n) {
// Wrap
n1 = n - n1;
System.arraycopy(dictionary, 0, b, off + result, n1);
result += n1;
outputBufferIndex += n1;
}
if (outputBufferIndex == outputBufferLength) {
outputBufferLength = 0;
outputBufferIndex = 0;
}
if (result == len)
return result;
}
// Now the output buffer is clear, and we have room to read at least one byte
assert outputBufferLength == 0 && outputBufferIndex == 0 && result < len;
// Get into a block if not already inside one
while (state == 0) {
if (isLastBlock)
return (result != 0) ? result : -1;
// Read and process the block header
isLastBlock = readBits(1) == 1;
switch (readBits(2)) { // Type
case 0:
alignInputToByte();
state = readBits(16); // Block length
if (state != (readBits(16) ^ 0xFFFF))
destroyAndThrow(new DataFormatException("len/nlen mismatch in uncompressed block"));
break;
case 1:
state = -1;
literalLengthCodeTree = FIXED_LITERAL_LENGTH_CODE_TREE;
literalLengthCodeTable = FIXED_LITERAL_LENGTH_CODE_TABLE;
distanceCodeTree = FIXED_DISTANCE_CODE_TREE;
distanceCodeTable = FIXED_DISTANCE_CODE_TABLE;
break;
case 2:
state = -1;
decodeHuffmanCodes();
break;
case 3:
destroyAndThrow(new DataFormatException("Reserved block type"));
break;
default:
throw new AssertionError();
}
}
// Read the current block's data into the argument array
if (1 <= state && state <= 0xFFFF) {
// Read bytes from uncompressed block
int toRead = Math.min(state, len - result);
readBytes(b, off + result, toRead);
updateMark(dictionaryIndex, toRead);
for (int i = 0; i < toRead; i++) {
dictionary[dictionaryIndex] = b[off + result];
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
result++;
}
state -= toRead;
return result;
} else if (state == -1) // Decode symbols from Huffman-coded block
return result + readInsideHuffmanBlock(b, off + result, len - result);
else if (state == -4) {
// Modification for Eclipse MAT
int n = Math.min(inputBufferLength - inputBufferIndex + (inputBitBufferLength >> 3), len - result);
if (n > 0) {
readBytes(b, off + result, n);
result += n;
} else if (result < len) {
n = len - result;
int r = in.read(b, off + result, n);
if (r >= 0) {
result += r;
} else if (result == 0)
result = r;
}
return result;
} else
throw new AssertionError("Impossible state");
}
/**
* Notes the current position of the output, so that later the caller can
* go back to this spot by calling reset.
* This uses the dictionary array as a cache of the last bytes returned to the caller.
* The dictionary is 32768 bytes in size, however when reading compressed data
* the inflator can generate an extra 257 bytes which are not returned to the caller
* but are stored in the dictionary. There is therefore a limit of 32768 - 257 = 32211 bytes
* that can be stored.
* Strictly speaking, the InputStream contract expects any value of limit to be
* honoured, and for implementation to add extra buffering to achieve this.
* Addition for Eclipse MAT.
* @param limit the caller can read at least this many bytes before calling {@link #reset()}
* @see #reset()
*/
@Override
public void mark(int limit)
{
if (limit > DICTIONARY_LENGTH - OUTPUT_BUFFER_LENGTH)
throw new IllegalArgumentException(String.valueOf(limit));
if (state == -4)
throw new IllegalStateException(String.valueOf(state));
markPos = -2;
}
/**
* Goes back in the output to the point where {@link #mark(int)} was called.
* Addition for Eclipse MAT
* @throws IOException if it is not possible to go back to the mark point.
* The current position is then unchanged.
* @see #mark(int)
*/
@Override
public void reset() throws IOException
{
// If we are between chunks then reset doesn't make sense at it
// only operates on decompressed data.
if (state == -4)
throw new IllegalStateException(String.valueOf(state));
if (markPos >= 0) {
int toread;
if (dictionaryIndex > markPos)
toread = dictionaryIndex - markPos;
else
toread = DICTIONARY_LENGTH - markPos + dictionaryIndex;
if (outputBufferLength > toread) {
assert outputBufferIndex >= outputBufferLength - toread;
outputBufferIndex = outputBufferLength - toread;
} else {
outputBufferLength = toread;
outputBufferIndex = 0;
}
} else if (markPos == -3)
throw new IOException("too far");
else if (markPos == -2)
{
// mark() immediately followed by reset() so we don't need to do anything
// mark is still valid for a subsequent reset.
}
else if (markPos == -1)
throw new IOException("no mark");
else
throw new IllegalStateException(String.valueOf(markPos));
}
/**
* Does this stream support {@link #mark(int)} and {@link #reset()} ?
* It does.
* Addition for Eclipse MAT.
* @return true
* @see #mark(int)
* @see #reset()
*/
@Override
public boolean markSupported()
{
return true;
}
/**
* The number of bytes which can be read without blocking.
* With the underlying stream it is not clear how many bytes those
* will expand to so just rely on what is in the buffers.
* Addition for Eclipse MAT.
* @return the number of bytes which can be read without blocking.
*/
public int available() throws IOException {
long input;
int actual = (outputBufferLength - outputBufferIndex);
if (state == -4) {
// pass through mode
input = inputBufferLength - inputBufferIndex + (inputBitBufferLength >> 3);
} else {
// The amount of compressed data
input = inputBufferLength - inputBufferIndex + (inputBitBufferLength >> 3);
if (state > 0) {
// Uncompressed block
if (input > state)
input = state;
} else if (state == -1 && input >= 3) {
// With 48 bits of input we can decode at least one symbol
// However, the symbol could be end of block!
input = 0;
} else {
// We don't know how much can be read without going to the underlying stream
input = 0;
}
}
return (int) Math.min(actual + input, Integer.MAX_VALUE);
}
//@Override
public long skip(long n) throws IOException
{
if (n <= 0)
return 0;
long skipped = 0;
if (outputBufferLength >= 0) {
// There could be a new mark while we are re-reading data, or reading duplicated bytes.
if (markPos == -2)
markPos = (dictionaryIndex - (outputBufferLength - outputBufferIndex)) & DICTIONARY_MASK;
if (n >= outputBufferLength - outputBufferIndex) {
skipped = outputBufferLength - outputBufferIndex;
outputBufferLength = 0;
outputBufferIndex = 0;
n -= skipped;
} else {
outputBufferIndex += n;
return n;
}
}
byte buf[] = null;
while (n > 0)
{
int toskip = (int)Math.min(n, 16384);
if (buf == null)
buf = new byte[toskip];
long r = read(buf, 0, toskip);
if (r == -1)
{
break;
}
skipped += r;
n -= r;
}
return skipped;
}
/**
* See if too much data has been read for a {@link #reset()} to not work anymore.
* Addition for Eclipse MAT.
* @param dictionaryIndex the next place to store in the dictionary
* @param count the number of bytes to add to dictionary
*/
private void updateMark(int dictionaryIndex, int count)
{
if (markPos == -1)
return;
else if (markPos == -2) {
if (count <= DICTIONARY_LENGTH)
markPos = dictionaryIndex;
else
markPos = -3;
} else if (count >= DICTIONARY_LENGTH)
markPos = -3;
else if (markPos >= dictionaryIndex)
if (dictionaryIndex + count >= markPos)
markPos = -3;
else if (((dictionaryIndex + count) & DICTIONARY_MASK) >= markPos)
markPos = -3;
}
private void endofblock() {
if (isLastBlock && !(markPos >= 0 || outputBufferLength > 0)) {
// Clear the dictionary early
dictionary = null;
dictionaryIndex = -1;
}
}
// This method exists to split up the public read(byte[],int,int) method that is rather long.
// For internal use only; must only be called by read(byte[],int,int). The input array's subrange must be valid
// (the caller checks the preconditions). The current state must be -1. This returns a number in the range [0, len].
private int readInsideHuffmanBlock(byte[] b, int off, int len) throws IOException {
int result = 0;
while (result < len) {
// Try to fill the input bit buffer (somewhat similar to logic in readBits())
if (inputBitBufferLength < 48) {
byte[] c = inputBuffer; // Shorter name
int i = inputBufferIndex; // Shorter name
int numBytes = Math.min((64 - inputBitBufferLength) >>> 3, inputBufferLength - i);
assert 0 <= numBytes && numBytes <= 8;
if (numBytes == 2) { // Only implement special cases that occur frequently in practice
inputBitBuffer |= (long)((c[i]&0xFF) | (c[i+1]&0xFF)<<8) << inputBitBufferLength;
inputBitBufferLength += 2 * 8;
inputBufferIndex += 2;
} else if (numBytes == 3) {
inputBitBuffer |= (long)((c[i]&0xFF) | (c[i+1]&0xFF)<<8 | (c[i+2]&0xFF)<<16) << inputBitBufferLength;
inputBitBufferLength += 3 * 8;
inputBufferIndex += 3;
} else if (numBytes == 4) {
inputBitBuffer |= (((c[i]&0xFF) | (c[i+1]&0xFF)<<8 | (c[i+2]&0xFF)<<16 | c[i+3]<<24) & 0xFFFFFFFFL) << inputBitBufferLength;
inputBitBufferLength += 4 * 8;
inputBufferIndex += 4;
} else { // This slower general logic is valid for 0 <= numBytes <= 8
for (int j = 0; j < numBytes; j++, inputBitBufferLength += 8, inputBufferIndex++)
inputBitBuffer |= (c[inputBufferIndex] & 0xFFL) << inputBitBufferLength;
}
}
// The worst-case number of bits consumed in one iteration:
// length (symbol (15) + extra (5)) + distance (symbol (15) + extra (13)) = 48.
// This allows us to do decoding entirely from the bit buffer, avoiding the byte buffer or actual I/O.
if (inputBitBufferLength >= 48) { // Fast path
// Decode next literal/length symbol (a customized version of decodeSymbol())
int sym;
{
int temp = literalLengthCodeTable[(int)inputBitBuffer & CODE_TABLE_MASK];
assert temp >= 0; // No need to mask off sign extension bits
int consumed = temp >>> 11;
inputBitBuffer >>>= consumed;
inputBitBufferLength -= consumed;
int node = (temp << 21) >> 21; // Sign extension from 11 bits
while (node >= 0) {
node = literalLengthCodeTree[node + ((int)inputBitBuffer & 1)];
inputBitBuffer >>>= 1;
inputBitBufferLength--;
}
sym = ~node;
}
// Handle the symbol by ranges
assert 0 <= sym && sym <= 287;
if (sym < 256) { // Literal byte
b[off + result] = (byte)sym;
updateMark(dictionaryIndex, 1);
dictionary[dictionaryIndex] = (byte)sym;
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
result++;
} else if (sym > 256) { // Length and distance for copying
// Decode the run length (a customized version of decodeRunLength())
assert 257 <= sym && sym <= 287;
if (sym > 285)
destroyAndThrow(new DataFormatException("Reserved run length symbol: " + sym));
int run;
{
int temp = RUN_LENGTH_TABLE[sym - 257];
run = temp >>> 3;
int numExtraBits = temp & 7;
run += (int)inputBitBuffer & ((1 << numExtraBits) - 1);
inputBitBuffer >>>= numExtraBits;
inputBitBufferLength -= numExtraBits;
}
assert 3 <= run && run <= 258;
// Decode next distance symbol (a customized version of decodeSymbol())
if (distanceCodeTree == null)
destroyAndThrow(new DataFormatException("Length symbol encountered with empty distance code"));
int distSym;
{
int temp = distanceCodeTable[(int)inputBitBuffer & CODE_TABLE_MASK];
assert temp >= 0; // No need to mask off sign extension bits
int consumed = temp >>> 11;
inputBitBuffer >>>= consumed;
inputBitBufferLength -= consumed;
int node = (temp << 21) >> 21; // Sign extension from 11 bits
while (node >= 0) { // Medium path
node = distanceCodeTree[node + ((int)inputBitBuffer & 1)];
inputBitBuffer >>>= 1;
inputBitBufferLength--;
}
distSym = ~node;
}
assert 0 <= distSym && distSym <= 31;
// Decode the distance (a customized version of decodeDistance())
if (distSym > 29)
destroyAndThrow(new DataFormatException("Reserved distance symbol: " + distSym));
int dist;
{
int temp = DISTANCE_TABLE[distSym];
dist = temp >>> 4;
int numExtraBits = temp & 0xF;
dist += (int)inputBitBuffer & ((1 << numExtraBits) - 1);
inputBitBuffer >>>= numExtraBits;
inputBitBufferLength -= numExtraBits;
}
assert 1 <= dist && dist <= 32768;
assert inputBitBufferLength >= 0;
// Copy bytes to output and dictionary
int dictReadIndex = (dictionaryIndex - dist) & DICTIONARY_MASK;
if (len - result >= run) { // Nice case with less branching
updateMark(dictionaryIndex, run);
for (int i = 0; i < run; i++) {
byte bb = dictionary[dictReadIndex];
dictionary[dictionaryIndex] = bb;
b[off + result] = bb;
dictReadIndex = (dictReadIndex + 1) & DICTIONARY_MASK;
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
result++;
}
} else { // General case
assert outputBufferLength == 0;
updateMark(dictionaryIndex, run);
for (int i = 0; i < run; i++) {
byte bb = dictionary[dictReadIndex];
dictionary[dictionaryIndex] = bb;
dictReadIndex = (dictReadIndex + 1) & DICTIONARY_MASK;
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
if (result < len) {
b[off + result] = bb;
result++;
} else {
assert outputBufferLength < DICTIONARY_LENGTH;
assert outputBufferLength < OUTPUT_BUFFER_LENGTH;
outputBufferLength++;
}
}
}
} else { // sym == 256, end of block
literalLengthCodeTree = null;
literalLengthCodeTable = null;
distanceCodeTree = null;
distanceCodeTable = null;
state = 0;
endofblock();
break;
}
} else { // General case (always correct), when not enough bits in buffer to guarantee reading
int sym = decodeSymbol(literalLengthCodeTree);
assert 0 <= sym && sym <= 287;
if (sym < 256) { // Literal byte
b[off + result] = (byte)sym;
updateMark(dictionaryIndex, 1);
dictionary[dictionaryIndex] = (byte)sym;
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
result++;
} else if (sym > 256) { // Length and distance for copying
int run = decodeRunLength(sym);
assert 3 <= run && run <= 258;
if (distanceCodeTree == null)
destroyAndThrow(new DataFormatException("Length symbol encountered with empty distance code"));
int distSym = decodeSymbol(distanceCodeTree);
assert 0 <= distSym && distSym <= 31;
int dist = decodeDistance(distSym);
assert 1 <= dist && dist <= 32768;
assert outputBufferLength == 0;
// Copy bytes to output and dictionary
int dictReadIndex = (dictionaryIndex - dist) & DICTIONARY_MASK;
updateMark(dictionaryIndex, run);
for (int i = 0; i < run; i++) {
byte bb = dictionary[dictReadIndex];
dictReadIndex = (dictReadIndex + 1) & DICTIONARY_MASK;
dictionary[dictionaryIndex] = bb;
dictionaryIndex = (dictionaryIndex + 1) & DICTIONARY_MASK;
if (result < len) {
b[off + result] = bb;
result++;
} else {
assert outputBufferLength < DICTIONARY_LENGTH;
assert outputBufferLength < OUTPUT_BUFFER_LENGTH;
outputBufferLength++;
}
}
} else { // sym == 256, end of block
literalLengthCodeTree = null;
literalLengthCodeTable = null;
distanceCodeTree = null;
distanceCodeTable = null;
state = 0;
endofblock();
break;
}
}
}
return result;
}
/**
* Detaches the underlying input stream from this decompressor. This puts the underlying stream
* at the position of the first byte after the data that this decompressor actually consumed.
* Calling {@code detach()} invalidates this stream object but doesn't close the underlying stream.
* <p>This method exists because for efficiency, the decompressor may read more bytes from the
* underlying stream than necessary to produce the decompressed data. If you want to continue
* reading the underlying stream exactly after the point the DEFLATE-compressed data ends,
* then it is necessary to call this detach method.</p>
* <p>This can only be called once, and is mutually exclusive with respect to calling
* {@link #close()}. It is illegal to call {@link #read()} after detaching.</p>
* @throws IllegalStateException if detach was already called or this stream has been closed
* @throws IOException if an I/O exception occurred
*/
public void detach() throws IOException {
// Modifications for Eclipse MAT
//if (!isDetachable)
// throw new IllegalStateException("Detachability not specified at construction");
if (in == null)
throw new IllegalStateException("Input stream already detached/closed");
if (exception != null)
throw exception;
if (!isDetachable)
{
if (state == -4)
throw new IllegalStateException("Input stream already detached");
endofblock();
state = -4;
return;
}
// Rewind the underlying stream, then skip over bytes that were already consumed.
// Note that a byte with some bits consumed is considered to be fully consumed.
in.reset();
int skip = inputBufferIndex - inputBitBufferLength / 8;
assert skip >= 0;
while (skip > 0) {
long n = in.skip(skip);
if (n <= 0)
throw new EOFException();
skip -= n;
}
in = null;
state = -3;
destroyState();
}
/**
* Resume decompression.
* Addition for Eclipse MAT.
*/
public void attach()
{
if (state != -4)
throw new IllegalStateException("Not detached");
// Keep the old dictionary if it is needed for reset()
// Could clear it (but no point) if (!(markPos >= 0 || outputBufferLength > 0))
if (dictionary == null) {
// The dictionary was cleared earlier
dictionary = new byte[DICTIONARY_LENGTH];
dictionaryIndex = 0;
}
isLastBlock = false;
state = 0;
}
public String toString() {
return this.getClass()+" "+state+" "+(dictionary == null ? "no buf" : dictionary);
}
/**
* Closes this input stream and the underlying stream.
* It is illegal to call {@link #read()} or {@link #detach()} after closing.
* It is idempotent to call this {@link #close()} method more than once.
* @throws IOException if an I/O exception occurred in the underlying stream
*/
public void close() throws IOException {
if (in == null)
return;
super.close();
in = null;
state = -3;
exception = null;
destroyState();
}
/*---- Huffman coding methods ----*/
// Reads the current block's dynamic Huffman code tables from from the input buffers/stream,
// processes the code lengths and computes the code trees, and ultimately sets just the variables
// {literalLengthCodeTree, literalLengthCodeTable, distanceCodeTree, distanceCodeTable}.
// This might throw an IOException for actual I/O exceptions, unexpected end of stream,
// or a description of an invalid Huffman code.
private void decodeHuffmanCodes() throws IOException {
int numLitLenCodes = readBits(5) + 257; // hlit + 257
int numDistCodes = readBits(5) + 1; // hdist + 1
// Read the code length code lengths
int numCodeLenCodes = readBits(4) + 4; // hclen + 4
byte[] codeLenCodeLen = new byte[19]; // This array is filled in a strange order
for (int i = 0; i < numCodeLenCodes; i++)
codeLenCodeLen[CODE_LENGTH_CODE_ORDER[i]] = (byte)readBits(3);
short[] codeLenCodeTree;
try {
codeLenCodeTree = codeLengthsToCodeTree(codeLenCodeLen);
} catch (DataFormatException e) {
destroyAndThrow(e);
throw new AssertionError("Unreachable");
}
// Read the main code lengths and handle runs
byte[] codeLens = new byte[numLitLenCodes + numDistCodes];
byte runVal = -1;
int runLen = 0;
for (int i = 0; i < codeLens.length; ) {
if (runLen > 0) {
assert runVal != -1;
codeLens[i] = runVal;
runLen--;
i++;
} else {
int sym = decodeSymbol(codeLenCodeTree);
assert 0 <= sym && sym <= 18;
if (sym < 16) {
runVal = codeLens[i] = (byte)sym;
i++;
} else if (sym == 16) {
if (runVal == -1)
destroyAndThrow(new DataFormatException("No code length value to copy"));
runLen = readBits(2) + 3;
} else if (sym == 17) {
runVal = 0;
runLen = readBits(3) + 3;
} else { // sym == 18
runVal = 0;
runLen = readBits(7) + 11;
}
}
}
if (runLen > 0)
destroyAndThrow(new DataFormatException("Run exceeds number of codes"));
// Create literal-length code tree
byte[] litLenCodeLen = Arrays.copyOf(codeLens, numLitLenCodes);
try {
literalLengthCodeTree = codeLengthsToCodeTree(litLenCodeLen);
} catch (DataFormatException e) {
destroyAndThrow(e);
throw new AssertionError("Unreachable");
}
literalLengthCodeTable = codeTreeToCodeTable(literalLengthCodeTree);
// Create distance code tree with some extra processing
byte[] distCodeLen = Arrays.copyOfRange(codeLens, numLitLenCodes, codeLens.length);
if (distCodeLen.length == 1 && distCodeLen[0] == 0)
distanceCodeTree = null; // Empty distance code; the block shall be all literal symbols
else {
// Get statistics for upcoming logic
int oneCount = 0;
int otherPositiveCount = 0;
for (byte x : distCodeLen) {
if (x == 1)
oneCount++;
else if (x > 1)
otherPositiveCount++;
}
// Handle the case where only one distance code is defined
if (oneCount == 1 && otherPositiveCount == 0) {
// Add a dummy invalid code to make the Huffman tree complete
distCodeLen = Arrays.copyOf(distCodeLen, 32);
distCodeLen[31] = 1;
}
try {
distanceCodeTree = codeLengthsToCodeTree(distCodeLen);
} catch (DataFormatException e) {
destroyAndThrow(e);
throw new AssertionError("Unreachable");
}
distanceCodeTable = codeTreeToCodeTable(distanceCodeTree);
}
}
/*
* Converts the given array of symbol code lengths into a canonical code tree.
* A symbol code length is either zero (absent from the tree) or a positive integer.
*
* A code tree is an array of integers, where each pair represents a node.
* Each pair is adjacent and starts on an even index. The first element of
* the pair represents the left child and the second element represents the
* right child. The root node is at index 0. If an element is non-negative,
* then it is the index of the child node in the array. Otherwise it is the
* bitwise complement of the leaf symbol. This tree is used in decodeSymbol()
* and codeTreeToCodeTable(). Not every element of the array needs to be
* used, nor do used elements need to be contiguous.
*
* For example, this Huffman tree:
* o
* / \
* o \
* / \ \
* 'a' 'b' 'c'
* is serialized as this array:
* {2, ~'c', ~'a', ~'b'}
* because the root is located at index 0 and the other internal node is
* located at index 2.
*/
private static short[] codeLengthsToCodeTree(byte[] codeLengths) throws DataFormatException {
// Allocate array for the worst case if all symbols are present
short[] result = new short[(codeLengths.length - 1) * 2];
Arrays.fill(result, CODE_TREE_UNUSED_SLOT);
result[0] = CODE_TREE_OPEN_SLOT;
result[1] = CODE_TREE_OPEN_SLOT;
int allocated = 2; // Always even in this algorithm
int maxCodeLen = 0;
for (byte cl : codeLengths) {
assert 0 <= cl && cl <= 15;
maxCodeLen = Math.max(cl, maxCodeLen);
}
if (maxCodeLen > 15)
throw new AssertionError("Maximum code length exceeds DEFLATE specification");
// Allocate Huffman tree nodes according to ascending code lengths
for (int curCodeLen = 1; curCodeLen <= maxCodeLen; curCodeLen++) {
// Loop invariant: Each OPEN child slot in the result array has depth curCodeLen
// Allocate all symbols of current code length to open slots in ascending order
int resultIndex = 0;
for (int symbol = 0; ; ) {
// Find next symbol having current code length
while (symbol < codeLengths.length && codeLengths[symbol] != curCodeLen)
symbol++;
if (symbol == codeLengths.length)
break; // No more symbols to process
// Find next open child slot
while (resultIndex < allocated && result[resultIndex] != CODE_TREE_OPEN_SLOT)
resultIndex++;
if (resultIndex == allocated) // No more slots left
throw new DataFormatException("Canonical code fails to produce full Huffman code tree");
// Put the symbol into the slot and increment
result[resultIndex] = (short)~symbol;
resultIndex++;
symbol++;
}
// Take all open slots and deepen them by one level
for (int end = allocated; resultIndex < end; resultIndex++) {
if (result[resultIndex] == CODE_TREE_OPEN_SLOT) {
// Allocate a new node
assert allocated + 2 <= result.length;
result[resultIndex] = (short)allocated;
result[allocated + 0] = CODE_TREE_OPEN_SLOT;
result[allocated + 1] = CODE_TREE_OPEN_SLOT;
allocated += 2;
}
}
}
// Check for unused open slots after all symbols are allocated
for (int i = 0; i < allocated; i++) {
if (result[i] == CODE_TREE_OPEN_SLOT)
throw new DataFormatException("Canonical code fails to produce full Huffman code tree");
}
return result;
}
/*
* Converts a code tree array into a fast look-up table that consumes up to
* CODE_TABLE_BITS at once. Each entry i in the table encodes the result of
* decoding starting from the root and consuming the bits of i starting from
* the lowest-order bits.
*
* Each array element encodes (numBitsConsumed << 11) | (node & 0x7FF), where:
* - numBitsConsumed is a 4-bit unsigned integer in the range [1, CODE_TABLE_BITS].
* - node is an 11-bit signed integer representing either the current node
* (which is a non-negative number) after consuming all the available bits
* from i, or the bitwise complement of the decoded symbol (so it's negative).
* Note that each element is a non-negative number.
*/
private static short[] codeTreeToCodeTable(short[] codeTree) {
assert 1 <= CODE_TABLE_BITS && CODE_TABLE_BITS <= 15;
short[] result = new short[1 << CODE_TABLE_BITS];
for (int i = 0; i < result.length; i++) {
// Simulate decodeSymbol() using the bits of i
int node = 0;
int consumed = 0;
do {
node = codeTree[node + ((i >>> consumed) & 1)];
consumed++;
} while (node >= 0 && consumed < CODE_TABLE_BITS);
assert 1 <= consumed && consumed <= 15; // 4 bits unsigned
assert -1024 <= node && node <= 1023; // 11 bits signed
result[i] = (short)(consumed << 11 | (node & 0x7FF));
assert result[i] >= 0;
}
return result;
}
// Reads bits from the input buffers/stream and uses the given code tree to decode the next symbol.
// The returned symbol value is a non-negative integer. This throws an IOException if the end of stream
// is reached before a symbol is decoded, or if the underlying stream experiences an I/O exception.
private int decodeSymbol(short[] codeTree) throws IOException {
int node = 0; // An index into the codeTree array which signifies the current tree node
while (node >= 0) {
if (inputBitBufferLength > 0) { // Medium path using buffered bits
node = codeTree[node + ((int)inputBitBuffer & 1)];
inputBitBuffer >>>= 1;
inputBitBufferLength--;
} else // Slow path with potential I/O operations
node = codeTree[node + readBits(1)];
}
return ~node; // Symbol was encoded as bitwise complement
}
// Takes the given run length symbol in the range [257, 287], possibly reads some more input bits,
// and returns a number in the range [3, 258]. This throws an IOException if bits needed to be read
// but the end of stream was reached or the underlying stream experienced an I/O exception.
private int decodeRunLength(int sym) throws IOException {
assert 257 <= sym && sym <= 287;
if (sym <= 264)
return sym - 254;
else if (sym <= 284) {
int numExtraBits = (sym - 261) >>> 2;
return ((((sym - 1) & 3) | 4) << numExtraBits) + 3 + readBits(numExtraBits);
} else if (sym == 285)
return 258;
else { // sym is 286 or 287
destroyAndThrow(new DataFormatException("Reserved run length symbol: " + sym));
throw new AssertionError("Unreachable");
}
}
// Takes the given run length symbol in the range [0, 31], possibly reads some more input bits,
// and returns a number in the range [1, 32768]. This throws an IOException if bits needed to
// be read but the end of stream was reached or the underlying stream experienced an I/O exception.
private int decodeDistance(int sym) throws IOException {
assert 0 <= sym && sym <= 31;
if (sym <= 3)
return sym + 1;
else if (sym <= 29) {
int numExtraBits = (sym >>> 1) - 1;
return (((sym & 1) | 2) << numExtraBits) + 1 + readBits(numExtraBits);
} else { // sym is 30 or 31
destroyAndThrow(new DataFormatException("Reserved distance symbol: " + sym));
throw new AssertionError("Unreachable");
}
}
/*---- I/O methods ----*/
// Returns the given number of least significant bits from the bit buffer.
// This updates the bit buffer state and possibly also the byte buffer state.
private int readBits(int numBits) throws IOException {
// Check arguments and invariants
assert 1 <= numBits && numBits <= 16; // Note: DEFLATE uses up to 16, but this method is correct up to 31
assert 0 <= inputBitBufferLength && inputBitBufferLength <= 63;
assert inputBitBuffer >>> inputBitBufferLength == 0; // Ensure high-order bits are clean
// Ensure there is enough data in the bit buffer to satisfy the request
while (inputBitBufferLength < numBits) {
while (inputBufferIndex >= inputBufferLength) // Fill and retry
fillInputBuffer();
// Pack as many bytes as possible from input byte buffer into the bit buffer
int numBytes = Math.min((64 - inputBitBufferLength) >>> 3, inputBufferLength - inputBufferIndex);
if (numBytes <= 0)
throw new AssertionError("Impossible state");
for (int i = 0; i < numBytes; i++, inputBitBufferLength += 8, inputBufferIndex++)
inputBitBuffer |= (inputBuffer[inputBufferIndex] & 0xFFL) << inputBitBufferLength;
assert inputBitBufferLength <= 64; // Can temporarily be 64
}
// Extract the bits to return
int result = (int)inputBitBuffer & ((1 << numBits) - 1);
inputBitBuffer >>>= numBits;
inputBitBufferLength -= numBits;
// Check return and recheck invariants
assert result >>> numBits == 0;
assert 0 <= inputBitBufferLength && inputBitBufferLength <= 63;
assert inputBitBuffer >>> inputBitBufferLength == 0;
return result;
}
// Reads exactly 'len' bytes from {the input buffers or underlying input stream} into the
// given array subrange. This method alters the input buffer states, may throw an IOException,
// and would destroy the decompressor state if EOF occurs before the read length is satisfied.
private void readBytes(byte[] b, int off, int len) throws IOException {
// Check bit buffer invariants
if (inputBitBufferLength < 0 || inputBitBufferLength > 63
|| inputBitBuffer >>> inputBitBufferLength != 0)
throw new AssertionError("Invalid input bit buffer state");
// First unpack saved bits
alignInputToByte();
for (; len > 0 && inputBitBufferLength >= 8; off++, len--) {
b[off] = (byte)inputBitBuffer;
inputBitBuffer >>>= 8;
inputBitBufferLength -= 8;
}
// Read from input buffer
{
int n = Math.min(len, inputBufferLength - inputBufferIndex);
assert inputBitBufferLength == 0 || n == 0;
System.arraycopy(inputBuffer, inputBufferIndex, b, off, n);
inputBufferIndex += n;
off += n;
len -= n;
}
// Read directly from input stream (without putting into input buffer)
while (len > 0) {
assert inputBufferIndex == inputBufferLength;
int n = in.read(b, off, len);
if (n == -1)
destroyAndThrow(new EOFException("Unexpected end of stream"));
off += n;
len -= n;
}
}
// Fills the input byte buffer with new data read from the underlying input stream.
// Requires the buffer to be fully consumed before being called. This method sets
// inputBufferLength to a value in the range [-1, inputBuffer.length] and inputBufferIndex to 0.
private void fillInputBuffer() throws IOException {
if (state < -1)
throw new AssertionError("Must not read in this state");
if (inputBufferIndex < inputBufferLength)
throw new AssertionError("Input buffer not fully consumed yet");
if (isDetachable)
in.mark(inputBuffer.length);
inputBufferLength = in.read(inputBuffer);
inputBufferIndex = 0;
if (inputBufferLength == -1)
destroyAndThrow(new EOFException("Unexpected end of stream")); // Note: This sets inputBufferLength to 0
if (inputBufferLength < -1 || inputBufferLength > inputBuffer.length)
throw new AssertionError();
}
// Discards the remaining bits (0 to 7) in the current byte being read, if any. Always succeeds.
private void alignInputToByte() {
int discard = inputBitBufferLength & 7;
inputBitBuffer >>>= discard;
inputBitBufferLength -= discard;
assert inputBitBufferLength % 8 == 0;
}
/*---- State management methods ----*/
// Throws an IOException with the given reason, and destroys the state of this decompressor.
private void destroyAndThrow(IOException e) throws IOException {
state = -2;
exception = e;
destroyState();
// Do not set 'in' to null, so that calling close() is still possible
throw e;
}
// Clears all state variables except {in, state, exception}, to prevent accidental use of the
// stream thereafter. It is illegal to call read() or detach() after this method is called.
// The caller is responsible for manipulating the other state variables appropriately.
private void destroyState() {
isLastBlock = true;
literalLengthCodeTree = null;
literalLengthCodeTable = null;
distanceCodeTree = null;
distanceCodeTable = null;
inputBuffer = null;
inputBufferLength = 0;
inputBufferIndex = 0;
inputBitBuffer = 0;
inputBitBufferLength = 0;
outputBufferLength = 0;
outputBufferIndex = 0;
dictionary = null;
dictionaryIndex = 0;
}
/*---- Constants and tables ----*/
private static final int[] CODE_LENGTH_CODE_ORDER =
{16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15};
private static final short[] FIXED_LITERAL_LENGTH_CODE_TREE;
private static final short[] FIXED_LITERAL_LENGTH_CODE_TABLE;
private static final short[] FIXED_DISTANCE_CODE_TREE;
private static final short[] FIXED_DISTANCE_CODE_TABLE;
// For use in codeLengthsToCodeTree() only.
private static final short CODE_TREE_UNUSED_SLOT = 0x7000;
private static final short CODE_TREE_OPEN_SLOT = 0x7002;
// Any integer from 1 to 15 is valid. Affects speed but produces same output.
private static final int CODE_TABLE_BITS = 9;
private static final int CODE_TABLE_MASK = (1 << CODE_TABLE_BITS) - 1;
static {
byte[] llcodelens = new byte[288];
Arrays.fill(llcodelens, 0, 144, (byte)8);
Arrays.fill(llcodelens, 144, 256, (byte)9);
Arrays.fill(llcodelens, 256, 280, (byte)7);
Arrays.fill(llcodelens, 280, 288, (byte)8);
byte[] distcodelens = new byte[32];
Arrays.fill(distcodelens, (byte)5);
try {
FIXED_LITERAL_LENGTH_CODE_TREE = codeLengthsToCodeTree(llcodelens);
FIXED_DISTANCE_CODE_TREE = codeLengthsToCodeTree(distcodelens);
} catch (DataFormatException e) {
throw new AssertionError(e);
}
FIXED_LITERAL_LENGTH_CODE_TABLE = codeTreeToCodeTable(FIXED_LITERAL_LENGTH_CODE_TREE);
FIXED_DISTANCE_CODE_TABLE = codeTreeToCodeTable(FIXED_DISTANCE_CODE_TREE);
}
// Must be a power of 2. Do not change this constant value. If the value is decreased, then
// decompression may produce different data that violates the DEFLATE spec (but no crashes).
// If the value is increased, the behavior stays the same but memory is wasted with no benefit.
private static final int DICTIONARY_LENGTH = 32 * 1024;
// This is why the above must be a power of 2.
private static final int DICTIONARY_MASK = DICTIONARY_LENGTH - 1;
// The maximum size of extra output that can be generated that might not fit into the
// read buffer. This data needs to be saved for later.
private static final int OUTPUT_BUFFER_LENGTH = 257;
// For length symbols from 257 to 285 (inclusive). RUN_LENGTH_TABLE[i] =
// (base of run length) << 3 | (number of extra bits to read).
private static final short[] RUN_LENGTH_TABLE = {24, 32, 40, 48, 56, 64, 72, 80, 89, 105, 121, 137,
154, 186, 218, 250, 283, 347, 411, 475, 540, 668, 796, 924, 1053, 1309, 1565, 1821, 2064};
// For length symbols from 0 to 29 (inclusive). DISTANCE_TABLE[i] =
// (base of distance) << 4 | (number of extra bits to read).
private static final int[] DISTANCE_TABLE = {16, 32, 48, 64, 81, 113, 146, 210, 275, 403, 532, 788, 1045, 1557,
2070, 3094, 4119, 6167, 8216, 12312, 16409, 24601, 32794, 49178, 65563, 98331, 131100, 196636, 262173, 393245};
}