1/* mpz_tdiv_qr(quot,rem,dividend,divisor) -- Set QUOT to DIVIDEND/DIVISOR,
2   and REM to DIVIDEND mod DIVISOR.
3
4Copyright 1991, 1993, 1994, 2000, 2001, 2005 Free Software Foundation, Inc.
5
6This file is part of the GNU MP Library.
7
8The GNU MP Library is free software; you can redistribute it and/or modify
9it under the terms of the GNU Lesser General Public License as published by
10the Free Software Foundation; either version 3 of the License, or (at your
11option) any later version.
12
13The GNU MP Library is distributed in the hope that it will be useful, but
14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
15or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
16License for more details.
17
18You should have received a copy of the GNU Lesser General Public License
19along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
20
21#include "gmp.h"
22#include "gmp-impl.h"
23#include "longlong.h"
24#ifdef BERKELEY_MP
25#include "mp.h"
26#endif
27
28void
29#ifndef BERKELEY_MP
30mpz_tdiv_qr (mpz_ptr quot, mpz_ptr rem, mpz_srcptr num, mpz_srcptr den)
31#else /* BERKELEY_MP */
32mdiv (mpz_srcptr num, mpz_srcptr den, mpz_ptr quot, mpz_ptr rem)
33#endif /* BERKELEY_MP */
34{
35  mp_size_t ql;
36  mp_size_t ns, ds, nl, dl;
37  mp_ptr np, dp, qp, rp;
38  TMP_DECL;
39
40  ns = SIZ (num);
41  ds = SIZ (den);
42  nl = ABS (ns);
43  dl = ABS (ds);
44  ql = nl - dl + 1;
45
46  if (dl == 0)
47    DIVIDE_BY_ZERO;
48
49  MPZ_REALLOC (rem, dl);
50
51  if (ql <= 0)
52    {
53      if (num != rem)
54	{
55	  mp_ptr np, rp;
56	  np = PTR (num);
57	  rp = PTR (rem);
58	  MPN_COPY (rp, np, nl);
59	  SIZ (rem) = SIZ (num);
60	}
61      /* This needs to follow the assignment to rem, in case the
62	 numerator and quotient are the same.  */
63      SIZ (quot) = 0;
64      return;
65    }
66
67  MPZ_REALLOC (quot, ql);
68
69  TMP_MARK;
70  qp = PTR (quot);
71  rp = PTR (rem);
72  np = PTR (num);
73  dp = PTR (den);
74
75  /* FIXME: We should think about how to handle the temporary allocation.
76     Perhaps mpn_tdiv_qr should handle it, since it anyway often needs to
77     allocate temp space.  */
78
79  /* Copy denominator to temporary space if it overlaps with the quotient
80     or remainder.  */
81  if (dp == rp || dp == qp)
82    {
83      mp_ptr tp;
84      tp = TMP_ALLOC_LIMBS (dl);
85      MPN_COPY (tp, dp, dl);
86      dp = tp;
87    }
88  /* Copy numerator to temporary space if it overlaps with the quotient or
89     remainder.  */
90  if (np == rp || np == qp)
91    {
92      mp_ptr tp;
93      tp = TMP_ALLOC_LIMBS (nl);
94      MPN_COPY (tp, np, nl);
95      np = tp;
96    }
97
98  mpn_tdiv_qr (qp, rp, 0L, np, nl, dp, dl);
99
100  ql -=  qp[ql - 1] == 0;
101  MPN_NORMALIZE (rp, dl);
102
103  SIZ (quot) = (ns ^ ds) >= 0 ? ql : -ql;
104  SIZ (rem) = ns >= 0 ? dl : -dl;
105  TMP_FREE;
106}
107