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);
}
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\$std::int32_t
and the other fixed-width types (assuming you include<cstdint>
rather than<stdint.h>
). \$\endgroup\$