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?
This is about Option 3 for STAR to be able to detect archive truncation at the format level --
I came here to find out if there was consistency in how signed varints are implemented across common implementations. I'm leaving depressed.
language | obvious choice | stdlib? | signed support? | strict? |
|---|---|---|---|---|
javascript | third-party | no | no | |
golang | stdlib | zigzag (implicit) | no | |
rust | third-party | zigzag | no | |
python | third-party | two's compliment, unsigned only | no, and both are buggy | |
zig | std.leb (is a trap), std.Io.Reader.takeLeb128 / std.Io.Writer.writeLeb128 | stdlib | two's compliment | std.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:
Library | language | strict? |
|---|---|---|
typescript | no | |
I think this was another carutil regression -- go-varint is still a dependency, and it is strict, but unused in indigo now. | golang | no (stdlib) |
rust | no (integer-encoding) | |
typescript | no |
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.
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...)