gfx/skia/trunk/src/core/SkAAClip.cpp@129ffea94266
gfx/skia/trunk/src/core/SkAAClip.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 2011 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 "SkAAClip.h"
10 #include "SkBlitter.h"
11 #include "SkColorPriv.h"
12 #include "SkPath.h"
13 #include "SkScan.h"
14 #include "SkThread.h"
15 #include "SkUtils.h"
17 class AutoAAClipValidate {
18 public:
19 AutoAAClipValidate(const SkAAClip& clip) : fClip(clip) {
20 fClip.validate();
21 }
22 ~AutoAAClipValidate() {
23 fClip.validate();
24 }
25 private:
26 const SkAAClip& fClip;
27 };
29 #ifdef SK_DEBUG
30 #define AUTO_AACLIP_VALIDATE(clip) AutoAAClipValidate acv(clip)
31 #else
32 #define AUTO_AACLIP_VALIDATE(clip)
33 #endif
35 ///////////////////////////////////////////////////////////////////////////////
37 #define kMaxInt32 0x7FFFFFFF
39 #ifdef SK_DEBUG
40 static inline bool x_in_rect(int x, const SkIRect& rect) {
41 return (unsigned)(x - rect.fLeft) < (unsigned)rect.width();
42 }
43 #endif
45 static inline bool y_in_rect(int y, const SkIRect& rect) {
46 return (unsigned)(y - rect.fTop) < (unsigned)rect.height();
47 }
49 /*
50 * Data runs are packed [count, alpha]
51 */
53 struct SkAAClip::YOffset {
54 int32_t fY;
55 uint32_t fOffset;
56 };
58 struct SkAAClip::RunHead {
59 int32_t fRefCnt;
60 int32_t fRowCount;
61 size_t fDataSize;
63 YOffset* yoffsets() {
64 return (YOffset*)((char*)this + sizeof(RunHead));
65 }
66 const YOffset* yoffsets() const {
67 return (const YOffset*)((const char*)this + sizeof(RunHead));
68 }
69 uint8_t* data() {
70 return (uint8_t*)(this->yoffsets() + fRowCount);
71 }
72 const uint8_t* data() const {
73 return (const uint8_t*)(this->yoffsets() + fRowCount);
74 }
76 static RunHead* Alloc(int rowCount, size_t dataSize) {
77 size_t size = sizeof(RunHead) + rowCount * sizeof(YOffset) + dataSize;
78 RunHead* head = (RunHead*)sk_malloc_throw(size);
79 head->fRefCnt = 1;
80 head->fRowCount = rowCount;
81 head->fDataSize = dataSize;
82 return head;
83 }
85 static int ComputeRowSizeForWidth(int width) {
86 // 2 bytes per segment, where each segment can store up to 255 for count
87 int segments = 0;
88 while (width > 0) {
89 segments += 1;
90 int n = SkMin32(width, 255);
91 width -= n;
92 }
93 return segments * 2; // each segment is row[0] + row[1] (n + alpha)
94 }
96 static RunHead* AllocRect(const SkIRect& bounds) {
97 SkASSERT(!bounds.isEmpty());
98 int width = bounds.width();
99 size_t rowSize = ComputeRowSizeForWidth(width);
100 RunHead* head = RunHead::Alloc(1, rowSize);
101 YOffset* yoff = head->yoffsets();
102 yoff->fY = bounds.height() - 1;
103 yoff->fOffset = 0;
104 uint8_t* row = head->data();
105 while (width > 0) {
106 int n = SkMin32(width, 255);
107 row[0] = n;
108 row[1] = 0xFF;
109 width -= n;
110 row += 2;
111 }
112 return head;
113 }
114 };
116 class SkAAClip::Iter {
117 public:
118 Iter(const SkAAClip&);
120 bool done() const { return fDone; }
121 int top() const { return fTop; }
122 int bottom() const { return fBottom; }
123 const uint8_t* data() const { return fData; }
124 void next();
126 private:
127 const YOffset* fCurrYOff;
128 const YOffset* fStopYOff;
129 const uint8_t* fData;
131 int fTop, fBottom;
132 bool fDone;
133 };
135 SkAAClip::Iter::Iter(const SkAAClip& clip) {
136 if (clip.isEmpty()) {
137 fDone = true;
138 fTop = fBottom = clip.fBounds.fBottom;
139 fData = NULL;
140 fCurrYOff = NULL;
141 fStopYOff = NULL;
142 return;
143 }
145 const RunHead* head = clip.fRunHead;
146 fCurrYOff = head->yoffsets();
147 fStopYOff = fCurrYOff + head->fRowCount;
148 fData = head->data() + fCurrYOff->fOffset;
150 // setup first value
151 fTop = clip.fBounds.fTop;
152 fBottom = clip.fBounds.fTop + fCurrYOff->fY + 1;
153 fDone = false;
154 }
156 void SkAAClip::Iter::next() {
157 if (!fDone) {
158 const YOffset* prev = fCurrYOff;
159 const YOffset* curr = prev + 1;
160 SkASSERT(curr <= fStopYOff);
162 fTop = fBottom;
163 if (curr >= fStopYOff) {
164 fDone = true;
165 fBottom = kMaxInt32;
166 fData = NULL;
167 } else {
168 fBottom += curr->fY - prev->fY;
169 fData += curr->fOffset - prev->fOffset;
170 fCurrYOff = curr;
171 }
172 }
173 }
175 #ifdef SK_DEBUG
176 // assert we're exactly width-wide, and then return the number of bytes used
177 static size_t compute_row_length(const uint8_t row[], int width) {
178 const uint8_t* origRow = row;
179 while (width > 0) {
180 int n = row[0];
181 SkASSERT(n > 0);
182 SkASSERT(n <= width);
183 row += 2;
184 width -= n;
185 }
186 SkASSERT(0 == width);
187 return row - origRow;
188 }
190 void SkAAClip::validate() const {
191 if (NULL == fRunHead) {
192 SkASSERT(fBounds.isEmpty());
193 return;
194 }
196 const RunHead* head = fRunHead;
197 SkASSERT(head->fRefCnt > 0);
198 SkASSERT(head->fRowCount > 0);
200 const YOffset* yoff = head->yoffsets();
201 const YOffset* ystop = yoff + head->fRowCount;
202 const int lastY = fBounds.height() - 1;
204 // Y and offset must be monotonic
205 int prevY = -1;
206 int32_t prevOffset = -1;
207 while (yoff < ystop) {
208 SkASSERT(prevY < yoff->fY);
209 SkASSERT(yoff->fY <= lastY);
210 prevY = yoff->fY;
211 SkASSERT(prevOffset < (int32_t)yoff->fOffset);
212 prevOffset = yoff->fOffset;
213 const uint8_t* row = head->data() + yoff->fOffset;
214 size_t rowLength = compute_row_length(row, fBounds.width());
215 SkASSERT(yoff->fOffset + rowLength <= head->fDataSize);
216 yoff += 1;
217 }
218 // check the last entry;
219 --yoff;
220 SkASSERT(yoff->fY == lastY);
221 }
222 #endif
224 ///////////////////////////////////////////////////////////////////////////////
226 // Count the number of zeros on the left and right edges of the passed in
227 // RLE row. If 'row' is all zeros return 'width' in both variables.
228 static void count_left_right_zeros(const uint8_t* row, int width,
229 int* leftZ, int* riteZ) {
230 int zeros = 0;
231 do {
232 if (row[1]) {
233 break;
234 }
235 int n = row[0];
236 SkASSERT(n > 0);
237 SkASSERT(n <= width);
238 zeros += n;
239 row += 2;
240 width -= n;
241 } while (width > 0);
242 *leftZ = zeros;
244 if (0 == width) {
245 // this line is completely empty return 'width' in both variables
246 *riteZ = *leftZ;
247 return;
248 }
250 zeros = 0;
251 while (width > 0) {
252 int n = row[0];
253 SkASSERT(n > 0);
254 if (0 == row[1]) {
255 zeros += n;
256 } else {
257 zeros = 0;
258 }
259 row += 2;
260 width -= n;
261 }
262 *riteZ = zeros;
263 }
265 #ifdef SK_DEBUG
266 static void test_count_left_right_zeros() {
267 static bool gOnce;
268 if (gOnce) {
269 return;
270 }
271 gOnce = true;
273 const uint8_t data0[] = { 0, 0, 10, 0xFF };
274 const uint8_t data1[] = { 0, 0, 5, 0xFF, 2, 0, 3, 0xFF };
275 const uint8_t data2[] = { 7, 0, 5, 0, 2, 0, 3, 0xFF };
276 const uint8_t data3[] = { 0, 5, 5, 0xFF, 2, 0, 3, 0 };
277 const uint8_t data4[] = { 2, 3, 2, 0, 5, 0xFF, 3, 0 };
278 const uint8_t data5[] = { 10, 10, 10, 0 };
279 const uint8_t data6[] = { 2, 2, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
281 const uint8_t* array[] = {
282 data0, data1, data2, data3, data4, data5, data6
283 };
285 for (size_t i = 0; i < SK_ARRAY_COUNT(array); ++i) {
286 const uint8_t* data = array[i];
287 const int expectedL = *data++;
288 const int expectedR = *data++;
289 int L = 12345, R = 12345;
290 count_left_right_zeros(data, 10, &L, &R);
291 SkASSERT(expectedL == L);
292 SkASSERT(expectedR == R);
293 }
294 }
295 #endif
297 // modify row in place, trimming off (zeros) from the left and right sides.
298 // return the number of bytes that were completely eliminated from the left
299 static int trim_row_left_right(uint8_t* row, int width, int leftZ, int riteZ) {
300 int trim = 0;
301 while (leftZ > 0) {
302 SkASSERT(0 == row[1]);
303 int n = row[0];
304 SkASSERT(n > 0);
305 SkASSERT(n <= width);
306 width -= n;
307 row += 2;
308 if (n > leftZ) {
309 row[-2] = n - leftZ;
310 break;
311 }
312 trim += 2;
313 leftZ -= n;
314 SkASSERT(leftZ >= 0);
315 }
317 if (riteZ) {
318 // walk row to the end, and then we'll back up to trim riteZ
319 while (width > 0) {
320 int n = row[0];
321 SkASSERT(n <= width);
322 width -= n;
323 row += 2;
324 }
325 // now skip whole runs of zeros
326 do {
327 row -= 2;
328 SkASSERT(0 == row[1]);
329 int n = row[0];
330 SkASSERT(n > 0);
331 if (n > riteZ) {
332 row[0] = n - riteZ;
333 break;
334 }
335 riteZ -= n;
336 SkASSERT(riteZ >= 0);
337 } while (riteZ > 0);
338 }
340 return trim;
341 }
343 #ifdef SK_DEBUG
344 // assert that this row is exactly this width
345 static void assert_row_width(const uint8_t* row, int width) {
346 while (width > 0) {
347 int n = row[0];
348 SkASSERT(n > 0);
349 SkASSERT(n <= width);
350 width -= n;
351 row += 2;
352 }
353 SkASSERT(0 == width);
354 }
356 static void test_trim_row_left_right() {
357 static bool gOnce;
358 if (gOnce) {
359 return;
360 }
361 gOnce = true;
363 uint8_t data0[] = { 0, 0, 0, 10, 10, 0xFF };
364 uint8_t data1[] = { 2, 0, 0, 10, 5, 0, 2, 0, 3, 0xFF };
365 uint8_t data2[] = { 5, 0, 2, 10, 5, 0, 2, 0, 3, 0xFF };
366 uint8_t data3[] = { 6, 0, 2, 10, 5, 0, 2, 0, 3, 0xFF };
367 uint8_t data4[] = { 0, 0, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
368 uint8_t data5[] = { 1, 0, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
369 uint8_t data6[] = { 0, 1, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
370 uint8_t data7[] = { 1, 1, 0, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
371 uint8_t data8[] = { 2, 2, 2, 10, 2, 0, 2, 0xFF, 2, 0, 2, 0xFF, 2, 0 };
372 uint8_t data9[] = { 5, 2, 4, 10, 2, 0, 2, 0, 2, 0, 2, 0xFF, 2, 0 };
373 uint8_t data10[] ={ 74, 0, 4, 150, 9, 0, 65, 0, 76, 0xFF };
375 uint8_t* array[] = {
376 data0, data1, data2, data3, data4,
377 data5, data6, data7, data8, data9,
378 data10
379 };
381 for (size_t i = 0; i < SK_ARRAY_COUNT(array); ++i) {
382 uint8_t* data = array[i];
383 const int trimL = *data++;
384 const int trimR = *data++;
385 const int expectedSkip = *data++;
386 const int origWidth = *data++;
387 assert_row_width(data, origWidth);
388 int skip = trim_row_left_right(data, origWidth, trimL, trimR);
389 SkASSERT(expectedSkip == skip);
390 int expectedWidth = origWidth - trimL - trimR;
391 assert_row_width(data + skip, expectedWidth);
392 }
393 }
394 #endif
396 bool SkAAClip::trimLeftRight() {
397 SkDEBUGCODE(test_trim_row_left_right();)
399 if (this->isEmpty()) {
400 return false;
401 }
403 AUTO_AACLIP_VALIDATE(*this);
405 const int width = fBounds.width();
406 RunHead* head = fRunHead;
407 YOffset* yoff = head->yoffsets();
408 YOffset* stop = yoff + head->fRowCount;
409 uint8_t* base = head->data();
411 // After this loop, 'leftZeros' & 'rightZeros' will contain the minimum
412 // number of zeros on the left and right of the clip. This information
413 // can be used to shrink the bounding box.
414 int leftZeros = width;
415 int riteZeros = width;
416 while (yoff < stop) {
417 int L, R;
418 count_left_right_zeros(base + yoff->fOffset, width, &L, &R);
419 SkASSERT(L + R < width || (L == width && R == width));
420 if (L < leftZeros) {
421 leftZeros = L;
422 }
423 if (R < riteZeros) {
424 riteZeros = R;
425 }
426 if (0 == (leftZeros | riteZeros)) {
427 // no trimming to do
428 return true;
429 }
430 yoff += 1;
431 }
433 SkASSERT(leftZeros || riteZeros);
434 if (width == leftZeros) {
435 SkASSERT(width == riteZeros);
436 return this->setEmpty();
437 }
439 this->validate();
441 fBounds.fLeft += leftZeros;
442 fBounds.fRight -= riteZeros;
443 SkASSERT(!fBounds.isEmpty());
445 // For now we don't realloc the storage (for time), we just shrink in place
446 // This means we don't have to do any memmoves either, since we can just
447 // play tricks with the yoff->fOffset for each row
448 yoff = head->yoffsets();
449 while (yoff < stop) {
450 uint8_t* row = base + yoff->fOffset;
451 SkDEBUGCODE((void)compute_row_length(row, width);)
452 yoff->fOffset += trim_row_left_right(row, width, leftZeros, riteZeros);
453 SkDEBUGCODE((void)compute_row_length(base + yoff->fOffset, width - leftZeros - riteZeros);)
454 yoff += 1;
455 }
456 return true;
457 }
459 static bool row_is_all_zeros(const uint8_t* row, int width) {
460 SkASSERT(width > 0);
461 do {
462 if (row[1]) {
463 return false;
464 }
465 int n = row[0];
466 SkASSERT(n <= width);
467 width -= n;
468 row += 2;
469 } while (width > 0);
470 SkASSERT(0 == width);
471 return true;
472 }
474 bool SkAAClip::trimTopBottom() {
475 if (this->isEmpty()) {
476 return false;
477 }
479 this->validate();
481 const int width = fBounds.width();
482 RunHead* head = fRunHead;
483 YOffset* yoff = head->yoffsets();
484 YOffset* stop = yoff + head->fRowCount;
485 const uint8_t* base = head->data();
487 // Look to trim away empty rows from the top.
488 //
489 int skip = 0;
490 while (yoff < stop) {
491 const uint8_t* data = base + yoff->fOffset;
492 if (!row_is_all_zeros(data, width)) {
493 break;
494 }
495 skip += 1;
496 yoff += 1;
497 }
498 SkASSERT(skip <= head->fRowCount);
499 if (skip == head->fRowCount) {
500 return this->setEmpty();
501 }
502 if (skip > 0) {
503 // adjust fRowCount and fBounds.fTop, and slide all the data up
504 // as we remove [skip] number of YOffset entries
505 yoff = head->yoffsets();
506 int dy = yoff[skip - 1].fY + 1;
507 for (int i = skip; i < head->fRowCount; ++i) {
508 SkASSERT(yoff[i].fY >= dy);
509 yoff[i].fY -= dy;
510 }
511 YOffset* dst = head->yoffsets();
512 size_t size = head->fRowCount * sizeof(YOffset) + head->fDataSize;
513 memmove(dst, dst + skip, size - skip * sizeof(YOffset));
515 fBounds.fTop += dy;
516 SkASSERT(!fBounds.isEmpty());
517 head->fRowCount -= skip;
518 SkASSERT(head->fRowCount > 0);
520 this->validate();
521 // need to reset this after the memmove
522 base = head->data();
523 }
525 // Look to trim away empty rows from the bottom.
526 // We know that we have at least one non-zero row, so we can just walk
527 // backwards without checking for running past the start.
528 //
529 stop = yoff = head->yoffsets() + head->fRowCount;
530 do {
531 yoff -= 1;
532 } while (row_is_all_zeros(base + yoff->fOffset, width));
533 skip = SkToInt(stop - yoff - 1);
534 SkASSERT(skip >= 0 && skip < head->fRowCount);
535 if (skip > 0) {
536 // removing from the bottom is easier than from the top, as we don't
537 // have to adjust any of the Y values, we just have to trim the array
538 memmove(stop - skip, stop, head->fDataSize);
540 fBounds.fBottom = fBounds.fTop + yoff->fY + 1;
541 SkASSERT(!fBounds.isEmpty());
542 head->fRowCount -= skip;
543 SkASSERT(head->fRowCount > 0);
544 }
545 this->validate();
547 return true;
548 }
550 // can't validate before we're done, since trimming is part of the process of
551 // making us valid after the Builder. Since we build from top to bottom, its
552 // possible our fBounds.fBottom is bigger than our last scanline of data, so
553 // we trim fBounds.fBottom back up.
554 //
555 // TODO: check for duplicates in X and Y to further compress our data
556 //
557 bool SkAAClip::trimBounds() {
558 if (this->isEmpty()) {
559 return false;
560 }
562 const RunHead* head = fRunHead;
563 const YOffset* yoff = head->yoffsets();
565 SkASSERT(head->fRowCount > 0);
566 const YOffset& lastY = yoff[head->fRowCount - 1];
567 SkASSERT(lastY.fY + 1 <= fBounds.height());
568 fBounds.fBottom = fBounds.fTop + lastY.fY + 1;
569 SkASSERT(lastY.fY + 1 == fBounds.height());
570 SkASSERT(!fBounds.isEmpty());
572 return this->trimTopBottom() && this->trimLeftRight();
573 }
575 ///////////////////////////////////////////////////////////////////////////////
577 void SkAAClip::freeRuns() {
578 if (fRunHead) {
579 SkASSERT(fRunHead->fRefCnt >= 1);
580 if (1 == sk_atomic_dec(&fRunHead->fRefCnt)) {
581 sk_free(fRunHead);
582 }
583 }
584 }
586 SkAAClip::SkAAClip() {
587 fBounds.setEmpty();
588 fRunHead = NULL;
589 }
591 SkAAClip::SkAAClip(const SkAAClip& src) {
592 SkDEBUGCODE(fBounds.setEmpty();) // need this for validate
593 fRunHead = NULL;
594 *this = src;
595 }
597 SkAAClip::~SkAAClip() {
598 this->freeRuns();
599 }
601 SkAAClip& SkAAClip::operator=(const SkAAClip& src) {
602 AUTO_AACLIP_VALIDATE(*this);
603 src.validate();
605 if (this != &src) {
606 this->freeRuns();
607 fBounds = src.fBounds;
608 fRunHead = src.fRunHead;
609 if (fRunHead) {
610 sk_atomic_inc(&fRunHead->fRefCnt);
611 }
612 }
613 return *this;
614 }
616 bool operator==(const SkAAClip& a, const SkAAClip& b) {
617 a.validate();
618 b.validate();
620 if (&a == &b) {
621 return true;
622 }
623 if (a.fBounds != b.fBounds) {
624 return false;
625 }
627 const SkAAClip::RunHead* ah = a.fRunHead;
628 const SkAAClip::RunHead* bh = b.fRunHead;
630 // this catches empties and rects being equal
631 if (ah == bh) {
632 return true;
633 }
635 // now we insist that both are complex (but different ptrs)
636 if (!a.fRunHead || !b.fRunHead) {
637 return false;
638 }
640 return ah->fRowCount == bh->fRowCount &&
641 ah->fDataSize == bh->fDataSize &&
642 !memcmp(ah->data(), bh->data(), ah->fDataSize);
643 }
645 void SkAAClip::swap(SkAAClip& other) {
646 AUTO_AACLIP_VALIDATE(*this);
647 other.validate();
649 SkTSwap(fBounds, other.fBounds);
650 SkTSwap(fRunHead, other.fRunHead);
651 }
653 bool SkAAClip::set(const SkAAClip& src) {
654 *this = src;
655 return !this->isEmpty();
656 }
658 bool SkAAClip::setEmpty() {
659 this->freeRuns();
660 fBounds.setEmpty();
661 fRunHead = NULL;
662 return false;
663 }
665 bool SkAAClip::setRect(const SkIRect& bounds) {
666 if (bounds.isEmpty()) {
667 return this->setEmpty();
668 }
670 AUTO_AACLIP_VALIDATE(*this);
672 #if 0
673 SkRect r;
674 r.set(bounds);
675 SkPath path;
676 path.addRect(r);
677 return this->setPath(path);
678 #else
679 this->freeRuns();
680 fBounds = bounds;
681 fRunHead = RunHead::AllocRect(bounds);
682 SkASSERT(!this->isEmpty());
683 return true;
684 #endif
685 }
687 bool SkAAClip::setRect(const SkRect& r, bool doAA) {
688 if (r.isEmpty()) {
689 return this->setEmpty();
690 }
692 AUTO_AACLIP_VALIDATE(*this);
694 // TODO: special case this
696 SkPath path;
697 path.addRect(r);
698 return this->setPath(path, NULL, doAA);
699 }
701 static void append_run(SkTDArray<uint8_t>& array, uint8_t value, int count) {
702 SkASSERT(count >= 0);
703 while (count > 0) {
704 int n = count;
705 if (n > 255) {
706 n = 255;
707 }
708 uint8_t* data = array.append(2);
709 data[0] = n;
710 data[1] = value;
711 count -= n;
712 }
713 }
715 bool SkAAClip::setRegion(const SkRegion& rgn) {
716 if (rgn.isEmpty()) {
717 return this->setEmpty();
718 }
719 if (rgn.isRect()) {
720 return this->setRect(rgn.getBounds());
721 }
723 #if 0
724 SkAAClip clip;
725 SkRegion::Iterator iter(rgn);
726 for (; !iter.done(); iter.next()) {
727 clip.op(iter.rect(), SkRegion::kUnion_Op);
728 }
729 this->swap(clip);
730 return !this->isEmpty();
731 #else
732 const SkIRect& bounds = rgn.getBounds();
733 const int offsetX = bounds.fLeft;
734 const int offsetY = bounds.fTop;
736 SkTDArray<YOffset> yArray;
737 SkTDArray<uint8_t> xArray;
739 yArray.setReserve(SkMin32(bounds.height(), 1024));
740 xArray.setReserve(SkMin32(bounds.width() * 128, 64 * 1024));
742 SkRegion::Iterator iter(rgn);
743 int prevRight = 0;
744 int prevBot = 0;
745 YOffset* currY = NULL;
747 for (; !iter.done(); iter.next()) {
748 const SkIRect& r = iter.rect();
749 SkASSERT(bounds.contains(r));
751 int bot = r.fBottom - offsetY;
752 SkASSERT(bot >= prevBot);
753 if (bot > prevBot) {
754 if (currY) {
755 // flush current row
756 append_run(xArray, 0, bounds.width() - prevRight);
757 }
758 // did we introduce an empty-gap from the prev row?
759 int top = r.fTop - offsetY;
760 if (top > prevBot) {
761 currY = yArray.append();
762 currY->fY = top - 1;
763 currY->fOffset = xArray.count();
764 append_run(xArray, 0, bounds.width());
765 }
766 // create a new record for this Y value
767 currY = yArray.append();
768 currY->fY = bot - 1;
769 currY->fOffset = xArray.count();
770 prevRight = 0;
771 prevBot = bot;
772 }
774 int x = r.fLeft - offsetX;
775 append_run(xArray, 0, x - prevRight);
777 int w = r.fRight - r.fLeft;
778 append_run(xArray, 0xFF, w);
779 prevRight = x + w;
780 SkASSERT(prevRight <= bounds.width());
781 }
782 // flush last row
783 append_run(xArray, 0, bounds.width() - prevRight);
785 // now pack everything into a RunHead
786 RunHead* head = RunHead::Alloc(yArray.count(), xArray.bytes());
787 memcpy(head->yoffsets(), yArray.begin(), yArray.bytes());
788 memcpy(head->data(), xArray.begin(), xArray.bytes());
790 this->setEmpty();
791 fBounds = bounds;
792 fRunHead = head;
793 this->validate();
794 return true;
795 #endif
796 }
798 ///////////////////////////////////////////////////////////////////////////////
800 const uint8_t* SkAAClip::findRow(int y, int* lastYForRow) const {
801 SkASSERT(fRunHead);
803 if (!y_in_rect(y, fBounds)) {
804 return NULL;
805 }
806 y -= fBounds.y(); // our yoffs values are relative to the top
808 const YOffset* yoff = fRunHead->yoffsets();
809 while (yoff->fY < y) {
810 yoff += 1;
811 SkASSERT(yoff - fRunHead->yoffsets() < fRunHead->fRowCount);
812 }
814 if (lastYForRow) {
815 *lastYForRow = fBounds.y() + yoff->fY;
816 }
817 return fRunHead->data() + yoff->fOffset;
818 }
820 const uint8_t* SkAAClip::findX(const uint8_t data[], int x, int* initialCount) const {
821 SkASSERT(x_in_rect(x, fBounds));
822 x -= fBounds.x();
824 // first skip up to X
825 for (;;) {
826 int n = data[0];
827 if (x < n) {
828 if (initialCount) {
829 *initialCount = n - x;
830 }
831 break;
832 }
833 data += 2;
834 x -= n;
835 }
836 return data;
837 }
839 bool SkAAClip::quickContains(int left, int top, int right, int bottom) const {
840 if (this->isEmpty()) {
841 return false;
842 }
843 if (!fBounds.contains(left, top, right, bottom)) {
844 return false;
845 }
846 #if 0
847 if (this->isRect()) {
848 return true;
849 }
850 #endif
852 int lastY SK_INIT_TO_AVOID_WARNING;
853 const uint8_t* row = this->findRow(top, &lastY);
854 if (lastY < bottom) {
855 return false;
856 }
857 // now just need to check in X
858 int count;
859 row = this->findX(row, left, &count);
860 #if 0
861 return count >= (right - left) && 0xFF == row[1];
862 #else
863 int rectWidth = right - left;
864 while (0xFF == row[1]) {
865 if (count >= rectWidth) {
866 return true;
867 }
868 rectWidth -= count;
869 row += 2;
870 count = row[0];
871 }
872 return false;
873 #endif
874 }
876 ///////////////////////////////////////////////////////////////////////////////
878 class SkAAClip::Builder {
879 SkIRect fBounds;
880 struct Row {
881 int fY;
882 int fWidth;
883 SkTDArray<uint8_t>* fData;
884 };
885 SkTDArray<Row> fRows;
886 Row* fCurrRow;
887 int fPrevY;
888 int fWidth;
889 int fMinY;
891 public:
892 Builder(const SkIRect& bounds) : fBounds(bounds) {
893 fPrevY = -1;
894 fWidth = bounds.width();
895 fCurrRow = NULL;
896 fMinY = bounds.fTop;
897 }
899 ~Builder() {
900 Row* row = fRows.begin();
901 Row* stop = fRows.end();
902 while (row < stop) {
903 delete row->fData;
904 row += 1;
905 }
906 }
908 const SkIRect& getBounds() const { return fBounds; }
910 void addRun(int x, int y, U8CPU alpha, int count) {
911 SkASSERT(count > 0);
912 SkASSERT(fBounds.contains(x, y));
913 SkASSERT(fBounds.contains(x + count - 1, y));
915 x -= fBounds.left();
916 y -= fBounds.top();
918 Row* row = fCurrRow;
919 if (y != fPrevY) {
920 SkASSERT(y > fPrevY);
921 fPrevY = y;
922 row = this->flushRow(true);
923 row->fY = y;
924 row->fWidth = 0;
925 SkASSERT(row->fData);
926 SkASSERT(0 == row->fData->count());
927 fCurrRow = row;
928 }
930 SkASSERT(row->fWidth <= x);
931 SkASSERT(row->fWidth < fBounds.width());
933 SkTDArray<uint8_t>& data = *row->fData;
935 int gap = x - row->fWidth;
936 if (gap) {
937 AppendRun(data, 0, gap);
938 row->fWidth += gap;
939 SkASSERT(row->fWidth < fBounds.width());
940 }
942 AppendRun(data, alpha, count);
943 row->fWidth += count;
944 SkASSERT(row->fWidth <= fBounds.width());
945 }
947 void addColumn(int x, int y, U8CPU alpha, int height) {
948 SkASSERT(fBounds.contains(x, y + height - 1));
950 this->addRun(x, y, alpha, 1);
951 this->flushRowH(fCurrRow);
952 y -= fBounds.fTop;
953 SkASSERT(y == fCurrRow->fY);
954 fCurrRow->fY = y + height - 1;
955 }
957 void addRectRun(int x, int y, int width, int height) {
958 SkASSERT(fBounds.contains(x + width - 1, y + height - 1));
959 this->addRun(x, y, 0xFF, width);
961 // we assum the rect must be all we'll see for these scanlines
962 // so we ensure our row goes all the way to our right
963 this->flushRowH(fCurrRow);
965 y -= fBounds.fTop;
966 SkASSERT(y == fCurrRow->fY);
967 fCurrRow->fY = y + height - 1;
968 }
970 void addAntiRectRun(int x, int y, int width, int height,
971 SkAlpha leftAlpha, SkAlpha rightAlpha) {
972 SkASSERT(fBounds.contains(x + width - 1 +
973 (leftAlpha > 0 ? 1 : 0) + (rightAlpha > 0 ? 1 : 0),
974 y + height - 1));
975 SkASSERT(width >= 0);
977 // Conceptually we're always adding 3 runs, but we should
978 // merge or omit them if possible.
979 if (leftAlpha == 0xFF) {
980 width++;
981 } else if (leftAlpha > 0) {
982 this->addRun(x++, y, leftAlpha, 1);
983 }
984 if (rightAlpha == 0xFF) {
985 width++;
986 }
987 if (width > 0) {
988 this->addRun(x, y, 0xFF, width);
989 }
990 if (rightAlpha > 0 && rightAlpha < 255) {
991 this->addRun(x + width, y, rightAlpha, 1);
992 }
994 // we assume the rect must be all we'll see for these scanlines
995 // so we ensure our row goes all the way to our right
996 this->flushRowH(fCurrRow);
998 y -= fBounds.fTop;
999 SkASSERT(y == fCurrRow->fY);
1000 fCurrRow->fY = y + height - 1;
1001 }
1003 bool finish(SkAAClip* target) {
1004 this->flushRow(false);
1006 const Row* row = fRows.begin();
1007 const Row* stop = fRows.end();
1009 size_t dataSize = 0;
1010 while (row < stop) {
1011 dataSize += row->fData->count();
1012 row += 1;
1013 }
1015 if (0 == dataSize) {
1016 return target->setEmpty();
1017 }
1019 SkASSERT(fMinY >= fBounds.fTop);
1020 SkASSERT(fMinY < fBounds.fBottom);
1021 int adjustY = fMinY - fBounds.fTop;
1022 fBounds.fTop = fMinY;
1024 RunHead* head = RunHead::Alloc(fRows.count(), dataSize);
1025 YOffset* yoffset = head->yoffsets();
1026 uint8_t* data = head->data();
1027 uint8_t* baseData = data;
1029 row = fRows.begin();
1030 SkDEBUGCODE(int prevY = row->fY - 1;)
1031 while (row < stop) {
1032 SkASSERT(prevY < row->fY); // must be monotonic
1033 SkDEBUGCODE(prevY = row->fY);
1035 yoffset->fY = row->fY - adjustY;
1036 yoffset->fOffset = SkToU32(data - baseData);
1037 yoffset += 1;
1039 size_t n = row->fData->count();
1040 memcpy(data, row->fData->begin(), n);
1041 #ifdef SK_DEBUG
1042 size_t bytesNeeded = compute_row_length(data, fBounds.width());
1043 SkASSERT(bytesNeeded == n);
1044 #endif
1045 data += n;
1047 row += 1;
1048 }
1050 target->freeRuns();
1051 target->fBounds = fBounds;
1052 target->fRunHead = head;
1053 return target->trimBounds();
1054 }
1056 void dump() {
1057 this->validate();
1058 int y;
1059 for (y = 0; y < fRows.count(); ++y) {
1060 const Row& row = fRows[y];
1061 SkDebugf("Y:%3d W:%3d", row.fY, row.fWidth);
1062 const SkTDArray<uint8_t>& data = *row.fData;
1063 int count = data.count();
1064 SkASSERT(!(count & 1));
1065 const uint8_t* ptr = data.begin();
1066 for (int x = 0; x < count; x += 2) {
1067 SkDebugf(" [%3d:%02X]", ptr[0], ptr[1]);
1068 ptr += 2;
1069 }
1070 SkDebugf("\n");
1071 }
1072 }
1074 void validate() {
1075 #ifdef SK_DEBUG
1076 if (false) { // avoid bit rot, suppress warning
1077 test_count_left_right_zeros();
1078 }
1079 int prevY = -1;
1080 for (int i = 0; i < fRows.count(); ++i) {
1081 const Row& row = fRows[i];
1082 SkASSERT(prevY < row.fY);
1083 SkASSERT(fWidth == row.fWidth);
1084 int count = row.fData->count();
1085 const uint8_t* ptr = row.fData->begin();
1086 SkASSERT(!(count & 1));
1087 int w = 0;
1088 for (int x = 0; x < count; x += 2) {
1089 int n = ptr[0];
1090 SkASSERT(n > 0);
1091 w += n;
1092 SkASSERT(w <= fWidth);
1093 ptr += 2;
1094 }
1095 SkASSERT(w == fWidth);
1096 prevY = row.fY;
1097 }
1098 #endif
1099 }
1101 // only called by BuilderBlitter
1102 void setMinY(int y) {
1103 fMinY = y;
1104 }
1106 private:
1107 void flushRowH(Row* row) {
1108 // flush current row if needed
1109 if (row->fWidth < fWidth) {
1110 AppendRun(*row->fData, 0, fWidth - row->fWidth);
1111 row->fWidth = fWidth;
1112 }
1113 }
1115 Row* flushRow(bool readyForAnother) {
1116 Row* next = NULL;
1117 int count = fRows.count();
1118 if (count > 0) {
1119 this->flushRowH(&fRows[count - 1]);
1120 }
1121 if (count > 1) {
1122 // are our last two runs the same?
1123 Row* prev = &fRows[count - 2];
1124 Row* curr = &fRows[count - 1];
1125 SkASSERT(prev->fWidth == fWidth);
1126 SkASSERT(curr->fWidth == fWidth);
1127 if (*prev->fData == *curr->fData) {
1128 prev->fY = curr->fY;
1129 if (readyForAnother) {
1130 curr->fData->rewind();
1131 next = curr;
1132 } else {
1133 delete curr->fData;
1134 fRows.removeShuffle(count - 1);
1135 }
1136 } else {
1137 if (readyForAnother) {
1138 next = fRows.append();
1139 next->fData = new SkTDArray<uint8_t>;
1140 }
1141 }
1142 } else {
1143 if (readyForAnother) {
1144 next = fRows.append();
1145 next->fData = new SkTDArray<uint8_t>;
1146 }
1147 }
1148 return next;
1149 }
1151 static void AppendRun(SkTDArray<uint8_t>& data, U8CPU alpha, int count) {
1152 do {
1153 int n = count;
1154 if (n > 255) {
1155 n = 255;
1156 }
1157 uint8_t* ptr = data.append(2);
1158 ptr[0] = n;
1159 ptr[1] = alpha;
1160 count -= n;
1161 } while (count > 0);
1162 }
1163 };
1165 class SkAAClip::BuilderBlitter : public SkBlitter {
1166 int fLastY;
1168 /*
1169 If we see a gap of 1 or more empty scanlines while building in Y-order,
1170 we inject an explicit empty scanline (alpha==0)
1172 See AAClipTest.cpp : test_path_with_hole()
1173 */
1174 void checkForYGap(int y) {
1175 SkASSERT(y >= fLastY);
1176 if (fLastY > -SK_MaxS32) {
1177 int gap = y - fLastY;
1178 if (gap > 1) {
1179 fBuilder->addRun(fLeft, y - 1, 0, fRight - fLeft);
1180 }
1181 }
1182 fLastY = y;
1183 }
1185 public:
1187 BuilderBlitter(Builder* builder) {
1188 fBuilder = builder;
1189 fLeft = builder->getBounds().fLeft;
1190 fRight = builder->getBounds().fRight;
1191 fMinY = SK_MaxS32;
1192 fLastY = -SK_MaxS32; // sentinel
1193 }
1195 void finish() {
1196 if (fMinY < SK_MaxS32) {
1197 fBuilder->setMinY(fMinY);
1198 }
1199 }
1201 /**
1202 Must evaluate clips in scan-line order, so don't want to allow blitV(),
1203 but an AAClip can be clipped down to a single pixel wide, so we
1204 must support it (given AntiRect semantics: minimum width is 2).
1205 Instead we'll rely on the runtime asserts to guarantee Y monotonicity;
1206 any failure cases that misses may have minor artifacts.
1207 */
1208 virtual void blitV(int x, int y, int height, SkAlpha alpha) SK_OVERRIDE {
1209 this->recordMinY(y);
1210 fBuilder->addColumn(x, y, alpha, height);
1211 fLastY = y + height - 1;
1212 }
1214 virtual void blitRect(int x, int y, int width, int height) SK_OVERRIDE {
1215 this->recordMinY(y);
1216 this->checkForYGap(y);
1217 fBuilder->addRectRun(x, y, width, height);
1218 fLastY = y + height - 1;
1219 }
1221 virtual void blitAntiRect(int x, int y, int width, int height,
1222 SkAlpha leftAlpha, SkAlpha rightAlpha) SK_OVERRIDE {
1223 this->recordMinY(y);
1224 this->checkForYGap(y);
1225 fBuilder->addAntiRectRun(x, y, width, height, leftAlpha, rightAlpha);
1226 fLastY = y + height - 1;
1227 }
1229 virtual void blitMask(const SkMask&, const SkIRect& clip) SK_OVERRIDE
1230 { unexpected(); }
1232 virtual const SkBitmap* justAnOpaqueColor(uint32_t*) SK_OVERRIDE {
1233 return NULL;
1234 }
1236 virtual void blitH(int x, int y, int width) SK_OVERRIDE {
1237 this->recordMinY(y);
1238 this->checkForYGap(y);
1239 fBuilder->addRun(x, y, 0xFF, width);
1240 }
1242 virtual void blitAntiH(int x, int y, const SkAlpha alpha[],
1243 const int16_t runs[]) SK_OVERRIDE {
1244 this->recordMinY(y);
1245 this->checkForYGap(y);
1246 for (;;) {
1247 int count = *runs;
1248 if (count <= 0) {
1249 return;
1250 }
1252 // The supersampler's buffer can be the width of the device, so
1253 // we may have to trim the run to our bounds. If so, we assert that
1254 // the extra spans are always alpha==0
1255 int localX = x;
1256 int localCount = count;
1257 if (x < fLeft) {
1258 SkASSERT(0 == *alpha);
1259 int gap = fLeft - x;
1260 SkASSERT(gap <= count);
1261 localX += gap;
1262 localCount -= gap;
1263 }
1264 int right = x + count;
1265 if (right > fRight) {
1266 SkASSERT(0 == *alpha);
1267 localCount -= right - fRight;
1268 SkASSERT(localCount >= 0);
1269 }
1271 if (localCount) {
1272 fBuilder->addRun(localX, y, *alpha, localCount);
1273 }
1274 // Next run
1275 runs += count;
1276 alpha += count;
1277 x += count;
1278 }
1279 }
1281 private:
1282 Builder* fBuilder;
1283 int fLeft; // cache of builder's bounds' left edge
1284 int fRight;
1285 int fMinY;
1287 /*
1288 * We track this, in case the scan converter skipped some number of
1289 * scanlines at the (relative to the bounds it was given). This allows
1290 * the builder, during its finish, to trip its bounds down to the "real"
1291 * top.
1292 */
1293 void recordMinY(int y) {
1294 if (y < fMinY) {
1295 fMinY = y;
1296 }
1297 }
1299 void unexpected() {
1300 SkDebugf("---- did not expect to get called here");
1301 sk_throw();
1302 }
1303 };
1305 bool SkAAClip::setPath(const SkPath& path, const SkRegion* clip, bool doAA) {
1306 AUTO_AACLIP_VALIDATE(*this);
1308 if (clip && clip->isEmpty()) {
1309 return this->setEmpty();
1310 }
1312 SkIRect ibounds;
1313 path.getBounds().roundOut(&ibounds);
1315 SkRegion tmpClip;
1316 if (NULL == clip) {
1317 tmpClip.setRect(ibounds);
1318 clip = &tmpClip;
1319 }
1321 if (path.isInverseFillType()) {
1322 ibounds = clip->getBounds();
1323 } else {
1324 if (ibounds.isEmpty() || !ibounds.intersect(clip->getBounds())) {
1325 return this->setEmpty();
1326 }
1327 }
1329 Builder builder(ibounds);
1330 BuilderBlitter blitter(&builder);
1332 if (doAA) {
1333 SkScan::AntiFillPath(path, *clip, &blitter, true);
1334 } else {
1335 SkScan::FillPath(path, *clip, &blitter);
1336 }
1338 blitter.finish();
1339 return builder.finish(this);
1340 }
1342 ///////////////////////////////////////////////////////////////////////////////
1344 typedef void (*RowProc)(SkAAClip::Builder&, int bottom,
1345 const uint8_t* rowA, const SkIRect& rectA,
1346 const uint8_t* rowB, const SkIRect& rectB);
1348 typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB);
1350 static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1351 // Multiply
1352 return SkMulDiv255Round(alphaA, alphaB);
1353 }
1355 static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1356 // SrcOver
1357 return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB);
1358 }
1360 static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1361 // SrcOut
1362 return SkMulDiv255Round(alphaA, 0xFF - alphaB);
1363 }
1365 static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1366 // XOR
1367 return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB);
1368 }
1370 static AlphaProc find_alpha_proc(SkRegion::Op op) {
1371 switch (op) {
1372 case SkRegion::kIntersect_Op:
1373 return sectAlphaProc;
1374 case SkRegion::kDifference_Op:
1375 return diffAlphaProc;
1376 case SkRegion::kUnion_Op:
1377 return unionAlphaProc;
1378 case SkRegion::kXOR_Op:
1379 return xorAlphaProc;
1380 default:
1381 SkDEBUGFAIL("unexpected region op");
1382 return sectAlphaProc;
1383 }
1384 }
1386 class RowIter {
1387 public:
1388 RowIter(const uint8_t* row, const SkIRect& bounds) {
1389 fRow = row;
1390 fLeft = bounds.fLeft;
1391 fBoundsRight = bounds.fRight;
1392 if (row) {
1393 fRight = bounds.fLeft + row[0];
1394 SkASSERT(fRight <= fBoundsRight);
1395 fAlpha = row[1];
1396 fDone = false;
1397 } else {
1398 fDone = true;
1399 fRight = kMaxInt32;
1400 fAlpha = 0;
1401 }
1402 }
1404 bool done() const { return fDone; }
1405 int left() const { return fLeft; }
1406 int right() const { return fRight; }
1407 U8CPU alpha() const { return fAlpha; }
1408 void next() {
1409 if (!fDone) {
1410 fLeft = fRight;
1411 if (fRight == fBoundsRight) {
1412 fDone = true;
1413 fRight = kMaxInt32;
1414 fAlpha = 0;
1415 } else {
1416 fRow += 2;
1417 fRight += fRow[0];
1418 fAlpha = fRow[1];
1419 SkASSERT(fRight <= fBoundsRight);
1420 }
1421 }
1422 }
1424 private:
1425 const uint8_t* fRow;
1426 int fLeft;
1427 int fRight;
1428 int fBoundsRight;
1429 bool fDone;
1430 uint8_t fAlpha;
1431 };
1433 static void adjust_row(RowIter& iter, int& leftA, int& riteA, int rite) {
1434 if (rite == riteA) {
1435 iter.next();
1436 leftA = iter.left();
1437 riteA = iter.right();
1438 }
1439 }
1441 #if 0 // UNUSED
1442 static bool intersect(int& min, int& max, int boundsMin, int boundsMax) {
1443 SkASSERT(min < max);
1444 SkASSERT(boundsMin < boundsMax);
1445 if (min >= boundsMax || max <= boundsMin) {
1446 return false;
1447 }
1448 if (min < boundsMin) {
1449 min = boundsMin;
1450 }
1451 if (max > boundsMax) {
1452 max = boundsMax;
1453 }
1454 return true;
1455 }
1456 #endif
1458 static void operatorX(SkAAClip::Builder& builder, int lastY,
1459 RowIter& iterA, RowIter& iterB,
1460 AlphaProc proc, const SkIRect& bounds) {
1461 int leftA = iterA.left();
1462 int riteA = iterA.right();
1463 int leftB = iterB.left();
1464 int riteB = iterB.right();
1466 int prevRite = bounds.fLeft;
1468 do {
1469 U8CPU alphaA = 0;
1470 U8CPU alphaB = 0;
1471 int left, rite;
1473 if (leftA < leftB) {
1474 left = leftA;
1475 alphaA = iterA.alpha();
1476 if (riteA <= leftB) {
1477 rite = riteA;
1478 } else {
1479 rite = leftA = leftB;
1480 }
1481 } else if (leftB < leftA) {
1482 left = leftB;
1483 alphaB = iterB.alpha();
1484 if (riteB <= leftA) {
1485 rite = riteB;
1486 } else {
1487 rite = leftB = leftA;
1488 }
1489 } else {
1490 left = leftA; // or leftB, since leftA == leftB
1491 rite = leftA = leftB = SkMin32(riteA, riteB);
1492 alphaA = iterA.alpha();
1493 alphaB = iterB.alpha();
1494 }
1496 if (left >= bounds.fRight) {
1497 break;
1498 }
1499 if (rite > bounds.fRight) {
1500 rite = bounds.fRight;
1501 }
1503 if (left >= bounds.fLeft) {
1504 SkASSERT(rite > left);
1505 builder.addRun(left, lastY, proc(alphaA, alphaB), rite - left);
1506 prevRite = rite;
1507 }
1509 adjust_row(iterA, leftA, riteA, rite);
1510 adjust_row(iterB, leftB, riteB, rite);
1511 } while (!iterA.done() || !iterB.done());
1513 if (prevRite < bounds.fRight) {
1514 builder.addRun(prevRite, lastY, 0, bounds.fRight - prevRite);
1515 }
1516 }
1518 static void adjust_iter(SkAAClip::Iter& iter, int& topA, int& botA, int bot) {
1519 if (bot == botA) {
1520 iter.next();
1521 topA = botA;
1522 SkASSERT(botA == iter.top());
1523 botA = iter.bottom();
1524 }
1525 }
1527 static void operateY(SkAAClip::Builder& builder, const SkAAClip& A,
1528 const SkAAClip& B, SkRegion::Op op) {
1529 AlphaProc proc = find_alpha_proc(op);
1530 const SkIRect& bounds = builder.getBounds();
1532 SkAAClip::Iter iterA(A);
1533 SkAAClip::Iter iterB(B);
1535 SkASSERT(!iterA.done());
1536 int topA = iterA.top();
1537 int botA = iterA.bottom();
1538 SkASSERT(!iterB.done());
1539 int topB = iterB.top();
1540 int botB = iterB.bottom();
1542 do {
1543 const uint8_t* rowA = NULL;
1544 const uint8_t* rowB = NULL;
1545 int top, bot;
1547 if (topA < topB) {
1548 top = topA;
1549 rowA = iterA.data();
1550 if (botA <= topB) {
1551 bot = botA;
1552 } else {
1553 bot = topA = topB;
1554 }
1556 } else if (topB < topA) {
1557 top = topB;
1558 rowB = iterB.data();
1559 if (botB <= topA) {
1560 bot = botB;
1561 } else {
1562 bot = topB = topA;
1563 }
1564 } else {
1565 top = topA; // or topB, since topA == topB
1566 bot = topA = topB = SkMin32(botA, botB);
1567 rowA = iterA.data();
1568 rowB = iterB.data();
1569 }
1571 if (top >= bounds.fBottom) {
1572 break;
1573 }
1575 if (bot > bounds.fBottom) {
1576 bot = bounds.fBottom;
1577 }
1578 SkASSERT(top < bot);
1580 if (!rowA && !rowB) {
1581 builder.addRun(bounds.fLeft, bot - 1, 0, bounds.width());
1582 } else if (top >= bounds.fTop) {
1583 SkASSERT(bot <= bounds.fBottom);
1584 RowIter rowIterA(rowA, rowA ? A.getBounds() : bounds);
1585 RowIter rowIterB(rowB, rowB ? B.getBounds() : bounds);
1586 operatorX(builder, bot - 1, rowIterA, rowIterB, proc, bounds);
1587 }
1589 adjust_iter(iterA, topA, botA, bot);
1590 adjust_iter(iterB, topB, botB, bot);
1591 } while (!iterA.done() || !iterB.done());
1592 }
1594 bool SkAAClip::op(const SkAAClip& clipAOrig, const SkAAClip& clipBOrig,
1595 SkRegion::Op op) {
1596 AUTO_AACLIP_VALIDATE(*this);
1598 if (SkRegion::kReplace_Op == op) {
1599 return this->set(clipBOrig);
1600 }
1602 const SkAAClip* clipA = &clipAOrig;
1603 const SkAAClip* clipB = &clipBOrig;
1605 if (SkRegion::kReverseDifference_Op == op) {
1606 SkTSwap(clipA, clipB);
1607 op = SkRegion::kDifference_Op;
1608 }
1610 bool a_empty = clipA->isEmpty();
1611 bool b_empty = clipB->isEmpty();
1613 SkIRect bounds;
1614 switch (op) {
1615 case SkRegion::kDifference_Op:
1616 if (a_empty) {
1617 return this->setEmpty();
1618 }
1619 if (b_empty || !SkIRect::Intersects(clipA->fBounds, clipB->fBounds)) {
1620 return this->set(*clipA);
1621 }
1622 bounds = clipA->fBounds;
1623 break;
1625 case SkRegion::kIntersect_Op:
1626 if ((a_empty | b_empty) || !bounds.intersect(clipA->fBounds,
1627 clipB->fBounds)) {
1628 return this->setEmpty();
1629 }
1630 break;
1632 case SkRegion::kUnion_Op:
1633 case SkRegion::kXOR_Op:
1634 if (a_empty) {
1635 return this->set(*clipB);
1636 }
1637 if (b_empty) {
1638 return this->set(*clipA);
1639 }
1640 bounds = clipA->fBounds;
1641 bounds.join(clipB->fBounds);
1642 break;
1644 default:
1645 SkDEBUGFAIL("unknown region op");
1646 return !this->isEmpty();
1647 }
1649 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds));
1650 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds));
1652 Builder builder(bounds);
1653 operateY(builder, *clipA, *clipB, op);
1655 return builder.finish(this);
1656 }
1658 /*
1659 * It can be expensive to build a local aaclip before applying the op, so
1660 * we first see if we can restrict the bounds of new rect to our current
1661 * bounds, or note that the new rect subsumes our current clip.
1662 */
1664 bool SkAAClip::op(const SkIRect& rOrig, SkRegion::Op op) {
1665 SkIRect rStorage;
1666 const SkIRect* r = &rOrig;
1668 switch (op) {
1669 case SkRegion::kIntersect_Op:
1670 if (!rStorage.intersect(rOrig, fBounds)) {
1671 // no overlap, so we're empty
1672 return this->setEmpty();
1673 }
1674 if (rStorage == fBounds) {
1675 // we were wholly inside the rect, no change
1676 return !this->isEmpty();
1677 }
1678 if (this->quickContains(rStorage)) {
1679 // the intersection is wholly inside us, we're a rect
1680 return this->setRect(rStorage);
1681 }
1682 r = &rStorage; // use the intersected bounds
1683 break;
1684 case SkRegion::kDifference_Op:
1685 break;
1686 case SkRegion::kUnion_Op:
1687 if (rOrig.contains(fBounds)) {
1688 return this->setRect(rOrig);
1689 }
1690 break;
1691 default:
1692 break;
1693 }
1695 SkAAClip clip;
1696 clip.setRect(*r);
1697 return this->op(*this, clip, op);
1698 }
1700 bool SkAAClip::op(const SkRect& rOrig, SkRegion::Op op, bool doAA) {
1701 SkRect rStorage, boundsStorage;
1702 const SkRect* r = &rOrig;
1704 boundsStorage.set(fBounds);
1705 switch (op) {
1706 case SkRegion::kIntersect_Op:
1707 case SkRegion::kDifference_Op:
1708 if (!rStorage.intersect(rOrig, boundsStorage)) {
1709 if (SkRegion::kIntersect_Op == op) {
1710 return this->setEmpty();
1711 } else { // kDifference
1712 return !this->isEmpty();
1713 }
1714 }
1715 r = &rStorage; // use the intersected bounds
1716 break;
1717 case SkRegion::kUnion_Op:
1718 if (rOrig.contains(boundsStorage)) {
1719 return this->setRect(rOrig);
1720 }
1721 break;
1722 default:
1723 break;
1724 }
1726 SkAAClip clip;
1727 clip.setRect(*r, doAA);
1728 return this->op(*this, clip, op);
1729 }
1731 bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) {
1732 return this->op(*this, clip, op);
1733 }
1735 ///////////////////////////////////////////////////////////////////////////////
1737 bool SkAAClip::translate(int dx, int dy, SkAAClip* dst) const {
1738 if (NULL == dst) {
1739 return !this->isEmpty();
1740 }
1742 if (this->isEmpty()) {
1743 return dst->setEmpty();
1744 }
1746 if (this != dst) {
1747 sk_atomic_inc(&fRunHead->fRefCnt);
1748 dst->freeRuns();
1749 dst->fRunHead = fRunHead;
1750 dst->fBounds = fBounds;
1751 }
1752 dst->fBounds.offset(dx, dy);
1753 return true;
1754 }
1756 static void expand_row_to_mask(uint8_t* SK_RESTRICT mask,
1757 const uint8_t* SK_RESTRICT row,
1758 int width) {
1759 while (width > 0) {
1760 int n = row[0];
1761 SkASSERT(width >= n);
1762 memset(mask, row[1], n);
1763 mask += n;
1764 row += 2;
1765 width -= n;
1766 }
1767 SkASSERT(0 == width);
1768 }
1770 void SkAAClip::copyToMask(SkMask* mask) const {
1771 mask->fFormat = SkMask::kA8_Format;
1772 if (this->isEmpty()) {
1773 mask->fBounds.setEmpty();
1774 mask->fImage = NULL;
1775 mask->fRowBytes = 0;
1776 return;
1777 }
1779 mask->fBounds = fBounds;
1780 mask->fRowBytes = fBounds.width();
1781 size_t size = mask->computeImageSize();
1782 mask->fImage = SkMask::AllocImage(size);
1784 Iter iter(*this);
1785 uint8_t* dst = mask->fImage;
1786 const int width = fBounds.width();
1788 int y = fBounds.fTop;
1789 while (!iter.done()) {
1790 do {
1791 expand_row_to_mask(dst, iter.data(), width);
1792 dst += mask->fRowBytes;
1793 } while (++y < iter.bottom());
1794 iter.next();
1795 }
1796 }
1798 ///////////////////////////////////////////////////////////////////////////////
1799 ///////////////////////////////////////////////////////////////////////////////
1801 static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width,
1802 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) {
1803 // we don't read our initial n from data, since the caller may have had to
1804 // clip it, hence the initialCount parameter.
1805 int n = initialCount;
1806 for (;;) {
1807 if (n > width) {
1808 n = width;
1809 }
1810 SkASSERT(n > 0);
1811 runs[0] = n;
1812 runs += n;
1814 aa[0] = data[1];
1815 aa += n;
1817 data += 2;
1818 width -= n;
1819 if (0 == width) {
1820 break;
1821 }
1822 // load the next count
1823 n = data[0];
1824 }
1825 runs[0] = 0; // sentinel
1826 }
1828 SkAAClipBlitter::~SkAAClipBlitter() {
1829 sk_free(fScanlineScratch);
1830 }
1832 void SkAAClipBlitter::ensureRunsAndAA() {
1833 if (NULL == fScanlineScratch) {
1834 // add 1 so we can store the terminating run count of 0
1835 int count = fAAClipBounds.width() + 1;
1836 // we use this either for fRuns + fAA, or a scaline of a mask
1837 // which may be as deep as 32bits
1838 fScanlineScratch = sk_malloc_throw(count * sizeof(SkPMColor));
1839 fRuns = (int16_t*)fScanlineScratch;
1840 fAA = (SkAlpha*)(fRuns + count);
1841 }
1842 }
1844 void SkAAClipBlitter::blitH(int x, int y, int width) {
1845 SkASSERT(width > 0);
1846 SkASSERT(fAAClipBounds.contains(x, y));
1847 SkASSERT(fAAClipBounds.contains(x + width - 1, y));
1849 const uint8_t* row = fAAClip->findRow(y);
1850 int initialCount;
1851 row = fAAClip->findX(row, x, &initialCount);
1853 if (initialCount >= width) {
1854 SkAlpha alpha = row[1];
1855 if (0 == alpha) {
1856 return;
1857 }
1858 if (0xFF == alpha) {
1859 fBlitter->blitH(x, y, width);
1860 return;
1861 }
1862 }
1864 this->ensureRunsAndAA();
1865 expandToRuns(row, initialCount, width, fRuns, fAA);
1867 fBlitter->blitAntiH(x, y, fAA, fRuns);
1868 }
1870 static void merge(const uint8_t* SK_RESTRICT row, int rowN,
1871 const SkAlpha* SK_RESTRICT srcAA,
1872 const int16_t* SK_RESTRICT srcRuns,
1873 SkAlpha* SK_RESTRICT dstAA,
1874 int16_t* SK_RESTRICT dstRuns,
1875 int width) {
1876 SkDEBUGCODE(int accumulated = 0;)
1877 int srcN = srcRuns[0];
1878 // do we need this check?
1879 if (0 == srcN) {
1880 return;
1881 }
1883 for (;;) {
1884 SkASSERT(rowN > 0);
1885 SkASSERT(srcN > 0);
1887 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]);
1888 int minN = SkMin32(srcN, rowN);
1889 dstRuns[0] = minN;
1890 dstRuns += minN;
1891 dstAA[0] = newAlpha;
1892 dstAA += minN;
1894 if (0 == (srcN -= minN)) {
1895 srcN = srcRuns[0]; // refresh
1896 srcRuns += srcN;
1897 srcAA += srcN;
1898 srcN = srcRuns[0]; // reload
1899 if (0 == srcN) {
1900 break;
1901 }
1902 }
1903 if (0 == (rowN -= minN)) {
1904 row += 2;
1905 rowN = row[0]; // reload
1906 }
1908 SkDEBUGCODE(accumulated += minN;)
1909 SkASSERT(accumulated <= width);
1910 }
1911 dstRuns[0] = 0;
1912 }
1914 void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[],
1915 const int16_t runs[]) {
1917 const uint8_t* row = fAAClip->findRow(y);
1918 int initialCount;
1919 row = fAAClip->findX(row, x, &initialCount);
1921 this->ensureRunsAndAA();
1923 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width());
1924 fBlitter->blitAntiH(x, y, fAA, fRuns);
1925 }
1927 void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
1928 if (fAAClip->quickContains(x, y, x + 1, y + height)) {
1929 fBlitter->blitV(x, y, height, alpha);
1930 return;
1931 }
1933 for (;;) {
1934 int lastY SK_INIT_TO_AVOID_WARNING;
1935 const uint8_t* row = fAAClip->findRow(y, &lastY);
1936 int dy = lastY - y + 1;
1937 if (dy > height) {
1938 dy = height;
1939 }
1940 height -= dy;
1942 row = fAAClip->findX(row, x);
1943 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]);
1944 if (newAlpha) {
1945 fBlitter->blitV(x, y, dy, newAlpha);
1946 }
1947 SkASSERT(height >= 0);
1948 if (height <= 0) {
1949 break;
1950 }
1951 y = lastY + 1;
1952 }
1953 }
1955 void SkAAClipBlitter::blitRect(int x, int y, int width, int height) {
1956 if (fAAClip->quickContains(x, y, x + width, y + height)) {
1957 fBlitter->blitRect(x, y, width, height);
1958 return;
1959 }
1961 while (--height >= 0) {
1962 this->blitH(x, y, width);
1963 y += 1;
1964 }
1965 }
1967 typedef void (*MergeAAProc)(const void* src, int width, const uint8_t* row,
1968 int initialRowCount, void* dst);
1970 static void small_memcpy(void* dst, const void* src, size_t n) {
1971 memcpy(dst, src, n);
1972 }
1974 static void small_bzero(void* dst, size_t n) {
1975 sk_bzero(dst, n);
1976 }
1978 static inline uint8_t mergeOne(uint8_t value, unsigned alpha) {
1979 return SkMulDiv255Round(value, alpha);
1980 }
1981 static inline uint16_t mergeOne(uint16_t value, unsigned alpha) {
1982 unsigned r = SkGetPackedR16(value);
1983 unsigned g = SkGetPackedG16(value);
1984 unsigned b = SkGetPackedB16(value);
1985 return SkPackRGB16(SkMulDiv255Round(r, alpha),
1986 SkMulDiv255Round(g, alpha),
1987 SkMulDiv255Round(b, alpha));
1988 }
1989 static inline SkPMColor mergeOne(SkPMColor value, unsigned alpha) {
1990 unsigned a = SkGetPackedA32(value);
1991 unsigned r = SkGetPackedR32(value);
1992 unsigned g = SkGetPackedG32(value);
1993 unsigned b = SkGetPackedB32(value);
1994 return SkPackARGB32(SkMulDiv255Round(a, alpha),
1995 SkMulDiv255Round(r, alpha),
1996 SkMulDiv255Round(g, alpha),
1997 SkMulDiv255Round(b, alpha));
1998 }
2000 template <typename T> void mergeT(const T* SK_RESTRICT src, int srcN,
2001 const uint8_t* SK_RESTRICT row, int rowN,
2002 T* SK_RESTRICT dst) {
2003 for (;;) {
2004 SkASSERT(rowN > 0);
2005 SkASSERT(srcN > 0);
2007 int n = SkMin32(rowN, srcN);
2008 unsigned rowA = row[1];
2009 if (0xFF == rowA) {
2010 small_memcpy(dst, src, n * sizeof(T));
2011 } else if (0 == rowA) {
2012 small_bzero(dst, n * sizeof(T));
2013 } else {
2014 for (int i = 0; i < n; ++i) {
2015 dst[i] = mergeOne(src[i], rowA);
2016 }
2017 }
2019 if (0 == (srcN -= n)) {
2020 break;
2021 }
2023 src += n;
2024 dst += n;
2026 SkASSERT(rowN == n);
2027 row += 2;
2028 rowN = row[0];
2029 }
2030 }
2032 static MergeAAProc find_merge_aa_proc(SkMask::Format format) {
2033 switch (format) {
2034 case SkMask::kBW_Format:
2035 SkDEBUGFAIL("unsupported");
2036 return NULL;
2037 case SkMask::kA8_Format:
2038 case SkMask::k3D_Format: {
2039 void (*proc8)(const uint8_t*, int, const uint8_t*, int, uint8_t*) = mergeT;
2040 return (MergeAAProc)proc8;
2041 }
2042 case SkMask::kLCD16_Format: {
2043 void (*proc16)(const uint16_t*, int, const uint8_t*, int, uint16_t*) = mergeT;
2044 return (MergeAAProc)proc16;
2045 }
2046 case SkMask::kLCD32_Format: {
2047 void (*proc32)(const SkPMColor*, int, const uint8_t*, int, SkPMColor*) = mergeT;
2048 return (MergeAAProc)proc32;
2049 }
2050 default:
2051 SkDEBUGFAIL("unsupported");
2052 return NULL;
2053 }
2054 }
2056 static U8CPU bit2byte(int bitInAByte) {
2057 SkASSERT(bitInAByte <= 0xFF);
2058 // negation turns any non-zero into 0xFFFFFF??, so we just shift down
2059 // some value >= 8 to get a full FF value
2060 return -bitInAByte >> 8;
2061 }
2063 static void upscaleBW2A8(SkMask* dstMask, const SkMask& srcMask) {
2064 SkASSERT(SkMask::kBW_Format == srcMask.fFormat);
2065 SkASSERT(SkMask::kA8_Format == dstMask->fFormat);
2067 const int width = srcMask.fBounds.width();
2068 const int height = srcMask.fBounds.height();
2070 const uint8_t* SK_RESTRICT src = (const uint8_t*)srcMask.fImage;
2071 const size_t srcRB = srcMask.fRowBytes;
2072 uint8_t* SK_RESTRICT dst = (uint8_t*)dstMask->fImage;
2073 const size_t dstRB = dstMask->fRowBytes;
2075 const int wholeBytes = width >> 3;
2076 const int leftOverBits = width & 7;
2078 for (int y = 0; y < height; ++y) {
2079 uint8_t* SK_RESTRICT d = dst;
2080 for (int i = 0; i < wholeBytes; ++i) {
2081 int srcByte = src[i];
2082 d[0] = bit2byte(srcByte & (1 << 7));
2083 d[1] = bit2byte(srcByte & (1 << 6));
2084 d[2] = bit2byte(srcByte & (1 << 5));
2085 d[3] = bit2byte(srcByte & (1 << 4));
2086 d[4] = bit2byte(srcByte & (1 << 3));
2087 d[5] = bit2byte(srcByte & (1 << 2));
2088 d[6] = bit2byte(srcByte & (1 << 1));
2089 d[7] = bit2byte(srcByte & (1 << 0));
2090 d += 8;
2091 }
2092 if (leftOverBits) {
2093 int srcByte = src[wholeBytes];
2094 for (int x = 0; x < leftOverBits; ++x) {
2095 *d++ = bit2byte(srcByte & 0x80);
2096 srcByte <<= 1;
2097 }
2098 }
2099 src += srcRB;
2100 dst += dstRB;
2101 }
2102 }
2104 void SkAAClipBlitter::blitMask(const SkMask& origMask, const SkIRect& clip) {
2105 SkASSERT(fAAClip->getBounds().contains(clip));
2107 if (fAAClip->quickContains(clip)) {
2108 fBlitter->blitMask(origMask, clip);
2109 return;
2110 }
2112 const SkMask* mask = &origMask;
2114 // if we're BW, we need to upscale to A8 (ugh)
2115 SkMask grayMask;
2116 grayMask.fImage = NULL;
2117 if (SkMask::kBW_Format == origMask.fFormat) {
2118 grayMask.fFormat = SkMask::kA8_Format;
2119 grayMask.fBounds = origMask.fBounds;
2120 grayMask.fRowBytes = origMask.fBounds.width();
2121 size_t size = grayMask.computeImageSize();
2122 grayMask.fImage = (uint8_t*)fGrayMaskScratch.reset(size,
2123 SkAutoMalloc::kReuse_OnShrink);
2125 upscaleBW2A8(&grayMask, origMask);
2126 mask = &grayMask;
2127 }
2129 this->ensureRunsAndAA();
2131 // HACK -- we are devolving 3D into A8, need to copy the rest of the 3D
2132 // data into a temp block to support it better (ugh)
2134 const void* src = mask->getAddr(clip.fLeft, clip.fTop);
2135 const size_t srcRB = mask->fRowBytes;
2136 const int width = clip.width();
2137 MergeAAProc mergeProc = find_merge_aa_proc(mask->fFormat);
2139 SkMask rowMask;
2140 rowMask.fFormat = SkMask::k3D_Format == mask->fFormat ? SkMask::kA8_Format : mask->fFormat;
2141 rowMask.fBounds.fLeft = clip.fLeft;
2142 rowMask.fBounds.fRight = clip.fRight;
2143 rowMask.fRowBytes = mask->fRowBytes; // doesn't matter, since our height==1
2144 rowMask.fImage = (uint8_t*)fScanlineScratch;
2146 int y = clip.fTop;
2147 const int stopY = y + clip.height();
2149 do {
2150 int localStopY SK_INIT_TO_AVOID_WARNING;
2151 const uint8_t* row = fAAClip->findRow(y, &localStopY);
2152 // findRow returns last Y, not stop, so we add 1
2153 localStopY = SkMin32(localStopY + 1, stopY);
2155 int initialCount;
2156 row = fAAClip->findX(row, clip.fLeft, &initialCount);
2157 do {
2158 mergeProc(src, width, row, initialCount, rowMask.fImage);
2159 rowMask.fBounds.fTop = y;
2160 rowMask.fBounds.fBottom = y + 1;
2161 fBlitter->blitMask(rowMask, rowMask.fBounds);
2162 src = (const void*)((const char*)src + srcRB);
2163 } while (++y < localStopY);
2164 } while (y < stopY);
2165 }
2167 const SkBitmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) {
2168 return NULL;
2169 }
