Le moyen le plus rapide de rechercher le modèle de bits dans un flux de bits

Question

J'ai besoin de rechercher un mot de 16 bits dans un flux binaire. Il n'est pas garanti d'être aligné sur les limites d'octets ou de mots .

Quel est le moyen le plus rapide d'y parvenir? Il existe différentes méthodes de force brute; en utilisant des tableaux et / ou des décalages, mais existe-t-il des "raccourcis de torsion de bits" qui peuvent réduire le nombre de calculs en donnant oui / non / contient peut-être les résultats de l'indicateur pour chaque octet ou mot à son arrivée?

Le code C, intrinsèque, le code machine x86 seraient tous intéressants.

Answer 1

Je pense que precalc toutes les valeurs décalées de la parole et de les mettre dans 16 ints si vous avez un tableau comme ceci

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

et puis pour tous les unsigned short-vous sortir du flux, de faire une int de ce court et la court et de les comparer unsigned int de 16 unsigned int. Si l'une d'entre elles correspondent, vous en avez un.

donc, fondamentalement, comme ceci:

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

edit: notez que cela pourrait signifier plusieurs frappe quand les motifs, c'est détectée plusieurs fois sur les mêmes bits:

par exemple 32 bits de 0 et le motif que vous voulez détecter est de 16 0, alors cela voudrait dire que le motif est détecté 16 fois!

Answer 2

Voici une astuce pour accélérer la recherche par un facteur de 32, si ni le Knuth-Morris-Pratt de l'algorithme sur l'alphabet de deux caractères {0, 1}, ni reinier l'idée est assez rapide.

Vous pouvez tout d'abord utiliser un tableau avec 256 entrées de vérifier pour chaque octet dans votre flux de bits si elle est contenue dans le mot de 16 bits vous êtes à la recherche pour. Le tableau que vous obtenez avec

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

Vous pouvez ensuite trouver les positions possibles pour les matches dans le flux de bits à l'aide de

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

Comme dans la plupart des 8 de 256 entrées de la table ne sont pas à zéro, en moyenne, vous avez à regarder de plus près, seulement à chaque 32ème position. Seulement pour cet octet (combiné avec les octets un avant et un après), vous avez alors à utiliser les opérations sur les bits ou certaines techniques de masquage comme suggéré par reinier pour voir si il y a un match.

Le code suppose que vous utilisez little endian ordre des octets. L'ordre des bits dans un octet peut également être un problème (connu de tous, qui a déjà mis en œuvre une somme de contrôle CRC32).

Answer 3

Je voudrais proposer une solution à l'aide de 3 tables de recherche de taille 256. Ce serait efficace pour le grand flux de bits. Cette solution prend 3 octets dans un échantillon à des fins de comparaison. Figure suivante montre tous les arrangements possibles de 16 bits de données dans les 3 octets. Chaque octet de la région a affiché dans une couleur différente.

Ici, la vérification de 1 à 8 seront pris en charge en premier échantillon et de 9 à 16 dans l'exemple suivant, et ainsi de suite. Maintenant, quand nous sommes à la recherche d'un Modèle, nous allons trouver tous les 8 arrangements possibles (comme ci-dessous) de ce Modèle et va stocker dans 3 tables de recherche (à Gauche, au Milieu et à Droite).

L'Initialisation Des Tables De Recherche:

Prenons un exemple 0111011101110111 comme un Modèle à trouver. Considérons maintenant la 4e arrangement. Partie gauche serait XXX01110. Remplissez tous les raws de Gauche de la table de pointage par la partie gauche (XXX01110) avec 00010000. 1 indique la position de départ de l'arrangement de la saisie de Schéma. Ainsi, après 8 raws de Gauche de la table devra être complété par 16 (00010000).

00001110
00101110
01001110
01101110
10001110
10101110
11001110
11101110

La partie moyenne de dispositions 11101110. Raw de pointage par cet indice (238) dans le Milieu de la table sera remplie par 16 (00010000).

Maintenant la partie Droite de dispositions 111XXXXX. Tous les raws (32 raws) avec index 111XXXXX sera rempli par 16 (00010000).

Nous ne devrions pas remplacer des éléments dans la table pendant le remplissage. Au lieu de faire un bit à bit OU de l'opération de mise à jour déjà rempli raw. Dans l'exemple ci-dessus, tous les raws écrit par le 3e accord serait mis à jour par 7 arrangement comme suit.

Ainsi raws avec index XX011101 à Gauche de la table de recherche et d' 11101110 dans le Milieu de la table de recherche et d' 111XXXXX en Droit de la table de recherche sera mis à jour en 00100010 par 7e arrangement.

Recherche Modèle:

Prendre un échantillon de trois octets. Trouver le Comte comme suit, où la Gauche est à gauche de la table de recherche, du Milieu est au milieu de la table de recherche et de Droite est à droite de la table de choix.

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

Nombre de 1 dans le Comte donne le nombre de correspondance de Motif dans la prise de l'échantillon.

Je peux vous donner un exemple de code qui est testé.

Initialisation de la table de choix:

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

Recherche Modèle:

De données est de la mémoire tampon, la Gauche est à gauche de la table de recherche, du Milieu est au milieu de la table de recherche et de Droite est à droite de la table de choix.

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

Limitation:

Au-dessus de la boucle ne peut pas détecter un Motif si elle est placée à la fin de la mémoire tampon. Code suivant besoin d'ajouter après la boucle pour surmonter cette limitation.

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

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

Avantage:

Cet algorithme prend seulement N-1 étapes logiques pour trouver un Modèle dans un tableau de N octets. Seuls les frais généraux est de remplir les tables de recherche d'abord ce qui est constant dans tous les cas. Donc, ce sera très efficace pour la recherche d'énormes flux d'octets.

Answer 4

Je voudrais mettre en œuvre une machine à état avec 16 états.

Chaque état représente la façon dont beaucoup ont reçu des bits de se conformer à la tendance. Si la prochaine reçu peu conforme à la partie suivante de la séquence, la machine suit à l'état suivant. Si ce n'est pas le cas, la machine retourne à l'état premier (ou d'un autre etat si le début du motif peut être mis en correspondance avec un plus petit nombre de bits).

Lorsque la machine atteint le dernier état, cela indique que le modèle a été identifié dans le flux de bits.