compress library

compress implements a lightweight, deflate-like compression algorithm designed to have a simple, zk-friendly decompression algorithm. We also provide a zk decompressor in gnark.

compress is is an Apache 2.0 licensed project.

How to use

The Compressor class in the lzss package does all the work.

• Load a Huffman table with NewHuffmanTable, then pass it and the dictionary to NewCompressor.
• Following golang conventions, the compressor implements the io.Writer interface, and data can be fed to it through the Write method.
• To retrieve the compressed data, use the Bytes method.
• For use-cases where raw data streams in and compressed blobs of only a limited size can be emitted, Len and Revert methods are provided to ensure maximal use of output space.
• For convenience, a Compress wrapper method is also provided, which compresses the entire input in one go and returns the compressed data.

Example

d := []byte("hello world, hello wordl")
tableData, _ := os.ReadFile("huffman_table")
table, _ := lzss.NewHuffmanTable(tableData)
compressor, _ := lzss.NewCompressor(nil, table)
c, _ := compressor.Compress(d)
dBack, _ := lzss.Decompress(c, nil, table)
if !bytes.Equal(d, dBack) {
    panic("decompression failed")
}

Generate a table from representative input files with:

go run ./cmd/hufftable -dict dictionary.bin -files 'corpus/*.bin' -o huffman_table

The table is a 512-byte file containing one canonical code length per symbol. The generator runs every matched file through the LZ parser, counts literal and back-reference-length symbols, and constructs a deterministic table. The same table must be supplied for compression and decompression.

For a complete example making use of the dictionary and revert features, see TestRevert.

Specification

A note on the encoding of numerical values

Non-enumerated numbers encoded in n bits represent values from 1 to 2ⁿ, inclusive. Compressed payload fields are packed least-significant-bit first. The version field in the compatibility header remains big-endian.

Compressed file format

The compressed output is structured as follows:

              0   1    2    3...
            +---+---+-----+===============+
            |  VSN  | NOC |... PHRASES ...|
            +---+---+-----+===============+

• VSN is a 16-bit version number, currently 0x0003.
• NOC is a byte-represented boolean number indicating if compression has been bypassed entirely. 0x01 indicates no compression at all, whereby PHRASES will consist of a literal copy of the data. The only other acceptable value is 0x00.
• Compressed PHRASES form a bit stream encoded with an external canonical Huffman table of 512 symbols. Symbols 0..255 represent literal bytes. Symbols 256..511 represent back-reference lengths 1..256.
• A literal phrase consists only of its Huffman symbol.
• A back-reference consists of its Huffman length symbol, a one-bit type, and an offset. Type 0 has a 14-bit offset; type 1 has a 21-bit offset.
• Every Huffman symbol is at least eight bits long. Consequently, the final padding of at most seven bits cannot be decoded as another symbol.

Interpreting back-references

A back-reference is an imperative to copy from already decompressed data. The "offset" field indicates how far back in the decompressed data to copy from, and the "length" field indicates how many bytes to copy. A back-reference may overlap with its own output, to create so-called "run length encodings", where many copies of the same byte are represented by a single back-reference. Whenever the computed index i of a byte to copy turns out negative, it is interpreted as the byte at index DICT_SIZE + i in the dictionary.

The dictionary is an unstructured, user-provided stream of bytes that domain knowledge suggests are likely to occur in the data. It can improve the compression ratio, especially for small data. The dictionary is not part of the compressed data, and is not transmitted. Users are responsible for ensuring that the same dictionary is used by both the compressor and the decompressor.