CODEWITHSUNDEEP
encodingbit-manipulationbit-fieldsbitstuffing
Patrick Oscity
Patrick Oscity

Reputation: 54684

Which data structure should I use for bit stuffing?

I am trying to implement bitstuffing for a project I am working on, namely a simple software AFSK modem. The simplified protocol looks something like this:

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

Now I need to find the reserved sequence 0111 1110 in the received data and therefore must ensure that neither the header nor the data contains six consecutive 1s. This can be done by bit stuffing, e.g. inserting a zero after every sequence of five 1s:

11111111

converts to 

111110111

and 

11111000

converts to 

111110000

If I want to implement this efficiently I guess I should not use arrays of 1s and 0s, where I have to convert the data bytes to 1s and 0s, then populate an array etc. but bitfields of static size do not seem to fit either, because the length of the content is variable due to the bit stuffing.

Which data structure can I use to do bit stuffing more efficiently?

Upvotes: 5

Views: 1250

Answers (1)

Koushik Shetty
Koushik Shetty

Reputation: 2176

I just saw this question now and seeing that it is unanswered and not deleted I'll go ahead and answer. It might help others who see this question and also provide closure.

Bit stuffing: here the maximum contiguous sequence of 1's is 5. After 5 1's there should be a 0 appended after those 5 1's.

Here is the C program that does that:

#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
}

The problem with this is that if there are more that 10 of 5 consecutive 1s then it might overflow. It's better to divide and then bitstuff and repeat.

Upvotes: 1

Related Questions