src/lib/sw_engine/tvgSwRle.cpp

   1 /*
   2  * Copyright (c) 2020 Samsung Electronics Co., Ltd. All rights reserved.
   3
   4  * Permission is hereby granted, free of charge, to any person obtaining a copy
   5  * of this software and associated documentation files (the "Software"), to deal
   6  * in the Software without restriction, including without limitation the rights
   7  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   8  * copies of the Software, and to permit persons to whom the Software is
   9  * furnished to do so, subject to the following conditions:
  10
  11  * The above copyright notice and this permission notice shall be included in all
  12  * copies or substantial portions of the Software.
  13
  14  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  15  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  16  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  17  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  18  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  19  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  20  * SOFTWARE.
  21  */
  22 #include <setjmp.h>
  23 #include <limits.h>
  24 #include <memory.h>
  25 #include <iostream>
  26 #include "tvgSwCommon.h"
  27
  28 /************************************************************************/
  29 /* Internal Class Implementation                                        */
  30 /************************************************************************/
  31
  32 constexpr auto MAX_SPANS = 256;
  33 constexpr auto PIXEL_BITS = 8;   //must be at least 6 bits!
  34 constexpr auto ONE_PIXEL = (1L << PIXEL_BITS);
  35
  36 using Area = long;
  37
  38 struct Band
  39 {
  40     SwCoord min, max;
  41 };
  42
  43 struct Cell
  44 {
  45     SwCoord x;
  46     SwCoord cover;
  47     Area area;
  48     Cell *next;
  49 };
  50
  51 struct RleWorker
  52 {
  53     SwRleData* rle;
  54
  55     SwPoint cellPos;
  56     SwPoint cellMin;
  57     SwPoint cellMax;
  58     SwCoord cellXCnt;
  59     SwCoord cellYCnt;
  60
  61     Area area;
  62     SwCoord cover;
  63
  64     Cell* cells;
  65     ptrdiff_t maxCells;
  66     ptrdiff_t cellsCnt;
  67
  68     SwPoint pos;
  69
  70     SwPoint bezStack[32 * 3 + 1];
  71     int levStack[32];
  72
  73     SwOutline* outline;
  74
  75     SwSpan spans[MAX_SPANS];
  76     int spansCnt;
  77     int ySpan;
  78
  79     int bandSize;
  80     int bandShoot;
  81
  82     jmp_buf jmpBuf;
  83
  84     void* buffer;
  85     long bufferSize;
  86
  87     Cell** yCells;
  88     SwCoord yCnt;
  89
  90     SwSize clip;
  91
  92     bool invalid;
  93     bool antiAlias;
  94 };
  95
  96
  97 static inline SwPoint UPSCALE(const SwPoint& pt)
  98 {
  99     return {pt.x << (PIXEL_BITS - 6), pt.y << (PIXEL_BITS - 6)};
 100 }
 101
 102
 103 static inline SwPoint TRUNC(const SwPoint& pt)
 104 {
 105     return  {pt.x >> PIXEL_BITS, pt.y >> PIXEL_BITS};
 106 }
 107
 108
 109 static inline SwCoord TRUNC(const SwCoord x)
 110 {
 111     return  x >> PIXEL_BITS;
 112 }
 113
 114
 115 static inline SwPoint SUBPIXELS(const SwPoint& pt)
 116 {
 117     return {pt.x << PIXEL_BITS, pt.y << PIXEL_BITS};
 118 }
 119
 120
 121 static inline SwCoord SUBPIXELS(const SwCoord x)
 122 {
 123     return (x << PIXEL_BITS);
 124 }
 125
 126 /*
 127  *  Approximate sqrt(x*x+y*y) using the `alpha max plus beta min'
 128  *  algorithm.  We use alpha = 1, beta = 3/8, giving us results with a
 129  *  largest error less than 7% compared to the exact value.
 130  */
 131 static inline SwCoord HYPOT(SwPoint pt)
 132 {
 133     if (pt.x < 0) pt.x = -pt.x;
 134     if (pt.y < 0) pt.y = -pt.y;
 135     return ((pt.x > pt.y) ? (pt.x + (3 * pt.y >> 3)) : (pt.y + (3 * pt.x >> 3)));
 136 }
 137
 138 static void _genSpan(SwRleData* rle, const SwSpan* spans, uint32_t count)
 139 {
 140     auto newSize = rle->size + count;
 141
 142     /* allocate enough memory for new spans */
 143     /* alloc is required to prevent free and reallocation */
 144     /* when the rle needs to be regenerated because of attribute change. */
 145     if (rle->alloc < newSize) {
 146         rle->alloc = (newSize * 2);
 147         rle->spans = static_cast<SwSpan*>(realloc(rle->spans, rle->alloc * sizeof(SwSpan)));
 148     }
 149
 150     //copy the new spans to the allocated memory
 151     SwSpan* lastSpan = rle->spans + rle->size;
 152     memcpy(lastSpan, spans, count * sizeof(SwSpan));
 153
 154     rle->size = newSize;
 155 }
 156
 157
 158 static void _horizLine(RleWorker& rw, SwCoord x, SwCoord y, SwCoord area, SwCoord acount)
 159 {
 160     x += rw.cellMin.x;
 161     y += rw.cellMin.y;
 162
 163     //Clip Y range
 164     if (y < 0) return;
 165     if (y >= rw.clip.h) return;
 166
 167     /* compute the coverage line's coverage, depending on the outline fill rule */
 168     /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
 169     auto coverage = static_cast<int>(area >> (PIXEL_BITS * 2 + 1 - 8));    //range 0 - 256
 170
 171     if (coverage < 0) coverage = -coverage;
 172
 173     if (rw.outline->fillRule == FillRule::EvenOdd) {
 174         coverage &= 511;
 175         if (coverage > 256) coverage = 512 - coverage;
 176         else if (coverage == 256) coverage = 255;
 177     } else {
 178         //normal non-zero winding rule
 179         if (coverage >= 256) coverage = 255;
 180     }
 181
 182     //span has ushort coordinates. check limit overflow
 183     if (x >= SHRT_MAX) {
 184         //LOG: x coordinate overflow!
 185         x = SHRT_MAX;
 186     }
 187     if (y >= SHRT_MAX) {
 188         //LOG: y coordinate overflow!
 189         y = SHRT_MAX;
 190     }
 191
 192     if (coverage > 0) {
 193         if (!rw.antiAlias) coverage = 255;
 194         auto count = rw.spansCnt;
 195         auto span = rw.spans + count - 1;
 196
 197         //see whether we can add this span to the current list
 198         if ((count > 0) && (rw.ySpan == y) &&
 199             (span->x + span->len == x) && (span->coverage == coverage)) {
 200
 201             //Clip x range
 202             SwCoord xOver = 0;
 203             if (x + acount >= rw.clip.w) xOver -= (x + acount - rw.clip.w);
 204             if (x < 0) xOver += x;
 205
 206             //span->len += (acount + xOver) - 1;
 207             span->len += (acount + xOver);
 208             return;
 209         }
 210
 211         if (count >=  MAX_SPANS) {
 212             _genSpan(rw.rle, rw.spans, count);
 213             rw.spansCnt = 0;
 214             rw.ySpan = 0;
 215             span = rw.spans;
 216         } else {
 217             ++span;
 218         }
 219
 220         //Clip x range
 221         SwCoord xOver = 0;
 222         if (x + acount >= rw.clip.w) xOver -= (x + acount - rw.clip.w);
 223         if (x < 0) {
 224             xOver += x;
 225             x = 0;
 226         }
 227
 228         //Nothing to draw
 229         if (acount + xOver <= 0) return;
 230
 231         //add a span to the current list
 232         span->x = x;
 233         span->y = y;
 234         span->len = (acount + xOver);
 235         span->coverage = coverage;
 236         ++rw.spansCnt;
 237         rw.ySpan = y;
 238     }
 239 }
 240
 241
 242 static void _sweep(RleWorker& rw)
 243 {
 244     if (rw.cellsCnt == 0) return;
 245
 246     rw.spansCnt = 0;
 247     rw.ySpan = 0;
 248
 249     for (int y = 0; y < rw.yCnt; ++y) {
 250         auto cover = 0;
 251         auto x = 0;
 252         auto cell = rw.yCells[y];
 253
 254         while (cell) {
 255
 256             if (cell->x > x && cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), cell->x - x);
 257             cover += cell->cover;
 258             auto area = cover * (ONE_PIXEL * 2) - cell->area;
 259             if (area != 0 && cell->x >= 0) _horizLine(rw, cell->x, y, area, 1);
 260
 261             x = cell->x + 1;
 262             cell = cell->next;
 263         }
 264
 265         if (cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), rw.cellXCnt - x);
 266     }
 267
 268     if (rw.spansCnt > 0) _genSpan(rw.rle, rw.spans, rw.spansCnt);
 269 }
 270
 271
 272 static Cell* _findCell(RleWorker& rw)
 273 {
 274     auto x = rw.cellPos.x;
 275     if (x > rw.cellXCnt) x = rw.cellXCnt;
 276
 277     auto pcell = &rw.yCells[rw.cellPos.y];
 278
 279     while(true) {
 280         Cell* cell = *pcell;
 281         if (!cell || cell->x > x) break;
 282         if (cell->x == x) return cell;
 283         pcell = &cell->next;
 284     }
 285
 286     if (rw.cellsCnt >= rw.maxCells) longjmp(rw.jmpBuf, 1);
 287
 288     auto cell = rw.cells + rw.cellsCnt++;
 289     cell->x = x;
 290     cell->area = 0;
 291     cell->cover = 0;
 292     cell->next = *pcell;
 293     *pcell = cell;
 294
 295     return cell;
 296 }
 297
 298
 299 static void _recordCell(RleWorker& rw)
 300 {
 301     if (rw.area | rw.cover) {
 302         auto cell = _findCell(rw);
 303         cell->area += rw.area;
 304         cell->cover += rw.cover;
 305     }
 306 }
 307
 308
 309 static void _setCell(RleWorker& rw, SwPoint pos)
 310 {
 311     /* Move the cell pointer to a new position.  We set the `invalid'      */
 312     /* flag to indicate that the cell isn't part of those we're interested */
 313     /* in during the render phase.  This means that:                       */
 314     /*                                                                     */
 315     /* . the new vertical position must be within min_ey..max_ey-1.        */
 316     /* . the new horizontal position must be strictly less than max_ex     */
 317     /*                                                                     */
 318     /* Note that if a cell is to the left of the clipping region, it is    */
 319     /* actually set to the (min_ex-1) horizontal position.                 */
 320
 321     /* All cells that are on the left of the clipping region go to the
 322        min_ex - 1 horizontal position. */
 323     pos.y -= rw.cellMin.y;
 324
 325     if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
 326     pos.x -= rw.cellMin.x;
 327     if (pos.x < 0) pos.x = -1;
 328
 329     //Are we moving to a different cell?
 330     if (pos != rw.cellPos) {
 331         //Record the current one if it is valid
 332         if (!rw.invalid) _recordCell(rw);
 333     }
 334
 335     rw.area = 0;
 336     rw.cover = 0;
 337     rw.cellPos = pos;
 338     rw.invalid = ((unsigned)pos.y >= (unsigned)rw.cellYCnt || pos.x >= rw.cellXCnt);
 339 }
 340
 341
 342 static void _startCell(RleWorker& rw, SwPoint pos)
 343 {
 344     if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
 345     if (pos.x < rw.cellMin.x) pos.x = rw.cellMin.x;
 346     //if (pos.x < rw.cellMin.x) pos.x = (rw.cellMin.x - 1);
 347
 348     rw.area = 0;
 349     rw.cover = 0;
 350     rw.cellPos = pos - rw.cellMin;
 351     rw.invalid = false;
 352
 353     _setCell(rw, pos);
 354 }
 355
 356
 357 static void _moveTo(RleWorker& rw, const SwPoint& to)
 358 {
 359     //record current cell, if any */
 360     if (!rw.invalid) _recordCell(rw);
 361
 362     //start to a new position
 363     _startCell(rw, TRUNC(to));
 364
 365     rw.pos = to;
 366 }
 367
 368
 369 static void _lineTo(RleWorker& rw, const SwPoint& to)
 370 {
 371 #define SW_UDIV(a, b) \
 372     static_cast<SwCoord>(((unsigned long)(a) * (unsigned long)(b)) >> \
 373     (sizeof(long) * CHAR_BIT - PIXEL_BITS))
 374
 375     auto e1 = TRUNC(rw.pos);
 376     auto e2 = TRUNC(to);
 377
 378     //vertical clipping
 379     if ((e1.y >= rw.cellMax.y && e2.y >= rw.cellMax.y) ||
 380         (e1.y < rw.cellMin.y && e2.y < rw.cellMin.y)) {
 381             rw.pos = to;
 382             return;
 383     }
 384
 385     auto diff = to - rw.pos;
 386     auto f1 = rw.pos - SUBPIXELS(e1);
 387     SwPoint f2;
 388
 389     //inside one cell
 390     if (e1 == e2) {
 391         ;
 392     //any horizontal line
 393     } else if (diff.y == 0) {
 394         e1.x = e2.x;
 395         _setCell(rw, e1);
 396     } else if (diff.x == 0) {
 397         //vertical line up
 398         if (diff.y > 0) {
 399             do {
 400                 f2.y = ONE_PIXEL;
 401                 rw.cover += (f2.y - f1.y);
 402                 rw.area += (f2.y - f1.y) * f1.x * 2;
 403                 f1.y = 0;
 404                 ++e1.y;
 405                 _setCell(rw, e1);
 406             } while(e1.y != e2.y);
 407         //vertical line down
 408         } else {
 409             do {
 410                 f2.y = 0;
 411                 rw.cover += (f2.y - f1.y);
 412                 rw.area += (f2.y - f1.y) * f1.x * 2;
 413                 f1.y = ONE_PIXEL;
 414                 --e1.y;
 415                 _setCell(rw, e1);
 416             } while(e1.y != e2.y);
 417         }
 418     //any other line
 419     } else {
 420         Area prod = diff.x * f1.y - diff.y * f1.x;
 421
 422         /* These macros speed up repetitive divisions by replacing them
 423            with multiplications and right shifts. */
 424         auto dx_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.x);
 425         auto dy_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.y);
 426
 427         /* The fundamental value `prod' determines which side and the  */
 428         /* exact coordinate where the line exits current cell.  It is  */
 429         /* also easily updated when moving from one cell to the next.  */
 430         do {
 431             auto px = diff.x * ONE_PIXEL;
 432             auto py = diff.y * ONE_PIXEL;
 433
 434             //left
 435             if (prod <= 0 && prod - px > 0) {
 436                 f2 = {0, SW_UDIV(-prod, -dx_r)};
 437                 prod -= py;
 438                 rw.cover += (f2.y - f1.y);
 439                 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
 440                 f1 = {ONE_PIXEL, f2.y};
 441                 --e1.x;
 442             //up
 443             } else if (prod - px <= 0 && prod - px + py > 0) {
 444                 prod -= px;
 445                 f2 = {SW_UDIV(-prod, dy_r), ONE_PIXEL};
 446                 rw.cover += (f2.y - f1.y);
 447                 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
 448                 f1 = {f2.x, 0};
 449                 ++e1.y;
 450             //right
 451             } else if (prod - px + py <= 0 && prod + py >= 0) {
 452                 prod += py;
 453                 f2 = {ONE_PIXEL, SW_UDIV(prod, dx_r)};
 454                 rw.cover += (f2.y - f1.y);
 455                 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
 456                 f1 = {0, f2.y};
 457                 ++e1.x;
 458             //down
 459             } else {
 460                 f2 = {SW_UDIV(prod, -dy_r), 0};
 461                 prod += px;
 462                 rw.cover += (f2.y - f1.y);
 463                 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
 464                 f1 = {f2.x, ONE_PIXEL};
 465                 --e1.y;
 466             }
 467
 468             _setCell(rw, e1);
 469
 470         } while(e1 != e2);
 471     }
 472
 473     f2 = {to.x - SUBPIXELS(e2.x), to.y - SUBPIXELS(e2.y)};
 474     rw.cover += (f2.y - f1.y);
 475     rw.area += (f2.y - f1.y) * (f1.x + f2.x);
 476     rw.pos = to;
 477 }
 478
 479
 480 static void _cubicTo(RleWorker& rw, const SwPoint& ctrl1, const SwPoint& ctrl2, const SwPoint& to)
 481 {
 482     auto arc = rw.bezStack;
 483     arc[0] = to;
 484     arc[1] = ctrl2;
 485     arc[2] = ctrl1;
 486     arc[3] = rw.pos;
 487
 488     //Short-cut the arc that crosses the current band
 489     auto min = arc[0].y;
 490     auto max = arc[0].y;
 491
 492     SwCoord y;
 493     for (auto i = 1; i < 4; ++i) {
 494         y = arc[i].y;
 495         if (y < min) min = y;
 496         if (y > max) max = y;
 497     }
 498
 499     if (TRUNC(min) >= rw.cellMax.y || TRUNC(max) < rw.cellMin.y) goto draw;
 500
 501     /* Decide whether to split or draw. See `Rapid Termination          */
 502     /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
 503     /* F. Hain, at                                                      */
 504     /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
 505     while (true) {
 506         {
 507             //diff is the P0 - P3 chord vector
 508             auto diff = arc[3] - arc[0];
 509             auto L = HYPOT(diff);
 510
 511             //avoid possible arithmetic overflow below by splitting
 512             if (L > SHRT_MAX) goto split;
 513
 514             //max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1)
 515             auto sLimit = L * (ONE_PIXEL / 6);
 516
 517             auto diff1 = arc[1] - arc[0];
 518             auto s = diff.y * diff1.x - diff.x * diff1.y;
 519             if (s < 0) s = -s;
 520             if (s > sLimit) goto split;
 521
 522             //s is L * the perpendicular distance from P2 to the line P0 - P3
 523             auto diff2 = arc[2] - arc[0];
 524             s = diff.y * diff2.x - diff.x * diff2.y;
 525             if (s < 0) s = -s;
 526             if (s > sLimit) goto split;
 527
 528             /* Split super curvy segments where the off points are so far
 529             from the chord that the angles P0-P1-P3 or P0-P2-P3 become
 530             acute as detected by appropriate dot products */
 531             if (diff1.x * (diff1.x - diff.x) + diff1.y * (diff1.y - diff.y) > 0 ||
 532                 diff2.x * (diff2.x - diff.x) + diff2.y * (diff2.y - diff.y) > 0)
 533                 goto split;
 534
 535             //no reason to split
 536             goto draw;
 537         }
 538     split:
 539         mathSplitCubic(arc);
 540         arc += 3;
 541         continue;
 542
 543     draw:
 544         _lineTo(rw, arc[0]);
 545         if (arc == rw.bezStack) return;
 546         arc -= 3;
 547     }
 548 }
 549
 550
 551 static bool _decomposeOutline(RleWorker& rw)
 552 {
 553     auto outline = rw.outline;
 554     auto first = 0;  //index of first point in contour
 555
 556     for (uint32_t n = 0; n < outline->cntrsCnt; ++n) {
 557         auto last = outline->cntrs[n];
 558         auto limit = outline->pts + last;
 559         auto start = UPSCALE(outline->pts[first]);
 560         auto pt = outline->pts + first;
 561         auto types = outline->types + first;
 562
 563         /* A contour cannot start with a cubic control point! */
 564         if (types[0] == SW_CURVE_TYPE_CUBIC) goto invalid_outline;
 565
 566         _moveTo(rw, UPSCALE(outline->pts[first]));
 567
 568         while (pt < limit) {
 569             ++pt;
 570             ++types;
 571
 572             //emit a single line_to
 573             if (types[0] == SW_CURVE_TYPE_POINT) {
 574                 _lineTo(rw, UPSCALE(*pt));
 575             //types cubic
 576             } else {
 577                 if (pt + 1 > limit || types[1] != SW_CURVE_TYPE_CUBIC)
 578                     goto invalid_outline;
 579
 580                 pt += 2;
 581                 types += 2;
 582
 583                 if (pt <= limit) {
 584                     _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), UPSCALE(pt[0]));
 585                     continue;
 586                 }
 587                 _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), start);
 588                 goto close;
 589             }
 590         }
 591         _lineTo(rw, start);
 592     close:
 593        first = last + 1;
 594     }
 595
 596     return true;
 597
 598 invalid_outline:
 599     //LOG: Invalid Outline!
 600     return false;
 601 }
 602
 603
 604 static int _genRle(RleWorker& rw)
 605 {
 606     if (setjmp(rw.jmpBuf) == 0) {
 607         auto ret = _decomposeOutline(rw);
 608         if (!rw.invalid) _recordCell(rw);
 609         if (ret) return 0;  //success
 610         else return 1;      //fail
 611     }
 612     return -1;              //lack of cell memory
 613 }
 614
 615
 616 SwSpan* _intersectSpansRegion(const SwRleData *clip, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt)
 617 {
 618     auto out = outSpans;
 619     auto spans = targetRle->spans;
 620     auto end = targetRle->spans + targetRle->size;
 621     auto clipSpans = clip->spans;
 622     auto clipEnd = clip->spans + clip->size;
 623
 624     while (spanCnt > 0 && spans < end ) {
 625         if (clipSpans == clipEnd) {
 626             spans = end;
 627             break;
 628         }
 629         if (clipSpans->y > spans->y) {
 630             ++spans;
 631             continue;
 632         }
 633         if (spans->y != clipSpans->y) {
 634             ++clipSpans;
 635             continue;
 636         }
 637         auto sx1 = spans->x;
 638         auto sx2 = sx1 + spans->len;
 639         auto cx1 = clipSpans->x;
 640         auto cx2 = cx1 + clipSpans->len;
 641
 642         if (cx1 < sx1 && cx2 < sx1) {
 643             ++clipSpans;
 644             continue;
 645         }
 646         else if (sx1 < cx1 && sx2 < cx1) {
 647             ++spans;
 648             continue;
 649         }
 650         auto x = sx1 > cx1 ? sx1 : cx1;
 651         auto len = (sx2 < cx2 ? sx2 : cx2) - x;
 652         if (len) {
 653             auto spansCorverage = spans->coverage;
 654             auto clipSpansCoverage = clipSpans->coverage;
 655             out->x = sx1 > cx1 ? sx1 : cx1;
 656             out->len = (sx2 < cx2 ? sx2 : cx2) - out->x;
 657             out->y = spans->y;
 658             out->coverage = (uint8_t)((spansCorverage * clipSpansCoverage) >> 8);
 659             ++out;
 660             --spanCnt;
 661         }
 662         if (sx2 < cx2) ++spans;
 663         else ++clipSpans;
 664     }
 665     return out;
 666 }
 667
 668 SwSpan* _intersectMaskRegion(const SwRleData *clip, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt)
 669 {
 670
 671     auto out = outSpans;
 672     auto spans = targetRle->spans;
 673     auto end = targetRle->spans + targetRle->size;
 674     auto clipSpans = clip->spans;
 675     auto clipSpans1 = clip->spans;
 676     auto clipEnd = clip->spans + clip->size;
 677
 678     auto maskClipMin = clipSpans1->y;
 679     auto maskClipMax = clipSpans1->y;
 680
 681     while (clipSpans1->y) {
 682         if (clipSpans1->y > maskClipMax)
 683             maskClipMax = clipSpans1->y;
 684
 685         if (clipSpans1->y < maskClipMax)
 686             maskClipMin = clipSpans1->y;
 687         clipSpans1++;
 688     }
 689
 690     while (spanCnt && spans < end ) {
 691         if (clipSpans > clipEnd) {
 692             spans = end;
 693             break;
 694         }
 695
 696
 697         if (spans->y < maskClipMin || spans->y > maskClipMax) {
 698             out->x = spans->x;
 699             out->y = spans->y;
 700             out->len = spans->len;
 701             out->coverage = spans->coverage;
 702             ++out;
 703         }
 704         else {
 705             while (clipSpans->y) {
 706                 auto sx1 = spans->x;
 707                 auto sx2 = sx1 + spans->len;
 708                 auto cx1 = clipSpans->x;
 709                 auto cx2 = cx1 + clipSpans->len;
 710                 auto x = sx1 > cx1 ? sx1 : cx1;
 711                 auto len = (sx2 < cx2 ? sx2 : cx2) - x;
 712
 713                 if (len > 1) {
 714                     out->x = sx1;
 715                     out->y = clipSpans->y;
 716                     out->len = cx1-sx1;
 717                     out->coverage = spans->coverage;
 718                     ++out;
 719
 720                     out->x = cx2;
 721                     out->y = clipSpans->y;
 722                     out->len = sx2 - cx2;
 723                     out->coverage = spans->coverage;
 724                     ++out;
 725                 }
 726                 clipSpans++;
 727             }
 728         }
 729         --spanCnt;
 730         ++spans;
 731     }
 732
 733     return out;
 734 }
 735
 736
 737 SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRleData *targetRle, SwSpan *outSpans, uint32_t spanCnt)
 738 {
 739     auto out = outSpans;
 740     auto spans = targetRle->spans;
 741     auto end = targetRle->spans + targetRle->size;
 742     auto minx = static_cast<int16_t>(bbox->min.x);
 743     auto miny = static_cast<int16_t>(bbox->min.y);
 744     auto maxx = minx + static_cast<int16_t>(bbox->max.x - bbox->min.x) - 1;
 745     auto maxy = miny + static_cast<int16_t>(bbox->max.y - bbox->min.y) - 1;
 746
 747     while (spanCnt && spans < end ) {
 748         if (spans->y > maxy) {
 749             spans = end;
 750             break;
 751         }
 752         if (spans->y < miny || spans->x > maxx || spans->x + spans->len <= minx) {
 753             ++spans;
 754             continue;
 755         }
 756         if (spans->x < minx) {
 757             out->len = (spans->len - (minx - spans->x)) < (maxx - minx + 1) ? (spans->len - (minx - spans->x)) : (maxx - minx + 1);
 758             out->x = minx;
 759         }
 760         else {
 761             out->x = spans->x;
 762             out->len = spans->len < (maxx - spans->x + 1) ? spans->len : (maxx - spans->x + 1);
 763         }
 764         if (out->len != 0) {
 765             out->y = spans->y;
 766             out->coverage = spans->coverage;
 767             ++out;
 768         }
 769         ++spans;
 770         --spanCnt;
 771     }
 772     return out;
 773 }
 774
 775 /************************************************************************/
 776 /* External Class Implementation                                        */
 777 /************************************************************************/
 778
 779 SwRleData* rleRender(SwRleData* rle, const SwOutline* outline, const SwBBox& bbox, const SwSize& clip, bool antiAlias)
 780 {
 781     constexpr auto RENDER_POOL_SIZE = 16384L;
 782     constexpr auto BAND_SIZE = 40;
 783
 784     //TODO: We can preserve several static workers in advance
 785     RleWorker rw;
 786     Cell buffer[RENDER_POOL_SIZE / sizeof(Cell)];
 787
 788     //Init Cells
 789     rw.buffer = buffer;
 790     rw.bufferSize = sizeof(buffer);
 791     rw.yCells = reinterpret_cast<Cell**>(buffer);
 792     rw.cells = nullptr;
 793     rw.maxCells = 0;
 794     rw.cellsCnt = 0;
 795     rw.area = 0;
 796     rw.cover = 0;
 797     rw.invalid = true;
 798     rw.cellMin = bbox.min;
 799     rw.cellMax = bbox.max;
 800     rw.cellXCnt = rw.cellMax.x - rw.cellMin.x;
 801     rw.cellYCnt = rw.cellMax.y - rw.cellMin.y;
 802     rw.ySpan = 0;
 803     rw.outline = const_cast<SwOutline*>(outline);
 804     rw.bandSize = rw.bufferSize / (sizeof(Cell) * 8);  //bandSize: 64
 805     rw.bandShoot = 0;
 806     rw.clip = clip;
 807     rw.antiAlias = antiAlias;
 808
 809     if (!rle) rw.rle = reinterpret_cast<SwRleData*>(calloc(1, sizeof(SwRleData)));
 810     else rw.rle = rle;
 811
 812     //Generate RLE
 813     Band bands[BAND_SIZE];
 814     Band* band;
 815
 816     /* set up vertical bands */
 817     auto bandCnt = static_cast<int>((rw.cellMax.y - rw.cellMin.y) / rw.bandSize);
 818     if (bandCnt == 0) bandCnt = 1;
 819     else if (bandCnt >= BAND_SIZE) bandCnt = (BAND_SIZE - 1);
 820
 821     auto min = rw.cellMin.y;
 822     auto yMax = rw.cellMax.y;
 823     SwCoord max;
 824     int ret;
 825
 826     for (int n = 0; n < bandCnt; ++n, min = max) {
 827         max = min + rw.bandSize;
 828         if (n == bandCnt -1 || max > yMax) max = yMax;
 829
 830         bands[0].min = min;
 831         bands[0].max = max;
 832         band = bands;
 833
 834         while (band >= bands) {
 835             rw.yCells = static_cast<Cell**>(rw.buffer);
 836             rw.yCnt = band->max - band->min;
 837
 838             int cellStart = sizeof(Cell*) * (int)rw.yCnt;
 839             int cellMod = cellStart % sizeof(Cell);
 840
 841             if (cellMod > 0) cellStart += sizeof(Cell) - cellMod;
 842
 843             auto cellEnd = rw.bufferSize;
 844             cellEnd -= cellEnd % sizeof(Cell);
 845
 846             auto cellsMax = reinterpret_cast<Cell*>((char*)rw.buffer + cellEnd);
 847             rw.cells = reinterpret_cast<Cell*>((char*)rw.buffer + cellStart);
 848
 849             if (rw.cells >= cellsMax) goto reduce_bands;
 850
 851             rw.maxCells = cellsMax - rw.cells;
 852             if (rw.maxCells < 2) goto reduce_bands;
 853
 854             for (int y = 0; y < rw.yCnt; ++y)
 855                 rw.yCells[y] = nullptr;
 856
 857             rw.cellsCnt = 0;
 858             rw.invalid = true;
 859             rw.cellMin.y = band->min;
 860             rw.cellMax.y = band->max;
 861             rw.cellYCnt = band->max - band->min;
 862
 863             ret = _genRle(rw);
 864             if (ret == 0) {
 865                 _sweep(rw);
 866                 --band;
 867                 continue;
 868             } else if (ret == 1) {
 869                 goto error;
 870             }
 871
 872         reduce_bands:
 873             /* render pool overflow: we will reduce the render band by half */
 874             auto bottom = band->min;
 875             auto top = band->max;
 876             auto middle = bottom + ((top - bottom) >> 1);
 877
 878             /* This is too complex for a single scanline; there must
 879                be some problems */
 880             if (middle == bottom) goto error;
 881
 882             if (bottom - top >= rw.bandSize) ++rw.bandShoot;
 883
 884             band[1].min = bottom;
 885             band[1].max = middle;
 886             band[0].min = middle;
 887             band[0].max = top;
 888             ++band;
 889         }
 890     }
 891
 892     if (rw.bandShoot > 8 && rw.bandSize > 16)
 893         rw.bandSize = (rw.bandSize >> 1);
 894
 895     return rw.rle;
 896
 897 error:
 898     free(rw.rle);
 899     rw.rle = nullptr;
 900     return nullptr;
 901 }
 902
 903
 904 void rleReset(SwRleData* rle)
 905 {
 906     if (!rle) return;
 907     rle->size = 0;
 908 }
 909
 910
 911 void rleFree(SwRleData* rle)
 912 {
 913     if (!rle) return;
 914     if (rle->spans) free(rle->spans);
 915     free(rle);
 916 }
 917
 918 void updateRleSpans(SwRleData *rle, const SwSpan* curSpans, uint32_t size)
 919 {
 920     if (size == 0) {
 921         rle->size = 0;
 922         return;
 923     }
 924
 925     if (!rle->spans || !curSpans) return;
 926     rle->size = size;
 927     rle->spans = static_cast<SwSpan*>(realloc(rle->spans, rle->size * sizeof(SwSpan)));
 928
 929     if (!rle->spans) return;
 930
 931     for (int i = 0; i < (int)rle->size ; i++)
 932     {
 933        rle->spans[i].x = curSpans[i].x;
 934        rle->spans[i].y = curSpans[i].y;
 935        rle->spans[i].len = curSpans[i].len;
 936        rle->spans[i].coverage = curSpans[i].coverage;
 937     }
 938 }
 939
 940 void rleClipPath(SwRleData *rle, const SwRleData *clip)
 941 {
 942     if (rle->size == 0 || clip->size == 0) return;
 943     auto spanCnt = rle->size > clip->size ? rle->size : clip->size;
 944     auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (spanCnt)));
 945     if (!spans) return;
 946     auto spansEnd = _intersectSpansRegion(clip, rle, spans, spanCnt);
 947
 948     //Update Spans
 949     updateRleSpans(rle, spans, spansEnd - spans);
 950
 951     if (spans) free(spans);
 952
 953 #ifdef THORVG_LOG_ENABLED
 954     cout << "SW_ENGINE: Using ClipPath!" << endl;
 955 #endif
 956 }
 957
 958 void rleClipRect(SwRleData *rle, const SwBBox* clip)
 959 {
 960     if (rle->size == 0) return;
 961     auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (rle->size)));
 962     if (!spans) return;
 963     auto spansEnd = _intersectSpansRect(clip, rle, spans, rle->size);
 964
 965     //Update Spans
 966     updateRleSpans(rle, spans, spansEnd - spans);
 967
 968     if (spans) free(spans);
 969
 970 #ifdef THORVG_LOG_ENABLED
 971     cout <<"SW_ENGINE: Using ClipRect!" << endl;
 972 #endif
 973 }
 974
 975
 976 void rleAlphaMask(SwRleData *rle, const SwRleData *clip)
 977 {
 978     if (rle->size == 0 || clip->size == 0) return;
 979     auto spanCnt = rle->size + clip->size;
 980
 981     auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (spanCnt)));
 982
 983     if (!spans) return;
 984     auto spansEnd = _intersectMaskRegion(clip, rle, spans, spanCnt);
 985
 986     //Update Spans
 987     updateRleSpans(rle, spans, spansEnd - spans);
 988
 989     if (spans) free(spans);
 990 }
 991