• file
• revisions
• annotate
• diff
• comparison
• raw

dom/smil/nsSMILKeySpline.cpp@97036ab72558 (annotated)

dom/smil/nsSMILKeySpline.cpp

Tue, 06 Jan 2015 21:39:09 +0100

author

Michael Schloh von Bennewitz <michael@schloh.com>

date

Tue, 06 Jan 2015 21:39:09 +0100

branch

TOR_BUG_9701

changeset 8

97036ab72558

permissions

-rw-r--r--

Conditionally force memory storage according to privacy.thirdparty.isolate;
This solves Tor bug #9701, complying with disk avoidance documented in
https://www.torproject.org/projects/torbrowser/design/#disk-avoidance.

michael@0	1	/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0	2	/* This Source Code Form is subject to the terms of the Mozilla Public
michael@0	3	* License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0	4	* file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0	5
michael@0	6	#include "nsSMILKeySpline.h"
michael@0	7	#include <stdint.h>
michael@0	8	#include <math.h>
michael@0	9
michael@0	10	#define NEWTON_ITERATIONS 4
michael@0	11	#define NEWTON_MIN_SLOPE 0.02
michael@0	12	#define SUBDIVISION_PRECISION 0.0000001
michael@0	13	#define SUBDIVISION_MAX_ITERATIONS 10
michael@0	14
michael@0	15	const double nsSMILKeySpline::kSampleStepSize =
michael@0	16	1.0 / double(kSplineTableSize - 1);
michael@0	17
michael@0	18	void
michael@0	19	nsSMILKeySpline::Init(double aX1,
michael@0	20	double aY1,
michael@0	21	double aX2,
michael@0	22	double aY2)
michael@0	23	{
michael@0	24	mX1 = aX1;
michael@0	25	mY1 = aY1;
michael@0	26	mX2 = aX2;
michael@0	27	mY2 = aY2;
michael@0	28
michael@0	29	if (mX1 != mY1 || mX2 != mY2)
michael@0	30	CalcSampleValues();
michael@0	31	}
michael@0	32
michael@0	33	double
michael@0	34	nsSMILKeySpline::GetSplineValue(double aX) const
michael@0	35	{
michael@0	36	if (mX1 == mY1 && mX2 == mY2)
michael@0	37	return aX;
michael@0	38
michael@0	39	return CalcBezier(GetTForX(aX), mY1, mY2);
michael@0	40	}
michael@0	41
michael@0	42	void
michael@0	43	nsSMILKeySpline::GetSplineDerivativeValues(double aX, double& aDX, double& aDY) const
michael@0	44	{
michael@0	45	double t = GetTForX(aX);
michael@0	46	aDX = GetSlope(t, mX1, mX2);
michael@0	47	aDY = GetSlope(t, mY1, mY2);
michael@0	48	}
michael@0	49
michael@0	50	void
michael@0	51	nsSMILKeySpline::CalcSampleValues()
michael@0	52	{
michael@0	53	for (uint32_t i = 0; i < kSplineTableSize; ++i) {
michael@0	54	mSampleValues[i] = CalcBezier(double(i) * kSampleStepSize, mX1, mX2);
michael@0	55	}
michael@0	56	}
michael@0	57
michael@0	58	/*static*/ double
michael@0	59	nsSMILKeySpline::CalcBezier(double aT,
michael@0	60	double aA1,
michael@0	61	double aA2)
michael@0	62	{
michael@0	63	// use Horner's scheme to evaluate the Bezier polynomial
michael@0	64	return ((A(aA1, aA2)*aT + B(aA1, aA2))*aT + C(aA1))*aT;
michael@0	65	}
michael@0	66
michael@0	67	/*static*/ double
michael@0	68	nsSMILKeySpline::GetSlope(double aT,
michael@0	69	double aA1,
michael@0	70	double aA2)
michael@0	71	{
michael@0	72	return 3.0 * A(aA1, aA2)*aT*aT + 2.0 * B(aA1, aA2) * aT + C(aA1);
michael@0	73	}
michael@0	74
michael@0	75	double
michael@0	76	nsSMILKeySpline::GetTForX(double aX) const
michael@0	77	{
michael@0	78	// Find interval where t lies
michael@0	79	double intervalStart = 0.0;
michael@0	80	const double* currentSample = &mSampleValues[1];
michael@0	81	const double* const lastSample = &mSampleValues[kSplineTableSize - 1];
michael@0	82	for (; currentSample != lastSample && *currentSample <= aX;
michael@0	83	++currentSample) {
michael@0	84	intervalStart += kSampleStepSize;
michael@0	85	}
michael@0	86	--currentSample; // t now lies between *currentSample and *currentSample+1
michael@0	87
michael@0	88	// Interpolate to provide an initial guess for t
michael@0	89	double dist = (aX - *currentSample) /
michael@0	90	(*(currentSample+1) - *currentSample);
michael@0	91	double guessForT = intervalStart + dist * kSampleStepSize;
michael@0	92
michael@0	93	// Check the slope to see what strategy to use. If the slope is too small
michael@0	94	// Newton-Raphson iteration won't converge on a root so we use bisection
michael@0	95	// instead.
michael@0	96	double initialSlope = GetSlope(guessForT, mX1, mX2);
michael@0	97	if (initialSlope >= NEWTON_MIN_SLOPE) {
michael@0	98	return NewtonRaphsonIterate(aX, guessForT);
michael@0	99	} else if (initialSlope == 0.0) {
michael@0	100	return guessForT;
michael@0	101	} else {
michael@0	102	return BinarySubdivide(aX, intervalStart, intervalStart + kSampleStepSize);
michael@0	103	}
michael@0	104	}
michael@0	105
michael@0	106	double
michael@0	107	nsSMILKeySpline::NewtonRaphsonIterate(double aX, double aGuessT) const
michael@0	108	{
michael@0	109	// Refine guess with Newton-Raphson iteration
michael@0	110	for (uint32_t i = 0; i < NEWTON_ITERATIONS; ++i) {
michael@0	111	// We're trying to find where f(t) = aX,
michael@0	112	// so we're actually looking for a root for: CalcBezier(t) - aX
michael@0	113	double currentX = CalcBezier(aGuessT, mX1, mX2) - aX;
michael@0	114	double currentSlope = GetSlope(aGuessT, mX1, mX2);
michael@0	115
michael@0	116	if (currentSlope == 0.0)
michael@0	117	return aGuessT;
michael@0	118
michael@0	119	aGuessT -= currentX / currentSlope;
michael@0	120	}
michael@0	121
michael@0	122	return aGuessT;
michael@0	123	}
michael@0	124
michael@0	125	double
michael@0	126	nsSMILKeySpline::BinarySubdivide(double aX, double aA, double aB) const
michael@0	127	{
michael@0	128	double currentX;
michael@0	129	double currentT;
michael@0	130	uint32_t i = 0;
michael@0	131
michael@0	132	do
michael@0	133	{
michael@0	134	currentT = aA + (aB - aA) / 2.0;
michael@0	135	currentX = CalcBezier(currentT, mX1, mX2) - aX;
michael@0	136
michael@0	137	if (currentX > 0.0) {
michael@0	138	aB = currentT;
michael@0	139	} else {
michael@0	140	aA = currentT;
michael@0	141	}
michael@0	142	} while (fabs(currentX) > SUBDIVISION_PRECISION
michael@0	143	&& ++i < SUBDIVISION_MAX_ITERATIONS);
michael@0	144
michael@0	145	return currentT;
michael@0	146	}