diff options
author | Pedro Alvarez <pedro.alvarez@codethink.co.uk> | 2016-05-27 17:39:31 +0100 |
---|---|---|
committer | Pedro Alvarez <pedro.alvarez@codethink.co.uk> | 2016-05-27 17:53:32 +0100 |
commit | 26c75cf8267919f81a1759c9c965a52c660233f9 (patch) | |
tree | cf2a39cf56c2c8ac45760854413ab233e6263974 /gmp/mpz/cong_2exp.c | |
parent | 56892c1d217baea02092b51a09bbc924130ca84c (diff) | |
download | gcc-tarball-baserock/pedroalvarez/gcc-5.3.0-gmp432.tar.gz |
go to gmp 4.3.2baserock/pedroalvarez/gcc-5.3.0-gmp432
Diffstat (limited to 'gmp/mpz/cong_2exp.c')
-rw-r--r-- | gmp/mpz/cong_2exp.c | 137 |
1 files changed, 65 insertions, 72 deletions
diff --git a/gmp/mpz/cong_2exp.c b/gmp/mpz/cong_2exp.c index 8e78b17378..873f195b8f 100644 --- a/gmp/mpz/cong_2exp.c +++ b/gmp/mpz/cong_2exp.c @@ -1,57 +1,36 @@ /* mpz_congruent_2exp_p -- test congruence of mpz mod 2^n. -Copyright 2001, 2002, 2013 Free Software Foundation, Inc. +Copyright 2001, 2002 Free Software Foundation, Inc. This file is part of the GNU MP Library. The GNU MP Library is free software; you can redistribute it and/or modify -it under the terms of either: - - * the GNU Lesser General Public License as published by the Free - Software Foundation; either version 3 of the License, or (at your - option) any later version. - -or - - * the GNU General Public License as published by the Free Software - Foundation; either version 2 of the License, or (at your option) any - later version. - -or both in parallel, as here. +it under the terms of the GNU Lesser General Public License as published by +the Free Software Foundation; either version 3 of the License, or (at your +option) any later version. The GNU MP Library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License -for more details. +or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public +License for more details. -You should have received copies of the GNU General Public License and the -GNU Lesser General Public License along with the GNU MP Library. If not, -see https://www.gnu.org/licenses/. */ +You should have received a copy of the GNU Lesser General Public License +along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ #include "gmp.h" #include "gmp-impl.h" int -mpz_congruent_2exp_p (mpz_srcptr a, mpz_srcptr c, mp_bitcnt_t d) __GMP_NOTHROW +mpz_congruent_2exp_p (mpz_srcptr a, mpz_srcptr c, unsigned long d) { - mp_size_t i, dlimbs; - unsigned dbits; + unsigned long i, dlimbs, dbits; mp_ptr ap, cp; mp_limb_t dmask, alimb, climb, sum; - mp_size_t as, cs, asize, csize; + mp_size_t asize_signed, csize_signed, asize, csize; - as = SIZ(a); - asize = ABS(as); - - cs = SIZ(c); - csize = ABS(cs); - - if (asize < csize) - { - MPZ_SRCPTR_SWAP (a, c); - MP_SIZE_T_SWAP (asize, csize); - } + if (ABSIZ(a) < ABSIZ(c)) + MPZ_SRCPTR_SWAP (a, c); dlimbs = d / GMP_NUMB_BITS; dbits = d % GMP_NUMB_BITS; @@ -60,32 +39,38 @@ mpz_congruent_2exp_p (mpz_srcptr a, mpz_srcptr c, mp_bitcnt_t d) __GMP_NOTHROW ap = PTR(a); cp = PTR(c); - if (csize == 0) + asize_signed = SIZ(a); + asize = ABS(asize_signed); + + csize_signed = SIZ(c); + csize = ABS(csize_signed); + + if (csize_signed == 0) goto a_zeros; - if ((cs ^ as) >= 0) + if ((asize_signed ^ csize_signed) >= 0) { /* same signs, direct comparison */ /* a==c for limbs in common */ if (mpn_cmp (ap, cp, MIN (csize, dlimbs)) != 0) - return 0; + return 0; /* if that's all of dlimbs, then a==c for remaining bits */ if (csize > dlimbs) - return ((ap[dlimbs]-cp[dlimbs]) & dmask) == 0; + return ((ap[dlimbs]-cp[dlimbs]) & dmask) == 0; a_zeros: /* a remains, need all zero bits */ /* if d covers all of a and c, then must be exactly equal */ if (asize <= dlimbs) - return asize == csize; + return asize == csize; /* whole limbs zero */ for (i = csize; i < dlimbs; i++) - if (ap[i] != 0) - return 0; + if (ap[i] != 0) + return 0; /* partial limb zero */ return (ap[dlimbs] & dmask) == 0; @@ -95,55 +80,63 @@ mpz_congruent_2exp_p (mpz_srcptr a, mpz_srcptr c, mp_bitcnt_t d) __GMP_NOTHROW /* different signs, negated comparison */ /* common low zero limbs, stopping at first non-zeros, which must - match twos complement */ + match twos complement */ i = 0; - do - { - ASSERT (i < csize); /* always have a non-zero limb on c */ - alimb = ap[i]; - climb = cp[i]; - sum = (alimb + climb) & GMP_NUMB_MASK; - - if (i >= dlimbs) - return (sum & dmask) == 0; - ++i; - - /* require both zero, or first non-zeros as twos-complements */ - if (sum != 0) - return 0; - } while (alimb == 0); + for (;;) + { + ASSERT (i < csize); /* always have a non-zero limb on c */ + alimb = ap[i]; + climb = cp[i]; + sum = (alimb + climb) & GMP_NUMB_MASK; + + if (i >= dlimbs) + return (sum & dmask) == 0; + i++; + + /* require both zero, or first non-zeros as twos-complements */ + if (sum != 0) + return 0; + + if (alimb != 0) + break; + } /* further limbs matching as ones-complement */ - for (; i < csize; ++i) - { - alimb = ap[i]; - climb = cp[i]; - sum = alimb ^ climb ^ GMP_NUMB_MASK; + for (;;) + { + if (i >= csize) + break; + + alimb = ap[i]; + climb = cp[i]; + sum = (alimb + climb + 1) & GMP_NUMB_MASK; + + if (i >= dlimbs) + return (sum & dmask) == 0; - if (i >= dlimbs) - return (sum & dmask) == 0; + if (sum != 0) + return 0; - if (sum != 0) - return 0; - } + i++; + } /* no more c, so require all 1 bits in a */ if (asize < dlimbs) - return 0; /* not enough a */ + return 0; /* not enough a */ /* whole limbs */ for ( ; i < dlimbs; i++) - if (ap[i] != GMP_NUMB_MAX) - return 0; + if (ap[i] != GMP_NUMB_MAX) + return 0; /* if only whole limbs, no further fetches from a */ if (dbits == 0) - return 1; + return 1; /* need enough a */ if (asize == dlimbs) - return 0; + return 0; return ((ap[dlimbs]+1) & dmask) == 0; } |