1*86d7f5d3SJohn Marino /* mpz_divisible_ui_p -- mpz by ulong divisibility test.
2*86d7f5d3SJohn Marino
3*86d7f5d3SJohn Marino Copyright 2000, 2001, 2002 Free Software Foundation, Inc.
4*86d7f5d3SJohn Marino
5*86d7f5d3SJohn Marino This file is part of the GNU MP Library.
6*86d7f5d3SJohn Marino
7*86d7f5d3SJohn Marino The GNU MP Library is free software; you can redistribute it and/or modify
8*86d7f5d3SJohn Marino it under the terms of the GNU Lesser General Public License as published by
9*86d7f5d3SJohn Marino the Free Software Foundation; either version 3 of the License, or (at your
10*86d7f5d3SJohn Marino option) any later version.
11*86d7f5d3SJohn Marino
12*86d7f5d3SJohn Marino The GNU MP Library is distributed in the hope that it will be useful, but
13*86d7f5d3SJohn Marino WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14*86d7f5d3SJohn Marino or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public
15*86d7f5d3SJohn Marino License for more details.
16*86d7f5d3SJohn Marino
17*86d7f5d3SJohn Marino You should have received a copy of the GNU Lesser General Public License
18*86d7f5d3SJohn Marino along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */
19*86d7f5d3SJohn Marino
20*86d7f5d3SJohn Marino #include "gmp.h"
21*86d7f5d3SJohn Marino #include "gmp-impl.h"
22*86d7f5d3SJohn Marino #include "longlong.h"
23*86d7f5d3SJohn Marino
24*86d7f5d3SJohn Marino
25*86d7f5d3SJohn Marino int
mpz_divisible_ui_p(mpz_srcptr a,unsigned long d)26*86d7f5d3SJohn Marino mpz_divisible_ui_p (mpz_srcptr a, unsigned long d)
27*86d7f5d3SJohn Marino {
28*86d7f5d3SJohn Marino mp_size_t asize;
29*86d7f5d3SJohn Marino mp_ptr ap;
30*86d7f5d3SJohn Marino unsigned twos;
31*86d7f5d3SJohn Marino
32*86d7f5d3SJohn Marino asize = SIZ(a);
33*86d7f5d3SJohn Marino if (UNLIKELY (d == 0))
34*86d7f5d3SJohn Marino return (asize == 0);
35*86d7f5d3SJohn Marino
36*86d7f5d3SJohn Marino if (asize == 0) /* 0 divisible by any d */
37*86d7f5d3SJohn Marino return 1;
38*86d7f5d3SJohn Marino
39*86d7f5d3SJohn Marino /* For nails don't try to be clever if d is bigger than a limb, just fake
40*86d7f5d3SJohn Marino up an mpz_t and go to the main mpz_divisible_p. */
41*86d7f5d3SJohn Marino if (d > GMP_NUMB_MAX)
42*86d7f5d3SJohn Marino {
43*86d7f5d3SJohn Marino mp_limb_t dlimbs[2];
44*86d7f5d3SJohn Marino mpz_t dz;
45*86d7f5d3SJohn Marino ALLOC(dz) = 2;
46*86d7f5d3SJohn Marino PTR(dz) = dlimbs;
47*86d7f5d3SJohn Marino mpz_set_ui (dz, d);
48*86d7f5d3SJohn Marino return mpz_divisible_p (a, dz);
49*86d7f5d3SJohn Marino }
50*86d7f5d3SJohn Marino
51*86d7f5d3SJohn Marino ap = PTR(a);
52*86d7f5d3SJohn Marino asize = ABS(asize); /* ignore sign of a */
53*86d7f5d3SJohn Marino
54*86d7f5d3SJohn Marino if (ABOVE_THRESHOLD (asize, BMOD_1_TO_MOD_1_THRESHOLD))
55*86d7f5d3SJohn Marino return mpn_mod_1 (ap, asize, (mp_limb_t) d) == 0;
56*86d7f5d3SJohn Marino
57*86d7f5d3SJohn Marino if (! (d & 1))
58*86d7f5d3SJohn Marino {
59*86d7f5d3SJohn Marino /* Strip low zero bits to get odd d required by modexact. If d==e*2^n
60*86d7f5d3SJohn Marino and a is divisible by 2^n and by e, then it's divisible by d. */
61*86d7f5d3SJohn Marino
62*86d7f5d3SJohn Marino if ((ap[0] & LOW_ZEROS_MASK (d)) != 0)
63*86d7f5d3SJohn Marino return 0;
64*86d7f5d3SJohn Marino
65*86d7f5d3SJohn Marino count_trailing_zeros (twos, (mp_limb_t) d);
66*86d7f5d3SJohn Marino d >>= twos;
67*86d7f5d3SJohn Marino }
68*86d7f5d3SJohn Marino
69*86d7f5d3SJohn Marino return mpn_modexact_1_odd (ap, asize, (mp_limb_t) d) == 0;
70*86d7f5d3SJohn Marino }
71