C: Вычисление серии бит натянутой на несколько байт

Question

Я получил неподписанный символ массив байт, как:

unsigned char[20] = {0xff, 0x1a, 0x70, 0xa9, ...} 

теперь я хочу, чтобы выполнять вычисления над й последовательными битами этого массива (с x > 8, например, x = 15). В частности, я хочу выполнить мажоритарное голосование каждые 15 бит, которое возвращает один бит. Впоследствии возвращаемые одиночные биты снова преобразуются в байты без знака.

Я уже реализовал алгоритм mostVoting. Я также реализован наивный алгоритм для всей задачи, которая работает следующим образом:

1. Преобразовать массив байтов в битовый массив (также неподписанные символ [], проведение нулей и единиц)
2. петлю на битовый массив и передавать каждую серию x бит в функцию большинства голосов
3. Соберите результаты большинства голосов также в бит-массиве (unsigned char [])
4. Заверните этот бит-массив и используйте побитовые операции для построения байтов из каждой серии из 8 биты.

Для меня это кажется интуитивным, но громоздким в то же время.

Вы видите какие-либо возможности для оптимизации или вы даже можете дать алгоритм скольжения?

С наилучшими пожеланиями, P.

Answer 1

Вы можете получить следующий бит массива с помощью функции, как этот

int nextBit(unsigned char [] arr, int *pByte, size_t nBytes, int *pBit) 
{ 
     int result; 

     if(*pByte >= nBytes) { 
      // Padding, neccessary if nBytes % 15 != 0 
      return 0; 
     } else { 
      result = (arr[*pByte] >> (*pBit)) & 0x1; 
      if(*pBit == 7) { 
       (*pByte)++; 
       *pBit = 0; 
      } else { 
       (*pBit)++; 
      } 
      return result; 
     } 
} 

и петли:

int byte=0, bit=0; 
int result; 
int i; 

while(byte < sizeof(arr)) { 
    for(i=0; i<15; i++) { 
     result = nextBit(arr, &byte, sizeof(arr), &bit); 
     // do the majority voting 
    } 
} 

Совершенно аналогичные функции могут создаются для непосредственного создания массива большинства бит

Answer 2

Вы можете битрейт каждого байта в 17 бит (и хранить их в 17 байт).

uint8_t bits[17]; 
bits[0] = !!(bytes[0] & 128); 
bits[1] = !!(bytes[0] & 64); 
bits[2] = !!(bytes[0] & 32); 
bits[3] = !!(bytes[0] & 16); 
bits[4] = !!(bytes[0] & 8); 
bits[5] = !!(bytes[0] & 4); 
bits[6] = !!(bytes[0] & 2); 
bits[7] = !!(bytes[0] & 1); 
bits[8] = !!(bytes[1] & 128); 
bits[9] = !!(bytes[1] & 64); 
bits[10] = !!(bytes[1] & 32); 
bits[11] = !!(bytes[1] & 16); 
bits[12] = !!(bytes[1] & 8); 
bits[13] = !!(bytes[1] & 4); 
bits[14] = !!(bytes[1] & 2); 
bits[15] = !!(bytes[1] & 1); 
bits[16] = !!(bytes[2] & 128); 

Я не уверен, что вы хотите делать с этими битами, но вы можете также рассмотреть вопрос о хранении битов в 32 разрядное целое число:

uint32_t chunk = (bytes[0] << 9) | (bytes[1] << 1) | (bytes[2] & 1);