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