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