Ask HN: Why LEB128 and VLQ use Base 128 instead of 64?
I am currently participating to the specification of a binary format that includes variable-length integers.
I am wondering why VLQ/LEB128 [1] use base 128 instead of a more usual Base 64? Is this related to specific needs of where these formats come from?
A Base 64 could not be simpler to implement?
[1] https://en.wikipedia.org/wiki/LEB128
4 comments
[ 0.25 ms ] story [ 22.9 ms ] threadThe counter example is schemes like UTF-8 where the prefix of the bitstream is 0, 10, 110, etc. and how many 1s there are tells how many extra bytes are used.
In programming languages, it is usual to have integers encoded on 32bits or 64bits. In my knowledge integers encoded on 128bits is not common.
In the case of LEB128 and VLQ you are breaking up a single byte (8 bits) into a 1 bit flag (are there any more?) and 7 bits for the actual data, so that is 128 possible values.
If you split up the byte so 2 bits were used for one purpose and 6 bits were used for another purpose you would get have 64 possible values for the second part and lastly out of 5 bits you would have 32 possible values.
Base64/Base32 encoding is something a little different. Let's consider Base 32, between the 26 letters and 10 digits we have 36 symbols, we can leave some of them out and have 32 symbols left.
We can encode some stream of bits 5 bits at a time using Base 32 and it is pretty efficient because we can just shift the bits. If, however, we were desperate to encode data at as high density as possible we might look at all the characters available in a particular place, say the 45 characters in here
https://www.thonky.com/qr-code-tutorial/alphanumeric-table
You could encode a bitstream "base-45" by treating it as a big number, taking the remainder against 45, picking the corresponding character, dividing by 45 until you get to 0.
The 32 in base 32 is just coincidentally the same number as the 32 in 32 bits.