cong_ui.c revision 1.1.1.1
1/* mpz_congruent_ui_p -- test congruence of mpz and ulong. 2 3Copyright 2000, 2001, 2002 Free Software Foundation, Inc. 4 5This file is part of the GNU MP Library. 6 7The GNU MP Library is free software; you can redistribute it and/or modify 8it under the terms of the GNU Lesser General Public License as published by 9the Free Software Foundation; either version 3 of the License, or (at your 10option) any later version. 11 12The GNU MP Library is distributed in the hope that it will be useful, but 13WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 14or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 15License for more details. 16 17You should have received a copy of the GNU Lesser General Public License 18along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 19 20#include "gmp.h" 21#include "gmp-impl.h" 22#include "longlong.h" 23 24 25/* There's some explicit checks for c<d since it seems reasonably likely an 26 application might use that in a test. 27 28 Hopefully the compiler can generate something good for r==(c%d), though 29 if modexact is being used exclusively then that's not reached. */ 30 31int 32mpz_congruent_ui_p (mpz_srcptr a, unsigned long cu, unsigned long du) 33{ 34 mp_srcptr ap; 35 mp_size_t asize; 36 mp_limb_t c, d, r; 37 38 if (UNLIKELY (du == 0)) 39 return (mpz_cmp_ui (a, cu) == 0); 40 41 asize = SIZ(a); 42 if (asize == 0) 43 { 44 if (cu < du) 45 return cu == 0; 46 else 47 return (cu % du) == 0; 48 } 49 50 /* For nails don't try to be clever if c or d is bigger than a limb, just 51 fake up some mpz_t's and go to the main mpz_congruent_p. */ 52 if (du > GMP_NUMB_MAX || cu > GMP_NUMB_MAX) 53 { 54 mp_limb_t climbs[2], dlimbs[2]; 55 mpz_t cz, dz; 56 57 ALLOC(cz) = 2; 58 PTR(cz) = climbs; 59 ALLOC(dz) = 2; 60 PTR(dz) = dlimbs; 61 62 mpz_set_ui (cz, cu); 63 mpz_set_ui (dz, du); 64 return mpz_congruent_p (a, cz, dz); 65 } 66 67 /* NEG_MOD works on limbs, so convert ulong to limb */ 68 c = cu; 69 d = du; 70 71 if (asize < 0) 72 { 73 asize = -asize; 74 NEG_MOD (c, c, d); 75 } 76 77 ap = PTR (a); 78 79 if (ABOVE_THRESHOLD (asize, BMOD_1_TO_MOD_1_THRESHOLD)) 80 { 81 r = mpn_mod_1 (ap, asize, d); 82 if (c < d) 83 return r == c; 84 else 85 return r == (c % d); 86 } 87 88 if ((d & 1) == 0) 89 { 90 /* Strip low zero bits to get odd d required by modexact. If 91 d==e*2^n then a==c mod d if and only if both a==c mod 2^n 92 and a==c mod e. */ 93 94 unsigned twos; 95 96 if ((ap[0]-c) & LOW_ZEROS_MASK (d)) 97 return 0; 98 99 count_trailing_zeros (twos, d); 100 d >>= twos; 101 } 102 103 r = mpn_modexact_1c_odd (ap, asize, d, c); 104 return r == 0 || r == d; 105} 106