|
Packit |
5c3484 |
/* mpn_gcd_1 -- mpn and limb greatest common divisor.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
Copyright 1994, 1996, 2000, 2001, 2009, 2012 Free Software Foundation, Inc.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
This file is part of the GNU MP Library.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is free software; you can redistribute it and/or modify
|
|
Packit |
5c3484 |
it under the terms of either:
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU Lesser General Public License as published by the Free
|
|
Packit |
5c3484 |
Software Foundation; either version 3 of the License, or (at your
|
|
Packit |
5c3484 |
option) any later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
* the GNU General Public License as published by the Free Software
|
|
Packit |
5c3484 |
Foundation; either version 2 of the License, or (at your option) any
|
|
Packit |
5c3484 |
later version.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
or both in parallel, as here.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The GNU MP Library is distributed in the hope that it will be useful, but
|
|
Packit |
5c3484 |
WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
|
|
Packit |
5c3484 |
or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
Packit |
5c3484 |
for more details.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
You should have received copies of the GNU General Public License and the
|
|
Packit |
5c3484 |
GNU Lesser General Public License along with the GNU MP Library. If not,
|
|
Packit |
5c3484 |
see https://www.gnu.org/licenses/. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#include "gmp.h"
|
|
Packit |
5c3484 |
#include "gmp-impl.h"
|
|
Packit |
5c3484 |
#include "longlong.h"
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#ifndef GCD_1_METHOD
|
|
Packit |
5c3484 |
#define GCD_1_METHOD 2
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#define USE_ZEROTAB 0
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if USE_ZEROTAB
|
|
Packit |
5c3484 |
#define MAXSHIFT 4
|
|
Packit |
5c3484 |
#define MASK ((1 << MAXSHIFT) - 1)
|
|
Packit |
5c3484 |
static const unsigned char zerotab[1 << MAXSHIFT] =
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
#if MAXSHIFT > 4
|
|
Packit |
5c3484 |
5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
|
|
Packit |
5c3484 |
};
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Does not work for U == 0 or V == 0. It would be tough to make it work for
|
|
Packit |
5c3484 |
V == 0 since gcd(x,0) = x, and U does not generally fit in an mp_limb_t.
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
The threshold for doing u%v when size==1 will vary by CPU according to
|
|
Packit |
5c3484 |
the speed of a division and the code generated for the main loop. Any
|
|
Packit |
5c3484 |
tuning for this is left to a CPU specific implementation. */
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
mp_limb_t
|
|
Packit |
5c3484 |
mpn_gcd_1 (mp_srcptr up, mp_size_t size, mp_limb_t vlimb)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
mp_limb_t ulimb;
|
|
Packit |
5c3484 |
unsigned long zero_bits, u_low_zero_bits;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (size >= 1);
|
|
Packit |
5c3484 |
ASSERT (vlimb != 0);
|
|
Packit |
5c3484 |
ASSERT_MPN_NONZERO_P (up, size);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ulimb = up[0];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* Need vlimb odd for modexact, want it odd to get common zeros. */
|
|
Packit |
5c3484 |
count_trailing_zeros (zero_bits, vlimb);
|
|
Packit |
5c3484 |
vlimb >>= zero_bits;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (size > 1)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
/* Must get common zeros before the mod reduction. If ulimb==0 then
|
|
Packit |
5c3484 |
vlimb already gives the common zeros. */
|
|
Packit |
5c3484 |
if (ulimb != 0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
count_trailing_zeros (u_low_zero_bits, ulimb);
|
|
Packit |
5c3484 |
zero_bits = MIN (zero_bits, u_low_zero_bits);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ulimb = MPN_MOD_OR_MODEXACT_1_ODD (up, size, vlimb);
|
|
Packit |
5c3484 |
if (ulimb == 0)
|
|
Packit |
5c3484 |
goto done;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
goto strip_u_maybe;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* size==1, so up[0]!=0 */
|
|
Packit |
5c3484 |
count_trailing_zeros (u_low_zero_bits, ulimb);
|
|
Packit |
5c3484 |
ulimb >>= u_low_zero_bits;
|
|
Packit |
5c3484 |
zero_bits = MIN (zero_bits, u_low_zero_bits);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* make u bigger */
|
|
Packit |
5c3484 |
if (vlimb > ulimb)
|
|
Packit |
5c3484 |
MP_LIMB_T_SWAP (ulimb, vlimb);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* if u is much bigger than v, reduce using a division rather than
|
|
Packit |
5c3484 |
chipping away at it bit-by-bit */
|
|
Packit |
5c3484 |
if ((ulimb >> 16) > vlimb)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ulimb %= vlimb;
|
|
Packit |
5c3484 |
if (ulimb == 0)
|
|
Packit |
5c3484 |
goto done;
|
|
Packit |
5c3484 |
goto strip_u_maybe;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ASSERT (ulimb & 1);
|
|
Packit |
5c3484 |
ASSERT (vlimb & 1);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if GCD_1_METHOD == 1
|
|
Packit |
5c3484 |
while (ulimb != vlimb)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ASSERT (ulimb & 1);
|
|
Packit |
5c3484 |
ASSERT (vlimb & 1);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
if (ulimb > vlimb)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ulimb -= vlimb;
|
|
Packit |
5c3484 |
do
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ulimb >>= 1;
|
|
Packit |
5c3484 |
ASSERT (ulimb != 0);
|
|
Packit |
5c3484 |
strip_u_maybe:
|
|
Packit |
5c3484 |
;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
while ((ulimb & 1) == 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
else /* vlimb > ulimb. */
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
vlimb -= ulimb;
|
|
Packit |
5c3484 |
do
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
vlimb >>= 1;
|
|
Packit |
5c3484 |
ASSERT (vlimb != 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
while ((vlimb & 1) == 0);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
# if GCD_1_METHOD == 2
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
ulimb >>= 1;
|
|
Packit |
5c3484 |
vlimb >>= 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
while (ulimb != vlimb)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
int c;
|
|
Packit |
5c3484 |
mp_limb_t t;
|
|
Packit |
5c3484 |
mp_limb_t vgtu;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
t = ulimb - vlimb;
|
|
Packit |
5c3484 |
vgtu = LIMB_HIGHBIT_TO_MASK (t);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* v <-- min (u, v) */
|
|
Packit |
5c3484 |
vlimb += (vgtu & t);
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
/* u <-- |u - v| */
|
|
Packit |
5c3484 |
ulimb = (t ^ vgtu) - vgtu;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
#if USE_ZEROTAB
|
|
Packit |
5c3484 |
/* Number of trailing zeros is the same no matter if we look at
|
|
Packit |
5c3484 |
* t or ulimb, but using t gives more parallelism. */
|
|
Packit |
5c3484 |
c = zerotab[t & MASK];
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
while (UNLIKELY (c == MAXSHIFT))
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
ulimb >>= MAXSHIFT;
|
|
Packit |
5c3484 |
if (0)
|
|
Packit |
5c3484 |
strip_u_maybe:
|
|
Packit |
5c3484 |
vlimb >>= 1;
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
c = zerotab[ulimb & MASK];
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
#else
|
|
Packit |
5c3484 |
if (0)
|
|
Packit |
5c3484 |
{
|
|
Packit |
5c3484 |
strip_u_maybe:
|
|
Packit |
5c3484 |
vlimb >>= 1;
|
|
Packit |
5c3484 |
t = ulimb;
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
count_trailing_zeros (c, t);
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
ulimb >>= (c + 1);
|
|
Packit |
5c3484 |
}
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
vlimb = (vlimb << 1) | 1;
|
|
Packit |
5c3484 |
# else
|
|
Packit |
5c3484 |
# error Unknown GCD_1_METHOD
|
|
Packit |
5c3484 |
# endif
|
|
Packit |
5c3484 |
#endif
|
|
Packit |
5c3484 |
|
|
Packit |
5c3484 |
done:
|
|
Packit |
5c3484 |
return vlimb << zero_bits;
|
|
Packit |
5c3484 |
}
|