integer overflow in atoi

[happy]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

 

[Tom St Denis]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
  int i, num;
  for( num = 0, i = 0 ; isdigit(str) ; i++)
      num = num * 10 + str - '0' ;
  return num;

}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

The usual way would be to check to ensure that num < (num * 10 +
value). I don't think that's 100% portable but for all practical
purposes it's just fine.

Tom

 

[news.telesweet.net]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;

}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

The usual way would be to check to ensure that num< (num * 10 +
value). I don't think that's 100% portable but for all practical
purposes it's just fine.

Tom

Except that that doesn't work. Take for example (assuming 32-bit ints)
num = 0x40000000. Then num*10 = 0x80000000 after the overflow, which is
still bigger than num.

The best I can come up with is to compare num with ((num * 10 + value) -
value)/10. If they are equal then the inner paranthetical expression
didn't overflow. If not then it did. To be explicit:

int atoi(char str[])
{
int i, num, numtemp;
for( num = 0, i = 0 ; isdigit(str) ; i++)
{
numtemp = num
num = num * 10 + str - '0' ;
if(numtemp != ((num - str) + '0')/10)
{
/* Overflow */
}
}
return num;
}

 

[Jens Thoms Toerring]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

You could check if num is larger than INT_MAX / 10 before you
multiply it by 10. If that isn't the case and num has been mul-
tiplied by 10 you then have to check if INT_MAX minus the new
digit is not smaller than 'num'. Another way would be to do a
string comparison on 'str' (but only the part that contains
numbers!) to a stringified version of INT_MAX, obtained defi-
ning the macros

#define _STRFY( x ) #x
#define STRFY( x ) _STRFY( x )

and using something like

if ( strlen( str ) > strlen( STRFY( INT_MAX ) )
|| strcmp( str, STRFY( INT_MAX ) ) > 0 )
puts( "overflow" );

Reporting an overflow back to the user could be done in the same
way strtol() does it, i.e. passing back INT_MAX and setting errno
to ERANGE.
Regards, Jens

 

[news.telesweet.net]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;

}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

The usual way would be to check to ensure that num< (num * 10 +
value). I don't think that's 100% portable but for all practical
purposes it's just fine.

Tom

Except that that doesn't work. Take for example (assuming 32-bit ints)
num = 0x40000000. Then num*10 = 0x80000000 after the overflow, which is
still bigger than num.

The best I can come up with is to compare num with ((num * 10 + value) -
value)/10. If they are equal then the inner paranthetical expression
didn't overflow. If not then it did. To be explicit:

int atoi(char str[])
{
int i, num, numtemp;
for( num = 0, i = 0 ; isdigit(str) ; i++)
{
numtemp = num
num = num * 10 + str - '0' ;
if(numtemp != ((num - str) + '0')/10)
{
/* Overflow */
}
}
return num;
}

I must be exhausted. The example above only works for unsigned ints.
For signed ints try num = 0x20000000. Then num*10 = 0x40000000 after
the overflow and the same considerations apply.

 

[Tom St Denis]

I want to implement atoi function which converts string to an integer.
So I did this :
int atoi(char str[])
{
   int i, num;
   for( num = 0, i = 0 ; isdigit(str) ; i++)
       num = num * 10 + str - '0' ;
   return num;
}
Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

The usual way would be to check to ensure that num<  (num * 10 +
value).  I don't think that's 100% portable but for all practical
purposes it's just fine.

Tom

Except that that doesn't work.  Take for example (assuming 32-bit ints)
num = 0x40000000.  Then num*10 = 0x80000000 after the overflow, which is
still bigger than num.

Except it does work...

tstdenis@photon:~$ cat test.c
#include<stdio.h>
#include<limits.h>
int main (void)
{
int a;
a = INT_MAX/10;
printf("%d %d %d\n", a < (a * 10), a, a*10);
++a;
printf("%d %d %d\n", a < (a * 10), a, a*10);
return 0;
}
tstdenis@photon:~$ ./test
1 214748364 2147483640
0 214748365 -2147483646

The second case fails since a is not less than a*10 which means an
overflow occurred.

Tom

 

[Tom St Denis]

I want to implement atoi function which converts string to an integer..
So I did this :
int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}
Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

The usual way would be to check to ensure that num < (num * 10 +
value).  I don't think that's 100% portable but for all practical
purposes it's just fine.

Yes, it's just fine, other than the fact that it doesn't work.  For example,
assume a platform with 32 bit two's complement int's, and which does
overflow handling by discarding the high order bits.  Then, on the last
iteration of computing:

   atoi( "5000000000" )

num will initially be 500000000, and then num*10+value will be 705032704;
because 705032704>500000000, overflow will not be detected.

Am I missing something here? neither of 0x1DCD6500 or 0x2A05F200 are
too big for a 32-bit int. Why would there be an overflow?

tstdenis@photon:~$ cat test.c
#include<stdio.h>
#include<limits.h>
int main (void)
{
int a;
a = 500000000; INT_MAX/10;
printf("%d %d %d\n", a < (a * 10), a, a*10);
++a;
printf("%d %d %d\n", a < (a * 10), a, a*10);
return 0;
}
tstdenis@photon:~$ ./test
1 500000000 705032704
1 500000001 705032714

Which is exactly what I would expect happen... They're both in range
and return true for the test a < (a*10 + v).

Tom

 

[Tom St Denis]

I want to implement atoi function which converts string to an integer.
So I did this :
int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}
Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?
The usual way would be to check to ensure that num < (num * 10 +
value).  I don't think that's 100% portable but for all practical
purposes it's just fine.

Yes, it's just fine, other than the fact that it doesn't work.  For example,
assume a platform with 32 bit two's complement int's, and which does
overflow handling by discarding the high order bits.  Then, on the last
iteration of computing:

   atoi( "5000000000" )

num will initially be 500000000, and then num*10+value will be 705032704;
because 705032704>500000000, overflow will not be detected.

Am I missing something here?  neither of  0x1DCD6500 or 0x2A05F200 are
too big for a 32-bit int.  Why would there be an overflow?

tstdenis@photon:~$ cat test.c
#include<stdio.h>
#include<limits.h>
int main (void)
{
int a;
a = 500000000; INT_MAX/10;
printf("%d %d %d\n", a < (a * 10), a, a*10);
++a;
printf("%d %d %d\n", a < (a * 10), a, a*10);
return 0;}

tstdenis@photon:~$ ./test
1 500000000 705032704
1 500000001 705032714

Which is exactly what I would expect happen...  They're both in range
and return true for the test a < (a*10 + v).

Here is the algorithm "not working" ... (ignore the use of sprintf, I
wasn't thinking and/or I'm busy at work ya ... that's it)

tstdenis@photon:~$ cat test.c
#include<stdio.h>
#include<limits.h>

int t_atoi(char *s)
{
int tmp, num = 0;
while (*s) {
tmp = num; num = num * 10 + *s++ - '0';
if (tmp > num) { printf("OVERFLOW\n"); }
}
return num;
}

int main(void)
{
char buf[64];
sprintf(buf, "%lu", (unsigned long)INT_MAX);
printf("%d\n", t_atoi(buf));
sprintf(buf, "%lu", (unsigned long)INT_MAX + 1);
printf("%d\n", t_atoi(buf));
return 0;
}

tstdenis@photon:~$ ./test
2147483647
OVERFLOW
-2147483648

Tom

 

[Willem]

Richard Heathfield wrote:
) The maximum value num can legally have is INT_MAX.
)
) The maximum value str can have (within the loop) is '9', so str -
) '0' is at most 9. Therefore, the result of num * 10 can't exceed INT_MAX
) - 9, so num mustn't exceed (INT_MAX - 9) / 10.

And what if a user enters a number that's (almost) exactly INT_MAX ?
You're trading simplicity for a slightly shorter range.

Perhaps you could precalculate two sentinels, and if you're inbetween
do the exact calculation.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[dgiaimo]

I want to implement atoi function which converts string to an integer.
So I did this :
int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}
Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?
The usual way would be to check to ensure that num < (num * 10 +
value).  I don't think that's 100% portable but for all practical
purposes it's just fine.

Yes, it's just fine, other than the fact that it doesn't work.  For example,
assume a platform with 32 bit two's complement int's, and which does
overflow handling by discarding the high order bits.  Then, on the last
iteration of computing:

   atoi( "5000000000" )

num will initially be 500000000, and then num*10+value will be 705032704;
because 705032704>500000000, overflow will not be detected.

Am I missing something here?  neither of  0x1DCD6500 or 0x2A05F200 are
too big for a 32-bit int.  Why would there be an overflow?

tstdenis@photon:~$ cat test.c
#include<stdio.h>
#include<limits.h>
int main (void)
{
int a;
a = 500000000; INT_MAX/10;
printf("%d %d %d\n", a < (a * 10), a, a*10);
++a;
printf("%d %d %d\n", a < (a * 10), a, a*10);
return 0;}

tstdenis@photon:~$ ./test
1 500000000 705032704
1 500000001 705032714

Which is exactly what I would expect happen...  They're both in range
and return true for the test a < (a*10 + v).

Tom

Look very carefully at what _you_ just wrote:

For a = 500000000:

(1) a < (a * 10) evaluated to 1

(2) a evaluated to 500000000

(3) a * 10 evaluated to 705032714

Last time I checked 500000000 * 10 = 5000000000, not 705032714.
Therefore
you overflowed. However, your test (see line (1)) would imply that no
overflow occurred. I don't think I can make this any simpler.

 

[Tom St Denis]

0x1DCD6500 == 5000000000 fits into a 32-bit int, however 10*5000000000+0 ==
0x12A05F200 does not.  The CPU handles the overflow by discarding the high
order bits, giving 0x2A05F200 == 705032704.  So, in this specific case, an
overflow happens that is not detected by your test.

The real problem [other than I shouldn't be posting to usenet over
lunch] is gcalc betrayed me and truncated the result.



Tom

 

[Ian Collins]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

If you want to report an error, don't implement atoi (which doesn't
indicate failure), implement strtol, which does.

 

[Keith Thompson]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

You could check if num is larger than INT_MAX / 10 before you
multiply it by 10. If that isn't the case and num has been mul-
tiplied by 10 you then have to check if INT_MAX minus the new
digit is not smaller than 'num'. Another way would be to do a
string comparison on 'str' (but only the part that contains
numbers!) to a stringified version of INT_MAX, obtained defi-
ning the macros

#define _STRFY( x ) #x
#define STRFY( x ) _STRFY( x )

and using something like

if ( strlen( str ) > strlen( STRFY( INT_MAX ) )
|| strcmp( str, STRFY( INT_MAX ) ) > 0 )
puts( "overflow" );

Reporting an overflow back to the user could be done in the same
way strtol() does it, i.e. passing back INT_MAX and setting errno
to ERANGE.

The string comparison trick only works if INT_MAX is defined as a
decimal constant. It merely has to be a constant expression of type
int. For example, <limits.h> could plausibly have:

#define INT_MAX 0x7fffffff

 

[Keith Thompson]

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

Apart from the other comments you've gotten, the identifier "atoi"
is always reserved for use as an external identifier. If you write
your own function with that name (unless you declare it static),
the behavior is undefined. For example, a call might quietly call
the system's atoi() function rather than yours.

If you're writing your own atoi() function as an exercise, pick a
different name (unless you're implementing the C standard library).

strtol(), also in the standard, is much better in terms of error
handling, though it's a little complicated to use. A friendlier
wrapper around strtol() might be a nice thing to have.

 

[Jens Thoms Toerring]

The string comparison trick only works if INT_MAX is defined as a
decimal constant. It merely has to be a constant expression of type
int. For example, <limits.h> could plausibly have:

#define INT_MAX 0x7fffffff

Right, what a pity;-) But with a bit more of effort I guess it
can still be made to work:

char im[ ( CHAR_BIT * sizeof( int ) ) / 3 + 1 ];
sprintf( im, "%d\n", INT_MAX );
if ( strlen( str ) > strlen( im ) || strcmp( str, im ) > 0 )
puts( "overflow" );
Regards, Jens

 

[Phil Carmody]

You just made that up.

No he didn't. He plucked it mostly from the standard. OK,
from the bit of the standard that describes the behaviour of
strtol rather than ato[il].

Phil

 

[jacob navia]

happy a écrit :

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

Use a double for comparing num*10 against INT_MAX:

double d = num;
if (d*10 > INT_MAX)
etc

jacob

 

[Ben Pfaff]

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?

if (num > INT_MAX / 10) {
...handle overflow...
}

 

[Keith Thompson]

happy a écrit :

I want to implement atoi function which converts string to an integer.
So I did this :

int atoi(char str[])
{
int i, num;
for( num = 0, i = 0 ; isdigit(str) ; i++)
num = num * 10 + str - '0' ;
return num;
}

Here I wnat to know is there any way to tell user if num goes out of
range of int ?
I mean we can't check num after overflow as it will be UB so is there
a way to check if str[] contains large integer ?

Use a double for comparing num*10 against INT_MAX:

double d = num;
if (d*10 > INT_MAX)
etc

That can fail if double has fewer value bits than int does (e.g., if
int and double are both 64 bits).

Aside from that, I'd write the above as:

if (num * 10.0 > INT_MAX) /* ... */

 

[bartc]

The string comparison trick only works if INT_MAX is defined as a
decimal constant. It merely has to be a constant expression of type
int. For example, <limits.h> could plausibly have:

#define INT_MAX 0x7fffffff

Right, what a pity;-) But with a bit more of effort I guess it
can still be made to work:

char im[ ( CHAR_BIT * sizeof( int ) ) / 3 + 1 ];
sprintf( im, "%d\n", INT_MAX );
if ( strlen( str ) > strlen( im ) || strcmp( str, im ) > 0 )
puts( "overflow" );

I use a similar technique in a real application. But I only do the strcmp()
test when both strings are the same length, otherwise it goes wrong I think.