astral-sh / astral-sh/tar-codec
Chapter-aware encoding/decoding
- Dominant language
- Rust
- Stars
- 9
- Forks
- 3
- Avg merge
- 9m
- Merged PRs (30d)
- 3
Description
This is a very cool trick: https://github.com/dtolnay/chapter-tgz
The TL;DR is that it makes a single DEFLATE stream behave like a collection of independently decompressible streams. Regions of the larger stream can be segmented into "chapters," each of which can contain one or more tar members (or technically anything, but tar is what matters for our purpose). The DEFLATE dictionary is reset at each chapter boundary so that decompression doesn't depend on earlier stream state.
Each chapter boundary is encoded as a valid Huffman tree description for a DEFLATE block that otherwise decompresses to nothing. A normal DEFLATE decompressor will effectively continue over the empty decompression, while a chapter-aware decoder can extract a distance back to the previous chapter boundary (earlier) in the stream, continuing until gzip header/stream start. So you get a one-time `O(n)` index step (for `n` chapters) and then `O(1)` chapter access afterwards.
The two nuances to this are:
1. Each chapter has its own dictionary, so compression is slightly pessimized. This probably doesn't matter much in practice; it's similar to per-file compression in ZIP (but potentially a lot better, since chapters can potentially span many files).
2. The performance advantage from chapters largely derives from being able to seek backwards to build the chapter boundary index/resume directly at an offset within the stream, plus being able to decompress multiple chapters in parallel if desired. If an I/O source doesn't support those (efficiently), raw throughput _can_ be faster depending on the stream's size.
`tar-codec` itself has no opinion about the compression layer, but it would be *extremely cool* if we could expose APIs that make it ergonomic to do chaptering with `tar-codec`. `chapter-tgz` uses the `tar` crate because it's more flexible around trailing markers than we are, but we could pretty easily expose some kind of `TarTerminator` stream adapter that just inserts `[0; 1024]` at the end of each chapter body.
Contributor guide
Research direction
Start by reading the chapter-tgz example and the tar-codec encoder/decoder APIs to understand how chapter boundaries and trailing markers are handled. Define what a TarTerminator stream adapter and chapter-oriented APIs would need to expose, with ergonomic chaptering and compatible tar output as the completion criteria.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- tooling
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Quiet
- Clarity
- Needs clarification
- Newbie friendliness
- 35/100