Convert integer to decimal string

Question

I have a need to do some conversions in a loop to display the results using C++98 on Linux, which doesn't have any itoa() to complement atoi(). I opted for this instead of snprintf(). This is for an embedded device and the conversions will be done in a few loops, so speed is important.

It's based on some code I found on GitHub. I modified it to write to a user-supplied buffer, so that it's reentrant.

Please let me know if anyone has a better method for small numeric conversions to ascii using base-10 only, or any recommended changes. Thanks.

/*
  Modified from:
  https://gist.github.com/madex/c5cd5c6a23965a845d6e

  This only works for up to 9 digits and only converts to base 10 ascii,
  but no division is used and this method is very fast.
*/

void itoaBase10(int32_t num, char *string, int lengthOfString)
{
    if (!string || num > 9999999999)
    return;
    memset(string, 0, lengthOfString);
    static uint32_t subtractors[10] =
     { 1000000000, 100000000, 10000000, 1000000, 100000, 10000,
       1000, 100, 10, 1 };
    char n, *str = string, sign = num < 0 ? '-' : ' ';
    uint32_t *sub = subtractors;
    uint32_t u = num < 0 ? (uint32_t)-num : (uint32_t)num;
    uint8_t  i = 10;
    while (i > 1 && u < *sub)
    {
        i--;
        sub++;
    }
    str++;
    *(str - 1) = sign;
    while (i--)
    {
        n = '0';
        while (u >= *sub)
        {
            u -= *sub;
            n++;
        }
        *str++ = n;
        sub++;
    }
}

Answer 1

@vnp good answer covered well most of the problems.

Weak buffer management

A common issue with itoa() like functions is the character buffer management. I recommend to convert to a known sufficient sized buffer and then copy as able.

OP's itoaBase10(0, 1) resulted in a non-terminated character array with no error indication. It also overwrote array bounds - UB.

Name is inconsistent with type.

Suggest

int32toaBase10(int32_t num
// or 
itoaBase10(int num

Suggested alternative

#include  <limits.h>
#include  <stdint.h>
#include  <stdio.h>
#include  <string.h>
// Worst case size needed: sign + about bit_width*log10(2) + 1 + \0
#define INTEGER_STR_SIZE(type) (sizeof(type)*CHAR_BIT/3 + 3)

char *int32toaBase10(int32_t num, char *string, size_t SizeOfString) {
  uint32_t u32;
  if (num < 0) {
    u32 = -(uint32_t) num;  // Convert before negating to avoid UB
  } else {
    u32 = (uint32_t) num;
  }

  char buf[INTEGER_STR_SIZE(int32_t)];
  char *s = &buf[sizeof buf - 1]; // start at the end of the buffer.
  *s = '\0';

  do {  // Use a do loop to handle `num == 0` --> "0" and not ""
    *(--s) = (char) (u32 % 10 + '0');
    u32 /= 10;
  } while (u32 > 0);

  if (num < 0) {
    *(--s) = '-';
  }

  size_t size_used = (size_t) (&buf[sizeof buf] - s);
  if (size_used > SizeOfString) {
    // TBD Customize how to handle lack of space.
    fflush(stdout);
    fprintf(stderr, "Insufficient memory %u < %u\n",
        (unsigned) SizeOfString, (unsigned) size_used);
    return NULL;
  }

  return memcpy(string, s, size_used);
}

Test code

void int32toaBase10_test(int32_t num, size_t SizeOfString) {
  char buf[100];
  memset(buf, '*', sizeof buf);
  char *s = int32toaBase10(num, buf + 1, SizeOfString);
  printf("num:%ld size:%u, <%s>\n", (long) num, (unsigned) SizeOfString,
      s ? s : "NULL");
}

int main() {
  int32toaBase10_test(0, 12);
  int32toaBase10_test(1, 12);
  int32toaBase10_test(42, 12);
  int32toaBase10_test(INT_MAX, 12);
  int32toaBase10_test(INT_MIN, 12);
  int32toaBase10_test(INT_MIN, 11);
}

Output

num:0 size:12, <0>
num:1 size:12, <1>
num:42 size:12, <42>
num:2147483647 size:12, <2147483647>
num:-2147483648 size:12, <-2147483648>
Insufficient memory 11 < 12
num:-2147483648 size:11, <NULL>

---

INTEGER_STR_SIZE(type) details

Space needed to convert an integer (signed or unsigned) to decimal characters:

Given the size of the integer is N bits sizeof(type)*CHAR_BIT.
The number of binary value bits is N or less.
The number of sign bits is 1 or less.

N binary bits convert to ceiling(N*log10(2)) digits which is ≤ N/3 + 1.

//                            sign  v---- digits ---------------v  \0
#define INTEGER_STR_SIZE(type) (1 + (sizeof(type)*CHAR_BIT/3 + 1) + 1)

For those who want to use the minimum space, code could use a tighter approximation of log10(2) and adjust per signed/unsigned.

#define SINTEGER_STR_SIZE(type) (1 + ((sizeof(type)*CHAR_BIT-1)*28/93 + 1) + 1)

#define UINTEGER_STR_SIZE(type) (0 + ((sizeof(type)*CHAR_BIT-0)*28/93 + 1) + 1)

The buffer size needed may be smaller yet if the type has rare padding bits.

Answer 2

• Since the function may bail out without computing the result, it must signal the caller that something got wrong. Consider returning an error code.

• Since you are dealing with negative numbers, testing for num > 9999999999 is not sufficient.

• Along the same line, -num may overflow.

• The lines

      str++;
      *(str - 1) = sign;
  

  are a long way to say

      *str++ = sign;
  

  That said, you seem to force a sign (a whitespace) into the output even for positives. Strictly speaking, it is not an itoa compatible behavior.

• memset seems superfluous. *str = 0; after the conversion is done suffices.

• I don't think that the benefits of a subtraction loop vs division/modulo are measurable. Did you profile?

• The only reason to prefer itoa to sprintf is that the former supports arbitrary conversion bases. It you only need decimal conversion, I strongly recommend to stick with the latter.

Answer 3

This kind of function (a pure function, where the results depend only on the inputs) lends itself extremely well to automated testing. So let's write some unit tests! I'll use GoogleTest, as that's what I know best, but almost any unit testing framework will support you here.

Let's start with our first test - we expect it to fail when passed a null pointer for the output:

#include <stdint.h>

extern "C" {
    void itoaBase10(int32_t num, char *string, int lengthOfString);
}


#include <gtest/gtest.h>

TEST(itoa, null_string)
{
    EXPECT_FALSE(itoaBase10(0, nullptr, 9));
}

Note that the tests are written in C++, though the code under test is C. That's fine - we just need to compile each part with the correct compiler and declare the function with extern "C" so they can be linked to make the final test program.

Here's our first problem - the function doesn't tell us whether or not we succeeded. That's easy to fix:

#include <stdbool.h>

bool itoaBase10(int32_t num, char *string, int lengthOfString)
////
{
    if (!string || num > 9999999999) { return false; }
                                              /////
    // ...
    return true;
    ////////////
}

That one passes.

---

Next, what about a zero-length buffer?

TEST(itoa, zero_space)
{
    char str[1];
    EXPECT_FALSE(itoaBase10(0, str, 0));
}

That one fails, so we need to add an extra check. While we're doing that, we can remove the test that the compiler warns us will always be true:

/* output is at least one digit and a terminating NUL */
if (!string || lengthOfString <= 1) { return false; }

---

With that working, time to add a new test. Let's make sure we succeed in printing 9 to a 2-char buffer, but fail when printing 10.

TEST(itoa, one_digit)
{
    char str[2];
    EXPECT_TRUE(itoaBase10(9, str, 2));
    EXPECT_STREQ(str, "9");
}

TEST(itoa, short_string)
{
    char str[2];
    EXPECT_FALSE(itoaBase10(10, str, 2));
}

This reveals some bugs. Firstly one_digit fails because we print a leading space for positive values, which is unlike %d conversion - apparently, this is supposed to be more like % d. Well, we can deal with that - we need to make the minimum buffer size be three characters, rather than two, and change our expectation:

/* output is at least sign char, one digit and a terminating NUL */
if (!string || lengthOfString <= 2) { return false; }

TEST(itoa, zero_space)
{
    char str[1];
    EXPECT_FALSE(itoaBase10(0, str, 0));
}

TEST(itoa, insufficient_space)
{
    char str[1];
    EXPECT_FALSE(itoaBase10(0, str, 2));
}

TEST(itoa, one_digit)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(9, str, 3));
    EXPECT_STREQ(str, " 9");
}

TEST(itoa, short_string)
{
    char str[3];
    EXPECT_FALSE(itoaBase10(10, str, 3));
}

Last bug first, short_string fails because we're not actually keeping count as we output. That reveals that we're not actually tracking where we're writing to. So fix that.

if (!string || lengthOfString <= 2) { return false; }
char const *const last_pos = string + lengthOfString - 1;
// ...
while (i--)  {
    if (str >= last_pos) { return false; }

---

Now we have five tests that succeed. We can start working on negative numbers. Let's make sure zero formats correctly, first:

TEST(itoa, zero)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(0, str, 3));
    EXPECT_STREQ(str, " 0");
}

Mmm, that one passed first time. How do we know it really works? Temporarily change " 0" to something else - say, "-0", and it fails. Good; the test works. Change it back and continue. (I won't show this procedure of testing the test on future passing tests, but be encouraged to do it anyway).

---

Our first tests of a negative number:

TEST(itoa, negative_one_digit)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(-9, str, 3));
    EXPECT_STREQ(str, "-9");
}

TEST(itoa, negative_short_string)
{
    char str[3];
    EXPECT_FALSE(itoaBase10(-10, str, 3));
}

Well, they were easy - no fixes required.

---

What about the absolute limits of int32_t? We could hard-code the string outputs, but I favour using snprintf() here to save us the hard work:

#include <inttypes.h>

TEST(itoa, max_int32)
{
    char expected[12];
    char str[12];
    snprintf(expected, sizeof expected, "% " PRId32, INT32_MAX);
    EXPECT_TRUE(itoaBase10(INT32_MAX, str, sizeof str));
    EXPECT_STREQ(str, expected);
}

TEST(itoa, min_int32)
{
    char expected[12];
    char str[12];
    snprintf(expected, sizeof expected, "% " PRId32, INT32_MIN);
    EXPECT_TRUE(itoaBase10(INT32_MIN, str, sizeof str));
    EXPECT_STREQ(str, expected);
}

We could reduce the duplication in these last two tests by creating a data-driven test. That would certainly be useful if we want to add more of these specific values, but I'll leave that for now.

---

Now that we have some confidence in the functionality, we can start on refactoring the function.

One thing that's immediately strange is the use of int for the maximum length, when normal C code will use size_t. That's easily fixed, and we can test it instantly.

Next, do we really need that memset()? It will touch memory we're about to write anyway, and we only need a single NUL at the end of our string, so let's ditch that, and write our NUL at the end:

*str = '\0';
return true;

That change may make a very small performance improvement.

sign variable is only used once; let's just inline that use with a comment:

/* write sign character */
*str++ = num < 0 ? '-' : ' ';

n can have a much smaller scope, so let's move it into the i-- loop. We don't use string after we've copied it to str, so let's combine them. These three changes should make no difference to the generated (optimised) code, but simplify the logic for future maintainers (perhaps future-you in 6 months?).

Instead of using index i to count entries in subtractors, just add a terminating zero entry to the list:

bool itoaBase10(int32_t num, char *str, size_t lengthOfString)
{
    /* output is at least sign char, one digit and a terminating NUL */
    if (!str || lengthOfString <= 2) { return false; }
    char const *const last_pos = str + lengthOfString - 1;

    static const uint32_t subtractors[] =
        { 1000000000,
          100000000,
          10000000,
          1000000,
          100000,
          10000,
          1000,
          100,
          10,
          1,
          0
        };

    /* write sign character */
    *str++ = num < 0 ? '-' : ' ';

    /* skip leading zeros */
    uint32_t const *sub = subtractors;
    uint32_t u = num < 0 ? -(uint32_t)num : (uint32_t)num;
    while (u < *sub) {
        sub++;
    }

    /* write the digits */
    while (*sub)  {
        if (str >= last_pos) { return false; }
        char n = '0';
        while (u >= *sub) {
            u -= *sub;
            n++;
        }
        *str++ = n;
        sub++;
    }

    *str = '\0';
    return true;
}

That almost works, but it broke one of our tests:

[ RUN      ] itoa.zero
204891-test.cpp:47: Failure
      Expected: str
      Which is: " "
To be equal to: " 0"
[  FAILED  ] itoa.zero (32 ms)

We can fix that. The simplest, and probably best way is to special-case test num==0 to just strcpy(str, " 0") (after the test that str and lengthOfString are valid). Alternatively, we could skip all but the last zero by changing the loop condition from (u < *sub) to (u < *sub && *sub > 1).

---

Modified code

/*
  Modified from:
  https://gist.github.com/madex/c5cd5c6a23965a845d6e

  This only works for up to 9 digits and only for base 10 numbers,
  but no division is used and this method is very fast.
*/

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

bool itoaBase10(int32_t num, char *str, size_t length)
{
    /* output is at least sign char, one digit and a terminating NUL */
    if (!str || length <= 2) {
        return false;
    }

    if (!num) {
        /* special-case zero (which would be skipped as a leading 0) */
        strcpy(str, " 0");
        return true;
    }

    static const uint32_t subtractands[] =  {
        1000000000,
        100000000,
        10000000,
        1000000,
        100000,
        10000,
        1000,
        100,
        10,
        1,
        0
    };

    /* last possible position for NUL */
    char const *const last_pos = str + length - 1;
    /* work with a positive version of num */
    uint32_t u = num < 0 ? -(uint32_t)num : (uint32_t)num;

    /* write sign character */
    *str++ = num < 0 ? '-' : ' ';

    /* skip leading zeros */
    uint32_t const *sub = subtractands;
    while (u < *sub) {
        ++sub;
    }

    /* write the digits */
    while (*sub)  {
        if (str >= last_pos) {
            /* no space for NUL */
            return false;
        }
        char n = '0';
        while (u >= *sub) { u -= *sub; ++n; }
        *str++ = n;
        ++sub;
    }

    *str = '\0';
    return true;
}

Unit tests

#include <inttypes.h>
#include <stdint.h>
#include <stdlib.h>

extern "C" {
    bool itoaBase10(int32_t num, char *string, size_t lengthOfString);
}


#include <gtest/gtest.h>

TEST(itoa, null_string)
{
    EXPECT_FALSE(itoaBase10(0, nullptr, 9));
}

TEST(itoa, zero_space)
{
    char str[1];
    EXPECT_FALSE(itoaBase10(0, str, 0));
}

TEST(itoa, insufficient_space)
{
    char str[1];
    EXPECT_FALSE(itoaBase10(0, str, 2));
}

TEST(itoa, one_digit)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(9, str, 3));
    EXPECT_STREQ(str, " 9");
}

TEST(itoa, short_string)
{
    char str[3];
    EXPECT_FALSE(itoaBase10(10, str, 3));
}


TEST(itoa, zero)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(0, str, 3));
    EXPECT_STREQ(str, " 0");
}


TEST(itoa, negative_one_digit)
{
    char str[3];
    EXPECT_TRUE(itoaBase10(-9, str, 3));
    EXPECT_STREQ(str, "-9");
}

TEST(itoa, negative_short_string)
{
    char str[3];
    EXPECT_FALSE(itoaBase10(-10, str, 3));
}



TEST(itoa, max_int32)
{
    char expected[12];
    char str[12];
    snprintf(expected, sizeof expected, "% " PRId32, INT32_MAX);
    EXPECT_TRUE(itoaBase10(INT32_MAX, str, sizeof str));
    EXPECT_STREQ(str, expected);
}

TEST(itoa, min_int32)
{
    char expected[12];
    char str[12];
    snprintf(expected, sizeof expected, "% " PRId32, INT32_MIN);
    EXPECT_TRUE(itoaBase10(INT32_MIN, str, sizeof str));
    EXPECT_STREQ(str, expected);
}