12
\$\begingroup\$

The function below implements safe multiplication of two 64-bit signed integers, preventing overflow from occurring:

// Multiplies two 64-bit signed ints if possible.
// Returns 0 on success, and puts the product of x and y into the result.
// Returns 1 if there was an overflow.
int int64_mult(int64_t x, int64_t y, int64_t * result)
{
    *result = 0;
    if (x > 0 && y > 0 && x > INT64_MAX / y) return 1;
    if (x < 0 && y > 0 && x < INT64_MIN / y) return 1;
    if (x > 0 && y < 0 && y < INT64_MIN / x) return 1;
    if (x < 0 && y < 0 && (x <= INT64_MIN || y <= INT64_MIN || -x > INT64_MAX / -y))
        return 1;
    *result = x * y;
    return 0;
}

Did I get the logic for detecting overflows right? I am most interested in making sure that no undefined behavior will occur, and that the function will always return the right results.

We can assume that int64_t will be a two's complement integer, because this is for GCC and GCC does not support any other type of integer.

For the convenience of the code reviewers (you), I made a complete, self-contained test suite that you can just run in your favorite C/C++ environment:

https://gist.github.com/DavidEGrayson/06cf7ea73f82a05490ba

I am not too interested in code style issues. I am aware it might be nice to assert that the output pointer is not null, and it might be nice to add braces and parentheses. But really I want to know if the code is actually correct.

I am somewhat interested in making the code simpler if you have a way to do that; maybe some of the cases could be combined.

I am also aware that the logic might be easier if I just used a 128-bit integer to store the multiplication result, but I would like to get it right without doing that.

The reason I am asking this is because I am working on adding intsafe.h to mingw-w64 (a GCC compiler for Windows), so I am implementing safe multiplication of signed and unsigned numbers. This function is analogous to LongLongMult in intsafe.h. Your contribution will help make this header safer. You can see my progress here.

\$\endgroup\$
11
\$\begingroup\$

Given that you are writing for gcc, is there a reason you're not using the builtins?

bool __builtin_add_overflow (type1 a, type2 b, type3 *res)
bool __builtin_sub_overflow (type1 a, type2 b, type3 *res)
bool __builtin_mul_overflow (type1 a, type2 b, type3 *res)

But as to your question, it looks correct to me, modulo the answer by the other poster.

\$\endgroup\$
  • \$\begingroup\$ FYI for anyone else reading this, these built-ins were added in GCC 5, which came out fairly recently. \$\endgroup\$ – David Grayson Aug 2 '15 at 16:27
  • \$\begingroup\$ All 253 functions in intsafe.h can be implemented using these built-ins, wow! Casting from one integer type to another can be done with __builtin_add_overflow(a, 0, res). \$\endgroup\$ – David Grayson Aug 2 '15 at 16:36
6
\$\begingroup\$

I believe your logic is correct: all combinations of positive and negative x and y are checked.

You can replace the last condition with the obvious, more natural and simple:

if (x < 0 && y < 0 && x < INT64_MAX / y) return 1;
\$\endgroup\$
  • \$\begingroup\$ Thanks, your change does indeed seem to work, and all the tests still pass. \$\endgroup\$ – David Grayson Aug 2 '15 at 6:41
4
\$\begingroup\$

There are multiple ways to fix C up for using a bool type. And using a bool type helps make our code more human-readable, so we should certainly be doing that.


There are no braces. "Optional" doesn't mean you should omit whenever possible. "Optional" means for some reason, the compiler will manage to compile even without the braces. It's two extra characters and it ensures that if anyone ever does get in here and modify this otherwise simple method, they have no chances of screwing it up.


You have appropriately documented the return values:

// Returns 0 on success, and puts the product of x and y into the result.
// Returns 1 if there was an overflow.

But I think you're returning the opposite of what you should.

Looking at this method, I want to use it something like this...

if(int64_mult(a, b, &c)) {
    // use c
} else {
    // there was an overflow
}

But I can't because you return 0 on success and non-zero on failure. This is what we expect from programs, but not what we expect from functions. I think this should be fixed.


*result = 0;

I don't write enough C to know if this would be the expected behavior or not. I think I would not want this to happen however.

If this function automatically sets our passed in value to 0 or the actual multiplied value, it's only barely more useful than not checking at all.

I think I would prefer the result variable not being set to anything at all if it would overflow. Just leave me with whatever my variable was before, and the return from the function tells me it didn't actually multiply.


The function's name leaves a lot to be desired. I don't think int64 is fully required here, as the function arguments declare the type. I'm not sure what we've gained by abbreviating multiply except leaving ourselves with the potential for possible confusion if we need some other similarly named sort of function (multiples perhaps?). And the name leave no indication that it's at all special versus just doing a * b.

Comments are great, and you've done that. But self-documenting code is better. Let's call this method something better. How about:

bool safe_overflow_multiply(int64_t a, int64_t b, int64_t *result);
\$\endgroup\$
  • \$\begingroup\$ I appreciate your taking the time to write all this up. However: I mentioned braces in the question. Since I am actually implementing a function in a header defined by Microsoft, I have no choice about the return value and function name. Setting the result to zero (or something) is important, since it could potentially save users from the undefined behavior of reading an uninitialized variable. Undefined behavior can cause security check elimination \$\endgroup\$ – David Grayson Aug 2 '15 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.