Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Bijou64: A variable-length integer encoding

inkandswitch.com

Post reply on HN
Print view View original

81–90 of 93 posts

Re: Bijou64: A variable-length integer encoding

#81

Post by chrismorgan »

pta2002 wrote: post #28
billpg wrote: post #26

I 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…

I believe that's how the varint encoding used by protobut works: https://protobuf.dev/programming-guides/encoding/#varints

> Drop continuation bits.

Clearly not.

Re: Bijou64: A variable-length integer encoding

#83

Post by TZubiri »

>The check is forgotten, optimised away, or never ported. The protocol’s security property silently degrades. This is the bug class bijou64 is designed to make impossible. Not by adding more checks, but by removing the one that mattered — and making the format such that, with no canonicality check at all, the only encoding that exists for any given value is the canonical one

Here's two passing tests for software craftmanship:

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

Re: Bijou64: A variable-length integer encoding

#84

Post by willtemperley »

i2talics wrote: post #70
willtemperley wrote: post #6

Maybe 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.

I think this is probably the real reason such encodings are considered valid. The webassembly spec is explicit about allowing valid over-wide encodings:

https://webassembly.github.io/spec/core/binary/values.html

Maybe a robust parser would benefit from a strict mode, disallowing over-wide encoding.

Re: Bijou64: A variable-length integer encoding

#85

Post by [deleted] »

kstenerud wrote: post #37
nine_k wrote: post #36

Earlier quoted context omitted.

I think these are different use cases. If you talk about SIMD, you talk about the CPU and efficient processing of large numbers of integers. I think that when a solution like this crops up, it's about storage or transmission, and dense packing at the cost of non-uniformity. It's more like time-series databases pack numbers by delta encoding.

The thing is, most real-world numbers will fit within 1-3 bytes (even at 7 bits per byte), so ultradense packing doesn't actually buy much outside of benchmarks. I spent WAYYYYYYYY too much time exploring this...

[deleted]

Re: Bijou64: A variable-length integer encoding

#86

Post by Someone »

stebalien wrote: post #5

I've used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte). 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 m…

> I’ve used LEB128 (with canonicalisation) extensively and... this looks so much nicer for most use-cases (length prefixed, supports the full uint64 range without that extra 10th byte)

If you only want to encode uint64 numbers LEB128 could easily be tweaked to fit in 9 bytes in several ways:

- using the offset trick described in this article would remove non-unique encodings (0x80 0x00 would encode 128)

- never allowing encodings longer than 9 bytes would mean the MSB of any ninth byte would always be zero, so you could reuse that, and store 8 bits in any ninth byte, for a total of 7 bits in each of the first eight bytes plus 8 in the ninth = 64

Both tweaks would lose LEB128’s property that you can find where each number starts from any byte in the stream, but the encoding discussed here doesn’t have that property either.

Re: Bijou64: A variable-length integer encoding

#88

Post by jdougan »

billpg wrote: post #26

I 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…

Humber encoding?
Post reply on HN