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