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