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