11
\$\begingroup\$

As an exercise, I limited my self to the man pages. I didn't look for a previous existing implementation because I wanted to see how well I could do on my own. I also tried to handle as many cases as I could think of. I am sure there are weaknesses so feel free to point them out. Where can I improve my usage of the C standard library, etc.

char *
itoa(int i)
{
  short digit_cnt;
  short index;
  void *ret;
  char digit;
  int tmp;

  errno = 0;
  feclearexcept(FE_ALL_EXCEPT);
  if (i == 0) {
    digit_cnt = 1;
  } else {
    tmp = (i == INT_MIN) ? (i + 1) : i;
    digit_cnt = floor(log10(abs(tmp))) + 1;
    if (errno || fetestexcept(FE_INVALID | FE_DIVBYZERO | FE_OVERFLOW |
      FE_UNDERFLOW)) {
      return NULL;
    }
  }

  if (i < 0) {
    ++digit_cnt;
  }
  ++digit_cnt; // '\0'

  errno = 0;
  if ((ret = malloc(digit_cnt * sizeof(char))) == NULL || errno) {
    print_error_msg(errno);
    free(ret);
    return NULL;
  }

  // This made debugging easier.
  memset(ret, '0', digit_cnt * sizeof(char));

  index = digit_cnt;
  ((char*)ret)[--index] = '\0';

  tmp = i;
  do {
    digit = (char)((int)'0' + abs(tmp % 10));
    ((char*)ret)[--index] = digit;
    tmp /= 10;
  } while (tmp != 0);

  if (i < 0) {
    ((char*)ret)[--index] = '-';
  }

  return ret;
}
\$\endgroup\$
4
\$\begingroup\$
  1. No reason to use floating point math here. At a minimum, it creates a non-portability as the aspects of FP math have corner cases and precision issues that will fail itoa(int i). At worst, it invoke undefined behavior: abs(tmp) may be UB if tmp == INT_MIN. (Code does use tmp = (i == INT_MIN) ? (i + 1) : i; to handle that case, but it call be handled cleaner in other ways.) Rare, but potential inexact result from log10() leads to off-by-one with floor(). C does not specify that double can represent every int. Think of a 64-bit int and 64-bit double. Code like log10(abs(tmp)) is a potential for conversion inaccuracies.

    // Many issues
    digit_cnt = floor(log10(abs(tmp))) + 1;
    
  2. Code is clearing a global value in code that is very unexpected to do so. feclearexcept(FE_ALL_EXCEPT); I would not expect the side-effect of itoa() to clear FP exceptions.

  3. errno = 0 is another unexpected side-effect of this itoa(). Like strtol() and other conversion functions, setting errno to 0 is the caller's responsibility. C does not specify that errno is set to some value on a out-of-memory. Since this post is not tagged OS specific, I am on the fence as to if errno should be set to indicate that error.

  4. Excessive malloc(). Just malloc() the space needed, not the worst case size. I see OP is right-sizing, yet in a dangerous fashion. OP's code relies on log10() coming up with the exact answer when i == power-of-10. Weak FP math libraries have been known to come up just short of the expected value. No only would this generate the wrong conversion, it would cause memory corruption.

  5. Avoid the name itoa() as that is well used by others.

  6. Note: C99 or later dependency. tmp % 10 and tmp /= 10 may not return the value expected with early compliers. I am noting it, but not think it if worth the effort to account for those compliers. YMMV

All in all a good attempt, but starting off will FP, really overcomplicated things and created unneeded dependencies on FP math/attributes. The FP math was only used to size the buffer, when a worst case buffer could be instead for the intermediate results. Thinking of embedded project, that log10() inclusion is especially space and time expensive.

A simple C99 alternative.

#include <stdlib.h>
// Worst case size needed: about bit_width * log10(2) + a few extra
#define INT_SIZE (sizeof(int)*CHAR_BIT / 3 + 3)

char *MH_itoa(int i) {
  char buf[INT_SIZE];
  char *p = &buf[sizeof buf - 1];
  *p = '\0';

  int j = i;
  //  Let us work with negative numbers to avoid problems with abs(INT_MIN)
  if (j > 0) {
    j = -j;
  }

  do {
    p--;
    *p = '0' - j % 10;
    j /= 10;
  } while (j);
  if (i < 0) {
    p--;
    *p = '-';
  }

  // Right size the allocation
  size_t size = (size_t) (&buf[sizeof buf] - p);
  char *dest = malloc(size);
  if (dest) {
    memcpy(dest, p, size);
  }

  return dest;
}
\$\endgroup\$
  • \$\begingroup\$ What incorrect results can a pre C99 compiler return for mod? I haven't heard that before? \$\endgroup\$ – AShelly Feb 18 '16 at 3:15
  • \$\begingroup\$ @AShelly When division of a negative number results in an inexact quotient (or something like that), the result might round up or down. en.wikipedia.org/wiki/… \$\endgroup\$ – chux - Reinstate Monica Feb 18 '16 at 3:21
10
\$\begingroup\$

Well, the code works. It's definitely not as efficient as it could be, though; you're using floating-point math to accomplish something that could be done entirely in integer operations.

You forgot to #include all the headers you need. By my count, that's

#include <fenv.h>  // feclearexcept
#include <limits.h>  // INT_MIN
#include <math.h>  // floor, log10
#include <stdlib.h>  // abs
#include <errno.h>  // errno
#include <string.h>  // memset

Plus wherever print_error_msg comes from; that's an undefined symbol in the code you posted. I'm guessing it does something similar to perror(NULL)?


If I were writing itoa, I'd start by assuming that I already had the memory allocation taken care of. Then filling the buffer is as easy as what you wrote:

size_t result_length = <some magic>;
char *result = malloc(result_length + 1);
result[result_length] = '\0';
if (number < 0) {
    result[0] = '-';
    number = -number;
}
for (int i = result_length, n = number; n != 0; n /= 10) {
    result[--i] = '0' + (n % 10);
}

(I'd special-case 0 and INT_MIN at the top of the function so that we don't have to worry about them down here.)

Then the only missing piece is the <some magic>. But that's easy — we just need to write some code to count the digits of number. And we already have some code to print the digits of number! So I'd just repeat that code again.

int result_length = (number < 0);
for (int n = number; n != 0; n /= 10) {
    result_length += 1;
}

There — the only headers we needed were <stdlib.h> (for malloc) and possibly <limits.h> (for INT_MIN).


Notice that I wrote '0' + x where you'd written (char)((int)'0' + x). C isn't Pascal or Python; there's no need to jump through hoops like chr(ord('0') + x) here. Characters in C are small integers, and you can do math on them just as you can on any other integer type.

Moreover, you should do math on character types, if it eliminates the need for a cast operation. Type-casting in C and C++ is a code smell; if you really need a cast, something is horribly wrong with your code. In this case, fortunately, you don't need one.


Another place your code uses casts is

void *ret;
...
((char*)ret)[--index] = '\0';

Kudos for using '\0' instead of 0; that's a nice way to indicate to the reader what this particular zero semantically represents. But kill the cast! In this case, you think you need the cast because ret is a void*. However, the only places you refer to ret, you cast it to char*. This is a huge honking sign that ret really wants to be char*.

char *ret;
...
ret[--index] = '\0';

Problem solved. ret had no business being a void* in the first place.


No comment on the theoretical correctness of the floating-point stuff; because, as I said, I wouldn't have used floating-point to print integers in the first place. I have tested your code on all 4 billion 32-bit integers, though, and can report that it works fine in practice.

\$\endgroup\$
  • \$\begingroup\$ Sometimes unneeded casting is needed. With OP's char digit; ... digit = (char)((int)'0' + abs(tmp % 10)); the (char) is useful to quiet the pedantic warning about converting an int to char. This warning is quieted by explicitly coding the down cast. Many compilations do not enable this warning as it is considered too annoying. Note: agree (int) cast here is best not coded. \$\endgroup\$ – chux - Reinstate Monica Feb 18 '16 at 2:30
3
\$\begingroup\$

You might consider avoiding the malloc inside this function. Many utility functions leave all the memory management up to the caller - the caller must provide a buffer and it's size. In your implementation, the caller needs to know to free the returned pointer after use.

Given that the size is dependent on the input, you could use a helper function to calculate the needed digits. (See Quuxplusone's answer for an implementation). Then callers can do:

int x = NUMBER_TO_PRINT;
int ndigits = digits_of(x);
char* buf = malloc(ndigits+1);
my_itoa(x, buf, ndigits+1);

But they can also use the function to print directly into an existing buffer, without requiring an extra copy.

Also, the typical itoa implementation usually takes the radix as an argument, so you can also use it to print in hex or binary. Supporting radix is as simple as replacing the 10s with a radix argument.

\$\endgroup\$
  • 1
    \$\begingroup\$ Note that @Quuxplusone's digits_of(x) code is off-by-1 for digits_of(0) as that answer hints at "special-case 0 and INT_MIN at the top of the function" yet this answer does not mention that exemption. It could easily be fixed with int result_length = (number <= 0); \$\endgroup\$ – chux - Reinstate Monica Feb 18 '16 at 2:36
  • 1
    \$\begingroup\$ Instead of providing two functions (digits_of and my_itoa), it's better to provide just one function, which either prints or computes-length-of, depending on whether its destination argument is NULL. See for example snprintf. \$\endgroup\$ – Quuxplusone Feb 20 '16 at 19:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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