Collapse consecutive SkTableColorFilters

BUG=skia:1366

For the added bench, the collapsing makes the bench take:
- 70% of the time for CPU rendering of 3 consecutive matrix filters
- almost no change in the GPU rendering of the matrix filters
- 50% of the time for CPU and GPU rendering of 3 consecutive table filters

Review URL: https://codereview.chromium.org/776673002

4 files changed, 269 insertions, 22 deletions

diff --git a/bench/ImageFilterCollapse.cpp b/bench/ImageFilterCollapse.cpp
new file mode 100644
index 0000000000..6cda6ac389
--- /dev/null
+++ b/bench/ImageFilterCollapse.cpp
@@ -0,0 +1,158 @@
+/*
+ * Copyright 2014 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "Benchmark.h"
+#include "SkBitmap.h"
+#include "SkCanvas.h"
+#include "SkColorFilterImageFilter.h"
+#include "SkColorMatrixFilter.h"
+#include "SkGradientShader.h"
+#include "SkImageFilter.h"
+#include "SkTableColorFilter.h"
+
+// Chains several matrix color filters image filter or several
+// table filter image filters and draws a bitmap.
+// This bench shows an improvement in performance and memory
+// when collapsing matrices or tables is implemented since all
+// the passes are collapsed in one.
+
+class BaseImageFilterCollapseBench : public Benchmark {
+public:
+    BaseImageFilterCollapseBench(): fImageFilter(NULL) {}
+    ~BaseImageFilterCollapseBench() {
+        SkSafeUnref(fImageFilter);
+    }
+
+protected:
+    void doPreDraw(SkColorFilter* colorFilters[], int nFilters) {
+        // Create a chain of ImageFilters from colorFilters
+        fImageFilter = NULL;
+        for(int i = nFilters; i --> 0;) {
+            SkAutoTUnref<SkImageFilter> filter(
+                        SkColorFilterImageFilter::Create(colorFilters[i], fImageFilter, NULL, 0)
+            );
+            SkRefCnt_SafeAssign(fImageFilter, filter.get());
+        }
+    }
+
+    void onDraw(const int loops, SkCanvas* canvas) SK_OVERRIDE {
+        makeBitmap();
+
+        for(int i = 0; i < loops; i++) {
+            SkPaint paint;
+            paint.setImageFilter(fImageFilter);
+            canvas->drawBitmap(fBitmap, 0, 0, &paint);
+        }
+    }
+
+private:
+    SkImageFilter* fImageFilter;
+    SkBitmap fBitmap;
+
+    void makeBitmap() {
+        int W = 400;
+        int H = 400;
+        fBitmap.allocN32Pixels(W, H);
+        fBitmap.eraseColor(SK_ColorTRANSPARENT);
+
+        SkCanvas canvas(fBitmap);
+        SkPaint paint;
+        SkPoint pts[] = { {0, 0}, {SkIntToScalar(W), SkIntToScalar(H)} };
+        SkColor colors[] = {
+            SK_ColorBLACK, SK_ColorGREEN, SK_ColorCYAN,
+            SK_ColorRED, 0, SK_ColorBLUE, SK_ColorWHITE
+        };
+        SkAutoTUnref<SkShader> shader(SkGradientShader::CreateLinear(
+                    pts, colors, NULL, SK_ARRAY_COUNT(colors), SkShader::kClamp_TileMode
+        ));
+        paint.setShader(shader);
+        canvas.drawPaint(paint);
+    }
+};
+
+class TableCollapseBench: public BaseImageFilterCollapseBench {
+public:
+    virtual ~TableCollapseBench() {}
+
+protected:
+    virtual const char* onGetName() SK_OVERRIDE {
+        return "image_filter_collapse_table";
+    }
+
+    virtual void onPreDraw() SK_OVERRIDE {
+        for (int i = 0; i < 256; ++i) {
+            int n = i >> 5;
+            table1[i] = (n << 5) | (n << 2) | (n >> 1);
+
+            table2[i] = i * i / 255;
+
+            float fi = i / 255.0f;
+            table3[i] = static_cast<uint8_t>(sqrtf(fi) * 255);
+        }
+
+        SkColorFilter* colorFilters[] = {
+            SkTableColorFilter::Create(table1),
+            SkTableColorFilter::Create(table2),
+            SkTableColorFilter::Create(table3),
+        };
+
+        doPreDraw(colorFilters, SK_ARRAY_COUNT(colorFilters));
+
+        for(unsigned i = 0; i < SK_ARRAY_COUNT(colorFilters); i++) {
+            colorFilters[i]->unref();
+        }
+    }
+
+private:
+    uint8_t table1[256], table2[256], table3[256];
+};
+
+static SkColorFilter* make_brightness(float amount) {
+    SkScalar amount255 = SkScalarMul(amount, SkIntToScalar(255));
+    SkScalar matrix[20] = { 1, 0, 0, 0, amount255,
+                            0, 1, 0, 0, amount255,
+                            0, 0, 1, 0, amount255,
+                            0, 0, 0, 1, 0 };
+    return SkColorMatrixFilter::Create(matrix);
+}
+
+static SkColorFilter* make_grayscale() {
+    SkScalar matrix[20];
+    memset(matrix, 0, 20 * sizeof(SkScalar));
+    matrix[0] = matrix[5] = matrix[10] = 0.2126f;
+    matrix[1] = matrix[6] = matrix[11] = 0.7152f;
+    matrix[2] = matrix[7] = matrix[12] = 0.0722f;
+    matrix[18] = 1.0f;
+    return SkColorMatrixFilter::Create(matrix);
+}
+
+class MatrixCollapseBench: public BaseImageFilterCollapseBench {
+public:
+    virtual ~MatrixCollapseBench() {}
+
+protected:
+    virtual const char* onGetName() SK_OVERRIDE {
+        return "image_filter_collapse_matrix";
+    }
+
+    virtual void onPreDraw() SK_OVERRIDE {
+        SkColorFilter* colorFilters[] = {
+            make_brightness(0.1f),
+            make_grayscale(),
+            make_brightness(-0.1f),
+        };
+
+        doPreDraw(colorFilters, SK_ARRAY_COUNT(colorFilters));
+
+        for(unsigned i = 0; i < SK_ARRAY_COUNT(colorFilters); i++) {
+            colorFilters[i]->unref();
+        }
+    }
+};
+
+DEF_BENCH(return new TableCollapseBench;)
+DEF_BENCH(return new MatrixCollapseBench;)
diff --git a/gm/tablecolorfilter.cpp b/gm/tablecolorfilter.cpp
index f806caad6a..a49859bf8f 100644
--- a/gm/tablecolorfilter.cpp
+++ b/gm/tablecolorfilter.cpp
@@ -7,6 +7,7 @@
 
 #include "gm.h"
 #include "SkCanvas.h"
+#include "SkColorFilterImageFilter.h"
 #include "SkGradientShader.h"
 #include "SkTableColorFilter.h"
 
@@ -68,6 +69,10 @@ static void make_table2(uint8_t table[]) {
     }
 }
 
+static SkColorFilter* make_null_cf() {
+    return NULL;
+}
+
 static SkColorFilter* make_cf0() {
     uint8_t table[256]; make_table0(table);
     return SkTableColorFilter::Create(table);
@@ -97,33 +102,82 @@ protected:
     }
 
     virtual SkISize onISize() {
-        return SkISize::Make(700, 300);
+        return SkISize::Make(700, 1650);
     }
 
     virtual void onDraw(SkCanvas* canvas) {
         canvas->drawColor(0xFFDDDDDD);
         canvas->translate(20, 20);
 
-        SkScalar x = 0, y = 0;
 
-        static void (*gMakers[])(SkBitmap*) = { make_bm0, make_bm1 };
-        for (size_t maker = 0; maker < SK_ARRAY_COUNT(gMakers); ++maker) {
+        static SkColorFilter* (*gColorFilterMakers[])() = { make_null_cf, make_cf0, make_cf1,
+                                                 make_cf2, make_cf3 };
+        static void (*gBitmapMakers[])(SkBitmap*) = { make_bm0, make_bm1 };
+
+        // This test will be done once for each bitmap with the results stacked vertically.
+        // For a single bitmap the resulting image will be the following:
+        //  - A first line with the original bitmap, followed by the image drawn once
+        //  with each of the N color filters
+        //  - N lines of the bitmap drawn N times, this will cover all N*N combinations of
+        //  pair of color filters in order to test the collpsing of consecutive table
+        //  color filters.
+        //
+        //  Here is a graphical representation of the result for 2 bitmaps and 2 filters
+        //  with the number corresponding to the number of filters the bitmap goes through:
+        //
+        //  --bitmap1
+        //  011
+        //  22
+        //  22
+        //  --bitmap2
+        //  011
+        //  22
+        //  22
+
+        SkScalar x = 0, y = 0;
+        for (size_t bitmapMaker = 0; bitmapMaker < SK_ARRAY_COUNT(gBitmapMakers); ++bitmapMaker) {
             SkBitmap bm;
-            gMakers[maker](&bm);
+            gBitmapMakers[bitmapMaker](&bm);
 
-            SkPaint paint;
+            SkScalar xOffset = SkScalar(bm.width() * 9 / 8);
+            SkScalar yOffset = SkScalar(bm.height() * 9 / 8);
+
+            // Draw the first element of the first line
             x = 0;
-            canvas->drawBitmap(bm, x, y, &paint);
-            paint.setColorFilter(make_cf0())->unref();  x += bm.width() * 9 / 8;
-            canvas->drawBitmap(bm, x, y, &paint);
-            paint.setColorFilter(make_cf1())->unref();  x += bm.width() * 9 / 8;
-            canvas->drawBitmap(bm, x, y, &paint);
-            paint.setColorFilter(make_cf2())->unref();  x += bm.width() * 9 / 8;
-            canvas->drawBitmap(bm, x, y, &paint);
-            paint.setColorFilter(make_cf3())->unref();  x += bm.width() * 9 / 8;
+            SkPaint paint;
             canvas->drawBitmap(bm, x, y, &paint);
 
-            y += bm.height() * 9 / 8;
+            // Draws the rest of the first line for this bitmap
+            // each draw being at xOffset of the previous one
+            for (unsigned i = 1; i < SK_ARRAY_COUNT(gColorFilterMakers); ++i) {
+                x += xOffset;
+                paint.setColorFilter(gColorFilterMakers[i]())->unref();
+                canvas->drawBitmap(bm, x, y, &paint);
+            }
+
+            paint.setColorFilter(NULL);
+
+            for (unsigned i = 0; i < SK_ARRAY_COUNT(gColorFilterMakers); ++i) {
+                SkAutoTUnref<SkColorFilter> colorFilter1(gColorFilterMakers[i]());
+                SkAutoTUnref<SkImageFilter> imageFilter1(SkColorFilterImageFilter::Create(
+                            colorFilter1, NULL, NULL, 0));
+
+                // Move down to the next line and draw it
+                // each draw being at xOffset of the previous one
+                y += yOffset;
+                x = 0;
+                for (unsigned j = 1; j < SK_ARRAY_COUNT(gColorFilterMakers); ++j) {
+                    SkAutoTUnref<SkColorFilter> colorFilter2(gColorFilterMakers[j]());
+                    SkAutoTUnref<SkImageFilter> imageFilter2(SkColorFilterImageFilter::Create(
+                                colorFilter2, imageFilter1, NULL, 0));
+                    paint.setImageFilter(imageFilter2);
+                    canvas->drawBitmap(bm, x, y, &paint);
+                    x += xOffset;
+                }
+            }
+
+            // Move down one line to the beginning of the block for next bitmap
+            y += yOffset;
         }
     }
 
diff --git a/gyp/bench.gypi b/gyp/bench.gypi
index dbb96d4a80..ce483e98e5 100644
--- a/gyp/bench.gypi
+++ b/gyp/bench.gypi
@@ -59,6 +59,7 @@
     '../bench/ImageCacheBench.cpp',
     '../bench/ImageDecodeBench.cpp',
     '../bench/ImageFilterDAGBench.cpp',
+    '../bench/ImageFilterCollapse.cpp',
     '../bench/InterpBench.cpp',
     '../bench/LightingBench.cpp',
     '../bench/LineBench.cpp',
diff --git a/src/effects/SkColorFilterImageFilter.cpp b/src/effects/SkColorFilterImageFilter.cpp
index acd6fac25e..0a4a693ab0 100755
--- a/src/effects/SkColorFilterImageFilter.cpp
+++ b/src/effects/SkColorFilterImageFilter.cpp
@@ -12,6 +12,7 @@
 #include "SkDevice.h"
 #include "SkColorFilter.h"
 #include "SkReadBuffer.h"
+#include "SkTableColorFilter.h"
 #include "SkWriteBuffer.h"
 
 namespace {
@@ -21,7 +22,19 @@ void mult_color_matrix(SkScalar a[20], SkScalar b[20], SkScalar out[20]) {
         for (int i = 0; i < 5; ++i) {
             out[i+j*5] = 4 == i ? a[4+j*5] : 0;
             for (int k = 0; k < 4; ++k)
-                out[i+j*5] += SkScalarMul(a[k+j*5], b[i+k*5]);
+                out[i+j*5] += a[k+j*5] * b[i+k*5];
+        }
+    }
+}
+
+// Combines the two lookup tables so that making a lookup using OUT has
+// the same effect as making a lookup through B then A.
+void combine_color_tables(const uint8_t a[4 * 256],
+                          const uint8_t b[4 * 256],
+                          uint8_t out[4 * 256]) {
+    for (int i = 0; i < 4; i++) {
+        for (int j = 0; j < 256; j++) {
+            out[i * 256 + j] = a[i * 256 + b[i * 256 + j]];
         }
     }
 }
@@ -59,23 +72,44 @@ bool matrix_needs_clamping(SkScalar matrix[20]) {
 
 SkColorFilterImageFilter* SkColorFilterImageFilter::Create(SkColorFilter* cf,
         SkImageFilter* input, const CropRect* cropRect, uint32_t uniqueID) {
-    SkASSERT(cf);
     if (NULL == cf) {
         return NULL;
     }
-    SkScalar colorMatrix[20], inputMatrix[20];
+
     SkColorFilter* inputColorFilter;
-    if (input && cf->asColorMatrix(colorMatrix)
-              && input->asColorFilter(&inputColorFilter)
-              && (inputColorFilter)) {
+    if (input && input->asColorFilter(&inputColorFilter) && inputColorFilter) {
         SkAutoUnref autoUnref(inputColorFilter);
-        if (inputColorFilter->asColorMatrix(inputMatrix) && !matrix_needs_clamping(inputMatrix)) {
+
+        // Try to collapse two consecutive matrix filters
+        SkScalar colorMatrix[20], inputMatrix[20];
+        if (cf->asColorMatrix(colorMatrix) && inputColorFilter->asColorMatrix(inputMatrix)
+                                           && !matrix_needs_clamping(inputMatrix)) {
             SkScalar combinedMatrix[20];
             mult_color_matrix(colorMatrix, inputMatrix, combinedMatrix);
             SkAutoTUnref<SkColorFilter> newCF(SkColorMatrixFilter::Create(combinedMatrix));
             return SkNEW_ARGS(SkColorFilterImageFilter, (newCF, input->getInput(0), cropRect, 0));
         }
+
+        // Try to collapse two consecutive table filters
+        SkBitmap colorTable, inputTable;
+        if (cf->asComponentTable(&colorTable) && inputColorFilter->asComponentTable(&inputTable)) {
+            uint8_t combinedTable[4 * 256];
+            SkAutoLockPixels colorLock(colorTable);
+            SkAutoLockPixels inputLock(inputTable);
+
+            combine_color_tables(colorTable.getAddr8(0, 0), inputTable.getAddr8(0, 0),
+                                 combinedTable);
+            SkAutoTUnref<SkColorFilter> newCF(SkTableColorFilter::CreateARGB(
+                        &combinedTable[256 * 0],
+                        &combinedTable[256 * 1],
+                        &combinedTable[256 * 2],
+                        &combinedTable[256 * 3])
+            );
+
+            return SkNEW_ARGS(SkColorFilterImageFilter, (newCF, input->getInput(0), cropRect, 0));
+        }
     }
+
     return SkNEW_ARGS(SkColorFilterImageFilter, (cf, input, cropRect, uniqueID));
 }