Hex Artifact Content
Not logged in

Artifact b7334498523674abdfc70db62740ab78193c4109:


0000: 2f 2a 20 6d 70 6e 5f 70 72 65 69 6e 76 5f 6d 6f  /* mpn_preinv_mo
0010: 64 5f 31 20 28 64 69 76 69 64 65 6e 64 5f 70 74  d_1 (dividend_pt
0020: 72 2c 20 64 69 76 69 64 65 6e 64 5f 73 69 7a 65  r, dividend_size
0030: 2c 20 64 69 76 69 73 6f 72 5f 6c 69 6d 62 2c 0a  , divisor_limb,.
0040: 09 09 20 20 20 20 20 20 20 64 69 76 69 73 6f 72  ..       divisor
0050: 5f 6c 69 6d 62 5f 69 6e 76 65 72 74 65 64 29 20  _limb_inverted) 
0060: 2d 2d 0a 20 20 20 44 69 76 69 64 65 20 28 44 49  --.   Divide (DI
0070: 56 49 44 45 4e 44 5f 50 54 52 2c 2c 44 49 56 49  VIDEND_PTR,,DIVI
0080: 44 45 4e 44 5f 53 49 5a 45 29 20 62 79 20 74 68  DEND_SIZE) by th
0090: 65 20 6e 6f 72 6d 61 6c 69 7a 65 64 20 44 49 56  e normalized DIV
00a0: 49 53 4f 52 5f 4c 49 4d 42 2e 0a 20 20 20 44 49  ISOR_LIMB..   DI
00b0: 56 49 53 4f 52 5f 4c 49 4d 42 5f 49 4e 56 45 52  VISOR_LIMB_INVER
00c0: 54 45 44 20 73 68 6f 75 6c 64 20 62 65 20 32 5e  TED should be 2^
00d0: 28 32 2a 42 49 54 53 5f 50 45 52 5f 4d 50 5f 4c  (2*BITS_PER_MP_L
00e0: 49 4d 42 29 20 2f 20 44 49 56 49 53 4f 52 5f 4c  IMB) / DIVISOR_L
00f0: 49 4d 42 20 2b 0a 20 20 20 2d 20 32 5e 42 49 54  IMB +.   - 2^BIT
0100: 53 5f 50 45 52 5f 4d 50 5f 4c 49 4d 42 2e 0a 20  S_PER_MP_LIMB.. 
0110: 20 20 52 65 74 75 72 6e 20 74 68 65 20 73 69 6e    Return the sin
0120: 67 6c 65 2d 6c 69 6d 62 20 72 65 6d 61 69 6e 64  gle-limb remaind
0130: 65 72 2e 0a 0a 43 6f 70 79 72 69 67 68 74 20 31  er...Copyright 1
0140: 39 39 31 2c 20 31 39 39 33 2c 20 31 39 39 34 2c  991, 1993, 1994,
0150: 20 32 30 30 30 2c 20 32 30 30 31 2c 20 32 30 30   2000, 2001, 200
0160: 32 20 46 72 65 65 20 53 6f 66 74 77 61 72 65 20  2 Free Software 
0170: 46 6f 75 6e 64 61 74 69 6f 6e 2c 20 49 6e 63 2e  Foundation, Inc.
0180: 0a 0a 54 68 69 73 20 66 69 6c 65 20 69 73 20 70  ..This file is p
0190: 61 72 74 20 6f 66 20 74 68 65 20 47 4e 55 20 4d  art of the GNU M
01a0: 50 20 4c 69 62 72 61 72 79 2e 0a 0a 54 68 65 20  P Library...The 
01b0: 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79 20 69  GNU MP Library i
01c0: 73 20 66 72 65 65 20 73 6f 66 74 77 61 72 65 3b  s free software;
01d0: 20 79 6f 75 20 63 61 6e 20 72 65 64 69 73 74 72   you can redistr
01e0: 69 62 75 74 65 20 69 74 20 61 6e 64 2f 6f 72 20  ibute it and/or 
01f0: 6d 6f 64 69 66 79 0a 69 74 20 75 6e 64 65 72 20  modify.it under 
0200: 74 68 65 20 74 65 72 6d 73 20 6f 66 20 74 68 65  the terms of the
0210: 20 47 4e 55 20 4c 65 73 73 65 72 20 47 65 6e 65   GNU Lesser Gene
0220: 72 61 6c 20 50 75 62 6c 69 63 20 4c 69 63 65 6e  ral Public Licen
0230: 73 65 20 61 73 20 70 75 62 6c 69 73 68 65 64 20  se as published 
0240: 62 79 0a 74 68 65 20 46 72 65 65 20 53 6f 66 74  by.the Free Soft
0250: 77 61 72 65 20 46 6f 75 6e 64 61 74 69 6f 6e 3b  ware Foundation;
0260: 20 65 69 74 68 65 72 20 76 65 72 73 69 6f 6e 20   either version 
0270: 32 2e 31 20 6f 66 20 74 68 65 20 4c 69 63 65 6e  2.1 of the Licen
0280: 73 65 2c 20 6f 72 20 28 61 74 20 79 6f 75 72 0a  se, or (at your.
0290: 6f 70 74 69 6f 6e 29 20 61 6e 79 20 6c 61 74 65  option) any late
02a0: 72 20 76 65 72 73 69 6f 6e 2e 0a 0a 54 68 65 20  r version...The 
02b0: 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79 20 69  GNU MP Library i
02c0: 73 20 64 69 73 74 72 69 62 75 74 65 64 20 69 6e  s distributed in
02d0: 20 74 68 65 20 68 6f 70 65 20 74 68 61 74 20 69   the hope that i
02e0: 74 20 77 69 6c 6c 20 62 65 20 75 73 65 66 75 6c  t will be useful
02f0: 2c 20 62 75 74 0a 57 49 54 48 4f 55 54 20 41 4e  , but.WITHOUT AN
0300: 59 20 57 41 52 52 41 4e 54 59 3b 20 77 69 74 68  Y WARRANTY; with
0310: 6f 75 74 20 65 76 65 6e 20 74 68 65 20 69 6d 70  out even the imp
0320: 6c 69 65 64 20 77 61 72 72 61 6e 74 79 20 6f 66  lied warranty of
0330: 20 4d 45 52 43 48 41 4e 54 41 42 49 4c 49 54 59   MERCHANTABILITY
0340: 0a 6f 72 20 46 49 54 4e 45 53 53 20 46 4f 52 20  .or FITNESS FOR 
0350: 41 20 50 41 52 54 49 43 55 4c 41 52 20 50 55 52  A PARTICULAR PUR
0360: 50 4f 53 45 2e 20 20 53 65 65 20 74 68 65 20 47  POSE.  See the G
0370: 4e 55 20 4c 65 73 73 65 72 20 47 65 6e 65 72 61  NU Lesser Genera
0380: 6c 20 50 75 62 6c 69 63 0a 4c 69 63 65 6e 73 65  l Public.License
0390: 20 66 6f 72 20 6d 6f 72 65 20 64 65 74 61 69 6c   for more detail
03a0: 73 2e 0a 0a 59 6f 75 20 73 68 6f 75 6c 64 20 68  s...You should h
03b0: 61 76 65 20 72 65 63 65 69 76 65 64 20 61 20 63  ave received a c
03c0: 6f 70 79 20 6f 66 20 74 68 65 20 47 4e 55 20 4c  opy of the GNU L
03d0: 65 73 73 65 72 20 47 65 6e 65 72 61 6c 20 50 75  esser General Pu
03e0: 62 6c 69 63 20 4c 69 63 65 6e 73 65 0a 61 6c 6f  blic License.alo
03f0: 6e 67 20 77 69 74 68 20 74 68 65 20 47 4e 55 20  ng with the GNU 
0400: 4d 50 20 4c 69 62 72 61 72 79 3b 20 73 65 65 20  MP Library; see 
0410: 74 68 65 20 66 69 6c 65 20 43 4f 50 59 49 4e 47  the file COPYING
0420: 2e 4c 49 42 2e 20 20 49 66 20 6e 6f 74 2c 20 77  .LIB.  If not, w
0430: 72 69 74 65 20 74 6f 0a 74 68 65 20 46 72 65 65  rite to.the Free
0440: 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e 64 61   Software Founda
0450: 74 69 6f 6e 2c 20 49 6e 63 2e 2c 20 35 39 20 54  tion, Inc., 59 T
0460: 65 6d 70 6c 65 20 50 6c 61 63 65 20 2d 20 53 75  emple Place - Su
0470: 69 74 65 20 33 33 30 2c 20 42 6f 73 74 6f 6e 2c  ite 330, Boston,
0480: 0a 4d 41 20 30 32 31 31 31 2d 31 33 30 37 2c 20  .MA 02111-1307, 
0490: 55 53 41 2e 20 2a 2f 0a 0a 23 69 6e 63 6c 75 64  USA. */..#includ
04a0: 65 20 22 67 6d 70 2e 68 22 0a 23 69 6e 63 6c 75  e "gmp.h".#inclu
04b0: 64 65 20 22 67 6d 70 2d 69 6d 70 6c 2e 68 22 0a  de "gmp-impl.h".
04c0: 23 69 6e 63 6c 75 64 65 20 22 6c 6f 6e 67 6c 6f  #include "longlo
04d0: 6e 67 2e 68 22 0a 0a 0a 2f 2a 20 54 68 69 73 20  ng.h".../* This 
04e0: 66 75 6e 63 74 69 6f 6e 20 75 73 65 64 20 74 6f  function used to
04f0: 20 62 65 20 64 6f 63 75 6d 65 6e 74 65 64 2c 20   be documented, 
0500: 62 75 74 20 69 73 20 6e 6f 77 20 63 6f 6e 73 69  but is now consi
0510: 64 65 72 65 64 20 6f 62 73 6f 6c 65 74 65 2e 20  dered obsolete. 
0520: 20 49 74 0a 20 20 20 63 6f 6e 74 69 6e 75 65 73   It.   continues
0530: 20 74 6f 20 65 78 69 73 74 20 66 6f 72 20 62 69   to exist for bi
0540: 6e 61 72 79 20 63 6f 6d 70 61 74 69 62 69 6c 69  nary compatibili
0550: 74 79 2c 20 65 76 65 6e 20 77 68 65 6e 20 6e 6f  ty, even when no
0560: 74 20 72 65 71 75 69 72 65 64 0a 20 20 20 69 6e  t required.   in
0570: 74 65 72 6e 61 6c 6c 79 2e 20 20 2a 2f 0a 0a 6d  ternally.  */..m
0580: 70 5f 6c 69 6d 62 5f 74 0a 6d 70 6e 5f 70 72 65  p_limb_t.mpn_pre
0590: 69 6e 76 5f 6d 6f 64 5f 31 20 28 6d 70 5f 73 72  inv_mod_1 (mp_sr
05a0: 63 70 74 72 20 64 69 76 69 64 65 6e 64 5f 70 74  cptr dividend_pt
05b0: 72 2c 20 6d 70 5f 73 69 7a 65 5f 74 20 64 69 76  r, mp_size_t div
05c0: 69 64 65 6e 64 5f 73 69 7a 65 2c 0a 09 09 20 20  idend_size,...  
05d0: 6d 70 5f 6c 69 6d 62 5f 74 20 64 69 76 69 73 6f  mp_limb_t diviso
05e0: 72 5f 6c 69 6d 62 2c 20 6d 70 5f 6c 69 6d 62 5f  r_limb, mp_limb_
05f0: 74 20 64 69 76 69 73 6f 72 5f 6c 69 6d 62 5f 69  t divisor_limb_i
0600: 6e 76 65 72 74 65 64 29 0a 7b 0a 20 20 6d 70 5f  nverted).{.  mp_
0610: 73 69 7a 65 5f 74 20 69 3b 0a 20 20 6d 70 5f 6c  size_t i;.  mp_l
0620: 69 6d 62 5f 74 20 6e 30 2c 20 72 3b 0a 20 20 6d  imb_t n0, r;.  m
0630: 70 5f 6c 69 6d 62 5f 74 20 64 75 6d 6d 79 3b 0a  p_limb_t dummy;.
0640: 0a 20 20 41 53 53 45 52 54 20 28 64 69 76 69 64  .  ASSERT (divid
0650: 65 6e 64 5f 73 69 7a 65 20 3e 3d 20 31 29 3b 0a  end_size >= 1);.
0660: 20 20 41 53 53 45 52 54 20 28 64 69 76 69 73 6f    ASSERT (diviso
0670: 72 5f 6c 69 6d 62 20 26 20 47 4d 50 5f 4c 49 4d  r_limb & GMP_LIM
0680: 42 5f 48 49 47 48 42 49 54 29 3b 0a 0a 20 20 72  B_HIGHBIT);..  r
0690: 20 3d 20 64 69 76 69 64 65 6e 64 5f 70 74 72 5b   = dividend_ptr[
06a0: 64 69 76 69 64 65 6e 64 5f 73 69 7a 65 2d 31 5d  dividend_size-1]
06b0: 3b 0a 20 20 69 66 20 28 72 20 3e 3d 20 64 69 76  ;.  if (r >= div
06c0: 69 73 6f 72 5f 6c 69 6d 62 29 0a 20 20 20 20 72  isor_limb).    r
06d0: 20 2d 3d 20 64 69 76 69 73 6f 72 5f 6c 69 6d 62   -= divisor_limb
06e0: 3b 0a 0a 20 20 66 6f 72 20 28 69 20 3d 20 64 69  ;..  for (i = di
06f0: 76 69 64 65 6e 64 5f 73 69 7a 65 20 2d 20 32 3b  vidend_size - 2;
0700: 20 69 20 3e 3d 20 30 3b 20 69 2d 2d 29 0a 20 20   i >= 0; i--).  
0710: 20 20 7b 0a 20 20 20 20 20 20 6e 30 20 3d 20 64    {.      n0 = d
0720: 69 76 69 64 65 6e 64 5f 70 74 72 5b 69 5d 3b 0a  ividend_ptr[i];.
0730: 20 20 20 20 20 20 75 64 69 76 5f 71 72 6e 6e 64        udiv_qrnnd
0740: 5f 70 72 65 69 6e 76 20 28 64 75 6d 6d 79 2c 20  _preinv (dummy, 
0750: 72 2c 20 72 2c 20 6e 30 2c 20 64 69 76 69 73 6f  r, r, n0, diviso
0760: 72 5f 6c 69 6d 62 2c 20 64 69 76 69 73 6f 72 5f  r_limb, divisor_
0770: 6c 69 6d 62 5f 69 6e 76 65 72 74 65 64 29 3b 0a  limb_inverted);.
0780: 20 20 20 20 7d 0a 20 20 72 65 74 75 72 6e 20 72      }.  return r
0790: 3b 0a 7d 0a                                      ;.}.