Implementation of itoa

Question

int get_digits (int num)
{
   if(num < 10)
      return 1;

   if(num < 100)
      return 2;

    if(num < 1000)
      return 3;

    if(num < 10000)
      return 4;

    if(num < 100000)
      return 5;

    if(num < 1000000)
      return 6;

    if(num < 10000000)
      return 7;

    if(num < 100000000)
      return 8;

    if(num < 1000000000)
      return 9;

    return 10; /* num > 1000000000 */
}

char *itoa (int n)
{
    static char temp[10]; // MN that can be replaced by some def?
    int nDigits = 0;
    int i = 0;
 
    if(n == 0)
    {
        temp[0] = '0';
        temp[1] = '\0';
 
       return temp; // or just return "0"; ?
    }
 
    nDigits = get_digits(n); // fast function to count digits..
 
    temp[nDigits] = '\0'; // ..needed just here
 

   for(i = n; i >= 1; i /= 10) // whole method stinks
    {
        temp[--nDigits] = ((i % 10) + '0'); // modulo is quite slow
    }
 
    return temp;
}

This is my implementation of the infamous function itoa(), which isn't available everywhere and more importantly not available in my environment. Generally, the implementation of this function is ought to be different anyway. Performance and memory optimization is important. This function converts an integer to a string. The function owns the reference to the returned string, which is statically allocated and the caller is responsible to make a copy of the returned string if he plans on changing it or preserving it across subsequent calls.

Answer 1

Interface

    static char temp[10];
    ⋮
    return temp;

Returning a pointer to a static member can be a problem. If clients aren't specifically warned, then they may inadvertently overwrite the storage before using it (consider printf("%s%s", itoa(1), itoa(2)) as a minimal example).

In any case, such functions are not safely usable from multiple threads, and writing single-threaded code is an onerous limitation in the modern world.

One alternative is to allocate memory, but that obviously carries a huge performance penalty.

The usual approach for such functions is for the caller to pass appropriate storage. The traditional interface is void itoa(int n, char *buf), but I would strongly recommend updating to imitate snprintf() with something like size_t itoa(int n, char *buf, size_t bufsize) - where the return value represents the number of characters that would be written, even if greater than bufsize.

---

The getdigits() function shouldn't need external linkage, I think, so declare it static.

It returns 1 for all negative numbers. The way to fix that is to convert all positive inputs to negative ones (note that the other way around does not work, since -INT_MIN isn't necessarily valid, but -INT_MAX always is).

int get_digits(int num)
{
    if (num > 0) {
        /* strip the leading '-' */
        return get_digits(-num) - 1;
    }

    if(num > -10)
       return 2;
    if(num > -100)
       return 3;
    ⋮

This function makes assumptions about INT_MAX which are not safe: If INT_MAX is less than 1000000000, then we have an undefined conversion, and if it's greater than 10000000000, we will return a value that's too small.

Since INT_MAX is guaranteed to be at least 10000, we can make a portable version:

int get_digits(int num)
{
    if (num > 0) {
        /* strip the leading '-' */
        return get_digits(-num) - 1;
    }

    int digit_count = 1;        /* leading '-' */
    while (num <= -10000) {
        digit_count += 4;
        num /= 10000;
    }

    if (num <= -100) {
        digit_count += 2;
        num /= 100;
    }

    if (num <= -10) {
        digit_count += 1;
    }

    return digit_count;
}

However, counting the digits in advance shouldn't be necessary - we can work backwards, then reverse the result in-place for less cost:

#include <stdlib.h>

size_t itoa(int n, char *buf, size_t bufsize)
{
    if (n == 0) {
        if (bufsize > 1) {
            buf[0] = '0';
            buf[1] = '\0';
        }
        return 1;
    }

    size_t i = 0;
    size_t digits = 0;
    if (n < 0) {
        while (n) {
            int r = n % 10;
            n /= 10;
            if (r > 0) {
                /* non-standard compiler */
                r -= 10;
                ++n;
            }
            if (buf && i < bufsize - 1) {
                buf[i++] = (char)('0' - r);
            }
            ++digits;
        }
        if (buf && i < bufsize - 1) {
            buf[i++] = '-';
        }
        ++digits;
    } else {
        /* n > 0 */
        while (n) {
            int r = n % 10;
            n = n / 10;
            if (buf && i < bufsize - 1) {
                buf[i++] = (char)('0' + r);
            }
            ++digits;
        }
    }
    if (buf && i < bufsize - 1) {
        buf[i--] = '\0';
        /* reverse the output in-place */
        for (size_t j = 0;  j < i;  --i, ++j) {
            char c = buf[i];
            buf[i] = buf[j];
            buf[j] = c;
        }
    }

    return digits;
}

#include <stdio.h>
#include <string.h>
int test_itoa(const char *file, int line,
              int n, const char *expected)
{
    char buf[20];
    int result = 0;
    size_t actual = itoa(n, 0, 0);
    if (actual != strlen(expected)) {
        fprintf(stderr, "%s:%d: error: itoa(%d) returned %zu instead of %zu\n",
                file, line,
                n, actual, strlen(expected));
        result = 1;
    }
    actual = itoa(n, buf, sizeof buf);
    if (actual != strlen(expected)) {
        fprintf(stderr, "%s:%d: error: itoa(%d) returned %zu instead of %zu\n",
                file, line,
                n, actual, strlen(expected));
        result = 1;
    }
    if (strcmp(buf, expected)) {
        fprintf(stderr, "%s:%d: error: itoa(%d) produced %s instead of %s\n",
                file, line,
                n, buf, expected);
        result = 1;
    }
    return result;
}

#define TEST_ITOA(n, s) test_itoa(__FILE__, __LINE__, n, s)

int main(void)
{
    return TEST_ITOA(0, "0")
        |  TEST_ITOA(1, "1")
        |  TEST_ITOA(10, "10")
        |  TEST_ITOA(12345, "12345")
        |  TEST_ITOA(-1, "-1")
        |  TEST_ITOA(-10, "-10")
        |  TEST_ITOA(-12345, "-12345")
        ;
}

Answer 2

The code almost works.

To make it work in all cases, test the program with Valgrind, which detects undefined behavior because of invalid memory access. This will prove that the buffer needs to be 11 bytes long, not only 10.

What about platforms where int has 64 bits instead of just 32? For these you need a larger buffer. Until then, you should use a compile-time assertion (static_assert) to ensure this implicit assumption.

What about negative numbers? -6 is a valid integer as well, and it should be converted appropriately.

If this function is the bottleneck of your whole program because it is too slow, have a look at how the Go programming language converts integers to strings. It's in the strconv package and uses lots of nice tricks to cut down the number of integer divisions, since that's the most expensive machine instruction in your code.

You can get rid of the get_digits function if you have the end of the string at a fixed address. Start with:

char *p = buf + sizeof buf - 1;
*p = '\0';

and then continue to fill the buffer from right to left by doing *(--p) = '0' + digit. At the end just return p, which will point to the first digit.

The return type should be const char * instead of char * since the caller is not supposed to do anything to the buffer.