granicus.if.org Git - libass/blob - libass/ass_render.c

   1 // -*- c-basic-offset: 8; indent-tabs-mode: t -*-
   2 // vim:ts=8:sw=8:noet:ai:
   3 /*
   4   Copyright (C) 2006 Evgeniy Stepanov <eugeni.stepanov@gmail.com>
   5
   6   This program is free software; you can redistribute it and/or modify
   7   it under the terms of the GNU General Public License as published by
   8   the Free Software Foundation; either version 2 of the License, or
   9   (at your option) any later version.
  10
  11   This program is distributed in the hope that it will be useful,
  12   but WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14   GNU General Public License for more details.
  15
  16   You should have received a copy of the GNU General Public License
  17   along with this program; if not, write to the Free Software
  18   Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
  19 */
  20
  21 #include "config.h"
  22
  23 #include <assert.h>
  24 #include <math.h>
  25 #include <inttypes.h>
  26 #include <ft2build.h>
  27 #include FT_FREETYPE_H
  28 #include FT_STROKER_H
  29 #include FT_GLYPH_H
  30 #include FT_SYNTHESIS_H
  31
  32 #include "mputils.h"
  33
  34 #include "ass.h"
  35 #include "ass_bitmap.h"
  36 #include "ass_cache.h"
  37 #include "ass_utils.h"
  38 #include "ass_fontconfig.h"
  39 #include "ass_library.h"
  40 #include "ass_font.h"
  41
  42 #define MAX_GLYPHS 1000
  43 #define MAX_LINES 100
  44
  45 static int last_render_id = 0;
  46
  47 typedef struct ass_settings_s {
  48         int frame_width;
  49         int frame_height;
  50         double font_size_coeff; // font size multiplier
  51         double line_spacing; // additional line spacing (in frame pixels)
  52         int top_margin; // height of top margin. Everything except toptitles is shifted down by top_margin.
  53         int bottom_margin; // height of bottom margin. (frame_height - top_margin - bottom_margin) is original video height.
  54         int left_margin;
  55         int right_margin;
  56         int use_margins; // 0 - place all subtitles inside original frame
  57                          // 1 - use margins for placing toptitles and subtitles
  58         double aspect; // frame aspect ratio, d_width / d_height.
  59
  60         char* default_font;
  61         char* default_family;
  62 } ass_settings_t;
  63
  64 struct ass_renderer_s {
  65         ass_library_t* library;
  66         FT_Library ftlibrary;
  67         fc_instance_t* fontconfig_priv;
  68         ass_settings_t settings;
  69         int render_id;
  70         ass_synth_priv_t* synth_priv;
  71
  72         ass_image_t* images_root; // rendering result is stored here
  73 };
  74
  75 typedef enum {EF_NONE = 0, EF_KARAOKE, EF_KARAOKE_KF, EF_KARAOKE_KO} effect_t;
  76
  77 // describes a glyph
  78 // glyph_info_t and text_info_t are used for text centering and word-wrapping operations
  79 typedef struct glyph_info_s {
  80         unsigned symbol;
  81         FT_Glyph glyph;
  82         FT_Glyph outline_glyph;
  83         bitmap_t* bm; // glyph bitmap
  84         bitmap_t* bm_o; // outline bitmap
  85         bitmap_t* bm_s; // shadow bitmap
  86         FT_BBox bbox;
  87         FT_Vector pos;
  88         char linebreak; // the first (leading) glyph of some line ?
  89         uint32_t c[4]; // colors
  90         FT_Vector advance; // 26.6
  91         effect_t effect_type;
  92         int effect_timing; // time duration of current karaoke word
  93                            // after process_karaoke_effects: distance in pixels from the glyph origin.
  94                            // part of the glyph to the left of it is displayed in a different color.
  95         int effect_skip_timing; // delay after the end of last karaoke word
  96         int asc, desc; // font max ascender and descender
  97 //      int height;
  98         int be; // blur edges
  99         int shadow;
 100         double frz; // z-axis rotation
 101
 102         glyph_hash_key_t hash_key;
 103 } glyph_info_t;
 104
 105 typedef struct line_info_s {
 106         int asc, desc;
 107 } line_info_t;
 108
 109 typedef struct text_info_s {
 110         glyph_info_t* glyphs;
 111         int length;
 112         line_info_t lines[MAX_LINES];
 113         int n_lines;
 114         int height;
 115 } text_info_t;
 116
 117
 118 // Renderer state.
 119 // Values like current font face, color, screen position, clipping and so on are stored here.
 120 typedef struct render_context_s {
 121         ass_event_t* event;
 122         ass_style_t* style;
 123
 124         ass_font_t* font;
 125         char* font_path;
 126         int font_size;
 127
 128         FT_Stroker stroker;
 129         int alignment; // alignment overrides go here; if zero, style value will be used
 130         double rotation;
 131         enum {  EVENT_NORMAL, // "normal" top-, sub- or mid- title
 132                 EVENT_POSITIONED, // happens after pos(,), margins are ignored
 133                 EVENT_HSCROLL, // "Banner" transition effect, text_width is unlimited
 134                 EVENT_VSCROLL // "Scroll up", "Scroll down" transition effects
 135                 } evt_type;
 136         int pos_x, pos_y; // position
 137         int org_x, org_y; // origin
 138         double scale_x, scale_y;
 139         int hspacing; // distance between letters, in pixels
 140         double border; // outline width
 141         uint32_t c[4]; // colors(Primary, Secondary, so on) in RGBA
 142         int clip_x0, clip_y0, clip_x1, clip_y1;
 143         char detect_collisions;
 144         uint32_t fade; // alpha from \fad
 145         char be; // blur edges
 146         int shadow;
 147
 148         effect_t effect_type;
 149         int effect_timing;
 150         int effect_skip_timing;
 151
 152         enum { SCROLL_LR, // left-to-right
 153                SCROLL_RL,
 154                SCROLL_TB, // top-to-bottom
 155                SCROLL_BT
 156                } scroll_direction; // for EVENT_HSCROLL, EVENT_VSCROLL
 157         int scroll_shift;
 158
 159         // face properties
 160         char* family;
 161         unsigned bold;
 162         unsigned italic;
 163
 164 } render_context_t;
 165
 166 // frame-global data
 167 typedef struct frame_context_s {
 168         ass_renderer_t* ass_priv;
 169         int width, height; // screen dimensions
 170         int orig_height; // frame height ( = screen height - margins )
 171         int orig_width; // frame width ( = screen width - margins )
 172         ass_track_t* track;
 173         long long time; // frame's timestamp, ms
 174         double font_scale;
 175         double font_scale_x; // x scale applied to all glyphs to preserve text aspect ratio
 176         double border_scale;
 177 } frame_context_t;
 178
 179 static ass_renderer_t* ass_renderer;
 180 static ass_settings_t* global_settings;
 181 static text_info_t text_info;
 182 static render_context_t render_context;
 183 static frame_context_t frame_context;
 184
 185 // a rendered event
 186 typedef struct event_images_s {
 187         ass_image_t* imgs;
 188         int top, height;
 189         int detect_collisions;
 190         int shift_direction;
 191         ass_event_t* event;
 192 } event_images_t;
 193
 194 struct render_priv_s {
 195         int top, height;
 196         int render_id;
 197 };
 198
 199 static void ass_lazy_track_init(void)
 200 {
 201         ass_track_t* track = frame_context.track;
 202         if (track->PlayResX && track->PlayResY)
 203                 return;
 204         if (!track->PlayResX && !track->PlayResY) {
 205                 mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_NeitherPlayResXNorPlayResYDefined);
 206                 track->PlayResX = 384;
 207                 track->PlayResY = 288;
 208         } else {
 209                 double orig_aspect = (global_settings->aspect * frame_context.height * frame_context.orig_width) /
 210                         frame_context.orig_height / frame_context.width;
 211                 if (!track->PlayResY) {
 212                         track->PlayResY = track->PlayResX / orig_aspect + .5;
 213                         mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_PlayResYUndefinedSettingY, track->PlayResY);
 214                 } else if (!track->PlayResX) {
 215                         track->PlayResX = track->PlayResY * orig_aspect + .5;
 216                         mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_PlayResXUndefinedSettingX, track->PlayResX);
 217                 }
 218         }
 219 }
 220
 221 ass_renderer_t* ass_renderer_init(ass_library_t* library)
 222 {
 223         int error;
 224         FT_Library ft;
 225         ass_renderer_t* priv = 0;
 226
 227         memset(&render_context, 0, sizeof(render_context));
 228         memset(&frame_context, 0, sizeof(frame_context));
 229         memset(&text_info, 0, sizeof(text_info));
 230
 231         error = FT_Init_FreeType( &ft );
 232         if ( error ) {
 233                 mp_msg(MSGT_ASS, MSGL_FATAL, MSGTR_LIBASS_FT_Init_FreeTypeFailed);
 234                 goto ass_init_exit;
 235         }
 236
 237         priv = calloc(1, sizeof(ass_renderer_t));
 238         if (!priv) {
 239                 FT_Done_FreeType(ft);
 240                 goto ass_init_exit;
 241         }
 242
 243         priv->synth_priv = ass_synth_init();
 244
 245         priv->library = library;
 246         priv->ftlibrary = ft;
 247         // images_root and related stuff is zero-filled in calloc
 248
 249         ass_font_cache_init();
 250         ass_glyph_cache_init();
 251
 252         text_info.glyphs = calloc(MAX_GLYPHS, sizeof(glyph_info_t));
 253
 254 ass_init_exit:
 255         if (priv) mp_msg(MSGT_ASS, MSGL_INFO, MSGTR_LIBASS_Init);
 256         else mp_msg(MSGT_ASS, MSGL_ERR, MSGTR_LIBASS_InitFailed);
 257
 258         return priv;
 259 }
 260
 261 void ass_renderer_done(ass_renderer_t* priv)
 262 {
 263         ass_font_cache_done();
 264         ass_glyph_cache_done();
 265         if (render_context.stroker) {
 266                 FT_Stroker_Done(render_context.stroker);
 267                 render_context.stroker = 0;
 268         }
 269         if (priv && priv->ftlibrary) FT_Done_FreeType(priv->ftlibrary);
 270         if (priv && priv->fontconfig_priv) fontconfig_done(priv->fontconfig_priv);
 271         if (priv && priv->synth_priv) ass_synth_done(priv->synth_priv);
 272         if (priv) free(priv);
 273         if (text_info.glyphs) free(text_info.glyphs);
 274 }
 275
 276 /**
 277  * \brief Create a new ass_image_t
 278  * Parameters are the same as ass_image_t fields.
 279  */
 280 static ass_image_t* my_draw_bitmap(unsigned char* bitmap, int bitmap_w, int bitmap_h, int stride, int dst_x, int dst_y, uint32_t color)
 281 {
 282         ass_image_t* img = calloc(1, sizeof(ass_image_t));
 283
 284         img->w = bitmap_w;
 285         img->h = bitmap_h;
 286         img->stride = stride;
 287         img->bitmap = bitmap;
 288         img->color = color;
 289         img->dst_x = dst_x;
 290         img->dst_y = dst_y;
 291
 292         return img;
 293 }
 294
 295 /**
 296  * \brief convert bitmap glyph into ass_image_t struct(s)
 297  * \param bit freetype bitmap glyph, FT_PIXEL_MODE_GRAY
 298  * \param dst_x bitmap x coordinate in video frame
 299  * \param dst_y bitmap y coordinate in video frame
 300  * \param color first color, RGBA
 301  * \param color2 second color, RGBA
 302  * \param brk x coordinate relative to glyph origin, color is used to the left of brk, color2 - to the right
 303  * \param tail pointer to the last image's next field, head of the generated list should be stored here
 304  * \return pointer to the new list tail
 305  * Performs clipping. Uses my_draw_bitmap for actual bitmap convertion.
 306  */
 307 static ass_image_t** render_glyph(bitmap_t* bm, int dst_x, int dst_y, uint32_t color, uint32_t color2, int brk, ass_image_t** tail)
 308 {
 309         // brk is relative to dst_x
 310         // color = color left of brk
 311         // color2 = color right of brk
 312         int b_x0, b_y0, b_x1, b_y1; // visible part of the bitmap
 313         int clip_x0, clip_y0, clip_x1, clip_y1;
 314         int tmp;
 315         ass_image_t* img;
 316
 317         dst_x += bm->left;
 318         dst_y += bm->top;
 319         brk -= bm->left;
 320
 321         // clipping
 322         clip_x0 = render_context.clip_x0;
 323         clip_y0 = render_context.clip_y0;
 324         clip_x1 = render_context.clip_x1;
 325         clip_y1 = render_context.clip_y1;
 326         b_x0 = 0;
 327         b_y0 = 0;
 328         b_x1 = bm->w;
 329         b_y1 = bm->h;
 330
 331         tmp = dst_x - clip_x0;
 332         if (tmp < 0) {
 333                 mp_msg(MSGT_ASS, MSGL_DBG2, "clip left\n");
 334                 b_x0 = - tmp;
 335         }
 336         tmp = dst_y - clip_y0;
 337         if (tmp < 0) {
 338                 mp_msg(MSGT_ASS, MSGL_DBG2, "clip top\n");
 339                 b_y0 = - tmp;
 340         }
 341         tmp = clip_x1 - dst_x - bm->w;
 342         if (tmp < 0) {
 343                 mp_msg(MSGT_ASS, MSGL_DBG2, "clip right\n");
 344                 b_x1 = bm->w + tmp;
 345         }
 346         tmp = clip_y1 - dst_y - bm->h;
 347         if (tmp < 0) {
 348                 mp_msg(MSGT_ASS, MSGL_DBG2, "clip bottom\n");
 349                 b_y1 = bm->h + tmp;
 350         }
 351
 352         if ((b_y0 >= b_y1) || (b_x0 >= b_x1))
 353                 return tail;
 354
 355         if (brk > b_x0) { // draw left part
 356                 if (brk > b_x1) brk = b_x1;
 357                 img = my_draw_bitmap(bm->buffer + bm->w * b_y0 + b_x0,
 358                         brk - b_x0, b_y1 - b_y0, bm->w,
 359                         dst_x + b_x0, dst_y + b_y0, color);
 360                 *tail = img;
 361                 tail = &img->next;
 362         }
 363         if (brk < b_x1) { // draw right part
 364                 if (brk < b_x0) brk = b_x0;
 365                 img = my_draw_bitmap(bm->buffer + bm->w * b_y0 + brk,
 366                         b_x1 - brk, b_y1 - b_y0, bm->w,
 367                         dst_x + brk, dst_y + b_y0, color2);
 368                 *tail = img;
 369                 tail = &img->next;
 370         }
 371         return tail;
 372 }
 373
 374 /**
 375  * \brief Render text_info_t struct into ass_images_t list
 376  * Rasterize glyphs and put them in glyph cache.
 377  */
 378 static ass_image_t* render_text(text_info_t* text_info, int dst_x, int dst_y)
 379 {
 380         int pen_x, pen_y;
 381         int i, error;
 382         bitmap_t* bm;
 383         glyph_hash_val_t hash_val;
 384         ass_image_t* head;
 385         ass_image_t** tail = &head;
 386
 387         for (i = 0; i < text_info->length; ++i) {
 388                 if (text_info->glyphs[i].glyph) {
 389                         if ((text_info->glyphs[i].symbol == '\n') || (text_info->glyphs[i].symbol == 0))
 390                                 continue;
 391                         error = glyph_to_bitmap(ass_renderer->synth_priv,
 392                                         text_info->glyphs[i].glyph, text_info->glyphs[i].outline_glyph,
 393                                         &text_info->glyphs[i].bm, &text_info->glyphs[i].bm_o,
 394                                         &text_info->glyphs[i].bm_s, text_info->glyphs[i].be);
 395                         if (error)
 396                                 text_info->glyphs[i].symbol = 0;
 397                         FT_Done_Glyph(text_info->glyphs[i].glyph);
 398                         if (text_info->glyphs[i].outline_glyph)
 399                                 FT_Done_Glyph(text_info->glyphs[i].outline_glyph);
 400
 401                         // cache
 402                         hash_val.bbox_scaled = text_info->glyphs[i].bbox;
 403                         hash_val.bm_o = text_info->glyphs[i].bm_o;
 404                         hash_val.bm = text_info->glyphs[i].bm;
 405                         hash_val.bm_s = text_info->glyphs[i].bm_s;
 406                         hash_val.advance.x = text_info->glyphs[i].advance.x;
 407                         hash_val.advance.y = text_info->glyphs[i].advance.y;
 408                         cache_add_glyph(&(text_info->glyphs[i].hash_key), &hash_val);
 409
 410                 }
 411         }
 412
 413         for (i = 0; i < text_info->length; ++i) {
 414                 glyph_info_t* info = text_info->glyphs + i;
 415                 if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm_s || (info->shadow == 0))
 416                         continue;
 417
 418                 pen_x = dst_x + info->pos.x + info->shadow;
 419                 pen_y = dst_y + info->pos.y + info->shadow;
 420                 bm = info->bm_s;
 421
 422                 tail = render_glyph(bm, pen_x, pen_y, info->c[3], 0, 1000000, tail);
 423         }
 424
 425         for (i = 0; i < text_info->length; ++i) {
 426                 glyph_info_t* info = text_info->glyphs + i;
 427                 if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm_o)
 428                         continue;
 429
 430                 pen_x = dst_x + info->pos.x;
 431                 pen_y = dst_y + info->pos.y;
 432                 bm = info->bm_o;
 433
 434                 if ((info->effect_type == EF_KARAOKE_KO) && (info->effect_timing <= info->bbox.xMax)) {
 435                         // do nothing
 436                 } else
 437                         tail = render_glyph(bm, pen_x, pen_y, info->c[2], 0, 1000000, tail);
 438         }
 439         for (i = 0; i < text_info->length; ++i) {
 440                 glyph_info_t* info = text_info->glyphs + i;
 441                 if ((info->symbol == 0) || (info->symbol == '\n') || !info->bm)
 442                         continue;
 443
 444                 pen_x = dst_x + info->pos.x;
 445                 pen_y = dst_y + info->pos.y;
 446                 bm = info->bm;
 447
 448                 if ((info->effect_type == EF_KARAOKE) || (info->effect_type == EF_KARAOKE_KO)) {
 449                         if (info->effect_timing > info->bbox.xMax)
 450                                 tail = render_glyph(bm, pen_x, pen_y, info->c[0], 0, 1000000, tail);
 451                         else
 452                                 tail = render_glyph(bm, pen_x, pen_y, info->c[1], 0, 1000000, tail);
 453                 } else if (info->effect_type == EF_KARAOKE_KF) {
 454                         tail = render_glyph(bm, pen_x, pen_y, info->c[0], info->c[1], info->effect_timing, tail);
 455                 } else
 456                         tail = render_glyph(bm, pen_x, pen_y, info->c[0], 0, 1000000, tail);
 457         }
 458
 459         *tail = 0;
 460         return head;
 461 }
 462
 463 /**
 464  * \brief Mapping between script and screen coordinates
 465  */
 466 static int x2scr(int x) {
 467         return x*frame_context.orig_width / frame_context.track->PlayResX + global_settings->left_margin;
 468 }
 469 /**
 470  * \brief Mapping between script and screen coordinates
 471  */
 472 static int y2scr(int y) {
 473         return y * frame_context.orig_height / frame_context.track->PlayResY + global_settings->top_margin;
 474 }
 475 // the same for toptitles
 476 static int y2scr_top(int y) {
 477         if (global_settings->use_margins)
 478                 return y * frame_context.orig_height / frame_context.track->PlayResY;
 479         else
 480                 return y * frame_context.orig_height / frame_context.track->PlayResY + global_settings->top_margin;
 481 }
 482 // the same for subtitles
 483 static int y2scr_sub(int y) {
 484         if (global_settings->use_margins)
 485                 return y * frame_context.orig_height / frame_context.track->PlayResY +
 486                        global_settings->top_margin + global_settings->bottom_margin;
 487         else
 488                 return y * frame_context.orig_height / frame_context.track->PlayResY + global_settings->top_margin;
 489 }
 490
 491 static void compute_string_bbox( text_info_t* info, FT_BBox *abbox ) {
 492         FT_BBox bbox;
 493         int i;
 494
 495         if (text_info.length > 0) {
 496                 bbox.xMin = 32000;
 497                 bbox.xMax = -32000;
 498                 bbox.yMin = - (text_info.lines[0].asc >> 6) + text_info.glyphs[0].pos.y;
 499                 bbox.yMax = ((text_info.height - text_info.lines[0].asc) >> 6) + text_info.glyphs[0].pos.y;
 500
 501                 for (i = 0; i < text_info.length; ++i) {
 502                         int s = text_info.glyphs[i].pos.x;
 503                         int e = s + (text_info.glyphs[i].advance.x >> 6);
 504                         bbox.xMin = FFMIN(bbox.xMin, s);
 505                         bbox.xMax = FFMAX(bbox.xMax, e);
 506                 }
 507         } else
 508                 bbox.xMin = bbox.xMax = bbox.yMin = bbox.yMax = 0;
 509
 510         /* return string bbox */
 511         *abbox = bbox;
 512 }
 513
 514
 515 /**
 516  * \brief Check if starting part of (*p) matches sample. If true, shift p to the first symbol after the matching part.
 517  */
 518 static inline int mystrcmp(char** p, const char* sample) {
 519         int len = strlen(sample);
 520         if (strncmp(*p, sample, len) == 0) {
 521                 (*p) += len;
 522                 return 1;
 523         } else
 524                 return 0;
 525 }
 526
 527 double ass_internal_font_size_coeff = 0.8;
 528
 529 static void change_font_size(int sz)
 530 {
 531         double size = sz * frame_context.font_scale;
 532
 533         if (size < 1)
 534                 size = 1;
 535         else if (size > frame_context.height * 2)
 536                 size = frame_context.height * 2;
 537
 538         ass_font_set_size(render_context.font, size);
 539
 540         render_context.font_size = sz;
 541 }
 542
 543 /**
 544  * \brief Change current font, using setting from render_context.
 545  */
 546 static void update_font(void)
 547 {
 548         unsigned val;
 549         ass_renderer_t* priv = frame_context.ass_priv;
 550         ass_font_desc_t desc;
 551         desc.family = strdup(render_context.family);
 552
 553         val = render_context.bold;
 554         // 0 = normal, 1 = bold, >1 = exact weight
 555         if (val == 0) val = 80; // normal
 556         else if (val == 1) val = 200; // bold
 557         desc.bold = val;
 558
 559         val = render_context.italic;
 560         if (val == 0) val = 0; // normal
 561         else if (val == 1) val = 110; //italic
 562         desc.italic = val;
 563
 564         render_context.font = ass_new_font(priv->ftlibrary, priv->fontconfig_priv, &desc);
 565
 566         if (render_context.font)
 567                 change_font_size(render_context.font_size);
 568 }
 569
 570 /**
 571  * \brief Change border width
 572  * negative value resets border to style value
 573  */
 574 static void change_border(double border)
 575 {
 576         int b;
 577         if (!render_context.font) return;
 578
 579         if (border < 0) {
 580                 if (render_context.style->BorderStyle == 1) {
 581                         if (render_context.style->Outline == 0 && render_context.style->Shadow > 0)
 582                                 border = 1.;
 583                         else
 584                                 border = render_context.style->Outline;
 585                 } else
 586                         border = 1.;
 587         }
 588         render_context.border = border;
 589
 590         b = 64 * border * frame_context.border_scale;
 591         if (b > 0) {
 592                 if (!render_context.stroker) {
 593                         int error;
 594 #if (FREETYPE_MAJOR > 2) || ((FREETYPE_MAJOR == 2) && (FREETYPE_MINOR > 1))
 595                         error = FT_Stroker_New( ass_renderer->ftlibrary, &render_context.stroker );
 596 #else // < 2.2
 597                         error = FT_Stroker_New( render_context.font->face->memory, &render_context.stroker );
 598 #endif
 599                         if (error) {
 600                                 mp_msg(MSGT_ASS, MSGL_V, "failed to get stroker\n");
 601                                 render_context.stroker = 0;
 602                         }
 603                 }
 604                 if (render_context.stroker)
 605                         FT_Stroker_Set( render_context.stroker, b,
 606                                         FT_STROKER_LINECAP_ROUND,
 607                                         FT_STROKER_LINEJOIN_ROUND,
 608                                         0 );
 609         } else {
 610                 FT_Stroker_Done(render_context.stroker);
 611                 render_context.stroker = 0;
 612         }
 613 }
 614
 615 #define _r(c)  ((c)>>24)
 616 #define _g(c)  (((c)>>16)&0xFF)
 617 #define _b(c)  (((c)>>8)&0xFF)
 618 #define _a(c)  ((c)&0xFF)
 619
 620 /**
 621  * \brief Calculate a weighted average of two colors
 622  * calculates c1*(1-a) + c2*a, but separately for each component except alpha
 623  */
 624 static void change_color(uint32_t* var, uint32_t new, double pwr)
 625 {
 626         (*var)= ((uint32_t)(_r(*var) * (1 - pwr) + _r(new) * pwr) << 24) +
 627                 ((uint32_t)(_g(*var) * (1 - pwr) + _g(new) * pwr) << 16) +
 628                 ((uint32_t)(_b(*var) * (1 - pwr) + _b(new) * pwr) << 8) +
 629                 _a(*var);
 630 }
 631
 632 // like change_color, but for alpha component only
 633 static void change_alpha(uint32_t* var, uint32_t new, double pwr)
 634 {
 635         *var = (_r(*var) << 24) + (_g(*var) << 16) + (_b(*var) << 8) + (_a(*var) * (1 - pwr) + _a(new) * pwr);
 636 }
 637
 638 /**
 639  * \brief Multiply two alpha values
 640  * \param a first value
 641  * \param b second value
 642  * \return result of multiplication
 643  * Parameters and result are limited by 0xFF.
 644  */
 645 static uint32_t mult_alpha(uint32_t a, uint32_t b)
 646 {
 647         return 0xFF - (0xFF - a) * (0xFF - b) / 0xFF;
 648 }
 649
 650 /**
 651  * \brief Calculate alpha value by piecewise linear function
 652  * Used for \fad, \fade implementation.
 653  */
 654 static unsigned interpolate_alpha(long long now,
 655                 long long t1, long long t2, long long t3, long long t4,
 656                 unsigned a1, unsigned a2, unsigned a3)
 657 {
 658         unsigned a;
 659         double cf;
 660         if (now <= t1) {
 661                 a = a1;
 662         } else if (now >= t4) {
 663                 a = a3;
 664         } else if (now < t2) { // and > t1
 665                 cf = ((double)(now - t1)) / (t2 - t1);
 666                 a = a1 * (1 - cf) + a2 * cf;
 667         } else if (now > t3) {
 668                 cf = ((double)(now - t3)) / (t4 - t3);
 669                 a = a2 * (1 - cf) + a3 * cf;
 670         } else { // t2 <= now <= t3
 671                 a = a2;
 672         }
 673
 674         return a;
 675 }
 676
 677 static void reset_render_context();
 678
 679 /**
 680  * \brief Parse style override tag.
 681  * \param p string to parse
 682  * \param pwr multiplier for some tag effects (comes from \t tags)
 683  */
 684 static char* parse_tag(char* p, double pwr) {
 685 #define skip_all(x) if (*p == (x)) ++p; else { \
 686         while ((*p != (x)) && (*p != '}') && (*p != 0)) {++p;} }
 687 #define skip(x) if (*p == (x)) ++p; else { return p; }
 688
 689         skip_all('\\');
 690         if ((*p == '}') || (*p == 0))
 691                 return p;
 692
 693         if (mystrcmp(&p, "fsc")) {
 694                 char tp = *p++;
 695                 double val;
 696                 if (tp == 'x') {
 697                         if (mystrtod(&p, &val)) {
 698                                 val /= 100;
 699                                 render_context.scale_x = (val - 1.) * pwr + 1.;
 700                         } else
 701                                 render_context.scale_x = render_context.style->ScaleX;
 702                 } else if (tp == 'y') {
 703                         if (mystrtod(&p, &val)) {
 704                                 val /= 100;
 705                                 render_context.scale_y = (val - 1.) * pwr + 1.;
 706                         } else
 707                                 render_context.scale_y = render_context.style->ScaleY;
 708                 }
 709         } else if (mystrcmp(&p, "fsp")) {
 710                 int val;
 711                 if (mystrtoi(&p, 10, &val))
 712                         render_context.hspacing = val * pwr;
 713                 else
 714                         render_context.hspacing = 0;
 715         } else if (mystrcmp(&p, "fs")) {
 716                 int val;
 717                 if (mystrtoi(&p, 10, &val))
 718                         val = render_context.font_size * ( 1 - pwr ) + val * pwr;
 719                 else
 720                         val = render_context.style->FontSize;
 721                 if (render_context.font)
 722                         change_font_size(val);
 723         } else if (mystrcmp(&p, "bord")) {
 724                 double val;
 725                 if (mystrtod(&p, &val))
 726                         val = render_context.border * ( 1 - pwr ) + val * pwr;
 727                 else
 728                         val = -1.; // reset to default
 729                 change_border(val);
 730         } else if (mystrcmp(&p, "move")) {
 731                 int x1, x2, y1, y2;
 732                 long long t1, t2, delta_t, t;
 733                 int x, y;
 734                 double k;
 735                 skip('(');
 736                 x1 = strtol(p, &p, 10);
 737                 skip(',');
 738                 y1 = strtol(p, &p, 10);
 739                 skip(',');
 740                 x2 = strtol(p, &p, 10);
 741                 skip(',');
 742                 y2 = strtol(p, &p, 10);
 743                 if (*p == ',') {
 744                         skip(',');
 745                         t1 = strtoll(p, &p, 10);
 746                         skip(',');
 747                         t2 = strtoll(p, &p, 10);
 748                         mp_msg(MSGT_ASS, MSGL_DBG2, "movement6: (%d, %d) -> (%d, %d), (%" PRId64 " .. %" PRId64 ")\n",
 749                                 x1, y1, x2, y2, (int64_t)t1, (int64_t)t2);
 750                 } else {
 751                         t1 = 0;
 752                         t2 = render_context.event->Duration;
 753                         mp_msg(MSGT_ASS, MSGL_DBG2, "movement: (%d, %d) -> (%d, %d)\n", x1, y1, x2, y2);
 754                 }
 755                 skip(')');
 756                 delta_t = t2 - t1;
 757                 t = frame_context.time - render_context.event->Start;
 758                 if (t < t1)
 759                         k = 0.;
 760                 else if (t > t2)
 761                         k = 1.;
 762                 else k = ((double)(t - t1)) / delta_t;
 763                 x = k * (x2 - x1) + x1;
 764                 y = k * (y2 - y1) + y1;
 765                 render_context.pos_x = x;
 766                 render_context.pos_y = y;
 767                 render_context.detect_collisions = 0;
 768                 render_context.evt_type = EVENT_POSITIONED;
 769         } else if (mystrcmp(&p, "frx") || mystrcmp(&p, "fry")) {
 770                 double val;
 771                 mystrtod(&p, &val);
 772                 mp_msg(MSGT_ASS, MSGL_V, "frx/fry unimplemented \n");
 773         } else if (mystrcmp(&p, "frz") || mystrcmp(&p, "fr")) {
 774                 double angle;
 775                 double val;
 776                 mystrtod(&p, &val);
 777                 mp_msg(MSGT_ASS, MSGL_DBG2, "setting rotation to %.2f\n", val * pwr);
 778                 angle = M_PI * val / 180;
 779                 render_context.rotation = angle * pwr;
 780         } else if (mystrcmp(&p, "fn")) {
 781                 char* start = p;
 782                 char* family;
 783                 skip_all('\\');
 784                 family = malloc(p - start + 1);
 785                 strncpy(family, start, p - start);
 786                 family[p - start] = '\0';
 787                 if (render_context.family)
 788                         free(render_context.family);
 789                 render_context.family = family;
 790                 update_font();
 791         } else if (mystrcmp(&p, "alpha")) {
 792                 uint32_t val;
 793                 int i;
 794                 if (strtocolor(&p, &val)) {
 795                         unsigned char a = val >> 24;
 796                         for (i = 0; i < 4; ++i)
 797                                 change_alpha(&render_context.c[i], a, pwr);
 798                 } else {
 799                         change_alpha(&render_context.c[0], render_context.style->PrimaryColour, pwr);
 800                         change_alpha(&render_context.c[1], render_context.style->SecondaryColour, pwr);
 801                         change_alpha(&render_context.c[2], render_context.style->OutlineColour, pwr);
 802                         change_alpha(&render_context.c[3], render_context.style->BackColour, pwr);
 803                 }
 804                 // FIXME: simplify
 805         } else if (mystrcmp(&p, "an")) {
 806                 int val = strtol(p, &p, 10);
 807                 int v = (val - 1) / 3; // 0, 1 or 2 for vertical alignment
 808                 mp_msg(MSGT_ASS, MSGL_DBG2, "an %d\n", val);
 809                 if (v != 0) v = 3 - v;
 810                 val = ((val - 1) % 3) + 1; // horizontal alignment
 811                 val += v*4;
 812                 mp_msg(MSGT_ASS, MSGL_DBG2, "align %d\n", val);
 813                 render_context.alignment = val;
 814         } else if (mystrcmp(&p, "a")) {
 815                 int val = strtol(p, &p, 10);
 816                 render_context.alignment = val;
 817         } else if (mystrcmp(&p, "pos")) {
 818                 int v1, v2;
 819                 skip('(');
 820                 v1 = strtol(p, &p, 10);
 821                 skip(',');
 822                 v2 = strtol(p, &p, 10);
 823                 skip(')');
 824                 mp_msg(MSGT_ASS, MSGL_DBG2, "pos(%d, %d)\n", v1, v2);
 825                 render_context.evt_type = EVENT_POSITIONED;
 826                 render_context.detect_collisions = 0;
 827                 render_context.pos_x = v1;
 828                 render_context.pos_y = v2;
 829         } else if (mystrcmp(&p, "fad")) {
 830                 int a1, a2, a3;
 831                 long long t1, t2, t3, t4;
 832                 if (*p == 'e') ++p; // either \fad or \fade
 833                 skip('(');
 834                 a1 = strtol(p, &p, 10);
 835                 skip(',');
 836                 a2 = strtol(p, &p, 10);
 837                 if (*p == ')') {
 838                         // 2-argument version (\fad, according to specs)
 839                         // a1 and a2 are fade-in and fade-out durations
 840                         t1 = 0;
 841                         t4 = render_context.event->Duration;
 842                         t2 = a1;
 843                         t3 = t4 - a2;
 844                         a1 = 0xFF;
 845                         a2 = 0;
 846                         a3 = 0xFF;
 847                 } else {
 848                         // 6-argument version (\fade)
 849                         // a1 and a2 (and a3) are opacity values
 850                         skip(',');
 851                         a3 = strtol(p, &p, 10);
 852                         skip(',');
 853                         t1 = strtoll(p, &p, 10);
 854                         skip(',');
 855                         t2 = strtoll(p, &p, 10);
 856                         skip(',');
 857                         t3 = strtoll(p, &p, 10);
 858                         skip(',');
 859                         t4 = strtoll(p, &p, 10);
 860                 }
 861                 skip(')');
 862                 render_context.fade = interpolate_alpha(frame_context.time - render_context.event->Start, t1, t2, t3, t4, a1, a2, a3);
 863         } else if (mystrcmp(&p, "org")) {
 864                 int v1, v2;
 865                 skip('(');
 866                 v1 = strtol(p, &p, 10);
 867                 skip(',');
 868                 v2 = strtol(p, &p, 10);
 869                 skip(')');
 870                 mp_msg(MSGT_ASS, MSGL_DBG2, "org(%d, %d)\n", v1, v2);
 871                 //                              render_context.evt_type = EVENT_POSITIONED;
 872                 render_context.org_x = v1;
 873                 render_context.org_y = v2;
 874         } else if (mystrcmp(&p, "t")) {
 875                 double v[3];
 876                 int v1, v2;
 877                 double v3;
 878                 int cnt;
 879                 long long t1, t2, t, delta_t;
 880                 double k;
 881                 skip('(');
 882                 for (cnt = 0; cnt < 3; ++cnt) {
 883                         if (*p == '\\')
 884                                 break;
 885                         v[cnt] = strtod(p, &p);
 886                         skip(',');
 887                 }
 888                 if (cnt == 3) {
 889                         v1 = v[0]; v2 = v[1]; v3 = v[2];
 890                 } else if (cnt == 2) {
 891                         v1 = v[0]; v2 = v[1]; v3 = 1.;
 892                 } else if (cnt == 1) {
 893                         v1 = 0; v2 = render_context.event->Duration; v3 = v[0];
 894                 } else { // cnt == 0
 895                         v1 = 0; v2 = render_context.event->Duration; v3 = 1.;
 896                 }
 897                 render_context.detect_collisions = 0;
 898                 t1 = v1;
 899                 t2 = v2;
 900                 delta_t = v2 - v1;
 901                 if (v3 < 0.)
 902                         v3 = 0.;
 903                 t = frame_context.time - render_context.event->Start; // FIXME: move to render_context
 904                 if (t < t1)
 905                         k = 0.;
 906                 else if (t > t2)
 907                         k = 1.;
 908                 else k = pow(((double)(t - t1)) / delta_t, v3);
 909                 while (*p == '\\')
 910                         p = parse_tag(p, k); // maybe k*pwr ? no, specs forbid nested \t's
 911                 skip_all(')'); // FIXME: better skip(')'), but much more tags support required
 912         } else if (mystrcmp(&p, "clip")) {
 913                 int x0, y0, x1, y1;
 914                 int res = 1;
 915                 skip('(');
 916                 res &= mystrtoi(&p, 10, &x0);
 917                 skip(',');
 918                 res &= mystrtoi(&p, 10, &y0);
 919                 skip(',');
 920                 res &= mystrtoi(&p, 10, &x1);
 921                 skip(',');
 922                 res &= mystrtoi(&p, 10, &y1);
 923                 skip(')');
 924                 if (res) {
 925                         render_context.clip_x0 = render_context.clip_x0 * (1-pwr) + x0 * pwr;
 926                         render_context.clip_x1 = render_context.clip_x1 * (1-pwr) + x1 * pwr;
 927                         render_context.clip_y0 = render_context.clip_y0 * (1-pwr) + y0 * pwr;
 928                         render_context.clip_y1 = render_context.clip_y1 * (1-pwr) + y1 * pwr;
 929                 } else {
 930                         render_context.clip_x0 = 0;
 931                         render_context.clip_y0 = 0;
 932                         render_context.clip_x1 = frame_context.track->PlayResX;
 933                         render_context.clip_y1 = frame_context.track->PlayResY;
 934                 }
 935         } else if (mystrcmp(&p, "c")) {
 936                 uint32_t val;
 937                 if (!strtocolor(&p, &val))
 938                         val = render_context.style->PrimaryColour;
 939                 mp_msg(MSGT_ASS, MSGL_DBG2, "color: %X\n", val);
 940                 change_color(&render_context.c[0], val, pwr);
 941         } else if ((*p >= '1') && (*p <= '4') && (++p) && (mystrcmp(&p, "c") || mystrcmp(&p, "a"))) {
 942                 char n = *(p-2);
 943                 int cidx = n - '1';
 944                 char cmd = *(p-1);
 945                 uint32_t val;
 946                 assert((n >= '1') && (n <= '4'));
 947                 if (!strtocolor(&p, &val))
 948                         switch(n) {
 949                                 case '1': val = render_context.style->PrimaryColour; break;
 950                                 case '2': val = render_context.style->SecondaryColour; break;
 951                                 case '3': val = render_context.style->OutlineColour; break;
 952                                 case '4': val = render_context.style->BackColour; break;
 953                                 default : val = 0; break; // impossible due to assert; avoid compilation warning
 954                         }
 955                 switch (cmd) {
 956                         case 'c': change_color(render_context.c + cidx, val, pwr); break;
 957                         case 'a': change_alpha(render_context.c + cidx, val >> 24, pwr); break;
 958                         default: mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_BadCommand, n, cmd); break;
 959                 }
 960                 mp_msg(MSGT_ASS, MSGL_DBG2, "single c/a at %f: %c%c = %X   \n", pwr, n, cmd, render_context.c[cidx]);
 961         } else if (mystrcmp(&p, "r")) {
 962                 reset_render_context();
 963         } else if (mystrcmp(&p, "be")) {
 964                 int val;
 965                 if (mystrtoi(&p, 10, &val))
 966                         render_context.be = val ? 1 : 0;
 967                 else
 968                         render_context.be = 0;
 969         } else if (mystrcmp(&p, "b")) {
 970                 int b;
 971                 if (mystrtoi(&p, 10, &b))
 972                         render_context.bold = b;
 973                 else
 974                         render_context.bold = - render_context.style->Bold;
 975                 update_font();
 976         } else if (mystrcmp(&p, "i")) {
 977                 int i;
 978                 if (mystrtoi(&p, 10, &i))
 979                         render_context.italic = i;
 980                 else
 981                         render_context.italic = - render_context.style->Italic;
 982                 update_font();
 983         } else if (mystrcmp(&p, "kf") || mystrcmp(&p, "K")) {
 984                 int val = strtol(p, &p, 10);
 985                 render_context.effect_type = EF_KARAOKE_KF;
 986                 if (render_context.effect_timing)
 987                         render_context.effect_skip_timing += render_context.effect_timing;
 988                 render_context.effect_timing = val * 10;
 989         } else if (mystrcmp(&p, "ko")) {
 990                 int val = strtol(p, &p, 10);
 991                 render_context.effect_type = EF_KARAOKE_KO;
 992                 if (render_context.effect_timing)
 993                         render_context.effect_skip_timing += render_context.effect_timing;
 994                 render_context.effect_timing = val * 10;
 995         } else if (mystrcmp(&p, "k")) {
 996                 int val = strtol(p, &p, 10);
 997                 render_context.effect_type = EF_KARAOKE;
 998                 if (render_context.effect_timing)
 999                         render_context.effect_skip_timing += render_context.effect_timing;
1000                 render_context.effect_timing = val * 10;
1001         } else if (mystrcmp(&p, "shad")) {
1002                 int val;
1003                 if (mystrtoi(&p, 10, &val))
1004                         render_context.shadow = val;
1005                 else
1006                         render_context.shadow = render_context.style->Shadow;
1007         }
1008
1009         return p;
1010
1011 #undef skip
1012 #undef skip_all
1013 }
1014
1015 /**
1016  * \brief Get next ucs4 char from string, parsing and executing style overrides
1017  * \param str string pointer
1018  * \return ucs4 code of the next char
1019  * On return str points to the unparsed part of the string
1020  */
1021 static unsigned get_next_char(char** str)
1022 {
1023         char* p = *str;
1024         unsigned chr;
1025         if (*p == '{') { // '\0' goes here
1026                 p++;
1027                 while (1) {
1028                         p = parse_tag(p, 1.);
1029                         if (*p == '}') { // end of tag
1030                                 p++;
1031                                 if (*p == '{') {
1032                                         p++;
1033                                         continue;
1034                                 } else
1035                                         break;
1036                         } else if (*p != '\\')
1037                                 mp_msg(MSGT_ASS, MSGL_V, "Unable to parse: \"%s\" \n", p);
1038                         if (*p == 0)
1039                                 break;
1040                 }
1041         }
1042         if (*p == '\t') {
1043                 ++p;
1044                 *str = p;
1045                 return ' ';
1046         }
1047         if (*p == '\\') {
1048                 if ((*(p+1) == 'N') || ((*(p+1) == 'n') && (frame_context.track->WrapStyle == 2))) {
1049                         p += 2;
1050                         *str = p;
1051                         return '\n';
1052                 } else if (*(p+1) == 'n') {
1053                         p += 2;
1054                         *str = p;
1055                         return ' ';
1056                 }
1057         }
1058         chr = utf8_get_char(&p);
1059         *str = p;
1060         return chr;
1061 }
1062
1063 static void apply_transition_effects(ass_event_t* event)
1064 {
1065         int v[4];
1066         int cnt;
1067         char* p = event->Effect;
1068
1069         if (!p || !*p) return;
1070
1071         cnt = 0;
1072         while (cnt < 4 && (p = strchr(p, ';'))) {
1073                 v[cnt++] = atoi(++p);
1074         }
1075
1076         if (strncmp(event->Effect, "Banner;", 7) == 0) {
1077                 int delay;
1078                 if (cnt < 1) {
1079                         mp_msg(MSGT_ASS, MSGL_V, "Error parsing effect: %s \n", event->Effect);
1080                         return;
1081                 }
1082                 if (cnt >= 2 && v[1] == 0) // right-to-left
1083                         render_context.scroll_direction = SCROLL_RL;
1084                 else // left-to-right
1085                         render_context.scroll_direction = SCROLL_LR;
1086
1087                 delay = v[0];
1088                 if (delay == 0) delay = 1; // ?
1089                 render_context.scroll_shift = (frame_context.time - render_context.event->Start) / delay;
1090                 render_context.evt_type = EVENT_HSCROLL;
1091                 return;
1092         }
1093
1094         if (strncmp(event->Effect, "Scroll up;", 10) == 0) {
1095                 render_context.scroll_direction = SCROLL_BT;
1096         } else if (strncmp(event->Effect, "Scroll down;", 12) == 0) {
1097                 render_context.scroll_direction = SCROLL_TB;
1098         } else {
1099                 mp_msg(MSGT_ASS, MSGL_V, "Unknown transition effect: %s \n", event->Effect);
1100                 return;
1101         }
1102         // parse scroll up/down parameters
1103         {
1104                 int delay;
1105                 int y0, y1;
1106                 if (cnt < 3) {
1107                         mp_msg(MSGT_ASS, MSGL_V, "Error parsing effect: %s \n", event->Effect);
1108                         return;
1109                 }
1110                 delay = v[2];
1111                 if (delay == 0) delay = 1; // ?
1112                 render_context.scroll_shift = (frame_context.time - render_context.event->Start) / delay;
1113                 if (v[0] < v[1]) {
1114                         y0 = v[0]; y1 = v[1];
1115                 } else {
1116                         y0 = v[1]; y1 = v[0];
1117                 }
1118                 if (y1 == 0)
1119                         y1 = frame_context.track->PlayResY; // y0=y1=0 means fullscreen scrolling
1120                 render_context.clip_y0 = y0;
1121                 render_context.clip_y1 = y1;
1122                 render_context.evt_type = EVENT_VSCROLL;
1123                 render_context.detect_collisions = 0;
1124         }
1125
1126 }
1127
1128 /**
1129  * \brief partially reset render_context to style values
1130  * Works like {\r}: resets some style overrides
1131  */
1132 static void reset_render_context(void)
1133 {
1134         render_context.c[0] = render_context.style->PrimaryColour;
1135         render_context.c[1] = render_context.style->SecondaryColour;
1136         render_context.c[2] = render_context.style->OutlineColour;
1137         render_context.c[3] = render_context.style->BackColour;
1138         render_context.font_size = render_context.style->FontSize;
1139
1140         if (render_context.family)
1141                 free(render_context.family);
1142         render_context.family = strdup(render_context.style->FontName);
1143         render_context.bold = - render_context.style->Bold;
1144         render_context.italic = - render_context.style->Italic;
1145         update_font();
1146
1147         change_border(-1.);
1148         render_context.scale_x = render_context.style->ScaleX;
1149         render_context.scale_y = render_context.style->ScaleY;
1150         render_context.hspacing = 0; // FIXME
1151         render_context.be = 0;
1152         render_context.shadow = render_context.style->Shadow;
1153
1154         // FIXME: does not reset unsupported attributes.
1155 }
1156
1157 /**
1158  * \brief Start new event. Reset render_context.
1159  */
1160 static void init_render_context(ass_event_t* event)
1161 {
1162         render_context.event = event;
1163         render_context.style = frame_context.track->styles + event->Style;
1164
1165         reset_render_context();
1166
1167         render_context.evt_type = EVENT_NORMAL;
1168         render_context.alignment = 0;
1169         render_context.rotation = M_PI * render_context.style->Angle / 180.;
1170         render_context.pos_x = 0;
1171         render_context.pos_y = 0;
1172         render_context.org_x = 0;
1173         render_context.org_y = 0;
1174         render_context.clip_x0 = 0;
1175         render_context.clip_y0 = 0;
1176         render_context.clip_x1 = frame_context.track->PlayResX;
1177         render_context.clip_y1 = frame_context.track->PlayResY;
1178         render_context.detect_collisions = 1;
1179         render_context.fade = 0;
1180         render_context.effect_type = EF_NONE;
1181         render_context.effect_timing = 0;
1182         render_context.effect_skip_timing = 0;
1183
1184         apply_transition_effects(event);
1185 }
1186
1187 static void free_render_context(void)
1188 {
1189 }
1190
1191 /**
1192  * \brief Get normal and outline glyphs from cache (if possible) or font face
1193  * \param index face glyph index
1194  * \param symbol ucs4 char
1195  * \param info out: struct filled with extracted data
1196  * \param advance advance vector of the extracted glyph
1197  * \return 0 on success
1198  */
1199 static int get_glyph(int index, int symbol, glyph_info_t* info, FT_Vector* advance)
1200 {
1201         int error;
1202         glyph_hash_val_t* val;
1203         glyph_hash_key_t* key = &(info->hash_key);
1204
1205         key->face = render_context.font->face;
1206         key->size = render_context.font_size;
1207         key->index = index;
1208         key->outline = (render_context.border * 0xFFFF); // convert to 16.16
1209         key->scale_x = (render_context.scale_x * 0xFFFF);
1210         key->scale_y = (render_context.scale_y * 0xFFFF);
1211         key->angle = (render_context.rotation * 0xFFFF);
1212         key->advance = *advance;
1213         key->bold = render_context.bold;
1214         key->italic = render_context.italic;
1215         key->be = render_context.be;
1216
1217         val = cache_find_glyph(key);
1218 //      val = 0;
1219
1220         if (val) {
1221                 info->glyph = info->outline_glyph = 0;
1222                 info->bm = val->bm;
1223                 info->bm_o = val->bm_o;
1224                 info->bm_s = val->bm_s;
1225                 info->bbox = val->bbox_scaled;
1226                 info->advance.x = val->advance.x;
1227                 info->advance.y = val->advance.y;
1228
1229                 return 0;
1230         }
1231
1232         // not found, get a new outline glyph from face
1233 //      mp_msg(MSGT_ASS, MSGL_INFO, "miss, index = %d, symbol = %c, adv = (%d, %d)\n", index, symbol, advance->x, advance->y);
1234
1235         info->glyph = ass_font_get_glyph(frame_context.ass_priv->fontconfig_priv, render_context.font, symbol);
1236         if (!info->glyph)
1237                 return 0;
1238
1239         info->advance.x = info->glyph->advance.x >> 10;
1240         info->advance.y = info->glyph->advance.y >> 10;
1241
1242         if (render_context.stroker) {
1243                 info->outline_glyph = info->glyph;
1244                 error = FT_Glyph_Stroke( &(info->outline_glyph), render_context.stroker, 0 ); // don't destroy original
1245                 if (error) {
1246                         mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_FT_Glyph_Stroke_Error, error);
1247                 }
1248         } else {
1249                 info->outline_glyph = 0;
1250         }
1251
1252         info->bm = info->bm_o = info->bm_s = 0;
1253
1254         return 0;
1255 }
1256
1257 /**
1258  * This function goes through text_info and calculates text parameters.
1259  * The following text_info fields are filled:
1260  *   n_lines
1261  *   height
1262  *   lines[].height
1263  *   lines[].asc
1264  *   lines[].desc
1265  */
1266 static void measure_text()
1267 {
1268         int cur_line = 0, max_asc = 0, max_desc = 0;
1269         int i;
1270         text_info.height = 0;
1271         for (i = 0; i < text_info.length + 1; ++i) {
1272                 if ((i == text_info.length) || text_info.glyphs[i].linebreak) {
1273                         text_info.lines[cur_line].asc = max_asc;
1274                         text_info.lines[cur_line].desc = max_desc;
1275                         text_info.height += max_asc + max_desc;
1276                         cur_line ++;
1277                         max_asc = max_desc = 0;
1278                 }
1279                 if (i < text_info.length) {
1280                         glyph_info_t* cur = text_info.glyphs + i;
1281                         if (cur->asc > max_asc)
1282                                 max_asc = cur->asc * render_context.scale_y;
1283                         if (cur->desc > max_desc)
1284                                 max_desc = cur->desc * render_context.scale_y;
1285                 }
1286         }
1287 }
1288
1289 /**
1290  * \brief rearrange text between lines
1291  * \param max_text_width maximal text line width in pixels
1292  * The algo is similar to the one in libvo/sub.c:
1293  * 1. Place text, wrapping it when current line is full
1294  * 2. Try moving words from the end of a line to the beginning of the next one while it reduces
1295  * the difference in lengths between this two lines.
1296  * The result may not be optimal, but usually is good enough.
1297  */
1298 static void wrap_lines_smart(int max_text_width)
1299 {
1300         int i, j;
1301         glyph_info_t *cur, *s1, *e1, *s2, *s3, *w;
1302         int last_space;
1303         int break_type;
1304         int exit;
1305         int pen_shift_x;
1306         int pen_shift_y;
1307         int cur_line;
1308
1309         last_space = -1;
1310         text_info.n_lines = 1;
1311         break_type = 0;
1312         s1 = text_info.glyphs; // current line start
1313         for (i = 0; i < text_info.length; ++i) {
1314                 int break_at, s_offset, len;
1315                 cur = text_info.glyphs + i;
1316                 break_at = -1;
1317                 s_offset = s1->bbox.xMin + s1->pos.x;
1318                 len = (cur->bbox.xMax + cur->pos.x) - s_offset;
1319
1320                 if (cur->symbol == '\n') {
1321                         break_type = 2;
1322                         break_at = i;
1323                         mp_msg(MSGT_ASS, MSGL_DBG2, "forced line break at %d\n", break_at);
1324                 }
1325
1326                 if (len >= max_text_width) {
1327                         break_type = 1;
1328                         break_at = last_space;
1329                         if (break_at == -1)
1330                                 break_at = i - 1;
1331                         if (break_at == -1)
1332                                 break_at = 0;
1333                         mp_msg(MSGT_ASS, MSGL_DBG2, "overfill at %d\n", i);
1334                         mp_msg(MSGT_ASS, MSGL_DBG2, "line break at %d\n", break_at);
1335                 }
1336
1337                 if (break_at != -1) {
1338                         // need to use one more line
1339                         // marking break_at+1 as start of a new line
1340                         int lead = break_at + 1; // the first symbol of the new line
1341                         if (text_info.n_lines >= MAX_LINES) {
1342                                 // to many lines !
1343                                 // no more linebreaks
1344                                 for (j = lead; j < text_info.length; ++j)
1345                                         text_info.glyphs[j].linebreak = 0;
1346                                 break;
1347                         }
1348                         if (lead < text_info.length)
1349                                 text_info.glyphs[lead].linebreak = break_type;
1350                         last_space = -1;
1351                         s1 = text_info.glyphs + lead;
1352                         s_offset = s1->bbox.xMin + s1->pos.x;
1353                         text_info.n_lines ++;
1354                 }
1355
1356                 if (cur->symbol == ' ')
1357                         last_space = i;
1358         }
1359 #define DIFF(x,y) (((x) < (y)) ? (y - x) : (x - y))
1360         exit = 0;
1361         while (!exit) {
1362                 exit = 1;
1363                 w = s3 = text_info.glyphs;
1364                 s1 = s2 = 0;
1365                 for (i = 0; i <= text_info.length; ++i) {
1366                         cur = text_info.glyphs + i;
1367                         if ((i == text_info.length) || cur->linebreak) {
1368                                 s1 = s2;
1369                                 s2 = s3;
1370                                 s3 = cur;
1371                                 if (s1 && (s2->linebreak == 1)) { // have at least 2 lines, and linebreak is 'soft'
1372                                         int l1, l2, l1_new, l2_new;
1373
1374                                         w = s2;
1375                                         do { --w; } while ((w > s1) && (w->symbol == ' '));
1376                                         while ((w > s1) && (w->symbol != ' ')) { --w; }
1377                                         e1 = w;
1378                                         while ((e1 > s1) && (e1->symbol == ' ')) { --e1; }
1379                                         if (w->symbol == ' ') ++w;
1380
1381                                         l1 = ((s2-1)->bbox.xMax + (s2-1)->pos.x) - (s1->bbox.xMin + s1->pos.x);
1382                                         l2 = ((s3-1)->bbox.xMax + (s3-1)->pos.x) - (s2->bbox.xMin + s2->pos.x);
1383                                         l1_new = (e1->bbox.xMax + e1->pos.x) - (s1->bbox.xMin + s1->pos.x);
1384                                         l2_new = ((s3-1)->bbox.xMax + (s3-1)->pos.x) - (w->bbox.xMin + w->pos.x);
1385
1386                                         if (DIFF(l1_new, l2_new) < DIFF(l1, l2)) {
1387                                                 w->linebreak = 1;
1388                                                 s2->linebreak = 0;
1389                                                 exit = 0;
1390                                         }
1391                                 }
1392                         }
1393                         if (i == text_info.length)
1394                                 break;
1395                 }
1396
1397         }
1398         assert(text_info.n_lines >= 1);
1399 #undef DIFF
1400
1401         measure_text();
1402
1403         pen_shift_x = 0;
1404         pen_shift_y = 0;
1405         cur_line = 1;
1406         for (i = 0; i < text_info.length; ++i) {
1407                 cur = text_info.glyphs + i;
1408                 if (cur->linebreak) {
1409                         int height = text_info.lines[cur_line - 1].desc + text_info.lines[cur_line].asc;
1410                         cur_line ++;
1411                         pen_shift_x = - cur->pos.x;
1412                         pen_shift_y += (height >> 6) + global_settings->line_spacing;
1413                         mp_msg(MSGT_ASS, MSGL_DBG2, "shifting from %d to %d by (%d, %d)\n", i, text_info.length - 1, pen_shift_x, pen_shift_y);
1414                 }
1415                 cur->pos.x += pen_shift_x;
1416                 cur->pos.y += pen_shift_y;
1417         }
1418 }
1419
1420 /**
1421  * \brief determine karaoke effects
1422  * Karaoke effects cannot be calculated during parse stage (get_next_char()),
1423  * so they are done in a separate step.
1424  * Parse stage: when karaoke style override is found, its parameters are stored in the next glyph's
1425  * (the first glyph of the karaoke word)'s effect_type and effect_timing.
1426  * This function:
1427  * 1. sets effect_type for all glyphs in the word (_karaoke_ word)
1428  * 2. sets effect_timing for all glyphs to x coordinate of the border line between the left and right karaoke parts
1429  * (left part is filled with PrimaryColour, right one - with SecondaryColour).
1430  */
1431 static void process_karaoke_effects(void)
1432 {
1433         glyph_info_t *cur, *cur2;
1434         glyph_info_t *s1, *e1; // start and end of the current word
1435         glyph_info_t *s2; // start of the next word
1436         int i;
1437         int timing; // current timing
1438         int tm_start, tm_end; // timings at start and end of the current word
1439         int tm_current;
1440         double dt;
1441         int x;
1442         int x_start, x_end;
1443
1444         tm_current = frame_context.time - render_context.event->Start;
1445         timing = 0;
1446         s1 = s2 = 0;
1447         for (i = 0; i <= text_info.length; ++i) {
1448                 cur = text_info.glyphs + i;
1449                 if ((i == text_info.length) || (cur->effect_type != EF_NONE)) {
1450                         s1 = s2;
1451                         s2 = cur;
1452                         if (s1) {
1453                                 e1 = s2 - 1;
1454                                 tm_start = timing + s1->effect_skip_timing;
1455                                 tm_end = tm_start + s1->effect_timing;
1456                                 timing = tm_end;
1457                                 x_start = 1000000;
1458                                 x_end = -1000000;
1459                                 for (cur2 = s1; cur2 <= e1; ++cur2) {
1460                                         x_start = FFMIN(x_start, cur2->bbox.xMin + cur2->pos.x);
1461                                         x_end = FFMAX(x_end, cur2->bbox.xMax + cur2->pos.x);
1462                                 }
1463
1464                                 dt = (tm_current - tm_start);
1465                                 if ((s1->effect_type == EF_KARAOKE) || (s1->effect_type == EF_KARAOKE_KO)) {
1466                                         if (dt > 0)
1467                                                 x = x_end + 1;
1468                                         else
1469                                                 x = x_start;
1470                                 } else if (s1->effect_type == EF_KARAOKE_KF) {
1471                                         dt /= (tm_end - tm_start);
1472                                         x = x_start + (x_end - x_start) * dt;
1473                                 } else {
1474                                         mp_msg(MSGT_ASS, MSGL_ERR, MSGTR_LIBASS_UnknownEffectType_InternalError);
1475                                         continue;
1476                                 }
1477
1478                                 for (cur2 = s1; cur2 <= e1; ++cur2) {
1479                                         cur2->effect_type = s1->effect_type;
1480                                         cur2->effect_timing = x - cur2->pos.x;
1481                                 }
1482                         }
1483                 }
1484         }
1485 }
1486
1487 static int get_face_ascender(FT_Face face)
1488 {
1489         int v = face->size->metrics.ascender;
1490         int v2 = FT_MulFix(face->bbox.yMax, face->size->metrics.y_scale);
1491         if (v > v2 * 0.9)
1492                 return v;
1493         else
1494                 return v2;
1495 }
1496
1497 static int get_face_descender(FT_Face face)
1498 {
1499         int v = - face->size->metrics.descender;
1500         int v2 = - FT_MulFix(face->bbox.yMin, face->size->metrics.y_scale);
1501         if (v > v2 * 0.9)
1502                 return v;
1503         else
1504                 return v2;
1505 }
1506
1507 /**
1508  * \brief Calculate base point for positioning and rotation
1509  * \param bbox text bbox
1510  * \param alignment alignment
1511  * \param bx, by out: base point coordinates
1512  */
1513 static void get_base_point(FT_BBox bbox, int alignment, int* bx, int* by)
1514 {
1515         const int halign = alignment & 3;
1516         const int valign = alignment & 12;
1517         if (bx)
1518                 switch(halign) {
1519                 case HALIGN_LEFT:
1520                         *bx = bbox.xMin;
1521                         break;
1522                 case HALIGN_CENTER:
1523                         *bx = (bbox.xMax + bbox.xMin) / 2;
1524                         break;
1525                 case HALIGN_RIGHT:
1526                         *bx = bbox.xMax;
1527                         break;
1528                 }
1529         if (by)
1530                 switch(valign) {
1531                 case VALIGN_TOP:
1532                         *by = bbox.yMin;
1533                         break;
1534                 case VALIGN_CENTER:
1535                         *by = (bbox.yMax + bbox.yMin) / 2;
1536                         break;
1537                 case VALIGN_SUB:
1538                         *by = bbox.yMax;
1539                         break;
1540                 }
1541 }
1542
1543 /**
1544  * \brief Main ass rendering function, glues everything together
1545  * \param event event to render
1546  * Process event, appending resulting ass_image_t's to images_root.
1547  */
1548 static int ass_render_event(ass_event_t* event, event_images_t* event_images)
1549 {
1550         char* p;
1551         FT_UInt glyph_index;
1552         FT_Bool use_kerning;
1553         FT_UInt previous;
1554         FT_UInt num_glyphs;
1555         FT_Vector pen;
1556         int error;
1557         unsigned code;
1558         FT_BBox bbox;
1559         int i, j;
1560         FT_Vector shift;
1561         int MarginL, MarginR, MarginV;
1562         int last_break;
1563         int alignment, halign, valign;
1564         int device_x = 0, device_y = 0;
1565
1566         if (event->Style >= frame_context.track->n_styles) {
1567                 mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_NoStyleFound);
1568                 return 1;
1569         }
1570         if (!event->Text) {
1571                 mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_EmptyEvent);
1572                 return 1;
1573         }
1574
1575         init_render_context(event);
1576
1577         text_info.length = 0;
1578         pen.x = 0;
1579         pen.y = 0;
1580         previous = 0;
1581         num_glyphs = 0;
1582         p = event->Text;
1583         // Event parsing.
1584         while (1) {
1585                 // get next char, executing style override
1586                 // this affects render_context
1587                 code = get_next_char(&p);
1588
1589                 // face could have been changed in get_next_char
1590                 if (!render_context.font) {
1591                         free_render_context();
1592                         return 1;
1593                 }
1594
1595                 if (code == 0)
1596                         break;
1597
1598                 use_kerning = FT_HAS_KERNING(render_context.font->face);
1599
1600                 if (text_info.length >= MAX_GLYPHS) {
1601                         mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_MAX_GLYPHS_Reached,
1602                                         (int)(event - frame_context.track->events), event->Start, event->Duration, event->Text);
1603                         break;
1604                 }
1605
1606                 glyph_index = FT_Get_Char_Index( render_context.font->face, code);
1607
1608                 if ( use_kerning && previous && glyph_index ) {
1609                         FT_Vector delta;
1610                         FT_Get_Kerning( render_context.font->face, previous, glyph_index, FT_KERNING_DEFAULT, &delta );
1611                         pen.x += delta.x * render_context.scale_x;
1612                         pen.y += delta.y * render_context.scale_y;
1613                 }
1614
1615                 shift.x = pen.x & 63;
1616                 shift.y = pen.y & 63;
1617
1618                 {
1619                         FT_Matrix matrix;
1620                         matrix.xx = (FT_Fixed)( render_context.scale_x * frame_context.font_scale_x * 0x10000L );
1621                         matrix.xy = (FT_Fixed)( 0 * 0x10000L );
1622                         matrix.yx = (FT_Fixed)( 0 * 0x10000L );
1623                         matrix.yy = (FT_Fixed)( render_context.scale_y * 0x10000L );
1624
1625                         ass_font_set_transform(render_context.font, &matrix, &shift );
1626                 }
1627
1628                 error = get_glyph(glyph_index, code, text_info.glyphs + text_info.length, &shift);
1629
1630                 if (error) {
1631                         continue;
1632                 }
1633
1634                 text_info.glyphs[text_info.length].pos.x = pen.x >> 6;
1635                 text_info.glyphs[text_info.length].pos.y = pen.y >> 6;
1636
1637                 pen.x += text_info.glyphs[text_info.length].advance.x;
1638                 pen.x += render_context.hspacing;
1639                 pen.y += text_info.glyphs[text_info.length].advance.y;
1640
1641                 // if it's an outline glyph, we still need to fill the bbox
1642                 if (text_info.glyphs[text_info.length].glyph) {
1643                         FT_Glyph_Get_CBox( text_info.glyphs[text_info.length].glyph, FT_GLYPH_BBOX_PIXELS, &(text_info.glyphs[text_info.length].bbox) );
1644                 }
1645
1646
1647                 previous = glyph_index;
1648
1649                 text_info.glyphs[text_info.length].symbol = code;
1650                 text_info.glyphs[text_info.length].linebreak = 0;
1651                 for (i = 0; i < 4; ++i) {
1652                         uint32_t clr = render_context.c[i];
1653                         change_alpha(&clr, mult_alpha(_a(clr), render_context.fade), 1.);
1654                         text_info.glyphs[text_info.length].c[i] = clr;
1655                 }
1656                 text_info.glyphs[text_info.length].effect_type = render_context.effect_type;
1657                 text_info.glyphs[text_info.length].effect_timing = render_context.effect_timing;
1658                 text_info.glyphs[text_info.length].effect_skip_timing = render_context.effect_skip_timing;
1659                 text_info.glyphs[text_info.length].asc = get_face_ascender(render_context.font->face);
1660                 text_info.glyphs[text_info.length].desc = get_face_descender(render_context.font->face);
1661                 text_info.glyphs[text_info.length].be = render_context.be;
1662                 text_info.glyphs[text_info.length].shadow = render_context.shadow;
1663                 text_info.glyphs[text_info.length].frz = render_context.rotation;
1664
1665                 text_info.length++;
1666
1667                 render_context.effect_type = EF_NONE;
1668                 render_context.effect_timing = 0;
1669                 render_context.effect_skip_timing = 0;
1670         }
1671
1672         if (text_info.length == 0) {
1673                 // no valid symbols in the event; this can be smth like {comment}
1674                 free_render_context();
1675                 return 1;
1676         }
1677
1678         // depends on glyph x coordinates being monotonous, so it should be done before line wrap
1679         process_karaoke_effects();
1680
1681         // alignments
1682         alignment = render_context.alignment;
1683         if (!alignment)
1684                 alignment = render_context.style->Alignment;
1685         halign = alignment & 3;
1686         valign = alignment & 12;
1687
1688         MarginL = (event->MarginL) ? event->MarginL : render_context.style->MarginL;
1689         MarginR = (event->MarginR) ? event->MarginR : render_context.style->MarginR;
1690         MarginV = (event->MarginV) ? event->MarginV : render_context.style->MarginV;
1691
1692         if (render_context.evt_type != EVENT_HSCROLL) {
1693                 int max_text_width;
1694
1695                 // calculate max length of a line
1696                 max_text_width = x2scr(frame_context.track->PlayResX - MarginR) - x2scr(MarginL);
1697
1698                 // rearrange text in several lines
1699                 wrap_lines_smart(max_text_width);
1700
1701                 // align text
1702                 last_break = -1;
1703                 for (i = 1; i < text_info.length + 1; ++i) { // (text_info.length + 1) is the end of the last line
1704                         if ((i == text_info.length) || text_info.glyphs[i].linebreak) {
1705                                 int width, shift;
1706                                 glyph_info_t* first_glyph = text_info.glyphs + last_break + 1;
1707                                 glyph_info_t* last_glyph = text_info.glyphs + i - 1;
1708
1709                                 while ((last_glyph > first_glyph) && ((last_glyph->symbol == '\n') || (last_glyph->symbol == 0)))
1710                                         last_glyph --;
1711
1712                                 width = last_glyph->pos.x + last_glyph->bbox.xMax - first_glyph->pos.x - first_glyph->bbox.xMin;
1713                                 shift = - first_glyph->bbox.xMin; // now text line starts exactly at 0 (left margin)
1714                                 if (halign == HALIGN_LEFT) { // left aligned, no action
1715                                 } else if (halign == HALIGN_RIGHT) { // right aligned
1716                                         shift = max_text_width - width;
1717                                 } else if (halign == HALIGN_CENTER) { // centered
1718                                         shift = (max_text_width - width) / 2;
1719                                 }
1720                                 for (j = last_break + 1; j < i; ++j) {
1721                                         text_info.glyphs[j].pos.x += shift;
1722                                 }
1723                                 last_break = i - 1;
1724                         }
1725                 }
1726         } else { // render_context.evt_type == EVENT_HSCROLL
1727                 measure_text();
1728         }
1729
1730         // determing text bounding box
1731         compute_string_bbox(&text_info, &bbox);
1732
1733         // determine device coordinates for text
1734
1735         // x coordinate for everything except positioned events
1736         if (render_context.evt_type == EVENT_NORMAL ||
1737             render_context.evt_type == EVENT_VSCROLL) {
1738                 device_x = x2scr(MarginL);
1739         } else if (render_context.evt_type == EVENT_HSCROLL) {
1740                 if (render_context.scroll_direction == SCROLL_RL)
1741                         device_x = x2scr(frame_context.track->PlayResX - render_context.scroll_shift);
1742                 else if (render_context.scroll_direction == SCROLL_LR)
1743                         device_x = x2scr(render_context.scroll_shift) - (bbox.xMax - bbox.xMin);
1744         }
1745
1746         // y coordinate for everything except positioned events
1747         if (render_context.evt_type == EVENT_NORMAL ||
1748             render_context.evt_type == EVENT_HSCROLL) {
1749                 if (valign == VALIGN_TOP) { // toptitle
1750                         device_y = y2scr_top(MarginV) + (text_info.lines[0].asc >> 6);
1751                 } else if (valign == VALIGN_CENTER) { // midtitle
1752                         int scr_y = y2scr(frame_context.track->PlayResY / 2);
1753                         device_y = scr_y - (bbox.yMax - bbox.yMin) / 2;
1754                 } else { // subtitle
1755                         int scr_y;
1756                         if (valign != VALIGN_SUB)
1757                                 mp_msg(MSGT_ASS, MSGL_V, "Invalid valign, supposing 0 (subtitle)\n");
1758                         scr_y = y2scr_sub(frame_context.track->PlayResY - MarginV);
1759                         device_y = scr_y;
1760                         device_y -= (text_info.height >> 6);
1761                         device_y += (text_info.lines[0].asc >> 6);
1762                 }
1763         } else if (render_context.evt_type == EVENT_VSCROLL) {
1764                 if (render_context.scroll_direction == SCROLL_TB)
1765                         device_y = y2scr(render_context.clip_y0 + render_context.scroll_shift) - (bbox.yMax - bbox.yMin);
1766                 else if (render_context.scroll_direction == SCROLL_BT)
1767                         device_y = y2scr(render_context.clip_y1 - render_context.scroll_shift);
1768         }
1769
1770         // positioned events are totally different
1771         if (render_context.evt_type == EVENT_POSITIONED) {
1772                 int base_x = 0;
1773                 int base_y = 0;
1774                 mp_msg(MSGT_ASS, MSGL_DBG2, "positioned event at %d, %d\n", render_context.pos_x, render_context.pos_y);
1775                 get_base_point(bbox, alignment, &base_x, &base_y);
1776                 device_x = x2scr(render_context.pos_x) - base_x;
1777                 device_y = y2scr(render_context.pos_y) - base_y;
1778         }
1779
1780         // fix clip coordinates (they depend on alignment)
1781         render_context.clip_x0 = x2scr(render_context.clip_x0);
1782         render_context.clip_x1 = x2scr(render_context.clip_x1);
1783         if (render_context.evt_type == EVENT_NORMAL ||
1784             render_context.evt_type == EVENT_HSCROLL ||
1785             render_context.evt_type == EVENT_VSCROLL) {
1786                 if (valign == VALIGN_TOP) {
1787                         render_context.clip_y0 = y2scr_top(render_context.clip_y0);
1788                         render_context.clip_y1 = y2scr_top(render_context.clip_y1);
1789                 } else if (valign == VALIGN_CENTER) {
1790                         render_context.clip_y0 = y2scr(render_context.clip_y0);
1791                         render_context.clip_y1 = y2scr(render_context.clip_y1);
1792                 } else if (valign == VALIGN_SUB) {
1793                         render_context.clip_y0 = y2scr_sub(render_context.clip_y0);
1794                         render_context.clip_y1 = y2scr_sub(render_context.clip_y1);
1795                 }
1796         } else if (render_context.evt_type == EVENT_POSITIONED) {
1797                 render_context.clip_y0 = y2scr(render_context.clip_y0);
1798                 render_context.clip_y1 = y2scr(render_context.clip_y1);
1799         }
1800
1801         // rotate glyphs if needed
1802         {
1803                 double angle = 0.;
1804                 FT_Vector center;
1805                 FT_Matrix matrix_rotate;
1806
1807                 if (((render_context.org_x != 0) || (render_context.org_y != 0)) && (render_context.evt_type == EVENT_POSITIONED)) {
1808                         center.x = render_context.org_x;
1809                         center.y = render_context.org_y;
1810                 } else {
1811                         int bx, by;
1812                         get_base_point(bbox, alignment, &bx, &by);
1813                         center.x = device_x + bx;
1814                         center.y = device_y + by;
1815                 }
1816
1817                 for (i = 0; i < text_info.length; ++i) {
1818                         FT_Vector start;
1819                         FT_Vector start_old;
1820                         glyph_info_t* info = text_info.glyphs + i;
1821
1822                         if (info->frz < 0.00001 && info->frz > -0.00001)
1823                                 continue;
1824
1825                         if (info->frz != angle) {
1826                                 angle = info->frz;
1827                                 matrix_rotate.xx = (FT_Fixed)( cos( angle ) * 0x10000L );
1828                                 matrix_rotate.xy = (FT_Fixed)( -sin( angle ) * 0x10000L );
1829                                 matrix_rotate.yx = (FT_Fixed)( sin( angle ) * 0x10000L );
1830                                 matrix_rotate.yy = (FT_Fixed)( cos( angle ) * 0x10000L );
1831                         }
1832
1833                         // calculating shift vector
1834                         // shift = (position - center)*M - (position - center)
1835                         start.x = (info->pos.x + device_x - center.x) << 6;
1836                         start.y = - (info->pos.y + device_y - center.y) << 6;
1837                         start_old.x = start.x;
1838                         start_old.y = start.y;
1839
1840                         FT_Vector_Transform(&start, &matrix_rotate);
1841
1842                         start.x -= start_old.x;
1843                         start.y -= start_old.y;
1844
1845                         info->pos.x += start.x >> 6;
1846                         info->pos.y -= start.y >> 6;
1847
1848                         if (info->glyph)
1849                                 FT_Glyph_Transform( info->glyph, &matrix_rotate, 0 );
1850                         if (info->outline_glyph)
1851                                 FT_Glyph_Transform( info->outline_glyph, &matrix_rotate, 0 );
1852                 }
1853         }
1854
1855         event_images->top = device_y - (text_info.lines[0].asc >> 6);
1856         event_images->height = text_info.height >> 6;
1857         event_images->detect_collisions = render_context.detect_collisions;
1858         event_images->shift_direction = (valign == VALIGN_TOP) ? 1 : -1;
1859         event_images->event = event;
1860         event_images->imgs = render_text(&text_info, device_x, device_y);
1861
1862         free_render_context();
1863
1864         return 0;
1865 }
1866
1867 static void ass_reconfigure(ass_renderer_t* priv)
1868 {
1869         priv->render_id = ++last_render_id;
1870         ass_glyph_cache_reset();
1871 }
1872
1873 void ass_set_frame_size(ass_renderer_t* priv, int w, int h)
1874 {
1875         if (priv->settings.frame_width != w || priv->settings.frame_height != h) {
1876                 priv->settings.frame_width = w;
1877                 priv->settings.frame_height = h;
1878                 if (priv->settings.aspect == 0.)
1879                         priv->settings.aspect = ((double)w) / h;
1880                 ass_reconfigure(priv);
1881         }
1882 }
1883
1884 void ass_set_margins(ass_renderer_t* priv, int t, int b, int l, int r)
1885 {
1886         if (priv->settings.left_margin != l ||
1887             priv->settings.right_margin != r ||
1888             priv->settings.top_margin != t ||
1889             priv->settings.bottom_margin != b) {
1890                 priv->settings.left_margin = l;
1891                 priv->settings.right_margin = r;
1892                 priv->settings.top_margin = t;
1893                 priv->settings.bottom_margin = b;
1894                 ass_reconfigure(priv);
1895         }
1896 }
1897
1898 void ass_set_use_margins(ass_renderer_t* priv, int use)
1899 {
1900         priv->settings.use_margins = use;
1901 }
1902
1903 void ass_set_aspect_ratio(ass_renderer_t* priv, double ar)
1904 {
1905         if (priv->settings.aspect != ar) {
1906                 priv->settings.aspect = ar;
1907                 ass_reconfigure(priv);
1908         }
1909 }
1910
1911 void ass_set_font_scale(ass_renderer_t* priv, double font_scale)
1912 {
1913         if (priv->settings.font_size_coeff != font_scale) {
1914                 priv->settings.font_size_coeff = font_scale;
1915                 ass_reconfigure(priv);
1916         }
1917 }
1918
1919 int ass_set_fonts(ass_renderer_t* priv, const char* default_font, const char* default_family)
1920 {
1921         if (priv->settings.default_font)
1922                 free(priv->settings.default_font);
1923         if (priv->settings.default_family)
1924                 free(priv->settings.default_family);
1925
1926         priv->settings.default_font = default_font ? strdup(default_font) : 0;
1927         priv->settings.default_family = default_family ? strdup(default_family) : 0;
1928
1929         if (priv->fontconfig_priv)
1930                 fontconfig_done(priv->fontconfig_priv);
1931         priv->fontconfig_priv = fontconfig_init(priv->library->fonts_dir, default_family, default_font);
1932
1933         return !!priv->fontconfig_priv;
1934 }
1935
1936 /**
1937  * \brief Start a new frame
1938  */
1939 static int ass_start_frame(ass_renderer_t *priv, ass_track_t* track, long long now)
1940 {
1941         ass_image_t* img;
1942
1943         ass_renderer = priv;
1944         global_settings = &priv->settings;
1945
1946         if (!priv->settings.frame_width && !priv->settings.frame_height)
1947                 return 1; // library not initialized
1948
1949         frame_context.ass_priv = priv;
1950         frame_context.width = global_settings->frame_width;
1951         frame_context.height = global_settings->frame_height;
1952         frame_context.orig_width = global_settings->frame_width - global_settings->left_margin - global_settings->right_margin;
1953         frame_context.orig_height = global_settings->frame_height - global_settings->top_margin - global_settings->bottom_margin;
1954         frame_context.track = track;
1955         frame_context.time = now;
1956
1957         ass_lazy_track_init();
1958
1959         frame_context.font_scale = global_settings->font_size_coeff * ass_internal_font_size_coeff *
1960                                    frame_context.orig_height / frame_context.track->PlayResY;
1961         frame_context.border_scale = ((double)frame_context.orig_height) / frame_context.track->PlayResY;
1962
1963         if (frame_context.orig_width * track->PlayResY == frame_context.orig_height * track->PlayResX)
1964                 frame_context.font_scale_x = 1.;
1965         else
1966                 frame_context.font_scale_x = ((double)(frame_context.orig_width * track->PlayResY)) / (frame_context.orig_height * track->PlayResX);
1967
1968         img = priv->images_root;
1969         while (img) {
1970                 ass_image_t* next = img->next;
1971                 free(img);
1972                 img = next;
1973         }
1974         priv->images_root = 0;
1975
1976         return 0;
1977 }
1978
1979 static int cmp_event_layer(const void* p1, const void* p2)
1980 {
1981         ass_event_t* e1 = ((event_images_t*)p1)->event;
1982         ass_event_t* e2 = ((event_images_t*)p2)->event;
1983         if (e1->Layer < e2->Layer)
1984                 return -1;
1985         if (e1->Layer > e2->Layer)
1986                 return 1;
1987         if (e1->Start < e2->Start)
1988                 return -1;
1989         if (e1->Start > e2->Start)
1990                 return 1;
1991         if (e1->ReadOrder < e2->ReadOrder)
1992                 return -1;
1993         if (e1->ReadOrder > e2->ReadOrder)
1994                 return 1;
1995         return 0;
1996 }
1997
1998 #define MAX_EVENTS 100
1999
2000 static render_priv_t* get_render_priv(ass_event_t* event)
2001 {
2002         if (!event->render_priv)
2003                 event->render_priv = calloc(1, sizeof(render_priv_t));
2004         // FIXME: check render_id
2005         if (ass_renderer->render_id != event->render_priv->render_id) {
2006                 memset(event->render_priv, 0, sizeof(render_priv_t));
2007                 event->render_priv->render_id = ass_renderer->render_id;
2008         }
2009         return event->render_priv;
2010 }
2011
2012 typedef struct segment_s {
2013         int a, b; // top and height
2014 } segment_t;
2015
2016 static int overlap(segment_t* s1, segment_t* s2)
2017 {
2018         if (s1->a >= s2->b || s2->a >= s1->b)
2019                 return 0;
2020         return 1;
2021 }
2022
2023 static int cmp_segment(const void* p1, const void* p2)
2024 {
2025         return ((segment_t*)p1)->a - ((segment_t*)p2)->a;
2026 }
2027
2028 static void shift_event(event_images_t* ei, int shift)
2029 {
2030         ass_image_t* cur = ei->imgs;
2031         while (cur) {
2032                 cur->dst_y += shift;
2033                 // clip top and bottom
2034                 if (cur->dst_y < 0) {
2035                         int clip = - cur->dst_y;
2036                         cur->h -= clip;
2037                         cur->bitmap += clip * cur->stride;
2038                         cur->dst_y = 0;
2039                 }
2040                 if (cur->dst_y + cur->h >= frame_context.height) {
2041                         int clip = cur->dst_y + cur->h - frame_context.height;
2042                         cur->h -= clip;
2043                 }
2044                 if (cur->h <= 0) {
2045                         cur->h = 0;
2046                         cur->dst_y = 0;
2047                 }
2048                 cur = cur->next;
2049         }
2050         ei->top += shift;
2051 }
2052
2053 // dir: 1 - move down
2054 //      -1 - move up
2055 static int fit_segment(segment_t* s, segment_t* fixed, int* cnt, int dir)
2056 {
2057         int i;
2058         int shift = 0;
2059
2060         if (dir == 1) // move down
2061                 for (i = 0; i < *cnt; ++i) {
2062                         if (s->b + shift <= fixed[i].a || s->a + shift >= fixed[i].b)
2063                                 continue;
2064                         shift = fixed[i].b - s->a;
2065                 }
2066         else // dir == -1, move up
2067                 for (i = *cnt-1; i >= 0; --i) {
2068                         if (s->b + shift <= fixed[i].a || s->a + shift >= fixed[i].b)
2069                                 continue;
2070                         shift = fixed[i].a - s->b;
2071                 }
2072
2073         fixed[*cnt].a = s->a + shift;
2074         fixed[*cnt].b = s->b + shift;
2075         (*cnt)++;
2076         qsort(fixed, *cnt, sizeof(segment_t), cmp_segment);
2077
2078         return shift;
2079 }
2080
2081 static void fix_collisions(event_images_t* imgs, int cnt)
2082 {
2083         segment_t used[MAX_EVENTS];
2084         int cnt_used = 0;
2085         int i, j;
2086
2087         // fill used[] with fixed events
2088         for (i = 0; i < cnt; ++i) {
2089                 render_priv_t* priv;
2090                 if (!imgs[i].detect_collisions) continue;
2091                 priv = get_render_priv(imgs[i].event);
2092                 if (priv->height > 0) { // it's a fixed event
2093                         segment_t s;
2094                         s.a = priv->top;
2095                         s.b = priv->top + priv->height;
2096                         if (priv->height != imgs[i].height) { // no, it's not
2097                                 mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_EventHeightHasChanged);
2098                                 priv->top = 0;
2099                                 priv->height = 0;
2100                         }
2101                         for (j = 0; j < cnt_used; ++j)
2102                                 if (overlap(&s, used + j)) { // no, it's not
2103                                         priv->top = 0;
2104                                         priv->height = 0;
2105                                 }
2106                         if (priv->height > 0) { // still a fixed event
2107                                 used[cnt_used].a = priv->top;
2108                                 used[cnt_used].b = priv->top + priv->height;
2109                                 cnt_used ++;
2110                                 shift_event(imgs + i, priv->top - imgs[i].top);
2111                         }
2112                 }
2113         }
2114         qsort(used, cnt_used, sizeof(segment_t), cmp_segment);
2115
2116         // try to fit other events in free spaces
2117         for (i = 0; i < cnt; ++i) {
2118                 render_priv_t* priv;
2119                 if (!imgs[i].detect_collisions) continue;
2120                 priv = get_render_priv(imgs[i].event);
2121                 if (priv->height == 0) { // not a fixed event
2122                         int shift;
2123                         segment_t s;
2124                         s.a = imgs[i].top;
2125                         s.b = imgs[i].top + imgs[i].height;
2126                         shift = fit_segment(&s, used, &cnt_used, imgs[i].shift_direction);
2127                         if (shift) shift_event(imgs + i, shift);
2128                         // make it fixed
2129                         priv->top = imgs[i].top;
2130                         priv->height = imgs[i].height;
2131                 }
2132
2133         }
2134 }
2135
2136 /**
2137  * \brief render a frame
2138  * \param priv library handle
2139  * \param track track
2140  * \param now current video timestamp (ms)
2141  */
2142 ass_image_t* ass_render_frame(ass_renderer_t *priv, ass_track_t* track, long long now)
2143 {
2144         int i, cnt, rc;
2145         event_images_t eimg[MAX_EVENTS];
2146         event_images_t* last;
2147         ass_image_t** tail;
2148
2149         // init frame
2150         rc = ass_start_frame(priv, track, now);
2151         if (rc != 0)
2152                 return 0;
2153
2154         // render events separately
2155         cnt = 0;
2156         for (i = 0; i < track->n_events; ++i) {
2157                 ass_event_t* event = track->events + i;
2158                 if ( (event->Start <= now) && (now < (event->Start + event->Duration)) ) {
2159                         if (cnt < MAX_EVENTS) {
2160                                 rc = ass_render_event(event, eimg + cnt);
2161                                 if (!rc) ++cnt;
2162                         } else {
2163                                 mp_msg(MSGT_ASS, MSGL_WARN, MSGTR_LIBASS_TooManySimultaneousEvents);
2164                                 break;
2165                         }
2166                 }
2167         }
2168
2169         // sort by layer
2170         qsort(eimg, cnt, sizeof(event_images_t), cmp_event_layer);
2171
2172         // call fix_collisions for each group of events with the same layer
2173         last = eimg;
2174         for (i = 1; i < cnt; ++i)
2175                 if (last->event->Layer != eimg[i].event->Layer) {
2176                         fix_collisions(last, eimg + i - last);
2177                         last = eimg + i;
2178                 }
2179         if (cnt > 0)
2180                 fix_collisions(last, eimg + cnt - last);
2181
2182         // concat lists
2183         tail = &ass_renderer->images_root;
2184         for (i = 0; i < cnt; ++i) {
2185                 ass_image_t* cur = eimg[i].imgs;
2186                 while (cur) {
2187                         *tail = cur;
2188                         tail = &cur->next;
2189                         cur = cur->next;
2190                 }
2191         }
2192
2193         return ass_renderer->images_root;
2194 }
2195