Мне нужно сканировать 16-битное слово в битовом потоке. Не гарантируется выравнивание по границам байтов или слов.
Каков самый быстрый способ достичь этого? Существуют различные методы грубой силы; используя таблицы и/или сдвиги, но есть ли какие-нибудь "быстрые сокращения бит", которые могут сократить количество вычислений, давая да/нет/может содержать результаты флага для каждого байта или слова по мере его поступления?
Код C, intrinsics, машинный код x86 будут интересны.
Иногда полезно использовать простую грубую силу.
Я думаю, что precalc все сдвинутые значения слова и положить их в 16 дюймов
таким образом, вы получили такой массив (при условии, что int в два раза шире, чем short)
unsigned short pattern = 1234;
unsigned int preShifts[16];
unsigned int masks[16];
int i;
for(i=0; i<16; i++)
{
preShifts[i] = (unsigned int)(pattern<<i); //gets promoted to int
masks[i] = (unsigned int) (0xffff<<i);
}
и затем для каждого неподписанного короткого замыкания, которое вы выводите из потока, сделайте int этого короткого и предыдущего короткого замыкания и сравните это беззнаковое int с 16 неподписанными целыми числами. Если кто-то из них совпадает, у вас есть один.
Так в основном так:
int numMatch(unsigned short curWord, unsigned short prevWord)
{
int numHits = 0;
int combinedWords = (prevWord<<16) + curWord;
int i=0;
for(i=0; i<16; i++)
{
if((combinedWords & masks[i]) == preShifsts[i]) numHits++;
}
return numHits;
}
Обратите внимание, что это может означать многократные попадания, когда шаблоны обнаруживаются более одного раза в одних и тех же битах:
например 32 бита из 0, и шаблон, который вы хотите обнаружить, равен 16, то это будет означать, что шаблон будет обнаружен 16 раз!
Затраты времени на это, если предположить, что они составляются примерно так, как написано, составляют 16 проверок на входное слово. Для каждого входного бита это делает одно & и ==, а также ветвление или другое условное приращение. А также поиск таблицы по маске для каждого бита.
Поиск в таблице не нужен; вместо этого, сдвигая вправо combined, мы получаем значительно более эффективный asm, как показано в другом ответе, который также показывает, как векторизовать это с помощью SIMD на x86.
Вот трюк, чтобы ускорить поиск в 32 раза, если ни алгоритм Кнута-Морриса-Пратта на алфавите из двух символов {0, 1}, ни идея инициализации достаточно быстры.
Сначала вы можете использовать таблицу с 256 элементами для проверки каждого байта в битовом потоке, если он содержится в 16-битном слове, который вы ищете. Таблица, которую вы получаете с помощью
unsigned char table[256];
for (int i=0; i<256; i++)
table[i] = 0; // initialize with false
for (i=0; i<8; i++)
table[(word >> i) & 0xff] = 1; // mark contained bytes with true
Затем вы можете найти возможные позиции для совпадений в потоке бит, используя
for (i=0; i<length; i++) {
if (table[bitstream[i]]) {
// here comes the code which checks if there is really a match
}
}
Как минимум 8 из 256 записей таблицы не равны нулю, в среднем вам нужно пристально смотреть только на каждую 32-ю позицию. Только для этого байта (в сочетании с байтами один до и после) вы должны использовать битовые операции или некоторые маскирующие методы, как это было предложено повторно, чтобы увидеть, есть ли совпадение.
В коде предполагается, что вы используете небольшой порядковый номер байта. Порядок бит в байте также может быть проблемой (известной всем, кто уже реализовал контрольную сумму CRC32).
Я хотел бы предложить решение с использованием 3 справочных таблиц размером 256. Это было бы эффективно для больших потоков битов. Это решение занимает 3 байта в образце для сравнения. На следующем рисунке показаны все возможные варианты размещения 16-битных данных в 3 байта. Каждая область байта показана другим цветом.
альтернативный текст http://img70.imageshack.us/img70/8711/80541519.jpg
Здесь будет проверяться от 1 до 8 в первом примере и от 9 до 16 в следующем и так далее. Теперь, когда мы ищем паттерн, мы найдем все 8 возможных расположений (как показано ниже) этого паттерна и сохраним их в 3 справочных таблицах (левый, средний и правый).
Инициализация таблиц поиска:
Давайте возьмем пример 0111011101110111 в качестве шаблона для поиска. Теперь рассмотрим 4-ю договоренность. Левая часть будет XXX01110. Заполните все строки левой справочной таблицы, указывая левой частью (XXX01110), на 00010000. 1 указывает начальную позицию расположения входного паттерна. Таким образом, следующие 8 строк таблицы поиска слева будут заполнены на 16 (00010000).
00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110
Средняя часть договоренности будет 11101110. Необработанный указатель по этому индексу (238) в средней 00010000 таблице будет заполнен на 16 (00010000).
Теперь правая часть аранжировки будет 111XXXXX. Все строки (32 строки) с индексом 111XXXXX будут заполнены на 16 (00010000).
Мы не должны перезаписывать элементы в таблице поиска при заполнении. Вместо этого выполните побитовую операцию ИЛИ, чтобы обновить уже заполненную строку. В вышеприведенном примере все исходные тексты, написанные по 3-му расположению, будут обновлены по 7-му расположению следующим образом
Таким образом, необработанные данные с индексом XX011101 в справочной таблице Left и 11101110 в справочной таблице Middle и 111XXXXX в справочной таблице Right будут обновлены до 00100010 по 7-му 00100010.
Шаблон поиска:
Взять образец из трех байтов. Найдите Count следующим образом, где Left - это левая таблица, Middle - средняя таблица, а Right - правая таблица.
Count = Left[Byte0] & Middle[Byte1] & Right[Byte2];
Число 1 в подсчете дает номер соответствующего шаблона в взятом образце.
Я могу дать пример кода, который тестируется.
Инициализация таблицы поиска:
for( RightShift = 0; RightShift < 8; RightShift++ )
{
LeftShift = 8 - RightShift;
Starting = 128 >> RightShift;
Byte = MSB >> RightShift;
Count = 0xFF >> LeftShift;
for( i = 0; i <= Count; i++ )
{
Index = ( i << LeftShift ) | Byte;
Left[Index] |= Starting;
}
Byte = LSB << LeftShift;
Count = 0xFF >> RightShift;
for( i = 0; i <= Count; i++ )
{
Index = i | Byte;
Right[Index] |= Starting;
}
Index = ( unsigned char )(( Pattern >> RightShift ) & 0xFF );
Middle[Index] |= Starting;
}
Шаблон поиска:
Данные - это буфер потока, слева - левая таблица поиска, середина - средняя таблица просмотра, а справа - правая таблица поиска.
for( int Index = 1; Index < ( StreamLength - 1); Index++ )
{
Count = Left[Data[Index - 1]] & Middle[Data[Index]] & Right[Data[Index + 1]];
if( Count )
{
TotalCount += GetNumberOfOnes( Count );
}
}
Ограничение:
Вышеуказанный цикл не может обнаружить шаблон, если он размещен в самом конце буфера потока. Следующий код необходимо добавить после цикла, чтобы преодолеть это ограничение.
Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;
if( Count )
{
TotalCount += GetNumberOfOnes( Count );
}
Преимущество:
Этот алгоритм выполняет только N-1 логических шагов, чтобы найти шаблон в массиве из N байтов. Только накладные расходы должны заполнить таблицы поиска изначально, что является постоянным во всех случаях. Так что это будет очень эффективно для поиска огромных потоков байтов.
Мои деньги на Knuth-Morris-Pratt с алфавитом из двух символов.
Я бы выполнил машину состояний с 16 состояниями.
Каждое состояние показывает, сколько принятых бит соответствует шаблону. Если следующий полученный бит соответствует следующему бит шаблона, машина переходит к следующему состоянию. Если это не так, машина возвращается к первому состоянию (или к другому состоянию, если начало шаблона можно сопоставить с меньшим количеством принятых бит).
Когда машина достигает последнего состояния, это указывает на то, что шаблон был идентифицирован в потоке бит.
atomice
выглядел хорошо, пока я не рассмотрел просьбы Люка и MSalter о дополнительной информации о деталях.
Выясняется, что данные могут указывать на более быстрый подход, чем KMP. Статья KMP ссылается на
для конкретного случая, когда шаблон поиска равен "AAAAAA". Для поиска нескольких шаблонов
может быть наиболее подходящим.
Вы можете найти дальнейшее вводное обсуждение здесь.
Похоже, что это полезно для инструкций SIMD. SSE2 добавила кучу целых инструкций для одновременного хрустания нескольких целых чисел, но я не могу представить много решений для этого, которые не связаны с большим количеством сдвигов бит, поскольку ваши данные не будут выровнены. Это действительно звучит как нечто, что нужно делать FPGA.
Что бы я сделал, это создать 16 префиксов и 16 суффиксов. Затем для каждого 16-битного входного блока определяют самый длинный суффикс. У вас есть соответствие, если следующий фрагмент имеет префиксное соответствие длины (16-N)
Совпадение суффиксов на самом деле не является 16 сравнениями. Однако это требует предварительного расчета на основе слова шаблона. Например, если шаблонное слово 101010101010101010, вы можете сначала протестировать последний бит вашего 16-битного входного блока. Если этот бит равен 0, вам нужно всего лишь проверить... 10101010. Если последний бит равен 1, вам нужно проверить... 1010101. У вас по 8 штук, в общей сложности 1 + 8 сравнений. Если шаблонное слово 1111111111110000, вы все равно будете тестировать последний бит вашего ввода для суффикса. Если этот бит равен 1, вам нужно выполнить 12 совпадений суффикса (regex: 1 {1,12}), но если он равен 0, у вас есть только 4 возможных совпадения (regex 1111 1111 1111 0 {1,4}), снова для среднего из 9 тестов. Добавьте соответствие префикса 16-N, и вы увидите, что вам нужно всего 10 проверок на 16-битный кусок.
Для универсального, не-SIMD-алгоритма вы вряд ли сможете сделать гораздо лучше, чем что-то вроде этого:
unsigned int const pattern = pattern to search for
unsigned int accumulator = first three input bytes
do
{
bool const found = ( ((accumulator ) & ((1<<16)-1)) == pattern )
| ( ((accumulator>>1) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>2) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>3) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>4) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>5) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>6) & ((1<<16)-1)) == pattern );
| ( ((accumulator>>7) & ((1<<16)-1)) == pattern );
if( found ) { /* pattern found */ }
accumulator >>= 8;
unsigned int const data = next input byte
accumulator |= (data<<8);
} while( there is input data left );
Вы можете использовать быстрое преобразование Фурье для чрезвычайно большого ввода (значение n) для поиска любой битовой диаграммы в O (n log n) времени. Вычислите кросс-корреляцию битовой маски с входом. Кросс-корреляция последовательности x и маски y с размером n и n 'соответственно определяется
R(m) = sum _ k = 0 ^ n' x_{k+m} y_k
то вхождения вашего битового шаблона, которые точно соответствуют маске, где R (m) = Y, где Y - сумма одного в вашей битовой маске.
Итак, если вы пытаетесь сопоставить шаблон бит
[0 0 1 0 1 0]
в
[ 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1]
то вы должны использовать маску
[-1 -1 1 -1 1 -1]
-1 в маске гарантирует, что эти места должны быть 0.
Вы можете реализовать кросс-корреляцию, используя FFT в O (n log n) времени.
Я думаю, что KMP имеет O (n + k) время исполнения, поэтому он превосходит это.
Возможно, вам нужно передать поток в потоке вектора (vec_str), поток в вашем шаблоне в другом векторе (vec_pattern), а затем сделать что-то вроде алгоритма ниже
i=0
while i<vec_pattern.length
j=0
while j<vec_str.length
if (vec_str[j] xor vec_pattern[i])
i=0
j++
(надеюсь, что алгоритм верен)
Более простой способ реализации простого алгоритма грубой силы @Toad, который проверяет каждую битовую позицию, - это смещение данных на место, а не смещение маски. Нет необходимости в каких-либо массивах, гораздо проще просто сдвинуть вправо в combined >>= 1 внутри цикла и сравнить младшие 16 бит. (Либо используйте фиксированную маску, либо uint16_t к uint16_t.)
(Из множества проблем я заметил, что создание маски обычно менее эффективно, чем просто удаление ненужных битов.)
(Правильная обработка самого последнего 16-битного фрагмента массива uint16_t, или, особенно, последнего байта массива байтов нечетного размера, оставлена в качестве упражнения для читателя.)
// simple brute-force scalar version, checks every bit position 1 at a time.
long bitstream_search_rshift(uint8_t *buf, size_t len, unsigned short pattern)
{
uint16_t *bufshort = (uint16_t*)buf; // maybe unsafe type punning
len /= 2;
for (size_t i = 0 ; i<len-1 ; i++) {
//unsigned short curWord = bufshort[i];
//unsigned short prevWord = bufshort[i+1];
//int combinedWords = (prevWord<<16) + curWord;
uint32_t combined; // assumes little-endian
memcpy(&combined, bufshort+i, sizeof(combined)); // safe unaligned load
for(int bitpos=0; bitpos<16; bitpos++) {
if( (combined&0xFFFF) == pattern) // compiles more efficiently on e.g. old ARM32 without UBFX than (uint16_t)combined
return i*16 + bitpos;
combined >>= 1;
}
}
return -1;
}
Это компилирует значительно более эффективно, чем загрузка маски из массива с последними gcc и clang для большинства ISA, таких как x86, AArch64 и ARM.
Компиляторы полностью развертывают цикл на 16, поэтому они могут использовать инструкции извлечения битового поля с непосредственными операндами (такими как ubfx битового ubfx без знака ARM ubfx или PowerPC rwlinm rotate-left + немедленная маска диапазона битов) для извлечения 16 битов в rwlinm 32 или 64-битный регистр, где они могут выполнять обычное сравнение и ветвление. На самом деле нет цепочки зависимостей правых сдвигов на 1.
На x86 процессор может делать 16-битное сравнение, которое игнорирует старшие биты, например, cmp cx,dx после сдвига вправо, combined в edx
Некоторые компиляторы для некоторых ISA справляются с версией @Toad так же хорошо, как и с этой версией, например, clang для PowerPC оптимизирует массив масок, используя rlwinm для маскирования 16-битного диапазона, combined с использованием немедленных rlwinm, и сохраняет все 16 предварительно смещенных значений паттернов в 16 регистрах, так что в любом случае это просто rlwinm/compare/branch, имеет ли rlwinm ненулевой счетчик поворота или нет. Но версия с правым сдвигом не требует установки 16 регистров tmp. https://godbolt.org/z/8mUaDI
Есть (по крайней мере) 2 способа сделать это:
С 64-разрядными сдвигами элементов вместо 32, мы могли бы проверять несколько смежных 16-разрядных окон вместо того, чтобы всегда игнорировать верхние 16 (где смещены нули). Но у нас все еще есть разрыв на границах элементов SIMD, где смещены нули вместо фактических данных с более высокого адреса. (Будущее решение: двойные смены VPSHRDW, такие как VPSHRDW, SIMD-версия SHRD.)
Возможно, в любом случае это стоит сделать, а затем вернуться к 4х 16-битным элементам, которые мы пропустили вверху каждого 64-битного элемента в __m256i. Возможно объединение остатков по нескольким векторам.
// simple brute force, broadcast 32 bits and then search for a 16-bit match at bit offset 0..15
#ifdef __AVX2__
#include <immintrin.h>
long bitstream_search_avx2(uint8_t *buf, size_t len, unsigned short pattern)
{
__m256i vpat = _mm256_set1_epi32(pattern);
len /= 2;
uint16_t *bufshort = (uint16_t*)buf;
for (size_t i = 0 ; i<len-1 ; i++) {
uint32_t combined; // assumes little-endian
memcpy(&combined, bufshort+i, sizeof(combined)); // safe unaligned load
__m256i v = _mm256_set1_epi32(combined);
// __m256i vlo = _mm256_srlv_epi32(v, _mm256_set_epi32(7,6,5,4,3,2,1,0));
// __m256i vhi = _mm256_srli_epi32(vlo, 8);
// shift counts set up to match lane ordering for vpacksswb
// SRLVD cost: Skylake: as fast as other shifts: 1 uop, 2-per-clock
// * Haswell: 3 uops
// * Ryzen: 1 uop, but 3c latency and 2c throughput. Or 4c / 4c for ymm 2 uop version
// * Excavator: latency worse than PSRLD xmm, imm8 by 1c, same throughput. XMM: 3c latency / 1c tput. YMM: 3c latency / 2c tput. (http://users.atw.hu/instlatx64/AuthenticAMD0660F51_K15_BristolRidge_InstLatX64.txt) Agner numbers are different.
__m256i vlo = _mm256_srlv_epi32(v, _mm256_set_epi32(11,10,9,8, 3,2,1,0));
__m256i vhi = _mm256_srlv_epi32(v, _mm256_set_epi32(15,14,13,12, 7,6,5,4));
__m256i cmplo = _mm256_cmpeq_epi16(vlo, vpat); // low 16 of every 32-bit element = useful
__m256i cmphi = _mm256_cmpeq_epi16(vhi, vpat);
__m256i cmp_packed = _mm256_packs_epi16(cmplo, cmphi); // 8-bit elements, preserves sign bit
unsigned cmpmask = _mm256_movemask_epi8(cmp_packed);
cmpmask &= 0x55555555; // discard odd bits
if (cmpmask) {
return i*16 + __builtin_ctz(cmpmask)/2;
}
}
return -1;
}
#endif
Это хорошо для поисков, которые обычно быстро обнаруживают попадание, особенно если данные меньше, чем первые 32 байта. Это неплохо для больших поисков (но все еще чисто грубая сила, проверяющая только одно слово за раз), и на Skylake, возможно, не хуже, чем проверка 16 смещений нескольких окон параллельно.
Это настроено для Skylake, на других процессорах, где переменные смещения менее эффективны, вы можете рассмотреть только 1 переменное смещение для смещений 0..7, а затем создать смещения 8..15, сдвигая это. Или что-то еще полностью.
Это на удивление хорошо компилируется с gcc/clang (на Godbolt) с внутренним циклом, который вещает прямо из памяти. (Оптимизация невыровненной загрузки memcpy и set1() в один vpbroadcastd)
Также на ссылку Godbolt тест main, который запускает его на небольшом массиве. (Возможно, я не проверял с момента последней настройки, но я проверял это раньше, и упаковка + бит-сканирование работает.)
## clang8.0 -O3 -march=skylake inner loop
.LBB0_2: # =>This Inner Loop Header: Depth=1
vpbroadcastd ymm3, dword ptr [rdi + 2*rdx] # broadcast load
vpsrlvd ymm4, ymm3, ymm1
vpsrlvd ymm3, ymm3, ymm2 # shift 2 ways
vpcmpeqw ymm4, ymm4, ymm0
vpcmpeqw ymm3, ymm3, ymm0 # compare those results
vpacksswb ymm3, ymm4, ymm3 # pack to 8-bit elements
vpmovmskb ecx, ymm3 # scalar bitmask
and ecx, 1431655765 # see if any even elements matched
jne .LBB0_4 # break out of the loop on found, going to a tzcnt / ... epilogue
add rdx, 1
add r8, 16 # stupid compiler, calculate this with a multiply on a hit.
cmp rdx, rsi
jb .LBB0_2 # } while(i<len-1);
# fall through to not-found.
Это 8 мопов работы + 3 мопов накладных расходов цикла (при условии макро-слияния и /jne, и cmp/jb, которые мы получим на Haswell/Skylake). На AMD, где 256-битные инструкции являются множественными мопами, это будет больше.
Или, конечно, используя простое немедленное смещение вправо, чтобы сместить все элементы на 1, и проверить несколько окон параллельно вместо нескольких смещений в одном окне.
Без эффективного смещения переменных (особенно без AVX2) это было бы лучше для больших поисков, даже если для определения местоположения первого попадания в случае попадания требуется немного больше работы. (После обнаружения попадания где-то, кроме самого нижнего элемента, вам нужно проверить все оставшиеся смещения всех предыдущих окон.)
Быстрый способ поиска совпадений в больших битовых строках состоял бы в вычислении таблицы поиска, которая показывает смещения бит, когда данный входной байт соответствует шаблону. Затем, комбинируя три совпадающих смещения, вы можете получить бит-вектор, который показывает, какие смещения соответствуют всему шаблону. Например, если байт x соответствует первым 3 битам шаблона, байт x + 1 соответствует битам 3..11, а байт x + 2 соответствует битам 11..16, то есть совпадение в байтах x + 5 бит.
Вот пример кода, который делает это, накапливая результаты для двух байтов за раз:
void find_matches(unsigned char* sequence, int n_sequence, unsigned short pattern) {
if (n_sequence < 2)
return; // 0 and 1 byte bitstring can't match a short
// Calculate a lookup table that shows for each byte at what bit offsets
// the pattern could match.
unsigned int match_offsets[256];
for (unsigned int in_byte = 0; in_byte < 256; in_byte++) {
match_offsets[in_byte] = 0xFF;
for (int bit = 0; bit < 24; bit++) {
match_offsets[in_byte] <<= 1;
unsigned int mask = (0xFF0000 >> bit) & 0xFFFF;
unsigned int match_location = (in_byte << 16) >> bit;
match_offsets[in_byte] |= !((match_location ^ pattern) & mask);
}
}
// Go through the input 2 bytes at a time, looking up where they match and
// anding together the matches offsetted by one byte. Each bit offset then
// shows if the input sequence is consistent with the pattern matching at
// that position. This is anded together with the large offsets of the next
// result to get a single match over 3 bytes.
unsigned int curr, next;
curr = 0;
for (int pos = 0; pos < n_sequence-1; pos+=2) {
next = ((match_offsets[sequence[pos]] << 8) | 0xFF) & match_offsets[sequence[pos+1]];
unsigned short match = curr & (next >> 16);
if (match)
output_match(pos, match);
curr = next;
}
// Handle the possible odd byte at the end
if (n_sequence & 1) {
next = (match_offsets[sequence[n_sequence-1]] << 8) | 0xFF;
unsigned short match = curr & (next >> 16);
if (match)
output_match(n_sequence-1, match);
}
}
void output_match(int pos, unsigned short match) {
for (int bit = 15; bit >= 0; bit--) {
if (match & 1) {
printf("Bitstring match at byte %d bit %d\n", (pos-2) + bit/8, bit % 8);
}
match >>= 1;
}
}
Основной цикл этого составляет 18 инструкций и обрабатывает 2 байта на итерацию. Если стоимость установки не является проблемой, это должно быть примерно так же быстро, как и получается.