Разбор быстрого подсчёта длины строки в UTF-8
Давайте попробуем всё-таки разобраться как работает быстрое вычисление длины строки в кодировке 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.
Теперь у нас получился вектор, в котором подсчитаны все внутренние байты символов, а чтобы подсчитать внешние, надо вычесть это число из длины вектора. Правильнее было бы инвертировать сравнение, до этого в разгаре экспериментов просто не дошли руки.
Полученное число мы добавляем к вычисляемой длине и сдвигаем указатель. В конце досчитываем хвост обычным циклом. Конец алгоритма.