4 ms·
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 le
by billpg 4mo ago
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?
- pkulak 4mo agoUTF-8?
- teo_zero 4mo agoUTF-8 notoriously doesn't prevent ambiguous encoding by construction, but only prohibiting it in the specs. It's known as overlong encoding. It's up to the encoder/decoder to prevent, correct, or reject it. This burden on the software is exactly what TFA tries to eliminate with the bijou64 format (unfortunately replacing it with another burden: overflow check).
- pta2002 4mo agoI believe that's how the varint encoding used by protobut works: https://protobuf.dev/programming-guides/encoding/#varints https://protobuf.dev/programming-guides/encoding/#varints
- chrismorgan 4mo ago> Drop continuation bits. Clearly not.
- pta2002 4mo agoIndeed, I was misinterpreting the OP's suggestion. Can't edit the comment anymore, unfortunately.
- ezwoodland 4mo agoAccording to Wikipedia, git does that: https://en.wikipedia.org/wiki/Variable-length_quantity#Removing_redundancy https://en.wikipedia.org/wiki/Variable-length_quantity#Remov...
- jdougan 4mo agoHumber encoding?
- sparkie 4mo agoBitcoin has a variable width encoding (`CompactSize`), but it doesn't prevent overlong encodings - however there are various canonicalization rules in the Bitcoin protocol to require minimal encoding.