What is a better method for packing 4 bytes into 3 than this?

Question

I have an array of values all well within the range 0 - 63, and decided I could pack every 4 bytes into 3 because the values only require 6 bits and I could use the extra 2bits to store the first 2 bits of the next value and so on.

Having never done this before I used the switch statement and a nextbit variable (a state machine like device) to do the packing and keep track of the starting bit. I'm convinced however, there must be a better way.

Suggestions/clues please, but don't ruin my fun ;-)

Any portability problems regarding big/little endian?

btw: I have verified this code is working, by unpacking it again and comparing with the input. And no it ain't homework, just an exercise I've set myself.

/* build with gcc -std=c99 -Wconversion */
#define ASZ 400
typedef unsigned char uc_;
uc_ data[ASZ];
int i;
for (i = 0; i < ASZ; ++i) {
    data[i] = (uc_)(i % 0x40);
}
size_t dl = sizeof(data);
printf("sizeof(data):%z\n",dl);
float fpl = ((float)dl / 4.0f) * 3.0f;
size_t pl = (size_t)(fpl > (float)((int)fpl) ? fpl + 1 : fpl);
printf("length of packed data:%z\n",pl);

for (i = 0; i < dl; ++i)
    printf("%02d  ", data[i]);
printf("\n");

uc_ * packeddata = calloc(pl, sizeof(uc_));
uc_ * byte = packeddata;
uc_ nextbit = 1;
for (int i = 0; i < dl; ++i) {
    uc_ m = (uc_)(data[i] & 0x3f);
    switch(nextbit) {
    case 1:
        /* all 6 bits of m into first 6 bits of byte: */
        *byte = m;
        nextbit = 7;
        break;
    case 3:
        /* all 6 bits of m into last 6 bits of byte: */
        *byte++ = (uc_)(*byte | (m << 2));
        nextbit = 1;
        break;
    case 5:
        /* 1st 4 bits of m into last 4 bits of byte: */
        *byte++ = (uc_)(*byte | ((m & 0x0f) << 4));
        /* 5th and 6th bits of m into 1st and 2nd bits of byte: */
        *byte = (uc_)(*byte | ((m & 0x30) >> 4));
        nextbit = 3;
        break;
    case 7:
        /* 1st 2 bits of m into last 2 bits of byte: */
        *byte++ = (uc_)(*byte | ((m & 0x03) << 6));
        /* next (last) 4 bits of m into 1st 4 bits of byte: */
        *byte = (uc_)((m & 0x3c) >> 2);
        nextbit = 5;
        break;
    }
}

Answer 1

So, this is kinda like code-golf, right?

---

#include <stdlib.h>
#include <string.h>

static void pack2(unsigned char *r, unsigned char *n) {
  unsigned v = n[0] + (n[1] << 6) + (n[2] << 12) + (n[3] << 18);
  *r++ = v;
  *r++ = v >> 8;
  *r++ = v >> 16;
}

unsigned char *apack(const unsigned char *s, int len) {
  unsigned char *s_end = s + len,
                *r, *result = malloc(len/4*3+3),
                lastones[4] = { 0 };
  if (result == NULL)
    return NULL;
  for(r = result; s + 4 <= s_end; s += 4, r += 3)
    pack2(r, s);
  memcpy(lastones, s, s_end - s);
  pack2(r, lastones);
  return result;
}

Answer 2

Check out the IETF RFC 4648 for 'The Base16, Base32 and Base64 Data Encodings'.

Partial code critique:

size_t dl = sizeof(data);
printf("sizeof(data):%d\n",dl);
float fpl = ((float)dl / 4.0f) * 3.0f;
size_t pl = (size_t)(fpl > (float)((int)fpl) ? fpl + 1 : fpl);
printf("length of packed data:%d\n",pl);

Don't use the floating point stuff - just use integers. And use '%z' to print 'size_t' values - assuming you've got a C99 library.

size_t pl = ((dl + 3) / 4) * 3;

I think your loop could be simplified by dealing with 3-byte input units until you've got a partial unit left over, and then dealing with a remainder of 1 or 2 bytes as special cases. I note that the standard referenced says that you use one or two '=' signs to pad at the end.

I have a Base64 encoder and decode which does some of that. You are describing the 'decode' part of Base64 -- where the Base64 code has 4 bytes of data that should be stored in just 3 - as your packing code. The Base64 encoder corresponds to the unpacker you will need.

Base-64 Decoder

Note: base_64_inv is an array of 256 values, one for each possible input byte value; it defines the correct decoded value for each encoded byte. In the Base64 encoding, this is a sparse array - 3/4 zeroes. Similarly, base_64_map is the mapping between a value 0..63 and the corresponding storage value.

enum { DC_PAD = -1, DC_ERR = -2 };

static int decode_b64(int c)
{
    int b64 = base_64_inv[c];

    if (c == base64_pad)
        b64 = DC_PAD;
    else if (b64 == 0 && c != base_64_map[0])
        b64 = DC_ERR;
    return(b64);
}

/* Decode 4 bytes into 3 */
static int decode_quad(const char *b64_data, char *bin_data)
{
    int b0 = decode_b64(b64_data[0]);
    int b1 = decode_b64(b64_data[1]);
    int b2 = decode_b64(b64_data[2]);
    int b3 = decode_b64(b64_data[3]);
    int bytes;

    if (b0 < 0 || b1 < 0 || b2 == DC_ERR || b3 == DC_ERR || (b2 == DC_PAD && b3 != DC_PAD))
        return(B64_ERR_INVALID_ENCODED_DATA);
    if (b2 == DC_PAD && (b1 & 0x0F) != 0)
        /* 3rd byte is '='; 2nd byte must end with 4 zero bits */
        return(B64_ERR_INVALID_TRAILING_BYTE);
    if (b2 >= 0 && b3 == DC_PAD && (b2 & 0x03) != 0)
        /* 4th byte is '='; 3rd byte is not '=' and must end with 2 zero bits */
        return(B64_ERR_INVALID_TRAILING_BYTE);
    bin_data[0] = (b0 << 2) | (b1 >> 4);
    bytes = 1;
    if (b2 >= 0)
    {
        bin_data[1] = ((b1 & 0x0F) << 4) | (b2 >> 2);
        bytes = 2;
    }
    if (b3 >= 0)
    {
        bin_data[2] = ((b2 & 0x03) << 6) | (b3);
        bytes = 3;
    }
    return(bytes);
}

/* Decode input Base-64 string to original data.  Output length returned, or negative error */
int base64_decode(const char *data, size_t datalen, char *buffer, size_t buflen)
{
    size_t outlen = 0;
    if (datalen % 4 != 0)
        return(B64_ERR_INVALID_ENCODED_LENGTH);
    if (BASE64_DECLENGTH(datalen) > buflen)
        return(B64_ERR_OUTPUT_BUFFER_TOO_SMALL);
    while (datalen >= 4)
    {
        int nbytes = decode_quad(data, buffer + outlen);
        if (nbytes < 0)
            return(nbytes);
        outlen += nbytes;
        data += 4;
        datalen -= 4;
    }
    assert(datalen == 0);   /* By virtue of the %4 check earlier */
    return(outlen);
}

Base-64 Encoder

/* Encode 3 bytes of data into 4 */
static void encode_triplet(const char *triplet, char *quad)
{
    quad[0] = base_64_map[(triplet[0] >> 2) & 0x3F];
    quad[1] = base_64_map[((triplet[0] & 0x03) << 4) | ((triplet[1] >> 4) & 0x0F)];
    quad[2] = base_64_map[((triplet[1] & 0x0F) << 2) | ((triplet[2] >> 6) & 0x03)];
    quad[3] = base_64_map[triplet[2] & 0x3F];
}

/* Encode 2 bytes of data into 4 */
static void encode_doublet(const char *doublet, char *quad, char pad)
{
    quad[0] = base_64_map[(doublet[0] >> 2) & 0x3F];
    quad[1] = base_64_map[((doublet[0] & 0x03) << 4) | ((doublet[1] >> 4) & 0x0F)];
    quad[2] = base_64_map[((doublet[1] & 0x0F) << 2)];
    quad[3] = pad;
}

/* Encode 1 byte of data into 4 */
static void encode_singlet(const char *singlet, char *quad, char pad)
{
    quad[0] = base_64_map[(singlet[0] >> 2) & 0x3F];
    quad[1] = base_64_map[((singlet[0] & 0x03) << 4)];
    quad[2] = pad;
    quad[3] = pad;
}

/* Encode input data as Base-64 string.  Output length returned, or negative error */
static int base64_encode_internal(const char *data, size_t datalen, char *buffer, size_t buflen, char pad)
{
    size_t outlen = BASE64_ENCLENGTH(datalen);
    const char *bin_data = (const void *)data;
    char *b64_data = (void *)buffer;

    if (outlen > buflen)
        return(B64_ERR_OUTPUT_BUFFER_TOO_SMALL);
    while (datalen >= 3)
    {
        encode_triplet(bin_data, b64_data);
        bin_data += 3;
        b64_data += 4;
        datalen -= 3;
    }
    b64_data[0] = '\0';

    if (datalen == 2)
        encode_doublet(bin_data, b64_data, pad);
    else if (datalen == 1)
        encode_singlet(bin_data, b64_data, pad);
    b64_data[4] = '\0';
    return((b64_data - buffer) + strlen(b64_data));
}

I complicate life by having to deal with a product that uses a variant alphabet for the Base64 encoding, and also manages not to pad data - hence the 'pad' argument (which can be zero for 'null padding' or '=' for standard padding. The 'base_64_map' array contains the alphabet to use for 6-bit values in the range 0..63.