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

41–50 of 93 posts

Re: Bijou64: A variable-length integer encoding

#41

Post by kstenerud »

jaen wrote: post #40
kstenerud wrote: post #20

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

This doesn't seem particularly hard to SIMD, especially when the CPU architecture has "compress/expand" horizontal instructions. The first byte fully encodes the length, which is not harder than the continuation bits of (U)LEB128. It's a basically a common length-prefixed encoding with an extra subtract added in, so someone has probably figured out an efficient algorithm. It might be slightly more instructions than s…

It can't be done, because the next bytes are dependent upon the first byte (which only works in limited circumstances, and where you have constant spacing between the values).

ULEB128 works in SIMD because there's only one dependent bit per byte, so you can speculatively decode and then correct later cheaply. Bijou requires you to check the first byte and then branch based on the value using all 8 bits in the decision matrix (to handle branches 0-247, 248, 249, 250, 251, 252, 253, 254, 255). This absolutely DESTROYS any parallelization opportunities.

Not to mention that non-canonical sized ints (3, 5, 6, 7) have abysmal performance compared to unaligned 2, 4, and 8 byte reads on modern processors.

Re: Bijou64: A variable-length integer encoding

#42

Post by aDyslecticCrow »

Clever, but one thought crossed my mind;

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.

Re: Bijou64: A variable-length integer encoding

#45

Post by gregschlom »

aDyslecticCrow wrote: post #42

Clever, but one thought crossed my mind; 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.

You have the same issue with LEB128 though, right?

Re: Bijou64: A variable-length integer encoding

#46

Post by dgllghr »

harrisi wrote: post #44

I'm surprised there's no mention in the post or here about SQLite's varint encoding. Not that it would necessarily satisfy the constraints, but it's one of the most used varint implementations.

It's not terribly fast. It's faster than LEB128 but not as fast as vu128 (at least according to https://github.com/Jiboo/varint_benchmark)

Re: Bijou64: A variable-length integer encoding

#47

Post by matja »

RedShift1 wrote: post #2

This seems quite convoluted just to avoid the "0 can be represented in more than one way" problem.

> canonicality matters — for signatures, content-addressing, or any kind of “two implementations must agree on the bytes” property

If you don't do this properly, you end up with things like: - SAML XSW attack due to XML signature wrapping - ASN.1 BER/DER signature forgery - Bitcoin transaction malleability attacks

Re: Bijou64: A variable-length integer encoding

#48

Post by i2talics »

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

Re: Bijou64: A variable-length integer encoding

#49

Post by pixelesque »

gregschlom wrote: post #45
aDyslecticCrow wrote: post #42

Clever, but one thought crossed my mind; 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.

You have the same issue with LEB128 though, right?

Very likely, but isn't this post claiming that bijou64 is safer than LEB128 for the situation of adversarial varints?

Re: Bijou64: A variable-length integer encoding

#50

Post by [deleted] »

kstenerud wrote: post #41
jaen wrote: post #40

Earlier quoted context omitted.

This doesn't seem particularly hard to SIMD, especially when the CPU architecture has "compress/expand" horizontal instructions. The first byte fully encodes the length, which is not harder than the continuation bits of (U)LEB128. It's a basically a common length-prefixed encoding with an extra subtract added in, so someone has probably figured out an efficient algorithm. It might be slightly more instructions than s…

It can't be done, because the next bytes are dependent upon the first byte (which only works in limited circumstances, and where you have constant spacing between the values). ULEB128 works in SIMD because there's only one dependent bit per byte, so you can speculatively decode and then correct later cheaply. Bijou requires you to check the first byte and then branch based on the value using all 8 bits in the decisio…

[deleted]
Post reply on HN