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

31–40 of 93 posts

Re: Bijou64: A variable-length integer encoding

#31

Post by onlyrealcuzzo »

nine_k wrote: post #7

In short: instead of a truly indefinite-length solution with a signal bit on the current byte saying whether to check the next byte, this uses a counter. Values 0x0 to 0xF7 are one-byte integers, 0xF8 to 0xFF use the upper 5 bits as a counter for the number of subsequent bytes. This limits the maximum magnitude to slightly less than 2 ^ 264 (almost all 33-byte values), which seems to be okay for practical computation…

> I though that for anything security-related (like the author's project) testing against adversarial input would be be a prominent part.

They might have a different definition of adversarial than you.

> My tests for quite pedestrian APIs often contain adversarial input of obvious shapes.

This doesn't seem like what I would call adversarial.

This seems like standard negative testing or boundary value analysis - which I would be shocked if they didn't do.

Re: Bijou64: A variable-length integer encoding

#32

Post by petermcneeley »

HansHamster wrote: post #11

It feels a bit unfair to say that it is faster by being able to tell the total length from the first byte and capping it at 64 bit, while some of the other formats can store arbitrarily large integers. I guess you could use another variable length encoding for the prefix at the cost of some performance and using even more space...

esp when the number is capped at only 64 bits which is quite small for some bigInt style numbers.

Re: Bijou64: A variable-length integer encoding

#33

Post by willtemperley »

Chaosvex wrote: post #22
willtemperley wrote: post #12

Earlier quoted context omitted.

So why does the spec allow it? Like a good engineer I read the spec and tested against the over-wide example encodings given.

Because it's not a real standard and there is no blessed RFC for it. The DWARF spec is as close as you'll get and it says, "The integer zero is a special case, consisting of a single zero byte." So in a way, it doesn't. Either way, a properly written decoder (and it's like ten lines) should really not have any problems with it. I was agreeing with you. Edit: to clarify, I was talking about the author's argument being…

The WASM spec is more explicit about over-long LEB128 encoding.

Edit: a properly written decoder is a lot more than 10 lines if you properly deal with integer overflow and both signed and unsigned ints.

Re: Bijou64: A variable-length integer encoding

#35

Post by kbolino »

layer8 wrote: post #13
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.

The issue is that non-unique encodings are an attack vector, because parsers may in practice behave differently for noncanonical (or nominally invalid) encodings.

For example, you have an envelope format that goes: length prefix in LEB128, message, signature. One party controls the length prefix and signature, a different party controls the message. The message-writing party carefully crafts the message so that, in isolation, it appears innocuous, but when wrapped in the envelope, the first few bytes of the message look like continuation of the length prefix. Best case is the receiving party safely fails to parse the message, worst case is the receiving party successfully parses the message, verifies its digital signature, and interprets it differently than the signer did.

Re: Bijou64: A variable-length integer encoding

#36

Post by nine_k »

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…

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.

Re: Bijou64: A variable-length integer encoding

#37

Post by kstenerud »

nine_k wrote: post #36
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…

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

Re: Bijou64: A variable-length integer encoding

#38

Post by the-lazy-guy »

nine_k wrote: post #36
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…

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.

Stored and transmitted data also has to be decoded. With modern datacenter hardware bottleneck is often CPU rather than network or disk (SSD). It depends on specific properties of the data. (I used to work on search index implementation which is about decoding and intersecting large amounts of hit-lists; and right SIMD-friendly varint encoding is obviously crucial)

Re: Bijou64: A variable-length integer encoding

#39

Post by michaelmure »

One nice upside of having a single way to encode a value is fuzzing: when you work on an encoder/decoder, you can use a fuzzer and do round-trip comparison until you find crashes or inputs/outputs that don't match (and therefore issues in the code). But with LEB128 for example, the fuzzer quickly learn about those alternatives encoding and there is not much you can do from there.

Re: Bijou64: A variable-length integer encoding

#40

Post by jaen »

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 some other serial VL (variable-length) integer codec choices, but overall I don't think it's more difficult.

The very efficient SIMD VL codecs tend to stripe (separate) the control and data bits, so they're in a different design space anyway.

Post reply on HN