Modulus by constant

[Joe Buck]

Richard Kenner wrote:

> Does anybody understand the code that Torbjorn wrote to do divides and modulus
> operations as multiplies?

I'll just describe one of the cases Torbjorn implemented.

Consider a / b where b is an odd number, and it is known that b divides a
(this case occurs in C pointer subtraction).  There always exists a number
that I'll call b_inv such that

	(b * b_inv) modulo 2**NBITS == 1

where NBITS is the number of bits in a word.  Unsigned multiplication in
C is effectively modulo 2**NBITS.  Then a / b is the same as

	(a * b_inv) modulo 2**NBITS

or simply a * b_inv in C.

If b isn't odd, then it is of the form p*(1<<q) where p is odd.  So, we
just form (a>>q)*p_inv for that case.