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