1/*
2 * Copyright (c) 2020 - 2023 the ThorVG project. 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
23/*
24 * The FreeType Project LICENSE
25 * ----------------------------
26
27 * 2006-Jan-27
28
29 * Copyright 1996-2002, 2006 by
30 * David Turner, Robert Wilhelm, and Werner Lemberg
31
32
33
34 * Introduction
35 * ============
36
37 * The FreeType Project is distributed in several archive packages;
38 * some of them may contain, in addition to the FreeType font engine,
39 * various tools and contributions which rely on, or relate to, the
40 * FreeType Project.
41
42 * This license applies to all files found in such packages, and
43 * which do not fall under their own explicit license. The license
44 * affects thus the FreeType font engine, the test programs,
45 * documentation and makefiles, at the very least.
46
47 * This license was inspired by the BSD, Artistic, and IJG
48 * (Independent JPEG Group) licenses, which all encourage inclusion
49 * and use of free software in commercial and freeware products
50 * alike. As a consequence, its main points are that:
51
52 * o We don't promise that this software works. However, we will be
53 * interested in any kind of bug reports. (`as is' distribution)
54
55 * o You can use this software for whatever you want, in parts or
56 * full form, without having to pay us. (`royalty-free' usage)
57
58 * o You may not pretend that you wrote this software. If you use
59 * it, or only parts of it, in a program, you must acknowledge
60 * somewhere in your documentation that you have used the
61 * FreeType code. (`credits')
62
63 * We specifically permit and encourage the inclusion of this
64 * software, with or without modifications, in commercial products.
65 * We disclaim all warranties covering The FreeType Project and
66 * assume no liability related to The FreeType Project.
67
68
69 * Finally, many people asked us for a preferred form for a
70 * credit/disclaimer to use in compliance with this license. We thus
71 * encourage you to use the following text:
72
73 * """
74 * Portions of this software are copyright � <year> The FreeType
75 * Project (www.freetype.org). All rights reserved.
76 * """
77
78 * Please replace <year> with the value from the FreeType version you
79 * actually use.
80
81* Legal Terms
82* ===========
83
84* 0. Definitions
85* --------------
86
87* Throughout this license, the terms `package', `FreeType Project',
88* and `FreeType archive' refer to the set of files originally
89* distributed by the authors (David Turner, Robert Wilhelm, and
90* Werner Lemberg) as the `FreeType Project', be they named as alpha,
91* beta or final release.
92
93* `You' refers to the licensee, or person using the project, where
94* `using' is a generic term including compiling the project's source
95* code as well as linking it to form a `program' or `executable'.
96* This program is referred to as `a program using the FreeType
97* engine'.
98
99* This license applies to all files distributed in the original
100* FreeType Project, including all source code, binaries and
101* documentation, unless otherwise stated in the file in its
102* original, unmodified form as distributed in the original archive.
103* If you are unsure whether or not a particular file is covered by
104* this license, you must contact us to verify this.
105
106* The FreeType Project is copyright (C) 1996-2000 by David Turner,
107* Robert Wilhelm, and Werner Lemberg. All rights reserved except as
108* specified below.
109
110* 1. No Warranty
111* --------------
112
113* THE FREETYPE PROJECT IS PROVIDED `AS IS' WITHOUT WARRANTY OF ANY
114* KIND, EITHER EXPRESS OR IMPLIED, INCLUDING, BUT NOT LIMITED TO,
115* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
116* PURPOSE. IN NO EVENT WILL ANY OF THE AUTHORS OR COPYRIGHT HOLDERS
117* BE LIABLE FOR ANY DAMAGES CAUSED BY THE USE OR THE INABILITY TO
118* USE, OF THE FREETYPE PROJECT.
119
120* 2. Redistribution
121* -----------------
122
123* This license grants a worldwide, royalty-free, perpetual and
124* irrevocable right and license to use, execute, perform, compile,
125* display, copy, create derivative works of, distribute and
126* sublicense the FreeType Project (in both source and object code
127* forms) and derivative works thereof for any purpose; and to
128* authorize others to exercise some or all of the rights granted
129* herein, subject to the following conditions:
130
131* o Redistribution of source code must retain this license file
132* (`FTL.TXT') unaltered; any additions, deletions or changes to
133* the original files must be clearly indicated in accompanying
134* documentation. The copyright notices of the unaltered,
135* original files must be preserved in all copies of source
136* files.
137
138* o Redistribution in binary form must provide a disclaimer that
139* states that the software is based in part of the work of the
140* FreeType Team, in the distribution documentation. We also
141* encourage you to put an URL to the FreeType web page in your
142* documentation, though this isn't mandatory.
143
144* These conditions apply to any software derived from or based on
145* the FreeType Project, not just the unmodified files. If you use
146* our work, you must acknowledge us. However, no fee need be paid
147* to us.
148
149* 3. Advertising
150* --------------
151
152* Neither the FreeType authors and contributors nor you shall use
153* the name of the other for commercial, advertising, or promotional
154* purposes without specific prior written permission.
155
156* We suggest, but do not require, that you use one or more of the
157* following phrases to refer to this software in your documentation
158* or advertising materials: `FreeType Project', `FreeType Engine',
159* `FreeType library', or `FreeType Distribution'.
160
161* As you have not signed this license, you are not required to
162* accept it. However, as the FreeType Project is copyrighted
163* material, only this license, or another one contracted with the
164* authors, grants you the right to use, distribute, and modify it.
165* Therefore, by using, distributing, or modifying the FreeType
166* Project, you indicate that you understand and accept all the terms
167* of this license.
168
169* 4. Contacts
170* -----------
171
172* There are two mailing lists related to FreeType:
173
174* o freetype@nongnu.org
175
176* Discusses general use and applications of FreeType, as well as
177* future and wanted additions to the library and distribution.
178* If you are looking for support, start in this list if you
179* haven't found anything to help you in the documentation.
180
181* o freetype-devel@nongnu.org
182
183* Discusses bugs, as well as engine internals, design issues,
184* specific licenses, porting, etc.
185
186* Our home page can be found at
187
188* http://www.freetype.org
189*/
190
191#include <setjmp.h>
192#include <limits.h>
193#include <memory.h>
194#include "tvgSwCommon.h"
195
196/************************************************************************/
197/* Internal Class Implementation */
198/************************************************************************/
199
200constexpr auto MAX_SPANS = 256;
201constexpr auto PIXEL_BITS = 8; //must be at least 6 bits!
202constexpr auto ONE_PIXEL = (1L << PIXEL_BITS);
203
204using Area = long;
205
206struct Band
207{
208 SwCoord min, max;
209};
210
211struct Cell
212{
213 SwCoord x;
214 SwCoord cover;
215 Area area;
216 Cell *next;
217};
218
219struct RleWorker
220{
221 SwRleData* rle;
222
223 SwPoint cellPos;
224 SwPoint cellMin;
225 SwPoint cellMax;
226 SwCoord cellXCnt;
227 SwCoord cellYCnt;
228
229 Area area;
230 SwCoord cover;
231
232 Cell* cells;
233 ptrdiff_t maxCells;
234 ptrdiff_t cellsCnt;
235
236 SwPoint pos;
237
238 SwPoint bezStack[32 * 3 + 1];
239 int levStack[32];
240
241 SwOutline* outline;
242
243 SwSpan spans[MAX_SPANS];
244 int spansCnt;
245 int ySpan;
246
247 int bandSize;
248 int bandShoot;
249
250 jmp_buf jmpBuf;
251
252 void* buffer;
253 long bufferSize;
254
255 Cell** yCells;
256 SwCoord yCnt;
257
258 bool invalid;
259 bool antiAlias;
260};
261
262
263static inline SwPoint UPSCALE(const SwPoint& pt)
264{
265 return {SwCoord(((unsigned long) pt.x) << (PIXEL_BITS - 6)), SwCoord(((unsigned long) pt.y) << (PIXEL_BITS - 6))};
266}
267
268
269static inline SwPoint TRUNC(const SwPoint& pt)
270{
271 return {pt.x >> PIXEL_BITS, pt.y >> PIXEL_BITS};
272}
273
274
275static inline SwCoord TRUNC(const SwCoord x)
276{
277 return x >> PIXEL_BITS;
278}
279
280
281static inline SwPoint SUBPIXELS(const SwPoint& pt)
282{
283 return {SwCoord(((unsigned long) pt.x) << PIXEL_BITS), SwCoord(((unsigned long) pt.y) << PIXEL_BITS)};
284}
285
286
287static inline SwCoord SUBPIXELS(const SwCoord x)
288{
289 return SwCoord(((unsigned long) x) << PIXEL_BITS);
290}
291
292/*
293 * Approximate sqrt(x*x+y*y) using the `alpha max plus beta min'
294 * algorithm. We use alpha = 1, beta = 3/8, giving us results with a
295 * largest error less than 7% compared to the exact value.
296 */
297static inline SwCoord HYPOT(SwPoint pt)
298{
299 if (pt.x < 0) pt.x = -pt.x;
300 if (pt.y < 0) pt.y = -pt.y;
301 return ((pt.x > pt.y) ? (pt.x + (3 * pt.y >> 3)) : (pt.y + (3 * pt.x >> 3)));
302}
303
304static void _genSpan(SwRleData* rle, const SwSpan* spans, uint32_t count)
305{
306 auto newSize = rle->size + count;
307
308 /* allocate enough memory for new spans */
309 /* alloc is required to prevent free and reallocation */
310 /* when the rle needs to be regenerated because of attribute change. */
311 if (rle->alloc < newSize) {
312 rle->alloc = (newSize * 2);
313 //OPTIMIZE: use mempool!
314 rle->spans = static_cast<SwSpan*>(realloc(rle->spans, rle->alloc * sizeof(SwSpan)));
315 }
316
317 //copy the new spans to the allocated memory
318 SwSpan* lastSpan = rle->spans + rle->size;
319 memcpy(lastSpan, spans, count * sizeof(SwSpan));
320
321 rle->size = newSize;
322}
323
324
325static void _horizLine(RleWorker& rw, SwCoord x, SwCoord y, SwCoord area, SwCoord acount)
326{
327 x += rw.cellMin.x;
328 y += rw.cellMin.y;
329
330 //Clip Y range
331 if (y < rw.cellMin.y || y >= rw.cellMax.y) return;
332
333 /* compute the coverage line's coverage, depending on the outline fill rule */
334 /* the coverage percentage is area/(PIXEL_BITS*PIXEL_BITS*2) */
335 auto coverage = static_cast<int>(area >> (PIXEL_BITS * 2 + 1 - 8)); //range 0 - 255
336
337 if (coverage < 0) coverage = -coverage;
338
339 if (rw.outline->fillRule == FillRule::EvenOdd) {
340 coverage &= 511;
341 if (coverage > 255) coverage = 511 - coverage;
342 } else {
343 //normal non-zero winding rule
344 if (coverage > 255) coverage = 255;
345 }
346
347 //span has ushort coordinates. check limit overflow
348 if (x >= SHRT_MAX) {
349 TVGERR("SW_ENGINE", "X-coordiante overflow!");
350 x = SHRT_MAX;
351 }
352 if (y >= SHRT_MAX) {
353 TVGERR("SW_ENGINE", "Y Coordiante overflow!");
354 y = SHRT_MAX;
355 }
356
357 if (coverage > 0) {
358 if (!rw.antiAlias) coverage = 255;
359 auto count = rw.spansCnt;
360 auto span = rw.spans + count - 1;
361
362 //see whether we can add this span to the current list
363 if ((count > 0) && (rw.ySpan == y) &&
364 (span->x + span->len == x) && (span->coverage == coverage)) {
365
366 //Clip x range
367 SwCoord xOver = 0;
368 if (x + acount >= rw.cellMax.x) xOver -= (x + acount - rw.cellMax.x);
369 if (x < rw.cellMin.x) xOver -= (rw.cellMin.x - x);
370
371 //span->len += (acount + xOver) - 1;
372 span->len += (acount + xOver);
373 return;
374 }
375
376 if (count >= MAX_SPANS) {
377 _genSpan(rw.rle, rw.spans, count);
378 rw.spansCnt = 0;
379 rw.ySpan = 0;
380 span = rw.spans;
381 } else {
382 ++span;
383 }
384
385 //Clip x range
386 SwCoord xOver = 0;
387 if (x + acount >= rw.cellMax.x) xOver -= (x + acount - rw.cellMax.x);
388 if (x < rw.cellMin.x) {
389 xOver -= (rw.cellMin.x - x);
390 x = rw.cellMin.x;
391 }
392
393 //Nothing to draw
394 if (acount + xOver <= 0) return;
395
396 //add a span to the current list
397 span->x = x;
398 span->y = y;
399 span->len = (acount + xOver);
400 span->coverage = coverage;
401 ++rw.spansCnt;
402 rw.ySpan = y;
403 }
404}
405
406
407static void _sweep(RleWorker& rw)
408{
409 if (rw.cellsCnt == 0) return;
410
411 rw.spansCnt = 0;
412 rw.ySpan = 0;
413
414 for (int y = 0; y < rw.yCnt; ++y) {
415 auto cover = 0;
416 auto x = 0;
417 auto cell = rw.yCells[y];
418
419 while (cell) {
420 if (cell->x > x && cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), cell->x - x);
421 cover += cell->cover;
422 auto area = cover * (ONE_PIXEL * 2) - cell->area;
423 if (area != 0 && cell->x >= 0) _horizLine(rw, cell->x, y, area, 1);
424 x = cell->x + 1;
425 cell = cell->next;
426 }
427
428 if (cover != 0) _horizLine(rw, x, y, cover * (ONE_PIXEL * 2), rw.cellXCnt - x);
429 }
430
431 if (rw.spansCnt > 0) _genSpan(rw.rle, rw.spans, rw.spansCnt);
432}
433
434
435static Cell* _findCell(RleWorker& rw)
436{
437 auto x = rw.cellPos.x;
438 if (x > rw.cellXCnt) x = rw.cellXCnt;
439
440 auto pcell = &rw.yCells[rw.cellPos.y];
441
442 while(true) {
443 Cell* cell = *pcell;
444 if (!cell || cell->x > x) break;
445 if (cell->x == x) return cell;
446 pcell = &cell->next;
447 }
448
449 if (rw.cellsCnt >= rw.maxCells) longjmp(rw.jmpBuf, 1);
450
451 auto cell = rw.cells + rw.cellsCnt++;
452 cell->x = x;
453 cell->area = 0;
454 cell->cover = 0;
455 cell->next = *pcell;
456 *pcell = cell;
457
458 return cell;
459}
460
461
462static void _recordCell(RleWorker& rw)
463{
464 if (rw.area | rw.cover) {
465 auto cell = _findCell(rw);
466 cell->area += rw.area;
467 cell->cover += rw.cover;
468 }
469}
470
471
472static void _setCell(RleWorker& rw, SwPoint pos)
473{
474 /* Move the cell pointer to a new position. We set the `invalid' */
475 /* flag to indicate that the cell isn't part of those we're interested */
476 /* in during the render phase. This means that: */
477 /* */
478 /* . the new vertical position must be within min_ey..max_ey-1. */
479 /* . the new horizontal position must be strictly less than max_ex */
480 /* */
481 /* Note that if a cell is to the left of the clipping region, it is */
482 /* actually set to the (min_ex-1) horizontal position. */
483
484 /* All cells that are on the left of the clipping region go to the
485 min_ex - 1 horizontal position. */
486 pos.x -= rw.cellMin.x;
487 pos.y -= rw.cellMin.y;
488
489 if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
490
491 //Are we moving to a different cell?
492 if (pos != rw.cellPos) {
493 //Record the current one if it is valid
494 if (!rw.invalid) _recordCell(rw);
495 }
496
497 rw.area = 0;
498 rw.cover = 0;
499 rw.cellPos = pos;
500 rw.invalid = ((unsigned)pos.y >= (unsigned)rw.cellYCnt || pos.x >= rw.cellXCnt);
501}
502
503
504static void _startCell(RleWorker& rw, SwPoint pos)
505{
506 if (pos.x > rw.cellMax.x) pos.x = rw.cellMax.x;
507 if (pos.x < rw.cellMin.x) pos.x = rw.cellMin.x;
508
509 rw.area = 0;
510 rw.cover = 0;
511 rw.cellPos = pos - rw.cellMin;
512 rw.invalid = false;
513
514 _setCell(rw, pos);
515}
516
517
518static void _moveTo(RleWorker& rw, const SwPoint& to)
519{
520 //record current cell, if any */
521 if (!rw.invalid) _recordCell(rw);
522
523 //start to a new position
524 _startCell(rw, TRUNC(to));
525
526 rw.pos = to;
527}
528
529
530static void _lineTo(RleWorker& rw, const SwPoint& to)
531{
532#define SW_UDIV(a, b) \
533 static_cast<SwCoord>(((unsigned long)(a) * (unsigned long)(b)) >> \
534 (sizeof(long) * CHAR_BIT - PIXEL_BITS))
535
536 auto e1 = TRUNC(rw.pos);
537 auto e2 = TRUNC(to);
538
539 //vertical clipping
540 if ((e1.y >= rw.cellMax.y && e2.y >= rw.cellMax.y) || (e1.y < rw.cellMin.y && e2.y < rw.cellMin.y)) {
541 rw.pos = to;
542 return;
543 }
544
545 auto diff = to - rw.pos;
546 auto f1 = rw.pos - SUBPIXELS(e1);
547 SwPoint f2;
548
549 //inside one cell
550 if (e1 == e2) {
551 ;
552 //any horizontal line
553 } else if (diff.y == 0) {
554 e1.x = e2.x;
555 _setCell(rw, e1);
556 } else if (diff.x == 0) {
557 //vertical line up
558 if (diff.y > 0) {
559 do {
560 f2.y = ONE_PIXEL;
561 rw.cover += (f2.y - f1.y);
562 rw.area += (f2.y - f1.y) * f1.x * 2;
563 f1.y = 0;
564 ++e1.y;
565 _setCell(rw, e1);
566 } while(e1.y != e2.y);
567 //vertical line down
568 } else {
569 do {
570 f2.y = 0;
571 rw.cover += (f2.y - f1.y);
572 rw.area += (f2.y - f1.y) * f1.x * 2;
573 f1.y = ONE_PIXEL;
574 --e1.y;
575 _setCell(rw, e1);
576 } while(e1.y != e2.y);
577 }
578 //any other line
579 } else {
580 Area prod = diff.x * f1.y - diff.y * f1.x;
581
582 /* These macros speed up repetitive divisions by replacing them
583 with multiplications and right shifts. */
584 auto dx_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.x);
585 auto dy_r = static_cast<long>(ULONG_MAX >> PIXEL_BITS) / (diff.y);
586
587 /* The fundamental value `prod' determines which side and the */
588 /* exact coordinate where the line exits current cell. It is */
589 /* also easily updated when moving from one cell to the next. */
590 do {
591 auto px = diff.x * ONE_PIXEL;
592 auto py = diff.y * ONE_PIXEL;
593
594 //left
595 if (prod <= 0 && prod - px > 0) {
596 f2 = {0, SW_UDIV(-prod, -dx_r)};
597 prod -= py;
598 rw.cover += (f2.y - f1.y);
599 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
600 f1 = {ONE_PIXEL, f2.y};
601 --e1.x;
602 //up
603 } else if (prod - px <= 0 && prod - px + py > 0) {
604 prod -= px;
605 f2 = {SW_UDIV(-prod, dy_r), ONE_PIXEL};
606 rw.cover += (f2.y - f1.y);
607 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
608 f1 = {f2.x, 0};
609 ++e1.y;
610 //right
611 } else if (prod - px + py <= 0 && prod + py >= 0) {
612 prod += py;
613 f2 = {ONE_PIXEL, SW_UDIV(prod, dx_r)};
614 rw.cover += (f2.y - f1.y);
615 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
616 f1 = {0, f2.y};
617 ++e1.x;
618 //down
619 } else {
620 f2 = {SW_UDIV(prod, -dy_r), 0};
621 prod += px;
622 rw.cover += (f2.y - f1.y);
623 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
624 f1 = {f2.x, ONE_PIXEL};
625 --e1.y;
626 }
627
628 _setCell(rw, e1);
629
630 } while(e1 != e2);
631 }
632
633 f2 = {to.x - SUBPIXELS(e2.x), to.y - SUBPIXELS(e2.y)};
634 rw.cover += (f2.y - f1.y);
635 rw.area += (f2.y - f1.y) * (f1.x + f2.x);
636 rw.pos = to;
637}
638
639
640static void _cubicTo(RleWorker& rw, const SwPoint& ctrl1, const SwPoint& ctrl2, const SwPoint& to)
641{
642 auto arc = rw.bezStack;
643 arc[0] = to;
644 arc[1] = ctrl2;
645 arc[2] = ctrl1;
646 arc[3] = rw.pos;
647
648 //Short-cut the arc that crosses the current band
649 auto min = arc[0].y;
650 auto max = arc[0].y;
651
652 SwCoord y;
653 for (auto i = 1; i < 4; ++i) {
654 y = arc[i].y;
655 if (y < min) min = y;
656 if (y > max) max = y;
657 }
658
659 if (TRUNC(min) >= rw.cellMax.y || TRUNC(max) < rw.cellMin.y) goto draw;
660
661 /* Decide whether to split or draw. See `Rapid Termination */
662 /* Evaluation for Recursive Subdivision of Bezier Curves' by Thomas */
663 /* F. Hain, at */
664 /* http://www.cis.southalabama.edu/~hain/general/Publications/Bezier/Camera-ready%20CISST02%202.pdf */
665 while (true) {
666 {
667 //diff is the P0 - P3 chord vector
668 auto diff = arc[3] - arc[0];
669 auto L = HYPOT(diff);
670
671 //avoid possible arithmetic overflow below by splitting
672 if (L > SHRT_MAX) goto split;
673
674 //max deviation may be as much as (s/L) * 3/4 (if Hain's v = 1)
675 auto sLimit = L * (ONE_PIXEL / 6);
676
677 auto diff1 = arc[1] - arc[0];
678 auto s = diff.y * diff1.x - diff.x * diff1.y;
679 if (s < 0) s = -s;
680 if (s > sLimit) goto split;
681
682 //s is L * the perpendicular distance from P2 to the line P0 - P3
683 auto diff2 = arc[2] - arc[0];
684 s = diff.y * diff2.x - diff.x * diff2.y;
685 if (s < 0) s = -s;
686 if (s > sLimit) goto split;
687
688 /* Split super curvy segments where the off points are so far
689 from the chord that the angles P0-P1-P3 or P0-P2-P3 become
690 acute as detected by appropriate dot products */
691 if (diff1.x * (diff1.x - diff.x) + diff1.y * (diff1.y - diff.y) > 0 ||
692 diff2.x * (diff2.x - diff.x) + diff2.y * (diff2.y - diff.y) > 0)
693 goto split;
694
695 //no reason to split
696 goto draw;
697 }
698 split:
699 mathSplitCubic(arc);
700 arc += 3;
701 continue;
702
703 draw:
704 _lineTo(rw, arc[0]);
705 if (arc == rw.bezStack) return;
706 arc -= 3;
707 }
708}
709
710
711static void _decomposeOutline(RleWorker& rw)
712{
713 auto outline = rw.outline;
714 auto first = 0; //index of first point in contour
715
716 for (auto cntr = outline->cntrs.data; cntr < outline->cntrs.end(); ++cntr) {
717 auto last = *cntr;
718 auto limit = outline->pts.data + last;
719 auto start = UPSCALE(outline->pts.data[first]);
720 auto pt = outline->pts.data + first;
721 auto types = outline->types.data + first;
722
723 _moveTo(rw, UPSCALE(outline->pts.data[first]));
724
725 while (pt < limit) {
726 ++pt;
727 ++types;
728
729 //emit a single line_to
730 if (types[0] == SW_CURVE_TYPE_POINT) {
731 _lineTo(rw, UPSCALE(*pt));
732 //types cubic
733 } else {
734 pt += 2;
735 types += 2;
736
737 if (pt <= limit) {
738 _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), UPSCALE(pt[0]));
739 continue;
740 }
741 _cubicTo(rw, UPSCALE(pt[-2]), UPSCALE(pt[-1]), start);
742 goto close;
743 }
744 }
745 _lineTo(rw, start);
746 close:
747 first = last + 1;
748 }
749}
750
751
752static int _genRle(RleWorker& rw)
753{
754 if (setjmp(rw.jmpBuf) == 0) {
755 _decomposeOutline(rw);
756 if (!rw.invalid) _recordCell(rw);
757 return 0;
758 }
759 return -1; //lack of cell memory
760}
761
762
763static SwSpan* _intersectSpansRegion(const SwRleData *clip, const SwRleData *target, SwSpan *outSpans, uint32_t outSpansCnt)
764{
765 auto out = outSpans;
766 auto spans = target->spans;
767 auto end = target->spans + target->size;
768 auto clipSpans = clip->spans;
769 auto clipEnd = clip->spans + clip->size;
770
771 while (spans < end && clipSpans < clipEnd) {
772 //align y cooridnates.
773 if (clipSpans->y > spans->y) {
774 ++spans;
775 continue;
776 }
777 if (spans->y > clipSpans->y) {
778 ++clipSpans;
779 continue;
780 }
781
782 //Try clipping with all clip spans which have a same y coordinate.
783 auto temp = clipSpans;
784 while(temp < clipEnd && outSpansCnt > 0 && temp->y == clipSpans->y) {
785 auto sx1 = spans->x;
786 auto sx2 = sx1 + spans->len;
787 auto cx1 = temp->x;
788 auto cx2 = cx1 + temp->len;
789
790 //The span must be left(x1) to right(x2) direction. Not intersected.
791 if (cx2 < sx1 || sx2 < cx1) {
792 ++temp;
793 continue;
794 }
795
796 //clip span region.
797 auto x = sx1 > cx1 ? sx1 : cx1;
798 auto len = (sx2 < cx2 ? sx2 : cx2) - x;
799 if (len > 0) {
800 out->x = x;
801 out->y = temp->y;
802 out->len = len;
803 out->coverage = (uint8_t)(((spans->coverage * temp->coverage) + 0xff) >> 8);
804 ++out;
805 --outSpansCnt;
806 }
807 ++temp;
808 }
809 ++spans;
810 }
811 return out;
812}
813
814
815static SwSpan* _intersectSpansRect(const SwBBox *bbox, const SwRleData *targetRle, SwSpan *outSpans, uint32_t outSpansCnt)
816{
817 auto out = outSpans;
818 auto spans = targetRle->spans;
819 auto end = targetRle->spans + targetRle->size;
820 auto minx = static_cast<int16_t>(bbox->min.x);
821 auto miny = static_cast<int16_t>(bbox->min.y);
822 auto maxx = minx + static_cast<int16_t>(bbox->max.x - bbox->min.x) - 1;
823 auto maxy = miny + static_cast<int16_t>(bbox->max.y - bbox->min.y) - 1;
824
825 while (outSpansCnt > 0 && spans < end) {
826 if (spans->y > maxy) {
827 spans = end;
828 break;
829 }
830 if (spans->y < miny || spans->x > maxx || spans->x + spans->len <= minx) {
831 ++spans;
832 continue;
833 }
834 if (spans->x < minx) {
835 out->len = (spans->len - (minx - spans->x)) < (maxx - minx + 1) ? (spans->len - (minx - spans->x)) : (maxx - minx + 1);
836 out->x = minx;
837 }
838 else {
839 out->x = spans->x;
840 out->len = spans->len < (maxx - spans->x + 1) ? spans->len : (maxx - spans->x + 1);
841 }
842 if (out->len > 0) {
843 out->y = spans->y;
844 out->coverage = spans->coverage;
845 ++out;
846 --outSpansCnt;
847 }
848 ++spans;
849 }
850 return out;
851}
852
853
854static SwSpan* _mergeSpansRegion(const SwRleData *clip1, const SwRleData *clip2, SwSpan *outSpans)
855{
856 auto out = outSpans;
857 auto spans1 = clip1->spans;
858 auto end1 = clip1->spans + clip1->size;
859 auto spans2 = clip2->spans;
860 auto end2 = clip2->spans + clip2->size;
861
862 //list two spans up in y order
863 //TODO: Remove duplicated regions?
864 while (spans1 < end1 && spans2 < end2) {
865 while (spans1 < end1 && spans1->y <= spans2->y) {
866 *out = *spans1;
867 ++spans1;
868 ++out;
869 }
870 if (spans1 >= end1) break;
871 while (spans2 < end2 && spans2->y <= spans1->y) {
872 *out = *spans2;
873 ++spans2;
874 ++out;
875 }
876 }
877
878 //Leftovers
879 while (spans1 < end1) {
880 *out = *spans1;
881 ++spans1;
882 ++out;
883 }
884 while (spans2 < end2) {
885 *out = *spans2;
886 ++spans2;
887 ++out;
888 }
889
890 return out;
891}
892
893
894void _replaceClipSpan(SwRleData *rle, SwSpan* clippedSpans, uint32_t size)
895{
896 free(rle->spans);
897 rle->spans = clippedSpans;
898 rle->size = rle->alloc = size;
899}
900
901
902/************************************************************************/
903/* External Class Implementation */
904/************************************************************************/
905
906SwRleData* rleRender(SwRleData* rle, const SwOutline* outline, const SwBBox& renderRegion, bool antiAlias)
907{
908 constexpr auto RENDER_POOL_SIZE = 16384L;
909 constexpr auto BAND_SIZE = 40;
910
911 //TODO: We can preserve several static workers in advance
912 RleWorker rw;
913 Cell buffer[RENDER_POOL_SIZE / sizeof(Cell)];
914
915 //Init Cells
916 rw.buffer = buffer;
917 rw.bufferSize = sizeof(buffer);
918 rw.yCells = reinterpret_cast<Cell**>(buffer);
919 rw.cells = nullptr;
920 rw.maxCells = 0;
921 rw.cellsCnt = 0;
922 rw.area = 0;
923 rw.cover = 0;
924 rw.invalid = true;
925 rw.cellMin = renderRegion.min;
926 rw.cellMax = renderRegion.max;
927 rw.cellXCnt = rw.cellMax.x - rw.cellMin.x;
928 rw.cellYCnt = rw.cellMax.y - rw.cellMin.y;
929 rw.ySpan = 0;
930 rw.outline = const_cast<SwOutline*>(outline);
931 rw.bandSize = rw.bufferSize / (sizeof(Cell) * 8); //bandSize: 64
932 rw.bandShoot = 0;
933 rw.antiAlias = antiAlias;
934
935 if (!rle) rw.rle = reinterpret_cast<SwRleData*>(calloc(1, sizeof(SwRleData)));
936 else rw.rle = rle;
937
938 //Generate RLE
939 Band bands[BAND_SIZE];
940 Band* band;
941
942 /* set up vertical bands */
943 auto bandCnt = static_cast<int>((rw.cellMax.y - rw.cellMin.y) / rw.bandSize);
944 if (bandCnt == 0) bandCnt = 1;
945 else if (bandCnt >= BAND_SIZE) bandCnt = (BAND_SIZE - 1);
946
947 auto min = rw.cellMin.y;
948 auto yMax = rw.cellMax.y;
949 SwCoord max;
950 int ret;
951
952 for (int n = 0; n < bandCnt; ++n, min = max) {
953 max = min + rw.bandSize;
954 if (n == bandCnt -1 || max > yMax) max = yMax;
955
956 bands[0].min = min;
957 bands[0].max = max;
958 band = bands;
959
960 while (band >= bands) {
961 rw.yCells = static_cast<Cell**>(rw.buffer);
962 rw.yCnt = band->max - band->min;
963
964 int cellStart = sizeof(Cell*) * (int)rw.yCnt;
965 int cellMod = cellStart % sizeof(Cell);
966
967 if (cellMod > 0) cellStart += sizeof(Cell) - cellMod;
968
969 auto cellEnd = rw.bufferSize;
970 cellEnd -= cellEnd % sizeof(Cell);
971
972 auto cellsMax = reinterpret_cast<Cell*>((char*)rw.buffer + cellEnd);
973 rw.cells = reinterpret_cast<Cell*>((char*)rw.buffer + cellStart);
974
975 if (rw.cells >= cellsMax) goto reduce_bands;
976
977 rw.maxCells = cellsMax - rw.cells;
978 if (rw.maxCells < 2) goto reduce_bands;
979
980 for (int y = 0; y < rw.yCnt; ++y)
981 rw.yCells[y] = nullptr;
982
983 rw.cellsCnt = 0;
984 rw.invalid = true;
985 rw.cellMin.y = band->min;
986 rw.cellMax.y = band->max;
987 rw.cellYCnt = band->max - band->min;
988
989 ret = _genRle(rw);
990 if (ret == 0) {
991 _sweep(rw);
992 --band;
993 continue;
994 } else if (ret == 1) {
995 goto error;
996 }
997
998 reduce_bands:
999 /* render pool overflow: we will reduce the render band by half */
1000 auto bottom = band->min;
1001 auto top = band->max;
1002 auto middle = bottom + ((top - bottom) >> 1);
1003
1004 /* This is too complex for a single scanline; there must
1005 be some problems */
1006 if (middle == bottom) goto error;
1007
1008 if (bottom - top >= rw.bandSize) ++rw.bandShoot;
1009
1010 band[1].min = bottom;
1011 band[1].max = middle;
1012 band[0].min = middle;
1013 band[0].max = top;
1014 ++band;
1015 }
1016 }
1017
1018 if (rw.bandShoot > 8 && rw.bandSize > 16)
1019 rw.bandSize = (rw.bandSize >> 1);
1020
1021 return rw.rle;
1022
1023error:
1024 free(rw.rle);
1025 rw.rle = nullptr;
1026 return nullptr;
1027}
1028
1029
1030SwRleData* rleRender(const SwBBox* bbox)
1031{
1032 auto width = static_cast<uint16_t>(bbox->max.x - bbox->min.x);
1033 auto height = static_cast<uint16_t>(bbox->max.y - bbox->min.y);
1034
1035 auto rle = static_cast<SwRleData*>(malloc(sizeof(SwRleData)));
1036 rle->spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * height));
1037 rle->size = height;
1038 rle->alloc = height;
1039
1040 auto span = rle->spans;
1041 for (uint16_t i = 0; i < height; ++i, ++span) {
1042 span->x = bbox->min.x;
1043 span->y = bbox->min.y + i;
1044 span->len = width;
1045 span->coverage = 255;
1046 }
1047
1048 return rle;
1049}
1050
1051
1052void rleReset(SwRleData* rle)
1053{
1054 if (!rle) return;
1055 rle->size = 0;
1056}
1057
1058
1059void rleFree(SwRleData* rle)
1060{
1061 if (!rle) return;
1062 if (rle->spans) free(rle->spans);
1063 free(rle);
1064}
1065
1066
1067void rleMerge(SwRleData* rle, SwRleData* clip1, SwRleData* clip2)
1068{
1069 if (!rle || (!clip1 && !clip2)) return;
1070 if (clip1 && clip1->size == 0 && clip2 && clip2->size == 0) return;
1071
1072 TVGLOG("SW_ENGINE", "Unifying Rle!");
1073
1074 //clip1 is empty, just copy clip2
1075 if (!clip1 || clip1->size == 0) {
1076 if (clip2) {
1077 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (clip2->size)));
1078 memcpy(spans, clip2->spans, clip2->size);
1079 _replaceClipSpan(rle, spans, clip2->size);
1080 } else {
1081 _replaceClipSpan(rle, nullptr, 0);
1082 }
1083 return;
1084 }
1085
1086 //clip2 is empty, just copy clip1
1087 if (!clip2 || clip2->size == 0) {
1088 if (clip1) {
1089 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (clip1->size)));
1090 memcpy(spans, clip1->spans, clip1->size);
1091 _replaceClipSpan(rle, spans, clip1->size);
1092 } else {
1093 _replaceClipSpan(rle, nullptr, 0);
1094 }
1095 return;
1096 }
1097
1098 auto spanCnt = clip1->size + clip2->size;
1099 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * spanCnt));
1100 auto spansEnd = _mergeSpansRegion(clip1, clip2, spans);
1101
1102 _replaceClipSpan(rle, spans, spansEnd - spans);
1103}
1104
1105
1106void rleClipPath(SwRleData *rle, const SwRleData *clip)
1107{
1108 if (rle->size == 0 || clip->size == 0) return;
1109 auto spanCnt = rle->size > clip->size ? rle->size : clip->size;
1110 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (spanCnt)));
1111 auto spansEnd = _intersectSpansRegion(clip, rle, spans, spanCnt);
1112
1113 _replaceClipSpan(rle, spans, spansEnd - spans);
1114
1115 TVGLOG("SW_ENGINE", "Using ClipPath!");
1116}
1117
1118
1119void rleClipRect(SwRleData *rle, const SwBBox* clip)
1120{
1121 if (rle->size == 0) return;
1122 auto spans = static_cast<SwSpan*>(malloc(sizeof(SwSpan) * (rle->size)));
1123 auto spansEnd = _intersectSpansRect(clip, rle, spans, rle->size);
1124
1125 _replaceClipSpan(rle, spans, spansEnd - spans);
1126
1127 TVGLOG("SW_ENGINE", "Using ClipRect!");
1128}
1129