1 /* 2 * Copyright 2006 The Android Open Source Project 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 "SkRegionPriv.h" 9 #include "SkBlitter.h" 10 #include "SkScan.h" 11 #include "SkTSort.h" 12 #include "SkTDArray.h" 13 #include "SkPath.h" 14 15 // The rgnbuilder caller *seems* to pass short counts, possible often seens early failure, so 16 // we may not want to promote this to a "std" routine just yet. 17 static bool sk_memeq32(const int32_t* SK_RESTRICT a, const int32_t* SK_RESTRICT b, int count) { 18 for (int i = 0; i < count; ++i) { 19 if (a[i] != b[i]) { 20 return false; 21 } 22 } 23 return true; 24 } 25 26 class SkRgnBuilder : public SkBlitter { 27 public: 28 SkRgnBuilder(); 29 virtual ~SkRgnBuilder(); 30 31 // returns true if it could allocate the working storage needed 32 bool init(int maxHeight, int maxTransitions, bool pathIsInverse); 33 34 void done() { 35 if (fCurrScanline != nullptr) { 36 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 37 if (!this->collapsWithPrev()) { // flush the last line 38 fCurrScanline = fCurrScanline->nextScanline(); 39 } 40 } 41 } 42 43 int computeRunCount() const; 44 void copyToRect(SkIRect*) const; 45 void copyToRgn(SkRegion::RunType runs[]) const; 46 47 void blitH(int x, int y, int width) override; 48 49 #ifdef SK_DEBUG 50 void dump() const { 51 SkDebugf("SkRgnBuilder: Top = %d\n", fTop); 52 const Scanline* line = (Scanline*)fStorage; 53 while (line < fCurrScanline) { 54 SkDebugf("SkRgnBuilder::Scanline: LastY=%d, fXCount=%d", line->fLastY, line->fXCount); 55 for (int i = 0; i < line->fXCount; i++) { 56 SkDebugf(" %d", line->firstX()[i]); 57 } 58 SkDebugf("\n"); 59 60 line = line->nextScanline(); 61 } 62 } 63 #endif 64 private: 65 /* 66 * Scanline mimics a row in the region, nearly. A row in a region is: 67 * [Bottom IntervalCount [L R]... Sentinel] 68 * while a Scanline is 69 * [LastY XCount [L R]... uninitialized] 70 * The two are the same length (which is good), but we have to transmute 71 * the scanline a little when we convert it to a region-row. 72 * 73 * Potentially we could recode this to exactly match the row format, in 74 * which case copyToRgn() could be a single memcpy. Not sure that is worth 75 * the effort. 76 */ 77 struct Scanline { 78 SkRegion::RunType fLastY; 79 SkRegion::RunType fXCount; 80 81 SkRegion::RunType* firstX() const { return (SkRegion::RunType*)(this + 1); } 82 Scanline* nextScanline() const { 83 // add final +1 for the x-sentinel 84 return (Scanline*)((SkRegion::RunType*)(this + 1) + fXCount + 1); 85 } 86 }; 87 SkRegion::RunType* fStorage; 88 Scanline* fCurrScanline; 89 Scanline* fPrevScanline; 90 // points at next avialable x[] in fCurrScanline 91 SkRegion::RunType* fCurrXPtr; 92 SkRegion::RunType fTop; // first Y value 93 94 int fStorageCount; 95 96 bool collapsWithPrev() { 97 if (fPrevScanline != nullptr && 98 fPrevScanline->fLastY + 1 == fCurrScanline->fLastY && 99 fPrevScanline->fXCount == fCurrScanline->fXCount && 100 sk_memeq32(fPrevScanline->firstX(), fCurrScanline->firstX(), fCurrScanline->fXCount)) 101 { 102 // update the height of fPrevScanline 103 fPrevScanline->fLastY = fCurrScanline->fLastY; 104 return true; 105 } 106 return false; 107 } 108 }; 109 110 SkRgnBuilder::SkRgnBuilder() 111 : fStorage(nullptr) { 112 } 113 114 SkRgnBuilder::~SkRgnBuilder() { 115 sk_free(fStorage); 116 } 117 118 bool SkRgnBuilder::init(int maxHeight, int maxTransitions, bool pathIsInverse) { 119 if ((maxHeight | maxTransitions) < 0) { 120 return false; 121 } 122 123 if (pathIsInverse) { 124 // allow for additional X transitions to "invert" each scanline 125 // [ L' ... normal transitions ... R' ] 126 // 127 maxTransitions += 2; 128 } 129 130 // compute the count with +1 and +3 slop for the working buffer 131 int64_t count = sk_64_mul(maxHeight + 1, 3 + maxTransitions); 132 133 if (pathIsInverse) { 134 // allow for two "empty" rows for the top and bottom 135 // [ Y, 1, L, R, S] == 5 (*2 for top and bottom) 136 count += 10; 137 } 138 139 if (count < 0 || !sk_64_isS32(count)) { 140 return false; 141 } 142 fStorageCount = sk_64_asS32(count); 143 144 int64_t size = sk_64_mul(fStorageCount, sizeof(SkRegion::RunType)); 145 if (size < 0 || !sk_64_isS32(size)) { 146 return false; 147 } 148 149 fStorage = (SkRegion::RunType*)sk_malloc_flags(sk_64_asS32(size), 0); 150 if (nullptr == fStorage) { 151 return false; 152 } 153 154 fCurrScanline = nullptr; // signal empty collection 155 fPrevScanline = nullptr; // signal first scanline 156 return true; 157 } 158 159 void SkRgnBuilder::blitH(int x, int y, int width) { 160 if (fCurrScanline == nullptr) { // first time 161 fTop = (SkRegion::RunType)(y); 162 fCurrScanline = (Scanline*)fStorage; 163 fCurrScanline->fLastY = (SkRegion::RunType)(y); 164 fCurrXPtr = fCurrScanline->firstX(); 165 } else { 166 SkASSERT(y >= fCurrScanline->fLastY); 167 168 if (y > fCurrScanline->fLastY) { 169 // if we get here, we're done with fCurrScanline 170 fCurrScanline->fXCount = (SkRegion::RunType)((int)(fCurrXPtr - fCurrScanline->firstX())); 171 172 int prevLastY = fCurrScanline->fLastY; 173 if (!this->collapsWithPrev()) { 174 fPrevScanline = fCurrScanline; 175 fCurrScanline = fCurrScanline->nextScanline(); 176 177 } 178 if (y - 1 > prevLastY) { // insert empty run 179 fCurrScanline->fLastY = (SkRegion::RunType)(y - 1); 180 fCurrScanline->fXCount = 0; 181 fCurrScanline = fCurrScanline->nextScanline(); 182 } 183 // setup for the new curr line 184 fCurrScanline->fLastY = (SkRegion::RunType)(y); 185 fCurrXPtr = fCurrScanline->firstX(); 186 } 187 } 188 // check if we should extend the current run, or add a new one 189 if (fCurrXPtr > fCurrScanline->firstX() && fCurrXPtr[-1] == x) { 190 fCurrXPtr[-1] = (SkRegion::RunType)(x + width); 191 } else { 192 fCurrXPtr[0] = (SkRegion::RunType)(x); 193 fCurrXPtr[1] = (SkRegion::RunType)(x + width); 194 fCurrXPtr += 2; 195 } 196 SkASSERT(fCurrXPtr - fStorage < fStorageCount); 197 } 198 199 int SkRgnBuilder::computeRunCount() const { 200 if (fCurrScanline == nullptr) { 201 return 0; 202 } 203 204 const SkRegion::RunType* line = fStorage; 205 const SkRegion::RunType* stop = (const SkRegion::RunType*)fCurrScanline; 206 207 return 2 + (int)(stop - line); 208 } 209 210 void SkRgnBuilder::copyToRect(SkIRect* r) const { 211 SkASSERT(fCurrScanline != nullptr); 212 // A rect's scanline is [bottom intervals left right sentinel] == 5 213 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage == 5); 214 215 const Scanline* line = (const Scanline*)fStorage; 216 SkASSERT(line->fXCount == 2); 217 218 r->set(line->firstX()[0], fTop, line->firstX()[1], line->fLastY + 1); 219 } 220 221 void SkRgnBuilder::copyToRgn(SkRegion::RunType runs[]) const { 222 SkASSERT(fCurrScanline != nullptr); 223 SkASSERT((const SkRegion::RunType*)fCurrScanline - fStorage > 4); 224 225 const Scanline* line = (const Scanline*)fStorage; 226 const Scanline* stop = fCurrScanline; 227 228 *runs++ = fTop; 229 do { 230 *runs++ = (SkRegion::RunType)(line->fLastY + 1); 231 int count = line->fXCount; 232 *runs++ = count >> 1; // intervalCount 233 if (count) { 234 memcpy(runs, line->firstX(), count * sizeof(SkRegion::RunType)); 235 runs += count; 236 } 237 *runs++ = SkRegion::kRunTypeSentinel; 238 line = line->nextScanline(); 239 } while (line < stop); 240 SkASSERT(line == stop); 241 *runs = SkRegion::kRunTypeSentinel; 242 } 243 244 static unsigned verb_to_initial_last_index(unsigned verb) { 245 static const uint8_t gPathVerbToInitialLastIndex[] = { 246 0, // kMove_Verb 247 1, // kLine_Verb 248 2, // kQuad_Verb 249 2, // kConic_Verb 250 3, // kCubic_Verb 251 0, // kClose_Verb 252 0 // kDone_Verb 253 }; 254 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToInitialLastIndex)); 255 return gPathVerbToInitialLastIndex[verb]; 256 } 257 258 static unsigned verb_to_max_edges(unsigned verb) { 259 static const uint8_t gPathVerbToMaxEdges[] = { 260 0, // kMove_Verb 261 1, // kLine_Verb 262 2, // kQuad_VerbB 263 2, // kConic_VerbB 264 3, // kCubic_Verb 265 0, // kClose_Verb 266 0 // kDone_Verb 267 }; 268 SkASSERT((unsigned)verb < SK_ARRAY_COUNT(gPathVerbToMaxEdges)); 269 return gPathVerbToMaxEdges[verb]; 270 } 271 272 // If returns 0, ignore itop and ibot 273 static int count_path_runtype_values(const SkPath& path, int* itop, int* ibot) { 274 SkPath::Iter iter(path, true); 275 SkPoint pts[4]; 276 SkPath::Verb verb; 277 278 int maxEdges = 0; 279 SkScalar top = SkIntToScalar(SK_MaxS16); 280 SkScalar bot = SkIntToScalar(SK_MinS16); 281 282 while ((verb = iter.next(pts, false)) != SkPath::kDone_Verb) { 283 maxEdges += verb_to_max_edges(verb); 284 285 int lastIndex = verb_to_initial_last_index(verb); 286 if (lastIndex > 0) { 287 for (int i = 1; i <= lastIndex; i++) { 288 if (top > pts[i].fY) { 289 top = pts[i].fY; 290 } else if (bot < pts[i].fY) { 291 bot = pts[i].fY; 292 } 293 } 294 } else if (SkPath::kMove_Verb == verb) { 295 if (top > pts[0].fY) { 296 top = pts[0].fY; 297 } else if (bot < pts[0].fY) { 298 bot = pts[0].fY; 299 } 300 } 301 } 302 if (0 == maxEdges) { 303 return 0; // we have only moves+closes 304 } 305 306 SkASSERT(top <= bot); 307 *itop = SkScalarRoundToInt(top); 308 *ibot = SkScalarRoundToInt(bot); 309 return maxEdges; 310 } 311 312 static bool check_inverse_on_empty_return(SkRegion* dst, const SkPath& path, const SkRegion& clip) { 313 if (path.isInverseFillType()) { 314 return dst->set(clip); 315 } else { 316 return dst->setEmpty(); 317 } 318 } 319 320 bool SkRegion::setPath(const SkPath& path, const SkRegion& clip) { 321 SkDEBUGCODE(this->validate();) 322 323 if (clip.isEmpty()) { 324 return this->setEmpty(); 325 } 326 327 if (path.isEmpty()) { 328 return check_inverse_on_empty_return(this, path, clip); 329 } 330 331 // compute worst-case rgn-size for the path 332 int pathTop, pathBot; 333 int pathTransitions = count_path_runtype_values(path, &pathTop, &pathBot); 334 if (0 == pathTransitions) { 335 return check_inverse_on_empty_return(this, path, clip); 336 } 337 338 int clipTop, clipBot; 339 int clipTransitions = clip.count_runtype_values(&clipTop, &clipBot); 340 341 int top = SkMax32(pathTop, clipTop); 342 int bot = SkMin32(pathBot, clipBot); 343 if (top >= bot) { 344 return check_inverse_on_empty_return(this, path, clip); 345 } 346 347 SkRgnBuilder builder; 348 349 if (!builder.init(bot - top, 350 SkMax32(pathTransitions, clipTransitions), 351 path.isInverseFillType())) { 352 // can't allocate working space, so return false 353 return this->setEmpty(); 354 } 355 356 SkScan::FillPath(path, clip, &builder); 357 builder.done(); 358 359 int count = builder.computeRunCount(); 360 if (count == 0) { 361 return this->setEmpty(); 362 } else if (count == kRectRegionRuns) { 363 builder.copyToRect(&fBounds); 364 this->setRect(fBounds); 365 } else { 366 SkRegion tmp; 367 368 tmp.fRunHead = RunHead::Alloc(count); 369 builder.copyToRgn(tmp.fRunHead->writable_runs()); 370 tmp.fRunHead->computeRunBounds(&tmp.fBounds); 371 this->swap(tmp); 372 } 373 SkDEBUGCODE(this->validate();) 374 return true; 375 } 376 377 ///////////////////////////////////////////////////////////////////////////////////////////////// 378 ///////////////////////////////////////////////////////////////////////////////////////////////// 379 380 struct Edge { 381 enum { 382 kY0Link = 0x01, 383 kY1Link = 0x02, 384 385 kCompleteLink = (kY0Link | kY1Link) 386 }; 387 388 SkRegion::RunType fX; 389 SkRegion::RunType fY0, fY1; 390 uint8_t fFlags; 391 Edge* fNext; 392 393 void set(int x, int y0, int y1) { 394 SkASSERT(y0 != y1); 395 396 fX = (SkRegion::RunType)(x); 397 fY0 = (SkRegion::RunType)(y0); 398 fY1 = (SkRegion::RunType)(y1); 399 fFlags = 0; 400 SkDEBUGCODE(fNext = nullptr;) 401 } 402 403 int top() const { 404 return SkFastMin32(fY0, fY1); 405 } 406 }; 407 408 static void find_link(Edge* base, Edge* stop) { 409 SkASSERT(base < stop); 410 411 if (base->fFlags == Edge::kCompleteLink) { 412 SkASSERT(base->fNext); 413 return; 414 } 415 416 SkASSERT(base + 1 < stop); 417 418 int y0 = base->fY0; 419 int y1 = base->fY1; 420 421 Edge* e = base; 422 if ((base->fFlags & Edge::kY0Link) == 0) { 423 for (;;) { 424 e += 1; 425 if ((e->fFlags & Edge::kY1Link) == 0 && y0 == e->fY1) { 426 SkASSERT(nullptr == e->fNext); 427 e->fNext = base; 428 e->fFlags = SkToU8(e->fFlags | Edge::kY1Link); 429 break; 430 } 431 } 432 } 433 434 e = base; 435 if ((base->fFlags & Edge::kY1Link) == 0) { 436 for (;;) { 437 e += 1; 438 if ((e->fFlags & Edge::kY0Link) == 0 && y1 == e->fY0) { 439 SkASSERT(nullptr == base->fNext); 440 base->fNext = e; 441 e->fFlags = SkToU8(e->fFlags | Edge::kY0Link); 442 break; 443 } 444 } 445 } 446 447 base->fFlags = Edge::kCompleteLink; 448 } 449 450 static int extract_path(Edge* edge, Edge* stop, SkPath* path) { 451 while (0 == edge->fFlags) { 452 edge++; // skip over "used" edges 453 } 454 455 SkASSERT(edge < stop); 456 457 Edge* base = edge; 458 Edge* prev = edge; 459 edge = edge->fNext; 460 SkASSERT(edge != base); 461 462 int count = 1; 463 path->moveTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY0)); 464 prev->fFlags = 0; 465 do { 466 if (prev->fX != edge->fX || prev->fY1 != edge->fY0) { // skip collinear 467 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 468 path->lineTo(SkIntToScalar(edge->fX), SkIntToScalar(edge->fY0)); // H 469 } 470 prev = edge; 471 edge = edge->fNext; 472 count += 1; 473 prev->fFlags = 0; 474 } while (edge != base); 475 path->lineTo(SkIntToScalar(prev->fX), SkIntToScalar(prev->fY1)); // V 476 path->close(); 477 return count; 478 } 479 480 struct EdgeLT { 481 bool operator()(const Edge& a, const Edge& b) const { 482 return (a.fX == b.fX) ? a.top() < b.top() : a.fX < b.fX; 483 } 484 }; 485 486 bool SkRegion::getBoundaryPath(SkPath* path) const { 487 // path could safely be nullptr if we're empty, but the caller shouldn't 488 // *know* that 489 SkASSERT(path); 490 491 if (this->isEmpty()) { 492 return false; 493 } 494 495 const SkIRect& bounds = this->getBounds(); 496 497 if (this->isRect()) { 498 SkRect r; 499 r.set(bounds); // this converts the ints to scalars 500 path->addRect(r); 501 return true; 502 } 503 504 SkRegion::Iterator iter(*this); 505 SkTDArray<Edge> edges; 506 507 for (const SkIRect& r = iter.rect(); !iter.done(); iter.next()) { 508 Edge* edge = edges.append(2); 509 edge[0].set(r.fLeft, r.fBottom, r.fTop); 510 edge[1].set(r.fRight, r.fTop, r.fBottom); 511 } 512 513 int count = edges.count(); 514 Edge* start = edges.begin(); 515 Edge* stop = start + count; 516 SkTQSort<Edge>(start, stop - 1, EdgeLT()); 517 518 Edge* e; 519 for (e = start; e != stop; e++) { 520 find_link(e, stop); 521 } 522 523 #ifdef SK_DEBUG 524 for (e = start; e != stop; e++) { 525 SkASSERT(e->fNext != nullptr); 526 SkASSERT(e->fFlags == Edge::kCompleteLink); 527 } 528 #endif 529 530 path->incReserve(count << 1); 531 do { 532 SkASSERT(count > 1); 533 count -= extract_path(start, stop, path); 534 } while (count > 0); 535 536 return true; 537 } 538