http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49552
--- Comment #2 from Wouter Vermaelen
2011-06-28 12:22:11 UTC ---
> Confirmed. Is this possible for all constant moduli?
It is. I recommend you get a copy of the book I mentioned before. The theory
behind the transformation is much better explained there than I could ever do
here. But I'll try to give a recipe to construct the routine for a specific
constant:
(all examples are for 32-bit, but it should be easy enough to generalize)
There are 3 different cases:
(x % C) == 0
* 'x' is unsigned, 'C' is odd:
return (x * Cinv) <= (0x / C);
Where Cinv is the multiplicative inverse of C (C * Cinv = 1 (modulo pow(2,
32))). Cinv is the same 'magic number' as is used to optimize exact-division
(division where it's known that the remainder will be zero).
* 'x' is unsigned, 'C' is even:
Split 'C' in an odd factor and a power of two.
C = Codd * Ceven
where Ceven = pow(2, k)
Now we test that 'x' is both divisible by 'Codd' and 'Ceven'.
return !(x & (Ceven - 1)) && ((x * Codd_inv) <= (0x / Codd))
When a rotate-right instruction is available, the expression above can be
rewritten so that it only requires one test:
return rotateRight(x * Codd_inv, k) <= (0x / C); // unsigned
comparison
* 'x' is signed, (C can be odd or even)
(I admit, I don't fully understand the theory behind this transformation, so
I'll only give the final result).
constexpr unsigned A = (0x7fff / Codd) & -(1 << k);
constexpr unsigned B = k ? (A >> (k - 1)) : (A << 1);
return rotateRight((x * Codd_inv) + A, k) <= B; // unsigned comparison
