astral-sh / astral-sh/tar-codec

Chapter-aware encoding/decoding

Open
#105 1 comment 0 reactions 0 assignees View on GitHub
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.