Find longest UTF-8 sequence without breaking multi-byte sequences

Update 2019-06-24: After a night's sleep, the problem appears to be far easier than my first attempt made it look. I've left the previous answer below for historic reasons.

The UTF-8 encoding is self-synchronizing. This makes it possible to determine, whether an arbitrarily chosen code unit in a symbol stream is the beginning of a code sequence. A UTF-8 sequence can be split to the left of the beginning of a code sequence.

The beginning of a code sequence is either an ASCII character (0xxxxxxxb), or a leading byte (11xxxxxxb) in a multi-byte sequence. Trailing bytes follow the pattern 10xxxxxxb. The beginning of a UTF-8 encoding satisfies the condition (code_unit & 0b11000000) != 0b10000000, in other words: It's not a trailing byte.

The longest UTF-8 sequence no longer than a requested byte count can be determined in constant time (O(1)) by applying the following algorithm:

1. If the input is no longer than the requested byte count return the actual byte count.
2. Otherwise, loop towards the beginning (starting one code unit past the requested byte count), until we find the beginning of a sequence. Return the byte count towards the left the beginning of the sequence.

Put in code:

#include <string_view>

size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
    // 1. Input no longer than max byte count
    if (sv.size() <= max_byte_count)
    {
        return sv.size();
    }

    // 2. Input longer than max byte count
    while ((sv[max_byte_count] & 0b11000000) == 0b10000000)
    {
        --max_byte_count;
    }
    return max_byte_count;
}

This test code

#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>

int main()
{
    using namespace std::literals::string_view_literals;

    std::cout << "max size output\n=== ==== ======" << std::endl;

    auto test{u8"€«test»"sv};
    for (size_t count{0}; count <= test.size(); ++count)
    {
        auto byte_count{find_max_utf8_length(test, count)};
        std::cout << std::setw(3) << std::setfill(' ') << count
                  << std::setw(5) << std::setfill(' ') << byte_count
                  << " " << std::string(begin(test), byte_count) << std::endl;
    }
}

produces the following output:

max size output
=== ==== ======
  0    0 
  1    0 
  2    0 
  3    3 €
  4    3 €
  5    5 €«
  6    6 €«t
  7    7 €«te
  8    8 €«tes
  9    9 €«test
 10    9 €«test
 11   11 €«test»

This algorithm operates on the UTF-8 encoding alone. It does not attempt to process Unicode in any way. While it will always produce a valid UTF-8 encoding sequence, the encoded code points may not form a meaningful Unicode grapheme.

The algorithm completes in constant time. Irrespective of the input size, the final loop will spin at most 3 times, given the current limit of at most 4 bytes per UTF-8 encoding. The algorithm will continue to work and complete in constant time, in case the UTF-8 encoding is ever changed to allow for up to 5 or 6 bytes per encoded code point.

Previous answer

This can be done in O(1), by decomposing the problem into the following cases:

1. The input is no longer than the requested byte count. Simply return the input in this case.
2. The input is longer than the requested byte count. Find out the relative location within an encoding at index max_byte_count - 1:
   1. If this is an ASCII character (highest bit not set 0xxxxxxxb), we are at a natural boundary, and can cut the string right after it.
   2. Otherwise, we are either at the start, middle, or tail of of a multi-byte sequence. To find out where, consider the following character. If it is an ASCII character (0xxxxxxxb) or the start of a multi-byte sequence (11xxxxxxb), we are at the tail of a multi-byte sequence, a natural boundary.
   3. Otherwise, we are either at the start or middle of a multi-byte sequence. Iterate towards the beginning of the string, until we find the start of a multi-byte encoding (11xxxxxxb). Cut the string before that character.

The following code calculates the length of the truncated string, given a maximum byte count. The input needs to form a valid UTF-8 encoding.

#include <string_view>

size_t find_max_utf8_length(std::string_view sv, size_t max_byte_count)
{
    // 1. No longer than max byte count
    if (sv.size() <= max_byte_count)
    {
        return sv.size();
    }

    // 2. Longer than byte count
    auto c0{static_cast<unsigned char>(sv[max_byte_count - 1])};
    if ((c0 & 0b10000000) == 0)
    {
        // 2.1 ASCII
        return max_byte_count;
    }

    auto c1{static_cast<unsigned char>(sv[max_byte_count])};
    if (((c1 & 0b10000000) == 0) || ((c1 & 0b11000000) == 0b11000000))
    {
        // 2.2. At end of multi-byte sequence
        return max_byte_count;
    }

    // 2.3. At start or middle of multi-byte sequence
    unsigned char c{};
    do
    {
        --max_byte_count;
        c = static_cast<unsigned char>(sv[max_byte_count]);
    } while ((c & 0b11000000) != 0b11000000);
    return max_byte_count;
}

The following test code

#include <iostream>
#include <iomanip>
#include <string_view>
#include <string>

int main()
{
    using namespace std::literals::string_view_literals;

    std::cout << "max size output\n=== ==== ======" << std::endl;

    auto test{u8"€«test»"sv};
    for (size_t count{0}; count <= test.size(); ++count)
    {
        auto byte_count{find_max_utf8_length(test, count)};
        std::cout << std::setw(3) << std::setfill(' ') << count
                  << std::setw(5) << std::setfill(' ') << byte_count
                  << " " << std::string(begin(test), byte_count) << std::endl;
    }
}

produces this output:

max size output
=== ==== ======
  0    0 
  1    0 
  2    0 
  3    3 €
  4    3 €
  5    5 €«
  6    6 €«t
  7    7 €«te
  8    8 €«tes
  9    9 €«test
 10    9 €«test
 11   11 €«test»