3 ms·
This is basically the design of UTF-8 or varint encoding. The integer's representation is read one byte (8 bits) at a time, which can then be interpreted by loo
by svat 3y ago
This is basically the design of UTF-8 or varint encoding. The integer's representation is read one byte (8 bits) at a time, which can then be interpreted by looking at the first bit which says whether the integer is "done" or more bytes need to be read.
(If we were using all 8 bits for the representation and an additional leading bit for whether it continues, we'd end up having to read 9 bits or something, which is awkward and not aligned with what the machine actually supports reading.)
- flohofwoe 3y agoUTF-8 is a bit more complex than that. The first byte in a sequence basically tells you how many bytes are following by looking at the top-most bits. 0xxxxxxx => no followup bytes, just the 7-bit ASCII code 110xxxxx => 1 byte follows 1110xxxx => 2 bytes follow 11110xxx => 3 bytes follow The followup bytes then always have the pattern 10xxxxxx. E.g. the only bytes that have bit 7 cleared are the single-byte 7-bit ASCII character codes.
- Mindless2112 3y agoA UTF-8-like encoding would probably be better than VLQ encoding because the length is known up-front, which allows for the decoder to have fewer branches. Something like [1] or alternatively [2]. See also [3]. [1] https://en.wikipedia.org/wiki/UTF-8#FSS-UTF https://en.wikipedia.org/wiki/UTF-8#FSS-UTF [2] https://sqlite.org/src4/doc/trunk/www/varint.wiki https://sqlite.org/src4/doc/trunk/www/varint.wiki [3] https://news.ycombinator.com/item?id=11263378 https://news.ycombinator.com/item?id=11263378