News for hackers. Stuff that matters.
Re:Making all your integers positive with zigzag encoding by eloff on Friday November 25, 2022 @03:51PM (#33746624)
Protobuf was the first major project I was aware of that uses zigzag encoding for integers. They then encode those integers using the typical 7 bit encoding scheme where the msb indicates there's another byte following. I'm sure they weren't the first by any means though.

I'm currently using this in a binary format for serializing dynamic JSON-like values that I invented and am implementing in Rust. I will release it as open source sometime next year.

Re:Making all your integers positive with zigzag encoding by tikhonj on Friday November 25, 2022 @04:17PM (#33746877)
I first ran into this encoding scheme in Avro, which you could also describe as a format for dynamic JSON-like values :)
Re:Making all your integers positive with zigzag encoding by ramranch on Friday November 25, 2022 @05:47PM (#33747700)
Does your protocol provide any advantages over bincode?
Re:Making all your integers positive with zigzag encoding by eloff on Friday November 25, 2022 @08:51PM (#33749038)
Yes, but not as a general purpose encoding. It's more fit for it's intended purpose.
Re:Making all your integers positive with zigzag encoding by anonymoushn on Saturday November 26, 2022 @03:25AM (#33750952)
This format makes it impossible to write fast decoders, as discussed elsewhere on the same blog as TFA: https://lemire.me/blog/2017/09/27/stream-vbyte-breaking-new-...

So it would be sweet to instead use a format for which it is possible to write fast decoders

Re:Making all your integers positive with zigzag encoding by eloff on Saturday November 26, 2022 @10:22AM (#33753351)
Yeah, I don't like that method for encoding variable length integers.

I usually use something I came up with years ago where the low 2 or 3 bits are the length - 1 in bytes. It's more compact and can be serialized/deserialized without branches in the common case. It uses the count leading zeroes instruction for encoding. I'm sure somebody else has come up with the idea as well.

The downside is you can only represent 30 bits for u32 and 61 for u64. In many cases you know you don't have values that large, so it's fine.

If you're encoding arrays of integers, Lemire has a library that uses vector instructions to encode them in the optimal number of bits. That's even better, but the use cases are far more restricted.