7 ms·

"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/UT

"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 filled with checksums at every stage, and reduces the bit efficiency of UTF-8. On the other hand, this was the only valid-y reason at the time to rewrite a UTF implementation from scratch. If not for that requirement, we would have just had UTF-8 implemented as regular VLQs. Edit: 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.

lifthrasiir 7y ago
> 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.
- kstenerud 7y ago
  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.
  - lifthrasiir 7y ago
    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.
  - SamReidHughes 7y ago
    Provided that you know where the string boundary is, so you don't scan off the front into differently encoded data. So it can't be backward scanned for some miscellaneous encoded number.
SamReidHughes 7y ago
It's still useful. If you have a string or text file and want to parallelize the processing of it, this lets you cut it in half and do that.
jstimpfle 7y ago
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 stores its own synchronization points, it has to read the file completely at least once, which can be annyoing for very large files. Also, many of the simpler text tools that only look for ASCII bytes wouldn't work. For example, printing the last lines. Also, I don't know that other sytem, but what about robustness if there's one bad byte somewhere in the file?
- kstenerud 7y ago
  You can do the same thing using VLQ, with less wastage. Just scan for the next cleared high bit.
  - mirekrusin 7y ago
    You can also construct malicious payloads which will DoS many implementations with architecture like that.
    - kstenerud 7y ago
      You can also trivially defend against that by having a max travel distance of, say, 4.
      - ludamad 7y ago
        Is that guaranteed to catch all valid cases?
      - mirekrusin 7y ago
        Exactly, so you arrived at the same conclusion - fixed distance so you can safely pick up stream at arbitrary position.
baybal2 7y ago
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
- SamReidHughes 7y ago
  Do you have a link to this 32-bit-aligned proposal?
acqq 7y ago
> now that I think about it, VLQ already does satisfy the synchronization requirement What was then the advantage of UTF8 over VLQ?
- SamReidHughes 7y ago
  You can determine whether the leading character is complete or not.
  - acqq 7y ago
    Other comments know, see: https://news.ycombinator.com/item?id=21212851 https://news.ycombinator.com/item?id=21212851
zajio1am 7y ago
> 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.
DagAgren 7y ago
UTF-8 lets you skip entire characters without scanning the individual bytes, which VLQ does not.
boomlinde 7y ago
> 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.
deleted 7y ago
[deleted]

lifthrasiir 7y ago

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

kstenerud 7y ago
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.
- lifthrasiir 7y ago
  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.
- SamReidHughes 7y ago
  Provided that you know where the string boundary is, so you don't scan off the front into differently encoded data. So it can't be backward scanned for some miscellaneous encoded number.

SamReidHughes 7y ago

It's still useful. If you have a string or text file and want to parallelize the processing of it, this lets you cut it in half and do that.

jstimpfle 7y ago

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 stores its own synchronization points, it has to read the file completely at least once, which can be annyoing for very large files. Also, many of the simpler text tools that only look for ASCII bytes wouldn't work. For example, printing the last lines. Also, I don't know that other sytem, but what about robustness if there's one bad byte somewhere in the file?

kstenerud 7y ago
You can do the same thing using VLQ, with less wastage. Just scan for the next cleared high bit.
- mirekrusin 7y ago
  You can also construct malicious payloads which will DoS many implementations with architecture like that.
  - kstenerud 7y ago
    You can also trivially defend against that by having a max travel distance of, say, 4.
    - ludamad 7y ago
      Is that guaranteed to catch all valid cases?
    - mirekrusin 7y ago
      Exactly, so you arrived at the same conclusion - fixed distance so you can safely pick up stream at arbitrary position.

baybal2 7y ago

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

SamReidHughes 7y ago
Do you have a link to this 32-bit-aligned proposal?

acqq 7y ago

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

SamReidHughes 7y ago
You can determine whether the leading character is complete or not.
- acqq 7y ago
  Other comments know, see: https://news.ycombinator.com/item?id=21212851 https://news.ycombinator.com/item?id=21212851

zajio1am 7y ago

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

DagAgren 7y ago

UTF-8 lets you skip entire characters without scanning the individual bytes, which VLQ does not.

boomlinde 7y ago

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

deleted 7y ago

[deleted]