Hex Artifact Content
Not logged in

Artifact 85bbb39a449853c2b2530f450be93630338e6963:


0000: 2f 2a 20 43 72 61 79 20 50 56 50 2f 49 45 45 45  /* Cray PVP/IEEE
0010: 20 6d 70 6e 5f 6d 75 6c 5f 62 61 73 65 63 61 73   mpn_mul_basecas
0020: 65 2e 0a 0a 43 6f 70 79 72 69 67 68 74 20 32 30  e...Copyright 20
0030: 30 30 2c 20 32 30 30 31 20 46 72 65 65 20 53 6f  00, 2001 Free So
0040: 66 74 77 61 72 65 20 46 6f 75 6e 64 61 74 69 6f  ftware Foundatio
0050: 6e 2c 20 49 6e 63 2e 0a 0a 54 68 69 73 20 66 69  n, Inc...This fi
0060: 6c 65 20 69 73 20 70 61 72 74 20 6f 66 20 74 68  le is part of th
0070: 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72 79  e GNU MP Library
0080: 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69  ...The GNU MP Li
0090: 62 72 61 72 79 20 69 73 20 66 72 65 65 20 73 6f  brary is free so
00a0: 66 74 77 61 72 65 3b 20 79 6f 75 20 63 61 6e 20  ftware; you can 
00b0: 72 65 64 69 73 74 72 69 62 75 74 65 20 69 74 20  redistribute it 
00c0: 61 6e 64 2f 6f 72 20 6d 6f 64 69 66 79 0a 69 74  and/or modify.it
00d0: 20 75 6e 64 65 72 20 74 68 65 20 74 65 72 6d 73   under the terms
00e0: 20 6f 66 20 74 68 65 20 47 4e 55 20 4c 65 73 73   of the GNU Less
00f0: 65 72 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69  er General Publi
0100: 63 20 4c 69 63 65 6e 73 65 20 61 73 20 70 75 62  c License as pub
0110: 6c 69 73 68 65 64 20 62 79 0a 74 68 65 20 46 72  lished by.the Fr
0120: 65 65 20 53 6f 66 74 77 61 72 65 20 46 6f 75 6e  ee Software Foun
0130: 64 61 74 69 6f 6e 3b 20 65 69 74 68 65 72 20 76  dation; either v
0140: 65 72 73 69 6f 6e 20 32 2e 31 20 6f 66 20 74 68  ersion 2.1 of th
0150: 65 20 4c 69 63 65 6e 73 65 2c 20 6f 72 20 28 61  e License, or (a
0160: 74 20 79 6f 75 72 0a 6f 70 74 69 6f 6e 29 20 61  t your.option) a
0170: 6e 79 20 6c 61 74 65 72 20 76 65 72 73 69 6f 6e  ny later version
0180: 2e 0a 0a 54 68 65 20 47 4e 55 20 4d 50 20 4c 69  ...The GNU MP Li
0190: 62 72 61 72 79 20 69 73 20 64 69 73 74 72 69 62  brary is distrib
01a0: 75 74 65 64 20 69 6e 20 74 68 65 20 68 6f 70 65  uted in the hope
01b0: 20 74 68 61 74 20 69 74 20 77 69 6c 6c 20 62 65   that it will be
01c0: 20 75 73 65 66 75 6c 2c 20 62 75 74 0a 57 49 54   useful, but.WIT
01d0: 48 4f 55 54 20 41 4e 59 20 57 41 52 52 41 4e 54  HOUT ANY WARRANT
01e0: 59 3b 20 77 69 74 68 6f 75 74 20 65 76 65 6e 20  Y; without even 
01f0: 74 68 65 20 69 6d 70 6c 69 65 64 20 77 61 72 72  the implied warr
0200: 61 6e 74 79 20 6f 66 20 4d 45 52 43 48 41 4e 54  anty of MERCHANT
0210: 41 42 49 4c 49 54 59 0a 6f 72 20 46 49 54 4e 45  ABILITY.or FITNE
0220: 53 53 20 46 4f 52 20 41 20 50 41 52 54 49 43 55  SS FOR A PARTICU
0230: 4c 41 52 20 50 55 52 50 4f 53 45 2e 20 20 53 65  LAR PURPOSE.  Se
0240: 65 20 74 68 65 20 47 4e 55 20 4c 65 73 73 65 72  e the GNU Lesser
0250: 20 47 65 6e 65 72 61 6c 20 50 75 62 6c 69 63 0a   General Public.
0260: 4c 69 63 65 6e 73 65 20 66 6f 72 20 6d 6f 72 65  License for more
0270: 20 64 65 74 61 69 6c 73 2e 0a 0a 59 6f 75 20 73   details...You s
0280: 68 6f 75 6c 64 20 68 61 76 65 20 72 65 63 65 69  hould have recei
0290: 76 65 64 20 61 20 63 6f 70 79 20 6f 66 20 74 68  ved a copy of th
02a0: 65 20 47 4e 55 20 4c 65 73 73 65 72 20 47 65 6e  e GNU Lesser Gen
02b0: 65 72 61 6c 20 50 75 62 6c 69 63 20 4c 69 63 65  eral Public Lice
02c0: 6e 73 65 0a 61 6c 6f 6e 67 20 77 69 74 68 20 74  nse.along with t
02d0: 68 65 20 47 4e 55 20 4d 50 20 4c 69 62 72 61 72  he GNU MP Librar
02e0: 79 3b 20 73 65 65 20 74 68 65 20 66 69 6c 65 20  y; see the file 
02f0: 43 4f 50 59 49 4e 47 2e 4c 49 42 2e 20 20 49 66  COPYING.LIB.  If
0300: 20 6e 6f 74 2c 20 77 72 69 74 65 20 74 6f 0a 74   not, write to.t
0310: 68 65 20 46 72 65 65 20 53 6f 66 74 77 61 72 65  he Free Software
0320: 20 46 6f 75 6e 64 61 74 69 6f 6e 2c 20 49 6e 63   Foundation, Inc
0330: 2e 2c 20 35 39 20 54 65 6d 70 6c 65 20 50 6c 61  ., 59 Temple Pla
0340: 63 65 20 2d 20 53 75 69 74 65 20 33 33 30 2c 20  ce - Suite 330, 
0350: 42 6f 73 74 6f 6e 2c 0a 4d 41 20 30 32 31 31 31  Boston,.MA 02111
0360: 2d 31 33 30 37 2c 20 55 53 41 2e 20 20 2a 2f 0a  -1307, USA.  */.
0370: 0a 2f 2a 20 54 68 65 20 6d 6f 73 74 20 63 72 69  ./* The most cri
0380: 74 69 63 61 6c 20 6c 6f 6f 70 20 6f 66 20 74 68  tical loop of th
0390: 69 73 20 63 6f 64 65 20 72 75 6e 73 20 61 74 20  is code runs at 
03a0: 61 62 6f 75 74 20 35 20 63 79 63 6c 65 73 2f 6c  about 5 cycles/l
03b0: 69 6d 62 20 6f 6e 20 61 20 54 39 30 2e 0a 20 20  imb on a T90..  
03c0: 20 54 68 61 74 20 69 73 20 6e 6f 74 20 70 65 72   That is not per
03d0: 66 65 63 74 2c 20 6d 61 69 6e 6c 79 20 64 75 65  fect, mainly due
03e0: 20 74 6f 20 76 65 63 74 6f 72 20 72 65 67 69 73   to vector regis
03f0: 74 65 72 20 73 68 6f 72 74 61 67 65 2e 20 20 2a  ter shortage.  *
0400: 2f 0a 0a 23 69 6e 63 6c 75 64 65 20 3c 69 6e 74  /..#include <int
0410: 72 69 6e 73 69 63 73 2e 68 3e 0a 23 69 6e 63 6c  rinsics.h>.#incl
0420: 75 64 65 20 22 67 6d 70 2e 68 22 0a 23 69 6e 63  ude "gmp.h".#inc
0430: 6c 75 64 65 20 22 67 6d 70 2d 69 6d 70 6c 2e 68  lude "gmp-impl.h
0440: 22 0a 0a 76 6f 69 64 0a 6d 70 6e 5f 6d 75 6c 5f  "..void.mpn_mul_
0450: 62 61 73 65 63 61 73 65 20 28 6d 70 5f 70 74 72  basecase (mp_ptr
0460: 20 72 70 2c 0a 09 09 20 20 6d 70 5f 73 72 63 70   rp,...  mp_srcp
0470: 74 72 20 75 70 2c 20 6d 70 5f 73 69 7a 65 5f 74  tr up, mp_size_t
0480: 20 75 6e 2c 0a 09 09 20 20 6d 70 5f 73 72 63 70   un,...  mp_srcp
0490: 74 72 20 76 70 2c 20 6d 70 5f 73 69 7a 65 5f 74  tr vp, mp_size_t
04a0: 20 76 6e 29 0a 7b 0a 20 20 6d 70 5f 6c 69 6d 62   vn).{.  mp_limb
04b0: 5f 74 20 63 79 5b 75 6e 20 2b 20 76 6e 5d 3b 0a  _t cy[un + vn];.
04c0: 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 76 6c 3b 0a    mp_limb_t vl;.
04d0: 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 61 2c 20 62    mp_limb_t a, b
04e0: 2c 20 72 2c 20 73 30 2c 20 73 31 2c 20 63 30 2c  , r, s0, s1, c0,
04f0: 20 63 31 3b 0a 20 20 6d 70 5f 73 69 7a 65 5f 74   c1;.  mp_size_t
0500: 20 69 2c 20 6a 3b 0a 20 20 69 6e 74 20 6d 6f 72   i, j;.  int mor
0510: 65 5f 63 61 72 72 69 65 73 3b 0a 0a 20 20 66 6f  e_carries;..  fo
0520: 72 20 28 69 20 3d 20 30 3b 20 69 20 3c 20 75 6e  r (i = 0; i < un
0530: 20 2b 20 76 6e 3b 20 69 2b 2b 29 0a 20 20 20 20   + vn; i++).    
0540: 7b 0a 20 20 20 20 20 20 72 70 5b 69 5d 20 3d 20  {.      rp[i] = 
0550: 30 3b 0a 20 20 20 20 20 20 63 79 5b 69 5d 20 3d  0;.      cy[i] =
0560: 20 30 3b 0a 20 20 20 20 7d 0a 0a 23 70 72 61 67   0;.    }..#prag
0570: 6d 61 20 5f 43 52 49 20 6e 6f 76 65 63 74 6f 72  ma _CRI novector
0580: 0a 20 20 66 6f 72 20 28 6a 20 3d 20 30 3b 20 6a  .  for (j = 0; j
0590: 20 3c 20 76 6e 3b 20 6a 2b 2b 29 0a 20 20 20 20   < vn; j++).    
05a0: 7b 0a 20 20 20 20 20 20 76 6c 20 3d 20 76 70 5b  {.      vl = vp[
05b0: 6a 5d 3b 0a 0a 20 20 20 20 20 20 61 20 3d 20 75  j];..      a = u
05c0: 70 5b 30 5d 20 2a 20 76 6c 3b 0a 20 20 20 20 20  p[0] * vl;.     
05d0: 20 72 20 3d 20 72 70 5b 6a 5d 3b 0a 20 20 20 20   r = rp[j];.    
05e0: 20 20 73 30 20 3d 20 61 20 2b 20 72 3b 0a 20 20    s0 = a + r;.  
05f0: 20 20 20 20 72 70 5b 6a 5d 20 3d 20 73 30 3b 0a      rp[j] = s0;.
0600: 20 20 20 20 20 20 63 30 20 3d 20 28 28 61 20 26        c0 = ((a &
0610: 20 72 29 20 7c 20 28 28 61 20 7c 20 72 29 20 26   r) | ((a | r) &
0620: 20 7e 73 30 29 29 20 3e 3e 20 36 33 3b 0a 20 20   ~s0)) >> 63;.  
0630: 20 20 20 20 63 79 5b 6a 5d 20 2b 3d 20 63 30 3b      cy[j] += c0;
0640: 0a 0a 23 70 72 61 67 6d 61 20 5f 43 52 49 20 69  ..#pragma _CRI i
0650: 76 64 65 70 0a 20 20 20 20 20 20 66 6f 72 20 28  vdep.      for (
0660: 69 20 3d 20 31 3b 20 69 20 3c 20 75 6e 3b 20 69  i = 1; i < un; i
0670: 2b 2b 29 0a 09 7b 0a 09 20 20 61 20 3d 20 75 70  ++)..{..  a = up
0680: 5b 69 5d 20 2a 20 76 6c 3b 0a 09 20 20 62 20 3d  [i] * vl;..  b =
0690: 20 5f 69 6e 74 5f 6d 75 6c 74 5f 75 70 70 65 72   _int_mult_upper
06a0: 20 28 75 70 5b 69 20 2d 20 31 5d 2c 20 76 6c 29   (up[i - 1], vl)
06b0: 3b 0a 09 20 20 73 30 20 3d 20 61 20 2b 20 62 3b  ;..  s0 = a + b;
06c0: 0a 09 20 20 63 30 20 3d 20 28 28 61 20 26 20 62  ..  c0 = ((a & b
06d0: 29 20 7c 20 28 28 61 20 7c 20 62 29 20 26 20 7e  ) | ((a | b) & ~
06e0: 73 30 29 29 20 3e 3e 20 36 33 3b 0a 09 20 20 72  s0)) >> 63;..  r
06f0: 20 3d 20 72 70 5b 6a 20 2b 20 69 5d 3b 0a 09 20   = rp[j + i];.. 
0700: 20 73 31 20 3d 20 73 30 20 2b 20 72 3b 0a 09 20   s1 = s0 + r;.. 
0710: 20 72 70 5b 6a 20 2b 20 69 5d 20 3d 20 73 31 3b   rp[j + i] = s1;
0720: 0a 09 20 20 63 31 20 3d 20 28 28 73 30 20 26 20  ..  c1 = ((s0 & 
0730: 72 29 20 7c 20 28 28 73 30 20 7c 20 72 29 20 26  r) | ((s0 | r) &
0740: 20 7e 73 31 29 29 20 3e 3e 20 36 33 3b 0a 09 20   ~s1)) >> 63;.. 
0750: 20 63 79 5b 6a 20 2b 20 69 5d 20 2b 3d 20 63 30   cy[j + i] += c0
0760: 20 2b 20 63 31 3b 0a 09 7d 0a 20 20 20 20 20 20   + c1;..}.      
0770: 72 70 5b 6a 20 2b 20 75 6e 5d 20 3d 20 5f 69 6e  rp[j + un] = _in
0780: 74 5f 6d 75 6c 74 5f 75 70 70 65 72 20 28 75 70  t_mult_upper (up
0790: 5b 75 6e 20 2d 20 31 5d 2c 20 76 6c 29 3b 0a 20  [un - 1], vl);. 
07a0: 20 20 20 7d 0a 0a 20 20 6d 6f 72 65 5f 63 61 72     }..  more_car
07b0: 72 69 65 73 20 3d 20 30 3b 0a 23 70 72 61 67 6d  ries = 0;.#pragm
07c0: 61 20 5f 43 52 49 20 69 76 64 65 70 0a 20 20 66  a _CRI ivdep.  f
07d0: 6f 72 20 28 69 20 3d 20 31 3b 20 69 20 3c 20 75  or (i = 1; i < u
07e0: 6e 20 2b 20 76 6e 3b 20 69 2b 2b 29 0a 20 20 20  n + vn; i++).   
07f0: 20 7b 0a 20 20 20 20 20 20 72 20 3d 20 72 70 5b   {.      r = rp[
0800: 69 5d 3b 0a 20 20 20 20 20 20 63 30 20 3d 20 63  i];.      c0 = c
0810: 79 5b 69 20 2d 20 31 5d 3b 0a 20 20 20 20 20 20  y[i - 1];.      
0820: 73 30 20 3d 20 72 20 2b 20 63 30 3b 0a 20 20 20  s0 = r + c0;.   
0830: 20 20 20 72 70 5b 69 5d 20 3d 20 73 30 3b 0a 20     rp[i] = s0;. 
0840: 20 20 20 20 20 63 30 20 3d 20 28 72 20 26 20 7e       c0 = (r & ~
0850: 73 30 29 20 3e 3e 20 36 33 3b 0a 20 20 20 20 20  s0) >> 63;.     
0860: 20 6d 6f 72 65 5f 63 61 72 72 69 65 73 20 2b 3d   more_carries +=
0870: 20 63 30 3b 0a 20 20 20 20 7d 0a 20 20 2f 2a 20   c0;.    }.  /* 
0880: 49 66 20 74 68 61 74 20 73 65 63 6f 6e 64 20 6c  If that second l
0890: 6f 6f 70 20 67 65 6e 65 72 61 74 65 64 20 63 61  oop generated ca
08a0: 72 72 79 2c 20 68 61 6e 64 6c 65 20 74 68 61 74  rry, handle that
08b0: 20 69 6e 20 73 63 61 6c 61 72 20 6c 6f 6f 70 2e   in scalar loop.
08c0: 20 20 2a 2f 0a 20 20 69 66 20 28 6d 6f 72 65 5f    */.  if (more_
08d0: 63 61 72 72 69 65 73 29 0a 20 20 20 20 7b 0a 20  carries).    {. 
08e0: 20 20 20 20 20 6d 70 5f 6c 69 6d 62 5f 74 20 63       mp_limb_t c
08f0: 79 72 65 63 20 3d 20 30 3b 0a 20 20 20 20 20 20  yrec = 0;.      
0900: 66 6f 72 20 28 69 20 3d 20 31 3b 20 69 20 3c 20  for (i = 1; i < 
0910: 75 6e 20 2b 20 76 6e 3b 20 69 2b 2b 29 0a 09 7b  un + vn; i++)..{
0920: 0a 09 20 20 72 20 3d 20 72 70 5b 69 5d 3b 0a 09  ..  r = rp[i];..
0930: 20 20 63 30 20 3d 20 28 72 20 3c 20 63 79 5b 69    c0 = (r < cy[i
0940: 20 2d 20 31 5d 29 3b 0a 09 20 20 73 30 20 3d 20   - 1]);..  s0 = 
0950: 72 20 2b 20 63 79 72 65 63 3b 0a 09 20 20 72 70  r + cyrec;..  rp
0960: 5b 69 5d 20 3d 20 73 30 3b 0a 09 20 20 63 31 20  [i] = s0;..  c1 
0970: 3d 20 28 72 20 26 20 7e 73 30 29 20 3e 3e 20 36  = (r & ~s0) >> 6
0980: 33 3b 0a 09 20 20 63 79 72 65 63 20 3d 20 63 30  3;..  cyrec = c0
0990: 20 7c 20 63 31 3b 0a 09 7d 0a 20 20 20 20 7d 0a   | c1;..}.    }.
09a0: 7d 0a                                            }.