You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by bo...@apache.org on 2013/12/15 16:23:36 UTC
svn commit: r1551026 - in
/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress:
archivers/zip/UnshrinkingInputStream.java
compressors/z/AbstractLZWInputStream.java
compressors/z/ZCompressorInputStream.java
Author: bodewig
Date: Sun Dec 15 15:23:35 2013
New Revision: 1551026
URL: http://svn.apache.org/r1551026
Log:
reduce code duplication in the two LZW input streams
Added:
commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java (with props)
Modified:
commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java
commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java
Modified: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java
URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java?rev=1551026&r1=1551025&r2=1551026&view=diff
==============================================================================
--- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java (original)
+++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java Sun Dec 15 15:23:35 2013
@@ -21,84 +21,43 @@ package org.apache.commons.compress.arch
import java.io.IOException;
import java.io.InputStream;
-import org.apache.commons.compress.compressors.CompressorInputStream;
+import org.apache.commons.compress.compressors.z.AbstractLZWInputStream;
/**
* Input stream that decompresses ZIP method 1 (unshrinking). A variation of the LZW algorithm, with some twists.
* @NotThreadSafe
* @since 1.7
*/
-class UnshrinkingInputStream extends CompressorInputStream {
- private final InputStream in;
- private final int clearCode;
- private final int MAX_CODE_SIZE = 13;
- private int codeSize = 9;
- private int bitsCached = 0;
- private int bitsCachedSize = 0;
- private int previousCode = -1;
- private int tableSize = 0;
- private final int[] prefixes;
- private final byte[] characters;
+class UnshrinkingInputStream extends AbstractLZWInputStream {
+ private static final int MAX_CODE_SIZE = 13;
+ private static final int MAX_TABLE_SIZE = 1 << MAX_CODE_SIZE;
private final boolean[] isUsed;
- private final byte[] outputStack;
- private int outputStackLocation;
public UnshrinkingInputStream(InputStream inputStream) throws IOException {
- this.in = inputStream;
- clearCode = (1 << (codeSize - 1));
- final int maxTableSize = 1 << MAX_CODE_SIZE;
- prefixes = new int[maxTableSize];
- characters = new byte[maxTableSize];
- isUsed = new boolean[maxTableSize];
- outputStack = new byte[maxTableSize];
- outputStackLocation = maxTableSize;
+ super(inputStream);
+ setClearCode(codeSize);
+ initializeTables(MAX_CODE_SIZE);
+ isUsed = new boolean[prefixes.length];
for (int i = 0; i < (1 << 8); i++) {
- prefixes[i] = -1;
- characters[i] = (byte)i;
isUsed[i] = true;
}
tableSize = clearCode + 1;
}
-
- public void close() throws IOException {
- in.close();
- }
-
- private int readNextCode() throws IOException {
- while (bitsCachedSize < codeSize) {
- final int nextByte = in.read();
- if (nextByte < 0) {
- return nextByte;
- }
- bitsCached |= (nextByte << bitsCachedSize);
- bitsCachedSize += 8;
- }
- final int mask = (1 << codeSize) - 1;
- final int code = (bitsCached & mask);
- bitsCached >>>= codeSize;
- bitsCachedSize -= codeSize;
- return code;
- }
-
- private int addEntry(int previousCode, byte character) throws IOException {
- final int maxTableSize = 1 << MAX_CODE_SIZE;
- while ((tableSize < maxTableSize) && isUsed[tableSize]) {
+
+ @Override
+ protected int addEntry(int previousCode, byte character) throws IOException {
+ while ((tableSize < MAX_TABLE_SIZE) && isUsed[tableSize]) {
tableSize++;
}
- if (tableSize < maxTableSize) {
- final int index = tableSize;
- prefixes[tableSize] = previousCode;
- characters[tableSize] = character;
- isUsed[tableSize] = true;
- tableSize++;
- return index;
- } else {
- return -1;
+ int idx = addEntry(previousCode, character, MAX_TABLE_SIZE);
+ if (idx >= 0) {
+ isUsed[idx] = true;
}
+ return idx;
}
private void partialClear() throws IOException {
- final boolean[] isParent = new boolean[1 << MAX_CODE_SIZE];
+ final boolean[] isParent = new boolean[MAX_TABLE_SIZE];
for (int i = 0; i < isUsed.length; i++) {
if (isUsed[i] && prefixes[i] != -1) {
isParent[prefixes[i]] = true;
@@ -112,7 +71,8 @@ class UnshrinkingInputStream extends Com
}
}
- private int decompressNextSymbol() throws IOException {
+ @Override
+ protected int decompressNextSymbol() throws IOException {
//
// table entry table entry
// _____________ _____
@@ -147,76 +107,12 @@ class UnshrinkingInputStream extends Com
return 0;
} else {
boolean addedUnfinishedEntry = false;
- final int effectiveCode;
- if (isUsed[code]) {
- effectiveCode = code;
- } else {
- // must be a repeat of the previous entry we haven't added yet
- if (previousCode == -1) {
- // ... which isn't possible for the very first code
- throw new IOException("The first code can't be a reference to its preceding code");
- }
- byte firstCharacter = 0;
- for (int last = previousCode; last >= 0; last = prefixes[last]) {
- firstCharacter = characters[last];
- }
- effectiveCode = addEntry(previousCode, firstCharacter);
+ int effectiveCode = code;
+ if (!isUsed[code]) {
+ effectiveCode = addRepeatOfPreviousCode();
addedUnfinishedEntry = true;
}
- for (int entry = effectiveCode; entry >= 0; entry = prefixes[entry]) {
- outputStack[--outputStackLocation] = characters[entry];
- }
- if (previousCode != -1 && !addedUnfinishedEntry) {
- addEntry(previousCode, outputStack[outputStackLocation]);
- }
- previousCode = code;
- return outputStackLocation;
- }
- }
-
- public int read() throws IOException {
- byte[] b = new byte[1];
- int ret;
- while ((ret = read(b)) == 0) {
- }
- if (ret < 0) {
- return ret;
- }
- return 0xff & b[0];
- }
-
- public int read(byte[] b, int off, int len) throws IOException {
- int bytesRead = 0;
- int remainingInStack = outputStack.length - outputStackLocation;
- if (remainingInStack > 0) {
- int maxLength = Math.min(remainingInStack, len);
- System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
- outputStackLocation += maxLength;
- off += maxLength;
- len -= maxLength;
- bytesRead += maxLength;
- }
- while (len > 0) {
- int result = decompressNextSymbol();
- if (result < 0) {
- if (bytesRead > 0) {
- count(bytesRead);
- return bytesRead;
- } else {
- return result;
- }
- }
- remainingInStack = outputStack.length - outputStackLocation;
- if (remainingInStack > 0) {
- int maxLength = Math.min(remainingInStack, len);
- System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
- outputStackLocation += maxLength;
- off += maxLength;
- len -= maxLength;
- bytesRead += maxLength;
- }
+ return expandCodeToOutputStack(effectiveCode, addedUnfinishedEntry);
}
- count(bytesRead);
- return bytesRead;
}
}
Added: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java
URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java?rev=1551026&view=auto
==============================================================================
--- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java (added)
+++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java Sun Dec 15 15:23:35 2013
@@ -0,0 +1,201 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.commons.compress.compressors.z;
+
+import java.io.IOException;
+import java.io.InputStream;
+
+import org.apache.commons.compress.compressors.CompressorInputStream;
+
+/**
+ * Base-class for traditional Unix ".Z" compression and the
+ * Unshrinking method of ZIP archive.
+ * @NotThreadSafe
+ * @since 1.7
+ */
+public abstract class AbstractLZWInputStream extends CompressorInputStream {
+ private final byte[] oneByte = new byte[1];
+
+ protected final InputStream in;
+ protected int clearCode = -1;
+ protected int codeSize = 9;
+ protected int bitsCached = 0;
+ protected int bitsCachedSize = 0;
+ protected int previousCode = -1;
+ protected int tableSize = 0;
+ protected int[] prefixes;
+ protected byte[] characters;
+ private byte[] outputStack;
+ private int outputStackLocation;
+
+ public AbstractLZWInputStream(InputStream inputStream) throws IOException {
+ this.in = inputStream;
+ }
+
+ @Override
+ public void close() throws IOException {
+ in.close();
+ }
+
+ @Override
+ public int read() throws IOException {
+ int ret;
+ while ((ret = read(oneByte)) == 0) { // NOPMD
+ }
+ if (ret < 0) {
+ return ret;
+ }
+ return 0xff & oneByte[0];
+ }
+
+ @Override
+ public int read(byte[] b, int off, int len) throws IOException {
+ int bytesRead = 0;
+ int remainingInStack = outputStack.length - outputStackLocation;
+ if (remainingInStack > 0) {
+ int maxLength = Math.min(remainingInStack, len);
+ System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
+ outputStackLocation += maxLength;
+ off += maxLength;
+ len -= maxLength;
+ bytesRead += maxLength;
+ }
+ while (len > 0) {
+ int result = decompressNextSymbol();
+ if (result < 0) {
+ if (bytesRead > 0) {
+ count(bytesRead);
+ return bytesRead;
+ } else {
+ return result;
+ }
+ }
+ remainingInStack = outputStack.length - outputStackLocation;
+ if (remainingInStack > 0) {
+ int maxLength = Math.min(remainingInStack, len);
+ System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
+ outputStackLocation += maxLength;
+ off += maxLength;
+ len -= maxLength;
+ bytesRead += maxLength;
+ }
+ }
+ count(bytesRead);
+ return bytesRead;
+ }
+
+ /**
+ * Read the next code and expand it.
+ */
+ protected abstract int decompressNextSymbol() throws IOException;
+
+ /**
+ * Add a new entry to the dictionary.
+ */
+ protected abstract int addEntry(int previousCode, byte character)
+ throws IOException;
+
+ /**
+ * Sets the clear code based on the code size.
+ */
+ protected void setClearCode(int codeSize) {
+ clearCode = (1 << (codeSize - 1));
+ }
+
+ /**
+ * Initializes the arrays based on the maximum code size.
+ */
+ protected void initializeTables(int maxCodeSize) {
+ final int maxTableSize = 1 << maxCodeSize;
+ prefixes = new int[maxTableSize];
+ characters = new byte[maxTableSize];
+ outputStack = new byte[maxTableSize];
+ outputStackLocation = maxTableSize;
+ final int max = 1 << 8;
+ for (int i = 0; i < max; i++) {
+ prefixes[i] = -1;
+ characters[i] = (byte) i;
+ }
+ }
+
+ /**
+ * Reads the next code from the stream.
+ */
+ protected int readNextCode() throws IOException {
+ while (bitsCachedSize < codeSize) {
+ final int nextByte = in.read();
+ if (nextByte < 0) {
+ return nextByte;
+ }
+ bitsCached |= (nextByte << bitsCachedSize);
+ bitsCachedSize += 8;
+ }
+ final int mask = (1 << codeSize) - 1;
+ final int code = (bitsCached & mask);
+ bitsCached >>>= codeSize;
+ bitsCachedSize -= codeSize;
+ return code;
+ }
+
+ /**
+ * Adds a new entry if the maximum table size hasn't been exceeded
+ * and returns the new index.
+ */
+ protected int addEntry(int previousCode, byte character, int maxTableSize) {
+ if (tableSize < maxTableSize) {
+ final int index = tableSize;
+ prefixes[tableSize] = previousCode;
+ characters[tableSize] = character;
+ tableSize++;
+ return index;
+ }
+ return -1;
+ }
+
+ /**
+ * Add entry for repeat of previousCode we haven't added, yet.
+ */
+ protected int addRepeatOfPreviousCode() throws IOException {
+ if (previousCode == -1) {
+ // can't have a repeat for the very first code
+ throw new IOException("The first code can't be a reference to its preceding code");
+ }
+ byte firstCharacter = 0;
+ for (int last = previousCode; last >= 0; last = prefixes[last]) {
+ firstCharacter = characters[last];
+ }
+ return addEntry(previousCode, firstCharacter);
+ }
+
+ /**
+ * Expands the entry with index code to the output stack and may
+ * create a new entry
+ */
+ protected int expandCodeToOutputStack(int code, boolean addedUnfinishedEntry)
+ throws IOException {
+ for (int entry = code; entry >= 0; entry = prefixes[entry]) {
+ outputStack[--outputStackLocation] = characters[entry];
+ }
+ if (previousCode != -1 && !addedUnfinishedEntry) {
+ addEntry(previousCode, outputStack[outputStackLocation]);
+ }
+ previousCode = code;
+ return outputStackLocation;
+ }
+}
Propchange: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java
URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java?rev=1551026&r1=1551025&r2=1551026&view=diff
==============================================================================
--- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java (original)
+++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java Sun Dec 15 15:23:35 2013
@@ -21,35 +21,22 @@ package org.apache.commons.compress.comp
import java.io.IOException;
import java.io.InputStream;
-import org.apache.commons.compress.compressors.CompressorInputStream;
-
/**
* Input stream that decompresses .Z files.
* @NotThreadSafe
* @since 1.7
*/
-public class ZCompressorInputStream extends CompressorInputStream {
+public class ZCompressorInputStream extends AbstractLZWInputStream {
private static final int MAGIC_1 = 0x1f;
private static final int MAGIC_2 = 0x9d;
private static final int BLOCK_MODE_MASK = 0x80;
private static final int MAX_CODE_SIZE_MASK = 0x1f;
- private final InputStream in;
private final boolean blockMode;
- private final int clearCode;
private final int maxCodeSize;
- private int codeSize = 9;
- private int bitsCached = 0;
- private int bitsCachedSize = 0;
private long totalCodesRead = 0;
- private int previousCode = -1;
- private int tableSize = 0;
- private final int[] prefixes;
- private final byte[] characters;
- private final byte[] outputStack;
- private int outputStackLocation;
public ZCompressorInputStream(InputStream inputStream) throws IOException {
- this.in = inputStream;
+ super(inputStream);
int firstByte = in.read();
int secondByte = in.read();
int thirdByte = in.read();
@@ -59,26 +46,12 @@ public class ZCompressorInputStream exte
blockMode = ((thirdByte & BLOCK_MODE_MASK) != 0);
maxCodeSize = thirdByte & MAX_CODE_SIZE_MASK;
if (blockMode) {
- clearCode = (1 << (codeSize - 1));
- } else {
- clearCode = -1; // unused
- }
- final int maxTableSize = 1 << maxCodeSize;
- prefixes = new int[maxTableSize];
- characters = new byte[maxTableSize];
- outputStack = new byte[maxTableSize];
- outputStackLocation = maxTableSize;
- for (int i = 0; i < (1 << 8); i++) {
- prefixes[i] = -1;
- characters[i] = (byte)i;
+ setClearCode(codeSize);
}
+ initializeTables(maxCodeSize);
clearEntries();
}
- public void close() throws IOException {
- in.close();
- }
-
private void clearEntries() {
tableSize = (1 << 8);
if (blockMode) {
@@ -86,20 +59,12 @@ public class ZCompressorInputStream exte
}
}
- private int readNextCode() throws IOException {
- while (bitsCachedSize < codeSize) {
- final int nextByte = in.read();
- if (nextByte < 0) {
- return nextByte;
- }
- bitsCached |= (nextByte << bitsCachedSize);
- bitsCachedSize += 8;
+ @Override
+ protected int readNextCode() throws IOException {
+ int code = super.readNextCode();
+ if (code >= 0) {
+ ++totalCodesRead;
}
- final int mask = (1 << codeSize) - 1;
- final int code = (bitsCached & mask);
- bitsCached >>>= codeSize;
- bitsCachedSize -= codeSize;
- ++totalCodesRead;
return code;
}
@@ -119,22 +84,19 @@ public class ZCompressorInputStream exte
bitsCachedSize = 0;
}
- private void addEntry(int previousCode, byte character) throws IOException {
+ @Override
+ protected int addEntry(int previousCode, byte character) throws IOException {
final int maxTableSize = 1 << codeSize;
- if (tableSize < maxTableSize) {
- prefixes[tableSize] = previousCode;
- characters[tableSize] = character;
- tableSize++;
- }
- if (tableSize == maxTableSize) {
- if (codeSize < maxCodeSize) {
- reAlignReading();
- codeSize++;
- }
+ int r = addEntry(previousCode, character, maxTableSize);
+ if (tableSize == maxTableSize && codeSize < maxCodeSize) {
+ reAlignReading();
+ codeSize++;
}
+ return r;
}
- private int decompressNextSymbol() throws IOException {
+ @Override
+ protected int decompressNextSymbol() throws IOException {
//
// table entry table entry
// _____________ _____
@@ -159,74 +121,13 @@ public class ZCompressorInputStream exte
} else {
boolean addedUnfinishedEntry = false;
if (code == tableSize) {
- // must be a repeat of the previous entry we haven't added yet
- if (previousCode == -1) {
- // ... which isn't possible for the very first code
- throw new IOException("The first code can't be a reference to its preceding code");
- }
- byte firstCharacter = 0;
- for (int last = previousCode; last >= 0; last = prefixes[last]) {
- firstCharacter = characters[last];
- }
- addEntry(previousCode, firstCharacter);
+ addRepeatOfPreviousCode();
addedUnfinishedEntry = true;
} else if (code > tableSize) {
throw new IOException(String.format("Invalid %d bit code 0x%x", codeSize, code));
}
- for (int entry = code; entry >= 0; entry = prefixes[entry]) {
- outputStack[--outputStackLocation] = characters[entry];
- }
- if (previousCode != -1 && !addedUnfinishedEntry) {
- addEntry(previousCode, outputStack[outputStackLocation]);
- }
- previousCode = code;
- return outputStackLocation;
- }
- }
-
- public int read() throws IOException {
- byte[] b = new byte[1];
- int ret;
- while ((ret = read(b)) == 0) {
+ return expandCodeToOutputStack(code, addedUnfinishedEntry);
}
- if (ret < 0) {
- return ret;
- }
- return 0xff & b[0];
}
- public int read(byte[] b, int off, int len) throws IOException {
- int bytesRead = 0;
- int remainingInStack = outputStack.length - outputStackLocation;
- if (remainingInStack > 0) {
- int maxLength = Math.min(remainingInStack, len);
- System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
- outputStackLocation += maxLength;
- off += maxLength;
- len -= maxLength;
- bytesRead += maxLength;
- }
- while (len > 0) {
- int result = decompressNextSymbol();
- if (result < 0) {
- if (bytesRead > 0) {
- count(bytesRead);
- return bytesRead;
- } else {
- return result;
- }
- }
- remainingInStack = outputStack.length - outputStackLocation;
- if (remainingInStack > 0) {
- int maxLength = Math.min(remainingInStack, len);
- System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
- outputStackLocation += maxLength;
- off += maxLength;
- len -= maxLength;
- bytesRead += maxLength;
- }
- }
- count(bytesRead);
- return bytesRead;
- }
}
Re: svn commit: r1551026 - in /commons/proper/compress/trunk/src/main/java/org/apache/commons/compress:
archivers/zip/UnshrinkingInputStream.java compressors/z/AbstractLZWInputStream.java
compressors/z/ZCompressorInputStream.java
Posted by Emmanuel Bourg <eb...@apache.org>.
Le 18/12/2013 09:21, Stefan Bodewig a écrit :
> The end-of-information part could probably be dealt with in the subclass
> specific implementation of decompressNextSymbol and increasing the code
> size may happen in addEntry, not sure. As for endianess, Emmanuel
> briefly mentioned a BitInputStream he had for the IMPLODE algortihm on
> IRC, maybe this could be used inside readNextCode and hide the concrete
> endianess?
I wrote two support classes to implement the explode algorithm:
- BitStream: takes an InputStream and returns the bits one by one with a
readBit() method, or n bits with readBits(n) (up to 8 bits). It doesn't
implement InputStream. The bit stream is formed by reading the bytes one
by one from the InputStream, and appending its bits to the left of a
long used as a buffer. There is no notion of endianness.
- BinaryTree: decodes the symbols on calling read(BitStream)
I suspect this could be reused for a huffman encoded input stream but I
haven't checked the details yet.
Emmanuel
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1551026 - in /commons/proper/compress/trunk/src/main/java/org/apache/commons/compress: archivers/zip/UnshrinkingInputStream.java compressors/z/AbstractLZWInputStream.java compressors/z/ZCompressorInputStream.java
Posted by Stefan Bodewig <bo...@apache.org>.
On 2013-12-17, Damjan Jovanovic wrote:
> I am wondering how far this can be taken. TIFF's LZW uses an
> end-of-information code after the clear code, allows both
> little-endian and big-endian packing of bytes, and increases the code
> size one step too early. Is it even possible to generalize LZW (any
> further), and would it be a good idea, given how uniquely it's
> implemented in each file format?
TBH my changes were driven by the code and not by actually understanding
LZW :-)
The end-of-information part could probably be dealt with in the subclass
specific implementation of decompressNextSymbol and increasing the code
size may happen in addEntry, not sure. As for endianess, Emmanuel
briefly mentioned a BitInputStream he had for the IMPLODE algortihm on
IRC, maybe this could be used inside readNextCode and hide the concrete
endianess?
Like you I'm not actually sure it would be worth the effort if this base
class became the only reason for making imaging depend on compress.
Rather not.
Stefan
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org
Re: svn commit: r1551026 - in /commons/proper/compress/trunk/src/main/java/org/apache/commons/compress:
archivers/zip/UnshrinkingInputStream.java compressors/z/AbstractLZWInputStream.java
compressors/z/ZCompressorInputStream.java
Posted by Damjan Jovanovic <da...@apache.org>.
Very nice.
I am wondering how far this can be taken. TIFF's LZW uses an
end-of-information code after the clear code, allows both
little-endian and big-endian packing of bytes, and increases the code
size one step too early. Is it even possible to generalize LZW (any
further), and would it be a good idea, given how uniquely it's
implemented in each file format?
Damjan
On Sun, Dec 15, 2013 at 5:23 PM, <bo...@apache.org> wrote:
> Author: bodewig
> Date: Sun Dec 15 15:23:35 2013
> New Revision: 1551026
>
> URL: http://svn.apache.org/r1551026
> Log:
> reduce code duplication in the two LZW input streams
>
> Added:
> commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java (with props)
> Modified:
> commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java
> commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java
>
> Modified: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java
> URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java?rev=1551026&r1=1551025&r2=1551026&view=diff
> ==============================================================================
> --- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java (original)
> +++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/archivers/zip/UnshrinkingInputStream.java Sun Dec 15 15:23:35 2013
> @@ -21,84 +21,43 @@ package org.apache.commons.compress.arch
> import java.io.IOException;
> import java.io.InputStream;
>
> -import org.apache.commons.compress.compressors.CompressorInputStream;
> +import org.apache.commons.compress.compressors.z.AbstractLZWInputStream;
>
> /**
> * Input stream that decompresses ZIP method 1 (unshrinking). A variation of the LZW algorithm, with some twists.
> * @NotThreadSafe
> * @since 1.7
> */
> -class UnshrinkingInputStream extends CompressorInputStream {
> - private final InputStream in;
> - private final int clearCode;
> - private final int MAX_CODE_SIZE = 13;
> - private int codeSize = 9;
> - private int bitsCached = 0;
> - private int bitsCachedSize = 0;
> - private int previousCode = -1;
> - private int tableSize = 0;
> - private final int[] prefixes;
> - private final byte[] characters;
> +class UnshrinkingInputStream extends AbstractLZWInputStream {
> + private static final int MAX_CODE_SIZE = 13;
> + private static final int MAX_TABLE_SIZE = 1 << MAX_CODE_SIZE;
> private final boolean[] isUsed;
> - private final byte[] outputStack;
> - private int outputStackLocation;
>
> public UnshrinkingInputStream(InputStream inputStream) throws IOException {
> - this.in = inputStream;
> - clearCode = (1 << (codeSize - 1));
> - final int maxTableSize = 1 << MAX_CODE_SIZE;
> - prefixes = new int[maxTableSize];
> - characters = new byte[maxTableSize];
> - isUsed = new boolean[maxTableSize];
> - outputStack = new byte[maxTableSize];
> - outputStackLocation = maxTableSize;
> + super(inputStream);
> + setClearCode(codeSize);
> + initializeTables(MAX_CODE_SIZE);
> + isUsed = new boolean[prefixes.length];
> for (int i = 0; i < (1 << 8); i++) {
> - prefixes[i] = -1;
> - characters[i] = (byte)i;
> isUsed[i] = true;
> }
> tableSize = clearCode + 1;
> }
> -
> - public void close() throws IOException {
> - in.close();
> - }
> -
> - private int readNextCode() throws IOException {
> - while (bitsCachedSize < codeSize) {
> - final int nextByte = in.read();
> - if (nextByte < 0) {
> - return nextByte;
> - }
> - bitsCached |= (nextByte << bitsCachedSize);
> - bitsCachedSize += 8;
> - }
> - final int mask = (1 << codeSize) - 1;
> - final int code = (bitsCached & mask);
> - bitsCached >>>= codeSize;
> - bitsCachedSize -= codeSize;
> - return code;
> - }
> -
> - private int addEntry(int previousCode, byte character) throws IOException {
> - final int maxTableSize = 1 << MAX_CODE_SIZE;
> - while ((tableSize < maxTableSize) && isUsed[tableSize]) {
> +
> + @Override
> + protected int addEntry(int previousCode, byte character) throws IOException {
> + while ((tableSize < MAX_TABLE_SIZE) && isUsed[tableSize]) {
> tableSize++;
> }
> - if (tableSize < maxTableSize) {
> - final int index = tableSize;
> - prefixes[tableSize] = previousCode;
> - characters[tableSize] = character;
> - isUsed[tableSize] = true;
> - tableSize++;
> - return index;
> - } else {
> - return -1;
> + int idx = addEntry(previousCode, character, MAX_TABLE_SIZE);
> + if (idx >= 0) {
> + isUsed[idx] = true;
> }
> + return idx;
> }
>
> private void partialClear() throws IOException {
> - final boolean[] isParent = new boolean[1 << MAX_CODE_SIZE];
> + final boolean[] isParent = new boolean[MAX_TABLE_SIZE];
> for (int i = 0; i < isUsed.length; i++) {
> if (isUsed[i] && prefixes[i] != -1) {
> isParent[prefixes[i]] = true;
> @@ -112,7 +71,8 @@ class UnshrinkingInputStream extends Com
> }
> }
>
> - private int decompressNextSymbol() throws IOException {
> + @Override
> + protected int decompressNextSymbol() throws IOException {
> //
> // table entry table entry
> // _____________ _____
> @@ -147,76 +107,12 @@ class UnshrinkingInputStream extends Com
> return 0;
> } else {
> boolean addedUnfinishedEntry = false;
> - final int effectiveCode;
> - if (isUsed[code]) {
> - effectiveCode = code;
> - } else {
> - // must be a repeat of the previous entry we haven't added yet
> - if (previousCode == -1) {
> - // ... which isn't possible for the very first code
> - throw new IOException("The first code can't be a reference to its preceding code");
> - }
> - byte firstCharacter = 0;
> - for (int last = previousCode; last >= 0; last = prefixes[last]) {
> - firstCharacter = characters[last];
> - }
> - effectiveCode = addEntry(previousCode, firstCharacter);
> + int effectiveCode = code;
> + if (!isUsed[code]) {
> + effectiveCode = addRepeatOfPreviousCode();
> addedUnfinishedEntry = true;
> }
> - for (int entry = effectiveCode; entry >= 0; entry = prefixes[entry]) {
> - outputStack[--outputStackLocation] = characters[entry];
> - }
> - if (previousCode != -1 && !addedUnfinishedEntry) {
> - addEntry(previousCode, outputStack[outputStackLocation]);
> - }
> - previousCode = code;
> - return outputStackLocation;
> - }
> - }
> -
> - public int read() throws IOException {
> - byte[] b = new byte[1];
> - int ret;
> - while ((ret = read(b)) == 0) {
> - }
> - if (ret < 0) {
> - return ret;
> - }
> - return 0xff & b[0];
> - }
> -
> - public int read(byte[] b, int off, int len) throws IOException {
> - int bytesRead = 0;
> - int remainingInStack = outputStack.length - outputStackLocation;
> - if (remainingInStack > 0) {
> - int maxLength = Math.min(remainingInStack, len);
> - System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> - outputStackLocation += maxLength;
> - off += maxLength;
> - len -= maxLength;
> - bytesRead += maxLength;
> - }
> - while (len > 0) {
> - int result = decompressNextSymbol();
> - if (result < 0) {
> - if (bytesRead > 0) {
> - count(bytesRead);
> - return bytesRead;
> - } else {
> - return result;
> - }
> - }
> - remainingInStack = outputStack.length - outputStackLocation;
> - if (remainingInStack > 0) {
> - int maxLength = Math.min(remainingInStack, len);
> - System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> - outputStackLocation += maxLength;
> - off += maxLength;
> - len -= maxLength;
> - bytesRead += maxLength;
> - }
> + return expandCodeToOutputStack(effectiveCode, addedUnfinishedEntry);
> }
> - count(bytesRead);
> - return bytesRead;
> }
> }
>
> Added: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java
> URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java?rev=1551026&view=auto
> ==============================================================================
> --- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java (added)
> +++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java Sun Dec 15 15:23:35 2013
> @@ -0,0 +1,201 @@
> +/*
> + * Licensed to the Apache Software Foundation (ASF) under one
> + * or more contributor license agreements. See the NOTICE file
> + * distributed with this work for additional information
> + * regarding copyright ownership. The ASF licenses this file
> + * to you under the Apache License, Version 2.0 (the
> + * "License"); you may not use this file except in compliance
> + * with the License. You may obtain a copy of the License at
> + *
> + * http://www.apache.org/licenses/LICENSE-2.0
> + *
> + * Unless required by applicable law or agreed to in writing,
> + * software distributed under the License is distributed on an
> + * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
> + * KIND, either express or implied. See the License for the
> + * specific language governing permissions and limitations
> + * under the License.
> + */
> +package org.apache.commons.compress.compressors.z;
> +
> +import java.io.IOException;
> +import java.io.InputStream;
> +
> +import org.apache.commons.compress.compressors.CompressorInputStream;
> +
> +/**
> + * Base-class for traditional Unix ".Z" compression and the
> + * Unshrinking method of ZIP archive.
> + * @NotThreadSafe
> + * @since 1.7
> + */
> +public abstract class AbstractLZWInputStream extends CompressorInputStream {
> + private final byte[] oneByte = new byte[1];
> +
> + protected final InputStream in;
> + protected int clearCode = -1;
> + protected int codeSize = 9;
> + protected int bitsCached = 0;
> + protected int bitsCachedSize = 0;
> + protected int previousCode = -1;
> + protected int tableSize = 0;
> + protected int[] prefixes;
> + protected byte[] characters;
> + private byte[] outputStack;
> + private int outputStackLocation;
> +
> + public AbstractLZWInputStream(InputStream inputStream) throws IOException {
> + this.in = inputStream;
> + }
> +
> + @Override
> + public void close() throws IOException {
> + in.close();
> + }
> +
> + @Override
> + public int read() throws IOException {
> + int ret;
> + while ((ret = read(oneByte)) == 0) { // NOPMD
> + }
> + if (ret < 0) {
> + return ret;
> + }
> + return 0xff & oneByte[0];
> + }
> +
> + @Override
> + public int read(byte[] b, int off, int len) throws IOException {
> + int bytesRead = 0;
> + int remainingInStack = outputStack.length - outputStackLocation;
> + if (remainingInStack > 0) {
> + int maxLength = Math.min(remainingInStack, len);
> + System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> + outputStackLocation += maxLength;
> + off += maxLength;
> + len -= maxLength;
> + bytesRead += maxLength;
> + }
> + while (len > 0) {
> + int result = decompressNextSymbol();
> + if (result < 0) {
> + if (bytesRead > 0) {
> + count(bytesRead);
> + return bytesRead;
> + } else {
> + return result;
> + }
> + }
> + remainingInStack = outputStack.length - outputStackLocation;
> + if (remainingInStack > 0) {
> + int maxLength = Math.min(remainingInStack, len);
> + System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> + outputStackLocation += maxLength;
> + off += maxLength;
> + len -= maxLength;
> + bytesRead += maxLength;
> + }
> + }
> + count(bytesRead);
> + return bytesRead;
> + }
> +
> + /**
> + * Read the next code and expand it.
> + */
> + protected abstract int decompressNextSymbol() throws IOException;
> +
> + /**
> + * Add a new entry to the dictionary.
> + */
> + protected abstract int addEntry(int previousCode, byte character)
> + throws IOException;
> +
> + /**
> + * Sets the clear code based on the code size.
> + */
> + protected void setClearCode(int codeSize) {
> + clearCode = (1 << (codeSize - 1));
> + }
> +
> + /**
> + * Initializes the arrays based on the maximum code size.
> + */
> + protected void initializeTables(int maxCodeSize) {
> + final int maxTableSize = 1 << maxCodeSize;
> + prefixes = new int[maxTableSize];
> + characters = new byte[maxTableSize];
> + outputStack = new byte[maxTableSize];
> + outputStackLocation = maxTableSize;
> + final int max = 1 << 8;
> + for (int i = 0; i < max; i++) {
> + prefixes[i] = -1;
> + characters[i] = (byte) i;
> + }
> + }
> +
> + /**
> + * Reads the next code from the stream.
> + */
> + protected int readNextCode() throws IOException {
> + while (bitsCachedSize < codeSize) {
> + final int nextByte = in.read();
> + if (nextByte < 0) {
> + return nextByte;
> + }
> + bitsCached |= (nextByte << bitsCachedSize);
> + bitsCachedSize += 8;
> + }
> + final int mask = (1 << codeSize) - 1;
> + final int code = (bitsCached & mask);
> + bitsCached >>>= codeSize;
> + bitsCachedSize -= codeSize;
> + return code;
> + }
> +
> + /**
> + * Adds a new entry if the maximum table size hasn't been exceeded
> + * and returns the new index.
> + */
> + protected int addEntry(int previousCode, byte character, int maxTableSize) {
> + if (tableSize < maxTableSize) {
> + final int index = tableSize;
> + prefixes[tableSize] = previousCode;
> + characters[tableSize] = character;
> + tableSize++;
> + return index;
> + }
> + return -1;
> + }
> +
> + /**
> + * Add entry for repeat of previousCode we haven't added, yet.
> + */
> + protected int addRepeatOfPreviousCode() throws IOException {
> + if (previousCode == -1) {
> + // can't have a repeat for the very first code
> + throw new IOException("The first code can't be a reference to its preceding code");
> + }
> + byte firstCharacter = 0;
> + for (int last = previousCode; last >= 0; last = prefixes[last]) {
> + firstCharacter = characters[last];
> + }
> + return addEntry(previousCode, firstCharacter);
> + }
> +
> + /**
> + * Expands the entry with index code to the output stack and may
> + * create a new entry
> + */
> + protected int expandCodeToOutputStack(int code, boolean addedUnfinishedEntry)
> + throws IOException {
> + for (int entry = code; entry >= 0; entry = prefixes[entry]) {
> + outputStack[--outputStackLocation] = characters[entry];
> + }
> + if (previousCode != -1 && !addedUnfinishedEntry) {
> + addEntry(previousCode, outputStack[outputStackLocation]);
> + }
> + previousCode = code;
> + return outputStackLocation;
> + }
> +}
>
> Propchange: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/AbstractLZWInputStream.java
> ------------------------------------------------------------------------------
> svn:eol-style = native
>
> Modified: commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java
> URL: http://svn.apache.org/viewvc/commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java?rev=1551026&r1=1551025&r2=1551026&view=diff
> ==============================================================================
> --- commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java (original)
> +++ commons/proper/compress/trunk/src/main/java/org/apache/commons/compress/compressors/z/ZCompressorInputStream.java Sun Dec 15 15:23:35 2013
> @@ -21,35 +21,22 @@ package org.apache.commons.compress.comp
> import java.io.IOException;
> import java.io.InputStream;
>
> -import org.apache.commons.compress.compressors.CompressorInputStream;
> -
> /**
> * Input stream that decompresses .Z files.
> * @NotThreadSafe
> * @since 1.7
> */
> -public class ZCompressorInputStream extends CompressorInputStream {
> +public class ZCompressorInputStream extends AbstractLZWInputStream {
> private static final int MAGIC_1 = 0x1f;
> private static final int MAGIC_2 = 0x9d;
> private static final int BLOCK_MODE_MASK = 0x80;
> private static final int MAX_CODE_SIZE_MASK = 0x1f;
> - private final InputStream in;
> private final boolean blockMode;
> - private final int clearCode;
> private final int maxCodeSize;
> - private int codeSize = 9;
> - private int bitsCached = 0;
> - private int bitsCachedSize = 0;
> private long totalCodesRead = 0;
> - private int previousCode = -1;
> - private int tableSize = 0;
> - private final int[] prefixes;
> - private final byte[] characters;
> - private final byte[] outputStack;
> - private int outputStackLocation;
>
> public ZCompressorInputStream(InputStream inputStream) throws IOException {
> - this.in = inputStream;
> + super(inputStream);
> int firstByte = in.read();
> int secondByte = in.read();
> int thirdByte = in.read();
> @@ -59,26 +46,12 @@ public class ZCompressorInputStream exte
> blockMode = ((thirdByte & BLOCK_MODE_MASK) != 0);
> maxCodeSize = thirdByte & MAX_CODE_SIZE_MASK;
> if (blockMode) {
> - clearCode = (1 << (codeSize - 1));
> - } else {
> - clearCode = -1; // unused
> - }
> - final int maxTableSize = 1 << maxCodeSize;
> - prefixes = new int[maxTableSize];
> - characters = new byte[maxTableSize];
> - outputStack = new byte[maxTableSize];
> - outputStackLocation = maxTableSize;
> - for (int i = 0; i < (1 << 8); i++) {
> - prefixes[i] = -1;
> - characters[i] = (byte)i;
> + setClearCode(codeSize);
> }
> + initializeTables(maxCodeSize);
> clearEntries();
> }
>
> - public void close() throws IOException {
> - in.close();
> - }
> -
> private void clearEntries() {
> tableSize = (1 << 8);
> if (blockMode) {
> @@ -86,20 +59,12 @@ public class ZCompressorInputStream exte
> }
> }
>
> - private int readNextCode() throws IOException {
> - while (bitsCachedSize < codeSize) {
> - final int nextByte = in.read();
> - if (nextByte < 0) {
> - return nextByte;
> - }
> - bitsCached |= (nextByte << bitsCachedSize);
> - bitsCachedSize += 8;
> + @Override
> + protected int readNextCode() throws IOException {
> + int code = super.readNextCode();
> + if (code >= 0) {
> + ++totalCodesRead;
> }
> - final int mask = (1 << codeSize) - 1;
> - final int code = (bitsCached & mask);
> - bitsCached >>>= codeSize;
> - bitsCachedSize -= codeSize;
> - ++totalCodesRead;
> return code;
> }
>
> @@ -119,22 +84,19 @@ public class ZCompressorInputStream exte
> bitsCachedSize = 0;
> }
>
> - private void addEntry(int previousCode, byte character) throws IOException {
> + @Override
> + protected int addEntry(int previousCode, byte character) throws IOException {
> final int maxTableSize = 1 << codeSize;
> - if (tableSize < maxTableSize) {
> - prefixes[tableSize] = previousCode;
> - characters[tableSize] = character;
> - tableSize++;
> - }
> - if (tableSize == maxTableSize) {
> - if (codeSize < maxCodeSize) {
> - reAlignReading();
> - codeSize++;
> - }
> + int r = addEntry(previousCode, character, maxTableSize);
> + if (tableSize == maxTableSize && codeSize < maxCodeSize) {
> + reAlignReading();
> + codeSize++;
> }
> + return r;
> }
>
> - private int decompressNextSymbol() throws IOException {
> + @Override
> + protected int decompressNextSymbol() throws IOException {
> //
> // table entry table entry
> // _____________ _____
> @@ -159,74 +121,13 @@ public class ZCompressorInputStream exte
> } else {
> boolean addedUnfinishedEntry = false;
> if (code == tableSize) {
> - // must be a repeat of the previous entry we haven't added yet
> - if (previousCode == -1) {
> - // ... which isn't possible for the very first code
> - throw new IOException("The first code can't be a reference to its preceding code");
> - }
> - byte firstCharacter = 0;
> - for (int last = previousCode; last >= 0; last = prefixes[last]) {
> - firstCharacter = characters[last];
> - }
> - addEntry(previousCode, firstCharacter);
> + addRepeatOfPreviousCode();
> addedUnfinishedEntry = true;
> } else if (code > tableSize) {
> throw new IOException(String.format("Invalid %d bit code 0x%x", codeSize, code));
> }
> - for (int entry = code; entry >= 0; entry = prefixes[entry]) {
> - outputStack[--outputStackLocation] = characters[entry];
> - }
> - if (previousCode != -1 && !addedUnfinishedEntry) {
> - addEntry(previousCode, outputStack[outputStackLocation]);
> - }
> - previousCode = code;
> - return outputStackLocation;
> - }
> - }
> -
> - public int read() throws IOException {
> - byte[] b = new byte[1];
> - int ret;
> - while ((ret = read(b)) == 0) {
> + return expandCodeToOutputStack(code, addedUnfinishedEntry);
> }
> - if (ret < 0) {
> - return ret;
> - }
> - return 0xff & b[0];
> }
>
> - public int read(byte[] b, int off, int len) throws IOException {
> - int bytesRead = 0;
> - int remainingInStack = outputStack.length - outputStackLocation;
> - if (remainingInStack > 0) {
> - int maxLength = Math.min(remainingInStack, len);
> - System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> - outputStackLocation += maxLength;
> - off += maxLength;
> - len -= maxLength;
> - bytesRead += maxLength;
> - }
> - while (len > 0) {
> - int result = decompressNextSymbol();
> - if (result < 0) {
> - if (bytesRead > 0) {
> - count(bytesRead);
> - return bytesRead;
> - } else {
> - return result;
> - }
> - }
> - remainingInStack = outputStack.length - outputStackLocation;
> - if (remainingInStack > 0) {
> - int maxLength = Math.min(remainingInStack, len);
> - System.arraycopy(outputStack, outputStackLocation, b, off, maxLength);
> - outputStackLocation += maxLength;
> - off += maxLength;
> - len -= maxLength;
> - bytesRead += maxLength;
> - }
> - }
> - count(bytesRead);
> - return bytesRead;
> - }
> }
>
>
---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@commons.apache.org
For additional commands, e-mail: dev-help@commons.apache.org