hb-ot-shape-normalize.cc (15460B)
1 /* 2 * Copyright © 2011,2012 Google, 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 * Google Author(s): Behdad Esfahbod 25 */ 26 27 #include "hb.hh" 28 29 #ifndef HB_NO_OT_SHAPE 30 31 #include "hb-ot-shape-normalize.hh" 32 #include "hb-ot-shaper.hh" 33 #include "hb-ot-shape.hh" 34 35 36 /* 37 * HIGHLEVEL DESIGN: 38 * 39 * This file exports one main function: _hb_ot_shape_normalize(). 40 * 41 * This function closely reflects the Unicode Normalization Algorithm, 42 * yet it's different. 43 * 44 * Each shaper specifies whether it prefers decomposed (NFD) or composed (NFC). 45 * The logic however tries to use whatever the font can support. 46 * 47 * In general what happens is that: each grapheme is decomposed in a chain 48 * of 1:2 decompositions, marks reordered, and then recomposed if desired, 49 * so far it's like Unicode Normalization. However, the decomposition and 50 * recomposition only happens if the font supports the resulting characters. 51 * 52 * The goals are: 53 * 54 * - Try to render all canonically equivalent strings similarly. To really 55 * achieve this we have to always do the full decomposition and then 56 * selectively recompose from there. It's kinda too expensive though, so 57 * we skip some cases. For example, if composed is desired, we simply 58 * don't touch 1-character clusters that are supported by the font, even 59 * though their NFC may be different. 60 * 61 * - When a font has a precomposed character for a sequence but the 'ccmp' 62 * feature in the font is not adequate, use the precomposed character 63 * which typically has better mark positioning. 64 * 65 * - When a font does not support a combining mark, but supports it precomposed 66 * with previous base, use that. This needs the itemizer to have this 67 * knowledge too. We need to provide assistance to the itemizer. 68 * 69 * - When a font does not support a character but supports its canonical 70 * decomposition, well, use the decomposition. 71 * 72 * - The shapers can customize the compose and decompose functions to 73 * offload some of their requirements to the normalizer. For example, the 74 * Indic shaper may want to disallow recomposing of two matras. 75 */ 76 77 78 static inline void 79 set_glyph (hb_glyph_info_t &info, hb_font_t *font) 80 { 81 (void) font->get_nominal_glyph (info.codepoint, &info.normalizer_glyph_index()); 82 } 83 84 static inline void 85 output_char (hb_buffer_t *buffer, hb_codepoint_t unichar, hb_codepoint_t glyph) 86 { 87 /* This is very confusing indeed. */ 88 buffer->cur().normalizer_glyph_index() = glyph; 89 (void) buffer->output_glyph (unichar); 90 _hb_glyph_info_set_unicode_props (&buffer->prev(), buffer); 91 } 92 93 static inline void 94 next_char (hb_buffer_t *buffer, hb_codepoint_t glyph) 95 { 96 buffer->cur().normalizer_glyph_index() = glyph; 97 (void) buffer->next_glyph (); 98 } 99 100 static inline void 101 skip_char (hb_buffer_t *buffer) 102 { 103 buffer->skip_glyph (); 104 } 105 106 /* Returns 0 if didn't decompose, number of resulting characters otherwise. */ 107 static inline unsigned int 108 decompose (const hb_ot_shape_normalize_context_t *c, bool shortest, hb_codepoint_t ab) 109 { 110 hb_codepoint_t a = 0, b = 0, a_glyph = 0, b_glyph = 0; 111 hb_buffer_t * const buffer = c->buffer; 112 hb_font_t * const font = c->font; 113 114 if (!c->decompose (c, ab, &a, &b) || 115 (b && !font->get_nominal_glyph (b, &b_glyph))) 116 return 0; 117 118 bool has_a = (bool) font->get_nominal_glyph (a, &a_glyph); 119 if (shortest && has_a) { 120 /* Output a and b */ 121 output_char (buffer, a, a_glyph); 122 if (likely (b)) { 123 output_char (buffer, b, b_glyph); 124 return 2; 125 } 126 return 1; 127 } 128 129 if (unsigned ret = decompose (c, shortest, a)) { 130 if (b) { 131 output_char (buffer, b, b_glyph); 132 return ret + 1; 133 } 134 return ret; 135 } 136 137 if (has_a) { 138 output_char (buffer, a, a_glyph); 139 if (likely (b)) { 140 output_char (buffer, b, b_glyph); 141 return 2; 142 } 143 return 1; 144 } 145 146 return 0; 147 } 148 149 static inline void 150 decompose_current_character (const hb_ot_shape_normalize_context_t *c, bool shortest) 151 { 152 hb_buffer_t * const buffer = c->buffer; 153 hb_codepoint_t u = buffer->cur().codepoint; 154 hb_codepoint_t glyph = 0; 155 156 if (shortest && c->font->get_nominal_glyph (u, &glyph, buffer->not_found)) 157 { 158 next_char (buffer, glyph); 159 return; 160 } 161 162 if (decompose (c, shortest, u)) 163 { 164 skip_char (buffer); 165 return; 166 } 167 168 if (!shortest && c->font->get_nominal_glyph (u, &glyph, buffer->not_found)) 169 { 170 next_char (buffer, glyph); 171 return; 172 } 173 174 if (_hb_glyph_info_is_unicode_space (&buffer->cur())) 175 { 176 hb_codepoint_t space_glyph; 177 hb_unicode_funcs_t::space_t space_type = buffer->unicode->space_fallback_type (u); 178 if (space_type != hb_unicode_funcs_t::NOT_SPACE && 179 (c->font->get_nominal_glyph (0x0020, &space_glyph) || (space_glyph = buffer->invisible))) 180 { 181 _hb_glyph_info_set_unicode_space_fallback_type (&buffer->cur(), space_type); 182 next_char (buffer, space_glyph); 183 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_SPACE_FALLBACK; 184 return; 185 } 186 } 187 188 if (u == 0x2011u) 189 { 190 /* U+2011 is the only sensible character that is a no-break version of another character 191 * and not a space. The space ones are handled already. Handle this lone one. */ 192 hb_codepoint_t other_glyph; 193 if (c->font->get_nominal_glyph (0x2010u, &other_glyph)) 194 { 195 next_char (buffer, other_glyph); 196 return; 197 } 198 } 199 200 next_char (buffer, glyph); /* glyph is initialized in earlier branches. */ 201 } 202 203 static inline void 204 handle_variation_selector_cluster (const hb_ot_shape_normalize_context_t *c, 205 unsigned int end, 206 bool short_circuit HB_UNUSED) 207 { 208 /* Currently if there's a variation-selector we give-up on normalization, it's just too hard. */ 209 hb_buffer_t * const buffer = c->buffer; 210 hb_font_t * const font = c->font; 211 for (; buffer->idx < end - 1 && buffer->successful;) { 212 if (unlikely (buffer->unicode->is_variation_selector (buffer->cur(+1).codepoint))) { 213 if (font->get_variation_glyph (buffer->cur().codepoint, buffer->cur(+1).codepoint, &buffer->cur().normalizer_glyph_index())) 214 { 215 hb_codepoint_t unicode = buffer->cur().codepoint; 216 (void) buffer->replace_glyphs (2, 1, &unicode); 217 } 218 else 219 { 220 /* Just pass on the two characters separately, let GSUB do its magic. */ 221 set_glyph (buffer->cur(), font); 222 (void) buffer->next_glyph (); 223 224 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_VARIATION_SELECTOR_FALLBACK; 225 _hb_glyph_info_set_variation_selector (&buffer->cur(), true); 226 if (buffer->not_found_variation_selector != HB_CODEPOINT_INVALID) 227 _hb_glyph_info_clear_default_ignorable (&buffer->cur()); 228 229 set_glyph (buffer->cur(), font); 230 (void) buffer->next_glyph (); 231 } 232 /* Skip any further variation selectors. */ 233 while (buffer->idx < end && 234 buffer->successful && 235 unlikely (buffer->unicode->is_variation_selector (buffer->cur().codepoint))) 236 { 237 set_glyph (buffer->cur(), font); 238 (void) buffer->next_glyph (); 239 } 240 } 241 else 242 { 243 set_glyph (buffer->cur(), font); 244 (void) buffer->next_glyph (); 245 } 246 } 247 if (likely (buffer->idx < end)) 248 { 249 set_glyph (buffer->cur(), font); 250 (void) buffer->next_glyph (); 251 } 252 } 253 254 static inline void 255 decompose_multi_char_cluster (const hb_ot_shape_normalize_context_t *c, unsigned int end, bool short_circuit) 256 { 257 hb_buffer_t * const buffer = c->buffer; 258 for (unsigned int i = buffer->idx; i < end && buffer->successful; i++) 259 if (unlikely (buffer->unicode->is_variation_selector (buffer->info[i].codepoint))) { 260 handle_variation_selector_cluster (c, end, short_circuit); 261 return; 262 } 263 264 while (buffer->idx < end && buffer->successful) 265 decompose_current_character (c, short_circuit); 266 } 267 268 269 static int 270 compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb) 271 { 272 unsigned int a = _hb_glyph_info_get_modified_combining_class (pa); 273 unsigned int b = _hb_glyph_info_get_modified_combining_class (pb); 274 275 return a < b ? -1 : a == b ? 0 : +1; 276 } 277 278 279 void 280 _hb_ot_shape_normalize (const hb_ot_shape_plan_t *plan, 281 hb_buffer_t *buffer, 282 hb_font_t *font) 283 { 284 if (unlikely (!buffer->len)) return; 285 286 _hb_buffer_assert_unicode_vars (buffer); 287 288 hb_ot_shape_normalization_mode_t mode = plan->shaper->normalization_preference; 289 if (mode == HB_OT_SHAPE_NORMALIZATION_MODE_AUTO) 290 { 291 if (plan->has_gpos_mark) 292 // https://github.com/harfbuzz/harfbuzz/issues/653#issuecomment-423905920 293 //mode = HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED; 294 mode = HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS; 295 else 296 mode = HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS; 297 } 298 299 hb_ot_shape_normalize_context_t c = { 300 plan, 301 buffer, 302 font, 303 buffer->unicode, 304 plan->shaper->decompose ? plan->shaper->decompose : hb_ot_shape_normalize_context_t::decompose_unicode, 305 plan->shaper->compose ? plan->shaper->compose : hb_ot_shape_normalize_context_t::compose_unicode 306 }; 307 c.override_decompose_and_compose (plan->shaper->decompose, plan->shaper->compose); 308 309 bool always_short_circuit = mode == HB_OT_SHAPE_NORMALIZATION_MODE_NONE; 310 bool might_short_circuit = always_short_circuit || 311 (mode != HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED && 312 mode != HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS_NO_SHORT_CIRCUIT); 313 unsigned int count; 314 315 /* We do a fairly straightforward yet custom normalization process in three 316 * separate rounds: decompose, reorder, recompose (if desired). Currently 317 * this makes two buffer swaps. We can make it faster by moving the last 318 * two rounds into the inner loop for the first round, but it's more readable 319 * this way. */ 320 321 322 /* First round, decompose */ 323 324 bool all_simple = true; 325 { 326 buffer->clear_output (); 327 count = buffer->len; 328 buffer->idx = 0; 329 do 330 { 331 unsigned int end; 332 for (end = buffer->idx + 1; end < count; end++) 333 if (_hb_glyph_info_is_unicode_mark (&buffer->info[end])) 334 break; 335 336 if (end < count) 337 end--; /* Leave one base for the marks to cluster with. */ 338 339 /* From idx to end are simple clusters. */ 340 if (might_short_circuit) 341 { 342 unsigned int done = font->get_nominal_glyphs (end - buffer->idx, 343 &buffer->cur().codepoint, 344 sizeof (buffer->info[0]), 345 &buffer->cur().normalizer_glyph_index(), 346 sizeof (buffer->info[0])); 347 if (unlikely (!buffer->next_glyphs (done))) break; 348 } 349 while (buffer->idx < end && buffer->successful) 350 decompose_current_character (&c, might_short_circuit); 351 352 if (buffer->idx == count || !buffer->successful) 353 break; 354 355 all_simple = false; 356 357 /* Find all the marks now. */ 358 for (end = buffer->idx + 1; end < count; end++) 359 if (!_hb_glyph_info_is_unicode_mark(&buffer->info[end])) 360 break; 361 362 /* idx to end is one non-simple cluster. */ 363 decompose_multi_char_cluster (&c, end, always_short_circuit); 364 } 365 while (buffer->idx < count && buffer->successful); 366 buffer->sync (); 367 } 368 369 370 /* Second round, reorder (inplace) */ 371 372 if (!all_simple && buffer->message(font, "start reorder")) 373 { 374 count = buffer->len; 375 hb_glyph_info_t *info = buffer->info; 376 for (unsigned int i = 0; i < count; i++) 377 { 378 if (_hb_glyph_info_get_modified_combining_class (&info[i]) == 0) 379 continue; 380 381 unsigned int end; 382 for (end = i + 1; end < count; end++) 383 if (_hb_glyph_info_get_modified_combining_class (&info[end]) == 0) 384 break; 385 386 /* We are going to do a O(n^2). Only do this if the sequence is short. */ 387 if (end - i > HB_OT_SHAPE_MAX_COMBINING_MARKS) { 388 i = end; 389 continue; 390 } 391 392 buffer->sort (i, end, compare_combining_class); 393 394 if (plan->shaper->reorder_marks) 395 plan->shaper->reorder_marks (plan, buffer, i, end); 396 397 i = end; 398 } 399 (void) buffer->message(font, "end reorder"); 400 } 401 if (buffer->scratch_flags & HB_BUFFER_SCRATCH_FLAG_HAS_CGJ) 402 { 403 /* For all CGJ, check if it prevented any reordering at all. 404 * If it did NOT, then make it skippable. 405 * https://github.com/harfbuzz/harfbuzz/issues/554 406 */ 407 unsigned count = buffer->len; 408 hb_glyph_info_t *info = buffer->info; 409 for (unsigned int i = 1; i + 1 < count; i++) 410 if (info[i].codepoint == 0x034Fu/*CGJ*/ && 411 (info_cc(info[i+1]) == 0 || info_cc(info[i-1]) <= info_cc(info[i+1]))) 412 { 413 _hb_glyph_info_unhide (&info[i]); 414 } 415 } 416 417 418 /* Third round, recompose */ 419 420 if (!all_simple && 421 buffer->successful && 422 (mode == HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS || 423 mode == HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS_NO_SHORT_CIRCUIT)) 424 { 425 /* As noted in the comment earlier, we don't try to combine 426 * ccc=0 chars with their previous Starter. */ 427 428 buffer->clear_output (); 429 count = buffer->len; 430 unsigned int starter = 0; 431 (void) buffer->next_glyph (); 432 while (buffer->idx < count /* No need for: && buffer->successful */) 433 { 434 hb_codepoint_t composed, glyph; 435 if (/* We don't try to compose a non-mark character with it's preceding starter. 436 * This is both an optimization to avoid trying to compose every two neighboring 437 * glyphs in most scripts AND a desired feature for Hangul. Apparently Hangul 438 * fonts are not designed to mix-and-match pre-composed syllables and Jamo. */ 439 _hb_glyph_info_is_unicode_mark(&buffer->cur())) 440 { 441 if (/* If there's anything between the starter and this char, they should have CCC 442 * smaller than this character's. */ 443 (starter == buffer->out_len - 1 || 444 info_cc (buffer->prev()) < info_cc (buffer->cur())) && 445 /* And compose. */ 446 c.compose (&c, 447 buffer->out_info[starter].codepoint, 448 buffer->cur().codepoint, 449 &composed) && 450 /* And the font has glyph for the composite. */ 451 font->get_nominal_glyph (composed, &glyph)) 452 { 453 /* Composes. */ 454 if (unlikely (!buffer->next_glyph ())) break; /* Copy to out-buffer. */ 455 buffer->merge_out_clusters (starter, buffer->out_len); 456 buffer->out_len--; /* Remove the second composable. */ 457 /* Modify starter and carry on. */ 458 buffer->out_info[starter].codepoint = composed; 459 buffer->out_info[starter].normalizer_glyph_index() = glyph; 460 _hb_glyph_info_set_unicode_props (&buffer->out_info[starter], buffer); 461 462 continue; 463 } 464 } 465 466 /* Blocked, or doesn't compose. */ 467 if (unlikely (!buffer->next_glyph ())) break; 468 469 if (info_cc (buffer->prev()) == 0) 470 starter = buffer->out_len - 1; 471 } 472 buffer->sync (); 473 } 474 } 475 476 477 #endif