Which way to test for signed integer overflow on multiply?

Question

Which if any of the following does "the right thing" in a standards-compliant manner? You can assume that m and n are of type int (signed integer). The main issue is signed integer overflow.

Sample 1.

size_t bytes = n * m;
if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
    /* allocate “bytes” space */
}

Sample 2.

if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
    size_t bytes = n * m;
    /* allocate “bytes” space */
}

Sample 3.

if (n > 0 && m > 0 && SIZE_MAX/n >= m) {
    size_t bytes = (size_t)n * (size_t)m;
    /* allocate “bytes” space */
}

I think they're all wrong, but not all for the same reason. So what would be correct?

These snippets are taken from here.

---

Edited to emphasise that the main issue is multiplying signed integers, which can lead to Undefined Behaviour (which unsigned does not).

I now think that the last sample works correctly provided that integer, signed integer, size_t and SIZE_MAX have the "usual" values, or at least that they comply with relevant standards.

Answer 1

Sample 1 is incorrect, because the multiplication of m * n may exceed the range of representable values for the signed integer type, which leads to Undefined Behaviour. See n1570 S6.5/5:

If an exceptional condition occurs during the evaluation of an expression (that is, if the result is not mathematically defined or not in the range of representable values for its type), the behavior is undefined.

This is of practical importance since one of the things the compiler is permitted to do is to assume that Undefined Behaviour has not happened, and it may use this to optimise the code so that the if statement disappears and is of no effect.

Note that this applies only to the signed type. Unsigned arithmetic does not overflow. See n1570 S6.2.5/9.

A computation involving unsigned operands can never overflow, because a result that cannot be represented by the resulting unsigned integer type is reduced modulo the number that is one greater than the largest value that can be represented by the resulting type.

Sample 2 is incorrect, because the multiplication of m * n is evaluated as a signed integer expression, which may again result in Undefined Behaviour. However in this case there is less likelihood of a practical effect. The result will most likely produce the correct bit-wise result and once cast to an unsigned the value is likely to be correct. The sample is wrong, but better, at least for 32 bit processors.

Edit: The above para will be true if unsigned int and size_t are the same size, as they usually are for 32 bit processors. Sample 2 will not work correctly where size_t is larger than unsigned int, as it usually is on 64 bit processors. The signed multiply will overflow and produce wrong behaviour for some values.

Sample 3 is almost certainly correct. With the multiplication of m * n evaluated as an unsigned integer expression, there is no possibility of Undefined Behaviour. [As noted in another answer, only one cast operation is actually required.]

The exact behaviour here is subtly dependent on the definitions of int, unsigned int, size_t and SIZE_MAX. The usual assumption is that size_t is the same as unsigned int (or perhaps larger) and that SIZE_MAX is an unsigned integer literal, but these are not actually requirements. Indeed, SIZE_MAX is only required to be at least 65535. At least size_t is required to be unsigned.

Since I have not been able to find any plausible (or even implausible) definitions for them that would cause the sample to fail, on that basis I say that Sample 3 works correctly.

Answer 2

1 and 2 are wrong because n * m may overflow. The fact that you go on to assign it to a size_t doesn't "reverse" the overflow.

I think 3 is correct. (The cast on m is superfluous BTW). If anyone disagrees please post sample values for m and n and SIZE_MAX that makes the test incorrect!

Also I cannot see a problem with:

if ( m > 0 && n > 0 && (size_t)m * n / n == m )
    size_t bytes = (size_t)m * n;