MulDiv Mayhem

Here's another episode in my ongoing quest to stamp out integer overflows. MulDiv is a Windows API that was around before we had 64-bit integers as native types. MulDiv is defined like so:

int MulDiv(int a, int b, int c)

Ironically, the problem it's trying to get around is integer overflows. If you've done any work with numerical analysis, the problem is obvious – what we're trying to do is (a*b)/c. If we multiply a*b as 32-bit numbers, it could overflow, and if we then divide, we'll get junk. If we did it as a*(b/c), then if b < c, the result is 0 (for positive values of b, c). Speaking of which, I think numerical analysis ought to be required for all programmers, and it helps when what you're working on matters – use bad math to figure out the specs for an airfoil, or just about any engineering design issue, and people could get hurt.

The way to fix this is to do what MulDiv does, which is essentially:

__int64 ret = ((__int64)a * (__int64)b)/c;

if(ret > INT_MAX || ret < INT_MIN)

    return -1;

return (int)ret;

This does fix most of the problems, and I use some of this in SafeInt – all possible values of a*b can be represented by a 64-bit int, and the division will take place afterwards, guaranteeing a numerically correct result, if the return fits into an int. Herein lies the first problem observed in real usage – people don't check the return, and worse yet, the error return is a perfectly valid value. Where the real problems come in is when people start passing unsigned ints into this function. What you get is the equivalent of doing:

(__int64)(int)(unsigned int)x

If you happen to have a number <= INT_MAX, the upper bit will be 0, we'll sign extend, the bit pattern and the value are both preserved, and things are good. But if we pass say 0x80000000 into this, the casts have us end up with 0xffffffff80000000. This could very well overflow internally, and put junk into ret. If you had a function that took an unsigned int, then our cast to __int64 gives you 0x0000000080000000 – very clearly a different number, and interestingly enough, you could write UMulDiv as:

__int64 ret = ((__int64)a * (__int64)b)/c;

if((unsigned __int64)ret > UINT_MAX) // could also be written as if((unsigned int)(ret >> 32)), which may be slightly more efficient

    return -1;

return (unsigned int)ret;

If you look at what's really going on, a 64-bit int multiplication can be broken up into this:

(+/-1)*(a*2^32 + b) * (+/-1)*(c*2^32 + d)

This now expands to:

(+/-1)*(ac*2^64 + ad*2^32 + bc*2^32 + bd)

Failures happen when ac != 0, ad >= 2^32, bc >= 2^32, or if the result of (ad+bc)*2^32 + bd overflows on addition. In the case of a large unsigned value coming in, we'll be very likely to fail in the second condition (ad or bc >= 2^32), since 2^31 times anything bigger than 1 meets our failure condition. So if you tried to calculate 2^31*2/4, and expected to get 2^30, you'd get a failure with MulDiv, and in fact, it does give you the wrong answer, with respect to an unsigned input – though it is correct with respect to signed math, since abs(0xc0000000) = 0x40000000.

int main(void)
{
printf("%x\n", MulDiv(0x80000000, 2, 4));
printf("%x\n", (int)((__int64)(0x80000000)* 2/ 4));
}

Yields:

C:\scratch>muldiv

c0000000

40000000

I should go look up the implementation, since if you feed it INT_MIN as every argument, it should return INT_MIN (the second line does), but instead it fails with -1. I'm not sure why that would happen, but since dividing by INT_MIN is a corner case, I'm not surprised.

You still obviously have the problem of a valid result being returned as an error, but essentially, passing unsigned values into MulDiv is a prescription for mayhem, and assigning MulDiv to unsigned numbers is just as bad. Another problem I've recently run into is this:

short s;

int i = MulDiv(s, 5, 6);

This is really just a silly waste of cycles – the operator casting does everything just fine, and what you end up with is the equivalent of:

int i = (int)s*(int)5/(int)6;

This is going to work just fine, especially if the fixed multiplier is smaller than the denominator – though again, you could hit truncation problems if you assign the results back to a short and we're making the value larger.

How to fix it? We could write a fairly large set of overloaded functions that take every combination of signed and unsigned input types, but if you want both signed and unsigned returns, you'll end up with 64 functions, and that's if we stick to the 32-bit inputs, and if you're overloading, don't forget to duplicate the ones for int and long (or ask your users to cast). A more correct implementation in C could be done simply by returning an error code, and putting the result into a pointer – we do have two failure modes – overflow and divide by zero. Or we can do this easily with SafeInt:

MY_INT_TYPE m = (SafeInt<__int64>(a)*b)/c; // note – parens not needed – for clarity only.

It will just do the right thing for nearly any combination of types, excepting if a and b are themselves 64-bit – fixing that one is hard, and you'll end up doing the multiplication and division by hand, register by register. Speaking of SafeInt, we're working on some changes that will tidy some things up and allow us to put it on MSDN again. Stay tuned.

Now that we do have 64-bit ints, it is almost always going to be better to just do this inline and do whatever checking makes sense for your code – and if you're scanning code for int overflows, doing a grep on MulDiv will very likely find some problems. I'm starting to think that putting MulDiv on the banned API list might be a good idea.

Comments

• Anonymous
  February 07, 2008
  PingBack from http://www.biosensorab.org/2008/02/07/muldiv-mayhem/

• Anonymous
  March 18, 2008
  a {color : #0033CC;} a:link {color: #0033CC;} a:visited.local {color: #0033CC;} a:visited {color : #800080;}

• Anonymous
  March 18, 2008
  a {color : #0033CC;} a:link {color: #0033CC;} a:visited.local {color: #0033CC;} a:visited {color : #800080;}

• Anonymous
  March 18, 2008
  a {color : #0033CC;} a:link {color: #0033CC;} a:visited.local {color: #0033CC;} a:visited {color : #800080;}

• Anonymous
  January 29, 2010
  "Another problem I've recently run into is this: " That was correct in 16-bit Windows, where int was 16-bit. [dcl] I don't think so, unless there was a different MulDiv that cast up to long. This one's declared as taking an int.