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 2017/02/07 18:49:20 UTC
commons-compress git commit: add support for prefill in LZ77
Compressor
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 <bo...@apache.org>
Authored: Tue Feb 7 19:48:32 2017 +0100
Committer: Stefan Bodewig <bo...@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());