c++ - La forma más rápida de escanear patrones de bits en una secuencia de bits

algorithm assembly

Question

Necesito escanear una palabra de 16 bits en un flujo de bits. No se garantiza que esté alineado en los límites de bytes o palabras .

¿Cuál es la forma más rápida de lograr esto? Hay varios métodos de fuerza bruta; usando tablas y / o turnos, pero ¿hay algún "atajo de bits" que pueda reducir el número de cálculos al dar sí / no / quizás contenga los resultados del indicador para cada byte o palabra a medida que llega?

C code, intrinsics, código de máquina x86 serían todos interesantes.

Answer 1

Aquí hay un truco para acelerar la búsqueda por un factor de 32, si ni el algoritmo de Knuth-Morris-Pratt en el alfabeto de dos caracteres {0, 1} ni la idea de reinier son lo suficientemente rápidos.

Primero puede usar una tabla con 256 entradas para verificar cada byte en su flujo de bits si está contenido en la palabra de 16 bits que está buscando. La mesa que obtienes

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

A continuación, puede encontrar posibles posiciones para las coincidencias en el flujo de bits utilizando

for (i=0; i<length; i++) {
  if (table[bitstream[i]]) {
    // here comes the code which checks if there is really a match
  }
}

Como a lo sumo 8 de las 256 entradas de tabla no son cero, en promedio debe mirar más de cerca solo en cada posición 32. Solo para este byte (combinado con los bytes uno antes y uno después) debe usar operaciones de bits o algunas técnicas de enmascaramiento como sugiere reinier para ver si hay una coincidencia.

El código asume que se usa un orden de byte pequeño. El orden de los bits en un byte también puede ser un problema (conocido por todos los que ya implementaron una suma de comprobación CRC32).

Answer 2

Creo que precalculó todos los valores modificados de la palabra y los puse en 16 ints, así que obtuve una matriz como esta

 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[16] = (unsigned int) (0xffff<<i);
 }

y luego, por cada corto sin signo que salga de la transmisión, haga una int de ese corto y el corto anterior y compare esa int sin signo con las 16 int sin signo. Si alguno de ellos coincide, tienes uno.

así que básicamente así:

  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;
  }

editar: tenga en cuenta que esto podría significar múltiples visitas cuando los patrones se detectan más de una vez en los mismos bits:

por ejemplo, 32 bits de 0 y el patrón que desea detectar es 16 0, ¡entonces significa que el patrón se detectará 16 veces!

Answer 3

Implementaría una máquina de estado con 16 estados.

Cada estado representa cuántos bits recibidos se ajustan al patrón. Si el siguiente bit recibido se ajusta al siguiente bit del patrón, la máquina pasa al siguiente estado. Si este no es el caso, la máquina retrocede al primer estado (o a otro estado si el comienzo del patrón puede coincidir con un número menor de bits recibidos).

Cuando la máquina alcanza el último estado, esto indica que el patrón se ha identificado en la secuencia de bits.

Answer 4

Lo que haría es crear 16 prefijos y 16 sufijos. Luego, para cada fragmento de entrada de 16 bits, determine la coincidencia de sufijo más larga. Tienes una coincidencia si el siguiente fragmento tiene una coincidencia de prefijo de longitud (16-N)

Una coincidencia de sufijo no es en realidad 16 comparaciones. Sin embargo, esto requiere un cálculo previo basado en la palabra de patrón. Por ejemplo, si la palabra patrón es 101010101010101010, primero puede probar el último bit de su fragmento de entrada de 16 bits. Si ese bit es 0, solo necesita probar el ... 10101010 es suficiente. Si el último bit es 1, necesita probar el ... 1010101 es suficiente. Tienes 8 de cada uno, para un total de 1 + 8 comparaciones. Si la palabra patrón es 1111111111110000, aún probaría el último bit de su entrada para una coincidencia de sufijo. Si ese bit es 1, tienes que hacer 12 coincidencias de sufijo (regex: 1 {1,12}) pero si es 0 solo tienes 4 posibles coincidencias (regex 1111 1111 1111 0 {1,4}), nuevamente para un promedio de 9 pruebas. Agregue la coincidencia de prefijo 16-N , y verá que solo necesita 10 cheques por porción de 16 bits.

Answer 5

Me gustaría sugerir una solución usando 3 tablas de búsqueda del tamaño 256. Esto sería eficiente para grandes flujos de bits. Esta solución toma 3 bytes en una muestra para comparación. La siguiente figura muestra todas las disposiciones posibles de datos de 16 bits en 3 bytes. Cada región de bytes se ha mostrado en diferentes colores.

texto alternativo http://img70.imageshack.us/img70/8711/80541519.jpg

Aquí, la verificación de 1 a 8 se tendrá en cuenta en la primera muestra y de 9 a 16 en la muestra siguiente, y así sucesivamente. Ahora, cuando estamos buscando un Patrón , encontraremos las 8 posibles disposiciones (como se muestra a continuación) de este Patrón y almacenaremos en 3 tablas de búsqueda (Izquierda, Media y Derecha).

Inicializando tablas de búsqueda:

0111011101110111 un ejemplo 0111011101110111 como un patrón para encontrar. Ahora considere el 4 ° arreglo. La parte izquierda sería XXX01110 . Llene todas las ramificaciones de la tabla de búsqueda izquierda apuntando por la parte izquierda ( XXX01110 ) con 00010000 . 1 indica la posición de inicio de la disposición del patrón de entrada. Por lo tanto, después de 8 raws of Left, la tabla de búsqueda se llenaría con 16 ( 00010000 ).

00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110

La parte media de la disposición sería 11101110 . La indicación en bruto de este índice (238) en la tabla de consulta del medio se completará con 16 ( 00010000 ).

Ahora la parte correcta de la disposición sería 111XXXXX . Todas las raws (32 raws) con índice 111XXXXX se llenarán por 16 ( 00010000 ).

No deberíamos sobrescribir elementos en la tabla de búsqueda mientras llenamos. En su lugar, realice una operación OR a nivel de bit para actualizar una línea cruda ya llena. En el ejemplo anterior, todos los raws escritos por el 3er arreglo se actualizarían mediante la 7ª disposición de la siguiente manera.

texto alternativo http://img527.imageshack.us/img527/8807/76437426.jpg

Por lo tanto, las ráfagas con índice XX011101 en la tabla de búsqueda izquierda y 11101110 en la tabla de búsqueda intermedia y 111XXXXX en la tabla de búsqueda derecha se actualizarán a 00100010 mediante la 7ª disposición.

Patrón de búsqueda:

Tome una muestra de tres bytes. Encuentre el recuento de la siguiente manera donde izquierda es la tabla de búsqueda izquierda, el medio es la tabla de búsqueda del medio y la derecha es la tabla de búsqueda derecha.

Count = Left[Byte0] & Middle[Byte1] & Right[Byte2];

El número de 1 en Count proporciona el número de patrones coincidentes en la muestra tomada.

Puedo dar un código de muestra que se prueba.

Inicializando la tabla de búsqueda:

    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;
    }

Patrón de búsqueda:

Los datos son buffer de transmisión, Left es la tabla de búsqueda izquierda, Middle es la tabla de búsqueda intermedia y Right es la tabla de búsqueda correcta.

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 );
    }
}

Limitación:

El ciclo anterior no puede detectar un patrón si se coloca al final del buffer de transmisión. El código siguiente debe agregarse después del ciclo para superar esta limitación.

Count = Left[Data[StreamLength - 2]] & Middle[Data[StreamLength - 1]] & 128;

if( Count )
{
    TotalCount += GetNumberOfOnes( Count );
}

Ventaja:

Este algoritmo toma solo N-1 pasos lógicos para encontrar un patrón en una matriz de N bytes. Solo la sobrecarga es para llenar las tablas de búsqueda inicialmente, que es constante en todos los casos. Por lo tanto, esto será muy efectivo para buscar grandes flujos de bytes.

Answer 6

Mi dinero está en Knuth-Morris-Pratt con un alfabeto de dos caracteres.

Answer 7

Para un algoritmo no SIMD de propósito general, es poco probable que pueda hacer mucho mejor que algo como esto:

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 );

Answer 8

Parece un buen uso para las instrucciones SIMD. SSE2 agregó un montón de instrucciones enteras para procesar múltiples enteros al mismo tiempo, pero no puedo imaginar muchas soluciones para esto que no impliquen muchos cambios de bit ya que sus datos no van a estar alineados. Esto realmente suena como algo que un FPGA debería estar haciendo.

Answer 9

Puede usar la transformada de Fourier rápida para una entrada extremadamente grande (valor de n) para encontrar cualquier patrón de bits en el tiempo O (n log n). Calcule la correlación cruzada de una máscara de bits con la entrada. La correlación cruzada de una secuencia xy una máscara y con un tamaño n y n ''respectivamente se define por

R(m) = sum  _ k = 0 ^ n'' x_{k+m} y_k

a continuación, las ocurrencias de su patrón de bits que coinciden con la máscara exactamente donde R (m) = Y donde Y es la suma de uno en su máscara de bits.

Entonces, si estás tratando de hacer coincidir el patrón de bits

[0 0 1 0 1 0]

en

[ 1 1 0 0 1 0 1 0 0 0 1 0 1 0 1]

entonces debes usar la máscara

[-1 -1  1 -1  1 -1]

los -1 en la máscara garantizan que esos lugares deben ser 0.

Puede implementar la correlación cruzada, usando la FFT en el tiempo O (n log n).

Creo que KMP tiene tiempo de ejecución O (n + k), por lo que es mejor.

Answer 10

Tal vez debería transmitir en su flujo de bits en un vector (vec_str), transmitir en su patrón en otro vector (vec_pattern) y luego hacer algo como el algoritmo a continuación

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++

(espero que el algoritmo sea correcto)

Answer 11

Una manera rápida de encontrar las coincidencias en grandes cadenas de bits sería calcular una tabla de búsqueda que muestre las compensaciones de bits donde un byte de entrada determinado coincide con el patrón. Luego, combinando tres coincidencias offset consecutivas, puedes obtener un vector de bits que muestra qué compensaciones coinciden con el patrón completo. Por ejemplo, si byte x coincide con los primeros 3 bits del patrón, byte x + 1 coincide con los bits 3..11 y byte x + 2 coincide con los bits 11..16, luego hay una coincidencia en byte x + 5 bits.

Aquí hay un código de ejemplo que hace esto, acumulando los resultados para dos bytes a la vez:

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;
    }
}

El ciclo principal de esto tiene 18 instrucciones y procesa 2 bytes por iteración. Si el costo de instalación no es un problema, esto debería ser lo más rápido posible.

Answer 12

atomice''s

• Knuth-Morris-Pratt

se veía bien hasta que consideré las solicitudes de Luke y MSalter para obtener más información sobre los detalles.

Resulta que los detalles pueden indicar un enfoque más rápido que KMP. El artículo de KMP se vincula a

• Boyer Moore

para un caso particular cuando el patrón de búsqueda es ''AAAAAA''. Para una búsqueda de patrones múltiples, el

• Rabin-Karp

podría ser el más adecuado.

Puede encontrar más discusión introductoria here .