1 /*
2 * Copyright 2012 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 "GrPath.h"
9
10 namespace {
11 // Verb count limit for generating path key from content of a volatile path.
12 // The value should accomodate at least simple rects and rrects.
13 static const int kSimpleVolatilePathVerbLimit = 10;
14
compute_key_for_line_path(const SkPath & path,const GrStrokeInfo & stroke,GrUniqueKey * key)15 inline static bool compute_key_for_line_path(const SkPath& path, const GrStrokeInfo& stroke,
16 GrUniqueKey* key) {
17 SkPoint pts[2];
18 if (!path.isLine(pts)) {
19 return false;
20 }
21 static_assert((sizeof(pts) % sizeof(uint32_t)) == 0 && sizeof(pts) > sizeof(uint32_t),
22 "pts_needs_padding");
23
24 const int kBaseData32Cnt = 1 + sizeof(pts) / sizeof(uint32_t);
25 int strokeDataCnt = stroke.computeUniqueKeyFragmentData32Cnt();
26 static const GrUniqueKey::Domain kOvalPathDomain = GrUniqueKey::GenerateDomain();
27 GrUniqueKey::Builder builder(key, kOvalPathDomain, kBaseData32Cnt + strokeDataCnt);
28 builder[0] = path.getFillType();
29 memcpy(&builder[1], &pts, sizeof(pts));
30 if (strokeDataCnt > 0) {
31 stroke.asUniqueKeyFragment(&builder[kBaseData32Cnt]);
32 }
33 return true;
34 }
35
compute_key_for_oval_path(const SkPath & path,const GrStrokeInfo & stroke,GrUniqueKey * key)36 inline static bool compute_key_for_oval_path(const SkPath& path, const GrStrokeInfo& stroke,
37 GrUniqueKey* key) {
38 SkRect rect;
39 // Point order is significant when dashing, so we cannot devolve to a rect key.
40 if (stroke.isDashed() || !path.isOval(&rect)) {
41 return false;
42 }
43 static_assert((sizeof(rect) % sizeof(uint32_t)) == 0 && sizeof(rect) > sizeof(uint32_t),
44 "rect_needs_padding");
45
46 const int kBaseData32Cnt = 1 + sizeof(rect) / sizeof(uint32_t);
47 int strokeDataCnt = stroke.computeUniqueKeyFragmentData32Cnt();
48 static const GrUniqueKey::Domain kOvalPathDomain = GrUniqueKey::GenerateDomain();
49 GrUniqueKey::Builder builder(key, kOvalPathDomain, kBaseData32Cnt + strokeDataCnt);
50 builder[0] = path.getFillType();
51 memcpy(&builder[1], &rect, sizeof(rect));
52 if (strokeDataCnt > 0) {
53 stroke.asUniqueKeyFragment(&builder[kBaseData32Cnt]);
54 }
55 return true;
56 }
57
58 // Encodes the full path data to the unique key for very small, volatile paths. This is typically
59 // hit when clipping stencils the clip stack. Intention is that this handles rects too, since
60 // SkPath::isRect seems to do non-trivial amount of work.
compute_key_for_simple_path(const SkPath & path,const GrStrokeInfo & stroke,GrUniqueKey * key)61 inline static bool compute_key_for_simple_path(const SkPath& path, const GrStrokeInfo& stroke,
62 GrUniqueKey* key) {
63 if (!path.isVolatile()) {
64 return false;
65 }
66 // The check below should take care of negative values casted positive.
67 const int verbCnt = path.countVerbs();
68 if (verbCnt > kSimpleVolatilePathVerbLimit) {
69 return false;
70 }
71
72 // If somebody goes wild with the constant, it might cause an overflow.
73 static_assert(kSimpleVolatilePathVerbLimit <= 100,
74 "big_simple_volatile_path_verb_limit_may_cause_overflow");
75
76 const int pointCnt = path.countPoints();
77 if (pointCnt < 0) {
78 SkASSERT(false);
79 return false;
80 }
81 SkSTArray<16, SkScalar, true> conicWeights(16);
82 if ((path.getSegmentMasks() & SkPath::kConic_SegmentMask) != 0) {
83 SkPath::RawIter iter(path);
84 SkPath::Verb verb;
85 SkPoint points[4];
86 while ((verb = iter.next(points)) != SkPath::kDone_Verb) {
87 if (verb == SkPath::kConic_Verb) {
88 conicWeights.push_back(iter.conicWeight());
89 }
90 }
91 }
92
93 const int conicWeightCnt = conicWeights.count();
94
95 // Construct counts that align as uint32_t counts.
96 #define ARRAY_DATA32_COUNT(array_type, count) \
97 static_cast<int>((((count) * sizeof(array_type) + sizeof(uint32_t) - 1) / sizeof(uint32_t)))
98
99 const int verbData32Cnt = ARRAY_DATA32_COUNT(uint8_t, verbCnt);
100 const int pointData32Cnt = ARRAY_DATA32_COUNT(SkPoint, pointCnt);
101 const int conicWeightData32Cnt = ARRAY_DATA32_COUNT(SkScalar, conicWeightCnt);
102
103 #undef ARRAY_DATA32_COUNT
104
105 // The unique key data is a "message" with following fragments:
106 // 0) domain, key length, uint32_t for fill type and uint32_t for verbCnt
107 // (fragment 0, fixed size)
108 // 1) verb, point data and conic weights (varying size)
109 // 2) stroke data (varying size)
110
111 const int baseData32Cnt = 2 + verbData32Cnt + pointData32Cnt + conicWeightData32Cnt;
112 const int strokeDataCnt = stroke.computeUniqueKeyFragmentData32Cnt();
113 static const GrUniqueKey::Domain kSimpleVolatilePathDomain = GrUniqueKey::GenerateDomain();
114 GrUniqueKey::Builder builder(key, kSimpleVolatilePathDomain, baseData32Cnt + strokeDataCnt);
115 int i = 0;
116 builder[i++] = path.getFillType();
117
118 // Serialize the verbCnt to make the whole message unambiguous.
119 // We serialize two variable length fragments to the message:
120 // * verbs, point data and conic weights (fragment 1)
121 // * stroke data (fragment 2)
122 // "Proof:"
123 // Verb count establishes unambiguous verb data.
124 // Verbs encode also point data size and conic weight size.
125 // Thus the fragment 1 is unambiguous.
126 // Unambiguous fragment 1 establishes unambiguous fragment 2, since the length of the message
127 // has been established.
128
129 builder[i++] = SkToU32(verbCnt); // The path limit is compile-asserted above, so the cast is ok.
130
131 // Fill the last uint32_t with 0 first, since the last uint8_ts of the uint32_t may be
132 // uninitialized. This does not produce ambiguous verb data, since we have serialized the exact
133 // verb count.
134 if (verbData32Cnt != static_cast<int>((verbCnt * sizeof(uint8_t) / sizeof(uint32_t)))) {
135 builder[i + verbData32Cnt - 1] = 0;
136 }
137 path.getVerbs(reinterpret_cast<uint8_t*>(&builder[i]), verbCnt);
138 i += verbData32Cnt;
139
140 static_assert(((sizeof(SkPoint) % sizeof(uint32_t)) == 0) && sizeof(SkPoint) > sizeof(uint32_t),
141 "skpoint_array_needs_padding");
142
143 // Here we assume getPoints does a memcpy, so that we do not need to worry about the alignment.
144 path.getPoints(reinterpret_cast<SkPoint*>(&builder[i]), pointCnt);
145 i += pointData32Cnt;
146
147 if (conicWeightCnt > 0) {
148 if (conicWeightData32Cnt != static_cast<int>(
149 (conicWeightCnt * sizeof(SkScalar) / sizeof(uint32_t)))) {
150 builder[i + conicWeightData32Cnt - 1] = 0;
151 }
152 memcpy(&builder[i], conicWeights.begin(), conicWeightCnt * sizeof(SkScalar));
153 SkDEBUGCODE(i += conicWeightData32Cnt);
154 }
155 SkASSERT(i == baseData32Cnt);
156 if (strokeDataCnt > 0) {
157 stroke.asUniqueKeyFragment(&builder[baseData32Cnt]);
158 }
159 return true;
160 }
161
compute_key_for_general_path(const SkPath & path,const GrStrokeInfo & stroke,GrUniqueKey * key)162 inline static void compute_key_for_general_path(const SkPath& path, const GrStrokeInfo& stroke,
163 GrUniqueKey* key) {
164 const int kBaseData32Cnt = 2;
165 int strokeDataCnt = stroke.computeUniqueKeyFragmentData32Cnt();
166 static const GrUniqueKey::Domain kGeneralPathDomain = GrUniqueKey::GenerateDomain();
167 GrUniqueKey::Builder builder(key, kGeneralPathDomain, kBaseData32Cnt + strokeDataCnt);
168 builder[0] = path.getGenerationID();
169 builder[1] = path.getFillType();
170 if (strokeDataCnt > 0) {
171 stroke.asUniqueKeyFragment(&builder[kBaseData32Cnt]);
172 }
173 }
174
175 }
176
ComputeKey(const SkPath & path,const GrStrokeInfo & stroke,GrUniqueKey * key,bool * outIsVolatile)177 void GrPath::ComputeKey(const SkPath& path, const GrStrokeInfo& stroke, GrUniqueKey* key,
178 bool* outIsVolatile) {
179 if (compute_key_for_line_path(path, stroke, key)) {
180 *outIsVolatile = false;
181 return;
182 }
183
184 if (compute_key_for_oval_path(path, stroke, key)) {
185 *outIsVolatile = false;
186 return;
187 }
188
189 if (compute_key_for_simple_path(path, stroke, key)) {
190 *outIsVolatile = false;
191 return;
192 }
193
194 compute_key_for_general_path(path, stroke, key);
195 *outIsVolatile = path.isVolatile();
196 }
197
198 #ifdef SK_DEBUG
isEqualTo(const SkPath & path,const GrStrokeInfo & stroke) const199 bool GrPath::isEqualTo(const SkPath& path, const GrStrokeInfo& stroke) const {
200 if (!fStroke.hasEqualEffect(stroke)) {
201 return false;
202 }
203
204 // We treat same-rect ovals as identical - but only when not dashing.
205 SkRect ovalBounds;
206 if (!fStroke.isDashed() && fSkPath.isOval(&ovalBounds)) {
207 SkRect otherOvalBounds;
208 return path.isOval(&otherOvalBounds) && ovalBounds == otherOvalBounds;
209 }
210
211 return fSkPath == path;
212 }
213 #endif
214
215