поиск определенной пары битов '10' или '01' в массиве символов - PullRequest
Новая
       11

поиск определенной пары битов '10' или '01' в массиве символов

4 голосов
/ 20 октября 2011

Это может быть немного теоретический вопрос.У меня есть массив байтов, содержащий сетевые пакеты.Я хочу проверить наличие определенной пары бит ('01' или '10') каждые 66 бит.То есть, когда я нахожу первую пару битов, мне нужно пропустить 66 битов и снова проверить наличие этой же пары битов.Я пытаюсь реализовать программу с масками и сменами, и это становится все сложнее.Я хочу знать, может ли кто-нибудь предложить лучший способ сделать то же самое.

Код, который я написал до сих пор, выглядит примерно так.Это не полный вопрос. 

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

Еще одна идея, с которой я пришел, состояла в том, чтобы использовать структуру, определенную ниже 

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

Верен ли мой подход?Может кто-нибудь предложить какие-либо улучшения для того же?

Ответы [ 2 ]

5 голосов
/ 20 октября 2011

Идея таблицы поиска

Есть только 256 возможных байтов. Этого достаточно, чтобы вы могли построить таблицу поиска всех возможных комбинаций битов, которые могут происходить в одном байте.

Значение таблицы поиска может записывать битовую позицию шаблона, а также может иметь специальные значения, отмечающие возможные значения начала продолжения или окончания продолжения.

Edit:

Я решил, что значения продолжения будут глупыми. Вместо этого для проверки шаблона, который перекрывает байт, сдвиньте байт и ИЛИ в бите от другого байта или вручную проверьте конечные биты в каждом байте. Возможно ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x80 и ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x01 подойдут для вас.

Вы не сказали, поэтому я также предполагаю, что вы ищете первое совпадение в любом байте. Если вы ищете каждое совпадение , тогда проверка конечного шаблона на +66 битах - это другая проблема.

Чтобы создать таблицу поиска, я написал бы программу, которая сделает это для меня. Он может быть на вашем любимом языке сценариев или на языке C. Программа напишет файл, который будет выглядеть примерно так: 

/* 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,
};

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

2 голосов
/ 20 октября 2011

Это разновидность классической проблемы деблокирования, которая часто возникает при чтении из потока.То есть данные поступают в дискретных единицах, которые не соответствуют размеру единицы, которую вы хотите сканировать.Проблемы в этом: 1) буферизация (которая не влияет на вас, потому что у вас есть доступ ко всему массиву) и 2) управление всем состоянием (как вы узнали)Хороший подход заключается в написании функции потребителя, которая действует как fread() и fseek(), которая поддерживает свое собственное состояние.Он возвращает запрошенные данные, которые вас интересуют, и выровнен должным образом по отношению к буферам, которые вы ему предоставляете.

...