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