Solved

Algorithm in Detecting Integer Overflows in C (on Unix)

Posted on 1998-02-23
8
426 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
 
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
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
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

How to improve team productivity

Quip adds documents, spreadsheets, and tasklists to your Slack experience
- Elevate ideas to Quip docs
- Share Quip docs in Slack
- Get notified of changes to your docs
- Available on iOS/Android/Desktop/Web
- Online/Offline

Join & Write a Comment

Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Windows programmers of the C/C++ variety, how many of you realise that since Window 9x Microsoft has been lying to you about what constitutes Unicode (http://en.wikipedia.org/wiki/Unicode)? They will have you believe that Unicode requires you to use…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.

743 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

Need Help in Real-Time?

Connect with top rated Experts

9 Experts available now in Live!

Get 1:1 Help Now