Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-compress

Source of release 0.9.0

0.9.0 / README.md

# luce-compress

Native Luce Base compression primitives with an owning Luce API.
MIT OR Apache-2.0; see [provenance](NOTICE.md) for the retained MIT source notice.
No zlib/C codec, foreign library or compression subprocess in the runtime.

**Experimental M1a work: whole-buffer zlib encoding/decoding and incremental
raw-DEFLATE/zlib encoding/decoding, with cooperative work budgets and deterministic
allocation-failure tests.** Resource, larger-stream and seeded fuzz tests are included;
this is not yet the completed compression milestone or a full zlib replacement.
Brotli decoding (RFC 7932) and the gzip format (RFC 1952), whole-buffer and
incremental, serve WOFF2 fonts and HTTP `Content-Encoding: br` and `gzip`.

## API

Add a path dependency while the package installer is under construction:

```toml
[dependencies]
luce_compress = "../luce-compress"
```

```luce
from luce_compress.compress import encode, decode

pub func main(arguments: list[str]) -> int!:
    let packed = encode(b"Luce package source")
    let plain = decode(packed.bytes(), max_output = 1024)
    assert(plain.bytes() == b"Luce package source")
    plain.close()
    packed.close()
    return 0
```

- `encode(data, max_output=67108864, level=6)`: a deterministic zlib stream at
  zlib's levels 0-9 (0 stores, 1 is fastest, 9 smallest; 6 by default), made
  by `flate`'s libdeflate-style matchers with dynamic, fixed or stored blocks.
  Base callers use `compress(data, level=6)` for the bytes alone. Over
  2 MiB, both deflate 1 MiB segments on several threads (each with a fresh
  window, joined by sync flushes into one stream any inflater reads, the
  segments' Adler-32s combined), as pigz does; the bytes do not depend on
  the machine.
- `decode(data, max_output=67108864, allow_trailing=false)`: stored/fixed/dynamic
  DEFLATE blocks in one zlib stream, through `flate`'s table-driven decoder (a
  256 KiB window, output grown to at most `max_output`); validates header,
  trees, backreferences and Adler32. Trailing bytes, including another stream,
  are rejected by default. A stream split into 1 MiB segments (what
  `encode` and `compress` write over 2 MiB) decodes on several threads, as
  does `inflate`'s: every segment is checked (its size, its end at the next
  flush, the Adler-32), and any other stream decodes on one thread.
- Results own their bytes. `bytes()` borrows them in Base; the Luce bridge copies
  them. `consumed()` is the input-byte count, including zlib header/checksum. With
  `allow_trailing=true`, it stops at the first stream so a caller can frame the next
  object without guessing compressed length. No trailing bytes are decoded.
- `adler32(data)` / `crc32(data)` return nonnegative 64-bit values for Luce
  compatibility. These detect corruption; they are not cryptographic integrity.
- `Data.status()` is `finished` for whole-buffer results and the current step
  status for incremental results.

Native callers release returned `interop.Reference[Data]` carriers. Luce owns them
through managed lifetime; `close()` is idempotent. Results and mutable state stay
worker-local. Independent operations may run on multiple threads; one DEFLATE
stream is not automatically parallelized.

## Incremental decoding

`Inflater(framing="zlib", max_input=1073741824, max_output=1073741824)` owns a native
decoder. Git loose objects and pack entries use **zlib** framing. Select
`framing="raw"` only for an enclosing format that specifies unwrapped DEFLATE;
there is no framing autodetection. `feed(input, capacity=65536, final_input=false,
work_limit=4096)` returns an owned `Data` chunk with `bytes()`, `consumed()`,
`status()` and `work_units()`:

- `need_input`: the offered input was consumed; supply the next bytes.
- `need_output`: the output chunk filled; reoffer the unconsumed input suffix with
  a positive output capacity. Do not resubmit bytes counted as consumed.
- `finished`: exactly one stream ended. Any unconsumed suffix belongs to the caller;
  reset or create a different decoder for the next stream.
- `yielded`: the operation allowance was used. Requeue the owner, then reoffer the
  unconsumed suffix. Zero consumed/produced bytes are legal; this is not a request
  for more input. All callers must handle this status, including with default limits.

The final-input flag declares an absolute end offset, not a promise that the stream
finishes in this call. It survives output backpressure; later calls can drain with
the unconsumed suffix without repeating the flag. Contradicting that declared end
is an error. Empty input/output chunks are supported. A finished decoder returns
`finished` with zero counts until reset. `reset()` preserves framing/budgets and
clears history, counters, end markers and error state; `close()` is idempotent.

Native zero-copy consumers use `compress_native.make_decoder(...)` and
`Decoder.step(input, output, final_input, work_limit)` with disjoint caller-owned spans.
The last two arguments default to `false` and `4096`. Its `Step` contains `consumed`,
`produced`, `status`, `work_units`. The core retains a 32 KiB history ring and
bounded bit/Huffman state, not caller pointers or the complete input/output. On the
initial 64-bit targets `memory.size_of(Decoder)` is 37,960 bytes. Independent streams may
run on separate bounded workers; never mutate/close one instance concurrently.

Streaming total budgets accept nonnegative signed 64-bit values and default to
1 GiB each. These are processed-byte bounds, not allocations of the budget size.
The owning facade limits each input chunk and output capacity to 1 MiB; native
callers control their own span sizes. The caller schedules calls and can stop/close
between them; there is no background worker or asynchronous cancellation.

`work_limit` accepts 1–65,536 bounded state-machine dispatches per call; invalid
values reject before mutation or facade allocation. `yielded` reports exactly the
chosen allowance; already finished streams report zero work. Native steps allocate
nothing. This is an operation bound, **not a millisecond deadline**: constructor,
reset, facade allocation/managed copies, caller I/O and aggregate concurrency are
outside it. See the [precise counting and scheduling contract](docs/STREAMING_CONTRACT.md#cooperative-scheduling-contract).
The whole-buffer API is not cooperative; its result reports zero counted step work.

Parse/budget errors poison a decoder; reset or close it. The current failed call
returns no chunk, but earlier chunks are **untrusted until final validation**. Keep
them quarantined. Raw DEFLATE has no checksum at all and needs an integrity check
from its enclosing format. Successful zlib Adler32 is not cryptographic verification.
`statistics()` exposes processed input/output counts, `finished`, and `failed` for
diagnostics, not authorization or proof that bytes were published.

The facade allocates its output/carrier before stepping, so an allocation error
cannot discard a successfully advanced step. Invalid facade chunk sizes likewise
fail before advancing. Deterministic Base-heap failure tests now sweep the actual
construction/result/growth allocations, including the native reference shell;
see [failure coverage and its limits](docs/ALLOCATION_FAILURES.md).
See the [contract](docs/STREAMING_CONTRACT.md) and executable
[Luce example](tests/facade.luc) / [native tests](src/stream_tests.lucb).

## Incremental encoding

`Deflater(framing="zlib", max_input=1073741824, max_output=1073741824)` has the same
owning `feed`, `reset`, `close`, `statistics` and `Data` chunk interface as `Inflater`.
Native consumers use `compress_native.make_encoder(...)`, returning an owning
`Encoder` handle with `step(input, output, final_input=false, work_limit=4096)`. Do not copy this handle or
share it across workers; its `close()` releases its two native allocations and is
idempotent on that handle. The decoder remains a fixed-state value, not a handle.

The incremental encoder is its own fixed-Huffman stream codec (work budgets, bounded
state); its bytes differ from the whole-buffer `encode`, which is `flate`'s. Both are
valid zlib and decode alike.

The encoder retains a 65,536-entry match table, 32 KiB history, 258-byte circular
lookahead and bounded pending bits. `encoder_storage_bytes()` is 557,448 bytes on
the initial 64-bit targets, including the handle but excluding allocator metadata
and caller buffers. The table is a separate allocation to avoid a large struct
initializer on small worker stacks. There are no allocations during native `step`;
reset clears/reuses state. Eight independent 512 KiB-stack workers exercise this.

It emits one final fixed-Huffman block with LZ77 matches, with optional zlib framing.
For a given input and framing, compressed bytes do not depend on chunk partitions,
empty calls or output capacity; the match policy agrees with the whole-buffer
encoder. It starts producing output before EOF once it has sufficient lookahead,
without retaining the whole source. Fixed codes can expand incompressible inputs;
there is no claim of optimal compression or a stored-block fallback in this version.

An explicit final-input declaration is required: reaching `max_input` does not
implicitly end the source. After accepting exactly that budget, `need_input` can
mean that an empty final call is needed; an additional source byte is rejected.
EOF declarations survive output backpressure just as in the decoder. Successful
input counts include up to 258 bytes of retained lookahead; output counts include
only bytes delivered to the caller. Pending bits/lookahead can remain after a call.
The same per-chunk 1 MiB facade cap, poisoned-error and quarantine rules apply.
No sync/full-flush operation, dictionary, dynamic-Huffman encoder or tuning level
is exposed. Git compatibility tests cover zlib loose objects and undeltified pack
entries only, not a production Git engine.

## Fast whole-buffer DEFLATE for codecs (`flate`)

`import flate` (Base) is for callers that know their sizes and frame their own data,
as PNG, TIFF and OpenEXR do:

```luce-base
from luce_compress import flate

let out = try alloc u8[flate.deflate_bound(data.length) + 6] in memory.heap
let used = try flate.deflate_zlib(data, 6, out)          # a zlib stream at level 0..9
try flate.inflate_zlib(out[..<used], plain)              # into exactly the plain size

# Independent segments (a fresh window each), joined into one stream as pigz does:
var at = try flate.deflate_raw(first, 6, buffer, false)  # ends in a sync flush
at += try flate.deflate_raw(second, 6, buffer[at..], true)
let adler = flate.adler32_combine(flate.adler32(first), flate.adler32(second), second.length)
```

- `inflate_raw(data, output, progress = none, context = none) -> usize` decodes raw
  DEFLATE into exactly `output` through 12-bit lookup tables and a 64-bit bit buffer,
  returning the input it used; it stops after a final block or at the end of the
  input (a segment). `progress(context, bytes)` hears of every 256 KiB, for callers
  that work on the output as it arrives. `inflate_zlib` adds the header and Adler-32.
- `deflate_raw(input, level, output, last) -> usize` is zlib's algorithm and level
  table with four-byte hash chains: greedy matching at levels 1..3, lazy at 4..9,
  and each block written dynamic, fixed or stored, whichever is smallest. Files come
  out within a percent of zlib's at the same level (usually smaller) in less time.
- `crc32(data, crc = 0)` (slicing by eight), `adler32(data, adler = 1)` and
  `adler32_combine` run several bytes a step.

## Reading ZIP archives (`zip`)

`import luce_compress.zip as zip` (Base) reads an archive held in memory, one entry at
a time, for formats packed in a ZIP (Procreate brushes, OpenDocument, EPUB):

```luce-base
from luce_compress import zip

var archive = try zip.open(bytes)                        # finds the end record, reads the directory
defer archive.close()                                    # frees the entry list; `bytes` stay yours
for index in 0..<archive.count:
    let entry = archive.entries[index]                   # name, method, flags, crc, sizes, offset
let settings = try archive.read("Brush.archive", max_size = 1048576)
defer free(settings) in memory.heap                      # CRC-32 checked
```

- `open(data, max_entries = 65535) -> Archive` searches back over the longest comment
  for the end-of-central-directory record and reads every central record. The archive
  and its entry names borrow `data`.
- `Archive.find(name) -> Entry?`, `has(name)`, `read(name, max_size = 256 MiB)` and
  `extract(entry, max_size)`; the result is a heap buffer of exactly the entry's size.
  Stored (0) and DEFLATE (8) entries read, the latter through `flate.inflate_raw`.
  Sizes come from the central directory, so data-descriptor entries read too.
- Refused with `unsupported`: ZIP64 (records or `0xFFFF…` fields), multi-disk archives,
  encrypted entries and other methods. `invalid`: no end record; `corrupt`: records
  outside the bytes or contradicting each other, a bad DEFLATE stream or CRC-32;
  `limit_exceeded`: more entries than `max_entries` or an entry over `max_size`;
  `missing`: no entry by that name.
- `Archive.stored_bytes(entry)` returns a stored entry's bytes in place, without a copy
  or a CRC check (usdz layers are read this way).
- Writing: `stored_size(files, alignment)` and `write_stored(files, alignment, output)`
  write an archive of `StoredFile(name, data)` entries, all stored, each entry's data
  starting at a multiple of `alignment` bytes (padding in the local header's extra field,
  id 0x1986, as usdz packages require: alignment 64). No compression, no ZIP64.

## LZ4 blocks (`lz4`)

`import lz4` (Base) compresses and decompresses the LZ4 block format, the one USD crate
files use through `TfFastCompression`:

- `bound(size)` is the most bytes compressing `size` bytes can take.
- `compress(input, output) -> usize` is LZ4's fast greedy compressor (12-bit hashes over a
  64 KiB window) and keeps the format's end rules, so any LZ4 decoder reads its output.
- `decompress(input, output) -> usize` checks every length and offset; damaged blocks and
  an output that is too small fail with `corrupt`.

## Brotli decoding (`brotli`)

`import brotli` (Base) decodes the whole Brotli format of RFC 7932: compressed,
uncompressed and metadata meta-blocks, simple and complex prefix codes, block switches,
context modelling, distance codes with NPOSTFIX/NDIRECT and the static dictionary with
all 121 transforms, over windows of 1 KiB to 16 MiB. Large-window streams (a separate,
incompatible format) are refused with `unsupported`. There is no Brotli encoder.

```luce-base
import brotli

let font_tables = try brotli.decode(woff2_data, max_output = 8388608)   # heap; free it
let used = try brotli.decode_into(data, output)                       # into a buffer you size

var state = brotli.Decoder.open(max_output = 1 << 30)                # allocates on first step
defer state.close()
let step = try state.step(piece, room, final_input = last)            # Step: consumed, produced, status
```

- `decode(data, max_output = 64 MiB, allow_trailing = false) -> u8[]` decodes a whole
  stream into a heap buffer the caller frees; `decode_into(data, output) -> usize`
  into the caller's buffer, failing with `limit_exceeded` (`binary.limit`) when it
  would not fit. Bytes after the stream fail with `corrupt` unless allowed.
- `Decoder.step(input, output, final_input = false)` takes input and gives output in
  pieces of any size, down to one byte of each, with the `need_input` / `need_output`
  / `finished` contract of the incremental zlib decoder: `need_input` consumed all the
  input; after `need_output` offer again the input not consumed; at `finished`,
  `consumed` ends exactly at the stream's end, so a caller frames what follows.
  `final_input` declares the end of the input; a stream left incomplete then fails.
  `statistics()`, `reset()` and an idempotent `close()` follow the zlib decoder's.
- Memory: the window (a ring of a power of two up to the stream's window size, started
  small and doubled as output grows, so short streams hold little) and the meta-block's
  prefix-code tables (a few MiB at most). Each meta-block's length is checked against
  `max_output` before its bytes are made, so a small input cannot expand past the
  limit. Every malformed or truncated stream fails with `corrupt`; nothing traps.
- Speed: a fast path decodes whole commands with the bit reader in registers while
  the input and window allow; the resumable states take over at the edges. Whole-buffer
  decoding (native, `--opt 3`, Apple M-series) against Google's decoder (Python's
  `brotli` 1.2.0, in process), best of five:

  | Stream (quality, window)        | Output  | Google    | luce-compress     |
  |---------------------------------|---------|-----------|-------------------|
  | alice29.txt (5, 22)             | 0.15 MB |  600 MB/s |  389 MB/s (0.65x) |
  | alice29.txt (11, 22)            | 0.15 MB |  517 MB/s |  340 MB/s (0.66x) |
  | HTML-like markup (11, 22)       | 0.20 MB |  779 MB/s |  475 MB/s (0.61x) |
  | mapsdatazrh (11, 22)            | 0.29 MB |  275 MB/s |  224 MB/s (0.81x) |
  | 20 MB mixed file (1, 16)        | 20 MB   |  303 MB/s |  273 MB/s (0.90x) |
  | 20 MB mixed file (5, 22)        | 20 MB   | 1892 MB/s | 1671 MB/s (0.88x) |
  | 20 MB mixed file (11, 24)       | 20 MB   | 1282 MB/s | 1271 MB/s (0.99x) |

The dictionary (`src/brotli/dictionary.lucb`) is generated by
`tools/brotli_dictionary.py` from Google's `dictionary.bin` (MIT, its notice kept in
the file) and checked against RFC 7932's appendices.

## gzip (`gzip`)

`import gzip` (Base) reads and writes the gzip format of RFC 1952 over `flate`:

- `decode(data, max_output = 64 MiB, allow_trailing = false) -> u8[]` decodes every
  member of a file through `flate`'s table-driven inflater, checking each header
  (FTEXT, FHCRC with its CRC, FEXTRA, FNAME, FCOMMENT; reserved flags fail) and each
  trailer's CRC-32 and size. Zero bytes after the last member are padding, as GNU gzip
  and Python accept; other trailing bytes fail with `corrupt` unless allowed.
- `Decoder` (`Decoder.open(max_output, multiple = true)`, `step`, `statistics`, `reset`,
  `close`) reads a file in pieces through the incremental raw DEFLATE decoder, with the
  same step contract as `brotli.Decoder`; `multiple = false` finishes after the first
  member, its `consumed` ending there.
- `read_header(data) -> Header` gives a member's fields (flags, time, XFL, system,
  extra, name, comment, length) as views of `data`.
- `encode(data, level = 6) -> u8[]` writes one member (no name, time 0, system 255).

Luce programs use `compress.decode_brotli`, `decode_gzip` and `encode_gzip`, which
return the owning `Data` result.

## Bounds and errors

For the whole-buffer API, input is limited to 1 GiB; the output bound defaults to
64 MiB and may be set to
0–1 GiB. Zero permits an empty decoded result. Validation/limit failures return no
public partial result. The caller's input is never modified. Internal buffers are
released on failures, including result-owner allocation failure.

`invalid`: bad API bound; `corrupt`: malformed/truncated stream, bad checksum or
unexpected trailing bytes; `limit_exceeded`: input/output bound; `unsupported`:
preset dictionary; `closed`: use of a closed native result.

Bounds are per input/output, not an aggregate memory or CPU-time guarantee. The
whole-buffer API retains the complete input and result. Buffer growth can temporarily hold
old and new allocations, encoding also uses a 65,536-entry native-size match table,
and Luce byte copies add memory. Bound concurrency too. Do not use this API as an
unbounded public decompression service.

No preset dictionaries, Brotli encoder, asynchronous cancellation,
dynamic-Huffman incremental encoder or tuning levels yet. The one-shot encoder still emits zlib,
not raw streams. The image library is not migrated to this package in this slice.

## Tests

With pinned sibling `luce-base` and `luce` checkouts:

```sh
python3 tools/bootstrap.py
python3 tests/run.py --mode native0
python3 tests/run.py
python3 tests/sanitize.py
```

Brotli and gzip: `tests/check_brotli.py` compresses seeded inputs at every quality
with Google's encoder (Python's `brotli` module, or the `brotli` CLI) and decodes them
whole and in seeded pieces, and checks that damaged streams are accepted exactly when
Google's decoder accepts them, with its bytes; `tests/check_gzip.py` does the same for
gzip against an RFC 1952 reading over Python's zlib and its `gzip` module. Both run in
every mode and under the sanitizers (CI installs the `brotli` module as an oracle).
Locally, with Google's repository cloned to `../.donors/brotli`:

```sh
python3 tools/conformance.py --tool build/codec_tool --python VENV/bin/python
python3 tools/fuzz.py --tool build/codec_tool --cases 200000
```

decode Google's test data and some 9,600 reference streams (every quality at every
window over varied inputs, a 20 MB file, Python's text/font/generic modes, metadata,
gzip at every level with every header flag and several members) byte for byte, and
fuzz mutated streams for traps, hangs and memory, comparing every Brotli verdict with
Google's decoder.

Bootstrap writes only this package's ignored build directory, never language
sources. Existing pinned compiler paths can be supplied with `--base` / `--luce`.
Python 3.10+, its zlib module and stock Git are test-only independent oracles. CI runs macOS
arm64 and Linux x86-64, all four native optimization modes plus C debug/release.
No Windows support claim is made yet.

Tests include independent encode/decode fixtures across levels/strategies and
32/64 KiB boundaries, exact output limits, checksums, all truncation offsets of a
fixture, malformed Huffman alphabets, empty distance alphabets, reserved symbols,
bad stored lengths, dictionaries, trailing/concatenated streams, bounded expansion,
seeded mutations, native ownership, Luce byte copies and eight independent workers.
AddressSanitizer/UndefinedBehaviorSanitizer run the native API and the full oracle.
Negative tests reject crashes/sanitizer reports rather than counting them as valid
parse failures. This is not a proof of complete coverage or a security review.

ZIP tests build archives in memory (stored, deflated, empty, commented) and damage
one field at a time: CRC-32, DEFLATE block type, encryption flag, method, ZIP64
sizes and counts, disk numbers, directory offset, and every truncated prefix.

Incremental tests add every first split and truncated prefix of short fixtures,
one-byte and varying input/output, overwritten borrowed buffers, end-marker
retention through backpressure, poisoned/reset/closed streams, exact total budgets,
32 KiB distance/wrap and cross-block history, raw trailing objects, checksum errors
after producing output and independent raw/zlib mutations. They run in every mode
and under the sanitizer gate, not only against the whole-buffer implementation.
Stock Git also creates loose objects and an undeltified pack in a disposable local
repository; the decoder checks exact zlib boundaries with later pack bytes still
present. This does not implement or validate a complete Git object/pack engine.

Encoder tests independently stream-decode Base output through Python/zlib, compare
compressed bytes across partitions and against the previous deterministic policy,
exercise every first split around short/lookahead fixtures, exact and insufficient
budgets, overwritten spans, canaries, reset/close and concurrent independent owners.
Stock Git reads Base-encoded loose objects and validates/indexes a separately framed
pack; a second empty repository verifies packed reads cannot fall back to loose data.

An additional 928 independent work-budget cases run one-unit, varying and default
allowances across raw/zlib stored/fixed/dynamic fixtures, exact splits/truncations,
empty-block chains, checksum/limit errors and deterministic encoder output. Together
the five oracle groups contain 6,000 cases per mode. Native and Luce suites cover
zero-I/O yields, cancellation/reset, retained chunks and eight independent workers.

The separate single-threaded allocation test executable runs 388 failure/retry
cases. It replaces the test process's Base heap with a fixed-size tracking allocator,
refuses each allocation in observed traces in both one-shot and persistent-failure
modes, and verifies exact frees and state-safe retries. It also exercises late
codec-error cleanup and proves native step/reset/close make no allocation attempts.
The production library has no test hooks or new allocator dependency. This does
not simulate process-wide OOM, Luce managed-runtime trap-on-exhaustion, OS resource
failures, or concurrent replacement of the process-global heap.

A generated-stream stress driver uses fixed 32 KiB spans, independent worker-owned
codec pairs and eight 512 KiB-stack workers. Five cases run in every compiler mode,
under sanitizers and in the VPS bundle. The full native-opt-3 profile adds sustained
16/128 MiB workloads and a 4 GiB + 1 byte logical stream, without large temporary
files. It checks process peak RSS and records step-latency histograms and paired
pipeline throughput. See [RESOURCES.md](docs/RESOURCES.md) for exact ceilings,
measurement units, exclusions and commands; these are not production SLOs.

Independent decoder fuzzing adds 4,096 seeded cases per mode, under ASan/UBSan and
in the prebuilt suite. Independent larger-file tests add 24 exact-byte/budget cases
at 1 MiB + 1 byte. Both CI hosts also run 65,536 mutations with a second seed and
48 file-stream cases through 16 MiB + 3 bytes. Failures must be normal codec
rejections, never signals or sanitizer findings. See [FUZZING.md](docs/FUZZING.md)
for corpus identities, bounded oracle behavior, retained reproducers and exclusions.
See [VALIDATION.md](docs/VALIDATION.md) for completed revision-specific evidence;
test definitions alone are not a claim that every deployment gate has passed.

## Next commits

1. Close the remaining M0 contracts before marking the dependent M1a milestone
   complete. The expanded codec gates passed locally, on Linux/macOS CI and in the
   isolated VPS suite at `b04e20e`; see the revision-specific validation record.
2. Full threaded Git-consumer integration and aggregate server admission follow
   in M2a/M3a, after their crypto/storage prerequisites.

M1a remains incomplete while its M0 prerequisite is open. The overall public
plan is in [luce-pkg-server](https://github.com/dymokomi/luce-pkg-server).