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