Utf 8 проверка на ошибки

Use python and str.encode|decode functions.

>>> a="γεια"
>>> a
'xcexb3xcexb5xcexb9xcexb1'
>>> b='xcexb3xcexb5xcexb9xffxb1' # note second-to-last char changed
>>> print b.decode("utf_8")
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "/usr/local/lib/python2.5/encodings/utf_8.py", line 16, in decode
    return codecs.utf_8_decode(input, errors, True)
UnicodeDecodeError: 'utf8' codec can't decode byte 0xff in position 6: unexpected code byte

The exception thrown has the info requested in its .args property.

>>> try: print b.decode("utf_8")
... except UnicodeDecodeError, exc: pass
...
>>> exc
UnicodeDecodeError('utf8', 'xcexb3xcexb5xcexb9xffxb1', 6, 7, 'unexpected code byte')
>>> exc.args
('utf8', 'xcexb3xcexb5xcexb9xffxb1', 6, 7, 'unexpected code byte')

Время на прочтение
4 мин

Количество просмотров 8.7K

Текстовая строка — один из самых распространённых «типов данных» в программировании. Когда программисты думают о строке, то представляют список или массив символов. Это «достаточно хорошее» приближение, но реальность сложнее.

Символы должны быть каким-то образом закодированы в биты. Большинство строк в интернете, включая этот пост на Хабре, закодированы в UTF-8. Формат UTF-8 представляет «символы» в одном, двух, трёх или четырёх байтах. Это обобщение для стандарта ASCII, использующего только один байт на символ. То есть строка ASCII также является строкой UTF-8.

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

Есть и другие стандарты. Некоторые старые языки программирования, такие как C# и Java, полагаются на UTF-16. Там используется два или четыре байта на символ. В то время это казалось хорошей идеей, но сейчас консенсус движется к использованию UTF-8 всегда и везде.

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

Какое это имеет значение? Большое. Например, в веб-сервере Microsoft есть такая уязвимость: он принимает URI, который кажется действительным и безопасным, но после интерпретации сервером даёт злоумышленнику удалённый доступ к диску. Даже если оставить в стороне вопросы безопасности, вы почти наверняка не захотите сохранять недопустимые строки в своей БД.

Таким образом, языки программирования, веб-серверы, браузеры и движки БД постоянно осуществляют валидацию UTF-8.

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

Ещё в 2018 году я задался вопросом: насколько быстро можно валидировать строки UTF-8? В то время я нашёл вариант валидации в несколько циклов CPU на символ. На этом можно было успокоиться, но меня такой ответ не удовлетворил.

Работа заняла годы, но кажется, теперь мы получили вариант, близкий к идеальному. Новый алгоритм на порядок быстрее, чем другие варианты быстрого поиска. Мы подготовили научную статью: «Валидация UTF-8 менее чем за одну инструкцию на байт» (будет опубликована в журнале Software: Practice and Experience), а также опубликовали утилиту для бенчмаркинга.

Все подробности объясняются в научной статье, так что не будем здесь вдаваться в детали, а только вкратце рассмотрим суть. Основная часть валидации UTF-8 выполняется путём поиска пар последовательных байтов. После проверки всех пар байтов и определения всех возможных нарушений, которые можно найти по этой информации, остаётся сделать относительно немного.

Во всех процессорах есть быстрые инструкции SIMD. Они работают с широкими регистрами (128 бит, 256 бит и т. д.). В большинстве наборов имеется инструкция «векторизованного поиска», которая принимает, скажем, 16-байтовые значения (в диапазоне от 0 до 16) и ищет их в 16-байтовой таблице. В процессорах Intel и AMD этому описанию соответствует инструкция pshufb. Значение в диапазоне от 0 до 16 иногда называют nibble, оно охватывает 4 бита. Байт состоит из двух nibble (низкий и высокий).

В нашем алгоритме поиска векторизованная инструкция поиска вызывается три раза: один раз для низкого nibble, один раз для высокого и один раз для высокого nibble следующего байта. У нас три соответствующие 16-байтовые таблицы поиска. Если выбрать их правильно, то побитовое AND из трёх поисков находит любую ошибку.

Подробнее см. в научной статье, но в конечном итоге почти полная валидация UTF-8 выполняется всего пятью строками быстрого кода C++ без каких-либо ветвлений… и эти пять строк за один раз проверяют блоки до 32 байт…

simd8 classify(simd8 input, simd8 previous_input) {
  auto prev1 = input.prev<1>(previous_input);
  auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
  auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
  auto byte_2_high = input.shift_right <4>().lookup_16(table3); 
  return (byte_1_high & byte_1_low & byte_2_high);
}

Хотя это сразу не совсем очевидно, но такой валидации достаточно, и она безопасна на 100%. Это действительно так. Остаётся всего несколько недорогих дополнительных технических шагов.

В результате на последних процессорах Intel/AMD требуется чуть меньше одной инструкции на байт для проверки даже самых мусорных, случайных входных данных. Поскольку код исключительно оптимизированный, вы можете выйти на три инструкции за цикл, и даже больше. То есть мы используем небольшую часть цикла (менее трети) на входной байт на современном CPU. Таким образом, скорость обработки надёжно поддерживается на уровне более 12 ГБ/с.

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

Если вам необходимо использовать функцию быстрой валидации UTF-8 в продакшне, рекомендуем библиотеку simdjson (версия 0.5 или выше). Она хорошо протестирована и имеет полезные встроенные функции, такие как диспетчеризация во время выполнения. Хотя библиотека создана для парсинга JSON, вы можете использовать её чисто для валидации UTF-8, даже если никакого JSON нет. Она поддерживает 64-битные процессоры ARM и x64, а также имеет резервный вариант обработки для других CPU. Мы упаковали её в один заголовочный файл вместе с одним исходным файлом; так что можете просто поместить её в свой проект C++.

Предыдущие работы. Основная заслуга в популяризации метода векторизованной классификации, который является ключом к алгоритму поиска, принадлежит Муле. Насколько мне известно, Кейзер впервые предложил нашу стратегию тройного поиска. Первый практический алгоритм валидации UTF-8 на основе SIMD создал К. Виллетс. Несколько человек, включая З. Вегнера, произвели улучшения в нём. Трэвис Даунс предложил грамотные идеи, как ускорить обычные алгоритмы.

Дальнейшее чтение. Если вам нравится эта работа, то могут понравиться другие статьи на смежные темы: «Кодирование и декодирование Base64 почти со скоростью копирования в памяти» (Software: Practice and Experience, 50 (2), 2020) и «Парсинг гигабайт JSON в секунду» (VLDB Journal, 28 (6), 2019).

(This blog post is now obsolete, see for example Validating UTF-8 bytes using only 0.45 cycles per byte (AVX edition).)

Though character strings are represented as bytes (values in [0,255]), not all sequences of bytes are valid strings. By far the most popular character encoding today is UTF-8, part of the unicode standard. How quickly can we check whether a sequence of bytes is valid UTF-8?

Any ASCII string is a valid UTF-8 string. An ASCII character is simply a byte value in [0,127] or [0x00, 0x7F] in hexadecimal. That is, the most significant bit is always zero.

You can check that a string is made of ASCII characters easily in C:

bool is_ascii(const signed char *c, size_t len) {
  for (size_t i = 0; i < len; i++) {
    if(c[i] < 0) return false;
  }
  return true;
}

However, there are many more unicode characters than can be represented using a single byte. For other characters, outside the ASCII set, we need to use two or more bytes. All of these “fancier” characters are made of sequences of bytes all having the most significant bit set to 1. However, there are somewhat esoteric restrictions:

• • All of the two-byte characters are made of a byte in [0xC2,0xDF] followed by a byte in [0x80,0xBF].
  • There are four types of characters made of three bytes. For example, if the first by is 0xE0, then the next byte must be in [0xA0,0xBF] followed by a byte in [0x80,0xBF].

It is all quite boring but can be summarized by the following table:

So, how quickly can we check whether a string satisfies these conditions?

I went looking for handy C/C++ code. I did not want to use a framework or a command-line tool.

The first thing I found is Björn Höhrmann’s finite-state machine. It looks quite fast. Without getting in the details, given a small table that includes character classes and state transitions, the gist of Höhrmann’s code consists in repeatedly calling this small function:

bool is_ok(uint32_t* state, uint32_t byte) {
  uint32_t type = utf8d[byte];
  *state = utf8d[256 + *state * 16 + type];
  return (*state != 1); // true on error 
}

(In practice, you can do better if you expect the strings to be valid by avoiding the branching on each character.)

Then I went looking for a fancier, vectorized, solution. That is, I want a version that uses advanced vector registers.

I found something sensible by Olivier Goffart. Goffart’s original code translates UTF-8 into UTF-16 which is more than I want done. So I modified his code slightly, mostly by removing the unneeded part. His code will only run on x64 processors.

To test these functions, I wanted to generate quickly some random strings, but to measure accurately the string, I need it to be valid UTF-8. So I simply generated ASCII strings. This makes the problem easier, so I probably underestimate the difficulty of the problem. This problem is obviously dependent on the data type and lots of interesting inputs are mostly just ASCII anyhow.

Olivier Goffart’s code “cheats” and short-circuit the processing when detecting ASCII code. That’s fine, but I created two versions of his function, one with and one without the “cheat”.

So, how quickly can these functions check that strings are valid UTF-8?

My source code is available.

The vectorized code gives us a nice boost… Sadly, in many applications, a lot of the strings can be quite small. In such cases, it seems that we need to spend something close to 8 cycles per byte just to check that the string is valid?

In many cases, you could short-circuit the check and just verify that the string is an ASCII string, but it is still not cheap, at about 2 cycles per input byte.

I would not consider any of the code that I have used to be “highly optimized” so it is likely that we can do much better. How much better remains an open question to me.

Update: Daniel Dunbar wrote on Twitter…

I would expect that in practice best version would be highly optimized ascii only check for short segments, with fallback to full check if any in the segment fail

That is close to Goffart’s approach.

Update: You can accelerate the finite-state machine quite a bit. You can bring it down to about 3 cycles per byte using trick that I attribute to Travis Downs: you split the string into two halves and process both at the same time.