Convert a number from one base to another

Question

I wrote a function to convert an unsigned integer number given by a string from one base to another. Can you please give me any tips to improve it?

#include <assert.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>
#include <limits.h>

#define MAX_BASE() strlen(alphabet)
static char const *alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

static unsigned int ullong2str(char [], unsigned long long, unsigned int);
static unsigned long long str2ullong(char const [], unsigned int);
static char *convertToNewBase(char const [], unsigned int, unsigned int);
static long indexOf(char const [], char);
static unsigned long long power(unsigned int, unsigned int);
static void reverse(char []);

int main(void)
{
    char *decimal = "28697";
    char *binary = convertToNewBase(decimal, 10, 2);

    printf("%s (base 10) = %s (base 2)\n", decimal, binary);
    perror(NULL);

    free(binary);
}

/*
===============
char *convertToNewBase(char [], unsigned int, unsigned int);

The function converts an unsigned integer number from the source base to
destination base. The function allocates a buffer of length large enough
to store the result and returns it. If an error occurs the function
returns NULL.
===============
*/
char *convertToNewBase(char const s[], unsigned int src, unsigned int dest)
{
    assert(s);
    assert(src >= 2 && src <= MAX_BASE());
    assert(dest >= 2 && dest <= MAX_BASE());

    errno = 0;

    unsigned long long const n = str2ullong(s, src);

    if (errno != 0)
        return NULL;

    unsigned int const resultLength = ullong2str(NULL, n, dest);
    char *result = calloc(resultLength + 1, 1);
    if (result == NULL)
        return NULL;

    ullong2str(result, n, dest);

    return result;
}

/*
===============
unsigned long long ullong2str(char [], unsigned long long, unsigned int);

The function converts an unsigned integer value to a null-terminated string
using the specified base and stores the result in the array given by the first
parameter. It assumes that size of the array is large enough to store the
result.

The function returns length of the result string. If the first parameter is
NULL nothing is written, however the return value is still calculated and
returned.
===============
*/
unsigned int ullong2str(char out[], unsigned long long n, unsigned int base)
{
    assert(base >= 2 && base <= MAX_BASE());

    unsigned int i = 0;

    do {
        if (out != NULL)
            out[i] = alphabet[n % base];

        n /= base;
        i++;
    } while (n);

    if (out != NULL) {
        out[i] = '\0';
        reverse(out);
    }

    return i;
}

/*
===============
unsigned long long str2ullong(char const [], base_t base);

If no errors occurs the function returns an unsigned integer value
corresponding to the contents of the input string. If the result is
too large the function returns 0 and sets errno to ERANGE [1]. If the
arguments is invalid the function return 0 and sets errno to EINVAL [2].

1. str2llong("18446744073709551616", 10) in most cases returns 0 and sets
   errno to ERANGE, since 18446744073709551616 is greater than ULLONG_MAX
   (in most cases).

2. str2llong("10191", 2) returns 0 and sets errno to EINVAL, since '9' is
   not allowed in a binary number.
===============
*/
unsigned long long str2ullong(char const s[], unsigned int base)
{
    assert(s != NULL);
    assert(base >= 2 && base <= MAX_BASE());

    unsigned long long r = 0;

    for (unsigned int i = strlen(s), j = 0; i-- > 0; j++) {
        long const index = indexOf(alphabet, s[i]);
        if (index == -1 || index >= (int) base) {
            errno = EINVAL;
            return 0;
        }

        unsigned long long const t = (unsigned long long) index * power(base, j);
        if (r > ULLONG_MAX - t) {
            errno = ERANGE;
            return 0;
        }

        r += t;
    }

    return r;
}

/*
===============
unsigned long long power(unsigned int, unsigned int);

If no errors occurs the function returns aⁿ. If the result is too large the
function returns 0 and sets errno to ERANGE.
===============
*/
unsigned long long power(unsigned int a, unsigned int n)
{
    unsigned long long r = 1;

    while (n--) {
        /* If a * r would overflow… */
        if (a > ULLONG_MAX / r) {
            errno = ERANGE;
            return 0;
        }

        r *= a;
    }

    return r;
}

/*
===============
long indexOf(char const [], char);

The function return index of the first occurence of the character in the
string. If the character is not found returns -1.
===============
*/
long indexOf(char const s[], char c)
{
    assert(s);

    for (size_t i = 0; s[i]; i++)
        if (s[i] == c)
            return (long) i;

    return -1;
}

/*
===============
void reverse(char []);

The function reverses the input string.
===============
*/
void reverse(char s[])
{
    assert(s);
    assert(strlen(s));

    for (unsigned int i = 0, j = strlen(s) - 1; i < j; i++, j--) {
        char const tmp = s[i];
        s[i] = s[j];
        s[j] = tmp;
    }
}

Answer 1

• power is suboptimal. Check out exponentiation by squaring. That said, I would rather avoid power completely. Consider instead

      unsigned long long power_factor = 1;
  
      for (unsigned int i = strlen(s), j = 0; i-- > 0; j++) {
          ....
          unsigned long long const t = index * power_factor;
          power_factor *= base;
      }
  

• indexOf may signal the failure via errno, just like your other functions. That would allow it to return an unsigned value, thus getting rid of the unpleasant (unsigned long long) index cast.

• Dynamic allocation of the resulting string (and the dry run to determine the required length) seem unnecessary. The longest possible result is obtained with base 2, and the resulting length is limited by sizeof(unsigned long long) * CHAR_BITS (realistically 64).

• Consider filling out buffer from right to left, to avoid the reversal.

  EDIT: (sketchy) filling out from right to left:

  int main()
  {
      ....
      char out[sizeof(unsigned long long) * CHAR_BITS + 1];
      char * result = ullong2str(out + sizeof(out), n, dest);
      ....
  }
  
  char * ullong2str(char * end, unsigned long long n, unsigned int base)
  {
      *--end = 0;
      do {
          *--end = alphabet[n % base];
          n /= base;
      }
      return end;
  }
  

Answer 2

When you make your alphabet static there is no need to declare the variable as a pointer and then assigning it an actual pointer to a string in an anonymous array (which is also static).

#define MAX_BASE() strlen(alphabet)
static char const *alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

You can as well declare the alphabet explicitly as an array:

static char const alphabet[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

and then you don't need to scan it with strlen each time you invoke the conversion, because the size of the array is constant and known at compile time:

#define MAX_BASE() (sizeof alphabet - 1)

However, if you need a variable-length alphabet, then you need to keep two variables, one const char* for the alphabet itself, and one int to store its length. Then you can re-assign the alphabet at run-time, but scan it with strlen() just once on each assignment instead of on each use.