1/*
2 * Copyright 2006 The Android Open Source Project
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
9#include "include/core/SkPathMeasure.h"
10#include "include/core/SkStrokeRec.h"
11#include "include/effects/SkDiscretePathEffect.h"
12#include "include/private/SkFixed.h"
13#include "src/core/SkPathEffectBase.h"
14#include "src/core/SkPointPriv.h"
15#include "src/core/SkReadBuffer.h"
16#include "src/core/SkWriteBuffer.h"
17
18/** \class LCGRandom
19
20    Utility class that implements pseudo random 32bit numbers using a fast
21    linear equation. Unlike rand(), this class holds its own seed (initially
22    set to 0), so that multiple instances can be used with no side-effects.
23
24    Copied from the original implementation of SkRandom. Only contains the
25    methods used by SkDiscretePathEffect::filterPath, with methods that were
26    not called directly moved to private.
27*/
28class LCGRandom {
29public:
30    LCGRandom(uint32_t seed) : fSeed(seed) {}
31
32    /** Return the next pseudo random number expressed as a SkScalar
33        in the range [-SK_Scalar1..SK_Scalar1).
34    */
35    SkScalar nextSScalar1() { return SkFixedToScalar(this->nextSFixed1()); }
36
37private:
38    /** Return the next pseudo random number as an unsigned 32bit value.
39    */
40    uint32_t nextU() { uint32_t r = fSeed * kMul + kAdd; fSeed = r; return r; }
41
42    /** Return the next pseudo random number as a signed 32bit value.
43     */
44    int32_t nextS() { return (int32_t)this->nextU(); }
45
46    /** Return the next pseudo random number expressed as a signed SkFixed
47     in the range [-SK_Fixed1..SK_Fixed1).
48     */
49    SkFixed nextSFixed1() { return this->nextS() >> 15; }
50
51    //  See "Numerical Recipes in C", 1992 page 284 for these constants
52    enum {
53        kMul = 1664525,
54        kAdd = 1013904223
55    };
56    uint32_t fSeed;
57};
58
59static void Perterb(SkPoint* p, const SkVector& tangent, SkScalar scale) {
60    SkVector normal = tangent;
61    SkPointPriv::RotateCCW(&normal);
62    normal.setLength(scale);
63    *p += normal;
64}
65
66class SK_API SkDiscretePathEffectImpl : public SkPathEffectBase {
67public:
68    SkDiscretePathEffectImpl(SkScalar segLength, SkScalar deviation, uint32_t seedAssist)
69        : fSegLength(segLength), fPerterb(deviation), fSeedAssist(seedAssist)
70    {
71        SkASSERT(SkScalarIsFinite(segLength));
72        SkASSERT(SkScalarIsFinite(deviation));
73        SkASSERT(segLength > SK_ScalarNearlyZero);
74    }
75
76    bool onFilterPath(SkPath* dst, const SkPath& src, SkStrokeRec* rec,
77                      const SkRect*, const SkMatrix&) const override {
78        bool doFill = rec->isFillStyle();
79
80        SkPathMeasure   meas(src, doFill);
81
82        /* Caller may supply their own seed assist, which by default is 0 */
83        uint32_t seed = fSeedAssist ^ SkScalarRoundToInt(meas.getLength());
84
85        LCGRandom   rand(seed ^ ((seed << 16) | (seed >> 16)));
86        SkScalar    scale = fPerterb;
87        SkPoint     p;
88        SkVector    v;
89
90        do {
91            SkScalar    length = meas.getLength();
92    #if defined(SK_BUILD_FOR_FUZZER)
93            if (length > 1000) {
94                return false;
95            }
96    #endif
97
98            if (fSegLength * (2 + doFill) > length) {
99                meas.getSegment(0, length, dst, true);  // to short for us to mangle
100            } else {
101                int         n = SkScalarRoundToInt(length / fSegLength);
102                constexpr int kMaxReasonableIterations = 100000;
103                n = std::min(n, kMaxReasonableIterations);
104                SkScalar    delta = length / n;
105                SkScalar    distance = 0;
106
107                if (meas.isClosed()) {
108                    n -= 1;
109                    distance += delta/2;
110                }
111
112                if (meas.getPosTan(distance, &p, &v)) {
113                    Perterb(&p, v, rand.nextSScalar1() * scale);
114                    dst->moveTo(p);
115                }
116                while (--n >= 0) {
117                    distance += delta;
118                    if (meas.getPosTan(distance, &p, &v)) {
119                        Perterb(&p, v, rand.nextSScalar1() * scale);
120                        dst->lineTo(p);
121                    }
122                }
123                if (meas.isClosed()) {
124                    dst->close();
125                }
126            }
127        } while (meas.nextContour());
128        return true;
129    }
130
131    bool computeFastBounds(SkRect* bounds) const override {
132        if (bounds) {
133            SkScalar maxOutset = SkScalarAbs(fPerterb);
134            bounds->outset(maxOutset, maxOutset);
135        }
136        return true;
137    }
138
139    static sk_sp<SkFlattenable> CreateProc(SkReadBuffer& buffer) {
140        SkScalar segLength = buffer.readScalar();
141        SkScalar perterb = buffer.readScalar();
142        uint32_t seed = buffer.readUInt();
143        return SkDiscretePathEffect::Make(segLength, perterb, seed);
144    }
145
146    void flatten(SkWriteBuffer& buffer) const override {
147        buffer.writeScalar(fSegLength);
148        buffer.writeScalar(fPerterb);
149        buffer.writeUInt(fSeedAssist);
150    }
151
152    Factory getFactory() const override { return CreateProc; }
153    const char* getTypeName() const override { return "SkDiscretePathEffect"; }
154
155private:
156    const SkScalar fSegLength,
157                   fPerterb;
158    /* Caller-supplied 32 bit seed assist */
159    const uint32_t fSeedAssist;
160
161    using INHERITED = SkPathEffectBase;
162};
163
164//////////////////////////////////////////////////////////////////////////////////////////////////
165
166sk_sp<SkPathEffect> SkDiscretePathEffect::Make(SkScalar segLength, SkScalar deviation,
167                                               uint32_t seedAssist) {
168    if (!SkScalarIsFinite(segLength) || !SkScalarIsFinite(deviation)) {
169        return nullptr;
170    }
171    if (segLength <= SK_ScalarNearlyZero) {
172        return nullptr;
173    }
174    return sk_sp<SkPathEffect>(new SkDiscretePathEffectImpl(segLength, deviation, seedAssist));
175}
176
177void SkDiscretePathEffect::RegisterFlattenables() {
178    SkFlattenable::Register("SkDiscretePathEffect", SkDiscretePathEffectImpl::CreateProc);
179}
180