compression: Snappy and LZ4 block formats in std/compression (step 1 of #121)

orion commented

2026-10-23 14:23:48 +00:00

Collaborator

Context

Step 1 of #121 (FIRST-PARTY.md gap 26: zstd, snappy and lz4 for std/compression). The two byte-oriented LZ77 block formats come first: they need no checksum and no new package, and they are what MongoDB's wire compression (snappy) and Kafka (snappy, lz4) build on. Frames, checksums and zstd are the later steps listed in #121.

Design

Ordinary TorbScript over Bytes in std/compression, like DEFLATE: no native, no syntax change, no new driver flag, no std name the compiler looks up by string. Touches the seed: no. Implemented from the public format descriptions (Snappy format_description.txt, LZ4's lz4_Block_format.md); no reference code is copied or linked, so the BSD-licensed reference implementations impose nothing on the repository.

New files std/compression/src/snappy.trb and std/compression/src/lz4.trb; the operations are methods of Bytes declared in the extend Bytes block of std/compression/src/lib.trb, imported by the name of the list they extend (use Buffer.snappyCompressed from "std/compression"), as gzipped is. Failures are the existing CompressionError (reason, byte offset).
fn snappyCompressed(): Bytes writes the raw Snappy block format (preamble varint of the uncompressed length, literal and copy elements, 1-, 2- and 4-byte-offset copies as the format allows); greedy hash-table match search, deterministic (same bytes, same output on every machine).
fn snappyDecompressed(): Result<Bytes, CompressionError> reads every valid block; fails on a truncated preamble or element, a copy that reaches before the start of the output, and an output length different from the preamble's. A preamble that declares more than the input could ever produce must not make it allocate that much up front (a 5-byte input declaring 4 GiB fails fast).
fn lz4BlockCompressed(): Bytes writes one LZ4 block (sequences of token, literals, 2-byte little-endian offset, match length; the last sequence literals only; the end-of-block parsing restrictions of the format: last match starts at least 12 bytes before the end, last 5 bytes literals); greedy, deterministic.
fn lz4BlockDecompressed(maximumSize: Int): Result<Bytes, CompressionError>: an LZ4 block does not store its decoded size, so the caller names the largest output it accepts; fails when the output would exceed it, on a truncated sequence, and on an offset of 0 or beyond the start of the output. Overlapping copies (offset smaller than length) repeat bytes as the formats define.
Naming follows deflated/inflated and gzipped/gunzipped (participle methods of Bytes, #146); "Block" is in the LZ4 names because step 2 adds the frame format beside it.
docs/design/FIRST-PARTY.md gap 26 becomes "partly done" (snappy block and lz4 block; the rest named). Add a time-bounded round trip of each codec to std/compression/tests only if it stays well under the existing suite's time; no change to benchmarks/ required.

Acceptance criteria

Bytes.snappyCompressed / snappyDecompressed and lz4BlockCompressed / lz4BlockDecompressed exist in std/compression, as methods importable with use Buffer.<name> from "std/compression".
Round trips are exact for: empty input, one byte, 15 and 16 literal bytes (LZ4 token boundary), a run of one byte (overlapping copy, offset 1), 70 000 bytes of text (copies beyond 64 KiB for Snappy's 4-byte offsets), and 100 000 pseudo-random incompressible bytes.
Known vectors taken from the format descriptions decode to the documented bytes (at least three per codec, by hand from the specs, written into the test with a comment naming the spec section); at least one stream per codec produced by a reference implementation, committed as hex in the test.
Output is deterministic: compressing the same bytes twice, and in the VM and the native build (tier B), gives identical bytes.
Malformed input returns Fail(CompressionError) with an offset, never a panic: truncated stream, copy before the start, offset 0 (LZ4), declared length mismatch (Snappy), output over maximumSize (LZ4), a Snappy preamble declaring 4 GiB over a tiny input (no large allocation).
Compression helps: 64 KiB of repetitive text compresses to under half its size with each codec.
std/compression doc comments updated (summary names all five formats), skills/ regenerated, torb format --check clean on touched files, FIRST-PARTY.md gap 26 marked partly done.
Gates: tier A green in forge CI; tier B (touches only std/, but the codecs run in both back ends) not required unless the round touches compiler/src/ir, compiler/src/backend or runtime/.

Dependencies

None. Blocks the later steps of #121 only in the sense that they extend the same files.

Commits

One or two Conventional Commits: feat(std): snappy and lz4 blocks in std/compression and, if the regenerated skills and design record are committed separately, docs(std): ....

## Context Step 1 of #121 (FIRST-PARTY.md gap 26: zstd, snappy and lz4 for `std/compression`). The two byte-oriented LZ77 block formats come first: they need no checksum and no new package, and they are what MongoDB's wire compression (snappy) and Kafka (snappy, lz4) build on. Frames, checksums and zstd are the later steps listed in #121. ## Design Ordinary TorbScript over `Bytes` in `std/compression`, like DEFLATE: no native, no syntax change, no new driver flag, no std name the compiler looks up by string. **Touches the seed: no.** Implemented from the public format descriptions (Snappy `format_description.txt`, LZ4's `lz4_Block_format.md`); no reference code is copied or linked, so the BSD-licensed reference implementations impose nothing on the repository. - New files `std/compression/src/snappy.trb` and `std/compression/src/lz4.trb`; the operations are methods of `Bytes` declared in the `extend Bytes` block of `std/compression/src/lib.trb`, imported by the name of the list they extend (`use Buffer.snappyCompressed from "std/compression"`), as `gzipped` is. Failures are the existing `CompressionError` (reason, byte offset). - `fn snappyCompressed(): Bytes` writes the raw Snappy block format (preamble varint of the uncompressed length, literal and copy elements, 1-, 2- and 4-byte-offset copies as the format allows); greedy hash-table match search, deterministic (same bytes, same output on every machine). - `fn snappyDecompressed(): Result<Bytes, CompressionError>` reads every valid block; fails on a truncated preamble or element, a copy that reaches before the start of the output, and an output length different from the preamble's. A preamble that declares more than the input could ever produce must not make it allocate that much up front (a 5-byte input declaring 4 GiB fails fast). - `fn lz4BlockCompressed(): Bytes` writes one LZ4 block (sequences of token, literals, 2-byte little-endian offset, match length; the last sequence literals only; the end-of-block parsing restrictions of the format: last match starts at least 12 bytes before the end, last 5 bytes literals); greedy, deterministic. - `fn lz4BlockDecompressed(maximumSize: Int): Result<Bytes, CompressionError>`: an LZ4 block does not store its decoded size, so the caller names the largest output it accepts; fails when the output would exceed it, on a truncated sequence, and on an offset of 0 or beyond the start of the output. Overlapping copies (offset smaller than length) repeat bytes as the formats define. - Naming follows `deflated`/`inflated` and `gzipped`/`gunzipped` (participle methods of `Bytes`, #146); "Block" is in the LZ4 names because step 2 adds the frame format beside it. - `docs/design/FIRST-PARTY.md` gap 26 becomes "partly done" (snappy block and lz4 block; the rest named). Add a time-bounded round trip of each codec to `std/compression/tests` only if it stays well under the existing suite's time; no change to `benchmarks/` required. ## Acceptance criteria - [ ] `Bytes.snappyCompressed` / `snappyDecompressed` and `lz4BlockCompressed` / `lz4BlockDecompressed` exist in `std/compression`, as methods importable with `use Buffer.<name> from "std/compression"`. - [ ] Round trips are exact for: empty input, one byte, 15 and 16 literal bytes (LZ4 token boundary), a run of one byte (overlapping copy, offset 1), 70 000 bytes of text (copies beyond 64 KiB for Snappy's 4-byte offsets), and 100 000 pseudo-random incompressible bytes. - [ ] Known vectors taken from the format descriptions decode to the documented bytes (at least three per codec, by hand from the specs, written into the test with a comment naming the spec section); at least one stream per codec produced by a reference implementation, committed as hex in the test. - [ ] Output is deterministic: compressing the same bytes twice, and in the VM and the native build (tier B), gives identical bytes. - [ ] Malformed input returns `Fail(CompressionError)` with an offset, never a panic: truncated stream, copy before the start, offset 0 (LZ4), declared length mismatch (Snappy), output over `maximumSize` (LZ4), a Snappy preamble declaring 4 GiB over a tiny input (no large allocation). - [ ] Compression helps: 64 KiB of repetitive text compresses to under half its size with each codec. - [ ] `std/compression` doc comments updated (summary names all five formats), `skills/` regenerated, `torb format --check` clean on touched files, FIRST-PARTY.md gap 26 marked partly done. - [ ] Gates: tier A green in forge CI; tier B (touches only `std/`, but the codecs run in both back ends) not required unless the round touches `compiler/src/ir`, `compiler/src/backend` or `runtime/`. ## Dependencies None. Blocks the later steps of #121 only in the sense that they extend the same files. ## Commits One or two Conventional Commits: `feat(std): snappy and lz4 blocks in std/compression` and, if the regenerated skills and design record are committed separately, `docs(std): ...`.

orion added the

loop

ready

labels

2026-10-23 14:23:48 +00:00

orion referenced this issue

2026-10-23 14:24:07 +00:00

compression: zstd, snappy and lz4 #121

orion referenced this issue

2026-10-23 14:24:07 +00:00

compression: zstd, snappy and lz4 #121

orion referenced this issue

2026-10-23 14:24:07 +00:00

compression: zstd, snappy and lz4 #121

orion commented

2026-10-23 14:32:23 +00:00

Author

Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261023 until 2026-10-23T20:32Z

orion referenced this issue from a commit

2026-10-23 14:47:26 +00:00

docs(std): snappy and lz4 blocks, gap 26 partly done

orion referenced this issue from a pull request that will close it,

2026-10-23 14:47:37 +00:00

feat(std): snappy and lz4 blocks in std/compression #433

orion commented

2026-10-23 15:21:29 +00:00

Author

Collaborator

[loop:torbscript] implement: snappy and lz4 block codecs in std/compression with tests, docs and regenerated skills; one docs-declaration round fixed after the first CI run, PR #433, CI success (tier A green), next: review. Tokens: not metered inside this worker run (long run, one context compaction).

[loop:torbscript] implement: snappy and lz4 block codecs in std/compression with tests, docs and regenerated skills; one docs-declaration round fixed after the first CI run, PR https://git.torb.dev/torbscript/language/pulls/433, CI success (tier A green), next: review. Tokens: not metered inside this worker run (long run, one context compaction).