libass/ass_shaper.c

   1 /*
   2  * Copyright (C) 2011 Grigori Goronzy <greg@chown.ath.cx>
   3  *
   4  * This file is part of libass.
   5  *
   6  * Permission to use, copy, modify, and distribute this software for any
   7  * purpose with or without fee is hereby granted, provided that the above
   8  * copyright notice and this permission notice appear in all copies.
   9  *
  10  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  11  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
  12  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
  13  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
  14  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
  15  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
  16  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
  17  */
  18
  19 #include "config.h"
  20
  21 #include <fribidi/fribidi.h>
  22
  23 #include "ass_shaper.h"
  24 #include "ass_render.h"
  25 #include "ass_font.h"
  26 #include "ass_parse.h"
  27 #include "ass_cache.h"
  28
  29 #define MAX_RUNS 50
  30
  31 #ifdef CONFIG_HARFBUZZ
  32 #include <hb-ft.h>
  33 enum {
  34     VERT = 0,
  35     VKNA,
  36     KERN
  37 };
  38 #define NUM_FEATURES 3
  39 #endif
  40
  41 struct ass_shaper {
  42     ASS_ShapingLevel shaping_level;
  43
  44     // FriBidi log2vis
  45     int n_glyphs;
  46     FriBidiChar *event_text;
  47     FriBidiCharType *ctypes;
  48     FriBidiLevel *emblevels;
  49     FriBidiStrIndex *cmap;
  50     FriBidiParType base_direction;
  51
  52 #ifdef CONFIG_HARFBUZZ
  53     // OpenType features
  54     int n_features;
  55     hb_feature_t *features;
  56     hb_language_t language;
  57
  58     // Glyph metrics cache, to speed up shaping
  59     Cache *metrics_cache;
  60 #endif
  61 };
  62
  63 #ifdef CONFIG_HARFBUZZ
  64 struct ass_shaper_metrics_data {
  65     Cache *metrics_cache;
  66     GlyphMetricsHashKey hash_key;
  67     int vertical;
  68 };
  69
  70 struct ass_shaper_font_data {
  71     hb_font_t *fonts[ASS_FONT_MAX_FACES];
  72     hb_font_funcs_t *font_funcs[ASS_FONT_MAX_FACES];
  73     struct ass_shaper_metrics_data *metrics_data[ASS_FONT_MAX_FACES];
  74 };
  75 #endif
  76
  77 /**
  78  * \brief Print version information
  79  */
  80 void ass_shaper_info(ASS_Library *lib)
  81 {
  82     ass_msg(lib, MSGL_V, "Shaper: FriBidi "
  83             FRIBIDI_VERSION " (SIMPLE)"
  84 #ifdef CONFIG_HARFBUZZ
  85             " HarfBuzz-ng %s (COMPLEX)", hb_version_string()
  86 #endif
  87            );
  88 }
  89
  90 /**
  91  * \brief grow arrays, if needed
  92  * \param new_size requested size
  93  */
  94 static void check_allocations(ASS_Shaper *shaper, size_t new_size)
  95 {
  96     if (new_size > shaper->n_glyphs) {
  97         shaper->event_text = realloc(shaper->event_text, sizeof(FriBidiChar) * new_size);
  98         shaper->ctypes     = realloc(shaper->ctypes, sizeof(FriBidiCharType) * new_size);
  99         shaper->emblevels  = realloc(shaper->emblevels, sizeof(FriBidiLevel) * new_size);
 100         shaper->cmap       = realloc(shaper->cmap, sizeof(FriBidiStrIndex) * new_size);
 101     }
 102 }
 103
 104 /**
 105  * \brief Free shaper and related data
 106  */
 107 void ass_shaper_free(ASS_Shaper *shaper)
 108 {
 109 #ifdef CONFIG_HARFBUZZ
 110     ass_cache_done(shaper->metrics_cache);
 111     free(shaper->features);
 112 #endif
 113     free(shaper->event_text);
 114     free(shaper->ctypes);
 115     free(shaper->emblevels);
 116     free(shaper->cmap);
 117     free(shaper);
 118 }
 119
 120 void ass_shaper_font_data_free(ASS_ShaperFontData *priv)
 121 {
 122 #ifdef CONFIG_HARFBUZZ
 123     int i;
 124     for (i = 0; i < ASS_FONT_MAX_FACES; i++)
 125         if (priv->fonts[i]) {
 126             free(priv->metrics_data[i]);
 127             hb_font_destroy(priv->fonts[i]);
 128             hb_font_funcs_destroy(priv->font_funcs[i]);
 129         }
 130     free(priv);
 131 #endif
 132 }
 133
 134 #ifdef CONFIG_HARFBUZZ
 135 /**
 136  * \brief set up the HarfBuzz OpenType feature list with some
 137  * standard features.
 138  */
 139 static void init_features(ASS_Shaper *shaper)
 140 {
 141     shaper->features = calloc(sizeof(hb_feature_t), NUM_FEATURES);
 142
 143     shaper->n_features = NUM_FEATURES;
 144     shaper->features[VERT].tag = HB_TAG('v', 'e', 'r', 't');
 145     shaper->features[VERT].end = INT_MAX;
 146     shaper->features[VKNA].tag = HB_TAG('v', 'k', 'n', 'a');
 147     shaper->features[VKNA].end = INT_MAX;
 148     shaper->features[KERN].tag = HB_TAG('k', 'e', 'r', 'n');
 149     shaper->features[KERN].end = INT_MAX;
 150 }
 151
 152 /**
 153  * \brief Set features depending on properties of the run
 154  */
 155 static void set_run_features(ASS_Shaper *shaper, GlyphInfo *info)
 156 {
 157         // enable vertical substitutions for @font runs
 158         if (info->font->desc.vertical)
 159             shaper->features[VERT].value = shaper->features[VKNA].value = 1;
 160         else
 161             shaper->features[VERT].value = shaper->features[VKNA].value = 0;
 162 }
 163
 164 /**
 165  * \brief Update HarfBuzz's idea of font metrics
 166  * \param hb_font HarfBuzz font
 167  * \param face associated FreeType font face
 168  */
 169 static void update_hb_size(hb_font_t *hb_font, FT_Face face)
 170 {
 171     hb_font_set_scale (hb_font,
 172             ((uint64_t) face->size->metrics.x_scale * (uint64_t) face->units_per_EM) >> 16,
 173             ((uint64_t) face->size->metrics.y_scale * (uint64_t) face->units_per_EM) >> 16);
 174     hb_font_set_ppem (hb_font, face->size->metrics.x_ppem,
 175             face->size->metrics.y_ppem);
 176 }
 177
 178
 179 /*
 180  * Cached glyph metrics getters follow
 181  *
 182  * These functions replace HarfBuzz' standard FreeType font functions
 183  * and provide cached access to essential glyph metrics. This usually
 184  * speeds up shaping a lot. It also allows us to use custom load flags.
 185  *
 186  */
 187
 188 GlyphMetricsHashValue *
 189 get_cached_metrics(struct ass_shaper_metrics_data *metrics, FT_Face face,
 190                    hb_codepoint_t glyph)
 191 {
 192     GlyphMetricsHashValue *val;
 193
 194     metrics->hash_key.glyph_index = glyph;
 195     val = ass_cache_get(metrics->metrics_cache, &metrics->hash_key);
 196
 197     if (!val) {
 198         int load_flags = FT_LOAD_DEFAULT | FT_LOAD_IGNORE_GLOBAL_ADVANCE_WIDTH
 199             | FT_LOAD_IGNORE_TRANSFORM;
 200         GlyphMetricsHashValue new_val;
 201
 202         if (FT_Load_Glyph(face, glyph, load_flags))
 203             return NULL;
 204
 205         memcpy(&new_val.metrics, &face->glyph->metrics, sizeof(FT_Glyph_Metrics));
 206
 207         // if @font rendering is enabled and the glyph should be rotated,
 208         // make cached_h_advance pick up the right advance later
 209         if (metrics->vertical && glyph >= VERTICAL_LOWER_BOUND)
 210             new_val.metrics.horiAdvance = new_val.metrics.vertAdvance;
 211
 212         val = ass_cache_put(metrics->metrics_cache, &metrics->hash_key, &new_val);
 213     }
 214
 215     return val;
 216 }
 217
 218 static hb_bool_t
 219 get_glyph(hb_font_t *font, void *font_data, hb_codepoint_t unicode,
 220           hb_codepoint_t variation, hb_codepoint_t *glyph, void *user_data)
 221 {
 222     FT_Face face = font_data;
 223
 224     if (variation)
 225         *glyph = FT_Face_GetCharVariantIndex(face, unicode, variation);
 226     else
 227         *glyph = FT_Get_Char_Index(face, unicode);
 228
 229     return *glyph != 0;
 230 }
 231
 232 static hb_position_t
 233 cached_h_advance(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 234                  void *user_data)
 235 {
 236     FT_Face face = font_data;
 237     struct ass_shaper_metrics_data *metrics_priv = user_data;
 238     GlyphMetricsHashValue *metrics = get_cached_metrics(metrics_priv, face, glyph);
 239
 240     if (!metrics)
 241         return 0;
 242
 243     return metrics->metrics.horiAdvance;
 244 }
 245
 246 static hb_position_t
 247 cached_v_advance(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 248                  void *user_data)
 249 {
 250     FT_Face face = font_data;
 251     struct ass_shaper_metrics_data *metrics_priv = user_data;
 252     GlyphMetricsHashValue *metrics = get_cached_metrics(metrics_priv, face, glyph);
 253
 254     if (!metrics)
 255         return 0;
 256
 257     return metrics->metrics.vertAdvance;
 258
 259 }
 260
 261 static hb_bool_t
 262 cached_h_origin(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 263                 hb_position_t *x, hb_position_t *y, void *user_data)
 264 {
 265     return 1;
 266 }
 267
 268 static hb_bool_t
 269 cached_v_origin(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 270                 hb_position_t *x, hb_position_t *y, void *user_data)
 271 {
 272     FT_Face face = font_data;
 273     struct ass_shaper_metrics_data *metrics_priv = user_data;
 274     GlyphMetricsHashValue *metrics = get_cached_metrics(metrics_priv, face, glyph);
 275
 276     if (!metrics)
 277         return 0;
 278
 279     *x = metrics->metrics.horiBearingX - metrics->metrics.vertBearingX;
 280     *y = metrics->metrics.horiBearingY - (-metrics->metrics.vertBearingY);
 281
 282     return 1;
 283 }
 284
 285 static hb_position_t
 286 get_h_kerning(hb_font_t *font, void *font_data, hb_codepoint_t first,
 287                  hb_codepoint_t second, void *user_data)
 288 {
 289     FT_Face face = font_data;
 290     FT_Vector kern;
 291
 292     if (FT_Get_Kerning (face, first, second, FT_KERNING_DEFAULT, &kern))
 293         return 0;
 294
 295     return kern.x;
 296 }
 297
 298 static hb_position_t
 299 get_v_kerning(hb_font_t *font, void *font_data, hb_codepoint_t first,
 300                  hb_codepoint_t second, void *user_data)
 301 {
 302     return 0;
 303 }
 304
 305 static hb_bool_t
 306 cached_extents(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 307                hb_glyph_extents_t *extents, void *user_data)
 308 {
 309     FT_Face face = font_data;
 310     struct ass_shaper_metrics_data *metrics_priv = user_data;
 311     GlyphMetricsHashValue *metrics = get_cached_metrics(metrics_priv, face, glyph);
 312
 313     if (!metrics)
 314         return 0;
 315
 316     extents->x_bearing = metrics->metrics.horiBearingX;
 317     extents->y_bearing = metrics->metrics.horiBearingY;
 318     extents->width     = metrics->metrics.width;
 319     extents->height    = metrics->metrics.height;
 320
 321     return 1;
 322 }
 323
 324 static hb_bool_t
 325 get_contour_point(hb_font_t *font, void *font_data, hb_codepoint_t glyph,
 326                      unsigned int point_index, hb_position_t *x,
 327                      hb_position_t *y, void *user_data)
 328 {
 329     FT_Face face = font_data;
 330     int load_flags = FT_LOAD_DEFAULT | FT_LOAD_IGNORE_GLOBAL_ADVANCE_WIDTH
 331         | FT_LOAD_IGNORE_TRANSFORM;
 332
 333     if (FT_Load_Glyph(face, glyph, load_flags))
 334         return 0;
 335
 336     if (point_index >= (unsigned)face->glyph->outline.n_points)
 337         return 0;
 338
 339     *x = face->glyph->outline.points[point_index].x;
 340     *y = face->glyph->outline.points[point_index].y;
 341
 342     return 1;
 343 }
 344
 345 /**
 346  * \brief Retrieve HarfBuzz font from cache.
 347  * Create it from FreeType font, if needed.
 348  * \param info glyph cluster
 349  * \return HarfBuzz font
 350  */
 351 static hb_font_t *get_hb_font(ASS_Shaper *shaper, GlyphInfo *info)
 352 {
 353     ASS_Font *font = info->font;
 354     hb_font_t **hb_fonts;
 355
 356     if (!font->shaper_priv)
 357         font->shaper_priv = calloc(sizeof(ASS_ShaperFontData), 1);
 358
 359
 360     hb_fonts = font->shaper_priv->fonts;
 361     if (!hb_fonts[info->face_index]) {
 362         hb_fonts[info->face_index] =
 363             hb_ft_font_create(font->faces[info->face_index], NULL);
 364
 365         // set up cached metrics access
 366         font->shaper_priv->metrics_data[info->face_index] =
 367             calloc(sizeof(struct ass_shaper_metrics_data), 1);
 368         struct ass_shaper_metrics_data *metrics =
 369             font->shaper_priv->metrics_data[info->face_index];
 370         metrics->metrics_cache = shaper->metrics_cache;
 371         metrics->vertical = info->font->desc.vertical;
 372
 373         hb_font_funcs_t *funcs = hb_font_funcs_create();
 374         font->shaper_priv->font_funcs[info->face_index] = funcs;
 375         hb_font_funcs_set_glyph_func(funcs, get_glyph,
 376                 metrics, NULL);
 377         hb_font_funcs_set_glyph_h_advance_func(funcs, cached_h_advance,
 378                 metrics, NULL);
 379         hb_font_funcs_set_glyph_v_advance_func(funcs, cached_v_advance,
 380                 metrics, NULL);
 381         hb_font_funcs_set_glyph_h_origin_func(funcs, cached_h_origin,
 382                 metrics, NULL);
 383         hb_font_funcs_set_glyph_v_origin_func(funcs, cached_v_origin,
 384                 metrics, NULL);
 385         hb_font_funcs_set_glyph_h_kerning_func(funcs, get_h_kerning,
 386                 metrics, NULL);
 387         hb_font_funcs_set_glyph_v_kerning_func(funcs, get_v_kerning,
 388                 metrics, NULL);
 389         hb_font_funcs_set_glyph_extents_func(funcs, cached_extents,
 390                 metrics, NULL);
 391         hb_font_funcs_set_glyph_contour_point_func(funcs, get_contour_point,
 392                 metrics, NULL);
 393         hb_font_set_funcs(hb_fonts[info->face_index], funcs,
 394                 font->faces[info->face_index], NULL);
 395     }
 396
 397     // XXX: this is a rather crude hack
 398     const double ft_size = 256.0;
 399     ass_face_set_size(font->faces[info->face_index], ft_size);
 400     update_hb_size(hb_fonts[info->face_index], font->faces[info->face_index]);
 401
 402     // update hash key for cached metrics
 403     struct ass_shaper_metrics_data *metrics =
 404         font->shaper_priv->metrics_data[info->face_index];
 405     metrics->hash_key.font = info->font;
 406     metrics->hash_key.face_index = info->face_index;
 407     metrics->hash_key.size = info->font_size;
 408     metrics->hash_key.scale_x = double_to_d6(info->scale_x);
 409     metrics->hash_key.scale_y = double_to_d6(info->scale_y);
 410
 411     return hb_fonts[info->face_index];
 412 }
 413
 414 /**
 415  * \brief Map script to default language.
 416  *
 417  * This maps a script to a language, if a script has a representative
 418  * language it is typically used with. Otherwise, the invalid language
 419  * is returned.
 420  *
 421  * The mapping is similar to Pango's pango-language.c.
 422  *
 423  * \param script script tag
 424  * \return language tag
 425  */
 426 static hb_language_t script_to_language(hb_script_t script)
 427 {
 428     switch (script) {
 429         // Unicode 1.1
 430         case HB_SCRIPT_ARABIC: return hb_language_from_string("ar", -1); break;
 431         case HB_SCRIPT_ARMENIAN: return hb_language_from_string("hy", -1); break;
 432         case HB_SCRIPT_BENGALI: return hb_language_from_string("bn", -1); break;
 433         case HB_SCRIPT_CANADIAN_ABORIGINAL: return hb_language_from_string("iu", -1); break;
 434         case HB_SCRIPT_CHEROKEE: return hb_language_from_string("chr", -1); break;
 435         case HB_SCRIPT_COPTIC: return hb_language_from_string("cop", -1); break;
 436         case HB_SCRIPT_CYRILLIC: return hb_language_from_string("ru", -1); break;
 437         case HB_SCRIPT_DEVANAGARI: return hb_language_from_string("hi", -1); break;
 438         case HB_SCRIPT_GEORGIAN: return hb_language_from_string("ka", -1); break;
 439         case HB_SCRIPT_GREEK: return hb_language_from_string("el", -1); break;
 440         case HB_SCRIPT_GUJARATI: return hb_language_from_string("gu", -1); break;
 441         case HB_SCRIPT_GURMUKHI: return hb_language_from_string("pa", -1); break;
 442         case HB_SCRIPT_HANGUL: return hb_language_from_string("ko", -1); break;
 443         case HB_SCRIPT_HEBREW: return hb_language_from_string("he", -1); break;
 444         case HB_SCRIPT_HIRAGANA: return hb_language_from_string("ja", -1); break;
 445         case HB_SCRIPT_KANNADA: return hb_language_from_string("kn", -1); break;
 446         case HB_SCRIPT_KATAKANA: return hb_language_from_string("ja", -1); break;
 447         case HB_SCRIPT_LAO: return hb_language_from_string("lo", -1); break;
 448         case HB_SCRIPT_LATIN: return hb_language_from_string("en", -1); break;
 449         case HB_SCRIPT_MALAYALAM: return hb_language_from_string("ml", -1); break;
 450         case HB_SCRIPT_MONGOLIAN: return hb_language_from_string("mn", -1); break;
 451         case HB_SCRIPT_ORIYA: return hb_language_from_string("or", -1); break;
 452         case HB_SCRIPT_SYRIAC: return hb_language_from_string("syr", -1); break;
 453         case HB_SCRIPT_TAMIL: return hb_language_from_string("ta", -1); break;
 454         case HB_SCRIPT_TELUGU: return hb_language_from_string("te", -1); break;
 455         case HB_SCRIPT_THAI: return hb_language_from_string("th", -1); break;
 456
 457         // Unicode 2.0
 458         case HB_SCRIPT_TIBETAN: return hb_language_from_string("bo", -1); break;
 459
 460         // Unicode 3.0
 461         case HB_SCRIPT_ETHIOPIC: return hb_language_from_string("am", -1); break;
 462         case HB_SCRIPT_KHMER: return hb_language_from_string("km", -1); break;
 463         case HB_SCRIPT_MYANMAR: return hb_language_from_string("my", -1); break;
 464         case HB_SCRIPT_SINHALA: return hb_language_from_string("si", -1); break;
 465         case HB_SCRIPT_THAANA: return hb_language_from_string("dv", -1); break;
 466
 467         // Unicode 3.2
 468         case HB_SCRIPT_BUHID: return hb_language_from_string("bku", -1); break;
 469         case HB_SCRIPT_HANUNOO: return hb_language_from_string("hnn", -1); break;
 470         case HB_SCRIPT_TAGALOG: return hb_language_from_string("tl", -1); break;
 471         case HB_SCRIPT_TAGBANWA: return hb_language_from_string("tbw", -1); break;
 472
 473         // Unicode 4.0
 474         case HB_SCRIPT_UGARITIC: return hb_language_from_string("uga", -1); break;
 475
 476         // Unicode 4.1
 477         case HB_SCRIPT_BUGINESE: return hb_language_from_string("bug", -1); break;
 478         case HB_SCRIPT_OLD_PERSIAN: return hb_language_from_string("peo", -1); break;
 479         case HB_SCRIPT_SYLOTI_NAGRI: return hb_language_from_string("syl", -1); break;
 480
 481         // Unicode 5.0
 482         case HB_SCRIPT_NKO: return hb_language_from_string("nko", -1); break;
 483
 484         // no representative language exists
 485         default: return HB_LANGUAGE_INVALID; break;
 486     }
 487 }
 488
 489 /**
 490  * \brief Determine language to be used for shaping a run.
 491  *
 492  * \param shaper shaper instance
 493  * \param script script tag associated with run
 494  * \return language tag
 495  */
 496 static hb_language_t
 497 hb_shaper_get_run_language(ASS_Shaper *shaper, hb_script_t script)
 498 {
 499     hb_language_t lang;
 500
 501     // override set, use it
 502     if (shaper->language != HB_LANGUAGE_INVALID)
 503         return shaper->language;
 504
 505     // get default language for given script
 506     lang = script_to_language(script);
 507
 508     // no dice, use system default
 509     if (lang == HB_LANGUAGE_INVALID)
 510         lang = hb_language_get_default();
 511
 512     return lang;
 513 }
 514
 515 /**
 516  * \brief Shape event text with HarfBuzz. Full OpenType shaping.
 517  * \param glyphs glyph clusters
 518  * \param len number of clusters
 519  */
 520 static void shape_harfbuzz(ASS_Shaper *shaper, GlyphInfo *glyphs, size_t len)
 521 {
 522     int i, j;
 523     int run = 0;
 524     struct {
 525         int offset;
 526         int end;
 527         hb_buffer_t *buf;
 528         hb_font_t *font;
 529     } runs[MAX_RUNS];
 530     const double ft_size = 256.0;
 531
 532     for (i = 0; i < len && run < MAX_RUNS; i++, run++) {
 533         // get length and level of the current run
 534         int k = i;
 535         int level = glyphs[i].shape_run_id;
 536         int direction = shaper->emblevels[k] % 2;
 537         hb_script_t script = glyphs[i].script;
 538         while (i < (len - 1) && level == glyphs[i+1].shape_run_id)
 539             i++;
 540         runs[run].offset = k;
 541         runs[run].end    = i;
 542         runs[run].buf    = hb_buffer_create();
 543         runs[run].font   = get_hb_font(shaper, glyphs + k);
 544         set_run_features(shaper, glyphs + k);
 545         hb_buffer_pre_allocate(runs[run].buf, i - k + 1);
 546         hb_buffer_set_direction(runs[run].buf, direction ? HB_DIRECTION_RTL :
 547                 HB_DIRECTION_LTR);
 548         hb_buffer_set_language(runs[run].buf,
 549                 hb_shaper_get_run_language(shaper, script));
 550         hb_buffer_set_script(runs[run].buf, script);
 551         hb_buffer_add_utf32(runs[run].buf, shaper->event_text + k, i - k + 1,
 552                 0, i - k + 1);
 553         hb_shape(runs[run].font, runs[run].buf, shaper->features,
 554                 shaper->n_features);
 555     }
 556
 557     // Initialize: skip all glyphs, this is undone later as needed
 558     for (i = 0; i < len; i++)
 559         glyphs[i].skip = 1;
 560
 561     // Update glyph indexes, positions and advances from the shaped runs
 562     for (i = 0; i < run; i++) {
 563         int num_glyphs = hb_buffer_get_length(runs[i].buf);
 564         hb_glyph_info_t *glyph_info = hb_buffer_get_glyph_infos(runs[i].buf, NULL);
 565         hb_glyph_position_t *pos    = hb_buffer_get_glyph_positions(runs[i].buf, NULL);
 566
 567         for (j = 0; j < num_glyphs; j++) {
 568             int idx = glyph_info[j].cluster + runs[i].offset;
 569             GlyphInfo *info = glyphs + idx;
 570             GlyphInfo *root = info;
 571
 572             // if we have more than one glyph per cluster, allocate a new one
 573             // and attach to the root glyph
 574             if (info->skip == 0) {
 575                 while (info->next)
 576                     info = info->next;
 577                 info->next = malloc(sizeof(GlyphInfo));
 578                 memcpy(info->next, info, sizeof(GlyphInfo));
 579                 info = info->next;
 580                 info->next = NULL;
 581             }
 582
 583             // set position and advance
 584             info->skip = 0;
 585             info->glyph_index = glyph_info[j].codepoint;
 586             info->offset.x    = pos[j].x_offset * info->scale_x * (info->font_size / ft_size);
 587             info->offset.y    = -pos[j].y_offset * info->scale_y * (info->font_size / ft_size);
 588             info->advance.x   = pos[j].x_advance * info->scale_x * (info->font_size / ft_size);
 589             info->advance.y   = -pos[j].y_advance * info->scale_y * (info->font_size / ft_size);
 590
 591             // accumulate advance in the root glyph
 592             root->cluster_advance.x += info->advance.x;
 593             root->cluster_advance.y += info->advance.y;
 594         }
 595     }
 596
 597     // Free runs and associated data
 598     for (i = 0; i < run; i++) {
 599         hb_buffer_destroy(runs[i].buf);
 600     }
 601
 602 }
 603
 604 /**
 605  * \brief Determine script property of all characters. Characters of script
 606  * common and inherited get their script from their context.
 607  *
 608  */
 609 void ass_shaper_determine_script(ASS_Shaper *shaper, GlyphInfo *glyphs,
 610                                   size_t len)
 611 {
 612     int i;
 613     int backwards_scan = 0;
 614     hb_unicode_funcs_t *ufuncs = hb_unicode_funcs_get_default();
 615     hb_script_t last_script = HB_SCRIPT_UNKNOWN;
 616
 617     // determine script (forward scan)
 618     for (i = 0; i < len; i++) {
 619         GlyphInfo *info = glyphs + i;
 620         info->script = hb_unicode_script(ufuncs, info->symbol);
 621
 622         // common/inherit codepoints inherit script from context
 623         if (info->script == HB_SCRIPT_COMMON ||
 624                 info->script == HB_SCRIPT_INHERITED) {
 625             // unknown is not a valid context
 626             if (last_script != HB_SCRIPT_UNKNOWN)
 627                 info->script = last_script;
 628             else
 629                 // do a backwards scan to check if next codepoint
 630                 // contains a valid script for context
 631                 backwards_scan = 1;
 632         } else {
 633             last_script = info->script;
 634         }
 635     }
 636
 637     // determine script (backwards scan, if needed)
 638     last_script = HB_SCRIPT_UNKNOWN;
 639     for (i = len - 1; i >= 0 && backwards_scan; i--) {
 640         GlyphInfo *info = glyphs + i;
 641
 642         // common/inherit codepoints inherit script from context
 643         if (info->script == HB_SCRIPT_COMMON ||
 644                 info->script == HB_SCRIPT_INHERITED) {
 645             // unknown script is not a valid context
 646             if (last_script != HB_SCRIPT_UNKNOWN)
 647                 info->script = last_script;
 648         } else {
 649             last_script = info->script;
 650         }
 651     }
 652 }
 653 #endif
 654
 655 /**
 656  * \brief Shape event text with FriBidi. Does mirroring and simple
 657  * Arabic shaping.
 658  * \param len number of clusters
 659  */
 660 static void shape_fribidi(ASS_Shaper *shaper, GlyphInfo *glyphs, size_t len)
 661 {
 662     int i;
 663     FriBidiJoiningType *joins = calloc(sizeof(*joins), len);
 664
 665     // shape on codepoint level
 666     fribidi_get_joining_types(shaper->event_text, len, joins);
 667     fribidi_join_arabic(shaper->ctypes, len, shaper->emblevels, joins);
 668     fribidi_shape(FRIBIDI_FLAGS_DEFAULT | FRIBIDI_FLAGS_ARABIC,
 669             shaper->emblevels, len, joins, shaper->event_text);
 670
 671     // update indexes
 672     for (i = 0; i < len; i++) {
 673         GlyphInfo *info = glyphs + i;
 674         FT_Face face = info->font->faces[info->face_index];
 675         info->symbol = shaper->event_text[i];
 676         info->glyph_index = FT_Get_Char_Index(face, shaper->event_text[i]);
 677     }
 678
 679     free(joins);
 680 }
 681
 682 /**
 683  * \brief Toggle kerning for HarfBuzz shaping.
 684  * NOTE: currently only works with OpenType fonts, the TrueType fallback *always*
 685  * kerns. It's a bug in HarfBuzz.
 686  */
 687 void ass_shaper_set_kerning(ASS_Shaper *shaper, int kern)
 688 {
 689 #ifdef CONFIG_HARFBUZZ
 690     shaper->features[KERN].value = !!kern;
 691 #endif
 692 }
 693
 694 /**
 695  * \brief Find shape runs according to the event's selected fonts
 696  */
 697 void ass_shaper_find_runs(ASS_Shaper *shaper, ASS_Renderer *render_priv,
 698                           GlyphInfo *glyphs, size_t len)
 699 {
 700     int i;
 701     int shape_run = 0;
 702
 703 #ifdef CONFIG_HARFBUZZ
 704     ass_shaper_determine_script(shaper, glyphs, len);
 705 #endif
 706
 707     // find appropriate fonts for the shape runs
 708     for (i = 0; i < len; i++) {
 709         GlyphInfo *last = glyphs + i - 1;
 710         GlyphInfo *info = glyphs + i;
 711         // skip drawings
 712         if (info->symbol == 0xfffc)
 713             continue;
 714         // set size and get glyph index
 715         ass_font_get_index(render_priv->fontconfig_priv, info->font,
 716                 info->symbol, &info->face_index, &info->glyph_index);
 717         // shape runs share the same font face and size
 718         if (i > 0 && (last->font != info->font ||
 719                     last->font_size != info->font_size ||
 720                     last->face_index != info->face_index ||
 721                     last->script != info->script))
 722             shape_run++;
 723         info->shape_run_id = shape_run;
 724     }
 725 }
 726
 727 /**
 728  * \brief Set base direction (paragraph direction) of the text.
 729  * \param dir base direction
 730  */
 731 void ass_shaper_set_base_direction(ASS_Shaper *shaper, FriBidiParType dir)
 732 {
 733     shaper->base_direction = dir;
 734 }
 735
 736 /**
 737  * \brief Set language hint. Some languages have specific character variants,
 738  * like Serbian Cyrillic.
 739  * \param lang ISO 639-1 two-letter language code
 740  */
 741 void ass_shaper_set_language(ASS_Shaper *shaper, const char *code)
 742 {
 743 #ifdef CONFIG_HARFBUZZ
 744     hb_language_t lang;
 745
 746     if (code)
 747         lang = hb_language_from_string(code, -1);
 748     else
 749         lang = HB_LANGUAGE_INVALID;
 750
 751     shaper->language = lang;
 752 #endif
 753 }
 754
 755 /**
 756  * Set shaping level. Essentially switches between FriBidi and HarfBuzz.
 757  */
 758 void ass_shaper_set_level(ASS_Shaper *shaper, ASS_ShapingLevel level)
 759 {
 760     shaper->shaping_level = level;
 761 }
 762
 763 /**
 764   * \brief Remove all zero-width invisible characters from the text.
 765   * \param text_info text
 766   */
 767 static void ass_shaper_skip_characters(TextInfo *text_info)
 768 {
 769     int i;
 770     GlyphInfo *glyphs = text_info->glyphs;
 771
 772     for (i = 0; i < text_info->length; i++) {
 773         // Skip direction override control characters
 774         if ((glyphs[i].symbol <= 0x202e && glyphs[i].symbol >= 0x202a)
 775                 || (glyphs[i].symbol <= 0x200f && glyphs[i].symbol >= 0x200b)
 776                 || (glyphs[i].symbol <= 0x2063 && glyphs[i].symbol >= 0x2060)
 777                 || glyphs[i].symbol == 0xfeff
 778                 || glyphs[i].symbol == 0x00ad
 779                 || glyphs[i].symbol == 0x034f) {
 780             glyphs[i].symbol = 0;
 781             glyphs[i].skip++;
 782         }
 783     }
 784 }
 785
 786 /**
 787  * \brief Shape an event's text. Calculates directional runs and shapes them.
 788  * \param text_info event's text
 789  */
 790 void ass_shaper_shape(ASS_Shaper *shaper, TextInfo *text_info)
 791 {
 792     int i, last_break;
 793     FriBidiParType dir;
 794     GlyphInfo *glyphs = text_info->glyphs;
 795
 796     check_allocations(shaper, text_info->length);
 797
 798     // Get bidi character types and embedding levels
 799     last_break = 0;
 800     for (i = 0; i < text_info->length; i++) {
 801         shaper->event_text[i] = glyphs[i].symbol;
 802         // embedding levels should be calculated paragraph by paragraph
 803         if (glyphs[i].symbol == '\n' || i == text_info->length - 1) {
 804             dir = shaper->base_direction;
 805             fribidi_get_bidi_types(shaper->event_text + last_break,
 806                     i - last_break + 1, shaper->ctypes + last_break);
 807             fribidi_get_par_embedding_levels(shaper->ctypes + last_break,
 808                     i - last_break + 1, &dir, shaper->emblevels + last_break);
 809             last_break = i + 1;
 810         }
 811     }
 812
 813     // add embedding levels to shape runs for final runs
 814     for (i = 0; i < text_info->length; i++) {
 815         glyphs[i].shape_run_id += shaper->emblevels[i];
 816     }
 817
 818 #ifdef CONFIG_HARFBUZZ
 819     switch (shaper->shaping_level) {
 820     case ASS_SHAPING_SIMPLE:
 821         shape_fribidi(shaper, glyphs, text_info->length);
 822         ass_shaper_skip_characters(text_info);
 823         break;
 824     case ASS_SHAPING_COMPLEX:
 825         shape_harfbuzz(shaper, glyphs, text_info->length);
 826         break;
 827     }
 828 #else
 829         shape_fribidi(shaper, glyphs, text_info->length);
 830         ass_shaper_skip_characters(text_info);
 831 #endif
 832 }
 833
 834 /**
 835  * \brief Create a new shaper instance and preallocate data structures
 836  * \param prealloc preallocation size
 837  */
 838 ASS_Shaper *ass_shaper_new(size_t prealloc)
 839 {
 840     ASS_Shaper *shaper = calloc(sizeof(*shaper), 1);
 841
 842     shaper->base_direction = FRIBIDI_PAR_ON;
 843     check_allocations(shaper, prealloc);
 844
 845 #ifdef CONFIG_HARFBUZZ
 846     init_features(shaper);
 847     shaper->metrics_cache = ass_glyph_metrics_cache_create();
 848 #endif
 849
 850     return shaper;
 851 }
 852
 853
 854 /**
 855  * \brief clean up additional data temporarily needed for shaping and
 856  * (e.g. additional glyphs allocated)
 857  */
 858 void ass_shaper_cleanup(ASS_Shaper *shaper, TextInfo *text_info)
 859 {
 860     int i;
 861
 862     for (i = 0; i < text_info->length; i++) {
 863         GlyphInfo *info = text_info->glyphs + i;
 864         info = info->next;
 865         while (info) {
 866             GlyphInfo *next = info->next;
 867             free(info);
 868             info = next;
 869         }
 870     }
 871 }
 872
 873 /**
 874  * \brief Calculate reorder map to render glyphs in visual order
 875  */
 876 FriBidiStrIndex *ass_shaper_reorder(ASS_Shaper *shaper, TextInfo *text_info)
 877 {
 878     int i;
 879
 880     // Initialize reorder map
 881     for (i = 0; i < text_info->length; i++)
 882         shaper->cmap[i] = i;
 883
 884     // Create reorder map line-by-line
 885     for (i = 0; i < text_info->n_lines; i++) {
 886         LineInfo *line = text_info->lines + i;
 887         int level;
 888         FriBidiParType dir = FRIBIDI_PAR_ON;
 889
 890         level = fribidi_reorder_line(0,
 891                 shaper->ctypes + line->offset, line->len, 0, dir,
 892                 shaper->emblevels + line->offset, NULL,
 893                 shaper->cmap + line->offset);
 894     }
 895
 896     return shaper->cmap;
 897 }
 898
 899 /**
 900  * \brief Resolve a Windows font charset number to a suitable
 901  * base direction. 177 and 178 are Hebrew and Arabic respectively, and
 902  * they map to RTL. Everything else maps to LTR for compatibility
 903  * reasons. The special value -1, which is not a legal Windows font charset
 904  * number, can be used for autodetection.
 905  * \param enc Windows font encoding
 906  */
 907 FriBidiParType resolve_base_direction(int enc)
 908 {
 909     switch (enc) {
 910         case -1:
 911             return FRIBIDI_PAR_ON;
 912         case 177:
 913         case 178:
 914             return FRIBIDI_PAR_RTL;
 915         default:
 916             return FRIBIDI_PAR_LTR;
 917     }
 918 }