0000: 2f 2a 20 6d 70 6e 5f 74 64 69 76 5f 71 72 20 2d /* mpn_tdiv_qr -
0010: 2d 20 44 69 76 69 64 65 20 74 68 65 20 6e 75 6d - Divide the num
0020: 65 72 61 74 6f 72 20 28 6e 70 2c 6e 6e 29 20 62 erator (np,nn) b
0030: 79 20 74 68 65 20 64 65 6e 6f 6d 69 6e 61 74 6f y the denominato
0040: 72 20 28 64 70 2c 64 6e 29 20 61 6e 64 0a 20 20 r (dp,dn) and.
0050: 20 77 72 69 74 65 20 74 68 65 20 6e 6e 2d 64 6e write the nn-dn
0060: 2b 31 20 71 75 6f 74 69 65 6e 74 20 6c 69 6d 62 +1 quotient limb
0070: 73 20 61 74 20 71 70 20 61 6e 64 20 74 68 65 20 s at qp and the
0080: 64 6e 20 72 65 6d 61 69 6e 64 65 72 20 6c 69 6d dn remainder lim
0090: 62 73 20 61 74 20 72 70 2e 20 20 49 66 0a 20 20 bs at rp. If.
00a0: 20 71 78 6e 20 69 73 20 6e 6f 6e 2d 7a 65 72 6f qxn is non-zero
00b0: 2c 20 67 65 6e 65 72 61 74 65 20 74 68 61 74 20 , generate that
00c0: 6d 61 6e 79 20 66 72 61 63 74 69 6f 6e 20 6c 69 many fraction li
00d0: 6d 62 73 20 61 6e 64 20 61 70 70 65 6e 64 20 74 mbs and append t
00e0: 68 65 6d 20 61 66 74 65 72 20 74 68 65 0a 20 20 hem after the.
00f0: 20 6f 74 68 65 72 20 71 75 6f 74 69 65 6e 74 20 other quotient
0100: 6c 69 6d 62 73 2c 20 61 6e 64 20 75 70 64 61 74 limbs, and updat
0110: 65 20 74 68 65 20 72 65 6d 61 69 6e 64 65 72 20 e the remainder
0120: 61 63 63 6f 72 64 6e 69 6e 67 6c 79 2e 20 20 54 accordningly. T
0130: 68 65 20 69 6e 70 75 74 0a 20 20 20 6f 70 65 72 he input. oper
0140: 61 6e 64 73 20 61 72 65 20 75 6e 61 66 66 65 63 ands are unaffec
0150: 74 65 64 2e 0a 0a 20 20 20 50 72 65 63 6f 6e 64 ted... Precond
0160: 69 74 69 6f 6e 73 3a 0a 20 20 20 31 2e 20 54 68 itions:. 1. Th
0170: 65 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61 e most significa
0180: 6e 74 20 6c 69 6d 62 20 6f 66 20 6f 66 20 74 68 nt limb of of th
0190: 65 20 64 69 76 69 73 6f 72 20 6d 75 73 74 20 62 e divisor must b
01a0: 65 20 6e 6f 6e 2d 7a 65 72 6f 2e 0a 20 20 20 32 e non-zero.. 2
01b0: 2e 20 4e 6f 20 61 72 67 75 6d 65 6e 74 20 6f 76 . No argument ov
01c0: 65 72 6c 61 70 20 69 73 20 70 65 72 6d 69 74 74 erlap is permitt
01d0: 65 64 2e 20 20 28 3f 3f 3f 20 72 65 6c 61 78 20 ed. (??? relax
01e0: 74 68 69 73 20 3f 3f 3f 29 0a 20 20 20 33 2e 20 this ???). 3.
01f0: 6e 6e 20 3e 3d 20 64 6e 2c 20 65 76 65 6e 20 69 nn >= dn, even i
0200: 66 20 71 78 6e 20 69 73 20 6e 6f 6e 2d 7a 65 72 f qxn is non-zer
0210: 6f 2e 20 20 28 3f 3f 3f 20 72 65 6c 61 78 20 74 o. (??? relax t
0220: 68 69 73 20 3f 3f 3f 29 0a 0a 20 20 20 54 68 65 his ???).. The
0230: 20 74 69 6d 65 20 63 6f 6d 70 6c 65 78 69 74 79 time complexity
0240: 20 6f 66 20 74 68 69 73 20 69 73 20 4f 28 71 6e of this is O(qn
0250: 2a 71 6e 2b 4d 28 64 6e 2c 71 6e 29 29 2c 20 77 *qn+M(dn,qn)), w
0260: 68 65 72 65 20 4d 28 6d 2c 6e 29 20 69 73 20 74 here M(m,n) is t
0270: 68 65 20 74 69 6d 65 0a 20 20 20 63 6f 6d 70 6c he time. compl
0280: 65 78 69 74 79 20 6f 66 20 6d 75 6c 74 69 70 6c exity of multipl
0290: 69 63 61 74 69 6f 6e 2e 0a 0a 43 6f 70 79 72 69 ication...Copyri
02a0: 67 68 74 20 31 39 39 37 2c 20 32 30 30 30 2c 20 ght 1997, 2000,
02b0: 32 30 30 31 2c 20 32 30 30 32 20 46 72 65 65 20 2001, 2002 Free
02c0: 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 61 74 Software Foundat
02d0: 69 6f 6e 2c 20 49 6e 63 2e 0a 0a 54 68 69 73 20 ion, Inc...This
02e0: 66 69 6c 65 20 69 73 20 70 61 72 74 20 6f 66 20 file is part of
02f0: 74 68 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 the GNU MP Libra
0300: 72 79 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 ry...The GNU MP
0310: 4c 69 62 72 61 72 79 20 69 73 20 66 72 65 65 20 Library is free
0320: 73 6f 66 74 77 61 72 65 3b 20 79 6f 75 20 63 61 software; you ca
0330: 6e 20 72 65 64 69 73 74 72 69 62 75 74 65 20 69 n redistribute i
0340: 74 20 61 6e 64 2f 6f 72 20 6d 6f 64 69 66 79 0a t and/or modify.
0350: 69 74 20 75 6e 64 65 72 20 74 68 65 20 74 65 72 it under the ter
0360: 6d 73 20 6f 66 20 74 68 65 20 47 4e 55 20 4c 65 ms of the GNU Le
0370: 73 73 65 72 20 47 65 6e 65 72 61 6c 20 50 75 62 sser General Pub
0380: 6c 69 63 20 4c 69 63 65 6e 73 65 20 61 73 20 70 lic License as p
0390: 75 62 6c 69 73 68 65 64 20 62 79 0a 74 68 65 20 ublished by.the
03a0: 46 72 65 65 20 53 6f 66 74 77 61 72 65 20 46 6f Free Software Fo
03b0: 75 6e 64 61 74 69 6f 6e 3b 20 65 69 74 68 65 72 undation; either
03c0: 20 76 65 72 73 69 6f 6e 20 32 2e 31 20 6f 66 20 version 2.1 of
03d0: 74 68 65 20 4c 69 63 65 6e 73 65 2c 20 6f 72 20 the License, or
03e0: 28 61 74 20 79 6f 75 72 0a 6f 70 74 69 6f 6e 29 (at your.option)
03f0: 20 61 6e 79 20 6c 61 74 65 72 20 76 65 72 73 69 any later versi
0400: 6f 6e 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 on...The GNU MP
0410: 4c 69 62 72 61 72 79 20 69 73 20 64 69 73 74 72 Library is distr
0420: 69 62 75 74 65 64 20 69 6e 20 74 68 65 20 68 6f ibuted in the ho
0430: 70 65 20 74 68 61 74 20 69 74 20 77 69 6c 6c 20 pe that it will
0440: 62 65 20 75 73 65 66 75 6c 2c 20 62 75 74 0a 57 be useful, but.W
0450: 49 54 48 4f 55 54 20 41 4e 59 20 57 41 52 52 41 ITHOUT ANY WARRA
0460: 4e 54 59 3b 20 77 69 74 68 6f 75 74 20 65 76 65 NTY; without eve
0470: 6e 20 74 68 65 20 69 6d 70 6c 69 65 64 20 77 61 n the implied wa
0480: 72 72 61 6e 74 79 20 6f 66 20 4d 45 52 43 48 41 rranty of MERCHA
0490: 4e 54 41 42 49 4c 49 54 59 0a 6f 72 20 46 49 54 NTABILITY.or FIT
04a0: 4e 45 53 53 20 46 4f 52 20 41 20 50 41 52 54 49 NESS FOR A PARTI
04b0: 43 55 4c 41 52 20 50 55 52 50 4f 53 45 2e 20 20 CULAR PURPOSE.
04c0: 53 65 65 20 74 68 65 20 47 4e 55 20 4c 65 73 73 See the GNU Less
04d0: 65 72 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 er General Publi
04e0: 63 0a 4c 69 63 65 6e 73 65 20 66 6f 72 20 6d 6f c.License for mo
04f0: 72 65 20 64 65 74 61 69 6c 73 2e 0a 0a 59 6f 75 re details...You
0500: 20 73 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 should have rec
0510: 65 69 76 65 64 20 61 20 63 6f 70 79 20 6f 66 20 eived a copy of
0520: 74 68 65 20 47 4e 55 20 4c 65 73 73 65 72 20 47 the GNU Lesser G
0530: 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 20 4c 69 eneral Public Li
0540: 63 65 6e 73 65 0a 61 6c 6f 6e 67 20 77 69 74 68 cense.along with
0550: 20 74 68 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 the GNU MP Libr
0560: 61 72 79 3b 20 73 65 65 20 74 68 65 20 66 69 6c ary; see the fil
0570: 65 20 43 4f 50 59 49 4e 47 2e 4c 49 42 2e 20 20 e COPYING.LIB.
0580: 49 66 20 6e 6f 74 2c 20 77 72 69 74 65 20 74 6f If not, write to
0590: 0a 74 68 65 20 46 72 65 65 20 53 6f 66 74 77 61 .the Free Softwa
05a0: 72 65 20 46 6f 75 6e 64 61 74 69 6f 6e 2c 20 49 re Foundation, I
05b0: 6e 63 2e 2c 20 35 39 20 54 65 6d 70 6c 65 20 50 nc., 59 Temple P
05c0: 6c 61 63 65 20 2d 20 53 75 69 74 65 20 33 33 30 lace - Suite 330
05d0: 2c 20 42 6f 73 74 6f 6e 2c 0a 4d 41 20 30 32 31 , Boston,.MA 021
05e0: 31 31 2d 31 33 30 37 2c 20 55 53 41 2e 20 2a 2f 11-1307, USA. */
05f0: 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 73 74 64 6c ..#include <stdl
0600: 69 62 2e 68 3e 0a 23 69 6e 63 6c 75 64 65 20 22 ib.h>.#include "
0610: 67 6d 70 2e 68 22 0a 23 69 6e 63 6c 75 64 65 20 gmp.h".#include
0620: 22 67 6d 70 2d 69 6d 70 6c 2e 68 22 0a 23 69 6e "gmp-impl.h".#in
0630: 63 6c 75 64 65 20 22 6c 6f 6e 67 6c 6f 6e 67 2e clude "longlong.
0640: 68 22 0a 0a 0a 76 6f 69 64 0a 6d 70 6e 5f 74 64 h"...void.mpn_td
0650: 69 76 5f 71 72 20 28 6d 70 5f 70 74 72 20 71 70 iv_qr (mp_ptr qp
0660: 2c 20 6d 70 5f 70 74 72 20 72 70 2c 20 6d 70 5f , mp_ptr rp, mp_
0670: 73 69 7a 65 5f 74 20 71 78 6e 2c 0a 09 20 20 20 size_t qxn,..
0680: 20 20 6d 70 5f 73 72 63 70 74 72 20 6e 70 2c 20 mp_srcptr np,
0690: 6d 70 5f 73 69 7a 65 5f 74 20 6e 6e 2c 20 6d 70 mp_size_t nn, mp
06a0: 5f 73 72 63 70 74 72 20 64 70 2c 20 6d 70 5f 73 _srcptr dp, mp_s
06b0: 69 7a 65 5f 74 20 64 6e 29 0a 7b 0a 20 20 2f 2a ize_t dn).{. /*
06c0: 20 46 49 58 4d 45 3a 0a 20 20 20 20 20 31 2e 20 FIXME:. 1.
06d0: 71 78 6e 0a 20 20 20 20 20 32 2e 20 70 61 73 73 qxn. 2. pass
06e0: 20 61 6c 6c 6f 63 61 74 65 64 20 73 74 6f 72 61 allocated stora
06f0: 67 65 20 69 6e 20 61 64 64 69 74 69 6f 6e 61 6c ge in additional
0700: 20 70 61 72 61 6d 65 74 65 72 3f 0a 20 20 2a 2f parameter?. */
0710: 0a 20 20 69 66 20 28 71 78 6e 20 21 3d 20 30 29 . if (qxn != 0)
0720: 0a 20 20 20 20 61 62 6f 72 74 20 28 29 3b 0a 0a . abort ();..
0730: 20 20 41 53 53 45 52 54 20 28 71 78 6e 20 3e 3d ASSERT (qxn >=
0740: 20 30 29 3b 0a 20 20 41 53 53 45 52 54 20 28 6e 0);. ASSERT (n
0750: 6e 20 3e 3d 20 30 29 3b 0a 20 20 41 53 53 45 52 n >= 0);. ASSER
0760: 54 20 28 64 6e 20 3e 3d 20 30 29 3b 0a 20 20 41 T (dn >= 0);. A
0770: 53 53 45 52 54 20 28 64 6e 20 3d 3d 20 30 20 7c SSERT (dn == 0 |
0780: 7c 20 64 70 5b 64 6e 20 2d 20 31 5d 20 21 3d 20 | dp[dn - 1] !=
0790: 30 29 3b 0a 20 20 41 53 53 45 52 54 20 28 21 20 0);. ASSERT (!
07a0: 4d 50 4e 5f 4f 56 45 52 4c 41 50 5f 50 20 28 71 MPN_OVERLAP_P (q
07b0: 70 2c 20 6e 6e 20 2d 20 64 6e 20 2b 20 31 20 2b p, nn - dn + 1 +
07c0: 20 71 78 6e 2c 20 6e 70 2c 20 6e 6e 29 29 3b 0a qxn, np, nn));.
07d0: 20 20 41 53 53 45 52 54 20 28 21 20 4d 50 4e 5f ASSERT (! MPN_
07e0: 4f 56 45 52 4c 41 50 5f 50 20 28 71 70 2c 20 6e OVERLAP_P (qp, n
07f0: 6e 20 2d 20 64 6e 20 2b 20 31 20 2b 20 71 78 6e n - dn + 1 + qxn
0800: 2c 20 64 70 2c 20 64 6e 29 29 3b 0a 0a 20 20 73 , dp, dn));.. s
0810: 77 69 74 63 68 20 28 64 6e 29 0a 20 20 20 20 7b witch (dn). {
0820: 0a 20 20 20 20 63 61 73 65 20 30 3a 0a 20 20 20 . case 0:.
0830: 20 20 20 44 49 56 49 44 45 5f 42 59 5f 5a 45 52 DIVIDE_BY_ZER
0840: 4f 3b 0a 0a 20 20 20 20 63 61 73 65 20 31 3a 0a O;.. case 1:.
0850: 20 20 20 20 20 20 7b 0a 09 72 70 5b 30 5d 20 3d {..rp[0] =
0860: 20 6d 70 6e 5f 64 69 76 6d 6f 64 5f 31 20 28 71 mpn_divmod_1 (q
0870: 70 2c 20 6e 70 2c 20 6e 6e 2c 20 64 70 5b 30 5d p, np, nn, dp[0]
0880: 29 3b 0a 09 72 65 74 75 72 6e 3b 0a 20 20 20 20 );..return;.
0890: 20 20 7d 0a 0a 20 20 20 20 63 61 73 65 20 32 3a }.. case 2:
08a0: 0a 20 20 20 20 20 20 7b 0a 09 6d 70 5f 70 74 72 . {..mp_ptr
08b0: 20 6e 32 70 2c 20 64 32 70 3b 0a 09 6d 70 5f 6c n2p, d2p;..mp_l
08c0: 69 6d 62 5f 74 20 71 68 6c 2c 20 63 79 3b 0a 09 imb_t qhl, cy;..
08d0: 54 4d 50 5f 44 45 43 4c 20 28 6d 61 72 6b 65 72 TMP_DECL (marker
08e0: 29 3b 0a 09 54 4d 50 5f 4d 41 52 4b 20 28 6d 61 );..TMP_MARK (ma
08f0: 72 6b 65 72 29 3b 0a 09 69 66 20 28 28 64 70 5b rker);..if ((dp[
0900: 31 5d 20 26 20 47 4d 50 5f 4e 55 4d 42 5f 48 49 1] & GMP_NUMB_HI
0910: 47 48 42 49 54 29 20 3d 3d 20 30 29 0a 09 20 20 GHBIT) == 0)..
0920: 7b 0a 09 20 20 20 20 69 6e 74 20 63 6e 74 3b 0a {.. int cnt;.
0930: 09 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 64 . mp_limb_t d
0940: 74 6d 70 5b 32 5d 3b 0a 09 20 20 20 20 63 6f 75 tmp[2];.. cou
0950: 6e 74 5f 6c 65 61 64 69 6e 67 5f 7a 65 72 6f 73 nt_leading_zeros
0960: 20 28 63 6e 74 2c 20 64 70 5b 31 5d 29 3b 0a 09 (cnt, dp[1]);..
0970: 20 20 20 20 63 6e 74 20 2d 3d 20 47 4d 50 5f 4e cnt -= GMP_N
0980: 41 49 4c 5f 42 49 54 53 3b 0a 09 20 20 20 20 64 AIL_BITS;.. d
0990: 32 70 20 3d 20 64 74 6d 70 3b 0a 09 20 20 20 20 2p = dtmp;..
09a0: 64 32 70 5b 31 5d 20 3d 20 28 64 70 5b 31 5d 20 d2p[1] = (dp[1]
09b0: 3c 3c 20 63 6e 74 29 20 7c 20 28 64 70 5b 30 5d << cnt) | (dp[0]
09c0: 20 3e 3e 20 28 47 4d 50 5f 4e 55 4d 42 5f 42 49 >> (GMP_NUMB_BI
09d0: 54 53 20 2d 20 63 6e 74 29 29 3b 0a 09 20 20 20 TS - cnt));..
09e0: 20 64 32 70 5b 30 5d 20 3d 20 28 64 70 5b 30 5d d2p[0] = (dp[0]
09f0: 20 3c 3c 20 63 6e 74 29 20 26 20 47 4d 50 5f 4e << cnt) & GMP_N
0a00: 55 4d 42 5f 4d 41 53 4b 3b 0a 09 20 20 20 20 6e UMB_MASK;.. n
0a10: 32 70 20 3d 20 28 6d 70 5f 70 74 72 29 20 54 4d 2p = (mp_ptr) TM
0a20: 50 5f 41 4c 4c 4f 43 20 28 28 6e 6e 20 2b 20 31 P_ALLOC ((nn + 1
0a30: 29 20 2a 20 42 59 54 45 53 5f 50 45 52 5f 4d 50 ) * BYTES_PER_MP
0a40: 5f 4c 49 4d 42 29 3b 0a 09 20 20 20 20 63 79 20 _LIMB);.. cy
0a50: 3d 20 6d 70 6e 5f 6c 73 68 69 66 74 20 28 6e 32 = mpn_lshift (n2
0a60: 70 2c 20 6e 70 2c 20 6e 6e 2c 20 63 6e 74 29 3b p, np, nn, cnt);
0a70: 0a 09 20 20 20 20 6e 32 70 5b 6e 6e 5d 20 3d 20 .. n2p[nn] =
0a80: 63 79 3b 0a 09 20 20 20 20 71 68 6c 20 3d 20 6d cy;.. qhl = m
0a90: 70 6e 5f 64 69 76 72 65 6d 5f 32 20 28 71 70 2c pn_divrem_2 (qp,
0aa0: 20 30 4c 2c 20 6e 32 70 2c 20 6e 6e 20 2b 20 28 0L, n2p, nn + (
0ab0: 63 79 20 21 3d 20 30 29 2c 20 64 32 70 29 3b 0a cy != 0), d2p);.
0ac0: 09 20 20 20 20 69 66 20 28 63 79 20 3d 3d 20 30 . if (cy == 0
0ad0: 29 0a 09 20 20 20 20 20 20 71 70 5b 6e 6e 20 2d ).. qp[nn -
0ae0: 20 32 5d 20 3d 20 71 68 6c 3b 09 2f 2a 20 61 6c 2] = qhl;./* al
0af0: 77 61 79 73 20 73 74 6f 72 65 20 6e 6e 2d 32 2b ways store nn-2+
0b00: 31 20 71 75 6f 74 69 65 6e 74 20 6c 69 6d 62 73 1 quotient limbs
0b10: 20 2a 2f 0a 09 20 20 20 20 6d 70 6e 5f 72 73 68 */.. mpn_rsh
0b20: 69 66 74 20 28 72 70 2c 20 6e 32 70 2c 20 28 6d ift (rp, n2p, (m
0b30: 70 5f 73 69 7a 65 5f 74 29 20 32 2c 20 63 6e 74 p_size_t) 2, cnt
0b40: 29 3b 0a 09 20 20 7d 0a 09 65 6c 73 65 0a 09 20 );.. }..else..
0b50: 20 7b 0a 09 20 20 20 20 64 32 70 20 3d 20 28 6d {.. d2p = (m
0b60: 70 5f 70 74 72 29 20 64 70 3b 0a 09 20 20 20 20 p_ptr) dp;..
0b70: 6e 32 70 20 3d 20 28 6d 70 5f 70 74 72 29 20 54 n2p = (mp_ptr) T
0b80: 4d 50 5f 41 4c 4c 4f 43 20 28 6e 6e 20 2a 20 42 MP_ALLOC (nn * B
0b90: 59 54 45 53 5f 50 45 52 5f 4d 50 5f 4c 49 4d 42 YTES_PER_MP_LIMB
0ba0: 29 3b 0a 09 20 20 20 20 4d 50 4e 5f 43 4f 50 59 );.. MPN_COPY
0bb0: 20 28 6e 32 70 2c 20 6e 70 2c 20 6e 6e 29 3b 0a (n2p, np, nn);.
0bc0: 09 20 20 20 20 71 68 6c 20 3d 20 6d 70 6e 5f 64 . qhl = mpn_d
0bd0: 69 76 72 65 6d 5f 32 20 28 71 70 2c 20 30 4c 2c ivrem_2 (qp, 0L,
0be0: 20 6e 32 70 2c 20 6e 6e 2c 20 64 32 70 29 3b 0a n2p, nn, d2p);.
0bf0: 09 20 20 20 20 71 70 5b 6e 6e 20 2d 20 32 5d 20 . qp[nn - 2]
0c00: 3d 20 71 68 6c 3b 09 2f 2a 20 61 6c 77 61 79 73 = qhl;./* always
0c10: 20 73 74 6f 72 65 20 6e 6e 2d 32 2b 31 20 71 75 store nn-2+1 qu
0c20: 6f 74 69 65 6e 74 20 6c 69 6d 62 73 20 2a 2f 0a otient limbs */.
0c30: 09 20 20 20 20 4d 50 4e 5f 43 4f 50 59 20 28 72 . MPN_COPY (r
0c40: 70 2c 20 6e 32 70 2c 20 32 29 3b 0a 09 20 20 7d p, n2p, 2);.. }
0c50: 0a 09 54 4d 50 5f 46 52 45 45 20 28 6d 61 72 6b ..TMP_FREE (mark
0c60: 65 72 29 3b 0a 09 72 65 74 75 72 6e 3b 0a 20 20 er);..return;.
0c70: 20 20 20 20 7d 0a 0a 20 20 20 20 64 65 66 61 75 }.. defau
0c80: 6c 74 3a 0a 20 20 20 20 20 20 7b 0a 09 69 6e 74 lt:. {..int
0c90: 20 61 64 6a 75 73 74 3b 0a 09 54 4d 50 5f 44 45 adjust;..TMP_DE
0ca0: 43 4c 20 28 6d 61 72 6b 65 72 29 3b 0a 09 54 4d CL (marker);..TM
0cb0: 50 5f 4d 41 52 4b 20 28 6d 61 72 6b 65 72 29 3b P_MARK (marker);
0cc0: 0a 09 61 64 6a 75 73 74 20 3d 20 6e 70 5b 6e 6e ..adjust = np[nn
0cd0: 20 2d 20 31 5d 20 3e 3d 20 64 70 5b 64 6e 20 2d - 1] >= dp[dn -
0ce0: 20 31 5d 3b 09 2f 2a 20 63 6f 6e 73 65 72 76 61 1];./* conserva
0cf0: 74 69 76 65 20 74 65 73 74 73 20 66 6f 72 20 71 tive tests for q
0d00: 75 6f 74 69 65 6e 74 20 73 69 7a 65 20 2a 2f 0a uotient size */.
0d10: 09 69 66 20 28 6e 6e 20 2b 20 61 64 6a 75 73 74 .if (nn + adjust
0d20: 20 3e 3d 20 32 20 2a 20 64 6e 29 0a 09 20 20 7b >= 2 * dn).. {
0d30: 0a 09 20 20 20 20 6d 70 5f 70 74 72 20 6e 32 70 .. mp_ptr n2p
0d40: 2c 20 64 32 70 3b 0a 09 20 20 20 20 6d 70 5f 6c , d2p;.. mp_l
0d50: 69 6d 62 5f 74 20 63 79 3b 0a 09 20 20 20 20 69 imb_t cy;.. i
0d60: 6e 74 20 63 6e 74 3b 0a 0a 09 20 20 20 20 71 70 nt cnt;... qp
0d70: 5b 6e 6e 20 2d 20 64 6e 5d 20 3d 20 30 3b 09 09 [nn - dn] = 0;..
0d80: 09 20 20 2f 2a 20 7a 65 72 6f 20 68 69 67 68 20 . /* zero high
0d90: 71 75 6f 74 69 65 6e 74 20 6c 69 6d 62 20 2a 2f quotient limb */
0da0: 0a 09 20 20 20 20 69 66 20 28 28 64 70 5b 64 6e .. if ((dp[dn
0db0: 20 2d 20 31 5d 20 26 20 47 4d 50 5f 4e 55 4d 42 - 1] & GMP_NUMB
0dc0: 5f 48 49 47 48 42 49 54 29 20 3d 3d 20 30 29 20 _HIGHBIT) == 0)
0dd0: 2f 2a 20 6e 6f 72 6d 61 6c 69 7a 65 20 64 69 76 /* normalize div
0de0: 69 73 6f 72 20 2a 2f 0a 09 20 20 20 20 20 20 7b isor */.. {
0df0: 0a 09 09 63 6f 75 6e 74 5f 6c 65 61 64 69 6e 67 ...count_leading
0e00: 5f 7a 65 72 6f 73 20 28 63 6e 74 2c 20 64 70 5b _zeros (cnt, dp[
0e10: 64 6e 20 2d 20 31 5d 29 3b 0a 09 09 63 6e 74 20 dn - 1]);...cnt
0e20: 2d 3d 20 47 4d 50 5f 4e 41 49 4c 5f 42 49 54 53 -= GMP_NAIL_BITS
0e30: 3b 0a 09 09 64 32 70 20 3d 20 28 6d 70 5f 70 74 ;...d2p = (mp_pt
0e40: 72 29 20 54 4d 50 5f 41 4c 4c 4f 43 20 28 64 6e r) TMP_ALLOC (dn
0e50: 20 2a 20 42 59 54 45 53 5f 50 45 52 5f 4d 50 5f * BYTES_PER_MP_
0e60: 4c 49 4d 42 29 3b 0a 09 09 6d 70 6e 5f 6c 73 68 LIMB);...mpn_lsh
0e70: 69 66 74 20 28 64 32 70 2c 20 64 70 2c 20 64 6e ift (d2p, dp, dn
0e80: 2c 20 63 6e 74 29 3b 0a 09 09 6e 32 70 20 3d 20 , cnt);...n2p =
0e90: 28 6d 70 5f 70 74 72 29 20 54 4d 50 5f 41 4c 4c (mp_ptr) TMP_ALL
0ea0: 4f 43 20 28 28 6e 6e 20 2b 20 31 29 20 2a 20 42 OC ((nn + 1) * B
0eb0: 59 54 45 53 5f 50 45 52 5f 4d 50 5f 4c 49 4d 42 YTES_PER_MP_LIMB
0ec0: 29 3b 0a 09 09 63 79 20 3d 20 6d 70 6e 5f 6c 73 );...cy = mpn_ls
0ed0: 68 69 66 74 20 28 6e 32 70 2c 20 6e 70 2c 20 6e hift (n2p, np, n
0ee0: 6e 2c 20 63 6e 74 29 3b 0a 09 09 6e 32 70 5b 6e n, cnt);...n2p[n
0ef0: 6e 5d 20 3d 20 63 79 3b 0a 09 09 6e 6e 20 2b 3d n] = cy;...nn +=
0f00: 20 61 64 6a 75 73 74 3b 0a 09 20 20 20 20 20 20 adjust;..
0f10: 7d 0a 09 20 20 20 20 65 6c 73 65 0a 09 20 20 20 }.. else..
0f20: 20 20 20 7b 0a 09 09 63 6e 74 20 3d 20 30 3b 0a {...cnt = 0;.
0f30: 09 09 64 32 70 20 3d 20 28 6d 70 5f 70 74 72 29 ..d2p = (mp_ptr)
0f40: 20 64 70 3b 0a 09 09 6e 32 70 20 3d 20 28 6d 70 dp;...n2p = (mp
0f50: 5f 70 74 72 29 20 54 4d 50 5f 41 4c 4c 4f 43 20 _ptr) TMP_ALLOC
0f60: 28 28 6e 6e 20 2b 20 31 29 20 2a 20 42 59 54 45 ((nn + 1) * BYTE
0f70: 53 5f 50 45 52 5f 4d 50 5f 4c 49 4d 42 29 3b 0a S_PER_MP_LIMB);.
0f80: 09 09 4d 50 4e 5f 43 4f 50 59 20 28 6e 32 70 2c ..MPN_COPY (n2p,
0f90: 20 6e 70 2c 20 6e 6e 29 3b 0a 09 09 6e 32 70 5b np, nn);...n2p[
0fa0: 6e 6e 5d 20 3d 20 30 3b 0a 09 09 6e 6e 20 2b 3d nn] = 0;...nn +=
0fb0: 20 61 64 6a 75 73 74 3b 0a 09 20 20 20 20 20 20 adjust;..
0fc0: 7d 0a 0a 09 20 20 20 20 69 66 20 28 64 6e 20 3d }... if (dn =
0fd0: 3d 20 32 29 0a 09 20 20 20 20 20 20 6d 70 6e 5f = 2).. mpn_
0fe0: 64 69 76 72 65 6d 5f 32 20 28 71 70 2c 20 30 4c divrem_2 (qp, 0L
0ff0: 2c 20 6e 32 70 2c 20 6e 6e 2c 20 64 32 70 29 3b , n2p, nn, d2p);
1000: 0a 09 20 20 20 20 65 6c 73 65 20 69 66 20 28 64 .. else if (d
1010: 6e 20 3c 20 44 49 56 5f 44 43 5f 54 48 52 45 53 n < DIV_DC_THRES
1020: 48 4f 4c 44 29 0a 09 20 20 20 20 20 20 6d 70 6e HOLD).. mpn
1030: 5f 73 62 5f 64 69 76 72 65 6d 5f 6d 6e 20 28 71 _sb_divrem_mn (q
1040: 70 2c 20 6e 32 70 2c 20 6e 6e 2c 20 64 32 70 2c p, n2p, nn, d2p,
1050: 20 64 6e 29 3b 0a 09 20 20 20 20 65 6c 73 65 0a dn);.. else.
1060: 09 20 20 20 20 20 20 7b 0a 09 09 2f 2a 20 50 65 . {.../* Pe
1070: 72 66 6f 72 6d 20 32 2a 64 6e 20 2f 20 64 6e 20 rform 2*dn / dn
1080: 6c 69 6d 62 20 64 69 76 69 73 69 6f 6e 73 20 61 limb divisions a
1090: 73 20 6c 6f 6e 67 20 61 73 20 74 68 65 20 6c 69 s long as the li
10a0: 6d 62 73 0a 09 09 20 20 20 69 6e 20 6e 70 20 6c mbs... in np l
10b0: 61 73 74 2e 20 20 2a 2f 0a 09 09 6d 70 5f 70 74 ast. */...mp_pt
10c0: 72 20 71 32 70 20 3d 20 71 70 20 2b 20 6e 6e 20 r q2p = qp + nn
10d0: 2d 20 32 20 2a 20 64 6e 3b 0a 09 09 6e 32 70 20 - 2 * dn;...n2p
10e0: 2b 3d 20 6e 6e 20 2d 20 32 20 2a 20 64 6e 3b 0a += nn - 2 * dn;.
10f0: 09 09 6d 70 6e 5f 64 63 5f 64 69 76 72 65 6d 5f ..mpn_dc_divrem_
1100: 6e 20 28 71 32 70 2c 20 6e 32 70 2c 20 64 32 70 n (q2p, n2p, d2p
1110: 2c 20 64 6e 29 3b 0a 09 09 6e 6e 20 2d 3d 20 64 , dn);...nn -= d
1120: 6e 3b 0a 09 09 77 68 69 6c 65 20 28 6e 6e 20 3e n;...while (nn >
1130: 3d 20 32 20 2a 20 64 6e 29 0a 09 09 20 20 7b 0a = 2 * dn)... {.
1140: 09 09 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 .. mp_limb_t
1150: 63 3b 0a 09 09 20 20 20 20 71 32 70 20 2d 3d 20 c;... q2p -=
1160: 64 6e 3b 20 20 6e 32 70 20 2d 3d 20 64 6e 3b 0a dn; n2p -= dn;.
1170: 09 09 20 20 20 20 63 20 3d 20 6d 70 6e 5f 64 63 .. c = mpn_dc
1180: 5f 64 69 76 72 65 6d 5f 6e 20 28 71 32 70 2c 20 _divrem_n (q2p,
1190: 6e 32 70 2c 20 64 32 70 2c 20 64 6e 29 3b 0a 09 n2p, d2p, dn);..
11a0: 09 20 20 20 20 41 53 53 45 52 54 5f 41 4c 57 41 . ASSERT_ALWA
11b0: 59 53 20 28 63 20 3d 3d 20 30 29 3b 0a 09 09 20 YS (c == 0);...
11c0: 20 20 20 6e 6e 20 2d 3d 20 64 6e 3b 0a 09 09 20 nn -= dn;...
11d0: 20 7d 0a 0a 09 09 69 66 20 28 6e 6e 20 21 3d 20 }....if (nn !=
11e0: 64 6e 29 0a 09 09 20 20 7b 0a 09 09 20 20 20 20 dn)... {...
11f0: 6e 32 70 20 2d 3d 20 6e 6e 20 2d 20 64 6e 3b 0a n2p -= nn - dn;.
1200: 09 09 20 20 20 20 2f 2a 20 49 6e 20 74 68 65 6f .. /* In theo
1210: 72 79 2c 20 77 65 20 63 6f 75 6c 64 20 66 61 6c ry, we could fal
1220: 6c 20 6f 75 74 20 74 6f 20 74 68 65 20 63 75 74 l out to the cut
1230: 65 20 63 6f 64 65 20 62 65 6c 6f 77 0a 09 09 20 e code below...
1240: 20 20 20 20 20 20 73 69 6e 63 65 20 77 65 20 6e since we n
1250: 6f 77 20 68 61 76 65 20 65 78 61 63 74 6c 79 20 ow have exactly
1260: 74 68 65 20 73 69 74 75 61 74 69 6f 6e 20 74 68 the situation th
1270: 61 74 20 63 6f 64 65 0a 09 09 20 20 20 20 20 20 at code...
1280: 20 69 73 20 64 65 73 69 67 6e 65 64 20 74 6f 20 is designed to
1290: 68 61 6e 64 6c 65 2e 20 20 57 65 20 62 6f 74 63 handle. We botc
12a0: 68 20 74 68 69 73 20 62 61 64 6c 79 20 61 6e 64 h this badly and
12b0: 20 63 61 6c 6c 0a 09 09 20 20 20 20 20 20 20 74 call... t
12c0: 68 65 20 62 61 73 69 63 20 6d 70 6e 5f 73 62 5f he basic mpn_sb_
12d0: 64 69 76 72 65 6d 5f 6d 6e 21 20 20 2a 2f 0a 09 divrem_mn! */..
12e0: 09 20 20 20 20 69 66 20 28 64 6e 20 3d 3d 20 32 . if (dn == 2
12f0: 29 0a 09 09 20 20 20 20 20 20 6d 70 6e 5f 64 69 )... mpn_di
1300: 76 72 65 6d 5f 32 20 28 71 70 2c 20 30 4c 2c 20 vrem_2 (qp, 0L,
1310: 6e 32 70 2c 20 6e 6e 2c 20 64 32 70 29 3b 0a 09 n2p, nn, d2p);..
1320: 09 20 20 20 20 65 6c 73 65 0a 09 09 20 20 20 20 . else...
1330: 20 20 6d 70 6e 5f 73 62 5f 64 69 76 72 65 6d 5f mpn_sb_divrem_
1340: 6d 6e 20 28 71 70 2c 20 6e 32 70 2c 20 6e 6e 2c mn (qp, n2p, nn,
1350: 20 64 32 70 2c 20 64 6e 29 3b 0a 09 09 20 20 7d d2p, dn);... }
1360: 0a 09 20 20 20 20 20 20 7d 0a 0a 0a 09 20 20 20 .. }....
1370: 20 69 66 20 28 63 6e 74 20 21 3d 20 30 29 0a 09 if (cnt != 0)..
1380: 20 20 20 20 20 20 6d 70 6e 5f 72 73 68 69 66 74 mpn_rshift
1390: 20 28 72 70 2c 20 6e 32 70 2c 20 64 6e 2c 20 63 (rp, n2p, dn, c
13a0: 6e 74 29 3b 0a 09 20 20 20 20 65 6c 73 65 0a 09 nt);.. else..
13b0: 20 20 20 20 20 20 4d 50 4e 5f 43 4f 50 59 20 28 MPN_COPY (
13c0: 72 70 2c 20 6e 32 70 2c 20 64 6e 29 3b 0a 09 20 rp, n2p, dn);..
13d0: 20 20 20 54 4d 50 5f 46 52 45 45 20 28 6d 61 72 TMP_FREE (mar
13e0: 6b 65 72 29 3b 0a 09 20 20 20 20 72 65 74 75 72 ker);.. retur
13f0: 6e 3b 0a 09 20 20 7d 0a 0a 09 2f 2a 20 57 68 65 n;.. }.../* Whe
1400: 6e 20 77 65 20 63 6f 6d 65 20 68 65 72 65 2c 20 n we come here,
1410: 74 68 65 20 6e 75 6d 65 72 61 74 6f 72 2f 70 61 the numerator/pa
1420: 72 74 69 61 6c 20 72 65 6d 61 69 6e 64 65 72 20 rtial remainder
1430: 69 73 20 6c 65 73 73 0a 09 20 20 20 74 68 61 6e is less.. than
1440: 20 74 77 69 63 65 20 74 68 65 20 73 69 7a 65 20 twice the size
1450: 6f 66 20 74 68 65 20 64 65 6e 6f 6d 69 6e 61 74 of the denominat
1460: 6f 72 2e 20 20 2a 2f 0a 0a 09 20 20 7b 0a 09 20 or. */... {..
1470: 20 20 20 2f 2a 20 50 72 6f 62 6c 65 6d 3a 0a 0a /* Problem:..
1480: 09 20 20 20 20 20 20 20 44 69 76 69 64 65 20 61 . Divide a
1490: 20 6e 75 6d 65 72 61 74 6f 72 20 4e 20 77 69 74 numerator N wit
14a0: 68 20 6e 6e 20 6c 69 6d 62 73 20 62 79 20 61 20 h nn limbs by a
14b0: 64 65 6e 6f 6d 69 6e 61 74 6f 72 20 44 20 77 69 denominator D wi
14c0: 74 68 20 64 6e 0a 09 20 20 20 20 20 20 20 6c 69 th dn.. li
14d0: 6d 62 73 20 66 6f 72 6d 69 6e 67 20 61 20 71 75 mbs forming a qu
14e0: 6f 74 69 65 6e 74 20 6f 66 20 6e 6e 2d 64 6e 2b otient of nn-dn+
14f0: 31 20 6c 69 6d 62 73 2e 20 20 57 68 65 6e 20 71 1 limbs. When q
1500: 6e 20 69 73 20 73 6d 61 6c 6c 0a 09 20 20 20 20 n is small..
1510: 20 20 20 63 6f 6d 70 61 72 65 64 20 74 6f 20 64 compared to d
1520: 6e 2c 20 63 6f 6e 76 65 6e 74 69 6f 6e 61 6c 20 n, conventional
1530: 64 69 76 69 73 69 6f 6e 20 61 6c 67 6f 72 69 74 division algorit
1540: 68 6d 73 20 70 65 72 66 6f 72 6d 20 70 6f 6f 72 hms perform poor
1550: 6c 79 2e 0a 09 20 20 20 20 20 20 20 57 65 20 77 ly... We w
1560: 61 6e 74 20 61 6e 20 61 6c 67 6f 72 69 74 68 6d ant an algorithm
1570: 20 74 68 61 74 20 68 61 73 20 61 6e 20 65 78 70 that has an exp
1580: 65 63 74 65 64 20 72 75 6e 6e 69 6e 67 20 74 69 ected running ti
1590: 6d 65 20 74 68 61 74 20 69 73 0a 09 20 20 20 20 me that is..
15a0: 20 20 20 64 65 70 65 6e 64 65 6e 74 20 6f 6e 6c dependent onl
15b0: 79 20 6f 6e 20 71 6e 2e 20 20 49 74 20 69 73 20 y on qn. It is
15c0: 61 73 73 75 6d 65 64 20 74 68 61 74 20 74 68 65 assumed that the
15d0: 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61 6e most significan
15e0: 74 0a 09 20 20 20 20 20 20 20 6c 69 6d 62 20 6f t.. limb o
15f0: 66 20 74 68 65 20 6e 75 6d 65 72 61 74 6f 72 20 f the numerator
1600: 69 73 20 73 6d 61 6c 6c 65 72 20 74 68 61 6e 20 is smaller than
1610: 74 68 65 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 the most signifi
1620: 63 61 6e 74 20 6c 69 6d 62 0a 09 20 20 20 20 20 cant limb..
1630: 20 20 6f 66 20 74 68 65 20 64 65 6e 6f 6d 69 6e of the denomin
1640: 61 74 6f 72 2e 0a 0a 09 20 20 20 20 20 20 20 41 ator.... A
1650: 6c 67 6f 72 69 74 68 6d 20 28 76 65 72 79 20 69 lgorithm (very i
1660: 6e 66 6f 72 6d 61 6c 6c 79 20 73 74 61 74 65 64 nformally stated
1670: 29 3a 0a 0a 09 20 20 20 20 20 20 20 31 29 20 44 ):... 1) D
1680: 69 76 69 64 65 20 74 68 65 20 32 20 78 20 71 6e ivide the 2 x qn
1690: 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61 6e most significan
16a0: 74 20 6c 69 6d 62 73 20 66 72 6f 6d 20 74 68 65 t limbs from the
16b0: 20 6e 75 6d 65 72 61 74 6f 72 0a 09 09 20 20 62 numerator... b
16c0: 79 20 74 68 65 20 71 6e 20 6d 6f 73 74 20 73 69 y the qn most si
16d0: 67 6e 69 66 69 63 61 6e 74 20 6c 69 6d 62 73 20 gnificant limbs
16e0: 66 72 6f 6d 20 74 68 65 20 64 65 6e 6f 6d 69 6e from the denomin
16f0: 61 74 6f 72 2e 20 20 43 61 6c 6c 0a 09 09 20 20 ator. Call...
1700: 74 68 65 20 72 65 73 75 6c 74 20 71 65 73 74 2e the result qest.
1710: 20 20 54 68 69 73 20 69 73 20 65 69 74 68 65 72 This is either
1720: 20 74 68 65 20 63 6f 72 72 65 63 74 20 71 75 6f the correct quo
1730: 74 69 65 6e 74 2c 20 62 75 74 0a 09 09 20 20 6d tient, but... m
1740: 69 67 68 74 20 62 65 20 31 20 6f 72 20 32 20 74 ight be 1 or 2 t
1750: 6f 6f 20 6c 61 72 67 65 2e 20 20 43 6f 6d 70 75 oo large. Compu
1760: 74 65 20 74 68 65 20 72 65 6d 61 69 6e 64 65 72 te the remainder
1770: 20 66 72 6f 6d 20 74 68 65 0a 09 09 20 20 64 69 from the... di
1780: 76 69 73 69 6f 6e 2e 20 20 28 54 68 69 73 20 73 vision. (This s
1790: 74 65 70 20 69 73 20 69 6d 70 6c 65 6d 65 6e 74 tep is implement
17a0: 65 64 20 62 79 20 61 20 6d 70 6e 5f 64 69 76 72 ed by a mpn_divr
17b0: 65 6d 20 63 61 6c 6c 2e 29 0a 0a 09 20 20 20 20 em call.)...
17c0: 20 20 20 32 29 20 49 73 20 74 68 65 20 6d 6f 73 2) Is the mos
17d0: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 6c 69 t significant li
17e0: 6d 62 20 66 72 6f 6d 20 74 68 65 20 72 65 6d 61 mb from the rema
17f0: 69 6e 64 65 72 20 3c 20 70 2c 20 77 68 65 72 65 inder < p, where
1800: 20 70 0a 09 09 20 20 69 73 20 74 68 65 20 70 72 p... is the pr
1810: 6f 64 75 63 74 20 6f 66 20 74 68 65 20 6d 6f 73 oduct of the mos
1820: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 6c 69 t significant li
1830: 6d 62 20 66 72 6f 6d 20 74 68 65 20 71 75 6f 74 mb from the quot
1840: 69 65 6e 74 0a 09 09 20 20 61 6e 64 20 74 68 65 ient... and the
1850: 20 6e 65 78 74 28 64 29 2e 20 20 28 4e 65 78 74 next(d). (Next
1860: 28 64 29 20 64 65 6e 6f 74 65 73 20 74 68 65 20 (d) denotes the
1870: 6e 65 78 74 20 69 67 6e 6f 72 65 64 20 6c 69 6d next ignored lim
1880: 62 20 66 72 6f 6d 0a 09 09 20 20 74 68 65 20 64 b from... the d
1890: 65 6e 6f 6d 69 6e 61 74 6f 72 2e 29 20 20 49 66 enominator.) If
18a0: 20 69 74 20 69 73 2c 20 64 65 63 72 65 6d 65 6e it is, decremen
18b0: 74 20 71 65 73 74 2c 20 61 6e 64 20 61 64 6a 75 t qest, and adju
18c0: 73 74 20 74 68 65 0a 09 09 20 20 72 65 6d 61 69 st the... remai
18d0: 6e 64 65 72 20 61 63 63 6f 72 64 69 6e 67 6c 79 nder accordingly
18e0: 2e 0a 0a 09 20 20 20 20 20 20 20 33 29 20 49 73 .... 3) Is
18f0: 20 74 68 65 20 72 65 6d 61 69 6e 64 65 72 20 3e the remainder >
1900: 3d 20 71 65 73 74 3f 20 20 49 66 20 69 74 20 69 = qest? If it i
1910: 73 2c 20 71 65 73 74 20 69 73 20 74 68 65 20 64 s, qest is the d
1920: 65 73 69 72 65 64 0a 09 09 20 20 71 75 6f 74 69 esired... quoti
1930: 65 6e 74 2e 20 20 54 68 65 20 61 6c 67 6f 72 69 ent. The algori
1940: 74 68 6d 20 74 65 72 6d 69 6e 61 74 65 73 2e 0a thm terminates..
1950: 0a 09 20 20 20 20 20 20 20 34 29 20 53 75 62 74 .. 4) Subt
1960: 72 61 63 74 20 71 65 73 74 20 78 20 6e 65 78 74 ract qest x next
1970: 28 64 29 20 66 72 6f 6d 20 74 68 65 20 72 65 6d (d) from the rem
1980: 61 69 6e 64 65 72 2e 20 20 49 66 20 74 68 65 72 ainder. If ther
1990: 65 20 69 73 0a 09 09 20 20 62 6f 72 72 6f 77 20 e is... borrow
19a0: 6f 75 74 2c 20 64 65 63 72 65 6d 65 6e 74 20 71 out, decrement q
19b0: 65 73 74 2c 20 61 6e 64 20 61 64 6a 75 73 74 20 est, and adjust
19c0: 74 68 65 20 72 65 6d 61 69 6e 64 65 72 0a 09 09 the remainder...
19d0: 20 20 61 63 63 6f 72 64 69 6e 67 6c 79 2e 0a 0a accordingly...
19e0: 09 20 20 20 20 20 20 20 35 29 20 53 6b 69 70 20 . 5) Skip
19f0: 6f 6e 65 20 77 6f 72 64 20 66 72 6f 6d 20 74 68 one word from th
1a00: 65 20 64 65 6e 6f 6d 69 6e 61 74 6f 72 20 28 69 e denominator (i
1a10: 2e 65 2e 2c 20 6c 65 74 20 6e 65 78 74 28 64 29 .e., let next(d)
1a20: 20 64 65 6e 6f 74 65 0a 09 09 20 20 74 68 65 20 denote... the
1a30: 6e 65 78 74 20 6c 65 73 73 20 73 69 67 6e 69 66 next less signif
1a40: 69 63 61 6e 74 20 6c 69 6d 62 2e 20 20 2a 2f 0a icant limb. */.
1a50: 0a 09 20 20 20 20 6d 70 5f 73 69 7a 65 5f 74 20 .. mp_size_t
1a60: 71 6e 3b 0a 09 20 20 20 20 6d 70 5f 70 74 72 20 qn;.. mp_ptr
1a70: 6e 32 70 2c 20 64 32 70 3b 0a 09 20 20 20 20 6d n2p, d2p;.. m
1a80: 70 5f 70 74 72 20 74 70 3b 0a 09 20 20 20 20 6d p_ptr tp;.. m
1a90: 70 5f 6c 69 6d 62 5f 74 20 63 79 3b 0a 09 20 20 p_limb_t cy;..
1aa0: 20 20 6d 70 5f 73 69 7a 65 5f 74 20 69 6e 2c 20 mp_size_t in,
1ab0: 72 6e 3b 0a 09 20 20 20 20 6d 70 5f 6c 69 6d 62 rn;.. mp_limb
1ac0: 5f 74 20 71 75 6f 74 69 65 6e 74 5f 74 6f 6f 5f _t quotient_too_
1ad0: 6c 61 72 67 65 3b 0a 09 20 20 20 20 75 6e 73 69 large;.. unsi
1ae0: 67 6e 65 64 20 69 6e 74 20 63 6e 74 3b 0a 0a 09 gned int cnt;...
1af0: 20 20 20 20 71 6e 20 3d 20 6e 6e 20 2d 20 64 6e qn = nn - dn
1b00: 3b 0a 09 20 20 20 20 71 70 5b 71 6e 5d 20 3d 20 ;.. qp[qn] =
1b10: 30 3b 09 09 09 09 2f 2a 20 7a 65 72 6f 20 68 69 0;..../* zero hi
1b20: 67 68 20 71 75 6f 74 69 65 6e 74 20 6c 69 6d 62 gh quotient limb
1b30: 20 2a 2f 0a 09 20 20 20 20 71 6e 20 2b 3d 20 61 */.. qn += a
1b40: 64 6a 75 73 74 3b 09 09 09 2f 2a 20 71 6e 20 63 djust;.../* qn c
1b50: 61 6e 6e 6f 74 20 62 65 63 6f 6d 65 20 62 69 67 annot become big
1b60: 67 65 72 20 2a 2f 0a 0a 09 20 20 20 20 69 66 20 ger */... if
1b70: 28 71 6e 20 3d 3d 20 30 29 0a 09 20 20 20 20 20 (qn == 0)..
1b80: 20 7b 0a 09 09 4d 50 4e 5f 43 4f 50 59 20 28 72 {...MPN_COPY (r
1b90: 70 2c 20 6e 70 2c 20 64 6e 29 3b 0a 09 09 54 4d p, np, dn);...TM
1ba0: 50 5f 46 52 45 45 20 28 6d 61 72 6b 65 72 29 3b P_FREE (marker);
1bb0: 0a 09 09 72 65 74 75 72 6e 3b 0a 09 20 20 20 20 ...return;..
1bc0: 20 20 7d 0a 0a 09 20 20 20 20 69 6e 20 3d 20 64 }... in = d
1bd0: 6e 20 2d 20 71 6e 3b 09 09 2f 2a 20 28 61 74 20 n - qn;../* (at
1be0: 6c 65 61 73 74 20 70 61 72 74 69 61 6c 6c 79 29 least partially)
1bf0: 20 69 67 6e 6f 72 65 64 20 23 20 6f 66 20 6c 69 ignored # of li
1c00: 6d 62 73 20 69 6e 20 6f 70 73 20 2a 2f 0a 09 20 mbs in ops */..
1c10: 20 20 20 2f 2a 20 4e 6f 72 6d 61 6c 69 7a 65 20 /* Normalize
1c20: 64 65 6e 6f 6d 69 6e 61 74 6f 72 20 62 79 20 73 denominator by s
1c30: 68 69 66 74 69 6e 67 20 69 74 20 74 6f 20 74 68 hifting it to th
1c40: 65 20 6c 65 66 74 20 73 75 63 68 20 74 68 61 74 e left such that
1c50: 20 69 74 73 0a 09 20 20 20 20 20 20 20 6d 6f 73 its.. mos
1c60: 74 20 73 69 67 6e 69 66 69 63 61 6e 74 20 62 69 t significant bi
1c70: 74 20 69 73 20 73 65 74 2e 20 20 54 68 65 6e 20 t is set. Then
1c80: 73 68 69 66 74 20 74 68 65 20 6e 75 6d 65 72 61 shift the numera
1c90: 74 6f 72 20 74 68 65 20 73 61 6d 65 0a 09 20 20 tor the same..
1ca0: 20 20 20 20 20 61 6d 6f 75 6e 74 2c 20 74 6f 20 amount, to
1cb0: 6d 61 74 68 65 6d 61 74 69 63 61 6c 6c 79 20 70 mathematically p
1cc0: 72 65 73 65 72 76 65 20 71 75 6f 74 69 65 6e 74 reserve quotient
1cd0: 2e 20 20 2a 2f 0a 09 20 20 20 20 69 66 20 28 28 . */.. if ((
1ce0: 64 70 5b 64 6e 20 2d 20 31 5d 20 26 20 47 4d 50 dp[dn - 1] & GMP
1cf0: 5f 4e 55 4d 42 5f 48 49 47 48 42 49 54 29 20 3d _NUMB_HIGHBIT) =
1d00: 3d 20 30 29 0a 09 20 20 20 20 20 20 7b 0a 09 09 = 0).. {...
1d10: 63 6f 75 6e 74 5f 6c 65 61 64 69 6e 67 5f 7a 65 count_leading_ze
1d20: 72 6f 73 20 28 63 6e 74 2c 20 64 70 5b 64 6e 20 ros (cnt, dp[dn
1d30: 2d 20 31 5d 29 3b 0a 09 09 63 6e 74 20 2d 3d 20 - 1]);...cnt -=
1d40: 47 4d 50 5f 4e 41 49 4c 5f 42 49 54 53 3b 0a 0a GMP_NAIL_BITS;..
1d50: 09 09 64 32 70 20 3d 20 28 6d 70 5f 70 74 72 29 ..d2p = (mp_ptr)
1d60: 20 54 4d 50 5f 41 4c 4c 4f 43 20 28 71 6e 20 2a TMP_ALLOC (qn *
1d70: 20 42 59 54 45 53 5f 50 45 52 5f 4d 50 5f 4c 49 BYTES_PER_MP_LI
1d80: 4d 42 29 3b 0a 09 09 6d 70 6e 5f 6c 73 68 69 66 MB);...mpn_lshif
1d90: 74 20 28 64 32 70 2c 20 64 70 20 2b 20 69 6e 2c t (d2p, dp + in,
1da0: 20 71 6e 2c 20 63 6e 74 29 3b 0a 09 09 64 32 70 qn, cnt);...d2p
1db0: 5b 30 5d 20 7c 3d 20 64 70 5b 69 6e 20 2d 20 31 [0] |= dp[in - 1
1dc0: 5d 20 3e 3e 20 28 47 4d 50 5f 4e 55 4d 42 5f 42 ] >> (GMP_NUMB_B
1dd0: 49 54 53 20 2d 20 63 6e 74 29 3b 0a 0a 09 09 6e ITS - cnt);....n
1de0: 32 70 20 3d 20 28 6d 70 5f 70 74 72 29 20 54 4d 2p = (mp_ptr) TM
1df0: 50 5f 41 4c 4c 4f 43 20 28 28 32 20 2a 20 71 6e P_ALLOC ((2 * qn
1e00: 20 2b 20 31 29 20 2a 20 42 59 54 45 53 5f 50 45 + 1) * BYTES_PE
1e10: 52 5f 4d 50 5f 4c 49 4d 42 29 3b 0a 09 09 63 79 R_MP_LIMB);...cy
1e20: 20 3d 20 6d 70 6e 5f 6c 73 68 69 66 74 20 28 6e = mpn_lshift (n
1e30: 32 70 2c 20 6e 70 20 2b 20 6e 6e 20 2d 20 32 20 2p, np + nn - 2
1e40: 2a 20 71 6e 2c 20 32 20 2a 20 71 6e 2c 20 63 6e * qn, 2 * qn, cn
1e50: 74 29 3b 0a 09 09 69 66 20 28 61 64 6a 75 73 74 t);...if (adjust
1e60: 29 0a 09 09 20 20 7b 0a 09 09 20 20 20 20 6e 32 )... {... n2
1e70: 70 5b 32 20 2a 20 71 6e 5d 20 3d 20 63 79 3b 0a p[2 * qn] = cy;.
1e80: 09 09 20 20 20 20 6e 32 70 2b 2b 3b 0a 09 09 20 .. n2p++;...
1e90: 20 7d 0a 09 09 65 6c 73 65 0a 09 09 20 20 7b 0a }...else... {.
1ea0: 09 09 20 20 20 20 6e 32 70 5b 30 5d 20 7c 3d 20 .. n2p[0] |=
1eb0: 6e 70 5b 6e 6e 20 2d 20 32 20 2a 20 71 6e 20 2d np[nn - 2 * qn -
1ec0: 20 31 5d 20 3e 3e 20 28 47 4d 50 5f 4e 55 4d 42 1] >> (GMP_NUMB
1ed0: 5f 42 49 54 53 20 2d 20 63 6e 74 29 3b 0a 09 09 _BITS - cnt);...
1ee0: 20 20 7d 0a 09 20 20 20 20 20 20 7d 0a 09 20 20 }.. }..
1ef0: 20 20 65 6c 73 65 0a 09 20 20 20 20 20 20 7b 0a else.. {.
1f00: 09 09 63 6e 74 20 3d 20 30 3b 0a 09 09 64 32 70 ..cnt = 0;...d2p
1f10: 20 3d 20 28 6d 70 5f 70 74 72 29 20 64 70 20 2b = (mp_ptr) dp +
1f20: 20 69 6e 3b 0a 0a 09 09 6e 32 70 20 3d 20 28 6d in;....n2p = (m
1f30: 70 5f 70 74 72 29 20 54 4d 50 5f 41 4c 4c 4f 43 p_ptr) TMP_ALLOC
1f40: 20 28 28 32 20 2a 20 71 6e 20 2b 20 31 29 20 2a ((2 * qn + 1) *
1f50: 20 42 59 54 45 53 5f 50 45 52 5f 4d 50 5f 4c 49 BYTES_PER_MP_LI
1f60: 4d 42 29 3b 0a 09 09 4d 50 4e 5f 43 4f 50 59 20 MB);...MPN_COPY
1f70: 28 6e 32 70 2c 20 6e 70 20 2b 20 6e 6e 20 2d 20 (n2p, np + nn -
1f80: 32 20 2a 20 71 6e 2c 20 32 20 2a 20 71 6e 29 3b 2 * qn, 2 * qn);
1f90: 0a 09 09 69 66 20 28 61 64 6a 75 73 74 29 0a 09 ...if (adjust)..
1fa0: 09 20 20 7b 0a 09 09 20 20 20 20 6e 32 70 5b 32 . {... n2p[2
1fb0: 20 2a 20 71 6e 5d 20 3d 20 30 3b 0a 09 09 20 20 * qn] = 0;...
1fc0: 20 20 6e 32 70 2b 2b 3b 0a 09 09 20 20 7d 0a 09 n2p++;... }..
1fd0: 20 20 20 20 20 20 7d 0a 0a 09 20 20 20 20 2f 2a }... /*
1fe0: 20 47 65 74 20 61 6e 20 61 70 70 72 6f 78 69 6d Get an approxim
1ff0: 61 74 65 20 71 75 6f 74 69 65 6e 74 20 75 73 69 ate quotient usi
2000: 6e 67 20 74 68 65 20 65 78 74 72 61 63 74 65 64 ng the extracted
2010: 20 6f 70 65 72 61 6e 64 73 2e 20 20 2a 2f 0a 09 operands. */..
2020: 20 20 20 20 69 66 20 28 71 6e 20 3d 3d 20 31 29 if (qn == 1)
2030: 0a 09 20 20 20 20 20 20 7b 0a 09 09 6d 70 5f 6c .. {...mp_l
2040: 69 6d 62 5f 74 20 71 30 2c 20 72 30 3b 0a 09 09 imb_t q0, r0;...
2050: 6d 70 5f 6c 69 6d 62 5f 74 20 67 63 63 32 37 32 mp_limb_t gcc272
2060: 62 75 67 5f 6e 31 2c 20 67 63 63 32 37 32 62 75 bug_n1, gcc272bu
2070: 67 5f 6e 30 2c 20 67 63 63 32 37 32 62 75 67 5f g_n0, gcc272bug_
2080: 64 30 3b 0a 09 09 2f 2a 20 44 75 65 20 74 6f 20 d0;.../* Due to
2090: 61 20 67 63 63 20 32 2e 37 2e 32 2e 33 20 72 65 a gcc 2.7.2.3 re
20a0: 6c 6f 61 64 20 70 61 73 73 20 62 75 67 2c 20 77 load pass bug, w
20b0: 65 20 68 61 76 65 20 74 6f 20 75 73 65 20 73 6f e have to use so
20c0: 6d 65 0a 09 09 20 20 20 74 65 6d 70 73 20 68 65 me... temps he
20d0: 72 65 2e 20 20 54 68 69 73 20 64 6f 65 73 6e 27 re. This doesn'
20e0: 74 20 68 75 72 74 20 63 6f 64 65 20 71 75 61 6c t hurt code qual
20f0: 69 74 79 20 6f 6e 20 61 6e 79 20 6d 61 63 68 69 ity on any machi
2100: 6e 65 73 0a 09 09 20 20 20 73 6f 20 77 65 20 64 nes... so we d
2110: 6f 20 69 74 20 75 6e 63 6f 6e 64 69 74 69 6f 6e o it uncondition
2120: 61 6c 6c 79 2e 20 20 2a 2f 0a 09 09 67 63 63 32 ally. */...gcc2
2130: 37 32 62 75 67 5f 6e 31 20 3d 20 6e 32 70 5b 31 72bug_n1 = n2p[1
2140: 5d 3b 0a 09 09 67 63 63 32 37 32 62 75 67 5f 6e ];...gcc272bug_n
2150: 30 20 3d 20 6e 32 70 5b 30 5d 3b 0a 09 09 67 63 0 = n2p[0];...gc
2160: 63 32 37 32 62 75 67 5f 64 30 20 3d 20 64 32 70 c272bug_d0 = d2p
2170: 5b 30 5d 3b 0a 09 09 75 64 69 76 5f 71 72 6e 6e [0];...udiv_qrnn
2180: 64 20 28 71 30 2c 20 72 30 2c 20 67 63 63 32 37 d (q0, r0, gcc27
2190: 32 62 75 67 5f 6e 31 2c 20 67 63 63 32 37 32 62 2bug_n1, gcc272b
21a0: 75 67 5f 6e 30 20 3c 3c 20 47 4d 50 5f 4e 41 49 ug_n0 << GMP_NAI
21b0: 4c 5f 42 49 54 53 2c 0a 09 09 09 20 20 20 20 67 L_BITS,.... g
21c0: 63 63 32 37 32 62 75 67 5f 64 30 20 3c 3c 20 47 cc272bug_d0 << G
21d0: 4d 50 5f 4e 41 49 4c 5f 42 49 54 53 29 3b 0a 09 MP_NAIL_BITS);..
21e0: 09 72 30 20 3e 3e 3d 20 47 4d 50 5f 4e 41 49 4c .r0 >>= GMP_NAIL
21f0: 5f 42 49 54 53 3b 0a 09 09 6e 32 70 5b 30 5d 20 _BITS;...n2p[0]
2200: 3d 20 72 30 3b 0a 09 09 71 70 5b 30 5d 20 3d 20 = r0;...qp[0] =
2210: 71 30 3b 0a 09 20 20 20 20 20 20 7d 0a 09 20 20 q0;.. }..
2220: 20 20 65 6c 73 65 20 69 66 20 28 71 6e 20 3d 3d else if (qn ==
2230: 20 32 29 0a 09 20 20 20 20 20 20 6d 70 6e 5f 64 2).. mpn_d
2240: 69 76 72 65 6d 5f 32 20 28 71 70 2c 20 30 4c 2c ivrem_2 (qp, 0L,
2250: 20 6e 32 70 2c 20 34 4c 2c 20 64 32 70 29 3b 0a n2p, 4L, d2p);.
2260: 09 20 20 20 20 65 6c 73 65 20 69 66 20 28 71 6e . else if (qn
2270: 20 3c 20 44 49 56 5f 44 43 5f 54 48 52 45 53 48 < DIV_DC_THRESH
2280: 4f 4c 44 29 0a 09 20 20 20 20 20 20 6d 70 6e 5f OLD).. mpn_
2290: 73 62 5f 64 69 76 72 65 6d 5f 6d 6e 20 28 71 70 sb_divrem_mn (qp
22a0: 2c 20 6e 32 70 2c 20 32 20 2a 20 71 6e 2c 20 64 , n2p, 2 * qn, d
22b0: 32 70 2c 20 71 6e 29 3b 0a 09 20 20 20 20 65 6c 2p, qn);.. el
22c0: 73 65 0a 09 20 20 20 20 20 20 6d 70 6e 5f 64 63 se.. mpn_dc
22d0: 5f 64 69 76 72 65 6d 5f 6e 20 28 71 70 2c 20 6e _divrem_n (qp, n
22e0: 32 70 2c 20 64 32 70 2c 20 71 6e 29 3b 0a 0a 09 2p, d2p, qn);...
22f0: 20 20 20 20 72 6e 20 3d 20 71 6e 3b 0a 09 20 20 rn = qn;..
2300: 20 20 2f 2a 20 4d 75 6c 74 69 70 6c 79 20 74 68 /* Multiply th
2310: 65 20 66 69 72 73 74 20 69 67 6e 6f 72 65 64 20 e first ignored
2320: 64 69 76 69 73 6f 72 20 6c 69 6d 62 20 62 79 20 divisor limb by
2330: 74 68 65 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 the most signifi
2340: 63 61 6e 74 0a 09 20 20 20 20 20 20 20 71 75 6f cant.. quo
2350: 74 69 65 6e 74 20 6c 69 6d 62 2e 20 20 49 66 20 tient limb. If
2360: 74 68 61 74 20 70 72 6f 64 75 63 74 20 69 73 20 that product is
2370: 3e 20 74 68 65 20 70 61 72 74 69 61 6c 20 72 65 > the partial re
2380: 6d 61 69 6e 64 65 72 27 73 0a 09 20 20 20 20 20 mainder's..
2390: 20 20 6d 6f 73 74 20 73 69 67 6e 69 66 69 63 61 most significa
23a0: 6e 74 20 6c 69 6d 62 2c 20 77 65 20 6b 6e 6f 77 nt limb, we know
23b0: 20 74 68 65 20 71 75 6f 74 69 65 6e 74 20 69 73 the quotient is
23c0: 20 74 6f 6f 20 6c 61 72 67 65 2e 20 20 54 68 69 too large. Thi
23d0: 73 0a 09 20 20 20 20 20 20 20 74 65 73 74 20 71 s.. test q
23e0: 75 69 63 6b 6c 79 20 63 61 74 63 68 65 73 20 6d uickly catches m
23f0: 6f 73 74 20 63 61 73 65 73 20 77 68 65 72 65 20 ost cases where
2400: 74 68 65 20 71 75 6f 74 69 65 6e 74 20 69 73 20 the quotient is
2410: 74 6f 6f 20 6c 61 72 67 65 3b 0a 09 20 20 20 20 too large;..
2420: 20 20 20 69 74 20 63 61 74 63 68 65 73 20 61 6c it catches al
2430: 6c 20 63 61 73 65 73 20 77 68 65 72 65 20 74 68 l cases where th
2440: 65 20 71 75 6f 74 69 65 6e 74 20 69 73 20 32 20 e quotient is 2
2450: 74 6f 6f 20 6c 61 72 67 65 2e 20 20 2a 2f 0a 09 too large. */..
2460: 20 20 20 20 7b 0a 09 20 20 20 20 20 20 6d 70 5f {.. mp_
2470: 6c 69 6d 62 5f 74 20 64 6c 2c 20 78 3b 0a 09 20 limb_t dl, x;..
2480: 20 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 68 mp_limb_t h
2490: 2c 20 6c 3b 0a 0a 09 20 20 20 20 20 20 69 66 20 , l;... if
24a0: 28 69 6e 20 2d 20 32 20 3c 20 30 29 0a 09 09 64 (in - 2 < 0)...d
24b0: 6c 20 3d 20 30 3b 0a 09 20 20 20 20 20 20 65 6c l = 0;.. el
24c0: 73 65 0a 09 09 64 6c 20 3d 20 64 70 5b 69 6e 20 se...dl = dp[in
24d0: 2d 20 32 5d 3b 0a 0a 23 69 66 20 47 4d 50 5f 4e - 2];..#if GMP_N
24e0: 41 49 4c 5f 42 49 54 53 20 3d 3d 20 30 0a 09 20 AIL_BITS == 0..
24f0: 20 20 20 20 20 78 20 3d 20 28 64 70 5b 69 6e 20 x = (dp[in
2500: 2d 20 31 5d 20 3c 3c 20 63 6e 74 29 20 7c 20 28 - 1] << cnt) | (
2510: 28 64 6c 20 3e 3e 20 31 29 20 3e 3e 20 28 28 7e (dl >> 1) >> ((~
2520: 63 6e 74 29 20 25 20 42 49 54 53 5f 50 45 52 5f cnt) % BITS_PER_
2530: 4d 50 5f 4c 49 4d 42 29 29 3b 0a 23 65 6c 73 65 MP_LIMB));.#else
2540: 0a 09 20 20 20 20 20 20 78 20 3d 20 28 64 70 5b .. x = (dp[
2550: 69 6e 20 2d 20 31 5d 20 3c 3c 20 63 6e 74 29 20 in - 1] << cnt)
2560: 26 20 47 4d 50 5f 4e 55 4d 42 5f 4d 41 53 4b 3b & GMP_NUMB_MASK;
2570: 0a 09 20 20 20 20 20 20 69 66 20 28 63 6e 74 20 .. if (cnt
2580: 21 3d 20 30 29 0a 09 09 78 20 7c 3d 20 64 6c 20 != 0)...x |= dl
2590: 3e 3e 20 28 47 4d 50 5f 4e 55 4d 42 5f 42 49 54 >> (GMP_NUMB_BIT
25a0: 53 20 2d 20 63 6e 74 29 3b 0a 23 65 6e 64 69 66 S - cnt);.#endif
25b0: 0a 09 20 20 20 20 20 20 75 6d 75 6c 5f 70 70 6d .. umul_ppm
25c0: 6d 20 28 68 2c 20 6c 2c 20 78 2c 20 71 70 5b 71 m (h, l, x, qp[q
25d0: 6e 20 2d 20 31 5d 20 3c 3c 20 47 4d 50 5f 4e 41 n - 1] << GMP_NA
25e0: 49 4c 5f 42 49 54 53 29 3b 0a 09 20 20 20 20 20 IL_BITS);..
25f0: 20 6c 20 3e 3e 3d 20 47 4d 50 5f 4e 41 49 4c 5f l >>= GMP_NAIL_
2600: 42 49 54 53 3b 0a 0a 09 20 20 20 20 20 20 69 66 BITS;... if
2610: 20 28 6e 32 70 5b 71 6e 20 2d 20 31 5d 20 3c 20 (n2p[qn - 1] <
2620: 68 29 0a 09 09 7b 0a 09 09 20 20 6d 70 5f 6c 69 h)...{... mp_li
2630: 6d 62 5f 74 20 63 79 3b 0a 0a 09 09 20 20 6d 70 mb_t cy;.... mp
2640: 6e 5f 64 65 63 72 5f 75 20 28 71 70 2c 20 28 6d n_decr_u (qp, (m
2650: 70 5f 6c 69 6d 62 5f 74 29 20 31 29 3b 0a 09 09 p_limb_t) 1);...
2660: 20 20 63 79 20 3d 20 6d 70 6e 5f 61 64 64 5f 6e cy = mpn_add_n
2670: 20 28 6e 32 70 2c 20 6e 32 70 2c 20 64 32 70 2c (n2p, n2p, d2p,
2680: 20 71 6e 29 3b 0a 09 09 20 20 69 66 20 28 63 79 qn);... if (cy
2690: 29 0a 09 09 20 20 20 20 7b 0a 09 09 20 20 20 20 )... {...
26a0: 20 20 2f 2a 20 54 68 65 20 70 61 72 74 69 61 6c /* The partial
26b0: 20 72 65 6d 61 69 6e 64 65 72 20 69 73 20 73 61 remainder is sa
26c0: 66 65 6c 79 20 6c 61 72 67 65 2e 20 20 2a 2f 0a fely large. */.
26d0: 09 09 20 20 20 20 20 20 6e 32 70 5b 71 6e 5d 20 .. n2p[qn]
26e0: 3d 20 63 79 3b 0a 09 09 20 20 20 20 20 20 2b 2b = cy;... ++
26f0: 72 6e 3b 0a 09 09 20 20 20 20 7d 0a 09 09 7d 0a rn;... }...}.
2700: 09 20 20 20 20 7d 0a 0a 09 20 20 20 20 71 75 6f . }... quo
2710: 74 69 65 6e 74 5f 74 6f 6f 5f 6c 61 72 67 65 20 tient_too_large
2720: 3d 20 30 3b 0a 09 20 20 20 20 69 66 20 28 63 6e = 0;.. if (cn
2730: 74 20 21 3d 20 30 29 0a 09 20 20 20 20 20 20 7b t != 0).. {
2740: 0a 09 09 6d 70 5f 6c 69 6d 62 5f 74 20 63 79 31 ...mp_limb_t cy1
2750: 2c 20 63 79 32 3b 0a 0a 09 09 2f 2a 20 41 70 70 , cy2;..../* App
2760: 65 6e 64 20 70 61 72 74 69 61 6c 6c 79 20 75 73 end partially us
2770: 65 64 20 6e 75 6d 65 72 61 74 6f 72 20 6c 69 6d ed numerator lim
2780: 62 20 74 6f 20 70 61 72 74 69 61 6c 20 72 65 6d b to partial rem
2790: 61 69 6e 64 65 72 2e 20 20 2a 2f 0a 09 09 63 79 ainder. */...cy
27a0: 31 20 3d 20 6d 70 6e 5f 6c 73 68 69 66 74 20 28 1 = mpn_lshift (
27b0: 6e 32 70 2c 20 6e 32 70 2c 20 72 6e 2c 20 47 4d n2p, n2p, rn, GM
27c0: 50 5f 4e 55 4d 42 5f 42 49 54 53 20 2d 20 63 6e P_NUMB_BITS - cn
27d0: 74 29 3b 0a 09 09 6e 32 70 5b 30 5d 20 7c 3d 20 t);...n2p[0] |=
27e0: 6e 70 5b 69 6e 20 2d 20 31 5d 20 26 20 28 47 4d np[in - 1] & (GM
27f0: 50 5f 4e 55 4d 42 5f 4d 41 53 4b 20 3e 3e 20 63 P_NUMB_MASK >> c
2800: 6e 74 29 3b 0a 0a 09 09 2f 2a 20 55 70 64 61 74 nt);..../* Updat
2810: 65 20 70 61 72 74 69 61 6c 20 72 65 6d 61 69 6e e partial remain
2820: 64 65 72 20 77 69 74 68 20 70 61 72 74 69 61 6c der with partial
2830: 6c 79 20 75 73 65 64 20 64 69 76 69 73 6f 72 20 ly used divisor
2840: 6c 69 6d 62 2e 20 20 2a 2f 0a 09 09 63 79 32 20 limb. */...cy2
2850: 3d 20 6d 70 6e 5f 73 75 62 6d 75 6c 5f 31 20 28 = mpn_submul_1 (
2860: 6e 32 70 2c 20 71 70 2c 20 71 6e 2c 20 64 70 5b n2p, qp, qn, dp[
2870: 69 6e 20 2d 20 31 5d 20 26 20 28 47 4d 50 5f 4e in - 1] & (GMP_N
2880: 55 4d 42 5f 4d 41 53 4b 20 3e 3e 20 63 6e 74 29 UMB_MASK >> cnt)
2890: 29 3b 0a 09 09 69 66 20 28 71 6e 20 21 3d 20 72 );...if (qn != r
28a0: 6e 29 0a 09 09 20 20 7b 0a 09 09 20 20 20 20 69 n)... {... i
28b0: 66 20 28 6e 32 70 5b 71 6e 5d 20 3c 20 63 79 32 f (n2p[qn] < cy2
28c0: 29 0a 09 09 20 20 20 20 20 20 61 62 6f 72 74 20 )... abort
28d0: 28 29 3b 0a 09 09 20 20 20 20 6e 32 70 5b 71 6e ();... n2p[qn
28e0: 5d 20 2d 3d 20 63 79 32 3b 0a 09 09 20 20 7d 0a ] -= cy2;... }.
28f0: 09 09 65 6c 73 65 0a 09 09 20 20 7b 0a 09 09 20 ..else... {...
2900: 20 20 20 6e 32 70 5b 71 6e 5d 20 3d 20 63 79 31 n2p[qn] = cy1
2910: 20 2d 20 63 79 32 3b 20 2f 2a 20 26 20 47 4d 50 - cy2; /* & GMP
2920: 5f 4e 55 4d 42 5f 4d 41 53 4b 3b 20 2a 2f 0a 0a _NUMB_MASK; */..
2930: 09 09 20 20 20 20 71 75 6f 74 69 65 6e 74 5f 74 .. quotient_t
2940: 6f 6f 5f 6c 61 72 67 65 20 3d 20 28 63 79 31 20 oo_large = (cy1
2950: 3c 20 63 79 32 29 3b 0a 09 09 20 20 20 20 2b 2b < cy2);... ++
2960: 72 6e 3b 0a 09 09 20 20 7d 0a 09 09 2d 2d 69 6e rn;... }...--in
2970: 3b 0a 09 20 20 20 20 20 20 7d 0a 09 20 20 20 20 ;.. }..
2980: 2f 2a 20 54 72 75 65 3a 20 70 61 72 74 69 61 6c /* True: partial
2990: 20 72 65 6d 61 69 6e 64 65 72 20 6e 6f 77 20 69 remainder now i
29a0: 73 20 6e 65 75 74 72 61 6c 2c 20 69 2e 65 2e 2c s neutral, i.e.,
29b0: 20 69 74 20 69 73 20 6e 6f 74 20 73 68 69 66 74 it is not shift
29c0: 65 64 20 75 70 2e 20 20 2a 2f 0a 0a 09 20 20 20 ed up. */...
29d0: 20 74 70 20 3d 20 28 6d 70 5f 70 74 72 29 20 54 tp = (mp_ptr) T
29e0: 4d 50 5f 41 4c 4c 4f 43 20 28 64 6e 20 2a 20 42 MP_ALLOC (dn * B
29f0: 59 54 45 53 5f 50 45 52 5f 4d 50 5f 4c 49 4d 42 YTES_PER_MP_LIMB
2a00: 29 3b 0a 0a 09 20 20 20 20 69 66 20 28 69 6e 20 );... if (in
2a10: 3c 20 71 6e 29 0a 09 20 20 20 20 20 20 7b 0a 09 < qn).. {..
2a20: 09 69 66 20 28 69 6e 20 3d 3d 20 30 29 0a 09 09 .if (in == 0)...
2a30: 20 20 7b 0a 09 09 20 20 20 20 4d 50 4e 5f 43 4f {... MPN_CO
2a40: 50 59 20 28 72 70 2c 20 6e 32 70 2c 20 72 6e 29 PY (rp, n2p, rn)
2a50: 3b 0a 09 09 20 20 20 20 69 66 20 28 72 6e 20 21 ;... if (rn !
2a60: 3d 20 64 6e 29 0a 09 09 20 20 20 20 20 20 61 62 = dn)... ab
2a70: 6f 72 74 20 28 29 3b 0a 09 09 20 20 20 20 67 6f ort ();... go
2a80: 74 6f 20 66 6f 6f 3b 0a 09 09 20 20 7d 0a 09 09 to foo;... }...
2a90: 6d 70 6e 5f 6d 75 6c 20 28 74 70 2c 20 71 70 2c mpn_mul (tp, qp,
2aa0: 20 71 6e 2c 20 64 70 2c 20 69 6e 29 3b 0a 09 20 qn, dp, in);..
2ab0: 20 20 20 20 20 7d 0a 09 20 20 20 20 65 6c 73 65 }.. else
2ac0: 0a 09 20 20 20 20 20 20 6d 70 6e 5f 6d 75 6c 20 .. mpn_mul
2ad0: 28 74 70 2c 20 64 70 2c 20 69 6e 2c 20 71 70 2c (tp, dp, in, qp,
2ae0: 20 71 6e 29 3b 0a 0a 09 20 20 20 20 63 79 20 3d qn);... cy =
2af0: 20 6d 70 6e 5f 73 75 62 20 28 6e 32 70 2c 20 6e mpn_sub (n2p, n
2b00: 32 70 2c 20 72 6e 2c 20 74 70 20 2b 20 69 6e 2c 2p, rn, tp + in,
2b10: 20 71 6e 29 3b 0a 09 20 20 20 20 4d 50 4e 5f 43 qn);.. MPN_C
2b20: 4f 50 59 20 28 72 70 20 2b 20 69 6e 2c 20 6e 32 OPY (rp + in, n2
2b30: 70 2c 20 64 6e 20 2d 20 69 6e 29 3b 0a 09 20 20 p, dn - in);..
2b40: 20 20 71 75 6f 74 69 65 6e 74 5f 74 6f 6f 5f 6c quotient_too_l
2b50: 61 72 67 65 20 7c 3d 20 63 79 3b 0a 09 20 20 20 arge |= cy;..
2b60: 20 63 79 20 3d 20 6d 70 6e 5f 73 75 62 5f 6e 20 cy = mpn_sub_n
2b70: 28 72 70 2c 20 6e 70 2c 20 74 70 2c 20 69 6e 29 (rp, np, tp, in)
2b80: 3b 0a 09 20 20 20 20 63 79 20 3d 20 6d 70 6e 5f ;.. cy = mpn_
2b90: 73 75 62 5f 31 20 28 72 70 20 2b 20 69 6e 2c 20 sub_1 (rp + in,
2ba0: 72 70 20 2b 20 69 6e 2c 20 72 6e 2c 20 63 79 29 rp + in, rn, cy)
2bb0: 3b 0a 09 20 20 20 20 71 75 6f 74 69 65 6e 74 5f ;.. quotient_
2bc0: 74 6f 6f 5f 6c 61 72 67 65 20 7c 3d 20 63 79 3b too_large |= cy;
2bd0: 0a 09 20 20 66 6f 6f 3a 0a 09 20 20 20 20 69 66 .. foo:.. if
2be0: 20 28 71 75 6f 74 69 65 6e 74 5f 74 6f 6f 5f 6c (quotient_too_l
2bf0: 61 72 67 65 29 0a 09 20 20 20 20 20 20 7b 0a 09 arge).. {..
2c00: 09 6d 70 6e 5f 64 65 63 72 5f 75 20 28 71 70 2c .mpn_decr_u (qp,
2c10: 20 28 6d 70 5f 6c 69 6d 62 5f 74 29 20 31 29 3b (mp_limb_t) 1);
2c20: 0a 09 09 6d 70 6e 5f 61 64 64 5f 6e 20 28 72 70 ...mpn_add_n (rp
2c30: 2c 20 72 70 2c 20 64 70 2c 20 64 6e 29 3b 0a 09 , rp, dp, dn);..
2c40: 20 20 20 20 20 20 7d 0a 09 20 20 7d 0a 09 54 4d }.. }..TM
2c50: 50 5f 46 52 45 45 20 28 6d 61 72 6b 65 72 29 3b P_FREE (marker);
2c60: 0a 09 72 65 74 75 72 6e 3b 0a 20 20 20 20 20 20 ..return;.
2c70: 7d 0a 20 20 20 20 7d 0a 7d 0a }. }.}.