https://gcc.gnu.org/bugzilla/show_bug.cgi?id=82853
Orr Shalom Dvory <dvoreader at gmail dot com> changed:
What |Removed |Added
----------------------------------------------------------------------------
CC| |dvoreader at gmail dot com
--- Comment #33 from Orr Shalom Dvory <dvoreader at gmail dot com> ---
(In reply to Jakub Jelinek from comment #25)
> Created attachment 44657 [details]
> gcc9-pr82853.patch
>
> Full untested patch. For x % C1 == C2 it handles all unsigned cases where
> C1 is odd, if C1 is even, just cases where C2 <= -1U % C1, if signed modulo,
> just x % C1 == 0 cases (where C1 is not INT_MIN).
Hi, I will try to help. I've got a more accurate formula. look at my comment
over here https://reviews.llvm.org/D50222
I'm copying it here for the sake of all.
Hi guys, I found the magical formula for unsigned integers that works also with
even numbers without the need to check for overflows with any remainder:
from divisor d and reminder r, I calculate 4 constants.
any d!=0 should fit.
void calculate_constants64(uint64_t d, uint64_t r, uint64_t &k,uint64_t &mmi,
uint64_t &s,uint64_t& u)
{
k=__builtin_ctzll(d);/* the power of 2 */
uint64_t d_odd=d>>k;
mmi=find_mod_mul_inverse(d_odd,64);
/* 64 is word size*/
s=(r*mmi);
u=(ULLONG_MAX-r)/d;/* note that I divide by d, not d_odd */
}
A little bit background: the constant (u +1) is the count of the possible
values in the range of 64 bit number that will yield the correct modulo.
The constant s should zero the first k bits if the given value have modulo of
r. it will also zero the modulo of d_odd.
then the compiler should generate the following code with the given constants:
int checkrem64(uint64_t k,uint64_t mmi, uint64_t s,uint64_t u,uint64_t x)
{
uint64_t o=((x*mmi)-s);
o= (o>>k)|(o<<(64-k));/*ROTR64(o,k)*/
return o<=u;
}
this replace the following:
/* d is the divisor, r is the remainder */
int checkrem64(uint64_t x)
{
return x%d==r;
}
this is the code to find modular inverse..
uint64_t find_mod_mul_inverse(uint64_t x, uint64_t bits)
{
if (bits > 64 || ((x&1)==0))
return 0;// invalid parameters
uint64_t mask;
if (bits == 64)
mask = -1;
else
{
mask = 1;
mask<<=bits;
mask--;
}
x&=mask;
uint64_t result=1, state=x, ctz=0;
while(state!=1ULL)
{
ctz=__builtin_ctzll(state^1);
result|=1ULL<<ctz;
state+=x<<ctz;
state&=mask;
}
return result;
}
good luck!
I tested this on all the cases of 10bit word size, and it passed.
*Edit:* I looked for something that will work for signed integers. I came up
with something that would work with negative numbers if the following
assumption was correct:
(-21)%10==9
but this assumption is not correct because (-21)%10 equals to -1.
anyway, the idea is like that, you shift the range and change s and
accordingly:
void calculate_constants64(uint64_t d, uint64_t r, uint64_t &k,uint64_t &mmi,
uint64_t &s,uint64_t& u)
{
k=__builtin_ctzll(d);/* the power of 2 */
uint64_t d_odd=d>>k;
mmi=find_mod_mul_inverse(d_odd,64);
/* 64 is word size*/
//this is the added line to make it work with signed integers
r+=0x8000 0000 0000 0000% d;
s=(r*mmi);
u=(ULLONG_MAX-r)/d;
}
int checkrem64(uint64_t k,uint64_t mmi, uint64_t s,uint64_t u,uint64_t x)
{
//this is the added line to make it work with signed integers
//x came as signed number but was casted to unsigned
x^=0x8000 0000 0000 0000;// this is addition simplified to xor, spaces for
clarity.
uint64_t o=((x*mmi)-s);
o= (o>>k)|(o<<(64-k));/*ROTR64(o,k)*/
return o<=u;
}
There is a way to tweak u and s to make it work on negative only numbers or
positive only numbers, when r is negative or positive... but for r=0, this
should work. please tell me the exact requirements, and I will do the math.
