Skip to content

Becoming a varint hater (who's compliment? zigzag??)

what if STAR used signed varints for length prefixes, so that -1 could be an end-of-archive signal?

fig (aka:[phil])
Oct 29, 20263 min read
2
2

his is about Option 3 for STAR to be able to detect archive truncation at the format level --

Should STAR detect early truncation? - Data service diaries

Weird varints? Control bytes?? And we are not too preoccupied to stop and ask whether or not we should.

I came here to find out if there was consistency in how signed varints are implemented across common implementations. I'm leaving depressed.

languageobvious choicestdlib?signed support?strict?
javascriptvarintthird-partynono
golangencoding/binarystdlibzigzag (implicit)no
rustinteger-encodingthird-partyzigzagno
pythonleb128,
varint
third-partytwo's compliment,
unsigned only
no, and both are buggy
zigstd.leb (is a trap),
std.Io.Reader.takeLeb128 / std.Io.Writer.writeLeb128
stdlibtwo's complimentstd.leb writes non-minimal(!)

Io readers: no

I don't think we can use signed varints, at least not if the choice is meant to build on common stdlib/library implementations: support is limited and even the encoding is inconsistent. If we still wanted negative length prefixes as a signal, i think there would be a reasonable case to pick bijoux over signed varints.

Wait, nothing is strict??

How about some atproto/DASL libraries:

Librarylanguagestrict?
Bluesky CAR readertypescriptno
Bluesky carutilI think this was another carutil regression -- go-varint is still a dependency, and it is strict, but unused in indigo now.golangno (stdlib)
iroh-carrustno (integer-encoding)
@atcute/varinttypescriptno

ZERO FOR NINE. eesh. calling it here.

I am, maybe unfortunately, becoming more and more tempted to use 0x8000 as an archive-terminating varint: it's a one-byte-extended varint for 0: not minimal, so not valid as a real 0 length prefix. It will probably force ~all implementations to add minimal-encoding checks to their varint parsers to work with STAR, which sucks for them but... might be good for the world? Or maybe it would just suck.

Update (2026-11-02): a very boring key length prefix shift

The plan is to settle Q3 with a variation on Option 3. No signed varints, but tentatively keeping unsigned varints. It will look like this: https://microcosm.tngl.io/star/spec-edits/shifted-key-len.html

If you want to fight for bijou64 instead of varint, now is the time.


Fun fact:

Some applications actually use trailing zero bytes (basically redundant leading zeros in the number) to encode LEB128 varints in a fixed-width form. Which defeats the whole point of varint space saving! but it lets you replace a number in the middle of a binary blob later with any other number, since its width is fixed: the new number will be the same fixed width size. So, evil-but-handy if your format requires LEB128, you need to be able to swap out numbers, and all your readers are not strict. Zig's comment about it: https://github.com/ziglang/zig/blob/master/lib/std/leb128.zig#L5-L14

(this is not desirable for STAR, which can almost claim to be a deterministic encoding, if strict varint can be a thing at all...)

Did you enjoy this article?

Recommend it — Standard Reader surfaces well-loved writing to more readers across the network.

Across the AtmosphereDiscussions