c - Efficient algorithm for finding a byte in a bit array -

given bytearray uint8_t data[n] efficient method find byte uint8_t search within even if search not octet aligned? i.e. first 3 bits of search in data[i] , next 5 bits in data[i+1].

my current method involves creating bool get_bit(const uint8_t* src, struct internal_state* state) function (struct internal_state contains mask bitshifted right, &ed src , returned, maintaining size_t src_index < size_t src_len) , leftshifting returned bits uint8_t my_register , comparing search every time, , using state->src_index , state->src_mask position of matched byte.

is there better method this?

if you're searching 8 bit pattern within large array can implement sliding window on 16 bit values check if searched pattern part of 2 bytes forming 16 bit value.

to portable have take care of endianness issues done implementation building 16 bit value search pattern manually. high byte iterated byte , low byte following byte. if simple conversion value = *((unsigned short *)pdata) run trouble on x86 processors...

once value, cmp , mask setup cmp , mask shifted. if pattern not found within hi high byte loop continues checking next byte start byte.

here implementation including debug printouts (the function returns bit position or -1 if pattern not found):

int findpattern(unsigned char *data, int size, unsigned char pattern) {     int result = -1;     unsigned char *pdata;     unsigned char *pend;     unsigned short value;     unsigned short mask;     unsigned short cmp;     int tmpresult;        if ((data != null) && (size > 0))     {         pdata = data;         pend = data + size;          while ((pdata < pend) && (result == -1))         {             printf("\n\npdata = {%02x, %02x, ...};\n", pdata[0], pdata[1]);              if ((pdata + 1) < pend)   /* still @ least 2 bytes check? */             {                 tmpresult = (int)(pdata - data) * 8;   /* calculate bit offset according current byte */                  /* avoid endianness troubles "manually" building value! */                 value = *pdata << 8;                 pdata++;                 value += *pdata;                  /* create sliding window check if search patter within value */                 cmp = pattern << 8;                 mask = 0xff00;                 while (mask > 0x00ff)   /* low byte checked within next iteration! */                 {                     printf("cmp = %04x, mask = %04x, tmpresult = %d\n", cmp, mask, tmpresult);                      if ((value & mask) == cmp)                     {                         result = tmpresult;                         break;                     }                      tmpresult++;   /* count bits! */                     mask >>= 1;                     cmp >>= 1;                 }             }             else             {                 /* 1 chance left if there 1 byte left check! */                 if (*pdata == pattern)                 {                     result = (int)(pdata - data) * 8;                 }                  pdata++;             }         }     }      return (result); }