js/src/jit-test/tests/sunspider/check-mont.js

   1 // regression test for Bug 452008 - TM: SRP in Clipperz crypto library fails when JIT (TraceMonkey) is enabled.
   2
   3 var x = [9385, 32112, 25383, 16317, 30138, 14565, 17812, 24500, 2719, 30174, 3546, 9096, 15352, 19120, 20648, 14334, 7426, 0, 0, 0];
   4 var n = [27875, 25925, 30422, 12227, 27798, 32170, 10873, 21748, 30629, 26296, 20697, 5125, 4815, 2221, 14392, 23369, 5560, 2, 0, 0];
   5 var np = 18229;
   6 var expected = [18770, 31456, 17999, 32635, 27508, 29131, 2856, 16233, 5439, 27580, 7093, 18192, 30804, 5472, 8529, 28649, 14852, 0, 0, 0];
   7
   8 //globals
   9 bpe=0;         //bits stored per array element
  10 mask=0;        //AND this with an array element to chop it down to bpe bits
  11
  12 //initialize the global variables
  13 for (bpe=0; (1<<(bpe+1)) > (1<<bpe); bpe++);  //bpe=number of bits in the mantissa on this platform
  14 bpe>>=1;                   //bpe=number of bits in one element of the array representing the bigInt
  15 mask=(1<<bpe)-1;           //AND the mask with an integer to get its bpe least significant bits
  16
  17
  18 //the following global variables are scratchpad memory to
  19 //reduce dynamic memory allocation in the inner loop
  20 sa = new Array(0); //used in mont_()
  21
  22 //do x=y on bigInts x and y.  x must be an array at least as big as y (not counting the leading zeros in y).
  23 function copy_(x,y) {
  24   var i;
  25   var k=x.length<y.length ? x.length : y.length;
  26   for (i=0;i<k;i++)
  27     x[i]=y[i];
  28   for (i=k;i<x.length;i++)
  29     x[i]=0;
  30 }
  31
  32 //do x=y on bigInt x and integer y.
  33 function copyInt_(x,n) {
  34   var i,c;
  35   for (c=n,i=0;i<x.length;i++) {
  36     x[i]=c & mask;
  37     c>>=bpe;
  38   }
  39 }
  40
  41 //is x > y? (x and y both nonnegative)
  42 function greater(x,y) {
  43   var i;
  44   var k=(x.length<y.length) ? x.length : y.length;
  45
  46   for (i=x.length;i<y.length;i++)
  47     if (y[i])
  48       return 0;  //y has more digits
  49
  50   for (i=y.length;i<x.length;i++)
  51     if (x[i])
  52       return 1;  //x has more digits
  53
  54   for (i=k-1;i>=0;i--)
  55     if (x[i]>y[i])
  56       return 1;
  57     else if (x[i]<y[i])
  58       return 0;
  59   return 0;
  60 }
  61
  62
  63 //do x=x*y*Ri mod n for bigInts x,y,n,
  64 //  where Ri = 2**(-kn*bpe) mod n, and kn is the
  65 //  number of elements in the n array, not
  66 //  counting leading zeros.
  67 //x must be large enough to hold the answer.
  68 //It's OK if x and y are the same variable.
  69 //must have:
  70 //  x,y < n
  71 //  n is odd
  72 //  np = -(n^(-1)) mod radix
  73 function mont_(x,y,n,np) {
  74   var i,j,c,ui,t;
  75   var kn=n.length;
  76   var ky=y.length;
  77
  78   if (sa.length!=kn)
  79     sa=new Array(kn);
  80
  81   for (;kn>0 && n[kn-1]==0;kn--); //ignore leading zeros of n
  82   for (;ky>0 && y[ky-1]==0;ky--); //ignore leading zeros of y
  83
  84   copyInt_(sa,0);
  85
  86   //the following loop consumes 95% of the runtime for randTruePrime_() and powMod_() for large keys
  87   for (i=0; i<kn; i++) {
  88     t=sa[0]+x[i]*y[0];
  89     ui=((t & mask) * np) & mask;  //the inner "& mask" is needed on Macintosh MSIE, but not windows MSIE
  90     c=(t+ui*n[0]) >> bpe;
  91     t=x[i];
  92
  93     //do sa=(sa+x[i]*y+ui*n)/b   where b=2**bpe
  94     for (j=1;j<ky;j++) {
  95       c+=sa[j]+t*y[j]+ui*n[j];
  96       sa[j-1]=c & mask;
  97       c>>=bpe;
  98     }
  99     for (;j<kn;j++) {
 100       c+=sa[j]+ui*n[j];
 101       sa[j-1]=c & mask;
 102       c>>=bpe;
 103     }
 104     sa[j-1]=c & mask;
 105   }
 106
 107   if (!greater(n,sa))
 108     sub_(sa,n);
 109   copy_(x,sa);
 110 }
 111
 112 mont_(x, x, n, np);
 113
 114 var passed = expected.length == x.length;
 115 for (var i = 0; i < expected.length; i++) {
 116   if (passed)
 117     passed = expected[i] == x[i];
 118 }
 119 assertEq(passed, true);