Hex Artifact Content
Not logged in

Artifact fa39a87b4b510549be2ff2137dfef6aba1d1bb8e:


0000: 2f 2a 20 6d 70 7a 5f 74 64 69 76 5f 72 5f 32 65  /* mpz_tdiv_r_2e
0010: 78 70 20 2d 2d 20 44 69 76 69 64 65 20 61 20 69  xp -- Divide a i
0020: 6e 74 65 67 65 72 20 62 79 20 32 2a 2a 43 4e 54  nteger by 2**CNT
0030: 20 61 6e 64 20 70 72 6f 64 75 63 65 20 61 20 72   and produce a r
0040: 65 6d 61 69 6e 64 65 72 2e 0a 0a 43 6f 70 79 72  emainder...Copyr
0050: 69 67 68 74 20 31 39 39 31 2c 20 31 39 39 33 2c  ight 1991, 1993,
0060: 20 31 39 39 34 2c 20 31 39 39 35 2c 20 32 30 30   1994, 1995, 200
0070: 31 2c 20 32 30 30 32 20 46 72 65 65 20 53 6f 66  1, 2002 Free Sof
0080: 74 77 61 72 65 20 46 6f 75 6e 64 61 74 69 6f 6e  tware Foundation
0090: 2c 20 49 6e 63 2e 0a 0a 54 68 69 73 20 66 69 6c  , Inc...This fil
00a0: 65 20 69 73 20 70 61 72 74 20 6f 66 20 74 68 65  e is part of the
00b0: 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79 2e   GNU MP Library.
00c0: 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69 62  ..The GNU MP Lib
00d0: 72 61 72 79 20 69 73 20 66 72 65 65 20 73 6f 66  rary is free sof
00e0: 74 77 61 72 65 3b 20 79 6f 75 20 63 61 6e 20 72  tware; you can r
00f0: 65 64 69 73 74 72 69 62 75 74 65 20 69 74 20 61  edistribute it a
0100: 6e 64 2f 6f 72 20 6d 6f 64 69 66 79 0a 69 74 20  nd/or modify.it 
0110: 75 6e 64 65 72 20 74 68 65 20 74 65 72 6d 73 20  under the terms 
0120: 6f 66 20 74 68 65 20 47 4e 55 20 4c 65 73 73 65  of the GNU Lesse
0130: 72 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63  r General Public
0140: 20 4c 69 63 65 6e 73 65 20 61 73 20 70 75 62 6c   License as publ
0150: 69 73 68 65 64 20 62 79 0a 74 68 65 20 46 72 65  ished by.the Fre
0160: 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64  e Software Found
0170: 61 74 69 6f 6e 3b 20 65 69 74 68 65 72 20 76 65  ation; either ve
0180: 72 73 69 6f 6e 20 32 2e 31 20 6f 66 20 74 68 65  rsion 2.1 of the
0190: 20 4c 69 63 65 6e 73 65 2c 20 6f 72 20 28 61 74   License, or (at
01a0: 20 79 6f 75 72 0a 6f 70 74 69 6f 6e 29 20 61 6e   your.option) an
01b0: 79 20 6c 61 74 65 72 20 76 65 72 73 69 6f 6e 2e  y later version.
01c0: 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69 62  ..The GNU MP Lib
01d0: 72 61 72 79 20 69 73 20 64 69 73 74 72 69 62 75  rary is distribu
01e0: 74 65 64 20 69 6e 20 74 68 65 20 68 6f 70 65 20  ted in the hope 
01f0: 74 68 61 74 20 69 74 20 77 69 6c 6c 20 62 65 20  that it will be 
0200: 75 73 65 66 75 6c 2c 20 62 75 74 0a 57 49 54 48  useful, but.WITH
0210: 4f 55 54 20 41 4e 59 20 57 41 52 52 41 4e 54 59  OUT ANY WARRANTY
0220: 3b 20 77 69 74 68 6f 75 74 20 65 76 65 6e 20 74  ; without even t
0230: 68 65 20 69 6d 70 6c 69 65 64 20 77 61 72 72 61  he implied warra
0240: 6e 74 79 20 6f 66 20 4d 45 52 43 48 41 4e 54 41  nty of MERCHANTA
0250: 42 49 4c 49 54 59 0a 6f 72 20 46 49 54 4e 45 53  BILITY.or FITNES
0260: 53 20 46 4f 52 20 41 20 50 41 52 54 49 43 55 4c  S FOR A PARTICUL
0270: 41 52 20 50 55 52 50 4f 53 45 2e 20 20 53 65 65  AR PURPOSE.  See
0280: 20 74 68 65 20 47 4e 55 20 4c 65 73 73 65 72 20   the GNU Lesser 
0290: 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 0a 4c  General Public.L
02a0: 69 63 65 6e 73 65 20 66 6f 72 20 6d 6f 72 65 20  icense for more 
02b0: 64 65 74 61 69 6c 73 2e 0a 0a 59 6f 75 20 73 68  details...You sh
02c0: 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 69 76  ould have receiv
02d0: 65 64 20 61 20 63 6f 70 79 20 6f 66 20 74 68 65  ed a copy of the
02e0: 20 47 4e 55 20 4c 65 73 73 65 72 20 47 65 6e 65   GNU Lesser Gene
02f0: 72 61 6c 20 50 75 62 6c 69 63 20 4c 69 63 65 6e  ral Public Licen
0300: 73 65 0a 61 6c 6f 6e 67 20 77 69 74 68 20 74 68  se.along with th
0310: 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79  e GNU MP Library
0320: 3b 20 73 65 65 20 74 68 65 20 66 69 6c 65 20 43  ; see the file C
0330: 4f 50 59 49 4e 47 2e 4c 49 42 2e 20 20 49 66 20  OPYING.LIB.  If 
0340: 6e 6f 74 2c 20 77 72 69 74 65 20 74 6f 0a 74 68  not, write to.th
0350: 65 20 46 72 65 65 20 53 6f 66 74 77 61 72 65 20  e Free Software 
0360: 46 6f 75 6e 64 61 74 69 6f 6e 2c 20 49 6e 63 2e  Foundation, Inc.
0370: 2c 20 35 39 20 54 65 6d 70 6c 65 20 50 6c 61 63  , 59 Temple Plac
0380: 65 20 2d 20 53 75 69 74 65 20 33 33 30 2c 20 42  e - Suite 330, B
0390: 6f 73 74 6f 6e 2c 0a 4d 41 20 30 32 31 31 31 2d  oston,.MA 02111-
03a0: 31 33 30 37 2c 20 55 53 41 2e 20 2a 2f 0a 0a 23  1307, USA. */..#
03b0: 69 6e 63 6c 75 64 65 20 22 67 6d 70 2e 68 22 0a  include "gmp.h".
03c0: 23 69 6e 63 6c 75 64 65 20 22 67 6d 70 2d 69 6d  #include "gmp-im
03d0: 70 6c 2e 68 22 0a 0a 76 6f 69 64 0a 6d 70 7a 5f  pl.h"..void.mpz_
03e0: 74 64 69 76 5f 72 5f 32 65 78 70 20 28 6d 70 7a  tdiv_r_2exp (mpz
03f0: 5f 70 74 72 20 72 65 73 2c 20 6d 70 7a 5f 73 72  _ptr res, mpz_sr
0400: 63 70 74 72 20 69 6e 2c 20 75 6e 73 69 67 6e 65  cptr in, unsigne
0410: 64 20 6c 6f 6e 67 20 69 6e 74 20 63 6e 74 29 0a  d long int cnt).
0420: 7b 0a 20 20 6d 70 5f 73 69 7a 65 5f 74 20 69 6e  {.  mp_size_t in
0430: 5f 73 69 7a 65 20 3d 20 41 42 53 20 28 69 6e 2d  _size = ABS (in-
0440: 3e 5f 6d 70 5f 73 69 7a 65 29 3b 0a 20 20 6d 70  >_mp_size);.  mp
0450: 5f 73 69 7a 65 5f 74 20 72 65 73 5f 73 69 7a 65  _size_t res_size
0460: 3b 0a 20 20 6d 70 5f 73 69 7a 65 5f 74 20 6c 69  ;.  mp_size_t li
0470: 6d 62 5f 63 6e 74 20 3d 20 63 6e 74 20 2f 20 47  mb_cnt = cnt / G
0480: 4d 50 5f 4e 55 4d 42 5f 42 49 54 53 3b 0a 20 20  MP_NUMB_BITS;.  
0490: 6d 70 5f 73 72 63 70 74 72 20 69 6e 5f 70 74 72  mp_srcptr in_ptr
04a0: 20 3d 20 69 6e 2d 3e 5f 6d 70 5f 64 3b 0a 0a 20   = in->_mp_d;.. 
04b0: 20 69 66 20 28 69 6e 5f 73 69 7a 65 20 3e 20 6c   if (in_size > l
04c0: 69 6d 62 5f 63 6e 74 29 0a 20 20 20 20 7b 0a 20  imb_cnt).    {. 
04d0: 20 20 20 20 20 2f 2a 20 54 68 65 20 69 6e 70 75       /* The inpu
04e0: 74 20 6f 70 65 72 61 6e 64 20 69 73 20 28 70 72  t operand is (pr
04f0: 6f 62 61 62 6c 79 29 20 67 72 65 61 74 65 72 20  obably) greater 
0500: 74 68 61 6e 20 32 2a 2a 43 4e 54 2e 20 20 2a 2f  than 2**CNT.  */
0510: 0a 20 20 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74  .      mp_limb_t
0520: 20 78 3b 0a 0a 20 20 20 20 20 20 78 20 3d 20 69   x;..      x = i
0530: 6e 5f 70 74 72 5b 6c 69 6d 62 5f 63 6e 74 5d 20  n_ptr[limb_cnt] 
0540: 26 20 28 28 28 6d 70 5f 6c 69 6d 62 5f 74 29 20  & (((mp_limb_t) 
0550: 31 20 3c 3c 20 63 6e 74 20 25 20 47 4d 50 5f 4e  1 << cnt % GMP_N
0560: 55 4d 42 5f 42 49 54 53 29 20 2d 20 31 29 3b 0a  UMB_BITS) - 1);.
0570: 20 20 20 20 20 20 69 66 20 28 78 20 21 3d 20 30        if (x != 0
0580: 29 0a 09 7b 0a 09 20 20 72 65 73 5f 73 69 7a 65  )..{..  res_size
0590: 20 3d 20 6c 69 6d 62 5f 63 6e 74 20 2b 20 31 3b   = limb_cnt + 1;
05a0: 0a 09 20 20 69 66 20 28 72 65 73 2d 3e 5f 6d 70  ..  if (res->_mp
05b0: 5f 61 6c 6c 6f 63 20 3c 20 72 65 73 5f 73 69 7a  _alloc < res_siz
05c0: 65 29 0a 09 20 20 20 20 5f 6d 70 7a 5f 72 65 61  e)..    _mpz_rea
05d0: 6c 6c 6f 63 20 28 72 65 73 2c 20 72 65 73 5f 73  lloc (res, res_s
05e0: 69 7a 65 29 3b 0a 0a 09 20 20 72 65 73 2d 3e 5f  ize);...  res->_
05f0: 6d 70 5f 64 5b 6c 69 6d 62 5f 63 6e 74 5d 20 3d  mp_d[limb_cnt] =
0600: 20 78 3b 0a 09 7d 0a 20 20 20 20 20 20 65 6c 73   x;..}.      els
0610: 65 0a 09 7b 0a 09 20 20 72 65 73 5f 73 69 7a 65  e..{..  res_size
0620: 20 3d 20 6c 69 6d 62 5f 63 6e 74 3b 0a 09 20 20   = limb_cnt;..  
0630: 4d 50 4e 5f 4e 4f 52 4d 41 4c 49 5a 45 20 28 69  MPN_NORMALIZE (i
0640: 6e 5f 70 74 72 2c 20 72 65 73 5f 73 69 7a 65 29  n_ptr, res_size)
0650: 3b 0a 0a 09 20 20 69 66 20 28 72 65 73 2d 3e 5f  ;...  if (res->_
0660: 6d 70 5f 61 6c 6c 6f 63 20 3c 20 72 65 73 5f 73  mp_alloc < res_s
0670: 69 7a 65 29 0a 09 20 20 20 20 5f 6d 70 7a 5f 72  ize)..    _mpz_r
0680: 65 61 6c 6c 6f 63 20 28 72 65 73 2c 20 72 65 73  ealloc (res, res
0690: 5f 73 69 7a 65 29 3b 0a 0a 09 20 20 6c 69 6d 62  _size);...  limb
06a0: 5f 63 6e 74 20 3d 20 72 65 73 5f 73 69 7a 65 3b  _cnt = res_size;
06b0: 0a 09 7d 0a 20 20 20 20 7d 0a 20 20 65 6c 73 65  ..}.    }.  else
06c0: 0a 20 20 20 20 7b 0a 20 20 20 20 20 20 2f 2a 20  .    {.      /* 
06d0: 54 68 65 20 69 6e 70 75 74 20 6f 70 65 72 61 6e  The input operan
06e0: 64 20 69 73 20 73 6d 61 6c 6c 65 72 20 74 68 61  d is smaller tha
06f0: 6e 20 32 2a 2a 43 4e 54 2e 20 20 57 65 20 70 65  n 2**CNT.  We pe
0700: 72 66 6f 72 6d 20 61 20 6e 6f 2d 6f 70 2c 0a 09  rform a no-op,..
0710: 20 61 70 61 72 74 20 66 72 6f 6d 20 74 68 61 74   apart from that
0720: 20 77 65 20 6d 69 67 68 74 20 6e 65 65 64 20 74   we might need t
0730: 6f 20 63 6f 70 79 20 49 4e 20 74 6f 20 52 45 53  o copy IN to RES
0740: 2e 20 20 2a 2f 0a 20 20 20 20 20 20 72 65 73 5f  .  */.      res_
0750: 73 69 7a 65 20 3d 20 69 6e 5f 73 69 7a 65 3b 0a  size = in_size;.
0760: 20 20 20 20 20 20 69 66 20 28 72 65 73 2d 3e 5f        if (res->_
0770: 6d 70 5f 61 6c 6c 6f 63 20 3c 20 72 65 73 5f 73  mp_alloc < res_s
0780: 69 7a 65 29 0a 09 5f 6d 70 7a 5f 72 65 61 6c 6c  ize).._mpz_reall
0790: 6f 63 20 28 72 65 73 2c 20 72 65 73 5f 73 69 7a  oc (res, res_siz
07a0: 65 29 3b 0a 0a 20 20 20 20 20 20 6c 69 6d 62 5f  e);..      limb_
07b0: 63 6e 74 20 3d 20 72 65 73 5f 73 69 7a 65 3b 0a  cnt = res_size;.
07c0: 20 20 20 20 7d 0a 0a 20 20 69 66 20 28 72 65 73      }..  if (res
07d0: 20 21 3d 20 69 6e 29 0a 20 20 20 20 4d 50 4e 5f   != in).    MPN_
07e0: 43 4f 50 59 20 28 72 65 73 2d 3e 5f 6d 70 5f 64  COPY (res->_mp_d
07f0: 2c 20 69 6e 2d 3e 5f 6d 70 5f 64 2c 20 6c 69 6d  , in->_mp_d, lim
0800: 62 5f 63 6e 74 29 3b 0a 20 20 72 65 73 2d 3e 5f  b_cnt);.  res->_
0810: 6d 70 5f 73 69 7a 65 20 3d 20 69 6e 2d 3e 5f 6d  mp_size = in->_m
0820: 70 5f 73 69 7a 65 20 3e 3d 20 30 20 3f 20 72 65  p_size >= 0 ? re
0830: 73 5f 73 69 7a 65 20 3a 20 2d 72 65 73 5f 73 69  s_size : -res_si
0840: 7a 65 3b 0a 7d 0a                                ze;.}.