You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@poi.apache.org by ni...@apache.org on 2007/10/13 17:46:10 UTC
svn commit: r584414 - in /poi/trunk/src/scratchpad: src/org/apache/poi/hdgf/
src/org/apache/poi/hdgf/streams/ testcases/org/apache/poi/hdgf/
Author: nick
Date: Sat Oct 13 08:46:09 2007
New Revision: 584414
URL: http://svn.apache.org/viewvc?rev=584414&view=rev
Log:
Replace the HDGW LZW engine with a fully documented, ASL licenced version. (Doesn't do compression yet, but is a much better start for that)
Added:
poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java (with props)
poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java (with props)
Removed:
poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/LZW4HDGF.java
poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestLZW4HDGF.java
Modified:
poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/streams/CompressedStreamStore.java
Added: poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java
URL: http://svn.apache.org/viewvc/poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java?rev=584414&view=auto
==============================================================================
--- poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java (added)
+++ poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java Sat Oct 13 08:46:09 2007
@@ -0,0 +1,161 @@
+/* ====================================================================
+ 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.poi.hdgf;
+
+import java.io.ByteArrayOutputStream;
+import java.io.IOException;
+import java.io.InputStream;
+import java.io.OutputStream;
+
+/**
+ * A decoder for the crazy LZW implementation used
+ * in Visio.
+ * According to VSDump, "it's a slightly perverted version of LZW
+ * compression, with inverted meaning of flag byte and 0xFEE as an
+ * 'initial shift'". It uses 12 bit codes
+ * (http://www.gnome.ru/projects/vsdump_en.html)
+ *
+ * Two good resources on LZW are:
+ * http://en.wikipedia.org/wiki/LZW
+ * http://marknelson.us/1989/10/01/lzw-data-compression/
+ */
+public class HDGFLZW {
+
+/**
+ * Given an integer, turn it into a java byte, handling
+ * the wrapping.
+ * This is a convenience method
+ */
+public byte fromInt(int b) {
+ if(b < 128) return (byte)b;
+ return (byte)(b - 256);
+}
+/**
+ * Given a java byte, turn it into an integer between 0
+ * and 255 (i.e. handle the unwrapping).
+ * This is a convenience method
+ */
+public int fromByte(byte b) {
+ if(b >= 0) return (int)b;
+ return (int)(b + 256);
+}
+
+/**
+ * Decompresses the given input stream, returning the array of bytes
+ * of the decompressed input.
+ */
+public byte[] decode(InputStream src) throws IOException {
+ ByteArrayOutputStream res = new ByteArrayOutputStream();
+ decode(src,res);
+ return res.toByteArray();
+}
+/**
+ * Perform a streaming decompression of the input.
+ * Works by:
+ * 1) Reading a flag byte, the 8 bits of which tell you if the
+ * following 8 codes are compressed our un-compressed
+ * 2) Consider the 8 bits in turn
+ * 3) If the bit is set, the next code is un-compressed, so
+ * add it to the dictionary and output it
+ * 4) If the bit isn't set, then read in the length and start
+ * position in the dictionary, and output the bytes there
+ * 5) Loop until we've done all 8 bits, then read in the next
+ * flag byte
+ */
+public void decode(InputStream src, OutputStream res) throws IOException {
+ // We use 12 bit codes:
+ // * 0-255 are real bytes
+ // * 256-4095 are the substring codes
+ // Java handily initialises our buffer / dictionary
+ // to all zeros
+ byte[] buffer = new byte[4096];
+
+ // How far through the output we've got
+ // (This is normally used &4095, so it nicely wraps)
+ int pos = 0;
+ // The flag byte is treated as its 8 individual
+ // bits, which tell us if the following 8 codes
+ // are compressed or un-compressed
+ int flag;
+ // The mask, between 1 and 255, which is used when
+ // processing each bit of the flag byte in turn
+ int mask;
+
+ // This is a byte as looked up in the dictionary
+ // It needs to be signed, as it'll get passed on to
+ // the output stream
+ byte dataB;
+ // This is an unsigned byte read from the stream
+ // It needs to be unsigned, so that bit stuff works
+ int dataI;
+ // The compressed code sequence is held over 2 bytes
+ int dataIPt1, dataIPt2;
+ // How long a code sequence is, and where in the
+ // dictionary to start at
+ int len, pntr;
+
+ while( (flag = src.read()) != -1 ) {
+ // Compare each bit in our flag byte in turn:
+ for(mask = 1; mask < 256 ; mask <<= 1) {
+ // Is this a new code (un-compressed), or
+ // the use of existing codes (compressed)?
+ if( (flag & mask) > 0 ) {
+ // Retrieve the un-compressed code
+ if( (dataI = src.read()) != -1) {
+ // Save the byte into the dictionary
+ buffer[(pos&4095)] = fromInt(dataI);
+ pos++;
+ // And output the byte
+ res.write( new byte[] {fromInt(dataI)} );
+ }
+ } else {
+ // We have a compressed sequence
+ // Grab the next 16 bits of data
+ dataIPt1 = src.read();
+ dataIPt2 = src.read();
+ if(dataIPt1 == -1 || dataIPt2 == -1) break;
+
+ // Build up how long the code sequence is, and
+ // what position of the code to start at
+ // (The position is the first 12 bits, the
+ // length is the last 4 bits)
+ len = (dataIPt2 & 15) + 3;
+ pntr = (dataIPt2 & 240)*16 + dataIPt1;
+
+ // If the pointer happens to be passed the end
+ // of our buffer, then wrap around
+ if(pntr > 4078) {
+ pntr = pntr - 4078;
+ } else {
+ pntr = pntr + 18;
+ }
+
+ // Loop over the codes, outputting what they correspond to
+ for(int i=0; i<len; i++) {
+ buffer [(pos + i) & 4095] = buffer [(pntr + i) & 4095];
+ dataB = buffer[(pntr + i) & 4095];
+ res.write(new byte[] {dataB});
+ }
+
+ // Record how far along the stream we have moved
+ pos = pos + len;
+ }
+ }
+ }
+}
+
+}
\ No newline at end of file
Propchange: poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/HDGFLZW.java
------------------------------------------------------------------------------
svn:eol-style = native
Modified: poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/streams/CompressedStreamStore.java
URL: http://svn.apache.org/viewvc/poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/streams/CompressedStreamStore.java?rev=584414&r1=584413&r2=584414&view=diff
==============================================================================
--- poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/streams/CompressedStreamStore.java (original)
+++ poi/trunk/src/scratchpad/src/org/apache/poi/hdgf/streams/CompressedStreamStore.java Sat Oct 13 08:46:09 2007
@@ -19,7 +19,7 @@
import java.io.ByteArrayInputStream;
import java.io.IOException;
-import org.apache.poi.hdgf.LZW4HDGF;
+import org.apache.poi.hdgf.HDGFLZW;
/**
* A StreamStore where the data on-disk is compressed,
@@ -76,7 +76,7 @@
ByteArrayInputStream bais = new ByteArrayInputStream(data, offset, length);
// Decompress
- LZW4HDGF lzw = new LZW4HDGF();
+ HDGFLZW lzw = new HDGFLZW();
byte[] decompressed = lzw.decode(bais);
// Split into header and contents
Added: poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java
URL: http://svn.apache.org/viewvc/poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java?rev=584414&view=auto
==============================================================================
--- poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java (added)
+++ poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java Sat Oct 13 08:46:09 2007
@@ -0,0 +1,101 @@
+/* ====================================================================
+ 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.poi.hdgf;
+
+import java.io.ByteArrayInputStream;
+
+import junit.framework.TestCase;
+
+public class TestHDGFLZW extends TestCase {
+ public static final byte[] testTrailerComp = new byte[] {
+ 123, -60, 2, -21, -16, 1, 0, 0, -72, -13, -16, 78, -32, -5, 1,
+ 0, 3, -21, -16, 10, 5, 4, -21, -16, 21, 9, -21, -16, 103, -21,
+ -16, 34, -36, -1, 52, 15, 70, 15, 120, 88, 15, -7, -2, -28, -9,
+ -123, 21, 0, 44, -122, 1, -4, 104, 15, -24, -13, 40, -98, 32,
+ 78, 102, -67, -1, -2, -30, 64, 40, -67, -113, -73, 116, -98,
+ -85, 2, 66, 123, 9, 109, -85, 2, -89, 14, -56, -69, -83, -79,
+ -34, -3, 120, 110, 75, -9, -10, 20, -6, -25, -12, 22, -21, -16,
+ -12, -81, 67, 1, -128, -70, -21, -16, 84, -21, -16, 70, 0, 23,
+ -21, -16, 76, 47, -40, 79, 1, -44, -21, -16, 32, 3, 18, 12, 17,
+ -43, -68, 17, 16, -8, 21, 22, -1, -21, -16, -84, -1, -35, 79,
+ -9, -10, 96, 0, 46, -21, -16, 44, -39, -41, 79, 1, 119, -13,
+ -16, -106, -13, -16, 84, 0, 125, 26, -21, -16, 68, -38, 79, 1,
+ 17, 10, 0, -97, 50, 10, 0, 0, -42, -108, 15, 118, 31, 0, -3, 29,
+ -21, -16, -100, -25, 79, 1, -18, 97, -36, 76, 16, -21, -16, 86,
+ 0, 36, -5, 1, -5, 79, 63, 1, -124, 98, 0, 0, 28, 3, 20, -34, -3,
+ 125, 33, -21, -16, 100, -4, 79, 1, -92, -91, 16, -22, 24, 19, 41,
+ -21, -16, -44, -59, 16, 108, 100, 0, -21, 0, 71, -105, 18, 39, 85,
+ 17, -3, 79, 1, 95, -108, 113, 0, 0, 104, 3, 18, 49, 49, 17, -1, 64,
+ 85, 1, 0, 114, 0, 0, -93, -36, -21, -16, 100, 31, 0, 0, -40, -21,
+ -16, -92, 66, 127, 85, 1, 98, 119, 0, 0, -48, 79, 18, -3, 50, -17,
+ 1, 67, 85, 1, 81, -127, 0, -41, 0, 14, 6, 4, 17, 63, -63, 17, 68,
+ 85, -65, 1, 30, -120, 0, 0, 42, 79, 18, 68, 126, -21, -16, -76, 69,
+ 85, 1, 102, -119, 72, 37, 0, 97, 33 };
+ public static final byte[] testTrailerDecomp = new byte[] {
+ -60, 2, 0, 0, 0, 1, 0, 0, -72, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 1, 0, 3, 0, 0, 0, 3, 0, 0, 0, 3, 0, 0, 0, 4, 0, 0,
+ 0, 9, 0, 0, 0, 103, 0, 0, 0, 34, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ -123, 21, 0, 44, -123, 21, 0, 44, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 40, -98, 32, 78, 102, -67,
+ -2, -30, 64, 40, -67, -113, -73, 116, -67, -2, -30, 64, 40, 66,
+ 123, 9, 109, -67, -2, -30, 64, 40, -98, 32, 78, 102, -67, -2, -30,
+ 64, 40, -67, -113, -73, 116, -67, -2, -30, 64, -56, -83, -79, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 120, 110, 75, 1, 0, 0, 0,
+ 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 22, 0, 0, 0, -12, -81, 67,
+ 1, -128, 0, 0, 0, 84, 0, 0, 0, 70, 0, 23, 0, 0, 0, 76, -40, 79, 1,
+ -44, 0, 0, 0, 32, 0, 0, 0, 84, 0, 23, 0, 0, 0, -68, -40, 79, 1, -8,
+ 0, 0, 0, 32, 0, 0, 0, 84, 0, -1, 0, 0, 0, -84, -1, 79, 1, 0, 0, 0,
+ 0, 0, 0, 0, 0, 96, 0, 46, 0, 0, 0, 44, -39, 79, 1, 119, 1, 0, 0,
+ -106, 1, 0, 0, 84, 0, 26, 0, 0, 0, 68, -38, 79, 1, 17, 3, 0, 0,
+ 50, 10, 0, 0, -42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 29, 0, 0, 0, -100, -25, 79, 1, -18, 97, 0, 0, -106, 0, 0, 0, 86, 0,
+ 36, 0, 0, 0, -12, -5, 79, 1, -124, 98, 0, 0, 28, 0, 0, 0, 84, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 33, 0, 0, 0, 100,
+ -4, 79, 1, -92, 98, 0, 0, 32, 0, 0, 0, 84, 0, 41, 0, 0, 0, -44, -4,
+ 79, 1, 108, 100, 0, 0, 71, 0, 0, 0, 86, 0, 39, 0, 0, 0, 68, -3, 79,
+ 1, -108, 113, 0, 0, 104, 0, 0, 0, 84, 0, 49, 0, 0, 0, -84, 64, 85,
+ 1, 0, 114, 0, 0, -93, 0, 0, 0, -42, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, -40, 0, 0, 0, -92, 66, 85, 1, 98, 119,
+ 0, 0, -48, 1, 0, 0, 84, 0, 50, 0, 0, 0, 20, 67, 85, 1, 81, -127,
+ 0, 0, 14, 6, 0, 0, 84, 0, 63, 0, 0, 0, 100, 68, 85, 1, 30, -120,
+ 0, 0, 42, 1, 0, 0, 84, 0, 68, 0, 0, 0, -76, 69, 85, 1, 102, -119,
+ 0, 0, 42, 1, 0, 0, 84, 0, 0, 0, 0, 0
+ };
+
+ public void testCounts() throws Exception {
+ assertEquals(339, testTrailerComp.length);
+ assertEquals(632, testTrailerDecomp.length);
+
+ // Decode it using our engine
+ HDGFLZW lzw = new HDGFLZW();
+ byte[] dec = lzw.decode(new ByteArrayInputStream(testTrailerComp));
+
+ // Check it's of the right size
+ assertEquals(632, dec.length);
+
+ // Now check it matches
+ for(int i=0; i<dec.length; i++) {
+ if(dec[i] != testTrailerDecomp[i])
+ System.err.println(i + "\t" + dec[i] + "\t" + testTrailerDecomp[i]);
+ }
+ }
+}
Propchange: poi/trunk/src/scratchpad/testcases/org/apache/poi/hdgf/TestHDGFLZW.java
------------------------------------------------------------------------------
svn:eol-style = native
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@poi.apache.org
For additional commands, e-mail: commits-help@poi.apache.org