1. Введение в Unicode (опять?)

Всем здравствуйте, меня зовут Антон, и этой статьей я открываю новый цикл статей про Unicode. Сразу‑же может возникнуть вопрос — зачем? Их‑же и так море?

На Хабре, как и вообще в русскоязычном сегменте Интернета, в‑основном можно найти обзорные статьи, дающие лишь общее представление о Юникоде, но о том, как с ним работать — информации крайне мало. Сами же его разработчики, Unicode Consortium, предоставляют довольно подробную… но очень объемную документацию, которую при этом мало просто прочитать — для полного понимания много чего в ней стоит прокодить.

Мы, разработчики, очень любим изобретать велосипеды и заглядывать в мануалы в самый последний момент. Полагаемся на сторонние библиотеки, зачастую не до конца понимая, что там под происходит капотом.

В работе с текстом, таких велосипедов, к сожалению, наделано много. Наверняка вы сталкивались с чем‑то подобным:

• поиск не находит казалось‑бы одни и те же слова.

• в поле ввода безобразно работает ограничение на количество введённых символов, в зависимости от выбранного языка. классика.

• куда‑то пропадают эмодзи в базе данных, в текстах всплывают ромбики‑квадратики… перечислять можно бесконечно.

Что в статьях:

Основная мысль — нет ничего лучше, чем разобрать что‑то на практике. Какие‑то темы будут упомянуты вскользь (например, из кодировок мы плотно затронем лишь UTF-8), какие‑то темы оставим сильно на потом (например, системы ввода), а про что‑то вообще забудем (например, про историю — на Хабре есть что почитать на эту тему, например, тут или тут).

Итак, ближайший план:

• разберём, что из себя представляет Unicode, его символы и их свойства, кодировки. Напишем валидацию строк UTF-8, научимся преобразовывать запись символа в кодировке UTF-8 в код символа (кодпоинт) Unicode и обратно.

• выясним, что представляет собой нормализация текста, зачем она нужна и где её применять. расскажу про каноническую эквивалентность символов и эквивалентность совместимости, разберём как делается декомпозиция/композиция, быстрые проверки, под конец — напишем реализацию алгоритмов нормализации.

• узнаем, что такое сопоставление (collation) строк, алгоритм сопоставления (UCA), что такое DUCET и CLDR; уровни и веса сопоставлений, различные подходы к взвешиванию весов, немного затронем тему баз данных, и, наконец, напишем пример.

Код примеров — на языке Rust, все примеры будут выложены на гитхаб.

? небольшой оффтопик

по мере продвижения в статьях, я буду использовать термины, которые в различных источниках в силу не менее различных причин (например, переводов) могут быть обозначены по‑разному. использовать буду те, которые считаю наиболее точными, но если я где‑то не прав — пожалуйста, не стесняйтесь мне на это указать.

---

Что такое Unicode

Юникод — стандарт кодирования символов, который включает в себя символы огромного количества письменностей, различные графические символы, эмодзи, управляющие символы.

На момент написания этой статьи, актуальная версия Unicode — 15.0.0, и по мере развития стандарта было сломано немало копий в обсуждениях — начиная с избыточности (стоит‑ли включать в него мёртвые языки), продолжая вопросами организации размещения кодпоинтов в таблице, и заканчивая вечным обсуждением эмодзи.

✍️ кодпоинт — code point, кодовая точка — в контексте кодирования символов — числовое значение, соответствующее определенному символу.

Кодпоинты Unicode обозначаются как U+xxxx, где xxxx — шестнадцатеричный код символа. По префиксу U+ мы можем определить, что имеется ввиду именно кодпоинт Unicode.

Плоскости Unicode

Unicode — это в первую очередь про символы. Кодпоинты символов Unicode принадлежат диапазону от U+0000 до U+10FFFF включительно.

Этот диапазон разбит на крупные части, которые называются плоскостями (planes) — непрерывные диапазоны, состоящими из (65 536) последовательно расположенных кодпоинтов.

Плоскости, в свою очередь, дробятся на блоки — диапазоны кодпоинтов, сгруппированных по назначению.

Существует 17 плоскостей (процитируем википедию):

BMP — основной диапазон символов, который встретится нам в 99% случаев.

Заметим и запомним — для записи значения кодпоинта из плоскости BMP достаточно 16 бит.

Некоторые блоки плоскости (и пара особенных символов), о которых стоит упомянуть:

Не лишним будет пролистать список блоков BMP, в англоязычной википедии описание даётся полнее, чем в русской версии.

✍️ Совет из разряда «Хозяйке на заметку»

Обратим внимание, что, как указано выше, первые 2 блока включают в себя управляющие символы (Control characters): U+0000 — U+001F, U+007F, U+0080 — U+009F. Хоть это и не относится к теме статьи, но будет полезным напомнить себе, что их стоит при необходимости экранировать.

SMP — преимущественно неиспользуемые языки. Однако, есть одна причина, по которой символы этой плоскости довольно‑таки часто встречаются: эмодзи.

SIP, TIP, SSP — устаревшие / редко используемые символы CJK, символы специального назначения.

⛩ CJK расшифровывается как Chinese Japanese Korean. Символы CJK имеют ряд особенностей, с первыми из которых мы столкнемся, когда доберёмся до нормализации.

SPUA‑A/B — Область частного использования (название которой говорит само за себя) можно использовать по собственному усмотрению. А можно и не использовать, что чаще всего и происходит.

Главное здесь тот факт, что авторы Unicode обязуются не задействовать Private Use при обновлениях стандарта; таким образом, значение любого уже определённого в Unicode кодпоинта занимает максимум 20 бит (так как последний кодпоинт перед началом области, U+EFFFF, требует именно столько).

Символы Unicode

До Unicode мы могли быть уверены, что за один графический символ отвечает один кодпоинт. Однако с его появлением ситуация изменилась, и та же буква Й может быть представлена как:

• отдельный кодпоинт U+0419 CYRILLIC CAPITAL LETTER SHORT I,

• буква И, U+0418 CYRILLIC CAPITAL LETTER I в сочетании с бреве, U+0306 COMBINING BREVE.

На картинке мы видим 2 кодпоинта, которые, очевидно, относятся к разным категориям символов. А ведь ещё есть цифры, пунктуация, графические символы и разделители, управляющие символы и суррогатные пары, и все они отображаются (или не отображаются) по‑разному, по‑разному ведут себя при сортировке, имеют разную направленность в тексте…

Свойства символов

Стандарт Unicode очень детально описывает свойства всех включённых в него кодпоинтов, но мы же пока остановимся на некоторых из них. Очень часто в документации / коде используются сокращения названий этих свойств, они приведены в скобках.

Name

У каждого символа есть название. Название символа является уникальным, и может содержать только прописные буквы латинского алфавита (A‑Z), цифры (0–9), пробелы и знаки дефиса (‑).

Например, название кодпоинта латинской буквы A — LATIN CAPITAL LETTER A.

General Category (Gc)

Упомянутая ранее основная категория символа. Значения этого свойства можно объединить в несколько групп по их типу:

• все буквы (L)

  • буквы, имеющие регистр (LC)

    • Lu — прописная буква (Letter, uppercase)

    • Ll — строчная буква (Letter, lowercase)

    • Lt — заглавная буква (Letter, titlecase)

  • Lm — буква‑модификатор (Letter, modifier)

  • Lo — буква, прочие (Letter, other)

• знаки (M)

  • Mn — неразрывный знак (Mark, nonspacing)

  • Mc — сочетаемый знак с интервалом (Mark, spacing combining)

  • Me — закрывающий знак (Mark, enclosing)
    

• цифры, числа (N)

  • Nd — десятичная цифра (Number, decimal digit)

  • Nl — буквенно‑числовой символ (Number, letter)

  • No — число, прочие (Number, other)
    

• пунктуация (P)

  • Pc — соединительный символ (Punctuation, connector)

  • Pd — знаки тире и дефиса (Punctuation, dash)

  • Ps — открывающая пунктуация (Punctuation, open)

  • Pe — закрывающая пунктуация (Punctuation, close)

  • Pi — открывающие кавычки (Punctuation, initial quote)

  • Pf — закрывающие кавычки (Punctuation, final quote)

  • Po — пунктуация, прочее (Punctuation, other)
    

• символы (S)

  • Sm — математический символ (Symbol, math)

  • Sc — символ валюты (Symbol, currency)

  • Sk — символ‑модификатор (Symbol, modifier)

  • So — символ, прочие (Symbol, other)
    

• разделители (Z)

  • Zs — пробел (Separator, space)

  • Zl — разделитель строк (Separator, line)

  • Zp — разделитель параграфов (Separator, paragraph)
    

• разное (C)

  • Cc — управляющие символы (Other, control)

  • Cf — символы форматирования (Other, format)

  • Cs — суррогаты (Other, surrogate)

  • Co — частное использование (Other, private use)

  • Cn — не назначенные, в том числе не‑символы (Other, not assigned (including noncharacters))

Canonical Combining Class (ССС)

Важнейшее из свойств — класс канонического комбинирования символов. Относится к свойствам нормализации, и используется, как несложно догадаться, в алгоритмах нормализации. Значением является число от 0 до 240, которое отвечает за расположение в последовательности кодпоинтов, составляющих букву.

Кодпоинт с CCC = 0 называется стартером (starter), все прочие — не‑стартерами (non‑starter). Стартером может являться какая‑либо буква, цифра — основной символ, к которому могут быть добавлены дополнительные знаки, либо символ, вообще не подразумевающий комбинирования с чем‑либо, — например, пробел. Стартеры не подлежат сортировке при декомпозиции символа / нормализации текста.

Значение CCC не‑стартера может нести какую‑то смысловую нагрузку — например, что кодпоинт перекрывает основной знак (ССС = 1), или является диакритическим знаком для чтения CJK (ССС = 2), или указывать расположение знака относительно стартера (ССС находятся в диапазоне 202–240), или быть просто весом для сортировки в последовательности (10–132).

Приведём пример:

В практическом плане, чаще всего нас будет интересовать, является‑ли кодпоинт стартером или нет. Тем не менее, приведём полный список значений CCC:

Может возникнуть вопрос — а чем, собственно, разница между, например, 214 и 230? Дело в том, что символы, имеющие класс канонического комбинирования от 200 до 212 — это диакритические знаки, являющиеся частью отображения символа, как, например, хвостик (ogonek) в польском языке (U+0328 COMBINING OGONEK). А вот, например, две точки в букве Ë (U+0308 COMBINING DIAERESIS) — расположены над символом, отдельно, и его CCC будет равен 230.

Прочие свойства

У символа также есть свойства, относящиеся к отображению текста (например, Bidirectional Class (Bidi class), отвечающее за направление текста); свойства числовых символов; связанные с кодпоинтом строчная/прописная/заглавная буква. Пока просто упомянем, что они существуют, и вернёмся к ним в дальнейших статьях.

Другое важнейшее свойство — декомпозицию символа (Decomposition Mapping + Decomposition Type), мы рассмотрим уже в следующей статье про нормализацию.

Полную информацию по свойствам символов можно найти в четвертой главе спецификации Unicode: https://www.unicode.org/versions/Unicode15.0.0/ch04.pdf

Хранятся данные о символах Unicode в Unicode Character Database (UCD), и найти её можно здесь: https://www.unicode.org/Public/UCD/latest/ucd/.

Описанию форматов файлов UCD посвящёно приложение #44 стандарта: https://www.unicode.org/reports/tr44/.

Кодировки

Спецификация Unicode описывает три формата кодирования кодпоинтов (UTF, Unicode Transformation Format): UTF-8, UTF-16 и UTF-32.

С помощью каждой из них можно закодировать любой кодпоинт, находящийся в диапазоне от U+0000 до U+10FFFF. Самой распространенной из них является UTF-8, тем не менее, и у UTF-16, и у UTF-32 находится свое применение.

well-formed и ill-formed

Строка текста, закодированная в любой из кодировок считается хорошо сформированной (well‑formed), когда для строки выполняются следующие условия:

• Для любой из кодировок недопустимы кодпоинты, выходящие за пределы таблицы символов Unicode (> U+10FFFF).

• В UTF-16 недопустимо наличие одного из элементов суррогатной пары без дополняющего его элемента. Отсюда также можно вывести правило, что младший суррогат не может стоять впереди старшего.

• В UTF-8 и UTF-32 недопустимо присутствие символов суррогатных пар (U+D800 — U+DFFF).

• В UTF-8 последовательности недопустимо избыточное кодирование. если кодпоинт можно закодировать, используя меньшее количество байт — такое кодирование является недопустимым.

• Старшие биты байтов последовательности UTF-8 должны соответствовать его формату.

Некорректно закодированная строка называется ill‑formed.

UTF-32

Ключевым преимуществом UTF-32 можно назвать скорость и возможность быстрого доступа к любому символу в тексте по его индексу. Платой за это будет повышенное использование памяти, так как кодирование любого кодпоинта требует 4 байт.

Учитывая, что большинство символов в тексте (если не все) скорее всего будут относиться к плоскости BMP, значение кодпоинта которого укладывается в 2 байта, — мы удивим, что до половины объема памяти будет использоваться для хранения нулей.

Порядок байт, используемый при записи 32-битного значения кодпоинта может быть как little‑endian, так и big‑endian — кодировка в таком случае обозначается как UTF-32LE и UTF-32BE соответственно. По умолчанию считается, что используется big‑endian.

Для того, чтобы однозначно определить, какой порядок байт используется, в начале текста в качестве маркера записывается символ U+FEFF ZERO WIDTH NO‑BREAK SPACE в выбранном формате. Этот маркер называется BOM — Byte Order Mark.

Приведём пример записи кодпоинта в различных форматах:

UTF-16

Кодировка UTF-16 в данный момент используется довольно нечасто.

Собственно, формат появился в тот момент, когда в 1996 году стало понятно, что 2 байта на символ — недостаточно (первая версия Юникода представляла собой 16-битную кодировку с фиксированной шириной символа).

Главные недостатки кодировки:

• по сравнению с UTF-8, кодировка избыточна, так как даже для кодирования ASCII‑символов используется 2 байта — так что она меньше подходит для хранения и передачи текстов.

• когда требуется скорость — UTF-16 стоит рядышком с UTF-32, при этом требуя меньше ресурсов, но не имеет главного преимущества UTF-32 — возможности быстрого доступа к символу по его индексу, так как кодпоинт Unicode может быть закодирован в UTF-16 как двумя, так и четырьмя байтами.

Алгоритм кодирования:

• В случае, если кодпоинт Unicode находится в плоскости BMP, то он кодируется как есть, двумя байтами.

• Если значение кодпоинта лежит за пределами 16 бит — то такое значение кодируется с помощью суррогатной пары — двух слов, первое из которых называется старший суррогат — high surrogate code point, и имеет значение в диапазоне U+D800 — U+DBFF, и младший суррогат — low surrogate code point, и имеет значение в диапазоне U+DC00 — U+DFFF .

Кодирование суррогатной пары осуществляется по следующей схеме распределения бит:

В данной схеме wwww = uuuuu - 1. Это работает потому, что максимальное значение кодпоинта — 0×10FFFF, в битовом представлении — только 21-й бит имеет значение 1, таким образом, после вычитания единицы для хранения значения кодпоинта нам потребуется на один бит меньше.

Как и в случае с UTF-32, UTF-8 также может быть записан в BE и LE виде, и для определения, какой порядок байт используется можно также использовать BOM.

Пример:

BOM

Перед тем, как перейти к UTF-8, немного поговорим о BOM.

Причины, которые привели к его появлению понятны: смысл был в том, чтобы дать понять программе, в каком формате читать текстовый файл, учитывая, что он может быть получен из стороннего источника.

На практике же — UTF-8 занял нишу формата для хранения и передачи текстовых данных, а там, где используется UTF-32 / UTF-16 — порядок байт заранее известен и BOM излишен.

Порядок байт в UTF-8 определен заранее, и BOM в UTF-8 файлах (EF BB BF) выполняет только функцию обозначения, что текст — в кодировке UTF-8. Загвоздка в том, что практически всегда мы и так знаем, что текст — в UTF-8.

Проблем же он создаёт огромное количество:

• Если текстовые данные имеют какой‑то формат (например, JSON), они в большинстве случаев обрабатываются программно. библиотека‑же, обрабатывающая этот JSON может не ожидать BOM.

• То же самое относится и к компиляторам / интерпретаторам: там, где при токенизации ожидаются whitespace‑символы, не самое место метке, которая является всё‑таки специальным, но тем не менее валидным символом.

• Определение длины текста, переход по индексу символа в тексте, замусоривание метками при конкатенации строк — везде BOM может изрядно помешать.

На данный момент, использование BOM не рекомендовано, и это хорошо.

UTF-8

Наиболее используемый формат для кодирования Unicode, имеющий свои плюсы и минусы:

плюсы:

• Совместим с ASCII.

• Использует от 1 до 4 байт для кодирования символов, что обеспечивает рациональное использование памяти.

минусы:

• Использование переменного размера байт, помимо положительной стороны, имеет и отрицательную — в UTF-8 невозможно быстро перейти к символу по его индексу или узнать количество кодпоинтов без итерации по всем его байтам.

распределение бит в схеме кодирования кодпоинта в UTF-8:

Таким образом мы видим:

• Если мы кодируем ACSII значение (U+0000 — U+007F), нам потребуется только один бит.

• Для кодирования символа из плоскости BMP за пределами ASCII (U+0080 — U+FFFF) нам потребуется от 2 до 3 байт.

• Кодирование символов, выходящих за плоскость BMP (U+10000 — U+10FFFF) всегда потребует 4 байта.

Если первый байт не соответствует указанной выше форме, или старшие биты 2, 3, 4 байтов не равны 10 , то текст, содержащий UTF-8-последовательность с такими байтами считается ill‑formed.

✍️ Если старшие биты встретившегося нам байта в well‑formed строке не равны 10, то это говорит нам о том, что мы встретили первый байт UTF-8-последовательности для символа, в противном случае — мы встретили 2, 3 или 4 байт последовательности.

В практическом применении это полезно, когда мы хотим разбить UTF-8-текст на части, и не нарушить его целостности (здесь мы говорим только о UTF-8, последовательность кодпоинтов в составных символах это всё‑таки нарушит).

Давайте определим, какие последовательности UTF-8 допустимы, а какие — нет (хотя можно просто посмотреть в табличку 3–7 третьей главы официальной документации).

• первый байт не может начинаться с битов 10 — исключаем диапазон 0x80 — 0xBF для него.

• 2, 3 и 4 байты последовательности должны начинаться с битов 10 — т. е. их диапазоны значений — 0x80 — 0xBF.

• начиная с U+0080, символы кодируются несколькими байтами.
  так как UTF-8 не допускает избыточного кодирования, то должны быть задействованы биты первого байта, что исключает некоторые его значения:

  • 2 байта на символ, диапазон начинается с U+0080:

    U+0080 — 1100 0010 1000 0000 .

    таким образом, первый байт не может быть равным 0xC0 и 0xC1.

  • 3 байта на символ, диапазон начинается с U+0800:

    U+0800 — 1110 0000 1010 0000 1000 0000 .

    вывод: если первый байт — 0xE0, то диапазон значений второго байта — от 0xA0 до 0xBF.

  • 4 байта на символ, диапазон начинается с U+10000:

    U+10000 — 1111 0000 1001 0000 1000 0000 1000 0000 .

    похоже на предыдущий случай: если первый байт — 0xF0, то диапазон значений второго байта — от 0x90 до 0xBF.

• так как UTF-8 позволяет напрямую кодировать символы, находящиеся за пределами BMP, использование символов суррогатных пар (U+D800 — U+DFFF) не допускается.

  запишем их в UTF-8:

  U+D800 — 1110 1101 1010 0000 1000 0000
U+DFFF — 1110 1101 1011 1111 1011 1111

  таким образом, последовательность UTF-8 некорректна, если первый байт равен 1110 1101 (0xED), а второй байт находится в диапазоне 0xA0 — 0xBF.

• последний кодпоинт в таблице Unicode — U+10FFFF, а максимальное значение, которое можно закодировать в UTF-8 — 0x1FFFFF. следовательно, существует возможность записать в UTF-8 символ, выходящий за пределы таблицы, чего допустить нельзя.

  запишем последний символ таблицы Unicode в UTF-8:

  U+10FFFF — 1111 0100 1000 1111 1000 1111 1011 1111

  отсюда становится очевидно, что мы вышли за пределы таблицы, если:

  • первый байт равен 1111 0100 (0xF4), и во втором байте записано значение, больше чем 1000 1111 (0x8F).

  • первый байт больше 1111 0100 (0xF4) — заодно мы убеждаемся в валидности последовательности старших бит первого байта.

Если записать это в виде таблицы, то мы получим ту самую таблицу 3–7:

В таблице выделены значения (во втором байте последовательностей), на которые стоит обратить внимание при имплементации валидации UTF-8.

? расширяем кругозор: Ill‑formed UTF-8 и MySQL старых версий

В старых версиях MySQL по‑умолчанию использовалась кодировка, которая обозначалась как utf8. Казалось‑бы, какие могут быть проблемы? Но проблемы стали всплывать, когда в моду вошли эмодзи — оказалось, что MySQL под кодировкой utf8 в целях оптимизации понимал её ill‑formed версию, utf8mb3, допускающую кодирование только BMP плоскости (т. е. максимум 3 байта на символ).

На смену utf8 пришла кодировка utf8mb4, полноценно поддерживающая диапазон символов Unicode, utf8mb3 же, в свою очередь, объявлена deprecated.

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

Обработка ошибок при валидации UTF-8

Согласно официальной документации (и я с ней полностью согласен), допустимо 2 варианта действий при столкновении с невалидным UTF-8.

Первый — не обрабатывать ничего, и просто сообщить об ошибке. Вероятность получения «битой» UTF-8 по техническим причинам обычно крайне мала, в то же время какие‑то злонамеренные попытки прощупать валидацию пользовательского ввода на некорректность, а как следствие — пробелы в безопасности, встречаются довольно часто.

Второй — при нахождении ошибки определить максимально длинную цепочку некорректных байт, и заменить их на специально предназначенный для этого символ U+FFFD REPLACEMENT CHARACTER (�).

В любом случае, выбор варианта обработки ошибок всецело зависит от контекста.

Особенно актуально соблюдать осторожность и не игнорировать ill‑formed UTF-8 в случаях, где возможны инъекции исполняемого кода, вроде JavaScript.

Более детально вопросы безопасности рассматриваются в приложении #36 — Unicode Security Considerations.

---

Немного практики

Теперь, давайте подведём некоторые итоги, и напишем конвертацию UTF-8 в кодпоинты и обратно, и валидацию UTF-8.

Конечно, Rust, как и практически любой другой язык, умеет работать с Unicode.

Но почему‑бы не попробовать написать реализацию некоторых функций самим? Вторая причина, по которой это может понадобиться — бывают ситуации, когда собственные имплементации решают какую‑то специфичную задачу, и использование стандартных сценариев не совсем оптимально по скорости / памяти.

Репозиторий, и что там находится:

Весь код я выложил на гитхаб: https://github.com/gpawru/01_habr_unicode

Структура репозитория:

/benches       - бенчмарки /benches/data  - тестовые данные на разных языках /src/v1        - первая версия, без оптимизаций /src/v2        - вторая версия, с оптимизацией для ASCII-текстов /lib.rs        - кодирование/декодирование UTF-8 /tests.rs      - тесты написанных функций валидации

В v1 и v2 некоторый код дублируется, это не ошибка, — на мой взгляд, так нагляднее.

Запускаем тесты:

cargo tests

Запускаем бенчмарки:

cargo bench из папки benches

UTF-8 → кодпоинт и наоборот

Алгоритм кодирования / декодирования сам по себе ничего особо интересного не представляет — обычные битовые сдвиги и маски.

Тем не менее, декодирование
_{(битовые операции — в макросе, т.к. этот макрос нам ещё пригодится в следующей статье):}

/// кодпоинт Unicode из последовательности UTF-8 #[macro_export] macro_rules! compose_charcode {     ($c0:expr) => {         $c0 as u32     };     ($c0:expr, $c1:expr) => {         ((($c0 & 0x1Fu8) as u32) << 6) | ($c1 & 0x3Fu8) as u32     };     ($c0:expr, $c1:expr, $c2:expr) => {         ((($c0 & 0x0Fu8) as u32) << 12) | ((($c1 & 0x3Fu8) as u32) << 6) | ($c2 & 0x3Fu8) as u32     };     ($c0:expr, $c1:expr, $c2:expr, $c3:expr) => {         ((($c0 & 0x07u8) as u32) << 18)             | ((($c1 & 0x3Fu8) as u32) << 12)             | ((($c2 & 0x3Fu8) as u32) << 6)             | (($c3 & 0x3Fu8) as u32)     }; }  /// декодировать последовательность UTF-8 pub fn decode_utf8(c: Vec<u8>) -> Result<u32, Utf8EncodeError> {     if c.is_empty() || (get_utf8_sequence_width(c[0]) as usize != c.len()) {         return Err(Utf8EncodeError::InvalidBytesCount);     }      let codepoint = match c.len() {         1 => compose_charcode!(c[0]),         2 => compose_charcode!(c[0], c[1]),         3 => compose_charcode!(c[0], c[1], c[2]),         4 => compose_charcode!(c[0], c[1], c[2], c[3]),         _ => return Err(Utf8EncodeError::InvalidBytesCount),     };      if codepoint > 0x10FFFF {         return Err(Utf8EncodeError::OutOfRange);     }      if (0xD800 ..= 0xDFFF).contains(&codepoint) {         return Err(Utf8EncodeError::SurrogatePoint);     }      Ok(codepoint) }

… и кодирование:

/// записать кодпоинт в UTF-8 pub fn encode_utf8(c: u32) -> Result<Vec<u8>, Utf8EncodeError> {     Ok(match c {         0 ..= 0x7F => vec![c as u8],         0x80 ..= 0x07FF => vec![0xC0 | ((c >> 6) as u8), (c as u8 & 0x3F)],         (0x800 ..= 0xD7FF) | (0xE000 ..= 0xFFFF) => {             vec![                 0xE0 | ((c >> 12) as u8),                 ((c >> 6) as u8 & 0x3F),                 (c as u8 & 0x3F),             ]         }         0xD800 ..= 0xDFFF => return Err(Utf8EncodeError::SurrogatePoint),         0x10000 ..= 0x10FFFF => {             vec![                 0xF0 | ((c >> 18) as u8),                 ((c >> 12) as u8 & 0x3F),                 ((c >> 6) as u8 & 0x3F),                 (c as u8 & 0x3F),             ]         }         _ => return Err(Utf8EncodeError::OutOfRange),     }) }

Общий алгоритм валидации

Тут всё просто:

1. Читаем байт.

2. Если он — валидный первый байт последовательности UTF-8 — уточняем количество символов последовательности и читаем их. Проверяем.

3. Повторяем, пока не закончатся данные.

базовая функция:

/// если данные являются валидной строкой UTF-8 - преобразуем их в строковый слайс #[inline(never)] pub fn from_utf8(source: &[u8]) -> Result<&str, Utf8ValidationError> {     match validate_utf8(source) {         Ok(_) => {             #[allow(clippy::transmute_bytes_to_str)]             // совершенно то же самое выполняет функция core::mem::from_utf8_unchecked,             // но я не использую её, чтобы показать, что под капотом             //             // SAFETY: это безопасно, потому-что и слайс u8, и строковый слайс имеют одинаковый лейаут             Ok(unsafe { core::mem::transmute(source) })         }         Err(error) => {             // здесь, при желании, можно написать код, который получит максимальную последующую длину             // невалидной последовательности байт             Err(error)         }     } }  /// ошибка валидации pub struct Utf8ValidationError {     pub valid_up_to: usize, }  /// валидация UTF-8. при ошибке возвращаем длину валидного блока данных #[inline(always)] pub fn validate_utf8(source: &[u8]) -> Result<(), Utf8ValidationError> {     let mut index = 0;     let len = source.len();      while index < len {         let old_index = index;          // напишем пару макросов, который облегчат нам код - возврат ошибки и получение следующего байта          macro_rules! err {             () => {                 return Err(Utf8ValidationError {                     valid_up_to: old_index,                 })             };         }          macro_rules! next {             () => {{                 index += 1;                 // мы читаем последовательность UTF-8, и ожидаем наличие в ней определенного количества байт                 // если же неожиданно их нет - это очевидная ошибка                 if index >= len {                     err!()                 };                 source[index]             }};         }          let first = source[index];         let sequence_width = get_utf8_sequence_width(first);          // проверяем последовательность         match sequence_width {             1 => (),             2 => {                 if !(0x80 ..= 0xBF).contains(&next!()) {                     err!()                 }             }             3 => {                 match (first, next!()) {                     (0xE0, 0xA0 ..= 0xBF)                     | (0xE1 ..= 0xEC, 0x80 ..= 0xBF)                     | (0xED, 0x80 ..= 0x9F)                     | (0xEE ..= 0xEF, 0x80 ..= 0xBF) => {}                     _ => err!(),                 }                  if !(0x80 ..= 0xBF).contains(&next!()) {                     err!()                 }             }             4 => {                 match (first, next!()) {                     (0xF0, 0x90 ..= 0xBF)                     | (0xF1 ..= 0xF3, 0x80 ..= 0xBF)                     | (0xF4, 0x80 ..= 0x8F) => {}                     _ => err!(),                 }                 if !(0x80 ..= 0xBF).contains(&next!()) {                     err!()                 }                 if !(0x80 ..= 0xBF).contains(&next!()) {                     err!()                 }             }             _ => err!(),         }          index += 1;     }      Ok(()) }  /// получаем количество байт в последовательности UTF-8 #[inline(always)] fn get_utf8_sequence_width(first: u8) -> u8 {     match first {         0 ..= 0x7F => 1,         0xC2 ..= 0xDF => 2,         0xE0 ..= 0xEF => 3,         0xF0 ..= 0xF4 => 4,         _ => 0,     } }

Прогоняем бенчмарки… видим — на языках, которые используют преимущественно латинский алфавит, встроенная функция валидации отрабатывает в 2 раза быстрее. как они этого добились?

Давайте предположим, что текст — в ASCII. Такой текст можно попробовать валидировать не побайтово, а блоками, что и используется в core::str::validations::run_utf8_validation ‑ почему‑бы не взять оптимизацию оттуда и не сравнить результаты?

В ней, если найден ASCII‑символ, а адрес следующего байта имеет выравнивание в памяти по usize, валидируются 2 usize‑блока с помощью битовой маски (только у ASCII‑символов старший бит равен нулю).

Что нужно сделать:

• Определим границу в тексте, после которой применять оптимизацию не нужно (после неё нет достаточного количества символов).

• Добавляем проверку — если адрес выровнен по usize, индекс меньше границы — читаем блок и проверяем с помощью маски, являются‑ли элементы этого блока ASCII‑символами.

• Повторяем, если проверка была успешной.

проверка:

/// маска из байт, где у каждого старший бит равен 1, используем для проверки, /// есть-ли среди них не-ASCII байт const NONASCII_MASK: usize = usize::from_ne_bytes([0x80; core::mem::size_of::<usize>()]);  /// содержат-ли несколько байт не-ASCII символы #[inline(always)] pub const fn contains_nonascii(x: usize) -> bool {     (x & NONASCII_MASK) != 0 }

добавляем границу:

let usize_bytes = core::mem::size_of::<usize>(); let ascii_block_size = 2 * usize_bytes; let align = source.as_ptr().align_offset(usize_bytes);  let blocks_end = match len >= ascii_block_size {     true => len - ascii_block_size + 1,     false => 0, };

добавляем блочные проверки:

let first = source[index];  // проверяем последовательность, если символ за пределами ASCII if first >= 128 {     match get_utf8_sequence_width(first) {         ...     }      index += 1; } else {     // ASCII, пробуем быстро проскочить блок     // если указатель выровнен, читаем данные поблочно, по 2 usize-переменных     // пока не встретим не-ASCII байт     if align != usize::MAX && align.wrapping_sub(index) % usize_bytes == 0 {         let ptr = source.as_ptr();          while index < blocks_end {             // SAFETY: чтение по 2 блока безопасно, т.к. мы заранее уточнили             // допустимую границу             unsafe {                 let block = ptr.add(index) as *const usize;                  let zu = contains_nonascii(*block);                 let zv = contains_nonascii(*block.add(1));                 if zu || zv {                     break;                 }             }             index += ascii_block_size;         }         // пропускаем всё до не-ASCII байта         while index < len && source[index] < 128 {             index += 1;         }     } else {         index += 1;     } }

Как и ожидалось по бенчмаркам, затраты на валидацию текста с UTF-8-последовательностями, не входящими в ASCII возросли — появилась дополнительная проверка. Также замедляется проверка за счет того, что если встречается ASCII‑символ в не‑ASCII тексте (никто не отменял знаки пунктуации, пробелы, переносы строк — ну или язык может сочетать в себе символы латиницы и диакритические знаки, лежащие за пределами ASCII).

Что можно ещё сделать?

Например, можно заменить функцию проверки количества символов get_utf8_sequence_width на получение количества символов последовательности из заранее построенного массива, как это делается в Rust:

// https://tools.ietf.org/html/rfc3629 const UTF8_CHAR_WIDTH: &[u8; 256] = &[     // 1  2  3  4  5  6  7  8  9  A  B  C  D  E  F     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 0     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 1     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 2     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 3     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 4     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 5     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 6     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, // 7     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 8     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // 9     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // A     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // B     0, 0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // C     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, // D     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, // E     4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // F ];  /// Given a first byte, determines how many bytes are in this UTF-8 character. #[unstable(feature = "str_internals", issue = "none")] #[must_use] #[inline] pub const fn utf8_char_width(b: u8) -> usize {     UTF8_CHAR_WIDTH[b as usize] as usize }

Можно вместо количества байт попробовать получать готовый кейс для сравнения последующих байт последовательности:

/// варианты валидации, определяемые по первому байту символа UTF-8 /// /// 0 - U+0080..U+07FF C2..DF 80..BF /// 1 - U+0800..U+0FFF E0 A0..BF 80..BF /// 2 - U+1000..U+CFFF E1..EC 80..BF 80..BF ///     U+E000..U+FFFF EE..EF 80..BF 80..BF /// 3 - U+D000..U+D7FF ED 80..9F 80..BF /// 4 - U+10000..U+3FFFF F0 90..BF 80..BF 80..BF /// 5 - U+40000..U+FFFFF F1..F3 80..BF 80..BF 80..BF /// 6 - U+100000..U+10FFFF F4 80..8F 80..BF 80..BF const UTF8_SEQUENCE_CASE: &[u8; 256] = &[     // 1  2  3  4  5  6  7  8  9  A  B  C  D  E  F     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 0     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 1     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 2     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 3     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 4     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 5     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 6     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 7     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 8     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // 9     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // A     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // B     7, 7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // C     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, // D     1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 2, 2, // E     4, 5, 5, 5, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, // F ];

Можно попробовать заменить проверки диапазона допустимых значений

!(0x80 ..= 0xBF).contains(&next!())

на проверки старших бит по битовой маске:

(next!() & 0xC0) != 0x80

или, что равнозначно,

next!() as i8 >= -64

Вобщем, оптимизация — отличное занятие, когда требуется отвлечься, пробуйте, сравнивайте!

Что дальше

На этом — закончу первую часть. Следующая будет посвящена декомпозиции и нормализации; возможно, эту тему разобью на два части — в первой затронем алгоритмы декомпозиции и NFD/NFKD, во второй же части поиграемся с канонической композицией и NFC/NFKC.