comment rechercher "n bits" dans un tableau d'octets?

Question

J'ai un tableau d'octets. Maintenant, j'ai besoin de connaître le nombre d'apparences d'un motif de bit dont la longueur est N.

Par exemple, mon tableau d'octets est "00100100 10010010" et le motif est "001". ici N = 3, et le compte est 5.

Traiter des bits est toujours mon côté faible.

Answer 1

Vous pouvez toujours OU XOR les premiers bits N et si vous obtenez 0 en conséquence, vous avez une correspondance. Puis déplacez le bit "stream" recherché d'un bit vers la gauche et répétez. C'est en supposant que vous voulez obtenir des correspondances si ces sous-modèles se chevauchent. Sinon, vous devriez changer de longueur de motif sur le match.

Answer 2

En supposant que votre tableau s'insère dans un unsigned int:

int main() { 
    unsigned int curnum; 
    unsigned int num = 0x2492; 
    unsigned int pattern = 0x1; 
    unsigned int i; 
    unsigned int mask = 0; 
    unsigned int n = 3; 
    unsigned int count = 0; 

    for (i = 0; i < n; i++) { 
     mask |= 1 << i; 
    } 

    for (i = 8 * sizeof(num) - n; i >= 0; i--) { 
     curnum = (num >> i) & mask; 
     if (! (curnum^pattern)) { 
      count++; 
     } 
    } 
} 

Answer 3

Convertir votre tableau d'octets et un motif chacun à un std::vector<bool>, puis appelez std::search(source.begin(), source.end(), pattern.begin(), pattern.end());. Malgré les particularités de vector<bool>, cela fonctionnera.

Answer 4

Si N peut être arbitrairement grand, vous pouvez stocker la configuration binaire dans un vecteur

vector<unsigned char> pattern; 

La taille du vecteur doit être

(N + 7)/8 

magasin le modèle déplacé vers la droite. Par cela, je veux dire que par exemple, si N == 19, Votre vecteur devrait ressembler à:

|<- v[0] ->|<- v[1] ->|<- v[2] ->| 
0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 
|   |<-    pattern    ->| 

Si vous avez votre modèle déplacé à l'origine vers la gauche, vous pouvez utiliser la fonction que je vais vous présenter ci-dessous , pour déplacer les bits vers la droite.

Définissez un vecteur d'octets, de la même longueur que le modèle, pour stocker une partie de Votre train de bits pour le comparer avec le modèle. Je vais l'appeler window

vector<unsigned char> window; 

Si N est pas un multiple entier de 8, Vous aurez besoin de masquer certains bits dans votre extrême gauche window, lorsque l'on compare avec le modèle. Vous pouvez définir le masque de cette façon:

unsigned char mask = (1 << (N % 8)) - 1; 

Maintenant, en supposant que le window contient les bits, il faut, vous pouvez comparer théoriquement le modèle avec le window en utilisant l'opérateur de vecteur == comme celui-ci

window[0] &= mask; 
bool isMatch = (window == pattern); 

Mais il y a de bonnes raisons d'être un peu plus sophistiqué. Si N est grand et votre tableau d'octets, vous recherchez le modèle en est nettement plus grande, il vaut la peine, pour traiter le modèle et construire un vecteur de taille N + 1:

vector<int> shifts; 

Ce vecteur stockera les informations, combien de bits pour déplacer le flux de bits par, pour la comparaison suivante, en fonction de la position, à laquelle il existe une discordance dans le courant window.

Envisagez le modèle . Vous devriez comparer les bits avec le window de droite à gauche.S'il y a une erreur au premier bit, vous savez que c'est 1 et la première occurrence de 1 dans Votre motif est à la position 2, le formulaire de comptage 0 forme la droite vers la gauche. Donc, dans ce cas, vous savez, cela n'a pas de sens de faire une comparaison si le nombre de nouveaux bits décalés forment le flux de bits dans le window est inférieur à 2. De même si la discordance se produit au troisième bit (position 2 en comptant le formulaire 0), le window doit être déplacé de 7, car 3 zéros consécutifs dans votre motif sont à la fin. Si la discordance est à la position 4, vous pouvez déplacer le window par 8 et ainsi de suite. Le vecteur sifts, à un index i contiendra le nombre de bits, par lequel déplacer le window, si la discordance se produit à la position i. S'il y a une correspondance, le window doit être déplacé du nombre de bits stockés dans shifts[N]. Dans l'exemple ci-dessus, une correspondance correspond à un décalage de 8.

En pratique, bien sûr, vous comparez des octets entiers à partir du modèle avec les octets du window (en cours de déplacement de droite à gauche) et en cas de non-concordance. les bits dans l'octet pour trouver la position de discordance.

if(window[i] != pattern[i]) 
{ 
    int j = 0; 
    unsigned char mismatches = window[i]^pattern[i]; 
    while((mismatches & 1) == 0) 
    { 
     mismatches >>= 1; 
     ++j; 
    } 
    mismatch_position = 8 * (window.size() - i - 1) + j; 
} 

Voici une fonction qui pourrait venir à portée de main, lorsque vous devez déplacer certains bits de votre flux de bits dans le window. Je l'ai écrit en C#, mais la conversion en C++ devrait être triviale. C# rend certains moulages nécessaires, qui ne sont probablement pas nécessaires en C++. Utilisez unsigned char au lieu de byte, vector<unsigned char> & au lieu de byte [], size() au lieu de Length et peut-être quelques modifications plus mineures. La fonction est probablement un peu plus générale que nécessaire dans Votre scénario, car elle n'utilise pas le fait que les appels consécutifs récupèrent des segments consécutifs de Votre tableau d'octets, ce qui pourrait peut-être simplifier un peu, mais je ne pense pas fait mal. Dans la forme actuelle, il peut extraire la sous-chaîne de bits arbitraire du tableau d'octets.

public static void shiftBitsIntoWindow_MSbFirst(byte[] window, byte[] source, 
               int startBitPosition, int numberOfBits) 
{ 
    int nob = numberOfBits/8; 
    // number of full bytes from the source 

    int ntsh = numberOfBits % 8; 
    // number of bits, by which to shift the left part of the window, 
    // in the case, when numberOfBits is not an integer multiple of 8 

    int nfstbb = (8 - startBitPosition % 8); 
    // number Of bits from the start to the first byte boundary 
    // The value is from the range [1, 8], which comes handy, 
    // when checking if the substring of ntsh first bits 
    // crosses the byte boundary in the source, by evaluating 
    // the expression ntsh <= nfstbb. 

    int nfbbte = (startBitPosition + numberOfBits) % 8; 
    // number of bits from the last byte boundary to the end 

    int sbtci; 
    // index of the first byte in the source, from which to start 
    // copying nob bytes from the source 
    // The way in which the (sbtci) index is calculated depends on, 
    // whether nob < window.Length 

    if(nob < window.Length)// part of the window will be replaced 
    // with bits from the source, but some part will remain in the 
    // window, only moved to the beginning and possibly shifted 
    { 
     sbtci = (startBitPosition + ntsh)/8; 

     //Loop below moves bits form the end of the window to the front 
     //making room for new bits that will come form the source 

     // In the corner case, when the number by which to shift (ntsh) 
     // is zero the expression (window[i + nob + 1] >> (8 - ntsh)) is 
     // zero and the loop just moves whole bytes 
     for(int i = 0; i < window.Length - nob - 1; ++i) 
     { 
      window[i] = (byte)((window[i + nob] << ntsh) 
       | (window[i + nob + 1] >> (8 - ntsh))); 
     } 

     // At this point, the left part of the window contains all the 
     // bytes that could be constructed solely from the bytes 
     // contained in the right part of the window. Next byte in the 
     // window may contain bits from up to 3 different bytes. One byte 
     // form the right edge of the window and one or two bytes form 
     // the source. If the substring of ntsh first bits crosses the 
     // byte boundary in the source it's two. 

     int si = startBitPosition/8; // index of the byte in the source 
     // where the bit stream starts 

     byte byteSecondPart; // Temporary variable to store the bits, 
     // that come from the source, to combine them later with the bits 
     // form the right edge of the window 

     int mask = (1 << ntsh) - 1; 
     // the mask of the form 0 0 1 1 1 1 1 1 
     //       |<- ntsh ->| 

     if(ntsh <= nfstbb)// the substring of ntsh first bits 
     // doesn't cross the byte boundary in the source 
     { 
      byteSecondPart = (byte)((source[si] >> (nfstbb - ntsh)) & mask); 
     } 
     else// the substring of ntsh first bits crosses the byte boundary 
     // in the source 
     { 
      byteSecondPart = (byte)(((source[si] << (ntsh - nfstbb)) 
            | (source[si + 1] >> (8 - ntsh + nfstbb))) & mask); 
     } 

     // The bits that go into one byte, but come form two sources 
     // -the right edge of the window and the source, are combined below 
     window[window.Length - nob - 1] = (byte)((window[window.Length - 1] << ntsh) 
               | byteSecondPart); 

     // At this point nob whole bytes in the window need to be filled 
     // with remaining bits form the source. It's done by a common loop 
     // for both cases (nob < window.Length) and (nob >= window.Length) 

    } 
    else// !(nob < window.Length) - all bits of the window will be replaced 
    // with the bits from the source. In this case, only the appropriate 
    // variables are set and the copying is done by the loop common for both 
    // cases 
    { 
     sbtci = (startBitPosition + numberOfBits)/8 - window.Length; 
     nob = window.Length; 
    } 


    if(nfbbte > 0)// The bit substring coppied into one byte in the 
    // window crosses byte boundary in the source, so it has to be 
    // combined form the bits, commming form two consecutive bytes 
    // in the source 
    { 
     for(int i = 0; i < nob; ++i) 
     { 
      window[window.Length - nob + i] = (byte)((source[sbtci + i] << nfbbte) 
       | (source[sbtci + 1 + i] >> (8 - nfbbte))); 
     } 
    } 
    else// The bit substring coppied into one byte in the window 
    // doesn't cross byte boundary in the source, so whole bytes 
    // are simply coppied 
    { 
     for(int i = 0; i < nob; ++i) 
     { 
      window[window.Length - nob + i] = source[sbtci + i]; 
     } 
    } 
}