1 /*
2 * Copyright (C) 2014 Vabishchevich Nikolay <vabnick@gmail.com>
3 *
4 * This file is part of libass.
5 *
6 * Permission to use, copy, modify, and distribute this software for any
7 * purpose with or without fee is hereby granted, provided that the above
8 * copyright notice and this permission notice appear in all copies.
9 *
10 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
11 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
12 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
13 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
14 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
15 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
16 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 */
18
19 #include "ass_utils.h"
20 #include "ass_rasterizer.h"
21 #include <assert.h>
22
23 #ifdef _MSC_VER
24 #include <intrin.h>
25 #pragma intrinsic(_BitScanReverse)
26 #endif
27
28
29
ilog2(uint32_t n)30 static inline int ilog2(uint32_t n) // XXX: different compilers
31 {
32 #ifdef __GNUC__
33 return __builtin_clz(n) ^ 31;
34 #elif defined(_MSC_VER)
35 int res;
36 _BitScanReverse(&res, n);
37 return res;
38 #else
39 int res = 0;
40 for (int ord = 16; ord; ord /= 2)
41 if (n >= ((uint32_t)1 << ord)) {
42 res += ord;
43 n >>= ord;
44 }
45 return res;
46 #endif
47 }
48
49
rasterizer_init(RasterizerData * rst,int outline_error)50 void rasterizer_init(RasterizerData *rst, int outline_error)
51 {
52 rst->outline_error = outline_error;
53 rst->linebuf[0] = rst->linebuf[1] = NULL;
54 rst->size[0] = rst->capacity[0] = 0;
55 rst->size[1] = rst->capacity[1] = 0;
56 }
57
58 /**
59 * \brief Ensure sufficient buffer size (allocate if necessary)
60 * \param index index (0 or 1) of the input segment buffer (rst->linebuf)
61 * \param delta requested size increase
62 * \return zero on error
63 */
check_capacity(RasterizerData * rst,int index,size_t delta)64 static inline int check_capacity(RasterizerData *rst, int index, size_t delta)
65 {
66 delta += rst->size[index];
67 if (rst->capacity[index] >= delta)
68 return 1;
69
70 size_t capacity = FFMAX(2 * rst->capacity[index], 64);
71 while (capacity < delta)
72 capacity *= 2;
73 void *ptr = realloc(rst->linebuf[index], sizeof(struct segment) * capacity);
74 if (!ptr)
75 return 0;
76
77 rst->linebuf[index] = (struct segment *)ptr;
78 rst->capacity[index] = capacity;
79 return 1;
80 }
81
rasterizer_done(RasterizerData * rst)82 void rasterizer_done(RasterizerData *rst)
83 {
84 free(rst->linebuf[0]);
85 free(rst->linebuf[1]);
86 }
87
88
89 /*
90 * Tiled Rasterization Algorithm
91 *
92 * 1) Convert splines into polylines using recursive subdivision.
93 *
94 * 2) Determine which segments of resulting polylines fall into each tile.
95 * That's done through recursive splitting of segment array with horizontal or vertical lines.
96 * Each individual segment can lie fully left(top) or right(bottom) from the splitting line or cross it.
97 * In the latter case copies of such segment go to both output arrays. Also winding count
98 * of the top-left corner of the second result rectangle gets calculated simultaneously with splitting.
99 * Winding count of the first result rectangle is the same as of the source rectangle.
100 *
101 * 3) When the splitting is done to the tile level, there are 3 possible outcome:
102 * - Tile doesn't have segments at all--fill it with solid color in accordance with winding count.
103 * - Tile have only 1 segment--use simple half-plane filling algorithm.
104 * - Generic case with 2 or more segments.
105 * In the latter case each segment gets rasterized as right trapezoid into buffer
106 * with additive or subtractive blending.
107 */
108
109
110 typedef struct {
111 int32_t x, y;
112 } OutlinePoint;
113
114 // Helper struct for spline split decision
115 typedef struct {
116 OutlinePoint r;
117 int64_t r2, er;
118 } OutlineSegment;
119
segment_init(OutlineSegment * seg,OutlinePoint beg,OutlinePoint end,int32_t outline_error)120 static inline void segment_init(OutlineSegment *seg,
121 OutlinePoint beg, OutlinePoint end,
122 int32_t outline_error)
123 {
124 int32_t x = end.x - beg.x;
125 int32_t y = end.y - beg.y;
126 int32_t abs_x = x < 0 ? -x : x;
127 int32_t abs_y = y < 0 ? -y : y;
128
129 seg->r.x = x;
130 seg->r.y = y;
131 seg->r2 = x * (int64_t)x + y * (int64_t)y;
132 seg->er = outline_error * (int64_t)FFMAX(abs_x, abs_y);
133 }
134
segment_subdivide(const OutlineSegment * seg,OutlinePoint beg,OutlinePoint pt)135 static inline int segment_subdivide(const OutlineSegment *seg,
136 OutlinePoint beg, OutlinePoint pt)
137 {
138 int32_t x = pt.x - beg.x;
139 int32_t y = pt.y - beg.y;
140 int64_t pdr = seg->r.x * (int64_t)x + seg->r.y * (int64_t)y;
141 int64_t pcr = seg->r.x * (int64_t)y - seg->r.y * (int64_t)x;
142 return pdr < -seg->er || pdr > seg->r2 + seg->er ||
143 (pcr < 0 ? -pcr : pcr) > seg->er;
144 }
145
146 /**
147 * \brief Add new segment to polyline
148 */
add_line(RasterizerData * rst,OutlinePoint pt0,OutlinePoint pt1)149 static inline int add_line(RasterizerData *rst, OutlinePoint pt0, OutlinePoint pt1)
150 {
151 int32_t x = pt1.x - pt0.x;
152 int32_t y = pt1.y - pt0.y;
153 if (!x && !y)
154 return 1;
155
156 if (!check_capacity(rst, 0, 1))
157 return 0;
158 struct segment *line = rst->linebuf[0] + rst->size[0];
159 ++rst->size[0];
160
161 line->flags = SEGFLAG_EXACT_LEFT | SEGFLAG_EXACT_RIGHT |
162 SEGFLAG_EXACT_TOP | SEGFLAG_EXACT_BOTTOM;
163 if (x < 0)
164 line->flags ^= SEGFLAG_UL_DR;
165 if (y >= 0)
166 line->flags ^= SEGFLAG_DN | SEGFLAG_UL_DR;
167
168 line->x_min = FFMIN(pt0.x, pt1.x);
169 line->x_max = FFMAX(pt0.x, pt1.x);
170 line->y_min = FFMIN(pt0.y, pt1.y);
171 line->y_max = FFMAX(pt0.y, pt1.y);
172
173 line->a = y;
174 line->b = -x;
175 line->c = y * (int64_t)pt0.x - x * (int64_t)pt0.y;
176
177 // halfplane normalization
178 int32_t abs_x = x < 0 ? -x : x;
179 int32_t abs_y = y < 0 ? -y : y;
180 uint32_t max_ab = (abs_x > abs_y ? abs_x : abs_y);
181 int shift = 30 - ilog2(max_ab);
182 max_ab <<= shift + 1;
183 line->a *= 1 << shift;
184 line->b *= 1 << shift;
185 line->c *= 1 << shift;
186 line->scale = (uint64_t)0x53333333 * (uint32_t)(max_ab * (uint64_t)max_ab >> 32) >> 32;
187 line->scale += 0x8810624D - (0xBBC6A7EF * (uint64_t)max_ab >> 32);
188 //line->scale = ((uint64_t)1 << 61) / max_ab;
189 return 1;
190 }
191
192 /**
193 * \brief Add quadratic spline to polyline
194 * Performs recursive subdivision if necessary.
195 */
add_quadratic(RasterizerData * rst,OutlinePoint pt0,OutlinePoint pt1,OutlinePoint pt2)196 static int add_quadratic(RasterizerData *rst,
197 OutlinePoint pt0, OutlinePoint pt1, OutlinePoint pt2)
198 {
199 OutlineSegment seg;
200 segment_init(&seg, pt0, pt2, rst->outline_error);
201 if (!segment_subdivide(&seg, pt0, pt1))
202 return add_line(rst, pt0, pt2);
203
204 OutlinePoint p01, p12, c; // XXX: overflow?
205 p01.x = pt0.x + pt1.x;
206 p01.y = pt0.y + pt1.y;
207 p12.x = pt1.x + pt2.x;
208 p12.y = pt1.y + pt2.y;
209 c.x = (p01.x + p12.x + 2) >> 2;
210 c.y = (p01.y + p12.y + 2) >> 2;
211 p01.x >>= 1;
212 p01.y >>= 1;
213 p12.x >>= 1;
214 p12.y >>= 1;
215 return add_quadratic(rst, pt0, p01, c) && add_quadratic(rst, c, p12, pt2);
216 }
217
218 /**
219 * \brief Add cubic spline to polyline
220 * Performs recursive subdivision if necessary.
221 */
add_cubic(RasterizerData * rst,OutlinePoint pt0,OutlinePoint pt1,OutlinePoint pt2,OutlinePoint pt3)222 static int add_cubic(RasterizerData *rst,
223 OutlinePoint pt0, OutlinePoint pt1, OutlinePoint pt2, OutlinePoint pt3)
224 {
225 OutlineSegment seg;
226 segment_init(&seg, pt0, pt3, rst->outline_error);
227 if (!segment_subdivide(&seg, pt0, pt1) && !segment_subdivide(&seg, pt0, pt2))
228 return add_line(rst, pt0, pt3);
229
230 OutlinePoint p01, p12, p23, p012, p123, c; // XXX: overflow?
231 p01.x = pt0.x + pt1.x;
232 p01.y = pt0.y + pt1.y;
233 p12.x = pt1.x + pt2.x + 2;
234 p12.y = pt1.y + pt2.y + 2;
235 p23.x = pt2.x + pt3.x;
236 p23.y = pt2.y + pt3.y;
237 p012.x = p01.x + p12.x;
238 p012.y = p01.y + p12.y;
239 p123.x = p12.x + p23.x;
240 p123.y = p12.y + p23.y;
241 c.x = (p012.x + p123.x - 1) >> 3;
242 c.y = (p012.y + p123.y - 1) >> 3;
243 p01.x >>= 1;
244 p01.y >>= 1;
245 p012.x >>= 2;
246 p012.y >>= 2;
247 p123.x >>= 2;
248 p123.y >>= 2;
249 p23.x >>= 1;
250 p23.y >>= 1;
251 return add_cubic(rst, pt0, p01, p012, c) && add_cubic(rst, c, p123, p23, pt3);
252 }
253
254
rasterizer_set_outline(RasterizerData * rst,const ASS_Outline * path)255 int rasterizer_set_outline(RasterizerData *rst, const ASS_Outline *path)
256 {
257 enum Status {
258 S_ON, S_Q, S_C1, S_C2
259 };
260
261 size_t i, j = 0;
262 rst->size[0] = 0;
263 for (i = 0; i < path->n_contours; ++i) {
264 OutlinePoint start, p[4];
265 int process_end = 1;
266 enum Status st;
267
268 int last = path->contours[i];
269 if (j > last)
270 return 0;
271
272 switch (FT_CURVE_TAG(path->tags[j])) {
273 case FT_CURVE_TAG_ON:
274 p[0].x = path->points[j].x;
275 p[0].y = -path->points[j].y;
276 start = p[0];
277 st = S_ON;
278 break;
279
280 case FT_CURVE_TAG_CONIC:
281 switch (FT_CURVE_TAG(path->tags[last])) {
282 case FT_CURVE_TAG_ON:
283 p[0].x = path->points[last].x;
284 p[0].y = -path->points[last].y;
285 p[1].x = path->points[j].x;
286 p[1].y = -path->points[j].y;
287 process_end = 0;
288 st = S_Q;
289 break;
290
291 case FT_CURVE_TAG_CONIC:
292 p[1].x = path->points[j].x;
293 p[1].y = -path->points[j].y;
294 p[0].x = (p[1].x + path->points[last].x) >> 1;
295 p[0].y = (p[1].y - path->points[last].y) >> 1;
296 start = p[0];
297 st = S_Q;
298 break;
299
300 default:
301 return 0;
302 }
303 break;
304
305 default:
306 return 0;
307 }
308
309 for (j++; j <= last; ++j)
310 switch (FT_CURVE_TAG(path->tags[j])) {
311 case FT_CURVE_TAG_ON:
312 switch (st) {
313 case S_ON:
314 p[1].x = path->points[j].x;
315 p[1].y = -path->points[j].y;
316 if (!add_line(rst, p[0], p[1]))
317 return 0;
318 p[0] = p[1];
319 break;
320
321 case S_Q:
322 p[2].x = path->points[j].x;
323 p[2].y = -path->points[j].y;
324 if (!add_quadratic(rst, p[0], p[1], p[2]))
325 return 0;
326 p[0] = p[2];
327 st = S_ON;
328 break;
329
330 case S_C2:
331 p[3].x = path->points[j].x;
332 p[3].y = -path->points[j].y;
333 if (!add_cubic(rst, p[0], p[1], p[2], p[3]))
334 return 0;
335 p[0] = p[3];
336 st = S_ON;
337 break;
338
339 default:
340 return 0;
341 }
342 break;
343
344 case FT_CURVE_TAG_CONIC:
345 switch (st) {
346 case S_ON:
347 p[1].x = path->points[j].x;
348 p[1].y = -path->points[j].y;
349 st = S_Q;
350 break;
351
352 case S_Q:
353 p[3].x = path->points[j].x;
354 p[3].y = -path->points[j].y;
355 p[2].x = (p[1].x + p[3].x) >> 1;
356 p[2].y = (p[1].y + p[3].y) >> 1;
357 if (!add_quadratic(rst, p[0], p[1], p[2]))
358 return 0;
359 p[0] = p[2];
360 p[1] = p[3];
361 break;
362
363 default:
364 return 0;
365 }
366 break;
367
368 case FT_CURVE_TAG_CUBIC:
369 switch (st) {
370 case S_ON:
371 p[1].x = path->points[j].x;
372 p[1].y = -path->points[j].y;
373 st = S_C1;
374 break;
375
376 case S_C1:
377 p[2].x = path->points[j].x;
378 p[2].y = -path->points[j].y;
379 st = S_C2;
380 break;
381
382 default:
383 return 0;
384 }
385 break;
386
387 default:
388 return 0;
389 }
390
391 if (process_end)
392 switch (st) {
393 case S_ON:
394 if (!add_line(rst, p[0], start))
395 return 0;
396 break;
397
398 case S_Q:
399 if (!add_quadratic(rst, p[0], p[1], start))
400 return 0;
401 break;
402
403 case S_C2:
404 if (!add_cubic(rst, p[0], p[1], p[2], start))
405 return 0;
406 break;
407
408 default:
409 return 0;
410 }
411 }
412
413 size_t k;
414 rst->x_min = rst->y_min = 0x7FFFFFFF;
415 rst->x_max = rst->y_max = 0x80000000;
416 for (k = 0; k < rst->size[0]; ++k) {
417 rst->x_min = FFMIN(rst->x_min, rst->linebuf[0][k].x_min);
418 rst->x_max = FFMAX(rst->x_max, rst->linebuf[0][k].x_max);
419 rst->y_min = FFMIN(rst->y_min, rst->linebuf[0][k].y_min);
420 rst->y_max = FFMAX(rst->y_max, rst->linebuf[0][k].y_max);
421 }
422 return 1;
423 }
424
425
segment_move_x(struct segment * line,int32_t x)426 static void segment_move_x(struct segment *line, int32_t x)
427 {
428 line->x_min -= x;
429 line->x_max -= x;
430 line->x_min = FFMAX(line->x_min, 0);
431 line->c -= line->a * (int64_t)x;
432
433 static const int test = SEGFLAG_EXACT_LEFT | SEGFLAG_UL_DR;
434 if (!line->x_min && (line->flags & test) == test)
435 line->flags &= ~SEGFLAG_EXACT_TOP;
436 }
437
segment_move_y(struct segment * line,int32_t y)438 static void segment_move_y(struct segment *line, int32_t y)
439 {
440 line->y_min -= y;
441 line->y_max -= y;
442 line->y_min = FFMAX(line->y_min, 0);
443 line->c -= line->b * (int64_t)y;
444
445 static const int test = SEGFLAG_EXACT_TOP | SEGFLAG_UL_DR;
446 if (!line->y_min && (line->flags & test) == test)
447 line->flags &= ~SEGFLAG_EXACT_LEFT;
448 }
449
segment_split_horz(struct segment * line,struct segment * next,int32_t x)450 static void segment_split_horz(struct segment *line, struct segment *next, int32_t x)
451 {
452 assert(x > line->x_min && x < line->x_max);
453
454 *next = *line;
455 next->c -= line->a * (int64_t)x;
456 next->x_min = 0;
457 next->x_max -= x;
458 line->x_max = x;
459
460 line->flags &= ~SEGFLAG_EXACT_TOP;
461 next->flags &= ~SEGFLAG_EXACT_BOTTOM;
462 if (line->flags & SEGFLAG_UL_DR) {
463 int32_t tmp = line->flags;
464 line->flags = next->flags;
465 next->flags = tmp;
466 }
467 line->flags |= SEGFLAG_EXACT_RIGHT;
468 next->flags |= SEGFLAG_EXACT_LEFT;
469 }
470
segment_split_vert(struct segment * line,struct segment * next,int32_t y)471 static void segment_split_vert(struct segment *line, struct segment *next, int32_t y)
472 {
473 assert(y > line->y_min && y < line->y_max);
474
475 *next = *line;
476 next->c -= line->b * (int64_t)y;
477 next->y_min = 0;
478 next->y_max -= y;
479 line->y_max = y;
480
481 line->flags &= ~SEGFLAG_EXACT_LEFT;
482 next->flags &= ~SEGFLAG_EXACT_RIGHT;
483 if (line->flags & SEGFLAG_UL_DR) {
484 int32_t tmp = line->flags;
485 line->flags = next->flags;
486 next->flags = tmp;
487 }
488 line->flags |= SEGFLAG_EXACT_BOTTOM;
489 next->flags |= SEGFLAG_EXACT_TOP;
490 }
491
segment_check_left(const struct segment * line,int32_t x)492 static inline int segment_check_left(const struct segment *line, int32_t x)
493 {
494 if (line->flags & SEGFLAG_EXACT_LEFT)
495 return line->x_min >= x;
496 int64_t cc = line->c - line->a * (int64_t)x -
497 line->b * (int64_t)(line->flags & SEGFLAG_UL_DR ? line->y_min : line->y_max);
498 if (line->a < 0)
499 cc = -cc;
500 return cc >= 0;
501 }
502
segment_check_right(const struct segment * line,int32_t x)503 static inline int segment_check_right(const struct segment *line, int32_t x)
504 {
505 if (line->flags & SEGFLAG_EXACT_RIGHT)
506 return line->x_max <= x;
507 int64_t cc = line->c - line->a * (int64_t)x -
508 line->b * (int64_t)(line->flags & SEGFLAG_UL_DR ? line->y_max : line->y_min);
509 if (line->a > 0)
510 cc = -cc;
511 return cc >= 0;
512 }
513
segment_check_top(const struct segment * line,int32_t y)514 static inline int segment_check_top(const struct segment *line, int32_t y)
515 {
516 if (line->flags & SEGFLAG_EXACT_TOP)
517 return line->y_min >= y;
518 int64_t cc = line->c - line->b * (int64_t)y -
519 line->a * (int64_t)(line->flags & SEGFLAG_UL_DR ? line->x_min : line->x_max);
520 if (line->b < 0)
521 cc = -cc;
522 return cc >= 0;
523 }
524
segment_check_bottom(const struct segment * line,int32_t y)525 static inline int segment_check_bottom(const struct segment *line, int32_t y)
526 {
527 if (line->flags & SEGFLAG_EXACT_BOTTOM)
528 return line->y_max <= y;
529 int64_t cc = line->c - line->b * (int64_t)y -
530 line->a * (int64_t)(line->flags & SEGFLAG_UL_DR ? line->x_max : line->x_min);
531 if (line->b > 0)
532 cc = -cc;
533 return cc >= 0;
534 }
535
536 /**
537 * \brief Split list of segments horizontally
538 * \param src in: input array, can coincide with *dst0 or *dst1
539 * \param n_src in: input array size
540 * \param dst0, dst1 out: pointers to output arrays of at least n_src size
541 * \param x in: split coordinate
542 * \return winding difference between bottom-split and bottom-left points
543 */
polyline_split_horz(const struct segment * src,size_t n_src,struct segment ** dst0,struct segment ** dst1,int32_t x)544 static int polyline_split_horz(const struct segment *src, size_t n_src,
545 struct segment **dst0, struct segment **dst1, int32_t x)
546 {
547 int winding = 0;
548 const struct segment *end = src + n_src;
549 for (; src != end; ++src) {
550 int delta = 0;
551 if (!src->y_min && (src->flags & SEGFLAG_EXACT_TOP))
552 delta = src->a < 0 ? 1 : -1;
553 if (segment_check_right(src, x)) {
554 winding += delta;
555 if (src->x_min >= x)
556 continue;
557 **dst0 = *src;
558 (*dst0)->x_max = FFMIN((*dst0)->x_max, x);
559 ++(*dst0);
560 continue;
561 }
562 if (segment_check_left(src, x)) {
563 **dst1 = *src;
564 segment_move_x(*dst1, x);
565 ++(*dst1);
566 continue;
567 }
568 if (src->flags & SEGFLAG_UL_DR)
569 winding += delta;
570 **dst0 = *src;
571 segment_split_horz(*dst0, *dst1, x);
572 ++(*dst0);
573 ++(*dst1);
574 }
575 return winding;
576 }
577
578 /**
579 * \brief Split list of segments vertically
580 */
polyline_split_vert(const struct segment * src,size_t n_src,struct segment ** dst0,struct segment ** dst1,int32_t y)581 static int polyline_split_vert(const struct segment *src, size_t n_src,
582 struct segment **dst0, struct segment **dst1, int32_t y)
583 {
584 int winding = 0;
585 const struct segment *end = src + n_src;
586 for (; src != end; ++src) {
587 int delta = 0;
588 if (!src->x_min && (src->flags & SEGFLAG_EXACT_LEFT))
589 delta = src->b < 0 ? 1 : -1;
590 if (segment_check_bottom(src, y)) {
591 winding += delta;
592 if (src->y_min >= y)
593 continue;
594 **dst0 = *src;
595 (*dst0)->y_max = (*dst0)->y_max < y ? (*dst0)->y_max : y;
596 ++(*dst0);
597 continue;
598 }
599 if (segment_check_top(src, y)) {
600 **dst1 = *src;
601 segment_move_y(*dst1, y);
602 ++(*dst1);
603 continue;
604 }
605 if (src->flags & SEGFLAG_UL_DR)
606 winding += delta;
607 **dst0 = *src;
608 segment_split_vert(*dst0, *dst1, y);
609 ++(*dst0);
610 ++(*dst1);
611 }
612 return winding;
613 }
614
615
rasterizer_fill_solid(const BitmapEngine * engine,uint8_t * buf,int width,int height,ptrdiff_t stride,int set)616 static inline void rasterizer_fill_solid(const BitmapEngine *engine,
617 uint8_t *buf, int width, int height, ptrdiff_t stride,
618 int set)
619 {
620 assert(!(width & ((1 << engine->tile_order) - 1)));
621 assert(!(height & ((1 << engine->tile_order) - 1)));
622
623 int i, j;
624 ptrdiff_t step = 1 << engine->tile_order;
625 ptrdiff_t tile_stride = stride * (1 << engine->tile_order);
626 width >>= engine->tile_order;
627 height >>= engine->tile_order;
628 for (j = 0; j < height; ++j) {
629 for (i = 0; i < width; ++i)
630 engine->fill_solid(buf + i * step, stride, set);
631 buf += tile_stride;
632 }
633 }
634
rasterizer_fill_halfplane(const BitmapEngine * engine,uint8_t * buf,int width,int height,ptrdiff_t stride,int32_t a,int32_t b,int64_t c,int32_t scale)635 static inline void rasterizer_fill_halfplane(const BitmapEngine *engine,
636 uint8_t *buf, int width, int height, ptrdiff_t stride,
637 int32_t a, int32_t b, int64_t c, int32_t scale)
638 {
639 assert(!(width & ((1 << engine->tile_order) - 1)));
640 assert(!(height & ((1 << engine->tile_order) - 1)));
641 if (width == 1 << engine->tile_order && height == 1 << engine->tile_order) {
642 engine->fill_halfplane(buf, stride, a, b, c, scale);
643 return;
644 }
645
646 uint32_t abs_a = a < 0 ? -a : a;
647 uint32_t abs_b = b < 0 ? -b : b;
648 int64_t size = (int64_t)(abs_a + abs_b) << (engine->tile_order + 5);
649 int64_t offs = ((int64_t)a + b) * (1 << (engine->tile_order + 5));
650
651 int i, j;
652 ptrdiff_t step = 1 << engine->tile_order;
653 ptrdiff_t tile_stride = stride * (1 << engine->tile_order);
654 width >>= engine->tile_order;
655 height >>= engine->tile_order;
656 for (j = 0; j < height; ++j) {
657 for (i = 0; i < width; ++i) {
658 int64_t cc = c - (a * (int64_t)i + b * (int64_t)j) * (1 << (engine->tile_order + 6));
659 int64_t offs_c = offs - cc;
660 int64_t abs_c = offs_c < 0 ? -offs_c : offs_c;
661 if (abs_c < size)
662 engine->fill_halfplane(buf + i * step, stride, a, b, cc, scale);
663 else
664 engine->fill_solid(buf + i * step, stride,
665 ((uint32_t)(offs_c >> 32) ^ scale) & 0x80000000);
666 }
667 buf += tile_stride;
668 }
669 }
670
671 /**
672 * \brief Main quad-tree filling function
673 * \param index index (0 or 1) of the input segment buffer (rst->linebuf)
674 * \param offs current offset from the beginning of the buffer
675 * \param winding bottom-left winding value
676 * \return zero on error
677 * Rasterizes (possibly recursive) one quad-tree level.
678 * Truncates used input buffer.
679 */
rasterizer_fill_level(const BitmapEngine * engine,RasterizerData * rst,uint8_t * buf,int width,int height,ptrdiff_t stride,int index,size_t offs,int winding)680 static int rasterizer_fill_level(const BitmapEngine *engine, RasterizerData *rst,
681 uint8_t *buf, int width, int height, ptrdiff_t stride,
682 int index, size_t offs, int winding)
683 {
684 assert(width > 0 && height > 0);
685 assert((unsigned)index < 2u && offs <= rst->size[index]);
686 assert(!(width & ((1 << engine->tile_order) - 1)));
687 assert(!(height & ((1 << engine->tile_order) - 1)));
688
689 size_t n = rst->size[index] - offs;
690 struct segment *line = rst->linebuf[index] + offs;
691 if (!n) {
692 rasterizer_fill_solid(engine, buf, width, height, stride, winding);
693 return 1;
694 }
695 if (n == 1) {
696 static const int test = SEGFLAG_UL_DR | SEGFLAG_EXACT_LEFT;
697 if (((line->flags & test) != test) == !(line->flags & SEGFLAG_DN))
698 winding++;
699
700 int flag = 0;
701 if (winding)
702 flag ^= 1;
703 if (winding - 1)
704 flag ^= 3;
705 if (flag & 1)
706 rasterizer_fill_halfplane(engine, buf, width, height, stride,
707 line->a, line->b, line->c,
708 flag & 2 ? -line->scale : line->scale);
709 else
710 rasterizer_fill_solid(engine, buf, width, height, stride, flag & 2);
711 rst->size[index] = offs;
712 return 1;
713 }
714 if (width == 1 << engine->tile_order && height == 1 << engine->tile_order) {
715 engine->fill_generic(buf, stride, line, rst->size[index] - offs, winding);
716 rst->size[index] = offs;
717 return 1;
718 }
719
720 size_t offs1 = rst->size[index ^ 1];
721 if (!check_capacity(rst, index ^ 1, n))
722 return 0;
723 struct segment *dst0 = line;
724 struct segment *dst1 = rst->linebuf[index ^ 1] + offs1;
725
726 int winding1 = winding;
727 uint8_t *buf1 = buf;
728 int width1 = width;
729 int height1 = height;
730 if (width > height) {
731 width = 1 << ilog2(width - 1);
732 width1 -= width;
733 buf1 += width;
734 winding1 += polyline_split_horz(line, n, &dst0, &dst1, (int32_t)width << 6);
735 } else {
736 height = 1 << ilog2(height - 1);
737 height1 -= height;
738 buf1 += height * stride;
739 winding1 += polyline_split_vert(line, n, &dst0, &dst1, (int32_t)height << 6);
740 }
741 rst->size[index ^ 0] = dst0 - rst->linebuf[index ^ 0];
742 rst->size[index ^ 1] = dst1 - rst->linebuf[index ^ 1];
743
744 if (!rasterizer_fill_level(engine, rst, buf, width, height, stride, index ^ 0, offs, winding))
745 return 0;
746 assert(rst->size[index ^ 0] == offs);
747 if (!rasterizer_fill_level(engine, rst, buf1, width1, height1, stride, index ^ 1, offs1, winding1))
748 return 0;
749 assert(rst->size[index ^ 1] == offs1);
750 return 1;
751 }
752
rasterizer_fill(const BitmapEngine * engine,RasterizerData * rst,uint8_t * buf,int x0,int y0,int width,int height,ptrdiff_t stride)753 int rasterizer_fill(const BitmapEngine *engine, RasterizerData *rst,
754 uint8_t *buf, int x0, int y0, int width, int height, ptrdiff_t stride)
755 {
756 assert(width > 0 && height > 0);
757 assert(!(width & ((1 << engine->tile_order) - 1)));
758 assert(!(height & ((1 << engine->tile_order) - 1)));
759 x0 *= 1 << 6; y0 *= 1 << 6;
760
761 size_t n = rst->size[0];
762 struct segment *line = rst->linebuf[0];
763 struct segment *end = line + n;
764 for (; line != end; ++line) {
765 line->x_min -= x0;
766 line->x_max -= x0;
767 line->y_min -= y0;
768 line->y_max -= y0;
769 line->c -= line->a * (int64_t)x0 + line->b * (int64_t)y0;
770 }
771 rst->x_min -= x0;
772 rst->x_max -= x0;
773 rst->y_min -= y0;
774 rst->y_max -= y0;
775
776 int index = 0;
777 int winding = 0;
778 if (!check_capacity(rst, 1, rst->size[0]))
779 return 0;
780 int32_t size_x = (int32_t)width << 6;
781 int32_t size_y = (int32_t)height << 6;
782 if (rst->x_max >= size_x) {
783 struct segment *dst0 = rst->linebuf[index];
784 struct segment *dst1 = rst->linebuf[index ^ 1];
785 polyline_split_horz(rst->linebuf[index], n, &dst0, &dst1, size_x);
786 n = dst0 - rst->linebuf[index];
787 }
788 if (rst->y_max >= size_y) {
789 struct segment *dst0 = rst->linebuf[index];
790 struct segment *dst1 = rst->linebuf[index ^ 1];
791 polyline_split_vert(rst->linebuf[index], n, &dst0, &dst1, size_y);
792 n = dst0 - rst->linebuf[index];
793 }
794 if (rst->x_min <= 0) {
795 struct segment *dst0 = rst->linebuf[index];
796 struct segment *dst1 = rst->linebuf[index ^ 1];
797 polyline_split_horz(rst->linebuf[index], n, &dst0, &dst1, 0);
798 index ^= 1;
799 n = dst1 - rst->linebuf[index];
800 }
801 if (rst->y_min <= 0) {
802 struct segment *dst0 = rst->linebuf[index];
803 struct segment *dst1 = rst->linebuf[index ^ 1];
804 winding = polyline_split_vert(rst->linebuf[index], n, &dst0, &dst1, 0);
805 index ^= 1;
806 n = dst1 - rst->linebuf[index];
807 }
808 rst->size[index] = n;
809 rst->size[index ^ 1] = 0;
810 return rasterizer_fill_level(engine, rst, buf, width, height, stride,
811 index, 0, winding);
812 }
813