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

21–30 of 93 posts

Re: Bijou64: A variable-length integer encoding

#21

Post by scottlamb »

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.

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, temporary buffer or slide it down into place. https://github.com/FFmpeg/FFmpeg/blob/468a743af1653a08f47081... vs say my own code which does the slide: https://github.com/scottlamb/retina/blob/6972ac4261ce7bf5b58...

Re: Bijou64: A variable-length integer encoding

#22

Post by Chaosvex »

willtemperley wrote: post #12
Chaosvex wrote: post #9

Earlier quoted context omitted.

You wouldn't. It's a strange argument that can be countered with, "maybe don't do that?"

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 strange, not yours.

Re: Bijou64: A variable-length integer encoding

#23

Post by cornstalks »

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 allows you to fill in padding in a buffer. For example, all data in a buffer will be interpreted by a downstream system, and someone pre-calculated the size of that buffer. Rather than encode everything twice (once to figure out the exact size needed, and a second time to actually populate the buffer) the buffer size was calculated using foreknowledge of how many values would be written to that buffer and then just pessimistically assuming all of them are max-size so writing will never fail. Another situation is when you're rewriting part of an already-encoded file. If you want to change a bit of payload then using padding bytes gives you more flexibility so you can do that without having to do any memcpy into a new buffer.

It's uncommon but I've definitely seen it done (with media containers like Matroska, not actually LEB128) in extremely high-throughput systems that can't spare any cycles.

Re: Bijou64: A variable-length integer encoding

#24

Post by b_fiive »

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…

sup steb, this is expede's work!

Re: Bijou64: A variable-length integer encoding

#25

Post by axod »

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.

Maybe you want to byte align some data, or pack to a certain size but keep compat. I think they're going to be rare cases, but I can see it being used.

Re: Bijou64: A variable-length integer encoding

#26

Post by billpg »

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 way to represent 128.

10000000 10000000 00000000 is the only way to represent 16512.

Does this encoding have a name?

Re: Bijou64: A variable-length integer encoding

#27

Post by pkulak »

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…

UTF-8?

Re: Bijou64: A variable-length integer encoding

#28

Post by pta2002 »

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

Re: Bijou64: A variable-length integer encoding

#29

Post by amluto »

Just a quick reminder:

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

Re: Bijou64: A variable-length integer encoding

#30

Post by willtemperley »

esrauch wrote: post #15
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.

Let's say you are writing into a byte[] and have a LEB128 length-prefix followed by a payload, but that determining the length actually involves nontrivial encoding work. For example, you have a UTF16 string and want to write out a UTF8 string, you want to go over the characters and write them out, but the UTF8 length is not known without doing all of that work. If you can choose a fixed number of bytes for the lengt…

Thank you for solving that mystery!
Post reply on HN