```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