Всем здравствуйте, меня зовут Антон, и этой статьей я открываю новый цикл публикаций про 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 плоскостей (процитируем википедию):
№ | аббр. | диапазон | название |
0 | BMP |
| Основная многоязычная плоскость |
1 | SMP |
| Дополнительная многоязычная плоскость |
2 | SIP |
| Дополнительная идеографическая плоскость |
3 | TIP |
| Третичная идеографическая плоскость |
4–13 |
| не используется | |
14 | SSP |
| Специализированная дополнительная плоскость |
15–16 | SPUA‑A/B |
| Дополнительные области для частного использования — A/B |
BMP — основной диапазон символов, который встретится нам в 99% случаев.
Заметим и запомним — для записи значения кодпоинта из плоскости BMP достаточно 16 бит.
Некоторые блоки плоскости (и пара особенных символов), о которых стоит упомянуть:
| C0 Controls and Basic Latin |
| С1 Controls and Latin-1 Supplement |
… | |
| Суррогатные пары |
… | |
| ZERO WIDTH NO‑BREAK SPACE |
… | |
| � — REPLACEMENT CHARACTER |
… | |
Не лишним будет пролистать список блоков 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:
0 | Not_Reordered | Не подлежащие сортировке: пробелы и обрамляющие знаки, а также множество гласных и согласных знаков, даже если они не образуют отдельных символов. |
1 | Overlay | Наложение: знаки, накладывающиеся на базовую букву или символ. |
6 | Han_Reading | Чтение китайских иероглифов: диакритические знаки для китайских, японских и корейских иероглифов. |
7 | Nukta | Точки нукта в письменности, основанной на брахми. |
8 | Kana_Voicing | Фонетические знаки Хираганы/Катаканы. |
9 | Virama | Вирамы: знаки, обозначающие отсутствие звука между символами в санскрите, хинди и ряде других индийских языков. |
10-199 | CCC10 - CCC199 | Классы фиксированного положения в комбинируемой последовательности. |
200 | Attached_Below_Left | Знаки, прикрепленные внизу слева. |
202 | Attached_Below | Знаки, прикрепленные под базовым символом. |
204 | Знаки, прикрепленные внизу справа. | |
208 | Знаки, прикрепленные слева. | |
210 | Знаки, прикрепленные справа. | |
212 | Знаки, прикрепленные сверху слева. | |
214 | Attached_Above | Знаки, прикрепленные над базовым символом. |
216 | Attached_Above_Right | Знаки, прикрепленные сверху справа. |
218 | Below_Left | Отдельные знаки снизу слева. |
220 | Below | Отдельные знаки под базовым символом. |
222 | Below_Right | Отдельные знаки снизу справа. |
224 | Left | Отдельные знаки слева. |
226 | Right | Отдельные знаки справа. |
228 | Above_Left | Отдельные знаки сверху слева. |
230 | Above | Отдельные знаки над базовым символом. |
232 | Above_Right | Отдельные знаки сверху справа. |
233 | Double_Below | Двойные знаки снизу. Отдельные знаки, которые располагаются ниже двух других диакритических знаков. |
234 | Double_Above | Двойные знаки сверху. Отдельные знаки, которые располагаются выше двух других диакритических знаков. |
240 | Iota_Subscript | Греческая подстрочная йота. единственный кодпоинт с этим 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.
Приведём пример записи кодпоинта в различных форматах:
Код символа (HEX) | Кодировка | Последовательность байт |
0x00010203 | UTF-32BE |
|
UTF-32LE |
| |
UTF-32 |
|
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-16 так же может быть записан в BE и LE виде, и для определения, какой порядок байт используется можно так же использовать BOM.
Пример:
Код символа (HEX) | Кодировка | Последовательность байт |
0x004D | UTF-16BE |
|
UTF-16LE |
| |
UTF-16 |
| |
0x10000 | UTF-16BE |
|
UTF-16LE |
| |
UTF-16 |
|
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:
биты кодпоинта | 1 байт | 2 байт | 3 байт | 4 байт |
|
| |||
|
|
| ||
|
|
|
| |
|
|
|
|
|
Таким образом мы видим:
Если мы кодируем ASCII значение (
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 00101000 0000.
таким образом, первый байт не может быть равным0xC0и0xC1.3 байта на символ, диапазон начинается с
U+0800:U+0800—1110 00001010 00001000 0000.
вывод: если первый байт —0xE0, то диапазон значений второго байта — от0xA0до0xBF.4 байта на символ, диапазон начинается с
U+10000:U+10000—1111 00001001 00001000 00001000 0000.
похоже на предыдущий случай: если первый байт —0xF0, то диапазон значений второго байта — от0x90до0xBF.
так как UTF-8 позволяет напрямую кодировать символы, находящиеся за пределами BMP, использование символов суррогатных пар (
U+D800—U+DFFF) не допускается.запишем их в UTF-8:
U+D800—1110 11011010 00001000 0000U+DFFF—1110 11011011 11111011 1111таким образом, последовательность UTF-8 некорректна, если первый байт равен
1110 1101(0xED), а второй байт находится в диапазоне0xA0—0xBF.последний кодпоинт в таблице Unicode —
U+10FFFF, а максимальное значение, которое можно закодировать в UTF-8 —0x1FFFFF. следовательно, существует возможность записать в UTF-8 символ, выходящий за пределы таблицы, чего допустить нельзя.запишем последний символ таблицы Unicode в UTF-8:
U+10FFFF—1111 01001000 11111000 11111011 1111отсюда становится очевидно, что мы вышли за пределы таблицы, если:
первый байт равен
1111 0100(0xF4), и во втором байте записано значение, больше чем1000 1111(0x8F).первый байт больше
1111 0100(0xF4) — заодно мы убеждаемся в валидности последовательности старших бит первого байта.
Если записать это в виде таблицы, то мы получим ту самую таблицу 3–7:
диапазон кодпоинтов | 1 байт | 2 байт | 3 байт | 4 байт |
|---|---|---|---|---|
|
| |||
|
|
| ||
|
| A0 - |
| |
|
|
|
| |
|
|
|
| |
|
|
|
| |
|
| 90 - |
|
|
|
|
|
|
|
|
|
|
|
|
В таблице выделены значения (во втором байте последовательностей), на которые стоит обратить внимание при имплементации валидации 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), 0x80 | (c as u8 & 0x3F)],
(0x800 ..= 0xD7FF) | (0xE000 ..= 0xFFFF) => {
vec![
0xE0 | ((c >> 12) as u8),
0x80 | ((c >> 6) as u8 & 0x3F),
0x80 | (c as u8 & 0x3F),
]
}
0xD800 ..= 0xDFFF => return Err(Utf8EncodeError::SurrogatePoint),
0x10000 ..= 0x10FFFF => {
vec![
0xF0 | ((c >> 18) as u8),
0x80 | ((c >> 12) as u8 & 0x3F),
0x80 | ((c >> 6) as u8 & 0x3F),
0x80 | (c as u8 & 0x3F),
]
}
_ => return Err(Utf8EncodeError::OutOfRange),
})
}Общий алгоритм валидации
Тут всё просто:
Читаем байт.
Если он — валидный первый байт последовательности UTF-8 — уточняем количество символов последовательности и читаем их. Проверяем.
Повторяем, пока не закончатся данные.
базовая функция:
/// если данные являются валидной строкой 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.
