#c #pointers #bit-manipulation #bitwise-operators
#c #указатели #манипулирование битами #побитовые операторы
Вопрос:
Это может быть немного теоретический вопрос. У меня есть массив символов байтов, содержащий сетевые пакеты. Я хочу проверить наличие определенной пары битов (’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 amp; 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},
};
Правильный ли мой подход? Кто-нибудь может предложить какие-либо улучшения для того же?
Комментарии:
1. Я бы рекомендовал использовать или записать какой-либо битовый массив (может быть, dynamic_bitset от boost?). Лично я написал свой собственный. Но он должен обрабатывать чтение x бит в битовой позиции y и обрабатывать все раздражающие крайние случаи. Тогда вы сможете закодировать свою идею намного аккуратнее.
2. Можете ли вы показать шестнадцатеричный дамп, скажем, в 100 байт, который включает эти биты синхронизации?
Ответ №1:
Идея таблицы поиска
Существует только 256 возможных байтов. Этого достаточно мало, чтобы вы могли построить таблицу поиска всех возможных комбинаций битов, которые могут произойти в одном байте.
Значение таблицы поиска может записывать битовую позицию шаблона, а также может иметь специальные значения, которые отмечают возможные значения начала или окончания продолжения.
Редактировать:
Я решил, что значения продолжения будут глупыми. Вместо этого, чтобы проверить шаблон, который перекрывает байт, сдвиньте байт и / ИЛИ в бит из другого байта или вручную проверьте конечные биты в каждом байте. Может ((bytes[i] amp; 0x01) amp; (bytes[i 1] amp; 0x80)) == 0x80 быть, и ((bytes[i] amp; 0x01) amp; (bytes[i 1] amp; 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,
};
Утомительно. Вот почему я бы написал программу, которая написала бы это для меня.
Комментарии:
1. что вы подразумеваете под 256 возможными байтами? можете ли вы немного расширить это?
2. @liv2hak: 2 ^ 8 = 256. В одном байте содержится 256 различных комбинаций битов. Моя идея состоит в том, чтобы сканировать по одному байту за раз, а не по биту за раз, как вы делали.
3. ОК. Я решил продолжить идею byte_lookup. но прежде всего вы определили P_01 0x00. Я думаю, что это должно быть 0x01 (поскольку 0x01 и 0x10 — это битовые шаблоны, которые я ищу.). И я до сих пор не понимаю, почему вы ИЛИ возможный шаблон (все комбинации 00,01,10 и 11 во всех позициях с битом идентификатора шаблона (что это значит?)) Извините, что беспокою вас. но мне трудно понять эту концепцию.
4. Я вижу только общее количество 9 * 4 = 36 допустимых комбинаций. Которые в основном представляют собой пары 00,01,01,11 в позициях битов.(0,1)(1,2)(2,3)(3,4)(4,5)(5,6)(6,7)(7,0)( перекрывающийся случай), из которых 9 * 2 = 18 случаев являются действительными, а остальные 18 случаев являются недействительными (00,11 случаев). Звучит ли моя логика разумно. Я подозреваю, что, возможно, я что-то упускаю из виду, что вы говорите.
5.@liv2hak: P_01 и P_10 предназначены для того, чтобы вы знали, какой шаблон найден.
if( (byte_lookup[byte] amp; 0x10) == P_01) {}if( (byte_lookup[byte] amp; 0x10) == P_10) {}
Ответ №2:
Это вариант классической проблемы деблокирования, которая часто возникает при чтении из потока. То есть данные поступают в дискретных единицах, которые не соответствуют размеру единицы, которую вы хотите сканировать. Проблемами в этом являются 1) буферизация (которая не влияет на вас, потому что у вас есть доступ ко всему массиву) и 2) управление всем состоянием (как вы выяснили). Хорошим подходом является написание функции-потребителя, которая действует примерно так fread() и fseek() которая поддерживает свое собственное состояние. Он возвращает запрошенные данные, которые вас интересуют, правильно выровненные по буферам, которые вы им предоставляете.