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 virtual 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 virtual 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
1340 if (doAA) {
1341 SkScan::AntiFillPath(path, snugClip, &blitter, true);
1342 } else {
1343 SkScan::FillPath(path, snugClip, &blitter);
1344 }
1345
1346 blitter.finish();
1347 return builder.finish(this);
1348}
1349
1350///////////////////////////////////////////////////////////////////////////////
1351
1352typedef void (*RowProc)(SkAAClip::Builder&, int bottom,
1353 const uint8_t* rowA, const SkIRect& rectA,
1354 const uint8_t* rowB, const SkIRect& rectB);
1355
1356typedef U8CPU (*AlphaProc)(U8CPU alphaA, U8CPU alphaB);
1357
1358static U8CPU sectAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1359 // Multiply
1360 return SkMulDiv255Round(alphaA, alphaB);
1361}
1362
1363static U8CPU unionAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1364 // SrcOver
1365 return alphaA + alphaB - SkMulDiv255Round(alphaA, alphaB);
1366}
1367
1368static U8CPU diffAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1369 // SrcOut
1370 return SkMulDiv255Round(alphaA, 0xFF - alphaB);
1371}
1372
1373static U8CPU xorAlphaProc(U8CPU alphaA, U8CPU alphaB) {
1374 // XOR
1375 return alphaA + alphaB - 2 * SkMulDiv255Round(alphaA, alphaB);
1376}
1377
1378static AlphaProc find_alpha_proc(SkRegion::Op op) {
1379 switch (op) {
1380 case SkRegion::kIntersect_Op:
1381 return sectAlphaProc;
1382 case SkRegion::kDifference_Op:
1383 return diffAlphaProc;
1384 case SkRegion::kUnion_Op:
1385 return unionAlphaProc;
1386 case SkRegion::kXOR_Op:
1387 return xorAlphaProc;
1388 default:
1389 SkDEBUGFAIL("unexpected region op");
1390 return sectAlphaProc;
1391 }
1392}
1393
1394class RowIter {
1395public:
1396 RowIter(const uint8_t* row, const SkIRect& bounds) {
1397 fRow = row;
1398 fLeft = bounds.fLeft;
1399 fBoundsRight = bounds.fRight;
1400 if (row) {
1401 fRight = bounds.fLeft + row[0];
1402 SkASSERT(fRight <= fBoundsRight);
1403 fAlpha = row[1];
1404 fDone = false;
1405 } else {
1406 fDone = true;
1407 fRight = kMaxInt32;
1408 fAlpha = 0;
1409 }
1410 }
1411
1412 bool done() const { return fDone; }
1413 int left() const { return fLeft; }
1414 int right() const { return fRight; }
1415 U8CPU alpha() const { return fAlpha; }
1416 void next() {
1417 if (!fDone) {
1418 fLeft = fRight;
1419 if (fRight == fBoundsRight) {
1420 fDone = true;
1421 fRight = kMaxInt32;
1422 fAlpha = 0;
1423 } else {
1424 fRow += 2;
1425 fRight += fRow[0];
1426 fAlpha = fRow[1];
1427 SkASSERT(fRight <= fBoundsRight);
1428 }
1429 }
1430 }
1431
1432private:
1433 const uint8_t* fRow;
1434 int fLeft;
1435 int fRight;
1436 int fBoundsRight;
1437 bool fDone;
1438 uint8_t fAlpha;
1439};
1440
1441static void adjust_row(RowIter& iter, int& leftA, int& riteA, int rite) {
1442 if (rite == riteA) {
1443 iter.next();
1444 leftA = iter.left();
1445 riteA = iter.right();
1446 }
1447}
1448
1449#if 0 // UNUSED
1450static bool intersect(int& min, int& max, int boundsMin, int boundsMax) {
1451 SkASSERT(min < max);
1452 SkASSERT(boundsMin < boundsMax);
1453 if (min >= boundsMax || max <= boundsMin) {
1454 return false;
1455 }
1456 if (min < boundsMin) {
1457 min = boundsMin;
1458 }
1459 if (max > boundsMax) {
1460 max = boundsMax;
1461 }
1462 return true;
1463}
1464#endif
1465
1466static void operatorX(SkAAClip::Builder& builder, int lastY,
1467 RowIter& iterA, RowIter& iterB,
1468 AlphaProc proc, const SkIRect& bounds) {
1469 int leftA = iterA.left();
1470 int riteA = iterA.right();
1471 int leftB = iterB.left();
1472 int riteB = iterB.right();
1473
1474 int prevRite = bounds.fLeft;
1475
1476 do {
1477 U8CPU alphaA = 0;
1478 U8CPU alphaB = 0;
1479 int left, rite;
1480
1481 if (leftA < leftB) {
1482 left = leftA;
1483 alphaA = iterA.alpha();
1484 if (riteA <= leftB) {
1485 rite = riteA;
1486 } else {
1487 rite = leftA = leftB;
1488 }
1489 } else if (leftB < leftA) {
1490 left = leftB;
1491 alphaB = iterB.alpha();
1492 if (riteB <= leftA) {
1493 rite = riteB;
1494 } else {
1495 rite = leftB = leftA;
1496 }
1497 } else {
1498 left = leftA; // or leftB, since leftA == leftB
1499 rite = leftA = leftB = std::min(riteA, riteB);
1500 alphaA = iterA.alpha();
1501 alphaB = iterB.alpha();
1502 }
1503
1504 if (left >= bounds.fRight) {
1505 break;
1506 }
1507 if (rite > bounds.fRight) {
1508 rite = bounds.fRight;
1509 }
1510
1511 if (left >= bounds.fLeft) {
1512 SkASSERT(rite > left);
1513 builder.addRun(left, lastY, proc(alphaA, alphaB), rite - left);
1514 prevRite = rite;
1515 }
1516
1517 adjust_row(iterA, leftA, riteA, rite);
1518 adjust_row(iterB, leftB, riteB, rite);
1519 } while (!iterA.done() || !iterB.done());
1520
1521 if (prevRite < bounds.fRight) {
1522 builder.addRun(prevRite, lastY, 0, bounds.fRight - prevRite);
1523 }
1524}
1525
1526static void adjust_iter(SkAAClip::Iter& iter, int& topA, int& botA, int bot) {
1527 if (bot == botA) {
1528 iter.next();
1529 topA = botA;
1530 SkASSERT(botA == iter.top());
1531 botA = iter.bottom();
1532 }
1533}
1534
1535static void operateY(SkAAClip::Builder& builder, const SkAAClip& A,
1536 const SkAAClip& B, SkRegion::Op op) {
1537 AlphaProc proc = find_alpha_proc(op);
1538 const SkIRect& bounds = builder.getBounds();
1539
1540 SkAAClip::Iter iterA(A);
1541 SkAAClip::Iter iterB(B);
1542
1543 SkASSERT(!iterA.done());
1544 int topA = iterA.top();
1545 int botA = iterA.bottom();
1546 SkASSERT(!iterB.done());
1547 int topB = iterB.top();
1548 int botB = iterB.bottom();
1549
1550 do {
1551 const uint8_t* rowA = nullptr;
1552 const uint8_t* rowB = nullptr;
1553 int top, bot;
1554
1555 if (topA < topB) {
1556 top = topA;
1557 rowA = iterA.data();
1558 if (botA <= topB) {
1559 bot = botA;
1560 } else {
1561 bot = topA = topB;
1562 }
1563
1564 } else if (topB < topA) {
1565 top = topB;
1566 rowB = iterB.data();
1567 if (botB <= topA) {
1568 bot = botB;
1569 } else {
1570 bot = topB = topA;
1571 }
1572 } else {
1573 top = topA; // or topB, since topA == topB
1574 bot = topA = topB = std::min(botA, botB);
1575 rowA = iterA.data();
1576 rowB = iterB.data();
1577 }
1578
1579 if (top >= bounds.fBottom) {
1580 break;
1581 }
1582
1583 if (bot > bounds.fBottom) {
1584 bot = bounds.fBottom;
1585 }
1586 SkASSERT(top < bot);
1587
1588 if (!rowA && !rowB) {
1589 builder.addRun(bounds.fLeft, bot - 1, 0, bounds.width());
1590 } else if (top >= bounds.fTop) {
1591 SkASSERT(bot <= bounds.fBottom);
1592 RowIter rowIterA(rowA, rowA ? A.getBounds() : bounds);
1593 RowIter rowIterB(rowB, rowB ? B.getBounds() : bounds);
1594 operatorX(builder, bot - 1, rowIterA, rowIterB, proc, bounds);
1595 }
1596
1597 adjust_iter(iterA, topA, botA, bot);
1598 adjust_iter(iterB, topB, botB, bot);
1599 } while (!iterA.done() || !iterB.done());
1600}
1601
1602bool SkAAClip::op(const SkAAClip& clipAOrig, const SkAAClip& clipBOrig,
1603 SkRegion::Op op) {
1604 AUTO_AACLIP_VALIDATE(*this);
1605
1606 if (SkRegion::kReplace_Op == op) {
1607 return this->set(clipBOrig);
1608 }
1609
1610 const SkAAClip* clipA = &clipAOrig;
1611 const SkAAClip* clipB = &clipBOrig;
1612
1613 if (SkRegion::kReverseDifference_Op == op) {
1614 using std::swap;
1615 swap(clipA, clipB);
1616 op = SkRegion::kDifference_Op;
1617 }
1618
1619 bool a_empty = clipA->isEmpty();
1620 bool b_empty = clipB->isEmpty();
1621
1622 SkIRect bounds;
1623 switch (op) {
1624 case SkRegion::kDifference_Op:
1625 if (a_empty) {
1626 return this->setEmpty();
1627 }
1628 if (b_empty || !SkIRect::Intersects(clipA->fBounds, clipB->fBounds)) {
1629 return this->set(*clipA);
1630 }
1631 bounds = clipA->fBounds;
1632 break;
1633
1634 case SkRegion::kIntersect_Op:
1635 if ((a_empty | b_empty) || !bounds.intersect(clipA->fBounds,
1636 clipB->fBounds)) {
1637 return this->setEmpty();
1638 }
1639 break;
1640
1641 case SkRegion::kUnion_Op:
1642 case SkRegion::kXOR_Op:
1643 if (a_empty) {
1644 return this->set(*clipB);
1645 }
1646 if (b_empty) {
1647 return this->set(*clipA);
1648 }
1649 bounds = clipA->fBounds;
1650 bounds.join(clipB->fBounds);
1651 break;
1652
1653 default:
1654 SkDEBUGFAIL("unknown region op");
1655 return !this->isEmpty();
1656 }
1657
1658 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds));
1659 SkASSERT(SkIRect::Intersects(bounds, clipB->fBounds));
1660
1661 Builder builder(bounds);
1662 operateY(builder, *clipA, *clipB, op);
1663
1664 return builder.finish(this);
1665}
1666
1667/*
1668 * It can be expensive to build a local aaclip before applying the op, so
1669 * we first see if we can restrict the bounds of new rect to our current
1670 * bounds, or note that the new rect subsumes our current clip.
1671 */
1672
1673bool SkAAClip::op(const SkIRect& rOrig, SkRegion::Op op) {
1674 SkIRect rStorage;
1675 const SkIRect* r = &rOrig;
1676
1677 switch (op) {
1678 case SkRegion::kIntersect_Op:
1679 if (!rStorage.intersect(rOrig, fBounds)) {
1680 // no overlap, so we're empty
1681 return this->setEmpty();
1682 }
1683 if (rStorage == fBounds) {
1684 // we were wholly inside the rect, no change
1685 return !this->isEmpty();
1686 }
1687 if (this->quickContains(rStorage)) {
1688 // the intersection is wholly inside us, we're a rect
1689 return this->setRect(rStorage);
1690 }
1691 r = &rStorage; // use the intersected bounds
1692 break;
1693 case SkRegion::kDifference_Op:
1694 break;
1695 case SkRegion::kUnion_Op:
1696 if (rOrig.contains(fBounds)) {
1697 return this->setRect(rOrig);
1698 }
1699 break;
1700 default:
1701 break;
1702 }
1703
1704 SkAAClip clip;
1705 clip.setRect(*r);
1706 return this->op(*this, clip, op);
1707}
1708
1709bool SkAAClip::op(const SkRect& rOrig, SkRegion::Op op, bool doAA) {
1710 SkRect rStorage, boundsStorage;
1711 const SkRect* r = &rOrig;
1712
1713 boundsStorage.set(fBounds);
1714 switch (op) {
1715 case SkRegion::kIntersect_Op:
1716 case SkRegion::kDifference_Op:
1717 if (!rStorage.intersect(rOrig, boundsStorage)) {
1718 if (SkRegion::kIntersect_Op == op) {
1719 return this->setEmpty();
1720 } else { // kDifference
1721 return !this->isEmpty();
1722 }
1723 }
1724 r = &rStorage; // use the intersected bounds
1725 break;
1726 case SkRegion::kUnion_Op:
1727 if (rOrig.contains(boundsStorage)) {
1728 return this->setRect(rOrig);
1729 }
1730 break;
1731 default:
1732 break;
1733 }
1734
1735 SkAAClip clip;
1736 clip.setRect(*r, doAA);
1737 return this->op(*this, clip, op);
1738}
1739
1740bool SkAAClip::op(const SkAAClip& clip, SkRegion::Op op) {
1741 return this->op(*this, clip, op);
1742}
1743
1744///////////////////////////////////////////////////////////////////////////////
1745
1746bool SkAAClip::translate(int dx, int dy, SkAAClip* dst) const {
1747 if (nullptr == dst) {
1748 return !this->isEmpty();
1749 }
1750
1751 if (this->isEmpty()) {
1752 return dst->setEmpty();
1753 }
1754
1755 if (this != dst) {
1756 fRunHead->fRefCnt++;
1757 dst->freeRuns();
1758 dst->fRunHead = fRunHead;
1759 dst->fBounds = fBounds;
1760 }
1761 dst->fBounds.offset(dx, dy);
1762 return true;
1763}
1764
1765static void expand_row_to_mask(uint8_t* SK_RESTRICT mask,
1766 const uint8_t* SK_RESTRICT row,
1767 int width) {
1768 while (width > 0) {
1769 int n = row[0];
1770 SkASSERT(width >= n);
1771 memset(mask, row[1], n);
1772 mask += n;
1773 row += 2;
1774 width -= n;
1775 }
1776 SkASSERT(0 == width);
1777}
1778
1779void SkAAClip::copyToMask(SkMask* mask) const {
1780 mask->fFormat = SkMask::kA8_Format;
1781 if (this->isEmpty()) {
1782 mask->fBounds.setEmpty();
1783 mask->fImage = nullptr;
1784 mask->fRowBytes = 0;
1785 return;
1786 }
1787
1788 mask->fBounds = fBounds;
1789 mask->fRowBytes = fBounds.width();
1790 size_t size = mask->computeImageSize();
1791 mask->fImage = SkMask::AllocImage(size);
1792
1793 Iter iter(*this);
1794 uint8_t* dst = mask->fImage;
1795 const int width = fBounds.width();
1796
1797 int y = fBounds.fTop;
1798 while (!iter.done()) {
1799 do {
1800 expand_row_to_mask(dst, iter.data(), width);
1801 dst += mask->fRowBytes;
1802 } while (++y < iter.bottom());
1803 iter.next();
1804 }
1805}
1806
1807///////////////////////////////////////////////////////////////////////////////
1808///////////////////////////////////////////////////////////////////////////////
1809
1810static void expandToRuns(const uint8_t* SK_RESTRICT data, int initialCount, int width,
1811 int16_t* SK_RESTRICT runs, SkAlpha* SK_RESTRICT aa) {
1812 // we don't read our initial n from data, since the caller may have had to
1813 // clip it, hence the initialCount parameter.
1814 int n = initialCount;
1815 for (;;) {
1816 if (n > width) {
1817 n = width;
1818 }
1819 SkASSERT(n > 0);
1820 runs[0] = n;
1821 runs += n;
1822
1823 aa[0] = data[1];
1824 aa += n;
1825
1826 data += 2;
1827 width -= n;
1828 if (0 == width) {
1829 break;
1830 }
1831 // load the next count
1832 n = data[0];
1833 }
1834 runs[0] = 0; // sentinel
1835}
1836
1837SkAAClipBlitter::~SkAAClipBlitter() {
1838 sk_free(fScanlineScratch);
1839}
1840
1841void SkAAClipBlitter::ensureRunsAndAA() {
1842 if (nullptr == fScanlineScratch) {
1843 // add 1 so we can store the terminating run count of 0
1844 int count = fAAClipBounds.width() + 1;
1845 // we use this either for fRuns + fAA, or a scaline of a mask
1846 // which may be as deep as 32bits
1847 fScanlineScratch = sk_malloc_throw(count * sizeof(SkPMColor));
1848 fRuns = (int16_t*)fScanlineScratch;
1849 fAA = (SkAlpha*)(fRuns + count);
1850 }
1851}
1852
1853void SkAAClipBlitter::blitH(int x, int y, int width) {
1854 SkASSERT(width > 0);
1855 SkASSERT(fAAClipBounds.contains(x, y));
1856 SkASSERT(fAAClipBounds.contains(x + width - 1, y));
1857
1858 const uint8_t* row = fAAClip->findRow(y);
1859 int initialCount;
1860 row = fAAClip->findX(row, x, &initialCount);
1861
1862 if (initialCount >= width) {
1863 SkAlpha alpha = row[1];
1864 if (0 == alpha) {
1865 return;
1866 }
1867 if (0xFF == alpha) {
1868 fBlitter->blitH(x, y, width);
1869 return;
1870 }
1871 }
1872
1873 this->ensureRunsAndAA();
1874 expandToRuns(row, initialCount, width, fRuns, fAA);
1875
1876 fBlitter->blitAntiH(x, y, fAA, fRuns);
1877}
1878
1879static void merge(const uint8_t* SK_RESTRICT row, int rowN,
1880 const SkAlpha* SK_RESTRICT srcAA,
1881 const int16_t* SK_RESTRICT srcRuns,
1882 SkAlpha* SK_RESTRICT dstAA,
1883 int16_t* SK_RESTRICT dstRuns,
1884 int width) {
1885 SkDEBUGCODE(int accumulated = 0;)
1886 int srcN = srcRuns[0];
1887 // do we need this check?
1888 if (0 == srcN) {
1889 return;
1890 }
1891
1892 for (;;) {
1893 SkASSERT(rowN > 0);
1894 SkASSERT(srcN > 0);
1895
1896 unsigned newAlpha = SkMulDiv255Round(srcAA[0], row[1]);
1897 int minN = std::min(srcN, rowN);
1898 dstRuns[0] = minN;
1899 dstRuns += minN;
1900 dstAA[0] = newAlpha;
1901 dstAA += minN;
1902
1903 if (0 == (srcN -= minN)) {
1904 srcN = srcRuns[0]; // refresh
1905 srcRuns += srcN;
1906 srcAA += srcN;
1907 srcN = srcRuns[0]; // reload
1908 if (0 == srcN) {
1909 break;
1910 }
1911 }
1912 if (0 == (rowN -= minN)) {
1913 row += 2;
1914 rowN = row[0]; // reload
1915 }
1916
1917 SkDEBUGCODE(accumulated += minN;)
1918 SkASSERT(accumulated <= width);
1919 }
1920 dstRuns[0] = 0;
1921}
1922
1923void SkAAClipBlitter::blitAntiH(int x, int y, const SkAlpha aa[],
1924 const int16_t runs[]) {
1925
1926 const uint8_t* row = fAAClip->findRow(y);
1927 int initialCount;
1928 row = fAAClip->findX(row, x, &initialCount);
1929
1930 this->ensureRunsAndAA();
1931
1932 merge(row, initialCount, aa, runs, fAA, fRuns, fAAClipBounds.width());
1933 fBlitter->blitAntiH(x, y, fAA, fRuns);
1934}
1935
1936void SkAAClipBlitter::blitV(int x, int y, int height, SkAlpha alpha) {
1937 if (fAAClip->quickContains(x, y, x + 1, y + height)) {
1938 fBlitter->blitV(x, y, height, alpha);
1939 return;
1940 }
1941
1942 for (;;) {
1943 int lastY SK_INIT_TO_AVOID_WARNING;
1944 const uint8_t* row = fAAClip->findRow(y, &lastY);
1945 int dy = lastY - y + 1;
1946 if (dy > height) {
1947 dy = height;
1948 }
1949 height -= dy;
1950
1951 row = fAAClip->findX(row, x);
1952 SkAlpha newAlpha = SkMulDiv255Round(alpha, row[1]);
1953 if (newAlpha) {
1954 fBlitter->blitV(x, y, dy, newAlpha);
1955 }
1956 SkASSERT(height >= 0);
1957 if (height <= 0) {
1958 break;
1959 }
1960 y = lastY + 1;
1961 }
1962}
1963
1964void SkAAClipBlitter::blitRect(int x, int y, int width, int height) {
1965 if (fAAClip->quickContains(x, y, x + width, y + height)) {
1966 fBlitter->blitRect(x, y, width, height);
1967 return;
1968 }
1969
1970 while (--height >= 0) {
1971 this->blitH(x, y, width);
1972 y += 1;
1973 }
1974}
1975
1976typedef void (*MergeAAProc)(const void* src, int width, const uint8_t* row,
1977 int initialRowCount, void* dst);
1978
1979static void small_memcpy(void* dst, const void* src, size_t n) {
1980 memcpy(dst, src, n);
1981}
1982
1983static void small_bzero(void* dst, size_t n) {
1984 sk_bzero(dst, n);
1985}
1986
1987static inline uint8_t mergeOne(uint8_t value, unsigned alpha) {
1988 return SkMulDiv255Round(value, alpha);
1989}
1990
1991static inline uint16_t mergeOne(uint16_t value, unsigned alpha) {
1992 unsigned r = SkGetPackedR16(value);
1993 unsigned g = SkGetPackedG16(value);
1994 unsigned b = SkGetPackedB16(value);
1995 return SkPackRGB16(SkMulDiv255Round(r, alpha),
1996 SkMulDiv255Round(g, alpha),
1997 SkMulDiv255Round(b, alpha));
1998}
1999
2000template <typename T>
2001void mergeT(const void* inSrc, int srcN, const uint8_t* SK_RESTRICT row, int rowN, void* inDst) {
2002 const T* SK_RESTRICT src = static_cast<const T*>(inSrc);
2003 T* SK_RESTRICT dst = static_cast<T*>(inDst);
2004 for (;;) {
2005 SkASSERT(rowN > 0);
2006 SkASSERT(srcN > 0);
2007
2008 int n = std::min(rowN, srcN);
2009 unsigned rowA = row[1];
2010 if (0xFF == rowA) {
2011 small_memcpy(dst, src, n * sizeof(T));
2012 } else if (0 == rowA) {
2013 small_bzero(dst, n * sizeof(T));
2014 } else {
2015 for (int i = 0; i < n; ++i) {
2016 dst[i] = mergeOne(src[i], rowA);
2017 }
2018 }
2019
2020 if (0 == (srcN -= n)) {
2021 break;
2022 }
2023
2024 src += n;
2025 dst += n;
2026
2027 SkASSERT(rowN == n);
2028 row += 2;
2029 rowN = row[0];
2030 }
2031}
2032
2033static MergeAAProc find_merge_aa_proc(SkMask::Format format) {
2034 switch (format) {
2035 case SkMask::kBW_Format:
2036 SkDEBUGFAIL("unsupported");
2037 return nullptr;
2038 case SkMask::kA8_Format:
2039 case SkMask::k3D_Format:
2040 return mergeT<uint8_t> ;
2041 case SkMask::kLCD16_Format:
2042 return mergeT<uint16_t>;
2043 default:
2044 SkDEBUGFAIL("unsupported");
2045 return nullptr;
2046 }
2047}
2048
2049static U8CPU bit2byte(int bitInAByte) {
2050 SkASSERT(bitInAByte <= 0xFF);
2051 // negation turns any non-zero into 0xFFFFFF??, so we just shift down
2052 // some value >= 8 to get a full FF value
2053 return -bitInAByte >> 8;
2054}
2055
2056static void upscaleBW2A8(SkMask* dstMask, const SkMask& srcMask) {
2057 SkASSERT(SkMask::kBW_Format == srcMask.fFormat);
2058 SkASSERT(SkMask::kA8_Format == dstMask->fFormat);
2059
2060 const int width = srcMask.fBounds.width();
2061 const int height = srcMask.fBounds.height();
2062
2063 const uint8_t* SK_RESTRICT src = (const uint8_t*)srcMask.fImage;
2064 const size_t srcRB = srcMask.fRowBytes;
2065 uint8_t* SK_RESTRICT dst = (uint8_t*)dstMask->fImage;
2066 const size_t dstRB = dstMask->fRowBytes;
2067
2068 const int wholeBytes = width >> 3;
2069 const int leftOverBits = width & 7;
2070
2071 for (int y = 0; y < height; ++y) {
2072 uint8_t* SK_RESTRICT d = dst;
2073 for (int i = 0; i < wholeBytes; ++i) {
2074 int srcByte = src[i];
2075 d[0] = bit2byte(srcByte & (1 << 7));
2076 d[1] = bit2byte(srcByte & (1 << 6));
2077 d[2] = bit2byte(srcByte & (1 << 5));
2078 d[3] = bit2byte(srcByte & (1 << 4));
2079 d[4] = bit2byte(srcByte & (1 << 3));
2080 d[5] = bit2byte(srcByte & (1 << 2));
2081 d[6] = bit2byte(srcByte & (1 << 1));
2082 d[7] = bit2byte(srcByte & (1 << 0));
2083 d += 8;
2084 }
2085 if (leftOverBits) {
2086 int srcByte = src[wholeBytes];
2087 for (int x = 0; x < leftOverBits; ++x) {
2088 *d++ = bit2byte(srcByte & 0x80);
2089 srcByte <<= 1;
2090 }
2091 }
2092 src += srcRB;
2093 dst += dstRB;
2094 }
2095}
2096
2097void SkAAClipBlitter::blitMask(const SkMask& origMask, const SkIRect& clip) {
2098 SkASSERT(fAAClip->getBounds().contains(clip));
2099
2100 if (fAAClip->quickContains(clip)) {
2101 fBlitter->blitMask(origMask, clip);
2102 return;
2103 }
2104
2105 const SkMask* mask = &origMask;
2106
2107 // if we're BW, we need to upscale to A8 (ugh)
2108 SkMask grayMask;
2109 if (SkMask::kBW_Format == origMask.fFormat) {
2110 grayMask.fFormat = SkMask::kA8_Format;
2111 grayMask.fBounds = origMask.fBounds;
2112 grayMask.fRowBytes = origMask.fBounds.width();
2113 size_t size = grayMask.computeImageSize();
2114 grayMask.fImage = (uint8_t*)fGrayMaskScratch.reset(size,
2115 SkAutoMalloc::kReuse_OnShrink);
2116
2117 upscaleBW2A8(&grayMask, origMask);
2118 mask = &grayMask;
2119 }
2120
2121 this->ensureRunsAndAA();
2122
2123 // HACK -- we are devolving 3D into A8, need to copy the rest of the 3D
2124 // data into a temp block to support it better (ugh)
2125
2126 const void* src = mask->getAddr(clip.fLeft, clip.fTop);
2127 const size_t srcRB = mask->fRowBytes;
2128 const int width = clip.width();
2129 MergeAAProc mergeProc = find_merge_aa_proc(mask->fFormat);
2130
2131 SkMask rowMask;
2132 rowMask.fFormat = SkMask::k3D_Format == mask->fFormat ? SkMask::kA8_Format : mask->fFormat;
2133 rowMask.fBounds.fLeft = clip.fLeft;
2134 rowMask.fBounds.fRight = clip.fRight;
2135 rowMask.fRowBytes = mask->fRowBytes; // doesn't matter, since our height==1
2136 rowMask.fImage = (uint8_t*)fScanlineScratch;
2137
2138 int y = clip.fTop;
2139 const int stopY = y + clip.height();
2140
2141 do {
2142 int localStopY SK_INIT_TO_AVOID_WARNING;
2143 const uint8_t* row = fAAClip->findRow(y, &localStopY);
2144 // findRow returns last Y, not stop, so we add 1
2145 localStopY = std::min(localStopY + 1, stopY);
2146
2147 int initialCount;
2148 row = fAAClip->findX(row, clip.fLeft, &initialCount);
2149 do {
2150 mergeProc(src, width, row, initialCount, rowMask.fImage);
2151 rowMask.fBounds.fTop = y;
2152 rowMask.fBounds.fBottom = y + 1;
2153 fBlitter->blitMask(rowMask, rowMask.fBounds);
2154 src = (const void*)((const char*)src + srcRB);
2155 } while (++y < localStopY);
2156 } while (y < stopY);
2157}
2158
2159const SkPixmap* SkAAClipBlitter::justAnOpaqueColor(uint32_t* value) {
2160 return nullptr;
2161}
2162