src/v8/src/math.js

   1 // Copyright 2012 the V8 project authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 // This file relies on the fact that the following declarations have been made
   6 // in runtime.js:
   7 // var $Object = global.Object;
   8
   9 // Keep reference to original values of some global properties.  This
  10 // has the added benefit that the code in this file is isolated from
  11 // changes to these properties.
  12 var $floor = MathFloor;
  13 var $abs = MathAbs;
  14
  15 // Instance class name can only be set on functions. That is the only
  16 // purpose for MathConstructor.
  17 function MathConstructor() {}
  18 var $Math = new MathConstructor();
  19
  20 // -------------------------------------------------------------------
  21
  22 // ECMA 262 - 15.8.2.1
  23 function MathAbs(x) {
  24   if (%_IsSmi(x)) return x >= 0 ? x : -x;
  25   x = TO_NUMBER_INLINE(x);
  26   if (x === 0) return 0;  // To handle -0.
  27   return x > 0 ? x : -x;
  28 }
  29
  30 // ECMA 262 - 15.8.2.2
  31 function MathAcos(x) {
  32   return %MathAcos(TO_NUMBER_INLINE(x));
  33 }
  34
  35 // ECMA 262 - 15.8.2.3
  36 function MathAsin(x) {
  37   return %MathAsin(TO_NUMBER_INLINE(x));
  38 }
  39
  40 // ECMA 262 - 15.8.2.4
  41 function MathAtan(x) {
  42   return %MathAtan(TO_NUMBER_INLINE(x));
  43 }
  44
  45 // ECMA 262 - 15.8.2.5
  46 // The naming of y and x matches the spec, as does the order in which
  47 // ToNumber (valueOf) is called.
  48 function MathAtan2(y, x) {
  49   return %MathAtan2(TO_NUMBER_INLINE(y), TO_NUMBER_INLINE(x));
  50 }
  51
  52 // ECMA 262 - 15.8.2.6
  53 function MathCeil(x) {
  54   return -MathFloor(-x);
  55 }
  56
  57 // ECMA 262 - 15.8.2.7
  58 function MathCos(x) {
  59   x = MathAbs(x);  // Convert to number and get rid of -0.
  60   return TrigonometricInterpolation(x, 1);
  61 }
  62
  63 // ECMA 262 - 15.8.2.8
  64 function MathExp(x) {
  65   return %MathExp(TO_NUMBER_INLINE(x));
  66 }
  67
  68 // ECMA 262 - 15.8.2.9
  69 function MathFloor(x) {
  70   x = TO_NUMBER_INLINE(x);
  71   // It's more common to call this with a positive number that's out
  72   // of range than negative numbers; check the upper bound first.
  73   if (x < 0x80000000 && x > 0) {
  74     // Numbers in the range [0, 2^31) can be floored by converting
  75     // them to an unsigned 32-bit value using the shift operator.
  76     // We avoid doing so for -0, because the result of Math.floor(-0)
  77     // has to be -0, which wouldn't be the case with the shift.
  78     return TO_UINT32(x);
  79   } else {
  80     return %MathFloor(x);
  81   }
  82 }
  83
  84 // ECMA 262 - 15.8.2.10
  85 function MathLog(x) {
  86   return %_MathLog(TO_NUMBER_INLINE(x));
  87 }
  88
  89 // ECMA 262 - 15.8.2.11
  90 function MathMax(arg1, arg2) {  // length == 2
  91   var length = %_ArgumentsLength();
  92   if (length == 2) {
  93     arg1 = TO_NUMBER_INLINE(arg1);
  94     arg2 = TO_NUMBER_INLINE(arg2);
  95     if (arg2 > arg1) return arg2;
  96     if (arg1 > arg2) return arg1;
  97     if (arg1 == arg2) {
  98       // Make sure -0 is considered less than +0.
  99       return (arg1 === 0 && %_IsMinusZero(arg1)) ? arg2 : arg1;
 100     }
 101     // All comparisons failed, one of the arguments must be NaN.
 102     return NAN;
 103   }
 104   var r = -INFINITY;
 105   for (var i = 0; i < length; i++) {
 106     var n = %_Arguments(i);
 107     if (!IS_NUMBER(n)) n = NonNumberToNumber(n);
 108     // Make sure +0 is considered greater than -0.
 109     if (NUMBER_IS_NAN(n) || n > r || (r === 0 && n === 0 && %_IsMinusZero(r))) {
 110       r = n;
 111     }
 112   }
 113   return r;
 114 }
 115
 116 // ECMA 262 - 15.8.2.12
 117 function MathMin(arg1, arg2) {  // length == 2
 118   var length = %_ArgumentsLength();
 119   if (length == 2) {
 120     arg1 = TO_NUMBER_INLINE(arg1);
 121     arg2 = TO_NUMBER_INLINE(arg2);
 122     if (arg2 > arg1) return arg1;
 123     if (arg1 > arg2) return arg2;
 124     if (arg1 == arg2) {
 125       // Make sure -0 is considered less than +0.
 126       return (arg1 === 0 && %_IsMinusZero(arg1)) ? arg1 : arg2;
 127     }
 128     // All comparisons failed, one of the arguments must be NaN.
 129     return NAN;
 130   }
 131   var r = INFINITY;
 132   for (var i = 0; i < length; i++) {
 133     var n = %_Arguments(i);
 134     if (!IS_NUMBER(n)) n = NonNumberToNumber(n);
 135     // Make sure -0 is considered less than +0.
 136     if (NUMBER_IS_NAN(n) || n < r || (r === 0 && n === 0 && %_IsMinusZero(n))) {
 137       r = n;
 138     }
 139   }
 140   return r;
 141 }
 142
 143 // ECMA 262 - 15.8.2.13
 144 function MathPow(x, y) {
 145   return %_MathPow(TO_NUMBER_INLINE(x), TO_NUMBER_INLINE(y));
 146 }
 147
 148 // ECMA 262 - 15.8.2.14
 149 var rngstate;  // Initialized to a Uint32Array during genesis.
 150 function MathRandom() {
 151   var r0 = (MathImul(18273, rngstate[0] & 0xFFFF) + (rngstate[0] >>> 16)) | 0;
 152   rngstate[0] = r0;
 153   var r1 = (MathImul(36969, rngstate[1] & 0xFFFF) + (rngstate[1] >>> 16)) | 0;
 154   rngstate[1] = r1;
 155   var x = ((r0 << 16) + (r1 & 0xFFFF)) | 0;
 156   // Division by 0x100000000 through multiplication by reciprocal.
 157   return (x < 0 ? (x + 0x100000000) : x) * 2.3283064365386962890625e-10;
 158 }
 159
 160 // ECMA 262 - 15.8.2.15
 161 function MathRound(x) {
 162   return %RoundNumber(TO_NUMBER_INLINE(x));
 163 }
 164
 165 // ECMA 262 - 15.8.2.16
 166 function MathSin(x) {
 167   x = x * 1;  // Convert to number and deal with -0.
 168   if (%_IsMinusZero(x)) return x;
 169   return TrigonometricInterpolation(x, 0);
 170 }
 171
 172 // ECMA 262 - 15.8.2.17
 173 function MathSqrt(x) {
 174   return %_MathSqrt(TO_NUMBER_INLINE(x));
 175 }
 176
 177 // ECMA 262 - 15.8.2.18
 178 function MathTan(x) {
 179   return MathSin(x) / MathCos(x);
 180 }
 181
 182 // Non-standard extension.
 183 function MathImul(x, y) {
 184   return %NumberImul(TO_NUMBER_INLINE(x), TO_NUMBER_INLINE(y));
 185 }
 186
 187
 188 var kInversePiHalf      = 0.636619772367581343;      // 2 / pi
 189 var kInversePiHalfS26   = 9.48637384723993156e-9;    // 2 / pi / (2^26)
 190 var kS26                = 1 << 26;
 191 var kTwoStepThreshold   = 1 << 27;
 192 // pi / 2 rounded up
 193 var kPiHalf             = 1.570796326794896780;      // 0x192d4454fb21f93f
 194 // We use two parts for pi/2 to emulate a higher precision.
 195 // pi_half_1 only has 26 significant bits for mantissa.
 196 // Note that pi_half > pi_half_1 + pi_half_2
 197 var kPiHalf1            = 1.570796325802803040;      // 0x00000054fb21f93f
 198 var kPiHalf2            = 9.920935796805404252e-10;  // 0x3326a611460b113e
 199
 200 var kSamples;            // Initialized to a number during genesis.
 201 var kIndexConvert;       // Initialized to kSamples / (pi/2) during genesis.
 202 var kSinTable;           // Initialized to a Float64Array during genesis.
 203 var kCosXIntervalTable;  // Initialized to a Float64Array during genesis.
 204
 205 // This implements sine using the following algorithm.
 206 // 1) Multiplication takes care of to-number conversion.
 207 // 2) Reduce x to the first quadrant [0, pi/2].
 208 //    Conveniently enough, in case of +/-Infinity, we get NaN.
 209 //    Note that we try to use only 26 instead of 52 significant bits for
 210 //    mantissa to avoid rounding errors when multiplying.  For very large
 211 //    input we therefore have additional steps.
 212 // 3) Replace x by (pi/2-x) if x was in the 2nd or 4th quadrant.
 213 // 4) Do a table lookup for the closest samples to the left and right of x.
 214 // 5) Find the derivatives at those sampling points by table lookup:
 215 //    dsin(x)/dx = cos(x) = sin(pi/2-x) for x in [0, pi/2].
 216 // 6) Use cubic spline interpolation to approximate sin(x).
 217 // 7) Negate the result if x was in the 3rd or 4th quadrant.
 218 // 8) Get rid of -0 by adding 0.
 219 function TrigonometricInterpolation(x, phase) {
 220   if (x < 0 || x > kPiHalf) {
 221     var multiple;
 222     while (x < -kTwoStepThreshold || x > kTwoStepThreshold) {
 223       // Let's assume this loop does not terminate.
 224       // All numbers x in each loop forms a set S.
 225       // (1) abs(x) > 2^27 for all x in S.
 226       // (2) abs(multiple) != 0 since (2^27 * inverse_pi_half_s26) > 1
 227       // (3) multiple is rounded down in 2^26 steps, so the rounding error is
 228       //     at most max(ulp, 2^26).
 229       // (4) so for x > 2^27, we subtract at most (1+pi/4)x and at least
 230       //     (1-pi/4)x
 231       // (5) The subtraction results in x' so that abs(x') <= abs(x)*pi/4.
 232       //     Note that this difference cannot be simply rounded off.
 233       // Set S cannot exist since (5) violates (1).  Loop must terminate.
 234       multiple = MathFloor(x * kInversePiHalfS26) * kS26;
 235       x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
 236     }
 237     multiple = MathFloor(x * kInversePiHalf);
 238     x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
 239     phase += multiple;
 240   }
 241   var double_index = x * kIndexConvert;
 242   if (phase & 1) double_index = kSamples - double_index;
 243   var index = double_index | 0;
 244   var t1 = double_index - index;
 245   var t2 = 1 - t1;
 246   var y1 = kSinTable[index];
 247   var y2 = kSinTable[index + 1];
 248   var dy = y2 - y1;
 249   return (t2 * y1 + t1 * y2 +
 250               t1 * t2 * ((kCosXIntervalTable[index] - dy) * t2 +
 251                          (dy - kCosXIntervalTable[index + 1]) * t1))
 252          * (1 - (phase & 2)) + 0;
 253 }
 254
 255 // -------------------------------------------------------------------
 256
 257 function SetUpMath() {
 258   %CheckIsBootstrapping();
 259
 260   %SetPrototype($Math, $Object.prototype);
 261   %SetProperty(global, "Math", $Math, DONT_ENUM);
 262   %FunctionSetInstanceClassName(MathConstructor, 'Math');
 263
 264   // Set up math constants.
 265   InstallConstants($Math, $Array(
 266     // ECMA-262, section 15.8.1.1.
 267     "E", 2.7182818284590452354,
 268     // ECMA-262, section 15.8.1.2.
 269     "LN10", 2.302585092994046,
 270     // ECMA-262, section 15.8.1.3.
 271     "LN2", 0.6931471805599453,
 272     // ECMA-262, section 15.8.1.4.
 273     "LOG2E", 1.4426950408889634,
 274     "LOG10E", 0.4342944819032518,
 275     "PI", 3.1415926535897932,
 276     "SQRT1_2", 0.7071067811865476,
 277     "SQRT2", 1.4142135623730951
 278   ));
 279
 280   // Set up non-enumerable functions of the Math object and
 281   // set their names.
 282   InstallFunctions($Math, DONT_ENUM, $Array(
 283     "random", MathRandom,
 284     "abs", MathAbs,
 285     "acos", MathAcos,
 286     "asin", MathAsin,
 287     "atan", MathAtan,
 288     "ceil", MathCeil,
 289     "cos", MathCos,
 290     "exp", MathExp,
 291     "floor", MathFloor,
 292     "log", MathLog,
 293     "round", MathRound,
 294     "sin", MathSin,
 295     "sqrt", MathSqrt,
 296     "tan", MathTan,
 297     "atan2", MathAtan2,
 298     "pow", MathPow,
 299     "max", MathMax,
 300     "min", MathMin,
 301     "imul", MathImul
 302   ));
 303
 304   %SetInlineBuiltinFlag(MathCeil);
 305   %SetInlineBuiltinFlag(MathRandom);
 306   %SetInlineBuiltinFlag(MathSin);
 307   %SetInlineBuiltinFlag(MathCos);
 308   %SetInlineBuiltinFlag(MathTan);
 309   %SetInlineBuiltinFlag(TrigonometricInterpolation);
 310 }
 311
 312 SetUpMath();