Hacker News Reader

Comment by pierrebai | Hacker News Reader

I never understood why ITF-8 did not use the much simpler encoding of:

    - 0xxxxxxx -> 7 bits, ASCII compatible (same as UTF-8)
    - 10xxxxxx -> 6 bits, more bits to come
    - 11xxxxxx -> final 6 bits.

It has multiple benefits:

    - It encodes more bits per octet: 7, 12, 18, 24 vs 7, 11, 16, 21 for UTF-8
    - It is easily extensible for more bits.
    - Such extra bits extension is backward compatible for reasonable implementations.

The last point is key: UTF-8 would need to invent a new prefix to go beyond 21 bits. Old software would not know the new prefix and what to do with it. With the simpler scheme, they could potentially work out of the box up to at least 30 bits (that's a billion code points, much more than the mere million of 21 bits).

The

View on HN

The problem is that UTF-8 has the ability to detect and reject partial characters at the start of the string; this encoding would silently produce an incorrect character. Also, UTF-8 is easily extensible already: the bit patterns 111110xx, 1111110x, and 11111110 are only disallowed for compatibility with UTF-16's limits.

How often are stream truncated at the start? In my career, I've seen plenty of end truncation, but start truncation never happens. Or, to be more precise, it only happens if previous decoding is already borked. If a previous decoding read too much data, then even UTF-8 is borked. You could be decoding UTF-8 from the bits of any follow-up data.

Even for pure text data, if a previous field was over-read (the only plausible way to have start-truncation), then you probably are decoding incorrect data from then on.

IOW, this upside is both ludicrously improbable and much more damning to the decoding than simply be able to skip a character.

It happens all the time when you're working with substrings. Under your encoding, "é" would be a substring of "ჩ":

           10000011 11101001 U+E9 "é"
  10000001 10000011 11101001 U+10E9 "ჩ"

This would make it incompatible with many existing processes that already handle text, which was one of the goals of UTF-8.

it's nice seeing my native language's character: ჩ

Imagine you plug a dumb terminal into an RS232 port. The computer may have already sent some data. Or it may be in the middle of sending log messages to the console as you plug in.

With a code like this, your dumb terminal can be built so it just automatically works. Without it, the terminal may be off by some number of bytes, and you have to have some sort of other (probably manual) synchronization procedure.

Similarly, imagine you've dialed in over modem to a remote system. You get some errors or lost text due to noise on the phone line. Or some bytes are lost due to bad RS232 flow control or no flow control. Your terminal emulator would be able to recover.

There might also be uses where text is broadcast, such as in TV closed captions, although maybe those have their own framing so you know where strings begin.

From the Wikipedia article:

Prefix code: The first byte indicates the number of bytes in the sequence. Reading from a stream can instantaneously decode each individual fully received sequence, without first having to wait for either the first byte of a next sequence or an end-of-stream indication. The length of multi-byte sequences is easily determined by humans as it is simply the number of high-order 1s in the leading byte. An incorrect character will not be decoded if a stream ends mid-sequence.

https://en.wikipedia.org/wiki/UTF-8#Comparison_with_other_en...

"instantaneously" in the sense of first having to read the first byte to know how many bytes to read. So it's a two-step process. Given the current maximum length and SIMD, detecting the end-byte of my scheme is easily parallelizable for up to 4 bytes, which conveniently goes to 24 bits, enough for all current unicode code points, so there is no waiting for termination. Furthermore, to decode a UTF-8 characters needs bits extraction and shifting of all bytes, so there is no practical gain of not looking at every byte. It actually makes the decoding loop more complex.

Also, the human readability sounds fishy. Humans are really bad at decoding high-order bits. For example can you tell the length of a UTF-8 sequence that would begin with 0xEC at a glance? With my scheme, either the high bit is not set (0x7F or less), which is easy to see you only need to compare the first digit to 7. Or the high bit is set and the high nibble is less than 0xC, meaning there is another byte, also easy to see, you compare the first digit to C.

The quote also implicitly mis-characterized the fact that in my scheme an incorrect character would also not be decoded if interrupted since it would lack the terminating flag (No byte > 0xC0).

"Instantly" as in you get a stream of characters and with UTF-8 you always know as soon as you have received a full character. With your encoding it is always possible that you have not received the full character yet and need to wait until the start of the next character (or a timeout).

UTF-8 as defined (or restricted) is a prefix code, it gets all relevant information on the first read, and the rest on the (optional) second. Your scheme requires an unbounded number of reads.

> - It is easily extensible for more bits.

UTF8 already is easily extensible to more bits, either 7 continuation bytes (and 42 bits), or infinite. Neither of which is actually useful to its purposes.

> The last point is key: UTF-8 would need to invent a new prefix to go beyond 21 bits

UTF8 was defined as encoding 31 bits over 6 bytes. It was restricted to 21 bits (over 4 bytes) when unicode itself was restricted to 21 bits.

> UTF8 already is easily extensible to more bits, either 7 continuation bytes (and 42 bits), or infinite.

Extending UTF-8 to 7 continuation bytes (or more) loses the useful property that the all-ones byte (0xFF) never happens in a valid UTF-8 string. Limiting it to 36 bits (6 continuation bytes) would be better.

Why is that useful?

You can use FF as a sentinel byte internally (I think utf8proc actually does that?); given that FE never occurs, either, if you see the byte sequence corresponding to U+FEFF BYTE ORDER MARK in one of the other UTFs you can pretty much immediately tell it can’t possibly be UTF-8. (In general UTF-8, because of all the self-synchronization redundancy, has a very distinctive pattern that allows it to be detected with almost perfect reliability, and that is a frequent point of UTF-8 advocacy, which lends some irony to the fact that UTF-8 is the one encoding that Web browsers support but refuse to detect[1].) I don’t think there is any other advantage to excluding FF specifically, it’s not like we’re using punched paper tape.

[1] https://hsivonen.fi/utf-8-detection/

You can use 11000000 and 11000001 as sentinel bytes; since a sequence beginning with them can't possibly be minimal.

And Unicode was restricted to 21 bits because of UTF-16. There is still the possibility of that restriction being lifted eventually.

No software decodes data by reading a stream byte-by-byte. Like I said in a previous comment, decoding 4 bytes using SIMD is possible and probably the best way to go. Furthermore, to actually decode, you need bit twiddling anyway, so you do need to do byte-processing. Finally, the inner loop of detecting character boundary is simpler: the UTF-8 scheme, due to the variable-length prefixes, requires to detect the first non-1 bits. It is probably written with a switch/case in C, vs two bit tests in my scheme. I'm not convinced the UTF-8 ends-up with a faster loop.

> No software decodes data by reading a stream byte-by-byte.

Maybe not in your bubble, but in my bubble this is the common case and highly optimized components using SIMD parsing is the exception.

By byte-by-byte, I presume you mean logically, not invoking a syscall for every byte. A parsing library is often handed a buffer to parse. If every layer had it's own buffering, you'd end up with too much data copying, which compounds and can spill your CPU caches in ways that microbenchmarks won't reflect, particularly in a streaming pipeline. So you stick to simpler, straight-forward code and data paths, unless and until you know a particular component is a bottleneck. I've had much better results optimizing globally first before optimizing locally. You can usually go back and optimize locally whenever you want, but optimizing globally is more often a one-shot deal as it typically requires non-local (i.e. cross-component) analysis and refactors, which nobody has time for.

The current scheme is extensible to 7x6=42 bits (which will probably never be needed). The advantage of the current scheme is that when you read the first byte you know how long the code point is in memory and you have less branching dependencies, i.e. better performance.

EDIT: another huge advantage is that lexicographical comparison/sorting is trivial (usually the ascii version of the code can be reused without modification).

like "A Branchless UTF-8 Decoder" at https://nullprogram.com/blog/2017/10/06/

> The current scheme is extensible to 7x6=42 bits (which will probably never be needed).

I have printed this out and inserted it into my safe deposit box, so my children's children's children can take it out and have a laugh.

You can actually extend it indefinitely, 42 bits is just the farthest you can go by trividally extending the bit patterns with the existing logic.

Unicode 13 uses 143859 code points. 21 bits can encode more than 10x of that. And there are not that many languages left to add. We are already debating elvish. I am not sure what would warrant extending the coding scheme if we are already on the level of fictional languages today. Also note that many things like flags or emoji skin colors, etc. are now done via grapheme clusters, which conserves code points.

I have stapled your reply to the original printout for extra hilarity! :)

UTF-8 is self-resynchronizing. You can scan forwards and/or backwards and all you have to do is look for bytes that start a UTF-8 codepoint encoding to find the boundaries between codepoints. It's genius.

Reply on news.ycombinator.com