gfx/skia/trunk/src/gpu/GrReducedClip.cpp@129ffea94266
gfx/skia/trunk/src/gpu/GrReducedClip.cpp
Sat, 03 Jan 2015 20:18:00 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Sat, 03 Jan 2015 20:18:00 +0100
- branch
- TOR_BUG_3246
- changeset 7
- 129ffea94266
- permissions
- -rw-r--r--
Conditionally enable double key logic according to:
private browsing mode or privacy.thirdparty.isolate preference and
implement in GetCookieStringCommon and FindCookie where it counts...
With some reservations of how to convince FindCookie users to test
condition and pass a nullptr when disabling double key logic.
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 */
9 #include "GrReducedClip.h"
11 typedef SkClipStack::Element Element;
12 ////////////////////////////////////////////////////////////////////////////////
14 namespace GrReducedClip {
16 // helper function
17 void reduced_stack_walker(const SkClipStack& stack,
18 const SkRect& queryBounds,
19 ElementList* result,
20 int32_t* resultGenID,
21 InitialState* initialState,
22 bool* requiresAA);
24 /*
25 There are plenty of optimizations that could be added here. Maybe flips could be folded into
26 earlier operations. Or would inserting flips and reversing earlier ops ever be a win? Perhaps
27 for the case where the bounds are kInsideOut_BoundsType. We could restrict earlier operations
28 based on later intersect operations, and perhaps remove intersect-rects. We could optionally
29 take a rect in case the caller knows a bound on what is to be drawn through this clip.
30 */
31 void ReduceClipStack(const SkClipStack& stack,
32 const SkIRect& queryBounds,
33 ElementList* result,
34 int32_t* resultGenID,
35 InitialState* initialState,
36 SkIRect* tighterBounds,
37 bool* requiresAA) {
38 result->reset();
40 // The clip established by the element list might be cached based on the last
41 // generation id. When we make early returns, we do not know what was the generation
42 // id that lead to the state. Make a conservative guess.
43 *resultGenID = stack.getTopmostGenID();
45 if (stack.isWideOpen()) {
46 *initialState = kAllIn_InitialState;
47 return;
48 }
51 // We initially look at whether the bounds alone is sufficient. We also use the stack bounds to
52 // attempt to compute the tighterBounds.
54 SkClipStack::BoundsType stackBoundsType;
55 SkRect stackBounds;
56 bool iior;
57 stack.getBounds(&stackBounds, &stackBoundsType, &iior);
59 const SkIRect* bounds = &queryBounds;
61 SkRect scalarQueryBounds = SkRect::Make(queryBounds);
63 if (iior) {
64 SkASSERT(SkClipStack::kNormal_BoundsType == stackBoundsType);
65 SkRect isectRect;
66 if (stackBounds.contains(scalarQueryBounds)) {
67 *initialState = kAllIn_InitialState;
68 if (NULL != tighterBounds) {
69 *tighterBounds = queryBounds;
70 }
71 if (NULL != requiresAA) {
72 *requiresAA = false;
73 }
74 } else if (isectRect.intersect(stackBounds, scalarQueryBounds)) {
75 // If the caller asked for tighter integer bounds we may be able to
76 // return kAllIn and give the bounds with no elements
77 if (NULL != tighterBounds) {
78 isectRect.roundOut(tighterBounds);
79 SkRect scalarTighterBounds = SkRect::Make(*tighterBounds);
80 if (scalarTighterBounds == isectRect) {
81 // the round-out didn't add any area outside the clip rect.
82 if (NULL != requiresAA) {
83 *requiresAA = false;
84 }
85 *initialState = kAllIn_InitialState;
86 return;
87 }
88 }
89 *initialState = kAllOut_InitialState;
90 // iior should only be true if aa/non-aa status matches among all elements.
91 SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
92 bool doAA = iter.prev()->isAA();
93 SkNEW_INSERT_AT_LLIST_HEAD(result, Element, (isectRect, SkRegion::kReplace_Op, doAA));
94 if (NULL != requiresAA) {
95 *requiresAA = doAA;
96 }
97 } else {
98 *initialState = kAllOut_InitialState;
99 if (NULL != requiresAA) {
100 *requiresAA = false;
101 }
102 }
103 return;
104 } else {
105 if (SkClipStack::kNormal_BoundsType == stackBoundsType) {
106 if (!SkRect::Intersects(stackBounds, scalarQueryBounds)) {
107 *initialState = kAllOut_InitialState;
108 if (NULL != requiresAA) {
109 *requiresAA = false;
110 }
111 return;
112 }
113 if (NULL != tighterBounds) {
114 SkIRect stackIBounds;
115 stackBounds.roundOut(&stackIBounds);
116 tighterBounds->intersect(queryBounds, stackIBounds);
117 bounds = tighterBounds;
118 }
119 } else {
120 if (stackBounds.contains(scalarQueryBounds)) {
121 *initialState = kAllOut_InitialState;
122 if (NULL != requiresAA) {
123 *requiresAA = false;
124 }
125 return;
126 }
127 if (NULL != tighterBounds) {
128 *tighterBounds = queryBounds;
129 }
130 }
131 }
133 SkRect scalarBounds = SkRect::Make(*bounds);
135 // Now that we have determined the bounds to use and filtered out the trivial cases, call the
136 // helper that actually walks the stack.
137 reduced_stack_walker(stack, scalarBounds, result, resultGenID, initialState, requiresAA);
139 // The list that was computed in this function may be cached based on the gen id of the last
140 // element.
141 SkASSERT(SkClipStack::kInvalidGenID != *resultGenID);
142 }
144 void reduced_stack_walker(const SkClipStack& stack,
145 const SkRect& queryBounds,
146 ElementList* result,
147 int32_t* resultGenID,
148 InitialState* initialState,
149 bool* requiresAA) {
151 // walk backwards until we get to:
152 // a) the beginning
153 // b) an operation that is known to make the bounds all inside/outside
154 // c) a replace operation
156 static const InitialState kUnknown_InitialState = static_cast<InitialState>(-1);
157 *initialState = kUnknown_InitialState;
159 // During our backwards walk, track whether we've seen ops that either grow or shrink the clip.
160 // TODO: track these per saved clip so that we can consider them on the forward pass.
161 bool embiggens = false;
162 bool emsmallens = false;
164 SkClipStack::Iter iter(stack, SkClipStack::Iter::kTop_IterStart);
165 int numAAElements = 0;
166 while ((kUnknown_InitialState == *initialState)) {
167 const Element* element = iter.prev();
168 if (NULL == element) {
169 *initialState = kAllIn_InitialState;
170 break;
171 }
172 if (SkClipStack::kEmptyGenID == element->getGenID()) {
173 *initialState = kAllOut_InitialState;
174 break;
175 }
176 if (SkClipStack::kWideOpenGenID == element->getGenID()) {
177 *initialState = kAllIn_InitialState;
178 break;
179 }
181 bool skippable = false;
182 bool isFlip = false; // does this op just flip the in/out state of every point in the bounds
184 switch (element->getOp()) {
185 case SkRegion::kDifference_Op:
186 // check if the shape subtracted either contains the entire bounds (and makes
187 // the clip empty) or is outside the bounds and therefore can be skipped.
188 if (element->isInverseFilled()) {
189 if (element->contains(queryBounds)) {
190 skippable = true;
191 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
192 *initialState = kAllOut_InitialState;
193 skippable = true;
194 }
195 } else {
196 if (element->contains(queryBounds)) {
197 *initialState = kAllOut_InitialState;
198 skippable = true;
199 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
200 skippable = true;
201 }
202 }
203 if (!skippable) {
204 emsmallens = true;
205 }
206 break;
207 case SkRegion::kIntersect_Op:
208 // check if the shape intersected contains the entire bounds and therefore can
209 // be skipped or it is outside the entire bounds and therefore makes the clip
210 // empty.
211 if (element->isInverseFilled()) {
212 if (element->contains(queryBounds)) {
213 *initialState = kAllOut_InitialState;
214 skippable = true;
215 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
216 skippable = true;
217 }
218 } else {
219 if (element->contains(queryBounds)) {
220 skippable = true;
221 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
222 *initialState = kAllOut_InitialState;
223 skippable = true;
224 }
225 }
226 if (!skippable) {
227 emsmallens = true;
228 }
229 break;
230 case SkRegion::kUnion_Op:
231 // If the union-ed shape contains the entire bounds then after this element
232 // the bounds is entirely inside the clip. If the union-ed shape is outside the
233 // bounds then this op can be skipped.
234 if (element->isInverseFilled()) {
235 if (element->contains(queryBounds)) {
236 skippable = true;
237 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
238 *initialState = kAllIn_InitialState;
239 skippable = true;
240 }
241 } else {
242 if (element->contains(queryBounds)) {
243 *initialState = kAllIn_InitialState;
244 skippable = true;
245 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
246 skippable = true;
247 }
248 }
249 if (!skippable) {
250 embiggens = true;
251 }
252 break;
253 case SkRegion::kXOR_Op:
254 // If the bounds is entirely inside the shape being xor-ed then the effect is
255 // to flip the inside/outside state of every point in the bounds. We may be
256 // able to take advantage of this in the forward pass. If the xor-ed shape
257 // doesn't intersect the bounds then it can be skipped.
258 if (element->isInverseFilled()) {
259 if (element->contains(queryBounds)) {
260 skippable = true;
261 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
262 isFlip = true;
263 }
264 } else {
265 if (element->contains(queryBounds)) {
266 isFlip = true;
267 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
268 skippable = true;
269 }
270 }
271 if (!skippable) {
272 emsmallens = embiggens = true;
273 }
274 break;
275 case SkRegion::kReverseDifference_Op:
276 // When the bounds is entirely within the rev-diff shape then this behaves like xor
277 // and reverses every point inside the bounds. If the shape is completely outside
278 // the bounds then we know after this element is applied that the bounds will be
279 // all outside the current clip.B
280 if (element->isInverseFilled()) {
281 if (element->contains(queryBounds)) {
282 *initialState = kAllOut_InitialState;
283 skippable = true;
284 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
285 isFlip = true;
286 }
287 } else {
288 if (element->contains(queryBounds)) {
289 isFlip = true;
290 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
291 *initialState = kAllOut_InitialState;
292 skippable = true;
293 }
294 }
295 if (!skippable) {
296 emsmallens = embiggens = true;
297 }
298 break;
299 case SkRegion::kReplace_Op:
300 // Replace will always terminate our walk. We will either begin the forward walk
301 // at the replace op or detect here than the shape is either completely inside
302 // or completely outside the bounds. In this latter case it can be skipped by
303 // setting the correct value for initialState.
304 if (element->isInverseFilled()) {
305 if (element->contains(queryBounds)) {
306 *initialState = kAllOut_InitialState;
307 skippable = true;
308 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
309 *initialState = kAllIn_InitialState;
310 skippable = true;
311 }
312 } else {
313 if (element->contains(queryBounds)) {
314 *initialState = kAllIn_InitialState;
315 skippable = true;
316 } else if (!SkRect::Intersects(element->getBounds(), queryBounds)) {
317 *initialState = kAllOut_InitialState;
318 skippable = true;
319 }
320 }
321 if (!skippable) {
322 *initialState = kAllOut_InitialState;
323 embiggens = emsmallens = true;
324 }
325 break;
326 default:
327 SkDEBUGFAIL("Unexpected op.");
328 break;
329 }
330 if (!skippable) {
331 if (0 == result->count()) {
332 // This will be the last element. Record the stricter genID.
333 *resultGenID = element->getGenID();
334 }
336 // if it is a flip, change it to a bounds-filling rect
337 if (isFlip) {
338 SkASSERT(SkRegion::kXOR_Op == element->getOp() ||
339 SkRegion::kReverseDifference_Op == element->getOp());
340 SkNEW_INSERT_AT_LLIST_HEAD(result,
341 Element,
342 (queryBounds, SkRegion::kReverseDifference_Op, false));
343 } else {
344 Element* newElement = result->addToHead(*element);
345 if (newElement->isAA()) {
346 ++numAAElements;
347 }
348 // Intersecting an inverse shape is the same as differencing the non-inverse shape.
349 // Replacing with an inverse shape is the same as setting initialState=kAllIn and
350 // differencing the non-inverse shape.
351 bool isReplace = SkRegion::kReplace_Op == newElement->getOp();
352 if (newElement->isInverseFilled() &&
353 (SkRegion::kIntersect_Op == newElement->getOp() || isReplace)) {
354 newElement->invertShapeFillType();
355 newElement->setOp(SkRegion::kDifference_Op);
356 if (isReplace) {
357 SkASSERT(kAllOut_InitialState == *initialState);
358 *initialState = kAllIn_InitialState;
359 }
360 }
361 }
362 }
363 }
365 if ((kAllOut_InitialState == *initialState && !embiggens) ||
366 (kAllIn_InitialState == *initialState && !emsmallens)) {
367 result->reset();
368 } else {
369 Element* element = result->headIter().get();
370 while (NULL != element) {
371 bool skippable = false;
372 switch (element->getOp()) {
373 case SkRegion::kDifference_Op:
374 // subtracting from the empty set yields the empty set.
375 skippable = kAllOut_InitialState == *initialState;
376 break;
377 case SkRegion::kIntersect_Op:
378 // intersecting with the empty set yields the empty set
379 if (kAllOut_InitialState == *initialState) {
380 skippable = true;
381 } else {
382 // We can clear to zero and then simply draw the clip element.
383 *initialState = kAllOut_InitialState;
384 element->setOp(SkRegion::kReplace_Op);
385 }
386 break;
387 case SkRegion::kUnion_Op:
388 if (kAllIn_InitialState == *initialState) {
389 // unioning the infinite plane with anything is a no-op.
390 skippable = true;
391 } else {
392 // unioning the empty set with a shape is the shape.
393 element->setOp(SkRegion::kReplace_Op);
394 }
395 break;
396 case SkRegion::kXOR_Op:
397 if (kAllOut_InitialState == *initialState) {
398 // xor could be changed to diff in the kAllIn case, not sure it's a win.
399 element->setOp(SkRegion::kReplace_Op);
400 }
401 break;
402 case SkRegion::kReverseDifference_Op:
403 if (kAllIn_InitialState == *initialState) {
404 // subtracting the whole plane will yield the empty set.
405 skippable = true;
406 *initialState = kAllOut_InitialState;
407 } else {
408 // this picks up flips inserted in the backwards pass.
409 skippable = element->isInverseFilled() ?
410 !SkRect::Intersects(element->getBounds(), queryBounds) :
411 element->contains(queryBounds);
412 if (skippable) {
413 *initialState = kAllIn_InitialState;
414 } else {
415 element->setOp(SkRegion::kReplace_Op);
416 }
417 }
418 break;
419 case SkRegion::kReplace_Op:
420 skippable = false; // we would have skipped it in the backwards walk if we
421 // could've.
422 break;
423 default:
424 SkDEBUGFAIL("Unexpected op.");
425 break;
426 }
427 if (!skippable) {
428 break;
429 } else {
430 if (element->isAA()) {
431 --numAAElements;
432 }
433 result->popHead();
434 element = result->headIter().get();
435 }
436 }
437 }
438 if (NULL != requiresAA) {
439 *requiresAA = numAAElements > 0;
440 }
442 if (0 == result->count()) {
443 if (*initialState == kAllIn_InitialState) {
444 *resultGenID = SkClipStack::kWideOpenGenID;
445 } else {
446 *resultGenID = SkClipStack::kEmptyGenID;
447 }
448 }
449 }
450 } // namespace GrReducedClip
