Roll skia/third_party/skcms 73399c8..cca4d5d (1 commits)

https://skia.googlesource.com/skcms.git/+log/73399c8..cca4d5d

2018-04-24 mtklein@chromium.org polytf


The AutoRoll server is located here: https://skcms-skia-roll.skia.org

Documentation for the AutoRoller is here:
https://skia.googlesource.com/buildbot/+/master/autoroll/README.md

If the roll is causing failures, please contact the current sheriff, who should
be CC'd on the roll, and stop the roller if necessary.



TBR=stani@google.com

Change-Id: I4611cabb3a2ee8fb13f42c2b35f6fbbb71ad1539
Reviewed-on: https://skia-review.googlesource.com/123527
Reviewed-by: skcms-skia-autoroll <skcms-skia-autoroll@skia-buildbots.google.com.iam.gserviceaccount.com>
Commit-Queue: skcms-skia-autoroll <skcms-skia-autoroll@skia-buildbots.google.com.iam.gserviceaccount.com>

10 files changed, 190 insertions, 19 deletions

diff --git a/third_party/skcms/skcms.c b/third_party/skcms/skcms.c
index 0fe2c7d1a0..0cf621ecc2 100644
--- a/third_party/skcms/skcms.c
+++ b/third_party/skcms/skcms.c
@@ -10,6 +10,7 @@
 #include "src/GaussNewton.c"
 #include "src/ICCProfile.c"
 #include "src/LinearAlgebra.c"
+#include "src/PolyTF.c"
 #include "src/PortableMath.c"
 #include "src/TransferFunction.c"
 #include "src/Transform.c"
diff --git a/third_party/skcms/skcms.h b/third_party/skcms/skcms.h
index 108eb58863..32c30cbe7d 100644
--- a/third_party/skcms/skcms.h
+++ b/third_party/skcms/skcms.h
@@ -38,6 +38,11 @@ typedef struct skcms_TransferFunction {
     float g, a,b,c,d,e,f;
 } skcms_TransferFunction;
 
+// A transfer function that's cheaper to evaluate than skcms_TransferFunction.
+typedef struct skcms_PolyTF {
+    float A,B,C,D;
+} skcms_PolyTF;
+
 // Unified representation of 'curv' or 'para' tag data, or a 1D table from 'mft1' or 'mft2'
 typedef union skcms_Curve {
     struct {
@@ -97,6 +102,10 @@ typedef struct skcms_ICCProfile {
     // and has_A2B to true.
     bool                   has_A2B;
     skcms_A2B              A2B;
+
+    // If the profile has_trc, we may be able to approximate those curves with skcms_PolyTF.
+    bool     has_poly_tf[3];
+    skcms_PolyTF poly_tf[3];
 } skcms_ICCProfile;
 
 // The sRGB color profile is so commonly used that we offer a canonical skcms_ICCProfile for it.
diff --git a/third_party/skcms/src/ICCProfile.c b/third_party/skcms/src/ICCProfile.c
index 88b419d931..8e4acc7017 100644
--- a/third_party/skcms/src/ICCProfile.c
+++ b/third_party/skcms/src/ICCProfile.c
@@ -611,10 +611,10 @@ static bool read_a2b(const skcms_ICCTag* tag, skcms_A2B* a2b, bool pcs_is_xyz) {
         if (curve && curve->table_entries && curve->table_entries <= (uint32_t)INT_MAX) {
             int N = (int)curve->table_entries;
 
-            skcms_TransferFunction tf;
-            if (N == skcms_fit_linear(curve, N, 1.0f/(2*N), &tf)
-                && tf.c == 1.0f
-                && tf.f == 0.0f) {
+            float c,d,f;
+            if (N == skcms_fit_linear(curve, N, 1.0f/(2*N), &c,&d,&f)
+                && c == 1.0f
+                && f == 0.0f) {
                 curve->table_entries = 0;
                 curve->table_8       = NULL;
                 curve->table_16      = NULL;
@@ -781,11 +781,6 @@ bool skcms_Parse(const void* buf, size_t len, skcms_ICCProfile* profile) {
     return usable_as_src(profile);
 }
 
-void skcms_OptimizeForSpeed(skcms_ICCProfile* profile) {
-    (void)profile;
-    // TODO
-}
-
 const skcms_ICCProfile skcms_sRGB_profile = {
     // These fields are moot when not a skcms_Parse()'d profile.
     .buffer    = NULL,
diff --git a/third_party/skcms/src/PolyTF.c b/third_party/skcms/src/PolyTF.c
new file mode 100644
index 0000000000..451a4272b7
--- /dev/null
+++ b/third_party/skcms/src/PolyTF.c
@@ -0,0 +1,144 @@
+/*
+ * Copyright 2018 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "../skcms.h"
+#include "GaussNewton.h"
+#include "Macros.h"
+#include "PortableMath.h"
+#include "TransferFunction.h"
+#include <limits.h>
+#include <stdlib.h>
+
+// f(x) = skcms_PolyTF{A,B,C,D}(x) =
+//     Cx                     x < D
+//     Ax^3 + Bx^2 + (1-A-B)  x ≥ D
+//
+// We'll fit C and D directly, and then hold them constant
+// and fit the other part using Gauss-Newton, subject to
+// the constraint that both parts meet at x=D:
+//
+//     CD = AD^3 + BD^2 + (1-A-B)
+//
+// This lets us solve for B, reducing the optimization problem
+// for that part down to just a single parameter A:
+//
+//     CD = A(D^3-1) + B(D^2-1) + 1
+//
+//         CD - A(D^3-1) - 1
+//     B = -----------------
+//               D^2-1
+//
+//                    x^2-1
+//  f(x) = A(x^3-1) + ----- [CD - A(D^3-1) - 1] + 1
+//                    D^2-1
+//
+//                  (x^2-1) (D^3-1)
+//  ∂f/∂A = x^3-1 - ---------------
+//                       D^2-1
+
+static float eval_poly_tf(float x, const void* ctx, const float P[4]) {
+    const skcms_PolyTF* tf = (const skcms_PolyTF*)ctx;
+
+    float A = P[0],
+          C = tf->C,
+          D = tf->D;
+    float B = (C*D - A*(D*D*D - 1) - 1) / (D*D - 1);
+
+    return x < D ? C*x
+                 : A*x*x*x + B*x*x + (1-A-B);
+}
+
+static void grad_poly_tf(float x, const void* ctx, const float P[4], float dfdP[4]) {
+    const skcms_PolyTF* tf = (const skcms_PolyTF*)ctx;
+    (void)P;
+    float D = tf->D;
+
+    dfdP[0] = (x*x*x - 1) - (x*x-1)*(D*D*D-1)/(D*D-1);
+}
+
+static bool fit_poly_tf(const skcms_Curve* curve, skcms_PolyTF* tf) {
+    if (curve->table_entries > (uint32_t)INT_MAX) {
+        return false;
+    }
+
+    const int N = curve->table_entries == 0 ? 256
+                                            :(int)curve->table_entries;
+
+    // We'll test the quality of our fit by roundtripping through a skcms_TransferFunction,
+    // either the inverse of the curve itself if it is parametric, or of its approximation if not.
+    skcms_TransferFunction baseline;
+    float err;
+    if (curve->table_entries == 0) {
+        baseline = curve->parametric;
+    } else if (!skcms_ApproximateCurve(curve, &baseline, &err)) {
+        return false;
+    }
+    skcms_TransferFunction inv;
+    if (!skcms_TransferFunction_invert(&baseline, &inv)) {
+        return false;
+    }
+
+    const float kTolerances[] = { 1.5f / 65535.0f, 1.0f / 512.0f };
+    for (int t = 0; t < ARRAY_COUNT(kTolerances); t++) {
+        float f;
+        const int L = skcms_fit_linear(curve, N, kTolerances[t], &tf->C, &tf->D, &f);
+        if (f != 0) {
+            return false;
+        }
+
+        if (tf->D == 1) {
+            tf->A = 0;
+            tf->B = 0;
+            return true;
+        }
+
+        // Start with guess A = 0, i.e. f(x) = x^2, gamma = 2.
+        float P[4] = {0, 0,0,0};
+
+        for (int i = 0; i < 3; i++) {
+            if (!skcms_gauss_newton_step(skcms_eval_curve, curve,
+                                         eval_poly_tf, tf,
+                                         grad_poly_tf, tf,
+                                         P,
+                                         tf->D, 1, N-L)) {
+                goto NEXT;
+            }
+        }
+
+        float A = tf->A = P[0],
+              C = tf->C,
+              D = tf->D;
+        tf->B = (C*D - A*(D*D*D - 1) - 1) / (D*D - 1);
+
+        for (int i = 0; i < N; i++) {
+            float x = i * (1.0f/(N-1));
+
+            float rt = skcms_TransferFunction_eval(&inv, eval_poly_tf(x, tf, P));
+            if (!isfinitef_(rt)) {
+                goto NEXT;
+            }
+
+            const int tol = (i == 0 || i == N-1) ? 0
+                                                 : N/256;
+            int ix = (int)((N-1) * rt + 0.5f);
+            if (abs(i - ix) > tol) {
+                goto NEXT;
+            }
+        }
+        return true;
+
+    NEXT: ;
+    }
+
+    return false;
+}
+
+void skcms_OptimizeForSpeed(skcms_ICCProfile* profile) {
+    for (int i = 0; profile->has_trc && i < 3; i++) {
+        profile->has_poly_tf[i] = fit_poly_tf(&profile->trc[i], &profile->poly_tf[i]);
+    }
+}
diff --git a/third_party/skcms/src/TransferFunction.c b/third_party/skcms/src/TransferFunction.c
index d5ecfdfe08..345b9aa3cb 100644
--- a/third_party/skcms/src/TransferFunction.c
+++ b/third_party/skcms/src/TransferFunction.c
@@ -161,7 +161,7 @@ static void grad_nonlinear(float x, const void* ctx, const float P[4], float dfd
             -   g*powf_(D, g-1);
 }
 
-int skcms_fit_linear(const skcms_Curve* curve, int N, float tol, skcms_TransferFunction* tf) {
+int skcms_fit_linear(const skcms_Curve* curve, int N, float tol, float* c, float* d, float* f) {
     assert(N > 1);
     // We iteratively fit the first points to the TF's linear piece.
     // We want the cx + f line to pass through the first and last points we fit exactly.
@@ -176,7 +176,7 @@ int skcms_fit_linear(const skcms_Curve* curve, int N, float tol, skcms_TransferF
     const float x_scale = 1.0f / (N - 1);
 
     int lin_points = 1;
-    tf->f = skcms_eval_curve(0, curve);
+    *f = skcms_eval_curve(0, curve);
 
     float slope_min = -INFINITY_;
     float slope_max = +INFINITY_;
@@ -184,8 +184,8 @@ int skcms_fit_linear(const skcms_Curve* curve, int N, float tol, skcms_TransferF
         float x = i * x_scale;
         float y = skcms_eval_curve(x, curve);
 
-        float slope_max_i = (y + tol - tf->f) / x,
-              slope_min_i = (y - tol - tf->f) / x;
+        float slope_max_i = (y + tol - *f) / x,
+              slope_min_i = (y - tol - *f) / x;
         if (slope_max_i < slope_min || slope_max < slope_min_i) {
             // Slope intervals would no longer overlap.
             break;
@@ -193,15 +193,15 @@ int skcms_fit_linear(const skcms_Curve* curve, int N, float tol, skcms_TransferF
         slope_max = fminf_(slope_max, slope_max_i);
         slope_min = fmaxf_(slope_min, slope_min_i);
 
-        float cur_slope = (y - tf->f) / x;
+        float cur_slope = (y - *f) / x;
         if (slope_min <= cur_slope && cur_slope <= slope_max) {
             lin_points = i + 1;
-            tf->c = cur_slope;
+            *c = cur_slope;
         }
     }
 
     // Set D to the last point that met our tolerance.
-    tf->d = (lin_points - 1) * x_scale;
+    *d = (lin_points - 1) * x_scale;
     return lin_points;
 }
 
@@ -267,7 +267,7 @@ bool skcms_ApproximateCurve(const skcms_Curve* curve,
     const float kTolerances[] = { 1.5f / 65535.0f, 1.0f / 512.0f };
     for (int t = 0; t < ARRAY_COUNT(kTolerances); t++) {
         skcms_TransferFunction tf;
-        int L = skcms_fit_linear(curve, N, kTolerances[t], &tf);
+        int L = skcms_fit_linear(curve, N, kTolerances[t], &tf.c, &tf.d, &tf.f);
 
         if (L == N) {
             // If the entire data set was linear, move the coefficients to the nonlinear portion
diff --git a/third_party/skcms/src/TransferFunction.h b/third_party/skcms/src/TransferFunction.h
index 284b1364ed..6a36f81abd 100644
--- a/third_party/skcms/src/TransferFunction.h
+++ b/third_party/skcms/src/TransferFunction.h
@@ -17,4 +17,4 @@ bool skcms_TransferFunction_invert(const skcms_TransferFunction*, skcms_Transfer
 
 // Fit c,d,f parameters of an skcms_TransferFunction to the first 2 < L ≤ N
 // evenly-spaced points on an skcms_Curve within a given tolerance, returning L.
-int skcms_fit_linear(const skcms_Curve*, int N, float tol, skcms_TransferFunction*);
+int skcms_fit_linear(const skcms_Curve*, int N, float tol, float* c, float* d, float* f);
diff --git a/third_party/skcms/src/Transform.c b/third_party/skcms/src/Transform.c
index 16cfaec0a2..9e893cf369 100644
--- a/third_party/skcms/src/Transform.c
+++ b/third_party/skcms/src/Transform.c
@@ -321,6 +321,11 @@ typedef struct {
     const void* arg;
 } OpAndArg;
 
+static OpAndArg select_poly_tf_op(const skcms_PolyTF* tf, int channel) {
+    static const Op ops[] = { Op_poly_tf_r, Op_poly_tf_g, Op_poly_tf_b };
+    return (OpAndArg){ops[channel], tf};
+}
+
 static OpAndArg select_curve_op(const skcms_Curve* curve, int channel) {
     static const struct { Op parametric, table_8, table_16; } ops[] = {
         { Op_tf_r, Op_table_8_r, Op_table_16_r },
@@ -522,6 +527,9 @@ bool skcms_Transform(const void*             src,
             for (int i = 0; i < 3; i++) {
                 OpAndArg oa = select_curve_op(&srcProfile->trc[i], i);
                 if (oa.op != Op_noop) {
+                    if (srcProfile->has_poly_tf[i]) {
+                        oa = select_poly_tf_op(&srcProfile->poly_tf[i], i);
+                    }
                     *ops++  = oa.op;
                     *args++ = oa.arg;
                 }
diff --git a/third_party/skcms/src/Transform.h b/third_party/skcms/src/Transform.h
index 1c4c15b4e3..c5892f1377 100644
--- a/third_party/skcms/src/Transform.h
+++ b/third_party/skcms/src/Transform.h
@@ -34,6 +34,9 @@
     M(tf_g)           \
     M(tf_b)           \
     M(tf_a)           \
+    M(poly_tf_r)      \
+    M(poly_tf_g)      \
+    M(poly_tf_b)      \
     M(table_8_r)      \
     M(table_8_g)      \
     M(table_8_b)      \
diff --git a/third_party/skcms/src/Transform_inl.h b/third_party/skcms/src/Transform_inl.h
index 3f2ac3ea96..529780ab7b 100644
--- a/third_party/skcms/src/Transform_inl.h
+++ b/third_party/skcms/src/Transform_inl.h
@@ -246,6 +246,13 @@ SI ATTR F NS(apply_transfer_function_)(const skcms_TransferFunction* tf, F x) {
 }
 #define apply_transfer_function NS(apply_transfer_function_)
 
+SI ATTR F NS(apply_poly_tf_)(const skcms_PolyTF* tf, F x) {
+    // TODO: handle x<0
+    return (F)if_then_else(x < tf->D, tf->C*x
+                                    , tf->A*x*x*x + tf->B*x*x + (1 - tf->A - tf->B));
+}
+#define apply_poly_tf NS(apply_poly_tf_)
+
 // Strided loads and stores of N values, starting from p.
 #if N == 1
     #define LOAD_3(T, p) (T)(p)[0]
@@ -847,6 +854,10 @@ static void NS(exec_ops)(const Op* ops, const void** args,
             case Op_tf_b:{ b = apply_transfer_function(*args++, b); } break;
             case Op_tf_a:{ a = apply_transfer_function(*args++, a); } break;
 
+            case Op_poly_tf_r:{ r = apply_poly_tf(*args++, r); } break;
+            case Op_poly_tf_g:{ g = apply_poly_tf(*args++, g); } break;
+            case Op_poly_tf_b:{ b = apply_poly_tf(*args++, b); } break;
+
             case Op_table_8_r: { r = NS(table_8_ )(*args++, r); } break;
             case Op_table_8_g: { g = NS(table_8_ )(*args++, g); } break;
             case Op_table_8_b: { b = NS(table_8_ )(*args++, b); } break;
diff --git a/third_party/skcms/version.sha1 b/third_party/skcms/version.sha1
index b6ca18f7cb..399e159cda 100755
--- a/third_party/skcms/version.sha1
+++ b/third_party/skcms/version.sha1
@@ -1 +1 @@
-73399c8ce4d8c1b44ab70554b999697e92e689ea
\ No newline at end of file
+cca4d5d9654b31900fc2a612007a9069f83f6de2
\ No newline at end of file