4

When you encode a code point to code units based on UTF-8, then if the code point fits on 7 bits, the most significant bit is set to zero so that it tells you it is a character which is stored on 1 byte (or more precisely 7 bits).

If the codepoint occupies more than 7 bits, then the number of leading one bits of the first byte tell you how many code units constitute that given code point. According to the specification this sequence of one bits is always followed by a sigle zero bit which terminates it and therefore separates it from the start of the code point.

I have specific questions, please answer separately.

1) If the first byte makes it crystal clear how many bytes you should read for the codepoint, why is it that the first 2 bits of every continuation byte are set to “10”? Why are they necessary if you know exactly how many bytes are there? They seem to be wasting precious space.

2) The second question is what are the theoretical limits of UTF-8? Due to compatibility reasons, UTF-8 will always encode to a maximum of 4 code units. But others say that theoretically it is capable of encoding code points to up to 7 code units, which means that the first byte does not contain any of the code point bits. It is 7 one bits followed by the terminating zero. But if we start to make theories, then we could say UTF-8 could encode to an arbitrary amount of code units too if we did not limit the size indication to the first byte. For example the 52-bit nonexistent code point 0x8000000000000 could be stored as follows:

1111 1111 - 1100 1000 1000 0000 - 1000 0000 1000 0000 - 1000 0000 1000 0000 - 1000 0000 1000 0000 - 1000 0000

This would mean that this character is stored on 10 bytes.

  • 1
    I think your second point is hypothetically possible. In addition, we don't have to keep to the same 11111111 pattern, we don't have to extend it one bit at a time, and we don't have to have that mean extending the data only one byte a a time. All that is technically required is to be able to positively differentiate between forms and there's lots of approaches for that, plus, different approaches can be mixed within a single code. – Erik Eidt Nov 15 at 22:23
  • Your second point may be correct but it is moot. The purpose of UTF-8 is to encode Unicode. By anyone's wildest imagination there will never be enough characters in the universe to need a second byte for the mapping part. So stating "the first byte will tell you the number of bytes" is correct as far as UTF-8 will ever be concerned. And considering the current state of the Unicode standard, a maximum of four bytes must suffice. – Martin Maat Nov 17 at 7:18
  • @Martin: Yes, there are over a million code points. But there are many many more possible characters, because characters can be made of several code points. And there is a slow progress to string libraries that natively handle characters which may consist of multiple code points. There are emojis already that are made of ten or more code points. – gnasher729 Nov 17 at 12:26
  • Before reading this question I did not really know what code points were. I assumed it was just a fancy word for the binary encoding behind a character. Which I then learned is basically correct but here's someone who explains it well: stackoverflow.com/questions/27331819/… – Martin Maat Nov 17 at 18:22
10

Answer to Question 1: why is it that the first 2 bits of every continuation byte are set to “10”?

It lets you land at a random place in the sequence and unambiguously work back to the beginning of the current code point (or forward to the start of the next one).

If you are starting from the beginning of a sequence, then you know the first byte is a leading byte, and can work forwards from there - easy. But if we aren't doing that, and if we didn't force the second-from-top bits of continuation bytes to zero, then we wouldn't be able to distinguish some continuation bytes from a start byte.

Consider as example: 110xxxxx 10xxxxxx, but in a world where we don't force the 0 in byte 2 and squeeze 7 bits of useful data in the second byte, we could have 11011111 11011111 as a legitimate char encoding, and we can't tell where the beginning is anymore.

It is self-synchronizing, as @ErikEidt notes in the comments. You can be dropped at a random place in the sequence, and back up no more than 3 bytes to find an unambiguous lead byte. You will also never find a shorter code buried in a longer one: without these properties, you wouldn't be able to go from this codepoint to the previous one in fast constant time (as highlighted in comments by @gnasher729). It means you can process a UTF-8 string in reverse with about the same cost overhead as working forwards.

Answer to Question 2: what are the theoretical limits of UTF-8?

I don't think I can put it better than Erik has in his comment to the question, which I shall copy here for posterity:

I think your second point is hypothetically possible. In addition, we don't have to keep to the same 11111111 pattern, we don't have to extend it one bit at a time, and we don't have to have that mean extending the data only one byte at a time. All that is technically required is to be able to positively differentiate between forms and there's lots of approaches for that, plus, different approaches can be mixed within a single code. – Erik Eidt

  • This property is call self-synchronizing (or a self synchronizing code). – Erik Eidt Nov 15 at 22:18
  • @ErikEidt I knew there was a name for it :-) I'll add that in, if that's ok? – SusanW Nov 15 at 22:24
  • @ErikEidt I felt bad that I hadn't answered q2, but your comment above sort of said it all, so I've edited it in. If you want it back, so to speak, or want to do your own answer, please just edit it out again and I'll fix it up. – SusanW Nov 15 at 23:40
  • Self-synchronising is very useful. I think more important is the less strict property that given the first byte of one code point, you can easily find the start of the previous code point (and of course the next code point). Easily = fast constant time. – gnasher729 Nov 16 at 21:49
  • @gnasher729 excellent point, yep, means that reverse-processing is cheap - I've just edited that into the answer. Do edit to taste if you like, or note any refinements here and I'll do them. Thanks! – SusanW Nov 18 at 9:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.