[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-ID: <20130725040648.GA12763@openwall.com>
Date: Thu, 25 Jul 2013 08:06:48 +0400
From: Solar Designer <solar@...nwall.com>
To: john-dev@...ts.openwall.com
Subject: Re: Parallella: bcrypt
On Thu, Jul 25, 2013 at 07:50:32AM +0400, Solar Designer wrote:
> Can the right shift by 22:
>
> y = x >> 22;
>
> be replaced with:
>
> y = (2 << 22) - x * 0xffbfffff;
>
> where 0xffbfffff is the multiplicative inverse for ((2 << 22) - 1).
No, that's totally wrong. Sorry.
> Would this work well enough for our purpose (where we only use 8 bits of
> the result, so don't need precision beyond that)? Note that, if needed,
> we can apply the AND mask before rather than after the simulated right
> shift - we have this flexibility.
>
> http://www.hackersdelight.org/magic.htm
We'd need IMUL producing 64-bit result for this, but we don't have that
with Epiphany. We can't use the multiplicative inverse because we'd
need to ensure that our input number is exactly divisible by a certain
odd number, and we can't achieve that with a mere mask.
Maybe you'll come up with another clever/crazy idea on how to do right
shifts with Epiphany's FPU instructions (like I mentioned, replacing one
right shift with multiple FPU instructions is OK).
> Another idea: rather than do:
>
> tmp4 = L >> 22; \
> tmp4 &= 0x3FC; \
>
> we can shift by 24 bits, which eliminates the need for a mask (we shift
> the 2 lower bits out, and the bits being shifted in from the left are
> all zeroes), and we can shift back by 2 bits using IMUL or IMADD (which
> we get for free, unlike the AND that we're saving).
This should work.
Alexander
Powered by blists - more mailing lists
Confused about mailing lists and their use?
Read about mailing lists on Wikipedia
and check out these
guidelines on proper formatting of your messages.
