Search for a specific pair of bits "10" or "01" in an array of characters

Question

This may be a little theoretical question. I have a w980 byte array containing network packets. I want to check for the presence of each pair of bits ('01' or '10') every 66 bits. That is, as soon as I find the first pair of bits, I must skip 66 bits and check again for the presence of the same pair of bits. I am trying to implement a program with masks and shifts, and it is quite difficult. I want to know if anyone can suggest a better way to do the same.

The code I wrote so far looks something like this. However, it is not complete.

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

Another idea that I came up with was to use the structure defined below

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

Is my approach right? Can anyone suggest any improvements for the same?

Answer 1

Search table idea

There are only 256 possible bytes. It’s not enough that you can build a lookup table for all possible combinations of bits that can occur in one byte.

The value of the lookup table can record the position of the bit in the template, and also have special values ​​that indicate the possible values ​​of the continuation or continuation of the continuation.

Edit:

I decided that the meanings of the sequel would be silly. Instead, to check for a pattern that overlays a byte, shift the byte and OR into a bit from another byte, or manually check the trailing bits in each byte. Perhaps ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x80 and ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x01 will work for you.

You did not say this, I also assume that you are looking for a first match in any byte. If you are looking for every match, then check the end pattern for +66 bits, this is another problem.

To create a lookup table, I would write a program to do this for me. It can be in your favorite script language or it can be in C. The program will write a file that looks something like this:

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

tiring. That is why I will write a program to write it for me.

Answer 2

This is a variation of the classic unlock problem that often arises when reading from a stream. That is, the data comes in separate units that do not match the size of the block that you want to scan. The problems are: 1) buffering (which does not affect you because you have access to the entire array) and 2) managing the entire state (as you found out). A good approach is to write a consumer function that acts like fread() and fseek() , which retains its own state. It returns the requested data that interests you, aligns correctly with the buffers that you give it.