How do I parse out n-bit elements from a byte addressable array

Question

I have a data stream that is addressable only in 8-bit bytes, I want to parse it out into 6-bit elements and store that into an array. Is there any best known methods to do this?

11110000 10101010 11001100

into

an array like

111100|001010|101011|001100

(can have zero padding, just needs to be addressable this way)

and the data is an 8-bit array that is also a multiple of 6-bits , not really endless

Answer 1

You count your 5 bit sequences, read each byte, shift the bits based on your counter and the expected word position (by xor-ing pieces from neighboring byte words), and form new correctly aligned byte words that you then process.

I hope you don't expect code ...

Answer 2

Depends how much bits a byte has on your particular architecture. On a six bit architecture it is quite simple :-)

Assuming a 8 bits per byte architecture you will have to do something along the lines:

int sixbits(unsigned char* datastream, unsigned int n) {
    int bitpos = n*6;
    return (datastream[bitpos/8] >> bitpos%8)    // lower part of the five bit group
        + (datastream[bitpos/8+1] << 8-bitpos%8) // if bitpos%8>2, we need to add some carry bits from the next char
        & 0x3f;                                  // and finally mask the lowest 6 bits
}

Where n is the n-th 6 bit group. Any decent compiler will substitute the division with shifts and the moduli with ands. Just use this function in a loop to fill up your destination array.

Answer 3

How about using a struct like this:

struct bit5
{
    unsigned int v1 : 5;
    unsigned int v2 : 5;
    unsigned int v3 : 5;
    unsigned int v4 : 5;
    unsigned int v5 : 5;
    unsigned int v6 : 5;
    unsigned int v7 : 5;
    unsigned int v8 : 5;
};

And then cast your array of bytes to the struct bit5 every 8 bytes (40 bits = 8 groups of 5 bits, fits in 8 bytes) to get the 5 bit chunks. Say:

unsigned char* array; // a byte array that you want to convert
int i;
struct bit5* pBit5;

for(i = 0; i < (int)(SIZE_OF_ARRAY / 8); i++)
    pBit5 = (struct bit5*)((int)array + i * 8);

Answer 4

You can do it using bit fiddling:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[])
{
    unsigned char source[3] = { 15, 85, 51 };
    unsigned char destination[4];
    memset(destination, 0, 4);
    for (int i = 0; i < (8 * 3); ++i)
    {
     destination[i / 6] |= ((source[i / 8] >> (i % 8) & 1) << (i % 6));
    }

    for (int j = 0; j < 4; ++j)
     printf("%d ", destination[j]);
}

Output:

15 20 53 12

Note that this starts working from the five least significant bits.

      15       85       51
11110000 10101010 11001100
111100 001010 101011 001100
    15     20     53     12

To get most significant first, do this instead:

destination[i / 6] |= ((source[i / 8] >> (7 - (i % 8))) & 1) << (5 - (i % 6));

This works as in your example, assuming you wrote the most significant bit first:

240      170      204
11110000 10101010 11001100
111100 001010 101011 001100
60     10     43     12

Answer 5

I would consider using a BitStream. It will allow you to read one bit at a time. You can shift that bit directly into place (using << n). It may not perform as well as reading an 8-bit byte at a time but it would certainly be cleaner looking code.

Answer 6

How about this Union?

union _EIGHT_TO_SIX_ {

    struct {

       unsigned char by6Bit0 : 6;
       unsigned char by6Bit1 : 6;
       unsigned char by6Bit2 : 6;
       unsigned char by6Bit3 : 6;

    } x6;

    struct {

       unsigned char by8Bit0;
       unsigned char by8Bit0;
       unsigned char by8Bit0;

    } x8;
}

Setting by8Bitx will automatically fill in by6Bitx ~~~