How can I implement a modulo operation on unsigned ints with limited hardware in C

Question

I have a machine which only supports 32 bit operations, long long does not work on this machine. I have one 64 bit quantity represented as two unsigned int 32s. The question is how can I perform a mod on that 64 bit quantity with a 32 bit divisor.

r = a mod b

where:

a is 64 bit value and b is 32 bit value

I was thinking that I could represent the mod part by doing: a = a1 * (2 ^ 32) + a2 (where a1 is the top bits and a2 is the bottom bits)

(a1 * (2 ^32) + a2) mod b = ( (a1 * 2 ^ 32) mod b + a2 mod b) mod b

( (a1 * 2 ^ 32) mod b + a2 mod b) mod b = (a1 mod b * 2 ^ 32 mod b + a2 mod b) mod b

but the problem is that 2 ^ 32 mod b may sometimes be equal to 2 ^ 32 and therefore the multiplication will overflow. I have looked at attempting to convert the multiplication into an addition but that also requires me to use 2 ^ 32 which if I mod will again give me 2 ^ 32 :) so I am not sure how to perform an unsigned mod of a 64 bit value with a 32 bit one.

I guess a simple solution to this would be to perform the following operations:

1. a / b = c

2. a = a - floor(c) * b

3. perform 1 until c is equal to 0 and use a as the answer.

but I am not sure how to combine these two integers together to form the 64 bit value

Just to be complete here are some links for binary division and subtractions: http://www.exploringbinary.com/binary-division/

and a description of binary division algorithm: http://en.wikipedia.org/wiki/Division_algorithm

Answer 1

Works: Tested with 1000M random combinations against a 64-bit %.

Like grade school long division a/b (but in base 2), subtract b from a if possible, then shift, looping 64 times. Return the remainder.

#define MSBit 0x80000000L
uint32_t mod32(uint32_t a1 /* MSHalf */, uint32_t a2 /* LSHalf */, uint32_t b) {
  uint32_t a = 0;
  for (int i = 31+32; i >= 0; i--) {
    if (a & MSBit) {  // Note 1
      a <<= 1;
      a -= b;
    } else {
      a <<= 1;
    }
    if (a1 & MSBit) a++;
    a1 <<= 1;
    if (a2 & MSBit) a1++;
    a2 <<= 1;
    if (a >= b)
      a -= b;
  }
  return a;
}

Note 1: This is the sneaky part to do a 33-bit subtraction. Since code knows n has the MSBit set, 2*n will be greater than b, then n = 2*n - b. This counts on unsigned wrap-around.

---

[Edit]

Below is a generic modu() that works with any array size a and any size unsigned integer.

#include <stdint.h>
#include <limits.h>

// Use any unpadded unsigned integer type
#define UINT uint32_t
#define BitSize (sizeof(UINT) * CHAR_BIT)
#define MSBit ((UINT)1 << (BitSize - 1))

UINT modu(const UINT *aarray, size_t alen, UINT b) {
  UINT r = 0;
  while (alen-- > 0) {
    UINT a = aarray[alen];
    for (int i = BitSize; i > 0; i--) {
      UINT previous = r;
      r <<= 1;
      if (a & MSBit) {
        r++;
      }
      a <<= 1;
      if ((previous & MSBit) || (r >= b)) {
        r -= b;
      }
    }
  }
  return r;
}

UINT modu2(UINT a1 /* MSHalf */, UINT a2 /* LSHalf */, UINT b) {
  UINT a[] = { a2, a1 };  // Least significant at index 0
  return modu(a, sizeof a / sizeof a[0], b);
}

Answer 2

Do it the same way you would do a long division with pencil and paper.

#include <stdio.h>

unsigned int numh = 0x12345678;
unsigned int numl = 0x456789AB;
unsigned int denom = 0x17234591;

int main() {
    unsigned int numer, quotient, remain;

    numer = numh >> 16;
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numh & 0xffff);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numl >> 16);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    numer = (remain << 16) | (numl & 0xffff);
    quotient = numer / denom;
    remain = numer - quotient * denom;

    printf("%X\n", remain);   
    return 0;
}