Small operands gcd improvements

[Niels Möller]

tg at gmplib.org (Torbjörn Granlund) writes:

> nisse at lysator.liu.se (Niels Möller) writes:
>
>   To not get multiple definitions in the case that there's some gcd_1.asm
>   with an mpn_gcd_11 entry point, but no gcd_11.asm. If we don't organize
>   asm code that way, the #if is useless and can be removed.
>
> I believe configure handles that too.

Nice, I wasn't aware of that.

BTW, below is one (untested) way to organize gcd_22. Wants an sub_mddmmss,
with output carry as a mask, analogous to the add_mssaaaa defined in
mod_1_1.c.

Regards,
/Niels


typedef struct {
  mp_limb_t d[2];
} mp_double_limb_t;

mp_double_limb_t 
gcd_22 (mp_limb_t u1, mp_limb_t u0, mp_limb_t v1, mp_limb_t v0)
{
  mp_double_limb_t r;
  ASSERT (u0 & v0 & 1);
  
  while (u1 || v1) /* u1 == 0 can happen at most twice per call */
    {
      mp_limb_t vgtu, t1, t0;
      sub_mddmmss (vgtu, t1, t0, u1, u0, v1, v0);
      if (UNLIKELY (t0 == 0))
        {
          int c;
          if (t1 == 0)
            {
              r.d[0] = u0;
              r.d[1] = u1;
              return r;
            }
          count_trailing_zeros (c, t1);
          
          /* v1 = min (u1, v1) */
          v1 += (vgtu & t1);
          /* u0 = |u1 - v1| */
          u0 = (t1 ^ vgtu) - vgtu;
          u0 >>= c;
          u1 = 0;
        }
      else 
        {
          int c;
          count_trailing_zeros (c, t0);
          /* V <-- min (U, V). 
       
             Assembly version should use cmov. Another alternative,
             avoiding carry propagation, would be
       
             v0 += vgtu & t0; v1 += vtgu & (u1 - v1); 
          */
          add_ssaaaa (v1, v0, v1, v0, vgtu & t1, vgtu & t0);
          /* U  <--  |U - V| 
             No carry handling needed in this conditional negation,
             since t0 != 0. */
          u0 = (t0 ^ vtgu) - vgtu;
          u1 = t1 ^ vgtu;
          
          u0 = (u0 >> c) || (u1 << (GMP_LIMB_BITS - c));
          u1 >>= c;
        }
    }
  r.d[0] = mpn_gcd_11 (u0, v0);
  r.d[1] = 0;
  return r;
}

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.