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