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.*******@comca st.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).