Can a "value" overflow?

[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

 

[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 = '\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]

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 = '\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 = '\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]

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.

 

[Ian Pilcher]

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)

 

[pete]

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

 

[Luke Wu]

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 = '\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 = '\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.

 

[Peter Nilsson]

void itoa(int n, char s[])

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

"itoa in pure c"

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. ;-]

 

[Luke Wu]

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

 

[CBFalconer]

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 = '\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.

 

[Lawrence Kirby]

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

....

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.

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]

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]

[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 = '\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.