2

Say you have an UTF-8 encoded string s. You extract the first bytes that appear to be an UTF-8 encoded codepoint and put them into a 32 bit integer c.

For example:

  • if you have s="AB" (which is {0x41,0x42,0x00}), c will be 0x41;
  • if you have s="èB" (which is {0xC3,0xA8,0x42,0x00}) c will be 0xC3A8;

The problem is to check if c is a valid encoding or not.
The function I wrote is the one below but I'm not sure if this is correct (I might miss some edge cases).

I know I can go byte by byte following the FSM specified by the standard but I need to check if this is a correct approach.

int chr_isvalid(uint32_t c)
{
  if (c <= 0x7F) return 1;
  if (0xC080 == c) return 1;   // Accept 0xC080 as representation for '\0'
  if (0xC280 <= c && c <= 0xDFBF) return ((c & 0xE0C0) == 0xC080);
  if (0xEDA080 <= c && c <= 0xEDBFBF) return 0; // Reject UTF-16 surrogates
  if (0xE0A080 <= c && c <= 0xEFBFBF) return ((c & 0xF0C0C0) == 0xE08080);
  if (0xF0908080 <= c && c <= 0xF48FBFBF) return ((c & 0xF8C0C0C0) == 0xF0808080);
  return 0;
}

CLARIFICATIONS:

  • Please look down at my self-response to see why I believe this code is correct.
  • I'm not trying to guess if this is UTF-8 or any other encoding. The assumption is that the string is UTF-8 encoded.
  • The candidate codepoint can be extracted just looking at the starting 1 in the bytes but this is not relevant because the function must work for any value of c.
  • The encoding for any valid codepoint (U+000000 - U+10FFFF) fits into a 32 bit integer.
  • I need the extracted c in its encoded form for other purposes
  • Thanks to Jonathan Leffler comment below on UTF-16 surrogates U+D800 - U+DFFF I now reject them.
  • Thanks to Jonathan Leffler comment below on overlong encoding, I fixed it and should be now correct. Any 2 bytes overlong encoding must be less than 0xC280, any 3 bytes overlong encoding less than 0xE0A080 and any 4 bytes overlong encoding less than 0xF0908080. I filtered those out.

To better pinpoint my mistakes, please provide an example of a valid encoded codepoint that this code rejects or an invalid encoding that this code accepts as valid.

21
  • 3
    Is there a reason why you need to load the bytes into an integer? It seems to make the problem a lot harder to write and understand. Why not just work with the bytes as bytes?
    – JoelFan
    Commented Mar 19, 2021 at 21:46
  • 1
    What @JoelFan said. Moreover, your proposed code doesn't make sense. It looks like it expects the caller to have already chopped off the correct number of bytes, which is only possible if the caller already did the work. But maybe this is just the weird (very artificial, most likely) problem scenario you've been given..? Commented Mar 19, 2021 at 21:48
  • 1
    @JoelFan: All UTF-8 characters are 1-4 bytes so 4 bytes are sufficient to determine if the next bytes form a character or not. Commented Mar 19, 2021 at 21:50
  • 2
    Your tests will accept non-minimal UTF-8 codes as valid when they aren't. Your tests will accept the UTF-16 surrogate code points as valid and they are not valid either. And no, your tests won't confirm that the bytes are not from a different encoding such as ISO 8859-x or UTF-16. Commented Mar 19, 2021 at 21:52
  • 2
    You have if (0xC080 == c) return 1; // Accept 0xC080 as representation for '\0' — that's an invalid UTF-8 encoding of '\0' and has no place in a function that's supposed to stringently check for validity. Commented Mar 20, 2021 at 14:34

4 Answers 4

3

Self-Response

To show why I believe this is correct, I'll summarize here my reasoning. Please point out anything that I might have missed.

I will try to show that:

  1. All valid encodings are accepted (easier).
  2. All invalid encodings are rejected (trickier).

This is the code for reference:

1:  if (c <= 0x7F) return 1;
2:  if (0xC080 == c) return 1;   // Accept 0xC080 as representation for '\0'
3:  if (0xC280 <= c && c <= 0xDFBF) return ((c & 0xE0C0) == 0xC080);
4:  if (0xEDA080 <= c && c <= 0xEDBFBF) return 0; // Reject UTF-16 surrogates
5:  if (0xE0A080 <= c && c <= 0xEFBFBF) return ((c & 0xF0C0C0) == 0xE08080);
6:  if (0xF0908080 <= c && c <= 0xF48FBFBF) return ((c & 0xF8C0C0C0) == 0xF0808080);
7:  return 0;

1) All valid encodings are accepted

Breaking down by the number of encoding bytes, I'll show that the valid encodings for the range U+000000 - U+10FFFF are accepted.

1a) 1-byte (U+0000 - U+007F)

Valid ASCII encoding (ranging from 0x00 to 0x7F) are accepted by line 1.

1b) 2-bytes (U+0080 - U+07FF)

Correct encodings for U+0080 is 0xC280, for U+07FF is 0xDFBF all the in-between codepoints are within this range due the UTF-8 encoding properties.
This is checked in line 3.
A valid encoding in this range must be in the form 110xxxxx 10xxxxxx meaning that masking the x bits we must have:

110xxxxx 10xxxxxx  &
11100000 11000000      <-- 0xE0C0
-------- --------
11000000 10000000      <-- 0xC080

Hence, all valid 2-bytes encoding are accepted by line 3.

Line 2 manages the special case for Modified UTF-8 that encodes U+0000 as 0xC080 (see https://en.wikipedia.org/wiki/UTF-8#Modified_UTF-8 ).

1c) 3-bytes (U+0800 - U+FFFF)

Correct encodings for U+0800 is 0xE0A080, for U+FFFF is 0xEFBFBF all the in-between codepoints are within this range due the UTF-8 encoding properties.
This is checked in line 3.
A valid encoding in this range must be in the form 1110xxxx 10xxxxxx 10xxxxxx meaning that masking the x bits we must have:

1110xxxx 10xxxxxx 10xxxxxx  &
11110000 11000000 11000000     <-- 0xF0C0C0
-------- -------- --------
11100000 10000000 10000000     <-- 0xE08080

Hence, all valid 3-bytes encoding are accepted by line 5.

1d) 4-bytes (U+010000 - U+10FFFF)

Correct encodings for U+010000 is 0xF0908080, for U+10FFFF is 0xF48FBFBF all the in-between codepoints are within this range due the UTF-8 encoding properties.
This is checked in line 3.
A valid encoding in this range must be in the form 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx meaning that masking the x bits we must have:

11110xxx 10xxxxxx 10xxxxxx 10xxxxxx  &
11111000 11000000 11000000 11000000     <-- 0xF8C0C0C0
-------- -------- -------- --------
11110000 10000000 10000000 10000000     <-- 0xF0808080

Hence, all valid 4-bytes encoding are accepted by line 6.

2) All invalid encodings are rejected

This is more tricky. I'll break them down by types of invalidity.

2a) Non ASCII single byte value (0x80 - 0xFF)

This includes:

  • possible stray continuation byte (0x80-0xBF)
  • invalid start byte (0xC0-0xC1, 0xF5-0xFF)
  • valid starting byte (0xC2-0xF4) not followed by a continuation byte

None of this values are in the range accepted by the lines 1-6, then line 7 will reject them.

2b) Missing continuation bytes

The case for having no continuation bytes at all is covered in 2a
If a supposedly 3-byte encoding is missing one, it means that the candidate codepoint is in the range 0xE000-0xEFFF which is not accepted by any of the line 1-6 and, hence, is rejected.

If a supposedly 4-byte encoding is missing two, it means that the candidate codepoint is in the range 0xF000-0xFFFF which is not accepted by any of the line 1-6 and, hence, is rejected.

If a supposedly 4-byte encoding is missing one, it means that the candidate codepoint is in the range 0xF00000-0xFFFFFF which is not accepted by any of the line 1-6 and, hence, is rejected.

2c) Invalid "continuation" byte

If one of the continuation byte is outside the valid range (0x80-0xBF) it wil be rejected by the masking operation in lines 3,5 and 6.

For example for 0xC26A (which is in the range accepted by line 3) the value 0x6A is invalid. In fact it will be rejected because:

11000010 01101010  &   <-- 0xC26A
11100000 11000000      <-- 0xE0C0
-------- --------
11000000 01000000      <-- 0xC040 (expected 0xC080)

Similarly for 0xE3DE82 (which is in the range accepted by line 5) the value 0xDE is invalid. In fact it will be rejected because:

11100011 11011110 10000010  &  <-- 0xE3DE82
11110000 11000000 11000000     <-- 0xF0C0C0
-------- -------- --------
11100000 11000000 10000000     <-- 0xE0C080 (expected 0xE08080)

Any value outside 0x80-0xBF when masked with 0xC0 will result in a value different from 0x80 and it will be rejected.

2d) UTF-16 surrogates

Their encodings are explicitly rejected by line 4.

2e) Overlong encodings

To create an overlong (invalid) encoding, the codepoint is extended to the left with 0s and then the encoding for the corresponding number of bits is used.

For example, let's say we want to create a 2-bytes encoding for 'A' (U+41).
We consider the codepoint to be on 11 bits (below named abcdefhijk from the least to the most significant one) and use the encoding rules for 2 bytes:

 |----------| 11 bits
 kji hgfedcba -> 110kjihg 10fedcba
 000 01000001 -> 11000001 10000001   (U+41 -> 0xC181)

but since the bits from k to h are 0, the resulting code will be always lower than 0xC280 and, hence, not in any range accepted by lines 1-6.

As another example, let's build a 3-byte encoding for the letter 'è' (U+E8):

   |--------------| 16 bits
   ponmlkj hgfedcba -> 1110ponm 10lkjihg 10fedcba
   0000000 11101000 -> 11100000 10000011 10101000   (U+E8 -> 0xE083A4)

Which has the bits from p to l equal to 0 and, hence, is outside the accepeted range (it is lower than E0A080, the minimun 3-byte encoding).

In other words: any overlong encoding is rejected as it would be lower than the minimun encoding values accepted by lines 1-6.

2f) Codepoints above U+10FFFF

Their encoding will be greater than 0xF48FBFBF and, hence, not in the range of any accepted value.

1

UTF-8 is defined in RFC 3629, and equivalently in the Unicode standard and in ISO 10646. The first has the advantage of using a simple ABNF description of the syntax for what byte sequences are valid. Your function will have to replicate this, which has no easy shortcuts by working with a 32-bit integer as input; the obvious solution is to break it back down into bytes and execute a DFA on them. There are some optimized vectorized implementations working on whole vectors, but they depend on ability to do range checks on individual bytes within the vector, which is not easy to implement with 32-bit arithmetic.

5
  • Thanks, the point is that I believe my code does exactly follow what's in that descriptions, just does it by looking at the encoded codepoint as a whole. I might be wrong but I've not been able to find any example where my code fails and I was hoping that our collective wisdom could see where I'm wrong.
    – Remo.D
    Commented Mar 19, 2021 at 22:56
  • @Remo.D: Your code does not do anything close to that. Try Jonathan Leffler's suggestion of test vectors. Commented Mar 20, 2021 at 13:35
  • For example, 0xC2C0 and 0xC341 are between 0xC280 and 0xDFBF but are not valid encodings. Commented Mar 20, 2021 at 13:37
  • 0xC2C0 will be rejected because 0xC2C0 & 0xE0C0 == 0xC0C0 which is not 0xC080 (see the test). The same goes for 0xC341 because 0xC341 & 0xE0C0 is 0xC040 which is not 0xC080. So, the two examples you provided are correctly rejected.
    – Remo.D
    Commented Mar 20, 2021 at 15:14
  • And sorry, I meant I believe I do the same checks indicated there, not "exactly the same thing". My bad for the the poor wording.
    – Remo.D
    Commented Mar 20, 2021 at 15:54
0

I'm not sure of what your total requirements are, but the way to recognize a valid UTF-8 code point is to count the number of leading 1 bits on the first byte to tell you the length of the sequence. Then each subsequent byte in the sequence must start with "10".

(If the first byte starts with a leading "0", then it's a 1-byte sequence, aka ASCII)

9
  • That's a necessary but not sufficient condition for validity. Commented Mar 19, 2021 at 22:02
  • @R..GitHubSTOPHELPINGICE, I think it is sufficient. If every sequence in the string follows those rules, it is a valid UTF-8 string. I guess you could also make sure that none of the code points have the value of UTF-16 surrogates, or are non-minimal UTF-8, if that's what you mean. But if you find a string like that, it's most likely not valid in any standard encoding.
    – JoelFan
    Commented Mar 19, 2021 at 22:04
  • 1
    No, it is not sufficient. The rules for validity are complex. C0, C1 and F5-FF are never valid. After E0 only A0-BF are valid. After ED only 80-9F are valid. After F0 only 90-BF are valid. After F4 only 80-8F are valid. Commented Mar 19, 2021 at 22:10
  • @R..GitHubSTOPHELPINGICE, I added "check for surrogate" and "check for non-minimal UTF-8" in my comment above. I think that covers all your examples of invalid bytes. It is not supposed to be "complex"
    – JoelFan
    Commented Mar 19, 2021 at 22:14
  • Those two conditions fail to cover the invalidity of F5-FF. Commented Mar 19, 2021 at 22:15
0

To decode a utf-8 byte sequence into code points, a prefix of 1 bits, followed by a 0 bit is used in the first byte of the sequence

0xxxxxxx  <-- code point is 7 bit only, and can be in the range \u0000 to \u007f
110xxxxx  10xxxxxx  <-- code point is 11 bit only, and can be in the range \u0080 to \u007ff
1110xxxx  10xxxxxx 10xxxxxx  <-- code point is 16 bit and can be in the range \u0800 to \uffff
11110xxx  10xxxxxx 10xxxxxx 10xxxxxx <-- codepoint is 21bit and can be in the range \U00010000 to \U0010ffff

Think that it is illegal to encode a utf-8 sequence more bytes than the minimum necessary. So encoding \u0000 as

11000000 10000000

is illegal, and it should be encoded as

00000000

The decoding of 0xc3 0xa8 into the Unicode codepoint 0xc3a8 is erroneous, because you first have to eliminate the extra bits added for encoding:

   c3       a8
11000011 10101000
   vvvvv   vvvvvv  these are the bits taken to form the code point.
   |||||   ||||||
   00011   101000
   |||||  //////
   ||||| //////
   vvvvvvvvvvv
   00011101000     this is the decoded codepoint:
     0   e   8     0xe8

And it's corresponding codepoint is \u00e8.

I recommend you to read the corresponding chapter of the Unicode specification, more preciselly sections 2.4 Code Points and Characters, and 2.5 Encoding Forms, this last covering the different encodings of Unicode.

1
  • 1
    Thanks Luis. The point you make are covered in the section 2e) of my self-response. If a code is illegal because it's a non-minimal one, it is rejected because it will be necessarily lower than the minimal valid encoding of the same length. The code above is not for decoding, it's for checking the validity of the encoding. Can you spot an invalid encoding that my code will accept as valid (or a valid encoding that it will rejects as invalid)?
    – Remo.D
    Commented Mar 21, 2021 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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