Implement fast quad-tree rasterizer in C and x86/SSE2/AVX2

Signed-off-by: Rodger Combs <rodger.combs@gmail.com>

10 files changed, 2365 insertions, 16 deletions

diff --git a/libass/Makefile.am b/libass/Makefile.am
index 7b4a0bf..bc5345b 100644
--- a/libass/Makefile.am
+++ b/libass/Makefile.am
@@ -15,6 +15,9 @@ yasm_verbose_0 = @echo "  YASM    " $@;
 
 SRC_INTEL = x86/blend_bitmaps.asm x86/cpuid.asm x86/blend_bitmaps.h x86/cpuid.h
 SRC_INTEL64 = x86/be_blur.asm x86/be_blur.h
+SRC_INTEL_RASTERIZER = x86/rasterizer.asm x86/rasterizer.h
+
+SRC_RASTERIZER = ass_rasterizer.h ass_rasterizer.c ass_rasterizer_c.c
 
 lib_LTLIBRARIES = libass.la
 libass_la_SOURCES = ass.c ass_cache.c ass_font.c ass_fontconfig.c ass_render.c \
@@ -28,9 +31,16 @@ libass_la_SOURCES = ass.c ass_cache.c ass_font.c ass_fontconfig.c ass_render.c \
 libass_la_LDFLAGS = -no-undefined -version-info $(LIBASS_LT_CURRENT):$(LIBASS_LT_REVISION):$(LIBASS_LT_AGE)
 libass_la_LDFLAGS += -export-symbols $(srcdir)/libass.sym
 
+if RASTERIZER
+libass_la_SOURCES += $(SRC_RASTERIZER)
+endif
+
 if ASM
 if INTEL
 libass_la_SOURCES += $(SRC_INTEL)
+if RASTERIZER
+libass_la_SOURCES += $(SRC_INTEL_RASTERIZER)
+endif
 if X64
 libass_la_SOURCES += $(SRC_INTEL64)
 endif
diff --git a/libass/ass_bitmap.c b/libass/ass_bitmap.c
index cfaa16b..23b24ea 100644
--- a/libass/ass_bitmap.c
+++ b/libass/ass_bitmap.c
@@ -18,6 +18,8 @@
  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  */
 
+#include "config.h"
+
 #include <stdlib.h>
 #include <string.h>
 #include <math.h>
@@ -156,7 +158,63 @@ Bitmap *copy_bitmap(const Bitmap *src)
     return dst;
 }
 
-Bitmap *outline_to_bitmap(ASS_Library *library, FT_Library ftlib,
+#if CONFIG_RASTERIZER
+
+Bitmap *outline_to_bitmap(ASS_Renderer *render_priv,
+                          FT_Outline *outline, int bord)
+{
+    ASS_Rasterizer *rst = &render_priv->rasterizer;
+    if (!rasterizer_set_outline(rst, outline)) {
+        ass_msg(render_priv->library, MSGL_WARN, "Failed to process glyph outline!\n");
+        return NULL;
+    }
+
+    if (rst->x_min >= rst->x_max || rst->y_min >= rst->y_max) {
+        Bitmap *bm = alloc_bitmap(2 * bord, 2 * bord);
+        bm->left = bm->top = -bord;
+        return bm;
+    }
+
+    int x_min = rst->x_min >> 6;
+    int y_min = rst->y_min >> 6;
+    int x_max = (rst->x_max + 63) >> 6;
+    int y_max = (rst->y_max + 63) >> 6;
+    int w = x_max - x_min;
+    int h = y_max - y_min;
+
+    if (w * h > 8000000) {
+        ass_msg(render_priv->library, MSGL_WARN, "Glyph bounding box too large: %dx%dpx",
+                w, h);
+        return NULL;
+    }
+
+    int mask = (1 << rst->tile_order) - 1;
+    int tile_w = (w + 2 * bord + mask) & ~mask;
+    int tile_h = (h + 2 * bord + mask) & ~mask;
+    Bitmap *bm = alloc_bitmap(tile_w, tile_h);
+    bm->left = x_min - bord;
+    bm->top = -y_max - bord;
+
+    int offs = bord & ~mask;
+    int bord_h = tile_h - h - bord;
+    if (!rasterizer_fill(rst,
+            bm->buffer + offs * (bm->stride + 1),
+            x_min - bord + offs,
+            y_min - bord_h + (bord_h & ~mask),
+            ((w + bord + mask) & ~mask) - offs,
+            ((h + bord + mask) & ~mask) - offs,
+            bm->stride, 1)) {
+        ass_msg(render_priv->library, MSGL_WARN, "Failed to rasterize glyph!\n");
+        ass_free_bitmap(bm);
+        return NULL;
+    }
+
+    return bm;
+}
+
+#else
+
+Bitmap *outline_to_bitmap(ASS_Renderer *render_priv,
                           FT_Outline *outline, int bord)
 {
     Bitmap *bm;
@@ -186,7 +244,7 @@ Bitmap *outline_to_bitmap(ASS_Library *library, FT_Library ftlib,
     bbox.yMax >>= 6;
 
     if (w * h > 8000000) {
-        ass_msg(library, MSGL_WARN, "Glyph bounding box too large: %dx%dpx",
+        ass_msg(render_priv->library, MSGL_WARN, "Glyph bounding box too large: %dx%dpx",
                 w, h);
         return NULL;
     }
@@ -203,8 +261,8 @@ Bitmap *outline_to_bitmap(ASS_Library *library, FT_Library ftlib,
     bitmap.pixel_mode = FT_PIXEL_MODE_GRAY;
 
     // render into target bitmap
-    if ((error = FT_Outline_Get_Bitmap(ftlib, outline, &bitmap))) {
-        ass_msg(library, MSGL_WARN, "Failed to rasterize glyph: %d\n", error);
+    if ((error = FT_Outline_Get_Bitmap(render_priv->ftlibrary, outline, &bitmap))) {
+        ass_msg(render_priv->library, MSGL_WARN, "Failed to rasterize glyph: %d\n", error);
         ass_free_bitmap(bm);
         return NULL;
     }
@@ -212,6 +270,8 @@ Bitmap *outline_to_bitmap(ASS_Library *library, FT_Library ftlib,
     return bm;
 }
 
+#endif
+
 /**
  * \brief fix outline bitmap
  *
@@ -495,8 +555,7 @@ void be_blur_c(uint8_t *buf, intptr_t w,
     }
 }
 
-int outline_to_bitmap3(ASS_Library *library, ASS_SynthPriv *priv_blur,
-                       FT_Library ftlib, FT_Outline *outline, FT_Outline *border,
+int outline_to_bitmap3(ASS_Renderer *render_priv, FT_Outline *outline, FT_Outline *border,
                        Bitmap **bm_g, Bitmap **bm_o, Bitmap **bm_s,
                        int be, double blur_radius, FT_Vector shadow_offset,
                        int border_style, int border_visible)
@@ -513,12 +572,12 @@ int outline_to_bitmap3(ASS_Library *library, ASS_SynthPriv *priv_blur,
     *bm_g = *bm_o = *bm_s = 0;
 
     if (outline)
-        *bm_g = outline_to_bitmap(library, ftlib, outline, bord);
+        *bm_g = outline_to_bitmap(render_priv, outline, bord);
     if (!*bm_g)
         return 1;
 
     if (border) {
-        *bm_o = outline_to_bitmap(library, ftlib, border, bord);
+        *bm_o = outline_to_bitmap(render_priv, border, bord);
         if (!*bm_o) {
             return 1;
         }
diff --git a/libass/ass_bitmap.h b/libass/ass_bitmap.h
index b05e112..64b3466 100644
--- a/libass/ass_bitmap.h
+++ b/libass/ass_bitmap.h
@@ -48,7 +48,7 @@ typedef struct {
     unsigned char *buffer;      // h * stride buffer
 } Bitmap;
 
-Bitmap *outline_to_bitmap(ASS_Library *library, FT_Library ftlib,
+Bitmap *outline_to_bitmap(ASS_Renderer *render_priv,
                           FT_Outline *outline, int bord);
 
 Bitmap *alloc_bitmap(int w, int h);
@@ -62,8 +62,7 @@ Bitmap *alloc_bitmap(int w, int h);
  * \param be 1 = produces blurred bitmaps, 0 = normal bitmaps
  * \param border_visible whether border is visible if border_style is 3
  */
-int outline_to_bitmap3(ASS_Library *library, ASS_SynthPriv *priv_blur,
-                       FT_Library ftlib, FT_Outline *outline, FT_Outline *border,
+int outline_to_bitmap3(ASS_Renderer *render_priv, FT_Outline *outline, FT_Outline *border,
                        Bitmap **bm_g, Bitmap **bm_o, Bitmap **bm_s,
                        int be, double blur_radius, FT_Vector shadow_offset,
                        int border_style, int border_visible);
diff --git a/libass/ass_rasterizer.c b/libass/ass_rasterizer.c
new file mode 100644
index 0000000..8cdbfd0
--- /dev/null
+++ b/libass/ass_rasterizer.c
@@ -0,0 +1,788 @@
+/*
+ * Copyright (C) 2014 Vabishchevich Nikolay <vabnick@gmail.com>
+ *
+ * This file is part of libass.
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include "ass_utils.h"
+#include "ass_rasterizer.h"
+#include <assert.h>
+
+#ifdef _MSC_VER
+#include <intrin.h>
+#pragma intrinsic(_BitScanReverse)
+#endif
+
+
+
+static inline int ilog2(uint32_t n)  // XXX: different compilers
+{
+#ifdef __GNUC__
+    return __builtin_clz(n) ^ 31;
+#elif defined(_MSC_VER)
+    int res;
+    _BitScanReverse(&res, n);
+    return res;
+#else
+    int res = 0;
+    for (int ord = 16; ord; ord /= 2)
+        if (n >= ((uint32_t)1 << ord)) {
+            res += ord;
+            n >>= ord;
+        }
+    return res;
+#endif
+}
+
+
+void rasterizer_init(ASS_Rasterizer *rst)
+{
+    rst->linebuf[0] = rst->linebuf[1] = NULL;
+    rst->size[0] = rst->capacity[0] = 0;
+    rst->size[1] = rst->capacity[1] = 0;
+}
+
+/**
+ * \brief Ensure sufficient buffer size (allocate if necessary)
+ * \param index index (0 or 1) of the input segment buffer (rst->linebuf)
+ * \param delta requested size increase
+ * \return zero on error
+ */
+static inline int check_capacity(ASS_Rasterizer *rst, int index, size_t delta)
+{
+    delta += rst->size[index];
+    if (rst->capacity[index] >= delta)
+        return 1;
+
+    size_t capacity = FFMAX(2 * rst->capacity[index], 64);
+    while (capacity < delta)
+        capacity *= 2;
+    void *ptr = realloc(rst->linebuf[index], sizeof(struct segment) * capacity);
+    if (!ptr)
+        return 0;
+
+    rst->linebuf[index] = (struct segment *)ptr;
+    rst->capacity[index] = capacity;
+    return 1;
+}
+
+void rasterizer_done(ASS_Rasterizer *rst)
+{
+    free(rst->linebuf[0]);
+    free(rst->linebuf[1]);
+}
+
+
+typedef struct {
+    int32_t x, y;
+} OutlinePoint;
+
+// Helper struct for spline split decision
+typedef struct {
+    OutlinePoint r;
+    int64_t r2, er;
+} OutlineSegment;
+
+static inline void segment_init(OutlineSegment *seg,
+                                OutlinePoint beg, OutlinePoint end,
+                                int32_t outline_error)
+{
+    int32_t x = end.x - beg.x;
+    int32_t y = end.y - beg.y;
+    int32_t abs_x = x < 0 ? -x : x;
+    int32_t abs_y = y < 0 ? -y : y;
+
+    seg->r.x = x;
+    seg->r.y = y;
+    seg->r2 = x * (int64_t)x + y * (int64_t)y;
+    seg->er = outline_error * (int64_t)FFMAX(abs_x, abs_y);
+}
+
+static inline int segment_subdivide(const OutlineSegment *seg,
+                                    OutlinePoint beg, OutlinePoint pt)
+{
+    int32_t x = pt.x - beg.x;
+    int32_t y = pt.y - beg.y;
+    int64_t pdr = seg->r.x * (int64_t)x + seg->r.y * (int64_t)y;
+    int64_t pcr = seg->r.x * (int64_t)y - seg->r.y * (int64_t)x;
+    return pdr < -seg->er || pdr > seg->r2 + seg->er ||
+        (pcr < 0 ? -pcr : pcr) > seg->er;
+}
+
+/**
+ * \brief Add new segment to polyline
+ */
+static inline int add_line(ASS_Rasterizer *rst, OutlinePoint pt0, OutlinePoint pt1)
+{
+    int32_t x = pt1.x - pt0.x;
+    int32_t y = pt1.y - pt0.y;
+    if (!x && !y)
+        return 1;
+
+    if (!check_capacity(rst, 0, 1))
+        return 0;
+    struct segment *line = rst->linebuf[0] + rst->size[0];
+    ++rst->size[0];
+
+    line->flags = SEGFLAG_EXACT_LEFT | SEGFLAG_EXACT_RIGHT |
+                  SEGFLAG_EXACT_BOTTOM | SEGFLAG_EXACT_TOP;
+    if (x < 0)
+        line->flags ^= SEGFLAG_UR_DL;
+    if (y >= 0)
+        line->flags ^= SEGFLAG_UP | SEGFLAG_UR_DL;
+
+    line->x_min = FFMIN(pt0.x, pt1.x);
+    line->x_max = FFMAX(pt0.x, pt1.x);
+    line->y_min = FFMIN(pt0.y, pt1.y);
+    line->y_max = FFMAX(pt0.y, pt1.y);
+
+    line->a = y;
+    line->b = -x;
+    line->c = y * (int64_t)pt0.x - x * (int64_t)pt0.y;
+
+    // halfplane normalization
+    int32_t abs_x = x < 0 ? -x : x;
+    int32_t abs_y = y < 0 ? -y : y;
+    uint32_t max_ab = (abs_x > abs_y ? abs_x : abs_y);
+    int shift = 30 - ilog2(max_ab);
+    max_ab <<= shift + 1;
+    line->a <<= shift;
+    line->b <<= shift;
+    line->c <<= shift;
+    line->scale = (uint64_t)0x53333333 * (uint32_t)(max_ab * (uint64_t)max_ab >> 32) >> 32;
+    line->scale += 0x8810624D - (0xBBC6A7EF * (uint64_t)max_ab >> 32);
+    //line->scale = ((uint64_t)1 << 61) / max_ab;
+    return 1;
+}
+
+/**
+ * \brief Add quadratic spline to polyline
+ * Preforms recursive subdivision if necessary.
+ */
+static int add_quadratic(ASS_Rasterizer *rst,
+                         OutlinePoint pt0, OutlinePoint pt1, OutlinePoint pt2)
+{
+    OutlineSegment seg;
+    segment_init(&seg, pt0, pt2, rst->outline_error);
+    if (!segment_subdivide(&seg, pt0, pt1))
+        return add_line(rst, pt0, pt2);
+
+    OutlinePoint p01, p12, c;  // XXX: overflow?
+    p01.x = pt0.x + pt1.x;
+    p01.y = pt0.y + pt1.y;
+    p12.x = pt1.x + pt2.x;
+    p12.y = pt1.y + pt2.y;
+    c.x = (p01.x + p12.x + 2) >> 2;
+    c.y = (p01.y + p12.y + 2) >> 2;
+    p01.x >>= 1;
+    p01.y >>= 1;
+    p12.x >>= 1;
+    p12.y >>= 1;
+    return add_quadratic(rst, pt0, p01, c) && add_quadratic(rst, c, p12, pt2);
+}
+
+/**
+ * \brief Add cubic spline to polyline
+ * Preforms recursive subdivision if necessary.
+ */
+static int add_cubic(ASS_Rasterizer *rst,
+                     OutlinePoint pt0, OutlinePoint pt1, OutlinePoint pt2, OutlinePoint pt3)
+{
+    OutlineSegment seg;
+    segment_init(&seg, pt0, pt3, rst->outline_error);
+    if (!segment_subdivide(&seg, pt0, pt1) && !segment_subdivide(&seg, pt0, pt2))
+        return add_line(rst, pt0, pt3);
+
+    OutlinePoint p01, p12, p23, p012, p123, c;  // XXX: overflow?
+    p01.x = pt0.x + pt1.x;
+    p01.y = pt0.y + pt1.y;
+    p12.x = pt1.x + pt2.x + 2;
+    p12.y = pt1.y + pt2.y + 2;
+    p23.x = pt2.x + pt3.x;
+    p23.y = pt2.y + pt3.y;
+    p012.x = p01.x + p12.x;
+    p012.y = p01.y + p12.y;
+    p123.x = p12.x + p23.x;
+    p123.y = p12.y + p23.y;
+    c.x = (p012.x + p123.x - 1) >> 3;
+    c.y = (p012.y + p123.y - 1) >> 3;
+    p01.x >>= 1;
+    p01.y >>= 1;
+    p012.x >>= 2;
+    p012.y >>= 2;
+    p123.x >>= 2;
+    p123.y >>= 2;
+    p23.x >>= 1;
+    p23.y >>= 1;
+    return add_cubic(rst, pt0, p01, p012, c) && add_cubic(rst, c, p123, p23, pt3);
+}
+
+
+int rasterizer_set_outline(ASS_Rasterizer *rst, const FT_Outline *path)
+{
+    enum Status {
+        S_ON, S_Q, S_C1, S_C2
+    };
+
+    int i, j = 0;
+    rst->size[0] = 0;
+    for (i = 0; i < path->n_contours; ++i) {
+        OutlinePoint start, p[4];
+        int process_end = 1;
+        enum Status st;
+
+        int last = path->contours[i];
+        switch (FT_CURVE_TAG(path->tags[j])) {
+        case FT_CURVE_TAG_ON:
+            p[0].x = path->points[j].x;
+            p[0].y = path->points[j].y;
+            start = p[0];
+            st = S_ON;
+            break;
+
+        case FT_CURVE_TAG_CONIC:
+            switch (FT_CURVE_TAG(path->tags[last])) {
+            case FT_CURVE_TAG_ON:
+                p[0].x = path->points[last].x;
+                p[0].y = path->points[last].y;
+                p[1].x = path->points[j].x;
+                p[1].y = path->points[j].y;
+                process_end = 0;
+                st = S_Q;
+                break;
+
+            case FT_CURVE_TAG_CONIC:
+                p[1].x = path->points[j].x;
+                p[1].y = path->points[j].y;
+                p[0].x = (p[1].x + path->points[last].x) >> 1;
+                p[0].y = (p[1].y + path->points[last].y) >> 1;
+                start = p[0];
+                st = S_Q;
+                break;
+
+            default:
+                return 0;
+            }
+            break;
+
+        default:
+            return 0;
+        }
+
+        for (j++; j <= last; ++j)
+            switch (FT_CURVE_TAG(path->tags[j])) {
+            case FT_CURVE_TAG_ON:
+                switch (st) {
+                case S_ON:
+                    p[1].x = path->points[j].x;
+                    p[1].y = path->points[j].y;
+                    if (!add_line(rst, p[0], p[1]))
+                        return 0;
+                    p[0] = p[1];
+                    break;
+
+                case S_Q:
+                    p[2].x = path->points[j].x;
+                    p[2].y = path->points[j].y;
+                    if (!add_quadratic(rst, p[0], p[1], p[2]))
+                        return 0;
+                    p[0] = p[2];
+                    st = S_ON;
+                    break;
+
+                case S_C2:
+                    p[3].x = path->points[j].x;
+                    p[3].y = path->points[j].y;
+                    if (!add_cubic(rst, p[0], p[1], p[2], p[3]))
+                        return 0;
+                    p[0] = p[3];
+                    st = S_ON;
+                    break;
+
+                default:
+                    return 0;
+                }
+                break;
+
+            case FT_CURVE_TAG_CONIC:
+                switch (st) {
+                case S_ON:
+                    p[1].x = path->points[j].x;
+                    p[1].y = path->points[j].y;
+                    st = S_Q;
+                    break;
+
+                case S_Q:
+                    p[3].x = path->points[j].x;
+                    p[3].y = path->points[j].y;
+                    p[2].x = (p[1].x + p[3].x) >> 1;
+                    p[2].y = (p[1].y + p[3].y) >> 1;
+                    if (!add_quadratic(rst, p[0], p[1], p[2]))
+                        return 0;
+                    p[0] = p[2];
+                    p[1] = p[3];
+                    break;
+
+                default:
+                    return 0;
+                }
+                break;
+
+            case FT_CURVE_TAG_CUBIC:
+                switch (st) {
+                case S_ON:
+                    p[1].x = path->points[j].x;
+                    p[1].y = path->points[j].y;
+                    st = S_C1;
+                    break;
+
+                case S_C1:
+                    p[2].x = path->points[j].x;
+                    p[2].y = path->points[j].y;
+                    st = S_C2;
+                    break;
+
+                default:
+                    return 0;
+                }
+                break;
+
+            default:
+                return 0;
+            }
+
+        if (process_end)
+            switch (st) {
+            case S_ON:
+                if (!add_line(rst, p[0], start))
+                    return 0;
+                break;
+
+            case S_Q:
+                if (!add_quadratic(rst, p[0], p[1], start))
+                    return 0;
+                break;
+
+            case S_C2:
+                if (!add_cubic(rst, p[0], p[1], p[2], start))
+                    return 0;
+                break;
+
+            default:
+                return 0;
+            }
+    }
+
+    size_t k;
+    rst->x_min = rst->y_min = 0x7FFFFFFF;
+    rst->x_max = rst->y_max = 0x80000000;
+    for (k = 0; k < rst->size[0]; ++k) {
+        rst->x_min = FFMIN(rst->x_min, rst->linebuf[0][k].x_min);
+        rst->x_max = FFMAX(rst->x_max, rst->linebuf[0][k].x_max);
+        rst->y_min = FFMIN(rst->y_min, rst->linebuf[0][k].y_min);
+        rst->y_max = FFMAX(rst->y_max, rst->linebuf[0][k].y_max);
+    }
+    return 1;
+}
+
+
+static void segment_move_x(struct segment *line, int32_t x)
+{
+    line->x_min -= x;
+    line->x_max -= x;
+    line->x_min = FFMAX(line->x_min, 0);
+    line->c -= line->a * (int64_t)x;
+
+    static const int test = SEGFLAG_EXACT_LEFT | SEGFLAG_UR_DL;
+    if (!line->x_min && (line->flags & test) == test)
+        line->flags &= ~SEGFLAG_EXACT_BOTTOM;
+}
+
+static void segment_move_y(struct segment *line, int32_t y)
+{
+    line->y_min -= y;
+    line->y_max -= y;
+    line->y_min = FFMAX(line->y_min, 0);
+    line->c -= line->b * (int64_t)y;
+
+    static const int test = SEGFLAG_EXACT_BOTTOM | SEGFLAG_UR_DL;
+    if (!line->y_min && (line->flags & test) == test)
+        line->flags &= ~SEGFLAG_EXACT_LEFT;
+}
+
+static void segment_split_horz(struct segment *line, struct segment *next, int32_t x)
+{
+    assert(x > line->x_min && x < line->x_max);
+
+    *next = *line;
+    next->c -= line->a * (int64_t)x;
+    next->x_min = 0;
+    next->x_max -= x;
+    line->x_max = x;
+
+    line->flags &= ~SEGFLAG_EXACT_BOTTOM;
+    next->flags &= ~SEGFLAG_EXACT_TOP;
+    if (line->flags & SEGFLAG_UR_DL) {
+        int32_t tmp = line->flags;
+        line->flags = next->flags;
+        next->flags = tmp;
+    }
+    line->flags |= SEGFLAG_EXACT_RIGHT;
+    next->flags |= SEGFLAG_EXACT_LEFT;
+}
+
+static void segment_split_vert(struct segment *line, struct segment *next, int32_t y)
+{
+    assert(y > line->y_min && y < line->y_max);
+
+    *next = *line;
+    next->c -= line->b * (int64_t)y;
+    next->y_min = 0;
+    next->y_max -= y;
+    line->y_max = y;
+
+    line->flags &= ~SEGFLAG_EXACT_LEFT;
+    next->flags &= ~SEGFLAG_EXACT_RIGHT;
+    if (line->flags & SEGFLAG_UR_DL) {
+        int32_t tmp = line->flags;
+        line->flags = next->flags;
+        next->flags = tmp;
+    }
+    line->flags |= SEGFLAG_EXACT_TOP;
+    next->flags |= SEGFLAG_EXACT_BOTTOM;
+}
+
+static inline int segment_check_right(const struct segment *line, int32_t x)
+{
+    if (line->flags & SEGFLAG_EXACT_RIGHT)
+        return line->x_max <= x;
+    int64_t cc = line->c - line->a * (int64_t)x -
+        line->b * (int64_t)(line->flags & SEGFLAG_UR_DL ? line->y_max : line->y_min);
+    if (line->a > 0)
+        cc = -cc;
+    return cc >= 0;
+}
+
+static inline int segment_check_left(const struct segment *line, int32_t x)
+{
+    if (line->flags & SEGFLAG_EXACT_LEFT)
+        return line->x_min >= x;
+    int64_t cc = line->c - line->a * (int64_t)x -
+        line->b * (int64_t)(line->flags & SEGFLAG_UR_DL ? line->y_min : line->y_max);
+    if (line->a < 0)
+        cc = -cc;
+    return cc >= 0;
+}
+
+static inline int segment_check_top(const struct segment *line, int32_t y)
+{
+    if (line->flags & SEGFLAG_EXACT_TOP)
+        return line->y_max <= y;
+    int64_t cc = line->c - line->b * (int64_t)y -
+        line->a * (int64_t)(line->flags & SEGFLAG_UR_DL ? line->x_max : line->x_min);
+    if (line->b > 0)
+        cc = -cc;
+    return cc >= 0;
+}
+
+static inline int segment_check_bottom(const struct segment *line, int32_t y)
+{
+    if (line->flags & SEGFLAG_EXACT_BOTTOM)
+        return line->y_min >= y;
+    int64_t cc = line->c - line->b * (int64_t)y -
+        line->a * (int64_t)(line->flags & SEGFLAG_UR_DL ? line->x_min : line->x_max);
+    if (line->b < 0)
+        cc = -cc;
+    return cc >= 0;
+}
+
+/**
+ * \brief Split list of segments horizontally
+ * \param src in: input array, can coincide with *dst0 or *dst1
+ * \param n_src in: input array size
+ * \param dst0, dst1 out: pointers to output arrays of at least n_src size
+ * \param x in: split coordinate
+ * \return winding difference between bottom-split and bottom-left points
+ */
+static int polyline_split_horz(const struct segment *src, size_t n_src,
+                               struct segment **dst0, struct segment **dst1, int32_t x)
+{
+    int winding = 0;
+    const struct segment *end = src + n_src;
+    for (; src != end; ++src) {
+        int delta = 0;
+        if (!src->y_min && (src->flags & SEGFLAG_EXACT_BOTTOM))
+            delta = src->a < 0 ? 1 : -1;
+        if (segment_check_right(src, x)) {
+            winding += delta;
+            if (src->x_min >= x)
+                continue;
+            **dst0 = *src;
+            (*dst0)->x_max = FFMIN((*dst0)->x_max, x);
+            ++(*dst0);
+            continue;
+        }
+        if (segment_check_left(src, x)) {
+            **dst1 = *src;
+            segment_move_x(*dst1, x);
+            ++(*dst1);
+            continue;
+        }
+        if (src->flags & SEGFLAG_UR_DL)
+            winding += delta;
+        **dst0 = *src;
+        segment_split_horz(*dst0, *dst1, x);
+        ++(*dst0);
+        ++(*dst1);
+    }
+    return winding;
+}
+
+/**
+ * \brief Split list of segments vertically
+ */
+static int polyline_split_vert(const struct segment *src, size_t n_src,
+                               struct segment **dst0, struct segment **dst1, int32_t y)
+{
+    int winding = 0;
+    const struct segment *end = src + n_src;
+    for (; src != end; ++src) {
+        int delta = 0;
+        if (!src->x_min && (src->flags & SEGFLAG_EXACT_LEFT))
+            delta = src->b < 0 ? 1 : -1;
+        if (segment_check_top(src, y)) {
+            winding += delta;
+            if (src->y_min >= y)
+                continue;
+            **dst0 = *src;
+            (*dst0)->y_max = (*dst0)->y_max < y ? (*dst0)->y_max : y;
+            ++(*dst0);
+            continue;
+        }
+        if (segment_check_bottom(src, y)) {
+            **dst1 = *src;
+            segment_move_y(*dst1, y);
+            ++(*dst1);
+            continue;
+        }
+        if (src->flags & SEGFLAG_UR_DL)
+            winding += delta;
+        **dst0 = *src;
+        segment_split_vert(*dst0, *dst1, y);
+        ++(*dst0);
+        ++(*dst1);
+    }
+    return winding;
+}
+
+
+static inline void rasterizer_fill_solid(ASS_Rasterizer *rst,
+                                         uint8_t *buf, int width, int height, ptrdiff_t stride)
+{
+    assert(!(width  & ((1 << rst->tile_order) - 1)));
+    assert(!(height & ((1 << rst->tile_order) - 1)));
+
+    int i, j;
+    ptrdiff_t step = 1 << rst->tile_order;
+    ptrdiff_t tile_stride = stride << rst->tile_order;
+    width  >>= rst->tile_order;
+    height >>= rst->tile_order;
+    for (j = 0; j < height; ++j) {
+        for (i = 0; i < width; ++i)
+            rst->fill_solid(buf + i * step, stride);
+        buf += tile_stride;
+    }
+}
+
+static inline void rasterizer_fill_halfplane(ASS_Rasterizer *rst,
+                                             uint8_t *buf, int width, int height, ptrdiff_t stride,
+                                             int32_t a, int32_t b, int64_t c, int32_t scale)
+{
+    assert(!(width  & ((1 << rst->tile_order) - 1)));
+    assert(!(height & ((1 << rst->tile_order) - 1)));
+    if (width == 1 << rst->tile_order && height == 1 << rst->tile_order) {
+        rst->fill_halfplane(buf, stride, a, b, c, scale);
+        return;
+    }
+
+    uint32_t abs_a = a < 0 ? -a : a;
+    uint32_t abs_b = b < 0 ? -b : b;
+    int64_t size = (int64_t)(abs_a + abs_b) << (rst->tile_order + 5);
+    int64_t offs = ((int64_t)a + b) << (rst->tile_order + 5);
+
+    int i, j;
+    ptrdiff_t step = 1 << rst->tile_order;
+    ptrdiff_t tile_stride = stride << rst->tile_order;
+    width  >>= rst->tile_order;
+    height >>= rst->tile_order;
+    for (j = 0; j < height; ++j) {
+        for (i = 0; i < width; ++i) {
+            int64_t cc = c - ((a * (int64_t)i + b * (int64_t)j) << (rst->tile_order + 6));
+            int64_t offs_c = offs - cc;
+            int64_t abs_c = offs_c < 0 ? -offs_c : offs_c;
+            if (abs_c < size)
+                rst->fill_halfplane(buf + i * step, stride, a, b, cc, scale);
+            else if (((int32_t)(offs_c >> 32) ^ scale) & (1 << 31))
+                rst->fill_solid(buf + i * step, stride);
+        }
+        buf += tile_stride;
+    }
+}
+
+/**
+ * \brief Main quad-tree filling function
+ * \param index index (0 or 1) of the input segment buffer (rst->linebuf)
+ * \param offs current offset from the beginning of the buffer
+ * \param winding bottom-left winding value
+ * \return zero on error
+ * Rasterizes (possibly recursive) one quad-tree level.
+ * Truncates used input buffer.
+ */
+static int rasterizer_fill_level(ASS_Rasterizer *rst,
+    uint8_t *buf, int width, int height, ptrdiff_t stride, int index, size_t offs, int winding)
+{
+    assert(width > 0 && height > 0);
+    assert((unsigned)index < 2u && offs <= rst->size[index]);
+    assert(!(width  & ((1 << rst->tile_order) - 1)));
+    assert(!(height & ((1 << rst->tile_order) - 1)));
+
+    size_t n = rst->size[index] - offs;
+    struct segment *line = rst->linebuf[index] + offs;
+    if (!n) {
+        if (winding)
+            rasterizer_fill_solid(rst, buf, width, height, stride);
+        return 1;
+    }
+    if (n == 1) {
+        int flag = 0;
+        if (line->c < 0)winding++;
+        if (winding)
+            flag ^= 1;
+        if (winding - 1)
+            flag ^= 3;
+        if (flag & 1)
+            rasterizer_fill_halfplane(rst, buf, width, height, stride,
+                                      line->a, line->b, line->c,
+                                      flag & 2 ? -line->scale : line->scale);
+        else if (flag & 2)
+            rasterizer_fill_solid(rst, buf, width, height, stride);
+        rst->size[index] = offs;
+        return 1;
+    }
+    if (width == 1 << rst->tile_order && height == 1 << rst->tile_order) {
+        rst->fill_generic(buf, stride, line, rst->size[index] - offs, winding);
+        rst->size[index] = offs;
+        return 1;
+    }
+
+    size_t offs1 = rst->size[index ^ 1];
+    if (!check_capacity(rst, index ^ 1, n))
+        return 0;
+    struct segment *dst0 = line;
+    struct segment *dst1 = rst->linebuf[index ^ 1] + offs1;
+
+    int winding1 = winding;
+    uint8_t *buf1 = buf;
+    int width1  = width;
+    int height1 = height;
+    if (width > height) {
+        width = 1 << ilog2(width - 1);
+        width1 -= width;
+        buf1 += width;
+        winding1 += polyline_split_horz(line, n, &dst0, &dst1, (int32_t)width << 6);
+    } else {
+        height = 1 << ilog2(height - 1);
+        height1 -= height;
+        buf1 += height * stride;
+        winding1 += polyline_split_vert(line, n, &dst0, &dst1, (int32_t)height << 6);
+    }
+    rst->size[index ^ 0] = dst0 - rst->linebuf[index ^ 0];
+    rst->size[index ^ 1] = dst1 - rst->linebuf[index ^ 1];
+
+    if (!rasterizer_fill_level(rst, buf,  width,  height,  stride, index ^ 0, offs,  winding))
+        return 0;
+    assert(rst->size[index ^ 0] == offs);
+    if (!rasterizer_fill_level(rst, buf1, width1, height1, stride, index ^ 1, offs1, winding1))
+        return 0;
+    assert(rst->size[index ^ 1] == offs1);
+    return 1;
+}
+
+int rasterizer_fill(ASS_Rasterizer *rst,
+                    uint8_t *buf, int x0, int y0, int width, int height, ptrdiff_t stride,
+                    int vert_flip)
+{
+    assert(width > 0 && height > 0);
+    assert(!(width  & ((1 << rst->tile_order) - 1)));
+    assert(!(height & ((1 << rst->tile_order) - 1)));
+    x0 <<= 6;  y0 <<= 6;
+
+    if (vert_flip) {
+        buf += (height - 1) * stride;
+        stride = -stride;
+    }
+
+    size_t n = rst->size[0];
+    struct segment *line = rst->linebuf[0];
+    struct segment *end = line + n;
+    for (; line != end; ++line) {
+        line->x_min -= x0;
+        line->x_max -= x0;
+        line->y_min -= y0;
+        line->y_max -= y0;
+        line->c -= line->a * (int64_t)x0 + line->b * (int64_t)y0;
+    }
+    rst->x_min -= x0;
+    rst->x_max -= x0;
+    rst->y_min -= y0;
+    rst->y_max -= y0;
+
+    int index = 0;
+    int winding = 0;
+    if (!check_capacity(rst, 1, rst->size[0]))
+        return 0;
+    int32_t size_x = (int32_t)width << 6;
+    int32_t size_y = (int32_t)height << 6;
+    if (rst->x_max >= size_x) {
+        struct segment *dst0 = rst->linebuf[index];
+        struct segment *dst1 = rst->linebuf[index ^ 1];
+        polyline_split_horz(rst->linebuf[index], n, &dst0, &dst1, size_x);
+        n = dst0 - rst->linebuf[index];
+    }
+    if (rst->y_max >= size_y) {
+        struct segment *dst0 = rst->linebuf[index];
+        struct segment *dst1 = rst->linebuf[index ^ 1];
+        polyline_split_vert(rst->linebuf[index], n, &dst0, &dst1, size_y);
+        n = dst0 - rst->linebuf[index];
+    }
+    if (rst->x_min <= 0) {
+        struct segment *dst0 = rst->linebuf[index];
+        struct segment *dst1 = rst->