?

Log in

No account? Create an account
nyaload

Журнал Пушыстого

Журнал Пушыстого

Previous Entry Share Flag Next Entry
fast utf-8 validation
nyaload
_winnie
Наткнулся на простую и быструю библиотеку декодирования UTF-8, кроссплатформенную, с валидацией всех возможных ошибок в utf-8 (overlong, surrogate pairs) - http://bjoern.hoehrmann.de/utf-8/decoder/dfa , без бранчинга ( «?:» заменяется на стандатный битхак mask=((int)x-1)>>31), легко векторизуется до чтения dword/qword. Декодирование рассматривается как конечный автомат, конечный автомат загонятся в таблицу [char x state] →state

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

Не законом Мура единым ускоряем софт
Tags:


  • 1
Гениально; непонятно другое, а почему раньше никто ничего такого не написал? Непонятно. На том же юникоде, куча народу такого типа грамотного, бывшие айбиэмовцы. Ну, правда, в их программистских способностях...

А я вот не понимаю, что именно тут гениального. Даже более того, не удивлюсь, если, к примеру, реализация здесь: https://github.com/behdad/harfbuzz/blob/master/src/hb-utf-private.hh (функция hb_utf_next), окажется быстрее.

Ну да, да, видел кучу такого кода. В котором /* TODO check for overlong sequences? */ и капуста из if -

#define HB_UTF8_COMPUTE(Char, Mask, Len) \
if (Char < 128) { Len = 1; Mask = 0x7f; } \
else if ((Char & 0xe0) == 0xc0) { Len = 2; Mask = 0x1f; } \
else if ((Char & 0xf0) == 0xe0) { Len = 3; Mask = 0x0f; } \
else if ((Char & 0xf8) == 0xf0) { Len = 4; Mask = 0x07; } \
else Len = 0;
( можно на табличку по (Char >> 4) заменить )

Вот этот цикл - for (i = 1; i < len; i++) - он на русском тексте срабатывает рандомноо 1 или 2 раза, у процессора нет возможности предсказать ветвление на начало цикла.

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

А как оно на самом деле на Intel'е будет - надо мерять.

опять в спам попал, будь оно всё неладно!

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

  • 1