?

Log in

No account? Create an account
nyaload

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

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

Previous Entry Share 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
Это не убирает бранч. Ну и потом, как минимум, есть бранч в цикле прохода по массиву. Чтобы его минимизировать нужно циклы разворачивать.

Бранч в цикле прохода по массиву предсказывается в разы лучше чем бранч, зависящий от структуры utf8 потока.

В коде по ссылке a ? b : c, предлагается заменить это на mask = (a - 1) >> 31; result = (b & mask) | (c & ~mask) с точностью до перемены b/c местами, внутри цикла *state не проверять вообще, и получить безбранчевый код на detect, если в цикле только смотреть, закончился ли стрим (и не делать early reject) - получается почти безбранчевый код проверки utf8.

Спасибо за объяснение! Дело в том, что я подробно не смотрел текст, а, просмотрев по диагонали не нашел объяснения. Даже при повторном просмотре сейчас. :-) Ну да ладно. А зачем >> 31 делать-то? 1-0 = 0, 0-1=0x11111.... То бишь маска получается без сдвига.


Сделать проверку state и окончания цикла почти без бранчей действительно не очень сложно.

Edited at 2013-03-22 05:47 am (UTC)

Ниже _winnie ответил, >> 31 это общий трюк, если a - 0 или 1 строго то да, не надо.

  • 1