Compressing a 'char' array using bit packing

Question

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

Answer 1

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.