nish/compress/deflate

DEFLATE (RFC 1951), both ways, in pure Nish: a compressor with levels and a decompressor that refuses malformed input with an error code. nish/compress/gzip and nish/compress/zlib frame it.

import {
  DEFLATE_BEST,
  DEFLATE_DEFAULT,
  DEFLATE_ERR_BLOCK_TYPE,
  DEFLATE_ERR_DISTANCE,
  DEFLATE_ERR_HUFFMAN,
  DEFLATE_ERR_OUTPUT_LIMIT,
  DEFLATE_ERR_STORED_LENGTH,
  DEFLATE_ERR_SYMBOL,
  DEFLATE_ERR_TRAILING,
  DEFLATE_ERR_TRUNCATED,
  DEFLATE_FAST,
  DEFLATE_NO_ROOM,
  DEFLATE_STORE,
  DeflateHuffmanScratch,
  Deflater,
  FixedDeflater,
  INFLATE_DONE,
  INFLATE_NEED_INPUT,
  INFLATE_NEED_OUTPUT,
  InflateTable,
  Inflater,
  compressBound,
  deflateBound,
  deflateCompress,
  deflateDecompress,
  fixedDeflateBound,
} from "nish/compress/deflate";
import { Deflater, Inflater, DEFLATE_FAST, deflateBound } from "nish/compress/deflate";

const deflater = new Deflater(DEFLATE_FAST); // tables, once
const out: u8[] = new Array<u8>(deflateBound(len));
const end: i32 = deflater.compress(src, off, len, out, 0); // -1: no room
const inflater = new Inflater();
const n: i32 = inflater.decompress(out, 0, end, back, 0, limit); // < 0: an error
Sans-IO and allocation-free once built

Both objects take caller-owned windows, src[off .. off + len) in and out[at ..) out, and answer where the output ends. Everything a call needs — the match finder's hash chains, the block's symbols, the Huffman scratch, the decoder's tables — is allocated by the constructor, about 330 KB for a Deflater and 28 KB for an Inflater, so build one per thread and reuse it: a call allocates nothing. The free functions deflateCompress and deflateDecompress build one for a single call, for a program that compresses once.

Levels

DEFLATE_STORE (0) writes stored blocks only. 1 to 3 match greedily on a four-byte hash with a short chain (DEFLATE_FAST is 1, about libdeflate's level 1); 4 to 9 match lazily on a three-byte hash with longer chains (DEFLATE_DEFAULT is 6). Every block is written as whichever of dynamic Huffman, fixed Huffman and stored is smallest, by its exact size in bits, so no level ever expands its input by more than deflateBound allows. A block ends after 16,383 symbols.

Decompression is bounded and total

Inflater.decompress writes at most limit bytes, and a stream that would write more answers DEFLATE_ERR_OUTPUT_LIMIT, so a small input cannot expand without bound. Every malformed stream — a reserved block type, a stored length whose complement is wrong, an over-subscribed or incomplete code, a symbol no code defines, a distance before the start of the output, input that ends inside the stream — answers its own negative DEFLATE_ERR_* code; nothing a stream holds can panic. Bytes after the final block are DEFLATE_ERR_TRAILING from decompress; inflate, the resumable step under it and nish/compress/gzip's reader, stops at the final block and says where.

What is unchecked

The hot loops read and write through nish:unsafe's uncheckedGet and uncheckedSet. Each such index is one of: a table entry, below a size the constructor allocated and the readonly field keeps; a position the caller's window was checked to contain before the loop; or a match candidate, which the loop checks lies in [histStart, p) before reading it. A stream's distances and lengths are checked against the output before any copy.

Written from RFC 1951; the code-length construction follows Moffat and Katajainen, "In-place calculation of minimum-redundancy codes" (1995), and the length limit is the Kraft-sum repair of the counts per length. Not ported from another implementation.

Functions

compressBound

The most bytes a compressed body of n input bytes takes in any of this directory's formats: deflateBound(n) with room for gzip's 18 bytes of header and trailer, which covers zlib's 6.

const compressBound: (n: i32) => i32
ni32required

The length of the input, in bytes.

returnsi32

A size in bytes, not a position: an out with this many bytes from at always holds the raw, zlib or gzip stream.

deflateBound

The most bytes Deflater.compress writes for n bytes of input, at any level: the input stored, five bytes of framing for every 65,535 and for every block, and slack for the last partial byte. n is at most 2^31 - 1 less the framing; a negative n answers 0.

const deflateBound: (n: i32) => i32
ni32required

The length of the input, in bytes.

returnsi32

A size in bytes, not a position: an out with this many bytes from at always holds the stream.

deflateCompress

Deflater.compress at level, building the compressor for this call alone: 330 KB allocated and filled each time, so keep a Deflater for anything repeated.

const deflateCompress: (
  src: u8[],
  off: i32,
  len: i32,
  out: u8[],
  at: i32,
  level: i32,
) => i32
srcu8[]required

The array that holds the data to compress.

offi32required

Where in src the data starts.

leni32required

How many bytes of data to compress.

outu8[]required

The caller's array the stream is written into.

ati32required

Where in out the stream starts.

leveli32required

How hard to compress, 0 to 9; another level panics.

returnsi32

The index in out one past the stream's last byte, or DEFLATE_NO_ROOM, as Deflater.compress answers.

deflateDecompress

Inflater.decompress, building the decompressor for this call alone.

const deflateDecompress: (
  src: u8[],
  off: i32,
  len: i32,
  out: u8[],
  at: i32,
  limit: i32,
) => i32
srcu8[]required

The array that holds the raw DEFLATE stream.

offi32required

Where in src the stream starts.

leni32required

How many bytes the stream is.

outu8[]required

The caller's array the data is written into.

ati32required

Where in out the data starts.

limiti32required

The most bytes of data to accept.

returnsi32

The index in out one past the data's last byte, or a negative DEFLATE_ERR_* code, as Inflater.decompress answers.

fixedDeflateBound

The most bytes FixedDeflater.compress writes for n bytes of input: nine bits a byte, the block's header and end code, and the eight bytes of slack its word-wide bit writer stores past the last whole byte. A negative n answers the bound of 0.

const fixedDeflateBound: (n: i32) => i32
ni32required

The length of the input, in bytes.

returnsi32

A size in bytes, not a position: a room of this many always holds the block.

Classes

DeflateHuffmanScratch

The scratch deflateLengths sorts and folds in, sized for the 288 literal/length symbols, the largest alphabet.

class DeflateHuffmanScratch
Member
new DeflateHuffmanScratch() Allocates the scratch.

Deflater

A DEFLATE compressor at one level: the match finder's tables, one block of symbols, the Huffman scratch and the bit writer, allocated once. Not shared between threads; reuse it for every call on one.

class Deflater
Member
new Deflater(level: i32) A compressor at level, 0 to 9; another level panics.
compress(src: u8[], off: i32, len: i32, out: u8[], at: i32): i32 Compresses src[off .. off + len) into out from at as one raw DEFLATE stream, and answers where it ends, or DEFLATE_NO_ROOM when out cannot hold it: deflateBound(len) bytes always can. A window outside its array panics. Allocates nothing.

FixedDeflater

A one-block DEFLATE compressor in the fixed Huffman code (BTYPE=01, §3.2.6) for short inputs such as an HTTP response body: one hash probe per position, matches at most FIXED_WINDOW back, no code to build or send. It carries nothing from one call to the next: the hash table, sized to the input, is cleared at the start of every call, so the output is a function of the input alone. About 70 KB of tables; reuse one per thread.

class FixedDeflater
Member
new FixedDeflater() The tables, once.
compress(src: u8[], off: i32, len: i32, out: u8[], at: i32, room: i32): i32 Compresses src[off .. off + len) as one final fixed-Huffman block into out[at .. at + room), and answers where it ends, or DEFLATE_NO_ROOM as soon as it would need more than room bytes: a caller that only wants the output when it is smaller passes the most it will take, and an input that does not compress is abandoned part way. fixedDeflateBound(len) always fits. A window outside its array panics. Allocates nothing.

InflateTable

One Huffman decoding table: the entries for every bits-bit prefix, and for the codes longer than that, the count per length and the symbols in canonical order that a bit-at-a-time decode walks (§3.2.2).

class InflateTable
Member
new InflateTable(bits: i32, symbols: i32, capacity: i32) A table indexing bits bits, for an alphabet of up to symbols symbols, with room for capacity entries: the main table and its subtables. The arrays are allocated here and filled by Inflater.

Inflater

A DEFLATE decompressor: the decoding tables, the fixed code's, and the state that lets inflate stop at the end of its input or output and resume. Not shared between threads.

class Inflater
Member
new Inflater() Builds the tables, the fixed code's among them.
consumed: i32 The input bytes the last decompress read, its final block included.
inPos: i32 Where the last inflate stopped in its input: the first byte it did not use, or after INFLATE_DONE the first byte after the final block.
outPos: i32 Where the last inflate stopped in its output: one past the last byte it wrote.
decompress(src: u8[], off: i32, len: i32, out: u8[], at: i32, limit: i32): i32 Decompresses the raw DEFLATE stream src[off .. off + len) into out from at, writing at most limit bytes and never past out's end, and answers where the output ends; or DEFLATE_ERR_OUTPUT_LIMIT when the stream holds more, DEFLATE_ERR_TRAILING when bytes follow its final block, or another negative DEFLATE_ERR_* for a malformed stream. A window outside its array, or a negative limit, panics. Allocates nothing.
inflate(src: u8[], ip: i32, inEnd: i32, more: boolean, out: u8[], op: i32, outEnd: i32, histStart: i32): i32 Decodes from src[ip .. inEnd) into out[op .. outEnd), resuming where the last call stopped: the resumable step under decompress, for a stream that arrives in pieces or an output buffer that is drained between calls. GzipDecompressor, GzipReader and ZlibDecompressor are built on it. inPos and outPos say where it stopped. Windows outside their arrays panic. Allocates nothing.
reset(): void Starts a new stream: the next inflate reads a first block header and whatever the last stream left in the bit buffer is dropped. A new Inflater is already at the start, and decompress resets itself; call this before reusing one for another stream through inflate.

Constants

9

DEFLATE_BEST: i32

Level 9: lazy matching on the longest chains.

6

DEFLATE_DEFAULT: i32

Level 6: lazy matching, zlib's and gzip's default balance.

-3

DEFLATE_ERR_BLOCK_TYPE: i32

A block of the reserved type 3 (RFC 1951 §3.2.3).

-7

DEFLATE_ERR_DISTANCE: i32

A distance that reaches back before the start of the output.

-5

DEFLATE_ERR_HUFFMAN: i32

A dynamic block's code is unusable (§3.2.7): an over-subscribed or incomplete set of lengths, a repeat with nothing to repeat or past the end, more than 286 literal/length or 30 distance codes, or no end-of-block code.

-8

DEFLATE_ERR_OUTPUT_LIMIT: i32

The output would pass limit bytes, or the end of out.

-4

DEFLATE_ERR_STORED_LENGTH: i32

A stored block whose NLEN is not the complement of its LEN (§3.2.4).

-6

DEFLATE_ERR_SYMBOL: i32

A code the block's tables do not define, or literal/length 286 or 287, or distance 30 or 31.

-15

DEFLATE_ERR_TRAILING: i32

decompress: bytes follow the final block.

-2

DEFLATE_ERR_TRUNCATED: i32

The input ends inside the stream.

1

DEFLATE_FAST: i32

Level 1: greedy matching on a short hash chain, for speed over ratio.

-1

DEFLATE_NO_ROOM: i32

compress and its framings: out has no room for the whole stream.

0

DEFLATE_STORE: i32

Level 0: stored blocks only, the input copied with five bytes of framing per 65,535.

1

INFLATE_DONE: i32

Inflater.inflate: the final block has ended; inPos is the first byte after it.

2

INFLATE_NEED_INPUT: i32

Inflater.inflate: every byte given was used and the stream goes on; call again with more.

3

INFLATE_NEED_OUTPUT: i32

Inflater.inflate: the next symbol does not fit before outEnd; make room and call again.