Skip to content

Commit 33b5db0

Browse files
author
yangguo@chromium.org
committed
Reland: Embed trigonometric lookup table.
R=danno@chromium.org Review URL: https://codereview.chromium.org/78263005 git-svn-id: https://v8.googlecode.com/svn/branches/bleeding_edge@17988 ce2b1a6d-e550-0410-aec6-3dcde31c8c00
1 parent 59c615f commit 33b5db0

8 files changed

Lines changed: 289 additions & 146 deletions

File tree

src/bootstrapper.cc

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,7 @@
4040
#include "objects-visiting.h"
4141
#include "platform.h"
4242
#include "snapshot.h"
43+
#include "trig-table.h"
4344
#include "extensions/externalize-string-extension.h"
4445
#include "extensions/gc-extension.h"
4546
#include "extensions/statistics-extension.h"
@@ -2635,6 +2636,44 @@ Genesis::Genesis(Isolate* isolate,
26352636
InitializeExperimentalGlobal();
26362637
if (!InstallExperimentalNatives()) return;
26372638

2639+
if (!Serializer::enabled()) {
2640+
Handle<JSBuiltinsObject> builtins(native_context()->builtins());
2641+
// Initialize trigonometric lookup tables and constants.
2642+
// The snapshot cannot contain typed arrays, and we don't need it to.
2643+
const int table_num_bytes = TrigonometricLookupTable::table_num_bytes();
2644+
v8::Local<v8::ArrayBuffer> sin_buffer = v8::ArrayBuffer::New(
2645+
TrigonometricLookupTable::sin_table(), table_num_bytes);
2646+
v8::Local<v8::ArrayBuffer> cos_buffer = v8::ArrayBuffer::New(
2647+
TrigonometricLookupTable::cos_x_interval_table(), table_num_bytes);
2648+
v8::Local<v8::Float64Array> sin_table = v8::Float64Array::New(
2649+
sin_buffer, 0, TrigonometricLookupTable::table_size());
2650+
v8::Local<v8::Float64Array> cos_table = v8::Float64Array::New(
2651+
cos_buffer, 0, TrigonometricLookupTable::table_size());
2652+
2653+
ForceSetProperty(builtins,
2654+
factory()->InternalizeOneByteString(
2655+
STATIC_ASCII_VECTOR("kSinTable")),
2656+
Utils::OpenHandle(*sin_table),
2657+
NONE);
2658+
ForceSetProperty(builtins,
2659+
factory()->InternalizeOneByteString(
2660+
STATIC_ASCII_VECTOR("kCosXIntervalTable")),
2661+
Utils::OpenHandle(*cos_table),
2662+
NONE);
2663+
ForceSetProperty(builtins,
2664+
factory()->InternalizeOneByteString(
2665+
STATIC_ASCII_VECTOR("kSamples")),
2666+
factory()->NewHeapNumber(
2667+
TrigonometricLookupTable::samples()),
2668+
NONE);
2669+
ForceSetProperty(builtins,
2670+
factory()->InternalizeOneByteString(
2671+
STATIC_ASCII_VECTOR("kIndexConvert")),
2672+
factory()->NewHeapNumber(
2673+
TrigonometricLookupTable::samples_over_pi_half()),
2674+
NONE);
2675+
}
2676+
26382677
// Initially seed the per-context random number generator
26392678
// using the per-isolate random number generator.
26402679
uint32_t* state = reinterpret_cast<uint32_t*>(

src/math.js

Lines changed: 70 additions & 112 deletions
Original file line numberDiff line numberDiff line change
@@ -79,7 +79,8 @@ function MathCeil(x) {
7979

8080
// ECMA 262 - 15.8.2.7
8181
function MathCos(x) {
82-
return MathCosImpl(x);
82+
x = MathAbs(x); // Convert to number and get rid of -0.
83+
return TrigonometricInterpolation(x, 1);
8384
}
8485

8586
// ECMA 262 - 15.8.2.8
@@ -179,7 +180,9 @@ function MathRound(x) {
179180

180181
// ECMA 262 - 15.8.2.16
181182
function MathSin(x) {
182-
return MathSinImpl(x);
183+
x = x * 1; // Convert to number and deal with -0.
184+
if (%_IsMinusZero(x)) return x;
185+
return TrigonometricInterpolation(x, 0);
183186
}
184187

185188
// ECMA 262 - 15.8.2.17
@@ -189,7 +192,7 @@ function MathSqrt(x) {
189192

190193
// ECMA 262 - 15.8.2.18
191194
function MathTan(x) {
192-
return MathSinImpl(x) / MathCosImpl(x);
195+
return MathSin(x) / MathCos(x);
193196
}
194197

195198
// Non-standard extension.
@@ -198,119 +201,73 @@ function MathImul(x, y) {
198201
}
199202

200203

201-
var MathSinImpl = function(x) {
202-
InitTrigonometricFunctions();
203-
return MathSinImpl(x);
204-
}
205-
206-
207-
var MathCosImpl = function(x) {
208-
InitTrigonometricFunctions();
209-
return MathCosImpl(x);
210-
}
211-
212-
213-
var InitTrigonometricFunctions;
214-
215-
216-
// Define constants and interpolation functions.
217-
// Also define the initialization function that populates the lookup table
218-
// and then wires up the function definitions.
219-
function SetupTrigonometricFunctions() {
220-
var samples = 1800; // Table size. Do not change arbitrarily.
221-
var inverse_pi_half = 0.636619772367581343; // 2 / pi
222-
var inverse_pi_half_s_26 = 9.48637384723993156e-9; // 2 / pi / (2^26)
223-
var s_26 = 1 << 26;
224-
var two_step_threshold = 1 << 27;
225-
var index_convert = 1145.915590261646418; // samples / (pi / 2)
226-
// pi / 2 rounded up
227-
var pi_half = 1.570796326794896780; // 0x192d4454fb21f93f
228-
// We use two parts for pi/2 to emulate a higher precision.
229-
// pi_half_1 only has 26 significant bits for mantissa.
230-
// Note that pi_half > pi_half_1 + pi_half_2
231-
var pi_half_1 = 1.570796325802803040; // 0x00000054fb21f93f
232-
var pi_half_2 = 9.920935796805404252e-10; // 0x3326a611460b113e
233-
var table_sin;
234-
var table_cos_interval;
235-
236-
// This implements sine using the following algorithm.
237-
// 1) Multiplication takes care of to-number conversion.
238-
// 2) Reduce x to the first quadrant [0, pi/2].
239-
// Conveniently enough, in case of +/-Infinity, we get NaN.
240-
// Note that we try to use only 26 instead of 52 significant bits for
241-
// mantissa to avoid rounding errors when multiplying. For very large
242-
// input we therefore have additional steps.
243-
// 3) Replace x by (pi/2-x) if x was in the 2nd or 4th quadrant.
244-
// 4) Do a table lookup for the closest samples to the left and right of x.
245-
// 5) Find the derivatives at those sampling points by table lookup:
246-
// dsin(x)/dx = cos(x) = sin(pi/2-x) for x in [0, pi/2].
247-
// 6) Use cubic spline interpolation to approximate sin(x).
248-
// 7) Negate the result if x was in the 3rd or 4th quadrant.
249-
// 8) Get rid of -0 by adding 0.
250-
var Interpolation = function(x, phase) {
251-
if (x < 0 || x > pi_half) {
252-
var multiple;
253-
while (x < -two_step_threshold || x > two_step_threshold) {
254-
// Let's assume this loop does not terminate.
255-
// All numbers x in each loop forms a set S.
256-
// (1) abs(x) > 2^27 for all x in S.
257-
// (2) abs(multiple) != 0 since (2^27 * inverse_pi_half_s26) > 1
258-
// (3) multiple is rounded down in 2^26 steps, so the rounding error is
259-
// at most max(ulp, 2^26).
260-
// (4) so for x > 2^27, we subtract at most (1+pi/4)x and at least
261-
// (1-pi/4)x
262-
// (5) The subtraction results in x' so that abs(x') <= abs(x)*pi/4.
263-
// Note that this difference cannot be simply rounded off.
264-
// Set S cannot exist since (5) violates (1). Loop must terminate.
265-
multiple = MathFloor(x * inverse_pi_half_s_26) * s_26;
266-
x = x - multiple * pi_half_1 - multiple * pi_half_2;
267-
}
268-
multiple = MathFloor(x * inverse_pi_half);
269-
x = x - multiple * pi_half_1 - multiple * pi_half_2;
270-
phase += multiple;
204+
var kInversePiHalf = 0.636619772367581343; // 2 / pi
205+
var kInversePiHalfS26 = 9.48637384723993156e-9; // 2 / pi / (2^26)
206+
var kS26 = 1 << 26;
207+
var kTwoStepThreshold = 1 << 27;
208+
// pi / 2 rounded up
209+
var kPiHalf = 1.570796326794896780; // 0x192d4454fb21f93f
210+
// We use two parts for pi/2 to emulate a higher precision.
211+
// pi_half_1 only has 26 significant bits for mantissa.
212+
// Note that pi_half > pi_half_1 + pi_half_2
213+
var kPiHalf1 = 1.570796325802803040; // 0x00000054fb21f93f
214+
var kPiHalf2 = 9.920935796805404252e-10; // 0x3326a611460b113e
215+
216+
var kSamples; // Initialized to a number during genesis.
217+
var kIndexConvert; // Initialized to kSamples / (pi/2) during genesis.
218+
var kSinTable; // Initialized to a Float64Array during genesis.
219+
var kCosXIntervalTable; // Initialized to a Float64Array during genesis.
220+
221+
// This implements sine using the following algorithm.
222+
// 1) Multiplication takes care of to-number conversion.
223+
// 2) Reduce x to the first quadrant [0, pi/2].
224+
// Conveniently enough, in case of +/-Infinity, we get NaN.
225+
// Note that we try to use only 26 instead of 52 significant bits for
226+
// mantissa to avoid rounding errors when multiplying. For very large
227+
// input we therefore have additional steps.
228+
// 3) Replace x by (pi/2-x) if x was in the 2nd or 4th quadrant.
229+
// 4) Do a table lookup for the closest samples to the left and right of x.
230+
// 5) Find the derivatives at those sampling points by table lookup:
231+
// dsin(x)/dx = cos(x) = sin(pi/2-x) for x in [0, pi/2].
232+
// 6) Use cubic spline interpolation to approximate sin(x).
233+
// 7) Negate the result if x was in the 3rd or 4th quadrant.
234+
// 8) Get rid of -0 by adding 0.
235+
function TrigonometricInterpolation(x, phase) {
236+
if (x < 0 || x > kPiHalf) {
237+
var multiple;
238+
while (x < -kTwoStepThreshold || x > kTwoStepThreshold) {
239+
// Let's assume this loop does not terminate.
240+
// All numbers x in each loop forms a set S.
241+
// (1) abs(x) > 2^27 for all x in S.
242+
// (2) abs(multiple) != 0 since (2^27 * inverse_pi_half_s26) > 1
243+
// (3) multiple is rounded down in 2^26 steps, so the rounding error is
244+
// at most max(ulp, 2^26).
245+
// (4) so for x > 2^27, we subtract at most (1+pi/4)x and at least
246+
// (1-pi/4)x
247+
// (5) The subtraction results in x' so that abs(x') <= abs(x)*pi/4.
248+
// Note that this difference cannot be simply rounded off.
249+
// Set S cannot exist since (5) violates (1). Loop must terminate.
250+
multiple = MathFloor(x * kInversePiHalfS26) * kS26;
251+
x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
271252
}
272-
var double_index = x * index_convert;
273-
if (phase & 1) double_index = samples - double_index;
274-
var index = double_index | 0;
275-
var t1 = double_index - index;
276-
var t2 = 1 - t1;
277-
var y1 = table_sin[index];
278-
var y2 = table_sin[index + 1];
279-
var dy = y2 - y1;
280-
return (t2 * y1 + t1 * y2 +
281-
t1 * t2 * ((table_cos_interval[index] - dy) * t2 +
282-
(dy - table_cos_interval[index + 1]) * t1))
283-
* (1 - (phase & 2)) + 0;
284-
}
285-
286-
var MathSinInterpolation = function(x) {
287-
x = x * 1; // Convert to number and deal with -0.
288-
if (%_IsMinusZero(x)) return x;
289-
return Interpolation(x, 0);
290-
}
291-
292-
// Cosine is sine with a phase offset.
293-
var MathCosInterpolation = function(x) {
294-
x = MathAbs(x); // Convert to number and get rid of -0.
295-
return Interpolation(x, 1);
296-
};
297-
298-
%SetInlineBuiltinFlag(Interpolation);
299-
%SetInlineBuiltinFlag(MathSinInterpolation);
300-
%SetInlineBuiltinFlag(MathCosInterpolation);
301-
302-
InitTrigonometricFunctions = function() {
303-
table_sin = new global.Float64Array(samples + 2);
304-
table_cos_interval = new global.Float64Array(samples + 2);
305-
%PopulateTrigonometricTable(table_sin, table_cos_interval, samples);
306-
MathSinImpl = MathSinInterpolation;
307-
MathCosImpl = MathCosInterpolation;
253+
multiple = MathFloor(x * kInversePiHalf);
254+
x = x - multiple * kPiHalf1 - multiple * kPiHalf2;
255+
phase += multiple;
308256
}
257+
var double_index = x * kIndexConvert;
258+
if (phase & 1) double_index = kSamples - double_index;
259+
var index = double_index | 0;
260+
var t1 = double_index - index;
261+
var t2 = 1 - t1;
262+
var y1 = kSinTable[index];
263+
var y2 = kSinTable[index + 1];
264+
var dy = y2 - y1;
265+
return (t2 * y1 + t1 * y2 +
266+
t1 * t2 * ((kCosXIntervalTable[index] - dy) * t2 +
267+
(dy - kCosXIntervalTable[index + 1]) * t1))
268+
* (1 - (phase & 2)) + 0;
309269
}
310270

311-
SetupTrigonometricFunctions();
312-
313-
314271
// -------------------------------------------------------------------
315272

316273
function SetUpMath() {
@@ -387,6 +344,7 @@ function SetUpMath() {
387344
%SetInlineBuiltinFlag(MathSin);
388345
%SetInlineBuiltinFlag(MathCos);
389346
%SetInlineBuiltinFlag(MathTan);
347+
%SetInlineBuiltinFlag(TrigonometricInterpolation);
390348
}
391349

392350
SetUpMath();

src/runtime.cc

Lines changed: 0 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -7848,35 +7848,6 @@ RUNTIME_FUNCTION(MaybeObject*, Runtime_Math_tan) {
78487848
}
78497849

78507850

7851-
RUNTIME_FUNCTION(MaybeObject*, Runtime_PopulateTrigonometricTable) {
7852-
HandleScope scope(isolate);
7853-
ASSERT(args.length() == 3);
7854-
CONVERT_ARG_HANDLE_CHECKED(JSTypedArray, sin_table, 0);
7855-
CONVERT_ARG_HANDLE_CHECKED(JSTypedArray, cos_table, 1);
7856-
CONVERT_SMI_ARG_CHECKED(samples, 2);
7857-
RUNTIME_ASSERT(sin_table->type() == kExternalDoubleArray);
7858-
RUNTIME_ASSERT(cos_table->type() == kExternalDoubleArray);
7859-
double* sin_buffer = reinterpret_cast<double*>(
7860-
JSArrayBuffer::cast(sin_table->buffer())->backing_store());
7861-
double* cos_buffer = reinterpret_cast<double*>(
7862-
JSArrayBuffer::cast(cos_table->buffer())->backing_store());
7863-
7864-
static const double pi_half = 3.1415926535897932 / 2;
7865-
double interval = pi_half / samples;
7866-
for (int i = 0; i < samples + 1; i++) {
7867-
double sample = sin(i * interval);
7868-
sin_buffer[i] = sample;
7869-
cos_buffer[samples - i] = sample * interval;
7870-
}
7871-
7872-
// Fill this to catch out of bound accesses when calculating Math.sin(pi/2).
7873-
sin_buffer[samples + 1] = sin(pi_half + interval);
7874-
cos_buffer[samples + 1] = cos(pi_half + interval) * interval;
7875-
7876-
return isolate->heap()->undefined_value();
7877-
}
7878-
7879-
78807851
RUNTIME_FUNCTION(MaybeObject*, Runtime_DateMakeDay) {
78817852
SealHandleScope shs(isolate);
78827853
ASSERT(args.length() == 2);

src/runtime.h

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -190,7 +190,6 @@ namespace internal {
190190
F(Math_sin, 1, 1) \
191191
F(Math_sqrt, 1, 1) \
192192
F(Math_tan, 1, 1) \
193-
F(PopulateTrigonometricTable, 3, 1) \
194193
\
195194
/* Regular expressions */ \
196195
F(RegExpCompile, 3, 1) \

src/trig-table.h

Lines changed: 61 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,61 @@
1+
// Copyright 2013 the V8 project authors. All rights reserved.
2+
// Redistribution and use in source and binary forms, with or without
3+
// modification, are permitted provided that the following conditions are
4+
// met:
5+
//
6+
// * Redistributions of source code must retain the above copyright
7+
// notice, this list of conditions and the following disclaimer.
8+
// * Redistributions in binary form must reproduce the above
9+
// copyright notice, this list of conditions and the following
10+
// disclaimer in the documentation and/or other materials provided
11+
// with the distribution.
12+
// * Neither the name of Google Inc. nor the names of its
13+
// contributors may be used to endorse or promote products derived
14+
// from this software without specific prior written permission.
15+
//
16+
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17+
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18+
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19+
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20+
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21+
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22+
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23+
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24+
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25+
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26+
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27+
28+
#ifndef V8_TRIG_TABLE_H_
29+
#define V8_TRIG_TABLE_H_
30+
31+
32+
namespace v8 {
33+
namespace internal {
34+
35+
class TrigonometricLookupTable : public AllStatic {
36+
public:
37+
// Casting away const-ness to use as argument for typed array constructor.
38+
static void* sin_table() {
39+
return const_cast<double*>(&kSinTable[0]);
40+
}
41+
42+
static void* cos_x_interval_table() {
43+
return const_cast<double*>(&kCosXIntervalTable[0]);
44+
}
45+
46+
static double samples_over_pi_half() { return kSamplesOverPiHalf; }
47+
static int samples() { return kSamples; }
48+
static int table_num_bytes() { return kTableSize * sizeof(*kSinTable); }
49+
static int table_size() { return kTableSize; }
50+
51+
private:
52+
static const double kSinTable[];
53+
static const double kCosXIntervalTable[];
54+
static const int kSamples;
55+
static const int kTableSize;
56+
static const double kSamplesOverPiHalf;
57+
};
58+
59+
} } // namespace v8::internal
60+
61+
#endif // V8_TRIG_TABLE_H_

0 commit comments

Comments
 (0)