[gtk+/wip/otte/tokenizer: 73/78] cssease: Optimize with Newton's method

[Benjamin Otte <otte src gnome org>]

commit 7ca4ef7b0c5ceb50d85a138c8a58c1a1983f6ad1
Author: Benjamin Otte <otte redhat com>
Date:   Mon Apr 4 14:53:46 2016 +0200

    cssease: Optimize with Newton's method
    
    Idea stolen from Webkit's implementation.

 gtk/gtkcsseasevalue.c |   25 +++++++++++++++++++++++++
 1 files changed, 25 insertions(+), 0 deletions(-)
---
diff --git a/gtk/gtkcsseasevalue.c b/gtk/gtkcsseasevalue.c
index 402696f..409ac1a 100644
--- a/gtk/gtkcsseasevalue.c
+++ b/gtk/gtkcsseasevalue.c
@@ -452,6 +452,12 @@ cubic (double a, double b, double c, double t)
   return ((a * t + b) * t + c) * t;
 }
 
+static inline double
+cubic_deriv (double a, double b, double c, double t)
+{
+  return (3 * a * t + 2 * b) * t + c;
+}
+
 double
 _gtk_css_ease_value_transform (const GtkCssValue *ease,
                                double             progress)
@@ -471,6 +477,7 @@ _gtk_css_ease_value_transform (const GtkCssValue *ease,
         double ax, bx, cx;
         double ay, by, cy;
         double tmin, t, tmax;
+        guint i;
 
         cx = 3.0 * ease->u.cubic.x1;
         bx = 3.0 * (ease->u.cubic.x2 - ease->u.cubic.x1) - cx;
@@ -479,6 +486,24 @@ _gtk_css_ease_value_transform (const GtkCssValue *ease,
         by = 3.0 * (ease->u.cubic.y2 - ease->u.cubic.y1) - cy;
         ay = 1.0 - cy - by;
 
+        /* Try with Newton's method first */
+        t = progress;
+        for (i = 0; i < 8; i++)
+          {
+            double sample, deriv;
+
+            sample = cubic (ax, bx, cx, t);
+            if (fabs (sample - t) < epsilon)
+              return cubic (ay, by, cy, t);
+
+            deriv = cubic_deriv (ax, bx, cx, t);
+            if (deriv < epsilon)
+              return cubic (ay, by, cy, t);
+
+            t = t - (sample - t) / deriv;
+          }
+
+        /* Fallback if Newton doesn't converge */
         tmin = 0.0;
         tmax = 1.0;
         t = progress;