Suggested mpn/generic/gcd.c patch

[Torbjörn Granlund]

This patch gets rid of the gcd_1 call and instead handles everything
with gcd_11 and gcd_22.  It also lifts the operands into registers.

Niels, do you agree with this?  Marco?

We discussed a gcd_21 in the past, and here again is a utility for it.
It is behind an UNLIKELY just as it is unlikely within gcd_22, so not
super important.  Perhaps gcd_21 is more common as operands directly
from user code.

We surely could make gcd_21 fast now with the table based algorithm; 4
bits per iteration is easy when the operands have different sizes of > 4
bits.  Or even binary euclid for machines with fast small quotient
division.

2019-09-09  Torbjörn Granlund  <tg at gmplib.org>

	* mpn/generic/gcd.c: Rewrite tail of function.

*** /tmp/extdiff.zlppJi/gmp-main.cf5765234af8/mpn/generic/gcd.c	Sun Sep  8 21:55:22 2019
--- /home/tege/prec/gmp-main/mpn/generic/gcd.c	Mon Sep  9 21:10:41 2019
***************
*** 218,252 ****
    ASSERT(up[n-1] | vp[n-1]);
  
!   if (n == 1)
!     {
!       *gp = mpn_gcd_1(up, 1, vp[0]);
!       ctx.gn = 1;
!       goto done;
!     }
! 
!   /* Due to the calling convention for mpn_gcd, at most one can be
!      even. */
! 
    if (! (up[0] & 1))
      MP_PTR_SWAP (up, vp);
  
!   ASSERT (up[0] & 1);
  
!   if (vp[0] == 0)
!     {
!       *gp = mpn_gcd_1 (up, 2, vp[1]);
!       ctx.gn = 1;
!       goto done;
!     }
!   else if (! (vp[0] & 1))
!     {
!       int r;
!       count_trailing_zeros (r, vp[0]);
!       vp[0] = ((vp[1] << (GMP_NUMB_BITS - r)) & GMP_NUMB_MASK) | (vp[0] >> r);
!       vp[1] >>= r;
!     }
  
!   {
!     mp_double_limb_t g = mpn_gcd_22 (up[1], up[0], vp[1], vp[0]);
      gp[0] = g.d0;
      gp[1] = g.d1;
--- 218,261 ----
    ASSERT(up[n-1] | vp[n-1]);
  
!   /* Due to the calling convention for mpn_gcd, at most one can be even. */
    if (! (up[0] & 1))
      MP_PTR_SWAP (up, vp);
  
!   {
!     mp_limb_t u0, u1, v0, v1;
!     mp_double_limb_t g;
  
!     u0 = up[0];
!     v0 = vp[0];
  
!     if (n == 1)
!       {
! 	int cnt;
! 	count_trailing_zeros (cnt, v0);
! 	*gp = mpn_gcd_11 (u0, v0 >> cnt);
! 	ctx.gn = 1;
! 	goto done;
!       }
! 
!     ASSERT ((u0 & 1) != 0);
! 
!     v1 = vp[1];
!     if (UNLIKELY (v0 == 0))
!       {
! 	v0 = v1;
! 	v1 = 0;
! 	/* FIXME: We could invoke a mpn_gcd_21 here, just like mpn_gcd_22 could
! 	   when this situation occurs internally.
!       }
!     if ((v0 & 1) == 0)
!       {
! 	int cnt;
! 	count_trailing_zeros (cnt, v0);
! 	v0 = ((v1 << (GMP_NUMB_BITS - cnt)) & GMP_NUMB_MASK) | (v0 >> cnt);
! 	v1 >>= cnt;
!       }
! 
!     u1 = up[1];
!     g = mpn_gcd_22 (u1, u0, v1, v0);
      gp[0] = g.d0;
      gp[1] = g.d1;


-- 
Torbjörn
Please encrypt, key id 0xC8601622