commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From bode...@apache.org
Subject commons-compress git commit: add support for prefill in LZ77 Compressor
Date Tue, 07 Feb 2017 18:49:20 GMT
Repository: commons-compress
Updated Branches:
  refs/heads/master 75bb48015 -> a0e27b5a4


add support for prefill in LZ77 Compressor


Project: http://git-wip-us.apache.org/repos/asf/commons-compress/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-compress/commit/a0e27b5a
Tree: http://git-wip-us.apache.org/repos/asf/commons-compress/tree/a0e27b5a
Diff: http://git-wip-us.apache.org/repos/asf/commons-compress/diff/a0e27b5a

Branch: refs/heads/master
Commit: a0e27b5a4c3fd1e650865656346cf7901124e832
Parents: 75bb480
Author: Stefan Bodewig <bodewig@apache.org>
Authored: Tue Feb 7 19:48:32 2017 +0100
Committer: Stefan Bodewig <bodewig@apache.org>
Committed: Tue Feb 7 19:48:32 2017 +0100

----------------------------------------------------------------------
 .../compressors/lz77support/LZ77Compressor.java |  32 +++++-
 .../lz77support/LZ77CompressorTest.java         | 110 +++++++++++++++++++
 2 files changed, 141 insertions(+), 1 deletion(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/commons-compress/blob/a0e27b5a/src/main/java/org/apache/commons/compress/compressors/lz77support/LZ77Compressor.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/compress/compressors/lz77support/LZ77Compressor.java
b/src/main/java/org/apache/commons/compress/compressors/lz77support/LZ77Compressor.java
index 6755dd1..48884cd 100644
--- a/src/main/java/org/apache/commons/compress/compressors/lz77support/LZ77Compressor.java
+++ b/src/main/java/org/apache/commons/compress/compressors/lz77support/LZ77Compressor.java
@@ -297,6 +297,36 @@ public class LZ77Compressor {
         callback.accept(THE_EOD);
     }
 
+    /**
+     * Adds some initial data to fill the window with.
+     *
+     * <p>This is used if the stream has been cut into blocks and
+     * back-references of one block may refer to data of the previous
+     * block(s). One such example is the LZ4 frame format using block
+     * dependency.</p>
+     *
+     * @param data the data to fill the window with.
+     * @throws IllegalStateException if the compressor has already started to accept data
+     */
+    public void prefill(byte[] data) {
+        if (currentPosition != 0 || lookahead != 0) {
+            throw new IllegalStateException("the compressor has already started to accept
data, can't prefill anymore");
+        }
+        final int len = Math.min(params.getWindowSize(), data.length);
+        System.arraycopy(data, data.length - len, window, 0, len);
+        if (len >= NUMBER_OF_BYTES_IN_HASH) {
+            initialize();
+            final int stop = len - NUMBER_OF_BYTES_IN_HASH + 1;
+            for (int i = 0; i < stop; i++) {
+                insertString(i);
+            }
+            missedInserts = NUMBER_OF_BYTES_IN_HASH - 1;
+        } else {
+            missedInserts = len;
+        }
+        blockStart = currentPosition = len;
+    }
+
     // we use a 15 bit hashcode as calculated in updateHash
     private static final int HASH_SIZE = 1 << 15;
     private static final int HASH_MASK = HASH_SIZE - 1;
@@ -394,7 +424,7 @@ public class LZ77Compressor {
 
     /**
      * Inserts the current three byte sequence into the dictionary and
-     * returns the previous previous head of the hash-chain.
+     * returns the previous head of the hash-chain.
      *
      * <p>Updates <code>insertHash</code> and <code>prev</code>
as a
      * side effect.</p>

http://git-wip-us.apache.org/repos/asf/commons-compress/blob/a0e27b5a/src/test/java/org/apache/commons/compress/compressors/lz77support/LZ77CompressorTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/compress/compressors/lz77support/LZ77CompressorTest.java
b/src/test/java/org/apache/commons/compress/compressors/lz77support/LZ77CompressorTest.java
index 6f7523b..ff925aa 100644
--- a/src/test/java/org/apache/commons/compress/compressors/lz77support/LZ77CompressorTest.java
+++ b/src/test/java/org/apache/commons/compress/compressors/lz77support/LZ77CompressorTest.java
@@ -196,6 +196,116 @@ public class LZ77CompressorTest {
         assertLiteralBlock(".", blocks.get(19));
     }
 
+    @Test
+    public void blaExampleWithPrefill() throws IOException {
+        final List<LZ77Compressor.Block> blocks = new ArrayList<>();
+        LZ77Compressor c = new LZ77Compressor(new Parameters(128), new LZ77Compressor.Callback()
{
+                @Override
+                public void accept(LZ77Compressor.Block block) {
+                    //System.err.println(block);
+                    if (block instanceof LZ77Compressor.LiteralBlock) {
+                        // replace with a real copy of data so tests
+                        // can see the results as they've been when
+                        // the callback has been called
+                        LZ77Compressor.LiteralBlock b = (LZ77Compressor.LiteralBlock) block;
+                        int len = b.getLength();
+                        block = new LZ77Compressor.LiteralBlock(
+                            Arrays.copyOfRange(b.getData(), b.getOffset(), b.getOffset()
+ len),
+                            0, len);
+                    }
+                    blocks.add(block);
+                }
+            });
+        c.prefill(Arrays.copyOfRange(BLA, 0, 6));
+        c.compress(Arrays.copyOfRange(BLA, 6, BLA.length));
+        c.finish();
+        assertSize(3, blocks);
+        assertBackReference(5, 18, blocks.get(0));
+        assertLiteralBlock("!", blocks.get(1));
+    }
+
+    @Test
+    public void blaExampleWithShortPrefill() throws IOException {
+        final List<LZ77Compressor.Block> blocks = new ArrayList<>();
+        LZ77Compressor c = new LZ77Compressor(new Parameters(128), new LZ77Compressor.Callback()
{
+                @Override
+                public void accept(LZ77Compressor.Block block) {
+                    //System.err.println(block);
+                    if (block instanceof LZ77Compressor.LiteralBlock) {
+                        // replace with a real copy of data so tests
+                        // can see the results as they've been when
+                        // the callback has been called
+                        LZ77Compressor.LiteralBlock b = (LZ77Compressor.LiteralBlock) block;
+                        int len = b.getLength();
+                        block = new LZ77Compressor.LiteralBlock(
+                            Arrays.copyOfRange(b.getData(), b.getOffset(), b.getOffset()
+ len),
+                            0, len);
+                    }
+                    blocks.add(block);
+                }
+            });
+        c.prefill(Arrays.copyOfRange(BLA, 0, 2));
+        c.compress(Arrays.copyOfRange(BLA, 2, BLA.length));
+        c.finish();
+        assertSize(4, blocks);
+        assertLiteralBlock("ah b", blocks.get(0));
+        assertBackReference(5, 18, blocks.get(1));
+        assertLiteralBlock("!", blocks.get(2));
+    }
+
+    @Test
+    public void blaExampleWithPrefillBiggerThanWindowSize() throws IOException {
+        final List<LZ77Compressor.Block> blocks = new ArrayList<>();
+        LZ77Compressor c = new LZ77Compressor(new Parameters(4), new LZ77Compressor.Callback()
{
+                @Override
+                public void accept(LZ77Compressor.Block block) {
+                    //System.err.println(block);
+                    if (block instanceof LZ77Compressor.LiteralBlock) {
+                        // replace with a real copy of data so tests
+                        // can see the results as they've been when
+                        // the callback has been called
+                        LZ77Compressor.LiteralBlock b = (LZ77Compressor.LiteralBlock) block;
+                        int len = b.getLength();
+                        block = new LZ77Compressor.LiteralBlock(
+                            Arrays.copyOfRange(b.getData(), b.getOffset(), b.getOffset()
+ len),
+                            0, len);
+                    }
+                    blocks.add(block);
+                }
+            });
+        c.prefill(Arrays.copyOfRange(BLA, 0, 6));
+        c.compress(Arrays.copyOfRange(BLA, 6, BLA.length));
+        c.finish();
+        assertSize(6, blocks);
+        assertLiteralBlock("lah ", blocks.get(0));
+        assertLiteralBlock("blah", blocks.get(1));
+        assertLiteralBlock(" bla", blocks.get(2));
+        assertLiteralBlock("h bl", blocks.get(3));
+        assertLiteralBlock("ah!", blocks.get(4));
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void cantPrefillTwice() {
+        LZ77Compressor c = new LZ77Compressor(new Parameters(128), new LZ77Compressor.Callback()
{
+                @Override
+                public void accept(LZ77Compressor.Block block) {
+                }
+            });
+        c.prefill(Arrays.copyOfRange(BLA, 0, 2));
+        c.prefill(Arrays.copyOfRange(BLA, 2, 4));
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void cantPrefillAfterCompress() throws IOException {
+        LZ77Compressor c = new LZ77Compressor(new Parameters(128), new LZ77Compressor.Callback()
{
+                @Override
+                public void accept(LZ77Compressor.Block block) {
+                }
+            });
+        c.compress(Arrays.copyOfRange(BLA, 0, 2));
+        c.prefill(Arrays.copyOfRange(BLA, 2, 4));
+    }
+
     private static final void assertSize(int expectedSize, List<LZ77Compressor.Block>
blocks) {
         assertEquals(expectedSize, blocks.size());
         assertEquals(LZ77Compressor.EOD.class, blocks.get(expectedSize - 1).getClass());


Mime
View raw message