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

[Peter Nilsson]

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

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.
Why is that important? If you want _maximum_ compiler optimisation
potential, then you should make sput_i take an unsigned argument as
not all compilers will recognise that the supplied integer will
always be non-negative.
2 No object is assumed capable of representing the
magnitude of INT_MIN.
But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int. James Kuyper has argued in csc that this
need not be true in C99.

So, [-1000000..33000] would be a valid range for int!

I would like the Committee to formally disallow this as it makes
statements like i |= 1 potential UB even if i is positive. Also, it
makes division of two arbitrarily signed integers highly problematic.
3 The string is constructed in place without reversal.
Why is this important? [Have you profiled the cost of recursion
against an iterative reversing of the string?]
4 No features from standard library are used.

<snip>

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
}
else
{
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

--
Peter

[pete]

Peter Nilsson wrote:

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

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.
Why is that important?

I've seen posted versions with implementation defined behavior.
If you want _maximum_ compiler optimisation
potential, then you should make sput_i take an unsigned argument as
not all compilers will recognise that the supplied integer will
always be non-negative.
It should be unsigned. I used int as a "nothing up my sleeves"
gesture, to emphasize that the magnitude of INT_MIN
wasn't be represented by an integer type.

2 No object is assumed capable of representing the
magnitude of INT_MIN.

But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int.
James Kuyper has argued in csc that this need not be true in C99.

Well, ... I'm guessing he was arguing with other smart people too.

So, [-1000000..33000] would be a valid range for int!

I would like the Committee to formally disallow this as it makes
statements like i |= 1 potential UB even if i is positive. Also, it
makes division of two arbitrarily signed integers highly problematic.

3 The string is constructed in place without reversal.

Why is this important?

It's a novelty feature.
I don't think anybody was waiting for a new itoa.

4 No features from standard library are used.

<snip>

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
}
else
{
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

At first glance, it seems to be efficient and thorough.
I'll take a closer look at it.

--
pete

[Jack Klein]

On Mon, 26 Jan 2004 11:41:28 +1100, "Peter Nilsson"
<ai***@acay.com.au> wrote in comp.lang.c:

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

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.
Why is that important? If you want _maximum_ compiler optimisation
potential, then you should make sput_i take an unsigned argument as
not all compilers will recognise that the supplied integer will
always be non-negative.

2 No object is assumed capable of representing the
magnitude of INT_MIN.

But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int. James Kuyper has argued in csc that this
need not be true in C99.

INT_MIN + 1 is certainly representable in a signed int. So is
-(INT_MIN + 1). Either you have misunderstood James' arguments, or he
is just plain wrong.
So, [-1000000..33000] would be a valid range for int!
No, it is not. INT_MAX must be some power of 2 minus 1. INT_MIN must
either be -INT_MAX, or -INT_MAX - 1. There is no combination of value
bits that is invalid in an unsigned integer type or in a positive
signed integer type.

There are only two possible combinations of sign and value bits that
might be trap representations for signed integer types, and only one
for each of the allowed types of representation. For signed magnitude
and 2's complement, that is the bit combination of the sign bits 0 and
all value bits 1. For 1's complement, it is the sign bit 1 and all
value bits 1.

Assuming that the value and sign bits do not have the one possible
invalid value for the representation, the only way to have a trap
value in a signed integer type is if there is some invalid combination
of padding bits.

6.6.2 makes this all quite clear.
I would like the Committee to formally disallow this as it makes
statements like i |= 1 potential UB even if i is positive. Also, it
makes division of two arbitrarily signed integers highly problematic.

This does make it possible for i |= 1 to produce undefined behavior on
1's complement implementations, specifically if the prior value of i
had the sign bit and all but the least significant value bit set to 1
prior to the operation, it could produce a trap representation.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Peter Nilsson]

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:e2********************************@4ax.com...

On Mon, 26 Jan 2004 11:41:28 +1100, "Peter Nilsson"
<ai***@acay.com.au> wrote in comp.lang.c:

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

I wrote a version of itoa yesterday.

Features: <snip> 2 No object is assumed capable of representing the
magnitude of INT_MIN.
But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int. James Kuyper has argued in csc that this
need not be true in C99.

INT_MIN + 1 is certainly representable in a signed int. So is
-(INT_MIN + 1). Either you have misunderstood James' arguments, or he
is just plain wrong.

Well I guess you choose the latter. Here's one thread in which he discusses
this...

http://groups.google.com/groups?thre...2%40wizard.net

<snip> 6.6.2 makes this all quite clear.

ITYM 6.2.6, but see the link above.

--
Peter

[pete]

Peter Nilsson wrote:

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:e2********************************@4ax.com...

On Mon, 26 Jan 2004 11:41:28 +1100, "Peter Nilsson"
<ai***@acay.com.au> wrote in comp.lang.c:

"pete" <pf*****@mindspring.com> wrote in message
news:40***********@mindspring.com...
> I wrote a version of itoa yesterday.
>
> Features: <snip> > 2 No object is assumed capable of representing the
> magnitude of INT_MIN.

But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int. James Kuyper has argued in csc that this
need not be true in C99.

INT_MIN + 1 is certainly representable in a signed int. So is
-(INT_MIN + 1). Either you have misunderstood James' arguments, or he
is just plain wrong.

Well I guess you choose the latter. Here's one thread in which he discusses
this...

http://groups.google.com/groups?thre...2%40wizard.net

<snip>

6.6.2 makes this all quite clear.

ITYM 6.2.6, but see the link above.

The matter of how many value bits are in the unsigned type,
is irrelevant.
The signed type has the same number of value bits as itself,
regardless of whether it's representing a positive or negative value.

--
pete

[Jack Klein]

On Mon, 26 Jan 2004 15:24:56 +1100, "Peter Nilsson"
<ai***@acay.com.au> wrote in comp.lang.c:

"Jack Klein" <ja*******@spamcop.net> wrote in message
news:e2********************************@4ax.com...

On Mon, 26 Jan 2004 11:41:28 +1100, "Peter Nilsson"
<ai***@acay.com.au> wrote in comp.lang.c:

"pete" <pf*****@mindspring.com> wrote in message
news:40***********@mindspring.com...
> I wrote a version of itoa yesterday.
>
> Features: <snip> > 2 No object is assumed capable of representing the
> magnitude of INT_MIN.

But you do assume that the magnitude of INT_MIN+1 (and others) _are_
representable within an int. James Kuyper has argued in csc that this
need not be true in C99.

INT_MIN + 1 is certainly representable in a signed int. So is
-(INT_MIN + 1). Either you have misunderstood James' arguments, or he
is just plain wrong.

Well I guess you choose the latter. Here's one thread in which he discusses
this...

http://groups.google.com/groups?thre...2%40wizard.net

<snip>

6.6.2 makes this all quite clear.

ITYM 6.2.6, but see the link above.

Yes, I've seen the thread, and it is hair-splitting nonsense.

Paragraph 5 of 6.2.6.1:

<quote>
Certain object representations need not represent a value of the
object type. If the stored value of an object has such a
representation and is read by an lvalue expression that does
not have character type, the behavior is undefined. If such a
representation is produced by a side effect that modifies all or any
part of the object by an lvalue expression that does not have
character type, the behavior is undefined. Such a representation is
called a trap representation.
<unquote>

The contents of an object referenced by an lvalue of a particular type
(other than unsigned char) can be one of two things: a value or a
trap representation. It can't be both, it can't be neither.

Then there are paragraphs 1 & 2 of 6.2.6.2:

<quote>
1 For unsigned integer types other than unsigned char, the bits of the
object representation shall be divided into two groups: value bits and
padding bits (there need not be any of the latter). If there are N
value bits, each bit shall represent a different power of 2 between 1
and 2N-1, so that objects of that type shall be capable of
representing values from 0 to 2N - 1 using a pure binary
representation; this shall be known as the value representation. The
values of any padding bits are unspecified.

2 For signed integer types, the bits of the object representation
shall be divided into three groups: value bits, padding bits, and the
sign bit. There need not be any padding bits; there shall be exactly
one sign bit. Each bit that is a value bit shall have the same value
as the same bit in the object representation of the corresponding
unsigned type (if there are M value bits in the signed type and N in
the unsigned type, then M <= N). If the sign bit
is zero, it shall not affect the resulting value. If the sign bit is
one, the value shall be modified in one of the following ways:

— the corresponding value with sign bit 0 is negated (sign and
magnitude);

— the sign bit has the value -(2N) (two’s complement);

— the sign bit has the value -(2N - 1) (one’s complement).

Which of these applies is implementation-defined, as is whether the
value with sign bit 1 and all value bits zero (for the first two), or
with sign bit and all value bits 1 (for one’s complement), is a trap
representation or a normal value. In the case of sign and magnitude
and one’s complement, if this representation is a normal value it is
called a negative zero.
<unquote>

Each value bit contributes to a value, and the sign bit, when set
specifically has a value that combines with the value of the value
bits.

When the standard provides a list of anything, in this case possible
combinations of sign and value bits that may be trap representations,
without a qualifier like "includes", that list is exclusive. Nowhere
in the standard does it say that any other combinations of sign and
value bits may be trap representations and not values.

--
Jack Klein
Home: http://JK-Technology.Com
FAQs for
comp.lang.c http://www.eskimo.com/~scs/C-faq/top.html
comp.lang.c++ http://www.parashift.com/c++-faq-lite/
alt.comp.lang.learn.c-c++
http://www.contrib.andrew.cmu.edu/~a...FAQ-acllc.html

[Larry Doolittle]

In article <8c********************************@4ax.com>, Jack Klein wrote:

Then there are paragraphs 1 & 2 of 6.2.6.2:

<quote>
1 For unsigned integer types other than unsigned char, the bits of the
object representation shall be divided into two groups: value bits and
padding bits (there need not be any of the latter). If there are N
value bits, each bit shall represent a different power of 2 between 1
and 2N-1, so that objects of that type shall be capable of
representing values from 0 to 2N - 1 using a pure binary
representation; this shall be known as the value representation. The
values of any padding bits are unspecified.

2 For signed integer types, the bits of the object representation
shall be divided into three groups: value bits, padding bits, and the
sign bit. There need not be any padding bits; there shall be exactly
one sign bit. Each bit that is a value bit shall have the same value
as the same bit in the object representation of the corresponding
unsigned type (if there are M value bits in the signed type and N in
the unsigned type, then M <= N). If the sign bit
This has bearing on _my_ long-term troubling question about writing
an honestly portable itoa.

If I write (in the OTBS):

char *local_itoa(int i)
{
unsigned int x = (i>=0) ? (unsigned) i : -(unsigned) i;
....
am I guaranteed that the absolute value of i can be represented
in x? A literal reading of this standard would suggest not, if
M (the _data_bit_ width of signed int) is equal to N (the width
of unsigned int), and the input value is INT_MIN in twos-complement,
i.e., -(2^N). In that case the absolute value (-(unsigned)i) should
be 2^N, but the max value representable is 2^M-1. This possibility
is unique to architectures with twos-complement signed representations.

If the standard does not guarantee this, should it? Are there
any known twos-complement architectures where N==M? Are there
_any_ architectures where N==M, or did the standard writers glitch
and mean to write M < N?

Enquiring minds want to know. ;-)

- Larry
is zero, it shall not affect the resulting value. If the sign bit is
one, the value shall be modified in one of the following ways:

— the corresponding value with sign bit 0 is negated (sign and
magnitude);

— the sign bit has the value -(2N) (two’s complement);

— the sign bit has the value -(2N - 1) (one’s complement).

Which of these applies is implementation-defined, as is whether the
value with sign bit 1 and all value bits zero (for the first two), or
with sign bit and all value bits 1 (for one’s complement), is a trap
representation or a normal value. In the case of sign and magnitude
and one’s complement, if this representation is a normal value it is
called a negative zero.
<unquote>

[CBFalconer]

Larry Doolittle wrote:

Jack Klein wrote:

Then there are paragraphs 1 & 2 of 6.2.6.2:

<quote>
1 For unsigned integer types other than unsigned char, the bits
of the object representation shall be divided into two groups:
value bits and padding bits (there need not be any of the
latter). If there are N value bits, each bit shall represent a
different power of 2 between 1 and 2N-1, so that objects of
that type shall be capable of representing values from 0 to 2N
- 1 using a pure binary representation; this shall be known as
the value representation. The values of any padding bits are
unspecified.

2 For signed integer types, the bits of the object
representation shall be divided into three groups: value bits,
padding bits, and the sign bit. There need not be any padding
bits; there shall be exactly one sign bit. Each bit that is a
value bit shall have the same value as the same bit in the
object representation of the corresponding unsigned type (if
there are M value bits in the signed type and N in the
unsigned type, then M <= N). If the sign bit

This has bearing on _my_ long-term troubling question about writing
an honestly portable itoa.

What is the problem? Write a routine for an unsigned integer.
For integers, resolve the sign, convert to unsigned, and apply
that routine.

When you have languages that do not provide unsigned versions
things are slighly harder, because you have to allow for the fact
that negative values may have a larger range. In that case write
a routine to convert negative integers, ignoring the sign, and
then call that from a routine that handles the sign. This does
not apply to C.

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[pete]

CBFalconer wrote:

Larry Doolittle wrote:

Jack Klein wrote:

Then there are paragraphs 1 & 2 of 6.2.6.2:

<quote>
1 For unsigned integer types other than unsigned char, the bits
of the object representation shall be divided into two groups:
value bits and padding bits (there need not be any of the
latter). If there are N value bits, each bit shall represent a
different power of 2 between 1 and 2N-1, so that objects of
that type shall be capable of representing values from 0 to 2N
- 1 using a pure binary representation; this shall be known as
the value representation. The values of any padding bits are
unspecified.

2 For signed integer types, the bits of the object
representation shall be divided into three groups: value bits,
padding bits, and the sign bit. There need not be any padding
bits; there shall be exactly one sign bit. Each bit that is a
value bit shall have the same value as the same bit in the
object representation of the corresponding unsigned type (if
there are M value bits in the signed type and N in the
unsigned type, then M <= N). If the sign bit

This has bearing on _my_ long-term troubling question about writing
an honestly portable itoa.

What is the problem? Write a routine for an unsigned integer.
For integers, resolve the sign, convert to unsigned, and apply
that routine.

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.

--
pete

[Larry Doolittle]

In article <sl*********************@recycle.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**********@mindspring.com> pete <pf*****@mindspring.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**********@mindspring.com> pete <pf*****@mindspring.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**********@mindspring.com>
pete <pf*****@mindspring.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*****@mindspring.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*****@mindspring.com> wrote in message
news:40***********@mindspring.com...

pete wrote:

Dan Pop wrote:

In <40**********@mindspring.com>
pete <pf*****@mindspring.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*****@mindspring.com> wrote in message
news:40***********@mindspring.com...

pete wrote:

Dan Pop wrote:
>
> In <40**********@mindspring.com>
> pete <pf*****@mindspring.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;
}
}

[CBFalconer]

pete wrote:

Dan Pop wrote:

.... snip ...

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;
}
}

Try a simpler method (untested in C).

if (0 > i) sign = '-';
else {
i = -i;
sign = '\0';
}
p = s;
/* Now sign has been recorded, and i is negative */
/* Only the first digit is critical, after that the range */
/* of i will easily be within that of a positive int */
do {
c = i % 10; /* this step requires careful std reading */
/* about modulus of -ve numbers. Check it */
*p++ = c + '0'; /* which may require adding 10 here */
i /= 10;
} while (i);
if (*p++ = sign) *p++ = '\0';
--p;
/* Now reverse the string s through p in place */
while (s < --p) {
c = *s;
*s++ = *p;
*p = c;
}

There may be an evil gotcha in the above, because something about
modulo changed between C89 and C99.

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;
}
}

--
Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home.att.net> USE worldnet address!

[pete]

pete wrote:

Peter Nilsson wrote:

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.
*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.
}
else
{
This code is unreachable on my machine,
so all I can do is to think about it.
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.
I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;
while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

At first glance, it seems to be efficient and thorough.
I'll take a closer look at it.

--
pete

[pete]

pete wrote:

pete wrote:

Peter Nilsson wrote:

What are your thoughts on...?

char *itoa(int i, char *s)
{
char *p = s;
char *q = s;

if (i >= 0)
{
do
{
*q++ = '0' + (i % 10);
}
while (i /= 10);
}
else if (-1 % 2 < 0)
{
This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.

/* (a/b)*b + a%b shall equal a */

(-1 / 10 == 0, 0) * 10 + (-1 % 10 == -1, -1) == -1

*q++ = '-';
p++;

do
{
*q++ = '0' - i % 10;
}
while (i /= 10);
I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.
}
else
{
This code is unreachable on my machine,
so all I can do is to think about it.
*q++ = '-';
p++;

do
{
int d = i % 10;
i = i / 10;
if (d) { i++; d = 10 - d; }
*q++ = '0' + d;
}
I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
That would explain
d = 10 - d;
but not
i++;

while (i);
}

for (*q = 0; p < --q; p++)
{
char c = *p;
*p = *q;
*q = c;
}

return s;
}

At first glance, it seems to be efficient and thorough.
I'll take a closer look at it.

--
pete

[pete]

pete wrote:

pete wrote:

pete wrote:

Peter Nilsson wrote:

> What are your thoughts on...?
>
> char *itoa(int i, char *s)
> {
> char *p = s;
> char *q = s;
>
> if (i >= 0)
> {
> do
> {
> *q++ = '0' + (i % 10);
> }
> while (i /= 10);
> }
> else if (-1 % 2 < 0)
> {

This is the part of the code that runs on my machine.
I believe that here, (-1 % 10 == -1) and (-1 / 10 == 0) are true.

/* (a/b)*b + a%b shall equal a */

(-1 / 10 == 0, 0) * 10 + (-1 % 10 == -1, -1) == -1

> *q++ = '-';
> p++;
>
> do
> {
> *q++ = '0' - i % 10;
> }
> while (i /= 10);

I'm thinking about converting -1.
'0' - i % 10 is '1', so that looks good.

> }
> else
> {

This code is unreachable on my machine,
so all I can do is to think about it.

> *q++ = '-';
> p++;
>
> do
> {
> int d = i % 10;
> i = i / 10;
> if (d) { i++; d = 10 - d; }
> *q++ = '0' + d;
> }

I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.

I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

--
pete

[Peter Nilsson]

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

pete wrote:

pete wrote: ....

I'm thinking about converting -1 again.
I think that in the above loop,
(-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
-1/10 => -0.1, so the integer division can be 0 or -1.

I see why i++ is there, but I think that the value of
int d = i % 10;
is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
Yes.
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

C89 supports no less than 8 different forms of integer division[*]. But I've
only ever seen two: rounding towards zero, and the mathematical non-negative
remainder version.

You can actually test all of the different versions, simply by adjusting the
results of the existing division. [That's how I tested my code; I replaced
the % and / calculations with some function macros.]
[*] there are three possible ways for at least one of two operands to be
negative, and there are two possible division results for each case.

--
Peter

[pete]

Peter Nilsson wrote:

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

pete wrote:

pete wrote: ... > I'm thinking about converting -1 again.
> I think that in the above loop,
> (-1 % 10 == 1) and (-1 / 10 == -2) are true.

I can't make , "(a/b)*b + a%b shall equal a "
hold for those numbers, so I think I'm wrong.
-1/10 => -0.1, so the integer division can be 0 or -1.
I see why i++ is there, but I think that the value of
> int d = i % 10;
> is correct and should not be altered as in d = 10 - d;

Is this what you're using ?
(-1 / 10 == -1) (-1 % 10 == 9)
Yes.
That would explain
d = 10 - d;
but not
i++;

Actually it does explain i++;

C89 supports no less than 8 different forms of integer division[*].
But I've only ever seen two: rounding towards zero, and the
mathematical non-negative remainder version.

You can actually test all of the different versions,
simply by adjusting the
results of the existing division.
[That's how I tested my code; I replaced
the % and / calculations with some function macros.]

[*] there are three possible ways for at least one of two operands
to be negative,
and there are two possible division results for each case.

You get my vote for
"most efficient library independant itoa alogorithm".

--
pete

[Dave Thompson]

On Thu, 29 Jan 2004 19:13:19 -0500 (EST), "Arthur J. O'Dwyer"
<aj*@nospam.andrew.cmu.edu> wrote:

On Thu, 29 Jan 2004, Larry Doolittle wrote:

[pete wrote:]

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

<snip> #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. <snip>

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc., so on
an absolute-maximum-portability quest you still have the problem.

- David.Thompson1 at worldnet.att.net

[Dan Pop]

In <vc********************************@4ax.com> Dave Thompson <da*************@worldnet.att.net> writes:

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc.,

^^^^^^^^^^^^^^^^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

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

[Dave Thompson]

On 6 Feb 2004 19:29:42 GMT, Da*****@cern.ch (Dan Pop) wrote:

In <vc********************************@4ax.com> Dave Thompson <da*************@worldnet.att.net> writes:

Not by definition; preprocessor arithmetic is done in u/long in C89,
and u/intmax_t in C99. But it is still *possible* that the largest
unsigned type cannot handle the full range of signed INT etc.,

^^^^^^^^^^^^^^^^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

Sorry, sloppy wording. I meant can't handle the magnitudes of the full
negative range, and in particular of the 2sC most negative value,
which was the issue upthread.

Nit: a thing that is necessarily or always so, like what you marked,
is a "certainty". "Certitude" is (and "certainty" is *also*) the
property of a person being confident of something.

- David.Thompson1 at worldnet.att.net

[Dan Pop]

In <b7********************************@4ax.com> Dave Thompson <da*************@worldnet.att.net> writes:

On 6 Feb 2004 19:29:42 GMT, Da*****@cern.ch (Dan Pop) wrote:

In <vc********************************@4ax.com> Dave Thompson <da*************@worldnet.att.net> writes:

>Not by definition; preprocessor arithmetic is done in u/long in C89,
>and u/intmax_t in C99. But it is still *possible* that the largest
>unsigned type cannot handle the full range of signed INT etc., ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
It's not only possible, it's a *certitude*.

Sorry, sloppy wording. I meant can't handle the magnitudes of the full
negative range, and in particular of the 2sC most negative value,
which was the issue upthread.

Unsigned types cannot handle any single bit of the negative range, by
definition.
Nit: a thing that is necessarily or always so, like what you marked,
is a "certainty". "Certitude" is (and "certainty" is *also*) the
property of a person being confident of something.

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