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