Convert a hex string to base64

Question

I wrote a program that converts a hex-encoded string to base64. It's my solution to the first of the Cryptopals challenges.

My main concerns are:

• Portability. I don't want to rely on implementation-specific or non-standard behavior.
• Reusability. I wrote a function to get bytes from hex and one to get base64 from bytes (rather than going straight from hex to base64), because I will probably need them for other challenges.
• Readability.
• Testability.

/* Convert hex to base64.
 *
 * This program takes as an argument a hex string, which it converts to base64
 * and then prints to stdout.
 */


#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>


/* A bytestring represents a string of (8-bit) bytes.
 *
 * Even if CHAR_BIT > 8, byte values are always in the range [0, 255].
 */
typedef struct {
    size_t size;
    unsigned char *data;
} bytestring;


static const char *const HEX_DIGITS = "0123456789abcdef";
static const char *const BASE64_DIGITS =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
static const char BASE64_PADDING = '=';


/* Print a usage message to stderr.
 */
static void print_usage(int argc, const char *argv[])
{
    const char *name = "s1e1.exe";
    if (argc >= 1) {
        name = argv[0];
    }
    fprintf(stderr, "Usage: %s hex\n", name);
}


/* Return the value represented by a hexadecimal digit.
 *
 * `digit` must be a valid hexadecimal digit.
 */
static unsigned char hex_value(char digit)
{
    return (unsigned char) (strchr(HEX_DIGITS, digit) - HEX_DIGITS);
}


/* Convert a hex string to a bytestring and return true on success.
 *
 * On success, the bytestring data must be freed by the caller.
 */
static bool bytes_from_hex(const char *hex, bytestring *bytes_ptr)
{
    size_t num_digits = 0;
    for (const char *ptr = hex; *ptr != '\0'; ptr++) {
        if (strchr(HEX_DIGITS, *ptr) == NULL) {
            fprintf(stderr, "Invalid hex digit: %c\n", *ptr);
            return false;
        }
        num_digits++;
    }

    if (num_digits % 2 == 1) {
        fprintf(stderr, "Error: odd number of hex digits\n");
        return false;
    }

    bytes_ptr->size = num_digits / 2;
    if ((bytes_ptr->data = malloc(bytes_ptr->size)) == NULL) {
        fprintf(stderr, "Error: couldn't allocate memory for bytes\n");
        return false;
    }

    for (size_t i = 0; i < bytes_ptr->size; i++) {
        unsigned char value_a = hex_value(hex[2*i + 0]);
        unsigned char value_b = hex_value(hex[2*i + 1]);
        bytes_ptr->data[i] = (unsigned char) (value_a << 4 | value_b);
    }

    return true;
}


/* Convert a bytestring to base64 and return true on success.
 *
 * On success, the base64 string must be freed by the caller.
 */
static bool base64_from_bytes(bytestring bytes, char **base64_ptr)
{
    size_t num_triplets = (bytes.size + 2) / 3;
    size_t buffer_size = 4 * num_triplets + 1;
    if ((*base64_ptr = malloc(buffer_size)) == NULL) {
        fprintf(stderr, "Error: couldn't allocate memory for base64\n");
        return false;
    }

    for (size_t i = 0; i < num_triplets; i++) {
        uint_fast32_t byte_a = bytes.data[3*i + 0];
        uint_fast32_t byte_b = 3*i + 1 < bytes.size ? bytes.data[3*i + 1] : 0;
        uint_fast32_t byte_c = 3*i + 2 < bytes.size ? bytes.data[3*i + 2] : 0;
        uint_fast32_t value = byte_a << 16 | byte_b << 8 | byte_c;

        unsigned char mask = (1 << 6) - 1;
        (*base64_ptr)[4*i + 0] = BASE64_DIGITS[value >> 18 & mask];
        (*base64_ptr)[4*i + 1] = BASE64_DIGITS[value >> 12 & mask];
        (*base64_ptr)[4*i + 2] = BASE64_DIGITS[value >> 6 & mask];
        (*base64_ptr)[4*i + 3] = BASE64_DIGITS[value >> 0 & mask];
        if (3*i + 1 >= bytes.size) {
            (*base64_ptr)[4*i + 2] = BASE64_PADDING;
        }
        if (3*i + 2 >= bytes.size) {
            (*base64_ptr)[4*i + 3] = BASE64_PADDING;
        }
    }
    (*base64_ptr)[buffer_size - 1] = '\0';

    return true;
}


/* Convert a hex string to base64 and return true on success.
 *
 * On success, the base64 string must be freed by the caller.
 */
static bool base64_from_hex(const char *hex, char **base64_ptr)
{
    bytestring bytes;
    if (!bytes_from_hex(hex, &bytes)) {
        return false;
    }

    bool success = base64_from_bytes(bytes, base64_ptr);

    free(bytes.data);
    return success;
}


/* Print the base64 representation of a hex string and return true on success.
 */
static bool print_base64(const char *hex)
{
    char *base64;
    if (!base64_from_hex(hex, &base64)) {
        return false;
    }

    bool success = puts(base64) != EOF;

    free(base64);
    return success;
}


/* Print the base64 representation of the hex string given as an argument.
 */
int main(int argc, const char *argv[])
{
    if (argc != 2) {
        print_usage(argc, argv);
        return EXIT_FAILURE;
    }

    if (!print_base64(argv[1])) {
        return EXIT_FAILURE;
    }

    return EXIT_SUCCESS;
}

Answer 1

Overall the code is fairly easy to read and I don't spot any portability issues.

Program design

• The module handling the allocation should also clean up after itself. If transferring this to a proper multi-file program, you would have a lib with a header/code pair like base64.h + base64.c. If there exists a function in base64.c that calls malloc, there should also be a function in that file responsible for clean-up. Returning pointers to dynamic memory to a caller outside the code is bad practice - it breaks private encapsulation and leads to memory leaks. Best practice by far is to let the handler deal with the allocation, if possible.

• Similarly, you should not expose internals of such a dynamic-allocated struct to the caller. The struct could be made opaque and all access to it could be restricted to setters/getters.

• Mixing error handling with algorithms isn't a good idea. Rather than printing errors inside the functions dealing with the algorithms, you should return an error code. Meaning you'll have to swap the bool return type for an enum or struct.

Performance

• Your struct member data should be replaced with a "flexible array member". This allows you to allocate the whole struct in one chunk of memory, which gives better cache performance and quicker look-ups. (Also gives less heap fragmentation)

• Your HEX_DIGITS lookups with strchr could probably be optimized by calling isxdigit instead. Although that function isn't case-sensitive. Otherwise you can roll it out yourself by first checking if a character is in range of '0'-'9' or 'A'-'F' then use table lookups from there. It would be faster overall.

• As a rule of thumb, never pass structs by value, always pass them by reference.

• It might be possible to branch-optimize the code quite a bit, but I didn't look at that since you mention portability, and branch optimizations only makes sense for architectures with branch prediction and instruction cache.

Best practice and style

• Avoid assignment inside control statements. It is hard to read and might cause unintentional side-effects. Lines such as if ((*base64_ptr = malloc(buffer_size)) == NULL) should be split in two, one for the malloc call and one for the check against NULL.

• To avoid the more complex syntax involved with a char**, you should use a local char*. For example char* p64 = malloc(...); ... p64[n] = ...; ... *bae64_ptr = p64; return true; }//end of function

• Replace "magic number" integer constants with named constants when possible. It isn't obvious what all those digits are for and you don't use comments explaining where you got them from.

• HEX_DIGITS and BASE64_DIGITS should be arrays. Makes the code easier to read, enables the use of sizeof and requires ever so slightly less memory. Example:

  static const char HEX_DIGITS[] = "0123456789abcdef";
  

Safety/security

• In a real application you would need to sanitize input more when dealing with command line arguments. You can't really know the length of the string passed. The simplest form of doing this would be to look for a null terminator in argv[1] until you reach to a certain max size, then have the program close with an error message if the input is too large. strchr(HEX_DIGITS, digit) - HEX_DIGITS is for example not guaranteed to be 255 or less, which is a vulnerability.

  Also, strchr will return NULL if the digit isn't found, in which case your program will crash.

• You should make a habit out of appending a u suffic to all integer constants involed in bitwise artimetic. Constants like 1 is of type signed int and therefore potentially dangerous in various ways.