Top Description Inners Fields Constructors Methods
org.apache.commons.compress.compressors.lz77support

public Class LZ77Compressor

extends Object
Class Inheritance
Imports
java.io.IOException, java.util.Arrays, .Objects
Helper class for compression algorithms that use the ideas of LZ77.

Most LZ77 derived algorithms split input data into blocks of uncompressed data (called literal blocks) and back-references (pairs of offsets and lengths) that state "add length bytes that are the same as those already written starting offset bytes before the current position. The details of how those blocks and back-references are encoded are quite different between the algorithms and some algorithms perform additional steps (Huffman encoding in the case of DEFLATE for example).

This class attempts to extract the core logic - finding back-references - so it can be re-used. It follows the algorithm explained in section 4 of RFC 1951 (DEFLATE) and currently doesn't implement the "lazy match" optimization. The three-byte hash function used in this class is the same as the one used by zlib and InfoZIP's ZIP implementation of DEFLATE. The whole class is strongly inspired by InfoZIP's implementation.

LZ77 is used vaguely here (as well as many other places that talk about it :-), LZSS would likely be closer to the truth but LZ77 has become the synonym for a whole family of algorithms.

The API consists of a compressor that is fed bytes and emits Blocks to a registered callback where the blocks represent either literal blocks, back-references or end of data markers. In order to ensure the callback receives all information, the #finish method must be used once all data has been fed into the compressor.

Several parameters influence the outcome of the "compression":

windowSize
the size of the sliding window, must be a power of two - this determines the maximum offset a back-reference can take. The compressor maintains a buffer of twice of windowSize - real world values are in the area of 32k.
minBackReferenceLength
Minimal length of a back-reference found. A true minimum of 3 is hard-coded inside of this implementation but bigger lengths can be configured.
maxBackReferenceLength
Maximal length of a back-reference found.
maxOffset
Maximal offset of a back-reference.
maxLiteralLength
Maximal length of a literal block.
Since
1.14
See Also
https://tools.ietf.org/html/rfc1951#section-4

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static class
LZ77Compressor.BackReference

Represents a back-reference.

public abstract static class
LZ77Compressor.Block

Base class representing blocks the compressor may emit.

public static interface
LZ77Compressor.Callback

Callback invoked while the compressor processes data.

public static class
LZ77Compressor.EOD

A simple "we are done" marker.

public static class
LZ77Compressor.LiteralBlock

Represents a literal block of data.

Field Summary

Modifier and TypeField and Description
private int
blockStart

private final LZ77Compressor.Callback
callback

private int
currentPosition

private static final int
H_SHIFT

private static final int
HASH_MASK

private static final int
HASH_SIZE

private final int[]
head

private boolean
initialized

private int
insertHash

private int
lookahead

private int
matchStart

private int
missedInserts

private static final int
NO_MATCH

pack-priv static final int
NUMBER_OF_BYTES_IN_HASH

private final Parameters
params

private final int[]
prev

private static final LZ77Compressor.Block
THE_EOD

private final byte[]
window

private final int
wMask

Constructor Summary

AccessConstructor and Description
public
LZ77Compressor(final Parameters
the parameters
params, final LZ77Compressor.Callback
the callback
callback)

Initializes a compressor with parameters and a callback.

Method Summary

Modifier and TypeMethod and Description
private void
catchUpMissedInserts()

private void
compress()

public void
compress(final byte[]
the data to compress - must not be null
data)

Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.

public void
compress(final byte[]
the data to compress - must not be null
data, int
the start offset of the data
off, int
the number of bytes to compress
len)

Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.

private void
doCompress(final byte[] data, final int off, final int len)

public void
finish()

Tells the compressor to process all remaining data and signal end of data to the callback.

private void
flushBackReference(final int matchLength)

private void
flushLiteralBlock()

private void
initialize()

private int
insertString(final int pos)

Inserts the current three byte sequence into the dictionary and returns the previous head of the hash-chain.

private void
insertStringsInMatch(final int matchLength)

private int
longestMatch(int matchHead)

Searches the hash chain for real matches and returns the length of the longest match (0 if none were found) that isn't too far away (WRT maxOffset).

private int
longestMatchForNextPosition(final int prevMatchLength)

private int
nextHash(final int oldHash, final byte nextByte)

Assumes we are calculating the hash for three consecutive bytes as a rolling hash, i.e. for bytes ABCD if H is the hash of ABC the new hash for BCD is nextHash(H, D).

public void
prefill(final byte[]
the data to fill the window with.
data)

Adds some initial data to fill the window with.

private void
slide()

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

blockStartback to summary
private int blockStart
callbackback to summary
private final LZ77Compressor.Callback callback
currentPositionback to summary
private int currentPosition
H_SHIFTback to summary
private static final int H_SHIFT
HASH_MASKback to summary
private static final int HASH_MASK
HASH_SIZEback to summary
private static final int HASH_SIZE
initializedback to summary
private boolean initialized
insertHashback to summary
private int insertHash
lookaheadback to summary
private int lookahead
matchStartback to summary
private int matchStart
missedInsertsback to summary
private int missedInserts
NO_MATCHback to summary
private static final int NO_MATCH
NUMBER_OF_BYTES_IN_HASHback to summary
pack-priv static final int NUMBER_OF_BYTES_IN_HASH
paramsback to summary
private final Parameters params
prevback to summary
private final int[] prev
THE_EODback to summary
private static final LZ77Compressor.Block THE_EOD
windowback to summary
private final byte[] window
wMaskback to summary
private final int wMask

Constructor Detail

LZ77Compressorback to summary
public LZ77Compressor(final Parameters params, final LZ77Compressor.Callback callback)

Initializes a compressor with parameters and a callback.

Parameters
params:Parameters

the parameters

callback:LZ77Compressor.Callback

the callback

Exceptions
NullPointerException:
if either parameter is null

Method Detail

catchUpMissedInsertsback to summary
private void catchUpMissedInserts()
compressback to summary
private void compress() throws IOException
compressback to summary
public void compress(final byte[] data) throws IOException

Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.

Parameters
data:byte[]

the data to compress - must not be null

Exceptions
IOException:
if the callback throws an exception
compressback to summary
public void compress(final byte[] data, int off, int len) throws IOException

Feeds bytes into the compressor which in turn may emit zero or more blocks to the callback during the execution of this method.

Parameters
data:byte[]

the data to compress - must not be null

off:int

the start offset of the data

len:int

the number of bytes to compress

Exceptions
IOException:
if the callback throws an exception
doCompressback to summary
private void doCompress(final byte[] data, final int off, final int len) throws IOException
finishback to summary
public void finish() throws IOException

Tells the compressor to process all remaining data and signal end of data to the callback.

The compressor will in turn emit at least one block (EOD) but potentially multiple blocks to the callback during the execution of this method.

Exceptions
IOException:
if the callback throws an exception
flushBackReferenceback to summary
private void flushBackReference(final int matchLength) throws IOException
flushLiteralBlockback to summary
private void flushLiteralBlock() throws IOException
initializeback to summary
private void initialize()
insertStringback to summary
private int insertString(final int pos)

Inserts the current three byte sequence into the dictionary and returns the previous head of the hash-chain.

Updates insertHash and prev as a side effect.

insertStringsInMatchback to summary
private void insertStringsInMatch(final int matchLength)
longestMatchback to summary
private int longestMatch(int matchHead)

Searches the hash chain for real matches and returns the length of the longest match (0 if none were found) that isn't too far away (WRT maxOffset).

Sets matchStart to the index of the start position of the longest match as a side effect.

longestMatchForNextPositionback to summary
private int longestMatchForNextPosition(final int prevMatchLength)
nextHashback to summary
private int nextHash(final int oldHash, final byte nextByte)

Assumes we are calculating the hash for three consecutive bytes as a rolling hash, i.e. for bytes ABCD if H is the hash of ABC the new hash for BCD is nextHash(H, D).

The hash is shifted by five bits on each update so all effects of A have been swapped after the third update.

prefillback to summary
public void prefill(final byte[] data)

Adds some initial data to fill the window with.

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.

Parameters
data:byte[]

the data to fill the window with.

Exceptions
IllegalStateException:
if the compressor has already started to accept data
slideback to summary
private void slide() throws IOException
org.apache.commons.compress.compressors.lz77support back to summary

public final Class LZ77Compressor.BackReference

extends Block
Class Inheritance
Represents a back-reference.

Field Summary

Modifier and TypeField and Description
private final int
length

private final int
offset

Constructor Summary

AccessConstructor and Description
public
BackReference(final int offset, final int length)

Method Summary

Modifier and TypeMethod and Description
public int

Returns:

the length
getLength()

Provides the length of the back-reference.

public int

Returns:

the offset
getOffset()

Provides the offset of the back-reference.

public LZ77Compressor.Block.BlockType
getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

Field Detail

lengthback to summary
private final int length
offsetback to summary
private final int offset

Constructor Detail

BackReferenceback to summary
public BackReference(final int offset, final int length)

Method Detail

getLengthback to summary
public int getLength()

Provides the length of the back-reference.

Returns:int

the length

getOffsetback to summary
public int getOffset()

Provides the offset of the back-reference.

Returns:int

the offset

getTypeback to summary
public LZ77Compressor.Block.BlockType getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override
org.apache.commons.compress.compressors.lz77support back to summary

public abstract Class LZ77Compressor.Block

extends Object
Class Inheritance
  • java.lang.Object
  • org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block
Known Direct Subclasses
org.apache.commons.compress.compressors.lz77support.LZ77Compressor.EOD, org.apache.commons.compress.compressors.lz77support.LZ77Compressor.LiteralBlock, org.apache.commons.compress.compressors.lz77support.LZ77Compressor.BackReference
Base class representing blocks the compressor may emit.

This class is not supposed to be subclassed by classes outside of Commons Compress so it is considered internal and changed that would break subclasses may get introduced with future releases.

Nested and Inner Type Summary

Modifier and TypeClass and Description
public static enum
LZ77Compressor.Block.BlockType

Enumeration of the block types the compressor may emit.

Constructor Summary

AccessConstructor and Description
public
Block()

Method Summary

Modifier and TypeMethod and Description
public abstract LZ77Compressor.Block.BlockType
getType()

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Constructor Detail

Blockback to summary
public Block()

Method Detail

getTypeback to summary
public abstract LZ77Compressor.Block.BlockType getType()
org.apache.commons.compress.compressors.lz77support back to summary

public final Enum LZ77Compressor.Block.BlockType

extends Enum<LZ77Compressor.Block.BlockType>
Class Inheritance
Enumeration of the block types the compressor may emit.

Field Summary

Modifier and TypeField and Description
public static final LZ77Compressor.Block.BlockType
BACK_REFERENCE

public static final LZ77Compressor.Block.BlockType
EOD

public static final LZ77Compressor.Block.BlockType
LITERAL

Constructor Summary

AccessConstructor and Description
private
BlockType()

Field Detail

BACK_REFERENCEback to summary
public static final LZ77Compressor.Block.BlockType BACK_REFERENCE
EODback to summary
public static final LZ77Compressor.Block.BlockType EOD
LITERALback to summary
public static final LZ77Compressor.Block.BlockType LITERAL

Constructor Detail

BlockTypeback to summary
private BlockType()

Method Detail

valueOfback to summary
public static LZ77Compressor.Block.BlockType valueOf(String name)
valuesback to summary
public static LZ77Compressor.Block.BlockType[] values()
org.apache.commons.compress.compressors.lz77support back to summary

public Interface LZ77Compressor.Callback

Callback invoked while the compressor processes data.

The callback is invoked on the same thread that receives the bytes to compress and may be invoked multiple times during the execution of compress or finish.

Method Summary

Modifier and TypeMethod and Description
public void
accept(LZ77Compressor.Block
the block to consume
b)

Consumes a block.

Method Detail

acceptback to summary
public void accept(LZ77Compressor.Block b) throws IOException

Consumes a block.

Parameters
b:LZ77Compressor.Block

the block to consume

Exceptions
IOException:
in case of an error
org.apache.commons.compress.compressors.lz77support back to summary

public final Class LZ77Compressor.EOD

extends Block
Class Inheritance
A simple "we are done" marker.

Constructor Summary

AccessConstructor and Description
public
EOD()

Method Summary

Modifier and TypeMethod and Description
public LZ77Compressor.Block.BlockType
getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

Constructor Detail

EODback to summary
public EOD()

Method Detail

getTypeback to summary
public LZ77Compressor.Block.BlockType getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

Annotations
@Override
org.apache.commons.compress.compressors.lz77support back to summary

public final Class LZ77Compressor.LiteralBlock

extends Block
Class Inheritance
Represents a literal block of data.

For performance reasons this encapsulates the real data, not a copy of it. Don't modify the data and process it inside of Callback#accept immediately as it will get overwritten sooner or later.

Field Summary

Modifier and TypeField and Description
private final byte[]
data

private final int
length

private final int
offset

Constructor Summary

AccessConstructor and Description
public
LiteralBlock(final byte[] data, final int offset, final int length)

Method Summary

Modifier and TypeMethod and Description
public byte[]

Returns:

the data
getData()

The literal data.

public int

Returns:

the length
getLength()

Length of literal block.

public int

Returns:

the offset
getOffset()

Offset into data where the literal block starts.

public LZ77Compressor.Block.BlockType
getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

public String
toString()

Overrides java.lang.Object.toString.

Returns a string representation of the object.

Field Detail

databack to summary
private final byte[] data
lengthback to summary
private final int length
offsetback to summary
private final int offset

Constructor Detail

LiteralBlockback to summary
public LiteralBlock(final byte[] data, final int offset, final int length)

Method Detail

getDataback to summary
public byte[] getData()

The literal data.

This returns a life view of the actual data in order to avoid copying, modify the array at your own risk.

Returns:byte[]

the data

getLengthback to summary
public int getLength()

Length of literal block.

Returns:int

the length

getOffsetback to summary
public int getOffset()

Offset into data where the literal block starts.

Returns:int

the offset

getTypeback to summary
public LZ77Compressor.Block.BlockType getType()

Implements abstract org.apache.commons.compress.compressors.lz77support.LZ77Compressor.Block.getType.

Annotations
@Override
toStringback to summary
public String toString()

Overrides java.lang.Object.toString.

Doc from java.lang.Object.toString.

Returns a string representation of the object.

Returns:String

a string representation of the object.

Annotations
@Override