Implement multi-color-stops in linear gradients using Sk4f

src/effects/gradients/SkLinearGradient.cpp

 /*
  * Copyright 2012 Google Inc.
  *
  * Use of this source code is governed by a BSD-style license that can be
  * found in the LICENSE file.
  */
 
 #include "SkLinearGradient.h"
 
+static const float kInv255Float = 1.0f / 255;

[caryclark, 2015/11/16 14:44:29]

This is a popular pattern:

src/effects/SkColorMatrixFilter.cpp:449:
src/effects/SkTableMaskFilter.cpp:88
include/gpu/GrColor.h:125:
include/gpu/GrColor.h:134:
src/gpu/GrFragmentProcessor.cpp:240:
src/gpu/effects/GrConstColorProcessor.cpp:50
src/gpu/gl/GrGLGpu.cpp:1705:

I wonder if it's worth having in one place (with one name)?

+
 static inline int repeat_bits(int x, const int bits) {
     return x & ((1 << bits) - 1);
 }
 
 static inline int repeat_8bits(int x) {
     return x & 0xFF;
 }
 
 // Visual Studio 2010 (MSC_VER=1600) optimizes bit-shift code incorrectly.
 // See http://code.google.com/p/skia/issues/detail?id=472
@@ skipping 59 matching lines @@
 }
 
 size_t SkLinearGradient::contextSize() const {
     return sizeof(LinearGradientContext);
 }
 
 SkShader::Context* SkLinearGradient::onCreateContext(const ContextRec& rec, void* storage) const {
     return new (storage) LinearGradientContext(*this, rec);
 }
 
+static uint32_t SkSwizzle_Color_to_PMColor(SkColor c) {
+    return SkPackARGB32NoCheck(SkColorGetA(c), SkColorGetR(c), SkColorGetG(c), SkColorGetB(c));
+}
+
 SkLinearGradient::LinearGradientContext::LinearGradientContext(
-        const SkLinearGradient& shader, const ContextRec& rec)
-    : INHERITED(shader, rec)
+        const SkLinearGradient& shader, const ContextRec& ctx)
+    : INHERITED(shader, ctx)
 {
     unsigned mask = SkMatrix::kTranslate_Mask | SkMatrix::kScale_Mask;
     if ((fDstToIndex.getType() & ~mask) == 0) {
         // when we dither, we are (usually) not const-in-Y
-        if ((fFlags & SkShader::kHasSpan16_Flag) && !rec.fPaint->isDither()) {
+        if ((fFlags & SkShader::kHasSpan16_Flag) && !ctx.fPaint->isDither()) {
             // only claim this if we do have a 16bit mode (i.e. none of our
             // colors have alpha), and if we are not dithering (which obviously
             // is not const in Y).
             fFlags |= SkShader::kConstInY16_Flag;
         }
     }
+
+    // setup for Sk4f
+    int count = shader.fColorCount;
+    fRecs.setCount(count);
+    Rec* rec = fRecs.begin();
+    if (shader.fOrigPos) {
+        rec[0].fPos = 0;
+        rec[0].fPosScale = 0;   // should never get used

[caryclark, 2015/11/16 14:44:29]

SkDEBUGCODE() ? 
Assign SK_ScalarNaN instead?

[reed1, 2015/11/16 16:43:33]

Done.

+        for (int i = 1; i < count; ++i) {
+            rec[i].fPos = SkTMin(SkTMax(rec[i - 1].fPos, shader.fOrigPos[i]), 1.0f);

[caryclark, 2015/11/16 14:44:29]

SkASSERT(rec[i - 1].fPos <= rec[i].fPos);
(see comment below)

+            rec[i].fPosScale = 1.0f / (rec[i].fPos - rec[i - 1].fPos);
+        }
+        rec[count - 1].fPos = 1;    // overwrite the last value just to be sure we end at 1.0

[caryclark, 2015/11/16 14:44:29]

This seems odd -- is it OK for the last iteration of the loop to derive
fPosScale from the value that gets overridden here?

[caryclark, 2015/11/16 14:44:29]

SkASSERT(rec[count - 2].fPos <= rec[count - 1].fPos);
(see comment below)

+    } else {
+        float invScale = 1.0f / (count - 1);
+        for (int i = 0; i < count; ++i) {
+            rec[i].fPos = i * invScale;
+            rec[i].fPosScale = count - 1;
+        }
+    }
+
+    fApplyAlphaAfterInterp = true;
+    if ((shader.getGradFlags() & SkGradientShader::kInterpolateColorsInPremul_Flag) ||
+        shader.colorsAreOpaque())
+    {
+        fApplyAlphaAfterInterp = false;
+    }

[caryclark, 2015/11/16 14:44:29]

fApplyAlphaAfterInterp = !(shader.getGradFlags() &
SkGradientShader::kInterpolateColorsInPremul_Flag) && !shader.colorsAreOpaque()

?

+
+    if (fApplyAlphaAfterInterp) {
+        const float paintAlpha = ctx.fPaint->getAlpha() * kInv255Float;
+        const Sk4f scale(1, 1, 1, paintAlpha);
+        for (int i = 0; i < count; ++i) {
+            uint32_t c = SkSwizzle_Color_to_PMColor(shader.fOrigColors[i]);
+            rec[i].fColor = Sk4f::FromBytes((const uint8_t*)&c) * scale;
+            if (i > 0) {
+                SkASSERT(rec[i - 1].fPos <= rec[i].fPos);

[caryclark, 2015/11/16 14:44:29]

this assert looks like it would be more at home above where fPos is computed
(see prior comment)

+            }
+        }
+    } else {
+        unsigned alphaScale = ctx.fPaint->getAlpha() + (ctx.fPaint->getAlpha() >> 7);
+        for (int i = 0; i < count; ++i) {
+            SkPMColor pmc = SkPreMultiplyColor(shader.fOrigColors[i]);
+            pmc = SkAlphaMulQ(pmc, alphaScale);
+            rec[i].fColor = Sk4f::FromBytes((const uint8_t*)&pmc);
+            if (i > 0) {
+                SkASSERT(rec[i - 1].fPos <= rec[i].fPos);

[caryclark, 2015/11/16 14:44:29]

Ditto

+            }
+        }
+    }
 }
 
 #define NO_CHECK_ITER               \
     do {                            \
     unsigned fi = SkGradFixedToFixed(fx) >> SkGradientShaderBase::kCache32Shift; \
     SkASSERT(fi <= 0xFF);           \
     fx += dx;                       \
     *dstC++ = cache[toggle + fi];   \
     toggle = next_dither_toggle(toggle); \
     } while (0)
@@ skipping 92 matching lines @@
         *dstC++ = cache[toggle + fi];
         toggle = next_dither_toggle(toggle);
     } while (--count != 0);
 }
 
 }
 
 void SkLinearGradient::LinearGradientContext::shadeSpan(int x, int y, SkPMColor* SK_RESTRICT dstC,
                                                         int count) {
     SkASSERT(count > 0);
+    const SkLinearGradient& linearGradient = static_cast<const SkLinearGradient&>(fShader);
 
-    const SkLinearGradient& linearGradient = static_cast<const SkLinearGradient&>(fShader);
+#ifndef SK_SUPPORT_LEGACY_LINEAR_GRADIENT_TABLE
+    if (SkShader::kClamp_TileMode == linearGradient.fTileMode &&
+        kLinear_MatrixClass == fDstToIndexClass &&
+        linearGradient.fColorCount > 2)
+    {
+        this->shade4_clamp(x, y, dstC, count);
+        return;
+    }
+#endif
 
     SkPoint             srcPt;
     SkMatrix::MapXYProc dstProc = fDstToIndexProc;
     TileProc            proc = linearGradient.fTileProc;
     const SkPMColor* SK_RESTRICT cache = fCache->getCache32();
     int                 toggle = init_dither_toggle(x, y);
 
     if (fDstToIndexClass != kPerspective_MatrixClass) {
         dstProc(fDstToIndex, SkIntToScalar(x) + SK_ScalarHalf,
                              SkIntToScalar(y) + SK_ScalarHalf, &srcPt);
@@ skipping 342 matching lines @@
     str->append("SkLinearGradient (");
 
     str->appendf("start: (%f, %f)", fStart.fX, fStart.fY);
     str->appendf(" end: (%f, %f) ", fEnd.fX, fEnd.fY);
 
     this->INHERITED::toString(str);
 
     str->append(")");
 }
 #endif
+
+///////////////////////////////////////////////////////////////////////////////////////////////////
+
+#include "SkNx.h"
+
+static const SkLinearGradient::LinearGradientContext::Rec* find(float tiledX,
+                                        const SkLinearGradient::LinearGradientContext::Rec rec[],
+                                                                int count) {
+    SkASSERT(count > 1);
+    SkASSERT(0 == rec[0].fPos);
+    SkASSERT(1 == rec[count - 1].fPos);
+    SkASSERT(tiledX >= 0 && tiledX <= 1);
+
+    int i = 1;
+    while (rec[i].fPos < tiledX) {
+        i += 1;
+    }

[caryclark, 2015/11/16 14:44:29]

Is this array ever so large that it's worth a non-linear search?

[reed1, 2015/11/16 16:43:33]

Could be (though my guess is it is usually between 2 and 6). My next step is to
fold the searcher directly into the callers, since both callers (forward and
backward) never need to search the entire list each time.

+    return &rec[i - 1];
+}
+
+template <bool apply_alpha> SkPMColor trunc_from_255(Sk4f x) {
+    SkPMColor c;
+    x.toBytes((uint8_t*)&c);
+    if (apply_alpha) {
+        c = SkPreMultiplyARGB(SkGetPackedA32(c), SkGetPackedR32(c),
+                              SkGetPackedG32(c), SkGetPackedB32(c));
+    }
+    return c;
+}
+
+template <bool apply_alpha> void fill(SkPMColor dst[], int count, Sk4f c4, Sk4f c4other) {
+    sk_memset32_dither(dst, trunc_from_255<apply_alpha>(c4),
+                            trunc_from_255<apply_alpha>(c4other), count);
+}
+
+/*
+ *  TODOs
+ *
+ *  - tilemodes
+ *  - interp before or after premul
+ *  - perspective
+ *  - optimizations

[f(malita), 2015/11/16 15:16:20]

How does current perf compare to existing impl?

[reed1, 2015/11/16 16:43:33]

Slower, by 10-20% depending.

+ *      - use fixed (32bit or 16bit) instead of floats?
+ */
+
+static Sk4f lerp_color(float fx, const SkLinearGradient::LinearGradientContext::Rec* rec) {
+    const float p0 = rec[0].fPos;
+    const Sk4f c0 = rec[0].fColor;
+    const Sk4f c1 = rec[1].fColor;
+    const Sk4f diffc = c1 - c0;
+    const float scale = rec[1].fPosScale;
+    const float t = (fx - p0) * scale;
+    return c0 + Sk4f(t) * diffc;
+}
+
+template <bool apply_alpha> void ramp(SkPMColor dstC[], int n, Sk4f c, Sk4f dc,
+                                      Sk4f dither0, Sk4f dither1) {
+    Sk4f dc2 = dc + dc;
+    Sk4f dc4 = dc2 + dc2;
+    Sk4f cd0 = c + dither0;
+    Sk4f cd1 = c + dc + dither1;
+    Sk4f cd2 = cd0 + dc2;
+    Sk4f cd3 = cd1 + dc2;
+    while (n >= 4) {
+        *dstC++ = trunc_from_255<apply_alpha>(cd0);
+        *dstC++ = trunc_from_255<apply_alpha>(cd1);
+        *dstC++ = trunc_from_255<apply_alpha>(cd2);
+        *dstC++ = trunc_from_255<apply_alpha>(cd3);

[caryclark, 2015/11/16 14:44:29]

probably not worth it, but

if (n >= 4) {
   do {
       *dstC++ ...   x 4
       cd0 = ...
       cd1 = ...
       if ((n -= 4) <= 0) {
          break;
       }
       cd2 = ...
       cd3 = ...
   } while (true);
}

might shave off a teeny bit

[reed1, 2015/11/16 16:43:33]

Good observation. But it took me a full minute to understand how/why. I may time
it, but only do it if it really pays off, as it is harder to parse (given that
that pattern isn't used very much).

+        cd0 = cd0 + dc4;
+        cd1 = cd1 + dc4;
+        cd2 = cd2 + dc4;
+        cd3 = cd3 + dc4;
+        n -= 4;
+    }
+    if (n & 2) {
+        *dstC++ = trunc_from_255<apply_alpha>(cd0);
+        *dstC++ = trunc_from_255<apply_alpha>(cd1);
+        cd0 = cd0 + dc2;

[caryclark, 2015/11/16 14:44:29]

move this into the condition below?

+    }
+    if (n & 1) {
+        *dstC++ = trunc_from_255<apply_alpha>(cd0);
+    }
+}
+
+template <bool apply_alpha> void SkLinearGradient::LinearGradientContext::shade4_pos_clamp(
+                                                               SkPMColor dstC[], int count,
+                                                               float fx, float dx, float invDx,
+                                                               Sk4f dither0, Sk4f dither1) {
+    const Rec* rec = fRecs.begin();
+
+    const Sk4f dx4 = Sk4f(dx);
+    SkDEBUGCODE(SkPMColor* endDstC = dstC + count;)
+
+    if (fx < 0) {
+        int n = SkTMin(SkFloatToIntFloor(-fx * invDx) + 1, count);
+        fill<apply_alpha>(dstC, n, rec[0].fColor + dither0, rec[0].fColor + dither1);
+        count -= n;
+        SkASSERT(count >= 0);
+        dstC += n;
+        fx += n * dx;
+        SkASSERT(0 == count || fx >= 0);
+        if (n & 1) {
+            SkTSwap(dither0, dither1);
+        }
+    }
+
+    while (count > 0) {
+        if (fx >= 1) {
+            Sk4f color = rec[fRecs.count() - 1].fColor;
+            fill<apply_alpha>(dstC, count, color + dither0, color + dither1);
+            return;
+        }
+
+        const Rec* r = find(fx, rec, fRecs.count());

[caryclark, 2015/11/16 14:44:29]

add
           const float p0 = r[0].fPos;
to mirror code below?

[f(malita), 2015/11/16 15:16:20]

Since we're peeking at r[1] below, I would SkASSERT(r < rec + fRecs.count() - 1)

[reed1, 2015/11/16 17:31:24]

Done.

[reed1, 2015/11/16 17:31:24]

Done.

+        const Sk4f c0 = r[0].fColor;
+        const Sk4f diffc = r[1].fColor - c0;
+        const float scale = r[1].fPosScale;
+        const float t = (fx - r[0].fPos) * scale;

[caryclark, 2015/11/16 14:44:29]

const float t = (fx - p0) * scale;

+        Sk4f c = c0 + Sk4f(t) * diffc;
+
+        const Sk4f dc = diffc * dx4 * Sk4f(scale);
+        const float p1 = r[1].fPos;
+
+        int n = SkTMin((int)((p1-fx)*invDx) + 1, count);

[caryclark, 2015/11/16 14:44:29]

Is this the same as the SkFloatToIntFloor in the < 0 condition above?

+
+        fx += n * dx;
+        count -= n;
+        SkASSERT(0 == count || fx >= p1);
+        SkASSERT(count >= 0);

[caryclark, 2015/11/16 14:44:29]

may be worth changing either the <0 condition or this to keep the order of the
lines the same to make it slightly easier to read and maintain

+
+        ramp<apply_alpha>(dstC, n, c, dc, dither0, dither1);
+        dstC += n;
+        SkASSERT(dstC <= endDstC);
+
+        if (n & 1) {
+            SkTSwap(dither0, dither1);
+        }
+    }
+}
+
+template <bool apply_alpha>void SkLinearGradient::LinearGradientContext::shade4_neg_clamp(

[f(malita), 2015/11/16 15:16:20]

shade4_neg_clamp & shade4_pos_clamp look pretty similar - is (moar) templateing
feasible?

+                                                               SkPMColor dstC[], int count,
+                                                               float fx, float dx, float invDx,
+                                                               Sk4f dither0, Sk4f dither1) {
+    const Rec* rec = fRecs.begin();
+
+    const Sk4f dx4 = Sk4f(dx);
+    SkDEBUGCODE(SkPMColor* endDstC = dstC + count;)
+
+    if (fx > 1) {
+        int n = SkTMin(SkFloatToIntFloor((1 - fx) * invDx) + 1, count);
+        Sk4f c = rec[fRecs.count() - 1].fColor;
+        fill<apply_alpha>(dstC, n, c + dither0, c + dither1);
+        count -= n;
+        SkASSERT(count >= 0);
+        dstC += n;
+        fx += n * dx;
+        SkASSERT(0 == count || fx <= 1);
+        if (n & 1) {
+            SkTSwap(dither0, dither1);
+        }
+    }
+
+    while (count > 0) {
+        if (fx <= 0) {
+            fill<apply_alpha>(dstC, count, rec[0].fColor + dither0, rec[0].fColor + dither1);

[caryclark, 2015/11/16 14:44:29]

maybe 

            Sk4f color = rec[0].fColor;
            fill<apply_alpha>(dstC, count, color + dither0, color + dither1);

just to mirror the code above

[reed1, 2015/11/16 16:43:33]

Done.

+            return;
+        }
+
+        const Rec* r = find(fx, rec, fRecs.count());
+        const float p0 = r[0].fPos;
+        const Sk4f c0 = r[0].fColor;
+        const Sk4f diffc = r[1].fColor - c0;
+        const float scale = r[1].fPosScale;
+        const float t = (fx - p0) * scale;
+        Sk4f c = c0 + Sk4f(t) * diffc;
+
+        const Sk4f dc = diffc * dx4 * Sk4f(scale);
+
+        int n = SkTMin((int)((p0 - fx)*invDx) + 1, count);
+
+        fx += n * dx;
+        count -= n;
+        SkASSERT(0 == count || fx <= p0);
+        SkASSERT(count >= 0);
+
+        ramp<apply_alpha>(dstC, n, c, dc, dither0, dither1);
+        dstC += n;
+        SkASSERT(dstC <= endDstC);
+
+        if (n & 1) {
+            SkTSwap(dither0, dither1);
+        }
+    }
+}
+
+void SkLinearGradient::LinearGradientContext::shade4_clamp(int x, int y, SkPMColor dstC[],
+                                                           int count) {
+    SkASSERT(count > 0);
+    SkASSERT(kLinear_MatrixClass == fDstToIndexClass);
+
+    SkPoint srcPt;
+    fDstToIndexProc(fDstToIndex, x + SK_ScalarHalf, y + SK_ScalarHalf, &srcPt);
+    float fx = srcPt.x();
+    const float dx = fDstToIndex.getScaleX();
+
+    Sk4f dither0, dither1;
+    if (fDither) {
+        // [ 1/8  5/8 ]
+        // [ 7/8  3/8 ]
+        const float ditherCell[] = {
+            0.125f, 0.625f,
+            0.875f, 0.375f,
+        };

[caryclark, 2015/11/16 14:44:29]

Out of curiosity, could this be

              1.0f/8, 5.0f/8,
              7.0f/8, 3.0f/8,
          };

to remove the need for the comment?

[reed1, 2015/11/16 16:43:33]

Very good idea. Done.

+        const int rowIndex = (y & 1) << 1;
+        dither0 = Sk4f(ditherCell[rowIndex]);
+        dither1 = Sk4f(ditherCell[rowIndex + 1]);
+    } else {
+        dither0 = dither1 = Sk4f(0.5f);
+    }
+
+    const float invDx = 1 / dx;
+
+    if (!SkScalarIsFinite(invDx)) { // dx is effectively zero, gradient is vertical
+        fx = SkTMin(SkTMax(fx, 0.0f), 1.0f);

[caryclark, 2015/11/16 14:44:28]

SkTPin(fx, 0.0f, 1.0f)

[reed1, 2015/11/16 16:43:33]

Done.

+        Sk4f c = lerp_color(fx, find(fx, fRecs.begin(), fRecs.count()));
+        if (fApplyAlphaAfterInterp) {
+            fill<true>(dstC, count, c + dither0, c + dither1);
+        } else {
+            fill<false>(dstC, count, c + dither0, c + dither1);
+        }
+        return;
+    }
+
+    if (dx > 0) {
+        if (fApplyAlphaAfterInterp) {
+            this->shade4_pos_clamp<true>(dstC, count, fx, dx, invDx, dither0, dither1);
+        } else {
+            this->shade4_pos_clamp<false>(dstC, count, fx, dx, invDx, dither0, dither1);
+        }
+    } else {
+        if (fApplyAlphaAfterInterp) {
+            this->shade4_neg_clamp<true>(dstC, count, fx, dx, invDx, dither0, dither1);
+        } else {
+            this->shade4_neg_clamp<false>(dstC, count, fx, dx, invDx, dither0, dither1);
+        }
+    }
+}
+