lzo

README

lzo

A pure-Go (CGO_ENABLED=0, no third-party dependency) decoder for the LZO1X compressed bytestream and the lzop (.lzo) container.

func Decompress(src []byte, uncompressedLen int) ([]byte, error) // one LZO1X block
func NewReader(r io.Reader) (io.Reader, error)                   // an lzop stream

Licence, and why this was written from scratch

liblzo2 — the reference LZO implementation — is GPL-2.0. This package is BSD-3-Clause, so no liblzo2 code, and no port or translation of liblzo2 code, was read, consulted or adapted.

It was written instead from a published prose description of the bytestream:

• "LZO stream format as understood by Linux's LZO decompressor" by Willy Tarreau and Dave Rodgman — Documentation/staging/lzo.rst in the Linux tree. It gives the instruction table, the variable-length encoding, the distance formulas, the meaning of the state variable and the end-of-stream marker. Every rule in lzo1x.go comes from that table.
• the lzop(1) command-line tool, used as a black box: lzop -c writes the fixtures, lzop -dc reads them back, and every hand-built corner case in testdata/crafted.json had to be decompressed by lzop to exactly the expected bytes before it was allowed to become a fixture.

Reading a format description and checking the result against a black-box reference is the whole method. The container layout was pinned down the same way — field by field, then confirmed against real .lzo files, which is how two mistakes in the working notes were caught (see Two things worth knowing, below).

Install

go get github.com/go-compressions/lzo

Usage

f, _ := os.Open("firmware.lzo")
r, err := lzo.NewReader(f)
if err != nil {
	log.Fatal(err) // not lzop, a filtered stream, a bad header checksum...
}
data, err := io.ReadAll(r)

// A bare LZO1X block, whose output length the caller already knows.
plain, err := lzo.Decompress(block, 4096)

Errors are sentinel-wrapped, so a caller can tell the cases apart with errors.Is: ErrMagic (not an lzop stream), ErrHeader (malformed or truncated), ErrChecksum, ErrUnsupported (a filter, an extra field, a non-LZO1X method, a stream needing a newer lzop), ErrCorrupt (a bad LZO1X block), ErrBitstreamVersion (LZO-RLE) and ErrTooLarge (a requested output above DefaultMaxOutput).

Untrusted input

Lengths come from a container header somebody else wrote, and LZO1X expands up to 255:1 (each extra length byte adds 255 — the kernel document says "the compression ratio cannot exceed around 255:1"). Before v0.3.0:

• Decompress(src, n) allocated n as given: three bytes asking for 1 GiB allocated 1 GiB (measured with TotalAlloc).
• NewReader sized its buffers from the block header before reading the payload: a block claiming 64 MiB followed by 10 bytes allocated 64 MiB, and a 100-byte block claiming 64 MiB allocated 64 MiB for output that could never be produced.

Now:

bound	where	result
n > DefaultMaxOutput (1 GiB)	Decompress	ErrTooLarge, before allocating
n > MaxExpansion (255) × len(src)	Decompress	ErrCorrupt, before allocating — such a block cannot exist
uncompressed length > 255 × compressed length	NewReader, per block	ErrHeader, before any buffer is sized
compressed length claim	NewReader, per block	the payload buffer grows with the bytes that actually arrive (64 KiB, then doubling)
block size > 64 MiB	NewReader	ErrHeader (lzop's own maximum, unchanged)

FuzzExpansion decodes into an output far above the bound and asserts that no accepted block exceeds it, so the 255 is checked rather than trusted, and FuzzDecompress no longer skips large lengths.

Decoder only

There is no compressor, on purpose. Writing .lzo serves nobody: every consumer of the format already reads gzip, zstd or xz, all of which compress better, and a second encoder would double the surface that has to be proved byte-exact while adding no capability a reader does not already give. Decoding is what lets Go programs open the .lzo files that already exist — Hadoop splits, firmware images, initramfs payloads, old archives.

How it works

LZO1X. The bytestream is a sequence of one-byte opcodes, each carrying a match length, part of a distance and the number of literals that follow it. Five instruction shapes cover the space:

opcode	shape	meaning
0..15	0000LLLL / 0000DDSS	a literal run of 4 or more, or a 2-byte match within 1 KiB, or a 3-byte match 2..3 KiB back — which one depends on how many literals the previous instruction copied
16..31	0001HLLL + LE16	a match 16..48 KiB back; distance 16384 means end of stream
32..63	001LLLLL + LE16	a match within 16 KiB
64..127	01LDDDSS + byte	3..4 bytes within 2 KiB
128..255	1LLDDDSS + byte	5..8 bytes within 2 KiB

A length field of zero switches to a continuation encoding: any number of 0x00 bytes each adding 255, then one non-zero byte adding its value. The opening byte of a block follows its own rule, because there is no output behind it to copy from: above 17 it means a literal run of byte−17, and it is the only way a run of 1 to 3 literals can be spelled.

The container. Nine magic bytes, then a big-endian header whose shape depends on its own version field, then an Adler-32 or CRC-32 over that header, then blocks: uncompressed length, compressed length, up to four optional checksums, payload. A zero uncompressed length ends the stream.

Methods 1, 2 and 3 are one format. LZO1X_1, LZO1X_1_15 and LZO1X_999 differ only in how hard the compressor searches; all three emit the same instruction grammar and all three decode with the same decoder. It looks like three formats and it is one.

Two things worth knowing

A block whose compressed length equals its uncompressed length is stored, not compressed. lzop falls back to storing whenever LZO1X would make a block bigger, which incompressible input always does. A decoder that hands every block to the LZO1X decompressor fails on the first random-bytes file it meets — and a corpus without such a file will never say so. rand.lzo and mixedstore.lzo exist for that, and the tests count the stored blocks they produce and fail if the count is zero.

lzop refuses a block whose compressed length is not strictly less than its uncompressed length. That is the same rule seen from the writer's side, and it is why every hand-crafted block in testdata/crafted.json ends with cheap padding: without it, lzop declines to read the fixture at all and cannot act as a judge.

Not supported

• LZO-RLE (bitstream version 1, the zram zero-run extension). No witness for it is available here, and a decoder that silently mis-decodes is worse than one that says no. ErrBitstreamVersion.
• lzop's delta filters (lzop --filter=N) and its header extra field. ErrUnsupported, with testdata/text-filter1.lzo as the real-world fixture.

Tests

• Every fixture's premise is asserted before it is judged. testdata/gen.sh makes each .lzo with real lzop and requires lzop -dc to reproduce the source byte-for-byte before the fixture is kept. A generator that reports success without doing the work is worse than no generator.
• The corpus is proved to reach the grammar, not assumed to. The decoder counts each instruction class it decodes, and a test fails if any class was never reached. That is how the one class lzop's compressors never emit — the state-4 short match, 3 bytes from 2..3 KiB back — was found, and why testdata/gen_crafted.py exists.
• The crafted cases are judged by lzop, not by this package. Each is built by hand from the published description, wrapped in a container carrying the Adler-32 of the expected output, and handed to lzop -dc. A case lzop refuses, or decodes differently, fails the generator and never becomes a fixture.
• Ablation. Each rule of the encoding, the stored-block shortcut, the end-of-stream zero, the checksum choice and the big-endian reads were broken one at a time to confirm the suite notices. That sweep found a test that only looked like it tested the compressed-length guard.
• 100 % statement coverage, gated in CI on four native and four emulated architectures (riscv64, loong64, ppc64le, s390x). Fixtures are embedded with //go:embed, because the emulated lanes run a cross-compiled test binary with no testdata beside it.

Regenerating the corpus

sh testdata/gen.sh      # needs lzop(1) and python3

Documentation

Overview

Package lzo decodes the LZO1X compressed bytestream and the lzop (.lzo) container, in pure Go, with no cgo and no third-party dependency.

Provenance and licence

This is an independent implementation written from a published prose description of the LZO1X bytestream — principally "LZO stream format as understood by Linux's LZO decompressor" by Willy Tarreau and Dave Rodgman, distributed as Documentation/staging/lzo.rst in the Linux source tree and published at https://docs.kernel.org/staging/lzo.html — cross-checked end-to-end against streams produced by the lzop(1) command-line tool, treated purely as a black box.

No liblzo2 code, and no port or translation of liblzo2 code, was read, consulted or adapted. liblzo2 is GPL-2.0; this package is BSD-3-Clause, and the two must not be mixed. The lzop container layout was likewise derived from a field-by-field description plus empirical inspection of real .lzo files, not from lzop's sources.

Decoder only

There is deliberately no compressor here. Writing .lzo serves nobody: every consumer of the format already reads gzip, zstd or xz, all of which compress better, and a second encoder would double the surface area that has to be proved byte-exact while adding no capability a reader does not already give. Decoding is what lets Go programs open the .lzo files that already exist — Hadoop splits, embedded firmware images, kernel initramfs payloads, old archives — and that is the whole scope.

The two layers

Decompress decodes one LZO1X block. LZO1X blocks are not self-delimiting in their output length, so the caller must supply it; containers such as lzop store it alongside each block.

NewReader decodes a whole lzop stream: it parses and checksum-verifies the file header, then walks the block list, decompressing each block and verifying its checksums.

Methods 1 (LZO1X_1), 2 (LZO1X_1_15) and 3 (LZO1X_999) all decode with the same LZO1X decoder. They look like three formats and they are one: only the compressor differs — how hard it searches for matches — and every one of them emits the same instruction grammar. A decoder that special-cased them would be three copies of one thing.

Untrusted input

An LZO1X length can grow 255-fold (MaxExpansion) and the lengths a caller passes to Decompress, like the block lengths NewReader reads, come from headers an attacker can write. Both are checked against what the input could possibly produce, and against DefaultMaxOutput, before any buffer is sized from them; NewReader also grows its payload buffer only as bytes arrive.

What is not supported

LZO-RLE (bitstream version 1, the zram zero-run extension) is rejected rather than guessed at: no witness for it is available to verify against here, and a decoder that silently mis-decodes is worse than one that says no. lzop's delta filters and its extra-field header block are rejected for the same reason. Each returns a distinguishable error.

Index

• Constants
• Variables
• func Decompress(src []byte, uncompressedLen int) ([]byte, error)
• func NewReader(r io.Reader) (io.Reader, error)

Constants

const DefaultMaxOutput = 1 << 30

DefaultMaxOutput is the largest uncompressedLen Decompress will allocate for: 1 GiB. Real containers are far below it (lzop blocks are at most 64 MiB, the kernel filesystems use 4 KiB to 1 MiB).

const MaxExpansion = 255

MaxExpansion is how many output bytes one input byte can produce at most. A length is extended 255 at a time by one extra zero byte each, so the ratio "cannot exceed around 255:1" (Documentation/staging/lzo.rst in the Linux tree); every instruction's output is strictly below 255 times its input.

Variables

var (
	// ErrMagic reports a stream that does not begin with the lzop magic.
	ErrMagic = errors.New("lzo: not an lzop stream")

	// ErrHeader reports a malformed or unreadable lzop header or block header.
	ErrHeader = errors.New("lzo: malformed lzop stream")

	// ErrChecksum reports a header or block checksum that does not match.
	ErrChecksum = errors.New("lzo: lzop checksum mismatch")

	// ErrUnsupported reports a well-formed lzop stream this package declines to
	// decode: an unknown compression method, a delta filter, an extra-field
	// header block, or a stream that demands a newer lzop than 1.04.
	ErrUnsupported = errors.New("lzo: unsupported lzop stream")
)

Container-level errors. Each is distinguishable with errors.Is so a caller can tell "this is not an lzop file" from "this is one, and I cannot read it".

var ErrBitstreamVersion = errors.New("lzo: unsupported LZO1X bitstream version")

ErrBitstreamVersion reports an LZO1X block carrying a bitstream version marker for a version this package does not decode. Version 1 is LZO-RLE, the zero-run extension used by zram; see the package documentation.

var ErrCorrupt = errors.New("lzo: corrupt LZO1X block")

ErrCorrupt reports an LZO1X block that cannot be decoded: a truncated instruction or operand, a match reaching back before the start of the block, an output overrun, or a missing end-of-stream marker.

var ErrTooLarge = errors.New("lzo: output exceeds the size limit")

ErrTooLarge reports a block that asks for more output than DefaultMaxOutput. It is returned before the output is allocated.

Functions

func Decompress

func Decompress(src []byte, uncompressedLen int) ([]byte, error)

Decompress decodes one LZO1X block and returns its uncompressedLen bytes.

LZO1X does not record its output length, so uncompressedLen must be supplied by the caller from wherever the container kept it. It is exact, not a hint: a block that ends after a different number of bytes, or that has bytes left over after its end-of-stream marker, is reported as ErrCorrupt rather than truncated or padded to fit.

The same decoder reads blocks from every LZO1X compressor variant — LZO1X_1, LZO1X_1_15 and LZO1X_999 (lzop methods 1, 2 and 3) — because they share one bytestream grammar.

uncompressedLen usually comes from a container header an attacker wrote, so it is checked before the output is allocated: a length above DefaultMaxOutput is ErrTooLarge, and a length that len(src) input bytes cannot possibly produce (see MaxExpansion) is ErrCorrupt.

func NewReader

func NewReader(r io.Reader) (io.Reader, error)

NewReader returns an io.Reader yielding the uncompressed contents of the lzop (.lzo) stream in r.

The file header is read and verified before NewReader returns, so a stream that is not lzop, or is lzop this package declines to decode, is reported here rather than on the first Read. Block and header checksums are verified whenever the stream carries them; a mismatch is reported as ErrChecksum.

lzop stores its own integers big-endian, and its blocks each carry both lengths, so a block whose compressed length equals its uncompressed length is stored verbatim rather than compressed — which is what lzop does with incompressible input. Such blocks are passed through, not handed to the LZO1X decoder.