1/* mpz_cdiv_r_ui -- Division rounding the quotient towards +infinity.  The
2   remainder gets the opposite sign as the denominator.  In order to make it
3   always fit into the return type, the negative of the true remainder is
4   returned.
5
6Copyright 1994, 1995, 1996, 2001, 2002, 2004, 2005 Free Software Foundation,
7Inc.
8
9This file is part of the GNU MP Library.
10
11The GNU MP Library is free software; you can redistribute it and/or modify
12it under the terms of the GNU Lesser General Public License as published by
13the Free Software Foundation; either version 3 of the License, or (at your
14option) any later version.
15
16The GNU MP Library is distributed in the hope that it will be useful, but
17WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
18or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
19License for more details.
20
21You should have received a copy of the GNU Lesser General Public License
22along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
23
24#include "gmp.h"
25#include "gmp-impl.h"
26
27unsigned long int
28mpz_cdiv_r_ui (mpz_ptr rem, mpz_srcptr dividend, unsigned long int divisor)
29{
30  mp_size_t ns, nn;
31  mp_ptr np;
32  mp_limb_t rl;
33
34  if (divisor == 0)
35    DIVIDE_BY_ZERO;
36
37  ns = SIZ(dividend);
38  if (ns == 0)
39    {
40      SIZ(rem) = 0;
41      return 0;
42    }
43
44  nn = ABS(ns);
45  np = PTR(dividend);
46#if BITS_PER_ULONG > GMP_NUMB_BITS  /* avoid warnings about shift amount */
47  if (divisor > GMP_NUMB_MAX)
48    {
49      mp_limb_t dp[2];
50      mp_ptr rp, qp;
51      mp_size_t rn;
52      TMP_DECL;
53
54      MPZ_REALLOC (rem, 2);
55      rp = PTR(rem);
56
57      if (nn == 1)		/* tdiv_qr requirements; tested above for 0 */
58	{
59	  rl = np[0];
60	  rp[0] = rl;
61	}
62      else
63	{
64	  TMP_MARK;
65	  dp[0] = divisor & GMP_NUMB_MASK;
66	  dp[1] = divisor >> GMP_NUMB_BITS;
67	  qp = TMP_ALLOC_LIMBS (nn - 2 + 1);
68	  mpn_tdiv_qr (qp, rp, (mp_size_t) 0, np, nn, dp, (mp_size_t) 2);
69	  TMP_FREE;
70	  rl = rp[0] + (rp[1] << GMP_NUMB_BITS);
71	}
72
73      if (rl != 0 && ns >= 0)
74	{
75	  rl = divisor - rl;
76	  rp[0] = rl & GMP_NUMB_MASK;
77	  rp[1] = rl >> GMP_NUMB_BITS;
78	}
79
80      rn = 1 + (rl > GMP_NUMB_MAX);  rn -= (rp[rn - 1] == 0);
81      SIZ(rem) = -rn;
82    }
83  else
84#endif
85    {
86      rl = mpn_mod_1 (np, nn, (mp_limb_t) divisor);
87      if (rl == 0)
88	SIZ(rem) = 0;
89      else
90	{
91	  if (ns >= 0)
92	    rl = divisor - rl;
93
94	  PTR(rem)[0] = rl;
95	  SIZ(rem) = -1;
96	}
97    }
98
99  return rl;
100}
101