3
\$\begingroup\$

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++;
    }
}
\$\endgroup\$
3
  • 1
    \$\begingroup\$ Why not snprintf()? If it's speed, then are you sure that decimal formatting is actually the bottleneck? (In other words, have you profiled your code, and determined that this conversion is taking a significant portion of the time, and you can't reduce the number of times it's used?). Also, you mention C++98, but tagged it as c; does that mean that this is a C function intended to be linked to a C++ program? Why not write it in C++? \$\endgroup\$ Oct 4, 2018 at 8:52
  • \$\begingroup\$ Sorry for the barrage of questions - but it may be helpful to edit the question to explain why you're writing this code instead of using library functions. Note that if you're compiling this as C++, you'll need to qualify std::int32_t and the other fixed-width types (assuming you include <cstdint> rather than <stdint.h>). \$\endgroup\$ Oct 4, 2018 at 13:49
  • 1
    \$\begingroup\$ Why did you add the C++ tag in Rev 3? None of this code is idiomatic C++; it's just going to be considered poor code by C++ standards. \$\endgroup\$ Oct 4, 2018 at 17:41

3 Answers 3

3
\$\begingroup\$

@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.

\$\endgroup\$
6
  • 1
    \$\begingroup\$ Very nice method and clever macro use. Thanks much. \$\endgroup\$
    – netcat
    Oct 4, 2018 at 13:34
  • \$\begingroup\$ @netcat the 28/93 uses the minimum space for intN_t, uintN_t for N up to 92. Past that, it sometimes uses 1 more than needed. It is never not enough. \$\endgroup\$ Oct 4, 2018 at 13:46
  • \$\begingroup\$ @chux The return should probably be: return (char*)memcpy(string, s, size_used); \$\endgroup\$
    – netcat
    Oct 4, 2018 at 14:26
  • \$\begingroup\$ @netcat 1) Having too much fun: 87/289 is good up to N = 288. 2) The (char *) is not needed for the same reason as malloc() does not need a cast. Its OK to use, just not needed in C. \$\endgroup\$ Oct 4, 2018 at 14:37
  • 1
    \$\begingroup\$ @netcat Since you commented here about speed, for the future, if speed is important, say that clearly in the post's goals and add some test code to assess the speed. I did not focus on speed as an important concern when the goal was "a better method". Perhaps put together all the good info from answers here and with speed assessment code, in a few days make a new post requesting speed performance ideas. Be sure to list any constraints. \$\endgroup\$ Oct 4, 2018 at 17:29
5
\$\begingroup\$
  • 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.

\$\endgroup\$
5
  • \$\begingroup\$ Thanks for your useful feedback. This is for an embedded device that runs Linux and I am displaying several values obtained in a loop that the user can scroll through. On my home PC running core I7, when I loop more than 100,000 times the elapsed time is 3 times slower with sprintf. This may not make much difference but the average embedded CPU being used will be about 400 Mhz and have only 32 MB RAM, so it may be worth it for me to not use sprintf for this. \$\endgroup\$
    – netcat
    Oct 4, 2018 at 2:47
  • \$\begingroup\$ int main() { /* Includes: #include <stdio.h> #include "stdafx.h" #include <stdint.h> #include <Windows.h> */ // To use DWORD add _CRT_SECURE_NO_WARNINGS to preprocessor definitions in Project Properties. DWORD oldTickcount = GetTickCount(); int val = 99999999; char sVal[16]; for (int i = 0; i < 1000000; i++) { //itoaBase10(val, sVal, 16); sprintf(sVal, "%d", val); } int elapsed = GetTickCount() - oldTickcount; printf("Elapsed milliseconds: %d\n", elapsed); getchar(); return 0; } \$\endgroup\$
    – netcat
    Oct 4, 2018 at 2:52
  • \$\begingroup\$ I will profile it tomorrow on Linux on the embedded device. \$\endgroup\$
    – netcat
    Oct 4, 2018 at 2:56
  • \$\begingroup\$ num > 9999999999 can never be true, given the fixed range of uint32_t, so it doesn't add any value anyway (and GCC warns that it's a useless test). \$\endgroup\$ Oct 4, 2018 at 18:03
  • \$\begingroup\$ @TobySpeight Aww, missed that. A case of blind trust, I suppose. \$\endgroup\$
    – vnp
    Oct 4, 2018 at 18:18
5
\$\begingroup\$

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);
}
\$\endgroup\$
4
  • \$\begingroup\$ Wow, thanks for posting this. Your modified method is 25% faster than chux's method on my embedded device, but I will probably use his, because of the flexibility his method has. \$\endgroup\$
    – netcat
    Oct 4, 2018 at 20:10
  • \$\begingroup\$ TBH, it's more about the journey than the end result - the unit-testing method is very helpful when used appropriately, and I'd like to think that what I've shown here will be useful to you in future work (and the tests I've written are valid regardless of which implementation you choose, so you can take them or write new tests based on them, independently of implementation). \$\endgroup\$ Oct 4, 2018 at 20:46
  • 1
    \$\begingroup\$ Since code does test against powers-of-10, unit tests at max_power_10 + {-1, 0, +1} and min_power_10 + {-1, 0, +1} are deserved to catch off-by-1 problems. \$\endgroup\$ May 23 at 18:41
  • \$\begingroup\$ Yes @chux - good additions to the test suite. We should parameterise the last two tests, and then it's easy to add all of those. \$\endgroup\$ May 24 at 6:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.