compress - GitLite

KO | EN

gitlite — search

#reactjs #animation #large-language-models #agents #sql #dotnet #swift #html #ui #kubernetes

compress

(★ 14)

compress library implements a lightweight, deflate-like compression algorithm designed to have a simple, zk-friendly decompression algorithm

File Explorer

ZIP Download

- - prpush.yml
  - security-code-scanner.yml
- dependabot.yml
- parse-tests.js
- - main.go
- - downloads.gotpl
  - package.gotpl
- - average_block.hex
  - dict_naive
  - huffman_table
- backref.go
- bitstream.go
- bitstream_test.go
- compress.go
- compress_test.go
- decompress.go
- header.go
- header_test.go
- huffman.go
- huffman_test.go
- regress_test.go
.gitignore
.golangci.yml
go.mod
go.sum
LICENSE
main.go
README.md

# Use via CDN

jsDelivr

jsDelivr serves any public GitHub repository as a CDN with zero setup. Pick a version and a file to get a ready-to-paste link and snippet.

Version

File

Link

Example

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

`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`](https://github.com/Consensys/gnark/tree/master/std/compress).

`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
```go
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:

```shell
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`](https://github.com/Consensys/compress/blob/main/lzss/compress_test.go#L299).

## 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.