# deflate.raw

> A module of deflate's API.

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`

```mojo
struct InflateStatus
```

Why `Inflater.run` or `GzipReader.run` returned.

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

Fields:

- `value: Int`

#### `OUTPUT`

```mojo
comptime OUTPUT = InflateStatus(Int(0))
```

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

#### `NEED_INPUT`

```mojo
comptime NEED_INPUT = InflateStatus(Int(1))
```

More input is needed before anything more can be decoded.

#### `FINISHED`

```mojo
comptime FINISHED = InflateStatus(Int(2))
```

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

#### `__eq__`

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

#### `write_to`

```mojo
def write_to(self, mut writer: T)
```

### `Inflater`

```mojo
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 `compact`s 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`.

```mojo
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__`

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

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

#### `output`

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

The window: everything decoded and not yet compacted away.

#### `__len__`

```mojo
def __len__(self) -> Int
```

`len(output())`.

#### `compact`

```mojo
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`

```mojo
def total_out(self) -> Int
```

Bytes decoded so far, compacted or not.

#### `finished`

```mojo
def finished(self) -> Bool
```

Whether the final block has been decoded.

#### `finish`

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

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

#### `input_used`

```mojo
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`

```mojo
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`

```mojo
def total_in(self) -> Int
```

Input consumed so far, discarded or not.

#### `run`

```mojo
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`

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

Decompress a raw DEFLATE stream.

### `inflate_at`

```mojo
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`

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

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

## Aliases

### `MARGIN`

```mojo
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.
