Overflow check in C

Question

Will have

int a, b, c; // may be char or float, anything actually c = a + b; 

Let int be represented by 4 bytes. Say a + b requires 1 bit more than 4 bytes (i.e., suppose the result is 1 00 .... 0 (32 zeros, in binary)). This will result in C = 0, and I'm sure the computer microprocessor will set some kind of overflow flag. Is there a built-in method for checking this in C?

I am really working on creating a type of number with a length of 1024 bits (for example, int is a built-in type of number with a length of 32 bits). I tried using an unsigned char array with 128 elements. I also need to define the operations of adding and subtracting these numbers. I wrote the code to add, but I have a problem with subtraction. I don’t have to worry about getting negative results, because the way I will call the subtraction function always ensures that the subtraction result is always positive, but to implement the subtraction function I need to somehow get 2 additions to the subtraction, that is my own 1024 -bit number.

I apologize if it is difficult to understand my description. If necessary, I will clarify this. I include code for the add function and an incomplete subtraction function. NUM_OF_WORDS is a constant declared as

#define NUM_OF_WORDS 128

Please let me know if you do not understand my question or any part of my code.

PS: I don’t see how to upload attachments in this forum, so I am directing you to another site. My code can be found there

click on download on this page

By the way, I found this. I intend to replace INT_MAX by UCHAR_MAX , since my 1024-bit numbers consist of an array of char types (8-bit variable). Is this check sufficient for all cases?

Update:

Yes, I am working on cryptography.
I need to implement the Montgomery Multiplication routine for 1024-bit integers.
I also looked at using the GMP library, but I was not able to find out how to use it. I looked through the tutorial, and after several small modifications, I managed to compile the GMP project file in VC ++ 6, which resulted in a lot of .obj files, but now I'm not sure what to do with them. Nevertheless, it would be nice if I could write my own data types, as this will give me full control over how arithmetic operations work with my user data type, and I also need to be able to expand it from 1024 bits to large numbers to the future.

Answer 1

If you add unsigned numbers, you can do it

 c = a+b; if (c<a) { // you'll get here if and only if overflow has occurred } 

and you may even find that your compiler is smart enough to implement it by checking the overflow or carry flag, instead of doing additional comparisons. For example, I just filed this on gcc -O3 -S :

 unsigned int foo() { unsigned int x=g(), y=h(); unsigned int z = x+y; return z<0 ? 0 : z; } 

and got this for the key bit of code:

 movl $0, %edx addl %ebx, %eax cmovb %edx, %eax 

where you will not notice additional comparison instructions.

Answer 2

Contrary to popular belief, int overflow leads to undefined behavior. This means that after overflow a + b it makes no sense to use this value (or do something else, for that matter). A wrap is what most cars do in the event of an overflow, but they can also explode.

To check if int overflow will occur when adding two non-negative integers a and b , you can do the following:

 if (INT_MAX - b < a) { /* int overflow when evaluating a+b */ } 

This is due to the fact that if a + b > INT_MAX , then INT_MAX - b < a , but INT_MAX - b cannot overflow.

You will need to pay special attention to the case when b negative, which remains as an exercise for the reader;)

As for your actual goal: 1024-bit numbers have the same common problems, like 32-bit numbers. Perhaps it would be more promising to choose a completely different approach, for example. representing numbers, for example, linked lists of numbers, using a very large base B. Usually B is chosen in such a way that B = sqrt(INT_MAX) , so multiplying the numbers does not overflow the machine type int .

Thus, you can represent arbitrarily large numbers, where "arbitrary" means "limited only by the amount of available main memory."

Answer 3

If you work with unisigned numbers, then if a <= UINT_MAX , b <= UINT_MAX and a + b >= UINT_MAX , then c = (a + b) % UINT_MAX will always be less than a and b . And this is the only time this can happen.

This way you can detect overflow in this way.

 int add_return_overflow(unsigned int a, unsigned int b, unsigned int* c) { *c = a + b; return *c < a && *c < b; } 

Answer 4

Information that may be useful in this matter:

• Secure Coding in C and C ++
• IntSafe Library

Answer 5

You can create a solution for a specific function of C. According to the specification, when you add two unsigned ints, "the result is obtained according to the 2 ^ n module of the true result" ("C - A Reference Guide" from Harbison and Steele). This means that you can use some simple arithmetic checks to detect overflow:

 #include <stdio.h> int main() { unsigned int a, b, c; char *overflow; a = (unsigned int)-1; for (b = 0; b < 3; b++) { c = a + b; overflow = (a < b) ? "yes" : "no"; printf("%u + %u = %u, %s overflow\n", a, b, c, overflow); } return 0; } 

Answer 6

Just xor MSB of both operands and result. The result of this operation is an overflow flag.

But this will not show you whether the result is correct or not. (this may be the correct result even with overflow), for example, 3 + (-1) is 2 whit overflows.

To understand that using signed arithmetic you need to check if both opaids were the same characters (xor MSB).

Answer 7

As soon as you add 1 to INT_MAX, you will get INT_MIN (i.e. overflow).
In C, there is no reliable way to check for overflow, since all 32 bytes are used to represent an integer (not a status flag). You can only check whether the number you receive will be in the valid range, as in your link.

You will get answers suggesting to test if (c < a) , however, note that you can overflow the value of a and / or b to the point where adding them is more than (but still overflowing)