Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Wed, 24 Jun 2015 07:32:56 +0300 (MSK)
From: Alexander Monakov <amonakov@...ras.ru>
To: musl@...ts.openwall.com
Subject: Re: [PATCH 2/5] dynlink.c: compute modulus via magic
 multiplication

On Wed, 24 Jun 2015, Rich Felker wrote:

> On Wed, Jun 24, 2015 at 02:24:52AM +0300, Alexander Monakov wrote:
> > +static uint32_t umod(uint32_t x, uint32_t div, struct udiv *p)
> > +{
> > +	if (!(div&(div-1)))
> > +		return x&(div-1);
> > +	uint32_t v = x;
> > +	if (p->s1) v >>= p->s1;
> > +	else if (v != ~0u) v += p->inc;
> > +	int s32=32, s2=p->s2;
> > +	if (sizeof(long) == 8)
> > +		s32+=s2, s2=0;
> > +	v = (1ull * v * p->mul) >> s32;
> > +	v >>= s2;
> > +	return x-v*div;
> > +}
> 
> I think having the div argument here is a pessimization.

How can I do the last step, 'x-v*div' without it?

> Power-of-two sizes are unlikely to be used,

probably so, but...

> and it's possible for precompute_udiv
> to setup the struct udiv to work perfectly fine for powers of two,

I gave it a thought, and I didn't find how to do that either.

> so that there is a single code path with no branches. The p->s1 branch
> should not be needed either.

p->s1 check is for this reason: shift are relatively costly, and s1 is rarely
non-zero, so try to skip the shift if possible; in the rare case the pre-shift
is non-zero, the check allows to skip the saturating increment operation.

Alexander

Powered by blists - more mailing lists

Your e-mail address:

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.