C and modulus

on 28 Apr 2007 by Mukund (@muks)

This macro was written because the % operation is implementation defined over negative integers in C. It was originally written by Simon Budig, Øyvind Kolås and me for a GIMP patch many moons ago, but we decided not to put the patch in. As this code took a while to arrive at, here it is for your pleasure and so that we may never have to rewrite it.

#define REMAINDER(dividend, divisor)                    \
  (((dividend) < 0) ?                                   \
   (divisor) - 1 - ((-(dividend) - 1) % (divisor)) :    \
   (dividend) % (divisor))

Update: The macro assumes a positive divisor. Our divisor was always a constant positive integer literal.

Morten Welinder found an underflow situation in the code above when INT_MIN is used as the dividend, which may fall in yet another undefined part of the C specification. Basically in the sub-expression (-(dividend) - 1), -(dividend) == (dividend) when dividend == INT_MIN. And INT_MIN - 1 will underflow (and wrap-around to INT_MAX in the case of most microprocessors' two's complement registers), and this behaviour is not defined in C. Although it'll work fine on most general purpose CPUs, because this is undocumented, there may be issues if gcc tries to reduce it at -O2 if both dividend and divisor are constants. More correct code with Morten's patch is:

#define REMAINDER(dividend, divisor)                    \
  (((dividend) < 0) ?                                   \
   (divisor) - 1 - ((-((dividend) + 1)) % (divisor)) :  \
   (dividend) % (divisor))

It won't overflow over INT_MAX in this case, as dividend is less than 0 when that sub-expression is used. So now, we have 4 authors. ;)