Какую структуру данных я должен использовать для вставки битов?

Question

Я пытаюсь реализовать битовый набор для проекта, над которым я работаю, а именно для простого программного модема AFSK. Упрощенный протокол выглядит примерно так:

0111 1110    # burst sequence
0111 1110    # 16 times 0b0111_1110
   ...
0111 1110
   ...
   ...       # 80 bit header (CRC, frame counter, etc.)
   ...
0111 1110    # header delimiter
   ...
   ...       # data
   ...
0111 1110    # end-of-frame sequence

Теперь мне нужно найти зарезервированную последовательность 0111 1110 в полученных данных и, следовательно, должны убедиться, что ни заголовок, ни данные не содержат шесть последовательных 1s. Это может быть сделано путем вставки битов, например, вставляя ноль после каждой последовательности из пяти 1s:

11111111  

превращается в

111110111  

а также

11111000  

превращается в

111110000

Если я хочу реализовать это эффективно, я думаю, что я не должен использовать массивы 1с и 0s, где я должен преобразовать байты данных в 1с и 0s, затем заполняют массив и т. д., но битовые поля статического размера тоже не подходят, потому что длина содержимого является переменной из-за вставки битов.

Какую структуру данных я могу использовать для более эффективной загрузки битов?

Answer 1

Я только что увидел этот вопрос сейчас и, увидев, что он остается без ответа и не удален, я продолжу и отвечу. Это может помочь тем, кто видит этот вопрос, а также обеспечить закрытие.

Битовая начинка: здесь максимальная непрерывная последовательность 1's является 5, После 51's должен быть 0 добавлено после тех 51's,

Вот программа C, которая делает это:

#include <stdio.h>
typedef unsigned long long int ulli;

int main()
{
    ulli buf = 0x0fffff01, // data to be stuffed
         temp2= 1ull << ((sizeof(ulli)*8)-1), // mask to stuff data
         temp3 = 0; // temporary  

    int count = 0; // continuous 1s indicator

    while(temp2)
    {
        if((buf & temp2) && count <= 5) // enter the loop if the bit is `1` and if count <= 5
        {
            count++;
            if(count == 5)
            {
                temp3 = buf & (~(temp2 - 1ull)); // make MS bits all 1s
                temp3 <<= 1ull; // shift 1 bit to accomodeate the `0`
                temp3 |= buf & ((temp2) - 1); // add back the LS bits or original producing stuffed data
                buf = temp3;
                count = 0; // reset count
                printf("%llx\n",temp3); // debug only               
            }           
        }
        else
        {
            count = 0; // this was what took 95% of my debug time. i had not put this else clause :-)
        }
        temp2 >>=1; // move on to next bit.
    }
    printf("ans = %llx",buf); // finally
}

Проблема заключается в том, что если есть более 10 из 5 последовательных 1, то он может переполниться. Лучше разделить, а потом по кусочкам и повторить.