Generic 4f gradient T sampler fallback

src/effects/gradients/Sk4fGradientBase.cpp

Index: src/effects/gradients/Sk4fGradientBase.cpp
diff --git a/src/effects/gradients/Sk4fGradientBase.cpp b/src/effects/gradients/Sk4fGradientBase.cpp
index 76fb178776a5ce7c07245a113a257966fcf9aae7..a7298127907f38aff93a2af0c7dc3b8bd650980e 100644
--- a/src/effects/gradients/Sk4fGradientBase.cpp
+++ b/src/effects/gradients/Sk4fGradientBase.cpp
@@ -6,17 +6,115 @@
  */
 
 #include "Sk4fGradientBase.h"
+#include "Sk4fGradientPriv.h"
+
+#include <functional>
 
 namespace {
 
-// true when x is in [k1,k2)
-bool in_range(SkScalar x, SkScalar k1, SkScalar k2) {
-    SkASSERT(k1 != k2);
-    return (k1 < k2)
-        ? (x >= k1 && x < k2)
-        : (x >= k2 && x < k1);
+SkPMColor pack_color(SkColor c, bool premul) {
+    return premul
+        ? SkPreMultiplyColor(c)
+        : SkPackARGB32NoCheck(SkColorGetA(c), SkColorGetR(c), SkColorGetG(c), SkColorGetB(c));
+}
+
+template<SkShader::TileMode>
+SkScalar tileProc(SkScalar t);
+
+template<>
+SkScalar tileProc<SkShader::kClamp_TileMode>(SkScalar t) {
+    // synthetic clamp-mode edge intervals allow for a free-floating t:
+    //   [-inf..0)[0..1)[1..+inf)
+    return t;
+}
+
+template<>
+SkScalar tileProc<SkShader::kRepeat_TileMode>(SkScalar t) {
+    // t % 1  (intervals range: [0..1))
+    return t - SkScalarFloorToScalar(t);
+}
+
+template<>
+SkScalar tileProc<SkShader::kMirror_TileMode>(SkScalar t) {
+    // t % 2  (synthetic mirror intervals expand the range to [0..2)
+    return t - SkScalarFloorToScalar(t / 2) * 2;
 }
 
+class IntervalIterator {
+public:
+    IntervalIterator(const SkColor* colors, const SkScalar* pos, int count, bool reverse)
+        : fColors(colors)
+        , fPos(pos)
+        , fCount(count)
+        , fFirstPos(reverse ? SK_Scalar1 : 0)
+        , fBegin(reverse ? count - 1 : 0)
+        , fAdvance(reverse ? -1 : 1) {
+        SkASSERT(colors);
+        SkASSERT(count > 0);
+    }
+
+    void iterate(std::function<void(SkColor, SkColor, SkScalar, SkScalar)> func) const {
+        if (!fPos) {
+            this->iterateImplicitPos(func);
+            return;
+        }
+
+        const int end = fBegin + fAdvance * (fCount - 1);
+        const SkScalar lastPos = 1 - fFirstPos;
+        int prev = fBegin;
+        SkScalar prevPos = fFirstPos;
+
+        do {
+            const int curr = prev + fAdvance;
+            SkASSERT(curr >= 0 && curr < fCount);
+
+            // TODO: this sanitization should be done in SkGradientShaderBase
+            const SkScalar currPos = (fAdvance > 0)
+                ? SkTPin(fPos[curr], prevPos, lastPos)
+                : SkTPin(fPos[curr], lastPos, prevPos);
+
+            if (currPos != prevPos) {
+                SkASSERT((currPos - prevPos > 0) == (fAdvance > 0));
+                func(fColors[prev], fColors[curr], prevPos, currPos);
+            }
+
+            prev = curr;
+            prevPos = currPos;
+        } while (prev != end);
+    }
+
+private:
+    void iterateImplicitPos(std::function<void(SkColor, SkColor, SkScalar, SkScalar)> func) const {
+        // When clients don't provide explicit color stop positions (fPos == nullptr),
+        // the color stops are distributed evenly across the unit interval
+        // (implicit positioning).
+        const SkScalar dt = fAdvance * SK_Scalar1 / (fCount - 1);
+        const int end = fBegin + fAdvance * (fCount - 2);
+        int prev = fBegin;
+        SkScalar prevPos = fFirstPos;
+
+        while (prev != end) {
+            const int curr = prev + fAdvance;
+            SkASSERT(curr >= 0 && curr < fCount);
+
+            const SkScalar currPos = prevPos + dt;
+            func(fColors[prev], fColors[curr], prevPos, currPos);
+            prev = curr;
+            prevPos = currPos;
+        }
+
+        // emit the last interval with a pinned end position, to avoid precision issues
+        func(fColors[prev], fColors[prev + fAdvance], prevPos, 1 - fFirstPos);
+    }
+
+    const SkColor*  fColors;
+    const SkScalar* fPos;
+    const int       fCount;
+    const SkScalar  fFirstPos;
+    const int       fBegin;
+    const int       fAdvance;
+};
+
 } // anonymous namespace
 
 SkGradientShaderBase::GradientShaderBase4fContext::
@@ -36,11 +134,6 @@ Interval::Interval(SkPMColor c0, SkScalar p0,
     dc4f.store(&fDc.fVec);
 }
 
-bool SkGradientShaderBase::GradientShaderBase4fContext::
-Interval::contains(SkScalar fx) const {
-    return in_range(fx, fP0, fP1);
-}
-
 SkGradientShaderBase::
 GradientShaderBase4fContext::GradientShaderBase4fContext(const SkGradientShaderBase& shader,
                                                          const ContextRec& rec)
@@ -65,3 +158,280 @@ GradientShaderBase4fContext::GradientShaderBase4fContext(const SkGradientShaderB
         (shader.fGradFlags & SkGradientShader::kInterpolateColorsInPremul_Flag)
         || shader.fColorsAreOpaque;
 }
+
+void SkGradientShaderBase::
+GradientShaderBase4fContext::buildIntervals(const SkGradientShaderBase& shader,
+                                            const ContextRec& rec, bool reverse) {
+    // The main job here is to build a specialized interval list: a different
+    // representation of the color stops data, optimized for efficient scan line
+    // access during shading.
+    //
+    //   [{P0,C0} , {P1,C1}) [{P1,C2} , {P2,c3}) ... [{Pn,C2n} , {Pn+1,C2n+1})
+    //
+    // The list may be inverted when requested (such that e.g. points are sorted
+    // in increasing x order when dx < 0).
+    //
+    // Note: the current representation duplicates pos data; we could refactor to
+    //       avoid this if interval storage size becomes a concern.
+    //
+    // Aside from reordering, we also perform two more pre-processing steps at
+    // this stage:
+    //
+    //   1) scale the color components depending on paint alpha and the requested
+    //      interpolation space (note: the interval color storage is SkPM4f, but
+    //      that doesn't necessarily mean the colors are premultiplied; that
+    //      property is tracked in fColorsArePremul)
+    //
+    //   2) inject synthetic intervals to support tiling.
+    //
+    //      * for kRepeat, no extra intervals are needed - the iterator just
+    //        wraps around at the end:
+    //
+    //          ->[P0,P1)->..[Pn-1,Pn)->
+    //
+    //      * for kClamp, we add two "infinite" intervals before/after:
+    //
+    //          [-/+inf , P0)->[P0 , P1)->..[Pn-1 , Pn)->[Pn , +/-inf)
+    //
+    //        (the iterator should never run off the end in this mode)
+    //
+    //      * for kMirror, we extend the range to [0..2] and add a flipped
+    //        interval series - then the iterator operates just as in the
+    //        kRepeat case:
+    //
+    //          ->[P0,P1)->..[Pn-1,Pn)->[2 - Pn,2 - Pn-1)->..[2 - P1,2 - P0)->
+    //
+    // TODO: investigate collapsing intervals << 1px.
+
+    SkASSERT(shader.fColorCount > 0);
+    SkASSERT(shader.fOrigColors);
+
+    const float paintAlpha = rec.fPaint->getAlpha() * (1.0f / 255);
+    const Sk4f componentScale = fColorsArePremul
+        ? Sk4f(paintAlpha)
+        : Sk4f(1.0f, 1.0f, 1.0f, paintAlpha);
+    const int first_index = reverse ? shader.fColorCount - 1 : 0;
+    const int last_index = shader.fColorCount - 1 - first_index;
+    const SkScalar first_pos = reverse ? SK_Scalar1 : 0;
+    const SkScalar last_pos = SK_Scalar1 - first_pos;
+
+    if (shader.fTileMode == SkShader::kClamp_TileMode) {
+        // synthetic edge interval: -/+inf .. P0
+        const SkPMColor clamp_color = pack_color(shader.fOrigColors[first_index],
+                                                 fColorsArePremul);
+        const SkScalar clamp_pos = reverse ? SK_ScalarMax : SK_ScalarMin;
+        fIntervals.emplace_back(clamp_color, clamp_pos,
+                                clamp_color, first_pos,
+                                componentScale);
+    } else if (shader.fTileMode == SkShader::kMirror_TileMode && reverse) {
+        // synthetic mirror intervals injected before main intervals: (2 .. 1]
+        addMirrorIntervals(shader, componentScale, false);
+    }
+
+    const IntervalIterator iter(shader.fOrigColors,
+                                shader.fOrigPos,
+                                shader.fColorCount,
+                                reverse);
+    iter.iterate([this, &componentScale] (SkColor c0, SkColor c1, SkScalar p0, SkScalar p1) {
+        SkASSERT(fIntervals.empty() || fIntervals.back().fP1 == p0);
+
+        fIntervals.emplace_back(pack_color(c0, fColorsArePremul),
+                                p0,
+                                pack_color(c1, fColorsArePremul),
+                                p1,
+                                componentScale);
+    });
+
+    if (shader.fTileMode == SkShader::kClamp_TileMode) {
+        // synthetic edge interval: Pn .. +/-inf
+        const SkPMColor clamp_color =
+            pack_color(shader.fOrigColors[last_index], fColorsArePremul);
+        const SkScalar clamp_pos = reverse ? SK_ScalarMin : SK_ScalarMax;
+        fIntervals.emplace_back(clamp_color, last_pos,
+                                clamp_color, clamp_pos,
+                                componentScale);
+    } else if (shader.fTileMode == SkShader::kMirror_TileMode && !reverse) {
+        // synthetic mirror intervals injected after main intervals: [1 .. 2)
+        addMirrorIntervals(shader, componentScale, true);
+    }
+}
+
+void SkGradientShaderBase::
+GradientShaderBase4fContext::addMirrorIntervals(const SkGradientShaderBase& shader,
+                                            const Sk4f& componentScale, bool reverse) {
+    const IntervalIterator iter(shader.fOrigColors,
+                                shader.fOrigPos,
+                                shader.fColorCount,
+                                reverse);
+    iter.iterate([this, &componentScale] (SkColor c0, SkColor c1, SkScalar p0, SkScalar p1) {
+        SkASSERT(fIntervals.empty() || fIntervals.back().fP1 == 2 - p0);
+
+        fIntervals.emplace_back(pack_color(c0, fColorsArePremul),
+                                2 - p0,
+                                pack_color(c1, fColorsArePremul),
+                                2 - p1,
+                                componentScale);
+    });
+}
+
+void SkGradientShaderBase::
+GradientShaderBase4fContext::shadeSpan(int x, int y, SkPMColor dst[], int count) {
+    if (fColorsArePremul) {

[reed1, 2016/03/10 19:01:12]

This is clearer now, but it is slightly awkward that we pick the boolean
opposite of the predicate here. That said, not sure that I would change
anything, except possibly using an enum instead of a bool for the template
parameter.

[f(malita), 2016/03/10 19:17:19]

Good idea, I'll do that in a follow-up.

+        this->shadePremulSpan<SkPMColor, false>(x, y, dst, count);
+    } else {
+        this->shadePremulSpan<SkPMColor, true>(x, y, dst, count);
+    }
+}
+
+void SkGradientShaderBase::
+GradientShaderBase4fContext::shadeSpan4f(int x, int y, SkPM4f dst[], int count) {
+    if (fColorsArePremul) {
+        this->shadePremulSpan<SkPM4f, false>(x, y, dst, count);
+    } else {
+        this->shadePremulSpan<SkPM4f, true>(x, y, dst, count);
+    }
+}
+
+template<typename DstType, bool do_premul>
+void SkGradientShaderBase::
+GradientShaderBase4fContext::shadePremulSpan(int x, int y,
+                                             DstType dst[],
+                                             int count) const {
+    const SkGradientShaderBase& shader =
+        static_cast<const SkGradientShaderBase&>(fShader);
+
+    switch (shader.fTileMode) {
+    case kClamp_TileMode:
+        this->shadeSpanInternal<DstType,
+                                do_premul,
+                                kClamp_TileMode>(x, y, dst, count);
+        break;
+    case kRepeat_TileMode:
+        this->shadeSpanInternal<DstType,
+                                do_premul,
+                                kRepeat_TileMode>(x, y, dst, count);
+        break;
+    case kMirror_TileMode:
+        this->shadeSpanInternal<DstType,
+                                do_premul,
+                                kMirror_TileMode>(x, y, dst, count);
+        break;
+    }
+}
+
+template<typename DstType, bool do_premul, SkShader::TileMode tileMode>
+void SkGradientShaderBase::
+GradientShaderBase4fContext::shadeSpanInternal(int x, int y,
+                                               DstType dst[],
+                                               int count) const {
+    static const int kBufSize = 128;
+    SkScalar ts[kBufSize];
+    TSampler<DstType, tileMode> sampler(*this);
+
+    SkASSERT(count > 0);
+    do {
+        const int n = SkTMin(kBufSize, count);
+        this->mapTs(x, y, ts, n);
+        for (int i = 0; i < n; ++i) {
+            const Sk4f c = sampler.sample(ts[i]);
+            store<DstType, do_premul>(c, dst++);
+        }
+        x += n;
+        count -= n;
+    } while (count > 0);
+}
+
+template<typename DstType, SkShader::TileMode tileMode>
+class SkGradientShaderBase::GradientShaderBase4fContext::TSampler {
+public:
+    TSampler(const GradientShaderBase4fContext& ctx)
+        : fFirstInterval(ctx.fIntervals.begin())
+        , fLastInterval(ctx.fIntervals.end() - 1)
+        , fInterval(nullptr) {
+        SkASSERT(fLastInterval >= fFirstInterval);
+    }
+
+    Sk4f sample(SkScalar t) {
+        const SkScalar tiled_t = tileProc<tileMode>(t);
+
+        if (!fInterval) {
+            // Very first sample => locate the initial interval.
+            // TODO: maybe do this in ctor to remove a branch?
+            fInterval = this->findFirstInterval(tiled_t);
+            this->loadIntervalData(fInterval);
+        } else if (tiled_t < fInterval->fP0 || tiled_t >= fInterval->fP1) {
+            fInterval = this->findNextInterval(t, tiled_t);
+            this->loadIntervalData(fInterval);
+        }
+
+        fPrevT = t;
+        return lerp(tiled_t);
+    }
+
+private:
+    Sk4f lerp(SkScalar t) {
+        SkASSERT(t >= fInterval->fP0 && t < fInterval->fP1);
+        return fCc + fDc * (t - fInterval->fP0);
+    }
+
+    const Interval* findFirstInterval(SkScalar t) const {
+        // Binary search.
+        const Interval* i0 = fFirstInterval;
+        const Interval* i1 = fLastInterval;
+
+        while (i0 != i1) {
+            SkASSERT(i0 < i1);
+            SkASSERT(t >= i0->fP0 && t < i1->fP1);
+
+            const Interval* i = i0 + ((i1 - i0) >> 1);
+
+            if (t >= i->fP1) {
+                i0 = i + 1;
+            } else {
+                i1 = i;
+            }
+        }
+
+        SkASSERT(t >= i0->fP0 && t <= i0->fP1);
+        return i0;
+    }
+
+    const Interval* findNextInterval(SkScalar t, SkScalar tiled_t) const {
+        SkASSERT(tiled_t < fInterval->fP0 || tiled_t >= fInterval->fP1);
+        SkASSERT(tiled_t >= fFirstInterval->fP0 && tiled_t < fLastInterval->fP1);
+
+        const Interval* i = fInterval;
+
+        // Use the t vs. prev_t signal to figure which direction we should search for
+        // the next interval, then perform a linear search.
+        if (t >= fPrevT) {
+            do {
+                i += 1;
+                if (i > fLastInterval) {
+                    i = fFirstInterval;
+                }
+            } while (tiled_t < i->fP0 || tiled_t >= i->fP1);
+        } else {
+            do {
+                i -= 1;
+                if (i < fFirstInterval) {
+                    i = fLastInterval;
+                }
+            } while (tiled_t < i->fP0 || tiled_t >= i->fP1);
+        }
+
+        return i;
+    }
+
+    void loadIntervalData(const Interval* i) {
+        fCc = dst_swizzle<DstType>(i->fC0) * dst_component_scale<DstType>();
+        fDc = dst_swizzle<DstType>(i->fDc) * dst_component_scale<DstType>();
+    }
+
+    const Interval* fFirstInterval;
+    const Interval* fLastInterval;
+    const Interval* fInterval;
+    SkScalar        fPrevT;
+    Sk4f            fCc;
+    Sk4f            fDc;
+};