triepack v2.0.0

A compressed trie-based dictionary format for fast, compact key-value storage.

TriePack encodes dictionaries into a compact binary format (.trp) optimized for fast lookups, prefix search, and ROM-safe deployment. It uses prefix sharing and bit-level packing with configurable symbol encoding and full value type support.

Features

• Compact binary format — compressed tries with prefix sharing and bit-level packing
• Fast lookups — O(key-length) point queries via skip pointers
• Prefix search — iterate all keys matching a prefix, by descending the trie
• ROM-safe — readers work directly on const buffers with zero allocation
• Typed values — null, bool, int, uint, float32, float64, string, blob
• Same bytes everywhere — every implementation encodes identically, checked by a conformance suite all ten run
• JSON support — encode/decode JSON documents to/from .trp format
• 10 languages — C core with native implementations across 9 additional languages
• Small footprint — trie codec and bitstream are 49 KB of static library (Release, 64-bit); bindings are 934-1,796 source lines each

Supported Languages

All bindings are native implementations that read/write the .trp binary format directly (no FFI).

Language	Type	Source Lines	Binary/Library Size	Notes
C	Core library	5,387	49 KB (codec + bitstream), 72 KB with JSON	C99, 32-bit and 64-bit, ROM-safe
C++	Wrapper	1,113	37 KB (static)	C++11 RAII, owning Value, iteration and prefix search
Python	Binding	934	pure source	No dependencies
JavaScript	Binding	1,134	pure source	Node.js and browser, ships type declarations
TypeScript	Binding	49	pure source	In-repo wrapper; published types come with the npm package
Go	Binding	1,307	pure source	No dependencies
Rust	Binding	1,796	pure source	No dependencies, no unsafe
Swift	Binding	1,156	pure source	SPM package
Kotlin	Binding	1,150	pure source	Kotlin/JVM, Gradle
Java	Binding	1,585	pure source	Java 11+, Gradle

Static library sizes are a Release build; the archives above are the trie codec plus bitstream, and the figure with JSON adds triepack_json.

Quick Start

C / C++

# Install
git clone https://github.com/deftio/triepack.git
cd triepack
cmake -B build -DBUILD_TESTS=ON -DBUILD_JSON=ON
cmake --build build
ctest --test-dir build --output-on-failure

#include "triepack/triepack.h"

tp_encoder *enc = NULL;
tp_encoder_create(&enc);
tp_value v = tp_value_int(42);
tp_encoder_add(enc, "hello", &v);
uint8_t *buf = NULL;  size_t len = 0;
tp_encoder_build(enc, &buf, &len);

tp_dict *dict = NULL;
tp_dict_open(&dict, buf, len);
tp_value val;
if (tp_dict_lookup(dict, "hello", &val) == TP_OK)
    printf("hello -> %lld\n", (long long)val.data.int_val);
tp_dict_close(&dict);
tp_encoder_destroy(&enc);
free(buf);

Python

pip install triepack

from triepack import encode, decode

buf = encode({"hello": 42, "world": "foo"})
result = decode(buf)
print(result)  # {'hello': 42, 'world': 'foo'}

JavaScript

npm install triepack

const { encode, decode } = require('triepack');

const buf = encode({ hello: 42, world: 'foo' });
const result = decode(buf);
console.log(result);  // { hello: 42, world: 'foo' }

TypeScript

The npm package ships its own type declarations, so there is nothing extra to install:

npm install triepack

import { encode, decode, TriePackData } from 'triepack';

const data: TriePackData = { hello: 42, world: 'foo' };
const buf: Uint8Array = encode(data);
const result: TriePackData = decode(buf);

Go

# The module lives in bindings/go; vendor it or add a replace directive:
# replace github.com/deftio/triepack => ./path/to/triepack/bindings/go

data := map[string]interface{}{"hello": uint64(42), "world": "foo"}
buf, _ := triepack.Encode(data)
result, _ := triepack.Decode(buf)

Rust

# Not on crates.io yet; add from source:
# [dependencies]
# triepack = { path = "bindings/rust" }

use triepack::{encode, decode, Value};
use std::collections::HashMap;

let mut data = HashMap::new();
data.insert("hello".into(), Value::UInt(42));
let buf = encode(&data);          // infallible for String keys
let result = decode(&buf)?;

Swift

# Add to Package.swift dependencies
# .package(path: "bindings/swift")

import Triepack

let data: [String: TriepackValue] = ["hello": .uint(42)]
let buf = try Triepack.encode(data)
let result = try Triepack.decode(buf)

Kotlin

# Add bindings/kotlin/ to your Gradle project
cd bindings/kotlin
gradle test

import com.deftio.triepack.*

val data = mapOf("hello" to TpValue.UInt(42))
val buf = encode(data)
val result = decode(buf)

Java

# Add bindings/java/ to your Gradle project
cd bindings/java
gradle test

import com.deftio.triepack.*;

Map<String, TpValue> data = new LinkedHashMap<>();
data.put("hello", TpValue.ofUInt(42));
byte[] buf = TriePack.encode(data);
Map<String, TpValue> result = TriePack.decode(buf);

Asking a build what it is

Every implementation reports the same metadata, so a polyglot system can ask each one and compare:

require('triepack').version()
// { name: 'triepack', implementation: 'javascript', version: '2.0.0',
//   versionMajor: 2, versionMinor: 0, versionPatch: 0,
//   formatVersionMajor: 1, formatVersionMinor: 0, maxAlphabetSize: 249 }

The same call is tp_version() in C, triepack::version() in C++, version() in Python, Rust and Kotlin, VersionMetadata() in Go, Triepack.versionInfo() in Swift and TriePack.version() in Java. The library version comes from triepack-version.txt at build time; the format version is separate and moves only when the bytes change.

Iterating and prefix search (C and C++)

tp_iterator *it = NULL;
tp_dict_find_prefix(dict, "app", &it);      /* descends, does not scan */

const char *key; size_t key_len; tp_value val;
while (tp_iter_next(it, &key, &key_len, &val) == TP_OK)
    printf("%.*s\n", (int)key_len, key);
tp_iter_destroy(&it);

Keys come out in lexicographic byte order. The bindings decode to a native map instead, so they iterate with whatever their language already provides.

See Examples for more detailed usage including JSON round-trips, file I/O, and cross-language interop.

Library Stack

triepack_json          (JSON encode/decode)
    |
triepack_core          (trie codec: encoder, dictionary, iterator)
    |
triepack_bitstream     (bit-level I/O, VarInt, UTF-8)

Each layer can be used independently. triepack_wrapper provides C++11 RAII wrappers over all three.

Build Options

Option	Default	Description
BUILD_TESTS	ON	Build test suite
BUILD_EXAMPLES	ON	Build example programs
BUILD_JSON	ON	Build JSON library
BUILD_DOCS	OFF	Build Doxygen documentation
ENABLE_COVERAGE	OFF	Enable code coverage instrumentation
ENABLE_SANITIZERS	OFF	Build with AddressSanitizer and UndefinedBehaviorSanitizer

File Format

• Magic bytes: TRP\0 (0x54 0x52 0x50 0x00)
• File extension: .trp
• 32-byte fixed header
• Bit-packed prefix trie, with the value store following it
• CRC-32 integrity check over the whole buffer

A valid checksum means the buffer is intact, not that it is trustworthy — anyone who can supply a buffer can supply a matching CRC.

See docs/internals/ for format details.

Documentation

• Getting Started
• Building
• API Reference
• Examples
• Testing
• Release Process

Project Status

v2.0.0. Core C library (bitstream, trie codec, JSON), C++ wrapper, and 8 language bindings (Python, JavaScript, TypeScript, Go, Rust, Swift, Kotlin, Java) are implemented. CI enforces floors of 97% lines and 80% branches on the C library, and runs the whole suite under AddressSanitizer and UndefinedBehaviorSanitizer — the leak half only exists on Linux, and it is what caught the leak fixed in 1.3.2.

What is not implemented is listed in Status, which exists because that gap was once large and undocumented. Read it before relying on anything a header names.

All ten implementations run a shared conformance suite: for each of 50 cases every one must decode the same C-generated fixture to the same values and re-encode it byte for byte, and reject the same 11 malformed buffers. About 1,600 tests in total.

scripts/make-release.sh --check builds and tests all ten targets locally; scripts/test-ci-linux.sh runs the ubuntu-only jobs in a container.

Roadmap

v1.1 — Client Libraries

• TypeScript binding (wraps JS implementation)
• Go binding
• Swift binding (with SPM package)
• Rust binding
• Kotlin binding
• Java binding
• npm package for JavaScript/TypeScript (ships bundled type declarations)
• PyPI package for Python
• crates.io package for Rust

Format v2 — the next format, not a v1 extension

The 249-symbol alphabet limit, the absent suffix table and the O(n) value lookup are not things v1 can be patched into. They are the subject of format v2, which breaks the header:

• LOUDS-encoded trie with rank/select — no alphabet limit, O(1) value lookup
• Suffix-merged tail pool (shared endings)
• 1 GB+ inputs within a bounded memory budget
• Bit vector, rank/select and tail pool libraries, with a measurement prototype

See the implementation plan for sequencing across ten implementations.

v1.3 — Tooling & Ecosystem

• trp CLI: encode/decode/validate/inspect
• Language binding conformance test suite
• Trie iteration and prefix search
• Fuzzy search (edit distance d<=2) — declared, returns TP_ERR_UNSUPPORTED
• Performance benchmarks across languages

Contributing

Bug reports and pull requests are welcome. See CONTRIBUTING.md for how to build and test each target, and for what a change to the binary format has to satisfy — every implementation has to agree byte for byte, which the conformance suite checks.

Participation is covered by the Code of Conduct. Security issues go through SECURITY.md rather than the public tracker.

Releases are cut with ./scripts/make-release.sh; see RELEASE.md.

terseml — a subproject, not a feature

terseml/ is a separate thing that lives in this repository: a positional encoding for tag / attribute / content trees (.tsml), with a formal grammar and implementations in C, Python and JavaScript.

It links nothing from TriePack and TriePack links nothing from it. It is not published to any registry. TriePack stores a dictionary; terseml carries a tree; they do not pipe into each other. See the terseml page for what it is and how to build it.

License

BSD-2-Clause. See LICENSE.txt.

Copyright (c) 2026 M. A. Chatterjee