Speed optimisation and general tips for base64 encoding/decoding functions in C

Question

So far, the below code appears to work well. It operates pretty fast, but I was wondering if it's possible to make it faster. I'm also looking for general tips on what I might be doing wrong and what I could do better. I have added in comments to explain certain decisions.

b64.h

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
static const char encode_table[] = \
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";
char *ascii_to_base64(char *asciistr)
{
 int asciistrlen = strlen(asciistr);
 int convertedlen = 4 * ceil((double)asciistrlen / 3.0);
 char *asciibuff = (char*)malloc(convertedlen + 1);
 if (asciibuff == NULL)
 goto exception;
 char *converted = malloc(convertedlen + 1);
 if (converted == NULL)
 goto exception;
 /*
 * By zero-ing out, I can just check 0x00 bytes and convert to padding
 * without any extra checks.
 */
 memset(asciibuff, 0x00, asciistrlen + 1);
 memset(converted, 0x00, convertedlen + 1);
 /*
 * Can't realloc the asciistr var so have to create individual buffer
 * with same values.
 */
 strcpy(asciibuff, asciistr);
 /*
 * Allows me to loop through original string input AND be able to check
 * for null bytes and pad accordingly without running into overwriting
 * problems caused by using the "converted" variable for both jobs.
 */
 int i, j; 
 for (i = 0, j = 0; i < convertedlen; i+=4, j+=3) 
 {
 converted[i+3] = encode_table[asciibuff[j+2] != 0x00 ? asciistr[j+2] & 0xbf : 64];
 converted[i+2] = encode_table[asciibuff[j+1] != 0x00 ? 
 ((asciistr[j+1] & 0x0f) << 2) + (asciibuff[j+2] >> 6) : 64];
 converted[i+1] = encode_table[asciibuff[j] != 0x00 ? 
 ((asciistr[j] & 0x03) << 4) + (asciibuff[j+1] >> 4) : 64];
 converted[i] = encode_table[asciibuff[j] != 0x00 ? asciibuff[j] >> 2 : 64];
 }
 free(asciibuff);
 return (converted);
exception:
 return (NULL);
}
/* Derive encoding index */
static unsigned int enci(int base64ascii)
{
 if (base64ascii <= 0x5a && base64ascii >= 0x41)
 return ((unsigned)(base64ascii - 0x41));
 else if (base64ascii <= 0x7a && base64ascii >= 0x61)
 return ((unsigned)(base64ascii - 0x47));
 else if (base64ascii <= 0x39 && base64ascii >= 0x30)
 return ((unsigned)(base64ascii + 0x04));
 else if (base64ascii == 0x2b)
 return ((unsigned)0x3e);
 else if (base64ascii == 0x2f)
 return ((unsigned)0x3f);
 else if (base64ascii == 0x3d)
 return ((unsigned)0x00);
 else
 return ((unsigned)0xff);
}
char *base64_to_ascii(char *base64str)
{
 int base64strlen = strlen(base64str);
 int convertedlen = (base64strlen / 4) * 3;
 /* If an end character is '=', there is one less byte to be generated. */
 if (base64str[base64strlen - 1] == '=')
 convertedlen--;
 if (base64str[base64strlen - 2] == '=')
 convertedlen--;
 char *converted = (char*)malloc(base64strlen + 1);
 if (converted == NULL)
 goto exception;
 memset(converted, 0x00, base64strlen + 1);
 int i, j;
 for (i = 0, j = 0; i < base64strlen; i+=4, j+=3)
 {
 converted[j] = (enci(base64str[i]) << 2) + (enci(base64str[i+1]) >> 4);
 converted[j+1] = ((enci(base64str[i+1]) & 0x0f) << 4) + (enci(base64str[i+2]) >> 2);
 converted[j+2] = ((enci(base64str[i+2]) & 0x03) << 6) + enci(base64str[i+3]);
 }
 /*
 * By making "converted" as long as the base64 encoded string
 * (when it really should be smaller.) I can loop through the base64
 * encoding with no invalid writes or reads and just cut off the excess
 * bytes with a realloc. Don't know if this is the best solution, but it
 * satiates valgrind. After running through many inputs, it appears to
 * always cut the converted string with its null-terminating character.
 * I always get valid c-strings.
 */
 converted = realloc(converted, convertedlen + 1);
 return (converted);
exception:
 return (NULL);
}

• Balog Pal: I thought we have abundance of stock base64 implementations and no one recreates the wheel. Do you have a reason to think those are too slow or that yours needs actual speed optimization? I think the first rule of the latter is still "don't do it' followed by second rule adding yet, and before measurements.
• Maggy May: @BalogPal Oh yes, there are plenty. I'm currently working through some crypto exercises, and it asked to implement base64 encode/decode functions. It's more a learning experience than anything. It's taught me tons about bit manipulation, but just wondering if I made any glaring errors or did something stupidly and if there are any speed optimizations I can make (just for knowledge's sake.)
• Balog Pal: Okay, learning is definitely a good goal, I suggest you state it in the question. Especially as performance op is normally at the far end of learning curve, first you write code that works correctly all the way, then code that is also elegant to the eye and easy to work with, then, IF optimization done by compiler is lacking in requirements you profile and possibly adjust. The code you presented is pretty far from the second goal and for that reason hard to tell if meets the first. As it's a commonly solved problem I suggest to read the alternatives you find,compare,adjust then ask again
• Maggy May: @BalogPal To be fair, my code isn't that bad. I've looked at other implementations and mine fits in with the structure of two of the many that I've seen. But yeah, as William Morris pointed out, I made a lot of rookie mistakes.
• Balog Pal: the point is that you learn :)

Answer 1

I only really looked at ascii_to_base64.

Firstly, you say that the code is "pretty fast", but why is that a consideration? Don't assume that execution speed is necessarily important. Readability and correctness are more so.

On correctness, your code does not handle padding correctly. Given the string "1" your code produces "MQ=K" where it should produce "MQ==" (with "11" it correctly produces "MTE="). This seems to come from using the wrong length in the first memset:

memset(asciibuff, 0x00, asciistrlen + 1);
memset(converted, 0x00, convertedlen + 1);

If you use convertedlen for both, the problem is resolved. Better still, use calloc instead of malloc followed by memset.

Another point is that you use strcpy to copy the input string, but you already know its length; memcpy is more efficient when the length is known.

Note that it is possible to encode the input string without copying it into a bigger buffer - you just have to be careful not to access beyond the end of the input string.

On readability, I have a little trouble with the function. The variable names are too long for my liking (they are local to a short function) and the four expressions in the for-loop are difficult to read. I dislike your use of the ternary operator (?:) in these expressions as it makes them hard to decode. And you mix access to asciibuff and asciistr (all should be to the former).

Your bit-twiddling is okay, with good use of bracketing, although the 0xbf should be 0x3f in the 1st line of the for-loop. I would prefer to see you combining the values with '|' not '+'; both will work but when combining non-numeric values '|' is more logical.

I prefer not to use goto, as you have. And if I were to use it I'd make sure not to leak asciibuff if allocation of converted failed.

Finally, your use of floating point to round-up when computing convertedlen is unnecessary. Instead of your:

int convertedlen = 4 * ceil((double)asciistrlen / 3.0);

I would expect something like:

int convertedlen = 4 * ((asciistrlen + 2) / 3);

BTW, your code has all sorts of singed/unsigned and loss of precision conversion warnings (gcc option -Wconversion).

---

EDIT : Variable naming is difficult. It is also open to argument, so I can only give you my preferences which are based on the widely found advice that the length of names should related to their scope. So variables in a small function can be small; those in a large function can be longer (but large functions should generally be avoided anyway). Global variables need to be larger still. But these are guidlelines, not fixed rules. If t1 has global significance to your application then using t1 as a global might be sensible; you wouldn't after all call pi anything but pi.

In the case of a smallish function like ascii_to_base64, I would call the input string s - the function name says it is an ASCII string so no need to repeat that. For the copy of s, which is used everywhere, I'd use ascii. The converted value I'd call base64. For the lengths: the length of s is used just once and needs no variable; the length of the conversion I'd call just len or maybe, len64. And the base-64 coding table, which in your example is used only in this function and so should be local to the function, not global, I'd call coding.

Really small names, such as your loop variables i and j are also okay (in fact they are preferable for small loops), but when mixed together can be difficult to tell apart. I have this problem with your for-loop, as it is not easy to tell at a glance that i is used only in the left-hand side of each line. You might use i and k, which are more easily distinguished. Or you could refactor the loop to avoid having two indices.

const char *a = ascii;
for (int i = 0; i < len; i += 4, a += 3)
{
 base64[i+3] = coding[a[2] != 0 ? a[2] & 63 : 64];
 base64[i+2] = coding[a[1] != 0 ? ((a[1] & 15) << 2) | (a[2] >> 6) : 64];
 base64[i+1] = coding[*a != 0 ? ((*a & 3) << 4) | (a[1] >> 4) : 64];
 base64[i] = coding[*a != 0 ? *a >> 2 : 64];
}

(but note that I wouldn`t have coded the loop that way in the first place).

Note also that 0 is just as good as 0x00 and 3 is as good as 0x03; the shorter versions are easier to read.

• Maggy May: Which compiler are you using? I've been using gcc with -Wall flag and got no precision loss warnings.
• Maggy May: Also: how should I name my variables? I'm trying not to fall into the bad habit of sentences for variable names but isn't explicitness the best policy?
• William Morris: -Wall does not in fact give 'all' warnings. -Wconversion will give you conversion warnings. The clang compiler with -Wconversion will give some more. These warnings can be quite annoying and are mostly harmless but I think it is worth knowing about them.
• William Morris: I have added some thoughts on variable naming to the answer

Answer 2

Just a couple of comments:

1. Always use { } for single line ifs (and for, while etc), even if it's not required. It'll save a lot of time one day...
2. Rather than malloc and then memset(...0...), you might consider using calloc instead to do it automatically.
3. if (converted == NULL) goto exception; leaves asciibuff still allocated, and hence a memory leak. Either free it in the if block, or use another goto label and free it there.

4. I would avoid for statements with multiple controlling variables like

   for (i = 0, j = 0; i < convertedlen; i+=4, j+=3) 
   {
    // stuff
   }
   

   and reword it to the following to make it easier to read (imo) and maybe even split the loop contents into another (deci) function:

   j = 0;
   for (i = 0; i < convertedlen; i += 4)
   {
    deci( &asciibuff[j], &asciistr[j], &converted[i] );
    j += 3;
   }
   

5. Use (unsigned int) instead of (unsigned) to be more explicit.
6. There's no real need to do the final converted = realloc(converted, convertedlen + 1);; strlen, strcpy etc will work fine without it.