compression: xxHash32/xxHash64 in std/digest and the LZ4 frame format (step 2 of #121)

orion commented

2026-11-14 05:54:59 +00:00

Collaborator

Context

Step 2 of #121 (FIRST-PARTY.md gap 26). Step 1 (#432) landed the Snappy and LZ4 block formats in std/compression. The LZ4 frame format needs two checksums, xxHash32 (header checksum byte, block and content checksums) and, for the content checksum, xxHash32 as well; xxHash64 is the sibling that Zstandard's frame content checksum uses (step 3), so both land in std/digest now.

Design

Ordinary TorbScript, 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 specifications (xxHash doc/xxhash_spec.md, LZ4 lz4_Frame_format.md); the BSD reference code is only used to produce test vectors.

std/digest/src/xxhash.trb (new, exported from std/digest/src/lib.trb): Bytes.xxHash32(seed: Int = 0): Int (unsigned 32-bit in an Int) and Bytes.xxHash64(seed: Int = 0), named like the existing digest methods of Bytes (look at sha1.trb/md5.trb for the precedent and the import form). Match the 64-bit wrap-around arithmetic of the language's Int as the existing digests do; if the 64-bit variant needs unsigned multiplication the language lacks, state it in the PR and ship xxHash32 plus the LZ4 frame only, keeping xxHash64 as step 2b.
std/compression/src/lz4_frame.trb (new): Bytes.lz4Framed(): Bytes writes one LZ4 frame (magic 0x184D2204, FLG with version 01, block independence on, block checksums off, content checksum on, no content size, BD with 4 MiB max block size, header checksum byte (xxHash32(descriptor) >> 8) & 0xFF, data blocks of at most 4 MiB each compressed with lz4BlockCompressed or stored uncompressed when that is not smaller, EndMark, content checksum); deterministic.
Bytes.lz4Unframed(maximumSize: Int): Result<Bytes, CompressionError> reads every valid frame: all FLG/BD options (block independence on or off with linked blocks, block checksum, content size, content checksum, dictionary id fails with a clear reason), uncompressed blocks, and skippable frames (0x184D2A5x) between frames; concatenated frames are decoded one after the other. Fails on bad magic, bad header checksum, block over the declared maximum, checksum mismatch, truncated input, and output over maximumSize; never allocates by a declared size.
Failures are the existing CompressionError.

Acceptance criteria

xxHash32 (and xxHash64, see above) produce the published vectors: empty input with seed 0 (0x02CC5D05 for xxHash32, 0xEF46DB3751D8E999 for xxHash64), the spec's other documented vectors, and at least two longer inputs (over 16 and over 32 bytes, so the striped main loop runs) with values taken from a reference implementation and committed as hex in the test.
lz4Framed / lz4Unframed round-trip: empty input, one byte, 70 000 bytes of text, 100 000 pseudo-random bytes (stored blocks), and an input larger than one block.
A frame written by the reference lz4 command line tool (committed as hex, at least one with block checksums and linked blocks, one with content size) decodes to the original bytes; a skippable frame before a frame is skipped; two concatenated frames decode to the concatenation.
Malformed input returns Fail(CompressionError) with an offset, never a panic: bad magic, wrong header checksum, flipped content checksum byte, truncated block, output over maximumSize.
Output is deterministic in the VM and the native build (tier B), identical bytes.
Doc comments of std/digest and std/compression updated, skills/ regenerated, torb format --check clean on touched files, FIRST-PARTY.md gap 26 updated (LZ4 frame done, rest named).
Gates: tier A green in forge CI; tier B only if the round touches compiler/src/ir, compiler/src/backend or runtime/.

Dependencies

Step 1 (#432), closed. No other dependency.

Commits

Two Conventional Commits: feat(std): xxHash32 and xxHash64 in std/digest and feat(std): the LZ4 frame format in std/compression.

## Context Step 2 of #121 (FIRST-PARTY.md gap 26). Step 1 (#432) landed the Snappy and LZ4 block formats in `std/compression`. The LZ4 frame format needs two checksums, xxHash32 (header checksum byte, block and content checksums) and, for the content checksum, xxHash32 as well; xxHash64 is the sibling that Zstandard's frame content checksum uses (step 3), so both land in `std/digest` now. ## Design Ordinary TorbScript, 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 specifications (xxHash `doc/xxhash_spec.md`, LZ4 `lz4_Frame_format.md`); the BSD reference code is only used to produce test vectors. - `std/digest/src/xxhash.trb` (new, exported from `std/digest/src/lib.trb`): `Bytes.xxHash32(seed: Int = 0): Int` (unsigned 32-bit in an `Int`) and `Bytes.xxHash64(seed: Int = 0)`, named like the existing digest methods of `Bytes` (look at `sha1.trb`/`md5.trb` for the precedent and the import form). Match the 64-bit wrap-around arithmetic of the language's `Int` as the existing digests do; if the 64-bit variant needs unsigned multiplication the language lacks, state it in the PR and ship xxHash32 plus the LZ4 frame only, keeping xxHash64 as step 2b. - `std/compression/src/lz4_frame.trb` (new): `Bytes.lz4Framed(): Bytes` writes one LZ4 frame (magic `0x184D2204`, FLG with version 01, block independence on, block checksums off, content checksum on, no content size, BD with 4 MiB max block size, header checksum byte `(xxHash32(descriptor) >> 8) & 0xFF`, data blocks of at most 4 MiB each compressed with `lz4BlockCompressed` or stored uncompressed when that is not smaller, EndMark, content checksum); deterministic. - `Bytes.lz4Unframed(maximumSize: Int): Result<Bytes, CompressionError>` reads every valid frame: all FLG/BD options (block independence on or off with linked blocks, block checksum, content size, content checksum, dictionary id fails with a clear reason), uncompressed blocks, and skippable frames (`0x184D2A5x`) between frames; concatenated frames are decoded one after the other. Fails on bad magic, bad header checksum, block over the declared maximum, checksum mismatch, truncated input, and output over `maximumSize`; never allocates by a declared size. - Failures are the existing `CompressionError`. ## Acceptance criteria - [ ] `xxHash32` (and `xxHash64`, see above) produce the published vectors: empty input with seed 0 (`0x02CC5D05` for xxHash32, `0xEF46DB3751D8E999` for xxHash64), the spec's other documented vectors, and at least two longer inputs (over 16 and over 32 bytes, so the striped main loop runs) with values taken from a reference implementation and committed as hex in the test. - [ ] `lz4Framed` / `lz4Unframed` round-trip: empty input, one byte, 70 000 bytes of text, 100 000 pseudo-random bytes (stored blocks), and an input larger than one block. - [ ] A frame written by the reference `lz4` command line tool (committed as hex, at least one with block checksums and linked blocks, one with content size) decodes to the original bytes; a skippable frame before a frame is skipped; two concatenated frames decode to the concatenation. - [ ] Malformed input returns `Fail(CompressionError)` with an offset, never a panic: bad magic, wrong header checksum, flipped content checksum byte, truncated block, output over `maximumSize`. - [ ] Output is deterministic in the VM and the native build (tier B), identical bytes. - [ ] Doc comments of `std/digest` and `std/compression` updated, `skills/` regenerated, `torb format --check` clean on touched files, FIRST-PARTY.md gap 26 updated (LZ4 frame done, rest named). - [ ] Gates: tier A green in forge CI; tier B only if the round touches `compiler/src/ir`, `compiler/src/backend` or `runtime/`. ## Dependencies Step 1 (#432), closed. No other dependency. ## Commits Two Conventional Commits: `feat(std): xxHash32 and xxHash64 in std/digest` and `feat(std): the LZ4 frame format in std/compression`.

orion added the

loop

ready

labels

2026-11-14 05:54:59 +00:00

orion referenced this issue

2026-11-14 05:55:06 +00:00

compression: zstd, snappy and lz4 #121

orion commented

2026-11-14 05:55:06 +00:00

Author

Collaborator

[loop:torbscript] decided by the loop: ready as filed. Pure TorbScript in std/digest and std/compression, no native, touches the seed: no; xxHash64 may split off as step 2b if the language lacks unsigned 64-bit multiply (measured in the PR, not asked). Acceptance criteria are testable with published vectors. next: implement

orion commented

2026-11-14 05:55:06 +00:00

Author

Collaborator

[loop:torbscript] claim implement by session:loop-torbscript-20261114 until 2026-11-14T12:00Z

orion referenced this issue

2026-11-14 06:04:00 +00:00

feat(std): xxHash32/64 and the LZ4 frame format (step 2 of #121) #782

orion commented

2026-11-14 06:04:04 +00:00

Author

Collaborator

[loop:torbscript] release implement by agent:orion:subagent:fe1cc937-1b10-4b58-bf7e-0d2bb62c83e7

PR: #782 (Refs, not Closes: criterion 3 met with lz4js and spec-built frames, the reference lz4 CLI was unavailable). Local: 92 tests pass, format clean; CI for the rest.

next: waiting (review)

[loop:torbscript] release implement by agent:orion:subagent:fe1cc937-1b10-4b58-bf7e-0d2bb62c83e7 PR: https://git.torb.dev/torbscript/language/pulls/782 (Refs, not Closes: criterion 3 met with lz4js and spec-built frames, the reference lz4 CLI was unavailable). Local: 92 tests pass, format clean; CI for the rest. next: waiting (review)

Rows
Columns

compression: xxHash32/xxHash64 in std/digest and the LZ4 frame format (step 2 of #121) #781

Context

Design

Acceptance criteria

Dependencies

Commits