Самый эффективный способ поиска последовательности нулевых байт?

Question

[Ukrainskiy]

Нужно найти последовательность нулевых байт определенной длины, memchr нули не ищет, пробовал сделать дополнительный буфер с нулями и искать его с помощью memmem, работает быстро, но не уверен, что это адекватный способ и не хотелось бы выделять под это доп. память. Какие другие способы есть?

Comments

[jcmvbkbc]

memchr нули не ищет

это не так, memchr ищет любые байты, в том числе со значением 0.

[Ukrainskiy]

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

[Василий Дёмин]

Ukrainskiy, В man написано, что она именно байты ищет, а не символы. К тому же она принимает указатель void*, а не char*, длину области памяти и int, как значение поиска. Если бы искала по строке, об этом бы написали в документации, и принимала бы она указатель char*.

[Василий Дёмин]

Ukrainskiy, Вот пример:

#include <stdio.h>
#include <string.h>

int main() {
	char buf[] = {90, 12, 89, 0, 11};
	size_t idx = memchr(buf, 11, sizeof(buf)) - (void*)buf;
	printf("Index of 11 is %lu\n", idx);
	idx = memchr(buf, 0, sizeof(buf)) - (void*)buf;
	printf("Index of 0 is %lu\n", idx);
}

Ссылка на ideone, чтобы сразу его запустить
https://ideone.com/2ZvWDx

[Ukrainskiy]

Василий Дёмин, да, точно. Но мне нужно найти последовательность определенной длины.

[Василий Дёмин]

Ukrainskiy, Неправильно понял ваш вопрос. memchr точно не подходит. Ваш вариант с memmem вполне подходящий, если вас устравивает скорость.

[jcmvbkbc]

это строковая функция и она воспринимает нулевой байт как конец строки.

Ukrainskiy, и это неверно. Функции str* воспринимают 0 как конец строки. Функции mem* принимают в качестве аргумента размер буфера и указатель на него и работают в пределах этого буфера, вне зависимости от того какие там байты.

Answer 1

[Wataru]

Самый эффективный способ - использовать SIMD инструкции (какой-нибудь _mm256_cmpeq_epi8 и хитрую битовую арифметику вроде _mm256_movemask_epi8 и подобных над результатом).

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

Если вы ищите короткую последовательность, то еще нужно прверить, что в текущем болке она встречается. Например, чтобы проверить, что в битовой маске М есть последовательность из 5 бит, можно проверить, что (M & M >> 1) && ((M & M >> 1) >> 2) & M >> 4 имеет ненулевые биты. Достаточно log k сдвигов и битовых И для поиска последовательности из K ненулевых бит.

Но вряд ли вы будете с этим возиться. Следующий вариант - эмулировать SIMD руками в int64. Читайте из памяти по 8 байт (через memcpy в int64) и там уже проверяйте через LSB/MSB сколько нулевых байт на конце, в начале. Чуть сложнее, если вам надо искать последовательность короче восьми байт. Тогда надо еще отдельно проверить через битовые сдвиги, есть ли она внутри блока из 8 байт.

Дальше, есть какой-то ненулевой шанс, что memmem именно вариант выше и реализует, но это вряд ли. Я думаю ваш случай достаточно частен и ручная реализация будет быстрее.