base85n
A Rust implementation of Base85N, an encoding for data that has to be embedded in a text-based format — JSON, XML, HTML, configuration files — where Base64 would otherwise be used and the size or the cleanliness of the result matters. It combines a dense 4-byte-to-5-character Base85 core with an adaptive Dynamic Passthrough (DP) mode — 1:1 efficiency and partially human-readable output on favourable input — and a Fill mode that carries a run of up to 2048 identical bytes in five characters, or a short zero run together with the two bytes beside it.
See the specification for the full normative text, in particular Section 4.2's donor profiles, Section 6's encoding procedure and Section 6.6's linear-time bound, which this crate follows exactly and exercises in its test suite.
It is also the implementation behind the Python bindings in
../python/, so the two cannot drift.
Usage
let data = b"hello, world!";
let encoded = encode;
let decoded = decode.unwrap;
assert_eq!;
API
;
;
;
encode_parallel returns exactly what encode returns — threads divides the
work and changes nothing about the result. The format allows that without a
chunk-size parameter because signals are self-describing and segment
boundaries are decided by the data, so encoders started at different offsets
converge and their output can be spliced; spec section 11.3 states the
procedure and the measured convergence distances that bound it. Inputs below a
couple of megabytes are encoded on the calling thread. On a four-core machine,
16 MiB of mixed input goes from 304 MB/s to 743 MB/s at four threads:
DecodeError implements std::error::Error and Display, with one variant
per error condition in the spec's Section 10: InvalidCharacter,
UnexpectedEndOfStream, UndefinedSignal (a group value in
FUTURE_SIGNAL_SPACE) and InvalidFinalBlock. DecodeError::code() returns
the shared error-code string the test vectors use, and position() the byte
offset where the condition names one.
The crate also re-exports the tables of Section 4 — ALPHABET_N, RSET_ASCII,
PROFILES — and the constants of Sections 6.4 and 9 under constants, so a
binding layer does not need a second copy of them.
Using it from C, and other languages
The crate also exports a C ABI, so anything with an FFI — C, C++, Python
(ctypes/cffi), Ruby, Zig, Java, Node, Lua — can link this implementation
instead of writing or vendoring its own. cargo build --release produces
target/release/libbase85n.so (.dylib/.dll) and target/release/libbase85n.a
next to the Rust library; the header is include/base85n.h.
char *encoded = NULL;
size_t len = 0;
if
/* ... */
;
The API is the C implementation's, deliberately: same three functions, same
status codes with the same numeric values, output buffers allocated with
malloc() and released by the caller with free(). The two libraries are
interchangeable — capi/run.sh compiles the same C program against both
headers and links it against this library, and CI runs it, so "drop-in" is a
checked claim.
This is the build to bind to. Everything below the three extern "C"
entry points is safe Rust, so decoding attacker-controlled input is
bounds-checked by the compiler rather than by review. That matters most for
exactly the callers who reach for a C library: see
SECURITY.md.
Two properties to know before you bind:
- A panic cannot unwind into your frames — an
extern "C"function aborts instead — and no panic is expected: encoding is total and decoding returns its errors as status codes. - Rust aborts on allocation failure inside the codec, where the C library
would return
BASE85N_ERR_ALLOC. That status is still returned when the caller-owned output buffer cannot be allocated.
src/ffi.rs is the only unsafe in the crate: the two pointer-validating
entry points, base85n_strerror, and one malloc-and-copy helper, each with
its safety argument stated at the site. The encoder and decoder themselves contain none.
Building and testing
Rust 1.88 or newer (rust-version in Cargo.toml): the decoder and block mode
use slice::as_chunks, which stabilised there. CI builds against that exact
version as well as stable and beta.
LICENSE and testvectors/ in this directory are symbolic links to the single
copies at the repository root; cargo package resolves them, so the tarball
carries the licence text and the golden vectors as real files and the test
suite above runs from an unpacked crate with no repository around it. CI does
exactly that on every push, which is what keeps "publishable" a checked claim
rather than an assumption.
The test suite:
- Loads and verifies every golden vector in
../testvectors/vectors.jsonfor bothencodeanddecode. - Runs randomized, fixed-seed round-trip property tests over a mix of arbitrary bytes, Alphabet-N literals, R-Set characters, donor characters and runs of identical bytes, across a wide range of input lengths -- including every donor paired with every R-Set character, which is what decides which profile can carry a run and where it has to break.
- Exercises explicit edge cases: empty input, partial-block boundary
lengths (1-4 bytes), the
MIN_PASSTHROUGH_BYTES(20) boundary, theMAX_DP_ANALYSIS_BYTES(2048) window boundary, the Fill thresholds and the 2048-byte Fill cap, transitions between all three modes, all 13 R-Set characters in one segment, and every byte value 0-255. - Feeds
decodedeliberately malformed input (invalid characters, truncated DP segments, values inFUTURE_SIGNAL_SPACE, the biased length fields' boundaries, non-canonical final blocks) and asserts it returnsErr, never panics -- and that a stream of Fill signals expands by no more than the ratio Section 13 states. - Calls the C entry points as a foreign caller would (
src/ffi.rs): round trips through them, null and zero-length arguments, non-UTF-8 input, and the rule that a rejected call leaves the caller's out-parameters untouched.capi/run.shthen repeats that from actual C, linked against the built static library, after checking that both headers declare exactly the functions the library exports. - Holds the encoder's decisions to the specification, which round trips do
not: spec section 12.3's requirement that skipping ahead emits exactly
what re-deciding emits (
tests::skipbuilds the second encoder out of the first and compares, over runs at every offset modulo four and the thresholds around each mode), section 12.1's structural assertions, and the four table invariants the encoder reads as facts -- each named at the place that consumes it, insrc/alphabet.rs. - Checks that each vectorised kernel answers what the scalar code it stands
in for answers (
src/simd.rs, with--features simd), and that the encoder's output never outgrows the buffer it sizes up front. - Guards the linear-time bound of section 6.6 with a timing check built to survive a busy machine -- and a second check that runs the same measurement against deliberately quadratic work, so that a guard which has stopped being able to fail fails.
Beyond the crate: c/fuzz/ runs the C and Rust implementations against each
other in one process, on generated input, comparing encoder output character
for character and decoder verdicts including the error code -- once for the
default build and once for the simd one. CI runs both, packages the crate
and runs its suite from the unpacked tarball, and builds against the declared
minimum toolchain.
And beyond CI, because they cost minutes to hours rather than seconds:
Miri over the unsafe at the C boundary with strict provenance, the suite
under AddressSanitizer, the parallel encoder under ThreadSanitizer,
cargo-deny over the build tree, and six coverage-guided fuzz targets --
rust/fuzz/ for the Rust API, including the parallel encoder's seams at a
chunk size a fuzz case can contain, and c/fuzz/ for the C implementation and
the two against each other. Anything not installed is reported and skipped
rather than failing the run.
How it compares to the C implementation
Both implementations follow the same specification and produce byte-identical
output -- 280,000 generated inputs are run through both and compared before any
speed number here is taken seriously (c/fuzz/). What differs is how fast they
produce it.
Throughput on 4 MB inputs, best of three interleaved rounds of twelve
(bench/throughput/run.sh), Intel Xeon at 2.1 GHz, gcc 13 -O2 against the
default release profile:
| input | encode | decode |
|---|---|---|
| random bytes | 0.87x C | 1.56x C |
| text | 1.04x C | 1.07x C |
| mixed | 1.12x C | 1.02x C |
Decoding -- the side that parses data your system did not produce -- is ahead of C throughout, by half again on high-entropy input. That is what matters for the recommendation in SECURITY.md to link this build rather than the C one from an FFI: the memory safety is not bought with decoder throughput.
Encoding is at parity, except on high-entropy binary, where C is about 15 %
ahead. Both encoders spend nearly all of their time deciding what mode to use
rather than writing output, and both are built around the same three ideas: a
fused classification table with a 64-bit "already accounted for" set that
retires every repeated character in one bit test, a block-mode skip that asks a
whole word whether eight bytes could begin a passthrough segment, and a
substitution table kept across segments rather than rebuilt. None of that needs
unsafe: the encoder and decoder in this crate contain none, and all of the
crate's unsafe is the three C-ABI entry points in src/ffi.rs.
Instruction counts are the wrong instrument here
bench/instructions/run.sh counts instructions under callgrind, which is
deterministic and reproduces on any machine where wall-clock numbers do not.
That makes it the right tool for comparing two specification versions, where
the difference is in what has to be computed. It is the wrong tool for this
encoder, and the 2026-08 optimisation pass shows why:
| random-byte encoding | instructions | throughput |
|---|---|---|
| before the pass | 3.42 M (1.74x C) | 261 MB/s (0.24x C) |
| with only the word gates in | 3.57 M (1.81x C) | 545 MB/s |
| after the pass | 2.21 M (1.12x C) | 948 MB/s (0.87x C) |
The middle row is the point. Asking a whole word whether eight bytes could begin a passthrough segment, instead of asking the table about one byte, added 4 % to the instruction count and made the encode 2.1 times faster. What it removed was a branch nothing could predict -- roughly a third of byte values are representable, so on binary that test is a coin flip resolved once per four bytes of the file. An instruction count charges nothing for a mispredict and full price for the arithmetic that avoids one.
Read bench/throughput for how fast the code is, and bench/instructions for
how much work it does.
Build-time options, measured
The library is written so that the compiler discharges its bounds checks rather
than emits them (see the module comment in src/decode.rs, and the padded
tables in src/digits.rs), which is what keeps it at the C implementation's
speed without any unsafe in the codec. Beyond that, the remaining levers are build settings -- and most of
them are the consumer's to set, since a [profile] in this crate does not
apply to a downstream binary.
Measured as instruction counts under callgrind on 200 kB inputs, against the default release profile:
| option | effect |
|---|---|
lto = "fat", codegen-units = 1 |
none (0 to -1 %). Everything hot is one crate and already inlines. |
| Profile-guided optimisation | 4-6 % better on text and mixed input, 4 % worse on random encoding. The gain is in branch layout, which is why it shows up where the mode decision is doing real work and not where the encoder is one straight line. |
-C target-cpu=native |
not measurable here -- it emits instructions valgrind cannot interpret. It is also a deployment choice, not a library one. |
One thing that sounds like it should help and does not: an assert! relating
the input and output lengths at the top of scan, as a hint, changes nothing --
the checks it would discharge are already gone.
Vectorising is a build setting too, and the one with the largest effect; it has a section of its own below.
A feature flag for more speed: simd
The crate is stable-only and portable by default. --features simd vectorises
the three per-byte loops the encoder spends its time in, and requires
nightly -- it is the only thing in the crate that does.
= { = "0.5", = ["simd"] }
# The whole recipe. All three parts are load-bearing; see below.
RUSTFLAGS="-C target-feature=+avx2" \
Encoding throughput against the default stable build, measured in the same
interleaved run so the ratios are the reading that travels between machines
(bench/throughput/run.sh, whose header carries the environment variables for
the second and third columns):
| input | simd, built as above |
simd, nightly alone |
|---|---|---|
| text of Alphabet-N characters only | 3.42x | 1.29x |
| text (this README, tiled) | 1.70x | 0.77x |
| mixed | 1.22x | 0.79x |
| random bytes | 1.09x | 1.09x |
Take the third column seriously. -Z build-std is not a refinement of the
recipe, it is part of it: without it the specialisation of swizzle_dyn stays
in precompiled core, built for baseline x86-64, and the shuffle the prefix
scan is built on compiles to a scalar fallback. The binary contains no pshufb
at all; nothing warns you, and the feature you turned on for speed costs you
almost a quarter of your text encoding. (The other two kernels use compile-time
shuffles and comparisons, which is why the last row survives that build.) If you
cannot build the standard library, do not turn this on.
What it vectorises
Three loops, in the order they were worth doing:
- The prefix scan's fast path. Sixteen bytes at a time, the scan asks "do
these change the state or open a run?" as a nibble-pair lookup -- the technique
simdjson uses -- against the same set of accounted-for classes the scalar loop
carries in a
u64. This is what encoding text is mostly made of. - The substitution of section 4.3. The table the scalar loop reads is the
identity with the segment's
kdonors patched in, andkis one to three on ordinary text, because a segment spends a donor per distinct R-Set character. So it is not a table to vectorise but a handful of "replace this byte with that one": a comparison and a blend each, sixteen bytes at a time. On a segment of only Alphabet-N characters this is most of the remaining work. - The block-mode skip of section 11.1. Eight groups settled per vector against two per word: the two Fill gates are collected by one shuffle each and stay exact, and the passthrough gate becomes "are eight bytes in range from this group start", folded out of the in-range bits of all forty bytes in three shifts. This is the one that moves binary input, where the skip is 39 % of the encode.
Why it cannot change the output
Each of the three answers a question, never a decision.
The scan's step returns a count of bytes it has proved the scalar loop would walk past without doing anything; the scalar loop then handles the byte that stopped it and everything after. The skip's window may only fail to rule a group out -- the exact per-group tests decide behind it, unchanged. And the substitution is the same mapping the table holds, applied by comparison instead of by lookup.
So a wrong "keep going" is not expressible in the first two, and the third is
checked against the table it replaces. All of it is checked rather than argued:
the crate's own suite runs unchanged under the feature and adds contract tests
for each kernel against the scalar predicate it stands in for, the section 12.3
skip differential runs in this build too, and the differential harness in
c/fuzz/ was run against the C implementation with the feature on -- 200,000
generated inputs, byte-identical output.
What is not vectorised
The Base85 conversion in block mode, which is what random binary spends its remaining time on: five digits per four bytes needs division by 85 in lanes and a shuffle to pack five-byte groups, and it is a project rather than a kernel. Nothing for the decoder, which is already ahead of the C implementation.
Threads and vectors multiply
They are independent: encode_parallel runs the same encoder on each chunk, so
the feature applies inside every worker. Measured on text, 16 MiB, same machine:
| 1 thread | 2 threads | 4 threads | |
|---|---|---|---|
| stable | 240 MB/s | 355 MB/s | 628 MB/s |
simd |
402 MB/s | 513 MB/s | 893 MB/s |
| 1.68x | 1.44x | 1.42x |
Threads alone buy 2.6x on four cores, the feature 1.7x on one, and together 3.7x. The vector gain narrows as threads are added, which is what a workload approaching memory bandwidth looks like.
What does not work, since it is the obvious next thought: running several encoders in lanes and splicing their output the way threads do. The splice works for threads because each one runs the whole branchy encoder independently and the format lets outputs be joined; lanes cannot, because they execute one instruction between them. Two lanes in different modes, with different segment lengths and different amounts of output, are not a vector operation -- they are eight state machines wearing one. What vectorises is the work inside one encoder's phases, which is what the three kernels above are.
Versioning
The major and minor version track the specification version this crate
implements — 0.5.x implements specification v0.5.0, whose wire format is
frozen. The patch level is this crate's own: packaging, provenance and
documentation changes that alter no encoded output. Anything that would change
the wire format would change the specification's version first.
Provenance
Every .crate published from this repository is uploaded by
.github/workflows/release.yml, never from
anyone's machine, and carries a Sigstore-signed
SLSA build provenance attestation — a
statement that this repository, this workflow and one particular commit
produced exactly those bytes. It is keyless: no signing key exists for longer
than the job that made it, and there is no public key to fetch.
crates.io has no signature mechanism of its own, so the attestation lives in
this repository's attestation store. That still lets you check the file cargo
downloaded, because cargo publish re-packages deterministically and the
checksum the workflow logs before uploading is the one crates.io records:
Each release also appears under Releases, with that exact file, its checksum, and a tag at the commit it was built from.