1
2/*
3 * Copyright 2012 Google Inc.
4 *
5 * Use of this source code is governed by a BSD-style license that can be
6 * found in the LICENSE file.
7 */
8
9#include "SkSweepGradient.h"
10
11SkSweepGradient::SkSweepGradient(SkScalar cx, SkScalar cy,
12                                 const Descriptor& desc)
13    : SkGradientShaderBase(desc)
14    , fCenter(SkPoint::Make(cx, cy))
15{
16    fPtsToUnit.setTranslate(-cx, -cy);
17
18    // overwrite the tilemode to a canonical value (since sweep ignores it)
19    fTileMode = SkShader::kClamp_TileMode;
20}
21
22SkShader::BitmapType SkSweepGradient::asABitmap(SkBitmap* bitmap,
23    SkMatrix* matrix, SkShader::TileMode* xy) const {
24    if (bitmap) {
25        this->getGradientTableBitmap(bitmap);
26    }
27    if (matrix) {
28        *matrix = fPtsToUnit;
29    }
30    if (xy) {
31        xy[0] = fTileMode;
32        xy[1] = kClamp_TileMode;
33    }
34    return kSweep_BitmapType;
35}
36
37SkShader::GradientType SkSweepGradient::asAGradient(GradientInfo* info) const {
38    if (info) {
39        commonAsAGradient(info);
40        info->fPoint[0] = fCenter;
41    }
42    return kSweep_GradientType;
43}
44
45SkSweepGradient::SkSweepGradient(SkFlattenableReadBuffer& buffer)
46    : INHERITED(buffer),
47      fCenter(buffer.readPoint()) {
48}
49
50void SkSweepGradient::flatten(SkFlattenableWriteBuffer& buffer) const {
51    this->INHERITED::flatten(buffer);
52    buffer.writePoint(fCenter);
53}
54
55#ifndef SK_SCALAR_IS_FLOAT
56#ifdef COMPUTE_SWEEP_TABLE
57#define PI  3.14159265
58static bool gSweepTableReady;
59static uint8_t gSweepTable[65];
60
61/*  Our table stores precomputed values for atan: [0...1] -> [0..PI/4]
62    We scale the results to [0..32]
63*/
64static const uint8_t* build_sweep_table() {
65    if (!gSweepTableReady) {
66        const int N = 65;
67        const double DENOM = N - 1;
68
69        for (int i = 0; i < N; i++)
70        {
71            double arg = i / DENOM;
72            double v = atan(arg);
73            int iv = (int)round(v * DENOM * 2 / PI);
74//            printf("[%d] atan(%g) = %g %d\n", i, arg, v, iv);
75            printf("%d, ", iv);
76            gSweepTable[i] = iv;
77        }
78        gSweepTableReady = true;
79    }
80    return gSweepTable;
81}
82#else
83static const uint8_t gSweepTable[] = {
84    0, 1, 1, 2, 3, 3, 4, 4, 5, 6, 6, 7, 8, 8, 9, 9,
85    10, 11, 11, 12, 12, 13, 13, 14, 15, 15, 16, 16, 17, 17, 18, 18,
86    19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24, 25, 25, 25, 26,
87    26, 27, 27, 27, 28, 28, 29, 29, 29, 30, 30, 30, 31, 31, 31, 32,
88    32
89};
90static const uint8_t* build_sweep_table() { return gSweepTable; }
91#endif
92#endif
93
94// divide numer/denom, with a bias of 6bits. Assumes numer <= denom
95// and denom != 0. Since our table is 6bits big (+1), this is a nice fit.
96// Same as (but faster than) SkFixedDiv(numer, denom) >> 10
97
98//unsigned div_64(int numer, int denom);
99#ifndef SK_SCALAR_IS_FLOAT
100static unsigned div_64(int numer, int denom) {
101    SkASSERT(numer <= denom);
102    SkASSERT(numer > 0);
103    SkASSERT(denom > 0);
104
105    int nbits = SkCLZ(numer);
106    int dbits = SkCLZ(denom);
107    int bits = 6 - nbits + dbits;
108    SkASSERT(bits <= 6);
109
110    if (bits < 0) {  // detect underflow
111        return 0;
112    }
113
114    denom <<= dbits - 1;
115    numer <<= nbits - 1;
116
117    unsigned result = 0;
118
119    // do the first one
120    if ((numer -= denom) >= 0) {
121        result = 1;
122    } else {
123        numer += denom;
124    }
125
126    // Now fall into our switch statement if there are more bits to compute
127    if (bits > 0) {
128        // make room for the rest of the answer bits
129        result <<= bits;
130        switch (bits) {
131        case 6:
132            if ((numer = (numer << 1) - denom) >= 0)
133                result |= 32;
134            else
135                numer += denom;
136        case 5:
137            if ((numer = (numer << 1) - denom) >= 0)
138                result |= 16;
139            else
140                numer += denom;
141        case 4:
142            if ((numer = (numer << 1) - denom) >= 0)
143                result |= 8;
144            else
145                numer += denom;
146        case 3:
147            if ((numer = (numer << 1) - denom) >= 0)
148                result |= 4;
149            else
150                numer += denom;
151        case 2:
152            if ((numer = (numer << 1) - denom) >= 0)
153                result |= 2;
154            else
155                numer += denom;
156        case 1:
157        default:    // not strictly need, but makes GCC make better ARM code
158            if ((numer = (numer << 1) - denom) >= 0)
159                result |= 1;
160            else
161                numer += denom;
162        }
163    }
164    return result;
165}
166#endif
167
168// Given x,y in the first quadrant, return 0..63 for the angle [0..90]
169#ifndef SK_SCALAR_IS_FLOAT
170static unsigned atan_0_90(SkFixed y, SkFixed x) {
171#ifdef SK_DEBUG
172    {
173        static bool gOnce;
174        if (!gOnce) {
175            gOnce = true;
176            SkASSERT(div_64(55, 55) == 64);
177            SkASSERT(div_64(128, 256) == 32);
178            SkASSERT(div_64(2326528, 4685824) == 31);
179            SkASSERT(div_64(753664, 5210112) == 9);
180            SkASSERT(div_64(229376, 4882432) == 3);
181            SkASSERT(div_64(2, 64) == 2);
182            SkASSERT(div_64(1, 64) == 1);
183            // test that we handle underflow correctly
184            SkASSERT(div_64(12345, 0x54321234) == 0);
185        }
186    }
187#endif
188
189    SkASSERT(y > 0 && x > 0);
190    const uint8_t* table = build_sweep_table();
191
192    unsigned result;
193    bool swap = (x < y);
194    if (swap) {
195        // first part of the atan(v) = PI/2 - atan(1/v) identity
196        // since our div_64 and table want v <= 1, where v = y/x
197        SkTSwap<SkFixed>(x, y);
198    }
199
200    result = div_64(y, x);
201
202#ifdef SK_DEBUG
203    {
204        unsigned result2 = SkDivBits(y, x, 6);
205        SkASSERT(result2 == result ||
206                 (result == 1 && result2 == 0));
207    }
208#endif
209
210    SkASSERT(result < SK_ARRAY_COUNT(gSweepTable));
211    result = table[result];
212
213    if (swap) {
214        // complete the atan(v) = PI/2 - atan(1/v) identity
215        result = 64 - result;
216        // pin to 63
217        result -= result >> 6;
218    }
219
220    SkASSERT(result <= 63);
221    return result;
222}
223#endif
224
225//  returns angle in a circle [0..2PI) -> [0..255]
226#ifdef SK_SCALAR_IS_FLOAT
227static unsigned SkATan2_255(float y, float x) {
228    //    static const float g255Over2PI = 255 / (2 * SK_ScalarPI);
229    static const float g255Over2PI = 40.584510488433314f;
230
231    float result = sk_float_atan2(y, x);
232    if (result < 0) {
233        result += 2 * SK_ScalarPI;
234    }
235    SkASSERT(result >= 0);
236    // since our value is always >= 0, we can cast to int, which is faster than
237    // calling floorf()
238    int ir = (int)(result * g255Over2PI);
239    SkASSERT(ir >= 0 && ir <= 255);
240    return ir;
241}
242#else
243static unsigned SkATan2_255(SkFixed y, SkFixed x) {
244    if (x == 0) {
245        if (y == 0) {
246            return 0;
247        }
248        return y < 0 ? 192 : 64;
249    }
250    if (y == 0) {
251        return x < 0 ? 128 : 0;
252    }
253
254    /*  Find the right quadrant for x,y
255        Since atan_0_90 only handles the first quadrant, we rotate x,y
256        appropriately before calling it, and then add the right amount
257        to account for the real quadrant.
258        quadrant 0 : add 0                  | x > 0 && y > 0
259        quadrant 1 : add 64 (90 degrees)    | x < 0 && y > 0
260        quadrant 2 : add 128 (180 degrees)  | x < 0 && y < 0
261        quadrant 3 : add 192 (270 degrees)  | x > 0 && y < 0
262
263        map x<0 to (1 << 6)
264        map y<0 to (3 << 6)
265        add = map_x ^ map_y
266    */
267    int xsign = x >> 31;
268    int ysign = y >> 31;
269    int add = ((-xsign) ^ (ysign & 3)) << 6;
270
271#ifdef SK_DEBUG
272    if (0 == add)
273        SkASSERT(x > 0 && y > 0);
274    else if (64 == add)
275        SkASSERT(x < 0 && y > 0);
276    else if (128 == add)
277        SkASSERT(x < 0 && y < 0);
278    else if (192 == add)
279        SkASSERT(x > 0 && y < 0);
280    else
281        SkDEBUGFAIL("bad value for add");
282#endif
283
284    /*  This ^ trick makes x, y positive, and the swap<> handles quadrants
285        where we need to rotate x,y by 90 or -90
286    */
287    x = (x ^ xsign) - xsign;
288    y = (y ^ ysign) - ysign;
289    if (add & 64) {             // quads 1 or 3 need to swap x,y
290        SkTSwap<SkFixed>(x, y);
291    }
292
293    unsigned result = add + atan_0_90(y, x);
294    SkASSERT(result < 256);
295    return result;
296}
297#endif
298
299void SkSweepGradient::shadeSpan(int x, int y, SkPMColor* SK_RESTRICT dstC,
300                               int count) {
301    SkMatrix::MapXYProc proc = fDstToIndexProc;
302    const SkMatrix&     matrix = fDstToIndex;
303    const SkPMColor* SK_RESTRICT cache = this->getCache32();
304    int                 toggle = init_dither_toggle(x, y);
305    SkPoint             srcPt;
306
307    if (fDstToIndexClass != kPerspective_MatrixClass) {
308        proc(matrix, SkIntToScalar(x) + SK_ScalarHalf,
309                     SkIntToScalar(y) + SK_ScalarHalf, &srcPt);
310        SkScalar dx, fx = srcPt.fX;
311        SkScalar dy, fy = srcPt.fY;
312
313        if (fDstToIndexClass == kFixedStepInX_MatrixClass) {
314            SkFixed storage[2];
315            (void)matrix.fixedStepInX(SkIntToScalar(y) + SK_ScalarHalf,
316                                      &storage[0], &storage[1]);
317            dx = SkFixedToScalar(storage[0]);
318            dy = SkFixedToScalar(storage[1]);
319        } else {
320            SkASSERT(fDstToIndexClass == kLinear_MatrixClass);
321            dx = matrix.getScaleX();
322            dy = matrix.getSkewY();
323        }
324
325        for (; count > 0; --count) {
326            *dstC++ = cache[toggle + SkATan2_255(fy, fx)];
327            fx += dx;
328            fy += dy;
329            toggle = next_dither_toggle(toggle);
330        }
331    } else {  // perspective case
332        for (int stop = x + count; x < stop; x++) {
333            proc(matrix, SkIntToScalar(x) + SK_ScalarHalf,
334                         SkIntToScalar(y) + SK_ScalarHalf, &srcPt);
335            *dstC++ = cache[toggle + SkATan2_255(srcPt.fY, srcPt.fX)];
336            toggle = next_dither_toggle(toggle);
337        }
338    }
339}
340
341void SkSweepGradient::shadeSpan16(int x, int y, uint16_t* SK_RESTRICT dstC,
342                                 int count) {
343    SkMatrix::MapXYProc proc = fDstToIndexProc;
344    const SkMatrix&     matrix = fDstToIndex;
345    const uint16_t* SK_RESTRICT cache = this->getCache16();
346    int                 toggle = init_dither_toggle16(x, y);
347    SkPoint             srcPt;
348
349    if (fDstToIndexClass != kPerspective_MatrixClass) {
350        proc(matrix, SkIntToScalar(x) + SK_ScalarHalf,
351                     SkIntToScalar(y) + SK_ScalarHalf, &srcPt);
352        SkScalar dx, fx = srcPt.fX;
353        SkScalar dy, fy = srcPt.fY;
354
355        if (fDstToIndexClass == kFixedStepInX_MatrixClass) {
356            SkFixed storage[2];
357            (void)matrix.fixedStepInX(SkIntToScalar(y) + SK_ScalarHalf,
358                                      &storage[0], &storage[1]);
359            dx = SkFixedToScalar(storage[0]);
360            dy = SkFixedToScalar(storage[1]);
361        } else {
362            SkASSERT(fDstToIndexClass == kLinear_MatrixClass);
363            dx = matrix.getScaleX();
364            dy = matrix.getSkewY();
365        }
366
367        for (; count > 0; --count) {
368            int index = SkATan2_255(fy, fx) >> (8 - kCache16Bits);
369            *dstC++ = cache[toggle + index];
370            toggle = next_dither_toggle16(toggle);
371            fx += dx;
372            fy += dy;
373        }
374    } else {  // perspective case
375        for (int stop = x + count; x < stop; x++) {
376            proc(matrix, SkIntToScalar(x) + SK_ScalarHalf,
377                         SkIntToScalar(y) + SK_ScalarHalf, &srcPt);
378
379            int index = SkATan2_255(srcPt.fY, srcPt.fX);
380            index >>= (8 - kCache16Bits);
381            *dstC++ = cache[toggle + index];
382            toggle = next_dither_toggle16(toggle);
383        }
384    }
385}
386
387/////////////////////////////////////////////////////////////////////
388
389#if SK_SUPPORT_GPU
390
391#include "GrTBackendEffectFactory.h"
392
393class GrGLSweepGradient : public GrGLGradientEffect {
394public:
395
396    GrGLSweepGradient(const GrBackendEffectFactory& factory,
397                      const GrDrawEffect&) : INHERITED (factory) { }
398    virtual ~GrGLSweepGradient() { }
399
400    virtual void emitCode(GrGLShaderBuilder*,
401                          const GrDrawEffect&,
402                          EffectKey,
403                          const char* outputColor,
404                          const char* inputColor,
405                          const TransformedCoordsArray&,
406                          const TextureSamplerArray&) SK_OVERRIDE;
407
408    static EffectKey GenKey(const GrDrawEffect& drawEffect, const GrGLCaps&) {
409        return GenBaseGradientKey(drawEffect);
410    }
411
412private:
413
414    typedef GrGLGradientEffect INHERITED;
415
416};
417
418/////////////////////////////////////////////////////////////////////
419
420class GrSweepGradient : public GrGradientEffect {
421public:
422    static GrEffectRef* Create(GrContext* ctx,
423                               const SkSweepGradient& shader,
424                               const SkMatrix& matrix) {
425        AutoEffectUnref effect(SkNEW_ARGS(GrSweepGradient, (ctx, shader, matrix)));
426        return CreateEffectRef(effect);
427    }
428    virtual ~GrSweepGradient() { }
429
430    static const char* Name() { return "Sweep Gradient"; }
431    virtual const GrBackendEffectFactory& getFactory() const SK_OVERRIDE {
432        return GrTBackendEffectFactory<GrSweepGradient>::getInstance();
433    }
434
435    typedef GrGLSweepGradient GLEffect;
436
437private:
438    GrSweepGradient(GrContext* ctx,
439                    const SkSweepGradient& shader,
440                    const SkMatrix& matrix)
441    : INHERITED(ctx, shader, matrix, SkShader::kClamp_TileMode) { }
442    GR_DECLARE_EFFECT_TEST;
443
444    typedef GrGradientEffect INHERITED;
445};
446
447/////////////////////////////////////////////////////////////////////
448
449GR_DEFINE_EFFECT_TEST(GrSweepGradient);
450
451GrEffectRef* GrSweepGradient::TestCreate(SkRandom* random,
452                                         GrContext* context,
453                                         const GrDrawTargetCaps&,
454                                         GrTexture**) {
455    SkPoint center = {random->nextUScalar1(), random->nextUScalar1()};
456
457    SkColor colors[kMaxRandomGradientColors];
458    SkScalar stopsArray[kMaxRandomGradientColors];
459    SkScalar* stops = stopsArray;
460    SkShader::TileMode tmIgnored;
461    int colorCount = RandomGradientParams(random, colors, &stops, &tmIgnored);
462    SkAutoTUnref<SkShader> shader(SkGradientShader::CreateSweep(center.fX, center.fY,
463                                                                colors, stops, colorCount));
464    SkPaint paint;
465    return shader->asNewEffect(context, paint);
466}
467
468/////////////////////////////////////////////////////////////////////
469
470void GrGLSweepGradient::emitCode(GrGLShaderBuilder* builder,
471                                 const GrDrawEffect&,
472                                 EffectKey key,
473                                 const char* outputColor,
474                                 const char* inputColor,
475                                 const TransformedCoordsArray& coords,
476                                 const TextureSamplerArray& samplers) {
477    this->emitUniforms(builder, key);
478    SkString coords2D = builder->ensureFSCoords2D(coords, 0);
479    SkString t;
480    t.printf("atan(- %s.y, - %s.x) * 0.1591549430918 + 0.5", coords2D.c_str(), coords2D.c_str());
481    this->emitColor(builder, t.c_str(), key,
482                          outputColor, inputColor, samplers);
483}
484
485/////////////////////////////////////////////////////////////////////
486
487GrEffectRef* SkSweepGradient::asNewEffect(GrContext* context, const SkPaint&) const {
488    SkMatrix matrix;
489    if (!this->getLocalMatrix().invert(&matrix)) {
490        return NULL;
491    }
492    matrix.postConcat(fPtsToUnit);
493    return GrSweepGradient::Create(context, *this, matrix);
494}
495
496#else
497
498GrEffectRef* SkSweepGradient::asNewEffect(GrContext*, const SkPaint&) const {
499    SkDEBUGFAIL("Should not call in GPU-less build");
500    return NULL;
501}
502
503#endif
504
505#ifdef SK_DEVELOPER
506void SkSweepGradient::toString(SkString* str) const {
507    str->append("SkSweepGradient: (");
508
509    str->append("center: (");
510    str->appendScalar(fCenter.fX);
511    str->append(", ");
512    str->appendScalar(fCenter.fY);
513    str->append(") ");
514
515    this->INHERITED::toString(str);
516
517    str->append(")");
518}
519#endif
520