granicus.if.org Git - libass/blob - libass/ass_rasterizer.c

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