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