"So we went to dinner, Ken figured out the bit-packing..."
I cannot find the words to describe how much I admire these guys (ken, rob, drm, etc).
UTF-8 history (2003)
11–20 of 58 posts
Re: UTF-8 history (2003)
#12"Why didn't we just use their FSS/UTF? As I remember, it was because in that first phone call I sang out a list of desiderata for any such encoding, and FSS/UTF was lacking at least one - the ability to synchronize a byte stream picked up mid-run, with less that one character being consumed before synchronization." I'm of two minds about this. On the one hand, such an ability is pretty useless in modern systems fille…
There are now encoding even more efficient than VLQ, but they blue the line in between encodings and compression algorithms. Most propose to trade efficiency of encoding 7 bit chars for ability to squeeze few thousands common Chinese characters into 16 bits.
The idea I heard was that to always code in 4 bytes blocks, and use some form of delta encoding. Some variations allow for less than OlogN character position search. And given that you can feed 32 wide data into NEON/SSE, and block are always 32 bit aligned, you can have that working faster than UTF-8
Re: UTF-8 history (2003)
#13"Why didn't we just use their FSS/UTF? As I remember, it was because in that first phone call I sang out a list of desiderata for any such encoding, and FSS/UTF was lacking at least one - the ability to synchronize a byte stream picked up mid-run, with less that one character being consumed before synchronization." I'm of two minds about this. On the one hand, such an ability is pretty useless in modern systems fille…
> now that I think about it, VLQ already does satisfy the synchronization requirement
What was then the advantage of UTF8 over VLQ?
Re: UTF-8 history (2003)
#14Earlier quoted context omitted.
The ability to pick up byte streams mid-run is not useless. It's required for example to jump to arbitrary locations in a file and make sense of the data you find there. Imagine a text editor displaying a large CSV file. Wouldn't you mind having to read everything betseen two locations if you jump forward from the one to the other? Or read everything from the start if you jumping backwards? Even if the text editor st…
You can do the same thing using VLQ, with less wastage. Just scan for the next cleared high bit.
You can also construct malicious payloads which will DoS many implementations with architecture like that.
Re: UTF-8 history (2003)
#15Earlier quoted context omitted.
You can do the same thing using VLQ, with less wastage. Just scan for the next cleared high bit.
You can also construct malicious payloads which will DoS many implementations with architecture like that.
You can also trivially defend against that by having a max travel distance of, say, 4.
Re: UTF-8 history (2003)
#16"Why didn't we just use their FSS/UTF? As I remember, it was because in that first phone call I sang out a list of desiderata for any such encoding, and FSS/UTF was lacking at least one - the ability to synchronize a byte stream picked up mid-run, with less that one character being consumed before synchronization." I'm of two minds about this. On the one hand, such an ability is pretty useless in modern systems fille…
> If not for that requirement, we would have just had UTF-8 implemented as regular VLQs.
There is a requirement that 7-bit ASCII character codes would not appear as a part of non-ASCII character encoding, so NULL-terminated strings, slash path separation and other similar issues could be handled by existing charset-independent code. That would not work with regular VLQs.
Re: UTF-8 history (2003)
#17Nice post, quite interesting.
I think Rob Pike may have one of the coolest email addresses in the world (r@google.com).
Re: UTF-8 history (2003)
#18Earlier quoted context omitted.
> If not for that requirement, we would have just had UTF-8 implemented as regular VLQs. While not technically equivalent, synchronized byte stream allows a backward scanning that is beneficial for many Unicode-related algorithms. In fact synchronization is the simplest way to do that.
VLQ can also be backward scanned, since the high bit is the continuation bit. Just scan for the next cleared high bit, which marks the end of a glyph.
Ah, good point. I'm still confusing which one is which. I was specifically thinking of UTF-1 that is definitely not synchronized nor backward scannable.
Re: UTF-8 history (2003)
#19"Why didn't we just use their FSS/UTF? As I remember, it was because in that first phone call I sang out a list of desiderata for any such encoding, and FSS/UTF was lacking at least one - the ability to synchronize a byte stream picked up mid-run, with less that one character being consumed before synchronization." I'm of two minds about this. On the one hand, such an ability is pretty useless in modern systems fille…
> If not for that requirement, we would have just had UTF-8 implemented as regular VLQs. There is a requirement that 7-bit ASCII character codes would not appear as a part of non-ASCII character encoding, so NULL-terminated strings, slash path separation and other similar issues could be handled by existing charset-independent code. That would not work with regular VLQs.
Actually, that's right, forgot about that :P
The only remaining mystery then would be why they bothered encoding it like this:
0xxxxxxx
110xxxxx 10xxxxxx
1110xxxx 10xxxxxx 10xxxxxx
11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
0xxxxxxx
11xxxxxx 11xxxxxx ... 10xxxxxx
0xxxxxxx
100xxxxx 1xxxxxxx
101xxxxx 1xxxxxxx 1xxxxxxx
110xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx
111xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxxRe: UTF-8 history (2003)
#20"Why didn't we just use their FSS/UTF? As I remember, it was because in that first phone call I sang out a list of desiderata for any such encoding, and FSS/UTF was lacking at least one - the ability to synchronize a byte stream picked up mid-run, with less that one character being consumed before synchronization." I'm of two minds about this. On the one hand, such an ability is pretty useless in modern systems fille…
UTF-8 lets you skip entire characters without scanning the individual bytes, which VLQ does not.