utf8

Сегодня очень плохо спал — всё время просыпался, потом долго ворочался, не мог уснуть. Утром оказалось мозг никак не мог успокоиться после вчерашней заметки про разбор быстрого алгоритма для подсчёта длины строки в UTF-8 при помощи векторизации для процессоров ARM.

Вчера я остановился на том, что у разбираемого способа есть две очевидные недоработки — ненужное вычисление, которое решается инвертированием условия и подсчёт «хвоста», который всегда вычисляется «классическим» способом — без векторизации, хотя если строка у нас кратна вектору, можно было бы этого избежать.

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

Зато, когда я проснулся, она уже была у меня в голове. Всего три операции — первой получаем вектор, где на позициях с ненулевым байтом записывается 255, потом делается операция «И» с номерами позиций и весь вектор суммируется.

В итоге, если ноль стоит в векторе только на крайней правой позиции, у нас получается сумма арифметической прогрессии без последнего элемента.

По замерам такой вариант чуть быстрее.

size_t strlen_utf8(unsigned char * p) {
    size_t len = 0;

    const int8x16_t threshold = vdupq_n_s8(-63);
    const uint8x16_t delta = vdupq_n_u8(1);

    for(;;) {
        int8x16_t operand = vld1q_s8((const int8_t * ) p);
        if (vminvq_u8(operand) == 0) {
            uint8x16_t pos = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
            uint8_t sum = vaddvq_u8(vandq_u8(vtstq_u8(operand, operand), pos));

            // арифметическая прогрессия без последнего члена
            if (sum == 16*(16+1) / 2 - 16) {
                uint8x16_t gt = vcgtq_s8(operand, threshold);
                return len + vaddvq_u8(vandq_u8(gt, delta)) - 1;
            } else {
                break;
            }
        }

        uint8x16_t gt = vcgtq_s8(operand, threshold);
        len += vaddvq_u8(vandq_u8(gt, delta));
        p += sizeof(uint8x16_t);
    }

    for (signed char c; (c = *p); p++) {
        if (c >= -64) {
            len++;
        }
    }

    return len;
}

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

Напомню как выглядел код:

size_t strlen_php(unsigned char * p) {
    size_t len = 0;

    const int8x16_t threshold = vdupq_n_s8(-64);
    const uint8x16_t delta = vdupq_n_u8(1);

    for(;;) {
        int8x16_t operand = vld1q_s8((const int8_t * ) p);
        if (vminvq_u8(operand) == 0) {
            break;
        }

        uint8x16_t lt = vcltq_s8(operand, threshold);
        len += sizeof(uint8x16_t) - vaddvq_u8(vandq_u8(lt, delta));
        p += sizeof(uint8x16_t);
    }

    for (signed char c; (c = *p); p++) {
        if (c >= -64) {
            len++;
        }
    }

    return len;
}

Для ускорения подсчёта в алгоритме используется векторизация, — это когда мы работаем с пачкой чисел, делая над каждым из них какое-то действие за одну операцию. В данном случае используется вектор 8×16 — шестнадцать значений по восемь бит (типы uint8x16_t и int8x16_t).

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

Ниже используется функция vminvq_u8, которая вычисляет минимальное значение в векторе, рассматривая его как набор байтов без знака. Если там ноль, значит строка кончилась и в нашем векторе — хвост, который надо досчитать обычным способом, без вектора. Тут можно было бы проверить на какой позиции слева находится признак конца строки, если на самой последней, то строка была кратна вектору. Но я не стал заморачиваться. Но такая проверка оказалась медленнее подсчёта длины хвоста обычным способом.

Дальше функция vcltq_s8 сравнивает каждый байт в векторе со значением −64  — это значение загружается в каждый элемент вектора для сравнения функцией vdupq_n_s8.

Результирующий вектор заполняется значениями 0 или 255, в зависимости от результата сравнения. Функция vandq_u8 производит операцию «И» с единицей, после чего у нас в векторе ноль остаётся неизменным, а 255 превращается в единицу. Эти единицы мы суммируем функцией vaddvq_u8.

Теперь у нас получился вектор, в котором подсчитаны все внутренние байты символов, а чтобы подсчитать внешние, надо вычесть это число из длины вектора. Правильнее было бы инвертировать сравнение, до этого в разгаре экспериментов просто не дошли руки.

Полученное число мы добавляем к вычисляемой длине и сдвигаем указатель. В конце досчитываем хвост обычным циклом. Конец алгоритма.

В Телеграме попросили рассказать как работает код, который я приводил вчера в заметке про ускорение функции, возвращающей количество символов в строке с кодировкой UTF-8.

Там действительно есть что рассказать, но рассказ придётся разбить на несколько частей. Я постараюсь по возможности не погружаться в дебри. В этой части начну с того, что расскажу чем вообще необычна эта кодировка.

Все кодировки условно можно разделить на две части: кодирующие символ фиксированным или переменным количеством байт. К первым можно отнести, например, CP1251, когда-то широко используемую в ОС «Виндоуз» — там символ кодировался одним байтом, ко вторым — UTF-8, где один символ может занимать от одного до четырёх байт.

Справедливости ради, есть и другие виды кодирования, но нам их рассматривать ни к чему.

Тут важно то, что для строки в UTF-8, нельзя получить её длину, подсчитав количество байт и разделив их на коэффициент хранения. Для каждого байта нам надо понять что он кодирует и считать только те байты, которые отвечают за начало символа. Как это сделать?

Посмотрим на картинку из «Википедии», которая показывает как устроена эта кодировка:

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

То есть, байты в диапазоне от 10000000 до 10111111 (в бинарном представлении) — внутренние байты, остальные — начало символа. Опять же, согласно таблице начала попадают в диапазоны 00000000-01111111 и от 11000000 до 11011111.

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

#include <stdio.h>

int main() {
    const signed char arr[] = {
        0b10000000, 0b10111111, 0b00000000, 0b01111111, 0b11000000, 0b11011111
    };

    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
        for (int b = 128; b; b >>= 1) {
            printf("%d", (arr[b] & i) > 0);
        }

        printf(" % d\n", arr[i]);
    }
}

Вот что она выводит (диапазон, в котором находятся внутренние байты, я выделил другим цветом):

Закономерность в том, что все внутренние байты в знаковом представлении по значению меньше −64. Это довольно дешёвая проверка с точки зрения машинного кода, что очень хорошо, так как наша цель — производительность.

Про остальное — в следующий раз.

Пока проект внедрения Юникода во «Флиппер Зеро» на паузе, — разработчики занимаются обновлением одной из важных библиотек, я вспомнил, что вообще-то в природе существуют разные способы ускорения обработки строки в кодировке UTF-8. Именно её я выбрал для хранения строк. А поскольку железо у «Флиппера» весьма ограниченное, может быть имеет смысл подумать как сэкономить ресурсы.

Например, когда-то, ещё во времена работы в «Яндексе», я сравнивал между собой различные реализации функции strlen, где ускорение достигалось за счёт векторизации.

Любопытно посмотреть как обстоят дела с ускорением таких вещей на процессоре, который установлен на «Флиппере». Правда до него у меня руки ещё не дошли, но я уже потренировался на своём «Макбуке», благо тут процессор той же архитектуры.

Идея всё та же — векторизация. За референс я взял наивную реализацию с перебором по одному байту:

size_t strlen_naive(const char* str) {
    size_t len = 0;
    char ch;
	
    while ((ch = *str++)) {
        len += (ch & 0b11000000) != 0b10000000;
    }

    return len;
}

Попробовал несколько вариантов, но лучше всех показали себя две функции: та, которую я упоминал в первом абзаце и переделанная нашими общими с братишкой усилиями реализация, найденная в недрах PHP.

После переделки она стала выглядеть так:

size_t strlen_php(unsigned char * p) {
    size_t len = 0;

    const int8x16_t threshold = vdupq_n_s8(-64);
    const uint8x16_t delta = vdupq_n_u8(1);

    for(;;) {
        int8x16_t operand = vld1q_s8((const int8_t * ) p);
        if (vminvq_u8(operand) == 0) {
            break;
        }

        uint8x16_t lt = vcltq_s8(operand, threshold);
        len += sizeof(uint8x16_t) - vaddvq_u8(vandq_u8(lt, delta));
        p += sizeof(uint8x16_t);
    }

    for (signed char c; (c = *p); p++) {
        if (c >= -64) {
            len++;
        }
    }

    return len;
}

Повторюсь, у меня пока не дошли руки попробовать это всё на «Флиппере», но на моём «Макбуке» результаты выглядят следующим образом. Это десять тысяч прогонов на русскоязычном тексте, размер которого чуть больше ста тысяч символов.

Name   Length  Time
----   ------  ----
PHP    117465   97797
Fast   117465  143780
Naïve  117465  531535

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

Цифры в попугаях (больше — хуже), которые выдаёт сишная функция clock(), компилировал компилятором Clang 15 с ключом -O3.

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

С различными кодировками сейчас мало где можно столкнуться, тем не менее мне неясно в чём сложность задачи. Вроде даже ничего знать не надо.

Например, я вижу вот такую строку: Требуется авторизация. Она так выглядит, потому что она была в кодировке UTF-8, но код подумал, что она с CP1251 и перекодировал её в UTF-8. Предположим это всё известно, как вернуть всё в норму и посмотреть что там написано?

Почему-то мало кто справляется с задачей в такой формулировке. Вроде всё просто — строка перекодировалась из CP1251 в UTF-8, значит надо перекодировать по этой цепочке обратно:

iconv -f utf8 -t cp1251 <<<"Требуется авторизация"
Требуется авторизация

Продолжаю писать про портирование «Гопника-2» под «Виндоуз», ибо там ещё есть о чём рассказать.

Я уже очень давно не работаю под этой операционной системой, поэтому некоторые обычные, возможно, для многих вещи для меня являются открытием. Когда я начинал процесс портирования игры под эту платформу, я был уверен, что столкнусь в трудностями совершенно в других частях кода. Одной из неожиданностей была плохая работа «Виндоуз» с кодировкой ЮТФ-8.

Если вывод в консоль удалось победить сравнительно легко, то со вводом возникли проблемы — вызов SetConsoleCP(CP_UTF8), который должен был помочь, не помог. В интернете пишут, что он, по всей видимости, не реализован — просто не делает ничего.

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

Рекомендуемый специалистами способ — переключить консоль в режим ввода кодировки ЮТФ-16, а потом перекодировать полученную строку в нужную кодировку. «Виндозу» ЮТФ-16 родная, поэтому проблем вообще никаких не возникает.

#ifdef __MINGW32__
        int wlen = 100;
        int save = _setmode(_fileno(stdin), _O_U16TEXT);
        wchar_t *wstr = (wchar_t *) malloc(wlen * sizeof(wchar_t));
        fgetws(wstr, wlen, stdin);

        int len = WideCharToMultiByte(CP_UTF8, 0, wstr, -1, 0, 0, 0, 0);
        user_name = (char *) malloc(len);
        WideCharToMultiByte(CP_UTF8, 0, wstr, -1, user_name, len, 0, 0);
        _setmode(_fileno(stdin), save);

        free(wstr);
#endif

Мне, к счастью, ввод русских букв нужен только в одном месте — там где игрок вводит своё имя. Я убрал используемую там функцию fgets под условную компиляцию и вставил кусок, который выше. С таким исправлением всё заработало, как ожидается.

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

Как я уже писал, мне понравилась библиотека RE2, я даже скомпилировал её и посмотрел, к сожалению, оказалось, что она использует треды, а в PHP с этим не очень (не все модули PHP thread safe, поэтому чаще всего PHP собирается без поддержки тредов).

Я уже начал смотреть другие библиотеки, когда Алексей Захлестин напомнил мне про модуль PHP Multibyte String (функции mb_*), который содержит в себе движок регулярных выражений Oniguruma.

Я всегда плохо относился к этому движку, так как считал, что у него очень бедные возможности для работы с UTF-8, так как там не работают \p, \P и есть ещё пара недостатков (возможно они имеют место из-за того, что в PHP используется версия 4.7.1, тогда как последняя 5.9.2).

Сегодня я присмотрелся к движку получше. Конечно, PCRE он не заменит, но некоторых случаях вполне сможет его подменить как быстрый аналог, только надо применять несколько правил (речь идёт о версии 4.7.1, которая в PHP):

Во-первых, модификатор „i“ не действует ни на какие буквы, кроме латинских, я перебрал весь Unicode, чтобы в этом убедиться.

Во-вторых, \b и \B внутри […] относятся к backspace, а не к word boundary, а \h и \H к hex digit, а не к horizontal whitespace.

В-третьих, не работают \p и \P, зато (хоть какая-то замена) с UTF-8 работают :…: (всякие там :space: и прочие).

В-четвёртых, есть синтаксис [a-w&&[^c-g]z], то есть «&» надо экранировать внутри диапазонов.

В-пятых, части синтаксиса PCRE просто нет, например, нет рекурсии, условных регулярок, но тут уже надо обращаться к документации.

Я погонял тесты, сравнивал PCRE в режиме полном UTF-8 (с «глаголом» UCP) и Oniguruma, по результатам последний в 4…4,5 раза быстрее:

bolk-dev ~/regexp-benchmark $ php test.php
PCRE Full UTF-8: 1.0458080768585
Oniguruma:         0.24942803382874

Как я уже писал, сегодня ночью я наткнулся на вариант измерения длины UTF-8 строки, написанный с применением ассемблерных иструкций SSE2. У этого кода есть недостаток — на каких-нибудь ARM он не заработает, с другой стороны, у меня нет такой потребности, запускать PHP на этих процессорах.

Сегодня я почистил код (в PHP известна бинарная длина строки, поэтому я убрал проверки на символ с кодом ноль и соптимизировал код), сгенерировал таблицу HammingWeight, которая отсутствует в коде автора и перевёл проверку в двух крайних циклах на подобную таблицу.

Потом это всё скомпилировал и погонял тесты.

Сначала я получил очень странные результаты и только потом понял что случилось. В общем, разрыв в скорости функций (mb_strlen и той, что на SSE2) тем больше, чем ближе тестируемая строка к однобайтовой. Чаще всего, с SSE2 быстрее встроенной в PHP в 5—8 раз:

thasonic-dev ~/uni/futf-0.1 $ php ../test/test_strlen.php | sort -k2 -t:
SSE2 UTF-8:                 0.025604963302612
mb_strlen:                   0.15917205810547
strlen/utf8_decode:   0.62052989006042

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

В общем, о приросте в 24 раза остаётся только мечтать.

Похоже, это почти предел на сегодняшний момент. Единственная возможность ускорения, которая приходит в голову — использовать GPU на видеокарте. Например, видеокарта GTX275 управляется с 16000 потоков (!), что позволяет подсчитать длину строки порциями по 15,5КБ!

Но это больше из разряда задач-головоломок, чем чего-то практического — у нас на серверах таких видеокарт нет и вряд ли появятся, пока интерпретаторы-флагманы не заявят у себя поддержку GPU.

Так что оставлю как есть, займусь переписываем substr в SSE2, а потом выложу всё в открытый доступ.

Добавлено позднее: в следующем году Intel и AMD выпустят процессоры, поддерживающие набор комманд AVX, интересно там то, что размер регистров SIMD (которые используются и в SSE) расширяется до 256 бит. То есть через годик-другой можно будет читать строку сразу по 32 байта за раз.

Из кода быстрой функции strlen для UTF-8 можно получить функцию substr. Николай Захаров, который работает со мной в группе внутренних сервисов, переделал strlen в substr.

Я вкомпилил эту функцию в PHP, помог найти ошибки и отладить и сделал замеры:

bolk-dev ~/uni/futf-0.1 $ php ../test/test_substr.php  | sort -k2 -t:
Fast UTF-8: 0.18010711669922
mb_substr:  0.87068700790405

Разница примерно в 4 раза. Я ещё попробовал отрезать строку через функцию preg_match, сравнимо по скорости с mb_substr, но медленнее и есть ограничение — квантификатор preg_match не захватывает больше 65535 символов.

Добавлено позднее: после того как мы отладили эту функцию, я вспомнил про команды ассемблера SSE — это наборы команд (сейчас их пять — SSE1, 2, 3, 4.1 и 4.2), которые оперируют восемью регистрами размером 128 бит.

Как я рассказывал, самый быстрый алгоритм для strlen, который я нашёл, работает следующим образом: сначала указатель на строку первым циклом выравнивается по границе 4 или 8 байт (в зависимости от архитектуры процессора), чтобы процессор смог быстрее читать дальше, потом, работая сразу с числом длиной 4 или 8 байт, одной операцией подсчитывается сколько в выделенной строке содержится начальных байт символов.

Если внутри нашего рабочего участка встречается символ с кодом ноль (признак конца строки), то происходит выход в последний цикл, который занимается тем, что просматривает побайтно получившийся «хвост».

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

Час назад я поставил себе gcc под Windows и стал потихоньку писать примерный код, читать документацию, изучать команды в интернете, пока совершенно случайно не наткнулся на уже готовый вариант, написанный с применением инструкций SSE2.

Нашёл в интернете тест для таких функций, включил туда найденную и сделал замеры:

C:\MinGW\bin\test.exe
cp_strlen_utf8:          0.105706
cp_strlen_utf8_sse2: 0.030002

В 3,5 раза обгоняет предыдущий вариант, то есть, смею надеяться, обгонит встроенную в PHP функцию примерно в 24 раза. Завтра попробую.

Немаловажно, что даже на машинах с архитектурой 32 бита рассматриваемый вариант покажет ту же скорость, что и на машинах 64 бита.

Поговорил с одним из разработчиков PHP по поводу судьбы PHP6, самое ожидаемое изменение которого — переход на юникодные строки. Так вот Антон Довгаль рассказал, что проект, по сути, заброшен. Те несколько человек, которые занимались проектом, либо уволились, либо потеряли к нему интерес и сейчас считается, что поддержка юникодных строк в языке не так уж и нужна.

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

То, что в PHP приходится для поддержки Юникода работать с UTF-8, а не с UTF-32 сильно снижает производительность всех строковых операций. И добро бы, если бы для всех функций были юникодные аналоги, так это ведь не так.

Работать в PHP с UTF-32 нельзя, если вы собираетесь использовать регулярные выражения: библиотека PCRE, предназначенная для работы с регулярными выражениями, понимает только две кодировки: latin-1 (по всей видимости) и UTF-8. Кроме того, функции, использующие локаль или ICU так же работают только с UTF-8.

Если бы этот язык нативно поддерживал UTF-32… Мечты-мечты.

Я потихоньку буду писать как получается оптимизировать самые важные функции работы с UTF-8 в PHP. Оформлять буду как продолжение своей эпопеи перевода наше внутренней «Вики» на UTF-8 (в ближайшее время добавлю оглавление).

Сейчас, после перевода «Вики» мы столкнулись с тем, что некоторые операции занимают непозволительно много времени. Кое-какие проблемы решаются моими итераторами для строки (прямым и обратным), но и другие оптимизации приходится делать.

Простые оптимизации я уже применил: выкинул из класса UTF-8 проверки на self::ON (по этой константе я определял включена ли в проекте поддержка UTF-8, сейчас в ней необходимости уже нет) и сделал другие микрооптимизации, теперь пора посмотреть на методы моего класса UTF.

Одна из самых частоиспользуемых функций — strlen, которая определяет длину строки. Я всегда считал, что самый быстрый способ подсчитать длину UTF-строки в PHP, это вызывать strlen(utf8_decode(…)).

Мои тесты показывают что это не так. Самый быстрый способ (по крайней мере в PHP 5.3.2) — это mb_strlen, strlen/utf8_decode — на втором месте, потом идёт sizeof+preg_split, а самый медленный — iconv_strlen.

Для интереса я вкомпилил в PHP функцию для быстрого подсчёта длины строки в UTF-8, найденную в интернете, выигрыш по сравнению с mb_strlen незначителен:

bolk-dev ~/uni/ $ php ../test/test_strlen.php | sort -k2 -t:
Fast UTF-8: 0.68232107162476
mb_strlen: 0.88710689544678
strlen/utf8_decode: 1.5211808681488

Это тысяча итераций на файле в 400КБ.

Я оставил функцию mb_strlen.

Добавлено позднее: другая быстрая функция дала ещё худший результат: 0,79, против прежнего варианта в 0,68.

Добавлено ещё позже: а вот третья функция показала действительно впечатляющие результаты:

bolk-dev ~/uni/ $ php ../test/test_strlen.php | sort -k2 -t:
More Fast UTF-8:  0.12948799133301
mb_strlen: 0.88710689544678
strlen/utf8_decode: 1.5211808681488

Это уже дело — она почти в 7 раз быстрее лучшего результата PHP.

Вкратце, алгоритм такой: строка циклом выравнивается по границе четырёх (на 64-битных системах — 8) байт, далее читается сразу по четыре (или восемь) байт и внутри каждого кусочка одним выражением считается сколько там байт, с которых начинается символ. Поэтому на моей 64-битной системе семикратный выигрыш (на 32 битах будет примерно в три раза).

Добавлено через несколько дней: есть и ещё более быстрая функция.

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

# вот эти файлы перекодировать не надо, они у меня уже в UTF-8
SKIPIT='./php/Utf.php|./php/UtfReverseString.php|./php/UtfString.php'
tmp=`tempfile`

for line in $(find -name '*.php' -or -name '*.tpl' -or -name '*.inc' | egrep -v "$SKIPIT"); do
    iconv -fcp1251 -tutf8 "$line" -o "$tmp"
    [ -e "$tmp" ] && mv -f "$tmp" "$line"
done

mysqldump -pпароль -uпользователь --add-drop-table --create-options --default-character-set=utf8 --order-by-primary -q база |
sed -e 's/cp1251;$/utf8;/mg' |
mysql -pпароль -uпользователь база

В прошлый раз я рассматривал, по сути, самый сложный этап — замену всех вхождений $var[$index] и им подобных на вызов моей функции. В процессе замены я несколько раз корректировал заметку и доводил некоторые вещи руками.

mkdir /tmp/pcre
cd !:1
wget ftp://ftp.csx.cam.ac.uk/pub/software/programming/pcre/pcre-8.10.tar.bz2
tar xvfj pcre-8.10.tar.bz2
cd pcre-8.10
./configure --prefix=/usr/local/pcre-8.10 --enable-utf8 --enable-unicode-properties --disable-static
make && make install
cd -

wget /files/php_fresh_pcre.zip
unzip php_fresh_pcre.zip
phpize
./configure --with-ygx-regex=/usr/local/pcre-8.10
make && sudo make install
phpize --clean
cd ; rm -rf /tmp/pcre

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

Я такой парсер начал писать несколько дней назад и очень быстро увидел, куда меня этот путь ведёт. К сожалению, из-за выбранных предпосылок код пришлось выкинуть — я парсил всё регулярными выражениями.

Код я выкинул и начал писать заново, основываясь на токенах (лексемах), которое выдаёт встроенное в язык API токинайзера. По ходу процесса я часто уточнял случаи и производил тестирование. Получился довольно неряшливый парсер, к тому же с некоторыми багами, которые я счёл несущественными. Например, не обрабатывается ситуация isset($var, $var[$idx]).

В PHP isset (а так же empty и unset) — конструкции, а не функции и принимают на вход только переменные. У меня получение символа по индексу заменяется на Utf::get(…), а внутри строки на другую конструкцию — $_ENV[0x5f3759df]->get(…), так что если произойдёт замена внутри isset, будет синтаксическая ошибка.

Т. е. у меня в коде, внутри файла с классом Utf есть ещё и такая строка — «$_ENV[0x5f3759df] = new Utf();». $_ENV я выбрал за то, что это переменная (а переменную внутри строки проще заменять на другую переменную, пусть и с вызовом метода, PHP это позволяется) и это, в терминах PHP, «суперглобальный» массив, то есть он доступен отовсюду.

Итак, я сказал, что парсер имеет баги, но на весь довольно большой код у меня было всего четыре случая, правда один довольно странный — пропала треть исходного кода, так что, если будете применять — сохраните оригинальный код (мой лежал в SVN).

Первая операция, которую вам нужно сделать ещё до запуска парсера — это запустить следующий скрипт. У меня парсер работает с UTF-8, а исходники у меня пока ещё в CP1251. Так что парсер сначала перекодирует код в UTF-8, потом обратно в CP1251. Но я беспокоился — не испортит ли двойная перекодировка что-то в исходниках.

Так что я перекодировал код туда и обратно и сравнил что получилось:

for file in $(find -name '*.php' -or -name '*.inc' -or -name '*.tpl'); do
    sum_new=`iconv -fcp1251 -tutf8 "$file" | iconv -futf8 -tcp1251 | md5sum -b | cut -d' ' -f1`
    sum_orig=`md5sum -b "$file" | cut -d' ' -f1`

    if [ $sum_new != $sum_orig ]; then
        echo $sum_new $sum_orig $file
    fi
done

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

find -name '*.php' -or -name '*.inc' -or -name '*.tpl' | xargs php -l

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

Добавлено позднее: а вот как выглядит метод get в классе Utf:

static public function get($str, $index)
    {
        if (!is_scalar($str)) {
            return isset($str[$index]) ? $str[$index] : null;
        }

        return self::substr($str, $index, 1);
    }

Добавлено позже: нашёл ещё два бага: неверно отрабатываются «$prop[$idx]->value» и «$str[$idx] ==». Второе надо править в регулярном выражении. Я их править не буду, они запросто ищутся утилитой «grep» и правятся руками. Кроме того, не заменяются переменные в heredoc (мне это не нужно).

Конструкции heredoc я нашёл при помощи «grep -FR ’<<<’ *» и просмотрел их все, их было очень мало и ни одна из них не содержала переменных.

Добавлено ещё позже: опаснее оказалась ситуация, которую просто так можно и не заметить: замена вызова func($var[$index]) на func(Utf::get($var, $index), где прототип func описан как func(&$var). Синтаксис PHP вполне допускает такие ситуации, а на деле в массив могут не попасть изменения, которые должны были переданы быть по ссылке.

Способов исправить такую ситуацию два. Первый — логгировать все вызовы Utf::get, которые применяются к массивам и править их на получение переменной по индексу. Второй — найти и просмотреть все такие ситуации. Я выбрал второй способ:

find \( -name '*.php' -or -name '*.tpl' -or -name '*.inc' \) |
xargs egrep -oh 'ion[\t ]+\w+[\t ]*([^{]+' | awk -F'[( ]' '/&\$/{print tolower($2)}' |
sort -u | egrep -v '^preg_' | xargs -I{} egrep -iR  --exclude-dir=.svn {}'[\t ]*(.*?Utf::get' *

Этот скрипт (который очень долго работает) показывает все подозрительные строки (у меня их 7 оказалось), их надо просмотреть, выявить потенциально проблемные и поправить, если проблема действительно есть.

И ещё позже: так же есть набор встроенных функций, которые используют передачу массива по ссылке, я их нашёл вот таким способом:

(cat<<FUNCS
'\b(?:array_multisort|array_pop|array_push|\
array_replace_recursive|array_replace|\
array_shift|array_splice|\
array_unshift|array_walk_recursive|\
array_walk|arsort|asort|current|each|\
end|key|krsort|ksort|natcasesort|natsort|\
next|pos|prev|reset|rsort|shuffle|\
sort|uasort|uksort|usort)[ \t]*\([\t ]*[^$)]'
FUNCS
) | xargs -I[] find \( -name '*.tpl' -or -name '*.php' -or -name '*.inc' \) -exec \
egrep [] {} \; -print

Итак, я достаточно долго думал над задачей как мне заменить все операции получения символа из строки по индексу, чтобы понять насколько она сложна. Решить её можно, но скучно и не нужно. Я подумал, что очень вряд ли у меня в коде встречаются все возможные случаи, которые я рассмотрел в прошлый раз, поэтому я решил посмотреть что же у меня встречается на самом делом.

bolk@dev:~/daproject$ find \( -name '*.php' -or -name '*.inc' -or -name '*.tpl' \) -exec \
egrep '\$\{?[a-zA-Z_\x7f-\xff][a-zA-Z0-9_\x7f-\xff]*[\[\{]' -- {} \; |
sort -u | tee out-vars-1.log | wc -l

3670

bolk@wiki:~/daproject$ IFS='\n'
for line in $(cat out-vars-1.log); do
(echo $line | sed -r 's/\$\w+\[\]//g' | egrep -q '\$\{?\w+[\[\{]') && echo $line
done | sed -r 's/^\s+//' | awk '!t[$0]++' | tee out-vars-2.log | wc -l

3357

bolk@dev:~/daproject$ IFS='\n'
for line in $(cat out-vars-2.log); do
(echo $line | sed -r 's/\$\w+[\[\{](["'\''])[^\1]*\1(\]|\})([^\[\{])/\2/g' | egrep -q '\$\{?\w+[\[\{]') && echo $line
done | tee out-vars-3.log | wc -l

1353

Работаю с низким приоритетом над автоматической заменой операций получения символа в строке по индексу на такую же операцию, но которая умела бы работать с UTF-8. Оказалось, что задача очень сложная.

Давайте я вам про Unicode ещё раз расскажу?

Как известно, в памяти компьютера числа представлены битами, которые группируются в байты. Один байт может хранить одно из 256 значений (поскольку состоит из восьми бит, каждый из которых может хранить одно из двух). Следовательно, числа, значения которых > 255 хранятся в больше, чем одном байте.

Например, числа до 65535 можно уместить уже в двух байтах: в так называемом старшем записывается сколько раз полных 256 содержится в числе, а в младшем — остаток: старший × 256 + младший.

В зависимости от типа процессора, порядок, в котором записаны в памяти старшие и младшие байты, различается. Собственно, мне хорошо известны только две системы: младший записывается первым (как в процессорах Intel) и старший записывается первым (в процессорах ARM, которые стоят в смартфонах). Есть ещё смешанная, но с ней я не сталкивался. Системы эти носят имена: little-endian и big-endian (системы со смешанным порядком называются middle-endian и термин не указывает на то как именно «мешается» этот порядок). Краткая запись названий — LE и BE.

Есть ещё системы, которые умеют переключать порядок (те же ARM) и называются bi-endian.

Термины little-endian и big-endian пришли к нам из «Приключений Гулливера» и на русский переводятся как «тупоконечный» и «остроконечный». Те, кто читали, те помнят (война по поводу того с какой стороны разбивать яйца). Информатика тут какбэ намекает. Хотя у каждой системы есть свои достоинства и (не удержался) мне ближе LE.

Сюрприз для непрограммистов: буквы в памяти компьютера тоже представлены числом. Это просто номер по порядку в компьютерном алфавите. Так девочки в нашем классе «кодировали» записки: вместо букв ставили номер позиции в алфавите. В чём-то они были правы, но только не в том, что это шифр.

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

Было принято очевидное решение — выделять на символ не один байт, а несколько. Так появился стандарт Unicode, где огромному количеству символов дано своё число и закреплены начертания, стандарт дополняется и новые версии выходят почти каждый год.

Система кодирования Unicode, где выделяются два байта, называется UTF-16 (16 бит на символ), там где четыре байта — UTF-32 (32 бита). Название UCS-4 (четыре байта) является синонимом UTF-32, а UCS-2 (два байта) подмножеством UTF-16. UCS-2 отличается от UTF-16 отсутствием так называемых «суррогатных пар» (которые появились только в Unicode 2.0, вы не хотите знать что это) и является устаревшим стандартом, можете про него забыть.

Так как способов хранения чисел, не умещающихся в памяти у нас несколько, то системы подразделяются на UTF-16BE, UTF-16LE, UTF-32BE и UTF-32LE. Отсюда видно, что UCS-4LE это тоже, что и UTF-32LE. Если порядок байт не указан, то принято считать, что используется big-endian.

Первого апреля 2005-го года были предложены шуточные «стандарты» UTF-9 и UTF-18, отношения к рассматриваемой проблеме они имеют. Для телеграфа и прочего слоновьего гуано, разрабатывались UTF-5 и UTF-6, но о их судьбе мне ничего не известно. Так же есть UTF-7, который в стандарт не вошёл, но реально применяется (в модифицированном виде) внутри почтового протокола IMAP4, про него я рассказывать не буду, мне он стал известен из-за оригинального способа его использования для XSS-атак в IE (в частности, решением этой проблемы я занимался в PEAR PHP классе HTML_Safe). Можно упомянуть ещё UTF-1, но с ней я не сталкивался в работе.

BOM. BOM расшифровывается как «byte order mark» (признак порядка байт) и ставится внутри файлов упомянутых двух- и четырёхбайтных кодировок. Если BOM внутри файла не встретился, принимается порядок big-endian. У BOM есть значание. В UCS-2 это 65279 (для программистов — FEFF), для UCS-4/UTF-32 — это 4278124544 (FEFF0000). Число выбрано так, чтобы старшие и младшие байты у них не совпадали и по их порядку можно было бы определить какой порядок байт используется. К сожалению, BOM не даёт возможности определить использутеся двух- или четырёхбайтная кодировка.

Теперь непрограммистам будет трудно.

Пока всё было достаточно просто, но человечество придумало ещё одну кодировку — UTF-8, с плавающим размером. Хорошие новости заключаются в том, что порядок следования байт тут определён и никаких LE и BE рядом с UTF-8 не ставится. Соотвественно и BOM тут не нужен. Он может использоваться только для того, чтобы указать программе, что это именно UTF-8 и имеет номер 15711167 (EF BB BF). Откуда можно сделать вывод (дорогие писатели редакторов), что использование в UTF-8 BOM от UTF-16 — ошибка.

Трудность в том, что UTF-8, по сути это ещё один способ записи многобайтовых чисел (а каждая буква в стандарте Unicode — многобайтовое число). У системы есть целых два плюса (ирония!): старая однобайтовая кодировка совместима с UTF-8, а значит буржуинам не нужно переделывать свои программы, если они не используют в них буквы и других языков (например, на любом старом англоязычном сайте как бы уже используется кодировка UTF-8), второй плюс — латиница записывается компактнее (в один символ). Минусы — чисто программисткие: работа с кодировкой требует больше ресурсов из-за плавающего размера.

Итак. Каждый символ в кодировке занимает от 1 до 4-х байт. Вообще, формат устроен так, что можно было бы взять и более длинные цепочки, но в Unicode нет столько символов, чтобы записывать их более длинными последовательностями.

Тут надо вспомнить что такое биты. Бит — единица информации, мельче не бывает, у него всего два значения — 0 или 1. Байт состоит из 8 битов, биты очень удобно записывать в позиционной двоичной системе: 00001011. «Позиционная» тут означает, что значение числа зависит от его позиции. Кстати, это привычная нам система. В числе «22» две двойки, но у первой значение в десять раз больше, чем у второй. Это десятичная позиционная система. В двоичной, каждая более левая однёрка будет больше в два раза своей соседки.

Таким образом число 1011 расшифровывается из двоичной как 1 × 2³ + 0 × 2² + 1 × 2¹ + 1 × 2⁰ = 1 × 8 + 1 × 2 + 1 × 1 = 8 + 2 + 1 = 11 в десятичной системе.

UTF-8 устроен следующим образом. Пусть, мы двигаемся по строке, содержащей два байта: 208 и 159. В битах это 11010000 и 10011111. (Немного осталось, потерпите).

В первом символе нужно посчитать количество бит со значением «1» до первого нуля. Это общее количество байт, которым записан данный символ. Если количество байт — один (это вроде как специальный признак), то вы нашли не первый байт символа.

У нас в примере количество бит до первого нуля — два. Значит, буква записана двумя символами — первый это тот, на которым мы находимся и второй — который следует за ним. Каждый байт в UTF-8 разбит на две части — до первого нулевого бита. Первая часть — общая длина байт последовательности, а оставшаяся — значение. Биты из значения записывают последовательно (у нас это 10000 011111) и смотрят какое число получилось (у нас это — 1055, это номер буквы «П» в Unicode).

Могу рассказать про UTF-7 и UTF-1, если интересно. Или про суррогатные пары.

Решил протестировать — чем быстрее всего можно отрезать строку в кодировке UTF-8. В PHP для этой цели (помимо использования извращений, типа SQL-запроса) можно использовать: mb_substr из модуля «Multibyte string function», iconv_substr из модуля iconv, preg_replace в режиме UTF-8 из Perl-Compatible regular expression function и собственную реализацию прохода по UTF-8 строке.

Я взял строку в 700 UTF-8-символов и отрезал от неё 500 разными функциями. Вот что получилось (PHP 5.2.4 без акселераторов):

• хуже всех справилась реализация на чистом PHP — 0.34 сек
• получше — iconv_substr. 0.063 сек
• ещё лучше — mb_substr. 0.0175 сек
• лучше всех — preg_replace. 0.005 сек
  Если кому интересно, вот моя функция по проходу по строке в кодировке UTF-8:

$len = strlen($text);
    for ($pos = $cutted = 0; $cutted < $cut && $pos < $len; ++$cutted)
    {
            $ch = ord($text[$pos]);

            // multibyte char
            if (0x80 & $ch)
            {
                    for (; $ch & 0x80; ++$pos, $ch <<= 1);
            }
            else
            {
                    $pos++;
            }
    }

Итак, лучший способ отрезать первые $N символов UTF-8 таков:

preg_replace('/^(.{'.$N.'}).*$/uSs', '$1', $text)