> This causes problems for signed data
Given that the context up to this point had been representation of integers, I initially trip on this. :)
Bijou64: A variable-length integer encoding
61–70 of 93 posts
Re: Bijou64: A variable-length integer encoding
#62This is pretty close to SQLite's varints [0] [0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki
I believe SQLite3 uses a somewhat different implementation:
> A variable-length integer or "varint" is a static Huffman encoding of 64-bit twos-complement integers that uses less space for small positive values. A varint is between 1 and 9 bytes in length. The varint consists of either zero or more bytes which have the high-order bit set followed by a single byte with the high-order bit clear, or nine bytes, whichever is shorter. The lower seven bits of each of the first eight bytes and all 8 bits of the ninth byte are used to reconstruct the 64-bit twos-complement integer. Varints are big-endian: bits taken from the earlier byte of the varint are more significant than bits taken from the later bytes.
from https://www.sqlite.org/fileformat2.html#varint
The one you linked for SQLite4 (abandoned project) is probably a better approach. I recall that the author has said that SQLite3's varint implementation is regretful.
Re: Bijou64: A variable-length integer encoding
#63The problem is that this breaks down once you try to use SIMD instructions. I'd developed a similar kind of approach to encoding integers (and ieee774 floats) a couple of years ago (first byte encodes length and first bit of data: https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b07186... ). It was very clever and used compiler intrinsics to get the length in 1 instruction, so 2 instructions got you the final va…
> The true irony is that even SIMD text parsing would outperform this! SIMD is that powerful.
Can you explain this part a bit? I feel like intuitively (and therefore probably incorrectly) these should have the same difficulties.
Re: Bijou64: A variable-length integer encoding
#64This reminds me of the varint encoding used by QUIC, but I've never implemented it. Anyone know the differences?
Re: Bijou64: A variable-length integer encoding
#65Maybe someone can explain why an encoder would ever create the padding bytes allowed in LEB128. I contributed the parser for LEB128 in apple/swift-binary-parsing and I’m still none the wiser. I’m genuinely mystified.
I can think of two reasons. The first is what they describe here: as an attack. It's like why would anyone ever overflow a buffer with shellcode. The second is that they are implementing a spec that requires appending a varint length-prefixed field to a buffer but don't really care about the space optimization, don't know the field's length when they start appending it, and don't want to put the field into a second,…
Third is by accident, including by buggy code, and the permissiveness means it's easier for bugs to go unnoticed. See, e.g., https://news.ycombinator.com/item?id=48327115
Re: Bijou64: A variable-length integer encoding
#66Non-canonical encodings are actually quite useful for some applications that need variable length integers. DWARF and WASM both use LEB128. 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 o…
I've often done same thing with encoding msgpack maps while streaming in key/value pairs
Re: Bijou64: A variable-length integer encoding
#67I forget where I encountered it, but I've seen similar encodings that eliminated the possibility of many possible encodings for the same number by making the length part of the value. 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 wa…
According to Wikipedia, git does that: https://en.wikipedia.org/wiki/Variable-length_quantity#Remov...
Re: Bijou64: A variable-length integer encoding
#68This reminds me of the varint encoding used by QUIC, but I've never implemented it. Anyone know the differences?
Similar, in that it encodes length in the first byte. The differences are:
* It does not require canonicality, it allows multiple encodings of the same value. To make things even more fun, the QUIC spec requires shortest encoding in some uses but not others.
* It uses 2 bits rather than cutting out a range.
* It only encodes values up to 62 bits long.
So, some similarities but also some differences.
[1]: https://www.rfc-editor.org/rfc/rfc9000.html#name-variable-le...
Re: Bijou64: A variable-length integer encoding
#69Non-canonical encodings are actually quite useful for some applications that need variable length integers. DWARF and WASM both use LEB128. 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 o…
I've often done same thing with encoding msgpack maps while streaming in key/value pairs
Neat! It's a useful technique whenever you don't know or want to defer knowing the size of an integer until a later time, but need to allocate space for it up front.
I'm wary of introducing these forced-canonical encodings by someone hyper focused on "efficiency" and "security" without reconsidering additional use cases.
Re: Bijou64: A variable-length integer encoding
#70Maybe someone can explain why an encoder would ever create the padding bytes allowed in LEB128. I contributed the parser for LEB128 in apple/swift-binary-parsing and I’m still none the wiser. I’m genuinely mystified.
It's useful whenever you don't know the value of an integer but would like to allocate space for it now, and then fill in the value later. Many have mentioned length-prefixed data, which is a good example. Another use case is static linking. I believe LLVM uses this when generating WASM object files.