hunting for a particular pair of bits '10' or '01' in a character array

Question

This may be a slightly theoretical question. I have a char array of bytes containing network packets. I want to check for the occurrence of a particular pair of bits ('01' or '10')every 66 bits. That is to say once I locate the first pair of bits I have to skip 66 bits and check the presence of same pair of bits again. I am trying to implement a program with masks and shifts and it is kind of getting complicated. I want to know if someone can suggest a better way to do the same thing.

The code I have written so far looks something like this. It is not complete though.

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 I came up with was to use a 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 correct? Can anyone suggest any improvements for the same?

Answer 1

Lookup Table Idea

There are only 256 possible bytes. That is few enough that you can construct a lookup table of all the possible bit combinations that can happen in one byte.

The lookup table value could record the bit position of the pattern and it could also have special values that mark possible continuation start or continuation finish values.

Edit:

I decided that continuation values would be silly. Instead, to check for a pattern that overlaps a byte, shift the byte and OR in the bit from the other byte, or manually check the end bits at each byte. Maybe ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x80 and ((bytes[i] & 0x01) & (bytes[i+1] & 0x80)) == 0x01 would work for you.

You didn't say so I am also assuming that you are looking for the first match in any byte. If you are looking for every match, then checking for the end pattern at +66 bits, that's a different problem.

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

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

Tedious. That's why I would write a program to write it for me.

Answer 2

This is a variation of the classic de-blocking problem that often comes up when reading from a stream. That is, data comes in discrete units that don't match up to the unit size that you wish to scan. The challenges in this are 1) buffering (which doesn't affect you because you have access to the whole array) and 2) managing all of the state (as you found out). A good approach is to write a consumer function that acts something like fread() and fseek() which maintains its own state. It returns the requested data you're interested in, aligned properly to the buffers you give it.