Здравствуйте, меня зовут Дмитрий Карловский и я... серийный убийца устоявшихся стандартов. Сегодня я выследил и нанёс критический урон UTF-8. И сейчас я расскажу, как я его переиграл и уничтожил новым стандартом кодирования текста — Unicode Compact Format.
Древний Вавилон
Сначала был 7-битный ASCII и все телетайпы понимали друг друга. И было это хорошо. Но никто не хотел учить английский язык или транслитерировать родной — все хотели говорить на своём. Благо в байте не 7 бит, а 8, а это значит, что туда можно всунуть много самых правильных букв.
И расплодились тогда 100500 кодировок: под каждый язык свои коды букв, а под каждую кодировку свой шрифт. И даже под один язык было более 9000 кодировок: от KOI8-R и CP-866, до Win-1251 и ISO-8859-5. Это привело к самозарождению крякозябр - адовых монстров, съедающих наши любовные послания, и оставляющих вместо них сами знаете что.
В этом свете, невозможность использовать в одном тексте слова на разных языках, была не более чем мелкой букашкой. Не приятно, ну и ладно — наш деды же как-то выжили без этой фичи!
Lingua Franca
И собрались умные мужи со всего мира. И решили они создать единый код, чтобы править всеми. И назвали они его — Юникод.
И появился у каждой буквы свой глобально уникальный номер. И жили мы с тех пор дол... да кого я обманываю — мужи эти быстро поняли, что на все комбинации букв и диактрики никаких кодов не напасёшься, поэтому имеем мы теперь много разных вариантов записи одной буквы, и несколько алгоритмов нормализации текста: NFD, NFC, NFKD, NFKC, KFC.
А чтобы жизнь раем не казалась, придумали они ещё и пачку кодировок:
Двух байтовые: UCS-2 фиксированной ширины и UTF-16 — переменной.
Четырёх байтовые: UCS-4 фиксированной ширины и UTF-32 — переменной.
Происходило же это всё и в разгар битвы тупоконечников с остроязычниками, так что каждая многобайтовая кодировка обзавелась ещё и двумя вариациями с разным порядком байт. А чтобы не запутаться в этом дикообразии, к ним во фронтальную проекцию прикрутили опциональный BOM.
А тут на сцену выходят китайцы, и достают из широких штанин свой GB-18030. Да вы, блин, издеваетесь!
В конце должен остаться только один
В таблице символов Юникода чуть более миллиона позиций, для кодирования которых хватило бы и 20 бит (что не более 3 байт). Но большая часть из них до сих пор не используется, так что пару бит можно смело выкидывать на мороз.
Ещё пара бит тратится на всякую никому не очень нужную экзотику. Так что если очень постараться, можно было бы упаковать все реально используемые письменности в 2 байта, не захламляя Юникод всевозможными картинками. Я вот всё жду, когда же туда начнут добавлять фотки известных личностей — вот тогда-то заживём! Тогда-то и пригодятся зарезервированные 640K значений в середине таблицы...
В этом свете 4-байтовые кодировки выглядят крайне избыточно. Поэтому их никто и не использует. Двухбайтовый UCS же очень удобен в работе, но доминирующий в IT английский текст, раздувается в ней двукратно.
Да и набор из 64К символов в какой-то момент стал всем жать, из-за чего появились костыли в виде суррогатных пар, руинящих все достоинства двухбайтовых кодировок. Но до сих пор многие рантаймы работают с UTF-16 строками в режиме UCS-2 в виде двухбайтовых массивов, то и дело выдавая WTF на суррогатных парах.
Более поздние языки и форматы уже безальтернативно прибили себя за яйца гвоздями к UTF-8, дающему 1 байт на символ для латиницы, 2 — для кирилицы, 3 — для китаицы, и 4 — для урожицы. Упоротый же UTF-1 с кодированием по модулю 160 и запрещённый UTF-7, который авторы наивно хотели использовать в протоколах без экранирования, так и не обрели популярность, поэтому их просто скипаем.
Звездолёты в большом театре
Англосаксы счастливы — у них каждый символ помещается в 1 байт. Но весь остальной мир, в котором на символ нужно минимум 2 байта, даже если он выглядит идентично латинице, тихо завидует и не находит себе места.
UTF-8 довольно простой, если не считать приколов с суррогатными парами, добравшимися и до него. Но добрую треть всех бит он тратит впустую во имя самосинхронизации, вместо того, чтобы потратить их на коды коррекции ошибок. Иначе говоря, решать вопрос битых данных надо не на уровне кодирования текста, а на транспортном уровне, чтобы он гарантировал точную доставку, любых данных. Даже не текстовых.
Так что появление кодировок без этого легаси, было лишь вопросом времени:
SCSU — это расширенная ASCII кодировка, где управляющие коды позволяют переключаться между семибитными однобайтовыми окнами и UTF-16-BE. При этом печатные ASCII символы всегда представляются одним байтом как есть, без переключения режимов.
Для работы с ней требуется куча таблиц и сложные алгоритмы, выбирающие самое компактное представление из нескольких возможных, что не только снижает производительность, но даёт ещё и недетерминированность бинарного представления одних и тех же символов.
BOCU-1 использует разностное кодирование переменной длины по модулю 243. Не смотря на относительную простоту и детерминированность, использование модулей не кратных 2, снижает производительность, так как вместо битовых операций приходится использовать дорогостоящие деления и умножения.
Но что ни сделаешь ради компактности... ведь расстояние между буквами, например, в русском языке не превышает 128, что позволяет уложиться в 1 байт на букву. Но кто же мог подумать, что любой знак препинания или цифра — это уже двухбайтовый прыжок до ASCII и такой же потом обратно? Хорошо хоть для пробела оставили костыль в виде абсолютного однобайтового значения, не влияющего на смещения.
UTF-C — тут товарищ начал за здравие с минимизацией служебных бит, а кончил как обычно: звездолёт с перекодированием таблицы символов под себя, и жонглированием кодов между основной страницей и дополнительной. Пожелаем же ему успехов в ручном переупорядочивании сотен тысяч символов Юникода и дальнейшей поддержке этого форка.
Итого: проблема компактного представления остаётся, а все её решения одно лечат, а другое калечат.
Да придёт спаситель
И тут на сцену выхожу я. Пиво я не пью, так что без долгий прелюдий начинаю отжигать, изобретая Unicode Compact Format...
Для большинства языков хватило бы и 1 байта на символ. Но таких языков много, а в байт помещается всего 256 значений. Следовательно, нам никуда не уйти от "режимов" соответствующим разным письменностям.
Так как символы из разных языков могут смешиваться как угодно, то переключение режима должно иметь минимальный размер и укладываться в 1 байт. Соответственно, число возможных режимов сильно ограничено, деля свои коды с кодами символов.
Таблица Юникод предусмотрительно выровнена по блокам из 128 значений, где самый первый блок идентичен ASCII для совместимости с ним. Отлично, будем использовать эти блоки как узкие станицы. Одним байтом переключились на нужную страницу и далее в рамках этой страницы каждый байт со значением до 128 — один символ. В наихудшем случае будет 2 байта на символ.
Появление байта со значением от 128 уже включает UCF расширения. 100 значений необходимо и достаточно, чтобы покрыть почти все письменности с компактными алфавитами, включая японскую Кану. А это суммарно диапазон в 12_800 символов от начала.
Ещё минимум 4 значения нужно для переключения на широкие страницы, где каждый символ кодируется 2 байтами. В каждую такую страницу влезает 32K значений (половина от первого байта и целиком второй). Этот режим актуален для иероглифического письма типа китайского или зумерского эмодзи.
Если отсчитывать широкие страницы от 0 символа, то базовый набор китайских иероглифов режется между двумя разными страницами, что может приводить к постоянным переключениям режимов. Однако, первый десяток тысяч символов мы уже кодируем узкими страницами, так что смещаем отсчёт широких страниц на 8К и вся китайщина влезает в первую страницу. Voilà!
Кстати, да, французам с диактрикой и украинцам с их Ґ мы помочь не сможем — придётся им переключаться между страницами, что в худшем случае выливается в 3 байта на одиноко стоящий такой символ вместо 2 у UTF-8. Можно было бы, конечно, всё переусложнить и накостылять что-то для одних языков, ценой ухудшения других, но мы такой ерундой страдать не будем. Хотя... может у вас есть светлые идеи на этот счёт?
Однако, заметим, что во всех языках есть включения тех или иных ASCII символов, а значит они должны быть по возможности доступны одним байтом без переключения режима. У нас осталось максимум 23 значения для цифр и базовой ASCII пунктуации, для которых всё же заведём табличку.
Ах, да, осталось ещё 1 значение, которое зарезервируем за переключением в 3-байтовый режим, позволяющий закодировать в 8 раз больше символов, чем вся таблица Юникода, большая часть которой на текущий момент вообще пуста. Нужен он нам лишь на всякий случай, чтобы не не терять данные и не кидать исключения на совсем экзотических кодах, которые в реальных текстах встретятся примерно никогда.
Мексиканская дуэль
Взглянув на референсную реализацию на TS вы можете заметить, что UCF так же прост, как и UTF-8, но при этом в 1.5-2 раза компактнее для почти всех языков:
Английский текст в UCF и в UTF-8 представляется одинаково — как ASCII.
Русский текст в UCF почти в 2 раза компактней, чем в UTF-8.
Китайский — почти в 1.5 раза.
Эмодзи — почти в 2 раза.
По скорости работы UCF и UTF-8 в Chrome примерно одинаковы, если не считать, что нативный UTF-8 энкодер в V8 — редкостный тормоз, поэтому я и запилил свой:
Сравнение с SCSU, BOCU-1 и UTF-C оставлю вам в качестве домашнего задания. По этим данным сжимают они примерно так же, а работают медленнее. Если потребуется, моя либа доступна не только в экосистеме MAM, но и в NPM.
И в чём я не прав?
Я много над всем этим думал (целую неделю), перепробовал кучу вариантов, игрался с константами, списывал у соседей, но пришёл к тому, что вы сейчас видите. Понятное дело, что никто не побежит сейчас внедрять этот формат в свои проекты, протоколы, языки. Ведь всё уже устоялось, и вообще наступил конец истории.
Однако, видя не совершенство мира, я не могу устоять от соблазна сделать его чуточку лучше. Поэтому я планирую внедрить UCF в свой форма�� бинаризации произвольных данных VaryPack, который используется в моей децентрализованной базе реального времени Giper Baza, у которой есть все задатки стать основой Web4. И совершенно не хочется тянуть легаси в будущее, в то время как есть возможность всё исправить, и не мучать наших правнуков призраками прошлого.
Но я всего-лишь человек с двумя глазами и двумя полушариями. Я могу что-то не заметить, до чего-то не догадаться. Поэтому я публикую эту статью в надежде, что вы поможете подсветить все возможные косяки или подкинуть интересных идей, пока яйца веба будущего ещё свободны.
Если вам интересна вся эта движуха, то присоединяйтесь к нашему ламповому сообществу самых заряженных разрабов Гипер Дев, а то и поддержите нас рублём. Чем нас больше, и чем мы активнее, тем большие горы мы сможем свернуть вместе. Не ссыте, прорвёмся!
