TriePack North Star

0. What this document is, and is not

Provenance matters here, so it is stated first.

This file was generated by Claude on 2026-09-18 and rewritten on 2026-09-20. It is not an original design document and does not record decisions made before the implementation existed. The only pre-implementation material in this repository is plan/txz-spec.md and dev/ (committed 2026-02-26), and the author has since described those notes as “original but not hardened — meant to start a conversation.”

An earlier revision of this file was quoted back to the author as though it recorded his intent. It did not. Everything in §1 below is now the author’s own words; everything after is marked [decided] or [proposed], and a proposal carries no authority until the author says otherwise.

For what is actually built — measured, with evidence — see What is actually built. That document quotes no other document.

1. The intent, in the author’s words

“TriePack was supposed to be a well designed bit aligned trie with skips and support for suffix tries and arbitrary (binary or ascii or utf8) sortable keys and values. Clever use of tries and bits was meant to make them compact and ROMmable (read in place).”

— M. A. Chatterjee, 2026-09-20

That sentence is the specification this project is measured against. It predates and outranks every generated document here, including this one.

2. Where the implementation stands against it

Nine claims in that sentence. Measured against the code (§evidence in What is actually built):

Claim State
Bit-aligned trie built
Skips built
Sortable keys (lexicographic iteration, prefix search) built
ROMmable — allocation-free lookup built
Typed values built, but O(n) to resolve
Compact keys-only 0.627 of raw; worse than input once values are added
UTF-8 keys works incidentally (it is bytes); the declared UTF-8 mode does not exist
Suffix tries not built — src/core/suffix.c is 14 lines ending in /* TODO */
Arbitrary binary keys not built — 249 distinct byte values maximum; 250 is refused

Five as intended, two partly, two not.

The two that are missing are the two that distinguish this from an ordinary prefix trie, and they share one cause. SUFFIX and ESCAPE occupy two of six control codes; those six are exactly what reduces the alphabet from 255 to 249. The format pays rent on suffix sharing it never received, and binary keys are the tenant that was evicted to pay it.

ESCAPE is not merely unbuilt — it is unreachable by construction. Control codes occupy 0–5 and the alphabet starts at 6, so a data byte can never collide with a control code and escaping can never be needed.

3. This is a do-over, not a patch [decided]

The gap in §2 is not a backlog. Suffix sharing, binary-safe keys and O(1) value access cannot be added to the shipped format:

Each is a format break. Taken together they are a redesign, and treating them as one redesign rather than three breaks is the cheaper path.

TriePack 2.0.0 (released) is a library version, not this redesign. It writes format v1 unchanged. The redesign is format v2 and has not shipped.

4. What TriePack is [decided]

A static, immutable, byte-identical file format for byte-string-keyed dictionaries with typed values, readable directly from ROM by independent implementations in many languages.

4.1 Multiple implementations are a design filter, not a cost

The ten current implementations average ~1,300 lines each, and they are that small because the format is small. That relationship is the whole strategy: if a feature is hard to implement ten times, the format is telling you it is too complicated, and design time is the only moment that feedback is cheap.

A wire-format bug in a sibling project in this repository survived 3,000 randomised round-trips in each of two implementations independently, because each decoded its own output the way it had encoded it. It surfaced in minutes once one implementation’s bytes met another’s parser. Independent implementations are the mechanism that finds that class of bug; nothing else does.

The goal is the JSON position: a specification precise enough that someone who has never read this codebase can write implementation number eleven and have it produce identical bytes. That is not true today, and §6.4 is the fix.

5. What we optimise, in order [proposed]

When two conflict, the earlier wins.

  1. Size on disk / in flash. A dictionary that does not fit is not slow, it is absent.
  2. ROM-ability. Readable in place with no RAM copy, no allocation, no load-time work.
  3. Cross-implementation byte-identity. Non-negotiable; listed third because it constrains how 1 and 2 are achieved rather than competing with them.
  4. Lookup speed. Fast enough that size is what you notice. Trade constant factors for bytes; never trade asymptotics.
  5. Implementation simplicity. See §4.1 — implementations as a design filter.

6. Design rules

6.1 Global optimisation is legal [decided — author’s words]

“Global optimization is legal in TriePack.” — M. A. Chatterjee

The encoder may examine the entire input before emitting a byte. Whole-corpus analysis, multi-pass layout, suffix deduplication, optimal-ish packing — all permitted, all encouraged. The encoder may be slow, subject to §6.11.

The decoder may not. That asymmetry is the deal: push every cost to build time, because build happens once on a workstation and read happens forever on something small.

6.2 Every optimisation must be an algorithm, not a goal [decided]

This is the rule v1 lacked and the one byte-identity depends on.

“The encoder deduplicates common suffixes” is a goal, and ten implementations pursuing a goal produce ten different files. “The encoder deduplicates suffixes by the exact procedure in §N, processing tails in the specified order, ties broken as specified” is an algorithm, and ten implementations of an algorithm produce one file.

Any optimisation admitted to the format must be pinned down to where two competent implementers cannot disagree about the output. If it cannot be, it does not belong in the format — it belongs in a build-time tool that emits a conforming file.

6.3 The file is the data structure [decided]

No load-time fixups, no pointer swizzling, no “parse into a runtime representation”. Offsets are file-relative so the blob is position independent; a reader adds its base pointer and walks. Acceleration structures a runtime would normally build — rank indices in particular — are precomputed by the encoder and stored in the file, because build time is free and load time is not.

6.4 The specification is the authority [proposed]

The format is defined by a written decoder grammar. Implementations conform to it; it does not describe them. Where an implementation and the grammar disagree, the implementation is wrong — including the C one.

The conformance corpus is generated from the grammar, not from any implementation. Every implementation is tested against bytes produced by a different implementation; self-round-trip is necessary and not sufficient.

6.5 The container is TLV [decided]

Required. The file is magic, version, then type-length-value chunks:

file  =  magic  version  chunk*  crc
chunk =  type:varint  flags:u(8)  length:varint  payload  align(4)

A fixed header means every future feature is a format break, and that is not hypothetical: v1 reserved has_suffix_table, has_nested_dicts and compact_mode as header bits and all three are still unbuilt, because there was no way to add the machinery incrementally.

TLV also makes §6.9 affordable — you need not reserve space when you can add a chunk.

A MUST_UNDERSTAND flag bit governs version evolution only: a later minor version marks a chunk must-understand when ignoring it would silently change meaning, and clears it when the chunk is a pure accelerator. Within one version there are no optional chunks (§6.10).

6.6 Nothing is padded because bytes exist [decided]

The lineage is dio_BitFile (2000): PutNBitQty(stream, value, n_bits) — arbitrary widths are the native unit, not an optimisation.

Every count, length and offset is a varint or has its width declared by a field appearing earlier in the stream. No format constant is a number the reader is expected to already know.

v1 honoured this for trie symbols and broke it in the header with a fixed 8-bit symbol_count. That one hardcoded width is the 249 limit. The same rule retires the 512 MB ceiling and the depth-256 cap.

Corollary: derive rather than declare wherever a value is a function of something already present. A declared width that can contradict its own data is a malformed state to detect; a derived one cannot be represented.

6.7 Alignment is a property of access [proposed]

Data randomly accessed as machine words is aligned — rank tables, bit vectors — because a Cortex-M0 cannot do unaligned word access. Data parsed sequentially is bit-packed. A reader parses a few varints at open and then does aligned access forever.

6.8 Structure and labels never share a code space [decided]

v1 put control codes and alphabet symbols in one space sized by one 8-bit field, so structural vocabulary stole from data vocabulary. Separate them and there is nothing to run out of: no alphabet limit, no symbol table, no escape mechanism, and all 256 byte values legal in keys.

6.9 Reserve nothing you are not building [decided]

v1’s reserved control codes are why this document exists. A future feature takes a new chunk type when it arrives. Reserved bits must be zero and readers must reject non-zero, so the space stays genuinely recoverable rather than accidentally load-bearing.

6.10 One format, not a family of profiles [proposed]

Every conforming reader implements everything. A file that only some readers can open destroys the property the project exists for. A feature may be unused in a file — its chunk absent — but “absent” is not “optional to implement.”

Small embedded readers are served by keeping the format small, not by fragmenting it. Testable version: a complete reader — open, validate, lookup, iterate — under ~1,500 lines in a typical language.

6.11 The encoder has a memory budget [proposed]

An encoder must build within ≤ 8× the input size in peak resident memory, tested at 1 GB. “Embedded-grade” applied only to the reader in the original notes and nothing constrained the encoder: the current v2 prototype measures ~87× linearly (420 MB for 5 MB, 1,654 MB for 20 MB), extrapolating to ~87 GB for 1 GB. That is a build strategy, not the format, but unstated budgets do not get met.

7. What we explicitly do not do [decided]

8. How we will know the redesign worked

Measured against what ships today, on tests/data/common_words_10k.txt and tests/data/benchmark_100k.json:

Property today target
Distinct byte values in keys 249 (250 refused) 256
Suffix sharing absent required
Value resolution O(n) — 30,500 µs at 699k keys O(1) by rank, not a stored index
Keys+values vs raw input larger than input smaller
Container fixed 32-byte header TLV
Load-time work none none
Allocation to open one struct zero
Encoder peak memory ~87× input ≤ 8×
Outside implementation possible from the spec alone no yes

The last row is the one that matters most and is the easiest to skip.

9. Open questions

  1. Value sharing. Flat store, suffix-shared store, or the second trie the original notes specified. Values today have no sharing at all, which is why JSON does badly — 99.8% of enwik9-as-JSON was value store. A concatenation experiment beat a value dictionary (70,665 vs 84,166 bytes) because tries share suffixes while dictionaries dedupe only exact matches. Suffix-shared store has never been measured. Measure before specifying.
  2. Huffman labels. Size ranks first in §5 and simplicity last, so this trade is genuinely open. Measure before deciding.
  3. §6.7 against ROM alignment. If section contents must be 4-byte aligned rather than just word-addressed tables, §6.6 needs rewriting.