Fastest way to convert 7-bit values into bytes

Question

I need to convert 112 bits (16 Bytes) of 7-bit value variables (They are received in bytes but the MSb have to be discarded) into 14 bytes the fastest way possible in C.

So basically, what I need to do is to take the first 7 bits of the first byte received and shift them to the left and then take the 7th bit of the the second byte put it in the first byte to store in the bit position 0 so I would get in the first byte the 7 bits of the first byte received plus the 7th bit of the second byte. Then I would have to do the same with the rest.

The first way I can think of to that would be this:

byteToStore [0] = 1 << byteReceived[0] + byteReceived[1] & 1; 
byteToStore [1] = 2 << byteReceived[1] + byteReceived[2] & 3; 
byteToStore [2] = 3 << byteReceived[2] + byteReceived[3] & 7; 

And so on.

Also, it would be great if it could be made easily with a for loop. I could it with a for loop with my method but it wouldn't be so "clean".

Thank you.

Answer 1

You want to pack some bits from adjacent bytes into one byte. That can be achieved by combining the lowest 7 bits of the left byte shifted left with the lowest 7 bits of the right byte shifted right:

void pack(const uint8_t in[16], uint8_t out[14])
{
    out[ 0] = (in[ 0] & 0x7f) << 1 | (in[ 1] & 0x7f) >> 6;
    out[ 1] = (in[ 1] & 0x7f) << 2 | (in[ 2] & 0x7f) >> 5;
    out[ 2] = (in[ 2] & 0x7f) << 3 | (in[ 3] & 0x7f) >> 4;
    out[ 3] = (in[ 3] & 0x7f) << 4 | (in[ 4] & 0x7f) >> 3;
    out[ 4] = (in[ 4] & 0x7f) << 5 | (in[ 5] & 0x7f) >> 2;
    out[ 5] = (in[ 5] & 0x7f) << 6 | (in[ 6] & 0x7f) >> 1;
    out[ 6] = (in[ 6] & 0x7f) << 7 | (in[ 7] & 0x7f) >> 0;

    out[ 7] = (in[ 8] & 0x7f) << 1 | (in[ 9] & 0x7f) >> 6;
    out[ 8] = (in[ 9] & 0x7f) << 2 | (in[10] & 0x7f) >> 5;
    out[ 9] = (in[10] & 0x7f) << 3 | (in[11] & 0x7f) >> 4;
    out[10] = (in[11] & 0x7f) << 4 | (in[12] & 0x7f) >> 3;
    out[11] = (in[12] & 0x7f) << 5 | (in[13] & 0x7f) >> 2;
    out[12] = (in[13] & 0x7f) << 6 | (in[14] & 0x7f) >> 1;
    out[13] = (in[14] & 0x7f) << 7 | (in[15] & 0x7f) >> 0;
}

Although there is a clear pattern for each of the blocks, it is probably faster to code this without a loop, because the loop control and shift arithmetic won't take any time. The code might be sped up by precalculating an auxiliary input array with all the most significant bits already removed, so you don't have to extract the lowest 7 bits (x & 0x7f) twice for each bit. (The last right shift by 0 doesn't do anything, but the compiler will optimise it away. I've kept it for symmetry.)