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