Integer overflow: Why doesn't something similar to "checked" from C# exist in C?

I was writing a program in C++ to find all solutions of ab = c, where a, b and c together use all the digits 0-9 exactly once. The program looped over values of a and b, and ran a digit-counting routine each time on a, b and ab to check if the digits condition was satisfied.

However, spurious solutions can be generated when ab overflows the integer limit. I ended up checking for this using code like:

unsigned long b, c, c_test; ... c_test=c*b;         // Possible overflow if (c_test/b != c) {/* There has been an overflow*/} else c=c_test;      // No overflow

Is there a better way of testing for overflow? I know that some chips have an internal flag that is set when overflow occurs, but I've never seen it accessed through C or C++.

Replay

There is a way to determine whether an operation is likely to overflow, using the positions of the most-significant one-bits in the operands and a little basic binary-math knowledge.

For addition, any two operands will result in (at most) one bit more than the largest operand's highest one-bit. For example:

bool addition_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits<32 && b_bits<32);
}

For multiplication, any two operands will result in (at most) the sum of the bits of the operands. For example:

bool multiplication_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a), b_bits=highestOneBitPosition(b);
return (a_bits+b_bits<=32);
}

Similarly, you can estimate the maximum size of the result of a to the power of b like this:

bool exponentiation_is_safe(uint32_t a, uint32_t b) {
size_t a_bits=highestOneBitPosition(a);
return (a_bits*b<=32);
}

(Substitute the number of bits for your target integer, of course.)

I'm not sure of the fastest way to determine the position of the highest one-bit in a number, here's a brute-force method:

size_t highestOneBitPosition(uint32_t a) {
size_t bits=0;
while (a!=0) {
++bits;
a>>=1;
};
return bits;
}

It's not perfect, but that'll give you a good idea whether any two numbers could overflow before you do the operation. I don't know whether it would be faster than simply checking the result the way you suggested, because of the loop in the highestOneBitPosition function, but it might (especially if you knew how many bits were in the operands beforehand).

I see you're using unsigned integers. By definition, in C (don't know about C++), unsigned arithmetic does not overflow ... so, at least for C, your point is moot :)

With signed integers, once there has been overflow, Undefined Behaviour has occurred and your program can do anything (for example: render tests inconclusive).

#include <limits.h>
int a = <something>;
int x = <something>;
a += x;              /* UB */
if (a < 0) {         /* unreliable test */
/* ... */
}

To create a conforming program you need to test for overflow before generating said overflow. The method can be used with unsigned integers too

#include <limits.h>
int a = <something>;
int x = <something>;
if ((x > 0) && (a > INT_MAX - x)) /* `a + x` would overflow */;
if ((x < 0) && (a < INT_MIN - x)) /* `a + x` would underflow */;
/* ... same thing for subtraction, multiplication, and division */

Clang 3.4+ and GCC 5+ offer checked arithmetic builtins. They offer a very fast solution to this problem, especially when compared to bit-testing safety checks.

For the example in OP's question, it would work like that:

unsigned long b, c, c_test;
if (__builtin_umull_overflow(b, c, &c_test))
{
// returned non-zero: there has been an overflow
}
else
{
// return zero: there hasn't been an overflow
}

The Clang documentation doesn't specify whether c_test contains the overflowed result if an overflow occurred, but the GCC documentation says that it does. Given that these two like to be __builtin-compatible, it's probably safe to assume that this is how Clang works too.

There is a __builtin for each arithmetic operation that can overflow (addition, subtraction, multiplication), with signed and unsigned variants, for normal sizes, long sizes, and long long sizes. The syntax for the name is __builtin_[us](operation)(l?l?)_overflow:

• u for unsigned or s for signed;
• operation is one of add, sub or mul;
• no l suffix means that the operands are ints; one l means long; two ls mean long long.

So for a checked signed long integer addition, it would be __builtin_saddl_overflow. The full list can be found on the Clang documentation page.

GCC 5 and above (but not Clang) additionally offer generic builtins that work without specifying the type of the values: __builtin_add_overflow, __builtin_sub_overflow and __builtin_mul_overflow.

The builtins lower to what's best for the platform. On x86, they check the overflow and sign flags.

Visual Studio's cl.exe does not have any equivalent, although you will be able to build Windows programs with Clang starting with VS2015. If that's an option to you, you could make small wrapper functions for the checked arithmetic builtins and build the rest with cl, as usual.

Some compilers provide access to the integer overflow flag in the CPU which you could then test but this isn't standard.

You could also test for the possibility of overflow before you perform the multiplication:

if ( b > ULONG_MAX / a ) // a * b would overflow

Warning: GCC can optimize away an overflow check when compiling with -O2. The option -Wall will give you a warning in some cases like

if (a + b < a) { /* deal with overflow */ }

but not in this example:

b = abs(a);
if (b < 0) { /* deal with overflow */ }

The only safe way is to check for overflow before it occurs, as described in the CERT paper, and this would be incredibly tedious to use systematically.

Compiling with -fwrapv solves the problem but disables some optimizations.

We desperately need a better solution. I think the compiler should issue a warning by default when making an optimization that relies on overflow not occurring. The present situation allows the compiler to optimize away an overflow check, which is unacceptable in my opinion.

For unsigned integers, just check that the result is smaller than one of the arguments :

unsigned int r, a, b;
r = a+b;
if (r < a)
{
// overflow
}

For signed integers you can check the signs of the arguments and of the result. integers of different signs can't overflow, and integers of same sign overflow only is the result is of different sign :

signed int r, a, b, s;
r = a+b;
s = a>=0;
if (s == (b>=0) && s != (r>=0))
{
// overflow
}

clang now support dynamic overflow checks for both signed and unsigned integers. See -fsanitize=integer switch. For now it is only one C++ compiler with fully supported dynamic overflow checking for debug purpose.

The simplest way is to convert your unsigned longs into unsigned long longs, do your multiplication, and compare the result to 0x100000000LL.

You'll probably find that this is more efficient than doing the division as you've done in your example.

Oh, and it'll work in both C and C++ (as you've tagged the question with both).

Just been taking a look at the glibc manual. There's a mention of an integer overflow trap (FPE_INTOVF_TRAP) as part of SIGFPE. That would be ideal, apart from the nasty bits in the manual:

FPE_INTOVF_TRAP Integer overflow (impossible in a C program unless you enable overflow trapping in a hardware-specific fashion).

A bit of a shame really.

I see that a lot of people answered the question about overflow, but I wanted to address his original problem. He said the problem was to find ab=c such that all digits are used without repeating. Ok, that's not what he asked in this post, but I'm still think that it was necessary to study the upper bound of the problem and conclude that he would never need to calculate or detect an overflow (note: I'm not proficient in math so I did this step by step, but the end result was so simple that this might have a simple formula).

The main point is that the upper bound that the problem requires for either a, b or c is 98.765.432. Anyway, starting by splitting the problem in the trivial and non trivial parts:

• x0 == 1 (all permutations of 9, 8, 7, 6, 5, 4, 3, 2 are solutions)
• x1 == x (no solution possible)
• 0b == 0 (no solution possible)
• 1b == 1 (no solution possible)
• ab, a > 1, b > 1 (non trivial)

Now we just need to show that no other solution is possible and only the permutations are valid (and then the code to print them is trivial). We go back to the upper bound. Actually the upper bound is c ≤ 98.765.432. It's the upper bound because it's the largest number with 8 digits (10 digits total minus 1 for each a and b). This upper bound is only for c because the bounds for a and b must be much lower because of the exponential growth, as we can calculate, varying b from 2 to the upper bound:

9938.08^2 == 98765432
462.241^3 == 98765432
99.6899^4 == 98765432
39.7119^5 == 98765432
21.4998^6 == 98765432
13.8703^7 == 98765432
9.98448^8 == 98765432
7.73196^9 == 98765432
6.30174^10 == 98765432
5.33068^11 == 98765432
4.63679^12 == 98765432
4.12069^13 == 98765432
3.72429^14 == 98765432
3.41172^15 == 98765432
3.15982^16 == 98765432
2.95305^17 == 98765432
2.78064^18 == 98765432
2.63493^19 == 98765432
2.51033^20 == 98765432
2.40268^21 == 98765432
2.30883^22 == 98765432
2.22634^23 == 98765432
2.15332^24 == 98765432
2.08826^25 == 98765432
2.02995^26 == 98765432
1.97741^27 == 98765432

Notice, for example the last line: it says that 1.97^27 ~98M. So, for example, 1^27 == 1 and 2^27 == 134.217.728 and that's not a solution because it has 9 digits (2 > 1.97 so it's actually bigger than what should be tested). As it can be seen, the combinations available for testing a and b are really small. For b == 14, we need to try 2 and 3. For b == 3, we start at 2 and stop at 462. All the results are granted to be less than ~98M.

Now just test all the combinations above and look for the ones that do not repeat any digits:

['0', '2', '4', '5', '6', '7', '8'] 2^84 = 7056
['1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481
['0', '1', '2', '3', '4', '5', '8', '9'] 2^59 = 3481 (+leading zero)
['1', '2', '3', '5', '8'] 3^8 = 512
['0', '1', '2', '3', '5', '8'] 3^8 = 512 (+leading zero)
['1', '2', '4', '6'] 2^4 = 16
['0', '1', '2', '4', '6'] 2^4 = 16 (+leading zero)
['1', '2', '4', '6'] 4^2 = 16
['0', '1', '2', '4', '6'] 4^2 = 16 (+leading zero)
['1', '2', '8', '9'] 2^9 = 81
['0', '1', '2', '8', '9'] 2^9 = 81 (+leading zero)
['1', '3', '4', '8'] 4^3 = 81
['0', '1', '3', '4', '8'] 4^3 = 81 (+leading zero)
['2', '3', '6', '7', '9'] 6^3 = 729
['0', '2', '3', '6', '7', '9'] 6^3 = 729 (+leading zero)
['2', '3', '8'] 3^2 = 8
['0', '2', '3', '8'] 3^2 = 8 (+leading zero)
['2', '3', '9'] 2^3 = 9
['0', '2', '3', '9'] 2^3 = 9 (+leading zero)
['2', '4', '6', '8'] 2^8 = 64
['0', '2', '4', '6', '8'] 2^8 = 64 (+leading zero)
['2', '4', '7', '9'] 2^7 = 49
['0', '2', '4', '7', '9'] 2^7 = 49 (+leading zero)

None of them matches the problem (which can also be seen by the absence of '0', '1', ..., '9').

The example code that solves it follows. Also note that's written in python, not because it needs arbitrary precision integers (the code doesn't calculate anything bigger than 98 million), but because we found out that the amount of tests is so small that we should use a high level language to make use of its built-in containers and libraries (also note: the code has 28 lines).

import math

m = 98765432
l = []
for i in xrange(2, 98765432):
inv = 1.0/i
r = m**inv
if (r < 2.0): break
top = int(math.floor(r))
assert(top <= m)

for j in xrange(2, top+1):
s = str(i) + str(j) + str(j**i)
l.append((sorted(s), i, j, j**i))
assert(j**i <= m)

l.sort()
for s, i, j, ji in l:
assert(ji <= m)
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d' % (s, i, j, ji)

# Try with non significant zero somewhere
s = ['0'] + s
ss = sorted(set(s))
if s == ss:
print '%s %d^%d = %d (+leading zero)' % (s, i, j, ji)

Here is a "non-portable" solution to the question. The Intel x86 and x64 CPUs have the so-called EFLAGS-register ( http://en.wikipedia.org/wiki/EFLAGS ), which is filled by the processor after each integer arithmetic operation. I will skip a detailed description here. The relevant flags are the "Overflow" Flag (mask 0x800) and the "Carry" Flag (mask 0x1). To interpret them correctly, one should consider if the operands are of signed or unsigned type.

Here is a practical way to check the flags from C/C++. The following code will work on Visual Studio 2005 or newer (both 32 and 64 bit), as well as on GNU C/C++ 64 bit.

#include <cstddef>
#if defined( _MSC_VER )
#include <intrin.h>
#endif

inline size_t query_intel_x86_eflags( const size_t query_bit_mask )
{
#if defined( _MSC_VER )
#elif defined( __GNUC__ )
// this code will work only on 64-bit GNU-C machines;
// Tested and does NOT work with Intel C++ 10.1!
size_t eflags;
__asm__ __volatile__(
"pushfq \n\t"
"pop %%rax\n\t"
"movq %%rax, %0\n\t"
:"=r"(eflags)
:
:"%rax"
);
return eflags & query_bit_mask;
#else
#pragma message("No inline assembly will work with this compiler!")
return 0;
#endif
}

int main(int argc, char **argv)
{
int x = 1000000000;
int y = 20000;
int z = x * y;
int f = query_intel_x86_eflags( 0x801 );
printf( "%X\n", f );
}

If the operands were multiplied without overflow, you would get a return value of 0 from query_intel_eflags( 0x801 ), i.e. neither the carry nor the overflow flags are set. In the provided example code of main(), an overflow occurs and the both flags are set to 1. This check does not imply any further calculations, so it should be quite fast.

If you have a datatype which is bigger than the one you want to test (say a you do a 32-bit add and you have a 64-bit type). Then this will detect if an overflow occured. My example is for an 8-bit add. But can be scaled up.

uint8_t x, y;   /* give these values */
const uint16_t data16   = x + y;
const bool carry        = (data16 > 0xff);
const bool overflow     = ((~(x ^ y)) & (x ^ data16) & 0x80);

It is based on the concepts explained on this page: http://www.cs.umd.edu/class/spring2003/cmsc311/Notes/Comb/overflow.html

For a 32-bit example, 0xff becomes 0xffffffff and 0x80 becomes 0x80000000 and finally uint16_t becomes a uint64_t.

NOTE: this catches integer addition/subtraction overflows, and I realized that your question involves multiplication. In which case, division is likely the best approach. This is commonly a way that calloc implementations make sure that the params don't overflow as they are multiplied to get the final size.

You can't access the overflow flag from C/C++.

Some compilers allow you to insert trap instructions into the code. On GCC the option is -ftrapv (but I have to admit that I've never used it. Will check it after posting).

The only portable and compiler independent thing you can do is to check for overflows on your own. Just like you did in your example.

Edit:

Just checked: -ftrapv seems to do nothing on x86 using the lastest GCC. Guess it's a left over from an old version or specific to some other architecture. I had expected the compiler to insert an INTO opcode after each addition. Unfortunately it does not do this.

Although it has been two years, I felt I might as well add my penithworth for a really fast way to detect overflow for at least additions, which might give a lead for multiplication, division and power-of

The idea is that exactly because the processor will just let the value wrap back to zero and that C/C++ is to abstracted from any specific processor, you can:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < (x | y);

This both ensures that if one operand is zero and one isn't, then overflow won't be falsely detected, and is significantly faster than a lot of NOT/XOR/AND/test operations as previously suggested.

Edit: As pointed out, this approach although better than other more elaborate ways is still optimisable. The following is a revision of the original code containing the optimisation:

uint32_t x, y;
uint32_t value = x + y;
bool overflow = value < x; // Alternatively "value < y" should also work

Another interesting tool: http://embed.cs.utah.edu/ioc/

This is a patched clang compiler, which adds checks to the code at compile time. So you get output looking like this:

CLANG ARITHMETIC UNDEFINED at <add.c, (9:11)> :
Op: +, Reason : Signed Addition Overflow,
BINARY OPERATION: left (int32): 2147483647 right (int32): 1

CERT has developed a new approach to detecting and reporting signed integer overflow, unsigned integer wrapping, and integer truncation using the "as-if" infinitely ranged (AIR) integer model. CERT has published a technical report describing the model and produced a working prototype based on GCC 4.4.0 and GCC 4.5.0.

The AIR integer model either produces a value equivalent to one that would have been obtained using infinitely ranged integers or results in a runtime constraint violation. Unlike previous integer models, AIR integers do not require precise traps, and consequently do not break or inhibit most existing optimizations.

Calculate the results with doubles. They have 15 significant digits. Your requirement has a hard upper bound on c of 108 — it can have at most 8 digits. Hence, the result will be precise if it's in range, and it will not overflow otherwise.

I needed to answer this same question for floating point numbers, where bit masking and shifting does not look promising. The approach I settled on works for signed and unsigned, integer and floating point numbers. It works even if there is no larger data type to promote to for intermediate calculations. It is not the most efficient for all of these types, but because it does work for all of them, it is worth using.

Signed Overflow test, Addition and Subtraction:

1. Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
2. Compute and compare the signs of the operands.

a. If either value is zero, then neither addition nor subtraction can overflow. Skip remaining tests.

b. If the signs are opposite, then addition cannot overflow. Skip remaining tests.

c. If the signs are the same, then subtraction cannot overflow. Skip remaining tests.

3. Test for positive overflow of MAXVALUE.

a. If both signs are positive and MAXVALUE - A < B, then addition will overflow.

b. If the sign of B is negative and MAXVALUE - A < -B, then subtraction will overflow.

4. Test for negative overflow of MINVALUE.

a. If both signs are negative and MINVALUE - A > B, then addition will overflow.

b. If the sign of A is negative and MINVALUE - A > B, then subtraction will overflow.

5. Otherwise, no overflow.

Signed Overflow test, Multiplication and Division:

1. Obtain the constants that represent the largest and smallest possible values for the type, MAXVALUE and MINVALUE.
2. Compute and compare the magnitudes (absolute values) of the operands to one. (Below, assume A and B are these magnitudes, not the signed originals.)

a. If either value is zero, multiplication cannot overflow, and division will yield zero or an infinity.

b. If either value is one, multiplication and division cannot overflow.

c. If the magnitude of one operand is below one and of the other is greater than one, multiplication cannot overflow.

d. If the magnitudes are both less than one, division cannot overflow.

3. Test for positive overflow of MAXVALUE.

a. If both operands are greater than one and MAXVALUE / A < B, then multiplication will overflow.

b. If B is less than one and MAXVALUE * B < A, then division will overflow.

4. Otherwise, no overflow.

Note: Minimum overflow of MINVALUE is handled by 3, because we took absolute values. However, if ABS(MINVALUE) > MAXVALUE, then we will have some rare false positives.

The tests for underflow are similar, but involve EPSILON (the smallest positive number greater than zero).

Try this macro to test the overflow bit of 32-bit machines (adapted the solution of Angel Sinigersky)

#define overflowflag(isOverflow){   \
size_t eflags;                      \
asm ("pushfl ;"                     \
"pop %%eax"                    \
: "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

I defined it as a macro because otherwise the overflow bit would have been overwritten.

Subsequent is a little application with the code segement above:

#include <cstddef>
#include <stdio.h>
#include <iostream>
#include <conio.h>
#if defined( _MSC_VER )
#include <intrin.h>
#include <oskit/x86>
#endif

using namespace std;

#define detectOverflow(isOverflow){     \
size_t eflags;                      \
asm ("pushfl ;"                     \
"pop %%eax"                     \
: "=a" (eflags));               \
isOverflow = (eflags >> 11) & 1;}

int main(int argc, char **argv) {

bool endTest = false;
bool isOverflow;

do {
cout << "Enter two intergers" << endl;
int x = 0;
int y = 0;
cin.clear();
cin >> x >> y;
int z = x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow occured\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}

z = x * x * y;
detectOverflow(isOverflow)
printf("\nThe result is: %d", z);
if (!isOverflow) {
std::cout << ": no overflow ocurred\n" << std::endl;
} else {
std::cout << ": overflow occured\n" << std::endl;
}

cout << "Do you want to stop? (Enter \"y\" or \"Y)" << endl;

char c = 0;

do {
c = getchar();
} while ((c == '\n') && (c != EOF));

if (c == 'y' || c == 'Y') {
endTest = true;
}

do {
c = getchar();
} while ((c != '\n') && (c != EOF));

} while (!endTest);
}

You can't access the overflow flag from C/C++.

I don't agree with this. You could write some inline asm and use a jo (jump overflow) instruction assuming you are on x86 to trap the overflow. Of course you code would no longer be portable to other architectures.

look at info as and info gcc.

Catching Integer Overflows in C points out a solution more general than the one discussed by CERT (it is more general in term of handled types), even if it requires some GCC extensions (I don't know how widely supported they are).

Another variant of solution using assembler is an external procedure. This example for unsigned integer multiplication using g++ and fasm under linux x64.

This procedure multiplies two unsigned integer arguments (32 bits) (according to specification for amd64 (section 3.2.3 Parameter Passing)

If the class is INTEGER, the next available register of the sequence %rdi,%rsi,%rdx,%rcx,%r8 and %r9 is used

(edi and esi registers in my code)) and returns the result or 0 if an overflow has occured.

format ELF64

section '.text' executable

public u_mul

u_mul:
MOV eax, edi
mul esi
jnc u_mul_ret
xor eax, eax
u_mul_ret:
ret

test:

extern "C" unsigned int u_mul(const unsigned int a, const unsigned int b);

int main() {
printf("%u\n", u_mul(4000000000,2));//0
printf("%u\n", u_mul(UINT_MAX/2,2));//ok
return 0;
}

link program with asm object file. In my case in Qt Creator add it to LIBS in a .pro file

Inline assembly lets you check the overflow bit directly. If you are going to be using C++, you really should learn assembly.

It depends what you use it for. Performing unsigned long(DWORD) addition or Multiplication the best solution is to use ULARGE_INTEGER.

ULARGE_INTEGER is a structure of two DWORDs. The full value can be accessed as "QuadPart" while the hi DWORD is accessed as "HighPart" and the low DWORD is accessed as "LowPart"

For example:

DWORD My Addition(DWORD Value_A,DWORD Value_B) { ULARGE_INTEGER a,b;

b.LowPart = Value_A;  // a 32 bit value(up to 32 bit)
b.HighPart = 0;
a.LowPart = Value_B;  // a 32 bit value(up to 32 bit)
a.HighPart = 0;

// if  a.HighPart
// Then a.HighPart contains the overflow(carry)

return (a.LowPart + a.HighPart)

// any overflow is stored in a.HighPart(up to 32 bits)

A clean way to do it would be to override all operators (+ and * in particular) and check for an overflow before perorming the operations.

@MSalters: Good idea.

If the integer calculation is required (for precision), but floating point is available, you could do something like:

uint64_t foo( uint64_t a, uint64_t b ) {
double   dc;

dc = pow( a, b );

if ( dc < UINT_MAX ) {
return ( powu64( a, b ) );
}
else {
// overflow
}
}

The simple way to test for overflow is to do validation by checking whether the current value is less than the previous value. For example, suppose you had a loop to print the powers of 2:

long lng; int n; for (n = 0; n < 34; ++n) { lng = pow (2, n); printf ("%li\n", lng); }

Adding overflow checking the way that I described results in this:

long signed lng, lng_prev = 0;
int n;
for (n = 0; n < 34; ++n)
{
lng = pow (2, n);
if (lng <= lng_prev)
{
printf ("Overflow: %i\n", n);
/* Do whatever you do in the event of overflow.  */
}
printf ("%li\n", lng);
lng_prev = lng;
}

It works for unsigned values as well as both positive and negative signed values.

Of course, if you wanted to do something similar for decreasing values instead of increasing values, you would flip the <= sign to make it >=, assuming the behaviour of underflow is the same as the behaviour of overflow. In all honesty, that's about as portable as you'll get without access to a CPU's overflow flag (and that would require inline assembly code, making your code non-portable across implementations anyway).

To expand on Head Geek's answer, there is a faster way to do the addition_is_safe;

bool addition_is_safe(unsigned int a, unsigned int b)
{
unsigned int L_Mask = std::numeric_limits<unsigned int>::max();

return ( a == 0 || b == 0 );
}

This uses machine-architecture safe, in that 64-bit and 32-bit unsigned integers will still work fine. Basically, I create a mask that will mask out all but the most significant bit. Then, I mask both integers, and if either of them do not have that bit set, then addition is safe.

This would be even faster if you pre-initialize the mask in some constructor, since it never changes.

#include <stdio.h>
#include <stdlib.h>

#define MAX 100

int mltovf(int a, int b)

{

if (a && b) return abs(a) > MAX/abs(b);
else return 0;

}

main()

{

int a, b;

for (a = 0; a <= MAX; a++)
for (b = 0; b < MAX; b++) {

if (mltovf(a, b) != (a*b > MAX))
printf("Bad calculation: a: %d b: %d\n", a, b);

}

}

x86 instruction set includes unsigned multiply instruction that stores the result to two registers. To use that instruction from C one can write following code in 64bit program (gcc):

unsigned long checked_imul(unsigned long a, unsigned long b) {
__int128 res = (__int128)a * (__int128)b;
if ((unsigned long)(res >> 64))
printf("overflow in integer multiply");
return (unsigned long)res;
}

For 32bit program one needs to make result 64 bit and parameters 32bit.

Alternative is to use compiler depend instincts to check the flag register. GCC documentation for overflow instincts can be found from https://gcc.gnu.org/onlinedocs/gcc/Integer-Overflow-Builtins.html

To perform an unsigned multiplication without overflowing in a portable way the following can be used:

... /* begin multiplication */
unsigned multiplicand, multiplier, product, productHalf;
int zeroesMultiplicand, zeroesMultiplier;
zeroesMultiplicand = number_of_leading_zeroes( multiplicand );
zeroesMultiplier   = number_of_leading_zeroes( multiplier );
if( zeroesMultiplicand + zeroesMultiplier <= 30 ) goto overflow;
productHalf = multiplicand * ( c >> 1 );
if( (int)productHalf < 0 ) goto overflow;
product = productHalf * 2;
if( multiplier & 1 ){
product += multiplicand;
if( product < multiplicand ) goto overflow;
}
..../* continue code here where "product" is the correct product */
....
overflow: /* put overflow handling code here */

int number_of_leading_zeroes( unsigned value ){
int ctZeroes;
if( value == 0 ) return 32;
ctZeroes = 1;
if( ( value >> 16 ) == 0 ){ ctZeroes += 16; value = value << 16; }
if( ( value >> 24 ) == 0 ){ ctZeroes +=  8; value = value <<  8; }
if( ( value >> 28 ) == 0 ){ ctZeroes +=  4; value = value <<  4; }
if( ( value >> 30 ) == 0 ){ ctZeroes +=  2; value = value <<  2; }
ctZeroes -= x >> 31;
return ctZeroes;
}

Category: c# Time: 2008-10-13 Views: 1