Can a "value" overflow?

[TTroy]

Hello, can anyone explain why the following function will not work for
INT_MIN:
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;

if((sign = n) < 0) /* record sign */
n = -n; /* make n positive */

i = 0;
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */

if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s); /* another function; irrelevant to my question */
}

I've narrowed it down to the n = -n line. On my machine, -(INT_MIN)
would be 1 more than INT_MAX. Does this overflow the temporary value
-n, or the actual object n. What I'm trying to ask is, when the fault
happens?

My feeling is that the fault (undefined behaviour) first occurs with
the -n, because the value of the result is a signed int (no promotions
or conversions) and that value is overflowed. Does that make sense?
Can a "value" overflow just like objects can?

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

[Romeo Colacitti]

TTroy wrote:

Hello, can anyone explain why the following function will not work for INT_MIN:
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;

if((sign = n) < 0) /* record sign */
n = -n; /* make n positive */

i = 0;
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */

if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s); /* another function; irrelevant to my question */
}

I've narrowed it down to the n = -n line. On my machine, -(INT_MIN)
would be 1 more than INT_MAX. Does this overflow the temporary value
-n, or the actual object n. What I'm trying to ask is, when the fault happens?

My feeling is that the fault (undefined behaviour) first occurs with
the -n, because the value of the result is a signed int (no promotions or conversions) and that value is overflowed. Does that make sense?
Can a "value" overflow just like objects can?

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

Values have types too. So the -n is a an expression that resolves to a
value of type signed int. You are overflowing the maximum capacity of
that type by 1, thus undefined behaviour.

Try this:

void itoa(int n, char s[]) {
int i, sign;
sign = n;

i = 0;
do {
s[i++] = abs(n % 10) + '0';
} while ( n /= 10 );
if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s);
}

In the example above, there are no overflows. I still think there is
an issue, though most computers will behave properly: the result of n %
10 is implementation defined because n could be negative (but any sane
compiler will produce the result most people expect)

Results like -18 % 10 = 8 are expected on any good implementation.

[davebsr]

TTroy wrote:

Hello, can anyone explain why the following function will not work for INT_MIN:

-- Snip itoa() from KnR2, pg 64. --
I've narrowed it down to the n = -n line. On my machine, -(INT_MIN)
would be 1 more than INT_MAX. Does this overflow the temporary value
-n, or the actual object n. What I'm trying to ask is, when the fault happens?

My feeling is that the fault (undefined behaviour) first occurs with
the -n, because the value of the result is a signed int (no promotions or conversions) and that value is overflowed. Does that make sense?
Can a "value" overflow just like objects can?

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?
Isn't this straight out of KnR2, Exercise 3-4?

Basically, you're right, in two's complement, the absolute value of
INT_MIN is one greater than INT_MAX. Therefore, setting int i = INT_MIN
* -1; results in overflow (in two's complement).

In the itoa function above,
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
runs once, and then the while loop ends because n is still negative
because of the overflow.
The '-' is added:
if (sign < 0)
s[i++] = '-';

and then the string is terminated and reversed.
There are many ways to write this function, you just have to catch the
case of INT_MIN, either explicitly, e.g.:

if(n == INT_MIN) /* do something to prevent overflow */

or implicitly in a way that converts the INT_MIN into something safe to
assign into an integer.

[Jonathan Bartlett]

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

You'll probably have to generate a special exception for INT_MIN, or
modify your algorithm.

The overflow happens to the value itself, so you can't save it by using
it before storing it in a variable (I think that was what you were asking).

However, a better method would probably be to not take the absolute
value. Just use it as a negative, and change your while to be

while((n /= 10) != 0)

Jon
----
Learn to program using Linux assembly language
http://www.cafeshops.com/bartlettpublish.8640017

[Ian Pilcher]

TTroy wrote:

void itoa(int n, char s[])

Others have addressed your specific question. I'd like to point out
that this is a poorly designed interface. You almost certainly want
to do something like:

void itoa(int n, char s[], size_t size)

--
================================================== ======================
Ian Pilcher i.*******@comcast.net
================================================== ======================

[pete]

Ian Pilcher wrote:

TTroy wrote:

void itoa(int n, char s[])

Others have addressed your specific question. I'd like to point out
that this is a poorly designed interface. You almost certainly want
to do something like:

void itoa(int n, char s[], size_t size)

void itoa(int n, char s[]); is from K&R

--
pete

[Luke Wu]

TTroy wrote:

Hello, can anyone explain why the following function will not work for INT_MIN:
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;

if((sign = n) < 0) /* record sign */
n = -n; /* make n positive */

i = 0;
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */

if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s); /* another function; irrelevant to my question */
}

I've narrowed it down to the n = -n line. On my machine, -(INT_MIN)
would be 1 more than INT_MAX. Does this overflow the temporary value
-n, or the actual object n. What I'm trying to ask is, when the fault happens?

My feeling is that the fault (undefined behaviour) first occurs with
the -n, because the value of the result is a signed int (no promotions or conversions) and that value is overflowed. Does that make sense?
Can a "value" overflow just like objects can?

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

The value is overflowing like others have said. You have to check for
n == INT_MIN and deal with it accordingly

Here is a version of itoa I just coded, a couple tests show it's
rock-solid but there could be portability issues:
void itoa(int n, char *s)
{
int i = 0
int sign;

if((sign = n) == INT_MIN){ /* if n is overflow possible */
n = -(n + 10); /* add 1 to tens column then negate */
s[i++] = n % 10 + '0'; /* gets digit from ones column */
n = n/10 + 1; /* shifts out ones col then adds 1 */
}
else if(n < 0){ /* if n is not overflow possible */
n = -n; /* makes n positive */
}

do{
s[i++] = n % 10 + '0'; /* gets digit from ones column */
} while ((n /= 10) != 0); /* shifts out ones column */

if (sign < 0) /* if n was originally negative */
s[i++] = '-'; /* add negative sign to string */

s[i] = '\0'; /* adds NUL termination to string */
reverse(s); /* reverses string to proper form */
}
As others have said, if you intend to use a similar function in serious
programs or save it for reuse with multiplie programs, it's dangerous
to work on a string within a function without knowing how much room has
been allocated for it. You really should add a third parameter to the
function, so the caller can pass in the size of the string (at issue is
whether the size will include space for NUL or not).

[pete]

davebsr wrote:

Basically, you're right, in two's complement, the absolute value of
INT_MIN is one greater than INT_MAX.
INT_MIN is allowed to be equal to -INT_MAX in two's complement.
if(n == INT_MIN) /* do something to prevent overflow */

(-INT_MAX > n) is the special case.

--
pete

[Peter Nilsson]

> TTroy wrote:

void itoa(int n, char s[])

This has been done to death. Search the clc archives for...

"itoa in pure c"

Ian Pilcher wrote: Others have addressed your specific question. I'd like to point
out that this is a poorly designed interface. You almost certainly
want to do something like:

void itoa(int n, char s[], size_t size)

There is a limit on how big an int's decimal representation can be.
I'd prefer a slighter faster itoa that expects an appropriate buffer.
[C has never been a language for the faint hearted. ;-]

--
Peter

[Luke Wu]

davebsr wrote:

Basically, you're right, in two's complement, the absolute value of
INT_MIN is one greater than INT_MAX. Therefore, setting int i = INT_MIN * -1; results in overflow (in two's complement).

In the itoa function above,

do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */
runs once, and then the while loop ends because n is still negative
because of the overflow.

Overflow causes undefined behaviour. You are 'assuming' that the
implementation just "wraps" numbers/bits like modular arithmetic and
allows the program to continue to assume that the bits held in the
signed integer is a valid/usable number.

The '-' is added:

if (sign < 0)
s[i++] = '-';

and then the string is terminated and reversed.
There are many ways to write this function, you just have to catch

the case of INT_MIN, either explicitly, e.g.:

if(n == INT_MIN) /* do something to prevent overflow */
yeap

or implicitly in a way that converts the INT_MIN into something safe to assign into an integer.

I'm not sure about that (can't think of an implicit method that works).

[Michael Mair]

Romeo Colacitti wrote:
[snip]

I still think there is
an issue, though most computers will behave properly: the result of n %
10 is implementation defined because n could be negative (but any sane
compiler will produce the result most people expect)

Results like -18 % 10 = 8 are expected on any good implementation.

If anything, -18%10 == -8 or -18%10 == 2.
Either C standard makes it very clear what is to be expected:
If a/b is representable, then
(a/b)*b + a%b == a
The problem is what a/b gives you for either a or b negative.
C89 says it is implementation defined whether you get the next
larger or next smaller integer.
That is:
-18/10 -> -1, i.e. -1*10 + -18%10 == -18, i.e. -18%10 == -8
-18/10 -> -2, -2*10 + -18%10 == -18, -18%10 == 2

C99 explicitly demands truncation towards zero for a/b, i.e.
you will get -18%10 == -8.
Cheers
Michael
--
E-Mail: Mine is an /at/ gmx /dot/ de address.

[CBFalconer]

TTroy wrote:

Hello, can anyone explain why the following function will not work for
INT_MIN:

/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;

if((sign = n) < 0) /* record sign */
n = -n; /* make n positive */

i = 0;
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */

if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s); /* another function; irrelevant to my question */
}

I've narrowed it down to the n = -n line. On my machine, -(INT_MIN)
would be 1 more than INT_MAX. Does this overflow the temporary value
-n, or the actual object n. What I'm trying to ask is, when the fault
happens?

My feeling is that the fault (undefined behaviour) first occurs with
the -n, because the value of the result is a signed int (no promotions
or conversions) and that value is overflowed. Does that make sense?
Can a "value" overflow just like objects can?

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

You can split off and handle INT_MIN separately, or make the
function use only negative values, or you can record the sign and
then convert to unsigned operands.

unsigned int v;

sign = (n < 0);
v = n;
/* do the rest using v in place of n */

however it is easier to have a master routine that converts
unsigned long, and to call it from the other conversion mechanisms
for other sizes. Maybe long long today.

--
"If you want to post a followup via groups.google.com, don't use
the broken "Reply" link at the bottom of the article. Click on
"show options" at the top of the article, then click on the
"Reply" at the bottom of the article headers." - Keith Thompson

[Lawrence Kirby]

On Mon, 07 Feb 2005 14:46:32 -0800, Luke Wu wrote:

....

There are many ways to write this function, you just have to catch

the

case of INT_MIN, either explicitly, e.g.:

if(n == INT_MIN) /* do something to prevent overflow */

yeap

Although n < -INT_MAX is the more precise test. There's no need to execute
the special case code on platforms where INT_MIN == -INT_MAX, although it
does no harm.

or implicitly in a way that converts the INT_MIN into something safe

to

assign into an integer.

I'm not sure about that (can't think of an implicit method that works).

Well positive_n = -(type)n works if type is a signed or unsigned integer
type where -INT_MIN is representable. Even a floating point type would
work if it has full (exact) coverage of integers in the range. The problem
is finding suh a type portably.

Lawrence

[David Resnick]

pete wrote:

Ian Pilcher wrote:

TTroy wrote:

void itoa(int n, char s[])

Others have addressed your specific question. I'd like to point out
that this is a poorly designed interface. You almost certainly want
to do something like:

void itoa(int n, char s[], size_t size)

void itoa(int n, char s[]); is from K&R

I suppose that makes it holy writ? But I agree that it is wise for
the function to take a size. My belief is that any function that is
handed a pointer to a buffer that it is going to fill in should know how
big it is. Even itoa. If optimization shows that using the size is a
bottleneck (doubt it) well, you could ignore it in your actual
implementation. I've seen too much code like this:

char buf[12];
itoa(my_int, buf);

Surely 12 is big enough. Until we switch to a 64 bit ints, etc etc.

-David

[Tim Rentsch]

"TTroy" <ti*****@gmail.com> writes:

[snip]
/* itoa: convert n to characters in s */
void itoa(int n, char s[])
{
int i, sign;

if((sign = n) < 0) /* record sign */
n = -n; /* make n positive */

i = 0;
do /* generate digits in reverse order */
{
s[i++] = n % 10 + '0'; /* get next digit */
} while ((n /= 10) > 0); /* delete it */

if (sign < 0)
s[i++] = '-';

s[i] = '\0';
reverse(s); /* another function; irrelevant to my question */
}

[snip]

Does anyone know how to fix this function to allow it to accept any
integer argument (including INT_MIN on 2's complement machines)?

The following function works in C99, and in ANSI C on implementations
that divide truncating towards zero:

void
itoa( const int n, char *s ){
static const char *digits = "9876543210123456789" + 9;
int t = n;
char *p = s;

do *p++ = digits[ t%10 ]; while( t /= 10 );
if( n < 0 ) *p++ = '-';
*p = 0;

reverse( s );
}
If you need something that works on implementations that divide
truncating towards minus infinity, try the following. I believe it
works on C89/C90 as long as '%' and '/' are appropriately in sync
(that is, (m/n)*n + m%n = m, whenever n != 0); but I've done
careful testing only with truncation towards zero and truncation
towards minus infinity.

void
more_general_itoa( const int n, char *s ){
static const char *digits = "9876543210987654321" + 9;
int r, t = n < 0 ? n : -n;
char *p = s;

do *p++ = digits[ r = t%10 ]; while( t = t/10 + (r > 0) );
if( n < 0 ) *p++ = '-';
*p = 0;

reverse( s );
}

Notice that the second function avoids problems with INT_MIN by
always switching to a *negative* representation.