Repository: commons-compress Updated Branches: refs/heads/COMPRESS-380 [created] 2042aa001
COMPRESS-380 initial patch by Christian Marquez Grabia Project: http://git-wip-us.apache.org/repos/asf/commons-compress/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-compress/commit/d07f04b7 Tree: http://git-wip-us.apache.org/repos/asf/commons-compress/tree/d07f04b7 Diff: http://git-wip-us.apache.org/repos/asf/commons-compress/diff/d07f04b7 Branch: refs/heads/COMPRESS-380 Commit: d07f04b73c06c45b75f53f38b03b25c987b7bca5 Parents: e35049e Author: Stefan Bodewig <bode...@apache.org> Authored: Wed Jan 3 15:14:32 2018 +0100 Committer: Stefan Bodewig <bode...@apache.org> Committed: Wed Jan 3 15:14:32 2018 +0100 ---------------------------------------------------------------------- .../commons/compress/archivers/zip/ZipFile.java | 4 +- .../commons/compress/archivers/zip/ZipUtil.java | 2 + .../compressors/zip/Deflate64InputStream.java | 71 +++ .../compressors/zip/HuffmanDecoder.java | 445 +++++++++++++++++++ .../compress/compressors/zip/HuffmanState.java | 8 + .../zip/Deflate64InputStreamTest.java | 111 +++++ .../compressors/zip/HuffmanDecoderTest.java | 205 +++++++++ 7 files changed, 845 insertions(+), 1 deletion(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/main/java/org/apache/commons/compress/archivers/zip/ZipFile.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/compress/archivers/zip/ZipFile.java b/src/main/java/org/apache/commons/compress/archivers/zip/ZipFile.java index 9b13cf3..b7a41a3 100644 --- a/src/main/java/org/apache/commons/compress/archivers/zip/ZipFile.java +++ b/src/main/java/org/apache/commons/compress/archivers/zip/ZipFile.java @@ -42,6 +42,7 @@ import java.util.zip.InflaterInputStream; import java.util.zip.ZipException; import org.apache.commons.compress.compressors.bzip2.BZip2CompressorInputStream; +import org.apache.commons.compress.compressors.zip.Deflate64InputStream; import org.apache.commons.compress.utils.IOUtils; import static org.apache.commons.compress.archivers.zip.ZipConstants.DWORD; @@ -502,8 +503,9 @@ public class ZipFile implements Closeable { }; case BZIP2: return new BZip2CompressorInputStream(bis); - case AES_ENCRYPTED: case ENHANCED_DEFLATED: + return new Deflate64InputStream(bis, ze.getSize()); + case AES_ENCRYPTED: case EXPANDING_LEVEL_1: case EXPANDING_LEVEL_2: case EXPANDING_LEVEL_3: http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/main/java/org/apache/commons/compress/archivers/zip/ZipUtil.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/compress/archivers/zip/ZipUtil.java b/src/main/java/org/apache/commons/compress/archivers/zip/ZipUtil.java index 97fd341..d22a62e 100644 --- a/src/main/java/org/apache/commons/compress/archivers/zip/ZipUtil.java +++ b/src/main/java/org/apache/commons/compress/archivers/zip/ZipUtil.java @@ -295,6 +295,7 @@ public abstract class ZipUtil { } return null; } + static void copy(final byte[] from, final byte[] to, final int offset) { if (from != null) { System.arraycopy(from, 0, to, offset, from.length); @@ -330,6 +331,7 @@ public abstract class ZipUtil { || entry.getMethod() == ZipMethod.UNSHRINKING.getCode() || entry.getMethod() == ZipMethod.IMPLODING.getCode() || entry.getMethod() == ZipEntry.DEFLATED + || entry.getMethod() == ZipMethod.ENHANCED_DEFLATED.getCode() || entry.getMethod() == ZipMethod.BZIP2.getCode(); } http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/main/java/org/apache/commons/compress/compressors/zip/Deflate64InputStream.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/compress/compressors/zip/Deflate64InputStream.java b/src/main/java/org/apache/commons/compress/compressors/zip/Deflate64InputStream.java new file mode 100644 index 0000000..aeceb2a --- /dev/null +++ b/src/main/java/org/apache/commons/compress/compressors/zip/Deflate64InputStream.java @@ -0,0 +1,71 @@ +package org.apache.commons.compress.compressors.zip; + +import java.io.IOException; +import java.io.InputStream; + +import static org.apache.commons.compress.utils.IOUtils.closeQuietly; + +public class Deflate64InputStream extends InputStream { + private HuffmanDecoder decoder; + private long uncompressedSize; + private long totalRead = 0; + + public Deflate64InputStream(InputStream in, long uncompressedSize) { + this(new HuffmanDecoder(in), uncompressedSize); + } + + Deflate64InputStream(HuffmanDecoder decoder, long uncompressedSize) { + this.uncompressedSize = uncompressedSize; + this.decoder = decoder; + } + + @Override + public int read() throws IOException { + byte[] b = new byte[1]; + while (true) { + int r = read(b); + switch (r) { + case 1: + return b[0] & 0xFF; + case -1: + return -1; + case 0: + continue; + default: + throw new IllegalStateException("Invalid return value from read: " + r); + } + } + } + + @Override + public int read(byte[] b, int off, int len) throws IOException { + int read = -1; + if (decoder != null) { + read = decoder.decode(b, off, len); + if (read == -1) { + close(); + } else { + totalRead += read; + } + } + return read; + } + + @Override + public int available() throws IOException { + long available = 0; + if (decoder != null) { + available = uncompressedSize - totalRead; + if (Long.compare(available, Integer.MAX_VALUE) > 0) { + available = Integer.MAX_VALUE; + } + } + return (int) available; + } + + @Override + public void close() throws IOException { + closeQuietly(decoder); + decoder = null; + } +} http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanDecoder.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanDecoder.java b/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanDecoder.java new file mode 100644 index 0000000..de4984b --- /dev/null +++ b/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanDecoder.java @@ -0,0 +1,445 @@ +package org.apache.commons.compress.compressors.zip; + +import org.apache.commons.compress.utils.BitInputStream; + +import java.io.Closeable; +import java.io.IOException; +import java.io.InputStream; +import java.nio.ByteOrder; +import java.util.Arrays; + +import static org.apache.commons.compress.compressors.zip.HuffmanState.*; +import static org.apache.commons.compress.utils.IOUtils.closeQuietly; + +public class HuffmanDecoder implements Closeable { + /** + * -------------------------------------------------------------------- + * idx xtra base idx xtra base idx xtra base + * -------------------------------------------------------------------- + * 257 0 3 267 1 15,16 277 4 67-82 + * 258 0 4 268 1 17,18 278 4 83-98 + * 259 0 5 269 2 19-22 279 4 99-114 + * 260 0 6 270 2 23-26 280 4 115-130 + * 261 0 7 271 2 27-30 281 5 131-162 + * 262 0 8 272 2 31-34 282 5 163-194 + * 263 0 9 273 3 35-42 283 5 195-226 + * 264 0 10 274 3 43-50 284 5 227-257 + * 265 1 11,12 275 3 51-58 285 96 3 + * 266 1 13,14 276 3 59-66 + * -------------------------------------------------------------------- + * value = (base of run length) << 5 | (number of extra bits to read) + */ + private static final short[] RUN_LENGTH_TABLE = { + 96, 128, 160, 192, 224, 256, 288, 320, 353, 417, 481, 545, 610, 738, 866, + 994, 1123, 1379, 1635, 1891, 2148, 2660, 3172, 3684, 4197, 5221, 6245, 7269, 112 + }; + + /** + * -------------------------------------------------------------------- + * idx xtra dist idx xtra dist idx xtra dist + * -------------------------------------------------------------------- + * 0 0 1 10 4 33-48 20 9 1025-1536 + * 1 0 2 11 4 49-64 21 9 1537-2048 + * 2 0 3 12 5 65-96 22 10 2049-3072 + * 3 0 4 13 5 97-128 23 10 3073-4096 + * 4 1 5,6 14 6 129-192 24 11 4097-6144 + * 5 1 7,8 15 6 193-256 25 11 6145-8192 + * 6 2 9-12 16 7 257-384 26 12 8193-12288 + * 7 2 13-16 17 7 385-512 27 12 12289-16384 + * 8 3 17-24 18 8 513-768 28 13 16385-24576 + * 9 3 25-32 19 8 769-1024 29 13 24577-32768 + * 30 14 32769-49152 + * 31 14 49153-65536 + * -------------------------------------------------------------------- + * value = (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, // 0-9 + 532, 788, 1045, 1557, 2070, 3094, 4119, 6167, 8216, 12312, // 10-19 + 16409, 24601, 32794, 49178, 65563, 98331, 131100, 196636, 262173, 393245, // 20-29 + 524318, 786462 // 30-31 + }; + + /** + * When using dynamic huffman codes the order in which the values are stored + * follows the positioning below + */ + private static final int[] CODE_LENGTHS_ORDER = + {16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15}; + + /** + * Huffman Fixed Literal / Distance tables for mode 1 + */ + private static final int[] FIXED_LITERALS; + private static final int[] FIXED_DISTANCE; + + static { + FIXED_LITERALS = new int[288]; + Arrays.fill(FIXED_LITERALS, 0, 144, 8); + Arrays.fill(FIXED_LITERALS, 144, 256, 9); + Arrays.fill(FIXED_LITERALS, 256, 280, 7); + Arrays.fill(FIXED_LITERALS, 280, 288, 8); + + FIXED_DISTANCE = new int[32]; + Arrays.fill(FIXED_DISTANCE, 5); + } + + private boolean finalBlock = false; + private DecoderState state; + private BitInputStream reader; + + private final DecodingMemory memory = new DecodingMemory(); + + HuffmanDecoder(InputStream in) { + this(new BitInputStream(in, ByteOrder.LITTLE_ENDIAN)); + } + + private HuffmanDecoder(BitInputStream reader) { + this.reader = reader; + state = new InitialState(); + } + + @Override + public void close() { + closeQuietly(reader); + reader = null; + } + + public int decode(byte[] b) throws IOException { + return decode(b, 0, b.length); + } + + public int decode(byte[] b, int off, int len) throws IOException { + while (!finalBlock || state.hasData()) { + switch (state.state()) { + case INITIAL: + finalBlock = reader.readBits(1) == 1; + int mode = (int) reader.readBits(2); + switch (mode) { + case 0: + reader.readBits(Byte.SIZE - 3); + long bLen = reader.readBits(16); + long bNLen = reader.readBits(16); + if (((bLen ^ 0xFFFF) & 0xFFFF) != bNLen) { + //noinspection DuplicateStringLiteralInspection + throw new IllegalStateException("Illegal LEN / NLEN values"); + } + state = new UncompressedState((int) bLen); + break; + case 1: + state = new HuffmanCodes(FIXED_CODES, FIXED_LITERALS, FIXED_DISTANCE); + break; + case 2: + int literals = (int) (reader.readBits(5) + 257); + int[] literalTable = new int[literals]; + + int distances = (int) (reader.readBits(5) + 1); + int[] distanceTable = new int[distances]; + + populateDynamicTables(reader, literalTable, distanceTable); + + state = new HuffmanCodes(DYNAMIC_CODES, literalTable, distanceTable); + break; + default: + throw new IllegalStateException("Unsupported compression: " + mode); + } + break; + default: + return state.read(b, off, len); + } + } + return -1; + } + + + private static abstract class DecoderState { + abstract HuffmanState state(); + + abstract int read(byte[] b, int off, int len) throws IOException; + + abstract boolean hasData(); + } + + private class UncompressedState extends DecoderState { + private final int blockLength; + private int read; + + private UncompressedState(int blockLength) { + this.blockLength = blockLength; + } + + @Override + HuffmanState state() { + return read < blockLength ? STORED : INITIAL; + } + + @Override + int read(byte[] b, int off, int len) throws IOException { + int max = Math.min(blockLength - read, len); + for (int i = 0; i < max; i++) { + byte next = (byte) (reader.readBits(Byte.SIZE) & 0xFF); + b[off + i] = memory.add(next); + read++; + } + return max; + } + + @Override + boolean hasData() { + return read < blockLength; + } + } + + private class InitialState extends DecoderState { + @Override + HuffmanState state() { + return INITIAL; + } + + @Override + int read(byte[] b, int off, int len) throws IOException { + throw new IllegalStateException("Cannot read in this state"); + } + + @Override + boolean hasData() { + return false; + } + } + + private class HuffmanCodes extends DecoderState { + private boolean endOfBlock = false; + private final HuffmanState state; + private final BinaryTreeNode lengthTree; + private final BinaryTreeNode distanceTree; + + private int runBufferPos = 0; + private byte[] runBuffer = new byte[0]; + + HuffmanCodes(HuffmanState state, int[] lengths, int[] distance) { + this.state = state; + lengthTree = buildTree(lengths); + distanceTree = buildTree(distance); + } + + @Override + HuffmanState state() { + return endOfBlock ? INITIAL : state; + } + + @Override + int read(byte[] b, int off, int len) throws IOException { + return decodeNext(b, off, len); + } + + private int decodeNext(byte[] b, int off, int len) throws IOException { + if (endOfBlock) { + return -1; + } + int result = copyFromRunBuffer(b, off, len); + + while (result < len) { + int symbol = nextSymbol(reader, lengthTree); + if (symbol < 256) { + b[off + result++] = memory.add((byte) (symbol & 0xFF)); + } else if (symbol > 256) { + int runMask = RUN_LENGTH_TABLE[symbol - 257]; + int run = runMask >>> 5; + int runXtra = runMask & 0x1F; + run += reader.readBits(runXtra); + + int distSym = nextSymbol(reader, distanceTree); + + int distMask = DISTANCE_TABLE[distSym]; + int dist = distMask >>> 4; + int distXtra = distMask & 0xF; + dist += reader.readBits(distXtra); + + runBuffer = new byte[run]; + runBufferPos = 0; + memory.recordToBuffer(dist, run, runBuffer); + + result += copyFromRunBuffer(b, off + result, len - result); + } else { + endOfBlock = true; + return result; + } + } + + return result; + } + + private int copyFromRunBuffer(byte[] b, int off, int len) { + int bytesInBuffer = runBuffer.length - runBufferPos; + int copiedBytes = 0; + if (bytesInBuffer > 0) { + copiedBytes = Math.min(len, bytesInBuffer); + System.arraycopy(runBuffer, runBufferPos, b, off, copiedBytes); + runBufferPos += copiedBytes; + } + return copiedBytes; + } + + @Override + boolean hasData() { + return !endOfBlock; + } + } + + private static int nextSymbol(BitInputStream reader, BinaryTreeNode tree) throws IOException { + BinaryTreeNode node = tree; + while (node != null && node.literal == -1) { + long bit = reader.readBits(1); + node = bit == 0 ? node.left : node.right; + } + return node != null ? node.literal : -1; + } + + private static void populateDynamicTables(BitInputStream reader, int[] literals, int[] distances) throws IOException { + int codeLengths = (int) (reader.readBits(4) + 4); + + int[] codeLengthValues = new int[19]; + for (int cLen = 0; cLen < codeLengths; cLen++) { + codeLengthValues[CODE_LENGTHS_ORDER[cLen]] = (int) reader.readBits(3); + } + + BinaryTreeNode codeLengthTree = buildTree(codeLengthValues); + + int[] auxBuffer = new int[literals.length + distances.length]; + + int value = -1, length = 0; + for (int i = 0; i < auxBuffer.length; ) { + if (length > 0) { + auxBuffer[i++] = value; + length--; + } else { + int symbol = nextSymbol(reader, codeLengthTree); + if (symbol < 16) { + value = symbol; + auxBuffer[i++] = value; + } else if (symbol == 16) { + length = (int) (reader.readBits(2) + 3); + } else if (symbol == 17) { + value = 0; + length = (int) (reader.readBits(3) + 3); + } else if (symbol == 18) { + value = 0; + length = (int) (reader.readBits(7) + 11); + } + } + } + + System.arraycopy(auxBuffer, 0, literals, 0, literals.length); + System.arraycopy(auxBuffer, literals.length, distances, 0, distances.length); + } + + private static class BinaryTreeNode { + private final int bits; + int literal = -1; + BinaryTreeNode left, right; + + private BinaryTreeNode(int bits) { + this.bits = bits; + } + + void leaf(int symbol) { + literal = symbol; + left = null; + right = null; + } + + BinaryTreeNode left() { + if (left == null && literal == -1) { + left = new BinaryTreeNode(bits + 1); + } + return left; + } + + BinaryTreeNode right() { + if (right == null && literal == -1) { + right = new BinaryTreeNode(bits + 1); + } + return right; + } + } + + private static BinaryTreeNode buildTree(int[] litTable) { + int[] literalCodes = getCodes(litTable); + + BinaryTreeNode root = new BinaryTreeNode(0); + + for (int i = 0; i < litTable.length; i++) { + int len = litTable[i]; + if (len != 0) { + BinaryTreeNode node = root; + int lit = literalCodes[len - 1]; + for (int p = len - 1; p >= 0; p--) { + int bit = lit & (1 << p); + node = bit == 0 ? node.left() : node.right(); + } + node.leaf(i); + literalCodes[len - 1]++; + } + } + return root; + } + + private static int[] getCodes(int[] litTable) { + int max = 0; + int[] blCount = new int[65]; + + for (int aLitTable : litTable) { + max = Math.max(max, aLitTable); + blCount[aLitTable]++; + } + blCount = Arrays.copyOf(blCount, max + 1); + + int code = 0; + int[] nextCode = new int[max + 1]; + for (int i = 0; i <= max; i++) { + code = (code + blCount[i]) << 1; + nextCode[i] = code; + } + + return nextCode; + } + + private static class DecodingMemory { + private final byte[] memory; + private final int mask; + private int wHead; + + private DecodingMemory() { + this(16); + } + + private DecodingMemory(int bits) { + memory = new byte[1 << bits]; + Arrays.fill(memory, (byte) -1); + mask = memory.length - 1; + } + + byte add(byte b) { + memory[wHead] = b; + wHead = incCounter(wHead); + return b; + } + + void recordToBuffer(int distance, int length, byte[] buff) { + if (distance > memory.length) { + throw new IllegalStateException("Illegal distance parameter: " + distance); + } + int start = (wHead - distance) & mask; + if (memory[start] == -1) { + throw new IllegalStateException("Attempt to read beyond memory: dist=" + distance); + } + for (int i = 0, pos = start; i < length; i++, pos = incCounter(pos)) { + buff[i] = add(memory[pos]); + } + } + + private int incCounter(int counter) { + return (counter + 1) & mask; + } + } +} http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanState.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanState.java b/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanState.java new file mode 100644 index 0000000..c871955 --- /dev/null +++ b/src/main/java/org/apache/commons/compress/compressors/zip/HuffmanState.java @@ -0,0 +1,8 @@ +package org.apache.commons.compress.compressors.zip; + +enum HuffmanState { + INITIAL, + STORED, + DYNAMIC_CODES, + FIXED_CODES +} http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/test/java/org/apache/commons/compress/compressors/zip/Deflate64InputStreamTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/compress/compressors/zip/Deflate64InputStreamTest.java b/src/test/java/org/apache/commons/compress/compressors/zip/Deflate64InputStreamTest.java new file mode 100644 index 0000000..f5f7943 --- /dev/null +++ b/src/test/java/org/apache/commons/compress/compressors/zip/Deflate64InputStreamTest.java @@ -0,0 +1,111 @@ +package org.apache.commons.compress.compressors.zip; + +import org.junit.Test; +import org.junit.runner.RunWith; +import org.mockito.Mock; +import org.mockito.Mockito; +import org.mockito.runners.MockitoJUnitRunner; + +import java.io.BufferedReader; +import java.io.ByteArrayInputStream; +import java.io.InputStreamReader; + +import static org.junit.Assert.assertEquals; +import static org.mockito.Mockito.times; + +@RunWith(MockitoJUnitRunner.class) +public class Deflate64InputStreamTest +{ + private final HuffmanDecoder nullDecoder = null; + + @Mock + private HuffmanDecoder decoder; + + @Test + public void readWhenClosed() throws Exception + { + long size = Integer.MAX_VALUE - 1; + Deflate64InputStream input = new Deflate64InputStream(nullDecoder, size); + assertEquals(-1, input.read()); + assertEquals(-1, input.read(new byte[1])); + assertEquals(-1, input.read(new byte[1], 0, 1)); + } + + @Test + public void properSizeWhenClosed() throws Exception + { + long size = Integer.MAX_VALUE - 1; + Deflate64InputStream input = new Deflate64InputStream(nullDecoder, size); + assertEquals(0, input.available()); + } + + @Test + public void properSizeWhenInRange() throws Exception + { + long size = Integer.MAX_VALUE - 1; + Deflate64InputStream input = new Deflate64InputStream(decoder, size); + assertEquals(size, input.available()); + } + + @Test + public void properSizeWhenOutOfRange() throws Exception + { + long size = Integer.MAX_VALUE + 1L; + Deflate64InputStream input = new Deflate64InputStream(decoder, size); + assertEquals(Integer.MAX_VALUE, input.available()); + } + + @Test + public void properSizeAfterReading() throws Exception + { + byte[] buf = new byte[4096]; + int offset = 1000; + int length = 3096; + + Mockito.when(decoder.decode(buf, offset, length)).thenReturn(2048); + + long size = Integer.MAX_VALUE + 2047L; + Deflate64InputStream input = new Deflate64InputStream(decoder, size); + assertEquals(2048, input.read(buf, offset, length)); + assertEquals(Integer.MAX_VALUE - 1, input.available()); + } + + @Test + public void closeCallsDecoder() throws Exception + { + + Deflate64InputStream input = new Deflate64InputStream(decoder, 10); + input.close(); + + Mockito.verify(decoder, times(1)).close(); + } + + @Test + public void closeIsDelegatedJustOnce() throws Exception + { + + Deflate64InputStream input = new Deflate64InputStream(decoder, 10); + + input.close(); + input.close(); + + Mockito.verify(decoder, times(1)).close(); + } + + @Test + public void uncompressedBlock() throws Exception + { + byte[] data = { + 1, 11, 0, -12, -1, + 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd' + }; + + try (Deflate64InputStream input = new Deflate64InputStream(new ByteArrayInputStream(data), 11); + BufferedReader br = new BufferedReader(new InputStreamReader(input))) + { + assertEquals("Hello World", br.readLine()); + assertEquals(null, br.readLine()); + } + } + +} \ No newline at end of file http://git-wip-us.apache.org/repos/asf/commons-compress/blob/d07f04b7/src/test/java/org/apache/commons/compress/compressors/zip/HuffmanDecoderTest.java ---------------------------------------------------------------------- diff --git a/src/test/java/org/apache/commons/compress/compressors/zip/HuffmanDecoderTest.java b/src/test/java/org/apache/commons/compress/compressors/zip/HuffmanDecoderTest.java new file mode 100644 index 0000000..27d0905 --- /dev/null +++ b/src/test/java/org/apache/commons/compress/compressors/zip/HuffmanDecoderTest.java @@ -0,0 +1,205 @@ +package org.apache.commons.compress.compressors.zip; + +import org.junit.Test; + +import java.io.ByteArrayInputStream; +import java.util.Arrays; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class HuffmanDecoderTest { + @Test + public void decodeUncompressedBlock() throws Exception { + byte[] data = { + 0b1, // end of block + no compression mode + 11, 0, -12, -1, // len & ~len + 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd' + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[100]; + int len = decoder.decode(result); + + assertEquals(11, len); + assertEquals("Hello World", new String(result, 0, len)); + } + + @Test + public void decodeUncompressedBlockWithInvalidLenNLenValue() throws Exception { + byte[] data = { + 0b1, // end of block + no compression mode + 11, 0, -12, -2, // len & ~len + 'H', 'e', 'l', 'l', 'o', ' ', 'W', 'o', 'r', 'l', 'd' + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[100]; + try { + int len = decoder.decode(result); + fail("Should have failed but returned " + len + " entries: " + Arrays.toString(Arrays.copyOf(result, len))); + } catch (IllegalStateException e) { + assertEquals("Illegal LEN / NLEN values", e.getMessage()); + } + } + + @Test + public void decodeSimpleFixedHuffmanBlock() throws Exception { + byte[] data = { + //|--- binary filling ---|76543210 + 0b11111111111111111111111111110011, // final block + fixed huffman + H + 0b00000000000000000000000001001000, // H + e + 0b11111111111111111111111111001101, // e + l + 0b11111111111111111111111111001001, // l + l + 0b11111111111111111111111111001001, // l + o + 0b00000000000000000000000001010111, // o + ' ' + 0b00000000000000000000000000001000, // ' ' + W + 0b11111111111111111111111111001111, // W + o + 0b00000000000000000000000000101111, // o + r + 0b11111111111111111111111111001010, // r + l + 0b00000000000000000000000001001001, // l + d + 0b00000000000000000000000000000001, // d + end of block + 0b11111111111111111111111111111100 // end of block (00) + garbage + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[100]; + int len = decoder.decode(result); + + assertEquals(11, len); + assertEquals("Hello World", new String(result, 0, len)); + } + + @Test + public void decodeSimpleFixedHuffmanBlockToSmallBuffer() throws Exception { + byte[] data = { + //|--- binary filling ---|76543210 + 0b11111111111111111111111111110011, // final block + fixed huffman + H + 0b00000000000000000000000001001000, // H + e + 0b11111111111111111111111111001101, // e + l + 0b11111111111111111111111111001001, // l + l + 0b11111111111111111111111111001001, // l + o + 0b00000000000000000000000001010111, // o + ' ' + 0b00000000000000000000000000001000, // ' ' + W + 0b11111111111111111111111111001111, // W + o + 0b00000000000000000000000000101111, // o + r + 0b11111111111111111111111111001010, // r + l + 0b00000000000000000000000001001001, // l + d + 0b00000000000000000000000000000001, // d + end of block + 0b11111111111111111111111111111100 // end of block (00) + garbage + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[10]; + int len; + len = decoder.decode(result); + assertEquals(10, len); + assertEquals("Hello Worl", new String(result, 0, len)); + len = decoder.decode(result); + assertEquals(1, len); + assertEquals("d", new String(result, 0, len)); + } + + + @Test + public void decodeFixedHuffmanBlockWithMemoryLookup() throws Exception { + byte[] data = { + //|--- binary filling ---|76543210 + 0b11111111111111111111111111110011, // final block + fixed huffman + H + 0b00000000000000000000000001001000, // H + e + 0b11111111111111111111111111001101, // e + l + 0b11111111111111111111111111001001, // l + l + 0b11111111111111111111111111001001, // l + o + 0b00000000000000000000000001010111, // o + ' ' + 0b00000000000000000000000000001000, // ' ' + W + 0b11111111111111111111111111001111, // W + o + 0b00000000000000000000000000101111, // o + r + 0b11111111111111111111111111001010, // r + l + 0b00000000000000000000000001001001, // l + d + 0b11111111111111111111111111100001, // d + '\n' + 0b00000000000000000000000000100010, // '\n' + <len> + 0b11111111111111111111111110000110, // <len> + offset <001> + dist6 + 0b00000000000000000000000000001101, // dist6 + offset <11> + end of block (000000) + 0b11111111111111111111111111111000 // end of block (0000) + garbage + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[100]; + int len = decoder.decode(result); + + assertEquals(48, len); + assertEquals("Hello World\nHello World\nHello World\nHello World\n", new String(result, 0, len)); + } + + @Test + public void decodeFixedHuffmanBlockWithMemoryLookupInSmallBuffer() throws Exception { + byte[] data = { + //|--- binary filling ---|76543210 + 0b11111111111111111111111111110011, // final block + fixed huffman + H + 0b00000000000000000000000001001000, // H + e + 0b11111111111111111111111111001101, // e + l + 0b11111111111111111111111111001001, // l + l + 0b11111111111111111111111111001001, // l + o + 0b00000000000000000000000001010111, // o + ' ' + 0b00000000000000000000000000001000, // ' ' + W + 0b11111111111111111111111111001111, // W + o + 0b00000000000000000000000000101111, // o + r + 0b11111111111111111111111111001010, // r + l + 0b00000000000000000000000001001001, // l + d + 0b11111111111111111111111111100001, // d + '\n' + 0b00000000000000000000000000100010, // '\n' + <len> + 0b11111111111111111111111110000110, // <len> + offset <001> + dist6 + 0b00000000000000000000000000001101, // dist6 + offset <11> + end of block (000000) + 0b11111111111111111111111111111000 // end of block (0000) + garbage + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[30]; + int len; + + len = decoder.decode(result); + assertEquals(30, len); + assertEquals("Hello World\nHello World\nHello ", new String(result, 0, len)); + + len = decoder.decode(result); + assertEquals(18, len); + assertEquals("World\nHello World\n", new String(result, 0, len)); + } + + @Test + public void decodeFixedHuffmanBlockWithMemoryLookupInExactBuffer() throws Exception { + byte[] data = { + //|--- binary filling ---|76543210 + 0b11111111111111111111111111110011, // final block + fixed huffman + H + 0b00000000000000000000000001001000, // H + e + 0b11111111111111111111111111001101, // e + l + 0b11111111111111111111111111001001, // l + l + 0b11111111111111111111111111001001, // l + o + 0b00000000000000000000000001010111, // o + ' ' + 0b00000000000000000000000000001000, // ' ' + W + 0b11111111111111111111111111001111, // W + o + 0b00000000000000000000000000101111, // o + r + 0b11111111111111111111111111001010, // r + l + 0b00000000000000000000000001001001, // l + d + 0b11111111111111111111111111100001, // d + '\n' + 0b00000000000000000000000000100010, // '\n' + <len> + 0b11111111111111111111111110000110, // <len> + offset <001> + dist6 + 0b00000000000000000000000000001101, // dist6 + offset <11> + end of block (000000) + 0b11111111111111111111111111111000 // end of block (0000) + garbage + }; + + HuffmanDecoder decoder = new HuffmanDecoder(new ByteArrayInputStream(data)); + byte[] result = new byte[48]; + int len; + + len = decoder.decode(result); + assertEquals(48, len); + assertEquals("Hello World\nHello World\nHello World\nHello World\n", new String(result, 0, len)); + + len = decoder.decode(result); + assertEquals(0, len); + + len = decoder.decode(result); + assertEquals(-1, len); + } +} \ No newline at end of file
