Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

UTF-8 history (2003)

cl.cam.ac.uk

Post reply on HN
Print view View original

21–30 of 58 posts

Re: UTF-8 history (2003)

#21

Post by SamReidHughes »

acqq wrote: post #13
kstenerud wrote: post #3

"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?

You can determine whether the leading character is complete or not.

Re: UTF-8 history (2003)

#22

Post by zajio1am »

kstenerud wrote: post #19
zajio1am wrote: post #16

Earlier quoted context omitted.

> 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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

Your second encoding (with binary coded length) would not be self-synchronizing.

Re: UTF-8 history (2003)

#23

Post by fefe23 »

kstenerud wrote: post #19
zajio1am wrote: post #16

Earlier quoted context omitted.

> 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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

One of the requirements is:

4) The first byte should indicate the number of bytes to follow in a multibyte sequence.

This is actually a pretty smart requirement for efficiency. This way the parser can know if the input bytes it has constitute a UTF-8 sequence by only looking at the first byte. That saves a lot of unnecessary processing.

Unfortunately the wording here breaks that advantage: https://en.cppreference.com/w/cpp/string/multibyte/mbrtoc16

if the next n bytes constitute an incomplete, but so far valid, multibyte character. Nothing is written to

The "so far valid" forces implementations to still look at the other bytes, which undoes the optimization in UTF-8. I suspect somebody was asleep at the wheel there.

Regarding your question about the wasted bits: I don't think it matters much. It certainly does not for English text like we exchange here, where the important case is the 0-0x7f case which UTF-8 handles optimally.

Your maximum compactness variant means if you start in the middle of a sequence, you can't tell you are in the middle and not at the start. UTF-8 is doing this well in my opinion. You can seek anywhere in a file and then move forwards or backwards till the beginning of a sequence without fear of misparsing the middle of a correct sequence as a different sequence.

Re: UTF-8 history (2003)

#24

Post by devit »

kstenerud wrote: post #19
zajio1am wrote: post #16

Earlier quoted context omitted.

> 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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

None of these encodings work.

If there is no length encoding, start, middle, end and ASCII byte encodings must not overlap to support correct decoding of any subslice of a document.

If there is a length encoding on the start, then start, middle and ASCII must not overlap.

Re: UTF-8 history (2003)

#26

Post by LoSboccacc »

kstenerud wrote: post #19
zajio1am wrote: post #16

Earlier quoted context omitted.

> 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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

because then you don't know when you jump in the middle of a stream and see a 11xxxxx whether it's the beginning of a valid multibyte character and you have to keep it or part of a multibyte you have to discard it

same with the second encoding, if so happens that one 1xxxxxxx takes the value of 11010101 how would you know it's a multibyte start or a continuation?

basically in the current solution if you read the head of a multibyte character you know it's a valid head, if you read the head of a multibyte in the proposed encoding you can't know if it's valid.

Re: UTF-8 history (2003)

#27

Post by kstenerud »

fefe23 wrote: post #23
kstenerud wrote: post #19

Earlier quoted context omitted.

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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

One of the requirements is: 4) The first byte should indicate the number of bytes to follow in a multibyte sequence. This is actually a pretty smart requirement for efficiency. This way the parser can know if the input bytes it has constitute a UTF-8 sequence by only looking at the first byte. That saves a lot of unnecessary processing. Unfortunately the wording here breaks that advantage: https://en.cppreference.com…

Yes, the ultra-compact encoding will not be self-sequencing. But the bit-6-continuation variant yields more bits per byte, which would give better compression in many languages. Regarding efficiency, you still have to read every character, with the difference being one check every 1, 2, 3, or 4 characters in a more complex algorithm vs a check on every character in a simpler algorithm (I haven't checked to see which beats the other in performance, but they look pretty similar).

This feels a lot like mixing transport layer metadata into the data format, potentially giving a small processing performance benefit at the cost of huge data wastage when certain languages are encoded.

Re: UTF-8 history (2003)

#28

Post by kstenerud »

LoSboccacc wrote: post #26
kstenerud wrote: post #19

Earlier quoted context omitted.

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 ... when it could have been done much more simply by putting the continuation bit in position 6 and keeping bit 7 set across the entire multibyte sequence: 0xxxxxxx 11xxxxxx 11xxxxxx ... 10xxxxxx Or even…

because then you don't know when you jump in the middle of a stream and see a 11xxxxx whether it's the beginning of a valid multibyte character and you have to keep it or part of a multibyte you have to discard it same with the second encoding, if so happens that one 1xxxxxxx takes the value of 11010101 how would you know it's a multibyte start or a continuation? basically in the current solution if you read the head…

Yes, the second one is not self-synchronizing, so it's out. However, I don't see much utility in getting first-character detection from the data format itself. You're very unlikely to miss the beginning of a stream of characters in any modern system, and in the event that your medium has no error detection, it would be trivial to add a zero synchronization byte to the beginning of the field.

My point is that embedding transport level metadata into the data format seems like a poor tradeoff because of the sheer inflation potential of the data encoding (potentially 10%), when a single guard byte per field would solve the problem of first character truncation detection.

Re: UTF-8 history (2003)

#29

Post by boomlinde »

kstenerud wrote: post #3

"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…

> Actually, now that I think about it, VLQ already does satisfy the synchronization requirement. Just scan for the next cleared high bit. At most 1 character consumed, and far less bit wastage.

There are other useful properties of UTF-8 encoding. For one, it is easy to identify invalid UTF-8 sequences, and valid UTF-8 sequences are unlikely to appear in written text encoded as e.g. ISO 8859-1. This must have been more useful in the past when fixed 8-bit encodings were more common. With a simple VLQ your guess whether a stream complies to your encoding won't be nearly as informed, and the means to provide a fallback is diminished. Allowing graceful transition from ASCII and extended ASCII encodings was a very important property for the sake of adoption.

It's also useful that any non-ASCII sequence has the msbit set through the whole sequence. You can easily discard all sequences that can not be displayed as ASCII by throwing bytes >= 0x80, or for example replace every contiguous sequence of >= 0x80 bytes as question marks in an ASCII-only display system and still display all ASCII compatible sequences perfectly.

EDIT: It's also very much not the case that the days of starting read mid-stream are over.

Re: UTF-8 history (2003)

#30

Post by acqq »

SamReidHughes wrote: post #21
acqq wrote: post #13

Earlier quoted context omitted.

> now that I think about it, VLQ already does satisfy the synchronization requirement What was then the advantage of UTF8 over VLQ?

You can determine whether the leading character is complete or not.

Other comments know, see:

https://news.ycombinator.com/item?id=21212851

Post reply on HN