Самый быстрый способ найти до 6 последовательных 0 битов в массиве символов

Вот что я сейчас делаю:

int dataLen = 500;
char data[dataLen];
int desired = 1; // between 1 and 6, inclusive
...
char bits[dataLen * 8];
for (int32 j = 0; j < dataLen; j++) {
for (int i = 0; i < 8; i++) {
bits[j*8+i] = ( (data[j] & (1 << (7-i))) ? '1' : '0' );
}
}
int offset = std::search_n(bits, bits + dataLen*8, desired, '0') - bits;

Я знаю, что это действительно противно, и это убивает производительность.

Какой самый быстрый способ найти битовое смещение первого набора x последовательные 0 битов в массиве символов, где 0 < x < 7? Я на GCC с SSE 4.2, поэтому встроенные функции, такие как __builtin_ctz, __builtin_popcountl, являются опцией, я просто не могу найти лучший способ их использования.

8

Решение

Сколько чисел имеют 6 последовательных 0 битов (даже если учитывать 2 последовательных байта)?

Byte 1
XXXXXXXX
000000??             0/1/2/3
?000000?             0/1/128/129
??000000             0/64/128/192

Таким образом, если мы рассмотрим 1 байт за раз, то 0/1/2/3/64/128/192

Byte a   Byte b
XXXXXXXX XXXXXXXX
??100000 0???????    (a & 31 == 0) && (b & 128 == 0)
???10000 00??????    (a & 15 == 0) && (b & 192 == 0)
????1000 000?????    (a & 7  == 0) && (b & 224 == 0)
?????100 0000????    (a & 3  == 0) && (b & 240 == 0)
??????10 00000???    (a & 1  == 0) && (b & 248 == 0)

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

Если мы приведем решение @Michael Burr ниже для использования табличного подхода. Затем мы можем организовать это так, чтобы вы могли сделать одно или два сравнения на байт.

struct TestStruct
{
bool    is6Consecutive;
bool    hasTrailing;
int     maskNextByte;
int     offset;
};
TestStruct   testData[256];

std::size_t findOffsetOf_6ConsecutiveZero(char const* data, size_t size)
{
for(int loop = 0;loop < (size-1); ++loop)
{
char const&           val  = data[loop];
TestStructure const&  test = testData[val];

if (test.is6Consecutive)
{   return loop*8 + test.offset;
}

if (test.hasTrailing)
{
if ((data[loop + 1] & test.maskNextByte) == 0)
{   return loop*8 + test.offset;
}
}
}
// Test last byte
TestStructure const&  test = testData[data[size-1]];
if (test.is6Consecutive)
{   return (size-1)*8 + test.offset;
}

return -1;
}

Первые несколько записей в таблице:

TestStruct   testData[256] =
{
{true,  false, 0x00, 0},
{true,  false, 0x00, 0},
{true,  false, 0x00, 0},
{true,  false, 0x00, 0},
{false, true,  0xf0, 6},  // 4 => 00000100 <Next 4 bytes are zero we hit>
{false, false, 0x00, 0},  // 5 => 00000101 <Ignore and move on>
{false, true,  0xf8, 7},  // 6 => 00000110 <Next 5 bytes are zero we hit>
etc...

};
5

Другие решения

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

struct zeros {
unsigned char leading;
unsigned char internal;
unsigned char trailing;
};

// forward declaration so the long, non-interesting table is at the
//  end of this
static struct zeros const zero_table[256];

int find_zero_bits_offset( char const* data, int datalen, int desired)
{
int offset = -1;
int found = 0;
char const* dataptr = &data[0];
char const* endptr  = &data[datalen];// first, find which byte the sequence of zeros begins

while (!found && (dataptr != endptr)) {
unsigned char ch1 = *dataptr++;
unsigned char ch2 = (dataptr != endptr) ? *dataptr : 0xff;

int internal = zero_table[ch1].internal;
int trailing = zero_table[ch1].trailing;
int leading =  zero_table[ch2].leading;

found = (desired <= internal) ||
(trailing && (desired <= (trailing + leading)));
}// now zero in on where the sequence starts within the byte

if (found) {
char ch = 0;
unsigned int mask = 0;

--dataptr;

// dataptr points to the byte where the sequence of zeros starts.
//  figure out exactly where the sequence is...

// there's possibly some opportunity for optimization, if neccesary,
//  by testing if the sequence was found in the "leading", "internal", or
//  "trailing" cases. But the explicit loop will only iterate at most
//  8 times (and will early-out on the first iteration if the match is
//  for the "leading" case) that it didn't seem too important

ch = *dataptr;
offset = (dataptr - data) * 8;

// figure out where the appropriate internal run starts
// note that the offset we need to return isn't necessarily the
//  offset for the run of zeros counted by zero_table[tmp].internal_offset
//  since a sufficient shorter run might come first

// there may be a more efficient bithack for this, but the
//  loop will iterate at most 8 times...
mask = ((1 << desired) - 1);
mask <<= (8 - desired);

while ((ch & mask) != 0) {
++offset;
mask >>= 1;
}
}
else {
// however you want to handle the "not found" situation.
//  This is equivalent to what was in the question:
offset = (endptr - data) * 8;
}

return offset;
}static struct zeros const zero_table[256] = {
{ 8, 8, 8 },  // 0000 0000
{ 7, 7, 0 },  // 0000 0001
{ 6, 6, 1 },  // 0000 0010
{ 6, 6, 0 },  // 0000 0011
{ 5, 5, 2 },  // 0000 0100
{ 5, 5, 0 },  // 0000 0101
{ 5, 5, 1 },  // 0000 0110
{ 5, 5, 0 },  // 0000 0111
{ 4, 4, 3 },  // 0000 1000
{ 4, 4, 0 },  // 0000 1001
{ 4, 4, 1 },  // 0000 1010
{ 4, 4, 0 },  // 0000 1011
{ 4, 4, 2 },  // 0000 1100
{ 4, 4, 0 },  // 0000 1101
{ 4, 4, 1 },  // 0000 1110
{ 4, 4, 0 },  // 0000 1111
{ 3, 4, 4 },  // 0001 0000
{ 3, 3, 0 },  // 0001 0001
{ 3, 3, 1 },  // 0001 0010
{ 3, 3, 0 },  // 0001 0011
{ 3, 3, 2 },  // 0001 0100
{ 3, 3, 0 },  // 0001 0101
{ 3, 3, 1 },  // 0001 0110
{ 3, 3, 0 },  // 0001 0111
{ 3, 3, 3 },  // 0001 1000
{ 3, 3, 0 },  // 0001 1001
{ 3, 3, 1 },  // 0001 1010
{ 3, 3, 0 },  // 0001 1011
{ 3, 3, 2 },  // 0001 1100
{ 3, 3, 0 },  // 0001 1101
{ 3, 3, 1 },  // 0001 1110
{ 3, 3, 0 },  // 0001 1111
{ 2, 5, 5 },  // 0010 0000
{ 2, 4, 0 },  // 0010 0001
{ 2, 3, 1 },  // 0010 0010
{ 2, 3, 0 },  // 0010 0011
{ 2, 2, 2 },  // 0010 0100
{ 2, 2, 0 },  // 0010 0101
{ 2, 2, 1 },  // 0010 0110
{ 2, 2, 0 },  // 0010 0111
{ 2, 3, 3 },  // 0010 1000
{ 2, 2, 0 },  // 0010 1001
{ 2, 2, 1 },  // 0010 1010
{ 2, 2, 0 },  // 0010 1011
{ 2, 2, 2 },  // 0010 1100
{ 2, 2, 0 },  // 0010 1101
{ 2, 2, 1 },  // 0010 1110
{ 2, 2, 0 },  // 0010 1111
{ 2, 4, 4 },  // 0011 0000
{ 2, 3, 0 },  // 0011 0001
{ 2, 2, 1 },  // 0011 0010
{ 2, 2, 0 },  // 0011 0011
{ 2, 2, 2 },  // 0011 0100
{ 2, 2, 0 },  // 0011 0101
{ 2, 2, 1 },  // 0011 0110
{ 2, 2, 0 },  // 0011 0111
{ 2, 3, 3 },  // 0011 1000
{ 2, 2, 0 },  // 0011 1001
{ 2, 2, 1 },  // 0011 1010
{ 2, 2, 0 },  // 0011 1011
{ 2, 2, 2 },  // 0011 1100
{ 2, 2, 0 },  // 0011 1101
{ 2, 2, 1 },  // 0011 1110
{ 2, 2, 0 },  // 0011 1111
{ 1, 6, 6 },  // 0100 0000
{ 1, 5, 0 },  // 0100 0001
{ 1, 4, 1 },  // 0100 0010
{ 1, 4, 0 },  // 0100 0011
{ 1, 3, 2 },  // 0100 0100
{ 1, 3, 0 },  // 0100 0101
{ 1, 3, 1 },  // 0100 0110
{ 1, 3, 0 },  // 0100 0111
{ 1, 3, 3 },  // 0100 1000
{ 1, 2, 0 },  // 0100 1001
{ 1, 2, 1 },  // 0100 1010
{ 1, 2, 0 },  // 0100 1011
{ 1, 2, 2 },  // 0100 1100
{ 1, 2, 0 },  // 0100 1101
{ 1, 2, 1 },  // 0100 1110
{ 1, 2, 0 },  // 0100 1111
{ 1, 4, 4 },  // 0101 0000
{ 1, 3, 0 },  // 0101 0001
{ 1, 2, 1 },  // 0101 0010
{ 1, 2, 0 },  // 0101 0011
{ 1, 2, 2 },  // 0101 0100
{ 1, 1, 0 },  // 0101 0101
{ 1, 1, 1 },  // 0101 0110
{ 1, 1, 0 },  // 0101 0111
{ 1, 3, 3 },  // 0101 1000
{ 1, 2, 0 },  // 0101 1001
{ 1, 1, 1 },  // 0101 1010
{ 1, 1, 0 },  // 0101 1011
{ 1, 2, 2 },  // 0101 1100
{ 1, 1, 0 },  // 0101 1101
{ 1, 1, 1 },  // 0101 1110
{ 1, 1, 0 },  // 0101 1111
{ 1, 5, 5 },  // 0110 0000
{ 1, 4, 0 },  // 0110 0001
{ 1, 3, 1 },  // 0110 0010
{ 1, 3, 0 },  // 0110 0011
{ 1, 2, 2 },  // 0110 0100
{ 1, 2, 0 },  // 0110 0101
{ 1, 2, 1 },  // 0110 0110
{ 1, 2, 0 },  // 0110 0111
{ 1, 3, 3 },  // 0110 1000
{ 1, 2, 0 },  // 0110 1001
{ 1, 1, 1 },  // 0110 1010
{ 1, 1, 0 },  // 0110 1011
{ 1, 2, 2 },  // 0110 1100
{ 1, 1, 0 },  // 0110 1101
{ 1, 1, 1 },  // 0110 1110
{ 1, 1, 0 },  // 0110 1111
{ 1, 4, 4 },  // 0111 0000
{ 1, 3, 0 },  // 0111 0001
{ 1, 2, 1 },  // 0111 0010
{ 1, 2, 0 },  // 0111 0011
{ 1, 2, 2 },  // 0111 0100
{ 1, 1, 0 },  // 0111 0101
{ 1, 1, 1 },  // 0111 0110
{ 1, 1, 0 },  // 0111 0111
{ 1, 3, 3 },  // 0111 1000
{ 1, 2, 0 },  // 0111 1001
{ 1, 1, 1 },  // 0111 1010
{ 1, 1, 0 },  // 0111 1011
{ 1, 2, 2 },  // 0111 1100
{ 1, 1, 0 },  // 0111 1101
{ 1, 1, 1 },  // 0111 1110
{ 1, 1, 0 },  // 0111 1111
{ 0, 7, 7 },  // 1000 0000
{ 0, 6, 0 },  // 1000 0001
{ 0, 5, 1 },  // 1000 0010
{ 0, 5, 0 },  // 1000 0011
{ 0, 4, 2 },  // 1000 0100
{ 0, 4, 0 },  // 1000 0101
{ 0, 4, 1 },  // 1000 0110
{ 0, 4, 0 },  // 1000 0111
{ 0, 3, 3 },  // 1000 1000
{ 0, 3, 0 },  // 1000 1001
{ 0, 3, 1 },  // 1000 1010
{ 0, 3, 0 },  // 1000 1011
{ 0, 3, 2 },  // 1000 1100
{ 0, 3, 0 },  // 1000 1101
{ 0, 3, 1 },  // 1000 1110
{ 0, 3, 0 },  // 1000 1111
{ 0, 4, 4 },  // 1001 0000
{ 0, 3, 0 },  // 1001 0001
{ 0, 2, 1 },  // 1001 0010
{ 0, 2, 0 },  // 1001 0011
{ 0, 2, 2 },  // 1001 0100
{ 0, 2, 0 },  // 1001 0101
{ 0, 2, 1 },  // 1001 0110
{ 0, 2, 0 },  // 1001 0111
{ 0, 3, 3 },  // 1001 1000
{ 0, 2, 0 },  // 1001 1001
{ 0, 2, 1 },  // 1001 1010
{ 0, 2, 0 },  // 1001 1011
{ 0, 2, 2 },  // 1001 1100
{ 0, 2, 0 },  // 1001 1101
{ 0, 2, 1 },  // 1001 1110
{ 0, 2, 0 },  // 1001 1111
{ 0, 5, 5 },  // 1010 0000
{ 0, 4, 0 },  // 1010 0001
{ 0, 3, 1 },  // 1010 0010
{ 0, 3, 0 },  // 1010 0011
{ 0, 2, 2 },  // 1010 0100
{ 0, 2, 0 },  // 1010 0101
{ 0, 2, 1 },  // 1010 0110
{ 0, 2, 0 },  // 1010 0111
{ 0, 3, 3 },  // 1010 1000
{ 0, 2, 0 },  // 1010 1001
{ 0, 1, 1 },  // 1010 1010
{ 0, 1, 0 },  // 1010 1011
{ 0, 2, 2 },  // 1010 1100
{ 0, 1, 0 },  // 1010 1101
{ 0, 1, 1 },  // 1010 1110
{ 0, 1, 0 },  // 1010 1111
{ 0, 4, 4 },  // 1011 0000
{ 0, 3, 0 },  // 1011 0001
{ 0, 2, 1 },  // 1011 0010
{ 0, 2, 0 },  // 1011 0011
{ 0, 2, 2 },  // 1011 0100
{ 0, 1, 0 },  // 1011 0101
{ 0, 1, 1 },  // 1011 0110
{ 0, 1, 0 },  // 1011 0111
{ 0, 3, 3 },  // 1011 1000
{ 0, 2, 0 },  // 1011 1001
{ 0, 1, 1 },  // 1011 1010
{ 0, 1, 0 },  // 1011 1011
{ 0, 2, 2 },  // 1011 1100
{ 0, 1, 0 },  // 1011 1101
{ 0, 1, 1 },  // 1011 1110
{ 0, 1, 0 },  // 1011 1111
{ 0, 6, 6 },  // 1100 0000
{ 0, 5, 0 },  // 1100 0001
{ 0, 4, 1 },  // 1100 0010
{ 0, 4, 0 },  // 1100 0011
{ 0, 3, 2 },  // 1100 0100
{ 0, 3, 0 },  // 1100 0101
{ 0, 3, 1 },  // 1100 0110
{ 0, 3, 0 },  // 1100 0111
{ 0, 3, 3 },  // 1100 1000
{ 0, 2, 0 },  // 1100 1001
{ 0, 2, 1 },  // 1100 1010
{ 0, 2, 0 },  // 1100 1011
{ 0, 2, 2 },  // 1100 1100
{ 0, 2, 0 },  // 1100 1101
{ 0, 2, 1 },  // 1100 1110
{ 0, 2, 0 },  // 1100 1111
{ 0, 4, 4 },  // 1101 0000
{ 0, 3, 0 },  // 1101 0001
{ 0, 2, 1 },  // 1101 0010
{ 0, 2, 0 },  // 1101 0011
{ 0, 2, 2 },  // 1101 0100
{ 0, 1, 0 },  // 1101 0101
{ 0, 1, 1 },  // 1101 0110
{ 0, 1, 0 },  // 1101 0111
{ 0, 3, 3 },  // 1101 1000
{ 0, 2, 0 },  // 1101 1001
{ 0, 1, 1 },  // 1101 1010
{ 0, 1, 0 },  // 1101 1011
{ 0, 2, 2 },  // 1101 1100
{ 0, 1, 0 },  // 1101 1101
{ 0, 1, 1 },  // 1101 1110
{ 0, 1, 0 },  // 1101 1111
{ 0, 5, 5 },  // 1110 0000
{ 0, 4, 0 },  // 1110 0001
{ 0, 3, 1 },  // 1110 0010
{ 0, 3, 0 },  // 1110 0011
{ 0, 2, 2 },  // 1110 0100
{ 0, 2, 0 },  // 1110 0101
{ 0, 2, 1 },  // 1110 0110
{ 0, 2, 0 },  // 1110 0111
{ 0, 3, 3 },  // 1110 1000
{ 0, 2, 0 },  // 1110 1001
{ 0, 1, 1 },  // 1110 1010
{ 0, 1, 0 },  // 1110 1011
{ 0, 2, 2 },  // 1110 1100
{ 0, 1, 0 },  // 1110 1101
{ 0, 1, 1 },  // 1110 1110
{ 0, 1, 0 },  // 1110 1111
{ 0, 4, 4 },  // 1111 0000
{ 0, 3, 0 },  // 1111 0001
{ 0, 2, 1 },  // 1111 0010
{ 0, 2, 0 },  // 1111 0011
{ 0, 2, 2 },  // 1111 0100
{ 0, 1, 0 },  // 1111 0101
{ 0, 1, 1 },  // 1111 0110
{ 0, 1, 0 },  // 1111 0111
{ 0, 3, 3 },  // 1111 1000
{ 0, 2, 0 },  // 1111 1001
{ 0, 1, 1 },  // 1111 1010
{ 0, 1, 0 },  // 1111 1011
{ 0, 2, 2 },  // 1111 1100
{ 0, 1, 0 },  // 1111 1101
{ 0, 1, 1 },  // 1111 1110
{ 0, 0, 0 },  // 1111 1111
};
3

Перебор массива слово за словом (32-битный или 64-битный зависит от вашей арки). использование __builtin_clz а также __builtin_ctz рассчитать начальные и конечные нули для каждого слова.

Есть два случая последовательных нулей:

  • В слове
  • Через прилагательные слова.

Первый случай легко проверить. Во втором случае требуется проверить, является ли начальные нули этого элемента + конечные нули предыдущего элемента> = 6.

2

Обратите внимание на эти арифметические трюки:

// remove the trailing one bits
y = x & (x + 1);

x       11100011
+      1
--------
x+1     11100100
x&(x+1) 11100000

// remove the trailing zero bits
z = y | (y - 1);

y       11100000
-      1
--------
y-1     11011111
y|(y-1) 11111111

// isolate the hole
hole = z - x;
hole = z ^ x;

z       11111111
x       11100011
--------
z^x     00011100

// Now you can count the set bits of the hole.
length = bitcount(hole);

// Or you can make it by computing highbit only (log2).
length = highbit(z^y) - highbit(x^y);

Таким образом, возможный алгоритм будет использовать эти приемы с большой целочисленной арифметикой и циклом до длины == 0 (больше нет дыр) или длины> = n (вы начнете следующий цикл с x = z;).

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

  • x + 1 имеет перенос, только если байт == 0xFF
  • у-1 есть перенос, только если байт == 0x00
  • старший бит легко программировать на один байт

Это даст что-то вроде этого:

// return 1-based position of highest bit set in a byte
int highbit(unsigned char c)
{
unsigned char n;
int position = 0;
n = c >> 4;
if( n > 0 ) { c=n; position+=4; };
n = c >> 2;
if( n > 0 ) { c=n; position+=2; };
n = c >> 1;
if( n > 0 ) { c=n; position+=1; };
position += c;
return position;
}

int find_consecutive_zeros( unsigned char *bits , int nbytes , int nzero )
{
int i,nTrailingOnes,nTrailingZero,sizeOfNextHole;
unsigned char x,y;
for(i=0 , x=bits[0]; 1; )
{
// perform y=x&(x+1) to count and remove trailing ones
for(;x==0xFF && i<nbytes-1;x=bits[++i]);
y = x&(x+1);
nTrailingOnes = 8*i + highbit( x^y );
// perform x=y|(y-1); to count and remove trailing zeros
for(;y==0 && i<nbytes-1;y=bits[++i]);
x = y|(y-1);
nTrailingZero = 8*i + highbit( x^y );
sizeOfNextHole = nTrailingZero - nTrailingOnes;
// if size of hole is long enough, return it's low bit rank (0-based)
if( sizeOfNextHole >= nzero ) return nTrailingOnes;
// or return -1 if no more hole
if( sizeOfNextHole == 0 ) return -1;
}
}

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

РЕДАКТИРОВАТЬ: ускорить, когда у вас есть фиксированный размер для Nzero, как 6
Приведенный выше алгоритм повторяется на всех отверстиях и может терять время на небольших отверстиях.
Вы можете избежать этого с помощью предварительно вычисленного стола с небольшими заполненными отверстиями.

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

Чтобы инициализировать такую ​​таблицу, вы просто берете 0xFF и xor с маской, содержащей 1 бит вместо конечных нулей (x|(x-1))^x и маска, содержащая 1 бит вместо ведущих нулей ((1<<highbit(x))-1)^0xFF,
Добавьте исключение для 10000001, единственный байт, содержащий 6 нулей между единицами.

EDIT2 : Сначала я обработал последовательность битов младшим значащим битом первого байта, что хорошо соответствует арифметическому подходу. Вопрос явно использует наиболее значимый бит первого байта первым. Поэтому я должен обратить биты, чтобы соответствовать вопросу, что делается при инициализации таблицы …

int reversebits(unsigned char c)
{
c = ((c & 0x0F) << 4) | ((c & 0xF0) >> 4);
c = ((c & 0x33) << 2) | ((c & 0xCC) >> 2);
c = ((c & 0x55) << 1) | ((c & 0xAA) >> 1);
return c;
}
void initializeFillShortHoles(unsigned char fillShortHoles[256])
for(unsigned int x=0;x<256;x++) {
fillShortHoles[reversebits(x)] = ((1<<highbit(x))-1) ^ (x|(x-1)) ^ x;
}
fillShortHoles[0]=0;     // no use to reverse bits for those two
fillShortHoles[129]=129;
}

Тогда вы просто замените вхождения x=bits[ i ] с x=fillShortHoles[ bits[ i ] ], и вы сделали:

int find_6_consecutive_zeros( unsigned char *bits , int nbytes )
{
static unsigned char fillShortHoles[256];
static unsigned char highbitTable[256];
static first=1;
int i,nTrailingOnes,nTrailingZero,sizeOfNextHole;
unsigned char x,y;

if (first)
{
first = 0;
initializeFillShortHoles( fillShortHoles );
for(i=0;i<256;i++) highbitTable[i]=highbit(i);
}
for(x=fillShortHoles[bits[i=0]]; 1; )
{
// perform y=x&(x+1) to count trailing ones
for(;x==0xFF && i<nbytes-1;x=fillShortHoles[bits[++i]]);
y = x&(x+1);
nTrailingOnes = 8*i + highbitTable[ x^y ];
// perform z=y|(y-1); to count trailing zeros
for(;y==0 && i<nbytes-1;y=fillShortHoles[bits[++i]]);
x = y|(y-1);
nTrailingZero = 8*i + highbitTable[ x^y ];
sizeOfNextHole = nTrailingZero - nTrailingOnes;
// if size of hole is long enough, return it's low bit rank (0-based)
if( sizeOfNextHole >= 6 ) return nTrailingOnes;
// or return -1 if no more hole
if( sizeOfNextHole == 0 ) return -1;
}
}

EDIT3: Наконец-то для нзеро<= 9, более быстрый способ — кэшировать позицию для каждой пары байтов.

int find_n_consecutive_zeros_bypair( unsigned char *bits , int nbytes , int nzero)
{
static int first=1;
static signed char holepositionbypair[8][65536];
signed char position;
int i;
unsigned short x;
if (first)
{
first = 0;
for(i=0;i<8;i++) {
initializeHolePositionByPair( holepositionbypair[i] , i+1 );
}
}
for (i=0 , x=0xFF; i<nbytes; i++) {
x = (x << 8) + bits[i];
if( (position = holepositionbypair[nzero-1][x]) >= 0) return (i-1)*8 + position;
}
return -1;
}

Обратите внимание, что инициализация x = 0xFF будет обрабатывать случаи nbytes<2.

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

int highbit16(unsigned short c)
{
unsigned short n;
int position = 0;
n = c >> 8;
if( n ) { c=n; position+=8; };
n = c >> 4;
if( n ) { c=n; position+=4; };
n = c >> 2;
if( n ) { c=n; position+=2; };
n = c >> 1;
if( n ) { c=n; position+=1; };
position += c;
return position;
}
unsigned short reversebits16(unsigned short c)
{
c = ((c & 0x00FF) << 8) | ((c & 0xFF00) >> 8);
c = ((c & 0x0F0F) << 4) | ((c & 0xF0F0) >> 4);
c = ((c & 0x3333) << 2) | ((c & 0xCCCC) >> 2);
c = ((c & 0x5555) << 1) | ((c & 0xAAAA) >> 1);
return c;
}
initializeHolePositionByPair(signed char holepositionbypair[65536],int n)
{
int i,n1,n0;
unsigned short x,y;
signed char position;
for(i=0;i<65536;i++) {
position = -1;
x = i;
while(x != 0xFFFF) {
/* remove trailing ones */
y = x&(x+1);
n1 = highbit16(x^y);
/* remove trailing zeros */
x = y|(y-1);
n0 = highbit16(x^y);
if(n0-n1>=n) {
position = n1; break;
}
}
holepositionbypair[reversebits16(i)] = position;
}
}
1

Вот, попробуйте этот код.

int dataLen = 500;
char data[dataLen];
//Get the data in place with whatever is your algorithm.
int i,j;
unsigned int dataSample;
unsigned int mask;
for(i=0;i<dataLen-1;i++){
dataSample=((unsigned int)(data[i+1]) << 8) | (unsigned int) (data[i]);
mask=(1<<6) - 1 ; //6 consecutive 1's
for(j=0;j<8;j++){
if((dataSample & (mask << j)) == 0){
printf("Found consecutive 6 zeros at byte %d offset %d\n",i,j);
j+=5; // Followed by j++ makes it j+=6.
}
}
}
0

Для байта вам нужно всего лишь сделать 3 теста:

if( (byte & 0x3F) == 0) { /* Found */ }
if( (byte & 0x7E) == 0) { /* Found */ }
if( (byte & 0xFC) == 0) { /* Found */ }

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

tempValue1 = value & 0x3F3F3F3F;
tempValue2 = value & 0x7E7E7E7E;
tempValue3 = value & 0xFCFCFCFC;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }
tempValue1 >>= 8;
tempValue2 >>= 8;
tempValue3 >>= 8;
if( ( (uint8_t)tempValue1 == 0) { /* Found */ }
if( ( (uint8_t)tempValue2 == 0) { /* Found */ }
if( ( (uint8_t)tempValue3 == 0) { /* Found */ }

Приведенный выше код не выглядит как лучший способ сделать это (потому что, вероятно, это не так). Я намеренно написал так, чтобы было проще понять, как это можно сделать с помощью SSE. Для SSE это было бы похоже на выше (но шире).

Однако для SSE вы можете выполнять все сравнения параллельно и избавляться от множества ветвей. Например, вы могли бы И с каждой из 3 масок и использовать PCMPEQB 3 раза, а затем ИЛИ эти результаты вместе, затем сделайте один PMOVMSKB; что даст вам 16-битное значение (которое представляет 16 байтов — один бит на исходный байт), которое можно протестировать с помощью одного if(result_flags == 0) { /* None of the 16 bytes matched */ }где этот последний тест может быть в конце цикла «do / while».

0

Предположим, вы ищете именно так 6 последовательных нулей. Вы можете использовать фрагмент кода следующим образом:

unsigned d1 = 0xff;
for (int i = 0; i < dataLen; i += 3) {
unsigned d1 = (d1 << 24) | (data[i] << 16) | (data [i+1] << 8) | (data[i+2]);
unsigned d2 = ~d1; // ones
unsigned d3 = d2 & (d2 << 2) & (d2 << 4);
unsigned d4 = d3 & (d3 << 1);
if (!d4) continue;
doSomethingWithTheSequence(i, d4);
}

d1 объединит последний байт предыдущего цикла с тремя новыми байтами. Таким образом, вы можете перебирать свои данные кратными 3. Вы можете попробовать кратные 2, что может быть более эффективным, поскольку вы можете рассматривать свои данные как 16-битные атомные величины. Вы также можете попробовать умножить на 4 и выполнить последующие вычисления для 64-разрядных чисел, особенно если вы используете 64-разрядную платформу. Или вы вводите специальный случай для нулевых последовательностей, охватывающих байты.

d2 инвертирует битовую комбинацию, что полезно, потому что сдвиги будут вводить искусственные нули, но никогда не будут искусственными. d3 ищет три совпадающих со смещением 0, 2 и 4. d4 затем добавляет еще один бит смещения, таким образом объединяя все смещения от 0 до 5. Так d4 будет отличным от нуля тогда и только тогда, когда в серии будет 6 последовательных нулей d1, Вы можете использовать __builtin_clz определить местонахождение наиболее значимого в d4, который также является положением первого из этих 6 битов в d1, Из этого вы можете получить положение в data,

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

0

Позвольте мне попробовать — как насчет:

class bitIterator{
unsigned char* farray;
int foffset;
public:
bitIterator(unsigned char* array, int offset)
:farray(array), foffset(offset)
{}

bool operator*() const {
return (farray[foffset/8] >> (7 - foffset%8)) & 1;
}

bitIterator& operator++(){
foffset++;
return *this;
}

int offset() const {
return foffset;
}

};

// Just to demonstrate how to call it
int find_first_n(unsigned char* buffer, int length, int n){
return std::search_n(bitIterator(buffer, 0), bitIterator(buffer, length*8), n, 0).offset();
}

Это было просто для удовольствия …

Теперь, если вы действительно хотите выжать из этого производительность, я буду suggset

int find_first_n(unsigned char* buffer, int length, int n){
int prev_trail = 0;
unsigned int* buf = reinterpret_cast<unsigned int*>(buffer);
int len = length/sizeof(int);
// Last few bytes will need special treatment if your array is not multple of int-size length.
// However last bytes should not influence overall performance of code - assuming it is used on rather long arrays.
// If you plan using rather short arrays (20-50 bytes?) you will probably be better off just using plain char.
for (int i=0; i<len; i++){
if (!buf[i]) return i*sizeof(int)*8-prev_trail; // __builtin_clz and __builtin_ctz are undefined on zero ;
// EDIT:
if (!~buf[i]){
prev_trail = 0;
continue;
}
// END EDIT!int shft = __builtin_clz(buf[i]);
if (shft + prev_trail >= n) return i*sizeof(int)*8-prev_trail; // Leading + previous trailing <= n
// Not enough leading zeros, continue search.
prev_trail = __builtin_ctz(buf[i]); // Store it to use for next int in array
unsigned int tmp =0;
while(shft < sizeof(int)*8-prev_trail){   // While we haven't got to trailing zeros in this uint
tmp = buf[i] << shft;               // Shift-out leading zeros;
shft += (__builtin_clz(~tmp));
tmp = buf[i] << shft;               // Shift-out leading ones;

lead_zeros = __builtin_clz(tmp);
if (lead_zeros >= n)                // and see if have enough leading zeros.
return i*sizeof(int)*8+shft;

shft += lead_zeros;
}
return length*8; // Not found :(
}

Это довольно сложно прочитать, но концепция проста — просто итерируйте по каждому блоку целого размера, и для каждого посмотрите, являются ли начальные нули + конечные нули из предыдущего>> = n. Если не просто многократно сдвигать начальные и последующие нули (устанавливать биты), и снова проверять наличие конечных нулей> = n, пока мы не дошли до конечных байтов.

И еще одна идея:

int find_first_n(unsigned char* buffer, int length, int n){
union {
unsigned char chr[2];
unsigned int uit;
};

unsigned int onemask = 0x8000;
for (int i = 1 ; i<n; i++) onemask = onemask | (onemask >> 1);

int* masks = new int[8];
for (int i = 0; i<8; i++){
masks[i]=onemask >> i;
}

// generating masks - eg. for n == 3 would be:
// [ 1110 0000 0000 0000 ]
// [ 0111 0000 0000 0000 ]
// [ 0011 1000 0000 0000 ]
// [ 0001 1100 0000 0000 ]
// [ ... ]
// [ 0000 0001 1100 0000 ]uit = 0;
for (int i=0; i<length-1; i++){
chr[0] = buffer[i];
chr[1] = buffer[i+1];
for (int j=0; j<8; j++){
if (!(uit & masks[j])) return i*8+j;
}
}
chr[0] = buffer[length-1];
chr[1] = 0xff; // Fill with ones at the end.
for (int j=0; j<8; j++){
if (!(uit & masks[j])) return (length-1)*8+j;
}
return length*8; // Not found :(
}

Вы можете испытать желание привести указатель на переменные, которые все еще находятся в буфере, непосредственно к слову (reinterpret_cast<unsigned short int*>(buffer[i])) и применять маски без использования объединения. Однако обратите внимание, что половина таких операций будет использовать невыровненные переменные, которые могут снизить производительность, а на некоторых платформах даже генерировать исключения.

0
По вопросам рекламы ammmcru@yandex.ru
Adblock
detector