tiny.deflate

Overview · API · Code relationships · Verification · Audit

Overview

The decoder expands data compressed with DEFLATE, either bare or inside a zlib or gzip wrapper, from one input buffer into one output buffer that the caller provides.

A program that reads a file format or a message with compressed parts, such as the content streams of a PDF file, needs the original bytes back. The program also needs to know that the bytes it got back are whole and correct before it acts on them. Compressed data arrives in three forms: the bare stream, the stream inside the short zlib header and checksum, and the stream inside the longer gzip header, checksum and length.

The compressed input alone decides how large the expanded data grows, so the program needs a bound on the output that the input cannot move. DEFLATE saves space by repeating bytes it has already produced, from up to 32768 bytes back, so a decoder has to keep that much recent output where it can read it again. A stream can stop short, carry a checksum that disagrees with its data, or be followed by more bytes, as when two gzip files are joined end to end, and a caller that misses any of these trusts output it should refuse.

RFC 1950, RFC 1951 and RFC 1952 define the zlib wrapper, the DEFLATE stream and the gzip wrapper, and the decoder follows their layouts: the three block types, the length and distance tables, the header flags and the trailers. libdeflate is the C library by Eric Biggers for fast DEFLATE compression and decompression of whole buffers. The package takes whole-buffer decoding from libdeflate, one call from a complete input to a complete output, and carries the libdeflate MIT license. The tests reproduce two cases from libdeflate commit b122c8b: the incomplete Huffman codes a stream may use, and code lengths that run past the end of their table.

The decoder allocates nothing: its code tables have fixed sizes and live on the call stack, and the caller's output buffer doubles as the history that repeated bytes are copied from. In exchange, the caller sizes the output buffer before the call, and a stream that expands past it fails with error.OutputTooSmall. The zlib and gzip checksums are always checked before a success, and a zlib stream that asks for a preset dictionary is refused. A second check, on by default, requires the input to end at the last byte of one compressed stream with whatever header and trailer its format adds (frame), so leftover bytes, including a second gzip member joined after the first, fail with error.TrailingInput, and where the data ends stays unambiguous. A third check, off by default, requires the expanded data to fill the output buffer exactly, for a caller that knows the expanded size from elsewhere.

Definitions

Actions

Public operations.

• decompress: Expands one compressed stream with whatever header and trailer its format adds (a frame of input), in the container that format names, into the front of output, so callers can expand a compressed buffer, such as a PDF content stream, into memory they already own.

Types and contracts

Public types and contracts.

• Error: Every way decompress can fail, for a caller to switch on and tell a buffer that is too small from input that is bad.
• Format: The three wrappings that decompress accepts around DEFLATE data, for a caller to pass one tag to decompress to say which wrapper surrounds the compressed data.
• Options: Two checks that decompress runs after the decoder for the format finishes one compressed stream with whatever header and trailer its format adds, a frame, for a caller to choose how closely the frame must match the two buffers.
• Result: The two byte counts of one successful decompress call, for a caller to read after a success and learn how much of each buffer the frame used.

Values and defaults

Public values and defaults.

• upstream_revision: The full commit hash of the libdeflate source that this package takes as its reference.

Code relationships

Direct static dependencies extracted from parsed source by semantic graph analysis.

Uses: tiny.bench, tiny.coz, tiny.hypothesis, tiny.sys
Used by: tiny.pdf, tiny.quic

Verification

No verification records are cataloged for this module in this build.

Audit