Decoding UTF-8. Part VII: Validation

In part VI of the UTF-8 decoding series we saw how a simple non-validating decoder might look like, but we emphasized the importance of validation. It is important to remember that in general we cannot assume that a stream of bytes represents valid UTF-8 encoded text. We need to be able to recognize any invalid UTF-8 sequence and deal with it.

To validate a UTF-8 string we have to perform the following three kinds of checks:

• The byte sequence is well-formed.
• Decoding results in a valid Unicode code point
• The code point is encoded in the minimal number of bytes (no overlong encoding).

Let’s look at them in some detail.

Validity of Bytes in the Sequence

As we have seen in the Part I, a valid UTF-8 encoding of a Unicode code point consists of a leading byte followed by a number of continuation bytes.

We start the check for validity of a byte sequence by looking at the lead byte. A valid lead byte has to start with one of the following bit fields:

• 0, in which case the lead byte alone encodes a code point.
• 110, which starts a two-byte sequence.
• 1110, which starts a three-byte sequence
• 11110, which starts a four-byte sequence.

Lead bytes that start with any other bit combination are invalid.

Once we establish the validity of the lead byte and compute the expected sequence length, we can perform the next important check: ensure the expected number of valid continuation bytes. A valid continuation byte starts with bits 10 and therefore falls in the range 0x80-0xBF.

Depending on the value of the lead byte, we expect between 0 and 3 continuation bytes to follow. If there are fewer, it means we have an incomplete sequence; if there are more, we have detected unexpected continuation bytes.

Validity of Decoded Code Points

Some well-formed UTF-8 sequences are decoded into invalid Unicode code points:

• Values greater than U+10FFFF.
• UTF-16 surrogates.

Unicode 2.0 and later support code points in the range U+0000-U+10FFFF. A well-formed UTF-8 sequence can be used to encode values that fall outside the range and therefore must be detected and reported as invalid.

Code points in the range U+D800-U+DFFF are reserved for use by UTF-16 encoding scheme as surrogate pairs. They cannot be used as standalone code points, and any UTF-8 sequence that is decoded to that range is invalid.

An interesting category to consider is noncharacters. These code points are reserved for internal use but can be interchanged and do not cause ill-formed Unicode texts. Some validators still reject them: the current version of Markus Kuhn's UTF-8 decoder capability and stress test calls them “a potential security risk, depending on what use is made of these codes subsequently”. Yet, as they are explicitly called out as valid code points by the Unicode standard, we are not going to reject them.

Overlong Sequences

If a Unicode code point is encoded with more bytes than necessary, we have an overlong encoding. For instance, the code point value for ‘A’ (U+0041) could be encoded as:

• 0x41 (0[1000001])
• 0xC1 0x81 (110[00001] 10[000001])
• 0xE0 0x81 0x81 (1110[0000] 10[000001] 10[000001])

Only the one-byte version is legal - the other two are overlong sequences, constructed by padding zeroes and must be rejected by a validator.

An obvious way to check for an overlong sequence is to complete the decoding and then check that the decoded value corresponds to an expected sequence length. That’s what we would do in a validating decoder.

If we are interested in validating without decoding, the task is easier. Overlong sequences can happen in the following three cases:

• if a two-byte sequence starts with 0xC0 or 0xC1 it is overlong.
• if a three-byte sequence starts with 0xE0 and the first continuation byte is in range [0x80, 0x9F]
• if a four-byte sequence starts with 0xF0 and the first continuation byte is in range [0x80, 0x9F].

Algorithm for Validating UTF-8 Sequences

Validating UTF-8 can be performed as a part of decoding, or as a separate process. Here we examine a straightforward approach to validating without fully decoding. The algorithm:

• Lead starts with bit 0; valid sequence.
• Lead starts with bits 110: two-byte sequence
  • 0xC0 or 0xC1: overlong two-byte sequence; invalid sequence.
  • No continuation bytes: incomplete sequence; invalid sequence.
  • One continuation byte; valid sequence.
• Lead starts with 1110: three-byte sequence
  • If 0xE0
    • First continuation byte in range [0x80, 0x9F]: overlong three-byte sequence; invalid sequence.
  • If 0xED
    • First continuation byte in range [0xA0, 0xBF]: UTF-16 surrogate: invalid sequence.
  • Less than two continuation bytes: incomplete sequence; invalid sequence.
  • Two continuation bytes: valid sequence.
• Lead starts with 11110: four-byte sequence
  • If 0xF0
    • First continuation byte in range [0x80, 0x9F]: overlong four-byte sequence; invalid sequence.
  • If in range [0xF5, 0xF7] code points above U+10FFFF; invalid sequence.
  • Less than three continuation bytes: incomplete sequence; invalid sequence.
• Lead starts with invalid prefix: invalid sequence.

Code example

A C function that would implement the algorithm above could look like:

/* Returns 0 if invalid, or sequence length if valid */
int validate_utf8_sequence(const char *str)
{
    const unsigned char *s = (const unsigned char *)str;
    unsigned char c0 = s[0];

    /* Empty string: no code point */
    if (c0 == '\0')
        return 0;

    /* ASCII */
    if ((c0 & 0x80) == 0)
        return 1;

    /* Two‑byte: 110xxxxx */
    if ((c0 & 0xE0) == 0xC0) {
        if (s[1] == '\0')
            return 0; /* truncated */

        unsigned char c1 = s[1];

        if (c0 == 0xC0 || c0 == 0xC1)
            return 0; /* overlong */

        if ((c1 & 0xC0) != 0x80)
            return 0;

        return 2;
    }

    /* Three‑byte: 1110xxxx */
    if ((c0 & 0xF0) == 0xE0) {
        if (s[1] == '\0' || s[2] == '\0')
            return 0; /* truncated */

        unsigned char c1 = s[1];
        unsigned char c2 = s[2];

        if ((c1 & 0xC0) != 0x80)
            return 0;

        if (c0 == 0xE0) {
            if (c1 < 0xA0)
                return 0; /* overlong */
        } else if (c0 == 0xED) {
            if (c1 >= 0xA0)
                return 0; /* surrogate */
        }

        if ((c2 & 0xC0) != 0x80)
            return 0;

        return 3;
    }

    /* Four‑byte: 11110xxx */
    if ((c0 & 0xF8) == 0xF0) {
        if (s[1] == '\0' || s[2] == '\0' || s[3] == '\0')
            return 0; /* truncated */

        unsigned char c1 = s[1];
        unsigned char c2 = s[2];
        unsigned char c3 = s[3];

        if (c0 == 0xF0) {
            if (c1 < 0x90)
                return 0; /* overlong */
        } else if (c0 == 0xF4) {
            if (c1 > 0x8F)
                return 0; /* > U+10FFFF */
        } else if (c0 >= 0xF5) {
            return 0; /* invalid lead */
        }

        if ((c1 & 0xC0) != 0x80)
            return 0;
        if ((c2 & 0xC0) != 0x80)
            return 0;
        if ((c3 & 0xC0) != 0x80)
            return 0;

        return 4;
    }
    /* Invalid lead byte */
    return 0;
}

Inspecting assembly of the function does not show anything interesting. Lots of branches, but as we have seen, modern CPUs handle branches surprisingly well.

In the next post of the series, we’ll look at a validating decoder.

We examined the process of computing the sequence length from the lead byte in several earlier posts.