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
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.
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.
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.
deflateDecompress
Inflater.decompress, building the decompressor for this call alone.
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.
DeflateHuffmanScratch
The scratch deflateLengths sorts and folds in, sized for the 288 literal/length symbols, the largest alphabet.
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.
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.
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).
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.
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
ni32requiredThe 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
ni32requiredThe 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[]requiredThe array that holds the data to compress.
offi32requiredWhere in src the data starts.
leni32requiredHow many bytes of data to compress.
outu8[]requiredThe caller's array the stream is written into.
ati32requiredWhere in out the stream starts.
leveli32requiredHow 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[]requiredThe array that holds the raw DEFLATE stream.
offi32requiredWhere in src the stream starts.
leni32requiredHow many bytes the stream is.
outu8[]requiredThe caller's array the data is written into.
ati32requiredWhere in out the data starts.
limiti32requiredThe 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
ni32requiredThe 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.

