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