Solved

Algorithm in Detecting Integer Overflows in C (on Unix)

Posted on 1998-02-23
8
428 Views
Last Modified: 2008-02-01
How do I detect integer overflows in C, on Unix.  The following is a sample code.

#include <stdio.h>

void main(void)
{
   unsigned short int op1, op2, answer;

   op1 = 65500;
   op2 = 10;
   answer = op1 * op2;
}

Is there a way that I can detect and prompt the user that the data being used to compute the multiplication in line #9 WILL CAUSE an integer overflow if computed.  Is there any algorithm or method in detecting this ?
The algorithm I use must be able to handle unsigned long int as operand types instead of unsigned short int too !!!
Please help !! thanks
0
Comment
Question by:rdosani
8 Comments
 
LVL 16

Expert Comment

by:imladris
ID: 1257345
There are no direct methods provided by C for detecting overflow, as I'm guessing you're aware, since you're asking for an algorithm. So, once the primitive operation op1*op2 has occurred the fat is already in the fire. There are two alternatives I can think of:

1. If portability is not a concern, you could probably use assembler to examine the overflow bit directly (probably since it depends on the tools you have available), and do something relevant if you determine that it has been set.

2. Implement the multiplication by hand, i.e. as repetitive addition. E.g. take the largest number, add it to an accumulator the number of times indicated by the smallest number. Before each addition check that the difference between MAXINT (65536 in the case of unsigned short) and the number being added is less than the number being added. If not you will get an overflow, i.e.

if(MAXINT-largeop<largeop)dooverflowwarning();


0
 

Author Comment

by:rdosani
ID: 1257346
I don't specifically have to use mutiplication.  Any operator should work for my algorithm.  It should be operator independent.  It should be able to handle (+ - / *) anything, and still detect an overflow. Example, What if I use addition instead of multiplication. For example
op1 = 65500;
op2 = 10000;
** Note **
At this point in the code.  I should realize that adding these two number will cause an overflow, and hence prompt the user that an overflow has occured.  Question is how do I realize this ?
ans = op1 + op2;
What then ? Your solution will not work for addition ?
Yes portability is a concern.  I can't use assembler only C
I realize I need some sort of algorithm in detecting this ?  I know there is not simple way around it.
0
 
LVL 16

Expert Comment

by:imladris
ID: 1257347
Carrying on along these lines the solution would be to code seperate checks for each operation (there's only 4 of them).
For addition:
     if(MAXINT - op1<op2) dooverflow();

For subtraction:
    if(op2>op1)dounderflow()

For multiplication as specified.

For division:
    if(op2==0)dodividebyzero();

0
Complete VMware vSphere® ESX(i) & Hyper-V Backup

Capture your entire system, including the host, with patented disk imaging integrated with VMware VADP / Microsoft VSS and RCT. RTOs is as low as 15 seconds with Acronis Active Restore™. You can enjoy unlimited P2V/V2V migrations from any source (even from a different hypervisor)

 
LVL 1

Accepted Solution

by:
jcea earned 100 total points
ID: 1257348
Unsigned integer arithmetic:

if(op1+op2<op1) add_overflow();

if(op1-op2>op1) sub_overflow();

if((!op2)&&(MAXINT/op2>op1) mul_overflow(); /* Try op1*op2=MAXINT */

Integer division has no overflow (unless divide by zero).
0
 
LVL 16

Expert Comment

by:imladris
ID: 1257349
You are right. I wrote mi answer without atention. Try (second round :-):

Unsigned integer arithmetic:

if(op1+op2<op1) add_overflow();
if(op1<op2) sub_overflow();
if((op2)&&(MAXINT/op2<op1-1) mul_overflow(); /* Try op1*op2=MAXINT */

Integer division has no overflow (unless divide by zero).
0
 
LVL 1

Expert Comment

by:jcea
ID: 1257350
Sorry, I see what jcea is doing now. He had the comparison reversed too. If it's flipped (or the clauses):

if((op2) && op1>(MAXINT/op2)) dooverflow();

it works admirably.

0
 
LVL 16

Expert Comment

by:imladris
ID: 1257351
You can also test to see if the opposite function yields the same results.

result = X + Y;
if( result/X != Y && result/Y != X )  /* overflow */

This assumes that you just want to know about the overflow and are not looking to head it off at the pass.
0
 
LVL 4

Expert Comment

by:emmons
ID: 1257352
Uhm, of course that should have been
result = X * Y
0

Featured Post

What is SQL Server and how does it work?

The purpose of this paper is to provide you background on SQL Server. It’s your self-study guide for learning fundamentals. It includes both the history of SQL and its technical basics. Concepts and definitions will form the solid foundation of your future DBA expertise.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: I’ve never tri…
An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

803 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question