4 ms·

> 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 appe

> 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.

kstenerud 7y ago
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 like this for maximum compactness: 0xxxxxxx 100xxxxx 1xxxxxxx 101xxxxx 1xxxxxxx 1xxxxxxx 110xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 111xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx
- zajio1am 7y ago
  Your second encoding (with binary coded length) would not be self-synchronizing.
- fefe23 7y ago
  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 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.
  - kstenerud 7y ago
    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.
    - marcosdumay 7y ago
      > huge data wastage when certain languages are encoded Is there a language that consistently uses codepoints with more than 2 bytes? It bothers me a bit that UTF-8 is not an infinitely extendable encoding. But that also isn't an important objection, because it is finite, but huge.
      - kstenerud 7y ago
        Yeah, it's fine that the encoding is not infinitely extendable. But if it didn't encode the length into the first byte, you'd have 1 extra bit for 2-byte sequences, 2 extra bits for 3-byte sequences, etc. That means that you can double the number of possible glyphs per 2-byte sequence (for an extra 2048 glyphs in the 2-byte range). For 3 bytes, it's 2 bits for an extra almost 200,000 glyphs before having to jump to 4 bytes. This would be a huge boon to East Asian languages like Chinese and Japanese.
      - XaspR8d 7y ago
        > Is there a language that consistently uses codepoints with more than 2 bytes? There are definitely (small) communities using scripts that lie entirely in the SMP. For example, Mru, Adlam, Takri, Pracalit, Miao, Wancho, etc. Most of these are either historic scripts that have mostly been supplanted by unified ones (esp. Devanagari) but retain usage in some areas, or languages that did not have a pre-colonial writing system that are attempting to reclaim cultural identity with a new script. But yes, I don't think there are major communities that consistently do so. My anecdata from a few Mandarin- and Japanese-speaking friends is that SIP characters rarely occur. Really if anything, emoji obsessives, mathematicians using bold/fraktur characters, and historical linguists/anthropologists would have the biggest savings. https://en.wikipedia.org/wiki/Mru_language#Alphabet https://en.wikipedia.org/wiki/Mru_language#Alphabet https://en.wikipedia.org/wiki/Adlam_script https://en.wikipedia.org/wiki/Adlam_script https://en.wikipedia.org/wiki/Takri_script https://en.wikipedia.org/wiki/Takri_script https://en.wikipedia.org/wiki/Pracalit_script https://en.wikipedia.org/wiki/Pracalit_script https://en.wikipedia.org/wiki/Pollard_script https://en.wikipedia.org/wiki/Pollard_script
- devit 7y ago
  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.
- LoSboccacc 7y ago
  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.
  - kstenerud 7y ago
    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.
    - labawi 7y ago
      > I don't see much utility in getting first-character detection .. > .. in the event that your medium has no error detection ... add a zero synchronization byte How would such encoding deal with non-utf8-safe editors, copy-pasting, programs truncating, then inserting previously broken sequences, etc? Encoding obviously can't fix all errors, but it is quite useful if broken sequences are obviously broken and non-broken sequences remain valid when handling text in non-aware/non-safe applications. I think in UTF8 two splices can generate a random character, but in a characters + splice combination, the character remains recognizable in any order and combination and a lone splice is also recognizable as an error.

kstenerud 7y ago

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 like this for maximum compactness: 0xxxxxxx 100xxxxx 1xxxxxxx 101xxxxx 1xxxxxxx 1xxxxxxx 110xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 111xxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx

zajio1am 7y ago
Your second encoding (with binary coded length) would not be self-synchronizing.
fefe23 7y ago
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 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.
- kstenerud 7y ago
  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.
  - marcosdumay 7y ago
    > huge data wastage when certain languages are encoded Is there a language that consistently uses codepoints with more than 2 bytes? It bothers me a bit that UTF-8 is not an infinitely extendable encoding. But that also isn't an important objection, because it is finite, but huge.
    - kstenerud 7y ago
      Yeah, it's fine that the encoding is not infinitely extendable. But if it didn't encode the length into the first byte, you'd have 1 extra bit for 2-byte sequences, 2 extra bits for 3-byte sequences, etc. That means that you can double the number of possible glyphs per 2-byte sequence (for an extra 2048 glyphs in the 2-byte range). For 3 bytes, it's 2 bits for an extra almost 200,000 glyphs before having to jump to 4 bytes. This would be a huge boon to East Asian languages like Chinese and Japanese.
    - XaspR8d 7y ago
      > Is there a language that consistently uses codepoints with more than 2 bytes? There are definitely (small) communities using scripts that lie entirely in the SMP. For example, Mru, Adlam, Takri, Pracalit, Miao, Wancho, etc. Most of these are either historic scripts that have mostly been supplanted by unified ones (esp. Devanagari) but retain usage in some areas, or languages that did not have a pre-colonial writing system that are attempting to reclaim cultural identity with a new script. But yes, I don't think there are major communities that consistently do so. My anecdata from a few Mandarin- and Japanese-speaking friends is that SIP characters rarely occur. Really if anything, emoji obsessives, mathematicians using bold/fraktur characters, and historical linguists/anthropologists would have the biggest savings. https://en.wikipedia.org/wiki/Mru_language#Alphabet https://en.wikipedia.org/wiki/Mru_language#Alphabet https://en.wikipedia.org/wiki/Adlam_script https://en.wikipedia.org/wiki/Adlam_script https://en.wikipedia.org/wiki/Takri_script https://en.wikipedia.org/wiki/Takri_script https://en.wikipedia.org/wiki/Pracalit_script https://en.wikipedia.org/wiki/Pracalit_script https://en.wikipedia.org/wiki/Pollard_script https://en.wikipedia.org/wiki/Pollard_script
devit 7y ago
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.
LoSboccacc 7y ago
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.
- kstenerud 7y ago
  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.
  - labawi 7y ago
    > I don't see much utility in getting first-character detection .. > .. in the event that your medium has no error detection ... add a zero synchronization byte How would such encoding deal with non-utf8-safe editors, copy-pasting, programs truncating, then inserting previously broken sequences, etc? Encoding obviously can't fix all errors, but it is quite useful if broken sequences are obviously broken and non-broken sequences remain valid when handling text in non-aware/non-safe applications. I think in UTF8 two splices can generate a random character, but in a characters + splice combination, the character remains recognizable in any order and combination and a lone splice is also recognizable as an error.