Overflow-safe modular addition and subtraction in C?

Question

I'm implementing an algorithm in C that needs to do modular addition and subtraction quickly on unsigned integers and can handle overflow conditions correctly. Here's what I have now (which does work):

/* a and/or b may be greater than m */
uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) {
    uint32_t tmp;
    if (b <= UINT32_MAX - a)
        return (a + b) % m;

    if (m <= (UINT32_MAX>>1))
        return ((a % m) + (b % m)) % m;

    tmp = a + b;
    if (tmp > (uint32_t)(m * 2)) // m*2 must be truncated before compare
        tmp -= m;
    tmp -= m;
    return tmp % m;
}

/* a and/or b may be greater than m */
uint32_t modsub_32(uint32_t a, uint32_t b, uint32_t m) {
    uint32_t tmp;
    if (a >= b)
        return (a - b) % m;

    tmp = (m - ((b - a) % m)); /* results in m when 0 is needed */
    if (tmp == m)
        return 0;
    return tmp;
}

Anybody know of a better algorithm? The libraries I've found that do modular arithmetic all seem to be for large arbitrary precision numbers which is way overkill.

Edit: I want this to run well on a 32 bit machine. Also, my existing functions are trivially converted to work on other sizes of unsigned integers, a property which would be nice to retain.

Answer 1

Modular operations usually assume that a and b are less than m. This allows simpler algorithms:

umod_t sub_mod(umod_t a, umod_t b, umod_t m)
{
  if ( a>=b )
    return a - b;
  else
    return m - b + a;
}

umod_t add_mod(umod_t a, umod_t b, umod_t m)
{
  if ( 0==b ) return a;

  // return sub_mod(a, m-b, m);
  b = m - b;
  if ( a>=b )
    return a - b;
  else
    return m - b + a;
}

Source: Matters Computational, chapter 39.1.

Answer 2

I'd just do the arithmetic in uint32_t if it fits and in uint64_t otherwise.

uint32_t modadd_32(uint32_t a, uint32_t b, uint32_t m) {
    if (b <= UINT32_MAX - a)
        return (a + b) % m;
    else
        return ((uint64_t)a + b) % m;
}

On an architecture with 64bit integer types, this should be almost no overhead, you could even think of just doing everything in uint64_t. On architectures where uint64_t is synthesized let the compiler decide what he thinks is best, an then look into the generated assembler and mmeasure to see if this is satisfactory.