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