1 /* dmincl.c -- include file for tdiv_qr.c, tdiv_r.c.
3 Copyright (C) 1991, 1993, 1994, 1996 Free Software Foundation, Inc.
5 This file is part of the GNU MP Library.
7 The GNU MP Library is free software; you can redistribute it and/or modify
8 it under the terms of the GNU Library General Public License as published by
9 the Free Software Foundation; either version 2 of the License, or (at your
10 option) any later version.
12 The GNU MP Library is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
14 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
15 License for more details.
17 You should have received a copy of the GNU Library General Public License
18 along with the GNU MP Library; see the file COPYING.LIB. If not, write to
19 the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
20 MA 02111-1307, USA. */
22 /* If den == quot, den needs temporary storage.
23 If den == rem, den needs temporary storage.
24 If num == quot, num needs temporary storage.
25 If den has temporary storage, it can be normalized while being copied,
26 i.e no extra storage should be allocated. */
28 /* This is the function body of mdiv, mpz_divmod, and mpz_mod.
30 If COMPUTE_QUOTIENT is defined, the quotient is put in the MP_INT
31 object quot, otherwise that variable is not referenced at all.
33 The remainder is always computed, and the result is put in the MP_INT
39 mp_size_t nsize = num->_mp_size;
40 mp_size_t dsize = den->_mp_size;
41 mp_size_t qsize, rsize;
42 mp_size_t sign_remainder = nsize;
43 #ifdef COMPUTE_QUOTIENT
44 mp_size_t sign_quotient = nsize ^ dsize;
46 unsigned normalization_steps;
53 /* Ensure space is enough for quotient and remainder. */
55 /* We need space for an extra limb in the remainder, because it's
56 up-shifted (normalized) below. */
58 if (rem->_mp_alloc < rsize)
59 _mpz_realloc (rem, rsize);
61 qsize = rsize - dsize; /* qsize cannot be bigger than this. */
66 rem->_mp_size = num->_mp_size;
67 MPN_COPY (rem->_mp_d, num->_mp_d, nsize);
69 #ifdef COMPUTE_QUOTIENT
70 /* This needs to follow the assignment to rem, in case the
71 numerator and quotient are the same. */
77 #ifdef COMPUTE_QUOTIENT
78 if (quot->_mp_alloc < qsize)
79 _mpz_realloc (quot, qsize);
82 /* Read pointers here, when reallocation is finished. */
87 /* Optimize division by a single-limb divisor. */
91 #ifdef COMPUTE_QUOTIENT
93 rlimb = mpn_divmod_1 (qp, np, nsize, dp[0]);
94 qsize -= qp[qsize - 1] == 0;
95 quot->_mp_size = sign_quotient >= 0 ? qsize : -qsize;
97 rlimb = mpn_mod_1 (np, nsize, dp[0]);
101 rem->_mp_size = sign_remainder >= 0 ? rsize : -rsize;
107 #ifdef COMPUTE_QUOTIENT
110 /* Make sure QP and NP point to different objects. Otherwise the
111 numerator would be gradually overwritten by the quotient limbs. */
114 /* Copy NP object to temporary space. */
115 np = (mp_ptr) TMP_ALLOC (nsize * BYTES_PER_MP_LIMB);
116 MPN_COPY (np, qp, nsize);
120 /* Put quotient at top of remainder. */
124 count_leading_zeros (normalization_steps, dp[dsize - 1]);
126 /* Normalize the denominator, i.e. make its most significant bit set by
127 shifting it NORMALIZATION_STEPS bits to the left. Also shift the
128 numerator the same number of steps (to keep the quotient the same!). */
129 if (normalization_steps != 0)
134 /* Shift up the denominator setting the most significant bit of
135 the most significant word. Use temporary storage not to clobber
136 the original contents of the denominator. */
137 tp = (mp_ptr) TMP_ALLOC (dsize * BYTES_PER_MP_LIMB);
138 mpn_lshift (tp, dp, dsize, normalization_steps);
141 /* Shift up the numerator, possibly introducing a new most
142 significant word. Move the shifted numerator in the remainder
144 nlimb = mpn_lshift (rp, np, nsize, normalization_steps);
155 /* The denominator is already normalized, as required. Copy it to
156 temporary space if it overlaps with the quotient or remainder. */
157 #ifdef COMPUTE_QUOTIENT
158 if (dp == rp || dp == qp)
165 tp = (mp_ptr) TMP_ALLOC (dsize * BYTES_PER_MP_LIMB);
166 MPN_COPY (tp, dp, dsize);
170 /* Move the numerator to the remainder. */
172 MPN_COPY (rp, np, nsize);
177 q_limb = mpn_divmod (qp, rp, rsize, dp, dsize);
179 #ifdef COMPUTE_QUOTIENT
180 qsize = rsize - dsize;
187 quot->_mp_size = sign_quotient >= 0 ? qsize : -qsize;
191 MPN_NORMALIZE (rp, rsize);
193 if (normalization_steps != 0 && rsize != 0)
195 mpn_rshift (rp, rp, rsize, normalization_steps);
196 rsize -= rp[rsize - 1] == 0;
199 rem->_mp_size = sign_remainder >= 0 ? rsize : -rsize;