1/*
2 * Copyright 2016 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "include/core/SkPaint.h"
9#include "include/private/SkTPin.h"
10#include "src/shaders/gradients/Sk4fLinearGradient.h"
11
12#include <cmath>
13#include <utility>
14
15namespace {
16
17template<ApplyPremul premul>
18void ramp(const Sk4f& c, const Sk4f& dc, SkPMColor dst[], int n,
19          const Sk4f& bias0, const Sk4f& bias1) {
20    SkASSERT(n > 0);
21
22    const Sk4f dc2 = dc + dc,
23               dc4 = dc2 + dc2;
24
25    Sk4f c0 =  c +      DstTraits<premul>::pre_lerp_bias(bias0),
26         c1 =  c + dc + DstTraits<premul>::pre_lerp_bias(bias1),
27         c2 = c0 + dc2,
28         c3 = c1 + dc2;
29
30    while (n >= 4) {
31        DstTraits<premul>::store4x(c0, c1, c2, c3, dst, bias0, bias1);
32        dst += 4;
33
34        c0 = c0 + dc4;
35        c1 = c1 + dc4;
36        c2 = c2 + dc4;
37        c3 = c3 + dc4;
38        n -= 4;
39    }
40    if (n & 2) {
41        DstTraits<premul>::store(c0, dst++, bias0);
42        DstTraits<premul>::store(c1, dst++, bias1);
43        c0 = c0 + dc2;
44    }
45    if (n & 1) {
46        DstTraits<premul>::store(c0, dst, bias0);
47    }
48}
49
50template<SkTileMode>
51SkScalar pinFx(SkScalar);
52
53template<>
54SkScalar pinFx<SkTileMode::kClamp>(SkScalar fx) {
55    return fx;
56}
57
58template<>
59SkScalar pinFx<SkTileMode::kRepeat>(SkScalar fx) {
60    SkScalar f = SkScalarIsFinite(fx) ? SkScalarFraction(fx) : 0;
61    if (f < 0) {
62        f = std::min(f + 1, nextafterf(1, 0));
63    }
64    SkASSERT(f >= 0);
65    SkASSERT(f < 1.0f);
66    return f;
67}
68
69template<>
70SkScalar pinFx<SkTileMode::kMirror>(SkScalar fx) {
71    SkScalar f = SkScalarIsFinite(fx) ? SkScalarMod(fx, 2.0f) : 0;
72    if (f < 0) {
73        f = std::min(f + 2, nextafterf(2, 0));
74    }
75    SkASSERT(f >= 0);
76    SkASSERT(f < 2.0f);
77    return f;
78}
79
80// true when x is in [k1,k2], or [k2, k1] when the interval is reversed.
81// TODO(fmalita): hoist the reversed interval check out of this helper.
82bool in_range(SkScalar x, SkScalar k1, SkScalar k2) {
83    SkASSERT(k1 != k2);
84    return (k1 < k2)
85        ? (x >= k1 && x <= k2)
86        : (x >= k2 && x <= k1);
87}
88
89} // anonymous namespace
90
91SkLinearGradient::
92LinearGradient4fContext::LinearGradient4fContext(const SkLinearGradient& shader,
93                                                 const ContextRec& rec)
94    : INHERITED(shader, rec) {
95
96    // Our fast path expects interval points to be monotonically increasing in x.
97    const bool reverseIntervals = std::signbit(fDstToPos.getScaleX());
98    fIntervals.init(shader, rec.fDstColorSpace, shader.fTileMode,
99                    fColorsArePremul, rec.fPaintAlpha * (1.0f / 255), reverseIntervals);
100
101    SkASSERT(fIntervals->count() > 0);
102    fCachedInterval = fIntervals->begin();
103}
104
105const Sk4fGradientInterval*
106SkLinearGradient::LinearGradient4fContext::findInterval(SkScalar fx) const {
107    SkASSERT(in_range(fx, fIntervals->front().fT0, fIntervals->back().fT1));
108
109    if (1) {
110        // Linear search, using the last scanline interval as a starting point.
111        SkASSERT(fCachedInterval >= fIntervals->begin());
112        SkASSERT(fCachedInterval < fIntervals->end());
113        const int search_dir = fDstToPos.getScaleX() >= 0 ? 1 : -1;
114        while (!in_range(fx, fCachedInterval->fT0, fCachedInterval->fT1)) {
115            fCachedInterval += search_dir;
116            if (fCachedInterval >= fIntervals->end()) {
117                fCachedInterval = fIntervals->begin();
118            } else if (fCachedInterval < fIntervals->begin()) {
119                fCachedInterval = fIntervals->end() - 1;
120            }
121        }
122        return fCachedInterval;
123    } else {
124        // Binary search.  Seems less effective than linear + caching.
125        const auto* i0 = fIntervals->begin();
126        const auto* i1 = fIntervals->end() - 1;
127
128        while (i0 != i1) {
129            SkASSERT(i0 < i1);
130            SkASSERT(in_range(fx, i0->fT0, i1->fT1));
131
132            const auto* i = i0 + ((i1 - i0) >> 1);
133
134            if (in_range(fx, i0->fT0, i->fT1)) {
135                i1 = i;
136            } else {
137                SkASSERT(in_range(fx, i->fT1, i1->fT1));
138                i0 = i + 1;
139            }
140        }
141
142        SkASSERT(in_range(fx, i0->fT0, i0->fT1));
143        return i0;
144    }
145}
146
147
148void SkLinearGradient::
149LinearGradient4fContext::shadeSpan(int x, int y, SkPMColor dst[], int count) {
150    SkASSERT(count > 0);
151
152    float bias0 = 0,
153          bias1 = 0;
154
155    if (fDither) {
156        static constexpr float dither_cell[] = {
157            -3/8.0f,  1/8.0f,
158             3/8.0f, -1/8.0f,
159        };
160
161        const int rowIndex = (y & 1) << 1;
162        bias0 = dither_cell[rowIndex + 0];
163        bias1 = dither_cell[rowIndex + 1];
164
165        if (x & 1) {
166            using std::swap;
167            swap(bias0, bias1);
168        }
169    }
170
171    if (fColorsArePremul) {
172        // In premul interpolation mode, components are pre-scaled by 255 and the store
173        // op is truncating. We pre-bias here to achieve rounding.
174        bias0 += 0.5f;
175        bias1 += 0.5f;
176
177        this->shadePremulSpan<ApplyPremul::False>(x, y, dst, count, bias0, bias1);
178    } else {
179        // In unpremul interpolation mode, Components are not pre-scaled.
180        bias0 *= 1/255.0f;
181        bias1 *= 1/255.0f;
182
183        this->shadePremulSpan<ApplyPremul::True >(x, y, dst, count, bias0, bias1);
184    }
185}
186
187template<ApplyPremul premul>
188void SkLinearGradient::
189LinearGradient4fContext::shadePremulSpan(int x, int y, SkPMColor dst[], int count,
190                                         float bias0, float bias1) const {
191    const SkLinearGradient& shader = static_cast<const SkLinearGradient&>(fShader);
192    switch (shader.fTileMode) {
193        case SkTileMode::kDecal:
194            SkASSERT(false);    // decal only supported via stages
195            [[fallthrough]];
196        case SkTileMode::kClamp:
197            this->shadeSpanInternal<premul, SkTileMode::kClamp >(x, y, dst, count, bias0, bias1);
198            break;
199        case SkTileMode::kRepeat:
200            this->shadeSpanInternal<premul, SkTileMode::kRepeat>(x, y, dst, count, bias0, bias1);
201            break;
202        case SkTileMode::kMirror:
203            this->shadeSpanInternal<premul, SkTileMode::kMirror>(x, y, dst, count, bias0, bias1);
204            break;
205    }
206}
207
208template<ApplyPremul premul, SkTileMode tileMode>
209void SkLinearGradient::
210LinearGradient4fContext::shadeSpanInternal(int x, int y, SkPMColor dst[], int count,
211                                           float bias0, float bias1) const {
212    SkPoint pt;
213    fDstToPosProc(fDstToPos,
214                  x + SK_ScalarHalf,
215                  y + SK_ScalarHalf,
216                  &pt);
217    const SkScalar fx = pinFx<tileMode>(pt.x());
218    const SkScalar dx = fDstToPos.getScaleX();
219    LinearIntervalProcessor<premul, tileMode> proc(fIntervals->begin(),
220                                                   fIntervals->end() - 1,
221                                                   this->findInterval(fx),
222                                                   fx,
223                                                   dx,
224                                                   SkScalarNearlyZero(dx * count));
225    Sk4f bias4f0(bias0),
226         bias4f1(bias1);
227
228    while (count > 0) {
229        // What we really want here is SkTPin(advance, 1, count)
230        // but that's a significant perf hit for >> stops; investigate.
231        const int n = std::min(SkScalarTruncToInt(proc.currentAdvance() + 1), count);
232
233        // The current interval advance can be +inf (e.g. when reaching
234        // the clamp mode end intervals) - when that happens, we expect to
235        //   a) consume all remaining count in one swoop
236        //   b) return a zero color gradient
237        SkASSERT(SkScalarIsFinite(proc.currentAdvance())
238            || (n == count && proc.currentRampIsZero()));
239
240        if (proc.currentRampIsZero()) {
241            DstTraits<premul>::store(proc.currentColor(), dst, n);
242        } else {
243            ramp<premul>(proc.currentColor(), proc.currentColorGrad(), dst, n,
244                         bias4f0, bias4f1);
245        }
246
247        proc.advance(SkIntToScalar(n));
248        count -= n;
249        dst   += n;
250
251        if (n & 1) {
252            using std::swap;
253            swap(bias4f0, bias4f1);
254        }
255    }
256}
257
258template<ApplyPremul premul, SkTileMode tileMode>
259class SkLinearGradient::
260LinearGradient4fContext::LinearIntervalProcessor {
261public:
262    LinearIntervalProcessor(const Sk4fGradientInterval* firstInterval,
263                            const Sk4fGradientInterval* lastInterval,
264                            const Sk4fGradientInterval* i,
265                            SkScalar fx,
266                            SkScalar dx,
267                            bool is_vertical)
268        : fAdvX(is_vertical ? SK_ScalarInfinity : (i->fT1 - fx) / dx)
269        , fFirstInterval(firstInterval)
270        , fLastInterval(lastInterval)
271        , fInterval(i)
272        , fDx(dx)
273        , fIsVertical(is_vertical)
274    {
275        SkASSERT(fAdvX >= 0);
276        SkASSERT(firstInterval <= lastInterval);
277
278        if (tileMode != SkTileMode::kClamp && !is_vertical) {
279            const auto spanX = (lastInterval->fT1 - firstInterval->fT0) / dx;
280            SkASSERT(spanX >= 0);
281
282            // If we're in a repeating tile mode and the whole gradient is compressed into a
283            // fraction of a pixel, we just use the average color in zero-ramp mode.
284            // This also avoids cases where we make no progress due to interval advances being
285            // close to zero.
286            static constexpr SkScalar kMinSpanX = .25f;
287            if (spanX < kMinSpanX) {
288                this->init_average_props();
289                return;
290            }
291        }
292
293        this->compute_interval_props(fx);
294    }
295
296    SkScalar currentAdvance() const {
297        SkASSERT(fAdvX >= 0);
298        SkASSERT(!std::isfinite(fAdvX) || fAdvX <= (fInterval->fT1 - fInterval->fT0) / fDx);
299        return fAdvX;
300    }
301
302    bool currentRampIsZero() const { return fZeroRamp; }
303    const Sk4f& currentColor() const { return fCc; }
304    const Sk4f& currentColorGrad() const { return fDcDx; }
305
306    void advance(SkScalar advX) {
307        SkASSERT(advX > 0);
308        SkASSERT(fAdvX >= 0);
309
310        if (advX >= fAdvX) {
311            advX = this->advance_interval(advX);
312        }
313        SkASSERT(advX < fAdvX);
314
315        fCc = fCc + fDcDx * Sk4f(advX);
316        fAdvX -= advX;
317    }
318
319private:
320    void compute_interval_props(SkScalar t) {
321        SkASSERT(in_range(t, fInterval->fT0, fInterval->fT1));
322
323        const Sk4f dc = DstTraits<premul>::load(fInterval->fCg);
324                  fCc = DstTraits<premul>::load(fInterval->fCb) + dc * Sk4f(t);
325                fDcDx = dc * fDx;
326            fZeroRamp = fIsVertical || (dc == 0).allTrue();
327    }
328
329    void init_average_props() {
330        fAdvX     = SK_ScalarInfinity;
331        fZeroRamp = true;
332        fDcDx     = 0;
333        fCc       = Sk4f(0);
334
335        // TODO: precompute the average at interval setup time?
336        for (const auto* i = fFirstInterval; i <= fLastInterval; ++i) {
337            // Each interval contributes its average color to the total/weighted average:
338            //
339            //   C = (c0 + c1) / 2 = (Cb + Cg * t0 + Cb + Cg * t1) / 2 = Cb + Cg *(t0 + t1) / 2
340            //
341            //   Avg += C * (t1 - t0)
342            //
343            const auto c = DstTraits<premul>::load(i->fCb)
344                         + DstTraits<premul>::load(i->fCg) * (i->fT0 + i->fT1) * 0.5f;
345            fCc = fCc + c * (i->fT1 - i->fT0);
346        }
347    }
348
349    const Sk4fGradientInterval* next_interval(const Sk4fGradientInterval* i) const {
350        SkASSERT(i >= fFirstInterval);
351        SkASSERT(i <= fLastInterval);
352        i++;
353
354        if (tileMode == SkTileMode::kClamp) {
355            SkASSERT(i <= fLastInterval);
356            return i;
357        }
358
359        return (i <= fLastInterval) ? i : fFirstInterval;
360    }
361
362    SkScalar advance_interval(SkScalar advX) {
363        SkASSERT(advX >= fAdvX);
364
365        do {
366            advX -= fAdvX;
367            fInterval = this->next_interval(fInterval);
368            fAdvX = (fInterval->fT1 - fInterval->fT0) / fDx;
369            SkASSERT(fAdvX >= 0); // fT1 must be bigger than fT0 but fAdvX can underflow.
370        } while (advX >= fAdvX);
371
372        compute_interval_props(fInterval->fT0);
373
374        SkASSERT(advX >= 0);
375        return advX;
376    }
377
378    // Current interval properties.
379    Sk4f            fDcDx;      // dst color gradient (dc/dx)
380    Sk4f            fCc;        // current color, interpolated in dst
381    SkScalar        fAdvX;      // remaining interval advance in dst
382    bool            fZeroRamp;  // current interval color grad is 0
383
384    const Sk4fGradientInterval* fFirstInterval;
385    const Sk4fGradientInterval* fLastInterval;
386    const Sk4fGradientInterval* fInterval;  // current interval
387    const SkScalar              fDx;        // 'dx' for consistency with other impls; actually dt/dx
388    const bool                  fIsVertical;
389};
390