deflate · API

deflate.raw

Raw DEFLATE (RFC 1951) — inflate and deflate, in pure Mojo.

Raw DEFLATE is the compressed stream on its own: no zlib (RFC 1950) header, no gzip (RFC 1952) wrapper, no trailing checksum. A caller that needs one of those framings parses it itself and hands the body here — Avro's deflate block codec is raw already, and Parquet's GZIP codec is this plus a gzip header and trailer.

Implementing it rather than binding zlib keeps the tin free of FFI and of any sibling dependency, so a consumer needs nothing but -I ../deflate.mojo/src.

inflate handles all three block types (stored, fixed-Huffman, dynamic-Huffman). deflate emits fixed-Huffman blocks from a single-slot hash-chain LZ77 matcher — the same "fast" strategy snappy.mojo uses — which keeps the encoder small.

Structs

InflateStatus

struct InflateStatus

Why Inflater.run or GzipReader.run returned.

Implements Copyable, Equatable, ImplicitlyCopyable, Movable, RegisterPassable, TrivialRegisterPassable, Writable

Fields
value: Int
comptime OUTPUT = InflateStatus(Int(0))

The window holds the output asked for (n >= want).

comptime NEED_INPUT = InflateStatus(Int(1))

More input is needed before anything more can be decoded.

comptime FINISHED = InflateStatus(Int(2))

The stream (every gzip member) has been decoded and checked.

__eq__

def __eq__(self, other: Self) -> Bool

write_to

def write_to(self, mut writer: T)

Inflater

struct Inflater

A raw DEFLATE stream decoded a window at a time.

The output collects in a window, output(). run decodes blocks until the window holds want bytes, the input runs short or the stream ends; the caller uses what is there, then compacts away what it no longer needs. The window keeps the last 32 KiB whatever is dropped, since later back-references may reach that far.

The input may still be arriving. run takes the input so far and whether that is all of it; a block that runs past the bytes there is rolled back to its start and decoded again on a later call, with more. The caller may drop input the inflater has finished with: see discard_input.

var inf = Inflater()
while True:
    var st = inf.run(Span(input), complete, want=len(inf) + (1 << 20))
    use(inf.output())
    _ = inf.compact(len(inf))
    if st == InflateStatus.FINISHED:
        break
    if st == InflateStatus.NEED_INPUT:
        ...  # append more to `input` (or set complete)

inflate and inflate_at are this with the whole input and a window that is never compacted.

Implements Movable, Sized

Fields
out: _Out
pos: Int: The next input byte not yet in the bit buffer, as an offset into the data passed to run.
bitbuf: UInt64
bitcnt: Int
state: Int
margin: Int: Input to have in hand before starting a block while more is still to come (MARGIN). 0 starts every block at once and rolls back each one that outruns the input, which tests use.
dropped_in: Int: Input bytes discard_input has released: what pos is relative to.
dropped_out: Int: Output bytes compact has dropped.
t: _Tables
fixed_lit: _Huffman
fixed_dist: _Huffman
dyn_lit: _Huffman
dyn_dist: _Huffman
dyn_clen: _Huffman: A dynamic block's three codes, rebuilt in place block after block.
lengths: List[Int]: Scratch for a dynamic block's code lengths.

__init__

def __init__(out self, capacity: Int = Int(1048576))

capacity is the window's starting size; it grows as needed.

output

def output(self) -> Span[UInt8, origin_of(self.out.buf)]

The window: everything decoded and not yet compacted away.

__len__

def __len__(self) -> Int

len(output()).

compact

def compact(mut self, keep_from: Int) -> Int

Drop output()[0:keep_from], as far as back-references allow, and return how many bytes went: subtract it from any offsets into the window the caller holds.

total_out

def total_out(self) -> Int

Bytes decoded so far, compacted or not.

finished

def finished(self) -> Bool

Whether the final block has been decoded.

finish

def finish(deinit self) -> List[UInt8]

The window as a list (trimmed to n), consuming the inflater.

input_used

def input_used(self) -> Int

How many bytes of data the inflater is done with. Once the stream has finished this is where it ended (rounded up to a byte), as inflate_at reports.

discard_input

def discard_input(mut self) -> Int

Forget the input before input_used() and return how many bytes that is: the next run must be passed data without them. A long stream can then be fed through a bounded input buffer.

total_in

def total_in(self) -> Int

Input consumed so far, discarded or not.

run

def run(mut self, data: Span[UInt8], complete: Bool, want: Int = Int.MAX) -> InflateStatus

Decode from data (the input so far, from where the last call left off unless discard_input said otherwise; all of it if complete) until the window holds want bytes.

Returns OUTPUT when it does, NEED_INPUT when a block is waiting for more input than data has, or FINISHED after the final block. Raises on corrupt input, and on input that ends early once complete is set.

Functions

inflate

def inflate(data: Span[UInt8]) -> List[UInt8]

Decompress a raw DEFLATE stream.

inflate_at

def inflate_at(data: Span[UInt8], mut end: Int) -> List[UInt8]

Decompress a DEFLATE stream, and report where it ended.

end is set to the offset of the first byte after the stream, rounded up to a byte boundary. Callers with several streams back to back — concatenated gzip members, for instance — need it to find the next one; callers that do not can use inflate.

deflate

def deflate(data: Span[UInt8]) -> List[UInt8]

Compress to a raw DEFLATE stream (one fixed-Huffman block).

Aliases

comptime MARGIN = Int(262144)

The input a block is started with when more is still to come (run with complete=False). zlib ends a block every 16 Ki or 32 Ki symbols, at most about 200 KB of input, so with 256 KiB in hand a block almost never runs past what has arrived; one that does is rolled back and decoded again once more input is there.