# 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. Jul 18, 2017 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. Jul 18, 2017 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, 2017 at 23:19

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));


There are many architectures where shifting is more expensive than masking, but I doubt there are any where the reverse holds. Thus, the following code, even though it probably requires one extra machine code instruction (3 shifts vs. 4 masks) is likely to be faster:

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. Jul 18, 2017 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) Jul 18, 2017 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. Jul 18, 2017 at 23:07
• Where is shifting not more expensive than masking? Many architectures lack barrel shifters, but none lack AND gates. :-) Jul 19, 2017 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. Jul 19, 2017 at 12:34