company_banner

Валидация UTF-8 меньше чем за одну инструкцию на байт



    Даниэль Лемир – профессор Заочного квебекского университета (TÉLUQ), придумавший способ очень быстро парсить double – совместно с инженером Джоном Кайзером из Microsoft опубликовали ещё одну свою находку: валидатор UTF-8, обгоняющий библиотеку UTF-8 CPP (2006) в 48..77 раз, ДКА от Бьёрна Хёрманна (2009) – в 20..45 раз, и алгоритм Google Fuchsia (2020) – в 13..35 раз. Новость об этой публикации на хабре уже постили, но без технических подробностей; так что восполняем этот недочёт.

    Требования UTF-8


    Для начала вспомним, что Unicode допускает code points от U+0000 до U+10FFFF, которые кодируются в UTF-8 последовательностями от 1 до 4 байтов:

    Число байтов в кодировке Число битов в code point Минимальное значение Максимальное значение
    1 1..7 U+0000 = 00000000 U+007F = 01111111
    2 8..11 U+0080 = 11000010 10000000 U+07FF = 11011111 10111111
    3 12..16 U+0800 = 11100000 10100000 10000000 U+FFFF = 11101111 10111111 10111111
    4 17..21 U+010000 = 11110000 10010000 10000000 10000000 U+10FFFF = 11110100 10001111 10111111 10111111

    По правилам кодирования, старшие биты первого байта последовательности определяют общее количество байтов в последовательности; нулевой старший бит может быть только у однобайтных (ASCII) символов, единичные два старших бита обозначают многобайтного символа, единичный и нулевой – продолжающий байт> многобайтного символа.

    Какого рода ошибки могут быть в строке, закодированной таким образом?

    1. Незаконченная последовательность: на месте, где ожидался продолжающий байт, встретился ведущий байт или ASCII-символ;
    2. Неначатая последовательность: на месте, где ожидался ведущий байт или ASCII-символ, встретился продолжающий байт;
    3. Слишком длинная последовательность: ведущий байт 11111xxx соответствует пятибайтной или более длинной последовательности, запрещённой в UTF-8;
    4. Выход за границы Unicode: после расшифровки четырёхбайтной последовательности получился code point выше U+10FFFF.

    Если в строке нет ни одной из этих четырёх ошибок, то её можно расшифровать в последовательность корректных code points. UTF-8, однако, требует большего – чтобы каждая последовательность корректных code points кодировалась единственным образом. Это добавляет ещё два рода возможных ошибок:

    1. Неминимальная последовательность: для расшифрованного code point возможна более короткая кодировка;
    2. Суррогаты: code points в диапазоне от U+D800 до U+DFFF зарезервированы для UTF-16, и последовательность из двух таких суррогатов обозначает code point выше U+FFFF. UTF-8 требует, чтобы такие code points кодировались напрямую, а не как пары суррогатов.

    В редко используемой кодировке CESU-8 последнее требование отменено (а в MUTF-8 – ещё и предпоследнее), благодаря чему длина последовательности ограничена тремя байтами, но расшифровка и валидация строк усложняются. Например, смайлик U+1F600 GRINNING FACE представляется в UTF-16 парой суррогатов 0xD83D 0xDE00, и CESU-8/MUTF-8 переводят её в пару трёхбайтных последовательностей 0xED 0xA0 0xBD 0xED 0xB8 0x80; но в UTF-8 этот смайлик кодируется одной четырёхбайтной последовательностью 0xF0 0x9F 0x98 0x80.

    Для каждого рода ошибки ниже перечислены последовательности битов, которые к ней приводят:
    Незаконченная последовательность Недостаёт 2-ого байта 11xxxxxx 0xxxxxxx
    11xxxxxx 11xxxxxx
    Недостаёт 3-его байта 111xxxxx 10xxxxxx 0xxxxxxx
    111xxxxx 10xxxxxx 11xxxxxx
    Недостаёт 4-ого байта 1111xxxx 10xxxxxx 10xxxxxx 0xxxxxxx
    1111xxxx 10xxxxxx 10xxxxxx 11xxxxxx
    Неначатая последовательность Лишний 2-ой байт 0xxxxxxx 10xxxxxx
    Лишний 3-ий байт 110xxxxx 10xxxxxx 10xxxxxx
    Лишний 4-ый байт 1110xxxx 10xxxxxx 10xxxxxx 10xxxxxx
    Лишний 5-ый байт 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx
    Слишком длинная последовательность 11111xxx
    Выход за границы Unicode U+110000..U+13FFFF 11110100 1001xxxx
    11110100 101xxxxx
    ≥ U+140000 11110101
    1111011x
    Неминимальная последовательность 2-байтная 1100000x
    3-байтная 11100000 100xxxxx
    4-байтная 11110000 1000xxxx
    Суррогаты 11101101 101xxxxx


    Валидация UTF-8


    При наивном подходе, использованном в библиотеке UTF-8 CPP серба Неманьи Трифуновича, валидация выполняется каскадом вложенных ветвлений:

    const octet_difference_type 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) {
        // Decoding succeeded. Now, security checks...
        if (utf8::internal::is_code_point_valid(cp)) {
            if (!utf8::internal::is_overlong_sequence(cp, length)){
                // Passed! Return here.
    

    Внутри sequence_length() и is_overlong_sequence() тоже ветвления в зависимости от длины последовательности. Если во входной строке непредсказуемо чередуются последовательности разной длины, то предсказатель переходов не сможет избежать сброса конвеера по нескольку раз на каждом обрабатываемом символе.

    Более эффективный подход к валидации UTF-8 заключается в использовании конечного автомата из 9 состояний: (состояние ошибки на диаграмме не показано)



    Когда таблица переходов автомата составлена, то код валидатора получается очень простым:

    uint32_t type = utf8d[byte];
    *codep = (*state != UTF8_ACCEPT) ?
      (byte & 0x3fu) | (*codep << 6) :
      (0xff >> type) & (byte);
    *state = utf8d[256 + *state + type];
    

    Здесь для каждого обрабатываемого символа повторяются одни и те же действия, без условных переходов – поэтому сбросов конвеера не потребуется; с другой стороны, на каждой итерации осуществляется дополнительный доступ к памяти (к таблице переходов utf8d) впридачу ко чтению входного символа.

    Лемир и Кайзер взяли за основу своего валидатора этот же ДКА, и достигли ускорения в десятки раз за счёт применения трёх усовершенствований:

    1. Таблицу переходов удалось ужать с 364 байтов до 48, так что она целиком помещается в трёх векторных регистрах (по 128 бит), и обращения к памяти требуются только для чтения входных символов;
    2. Блоки по 16 соседних байтов обрабатываются параллельно;
    3. Если 16-байтный блок целиком состоит из ASCII-символов – то он заведомо корректный, и нет нужды в более тщательной проверке. Этот «срез пути» ускоряет обработку «реалистичных» текстов, содержащих целые предложения латиницей, в два-три раза; но на случайных текстах, где латиница, иероглифы и смайлики равномерно перемешаны, это ускорения не даёт.

    В реализации каждого из этих усовершенствований есть неочевидные тонкости, так что их стоит рассмотреть подробно.

    Уменьшение таблицы переходов


    Первое усовершенствование основывается на том наблюдении, что для обнаружения большинства ошибок (12 недопустимых последовательностей битов из 19 перечисленных в таблице выше) достаточно проверить 12 первых битов последовательности:
    Незаконченная последовательность Недостаёт 2-ого байта 11xxxxxx 0xxxxxxx 0x02
    11xxxxxx 11xxxxxx
    Неначатая последовательность Лишний 2-ой байт 0xxxxxxx 10xxxxxx 0x01
    Слишком длинная последовательность 11111xxx 1000xxxx 0x20
    11111xxx 1001xxxx 0x40
    11111xxx 101xxxxx
    Выход за границы Unicode U+1[1235679ABDEF]xxxx 111101xx 1001xxxx
    111101xx 101xxxxx
    U+1[48C]xxxx 11110101 1000xxxx 0x20
    1111011x 1000xxxx
    Неминимальная последовательность 2-байтная 1100000x 0x04
    3-байтная 11100000 100xxxxx 0x10
    4-байтная 11110000 1000xxxx 0x20
    Суррогаты 11101101 101xxxxx 0x08

    Каждой из этих возможных ошибок исследователи присвоили один из семи битов, как показано в самом правом столбце. (Присвоенные биты различаются между их опубликованной статьёй и их кодом на GitHub; здесь взяты значения из статьи.) Для того, чтобы обойтись семью битами, два подслучая выхода за границы Unicode пришлось переразбить так, чтобы второй объединялся с 4-байтной неминимальной последовательностью; а случай слишком длинной последовательности разбит на три подслучая и объединён с подслучаями выхода за границы Unicode.

    Таким образом с ДКА Хёрманна были произведены следующие изменения:

    1. Вход поступает не по байту, а по тетраде (полубайту);
    2. Автомат используется как недетерминированный – обработка каждой тетрады переводит автомат между подмножествами всех возможных состояний;
    3. Восемь корректных состояний объединены в одно, зато одно ошибочное разделено на семь;
    4. Три соседние тетрады обрабатываются не последовательно, а независимо друг от друга, и результат получается как пересечение трёх множеств конечных состояний.

    Благодаря этим изменениям, для описания всех возможных переходов достаточно трёх таблиц по 16 байт: каждый элемент таблицы используется как битовое поле, перечисляющее все возможные конечные состояния. Три таких элемента объединяются по AND, и если в результате есть ненулевые биты, значит, обнаружена ошибка.
    Тетрада Значение Возможные ошибки Код
    Старшая в первом байте 0–7 Лишний 2-ой байт 0x01
    8–11 (нет) 0x00
    12 Недостаёт 2-ого байта; 2-байтная неминимальная последовательность 0x06
    13 Недостаёт 2-ого байта 0x02
    14 Недостаёт 2-ого байта; 2-байтная неминимальная последовательность; суррогаты 0x0E
    15 Недостаёт 2-ого байта; слишком длинная последовательность; выход за границы Unicode; 4-байтная неминимальная последовательность 0x62
    Младшая в первом байте 0 Недостаёт 2-ого байта; лишний 2-ой байт; неминимальная последовательность 0x37
    1 Недостаёт 2-ого байта; лишний 2-ой байт; 2-байтная неминимальная последовательность 0x07
    2–3 Недостаёт 2-ого байта; лишний 2-ой байт 0x03
    4 Недостаёт 2-ого байта; лишний 2-ой байт; выход за границы Unicode 0x43
    5–7 0x63
    8–10, 12–15 Недостаёт 2-ого байта; лишний 2-ой байт; слишком длинная последовательность
    11 Недостаёт 2-ого байта; лишний 2-ой байт; слишком длинная последовательность; суррогаты 0x6B
    Старшая во втором байте 0–7, 12–15 Недостаёт 2-ого байта; слишком длинная последовательность; 2-байтная неминимальная последовательность 0x06
    8 Лишний 2-ой байт; слишком длинная последовательность; выход за границы Unicode; неминимальная последовательность 0x35
    9 0x55
    10–11 Лишний 2-ой байт; слишком длинная последовательность; выход за границы Unicode; 2-байтная неминимальная последовательность; суррогаты 0x4D

    Остались необработанными ещё 7 недопустимых последовательностей битов:
    Незаконченная последовательность Недостаёт 3-его байта 111xxxxx 10xxxxxx 0xxxxxxx
    111xxxxx 10xxxxxx 11xxxxxx
    Недостаёт 4-ого байта 1111xxxx 10xxxxxx 10xxxxxx 0xxxxxxx
    1111xxxx 10xxxxxx 10xxxxxx 11xxxxxx
    Неначатая последовательность Лишний 3-ий байт 110xxxxx 10xxxxxx 10xxxxxx
    Лишний 4-ый байт 1110xxxx 10xxxxxx 10xxxxxx 10xxxxxx
    Лишний 5-ый байт 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx

    И здесь пригождается старший бит, предусмотрительно оставленный в таблицах переходов неиспользованным: он будет соответствовать последовательности битов 10xxxxxx 10xxxxxx, т.е. двум продолжающим байтам подряд. Теперь проверка трёх тетрад может либо обнаружить ошибку, либо дать результат 0x00 или 0x80. И вот этого результата первой проверки – вместе с первой тетрадой – нам уже достаточно:
    Недостаёт 3-его байта 111xxxxx 10xxxxxx 0xxxxxxx 111xxxxx (0x00)
    111xxxxx 10xxxxxx 11xxxxxx
    Недостаёт 4-ого байта 1111xxxx 10xxxxxx 10xxxxxx 0xxxxxxx 1111xxxx (x) (0x00)
    1111xxxx 10xxxxxx 10xxxxxx 11xxxxxx
    Лишний 3-ий байт 110xxxxx 10xxxxxx 10xxxxxx 110xxxxx (0x80)
    Лишний 4-ый байт 1110xxxx 10xxxxxx 10xxxxxx 10xxxxxx 1110xxxx (x) (0x80)
    Лишний 5-ый байт 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx 10xxxxxx (x) (0x80)
    Допустимые комбинации 111xxxxx (0x80)
    1111xxxx (x) (0x80)

    Значит, для завершения проверки достаточно убедиться, что каждый результат 0x80 соответствует одной из двух допустимых комбинаций.

    Векторизация


    Как обрабатывать блоки по 16 соседних байтов параллельно? Центральная идея состоит в том, чтобы использовать инструкцию pshufb как 16 одновременных подстановок в соответствии с 16-байтной таблицей. Для второй проверки нужно найти в блоке все байты вида 111xxxxx и 1111xxxx; поскольку на Intel нет беззнакового векторного сравнения, то оно заменяется вычитанием с насыщением (psubusb).

    Исходники simdjson тяжеловато читаются из-за того, что весь код разбит на однострочные функции. Псевдокод всего валидатора целиком выглядит примерно так:
    prev = vector(0)
    while !input_exhausted:
        input = vector(...)
        prev1 = prev<<120 | input>>8
        prev2 = prev<<112 | input>>16
        prev3 = prev<<104 | input>>24
    
        # первая проверка
        nibble1 = prev1.shr(4).lookup(table1)
        nibble2 = prev1.and(15).lookup(table2)
        nibble3 = input.shr(4).lookup(table3)
        result1 = nibble1 & nibble2 & nibble3
    
        # вторая проверка
        test1 = prev2.saturating_sub(0xDF) # 111xxxxx => >0
        test2 = prev3.saturating_sub(0xEF) # 1111xxxx => >0
        result2 = (test1 | test2).gt(0) & vector(0x80)
    
        # в result1 должны быть 0x80 на тех же местах, как и в result2,
        # и нули на всех остальных
        if result1 != result2:
            return false
    
        prev = input
    
    return true
    

    Если некорректная последовательность находится у правого края самого последнего блока, то она этим кодом не будет обнаружена. Чтобы не заморачиваться, можно дополнить входную строку нулевыми байтами так, чтобы в конце получился один полностью нулевой блок. В simdjson предпочли вместо этого реализовать особую проверку для последних байтов: для корректности строки нужно, чтобы самый последний байт был строго меньше 0xC0, предпоследний – строго меньше 0xE0, и третий с конца – строго меньше 0xF0.

    Последнее из усовершенствований, придуманных Лемиром и Кайзером – это «срез пути» для ASCII. Определить, что в текущем блоке есть только ASCII-символы, очень просто: input & vector(0x80) == vector(0). В этом случае достаточно убедиться, что нет некорректных последовательностей на границе prev и input, – и можно переходить к следующему блоку. Эта проверка осуществляется аналогично проверке в конце входной строки; беззнаковое векторное сравнение с [..., 0xС0, 0xE0, 0xC0], которого нет на Intel, заменяется на вычисление векторного максимума (pmaxub) и его сравнение с тем же вектором.

    Проверка на ASCII оказывается единственным ветвлением внутри итерации валидатора, и для успешного предсказания этого ветвления достаточно, чтобы во входной строке не чередовались блоки целиком из ASCII со блоками, содержащими не-ASCII-символы. Исследователи обнаружили, что ещё лучших результатов на реальных текстах удаётся добиться, проверяя на ASCII объединение по OR четырёх соседних блоков, и пропуская все четыре блока в случае ASCII. И действительно: можно ожидать, что если автор текста в принципе пользуется не-ASCII-символами, то они будут встречаться как минимум раз на 64 символа, чего достаточно для предсказания перехода.

    RUVDS.com
    VDS/VPS-хостинг. Скидка 10% по коду HABR

    Comments 14

      +18

      Ничего не понял, но звучит очень круто!

        +4

        Очень круто оптимизировано, но есть ли тут кто-то, кому нужна валидация UTF-8 в чистом виде? Не получение из него codepoints, не итерация по нему, не ещё что-то, а чисто валидация?

          +2

          Первое что приходит в голову: SMTP-сервер может валидировать тела писем перед доставкой адресату, HTTP-сервер может валидировать тела POST-запросов перед передачей скрипту-обработчику.

            +2

            Если нужно выполнять разбор длинного текста, где преимущественно не-ASCII символы используются, то довольно полезно иметь быструю предфильтрацию.


            Если, к примеру, вам прислали байтовый мусор, а вы большую часть входящего текста уже проитерировали и что-то с ним сделали, то обидно узнать под конец, что можно было даже не начинать получать из него codepoints или делать какой-то более ресурсоёмкий анализ

              +4

              Есть. Всякие фронты и прокси которые потом это передают дальше и отсекают всякий мусор.

                +2
                По хорошему в протоколах типа websockets должна проходить валидация для входных текстовых данных это из того с чем в последнее столкнулся.
                  +7

                  Вообще, они это для своего парсера simdjson сделали, который 3.5гига в секунду парсит, но первый шаг там — валидация UTF-8. И так хорошо получилось, что решили отдельно описать и запаковать, вдруг кому ещё пригодится.

                    0

                    Угу, постоянно применяю fastutf в своем Rspamd, потому что задача валидации utf8 текстов стоит там постоянно и повсюду. Правда, я использую версию от китайца: https://github.com/cyb70289/utf8
                    который все организовал чуть более удобным для меня способом. Ну и для коротких строк (<64 байт) наивный метод валидации utf оказался быстрее avx2/sse41.
                    Ну а code points получать тоже приходится, но это потом — вначале нужно понять, не мусор ли у нас на входе, и не надо ли запустить тяжелые эвристики по определению кодировки, например.

                      0

                      Т.е. мусор приходит достаточно часто, чтобы имело смысл валидировать отдельно от парсинга?

                        0

                        Да, весьма часто, а кроме того, если заранее знать, что utf8 валидный, то можно парсить более дешевым способом (в libicu U8_NEXT_UNSAFE вместо U8_NEXT). Хотя я пока это не применял — мне было важнее выбросить мусор пораньше, особенно когда обрабатывается "плохой" трафик, например, со спамтрапов, где как раз стоит вопрос производительности.

                      0
                      Известная библиотека PCRE валидирует UTF-8 (при включении этого режима) до применения регулярки.
                        0

                        Ну если брать тот же раст — то он требует чтобы стрка была валидным UTF8. Поэтому он валидирует вообще все строки которые каким-либо образом появляются в программе (по сети ли, с диска ли). Можно ансейфно создавать строки из набора байт без валидации, но это УБ и так не делают.


                        Так что да — валидация важна.

                        +1
                        Почему раньше никто не додумался до векторизации?
                          0
                          Ну как почему?) Потому что 99.9 лабают никчомные сайтики и ещё более никчомные серваки.
                          Ну а 0.000..1 действительно заняты делом.

                          п.с.: Сие можно распространить не только на так называемых «программистов», а и вообще на всех «деятельных» хуманов. Планета такая. Что поделать) На 99.9 не очень удачно заселена. И это сильно мягко выражаясь.
                          п.п.с.: Да да, очень очень скоро ии будет делать всё за вас. Математики не нужны и прочая прочая бредятина. Чей то кэп. (с)

                        Only users with full accounts can post comments. Log in, please.