Bijou64: A variable-length integer encoding

But testing proved that when you move to SIMD instructions, ULEB128 (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#ty...) or sentinel values (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#lo...) win every time because of the parallelization opportunities.

The true irony is that even SIMD text parsing would outperform this! SIMD is that powerful.

The problem is linking: a compiler needs to emit code into independent translation units, which contain "missing" references to symbols in other translation units, without yet knowing where all the code will end up in the final executable. Since we don't know where the location of other code is yet, we don't know how big the number representing that location is yet, which means that we don't know how wide the variable length encoding of that number will be. If the width changes after linking, then we have to push around the surrounding code to make space for the wider integer. Unfortunately, this changes the location of all the surrounding code, so we have to recompute all the references!

The solution is to always emit un-linked var ints in the widest possible encoding (5 bytes for LEB128) that way when the references are patched during linking, no code is moved around. All integers can be converted to a non-canonical 5 byte form that is "wasteful" but its a worthwhile tradeoff because it solves this issue. Other integers that don't need to be linked can be packed in a smaller var int form to save space.

EDIT: BUT, BER-TLV does permit overlong encodings. And I once found and reported a Yubikey 4 bug related to this. My source code comment for the workaround:

  -- The Yubikey 4 has an off-by-one bug which
  -- declares tag length of 255 (for the 0x53 outer
  -- tag of a certficate DO) when there are only 254
  -- bytes remaining in the reply. The reply is
  -- chained across two packets, but the off-by-one is
  -- probably related to the over-long encoded length
  -- (0x82 0x00 0xff instead of 0x81 0xff).
  --
  -- [snip packet captures]
  --
  -- Yubico's ykpiv_fetch_object function in ykpiv.c
  -- (confirmed 1.4.3-1.5.0) contains a read (memmove)
  -- overflow when the declared inner BER-TLV length
  -- (of the 0x53 tag) is longer than what was
  -- received over the wire. That makes Yubico's
  -- library oblivious to the issue. Relatedly, the
  -- set_length function has an off-by-one bug (length
  -- < 0xff instead of length <= 0xff) which produces
  -- an over-long encoded length. That doesn't by
  -- itself explain why the Yubikey 4 transmits a
  -- truncated logical reply unless the same code is
  -- being used.

The downside is the encoding size. LEB128 quickly grows to 2 bytes, but stays at 2 bytes all the way to 2^14. This is important if you're using these numbers as tags/identifiers as we were in the multicodec [1] project, or for network message lengths. bijou64 only gives you 500 <= 2 byte numbers.

[1]: https://github.com/multiformats/multicodec

This looks neat, but if encoding/decoding performance is important, payload size isn't and the integer is bounded, I would just put a fixed-size integer into the payload as-is.

LEB128 (and JSON for that matter) can encode integer values of arbitrary length. This doesn't, which may or may not be important but it's different.

I'll admit that I do not do any cryptographic work with my library and therefore canonical representations aren't a huge concern in my use-cases. I merely provide various configurable limits (max value length, max depth, max items per collection) in an effort to prevent infinitely long documents from hogging my tokenizers indefinitely.

https://news.ycombinator.com/item?id=44456073 - Corrected UTF-8 (2025-07-03, 54 comments)

This "corrected UTF-8" has other problems, but I thought it's interesting how the shifted-offset idea carries over.

Values 0-127 are a single byte, but if that first byte has the continuation bit set, not only does that indicate the next byte has 7 more bits to contribute, it also moves the base up to the next window.

10000000 00000000 is the only way to represent 128.

10000000 10000000 00000000 is the only way to represent 16512.

Does this encoding have a name?

vu128: https://john-millikin.com/vu128-efficient-variable-length-in...

metric/imperial varint: https://dcreager.net/2021/03/a-better-varint/

vectorizing VByte: https://arxiv.org/abs/1503.07387

[0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki

An adveserial package can claim to have a 255 tagged integer but not actually have any followup, tricking the payload parser into an incorrect offset and reading straight off into followup memory.

It's a classic thing to check for when dealing with variable length strings or binary, but it may not cross the mind when it's hiding in the Bijou64_decode(*buff, *cr) function.

The upsides: the size of the integer is apparent upon reading the first byte, and every number has exactly one canonical representation. I wish C strings had been standardized around something similar, instead on null termination.

> ...adversarial input, which is rarely in the test suite.

This made my scratch my head. My tests for quite pedestrian APIs often contain adversarial input of obvious shapes. I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part.

Forgetting to do the range check on the first_byte==255 case and just letting it do 64-bit wraparound is exactly as much of a plausible bug as missing range checks on LEB128. Any test suite with the goal of covering canonicality will trivially cover both properly; and a programmer that implements things by reading 7 words into the spec, saying "oh yeah I got this" and goes to implement what seems simple, will write a broken version of both.

Perhaps the biggest benefit is just not being associated with a format that tolerates non-canonicality in other places (though, if bijou64 gains traction, it'll only be a matter of time for wraparound-check-less versions to start appearing in places where the wraparound is fine); and I guess also it being less annoying to implement the canonicality check, though hopefully people writing security-sensitive software aren't ones to skip out on correctness checks due to annoyingness.

In a sense, bijou64 could perhaps even be more problematic - it invites not doing any range checks for the smaller inputs because they obviously don't need it, and so you can just forget to special-case the max length case; whereas LEB128 makes you already care about it at the first point it is actually LEB128.

(of course, the format does still have other benefits; enforced canonicality is just...not one of them)

For example you can use a denormalized zero to signal null.

You can still define a canonical encoding where denormalizations have specific meaning or signal an error.

Why not little endian like modern CPUs?

Given that the context up to this point had been representation of integers, I initially trip on this. :)

> This causes problems for signed data if you ever want to do things like compression since you need to know the exact bytes that were signed.

If you are verifying a signature by taking some logical data structure, turning it into a byte string, and calling the verification primitive on those bytes, you likely have a design error. You should instead collect bytes, verify the signature, and then parse the bytes after verifying the signature. And remember to include enough context in those bytes so a different message signed for a different purpose by the same key doesn’t confuse you.

Here's two passing tests for software craftmanship:

1) it looks decades into the past 2) it looks decades into the future