LinuxQuestions.org
Download your favorite Linux distribution at LQ ISO.
Go Back   LinuxQuestions.org > Forums > Non-*NIX Forums > Programming
User Name
Password
Programming This forum is for all programming questions.
The question does not have to be directly related to Linux and any language is fair game.

Notices



Reply
 
Search this Thread
Old 04-03-2003, 06:28 AM   #1
tda
Member
 
Registered: Mar 2002
Location: Ukraine, Kiev
Distribution: Mandrake 7.2
Posts: 37

Rep: Reputation: 15
Question math overflow error


Hello ALL
I've a question. How to do detection of mathematical overflow error in C programs. Suppose a program has follofind code:

int a = 345335;
int b = 34543;
int c = a * b;

How to detect in independet platform/os/compiler form that result c is correct and not overfloved? Are there any standart methods in ANSI C?

Thenks for any propositions.
 
Old 04-03-2003, 08:07 AM   #2
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
There is no overflow in unsigned arithmetic. If one operand is unsigned and the other is signed, than the signed is converted into unsigned. Overflow can occur if both operands are signed.

Code:
if ( (unsigned) a + (unsigned) b > INT_MAX )
  complain();
INT_MAX is defined in <limits.h>

see book: C Traps and Pitfalls
 
Old 04-03-2003, 08:12 AM   #3
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
Also this:
Code:
if ( a > INT_MAX - b )
 complain();
Which doesn't involve using unsigned casts.
 
Old 04-03-2003, 08:30 AM   #4
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
Well, at least that's what the book said.
 
Old 04-03-2003, 08:40 AM   #5
tda
Member
 
Registered: Mar 2002
Location: Ukraine, Kiev
Distribution: Mandrake 7.2
Posts: 37

Original Poster
Rep: Reputation: 15
Quote:
Originally posted by GtkUser
[B]There is no overflow in unsigned arithmetic.[B]
Hmmm...
Suppose type int has 16 bit capacity. Therefore maximal unsigned int is 2^16 - 1 = 65535. Suppose have two vars:

unsigned int a = 60000;
unsigned int b = 40000;

and want to add a to b:

unsigned int c = a + b;

Correct result in this case is 100000 but var c due to 16 bit capacity will contain incorrect val 44465.

How to detect this situation???
In simplest cases when used only '+' and '-' operations I can try detect overflow with help of INT_MIN/MAX. But what about other mathematical operations '/', '*', '%' etc?

P.S. Thenks for reference to book. I try to find it.
 
Old 04-03-2003, 08:54 AM   #6
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
What are the results of this program on your system?
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  printf("%d\n", INT_MAX);
  return 0;
 
}
 
Old 04-03-2003, 09:10 AM   #7
tda
Member
 
Registered: Mar 2002
Location: Ukraine, Kiev
Distribution: Mandrake 7.2
Posts: 37

Original Poster
Rep: Reputation: 15
Quote:
Originally posted by GtkUser
What are the results of this program on your system?
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  printf("%d\n", INT_MAX);
  return 0;
 
}

OK

I use x386 linux box and INT_MAX in limits.h defined as 2147483647.
 
Old 04-03-2003, 09:14 AM   #8
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
My computer gives me: 2147483647
So that is the max.

Now I run this program:
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}
And The output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0

So there is some overflow! The last couple of multiples of 2.

Now I revise the program by adding the overflow check:
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      if (! ( (unsigned) sum * (unsigned) x > INT_MAX) )
        sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}
And this output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
1073741824
1073741824

So in other words, there was no buffer overflow.

Last edited by GtkUser; 04-03-2003 at 09:15 AM.
 
Old 04-03-2003, 09:36 AM   #9
tda
Member
 
Registered: Mar 2002
Location: Ukraine, Kiev
Distribution: Mandrake 7.2
Posts: 37

Original Poster
Rep: Reputation: 15
Quote:
Originally posted by GtkUser
My computer gives me: 2147483647
So that is the max.

Now I run this program:
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}
And The output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
-2147483648
0

So there is some overflow! The last couple of multiples of 2.

Now I revise the program by adding the overflow check:
Code:
#include<stdio.h>
#include<limits.h>
 
int main() {
 
  int i;
  int x = 2;
  int sum = 1;
 
  for ( i = 0; i < 32; ++i )
    {
      if (! ( (unsigned) sum * (unsigned) x > INT_MAX) )
        sum *= x;
      printf("%d\n", sum);
    }
  return 0;
 
}
And this output is:
2
4
8
16
32
64
128
256
512
1024
2048
4096
8192
16384
32768
65536
131072
262144
524288
1048576
2097152
4194304
8388608
16777216
33554432
67108864
134217728
268435456
536870912
1073741824
1073741824
1073741824

So in other words, there was no buffer overflow.
This is work Many thanks. But is this approach correct???
I can guess that expression (unsigned) sum * (unsigned) x is calculated in FPU with 64/80 bit precise. But I think that on more weak hard (suppose 8088) this code will return incorrect result.
Moreover on your PC it can produce error result if result of expression will be more than 2^80.
 
Old 04-03-2003, 10:01 AM   #10
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
It is supposed to be correct, for all implementations that define an INT_MAX in <limits.h>

The book says that all unsigned operations are done modulo 2^n, where n is the number of bits in the result. It says that there is no such thing as overflow in unsigned arithmetic.

If you can, test is out on other architectures before deploying. I don't know the mathematical details. I am just going by the book, and I only figured out this example to demonstrate it.
 
Old 04-03-2003, 10:02 AM   #11
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
The book says that this is the WRONG approach:
Code:
if (a + b < 0 )
  complain();
 
Old 04-03-2003, 11:29 AM   #12
GtkUser
Member
 
Registered: Sep 2002
Location: Canada
Distribution: Redhat 9.0
Posts: 637

Rep: Reputation: 30
If you want definitive answers than go here: < http://groups.google.com/groups?group=comp.lang.c >.
 
Old 04-03-2003, 11:43 AM   #13
wapcaplet
Guru
 
Registered: Feb 2003
Location: Colorado Springs, CO
Distribution: Gentoo
Posts: 2,018

Rep: Reputation: 48
One method I've used to check in advance whether overflow will occur is:

Code:
int x;
int y;

// other stuff, assigns some values to x and y

if ( x < INT_MAX - y )
  z = x + y;
else
  complain();
or:

Code:
// ...
if ( x < INT_MAX / y )
  z = x * y;
else
  complain();
Granted, in a way this involves doing the computation twice, but this will at least make sure x+y (or x*y in the second example) is less than INT_MAX before doing the calculation. (Hope this makes sense... if you know your algebra, it will )
 
  


Reply


Thread Tools Search this Thread
Search this Thread:

Advanced Search

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
error while accessing math functions in kernel modules dypgrp Programming 0 01-19-2005 10:12 AM
"neighbor table overflow" error on 9.2 network install jordan0 Mandriva 0 04-08-2004 03:53 PM
Neighbor Table Overflow error snowmonkey Linux - Software 1 11-04-2003 05:10 PM
Can you find the error ? (160 lines) math-cases etc Dimitris Programming 5 09-02-2003 05:42 PM
buffer overflow cxel91a Programming 3 08-14-2003 06:23 PM


All times are GMT -5. The time now is 09:53 PM.

Main Menu
My LQ
Write for LQ
LinuxQuestions.org is looking for people interested in writing Editorials, Articles, Reviews, and more. If you'd like to contribute content, let us know.
Main Menu
Syndicate
RSS1  Latest Threads
RSS1  LQ News
Twitter: @linuxquestions
identi.ca: @linuxquestions
Facebook: linuxquestions Google+: linuxquestions
Open Source Consulting | Domain Registration