1/* mpz_divisible_ui_p -- mpz by ulong divisibility test.
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
25int
26mpz_divisible_ui_p (mpz_srcptr a, unsigned long d)
27{
28  mp_size_t  asize;
29  mp_ptr     ap;
30  unsigned   twos;
31
32  asize = SIZ(a);
33  if (UNLIKELY (d == 0))
34    return (asize == 0);
35
36  if (asize == 0)  /* 0 divisible by any d */
37    return 1;
38
39  /* For nails don't try to be clever if d is bigger than a limb, just fake
40     up an mpz_t and go to the main mpz_divisible_p.  */
41  if (d > GMP_NUMB_MAX)
42    {
43      mp_limb_t  dlimbs[2];
44      mpz_t      dz;
45      ALLOC(dz) = 2;
46      PTR(dz) = dlimbs;
47      mpz_set_ui (dz, d);
48      return mpz_divisible_p (a, dz);
49    }
50
51  ap = PTR(a);
52  asize = ABS(asize);  /* ignore sign of a */
53
54  if (ABOVE_THRESHOLD (asize, BMOD_1_TO_MOD_1_THRESHOLD))
55    return mpn_mod_1 (ap, asize, (mp_limb_t) d) == 0;
56
57  if (! (d & 1))
58    {
59      /* Strip low zero bits to get odd d required by modexact.  If d==e*2^n
60         and a is divisible by 2^n and by e, then it's divisible by d. */
61
62      if ((ap[0] & LOW_ZEROS_MASK (d)) != 0)
63        return 0;
64
65      count_trailing_zeros (twos, (mp_limb_t) d);
66      d >>= twos;
67    }
68
69  return mpn_modexact_1_odd (ap, asize, (mp_limb_t) d) == 0;
70}
71