Utf-8

Даниэль Лемир профессор Заочного квебекского университета (TLUQ), придумавший способ очень быстро парсить 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 байтов:


По правилам кодирования, старшие биты первого байта последовательности определяют общее количество байтов в последовательности; нулевой старший бит может быть только у однобайтных (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.

Для каждого рода ошибки ниже перечислены последовательности битов, которые к ней приводят:

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

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

const octet_difference_type length = utf8::internal::sequence_length(it);// Get trail octets and calculate the code pointutf_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 первых битов последовательности:
Каждой из этих возможных ошибок исследователи присвоили один из семи битов, как показано в самом правом столбце. (Присвоенные биты различаются между их опубликованной статьёй и их кодом на GitHub; здесь взяты значения из статьи.) Для того, чтобы обойтись семью битами, два подслучая выхода за границы Unicode пришлось переразбить так, чтобы второй объединялся с 4-байтной неминимальной последовательностью; а случай слишком длинной последовательности разбит на три подслучая и объединён с подслучаями выхода за границы Unicode.

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

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

Благодаря этим изменениям, для описания всех возможных переходов достаточно трёх таблиц по 16 байт: каждый элемент таблицы используется как битовое поле, перечисляющее все возможные конечные состояния. Три таких элемента объединяются по AND, и если в результате есть ненулевые биты, значит, обнаружена ошибка.
Остались необработанными ещё 7 недопустимых последовательностей битов:
И здесь пригождается старший бит, предусмотрительно оставленный в таблицах переходов неиспользованным: он будет соответствовать последовательности битов 10xxxxxx 10xxxxxx, т.е. двум продолжающим байтам подряд. Теперь проверка трёх тетрад может либо обнаружить ошибку, либо дать результат 0x00 или 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 = inputreturn 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 символа, чего достаточно для предсказания перехода.

Всем известна кодировка UTF-8, что давно доминирует в интернет пространстве, и которой пользуются много лет. Казалось бы, о ней все известно, и ничего интересного на эту тему не рассказать. Если почитать популярные ресурсы типа Википедии, то действительно там нет ничего необычного, разве что в английской версии кратко упоминается странная история о том, как ее набросали на салфетке в закусочной.

На самом деле изобретение этой кодировки не может быть настолько банальным хотя бы потому, что к ее созданию приложил руку Кен Томпсон легендарная личность. Он работал вместе с Деннисом Ритчи, был одним из создателей UNIX, внес вклад в разработку C (изобрел его предшественника B), а позднее, во время работы в Google, принял участие в создании языка Go.

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

Действующие лица:

ken (at) entrisphere.com Кен Томпсон

Кен Томпсон (слева) с Деннисом Ритчи

Rob 'Commander' Pike Роберт Пайк, канадский программист, работавший над UTF-8 вместе c Кеном Томпсоном


mkuhn (at) acm.org Маркус Кун, немецкий ученый в области информатики


henry (at) spsystems.net Генри Сперсер, автор одной из реализаций RegExp


Russ Cox <rsc@plan9.bell-labs.com> Русс Кокс, сотрудник Bell Labs, работавший над системой Plane 9


Greger Leijonhufvud <greger@friherr.com> Один из сотрудников X/Open


Plane 9 Операционная система, в которой впервые была использована кодировка UTF-8 для обеспечения ее мультиязычности.


UTF-8 Кодировка символов Юникода

---

Переписка 2003 года

Ниже переписка создателей кодировки, Роберта и Кена, которую Роберт Пайк начал, сетуя на то, что их вклад в создание UTF-8 незаслуженно забыли. Роберт просит одного из старых знакомых порыться в архивах почтового сервера и найти там доказательства их участия. (прим. пер.)

Subject: UTF-8 history
From: "Rob 'Commander' Pike" <r (at) google.com>
Date: Wed, 30 Apr 2003 22:32:32 -0700 (Thu 06:32 BST)
To: mkuhn (at) acm.org, henry (at) spsystems.net
Cc: ken (at) entrisphere.com

Глядя на разговоры о происхождении UTF-8, я вижу, как постоянно повторяют одну и ту же историю.
Неправильная версия:
1. UTF-8 разработала IBM.
2. Она была реализована в Plane 9 (операционная система, разработанная Bell Laboratories)
Это неправда. Я своими глазами видел, как однажды вечером в сентябре 1992 года была придумана UTF-8 на салфетке в одной закусочных Нью-Джерси.

Произошло это таким образом. Мы пользовались оригинальным UTF из стандарта ISO 10646 для поддержки 16-битных символов в Plane 9, который ненавидели, и уже были готовы к выпуску Plane 9, когда однажды поздно вечером мне позвонили одни парни, кажется они были из IBM. Я припоминаю, что встречался с ними на заседании комитета X/Open в Остине. Они хотели, чтобы мы с Кеном посмотрели их проект FSS/UTF.

В то время подавляющее большинство компьютерных программ и систем (документация, сообщения об ошибках и т.п.) было только на английском и только слева направо. Инженерам из Bell Labs показалось, что релиз Plane 9 хороший повод для того, чтобы изменить это, поскольку проще всего вводить новшества в систему на этапе ее разработки, а не исправлять уже выпущенный продукт. Потому они стали искать специалистов, которые помогут им интернационализировать их проект.

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

Мы поняли, почему они хотят изменить дизайн и решили, что это хорошая возможность использовать наш опыт, чтобы разработать новый стандарт и заставить ребят из X/Open продвинуть его. Нам пришлось рассказать им об этом, и они согласились при условии, что мы быстро с этим справимся.
Потом мы пошли перекусить, и во время ужина Кен разобрался с упаковкой битов, а когда вернулись, то позвонили ребятам из X/Open и объяснили им нашу идею. Мы отправили по почте наш набросок, и они ответили, что это лучше, чем у них (но я точно помню, что они нам свой вариант не показывали), и спросили, когда мы сможем это реализовать.

Одним из вариантов разграничения символов был слэш, но это могло запутать файловую систему, она бы могла интерпретировать его как эскейп-последовательность.
(прим. пер.)

Мне кажется, что это происходило в среду вечером. Мы пообещали, что запустим систему к понедельнику, когда у них, как мне кажется, намечалось какое-то важное совещание. В тот же вечер Кен написал код кодировщика/раскодировщика, а я начал разбираться с С и с графическими библиотеками. На следующий день код был готов, и мы начали конвертировать текстовые файлы системы. К пятнице Plane 9 уже запускался и работал на так называемом UTF-8.
А в дальнейшем история была немного переписана.

Почему мы просто не воспользовались их FSS/UTF?
Насколько я помню, в том первом телефонном звонке я напел им Дезидерату своих требований для кодировки, и в FSS/UTF не было как минимум одного возможности синхронизировать поток байтов взятых из середины потока, используя для синхронизации как можно меньше символов (см выше, про определение границ символов. прим. пер). Поскольку нигде решения не было, мы были вольны делать это как хотели.
Я думаю, что историю придумали IBM, а реализовали в Plane 9 берет свое начало в документации по RFC 2279. Мы были так счастливы, когда UTF-8 прижился, что никому не рассказали эту историю.

Никто из нас больше не работает в Bell Labs, но я уверен, что сохранился архив электронной почты, которая может подтвердить нашу историю, и я могу попросить кого-нибудь покопаться в ней.
Итак, вся слава достается парням из X/Open и IBM за то, что они сделали это возможным и продвинули кодировку, но разработал ее Кен, и я ему помогал в этом, что бы там не говорилось в книгах по истории.

Роб

---

Date: Sat, 07 Jun 2003 18:44:05 -0700
From: "Rob `Commander' Pike" <r@google.com>
To: Markus Kuhn <Markus.Kuhn@cl.cam.ac.uk>
cc: henry@spsystems.net, ken@entrisphere.com,
Greger Leijonhufvud <greger@friherr.com>
Subject: Re: UTF-8 history

Я попросил Расса Кокса покопаться в архивах. Прикладываю его сообщение. Я думаю, вы согласитесь, что это подтверждает историю, которую я отправил раньше. Письмо, которое мы выслали в X/Open (думаю, что Кен редактировал и рассылал этот документ) включает новый desideratum номер 6 про обнаружение границ символов.

Мы уже не узнаем, какое влияние оказало на нас оригинальное решение от X/Open. Они хоть и отличаются, но имеют общие характерные черты. Я не помню, чтобы подробно его рассматривал, это было слишком давно (в прошлом письме он говорит, что X/Open им свой вариант реализации не показывали. прим. пер). Но я очень хорошо помню, как Кен писал наброски на салфетке и потом жалел, что мы ее не сохранили.

Роб

---

From: Russ Cox <rsc@plan9.bell-labs.com>
To: r@google.com
Subject: utf digging
Date-Sent: Saturday, June 07, 2003 7:46 PM -0400

Файл пользователя bootes /sys/src/libc/port/rune.c был изменен пользователем division-heavy 4 сентября 1992 года. Версия, попавшая в дамп имеет время 19:51:55. На другой день в него был добавлен комментарий, но в остальном он не изменялся до 14 ноября 1996 года, когда runelen была ускорена путем явной проверки значения rune вместо использования значения, возвращаемого runetochar. Последнее изменение было 26 мая 2001 года, когда была добавлена runenlen. (Rune структура, содержащая значение Юникод. Runelen и runetochar функции, работающие с этим типом данных. прим.пер)

Нашлось несколько писем из ваших ящиков, которые выдал грепинг по строке utf.

В первом идет речь про файл utf.c, который является копией wctomb и mbtowc (функции преобразования символов. прим. пер.), что обрабатывают полную 6-байтовую кодировку UTF-8, 32-битных runes. С логикой управления потоком это выглядит довольно уродливо. Я предполагаю, что этот код появился в результате того первого письма.

В /usr/ken/utf/xutf я нашел копию того, что, по видимому, является исходником того не самосинхронизирующегося способа кодирования.со схемой UTF-8, добавленной в конце письма (начинается со слов Мы определяем 7 типов byte).

Приведенная ниже версия письма, датированная 2 сентября 23:44:10, является первой. После нескольких правок, утром 8 сентября, получилась вторая версия. Логи почтового сервера показывают, как отправляется вторая версия письма и, через некоторое время, возвращается к Кену:

helix: Sep 8 03:22:13: ken: upas/sendmail: remote inet!xopen.co.uk!xojig
>From ken Tue Sep 8 03:22:07 EDT 1992 (xojig@xopen.co.uk) 6833
helix: Sep 8 03:22:13: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:22:07 EDT 1992 6833
helix: Sep 8 03:22:16: ken: upas/sendmail: remote pyxis!andrew From ken Tue Sep 8 03:22:07 EDT 1992 (andrew) 6833
helix: Sep 8 03:22:19: ken: upas/sendmail: remote coma!dmr From ken Tue Sep 8 03:22:07 EDT 1992 (dmr) 6833
helix: Sep 8 03:25:52: ken: upas/sendmail: delivered rob From ken Tue Sep 8 03:24:58 EDT 1992 141
helix: Sep 8 03:36:13: ken: upas/sendmail: delivered ken From ken Tue Sep 8 03:36:12 EDT 1992 6833

Всего хорошего.

Файлы из почтового архива

Далее файл с перепиской из дапма почтового сервера, который Расс Кокс приаттачил к своему, в ответ на просьбу Роберта покопаться в истории. Это первая версия. (прим пер.)

>From ken Fri Sep 4 03:37:39 EDT 1992

Вот наше предложение по модификации FSS-UTF. Речь идет о том же, о чем и в предыдущем. Приношу свои извинения автору.

Код был в какой-то степени протестирован и должен быть в довольно неплохой форме. Мы переделали код Plane 9 для использования с этой кодировкой, собрались выпустить дистрибутив и отобрать пользователей университета для начального тестирования.

File System Safe Universal Character Set Transformation Format (FSS-UTF)

---

В связи с утверждением ISO/IEC 10646 (Unicode) в качестве международного стандарта и ожиданием широкого распространения этого Универсального Набора Кодированных символов (UCS), для операционных систем, исторически основанных на формате ASCII, необходимо разработать способы представления и обработки большого количества символов, которые можно закодировать с помощью нового стандарта. У UCS есть несколько проблем, которые нужно решить в исторически сложившихся операционных системах и среде для программирования на языке C.

(Далее в тексте несколько раз упоминаются historical operating systems. Видимо в контексте исторически работающие с кодировкой ASCII. Я или опускал этот эпитет, или заменял его на существующие и т.п. прим. пер)

Самой серьезной проблемой является схема кодирования, используемая в UCS. А именно объединение стандарта UCS с существующими языками программирования, операционными системами и утилитами. Проблемы в языках программирования и операционных системах решаются в разных отраслях, тем не менее мы все еще сталкиваемся с обработкой UCS операционными системами и утилитами.

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

UCS дает возможность закодировать многоязычный текст с помощью одного набора символов. Но UCS и UTF не защищают нулевые байты (конец строки в некоторых языках. прим. пер.) и/или слеш в ASCII /, что делает эти кодировки несовместимыми с Unix. Следующее предложение обеспечивает формат преобразования UCS, совместимый с Unix, и, таким образом, Unix-системы могут поддерживать многоязычный текст в рамках одной кодировки.

Данная кодировка формата преобразования предназначена для кодирования файлов, как промежуточный шаг к полной поддержке UCS. Однако, поскольку почти все реализации Unis сталкиваются с одинаковыми проблемами поддержки UCS, это предложение предназначено для обеспечения общей совместимости кодировки на данном этапе.

Цель/Задача

---

Исходя из предположения получаем, что если известны практически все проблемы обработки и хранения UCS в файловых системах ОС, то надо пользоваться таким форматом преобразования UCS, который будет работать не нарушая структуры операционной системы. Цель состоит в том, чтобы процесс преобразования формата можно было использовать для кодирования файла.

Критерии для формата преобразования

---

Ниже приведены рекомендации, которые должны соблюдаться, при определении формата преобразования UCS:

1. Совместимость с существующими файловыми системами.
   Запрещено использовать нулевой байт и символ слэша как часть имени файла.
2. Совместимость с существующими программами.
   В существующей модели многобайтовой обработки не должны использоваться коды ASCII. В формате преобразования представления символа UCS, которого нет в наборе символов ASCII, не должны использоваться коды ASCII.
3. Простота конвертации из UCS и обратно.
4. Первый байт содержит указание на длину многобайтовой последовательности.
5. Формат преобразования не должен быть затратным, в смысле количества байт, используемых для кодирования.
6. Должна быть возможность легко определять начало символа, находясь в любом месте байтового потока (строки. прим.пер.).

Предписания FSS-UTF

---

Предлагаемый формат преобразования UCS кодирует значения UCS в диапазоне [0,0x7fffffff] с использованием нескольких байт на один символ и длинной 1, 2, 3, 4, 5, и 6 байт. Во всех случаях кодирования более чем одним байтом начальный байт определяет количество используемых байтов, при этом в каждом байте устанавливается старший бит. Каждый байт, который не начинается с 10XXXXXX, является началом последовательности символов UCS.

Простой способ запомнить формат: количество старших единиц в первом байте означает количество байт в многобайтовом символе.

Bits  Hex Min Hex Max Byte Sequence in Binary1  7 00000000 0000007f 0vvvvvvv2  11 00000080 000007FF 110vvvvv 10vvvvvv3  16 00000800 0000FFFF 1110vvvv 10vvvvvv 10vvvvvv4  21 00010000 001FFFFF 11110vvv 10vvvvvv 10vvvvvv 10vvvvvv5  26 00200000 03FFFFFF 111110vv 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv6  31 04000000 7FFFFFFF 1111110v 10vvvvvv 10vvvvvv 10vvvvvv 10vvvvvv10vvvvvv

Значение символа UCD в многобайтовой кодировке это конкатенация v-битов. Если возможно несколько способов кодирования, например UCS 0, то допустимым считается самый короткий.

Ниже приведены примеры реализаций стандартных функций C wcstombs() и mbstowcs(), которые демонстрируют алгоритмы конвертирования из UCS в формат преобразования и конвертирования из формата преобразования в UCS. Примеры реализаций включают проверку ошибок, некоторые из которых могут быть не нужны для согласования:

typedefstruct{int  cmask;int  cval;int  shift;long lmask;long lval;} Tab;staticTab    tab[] ={0x80, 0x00, 0*6,  0x7F,     0,      /* 1 byte sequence */0xE0, 0xC0, 1*6,  0x7FF,    0x80,     /* 2 byte sequence */0xF0, 0xE0, 2*6,  0xFFFF,       0x800,    /* 3 byte sequence */0xF8, 0xF0, 3*6,  0x1FFFFF,   0x10000,   /* 4 byte sequence */0xFC, 0xF8, 4*6,  0x3FFFFFF,  0x200000,   /* 5 byte sequence */0xFE, 0xFC, 5*6,  0x7FFFFFFF,  0x4000000,  /* 6 byte sequence */0,                       /* end of table */};intmbtowc(wchar_t *p, char *s, size_t n){long l;int c0, c, nc;Tab *t;if(s == 0)return 0;nc = 0;if(n <= nc)return -1;c0 = *s & 0xff;l = c0;for(t=tab; t->cmask; t++) {nc++;if((c0 & t->cmask) == t->cval) {l &= t->lmask;if(l < t->lval)return -1;*p = l;return nc;}if(n <= nc)return -1;s++;c = (*s ^ 0x80) & 0xFF;if(c & 0xC0)return -1;l = (l<<6) | c;}return -1;}intwctomb(char *s, wchar_t wc){long l;int c, nc;Tab *t;if(s == 0)return 0;l = wc;nc = 0;for(t=tab; t->cmask; t++) {nc++;if(l <= t->lmask) {c = t->shift;*s = t->cval | (l>>c);while(c > 0) {c -= 6;s++;*s = 0x80 | ((l>>c) & 0x3F);}return nc;}}return -1;}

>From ken Tue Sep 8 03:24:58 EDT 1992

Я послал его по почте, но письмо ушло в черную дыру, потому я не получил свою копию. Наверное, это интернет-адрес был в коме.

Вторая версия письма, с правками

Далее прикладывается копия письма, которая выше описывается как: После нескольких правок, утром 8 сентября, получилась вторая версия. Повторяющаяся часть скрыта под спойлером. (прим.пер.)

>From ken Tue Sep 8 03:42:43 EDT 1992

Наконец-то я получил свою копию.
--- /usr/ken/utf/xutf from dump of Sep 2 1992 ---

int mbtowc(wchar_t *p, const char *s, size_t n){unsigned char *uc;   /* so that all bytes are nonnegative */if ((uc = (unsigned char *)s) == 0)return 0;        /* no shift states */if (n == 0)return -1;if ((*p = uc[0]) < 0x80)return uc[0] != '\0';  /* return 0 for '\0', else 1 */if (uc[0] < 0xc0){if (n < 2)return -1;if (uc[1] < 0x80)goto bad;*p &= 0x3f;*p <<= 7;*p |= uc[1] & 0x7f;*p += OFF1;return 2;}if (uc[0] < 0xe0){if (n < 3)return -1;if (uc[1] < 0x80 || uc[2] < 0x80)goto bad;*p &= 0x1f;*p <<= 14;*p |= (uc[1] & 0x7f) << 7;*p |= uc[2] & 0x7f;*p += OFF2;return 3;}if (uc[0] < 0xf0){if (n < 4)return -1;if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80)goto bad;*p &= 0x0f;*p <<= 21;*p |= (uc[1] & 0x7f) << 14;*p |= (uc[2] & 0x7f) << 7;*p |= uc[3] & 0x7f;*p += OFF3;return 4;}if (uc[0] < 0xf8){if (n < 5)return -1;if (uc[1] < 0x80 || uc[2] < 0x80 || uc[3] < 0x80 || uc[4] < 0x80)goto bad;*p &= 0x07;*p <<= 28;*p |= (uc[1] & 0x7f) << 21;*p |= (uc[2] & 0x7f) << 14;*p |= (uc[3] & 0x7f) << 7;*p |= uc[4] & 0x7f;if (((*p += OFF4) & ~(wchar_t)0x7fffffff) == 0)return 5;}bad:;errno = EILSEQ;return -1;}

Мы определяем 7 байтовых типов:

T0 0xxxxxxx   7 free bitsTx 10xxxxxx   6 free bitsT1 110xxxxx   5 free bitsT2 1110xxxx   4 free bitsT3 11110xxx   3 free bitsT4 111110xx   2 free bitsT5 111111xx   2 free bits

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

>From hex Thru hex   Sequence       Bits00000000 0000007f   T0          700000080 000007FF   T1 Tx        1100000800 0000FFFF   T2 Tx Tx       1600010000 001FFFFF   T3 Tx Tx Tx     2100200000 03FFFFFF   T4 Tx Tx Tx Tx    2604000000 FFFFFFFF   T5 Tx Tx Tx Tx Tx  32

Некоторые примечания:

1. Двумя байтами можно закодировать 2^11 степени символов, но использоваться будут только 2^112^7. Коды в диапазоне 0-7F будут считаться недопустимыми. Я думаю, что это лучше, чем добавление кучи магических констант без реальной пользы. Это замечание применимо ко всем более длинным последовательностям.
2. Последовательности из 4, 5 и 6 байт существуют только по политическим причинам. Я бы предпочел их удалить.
3. 6-байтовая последовательность охватывает 32 бита, предложение FSS-UTF охватывает только 31.
4. Все последовательности синхронизируются по любому байту, не являющемуся Tx.

***

Эта короткая переписка расставила все по своим местам. Хоть и не сохранилась та легендарная салфетка, но выдержек из архива почтового сервера хватило, чтобы сообщество признало их заслуги. В Википедию добавили имена Кена и Роберта и забавный факт про салфетку в закусочной, а в сети эта история гуляет и обсуждается как есть, в виде простого текста, содержащего несколько писем и часть дампа из почтового сервера.

Давно забыта операционная система Plane 9, никто не помнит для чего ее писали и почему она номер девять, а UTF-8, спустя почти тридцать лет, все еще актуальна и не собирается уходить на покой.

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

Если вы разработчик и перед вами стоит задача выбора кодировки, то почти всегда правильным решением будет Юникод. Конкретный способ представления зависит от контекста, но чаще всего тут тоже есть универсальный ответ UTF-8. Он хорош тем, что позволяет использовать все символы Юникода, не тратя слишком много байт в большинстве случаев. Правда, для языков, использующих не только латиницу, не слишком много это как минимум два байта на символ. Можно ли лучше, не возвращаясь к доисторическим кодировкам, ограничивающим нас всего 256 доступными символами?

Ниже предлагаю ознакомиться с моей попыткой дать ответ на этот вопрос и реализацию относительно простого алгоритма, позволяющего хранить строчки на большинстве языков мира, не добавляя той избыточности, которая есть в UTF-8.

Дисклеймер. Сразу сделаю несколько важных оговорок: описанное решение не предлагается как универсальная замена UTF-8, оно подходит только в узком списке случаев (о них ниже), и его ни в коем случае нельзя использовать для взаимодействия со сторонними API (которые о нём и знать не знают). Чаще всего для компактного хранения больших объемов текстовых данных подойдут алгоритмы сжатия общего назначения (например, deflate). Кроме того, уже в процессе создания своего решения я нашёл существующий стандарт в самом Юникоде, который решает ту же задачу он несколько сложнее (и нередко хуже), но всё-таки является принятым стандартом, а не собранным на коленке. О нём я тоже расскажу.

О Unicode и UTF-8

Для начала несколько слов о том, что вообще такое Unicode и UTF-8.

Как известно, раньше имели популярность 8-битные кодировки. С ними всё было просто: 256 символов можно занумеровать числами от 0 до 255, а числа от 0 до 255 очевидным образом представимы в виде одного байта. Если возвращаться к самым истокам, то кодировка ASCII и вовсе ограничивается 7 битами, поэтому самый старший бит в её байтовом представлении равен нулю, и большинство 8-битных кодировок с ней совместимы (они различаются только в верхней части, где старший бит единица).

Чем же от тех кодировок отличается Юникод и почему с ним связано сразу множество конкретных представлений UTF-8, UTF-16 (BE и LE), UTF-32? Разберёмся по порядку.

Основной стандарт Юникода описывает только соответствие между символами (а в некоторых случаях отдельными компонентами символов) и их номерами. И возможных номеров в этом стандарте очень много от 0x00 до 0x10FFFF (1 114 112 штук). Если бы мы хотели положить число в таком диапазоне в переменную, ни 1, ни 2 байт нам бы не хватило. А так как под работу с трехбайтовыми числами наши процессоры не очень заточены, мы были бы вынуждены использовать целых 4 байта на один символ! Это и есть UTF-32, но именно из-за этой расточительности этот формат не пользуется популярностью.

К счастью, символы внутри Юникода упорядочены не случайно. Всё их множество разделено на 17 плоскостей, каждая из которых содержит 65536 (0x10000) кодовых точек. Понятие кодовой точки тут это просто номер символа, присвоенный ему Юникодом. Но, как было сказано выше, в Юникоде занумерованы не только отдельные символы, но также их компоненты и служебные пометки (а иногда и вовсе номеру ничего не соответствует возможно, до поры до времени, но для нас это не так важно), поэтому корректнее всегда говорить именно про число самих номеров, а не символов. Однако далее для краткости я часто буду употреблять слово символ, подразумевая термин кодовая точка.


Плоскости Юникода. Как видно, большая часть (плоскости с 4 по 13) всё ещё не использована.

Что самое замечательное вся основная мякотка лежит в нулевой плоскости, она называется "Basic Multilingual Plane". Если строчка содержит текст на одном из современных языков (включая китайский), за пределы этой плоскости вы не выйдете. Но отсекать остальную часть Юникода тоже нельзя например, эмодзи в основном находятся в конце следующей по счёту плоскости, "Supplementary Multilingual Plane" (она простирается от 0x10000 до 0x1FFFF). Поэтому UTF-16 поступает так: все символы, попадающие в Basic Multilingual Plane, кодируются как есть, соответствующим им двухбайтовым числом. Однако часть чисел в этом диапазоне вообще не обозначают конкретные символы, а указывают на то, что следом за этой парой байт нужно рассмотреть ещё одну скомбинировав значения этих четырёх байт вместе, у нас получится число, охватывающее весь допустимый диапазон Юникода. Такое представление называется суррогатными парами возможно, вы о них слышали.

Таким образом, UTF-16 требует два или (в очень редких случаях) четыре байта на одну кодовую точку. Это лучше, чем постоянно использовать четыре байта, но латиница (и другие ASCII-символы) при таком кодировании расходует половину занимаемого места на нули. UTF-8 призван это поправить: ASCII в нём занимает, как раньше, всего один байт; коды от 0x80 до 0x7FF два байта; от 0x800 до 0x7FFF три, а от 0x8000 до 0x1FFFF четыре. С одной стороны, латинице стало хорошо: вернулась совместимость с ASCII, да и распределение более равномерно размазано от 1 до 4 байт. Но алфавиты, отличные от латинского, увы, никак не выигрывают по сравнению с UTF-16, а многие и вовсе теперь требуют трёх байт вместо двух диапазон, покрываемый двухбайтовой записью, сузился в 32 раза, с 0xFFFF до 0x7FF, и в него не попадает уже ни китайский, ни, к примеру, грузинский. Кириллице и ещё пяти алфавитам ура повезло, 2 байта на символ.

Почему так выходит? Давайте посмотрим, как UTF-8 представляет коды символов:

Непосредственно для представления чисел тут использованы биты, помеченные символом x. Видно, что в двухбайтовой записи таких бит лишь 11 (из 16). Ведущие биты тут несут только служебную функцию. В случае с четырёхбайтовой записью и вовсе под номер кодовой точки отведён 21 бит из 32 казалось бы, тут хватило бы и трёх байт (которые дают суммарно 24 бита), но служебные маркеры съедают слишком много.

Плохо ли это? На самом деле, не очень. С одной стороны если мы сильно заботимся о занимаемом пространстве, у нас есть алгоритмы сжатия, которые легко устранят всю лишнюю энтропию и избыточность. С другой целью Юникода было дать максимально универсальное кодирование. Например, закодированную в UTF-8 строчку мы можем доверить коду, который раньше работал только с ASCII, и не бояться, что он там увидит символ из ASCII-диапазона, которого там на самом деле нет (ведь в UTF-8 все байты, начинающиеся с нулевого бита это именно ASCII и есть). А если мы захотим вдруг отрезать маленький хвост от большой строки, не декодируя её с самого начала (или восстановить часть информации после повреждённого участка) нам несложно найти то смещение, где начинается какой-то символ (достаточно пропустить байты, имеющие битовый префикс 10).

Зачем же тогда выдумывать что-то новое?

В то же время, изредка бывают ситуации, когда алгоритмы сжатия вроде deflate плохоприменимы, а добиться компактного хранения строк хочется. Лично я столкнулся с такой задачей, размышляя о построении сжатого префиксного дерева для большого словаря, включающего слова на произвольных языках. С одной стороны каждое слово очень короткое, поэтому сжимать его будет неэффективно. С другой реализация дерева, которую я рассматривал, была рассчитана на то, что каждый байт хранимой строки порождал отдельную вершину дерева, так что минимизировать их количество было очень полезно. В моей библиотеке Az.js (как и в pymorphy2, на котором она основана) подобная проблема решается просто строки, упакованные в DAWG-словарь, хранятся там в старой доброй CP1251. Но, как нетрудно понять, это хорошо работает только для ограниченного алфавита строчку на китайском в такой словарь уже не сложить.

Отдельно отмечу ещё один неприятный нюанс, который возникает при использовании UTF-8 в такой структуре данных. На картинке выше видно, что при записи символа в виде двух байт, биты, относящиеся к его номеру, не идут подряд, а разорваны парой бит 10 посередине: 110xxxxx 10xxxxxx. Из-за этого, когда в коде символа переполняются младшие 6 бит второго байта (т.е. происходит переход 10111111 10000000), то меняется и первый байт тоже. Получается, что буква п обозначается байтами 0xD00xBF, а следующая за ней р уже 0xD10x80. В префиксном дереве это приводит к расщеплению родительской вершины на две одной для префикса 0xD0, и другой для 0xD1 (хотя вся кириллица могла бы кодироваться только вторым байтом).

Что у меня получилось

Столкнувшись с этой задачей я решил поупражняться в играх с битами, а заодно чуть лучше познакомиться со структурой Юникода в целом. Результатом стал формат кодирования UTF-C (C от compact), который тратит не более 3 байт на одну кодовую точку, а очень часто позволяет тратить лишь один лишний байт на всю кодируемую строчку. Это приводит к тому, что на многих не-ASCII алфавитах такое кодирование оказывается на 30-60% компактнее UTF-8.

Я оформил примеры реализации алгоритмов кодирования и декодирования в виде библиотек на JavaScript и Go, вы можете свободно использовать их в своём коде. Но я всё же подчеркну, что в некотором смысле этот формат остаётся велосипедом, и я не рекомендую его использовать без осознания того, зачем он вам нужен. Это всё-таки больше эксперимент, чем серьёзное улучшение UTF-8. Тем не менее, код там написан аккуратно, лаконично, с большим числом комментариев и покрытием тестами.


Результат выполнения тестов и сравнение с UTF-8

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

Устраняем избыточные биты

За основу я взял, конечно, UTF-8. Первое и самое очевидное, что в нём можно поменять уменьшить число служебных бит в каждом байте. Например, первый байт в UTF-8 всегда начинается либо с 0, либо с 11 а префикс 10 есть только у следующих байт. Заменим префикс 11 на 1, а у следующих байт уберём префиксы совсем. Что получится?

0xxxxxxx 1 байт
10xxxxxx xxxxxxxx 2 байта
110xxxxx xxxxxxxx xxxxxxxx 3 байта

Стоп, а где же четырёхбайтовая запись? А она стала не нужна при записи тремя байтами у нас теперь доступен 21 бит и этого с запасом хватает на все числа до 0x10FFFF.

Чем мы пожертвовали тут? Самое главное обнаружением границ символов из произвольного места буфера. Мы не можем ткнуть в произвольный байт и от него найти начало следующего символа. Это ограничение нашего формата, но на практике необходимость в таком встаёт нечасто. Обычно мы способны пробежать буфер с самого начала (особенно когда речь идёт о коротких строках).

Ситуация с покрытием языков 2 байтами тоже стала лучше: теперь двухбайтовый формат даёт диапазон в 14 бит, а это коды до 0x3FFF. Китайцам не везёт (их иероглифы в основном лежат в диапазоне от 0x4E00 до 0x9FFF), но вот грузинам и многим другим народам стало повеселее их языки тоже укладываются в 2 байта на символ.

Вводим состояние энкодера

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

Как было сказано выше, Юникод поделён на плоскости по 65536 кодов каждая. Но это не очень полезное деление (как уже сказано, чаще всего мы находимся в нулевой плоскости). Более интересным является деление на блоки. Эти диапазоны уже не имеют фиксированной длины, и несут больше смысла как правило, каждый объединяет символы одного алфавита.


Блок, содержащий символы бенгальского алфавита. К сожалению, по историческим причинам, это пример не очень плотной упаковки 96 символов хаотично раскиданы по 128 кодовым точкам блока.

Начала блоков и их размеры всегда кратны 16 сделано это просто для удобства. Кроме того, многие блоки начинаются и заканчиваются на значениях, кратных 128 или даже 256 например, основная кириллица занимает 256 байт от 0x0400 до 0x04FF. Это довольно удобно: если мы один раз сохраним префикс 0x04, то дальше любой кириллический символ можно записывать одним байтом. Правда, так мы потеряем возможность вернуться к ASCII (и к любым другим символам вообще). Поэтому делаем так:

1. Два байта 10yyyyyy yxxxxxxx не только обозначают символ с номером yyyyyy yxxxxxxx, но и меняют текущий алфавит на yyyyyy y0000000 (т.е. запоминаем все биты, кроме младших 7 бит);
2. Один байт 0xxxxxxx это символ текущего алфавита. Его нужно просто сложить с тем смещением, которое мы запомнили на шаге 1. Пока алфавит мы не меняли, смещение равно нулю, так что совместимость с ASCII мы сохранили.

Аналогично для кодов, требующих 3 байт:

1. Три байта 110yyyyy yxxxxxxx xxxxxxxx обозначают символ с номером yyyyyy yxxxxxxx xxxxxxxx, меняют текущий алфавит на yyyyyy y0000000 00000000 (запомнили всё, кроме младших 15 бит), и ставят флажок, что мы теперь в длинном режиме (при смене алфавита обратно на двухбайтовый этот флажок мы сбросим);
2. Два байта 0xxxxxxx xxxxxxxx в длинном режиме это символ текущего алфавита. Аналогично, мы складываем его со смещением из шага 1. Вся разница только в том, что теперь мы читаем по два байта (потому что мы переключились в такой режим).

Звучит неплохо: теперь пока нам нужно кодировать символы из одного и того же 7-битного диапазона Юникода, мы тратим 1 лишний байт в начале и всего по байту на каждый символ.


Работа одной из ранних версий. Уже нередко обходит UTF-8, но ещё есть что улучшать.

Что стало хуже? Во-первых, у нас появилось состояние, а именно смещение текущего алфавита и флажок длинного режима. Это нас дополнительно ограничивает: теперь одни и те же символы могут быть закодированы по-разному в разных контекстах. Поиск подстрок, например, придётся делать уже с учётом этого, а не просто сравнивая байты. Во-вторых, как только мы сменили алфавит, стало плохо с кодированием ASCII-символов (а это не только латиница, но и базовая пунктуация, включая пробелы) они требуют повторной смены алфавита в 0, то есть снова лишнего байта (а потом ещё одного, чтобы вернуться к нашему основному).

Один алфавит хорошо, два лучше

Попробуем чуть-чуть поменять наши битовые префиксы, втиснув к трём вышеописанным ещё один:

0xxxxxxx 1 байт в обычном режиме, 2 в длинном
11xxxxxx 1 байт
100xxxxx xxxxxxxx 2 байта
101xxxxx xxxxxxxx xxxxxxxx 3 байта



Теперь в двухбайтовой записи на один доступный бит стало меньше помещаются кодовые точки вплоть до 0x1FFF, а не 0x3FFF. Впрочем, всё ещё ощутимо больше, чем в двухбайтовых кодах UTF-8, большая часть распространённых языков всё ещё влезает, самая заметная потеря выпала хирагана и катакана, японцы в печали.

Что же за новый код 11xxxxxx? Это небольшой загашник размером в 64 символа, он дополняет наш основной алфавит, поэтому я назвал его вспомогательным (auxiliary) алфавитом. Когда мы переключаем текущий алфавит, то кусок старого алфавита становится вспомогательным. Например, переключились с ASCII на кириллицу в загашнике теперь 64 символа, содержащих латиницу, цифры, пробел и запятую (самые частые вставки в не-ASCII текстах). Переключились обратно на ASCII и вспомогательным алфавитом станет основная часть кириллицы.

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

Бонус: обозначив допалфавит префиксом 11xxxxxx и выбрав его начальное смещение равным 0xC0, у нас получается частичная совместимость с CP1252. Иными словами, многие (но не все) западноевропейские тексты, закодированные в CP1252, будут выглядеть так же и в UTF-C.

Тут, правда, возникает трудность: как из основного алфавита получить вспомогательный? Можно оставить то же самое смещение, но увы тут структура Юникода уже играет против нас. Очень часто основная часть алфавита находится не в начале блока (например, русская заглавная А имеет код 0x0410, хотя кириллический блок начинается с 0x0400). Таким образом, взяв в загашник первые 64 символа, мы, возможно, утратим доступ к хвостовой части алфавита.

Для устранения этой проблемы я вручную прошёлся по некоторым блокам, соответствующим различным языкам, и указал для них смещение вспомогательного алфавита внутри основного. Латиницу, в порядке исключения, вообще переупорядочил наподобие base64.

Финальные штрихи

Давайте напоследок подумаем, где мы ещё можем что-то доработать.

Заметим, что формат 101xxxxx xxxxxxxx xxxxxxxx позволяет закодировать числа вплоть до 0x1FFFFF, а Юникод заканчивается раньше, на 0x10FFFF. Иными словами, последняя кодовая точка будет представлена как 10110000 11111111 11111111. Стало быть, мы можем сказать, что если первый байт имеет вид 1011xxxx (где xxxx больше 0), то он обозначает что-то ещё. Например, можно добавить туда ещё 15 символов, постоянно доступные для кодирования одним байтом, но я решил поступить по-другому.

Посмотрим на те блоки Юникода, которые требуют трёх байт сейчас. В основном, как уже было сказано, это китайские иероглифы но с ними трудно что-то сделать, их 21 тысяча. Но ещё туда улетела хирагана с катаканой а их уже не так много, меньше двухсот. И, раз уж мы вспомнили про японцев там же лежат эмодзи (на самом деле они много где раскиданы в Юникоде, но основные блоки в диапазоне 0x1F300 0x1FBFF). Если подумать о том, что сейчас существуют эмодзи, которые собираются из сразу нескольких кодовых точек (например, эмодзи состоит аж из 7 кодов!), то становится совсем жалко тратить на каждую по три байта (73 = 21 байт ради одного значка, кошмар же).

Поэтому выбираем несколько избранных диапазонов, соответствующих эмодзи, хирагане и катакане, перенумеровываем их в один непрерывный список и кодируем в виде двух байт вместо трёх:

1011xxxx xxxxxxxx

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

Попробуем исправить ещё одну проблему. Как мы помним, основной алфавит это по сути старшие 6 бит, которые мы держим в уме, и приклеиваем к коду каждого очередного декодируемого символа. В случае с китайскими иероглифами, которые находятся в блоке 0x4E00 0x9FFF, это либо бит 0, либо 1. Это не очень удобно: нам нужно будет постоянно переключать алфавит между этими двумя значениями (т.е. тратить по три байта). Но заметим, что в длинном режиме из самого кода мы можем вычесть число символов, которое мы кодируем с помощью короткого режима (после всех вышеописанных хитростей это 10240) тогда диапазон иероглифов сместится к 0x2600 0x77FF, и в этом случае на всём этом диапазоне старшие 6 бит (из 21) будут равны 0. Таким образом, последовательности иероглифов будут использовать по два байта на иероглиф (что оптимально для такого большого диапазона), не вызывая переключений алфавита.

Альтернативные решения: SCSU, BOCU-1

Знатоки Unicode, ещё только прочитав название статьи, скорее всего, поспешат напомнить, что непосредственно среди стандартов Юникода есть Standard Compression Scheme for Unicode (SCSU), который описывает способ кодирования, весьма сходный с описанным в статье.

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

Что занятно, SCSU использует идеи, очень похожие на те, к которым я пришёл самостоятельно (вместо понятия алфавитов там используются окна, и их доступно больше, чем у меня). В то же время, у этого формата тоже есть минусы: он чуть ближе к алгоритмам сжатия, нежели кодирования. В частности, стандарт даёт множество способов представления, но не говорит, как выбрать из них оптимальный для этого энкодер должен применять какие-то эвристики. Таким образом, SCSU-энкодер, дающий хорошую упаковку, будет сложнее и более громоздок, чем мой алгоритм.

Для сравнения я перенёс относительно простую реализацию SCSU на JavaScript по объему кода она оказалась сравнима с моим UTF-C, но в ряде случаев показала результат на десятки процентов хуже (иногда она может и превосходить его, но ненамного). Например, тексты на иврите и греческом UTF-C закодировал аж на 60% лучше, чем SCSU (вероятно, из-за их компактных алфавитов).

Отдельно добавлю, что кроме SCSU существует также другой способ компактного представления Юникода BOCU-1, но он ставит целью совместимость с MIME (что мне не требовалось), и использует несколько иной подход к кодированию. Его эффективность я не оценивал, но мне кажется, что она вряд ли будет выше, чем SCSU.

Возможные доработки

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

Например, очевидным образом можно избавиться от наличия состояния, сделать кодирование stateless просто не обновлять переменные offs, auxOffs и is21Bit в энкодере и декодере. В таком случае не получится эффективно упаковывать последовательности символов одного алфавита, зато будет гарантия, что один и тот же символ всегда кодируется одними и теми же байтами, независимо от контекста.

Кроме того, можно заточить кодировщик под конкретный язык, поменяв состояние по умолчанию например, ориентируясь на русские тексты, выставить в начале энкодера и декодера offs = 0x0400 и auxOffs = 0. В особенности это имеет смысл именно в случае stateless режима. В целом это будет похоже на использование старой восьмибитной кодировки, только не лишает возможности вставлять символы из всего Юникода по необходимости.

Ещё один недостаток, упомянутый ранее в объемном тексте, закодированном в UTF-C, нет быстрого способа найти границу символа, ближайшего к произвольному байту. Отрезав от закодированного буфера последние, скажем, 100 байт, вы рискуете получить мусор, с которым ничего не сделать. На хранение многогигабайтных логов кодировка и не рассчитана, но в целом это можно поправить. Байт 0xBF никогда не должен встречаться в качестве первого байта (но может быть вторым или третьим). Поэтому при кодировании можно вставлять последовательность 0xBF 0xBF 0xBF каждые, скажем, 10 Кб тогда при необходимости найти границу будет достаточно просканировать выбранный кусок до тех пор, пока не найдётся подобный маркер. Вслед за последним 0xBF гарантированно будет начало символа. (При декодировании эту последовательность из трёх байт, конечно, нужно будет игнорировать.)

Подводя итог

Если вы дочитали досюда поздравляю! Надеюсь, вы, как и я, узнали что-то новое (или освежили в памяти старое) об устройстве Юникода.


Демонтрационная страница. На примере иврита видны преимущества как перед UTF-8, так и перед SCSU.

Не стоит рассматривать вышеописанные изыскания как посягательство на стандарты. Однако я в целом доволен результатами своих наработок, поэтому рад ими поделиться: например, JS-библиотека в минифицированном виде весит всего 1710 байт (и не имеет зависимостей, конечно). Как я упоминал выше, с её работой можно ознакомиться на демо-страничке (там же есть набор текстов, на которых её можно посравнивать с UTF-8 и SCSU).

Напоследок ещё раз напомню, что закодированная с помощью UTF-C строка не обеспечивает ASCII transparency в ней могут находиться байты, соответствующие ASCII-символам. Попросту говоря использовать её можно только внутренне, в противном случае вы рискуете получить непредвиденные уязвимости.