Utf 8 может хранить символ более чем в одном байте

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

Пара слов про UTF-8

Perl долгое время ничего не знал про кодировки. Строка была просто последовательностью байтов, каждый держал там все что хотел, и лишь изредка приходилось задумываться о том, какая же все-таки кодировка у этих данных. Времена изменились, появился UTF; поддержать его пришлось и перлистам. Как это обычно бывает, in a perl way. Я надеюсь, что эта статья сбережет немного здоровья тем, кто до сих пор пребывает в неведении относительно реализации UTF-8 в Perl.

Собственно, реализации UTF-8 в Perl было две. Первая появилась в Perl 5.6, но была достаточно сырой и неудобной. Начиная с Perl 5.8 механизм работы с уникодом был радикально пересмотрен, и модули на CPAN запестрили забавными проверками на версию интерпретатора. Все, что написано ниже, относится именно к этой, второй реализации.

За и против

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

Вам наверняка понадобится UTF-8, если Вы не знаете наперед, в каком виде придет приложению очередная порция данных, или разрабатываете международный проект. Ведь даже если Ваш сайт на английском языке, на нем вполне может зарегистрироваться какой-нибудь немец с умляутами в ФИО, или даже житель поднебесной. Простейший способ не задумываться о том, что окажется после этого в БД (ну и о том, как вы будете показывать имя китайца в любимой latin-1) — работать в кодировке, поддерживающей множество языков.

И еще один случай, когда без знакомства с Perl UTF не обойтись — интеграция с работающими в этом формате сторонними компонентами. Например, библиотека XML::LibXML возвращает результаты разбора XML-файлов именно в этом формате.

The Perl Way

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

Стоит упомянуть, что символы UTF-8 в терминологии Perl часто называются wide characters. Если у вас попадаются варнинги с этими словами, значит дело касается уникодных строк.

Модуль Encode

Модуль входит в поставку Perl 5.8, так что использовать его имеет смысл не только для уникода, но и для любых других преобразований кодировки. Работа с модулем не слишком сложна. Единственная проблема — научиться не путать функцию encode с функцией decode :-). Интерфейс у них одинаковый, а логика наименования не настолько очевидна, как хотелось бы. Поскольку формат строк с unicode-флагом считается внутренним форматом, в него нужно декодировать данные из произвольной кодировки (в том числе и UTF-8 без флага), и наоборот, при желании перевести данные в некую внешнюю кодировку, их нужно из внутреннего формата закодировать в нее. Выглядит это примерно так:

use utf8;

PerlIO

Тема Perl IO Layers в принципе заслуживает отдельной статьи. Идея в том, что с некоторых пор старая добрая функция open обзавелась трехаргументным синтаксисом:

Если речь идет о файле, содержащем данные в UTF-8, код можно слегка упростить:

Безусловно, использовать данные модификаторы можно и для модификации файлов — эффект будет обратным.

Грабли

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

use Digest::MD5 ‘md5_hex’;
print md5_hex(«\x<400>«);

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

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

$c = «Мне нравится на Хабре»

Глюк достаточно хорошо виден невооруженным взглядом по специфичным для уникода кракозябрам — ни с чем не спутаешь.

Заключение

Источник

Что нужно знать каждому разработчику о кодировках и наборах символов для работы с текстом

Это первая часть перевода статьи What Every Programmer Absolutely, Positively Needs To Know About Encodings And Character Sets To Work With Text

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

Эта статья о кодировках и наборах символов.

Статья Джоеэля Спольски под названием «Абсолютный минимум о Unicode и наборе символов для каждого разработчика(без исключений!)» будет хорошей вводной и мне доставляет большое удовольствие перечитывать ее время от времени. Я стесняюсь отсылать к ней тех людей, которые испытывают трудности с пониманием проблем с кодировкам, хотя она довольно легкая в плане технических деталей. Я надеюсь, эта статья прольет немного света на то, чем именно являются кодировки, и почему все ваши тексты оказываются испорченными в самый ненужный момент. Статья предназначена для разработчиков(главным образом, на PHP), но пользу от нее может получить любой пользователь компьютера.

Основы

Все более или менее слышали об этом, но каким-то образом знание испаряется, когда дело доходит до обсуждения, так что вот вам: компьютер не может хранить буквы, числа, картинки или что-либо еще. Он может запомнить только биты. Бит имеет только два значения: ДА или НЕТ, ПРАВДА или ЛОЖЬ, 1 или 0 или любую другую пару, которую вы можете вообразить. Раз уж компьютер работает с электричеством, бит представлен электрическим зарядом: он либо есть, либо его нет. Людям проще представлять это в виде 1 и 0, так что я буду придерживаться этих обозначений.

Чтобы с помощью битов представлять нечно полезное, нам нужны правила. Надо сконвертировать последовательность бит в что-то похожее на буквы, числа и изображения, используя схему кодирования, или, коротко, кодировку. Вот так, например:

01100010 01101001 01110100 01110011
b i t s

В этой кодировке, 01100010 представляет из себя ‘b’, 01101001 — ‘i’, 01110100 — ‘t’, 01110011 — ‘s’. Конкретная последовательность бит соответствует букве, а буква – конкретной последовательности битов. Если вы можете запомнить последовательности для 26 букв или умеете действительно быстро находить нужное соответствие, то вы сможете читать биты, как книги.
Упомянутая схема носит название ASCII. Строка с нолями и единицами разбивается на части по 8 бит(по байтам). Кодировка ASCII определяет таблицу перевода байтов в человеческие буквы. Вот небольшой кусочек этой таблицы:

01000001 A
01000010 B
01000011 C
01000100 D
01000101 E
01000110 F

В ней 95 символов, включая буквы от A до Z, в нижнем и верхнем регистре, цифры от 0 до 9, с десяток знаков препинания, амперсанд, знак доллара и прочие. В нее также включены 33 значения, такие как пробел, табуляция, перевод строки, возврат символа и прочие. Это непечатаемые символы, хотя они видимы человеку и используются им. Некоторые значения полезны только компьютеру, такие как коды начала и конца текста. Всего в кодировку ASCII включены 128 символов — прекрасное ровное число для тех, кто смыслит в компьютерах, так как оно использует все комбинации 7ми битов (от 0000000 до 1111111).

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

01001000 01100101 01101100 01101100 01101111 00100000
01010111 01101111 01110010 01101100 01100100

Важные термины

Для кодирования чего-либо в ASCII двигайтесь справа налево, подменяя буквы на биты. Для декодирования битов в символы, следуйте по таблице слева направо, подменяя биты на буквы.

encode |enˈkōd|
verb [ with obj. ]
convert into a coded form
code |kōd|
noun
a system of words, letters, figures, or other symbols substituted for other words, letters, etc.

Кодирование – это представление чего-либо чем-нибудь другим. Кодировка – это набор правил, описывающий способ перевода одного представления в другое.

Прочие термины, заслуживающие прояснения:

Набор символов, чарсет, charset – Набор символов, который может быть закодирован. «Кодировка ASCII включает набор из 128 символов». Синоним к кодировке.

Кодовая страница – страница кодов, закрепляюшая за символом набор битов. Таблица. Синоним к кодировке.

Строка – пачка чего-нибудь, объединенных вместе. Битовая строка – это пачка бит, такая как 00011011. Символьная строка – это пачка символов, например «Вот эта». Синоним к последовательности.

Двоичный, восьмеричный, десятичный, шестнадцатеричный

Существует множество способов записывать числа. 10011111 – это бинарная запись для 237 в восьмеричной, 159 в десятичной и 9F в шестнадцатиричной системах. Значения у всех этих чисел одинаково, но шестнадцатиричная система короче и проще для понимания, чем двоичная. Я буду придерживаться двоичной системы в этой статье, чтобы улучшить понимание и убрать лишний уровень абстракции. Не пугайтесь, встречая коды символов в других нотациях, все значения эквиваленты.

Excusez-Moi?

Раз уж мы теперь знаем, о чем говорим, заметим: 95 символов – это совсем немного, когда речь идет о языках. Этот набор покрывает базовый английский, но как насчет французских символов? А вот это Straßen¬übergangs¬änderungs¬gesetz из немецкого языка? А приглашение на smörgåsbord в шведском? В-общем, не получится. Не в ASCII. Спецификация на представление é, ß, ü, ä, ö просто отсутствует.

“Постойте-ка”, скажут европейцы, “в обычных компьютерах с 8 битами в байте, ASCII никак не использует бит, который всегда равен 0! Мы можем использовать его, чтобы расширить таблицу еще на 128 значений”. И было так. Но способов обозначить звучание гласных еще слишком много. Не все сочетания букв и значений, используемые в европейских языках, влезают в таблицу из 256 записей. Так мир пришел к изобилию кодировок, стандартов, стандартов де-факто и недостандартов, которые покрывают все субнаборы символов. Кому-то понадобилось написать документ на шведском или чешском, и, не найдя нужной кодировки, просто изобрел еще одну. Или я думаю, что все так и произошло.

Не забывайте о русском, хинди, арабском, корейском и множестве других живых языков планеты. Про мертвые уж молчим. Как только вы найдете способ писать документ, использующий несколько языков, попробуйте добавить китайский. Или японский. Оба содержат тысячи символов. И у вас всего 256 значений. Вперед!

Многобайтные кодировки

Для создания таблиц, которые содержат более 256 символов, одного байта просто недостаточно. Двух байтов (16 бит) хватит для кодировки 65536 различных значений. Big-5 например, кодировка двухбайтная. Вместо разбиения последовательности битов в блоки по 8, она использует блоки по 16 битов и содержит большую(я имею ввиду БОЛЬШУЮ) таблицу с соответствием. Big-5 в своем основном виде покрывает большинство символов традиционного китайского. GB18030 – это похожая кодировка, но она включает как традиционный, так и упрощенный китайский. И, прежде чем вы спросите, да, есть кодировки только для упрощенного китайского. А разве одной недостаточно?

Вот кусок таблицы GB18030:

bits character
10000001 01000000 丂
10000001 01000001 丄
10000001 01000010 丅
10000001 01000011 丆
10000001 01000100 丏

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

Путаница с Unicode

В итоге тем, кому больше всех надоела эта каша, пришла в голову идея разработать единый стандарт, объединяющий все кодировки. Этим стандартом стал Unicode. Он определяет невероятную таблицу из 1 114 112 пунктов, используемую для всех вариантов букв и символов. Этого хватит для кодирования всех европейских, средне-азиатских, дальневосточных, южных, северных, западных, доисторических и будущих символов, о которых человечеству известно. Unicode позволяет создать документ на любом языке любыми символами, которые можно ввести в компьютер. Это было невозможно, или очень затруднительно до эры Unicode. В стандарте есть даже неофициальная секция под клингонский. Вы поняли, Unicode настолько большой, чтобы допускает неофициальные секции.

Итак, и сколько же байт использует Unicode для кодирования? Нисколько. Потому что Unicode – это не кодировка.
Смущены? Не вы одни. Unicode в первую и главную очередь определяет таблицу пунктов для символов. Это такой способ сказать «65 – A, 66 – B, 9731 – »(я не шучу, так и есть). Как эти пункты кодируются в байты является предметом другого разговора. Для представления 1 114 112 значений двух байт недостаточно. Трех достаточно, но 3 – странное число, так что 4 является комфортным минимумом. Но, пока вы не используете китайский, или другой язык со множеством символов, которые требуют большого количества битов для кодирования, вам никогда не придет в голову использовать толстую колбасу из 4х байт. Если “A” всегда кодируется в 00000000 00000000 00000000 01000001, а “B” – в 00000000 00000000 00000000 01000010, то документ, использующий такую кодировку, распухнет в 4 раза.

Существует несколько способов решения этой проблемы. UTF-32 – это кодировка, которая переводит все символы в наборы из 32 бит. Это простой алгоритм, но изводящий много места впустую. UTF-16 и UTF-8 являются кодировками с переменной длиной кодирования. Если символ может быть закодирован одним байтом(потому что номер пункта символа очень маленький), UTF-8 закодирует его одним байтом. Если нужно 2 байта, то используется 2 байта. Кодировка сообщает старшими битами, сколькими битами кодируется текущий символ. Такой способ экономит место, но так же и тратит его в случае, если эти сигнальные биты часто используются. UTF-16 является компромиссом: все символы как минимум двухбайтные, но их размер может увеличиваться до 4 байт, если нужно.

character encoding bits
A UTF-8 01000001
A UTF-16 00000000 01000001
A UTF-32 00000000 00000000 00000000 01000001
あ UTF-8 11100011 10000001 10000010
あ UTF-16 00110000 01000010
あ UTF-32 00000000 00000000 00110000 01000010

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

Пункты

Символы определяются по их Unicode-пунктам. Эти пункты записаны в шестнадцатеричной системе и предварены “ U+” (просто для удобство, не значит ничего, кроме “Это пункт Unicode”). Символ Ḁ имеет пункт U+1E00. Иными(десятичными) словами, это 7680й символ таблицы Unicode. Он официально называется “ЛАТИНСКАЯ ЗАГЛАВНАЯ БУКВА А С КОЛЬЦОМ СНИЗУ”.

Ниасилил

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

11000100 01000010 Windows Latin 1 ÄB
11000100 01000010 Mac Roman ƒB
11000100 01000010 GB18030 腂

characters encoding bits

Føö Windows Latin 1 01000110 11111000 11110110
Føö Mac Roman 01000110 10111111 10011010
Føö UTF-8 01000110 11000011 10111000 11000011 10110110

Заблуждения, смущения и проблемы

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

Какого черта мой текст нечитаем?

Если вы откроете документ, и он выглядит так, как текст выше, то причина у этого одна: ваша программа ошиблась с кодировкой. И все. Документ не испорчен(по крайней мере, пока), и не нужно никакое волшебство. Вместо него надо просто выбрать правильную кодировку для отображения текста. Предполагаемый документ выше содержит биты:

10000011 01000111 10000011 10010011 10000011 01010010 10000001 01011011
10000011 01100110 10000011 01000010 10000011 10010011 10000011 01001111
10000010 11001101 10010011 11101111 10000010 10110101 10000010 10101101
10000010 11001000 10000010 10100010

Так, быстренько угадали кодировку? Если вы пожали плечами, то вы правы. Да кто знает?
Попробуем с ASCII. Большая часть этих байтов начинается с 1. Если вы правильно помните, ASCII вообще-то не использует этот бит. Так что ASCII не вариант. Как насчет UTF-8? Большая часть байт не является валидными значениями в этой кодировке. Как насчет Mac Roman(еще одна европейская кодировка)? Хм, для нее эти байты являются правильными значениями. 10000011 декодируетися в ”É”, в “G” и так далее. Так что в Mac Roman текст будет выглядеть так: ÉGÉìÉRÅ[ÉfÉBÉìÉOÇÕìÔǵÇ≠ǻǢ. Правильно? Нет? Может быть? А компьютер-то откуда знает? Может кто-то хотел написать именно это. Насколько я знаю, это может быть последовательностью ДНК! Так и порешим: это Mac Roman, и это ДНК.

Конечно, это полный бред. Правильный ответ таков: текст закодирован в Japanes Shift-JIS и должен выглядеть как エンコーディングは難しくない. Кто бы мог подумать?
Первая причина нечитаемости текста в том, что кто-то пытается прочитать последовательность байт в неверной кодировке. Компьютеру всегда нужно подсказывать. Сам он не догадается. Некоторые типы документов определяют кодировку своего содержимого, но последовательность байт всегда остается черным ящиком.
Большинство браузеров предоставляют возможность указать кодировку страницы с помощью специального пункта меню. Иные программы тоже имеют аналогичные пункты.

У автора нет разбиения на части, но статья и так длинна. Продолжение будет через пару дней.

Источник