Page MenuHomePhabricator

gnudles (Kapandaria)
User

Projects

User does not belong to any projects.

User Details

User Since
Feb 23 2019, 10:36 AM (91 w, 6 d)

Recent Activity

Feb 23 2019

gnudles requested changes to D50222: [CodeGen] [SelectionDAG] More efficient code for X % C == 0 (UREM case).

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 */
}
Feb 23 2019, 11:05 AM · Restricted Project