Suche nach einem bestimmten Bitpaar "10" oder "01" in einem Zeichenfeld

Question

Dies mag eine etwas theoretische Frage sein. Ich habe ein Char-Array mit Bytes, die Netzwerkpakete enthalten. Ich möchte alle 66 Bits prüfen, ob ein bestimmtes Bitpaar ('01' oder '10') vorkommt. Das heißt, sobald ich das erste Bit-Paar gefunden habe, muss ich 66 Bits überspringen und das Vorhandensein desselben Bit-Paares erneut überprüfen. Ich versuche, ein Programm mit Masken und Verschiebungen zu implementieren, und es wird ziemlich kompliziert. Ich möchte wissen, ob jemand einen besseren Weg vorschlagen kann, um das Gleiche zu tun.

Der Code, den ich bisher geschrieben habe, sieht ungefähr so aus. Er ist allerdings nicht vollständig.

test_sync_bits(char *rec, int len)
{
        uint8_t target_byte = 0;
    int offset = 0;
    int save_offset = 0;

    uint8_t *pload = (uint8_t*)(rec + 24);
    uint8_t seed_mask = 0xc0;
    uint8_t seed_shift = 6;
    uint8_t value = 0;
    uint8_t found_sync = 0;
    const uint8_t sync_bit_spacing = 66;

    /*hunt for the first '10' or '01' combination.*/
    target_byte = *(uint8_t*)(pload + offset);
    /*Get all combinations of two bits from target byte.*/
    while(seed_shift)
    {
        value = ((target_byte & seed_mask) >> seed_shift);
        if((value == 0x01) || (value == 0x10))
        {
          save_offset = offset;
          found_sync = 1;
          break;
        }
        else
        {
         seed_mask = (seed_mask >> 2) ;
         seed_shift-=2;
        }  
    }
    offset = offset + 8;
    seed_shift = (seed_shift - 4) > 0 ? (seed_shift - 4) : (seed_shift + 8 - 4);
    seed_mask = (seed_mask >> (6 - seed_shift));
}

Eine andere Idee, die ich hatte, war die Verwendung einer Struktur, die wie folgt definiert ist

typedef struct
{
    int remainder_bits;
    int extra_bits;
    int extra_byte;
}remainder_bits_extra_bits_map_t;

static remainder_bits_extra_bits_map_t sync_bit_check [] =
{
    {6, 4, 0},
    {5, 5, 0},
    {4, 6, 0},
    {3, 7, 0},
    {2, 8, 0},
    {1, 1, 1},
    {0, 2, 1},
};

Ist mein Ansatz richtig? Kann jemand Verbesserungsvorschläge für dasselbe machen?

Answer 1

Idee einer Nachschlagetabelle

Es sind nur 256 Bytes möglich. Das sind so wenige, dass man eine Nachschlagetabelle mit allen möglichen Bitkombinationen erstellen kann, die in einem Byte vorkommen können.

Der Wert der Nachschlagetabelle könnte die Bitposition des Musters aufzeichnen und könnte auch spezielle Werte enthalten, die mögliche Start- oder Endwerte für die Fortsetzung markieren.

Bearbeiten:

Ich habe beschlossen, dass Fortsetzungswerte albern wären. Um ein Muster zu prüfen, das sich mit einem Byte überschneidet, muss man das Byte verschieben und das Bit des anderen Bytes mit ODER verknüpfen oder die Endbits an jedem Byte manuell prüfen. Vielleicht ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x80 y ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x01 für Sie funktionieren würde.

Da Sie das nicht gesagt haben, gehe ich davon aus, dass Sie nach dem erste in jedem Byte übereinstimmen. Wenn Sie suchen nach jede übereinstimmen und dann nach dem Endmuster bei +66 Bits suchen, ist das ein anderes Problem.

Um die Nachschlagetabelle zu erstellen, würde ich ein Programm schreiben, das dies für mich erledigt. Es könnte in Ihrer bevorzugten Skriptsprache oder in C geschrieben sein. Das Programm würde eine Datei schreiben, die etwa so aussieht:

/* each value is the bit position of a possible pattern OR'd with a pattern ID bit. */
/* 0 is no match */
#define P_01 0x00
#define P_10 0x10
const char byte_lookup[256] = {
    /*  0: 0000_0000, 0000_0001, 0000_0010, 0000_0011 */
                   0,    2|P_01,    3|P_01,    3|P_01,
    /*  4: 0000_0100, 0000_0101, 0000_0110, 0000_0111, */
              4|P_01,    4|P_01,    4|P_01,    4|P_01,
    /*  8: 0000_1000, 0000_1001, 0000_1010, 0000_1011, */
              5|P_01,    5|P_01,    5|P_01,    5|P_01,
};

Mühsam. Deshalb würde ich ein Programm schreiben, das das für mich erledigt.

Answer 2

Dies ist eine Variante des klassischen De-Blocking-Problems, das häufig beim Lesen aus einem Stream auftritt. Das heißt, die Daten kommen in diskreten Einheiten, die nicht mit der Größe der Einheit übereinstimmen, die Sie scannen möchten. Die Herausforderungen dabei sind 1) die Pufferung (die Sie nicht betrifft, da Sie Zugriff auf das gesamte Array haben) und 2) die Verwaltung des gesamten Zustands (wie Sie herausgefunden haben). Ein guter Ansatz ist es, eine Verbraucherfunktion zu schreiben, die in etwa wie folgt funktioniert fread() y fseek() die ihren eigenen Zustand beibehält. Es gibt die angeforderten Daten zurück, die Sie interessieren, ordnungsgemäß an den Puffern ausgerichtet, die Sie ihm geben.