src/hb-ot-shape.cc

   1 /*
   2  * Copyright (C) 2009,2010  Red Hat, Inc.
   3  * Copyright (C) 2010  Google, Inc.
   4  *
   5  *  This is part of HarfBuzz, a text shaping library.
   6  *
   7  * Permission is hereby granted, without written agreement and without
   8  * license or royalty fees, to use, copy, modify, and distribute this
   9  * software and its documentation for any purpose, provided that the
  10  * above copyright notice and the following two paragraphs appear in
  11  * all copies of this software.
  12  *
  13  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  14  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  15  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  16  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  17  * DAMAGE.
  18  *
  19  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  20  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  21  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  22  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  23  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  24  *
  25  * Red Hat Author(s): Behdad Esfahbod
  26  * Google Author(s): Behdad Esfahbod
  27  */
  28
  29 #include "hb-ot-shape-private.h"
  30
  31 #include "hb-open-type-private.hh"
  32
  33 #include "hb-ot-layout.h"
  34
  35 HB_BEGIN_DECLS
  36
  37
  38 /* XXX vertical */
  39 hb_tag_t default_features[] = {
  40   HB_TAG('c','a','l','t'),
  41   HB_TAG('c','c','m','p'),
  42   HB_TAG('c','l','i','g'),
  43   HB_TAG('c','s','w','h'),
  44   HB_TAG('c','u','r','s'),
  45   HB_TAG('k','e','r','n'),
  46   HB_TAG('l','i','g','a'),
  47   HB_TAG('l','o','c','l'),
  48   HB_TAG('m','a','r','k'),
  49   HB_TAG('m','k','m','k'),
  50   HB_TAG('r','l','i','g')
  51 };
  52
  53 struct lookup_map {
  54   unsigned int index;
  55   hb_mask_t mask;
  56 };
  57
  58
  59 static void
  60 add_lookups (hb_face_t    *face,
  61              hb_tag_t      table_tag,
  62              unsigned int  feature_index,
  63              hb_mask_t     mask,
  64              lookup_map   *lookups,
  65              unsigned int *num_lookups,
  66              unsigned int  room_lookups)
  67 {
  68   unsigned int i = room_lookups - *num_lookups;
  69   lookups += *num_lookups;
  70
  71   unsigned int *lookup_indices = (unsigned int *) lookups;
  72
  73   hb_ot_layout_feature_get_lookup_indexes (face, table_tag, feature_index, 0,
  74                                            &i,
  75                                            lookup_indices);
  76
  77   *num_lookups += i;
  78
  79   while (i--) {
  80     lookups[i].mask = mask;
  81     lookups[i].index = lookup_indices[i];
  82   }
  83 }
  84
  85 static int
  86 cmp_lookups (const void *p1, const void *p2)
  87 {
  88   const lookup_map *a = (const lookup_map *) p1;
  89   const lookup_map *b = (const lookup_map *) p2;
  90
  91   return a->index - b->index;
  92 }
  93
  94
  95 #define MAX_FEATURES 100 /* FIXME */
  96
  97 struct hb_mask_allocator_t {
  98
  99   struct feature_info_t {
 100     hb_tag_t tag;
 101     unsigned int value;
 102     unsigned int seq;
 103     bool global;
 104
 105     static int
 106     cmp (const void *p1, const void *p2)
 107     {
 108       const feature_info_t *a = reinterpret_cast<const feature_info_t *>(p1);
 109       const feature_info_t *b = reinterpret_cast<const feature_info_t *>(p2);
 110
 111       if (a->tag != b->tag)
 112         return a->tag < b->tag ? -1 : 1;
 113
 114       return a->seq < b->seq ? -1 : 1;
 115     }
 116   };
 117
 118   struct feature_map_t {
 119     hb_tag_t tag; /* should be first */
 120     unsigned int index;
 121     unsigned int shift;
 122     hb_mask_t mask;
 123
 124     static int
 125     cmp (const void *p1, const void *p2)
 126     {
 127       const feature_map_t *a = reinterpret_cast<const feature_map_t *>(p1);
 128       const feature_map_t *b = reinterpret_cast<const feature_map_t *>(p2);
 129
 130       return a->tag < b->tag ? -1 : a->tag > b->tag ? 1 : 0;
 131     }
 132   };
 133
 134   hb_mask_allocator_t (void) : count (0) {}
 135
 136   void add_feature (hb_tag_t tag,
 137                     unsigned int value,
 138                     bool global)
 139   {
 140     feature_info_t *info = &infos[count++];
 141     info->tag = tag;
 142     info->value = value;
 143     info->seq = count;
 144     info->global = global;
 145   }
 146
 147   void compile (hb_face_t *face,
 148                 hb_tag_t table_tag,
 149                 unsigned int script_index,
 150                 unsigned int language_index)
 151   {
 152     global_mask = 0;
 153     unsigned int next_bit = 1;
 154
 155     if (!count)
 156       return;
 157
 158     qsort (infos, count, sizeof (infos[0]), feature_info_t::cmp);
 159
 160     unsigned int j = 0;
 161     for (unsigned int i = 1; i < count; i++)
 162       if (infos[i].tag != infos[j].tag)
 163         infos[++j] = infos[i];
 164       else {
 165         if (infos[i].global)
 166           infos[j] = infos[i];
 167         else {
 168           infos[j].global = infos[j].global && (infos[j].value == infos[i].value);
 169           infos[j].value = MAX (infos[j].value, infos[i].value);
 170         }
 171       }
 172     count = j + 1;
 173
 174     /* Allocate bits now */
 175     j = 0;
 176     for (unsigned int i = 0; i < count; i++) {
 177       const feature_info_t *info = &infos[i];
 178
 179       unsigned int bits_needed;
 180
 181       if (info->global && info->value == 1)
 182         /* Uses the global bit */
 183         bits_needed = 0;
 184       else
 185         bits_needed = _hb_bit_storage (info->value);
 186
 187       if (!info->value || next_bit + bits_needed > 8 * sizeof (hb_mask_t))
 188         continue; /* Feature disabled, or not enough bits. */
 189
 190       unsigned int feature_index;
 191       if (!hb_ot_layout_language_find_feature (face, table_tag, script_index, language_index,
 192                                                info->tag, &feature_index))
 193         continue;
 194
 195       feature_map_t *map = &maps[j++];
 196
 197       map->tag = info->tag;
 198       map->index = feature_index;
 199       if (info->global && info->value == 1) {
 200         /* Use the global bit */
 201         map->shift = 0;
 202         map->mask = 1;
 203       } else {
 204         map->shift = next_bit;
 205         map->mask = (1 << (next_bit + bits_needed)) - (1 << next_bit);
 206         next_bit += bits_needed;
 207       }
 208
 209       if (info->global && map->mask != 1)
 210         global_mask |= map->mask;
 211     }
 212     count = j;
 213   }
 214
 215   hb_mask_t get_global_mask (void) { return global_mask; }
 216
 217   const feature_map_t *get_features (unsigned int *num_features) const {
 218     *num_features = count;
 219     return maps;
 220   }
 221
 222
 223   const feature_map_t *find_feature (hb_tag_t tag) const {
 224     static const feature_map_t off_map = { HB_TAG_NONE, Index::NOT_FOUND_INDEX, 0, 0 };
 225     const feature_map_t *map = (const feature_map_t *) bsearch (&tag, maps, count, sizeof (maps[0]), feature_map_t::cmp);
 226     return map ? map : &off_map;
 227   }
 228
 229
 230   private:
 231
 232   unsigned int count;
 233   feature_info_t infos[MAX_FEATURES];
 234
 235   feature_map_t maps[MAX_FEATURES];
 236   hb_mask_t global_mask;
 237 };
 238
 239 static void
 240 hb_ot_shape_collect_features (hb_ot_shape_context_t *c,
 241                               hb_mask_allocator_t   *allocator)
 242 {
 243   switch (c->original_direction) {
 244     case HB_DIRECTION_LTR:
 245       allocator->add_feature (HB_TAG ('l','t','r','a'), 1, true);
 246       allocator->add_feature (HB_TAG ('l','t','r','m'), 1, true);
 247       break;
 248     case HB_DIRECTION_RTL:
 249       allocator->add_feature (HB_TAG ('r','t','l','a'), 1, true);
 250       allocator->add_feature (HB_TAG ('r','t','l','m'), 1, false);
 251       break;
 252     case HB_DIRECTION_TTB:
 253     case HB_DIRECTION_BTT:
 254     default:
 255       break;
 256   }
 257
 258   for (unsigned int i = 0; i < ARRAY_LENGTH (default_features); i++)
 259     allocator->add_feature (default_features[i], 1, true);
 260
 261   /* complex */
 262
 263   for (unsigned int i = 0; i < c->num_features; i++) {
 264     const hb_feature_t *feature = &c->features[i];
 265     allocator->add_feature (feature->tag, feature->value, (feature->start == 0 && feature->end == (unsigned int) -1));
 266   }
 267 }
 268
 269
 270 static void
 271 hb_ot_shape_setup_lookups (hb_ot_shape_context_t *c,
 272                            lookup_map            *lookups,
 273                            unsigned int          *num_lookups)
 274 {
 275   hb_mask_allocator_t allocator;
 276
 277   hb_ot_shape_collect_features (c, &allocator);
 278
 279   /* Compile features */
 280   unsigned int script_index, language_index, feature_index;
 281   unsigned int room_lookups;
 282
 283   hb_ot_layout_table_choose_script (c->face, c->table_tag,
 284                                     hb_ot_tags_from_script (c->buffer->props.script),
 285                                     &script_index);
 286   hb_ot_layout_script_find_language (c->face, c->table_tag, script_index,
 287                                      hb_ot_tag_from_language (c->buffer->props.language),
 288                                      &language_index);
 289
 290   allocator.compile (c->face, c->table_tag, script_index, language_index);
 291
 292
 293   /* Gather lookup indices for features */
 294
 295   room_lookups = *num_lookups;
 296   *num_lookups = 0;
 297
 298   if (hb_ot_layout_language_get_required_feature_index (c->face, c->table_tag, script_index, language_index,
 299                                                         &feature_index))
 300     add_lookups (c->face, c->table_tag, feature_index, 1, lookups, num_lookups, room_lookups);
 301
 302   const hb_mask_allocator_t::feature_map_t *map;
 303   unsigned int num_features;
 304
 305   map = allocator.get_features (&num_features);
 306   for (unsigned i = 0; i < num_features; i++)
 307     add_lookups (c->face, c->table_tag, map[i].index, map[i].mask, lookups, num_lookups, room_lookups);
 308
 309   /* Sort lookups and merge duplicates */
 310
 311   qsort (lookups, *num_lookups, sizeof (lookups[0]), cmp_lookups);
 312
 313   if (*num_lookups)
 314   {
 315     unsigned int j = 0;
 316     for (unsigned int i = 1; i < *num_lookups; i++)
 317       if (lookups[i].index != lookups[j].index)
 318         lookups[++j] = lookups[i];
 319       else
 320         lookups[j].mask |= lookups[i].mask;
 321     j++;
 322     *num_lookups = j;
 323   }
 324
 325
 326   /* Set masks in buffer */
 327
 328   hb_mask_t global_mask = allocator.get_global_mask ();
 329   if (global_mask)
 330     c->buffer->set_masks (global_mask, global_mask, 0, (unsigned int) -1);
 331
 332   for (unsigned int i = 0; i < c->num_features; i++)
 333   {
 334     hb_feature_t *feature = &c->features[i];
 335     map = allocator.find_feature (feature->tag);
 336     if (!(feature->start == 0 && feature->end == (unsigned int)-1))
 337       c->buffer->set_masks (feature->value << map->shift, map->mask, feature->start, feature->end);
 338   }
 339
 340   /* complex */
 341 }
 342
 343
 344 static void
 345 hb_ot_substitute_complex (hb_ot_shape_context_t *c)
 346 {
 347   lookup_map lookups[1000]; /* FIXME */
 348   unsigned int num_lookups = ARRAY_LENGTH (lookups);
 349
 350   if (!hb_ot_layout_has_substitution (c->face))
 351     return;
 352
 353   c->table_tag = HB_OT_TAG_GSUB;
 354
 355   hb_ot_shape_setup_lookups (c, lookups, &num_lookups);
 356
 357   for (unsigned int i = 0; i < num_lookups; i++)
 358     hb_ot_layout_substitute_lookup (c->face, c->buffer, lookups[i].index, lookups[i].mask);
 359
 360   c->applied_substitute_complex = TRUE;
 361   return;
 362 }
 363
 364 static void
 365 hb_ot_position_complex (hb_ot_shape_context_t *c)
 366 {
 367   lookup_map lookups[1000]; /* FIXME */
 368   unsigned int num_lookups = ARRAY_LENGTH (lookups);
 369
 370   if (!hb_ot_layout_has_positioning (c->face))
 371     return;
 372
 373   c->table_tag = HB_OT_TAG_GPOS;
 374
 375   hb_ot_shape_setup_lookups (c, lookups, &num_lookups);
 376
 377   for (unsigned int i = 0; i < num_lookups; i++)
 378     hb_ot_layout_position_lookup (c->font, c->face, c->buffer, lookups[i].index, lookups[i].mask);
 379
 380   hb_ot_layout_position_finish (c->font, c->face, c->buffer);
 381
 382   c->applied_position_complex = TRUE;
 383   return;
 384 }
 385
 386
 387 /* Main shaper */
 388
 389 /* Prepare */
 390
 391 static inline hb_bool_t
 392 is_variation_selector (hb_codepoint_t unicode)
 393 {
 394   return unlikely ((unicode >=  0x180B && unicode <=  0x180D) || /* MONGOLIAN FREE VARIATION SELECTOR ONE..THREE */
 395                    (unicode >=  0xFE00 && unicode <=  0xFE0F) || /* VARIATION SELECTOR-1..16 */
 396                    (unicode >= 0xE0100 && unicode <= 0xE01EF));  /* VARIATION SELECTOR-17..256 */
 397 }
 398
 399 static void
 400 hb_form_clusters (hb_buffer_t *buffer)
 401 {
 402   unsigned int count = buffer->len;
 403   for (unsigned int i = 1; i < count; i++)
 404     if (buffer->unicode->v.get_general_category (buffer->info[i].codepoint) == HB_CATEGORY_NON_SPACING_MARK)
 405       buffer->info[i].cluster = buffer->info[i - 1].cluster;
 406 }
 407
 408 static void
 409 hb_ensure_native_direction (hb_buffer_t *buffer)
 410 {
 411   hb_direction_t direction = buffer->props.direction;
 412
 413   /* TODO vertical */
 414   if (HB_DIRECTION_IS_HORIZONTAL (direction) &&
 415       direction != _hb_script_get_horizontal_direction (buffer->props.script))
 416   {
 417     hb_buffer_reverse_clusters (buffer);
 418     buffer->props.direction = HB_DIRECTION_REVERSE (buffer->props.direction);
 419   }
 420 }
 421
 422
 423 /* Substitute */
 424
 425 static void
 426 hb_mirror_chars (hb_buffer_t *buffer)
 427 {
 428   hb_unicode_get_mirroring_func_t get_mirroring = buffer->unicode->v.get_mirroring;
 429
 430   if (HB_DIRECTION_IS_FORWARD (buffer->props.direction))
 431     return;
 432
 433 //  map = allocator.find_feature (HB_TAG ('r','t','l','m'));
 434
 435   unsigned int count = buffer->len;
 436   for (unsigned int i = 0; i < count; i++) {
 437     hb_codepoint_t codepoint = get_mirroring (buffer->info[i].codepoint);
 438     if (likely (codepoint == buffer->info[i].codepoint))
 439 ;//      buffer->info[i].mask |= map->mask;
 440     else
 441       buffer->info[i].codepoint = codepoint;
 442   }
 443 }
 444
 445 static void
 446 hb_map_glyphs (hb_font_t    *font,
 447                hb_face_t    *face,
 448                hb_buffer_t  *buffer)
 449 {
 450   if (unlikely (!buffer->len))
 451     return;
 452
 453   buffer->clear_output ();
 454   unsigned int count = buffer->len - 1;
 455   for (buffer->i = 0; buffer->i < count;) {
 456     if (unlikely (is_variation_selector (buffer->info[buffer->i + 1].codepoint))) {
 457       buffer->add_output_glyph (hb_font_get_glyph (font, face, buffer->info[buffer->i].codepoint, buffer->info[buffer->i + 1].codepoint));
 458       buffer->i++;
 459     } else {
 460       buffer->add_output_glyph (hb_font_get_glyph (font, face, buffer->info[buffer->i].codepoint, 0));
 461     }
 462   }
 463   if (likely (buffer->i < buffer->len))
 464     buffer->add_output_glyph (hb_font_get_glyph (font, face, buffer->info[buffer->i].codepoint, 0));
 465   buffer->swap ();
 466 }
 467
 468 static void
 469 hb_substitute_default (hb_ot_shape_context_t *c)
 470 {
 471   hb_map_glyphs (c->font, c->face, c->buffer);
 472 }
 473
 474 static void
 475 hb_substitute_complex_fallback (hb_ot_shape_context_t *c HB_UNUSED)
 476 {
 477   /* TODO Arabic */
 478 }
 479
 480
 481 /* Position */
 482
 483 static void
 484 hb_position_default (hb_ot_shape_context_t *c)
 485 {
 486   hb_buffer_clear_positions (c->buffer);
 487
 488   unsigned int count = c->buffer->len;
 489   for (unsigned int i = 0; i < count; i++) {
 490     hb_glyph_metrics_t metrics;
 491     hb_font_get_glyph_metrics (c->font, c->face, c->buffer->info[i].codepoint, &metrics);
 492     c->buffer->pos[i].x_advance = metrics.x_advance;
 493     c->buffer->pos[i].y_advance = metrics.y_advance;
 494   }
 495 }
 496
 497 static void
 498 hb_position_complex_fallback (hb_ot_shape_context_t *c HB_UNUSED)
 499 {
 500   /* TODO Mark pos */
 501 }
 502
 503 static void
 504 hb_truetype_kern (hb_ot_shape_context_t *c)
 505 {
 506   /* TODO Check for kern=0 */
 507   unsigned int count = c->buffer->len;
 508   for (unsigned int i = 1; i < count; i++) {
 509     hb_position_t kern, kern1, kern2;
 510     kern = hb_font_get_kerning (c->font, c->face, c->buffer->info[i - 1].codepoint, c->buffer->info[i].codepoint);
 511     kern1 = kern >> 1;
 512     kern2 = kern - kern1;
 513     c->buffer->pos[i - 1].x_advance += kern1;
 514     c->buffer->pos[i].x_advance += kern2;
 515     c->buffer->pos[i].x_offset += kern2;
 516   }
 517 }
 518
 519 static void
 520 hb_position_complex_fallback_visual (hb_ot_shape_context_t *c)
 521 {
 522   hb_truetype_kern (c);
 523 }
 524
 525
 526 /* Do it! */
 527
 528 static void
 529 hb_ot_shape_internal (hb_ot_shape_context_t *c)
 530 {
 531   hb_form_clusters (c->buffer);
 532
 533   /* SUBSTITUTE */
 534   {
 535     c->buffer->clear_masks ();
 536
 537     /* Mirroring needs to see the original direction */
 538     hb_mirror_chars (c->buffer);
 539
 540     hb_ensure_native_direction (c->buffer);
 541
 542     hb_substitute_default (c);
 543
 544     hb_ot_substitute_complex (c);
 545
 546     if (!c->applied_substitute_complex)
 547       hb_substitute_complex_fallback (c);
 548   }
 549
 550   /* POSITION */
 551   {
 552     c->buffer->clear_masks ();
 553
 554     hb_position_default (c);
 555
 556     hb_ot_position_complex (c);
 557
 558     hb_bool_t position_fallback = !c->applied_position_complex;
 559     if (position_fallback)
 560       hb_position_complex_fallback (c);
 561
 562     if (HB_DIRECTION_IS_BACKWARD (c->buffer->props.direction))
 563       hb_buffer_reverse (c->buffer);
 564
 565     if (position_fallback)
 566       hb_position_complex_fallback_visual (c);
 567   }
 568
 569   c->buffer->props.direction = c->original_direction;
 570 }
 571
 572 void
 573 hb_ot_shape (hb_font_t    *font,
 574              hb_face_t    *face,
 575              hb_buffer_t  *buffer,
 576              hb_feature_t *features,
 577              unsigned int  num_features)
 578 {
 579   hb_ot_shape_context_t c = {font, face, buffer, features, num_features};
 580
 581   /* Setup transient context members */
 582   c.original_direction = buffer->props.direction;
 583
 584   hb_ot_shape_internal (&c);
 585 }
 586
 587
 588 HB_END_DECLS