Encoding a string into base64

Question

I'm trying to create a simple HTTP client. In order to make one that is standard compliant, I must be able to extract user information from a URI and convert it to base64 and send it via an authentication header to the server. I created this demo program to test my progress on this function I've made. Does this program seem sufficient? Is there any major flaws with it? You can see the demo here.

char *base64encode(char *input) {
    int len = strlen(input), padding = (len % 3)?3 - (len % 3):0, n, xlen = 0;
    size_t bitlen = len * 8;
    uint8_t *x = malloc(((int)(bitlen / 24) * 4) + ((padding)?4:0)), i, o;
    for (n = 0; n < len; n++) {
        switch (n % 3) {
            case 0:
                i = (uint8_t)(input[n] >> 2);
                x[xlen++] = i;
                break;
            case 1:
                i = (uint8_t)((input[n-1] & 3) << 4);
                o = (uint8_t)((input[n] & 240) >> 4);
                x[xlen++] = i | o;
                break;
            case 2:
                i = (uint8_t)((input[n-1] & 15) << 2);
                o = (uint8_t)((input[n] & 192) >> 6);
                x[xlen++] = i | o;
                i = (uint8_t)(input[n] & 63);
                x[xlen++] = i;
                break;
        }
        if ((len - n) == ((padding==2)?2:3) && padding > 0) {
            n++;
            break;
        }
    }
    if (padding == 2) {
        i = (uint8_t)(input[n] >> 2);
        x[xlen++] = i;
        i = (uint8_t)((input[n] & 3) << 4);
        x[xlen++] = i;
    } else if (padding == 1) {
        i = (uint8_t)(input[n] >> 2);
        x[xlen++] = i;
        i = (uint8_t)((input[n] & 3) << 4);
        o = (uint8_t)((input[n+1] & 240) >> 4);
        x[xlen++] = i | o;
        i = (uint8_t)((input[n+1] & 15) << 2);
        x[xlen++] = i;
    }
    const char *index = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    char *returnString = malloc((int)((bitlen / 24) + padding) * 4 + 1);
    for (n = 0; n < ((int)(bitlen / 24) * 4) + ((padding)?4:0) - padding; n++) {
        returnString[n] = index[x[n]];
    }
    free(x);
    for (;padding > 0; padding--) {
        returnString[n++] = '=';
    }
    returnString[n] = '\0';
    return returnString;
}

Answer 1

Bugs

I found a couple of bugs in your program.

1. Your end-of-string handling is off for input strings smaller than 3 bytes. This is because your end-of-string check is too late to stop the first byte from being processed. So for the input "a", your function returns "YA==" instead of "YQ==". See below for a solution for this problem.

2. If the input string contains characters with the high bit set, such as what could happen with UTF-8 input, then your function handles that incorrectly. The culprit is that you use signed chars, and do bit shifting with those signed chars. Imagine that input[n] is 0x80 here:

           i = (uint8_t)(input[n] >> 2);
   

   What you would like to be calculated for i is 0x20. But what you will actually calculate for i is 0xe0. Later you will use 0xe0 as an index into your string and it will overflow the bounds. You can fix this by moving your cast to the right place:

           i = ((uint8_t)input[n] >> 2);
   

One pass instead of two

Right now you are building up an array x of indices and then you use a second pass to convert the x array into the base64 string. It would be quicker and simpler to just build up returnString directly and get rid of the intermediary x array. For example, instead of:

        case 0:
            i = (uint8_t)(input[n] >> 2);
            x[xlen++] = i;
            break;

You could write:

        case 0:
            i = (uint8_t)(input[n] >> 2);
            returnString[xlen++] = index[i];
            break;

Simplifying the loop termination check

Right now, you have a complicated check that looks like this:

    if ((len - n) == ((padding==2)?2:3) && padding > 0) {
        n++;
        break;
    }

As mentioned earlier, this check was also insufficient for strings smaller than 3 bytes. A simpler way of doing this is just to modify len to round down to the nearest multiple of 3 before starting the loop. This does exactly what you wanted and also handles smaller than 3 byte strings:

    len -= (len % 3);
    for (n = 0; n < len; n++) {
        switch (n % 3) {
            ...
        }
        // Complicated check removed.
    }

Getting rid of the switch

Once you have made len a multiple of three (above), you can actually get rid of the switch statement. Instead of iterating over every byte of the input, you can now iterate by three bytes at a time and do all three switch cases one after the other.

Confusing bitmask constants

Your code is correct, but I had a hard time trying to figure out what some of your constants meant. For example:

            o = (uint8_t)((input[n] & 240) >> 4);

would make a lot more sense if you used the hex value like this:

            o = (uint8_t)((input[n] & 0xf0) >> 4);

Now I know you are taking the top 4 bits and shifting them down.

Reusing common code

After the main loop when you handle the two possible padding cases, most of the code for the padding == 2 case is also done in the padding == 1 case. You can combine some of the common code together so that you don't repeat the code twice. This is a matter of preference though, so what you have is fine if you find it more readable.

Other things

• You should check the return value of malloc.
• Your input argument is unmodified so you can make it a const argument.
• You don't really need both i and o although if you like them to be separate variables you can.

---

Putting it all together

Here's what your code would look like after all my suggested changes (and a lot of other tweaks that are stylistic/optional):

char *base64encode(const char *input)
{
    int      len      = strlen(input);
    int      leftover = len % 3;
    char    *ret      = malloc(((len/3) * 4) + ((leftover)?4:0) + 1);
    int      n        = 0;
    int      outlen   = 0;
    uint8_t  i        = 0;
    uint8_t *inp      = (uint8_t *) input;
    const char *index = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
                        "abcdefghijklmnopqrstuvwxyz"
                        "0123456789+/";

    if (ret == NULL)
        return NULL;

    // Convert each 3 bytes of input to 4 bytes of output.
    len -= leftover;
    for (n = 0; n < len; n+=3) {
        i = inp[n] >> 2;
        ret[outlen++] = index[i];

        i  = (inp[n]   & 0x03) << 4;
        i |= (inp[n+1] & 0xf0) >> 4;
        ret[outlen++] = index[i];

        i  = ((inp[n+1] & 0x0f) << 2);
        i |= ((inp[n+2] & 0xc0) >> 6);
        ret[outlen++] = index[i];

        i  = (inp[n+2] & 0x3f);
        ret[outlen++] = index[i];
    }

    // Handle leftover 1 or 2 bytes.
    if (leftover) {
        i = (inp[n] >> 2);
        ret[outlen++] = index[i];

        i = (inp[n]   & 0x03) << 4;
        if (leftover == 2) {
            i |= (inp[n+1] & 0xf0) >> 4;
            ret[outlen++] = index[i];

            i  = ((inp[n+1] & 0x0f) << 2);
        }
        ret[outlen++] = index[i];
        ret[outlen++] = '=';
        if (leftover == 1)
            ret[outlen++] = '=';
    }
    ret[outlen] = '\0';
    return ret;
}