itoa in pure C

[pete]

I wrote a version of itoa yesterday.

Features:
1 No implementation defined arithmetic. All of the division
and modulus division is done on positive values only.
2 No object is assumed capable of representing the
magnitude of INT_MIN.
3 The string is constructed in place without reversal.
4 No features from standard library are used.

sput_i writes the decimal representation of a nonnegative int value
argument to an array of char.
sput_ip1 writes the representation of one greater than the
argument value, for any nonnegative int value argument, to an
array of char.

/* BEGIN itoa.c */

void itoa(int, char *);
char *sput_i(int, char *);
char *sput_ip1(int, char *);

void itoa(int integer, char *string)
{
if (0 > integer) {
++integer;
*string++ = '-';
*sput_ip1(-integer, string) = '\0';
} else {
*sput_i(integer , string) = '\0';
}
}

char *sput_i(int integer, char *string)
{
if (integer / 10 != 0) {
string = sput_i(integer / 10, string);
}
*string++ = (char)('0' + integer % 10);
return string;
}

char *sput_ip1(int integer, char *string)
{
int digit;

digit = (integer % 10 + 1) % 10;
if (integer / 10 != 0) {
string = (digit == 0 ? sput_ip1 : sput_i)(integer / 10, string);
*string++ = (char)('0' + digit);
} else {
if (digit == 0) {
*string++ = '1';
}
*string++ = (char)('0' + digit);
}
return string;
}

/* END itoa.c */

--
pete

[Larry Doolittle]

In article <sl************ *********@recyc le.lbl.gov>, Larry Doolittle wrote:

am I guaranteed that the absolute value of i can be represented
in x? A literal reading of this standard would suggest not, [chop
Pete replied (using an forged e-mail address, and in a posting
that never showed up on my news server):
Can't do it if UINT_MAX == 65535, and INT_MIN == -65536.

CHAR_BIT == 16
INT_MAX == 65535
sizeof(unsigned ) == 2
sizeof(int) == 2

unsigned isn't guaranteed to be able to represent
the magnitude of INT_MIN.

Try as I might, I can't think of a machine that
could or would set things up like this. Is there
one, or is the standard unnecessarily permissive?

I guess my code should really look like:

#if -(INT_MIN)>UINT_ MAX
#error this computer may be conforming, but it is too strange for this program
#endif
char *local_itoa(int i)
{
unsigned int x = (i>=0) ? (unsigned) i : -(unsigned) i;

- Larry

[Arthur J. O'Dwyer]

On Thu, 29 Jan 2004, Larry Doolittle wrote:

[pete wrote:]

Can't do it if UINT_MAX == 65535, and INT_MIN == -65536.

CHAR_BIT == 16
INT_MAX == 65535
sizeof(unsigned ) == 2
sizeof(int) == 2

unsigned isn't guaranteed to be able to represent
the magnitude of INT_MIN.

[I haven't checked Pete's references, but I'll take it as given
for the moment that he's right.]
Try as I might, I can't think of a machine that
could or would set things up like this. Is there
one, or is the standard unnecessarily permissive?
Sounds unnecessarily permissive to me. But if the Standard
allows it, then you can bet the DS9000 implements it. ;-)
I guess my code should really look like:

#if -(INT_MIN)>UINT_ MAX

Huh? On a "normal" two's-complement machine, this would produce
undefined behavior when you tried to negate INT_MIN. "Fixing" the
code to read

#if (0u - INT_MIN) > UINT_MAX

just makes it sillier: the left-hand side evaluates to some unsigned
int, which by definition cannot be greater than UINT_MAX. So I
have no idea how you thought this code could work -- and even less
idea of how to make it compute what you apparently think it's computing.

-Arthur

[Larry Doolittle]

Arthur J. O'Dwyer wrote:

On Thu, 29 Jan 2004, Larry Doolittle wrote:

[pete wrote:]

> Can't do it if UINT_MAX == 65535, and INT_MIN == -65536.
>
> CHAR_BIT == 16
> INT_MAX == 65535
> sizeof(unsigned ) == 2
> sizeof(int) == 2

Try as I might, I can't think of a machine that
could or would set things up like this. Is there
one, or is the standard unnecessarily permissive?

Looking at this closer, this sounds like 16 pad bits on unsigned,
and 15 pad bits plus 1 sign bit on signed. Implausible, but
maybe not impossible.
Sounds unnecessarily permissive to me. But if the Standard
allows it, then you can bet the DS9000 implements it. ;-)

I guess my code should really look like:

#if -(INT_MIN)>UINT_ MAX
Huh? On a "normal" two's-complement machine, this would produce
undefined behavior when you tried to negate INT_MIN.

I wasn't aware that the preprocessor suffered the same potential
warts as the execution model. I'll have to go read the standard
more carefully.
So I have no idea how you thought this code could work -- and even less
idea of how to make it compute what you apparently think it's computing.

While I would prefer the standard guarantee that -INT_MIN could be
represented as an unsigned int, I should at least be able to detect
a failure of this assumption at compile time. How about

#if -(INT_MIN+1) > (UINT_MAX-1)

?

- Larry

[pete]

Larry Doolittle wrote:

Arthur J. O'Dwyer wrote:

On Thu, 29 Jan 2004, Larry Doolittle wrote:

[pete wrote:]
> Can't do it if UINT_MAX == 65535, and INT_MIN == -65536.
>
> CHAR_BIT == 16
> INT_MAX == 65535
> sizeof(unsigned ) == 2
> sizeof(int) == 2

Try as I might, I can't think of a machine that
could or would set things up like this. Is there
one, or is the standard unnecessarily permissive?

Looking at this closer, this sounds like 16 pad bits on unsigned,
and 15 pad bits plus 1 sign bit on signed. Implausible, but
maybe not impossible.

Sounds unnecessarily permissive to me. But if the Standard
allows it, then you can bet the DS9000 implements it. ;-)

I guess my code should really look like:

#if -(INT_MIN)>UINT_ MAX

Huh? On a "normal" two's-complement machine, this would produce
undefined behavior when you tried to negate INT_MIN.

I wasn't aware that the preprocessor suffered the same potential
warts as the execution model. I'll have to go read the standard
more carefully.

So I have no idea how you thought this code could work -- and even less
idea of how to make it compute what you apparently think it's computing.

While I would prefer the standard guarantee that -INT_MIN could be
represented as an unsigned int, I should at least be able to detect
a failure of this assumption at compile time. How about

#if -(INT_MIN+1) > (UINT_MAX-1)

bottom line:
The standard doesn't guarantee that there is any integer type
capable of representing the magnitude of INT_MIN.
That's the relevant rule which makes implementing itoa, amusing.

--
pete

[Dan Pop]

In <40**********@m indspring.com> pete <pf*****@mindsp ring.com> writes:

bottom line:
The standard doesn't guarantee that there is any integer type
capable of representing the magnitude of INT_MIN.
That's the relevant rule which makes implementing itoa, amusing.

It's not that amusing: just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1. If the flag is set, increment the least
significant digit of the result. No need to worry about carry propagation
because no power of two has 0 as its least significant digit.

Dan
--
Dan Pop
DESY Zeuthen, RZ group
Email: Da*****@ifh.de

[pete]

Dan Pop wrote:

In <40**********@m indspring.com> pete <pf*****@mindsp ring.com> writes:

bottom line:
The standard doesn't guarantee that there is any integer type
capable of representing the magnitude of INT_MIN.
That's the relevant rule which makes implementing itoa, amusing.
It's not that amusing:

That might be why I did it without any standard library headers.
It was adapted from put_d(),
which is a functional component of a minprintf() (K&R2, 7.3)
that I'm writing from "first principles", for no important reason.
It uses stdarg.h of course, but only four features from stdio.h:
EOF, FILE, stdout, and putc(c, stream)
just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1. If the flag is set, increment the least
significant digit of the result.
No need to worry about carry propagation
because no power of two has 0 as its least significant digit.

void ito_a(int i, char *s)
{
char c, *p;
int int_min = 0;

p = s;
if (0 > i) {
*p++ = '-';
++s;
if (i == INT_MIN) {
int_min = 1;
i = INT_MAX;
} else {
i = -i;
}
}
do {
*p++ = (char)('0' + i % 10);
i /= 10;
} while (i);
if (int_min) {
++*s;
}
for (*p = '\0'; --p > s; ++s) {
c = *s;
*s = *p;
*p = c;
}
}

[pete]

pete wrote:

Dan Pop wrote:

In <40**********@m indspring.com>
pete <pf*****@mindsp ring.com> writes:

The standard doesn't guarantee that there is any integer type
capable of representing the magnitude of INT_MIN.
That's the relevant rule which makes implementing itoa, amusing.
It's not that amusing: just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1.

I think you mean, handle (-1 - INT_MAX) as a special case
if (i == INT_MIN) {

void ito_a(int i, char *s)
{
char c, *p;
int flag = 0;

p = s;
if (0 > i) {
*p++ = '-';
++s;
if (i == -1 - INT_MAX) {
flag = 1;
i = INT_MAX;
} else {
i = -i;
}
}
do {
*p++ = (char)('0' + i % 10);
i /= 10;
} while (i);
if (flag) {
++*s;
}
for (*p = '\0'; --p > s; ++s) {
c = *s;
*s = *p;
*p = c;
}
}

[Peter Nilsson]

"pete" <pf*****@mindsp ring.com> wrote in message
news:40******** ***@mindspring. com...

Dan Pop wrote:

just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1. If the flag is set, increment the least
significant digit of the result.
No need to worry about carry propagation
because no power of two has 0 as its least significant digit.
void ito_a(int i, char *s)
{
char c, *p;
int int_min = 0;

p = s;
if (0 > i) {
*p++ = '-';
++s;
if (i == INT_MIN) {
int_min = 1;
i = INT_MAX;

You're assuming INT_MIN + 1 == INT_MAX.

i = -(INT_MIN + 1);
} else {
i = -i;
}
}
do {
*p++ = (char)('0' + i % 10);
i /= 10;
} while (i);
if (int_min) {
++*s;
}
for (*p = '\0'; --p > s; ++s) {
c = *s;
*s = *p;
*p = c;
}
}

--
Peter

[Peter Nilsson]

"pete" <pf*****@mindsp ring.com> wrote in message
news:40******** ***@mindspring. com...

pete wrote:

Dan Pop wrote:

In <40**********@m indspring.com>
pete <pf*****@mindsp ring.com> writes: The standard doesn't guarantee that there is any integer type
> capable of representing the magnitude of INT_MIN.
>That's the relevant rule which makes implementing itoa, amusing.

It's not that amusing: just treat INT_MIN as a special case: set a flag
and handle it as INT_MIN + 1.

I think you mean, handle (-1 - INT_MAX) as a special case

if (i == INT_MIN) {

if (i == -1 - INT_MAX) {

No. On implementations where INT_MIN == -INT_MAX, -1-INT_MAX can overflow.

--
Peter

[pete]

Peter Nilsson wrote:

"pete" <pf*****@mindsp ring.com> wrote in message
news:40******** ***@mindspring. com...

pete wrote:

Dan Pop wrote:
>
> In <40**********@m indspring.com>
> pete <pf*****@mindsp ring.com> writes:

> > The standard doesn't guarantee that there is any integer type
> > capable of representing the magnitude of INT_MIN.
> >That's the relevant rule which makes implementing itoa, amusing.
>
> It's not that amusing:

> just treat INT_MIN as a special case: set a flag
> and handle it as INT_MIN + 1.

I think you mean, handle (-1 - INT_MAX) as a special case

if (i == INT_MIN) {

if (i == -1 - INT_MAX) {

No. On implementations where INT_MIN == -INT_MAX,
-1-INT_MAX can overflow.

Thank you.

void ito_a(int i, char *s)
{
char c, *p;
int flag = 0;

p = s;
if (0 > i) {
*p++ = '-';
++s;
if (-INT_MAX > i) {
flag = 1;
i = INT_MAX;
} else {
i = -i;
}
}
do {
*p++ = (char)('0' + i % 10);
i /= 10;
} while (i);
if (flag) {
++*s;
}
for (*p = '\0'; --p > s; ++s) {
c = *s;
*s = *p;
*p = c;
}
}