Search code examples
c++cbitarray

Little Big Endian Bit Operation and Extraction

I am trying to work out a solution to a driver problem in which I have to extract a number of bits from an arbitrary bit stream starting from an arbitrary position. I have searched for the post around here and I have found that most of the Bit operations involved are 64 Bit machines or no special storage layout conditions.

Well, the Bit stream is stored as a Byte array in a 32 bit Micro. But the stream is little endian, for example a stream of bytes below

LSBit (Bit 0) --> 0100 1001 0100 0100 <-- MSBit (Bit 15)

is stored in memory as

Byte 0 1001 0010 Bit Layout, Bit 7-> 1001 0010 -> Bit 0

Byte 1 0010 0010 Bit Layout, Bit 15-> 0010 0010 -> Bit 8

here the Bit layout in a Byte is Big Endian, but the bytes are Little Endian.

If I have to extract Bit 4 to 11 from the Little endian stream to get 0010 1001 then I need to extract

from Byte 0

1001, Higher nibble of Byte 0

from Byte 1

0010, Lower Nibble of Byte 1

Shift the bits left from Byte 1 to get 0010 and OR with 1001 from Byte 0

The problem is that the stream can go to a length of 64 bits and the number of bits (upto 64) is arbitrary, as well as the starting bit is arbitrary. But for storage internally I can of course store in the appropriate data type which can fit the bits of course.

And to add to this, I have to pack them in the same way, from a valid data into this stream of Little Big Endian. :'(

I have to worry about runtime as well and the fact that long is 4 bytes. So to store a value of 48 bits I need to maintain an array of 6 bytes arranged in host format. without the compiler long long support.

EDIT: 64-bit long long support is there; I just checked the compiler manual.

Any suggestions please, I am stuck for three weeks now.

Solution

  • Read your stream byte-per-byte, building a 64Bit number in host-byte-order (As that is the maximum bitstream length).
    Then extract using standard bit-fiddling.

    This two-step recipe has the benefit of being host-endian-agnostic.

    Getting a window of n bits at index i:

    uint64_t extract(uint64_t in, int n, int i) {
    return in<<(64-i-n)>>(64-n);
}