1/* mpn_bdiv_qr -- Hensel division with precomputed inverse, returning quotient
2   and remainder.
3
4   Contributed to the GNU project by Torbjorn Granlund.
5
6   THE FUNCTIONS IN THIS FILE ARE INTERNAL WITH MUTABLE INTERFACES.  IT IS ONLY
7   SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN FACT, IT IS ALMOST
8   GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE GMP RELEASE.
9
10Copyright 2006, 2007, 2009 Free Software Foundation, Inc.
11
12This file is part of the GNU MP Library.
13
14The GNU MP Library is free software; you can redistribute it and/or modify
15it under the terms of the GNU Lesser General Public License as published by
16the Free Software Foundation; either version 3 of the License, or (at your
17option) any later version.
18
19The GNU MP Library is distributed in the hope that it will be useful, but
20WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
21or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
22License for more details.
23
24You should have received a copy of the GNU Lesser General Public License
25along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
26
27#include "gmp.h"
28#include "gmp-impl.h"
29
30
31/* Computes Q = N / D mod B^n,
32	    R = N - QD.	 */
33
34mp_limb_t
35mpn_bdiv_qr (mp_ptr qp, mp_ptr rp,
36	     mp_srcptr np, mp_size_t nn,
37	     mp_srcptr dp, mp_size_t dn,
38	     mp_ptr tp)
39{
40  mp_limb_t di;
41  mp_limb_t rh;
42
43  if (BELOW_THRESHOLD (dn, DC_BDIV_QR_THRESHOLD) ||
44      BELOW_THRESHOLD (nn - dn, DC_BDIV_QR_THRESHOLD))
45    {
46      MPN_COPY (tp, np, nn);
47      binvert_limb (di, dp[0]);  di = -di;
48      rh = mpn_sbpi1_bdiv_qr (qp, tp, nn, dp, dn, di);
49      MPN_COPY (rp, tp + nn - dn, dn);
50    }
51  else if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD))
52    {
53      MPN_COPY (tp, np, nn);
54      binvert_limb (di, dp[0]);  di = -di;
55      rh = mpn_dcpi1_bdiv_qr (qp, tp, nn, dp, dn, di);
56      MPN_COPY (rp, tp + nn - dn, dn);
57    }
58  else
59    {
60      rh = mpn_mu_bdiv_qr (qp, rp, np, nn, dp, dn, tp);
61    }
62
63  return rh;
64}
65
66mp_size_t
67mpn_bdiv_qr_itch (mp_size_t nn, mp_size_t dn)
68{
69  if (BELOW_THRESHOLD (dn, MU_BDIV_QR_THRESHOLD))
70    return nn;
71  else
72    return  mpn_mu_bdiv_qr_itch (nn, dn);
73}
74