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