code.vuplus.com Git - vuplus_xbmc/blob - lib/libass/libass/ass_render.c

   1 /*
   2  * Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@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
  21 #include <assert.h>
  22 #include <math.h>
  23
  24 #include "ass_render.h"
  25 #include "ass_parse.h"
  26 #include "ass_shaper.h"
  27
  28 #define MAX_GLYPHS_INITIAL 1024
  29 #define MAX_LINES_INITIAL 64
  30 #define SUBPIXEL_MASK 63
  31 #define SUBPIXEL_ACCURACY 7
  32
  33 ASS_Renderer *ass_renderer_init(ASS_Library *library)
  34 {
  35     int error;
  36     FT_Library ft;
  37     ASS_Renderer *priv = 0;
  38     int vmajor, vminor, vpatch;
  39
  40     error = FT_Init_FreeType(&ft);
  41     if (error) {
  42         ass_msg(library, MSGL_FATAL, "%s failed", "FT_Init_FreeType");
  43         goto ass_init_exit;
  44     }
  45
  46     FT_Library_Version(ft, &vmajor, &vminor, &vpatch);
  47     ass_msg(library, MSGL_V, "Raster: FreeType %d.%d.%d",
  48            vmajor, vminor, vpatch);
  49
  50     priv = calloc(1, sizeof(ASS_Renderer));
  51     if (!priv) {
  52         FT_Done_FreeType(ft);
  53         goto ass_init_exit;
  54     }
  55
  56     priv->synth_priv = ass_synth_init(BLUR_MAX_RADIUS);
  57
  58     priv->library = library;
  59     priv->ftlibrary = ft;
  60     // images_root and related stuff is zero-filled in calloc
  61
  62     priv->cache.font_cache = ass_font_cache_create();
  63     priv->cache.bitmap_cache = ass_bitmap_cache_create();
  64     priv->cache.composite_cache = ass_composite_cache_create();
  65     priv->cache.outline_cache = ass_outline_cache_create();
  66     priv->cache.glyph_max = GLYPH_CACHE_MAX;
  67     priv->cache.bitmap_max_size = BITMAP_CACHE_MAX_SIZE;
  68
  69     priv->text_info.max_glyphs = MAX_GLYPHS_INITIAL;
  70     priv->text_info.max_lines = MAX_LINES_INITIAL;
  71     priv->text_info.glyphs = calloc(MAX_GLYPHS_INITIAL, sizeof(GlyphInfo));
  72     priv->text_info.lines = calloc(MAX_LINES_INITIAL, sizeof(LineInfo));
  73
  74     priv->settings.font_size_coeff = 1.;
  75
  76     priv->shaper = ass_shaper_new(0);
  77     ass_shaper_info(library);
  78 #ifdef CONFIG_HARFBUZZ
  79     priv->settings.shaper = ASS_SHAPING_COMPLEX;
  80 #else
  81     priv->settings.shaper = ASS_SHAPING_SIMPLE;
  82 #endif
  83
  84   ass_init_exit:
  85     if (priv)
  86         ass_msg(library, MSGL_V, "Initialized");
  87     else
  88         ass_msg(library, MSGL_ERR, "Initialization failed");
  89
  90     return priv;
  91 }
  92
  93 static void free_list_clear(ASS_Renderer *render_priv)
  94 {
  95     if (render_priv->free_head) {
  96         FreeList *item = render_priv->free_head;
  97         while(item) {
  98             FreeList *oi = item;
  99             free(item->object);
 100             item = item->next;
 101             free(oi);
 102         }
 103         render_priv->free_head = NULL;
 104     }
 105 }
 106
 107 void ass_renderer_done(ASS_Renderer *render_priv)
 108 {
 109     ass_cache_done(render_priv->cache.font_cache);
 110     ass_cache_done(render_priv->cache.bitmap_cache);
 111     ass_cache_done(render_priv->cache.composite_cache);
 112     ass_cache_done(render_priv->cache.outline_cache);
 113
 114     ass_free_images(render_priv->images_root);
 115     ass_free_images(render_priv->prev_images_root);
 116
 117     if (render_priv->state.stroker) {
 118         FT_Stroker_Done(render_priv->state.stroker);
 119         render_priv->state.stroker = 0;
 120     }
 121     if (render_priv->ftlibrary)
 122         FT_Done_FreeType(render_priv->ftlibrary);
 123     if (render_priv->fontconfig_priv)
 124         fontconfig_done(render_priv->fontconfig_priv);
 125     if (render_priv->synth_priv)
 126         ass_synth_done(render_priv->synth_priv);
 127     ass_shaper_free(render_priv->shaper);
 128     free(render_priv->eimg);
 129     free(render_priv->text_info.glyphs);
 130     free(render_priv->text_info.lines);
 131
 132     free(render_priv->settings.default_font);
 133     free(render_priv->settings.default_family);
 134
 135     free_list_clear(render_priv);
 136     free(render_priv);
 137 }
 138
 139 /**
 140  * \brief Create a new ASS_Image
 141  * Parameters are the same as ASS_Image fields.
 142  */
 143 static ASS_Image *my_draw_bitmap(unsigned char *bitmap, int bitmap_w,
 144                                  int bitmap_h, int stride, int dst_x,
 145                                  int dst_y, uint32_t color)
 146 {
 147     ASS_Image *img = malloc(sizeof(ASS_Image));
 148
 149     if (img) {
 150         img->w = bitmap_w;
 151         img->h = bitmap_h;
 152         img->stride = stride;
 153         img->bitmap = bitmap;
 154         img->color = color;
 155         img->dst_x = dst_x;
 156         img->dst_y = dst_y;
 157     }
 158
 159     return img;
 160 }
 161
 162 /**
 163  * \brief Mapping between script and screen coordinates
 164  */
 165 static double x2scr(ASS_Renderer *render_priv, double x)
 166 {
 167     return x * render_priv->orig_width_nocrop / render_priv->font_scale_x /
 168         render_priv->track->PlayResX +
 169         FFMAX(render_priv->settings.left_margin, 0);
 170 }
 171 static double x2scr_pos(ASS_Renderer *render_priv, double x)
 172 {
 173     return x * render_priv->orig_width / render_priv->font_scale_x / render_priv->track->PlayResX +
 174         render_priv->settings.left_margin;
 175 }
 176 static double x2scr_scaled(ASS_Renderer *render_priv, double x)
 177 {
 178     return x * render_priv->orig_width_nocrop /
 179         render_priv->track->PlayResX +
 180         FFMAX(render_priv->settings.left_margin, 0);
 181 }
 182 static double x2scr_pos_scaled(ASS_Renderer *render_priv, double x)
 183 {
 184     return x * render_priv->orig_width / render_priv->track->PlayResX +
 185         render_priv->settings.left_margin;
 186 }
 187 /**
 188  * \brief Mapping between script and screen coordinates
 189  */
 190 static double y2scr(ASS_Renderer *render_priv, double y)
 191 {
 192     return y * render_priv->orig_height_nocrop /
 193         render_priv->track->PlayResY +
 194         FFMAX(render_priv->settings.top_margin, 0);
 195 }
 196 static double y2scr_pos(ASS_Renderer *render_priv, double y)
 197 {
 198     return y * render_priv->orig_height / render_priv->track->PlayResY +
 199         render_priv->settings.top_margin;
 200 }
 201
 202 // the same for toptitles
 203 static double y2scr_top(ASS_Renderer *render_priv, double y)
 204 {
 205     if (render_priv->settings.use_margins)
 206         return y * render_priv->orig_height_nocrop /
 207             render_priv->track->PlayResY;
 208     else
 209         return y * render_priv->orig_height_nocrop /
 210             render_priv->track->PlayResY +
 211             FFMAX(render_priv->settings.top_margin, 0);
 212 }
 213 // the same for subtitles
 214 static double y2scr_sub(ASS_Renderer *render_priv, double y)
 215 {
 216     if (render_priv->settings.use_margins)
 217         return y * render_priv->orig_height_nocrop /
 218             render_priv->track->PlayResY +
 219             FFMAX(render_priv->settings.top_margin, 0)
 220             + FFMAX(render_priv->settings.bottom_margin, 0);
 221     else
 222         return y * render_priv->orig_height_nocrop /
 223             render_priv->track->PlayResY +
 224             FFMAX(render_priv->settings.top_margin, 0);
 225 }
 226
 227 /*
 228  * \brief Convert bitmap glyphs into ASS_Image list with inverse clipping
 229  *
 230  * Inverse clipping with the following strategy:
 231  * - find rectangle from (x0, y0) to (cx0, y1)
 232  * - find rectangle from (cx0, y0) to (cx1, cy0)
 233  * - find rectangle from (cx0, cy1) to (cx1, y1)
 234  * - find rectangle from (cx1, y0) to (x1, y1)
 235  * These rectangles can be invalid and in this case are discarded.
 236  * Afterwards, they are clipped against the screen coordinates.
 237  * In an additional pass, the rectangles need to be split up left/right for
 238  * karaoke effects.  This can result in a lot of bitmaps (6 to be exact).
 239  */
 240 static ASS_Image **render_glyph_i(ASS_Renderer *render_priv,
 241                                   Bitmap *bm, int dst_x, int dst_y,
 242                                   uint32_t color, uint32_t color2, int brk,
 243                                   ASS_Image **tail)
 244 {
 245     int i, j, x0, y0, x1, y1, cx0, cy0, cx1, cy1, sx, sy, zx, zy;
 246     Rect r[4];
 247     ASS_Image *img;
 248
 249     dst_x += bm->left;
 250     dst_y += bm->top;
 251
 252     // we still need to clip against screen boundaries
 253     zx = x2scr_pos_scaled(render_priv, 0);
 254     zy = y2scr_pos(render_priv, 0);
 255     sx = x2scr_pos_scaled(render_priv, render_priv->track->PlayResX);
 256     sy = y2scr_pos(render_priv, render_priv->track->PlayResY);
 257
 258     x0 = 0;
 259     y0 = 0;
 260     x1 = bm->w;
 261     y1 = bm->h;
 262     cx0 = render_priv->state.clip_x0 - dst_x;
 263     cy0 = render_priv->state.clip_y0 - dst_y;
 264     cx1 = render_priv->state.clip_x1 - dst_x;
 265     cy1 = render_priv->state.clip_y1 - dst_y;
 266
 267     // calculate rectangles and discard invalid ones while we're at it.
 268     i = 0;
 269     r[i].x0 = x0;
 270     r[i].y0 = y0;
 271     r[i].x1 = (cx0 > x1) ? x1 : cx0;
 272     r[i].y1 = y1;
 273     if (r[i].x1 > r[i].x0 && r[i].y1 > r[i].y0) i++;
 274     r[i].x0 = (cx0 < 0) ? x0 : cx0;
 275     r[i].y0 = y0;
 276     r[i].x1 = (cx1 > x1) ? x1 : cx1;
 277     r[i].y1 = (cy0 > y1) ? y1 : cy0;
 278     if (r[i].x1 > r[i].x0 && r[i].y1 > r[i].y0) i++;
 279     r[i].x0 = (cx0 < 0) ? x0 : cx0;
 280     r[i].y0 = (cy1 < 0) ? y0 : cy1;
 281     r[i].x1 = (cx1 > x1) ? x1 : cx1;
 282     r[i].y1 = y1;
 283     if (r[i].x1 > r[i].x0 && r[i].y1 > r[i].y0) i++;
 284     r[i].x0 = (cx1 < 0) ? x0 : cx1;
 285     r[i].y0 = y0;
 286     r[i].x1 = x1;
 287     r[i].y1 = y1;
 288     if (r[i].x1 > r[i].x0 && r[i].y1 > r[i].y0) i++;
 289
 290     // clip each rectangle to screen coordinates
 291     for (j = 0; j < i; j++) {
 292         r[j].x0 = (r[j].x0 + dst_x < zx) ? zx - dst_x : r[j].x0;
 293         r[j].y0 = (r[j].y0 + dst_y < zy) ? zy - dst_y : r[j].y0;
 294         r[j].x1 = (r[j].x1 + dst_x > sx) ? sx - dst_x : r[j].x1;
 295         r[j].y1 = (r[j].y1 + dst_y > sy) ? sy - dst_y : r[j].y1;
 296     }
 297
 298     // draw the rectangles
 299     for (j = 0; j < i; j++) {
 300         int lbrk = brk;
 301         // kick out rectangles that are invalid now
 302         if (r[j].x1 <= r[j].x0 || r[j].y1 <= r[j].y0)
 303             continue;
 304         // split up into left and right for karaoke, if needed
 305         if (lbrk > r[j].x0) {
 306             if (lbrk > r[j].x1) lbrk = r[j].x1;
 307             img = my_draw_bitmap(bm->buffer + r[j].y0 * bm->stride + r[j].x0,
 308                 lbrk - r[j].x0, r[j].y1 - r[j].y0,
 309                 bm->stride, dst_x + r[j].x0, dst_y + r[j].y0, color);
 310             if (!img) break;
 311             *tail = img;
 312             tail = &img->next;
 313         }
 314         if (lbrk < r[j].x1) {
 315             if (lbrk < r[j].x0) lbrk = r[j].x0;
 316             img = my_draw_bitmap(bm->buffer + r[j].y0 * bm->stride + lbrk,
 317                 r[j].x1 - lbrk, r[j].y1 - r[j].y0,
 318                 bm->stride, dst_x + lbrk, dst_y + r[j].y0, color2);
 319             if (!img) break;
 320             *tail = img;
 321             tail = &img->next;
 322         }
 323     }
 324
 325     return tail;
 326 }
 327
 328 /**
 329  * \brief convert bitmap glyph into ASS_Image struct(s)
 330  * \param bit freetype bitmap glyph, FT_PIXEL_MODE_GRAY
 331  * \param dst_x bitmap x coordinate in video frame
 332  * \param dst_y bitmap y coordinate in video frame
 333  * \param color first color, RGBA
 334  * \param color2 second color, RGBA
 335  * \param brk x coordinate relative to glyph origin, color is used to the left of brk, color2 - to the right
 336  * \param tail pointer to the last image's next field, head of the generated list should be stored here
 337  * \return pointer to the new list tail
 338  * Performs clipping. Uses my_draw_bitmap for actual bitmap convertion.
 339  */
 340 static ASS_Image **
 341 render_glyph(ASS_Renderer *render_priv, Bitmap *bm, int dst_x, int dst_y,
 342              uint32_t color, uint32_t color2, int brk, ASS_Image **tail)
 343 {
 344
 345     // brk is relative to dst_x
 346     // color = color left of brk
 347     // color2 = color right of brk
 348     int b_x0, b_y0, b_x1, b_y1; // visible part of the bitmap
 349     int clip_x0, clip_y0, clip_x1, clip_y1;
 350     int tmp;
 351     ASS_Image *img;
 352
 353     // Inverse clipping in use?
 354     if (render_priv->state.clip_mode)
 355         return render_glyph_i(render_priv, bm, dst_x, dst_y, color, color2,
 356                               brk, tail);
 357
 358     dst_x += bm->left;
 359     dst_y += bm->top;
 360     brk -= bm->left;
 361
 362     // clipping
 363     clip_x0 = FFMINMAX(render_priv->state.clip_x0, 0, render_priv->width);
 364     clip_y0 = FFMINMAX(render_priv->state.clip_y0, 0, render_priv->height);
 365     clip_x1 = FFMINMAX(render_priv->state.clip_x1, 0, render_priv->width);
 366     clip_y1 = FFMINMAX(render_priv->state.clip_y1, 0, render_priv->height);
 367     b_x0 = 0;
 368     b_y0 = 0;
 369     b_x1 = bm->w;
 370     b_y1 = bm->h;
 371
 372     tmp = dst_x - clip_x0;
 373     if (tmp < 0) {
 374         ass_msg(render_priv->library, MSGL_DBG2, "clip left");
 375         b_x0 = -tmp;
 376     }
 377     tmp = dst_y - clip_y0;
 378     if (tmp < 0) {
 379         ass_msg(render_priv->library, MSGL_DBG2, "clip top");
 380         b_y0 = -tmp;
 381     }
 382     tmp = clip_x1 - dst_x - bm->w;
 383     if (tmp < 0) {
 384         ass_msg(render_priv->library, MSGL_DBG2, "clip right");
 385         b_x1 = bm->w + tmp;
 386     }
 387     tmp = clip_y1 - dst_y - bm->h;
 388     if (tmp < 0) {
 389         ass_msg(render_priv->library, MSGL_DBG2, "clip bottom");
 390         b_y1 = bm->h + tmp;
 391     }
 392
 393     if ((b_y0 >= b_y1) || (b_x0 >= b_x1))
 394         return tail;
 395
 396     if (brk > b_x0) {           // draw left part
 397         if (brk > b_x1)
 398             brk = b_x1;
 399         img = my_draw_bitmap(bm->buffer + bm->stride * b_y0 + b_x0,
 400                              brk - b_x0, b_y1 - b_y0, bm->stride,
 401                              dst_x + b_x0, dst_y + b_y0, color);
 402         if (!img) return tail;
 403         *tail = img;
 404         tail = &img->next;
 405     }
 406     if (brk < b_x1) {           // draw right part
 407         if (brk < b_x0)
 408             brk = b_x0;
 409         img = my_draw_bitmap(bm->buffer + bm->stride * b_y0 + brk,
 410                              b_x1 - brk, b_y1 - b_y0, bm->stride,
 411                              dst_x + brk, dst_y + b_y0, color2);
 412         if (!img) return tail;
 413         *tail = img;
 414         tail = &img->next;
 415     }
 416     return tail;
 417 }
 418
 419 /**
 420  * \brief Replace the bitmap buffer in ASS_Image with a copy
 421  * \param img ASS_Image to operate on
 422  * \return pointer to old bitmap buffer
 423  */
 424 static unsigned char *clone_bitmap_buffer(ASS_Image *img)
 425 {
 426     unsigned char *old_bitmap = img->bitmap;
 427     int size = img->stride * (img->h - 1) + img->w;
 428     img->bitmap = malloc(size);
 429     memcpy(img->bitmap, old_bitmap, size);
 430     return old_bitmap;
 431 }
 432
 433 /**
 434  * \brief Calculate overlapping area of two consecutive bitmaps and in case they
 435  * overlap, blend them together
 436  * Mainly useful for translucent glyphs and especially borders, to avoid the
 437  * luminance adding up where they overlap (which looks ugly)
 438  */
 439 static void
 440 render_overlap(ASS_Renderer *render_priv, ASS_Image **last_tail,
 441                ASS_Image **tail)
 442 {
 443     int left, top, bottom, right;
 444     int old_left, old_top, w, h, cur_left, cur_top;
 445     int x, y, opos, cpos;
 446     char m;
 447     CompositeHashKey hk;
 448     CompositeHashValue *hv;
 449     CompositeHashValue chv;
 450     int ax = (*last_tail)->dst_x;
 451     int ay = (*last_tail)->dst_y;
 452     int aw = (*last_tail)->w;
 453     int as = (*last_tail)->stride;
 454     int ah = (*last_tail)->h;
 455     int bx = (*tail)->dst_x;
 456     int by = (*tail)->dst_y;
 457     int bw = (*tail)->w;
 458     int bs = (*tail)->stride;
 459     int bh = (*tail)->h;
 460     unsigned char *a;
 461     unsigned char *b;
 462
 463     if ((*last_tail)->bitmap == (*tail)->bitmap)
 464         return;
 465
 466     if ((*last_tail)->color != (*tail)->color)
 467         return;
 468
 469     // Calculate overlap coordinates
 470     left = (ax > bx) ? ax : bx;
 471     top = (ay > by) ? ay : by;
 472     right = ((ax + aw) < (bx + bw)) ? (ax + aw) : (bx + bw);
 473     bottom = ((ay + ah) < (by + bh)) ? (ay + ah) : (by + bh);
 474     if ((right <= left) || (bottom <= top))
 475         return;
 476     old_left = left - ax;
 477     old_top = top - ay;
 478     w = right - left;
 479     h = bottom - top;
 480     cur_left = left - bx;
 481     cur_top = top - by;
 482
 483     // Query cache
 484     hk.a = (*last_tail)->bitmap;
 485     hk.b = (*tail)->bitmap;
 486     hk.aw = aw;
 487     hk.ah = ah;
 488     hk.bw = bw;
 489     hk.bh = bh;
 490     hk.ax = ax;
 491     hk.ay = ay;
 492     hk.bx = bx;
 493     hk.by = by;
 494     hk.as = as;
 495     hk.bs = bs;
 496     hv = ass_cache_get(render_priv->cache.composite_cache, &hk);
 497     if (hv) {
 498         (*last_tail)->bitmap = hv->a;
 499         (*tail)->bitmap = hv->b;
 500         return;
 501     }
 502     // Allocate new bitmaps and copy over data
 503     a = clone_bitmap_buffer(*last_tail);
 504     b = clone_bitmap_buffer(*tail);
 505
 506     // Blend overlapping area
 507     for (y = 0; y < h; y++)
 508         for (x = 0; x < w; x++) {
 509             opos = (old_top + y) * (as) + (old_left + x);
 510             cpos = (cur_top + y) * (bs) + (cur_left + x);
 511             m = FFMIN(a[opos] + b[cpos], 0xff);
 512             (*last_tail)->bitmap[opos] = 0;
 513             (*tail)->bitmap[cpos] = m;
 514         }
 515
 516     // Insert bitmaps into the cache
 517     chv.a = (*last_tail)->bitmap;
 518     chv.b = (*tail)->bitmap;
 519     ass_cache_put(render_priv->cache.composite_cache, &hk, &chv);
 520 }
 521
 522 static void free_list_add(ASS_Renderer *render_priv, void *object)
 523 {
 524     if (!render_priv->free_head) {
 525         render_priv->free_head = calloc(1, sizeof(FreeList));
 526         render_priv->free_head->object = object;
 527         render_priv->free_tail = render_priv->free_head;
 528     } else {
 529         FreeList *l = calloc(1, sizeof(FreeList));
 530         l->object = object;
 531         render_priv->free_tail->next = l;
 532         render_priv->free_tail = render_priv->free_tail->next;
 533     }
 534 }
 535
 536 /**
 537  * Iterate through a list of bitmaps and blend with clip vector, if
 538  * applicable. The blended bitmaps are added to a free list which is freed
 539  * at the start of a new frame.
 540  */
 541 static void blend_vector_clip(ASS_Renderer *render_priv,
 542                               ASS_Image *head)
 543 {
 544     FT_Outline *outline;
 545     Bitmap *clip_bm = NULL;
 546     ASS_Image *cur;
 547     ASS_Drawing *drawing = render_priv->state.clip_drawing;
 548     BitmapHashKey key;
 549     BitmapHashValue *val;
 550     int error;
 551
 552     if (!drawing)
 553         return;
 554
 555     // Try to get mask from cache
 556     memset(&key, 0, sizeof(key));
 557     key.type = BITMAP_CLIP;
 558     key.u.clip.text = drawing->text;
 559     val = ass_cache_get(render_priv->cache.bitmap_cache, &key);
 560
 561     if (val) {
 562         clip_bm = val->bm;
 563     } else {
 564         BitmapHashValue v;
 565
 566         // Not found in cache, parse and rasterize it
 567         outline = ass_drawing_parse(drawing, 1);
 568         if (!outline) {
 569             ass_msg(render_priv->library, MSGL_WARN,
 570                     "Clip vector parsing failed. Skipping.");
 571             goto blend_vector_error;
 572         }
 573
 574         // We need to translate the clip according to screen borders
 575         if (render_priv->settings.left_margin != 0 ||
 576             render_priv->settings.top_margin != 0) {
 577             FT_Vector trans;
 578             trans.x = int_to_d6(render_priv->settings.left_margin);
 579             trans.y = -int_to_d6(render_priv->settings.top_margin);
 580             FT_Outline_Translate(outline, trans.x, trans.y);
 581         }
 582
 583         ass_msg(render_priv->library, MSGL_DBG2,
 584                 "Parsed vector clip: scales (%f, %f) string [%s]\n",
 585                 drawing->scale_x, drawing->scale_y, drawing->text);
 586
 587         clip_bm = outline_to_bitmap(render_priv->library,
 588                 render_priv->ftlibrary, outline, 0);
 589         if (clip_bm == NULL) {
 590             ass_msg(render_priv->library, MSGL_WARN,
 591                 "Clip vector rasterization failed: %d. Skipping.", error);
 592         }
 593
 594         // Add to cache
 595         memset(&v, 0, sizeof(v));
 596         key.u.clip.text = strdup(drawing->text);
 597         v.bm = clip_bm;
 598         ass_cache_put(render_priv->cache.bitmap_cache, &key, &v);
 599     }
 600 blend_vector_error:
 601
 602     if (!clip_bm) goto blend_vector_exit;
 603
 604     // Iterate through bitmaps and blend/clip them
 605     for (cur = head; cur; cur = cur->next) {
 606         int left, top, right, bottom, apos, bpos, y, x, w, h;
 607         int ax, ay, aw, ah, as;
 608         int bx, by, bw, bh, bs;
 609         int aleft, atop, bleft, btop;
 610         unsigned char *abuffer, *bbuffer, *nbuffer;
 611
 612         abuffer = cur->bitmap;
 613         bbuffer = clip_bm->buffer;
 614         ax = cur->dst_x;
 615         ay = cur->dst_y;
 616         aw = cur->w;
 617         ah = cur->h;
 618         as = cur->stride;
 619         bx = clip_bm->left;
 620         by = clip_bm->top;
 621         bw = clip_bm->w;
 622         bh = clip_bm->h;
 623         bs = clip_bm->stride;
 624
 625         // Calculate overlap coordinates
 626         left = (ax > bx) ? ax : bx;
 627         top = (ay > by) ? ay : by;
 628         right = ((ax + aw) < (bx + bw)) ? (ax + aw) : (bx + bw);
 629         bottom = ((ay + ah) < (by + bh)) ? (ay + ah) : (by + bh);
 630         aleft = left - ax;
 631         atop = top - ay;
 632         w = right - left;
 633         h = bottom - top;
 634         bleft = left - bx;
 635         btop = top - by;
 636
 637         if (render_priv->state.clip_drawing_mode) {
 638             // Inverse clip
 639             if (ax + aw < bx || ay + ah < by || ax > bx + bw ||
 640                 ay > by + bh) {
 641                 continue;
 642             }
 643
 644             // Allocate new buffer and add to free list
 645             nbuffer = malloc(as * ah);
 646             if (!nbuffer) goto blend_vector_exit;
 647             free_list_add(render_priv, nbuffer);
 648
 649             // Blend together
 650             memcpy(nbuffer, abuffer, as * (ah - 1) + aw);
 651             for (y = 0; y < h; y++)
 652                 for (x = 0; x < w; x++) {
 653                     apos = (atop + y) * as + aleft + x;
 654                     bpos = (btop + y) * bs + bleft + x;
 655                     nbuffer[apos] = FFMAX(0, abuffer[apos] - bbuffer[bpos]);
 656                 }
 657         } else {
 658             // Regular clip
 659             if (ax + aw < bx || ay + ah < by || ax > bx + bw ||
 660                 ay > by + bh) {
 661                 cur->w = cur->h = 0;
 662                 continue;
 663             }
 664
 665             // Allocate new buffer and add to free list
 666             nbuffer = calloc(as, ah);
 667             if (!nbuffer) goto blend_vector_exit;
 668             free_list_add(render_priv, nbuffer);
 669
 670             // Blend together
 671             for (y = 0; y < h; y++)
 672                 for (x = 0; x < w; x++) {
 673                     apos = (atop + y) * as + aleft + x;
 674                     bpos = (btop + y) * bs + bleft + x;
 675                     nbuffer[apos] = (abuffer[apos] * bbuffer[bpos] + 255) >> 8;
 676                 }
 677         }
 678         cur->bitmap = nbuffer;
 679     }
 680
 681 blend_vector_exit:
 682     ass_drawing_free(render_priv->state.clip_drawing);
 683     render_priv->state.clip_drawing = 0;
 684 }
 685
 686 /**
 687  * \brief Convert TextInfo struct to ASS_Image list
 688  * Splits glyphs in halves when needed (for \kf karaoke).
 689  */
 690 static ASS_Image *render_text(ASS_Renderer *render_priv, int dst_x, int dst_y)
 691 {
 692     int pen_x, pen_y;
 693     int i;
 694     Bitmap *bm;
 695     ASS_Image *head;
 696     ASS_Image **tail = &head;
 697     ASS_Image **last_tail = 0;
 698     ASS_Image **here_tail = 0;
 699     TextInfo *text_info = &render_priv->text_info;
 700
 701     for (i = 0; i < text_info->length; ++i) {
 702         GlyphInfo *info = text_info->glyphs + i;
 703         if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm_s
 704             || (info->shadow_x == 0 && info->shadow_y == 0) || info->skip)
 705             continue;
 706
 707         while (info) {
 708             if (!info->bm_s) {
 709                 info = info->next;
 710                 continue;
 711             }
 712
 713             pen_x =
 714                 dst_x + (info->pos.x >> 6) +
 715                 (int) (info->shadow_x * render_priv->border_scale);
 716             pen_y =
 717                 dst_y + (info->pos.y >> 6) +
 718                 (int) (info->shadow_y * render_priv->border_scale);
 719             bm = info->bm_s;
 720
 721             here_tail = tail;
 722             tail =
 723                 render_glyph(render_priv, bm, pen_x, pen_y, info->c[3], 0,
 724                         1000000, tail);
 725
 726             if (last_tail && tail != here_tail && ((info->c[3] & 0xff) > 0))
 727                 render_overlap(render_priv, last_tail, here_tail);
 728             last_tail = here_tail;
 729
 730             info = info->next;
 731         }
 732     }
 733
 734     last_tail = 0;
 735     for (i = 0; i < text_info->length; ++i) {
 736         GlyphInfo *info = text_info->glyphs + i;
 737         if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm_o
 738             || info->skip)
 739             continue;
 740
 741         while (info) {
 742             if (!info->bm_o) {
 743                 info = info->next;
 744                 continue;
 745             }
 746
 747             pen_x = dst_x + (info->pos.x >> 6);
 748             pen_y = dst_y + (info->pos.y >> 6);
 749             bm = info->bm_o;
 750
 751             if ((info->effect_type == EF_KARAOKE_KO)
 752                     && (info->effect_timing <= (info->bbox.xMax >> 6))) {
 753                 // do nothing
 754             } else {
 755                 here_tail = tail;
 756                 tail =
 757                     render_glyph(render_priv, bm, pen_x, pen_y, info->c[2],
 758                             0, 1000000, tail);
 759                 if (last_tail && tail != here_tail && ((info->c[2] & 0xff) > 0))
 760                     render_overlap(render_priv, last_tail, here_tail);
 761
 762                 last_tail = here_tail;
 763             }
 764             info = info->next;
 765         }
 766     }
 767
 768     for (i = 0; i < text_info->length; ++i) {
 769         GlyphInfo *info = text_info->glyphs + i;
 770         if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm
 771             || info->skip)
 772             continue;
 773
 774         while (info) {
 775             if (!info->bm) {
 776                 info = info->next;
 777                 continue;
 778             }
 779
 780             pen_x = dst_x + (info->pos.x >> 6);
 781             pen_y = dst_y + (info->pos.y >> 6);
 782             bm = info->bm;
 783
 784             if ((info->effect_type == EF_KARAOKE)
 785                     || (info->effect_type == EF_KARAOKE_KO)) {
 786                 if (info->effect_timing > (info->bbox.xMax >> 6))
 787                     tail =
 788                         render_glyph(render_priv, bm, pen_x, pen_y,
 789                                 info->c[0], 0, 1000000, tail);
 790                 else
 791                     tail =
 792                         render_glyph(render_priv, bm, pen_x, pen_y,
 793                                 info->c[1], 0, 1000000, tail);
 794             } else if (info->effect_type == EF_KARAOKE_KF) {
 795                 tail =
 796                     render_glyph(render_priv, bm, pen_x, pen_y, info->c[0],
 797                             info->c[1], info->effect_timing, tail);
 798             } else
 799                 tail =
 800                     render_glyph(render_priv, bm, pen_x, pen_y, info->c[0],
 801                             0, 1000000, tail);
 802             info = info->next;
 803         }
 804     }
 805
 806     *tail = 0;
 807     blend_vector_clip(render_priv, head);
 808
 809     return head;
 810 }
 811
 812 static void compute_string_bbox(TextInfo *text, DBBox *bbox)
 813 {
 814     int i;
 815
 816     if (text->length > 0) {
 817         bbox->xMin = 32000;
 818         bbox->xMax = -32000;
 819         bbox->yMin = -1 * text->lines[0].asc + d6_to_double(text->glyphs[0].pos.y);
 820         bbox->yMax = text->height - text->lines[0].asc +
 821                      d6_to_double(text->glyphs[0].pos.y);
 822
 823         for (i = 0; i < text->length; ++i) {
 824             GlyphInfo *info = text->glyphs + i;
 825             if (info->skip) continue;
 826             while (info) {
 827                 double s = d6_to_double(info->pos.x);
 828                 double e = s + d6_to_double(info->advance.x);
 829                 bbox->xMin = FFMIN(bbox->xMin, s);
 830                 bbox->xMax = FFMAX(bbox->xMax, e);
 831                 info = info->next;
 832             }
 833         }
 834     } else
 835         bbox->xMin = bbox->xMax = bbox->yMin = bbox->yMax = 0.;
 836 }
 837
 838 /**
 839  * \brief partially reset render_context to style values
 840  * Works like {\r}: resets some style overrides
 841  */
 842 void reset_render_context(ASS_Renderer *render_priv)
 843 {
 844     render_priv->state.c[0] = render_priv->state.style->PrimaryColour;
 845     render_priv->state.c[1] = render_priv->state.style->SecondaryColour;
 846     render_priv->state.c[2] = render_priv->state.style->OutlineColour;
 847     render_priv->state.c[3] = render_priv->state.style->BackColour;
 848     render_priv->state.flags =
 849         (render_priv->state.style->Underline ? DECO_UNDERLINE : 0) |
 850         (render_priv->state.style->StrikeOut ? DECO_STRIKETHROUGH : 0);
 851     render_priv->state.font_size = render_priv->state.style->FontSize;
 852
 853     free(render_priv->state.family);
 854     render_priv->state.family = NULL;
 855     render_priv->state.family = strdup(render_priv->state.style->FontName);
 856     render_priv->state.treat_family_as_pattern =
 857         render_priv->state.style->treat_fontname_as_pattern;
 858     render_priv->state.bold = render_priv->state.style->Bold;
 859     render_priv->state.italic = render_priv->state.style->Italic;
 860     update_font(render_priv);
 861
 862     change_border(render_priv, -1., -1.);
 863     render_priv->state.scale_x = render_priv->state.style->ScaleX;
 864     render_priv->state.scale_y = render_priv->state.style->ScaleY;
 865     render_priv->state.hspacing = render_priv->state.style->Spacing;
 866     render_priv->state.be = 0;
 867     render_priv->state.blur = 0.0;
 868     render_priv->state.shadow_x = render_priv->state.style->Shadow;
 869     render_priv->state.shadow_y = render_priv->state.style->Shadow;
 870     render_priv->state.frx = render_priv->state.fry = 0.;
 871     render_priv->state.frz = M_PI * render_priv->state.style->Angle / 180.;
 872     render_priv->state.fax = render_priv->state.fay = 0.;
 873     render_priv->state.wrap_style = render_priv->track->WrapStyle;
 874     render_priv->state.font_encoding = render_priv->state.style->Encoding;
 875 }
 876
 877 /**
 878  * \brief Start new event. Reset render_priv->state.
 879  */
 880 static void
 881 init_render_context(ASS_Renderer *render_priv, ASS_Event *event)
 882 {
 883     render_priv->state.event = event;
 884     render_priv->state.style = render_priv->track->styles + event->Style;
 885     render_priv->state.parsed_tags = 0;
 886
 887     reset_render_context(render_priv);
 888
 889     render_priv->state.evt_type = EVENT_NORMAL;
 890     render_priv->state.alignment = render_priv->state.style->Alignment;
 891     render_priv->state.pos_x = 0;
 892     render_priv->state.pos_y = 0;
 893     render_priv->state.org_x = 0;
 894     render_priv->state.org_y = 0;
 895     render_priv->state.have_origin = 0;
 896     render_priv->state.clip_x0 = 0;
 897     render_priv->state.clip_y0 = 0;
 898     render_priv->state.clip_x1 = render_priv->track->PlayResX;
 899     render_priv->state.clip_y1 = render_priv->track->PlayResY;
 900     render_priv->state.clip_mode = 0;
 901     render_priv->state.detect_collisions = 1;
 902     render_priv->state.fade = 0;
 903     render_priv->state.drawing_mode = 0;
 904     render_priv->state.effect_type = EF_NONE;
 905     render_priv->state.effect_timing = 0;
 906     render_priv->state.effect_skip_timing = 0;
 907     render_priv->state.bm_run_id = 0;
 908     ass_drawing_free(render_priv->state.drawing);
 909     render_priv->state.drawing = ass_drawing_new(render_priv->library,
 910             render_priv->ftlibrary);
 911
 912     apply_transition_effects(render_priv, event);
 913 }
 914
 915 static void free_render_context(ASS_Renderer *render_priv)
 916 {
 917     free(render_priv->state.family);
 918     ass_drawing_free(render_priv->state.drawing);
 919
 920     render_priv->state.family = NULL;
 921     render_priv->state.drawing = NULL;
 922 }
 923
 924 /*
 925  * Replace the outline of a glyph by a contour which makes up a simple
 926  * opaque rectangle.
 927  */
 928 static void draw_opaque_box(ASS_Renderer *render_priv, int asc, int desc,
 929                             FT_Outline *ol, FT_Vector advance, int sx, int sy)
 930 {
 931     int i;
 932     int adv = advance.x;
 933     double scale_y = render_priv->state.scale_y;
 934     double scale_x = render_priv->state.scale_x;
 935     FT_Vector points[4];
 936
 937     // to avoid gaps
 938     sx = FFMAX(64, sx);
 939     sy = FFMAX(64, sy);
 940
 941     // Emulate the WTFish behavior of VSFilter, i.e. double-scale
 942     // the sizes of the opaque box.
 943     adv += double_to_d6(render_priv->state.hspacing * render_priv->font_scale
 944                         * scale_x);
 945     adv *= scale_x;
 946     sx *= scale_x;
 947     sy *= scale_y;
 948     desc *= scale_y;
 949     desc += asc * (scale_y - 1.0);
 950
 951     points[0].x = -sx;
 952     points[0].y = asc + sy;
 953     points[1].x = adv + sx;
 954     points[1].y = asc + sy;
 955     points[2].x = adv + sx;
 956     points[2].y = -desc - sy;
 957     points[3].x = -sx;
 958     points[3].y = -desc - sy;
 959
 960     FT_Outline_New(render_priv->ftlibrary, 4, 1, ol);
 961
 962     ol->n_points = ol->n_contours = 0;
 963     for (i = 0; i < 4; i++) {
 964         ol->points[ol->n_points] = points[i];
 965         ol->tags[ol->n_points++] = 1;
 966     }
 967     ol->contours[ol->n_contours++] = ol->n_points - 1;
 968 }
 969
 970 /*
 971  * Stroke an outline glyph in x/y direction.  Applies various fixups to get
 972  * around limitations of the FreeType stroker.
 973  */
 974 static void stroke_outline(ASS_Renderer *render_priv, FT_Outline *outline,
 975                            int sx, int sy)
 976 {
 977     if (sx <= 0 && sy <= 0)
 978         return;
 979
 980     fix_freetype_stroker(outline, sx, sy);
 981
 982     // Borders are equal; use the regular stroker
 983     if (sx == sy && render_priv->state.stroker) {
 984         int error;
 985         unsigned n_points, n_contours;
 986
 987         FT_StrokerBorder border = FT_Outline_GetOutsideBorder(outline);
 988         error = FT_Stroker_ParseOutline(render_priv->state.stroker, outline, 0);
 989         if (error) {
 990             ass_msg(render_priv->library, MSGL_WARN,
 991                     "FT_Stroker_ParseOutline failed, error: %d", error);
 992         }
 993         error = FT_Stroker_GetBorderCounts(render_priv->state.stroker, border,
 994                 &n_points, &n_contours);
 995         if (error) {
 996             ass_msg(render_priv->library, MSGL_WARN,
 997                     "FT_Stroker_GetBorderCounts failed, error: %d", error);
 998         }
 999         FT_Outline_Done(render_priv->ftlibrary, outline);
1000         FT_Outline_New(render_priv->ftlibrary, n_points, n_contours, outline);
1001         outline->n_points = outline->n_contours = 0;
1002         FT_Stroker_ExportBorder(render_priv->state.stroker, border, outline);
1003
1004     // "Stroke" with the outline emboldener in two passes.
1005     // The outlines look uglier, but the emboldening never adds any points
1006     } else {
1007         int i;
1008         FT_Outline nol;
1009
1010         FT_Outline_New(render_priv->ftlibrary, outline->n_points,
1011                        outline->n_contours, &nol);
1012         FT_Outline_Copy(outline, &nol);
1013
1014         FT_Outline_Embolden(outline, sx * 2);
1015         FT_Outline_Translate(outline, -sx, -sx);
1016         FT_Outline_Embolden(&nol, sy * 2);
1017         FT_Outline_Translate(&nol, -sy, -sy);
1018
1019         for (i = 0; i < outline->n_points; i++)
1020             outline->points[i].y = nol.points[i].y;
1021
1022         FT_Outline_Done(render_priv->ftlibrary, &nol);
1023     }
1024 }
1025
1026 /**
1027  * \brief Prepare glyph hash
1028  */
1029 static void
1030 fill_glyph_hash(ASS_Renderer *priv, OutlineHashKey *outline_key,
1031                 GlyphInfo *info)
1032 {
1033     if (info->drawing) {
1034         DrawingHashKey *key = &outline_key->u.drawing;
1035         outline_key->type = OUTLINE_DRAWING;
1036         key->scale_x = double_to_d16(info->scale_x);
1037         key->scale_y = double_to_d16(info->scale_y);
1038         key->outline.x = double_to_d16(info->border_x);
1039         key->outline.y = double_to_d16(info->border_y);
1040         key->border_style = priv->state.style->BorderStyle;
1041         key->hash = info->drawing->hash;
1042         key->text = info->drawing->text;
1043         key->pbo = info->drawing->pbo;
1044         key->scale = info->drawing->scale;
1045     } else {
1046         GlyphHashKey *key = &outline_key->u.glyph;
1047         outline_key->type = OUTLINE_GLYPH;
1048         key->font = info->font;
1049         key->size = info->font_size;
1050         key->face_index = info->face_index;
1051         key->glyph_index = info->glyph_index;
1052         key->bold = info->bold;
1053         key->italic = info->italic;
1054         key->scale_x = double_to_d16(info->scale_x);
1055         key->scale_y = double_to_d16(info->scale_y);
1056         key->outline.x = double_to_d16(info->border_x);
1057         key->outline.y = double_to_d16(info->border_y);
1058         key->flags = info->flags;
1059         key->border_style = priv->state.style->BorderStyle;
1060     }
1061 }
1062
1063 /**
1064  * \brief Get normal and outline (border) glyphs
1065  * \param info out: struct filled with extracted data
1066  * Tries to get both glyphs from cache.
1067  * If they can't be found, gets a glyph from font face, generates outline with FT_Stroker,
1068  * and add them to cache.
1069  * The glyphs are returned in info->glyph and info->outline_glyph
1070  */
1071 static void
1072 get_outline_glyph(ASS_Renderer *priv, GlyphInfo *info)
1073 {
1074     OutlineHashValue *val;
1075     OutlineHashKey key;
1076
1077     memset(&info->hash_key, 0, sizeof(key));
1078
1079     fill_glyph_hash(priv, &key, info);
1080     val = ass_cache_get(priv->cache.outline_cache, &key);
1081
1082     if (!val) {
1083         OutlineHashValue v;
1084         memset(&v, 0, sizeof(v));
1085
1086         if (info->drawing) {
1087             ASS_Drawing *drawing = info->drawing;
1088             ass_drawing_hash(drawing);
1089             if(!ass_drawing_parse(drawing, 0))
1090                 return;
1091             outline_copy(priv->ftlibrary, &drawing->outline,
1092                     &v.outline);
1093             v.advance.x = drawing->advance.x;
1094             v.advance.y = drawing->advance.y;
1095             v.asc = drawing->asc;
1096             v.desc = drawing->desc;
1097             key.u.drawing.text = strdup(drawing->text);
1098         } else {
1099             FT_Glyph glyph;
1100             ass_face_set_size(info->font->faces[info->face_index],
1101                     info->font_size);
1102             ass_font_set_transform(info->font, info->scale_x,
1103                     info->scale_y, NULL);
1104             glyph =
1105                 ass_font_get_glyph(priv->fontconfig_priv, info->font,
1106                         info->symbol, info->face_index, info->glyph_index,
1107                         priv->settings.hinting, info->flags);
1108             if (glyph != NULL) {
1109                 outline_copy(priv->ftlibrary,
1110                         &((FT_OutlineGlyph)glyph)->outline, &v.outline);
1111                 if (priv->settings.shaper == ASS_SHAPING_SIMPLE) {
1112                     v.advance.x = d16_to_d6(glyph->advance.x);
1113                     v.advance.y = d16_to_d6(glyph->advance.y);
1114                 }
1115                 FT_Done_Glyph(glyph);
1116                 ass_font_get_asc_desc(info->font, info->symbol,
1117                         &v.asc, &v.desc);
1118                 v.asc  *= info->scale_y;
1119                 v.desc *= info->scale_y;
1120             }
1121         }
1122
1123         if (!v.outline)
1124             return;
1125
1126         FT_Outline_Get_CBox(v.outline, &v.bbox_scaled);
1127
1128         if (priv->state.style->BorderStyle == 3 &&
1129                 (info->border_x > 0 || info->border_y > 0)) {
1130             FT_Vector advance;
1131
1132             v.border = calloc(1, sizeof(FT_Outline));
1133
1134             if (priv->settings.shaper == ASS_SHAPING_SIMPLE || info->drawing)
1135                 advance = v.advance;
1136             else
1137                 advance = info->advance;
1138
1139             draw_opaque_box(priv, v.asc, v.desc, v.border, advance,
1140                     double_to_d6(info->border_x * priv->border_scale),
1141                     double_to_d6(info->border_y * priv->border_scale));
1142
1143         } else if ((info->border_x > 0 || info->border_y > 0)
1144                 && double_to_d6(info->scale_x) && double_to_d6(info->scale_y)) {
1145
1146             outline_copy(priv->ftlibrary, v.outline, &v.border);
1147             stroke_outline(priv, v.border,
1148                     double_to_d6(info->border_x * priv->border_scale),
1149                     double_to_d6(info->border_y * priv->border_scale));
1150         }
1151
1152         v.lib = priv->ftlibrary;
1153         val = ass_cache_put(priv->cache.outline_cache, &key, &v);
1154     }
1155
1156     info->hash_key.u.outline.outline = val;
1157     info->outline = val->outline;
1158     info->border = val->border;
1159     info->bbox = val->bbox_scaled;
1160     if (info->drawing || priv->settings.shaper == ASS_SHAPING_SIMPLE) {
1161         info->cluster_advance.x = info->advance.x = val->advance.x;
1162         info->cluster_advance.y = info->advance.y = val->advance.y;
1163     }
1164     info->asc = val->asc;
1165     info->desc = val->desc;
1166
1167     ass_drawing_free(info->drawing);
1168 }
1169
1170 /**
1171  * \brief Apply transformation to outline points of a glyph
1172  * Applies rotations given by frx, fry and frz and projects the points back
1173  * onto the screen plane.
1174  */
1175 static void
1176 transform_3d_points(FT_Vector shift, FT_Outline *outline, double frx, double fry,
1177                     double frz, double fax, double fay, double scale,
1178                     int yshift)
1179 {
1180     double sx = sin(frx);
1181     double sy = sin(fry);
1182     double sz = sin(frz);
1183     double cx = cos(frx);
1184     double cy = cos(fry);
1185     double cz = cos(frz);
1186     FT_Vector *p = outline->points;
1187     double x, y, z, xx, yy, zz;
1188     int i, dist;
1189
1190     dist = 20000 * scale;
1191     for (i = 0; i < outline->n_points; i++) {
1192         x = (double) p[i].x + shift.x + (fax * (yshift - p[i].y));
1193         y = (double) p[i].y + shift.y + (-fay * p[i].x);
1194         z = 0.;
1195
1196         xx = x * cz + y * sz;
1197         yy = -(x * sz - y * cz);
1198         zz = z;
1199
1200         x = xx;
1201         y = yy * cx + zz * sx;
1202         z = yy * sx - zz * cx;
1203
1204         xx = x * cy + z * sy;
1205         yy = y;
1206         zz = x * sy - z * cy;
1207
1208         zz = FFMAX(zz, 1000 - dist);
1209
1210         x = (xx * dist) / (zz + dist);
1211         y = (yy * dist) / (zz + dist);
1212         p[i].x = x - shift.x + 0.5;
1213         p[i].y = y - shift.y + 0.5;
1214     }
1215 }
1216
1217 /**
1218  * \brief Apply 3d transformation to several objects
1219  * \param shift FreeType vector
1220  * \param glyph FreeType glyph
1221  * \param glyph2 FreeType glyph
1222  * \param frx x-axis rotation angle
1223  * \param fry y-axis rotation angle
1224  * \param frz z-axis rotation angle
1225  * Rotates both glyphs by frx, fry and frz. Shift vector is added before rotation and subtracted after it.
1226  */
1227 static void
1228 transform_3d(FT_Vector shift, FT_Outline *outline, FT_Outline *border,
1229              double frx, double fry, double frz, double fax, double fay,
1230              double scale, int yshift)
1231 {
1232     frx = -frx;
1233     frz = -frz;
1234     if (frx != 0. || fry != 0. || frz != 0. || fax != 0. || fay != 0.) {
1235         if (outline)
1236             transform_3d_points(shift, outline, frx, fry, frz,
1237                                 fax, fay, scale, yshift);
1238
1239         if (border)
1240             transform_3d_points(shift, border, frx, fry, frz,
1241                                 fax, fay, scale, yshift);
1242     }
1243 }
1244
1245 /**
1246  * \brief Get bitmaps for a glyph
1247  * \param info glyph info
1248  * Tries to get glyph bitmaps from bitmap cache.
1249  * If they can't be found, they are generated by rotating and rendering the glyph.
1250  * After that, bitmaps are added to the cache.
1251  * They are returned in info->bm (glyph), info->bm_o (outline) and info->bm_s (shadow).
1252  */
1253 static void
1254 get_bitmap_glyph(ASS_Renderer *render_priv, GlyphInfo *info)
1255 {
1256     BitmapHashValue *val;
1257     OutlineBitmapHashKey *key = &info->hash_key.u.outline;
1258
1259     if (!info->outline || info->symbol == '\n' || info->symbol == 0 || info->skip)
1260         return;
1261
1262     val = ass_cache_get(render_priv->cache.bitmap_cache, &info->hash_key);
1263
1264     if (!val) {
1265         FT_Vector shift;
1266         BitmapHashValue hash_val;
1267         int error;
1268         double fax_scaled, fay_scaled;
1269         FT_Outline *outline, *border;
1270         double scale_x = render_priv->font_scale_x;
1271         FT_Matrix m;
1272
1273         hash_val.bm = hash_val.bm_o = hash_val.bm_s = 0;
1274
1275         outline_copy(render_priv->ftlibrary, info->outline, &outline);
1276         outline_copy(render_priv->ftlibrary, info->border, &border);
1277
1278         // calculating rotation shift vector (from rotation origin to the glyph basepoint)
1279         shift.x = key->shift_x;
1280         shift.y = key->shift_y;
1281         fax_scaled = info->fax * render_priv->state.scale_x;
1282         fay_scaled = info->fay * render_priv->state.scale_y;
1283
1284         // apply rotation
1285         transform_3d(shift, outline, border,
1286                 info->frx, info->fry, info->frz, fax_scaled,
1287                 fay_scaled, render_priv->font_scale, info->asc);
1288
1289         // PAR correction scaling
1290         m.xx = double_to_d16(scale_x);
1291         m.xy = 0;
1292         m.yx = 0;
1293         m.yy = double_to_d16(1.0);
1294
1295         // subpixel shift
1296         if (outline) {
1297             if (scale_x != 1.0)
1298                 FT_Outline_Transform(outline, &m);
1299             FT_Outline_Translate(outline, key->advance.x, -key->advance.y);
1300         }
1301         if (border) {
1302             if (scale_x != 1.0)
1303                 FT_Outline_Transform(border, &m);
1304             FT_Outline_Translate(border, key->advance.x, -key->advance.y);
1305         }
1306
1307         // render glyph
1308         error = outline_to_bitmap3(render_priv->library,
1309                 render_priv->synth_priv,
1310                 render_priv->ftlibrary,
1311                 outline, border,
1312                 &hash_val.bm, &hash_val.bm_o,
1313                 &hash_val.bm_s, info->be,
1314                 info->blur * render_priv->border_scale,
1315                 key->shadow_offset,
1316                 render_priv->state.style->BorderStyle);
1317         if (error)
1318             info->symbol = 0;
1319
1320         val = ass_cache_put(render_priv->cache.bitmap_cache, &info->hash_key,
1321                 &hash_val);
1322
1323         outline_free(render_priv->ftlibrary, outline);
1324         outline_free(render_priv->ftlibrary, border);
1325     }
1326
1327     info->bm = val->bm;
1328     info->bm_o = val->bm_o;
1329     info->bm_s = val->bm_s;
1330
1331     // VSFilter compatibility: invisible fill and no border?
1332     // In this case no shadow is supposed to be rendered.
1333     if (!info->border && (info->c[0] & 0xFF) == 0xFF)
1334         info->bm_s = 0;
1335 }
1336
1337 /**
1338  * This function goes through text_info and calculates text parameters.
1339  * The following text_info fields are filled:
1340  *   height
1341  *   lines[].height
1342  *   lines[].asc
1343  *   lines[].desc
1344  */
1345 static void measure_text(ASS_Renderer *render_priv)
1346 {
1347     TextInfo *text_info = &render_priv->text_info;
1348     int cur_line = 0;
1349     double max_asc = 0., max_desc = 0.;
1350     GlyphInfo *last = NULL;
1351     int i;
1352     int empty_line = 1;
1353     text_info->height = 0.;
1354     for (i = 0; i < text_info->length + 1; ++i) {
1355         if ((i == text_info->length) || text_info->glyphs[i].linebreak) {
1356             if (empty_line && cur_line > 0 && last && i < text_info->length) {
1357                 max_asc = d6_to_double(last->asc) / 2.0;
1358                 max_desc = d6_to_double(last->desc) / 2.0;
1359             }
1360             text_info->lines[cur_line].asc = max_asc;
1361             text_info->lines[cur_line].desc = max_desc;
1362             text_info->height += max_asc + max_desc;
1363             cur_line++;
1364             max_asc = max_desc = 0.;
1365             empty_line = 1;
1366         } else
1367             empty_line = 0;
1368         if (i < text_info->length) {
1369             GlyphInfo *cur = text_info->glyphs + i;
1370             if (d6_to_double(cur->asc) > max_asc)
1371                 max_asc = d6_to_double(cur->asc);
1372             if (d6_to_double(cur->desc) > max_desc)
1373                 max_desc = d6_to_double(cur->desc);
1374             if (cur->symbol != '\n' && cur->symbol != 0)
1375                 last = cur;
1376         }
1377     }
1378     text_info->height +=
1379         (text_info->n_lines -
1380          1) * render_priv->settings.line_spacing;
1381 }
1382
1383 /**
1384  * Mark extra whitespace for later removal.
1385  */
1386 #define IS_WHITESPACE(x) ((x->symbol == ' ' || x->symbol == '\n') \
1387                           && !x->linebreak)
1388 static void trim_whitespace(ASS_Renderer *render_priv)
1389 {
1390     int i, j;
1391     GlyphInfo *cur;
1392     TextInfo *ti = &render_priv->text_info;
1393
1394     // Mark trailing spaces
1395     i = ti->length - 1;
1396     cur = ti->glyphs + i;
1397     while (i && IS_WHITESPACE(cur)) {
1398         cur->skip++;
1399         cur = ti->glyphs + --i;
1400     }
1401
1402     // Mark leading whitespace
1403     i = 0;
1404     cur = ti->glyphs;
1405     while (i < ti->length && IS_WHITESPACE(cur)) {
1406         cur->skip++;
1407         cur = ti->glyphs + ++i;
1408     }
1409
1410     // Mark all extraneous whitespace inbetween
1411     for (i = 0; i < ti->length; ++i) {
1412         cur = ti->glyphs + i;
1413         if (cur->linebreak) {
1414             // Mark whitespace before
1415             j = i - 1;
1416             cur = ti->glyphs + j;
1417             while (j && IS_WHITESPACE(cur)) {
1418                 cur->skip++;
1419                 cur = ti->glyphs + --j;
1420             }
1421             // A break itself can contain a whitespace, too
1422             cur = ti->glyphs + i;
1423             if (cur->symbol == ' ') {
1424                 cur->skip++;
1425                 // Mark whitespace after
1426                 j = i + 1;
1427                 cur = ti->glyphs + j;
1428                 while (j < ti->length && IS_WHITESPACE(cur)) {
1429                     cur->skip++;
1430                     cur = ti->glyphs + ++j;
1431                 }
1432                 i = j - 1;
1433             }
1434         }
1435     }
1436 }
1437 #undef IS_WHITESPACE
1438
1439 /**
1440  * \brief rearrange text between lines
1441  * \param max_text_width maximal text line width in pixels
1442  * The algo is similar to the one in libvo/sub.c:
1443  * 1. Place text, wrapping it when current line is full
1444  * 2. Try moving words from the end of a line to the beginning of the next one while it reduces
1445  * the difference in lengths between this two lines.
1446  * The result may not be optimal, but usually is good enough.
1447  *
1448  * FIXME: implement style 0 and 3 correctly
1449  */
1450 static void
1451 wrap_lines_smart(ASS_Renderer *render_priv, double max_text_width)
1452 {
1453     int i;
1454     GlyphInfo *cur, *s1, *e1, *s2, *s3, *w;
1455     int last_space;
1456     int break_type;
1457     int exit;
1458     double pen_shift_x;
1459     double pen_shift_y;
1460     int cur_line;
1461     int run_offset;
1462     TextInfo *text_info = &render_priv->text_info;
1463
1464     last_space = -1;
1465     text_info->n_lines = 1;
1466     break_type = 0;
1467     s1 = text_info->glyphs;     // current line start
1468     for (i = 0; i < text_info->length; ++i) {
1469         int break_at = -1;
1470         double s_offset, len;
1471         cur = text_info->glyphs + i;
1472         s_offset = d6_to_double(s1->bbox.xMin + s1->pos.x);
1473         len = d6_to_double(cur->bbox.xMax + cur->pos.x) - s_offset;
1474
1475         if (cur->symbol == '\n') {
1476             break_type = 2;
1477             break_at = i;
1478             ass_msg(render_priv->library, MSGL_DBG2,
1479                     "forced line break at %d", break_at);
1480         } else if (cur->symbol == ' ') {
1481             last_space = i;
1482         } else if (len >= max_text_width
1483                    && (render_priv->state.wrap_style != 2)) {
1484             break_type = 1;
1485             break_at = last_space;
1486             if (break_at >= 0)
1487                 ass_msg(render_priv->library, MSGL_DBG2, "line break at %d",
1488                         break_at);
1489         }
1490
1491         if (break_at != -1) {
1492             // need to use one more line
1493             // marking break_at+1 as start of a new line
1494             int lead = break_at + 1;    // the first symbol of the new line
1495             if (text_info->n_lines >= text_info->max_lines) {
1496                 // Raise maximum number of lines
1497                 text_info->max_lines *= 2;
1498                 text_info->lines = realloc(text_info->lines,
1499                                            sizeof(LineInfo) *
1500                                            text_info->max_lines);
1501             }
1502             if (lead < text_info->length) {
1503                 text_info->glyphs[lead].linebreak = break_type;
1504                 last_space = -1;
1505                 s1 = text_info->glyphs + lead;
1506                 s_offset = d6_to_double(s1->bbox.xMin + s1->pos.x);
1507                 text_info->n_lines++;
1508             }
1509         }
1510     }
1511 #define DIFF(x,y) (((x) < (y)) ? (y - x) : (x - y))
1512     exit = 0;
1513     while (!exit && render_priv->state.wrap_style != 1) {
1514         exit = 1;
1515         w = s3 = text_info->glyphs;
1516         s1 = s2 = 0;
1517         for (i = 0; i <= text_info->length; ++i) {
1518             cur = text_info->glyphs + i;
1519             if ((i == text_info->length) || cur->linebreak) {
1520                 s1 = s2;
1521                 s2 = s3;
1522                 s3 = cur;
1523                 if (s1 && (s2->linebreak == 1)) {       // have at least 2 lines, and linebreak is 'soft'
1524                     double l1, l2, l1_new, l2_new;
1525
1526                     w = s2;
1527                     do {
1528                         --w;
1529                     } while ((w > s1) && (w->symbol == ' '));
1530                     while ((w > s1) && (w->symbol != ' ')) {
1531                         --w;
1532                     }
1533                     e1 = w;
1534                     while ((e1 > s1) && (e1->symbol == ' ')) {
1535                         --e1;
1536                     }
1537                     if (w->symbol == ' ')
1538                         ++w;
1539
1540                     l1 = d6_to_double(((s2 - 1)->bbox.xMax + (s2 - 1)->pos.x) -
1541                         (s1->bbox.xMin + s1->pos.x));
1542                     l2 = d6_to_double(((s3 - 1)->bbox.xMax + (s3 - 1)->pos.x) -
1543                         (s2->bbox.xMin + s2->pos.x));
1544                     l1_new = d6_to_double(
1545                         (e1->bbox.xMax + e1->pos.x) -
1546                         (s1->bbox.xMin + s1->pos.x));
1547                     l2_new = d6_to_double(
1548                         ((s3 - 1)->bbox.xMax + (s3 - 1)->pos.x) -
1549                         (w->bbox.xMin + w->pos.x));
1550
1551                     if (DIFF(l1_new, l2_new) < DIFF(l1, l2)) {
1552                         w->linebreak = 1;
1553                         s2->linebreak = 0;
1554                         exit = 0;
1555                     }
1556                 }
1557             }
1558             if (i == text_info->length)
1559                 break;
1560         }
1561
1562     }
1563     assert(text_info->n_lines >= 1);
1564 #undef DIFF
1565
1566     measure_text(render_priv);
1567     trim_whitespace(render_priv);
1568
1569     pen_shift_x = 0.;
1570     pen_shift_y = 0.;
1571     cur_line = 1;
1572     run_offset = 0;
1573
1574     i = 0;
1575     cur = text_info->glyphs + i;
1576     while (i < text_info->length && cur->skip)
1577         cur = text_info->glyphs + ++i;
1578     pen_shift_x = d6_to_double(-cur->pos.x);
1579
1580     for (i = 0; i < text_info->length; ++i) {
1581         cur = text_info->glyphs + i;
1582         if (cur->linebreak) {
1583             double height;
1584             while (i < text_info->length && cur->skip && cur->symbol != '\n')
1585                 cur = text_info->glyphs + ++i;
1586             height =
1587                 text_info->lines[cur_line - 1].desc +
1588                 text_info->lines[cur_line].asc;
1589             text_info->lines[cur_line - 1].len = i -
1590                 text_info->lines[cur_line - 1].offset;
1591             text_info->lines[cur_line].offset = i;
1592             cur_line++;
1593             run_offset++;
1594             pen_shift_x = d6_to_double(-cur->pos.x);
1595             pen_shift_y += height + render_priv->settings.line_spacing;
1596             ass_msg(render_priv->library, MSGL_DBG2,
1597                    "shifting from %d to %d by (%f, %f)", i,
1598                    text_info->length - 1, pen_shift_x, pen_shift_y);
1599         }
1600         cur->bm_run_id += run_offset;
1601         cur->pos.x += double_to_d6(pen_shift_x);
1602         cur->pos.y += double_to_d6(pen_shift_y);
1603     }
1604     text_info->lines[cur_line - 1].len =
1605         text_info->length - text_info->lines[cur_line - 1].offset;
1606
1607 #if 0
1608     // print line info
1609     for (i = 0; i < text_info->n_lines; i++) {
1610         printf("line %d offset %d length %d\n", i, text_info->lines[i].offset,
1611                 text_info->lines[i].len);
1612     }
1613 #endif
1614 }
1615
1616 /**
1617  * \brief Calculate base point for positioning and rotation
1618  * \param bbox text bbox
1619  * \param alignment alignment
1620  * \param bx, by out: base point coordinates
1621  */
1622 static void get_base_point(DBBox *bbox, int alignment, double *bx, double *by)
1623 {
1624     const int halign = alignment & 3;
1625     const int valign = alignment & 12;
1626     if (bx)
1627         switch (halign) {
1628         case HALIGN_LEFT:
1629             *bx = bbox->xMin;
1630             break;
1631         case HALIGN_CENTER:
1632             *bx = (bbox->xMax + bbox->xMin) / 2.0;
1633             break;
1634         case HALIGN_RIGHT:
1635             *bx = bbox->xMax;
1636             break;
1637         }
1638     if (by)
1639         switch (valign) {
1640         case VALIGN_TOP:
1641             *by = bbox->yMin;
1642             break;
1643         case VALIGN_CENTER:
1644             *by = (bbox->yMax + bbox->yMin) / 2.0;
1645             break;
1646         case VALIGN_SUB:
1647             *by = bbox->yMax;
1648             break;
1649         }
1650 }
1651
1652 /**
1653  * Prepare bitmap hash key of a glyph
1654  */
1655 static void
1656 fill_bitmap_hash(ASS_Renderer *priv, GlyphInfo *info,
1657                  OutlineBitmapHashKey *hash_key)
1658 {
1659     hash_key->frx = rot_key(info->frx);
1660     hash_key->fry = rot_key(info->fry);
1661     hash_key->frz = rot_key(info->frz);
1662     hash_key->fax = double_to_d16(info->fax);
1663     hash_key->fay = double_to_d16(info->fay);
1664     hash_key->be = info->be;
1665     hash_key->blur = info->blur;
1666     hash_key->shadow_offset.x = double_to_d6(
1667             info->shadow_x * priv->border_scale -
1668             (int) (info->shadow_x * priv->border_scale));
1669     hash_key->shadow_offset.y = double_to_d6(
1670             info->shadow_y * priv->border_scale -
1671             (int) (info->shadow_y * priv->border_scale));
1672 }
1673
1674 /**
1675  * \brief Main ass rendering function, glues everything together
1676  * \param event event to render
1677  * \param event_images struct containing resulting images, will also be initialized
1678  * Process event, appending resulting ASS_Image's to images_root.
1679  */
1680 static int
1681 ass_render_event(ASS_Renderer *render_priv, ASS_Event *event,
1682                  EventImages *event_images)
1683 {
1684     char *p;
1685     FT_UInt previous;
1686     FT_UInt num_glyphs;
1687     FT_Vector pen;
1688     unsigned code;
1689     DBBox bbox;
1690     int i, j;
1691     int MarginL, MarginR, MarginV;
1692     int last_break;
1693     int alignment, halign, valign;
1694     double device_x = 0;
1695     double device_y = 0;
1696     TextInfo *text_info = &render_priv->text_info;
1697     GlyphInfo *glyphs = render_priv->text_info.glyphs;
1698     ASS_Drawing *drawing;
1699     double max_text_width = 0;
1700     FriBidiStrIndex *cmap = NULL;
1701     int lineno = 1;
1702     int left = 0;
1703
1704     if (event->Style >= render_priv->track->n_styles) {
1705         ass_msg(render_priv->library, MSGL_WARN, "No style found");
1706         return 1;
1707     }
1708     if (!event->Text) {
1709         ass_msg(render_priv->library, MSGL_WARN, "Empty event");
1710         return 1;
1711     }
1712
1713     init_render_context(render_priv, event);
1714
1715     drawing = render_priv->state.drawing;
1716     text_info->length = 0;
1717     num_glyphs = 0;
1718     p = event->Text;
1719
1720     // Event parsing.
1721     while (1) {
1722         // get next char, executing style override
1723         // this affects render_context
1724         do {
1725             code = get_next_char(render_priv, &p);
1726             if (render_priv->state.drawing_mode && code)
1727                 ass_drawing_add_char(drawing, (char) code);
1728         } while (code && render_priv->state.drawing_mode);      // skip everything in drawing mode
1729
1730         if (text_info->length >= text_info->max_glyphs) {
1731             // Raise maximum number of glyphs
1732             text_info->max_glyphs *= 2;
1733             text_info->glyphs = glyphs =
1734                 realloc(text_info->glyphs,
1735                         sizeof(GlyphInfo) * text_info->max_glyphs);
1736         }
1737
1738         // Clear current GlyphInfo
1739         memset(&glyphs[text_info->length], 0, sizeof(GlyphInfo));
1740
1741         // Parse drawing
1742         if (drawing->i) {
1743             drawing->scale_x = render_priv->state.scale_x *
1744                                      render_priv->font_scale;
1745             drawing->scale_y = render_priv->state.scale_y *
1746                                      render_priv->font_scale;
1747             p--;
1748             code = 0xfffc; // object replacement character
1749             glyphs[text_info->length].drawing = drawing;
1750         }
1751
1752         // face could have been changed in get_next_char
1753         if (!render_priv->state.font) {
1754             free_render_context(render_priv);
1755             return 1;
1756         }
1757
1758         if (code == 0)
1759             break;
1760
1761         // Fill glyph information
1762         glyphs[text_info->length].symbol = code;
1763         glyphs[text_info->length].font = render_priv->state.font;
1764         for (i = 0; i < 4; ++i) {
1765             uint32_t clr = render_priv->state.c[i];
1766             change_alpha(&clr,
1767                          mult_alpha(_a(clr), render_priv->state.fade), 1.);
1768             glyphs[text_info->length].c[i] = clr;
1769         }
1770         glyphs[text_info->length].effect_type = render_priv->state.effect_type;
1771         glyphs[text_info->length].effect_timing =
1772             render_priv->state.effect_timing;
1773         glyphs[text_info->length].effect_skip_timing =
1774             render_priv->state.effect_skip_timing;
1775         glyphs[text_info->length].font_size = ensure_font_size(render_priv,
1776                     render_priv->state.font_size * render_priv->font_scale);
1777         glyphs[text_info->length].be = render_priv->state.be;
1778         glyphs[text_info->length].blur = render_priv->state.blur;
1779         glyphs[text_info->length].shadow_x = render_priv->state.shadow_x;
1780         glyphs[text_info->length].shadow_y = render_priv->state.shadow_y;
1781         glyphs[text_info->length].scale_x= render_priv->state.scale_x;
1782         glyphs[text_info->length].scale_y = render_priv->state.scale_y;
1783         glyphs[text_info->length].border_x= render_priv->state.border_x;
1784         glyphs[text_info->length].border_y = render_priv->state.border_y;
1785         glyphs[text_info->length].bold = render_priv->state.bold;
1786         glyphs[text_info->length].italic = render_priv->state.italic;
1787         glyphs[text_info->length].flags = render_priv->state.flags;
1788         glyphs[text_info->length].frx = render_priv->state.frx;
1789         glyphs[text_info->length].fry = render_priv->state.fry;
1790         glyphs[text_info->length].frz = render_priv->state.frz;
1791         glyphs[text_info->length].fax = render_priv->state.fax;
1792         glyphs[text_info->length].fay = render_priv->state.fay;
1793         glyphs[text_info->length].bm_run_id = render_priv->state.bm_run_id;
1794
1795         if (glyphs[text_info->length].drawing) {
1796             drawing = render_priv->state.drawing =
1797                 ass_drawing_new(render_priv->library, render_priv->ftlibrary);
1798         }
1799
1800         text_info->length++;
1801
1802         render_priv->state.effect_type = EF_NONE;
1803         render_priv->state.effect_timing = 0;
1804         render_priv->state.effect_skip_timing = 0;
1805
1806     }
1807
1808     if (text_info->length == 0) {
1809         // no valid symbols in the event; this can be smth like {comment}
1810         free_render_context(render_priv);
1811         return 1;
1812     }
1813
1814     // Find shape runs and shape text
1815     ass_shaper_set_base_direction(render_priv->shaper,
1816             resolve_base_direction(render_priv->state.font_encoding));
1817     ass_shaper_find_runs(render_priv->shaper, render_priv, glyphs,
1818             text_info->length);
1819     ass_shaper_shape(render_priv->shaper, text_info);
1820
1821     // Retrieve glyphs
1822     for (i = 0; i < text_info->length; i++) {
1823         GlyphInfo *info = glyphs + i;
1824         while (info) {
1825             get_outline_glyph(render_priv, info);
1826             info = info->next;
1827         }
1828         info = glyphs + i;
1829
1830         // Add additional space after italic to non-italic style changes
1831         if (i && glyphs[i - 1].italic && !info->italic) {
1832             int back = i - 1;
1833             GlyphInfo *og = &glyphs[back];
1834             while (back && og->bbox.xMax - og->bbox.xMin == 0
1835                     && og->italic)
1836                 og = &glyphs[--back];
1837             if (og->bbox.xMax > og->cluster_advance.x)
1838                 og->cluster_advance.x = og->bbox.xMax;
1839         }
1840
1841         // add horizontal letter spacing
1842         info->cluster_advance.x += double_to_d6(render_priv->state.hspacing *
1843                 render_priv->font_scale * info->scale_x);
1844
1845         // add displacement for vertical shearing
1846         info->cluster_advance.y += (info->fay * info->scale_y) * info->cluster_advance.x;
1847
1848     }
1849
1850     // Preliminary layout (for line wrapping)
1851     previous = 0;
1852     pen.x = 0;
1853     pen.y = 0;
1854     for (i = 0; i < text_info->length; i++) {
1855         GlyphInfo *info = glyphs + i;
1856         FT_Vector cluster_pen = pen;
1857         while (info) {
1858             info->pos.x = cluster_pen.x;
1859             info->pos.y = cluster_pen.y;
1860
1861             cluster_pen.x += info->advance.x;
1862             cluster_pen.y += info->advance.y;
1863
1864             // fill bitmap hash
1865             info->hash_key.type = BITMAP_OUTLINE;
1866             fill_bitmap_hash(render_priv, info, &info->hash_key.u.outline);
1867
1868             info = info->next;
1869         }
1870         info = glyphs + i;
1871         pen.x += info->cluster_advance.x;
1872         pen.y += info->cluster_advance.y;
1873         previous = info->symbol;
1874     }
1875
1876
1877     // depends on glyph x coordinates being monotonous, so it should be done before line wrap
1878     process_karaoke_effects(render_priv);
1879
1880     // alignments
1881     alignment = render_priv->state.alignment;
1882     halign = alignment & 3;
1883     valign = alignment & 12;
1884
1885     MarginL =
1886         (event->MarginL) ? event->MarginL : render_priv->state.style->MarginL;
1887     MarginR =
1888         (event->MarginR) ? event->MarginR : render_priv->state.style->MarginR;
1889     MarginV =
1890         (event->MarginV) ? event->MarginV : render_priv->state.style->MarginV;
1891
1892     // calculate max length of a line
1893     max_text_width =
1894         x2scr(render_priv, render_priv->track->PlayResX - MarginR) -
1895         x2scr(render_priv, MarginL);
1896
1897     // wrap lines
1898     if (render_priv->state.evt_type != EVENT_HSCROLL) {
1899         // rearrange text in several lines
1900         wrap_lines_smart(render_priv, max_text_width);
1901     } else {
1902         // no breaking or wrapping, everything in a single line
1903         text_info->lines[0].offset = 0;
1904         text_info->lines[0].len = text_info->length;
1905         text_info->n_lines = 1;
1906         measure_text(render_priv);
1907     }
1908
1909     // Reorder text into visual order
1910     cmap = ass_shaper_reorder(render_priv->shaper, text_info);
1911
1912     // Reposition according to the map
1913     pen.x = 0;
1914     pen.y = 0;
1915     for (i = 0; i < text_info->length; i++) {
1916         GlyphInfo *info = glyphs + cmap[i];
1917         FT_Vector cluster_pen;
1918         if (glyphs[i].linebreak) {
1919             pen.x = 0;
1920             pen.y += double_to_d6(text_info->lines[lineno-1].desc);
1921             pen.y += double_to_d6(text_info->lines[lineno].asc);
1922             pen.y += double_to_d6(render_priv->settings.line_spacing);
1923             lineno++;
1924         }
1925         if (info->skip) continue;
1926         cluster_pen = pen;
1927         while (info) {
1928             info->pos.x = info->offset.x + cluster_pen.x;
1929             info->pos.y = info->offset.y + cluster_pen.y;
1930             cluster_pen.x += info->advance.x;
1931             cluster_pen.y += info->advance.y;
1932             info = info->next;
1933         }
1934         info = glyphs + cmap[i];
1935         pen.x += info->cluster_advance.x;
1936         pen.y += info->cluster_advance.y;
1937     }
1938
1939     // align lines
1940     if (render_priv->state.evt_type != EVENT_HSCROLL) {
1941         double width = 0;
1942         last_break = -1;
1943         for (i = 0; i <= text_info->length; ++i) {   // (text_info->length + 1) is the end of the last line
1944             if ((i == text_info->length) || glyphs[i].linebreak) {
1945                 double shift = 0;
1946                 // remove letter spacing (which is included in cluster_advance)
1947                 if (i > 0)
1948                     width -= render_priv->state.hspacing * render_priv->font_scale *
1949                         glyphs[i-1].scale_x;
1950                 if (halign == HALIGN_LEFT) {    // left aligned, no action
1951                     shift = 0;
1952                 } else if (halign == HALIGN_RIGHT) {    // right aligned
1953                     shift = max_text_width - width;
1954                 } else if (halign == HALIGN_CENTER) {   // centered
1955                     shift = (max_text_width - width) / 2.0;
1956                 }
1957                 for (j = last_break + 1; j < i; ++j) {
1958                     GlyphInfo *info = glyphs + j;
1959                     while (info) {
1960                         info->pos.x += double_to_d6(shift);
1961                         info = info->next;
1962                     }
1963                 }
1964                 last_break = i - 1;
1965                 width = 0;
1966             }
1967             if (i < text_info->length && !glyphs[i].skip &&
1968                     glyphs[i].symbol != '\n' && glyphs[i].symbol != 0) {
1969                 width += d6_to_double(glyphs[i].cluster_advance.x);
1970             }
1971         }
1972     }
1973
1974     // determing text bounding box
1975     compute_string_bbox(text_info, &bbox);
1976
1977     // determine device coordinates for text
1978
1979     // x coordinate for everything except positioned events
1980     if (render_priv->state.evt_type == EVENT_NORMAL ||
1981         render_priv->state.evt_type == EVENT_VSCROLL) {
1982         device_x = x2scr(render_priv, MarginL);
1983     } else if (render_priv->state.evt_type == EVENT_HSCROLL) {
1984         if (render_priv->state.scroll_direction == SCROLL_RL)
1985             device_x =
1986                 x2scr(render_priv,
1987                       render_priv->track->PlayResX -
1988                       render_priv->state.scroll_shift);
1989         else if (render_priv->state.scroll_direction == SCROLL_LR)
1990             device_x =
1991                 x2scr(render_priv,
1992                       render_priv->state.scroll_shift) - (bbox.xMax -
1993                                                           bbox.xMin);
1994     }
1995
1996     // y coordinate for everything except positioned events
1997     if (render_priv->state.evt_type == EVENT_NORMAL ||
1998         render_priv->state.evt_type == EVENT_HSCROLL) {
1999         if (valign == VALIGN_TOP) {     // toptitle
2000             device_y =
2001                 y2scr_top(render_priv,
2002                           MarginV) + text_info->lines[0].asc;
2003         } else if (valign == VALIGN_CENTER) {   // midtitle
2004             double scr_y =
2005                 y2scr(render_priv, render_priv->track->PlayResY / 2.0);
2006             device_y = scr_y - (bbox.yMax + bbox.yMin) / 2.0;
2007         } else {                // subtitle
2008             double scr_y;
2009             if (valign != VALIGN_SUB)
2010                 ass_msg(render_priv->library, MSGL_V,
2011                        "Invalid valign, assuming 0 (subtitle)");
2012             scr_y =
2013                 y2scr_sub(render_priv,
2014                           render_priv->track->PlayResY - MarginV);
2015             device_y = scr_y;
2016             device_y -= text_info->height;
2017             device_y += text_info->lines[0].asc;
2018         }
2019     } else if (render_priv->state.evt_type == EVENT_VSCROLL) {
2020         if (render_priv->state.scroll_direction == SCROLL_TB)
2021             device_y =
2022                 y2scr(render_priv,
2023                       render_priv->state.clip_y0 +
2024                       render_priv->state.scroll_shift) - (bbox.yMax -
2025                                                           bbox.yMin);
2026         else if (render_priv->state.scroll_direction == SCROLL_BT)
2027             device_y =
2028                 y2scr(render_priv,
2029                       render_priv->state.clip_y1 -
2030                       render_priv->state.scroll_shift);
2031     }
2032
2033     // positioned events are totally different
2034     if (render_priv->state.evt_type == EVENT_POSITIONED) {
2035         double base_x = 0;
2036         double base_y = 0;
2037         ass_msg(render_priv->library, MSGL_DBG2, "positioned event at %f, %f",
2038                render_priv->state.pos_x, render_priv->state.pos_y);
2039         get_base_point(&bbox, alignment, &base_x, &base_y);
2040         device_x =
2041             x2scr_pos(render_priv, render_priv->state.pos_x) - base_x;
2042         device_y =
2043             y2scr_pos(render_priv, render_priv->state.pos_y) - base_y;
2044     }
2045
2046     // fix clip coordinates (they depend on alignment)
2047     if (render_priv->state.evt_type == EVENT_NORMAL ||
2048         render_priv->state.evt_type == EVENT_HSCROLL ||
2049         render_priv->state.evt_type == EVENT_VSCROLL) {
2050         render_priv->state.clip_x0 =
2051             x2scr_scaled(render_priv, render_priv->state.clip_x0);
2052         render_priv->state.clip_x1 =
2053             x2scr_scaled(render_priv, render_priv->state.clip_x1);
2054         if (valign == VALIGN_TOP) {
2055             render_priv->state.clip_y0 =
2056                 y2scr_top(render_priv, render_priv->state.clip_y0);
2057             render_priv->state.clip_y1 =
2058                 y2scr_top(render_priv, render_priv->state.clip_y1);
2059         } else if (valign == VALIGN_CENTER) {
2060             render_priv->state.clip_y0 =
2061                 y2scr(render_priv, render_priv->state.clip_y0);
2062             render_priv->state.clip_y1 =
2063                 y2scr(render_priv, render_priv->state.clip_y1);
2064         } else if (valign == VALIGN_SUB) {
2065             render_priv->state.clip_y0 =
2066                 y2scr_sub(render_priv, render_priv->state.clip_y0);
2067             render_priv->state.clip_y1 =
2068                 y2scr_sub(render_priv, render_priv->state.clip_y1);
2069         }
2070     } else if (render_priv->state.evt_type == EVENT_POSITIONED) {
2071         render_priv->state.clip_x0 =
2072             x2scr_pos_scaled(render_priv, render_priv->state.clip_x0);
2073         render_priv->state.clip_x1 =
2074             x2scr_pos_scaled(render_priv, render_priv->state.clip_x1);
2075         render_priv->state.clip_y0 =
2076             y2scr_pos(render_priv, render_priv->state.clip_y0);
2077         render_priv->state.clip_y1 =
2078             y2scr_pos(render_priv, render_priv->state.clip_y1);
2079     }
2080
2081     // calculate rotation parameters
2082     {
2083         DVector center;
2084
2085         if (render_priv->state.have_origin) {
2086             center.x = x2scr(render_priv, render_priv->state.org_x);
2087             center.y = y2scr(render_priv, render_priv->state.org_y);
2088         } else {
2089             double bx = 0., by = 0.;
2090             get_base_point(&bbox, alignment, &bx, &by);
2091             center.x = device_x + bx;
2092             center.y = device_y + by;
2093         }
2094
2095         for (i = 0; i < text_info->length; ++i) {
2096             GlyphInfo *info = glyphs + i;
2097             while (info) {
2098                 OutlineBitmapHashKey *key = &info->hash_key.u.outline;
2099
2100                 if (key->frx || key->fry || key->frz || key->fax || key->fay) {
2101                     key->shift_x = info->pos.x + double_to_d6(device_x - center.x);
2102                     key->shift_y = -(info->pos.y + double_to_d6(device_y - center.y));
2103                 } else {
2104                     key->shift_x = 0;
2105                     key->shift_y = 0;
2106                 }
2107                 info = info->next;
2108             }
2109         }
2110     }
2111
2112     // convert glyphs to bitmaps
2113     left = render_priv->settings.left_margin;
2114     device_x = (device_x - left) * render_priv->font_scale_x + left;
2115     for (i = 0; i < text_info->length; ++i) {
2116         GlyphInfo *info = glyphs + i;
2117         while (info) {
2118             OutlineBitmapHashKey *key = &info->hash_key.u.outline;
2119             info->pos.x *= render_priv->font_scale_x;
2120             key->advance.x =
2121                 double_to_d6(device_x - (int) device_x +
2122                         d6_to_double(info->pos.x & SUBPIXEL_MASK)) & ~SUBPIXEL_ACCURACY;
2123             key->advance.y =
2124                 double_to_d6(device_y - (int) device_y +
2125                         d6_to_double(info->pos.y & SUBPIXEL_MASK)) & ~SUBPIXEL_ACCURACY;
2126             get_bitmap_glyph(render_priv, info);
2127             info = info->next;
2128         }
2129     }
2130
2131     memset(event_images, 0, sizeof(*event_images));
2132     event_images->top = device_y - text_info->lines[0].asc;
2133     event_images->height = text_info->height;
2134     event_images->left =
2135         (device_x + bbox.xMin * render_priv->font_scale_x) + 0.5;
2136     event_images->width =
2137         (bbox.xMax - bbox.xMin) * render_priv->font_scale_x + 0.5;
2138     event_images->detect_collisions = render_priv->state.detect_collisions;
2139     event_images->shift_direction = (valign == VALIGN_TOP) ? 1 : -1;
2140     event_images->event = event;
2141     event_images->imgs = render_text(render_priv, (int) device_x, (int) device_y);
2142
2143     ass_shaper_cleanup(render_priv->shaper, text_info);
2144     free_render_context(render_priv);
2145
2146     return 0;
2147 }
2148
2149 /**
2150  * \brief deallocate image list
2151  * \param img list pointer
2152  */
2153 void ass_free_images(ASS_Image *img)
2154 {
2155     while (img) {
2156         ASS_Image *next = img->next;
2157         free(img);
2158         img = next;
2159     }
2160 }
2161
2162 /**
2163  * \brief Check cache limits and reset cache if they are exceeded
2164  */
2165 static void check_cache_limits(ASS_Renderer *priv, CacheStore *cache)
2166 {
2167     if (ass_cache_empty(cache->bitmap_cache, cache->bitmap_max_size)) {
2168         ass_cache_empty(cache->composite_cache, 0);
2169         ass_free_images(priv->prev_images_root);
2170         priv->prev_images_root = 0;
2171     }
2172     if (ass_cache_empty(cache->outline_cache, cache->glyph_max)) {
2173         ass_cache_empty(cache->bitmap_cache, 0);
2174         ass_cache_empty(cache->composite_cache, 0);
2175         ass_free_images(priv->prev_images_root);
2176         priv->prev_images_root = 0;
2177     }
2178 }
2179
2180 /**
2181  * \brief Start a new frame
2182  */
2183 static int
2184 ass_start_frame(ASS_Renderer *render_priv, ASS_Track *track,
2185                 long long now)
2186 {
2187     ASS_Settings *settings_priv = &render_priv->settings;
2188
2189     if (!render_priv->settings.frame_width
2190         && !render_priv->settings.frame_height)
2191         return 1;               // library not initialized
2192
2193     if (render_priv->library != track->library)
2194         return 1;
2195
2196     if (!render_priv->fontconfig_priv)
2197         return 1;
2198
2199     free_list_clear(render_priv);
2200
2201     if (track->n_events == 0)
2202         return 1;               // nothing to do
2203
2204     render_priv->track = track;
2205     render_priv->time = now;
2206
2207     ass_lazy_track_init(render_priv->library, render_priv->track);
2208
2209     render_priv->font_scale = settings_priv->font_size_coeff *
2210         render_priv->orig_height / render_priv->track->PlayResY;
2211     if (render_priv->track->ScaledBorderAndShadow)
2212         render_priv->border_scale =
2213             ((double) render_priv->orig_height) /
2214             render_priv->track->PlayResY;
2215     else
2216         render_priv->border_scale = 1.;
2217
2218     ass_shaper_set_kerning(render_priv->shaper, track->Kerning);
2219     if (track->Language)
2220         ass_shaper_set_language(render_priv->shaper, track->Language);
2221     ass_shaper_set_level(render_priv->shaper, render_priv->settings.shaper);
2222
2223     // PAR correction
2224     render_priv->font_scale_x = render_priv->settings.aspect /
2225                                 render_priv->settings.storage_aspect;
2226
2227     render_priv->prev_images_root = render_priv->images_root;
2228     render_priv->images_root = 0;
2229
2230     check_cache_limits(render_priv, &render_priv->cache);
2231
2232     return 0;
2233 }
2234
2235 static int cmp_event_layer(const void *p1, const void *p2)
2236 {
2237     ASS_Event *e1 = ((EventImages *) p1)->event;
2238     ASS_Event *e2 = ((EventImages *) p2)->event;
2239     if (e1->Layer < e2->Layer)
2240         return -1;
2241     if (e1->Layer > e2->Layer)
2242         return 1;
2243     if (e1->ReadOrder < e2->ReadOrder)
2244         return -1;
2245     if (e1->ReadOrder > e2->ReadOrder)
2246         return 1;
2247     return 0;
2248 }
2249
2250 static ASS_RenderPriv *get_render_priv(ASS_Renderer *render_priv,
2251                                        ASS_Event *event)
2252 {
2253     if (!event->render_priv)
2254         event->render_priv = calloc(1, sizeof(ASS_RenderPriv));
2255     if (render_priv->render_id != event->render_priv->render_id) {
2256         memset(event->render_priv, 0, sizeof(ASS_RenderPriv));
2257         event->render_priv->render_id = render_priv->render_id;
2258     }
2259
2260     return event->render_priv;
2261 }
2262
2263 static int overlap(Segment *s1, Segment *s2)
2264 {
2265     if (s1->a >= s2->b || s2->a >= s1->b ||
2266         s1->ha >= s2->hb || s2->ha >= s1->hb)
2267         return 0;
2268     return 1;
2269 }
2270
2271 static int cmp_segment(const void *p1, const void *p2)
2272 {
2273     return ((Segment *) p1)->a - ((Segment *) p2)->a;
2274 }
2275
2276 static void
2277 shift_event(ASS_Renderer *render_priv, EventImages *ei, int shift)
2278 {
2279     ASS_Image *cur = ei->imgs;
2280     while (cur) {
2281         cur->dst_y += shift;
2282         // clip top and bottom
2283         if (cur->dst_y < 0) {
2284             int clip = -cur->dst_y;
2285             cur->h -= clip;
2286             cur->bitmap += clip * cur->stride;
2287             cur->dst_y = 0;
2288         }
2289         if (cur->dst_y + cur->h >= render_priv->height) {
2290             int clip = cur->dst_y + cur->h - render_priv->height;
2291             cur->h -= clip;
2292         }
2293         if (cur->h <= 0) {
2294             cur->h = 0;
2295             cur->dst_y = 0;
2296         }
2297         cur = cur->next;
2298     }
2299     ei->top += shift;
2300 }
2301
2302 // dir: 1 - move down
2303 //      -1 - move up
2304 static int fit_segment(Segment *s, Segment *fixed, int *cnt, int dir)
2305 {
2306     int i;
2307     int shift = 0;
2308
2309     if (dir == 1)               // move down
2310         for (i = 0; i < *cnt; ++i) {
2311             if (s->b + shift <= fixed[i].a || s->a + shift >= fixed[i].b ||
2312                 s->hb <= fixed[i].ha || s->ha >= fixed[i].hb)
2313                 continue;
2314             shift = fixed[i].b - s->a;
2315     } else                      // dir == -1, move up
2316         for (i = *cnt - 1; i >= 0; --i) {
2317             if (s->b + shift <= fixed[i].a || s->a + shift >= fixed[i].b ||
2318                 s->hb <= fixed[i].ha || s->ha >= fixed[i].hb)
2319                 continue;
2320             shift = fixed[i].a - s->b;
2321         }
2322
2323     fixed[*cnt].a = s->a + shift;
2324     fixed[*cnt].b = s->b + shift;
2325     fixed[*cnt].ha = s->ha;
2326     fixed[*cnt].hb = s->hb;
2327     (*cnt)++;
2328     qsort(fixed, *cnt, sizeof(Segment), cmp_segment);
2329
2330     return shift;
2331 }
2332
2333 static void
2334 fix_collisions(ASS_Renderer *render_priv, EventImages *imgs, int cnt)
2335 {
2336     Segment *used = malloc(cnt * sizeof(*used));
2337     int cnt_used = 0;
2338     int i, j;
2339
2340     // fill used[] with fixed events
2341     for (i = 0; i < cnt; ++i) {
2342         ASS_RenderPriv *priv;
2343         if (!imgs[i].detect_collisions)
2344             continue;
2345         priv = get_render_priv(render_priv, imgs[i].event);
2346         if (priv->height > 0) { // it's a fixed event
2347             Segment s;
2348             s.a = priv->top;
2349             s.b = priv->top + priv->height;
2350             s.ha = priv->left;
2351             s.hb = priv->left + priv->width;
2352             if (priv->height != imgs[i].height) {       // no, it's not
2353                 ass_msg(render_priv->library, MSGL_WARN,
2354                         "Event height has changed");
2355                 priv->top = 0;
2356                 priv->height = 0;
2357                 priv->left = 0;
2358                 priv->width = 0;
2359             }
2360             for (j = 0; j < cnt_used; ++j)
2361                 if (overlap(&s, used + j)) {    // no, it's not
2362                     priv->top = 0;
2363                     priv->height = 0;
2364                     priv->left = 0;
2365                     priv->width = 0;
2366                 }
2367             if (priv->height > 0) {     // still a fixed event
2368                 used[cnt_used].a = priv->top;
2369                 used[cnt_used].b = priv->top + priv->height;
2370                 used[cnt_used].ha = priv->left;
2371                 used[cnt_used].hb = priv->left + priv->width;
2372                 cnt_used++;
2373                 shift_event(render_priv, imgs + i, priv->top - imgs[i].top);
2374             }
2375         }
2376     }
2377     qsort(used, cnt_used, sizeof(Segment), cmp_segment);
2378
2379     // try to fit other events in free spaces
2380     for (i = 0; i < cnt; ++i) {
2381         ASS_RenderPriv *priv;
2382         if (!imgs[i].detect_collisions)
2383             continue;
2384         priv = get_render_priv(render_priv, imgs[i].event);
2385         if (priv->height == 0) {        // not a fixed event
2386             int shift;
2387             Segment s;
2388             s.a = imgs[i].top;
2389             s.b = imgs[i].top + imgs[i].height;
2390             s.ha = imgs[i].left;
2391             s.hb = imgs[i].left + imgs[i].width;
2392             shift = fit_segment(&s, used, &cnt_used, imgs[i].shift_direction);
2393             if (shift)
2394                 shift_event(render_priv, imgs + i, shift);
2395             // make it fixed
2396             priv->top = imgs[i].top;
2397             priv->height = imgs[i].height;
2398             priv->left = imgs[i].left;
2399             priv->width = imgs[i].width;
2400         }
2401
2402     }
2403
2404     free(used);
2405 }
2406
2407 /**
2408  * \brief compare two images
2409  * \param i1 first image
2410  * \param i2 second image
2411  * \return 0 if identical, 1 if different positions, 2 if different content
2412  */
2413 static int ass_image_compare(ASS_Image *i1, ASS_Image *i2)
2414 {
2415     if (i1->w != i2->w)
2416         return 2;
2417     if (i1->h != i2->h)
2418         return 2;
2419     if (i1->stride != i2->stride)
2420         return 2;
2421     if (i1->color != i2->color)
2422         return 2;
2423     if (i1->bitmap != i2->bitmap)
2424         return 2;
2425     if (i1->dst_x != i2->dst_x)
2426         return 1;
2427     if (i1->dst_y != i2->dst_y)
2428         return 1;
2429     return 0;
2430 }
2431
2432 /**
2433  * \brief compare current and previous image list
2434  * \param priv library handle
2435  * \return 0 if identical, 1 if different positions, 2 if different content
2436  */
2437 static int ass_detect_change(ASS_Renderer *priv)
2438 {
2439     ASS_Image *img, *img2;
2440     int diff;
2441
2442     img = priv->prev_images_root;
2443     img2 = priv->images_root;
2444     diff = 0;
2445     while (img && diff < 2) {
2446         ASS_Image *next, *next2;
2447         next = img->next;
2448         if (img2) {
2449             int d = ass_image_compare(img, img2);
2450             if (d > diff)
2451                 diff = d;
2452             next2 = img2->next;
2453         } else {
2454             // previous list is shorter
2455             diff = 2;
2456             break;
2457         }
2458         img = next;
2459         img2 = next2;
2460     }
2461
2462     // is the previous list longer?
2463     if (img2)
2464         diff = 2;
2465
2466     return diff;
2467 }
2468
2469 /**
2470  * \brief render a frame
2471  * \param priv library handle
2472  * \param track track
2473  * \param now current video timestamp (ms)
2474  * \param detect_change a value describing how the new images differ from the previous ones will be written here:
2475  *        0 if identical, 1 if different positions, 2 if different content.
2476  *        Can be NULL, in that case no detection is performed.
2477  */
2478 ASS_Image *ass_render_frame(ASS_Renderer *priv, ASS_Track *track,
2479                             long long now, int *detect_change)
2480 {
2481     int i, cnt, rc;
2482     EventImages *last;
2483     ASS_Image **tail;
2484
2485     // init frame
2486     rc = ass_start_frame(priv, track, now);
2487     if (rc != 0)
2488         return 0;
2489
2490     // render events separately
2491     cnt = 0;
2492     for (i = 0; i < track->n_events; ++i) {
2493         ASS_Event *event = track->events + i;
2494         if ((event->Start <= now)
2495             && (now < (event->Start + event->Duration))) {
2496             if (cnt >= priv->eimg_size) {
2497                 priv->eimg_size += 100;
2498                 priv->eimg =
2499                     realloc(priv->eimg,
2500                             priv->eimg_size * sizeof(EventImages));
2501             }
2502             rc = ass_render_event(priv, event, priv->eimg + cnt);
2503             if (!rc)
2504                 ++cnt;
2505         }
2506     }
2507
2508     // sort by layer
2509     qsort(priv->eimg, cnt, sizeof(EventImages), cmp_event_layer);
2510
2511     // call fix_collisions for each group of events with the same layer
2512     last = priv->eimg;
2513     for (i = 1; i < cnt; ++i)
2514         if (last->event->Layer != priv->eimg[i].event->Layer) {
2515             fix_collisions(priv, last, priv->eimg + i - last);
2516             last = priv->eimg + i;
2517         }
2518     if (cnt > 0)
2519         fix_collisions(priv, last, priv->eimg + cnt - last);
2520
2521     // concat lists
2522     tail = &priv->images_root;
2523     for (i = 0; i < cnt; ++i) {
2524         ASS_Image *cur = priv->eimg[i].imgs;
2525         while (cur) {
2526             *tail = cur;
2527             tail = &cur->next;
2528             cur = cur->next;
2529         }
2530     }
2531
2532     if (detect_change)
2533         *detect_change = ass_detect_change(priv);
2534
2535     // free the previous image list
2536     ass_free_images(priv->prev_images_root);
2537     priv->prev_images_root = 0;
2538
2539     return priv->images_root;
2540 }