Hex Artifact Content
Not logged in

Artifact 328e91dfec3a100164d524601142c8d6fc7854fc:


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                    }.    }.}.