Decoding UTF-8. Part VIII: Validating Decoder

In part VII of the series, we saw how to validate a UTF-8 sequence, that is to ensure it can be safely decoded into a Unicode code point. In part VI, we set validation aside and saw how a non-validating decoder would look like. Now it is time to investigate a decoding validator - e.g. decode a UTF-8 sequence without assuming it is valid.

An obvious approach would be to perform the two steps sequentially: first validate the sequence, then decode it using the non‑validating decoder. That is a reasonable strategy, especially if the string will be decoded more than once or if subsequent operations assume valid UTF‑8. However, if all we want to do is decode a byte sequence once, we can do better by validating while decoding.

Intermixing decoding with validation is not hard, once we have figured out both steps. We can start from the validation algorithm and add composition of the code point value in the “valid sequence” branches. Here is how it is implemented in the utfcpp library:

    template 
    utf_error decode_next(octet_iterator& it, octet_iterator end, utfchar32_t& cp)
    {
        if (it == end)
            return NOT_ENOUGH_ROOM;

        // Save the original value of it so we can go back in case of failure
        // Of course, it does not make much sense with i.e. stream iterators
        octet_iterator original_it = it;

        cp = 0;
        // Determine the sequence length based on the lead octet
        const int length = utf8::internal::sequence_length(it);

        // Get trail octets and calculate the code point
        utf_error err = UTF8_OK;
        switch (length) {
            case 0:
                return INVALID_LEAD;
            case 1:
                err = utf8::internal::get_sequence_1(it, end, cp);
                break;
            case 2:
                err = utf8::internal::get_sequence_2(it, end, cp);
            break;
            case 3:
                err = utf8::internal::get_sequence_3(it, end, cp);
            break;
            case 4:
                err = utf8::internal::get_sequence_4(it, end, cp);
            break;
        }

        if (err != UTF8_OK) {
        // Failure branch - restore the original value of the iterator
            it = original_it;
            cp = 0;
            return err;
        }

        it++; // Successfully parsed the sequence, advance the iterator
        return UTF8_OK;
    }

The sequence_length() function is similar to what we saw in Part II: Determining Sequence Length - a Straightforward Approach: based on the lead byte value, it returns the expected length of the sequence or 0 in case of an invalid lead. More interesting are the get_sequence_n functions. Here is get_sequence_2():

    template 
    utf_error get_sequence_2(octet_iterator& it, octet_iterator end, utfchar32_t& code_point)
    {
        if (it == end)
            return NOT_ENOUGH_ROOM;

        const utfchar8_t lead = utf8::internal::mask8(*it);
        code_point = static_cast(lead);

        UTF8_CPP_INCREASE_AND_RETURN_ON_ERROR(it, end)

        const utfchar8_t trail1 = utf8::internal::mask8(*it);
        code_point = ((code_point << 6) & 0x7ff) + (trail1 & 0x3f);

        if (lead == 0xC0 || lead == 0xC1) {
            return OVERLONG_SEQUENCE;
        }

        return UTF8_OK;
    }

Note how we scan for errors as we decode: after we set the initial value of the code point based on the lead byte, there is a checked advancement to the trail byte that ensures a valid trail byte exists. Then, after getting the trail byte and calculating the code point, we check for an overlong sequence based on the lead byte. If get_sequence_2 returns successfully, there is no need for additional checks for validity of the code point.

Let’s look at the generated machine code (aarch64 on Linux). I built the apitests executable with debug symbols and then searched for decode_next:

$ objdump -t --demangle build/tests/apitests | grep -F 'decode_next'
000000000000a2f8  w    F .text  0000000000000208     utf8::internal::utf_error utf8::internal::decode_next(char const*&, char const*, char32_t&)
000000000000a964  w    F .text  0000000000000208     uf8::internal::utf_error utf8::internal::decode_next(char*&, char*, char32_t&)

We got two specializations: the char const* specialization at 0xa2f8 and the char* specialization at 0xa964. They are identical: only their addresses and template types are different.

With that information, I disassembled one of the specializations:

$  objdump --demangle --source --line-numbers --disassemble   --start-address=0xa2f8 --stop-address=0xa500 build/tests/apitests

build/tests/apitests:     file format elf64-littleaarch64


Disassembly of section .text:

000000000000a2f8 (char const*&, char const*, char32_t&)>:
utf8::internal::utf_error utf8::internal::decode_next(char const*&, char const*, char32_t&):
/home/ntrif/utfcpp/tests/../source/utf8/core.h:268
    #undef UTF8_CPP_INCREASE_AND_RETURN_ON_ERROR

    template 
    utf_error decode_next(octet_iterator& it, octet_iterator end, utfchar32_t& cp)
    {
        if (it == end)
    a2f8:       f9400009        ldr     x9, [x0]
    a2fc:       eb01013f        cmp     x9, x1
    a300:       54000160        b.eq    a32c (char const*&, char const*, char32_t&)+0x34>  // b.none
...

The listing is pretty long; as expected for header-only C++ code, the function calls are fully inlined. Instead of showing the entire dump here, let’s focus on a few interesting points:

As expected, (see When Compilers Disagree About UTF-8), there is a shortcut for the ASCII range:

a308: 39c0012a        ldrsb   w10, [x9]        // load lead byte
a30c: 12001d48        and     w8, w10, #0xff   // mask8
a310: 37f8012a        tbnz    w10, #31, a334   // if top bit is set, not ASCII - bail out
a314: aa0903ea        mov     x10, x9          // ASCII case
a318: b9000048        str     w8, [x2]         // cp = lead
a31c: 91000549        add     x9, x10, #1      // it++
a320: f9000009        str     x9, [x0]         // store iterator
a324: 2a1f03e0        mov     w0, wzr          // return UTF8_OK
a328: d65f03c0        ret

It is the TBNZ instruction that “recognizes” an ASCII code point and sends the code to the no-validation path.

The C++ function that is used to check whether a byte is a valid UTF-8 trail:

    template
    inline bool is_trail(octet_type oc)
    {
        return ((utf8::internal::mask8(oc) >> 6) == 0x2);
    }

after inlining ends up as:

a354: 3940014b        ldrb    w11, [x10]       // load trail byte
a358: 121a056c        and     w12, w11, #0xc0  // mask top two bits
a35c: 7102019f        cmp     w12, #0x80       // must be 10xxxxxx
a360: 54000c21        b.ne    a4e4             // INVALID_TRAIL

Pretty much nothing exciting - straightforward C++ code being well optimized. We did not use any tricks to avoid branching or use non-portable techniques like SIMD. The combination of inlining, predictable branches, and the ASCII shortcut gives good throughput without sacrificing portability.