Compressing a 'char' array using bit packing

I have a large array (around 1 MB) of type unsigned char (i.e. uint8_t). I know that the bytes in it can have only one of 5 values (i.e. 0, 1, 2, 3, 4). Moreover, we do not need to preserve '3's from the input, they can be safely lost when we encode/decode.

So I guessed bit packing would be the simplest way to compress it, so every byte can be converted to 2 bits (00, 01..., 11).

As mentioned, all elements of value 3 can be removed (i.e. saved as 0), which gives me option to save '4' as '3'. While reconstructing (decompressing) I restore 3's to 4's.

I wrote a small function for the compression but I feel this has too many operations and is just not efficient enough. Any suggestions or hints on how to handle the operations more efficiently but maintaining the readability will be of much help.

/// Compress by packing ...
void compressByPacking (uint8_t* out, uint8_t* in, uint32_t length)
{
for (int loop = 0; loop < length/4; loop ++, in += 4, out++)
{
uint8_t temp[4];

for (int small_loop = 0; small_loop < 4; small_loop++)
{
temp[small_loop] = *in;           // Load into local variable

if (temp[small_loop] == 3)        // 3's are discarded
temp[small_loop] = 0;
else if (temp[small_loop] == 4)   // and 4's are converted to 3
temp[small_loop] = 3;

} // end small loop

// Pack the bits into write pointer
*out = (uint8_t)((temp[0] & 0x03) << 6) |
((temp[1] & 0x03) << 4) |
((temp[2] & 0x03) << 2) |
((temp[3] & 0x03));

} // end loop
}


Cross-posted from SO

• Cross-posted from Stack Overflow. As a courtesy to other users, please declare your cross-posts. – 200_success Jul 18 '17 at 21:00
• @200_success I am quite new to SO/SO and wasn't aware of that. Thanks for adding the information in comment. I will edit and add a mention in my post too. – avikpram Jul 18 '17 at 21:27
• It would be good to mention what target you are building for - some analysis on the other thread has assumed x86/x64 – M.M Jul 18 '17 at 23:19

1 Answer

Conditional jumps are murder on throughput due to branch-misprediction. Consider simply using a lookup-table instead:

const static uint8_t map[] = { 0, 1, 2, 0, 3 };
*out = (uint8_t)
( (map[in[0]] << 0)
| (map[in[1]] << 2)
| (map[in[2]] << 4)
| (map[in[3]] << 6));


On some architectures, shifting is more expensive than masking, so this variant might be faster (even though it probably requires one extra machine code instruction):

const static uint8_t map[] = { 0x00, 0x55, 0xaa, 0x00, 0xff };
*out = (uint8_t)
( (map[in[0]] & 0x03)
| (map[in[1]] & 0x0c)
| (map[in[2]] & 0x30)
| (map[in[3]] & 0xc0));


By the way, how do you handle the tail of up to 3 bytes? Or is your data guaranteed to be a multiple of 4 bytes long?

Also, your inner loop currently duplicates the first byte of every 4-byte-chunk four times.

Your comments are blatantly superfluous; at best they repeat the code. Say why you do something, not what you just did.

• Thanks @Deduplicator . This might the simplest possible optimization without. To answer your questions 1) The input and output data is multiple of 4. So that's not a problem. 2) Sorry about the inner-loop issue. I was tinkering with it and should've checked before posting it. Apologies. 3) Thanks for pointing out the about 'obvious' comments. I guess it's result of a bad habits acquired long back in some dept where stuff like that was commended. * sigh * Trying to get rid of it. – avikpram Jul 18 '17 at 21:41
• this will be safer isn't it (to avoid any out-of-bound array access) :(map[in[0] % 5] << 0) | (map[in[1] % 5] << 2) | (map[in[2] % 5] << 4) | (map[in[3] % 5] << 6) – avikpram Jul 18 '17 at 22:23
• @avikpram: You know remainder is a very expensive operation? And you only moved from invalid data possibly crashing to GIGO, which is cheaper done by extending map to 256 entries, and is anyway not really an improvement. If you insist, you could put assert(in[0] < 5 && in[1] < 5 && in[2] < 5 && in[3] < 5); before the mapping. That's removed in release builds, if you want to retain the check maybe if(...) abort(); is more to your liking. – Deduplicator Jul 18 '17 at 23:07
• Where is shifting not more expensive than masking? Many architectures lack barrel shifters, but none lack AND gates. :-) – Cody Gray Jul 19 '17 at 8:44
• @CodyGray Thanks for the improvement suggestions. I am not sure which one is faster but I think I would go with masking. Also, aesthetics :) , but that's a personal preference I guess. – avikpram Jul 19 '17 at 12:34