hb-ot-shape-normalize.cc revision dcdc51cdc0ba9d9fb75f84dd5fa7a49aa0b24ea0
1/* 2 * Copyright © 2011 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-ot-shape-private.hh" 28#include "hb-ot-shape-complex-private.hh" 29 30HB_BEGIN_DECLS 31 32/* 33 * HIGHLEVEL DESIGN: 34 * 35 * This file exports one main function: _hb_ot_shape_normalize(). 36 * 37 * This function closely reflects the Unicode Normalization Algorithm, 38 * yet it's different. The shaper an either prefer decomposed (NFD) or 39 * composed (NFC). 40 * 41 * In general what happens is that: each grapheme is decomposed in a chain 42 * of 1:2 decompositions, marks reordered, and then recomposed if desires, 43 * so far it's like Unicode Normalization. However, the decomposition and 44 * recomposition only happens if the font supports the resulting characters. 45 * 46 * The goals are: 47 * 48 * - Try to render all canonically equivalent strings similarly. To really 49 * achieve this we have to always do the full decomposition and then 50 * selectively recompose from there. It's kinda too expensive though, so 51 * we skip some cases. For example, if composed is desired, we simply 52 * don't touch 1-character clusters that are supported by the font, even 53 * though their NFC may be different. 54 * 55 * - When a font has a precomposed character for a sequence but the 'ccmp' 56 * feature in the font is not adequate, form use the precomposed character 57 * which typically has better mark positioning. 58 * 59 * - When a font does not support a character but supports its decomposition, 60 * well, use the decomposition. 61 * 62 * - The Indic shaper requests decomposed output. This will handle splitting 63 * matra for the Indic shaper. 64 */ 65 66 67static bool 68decompose (hb_ot_shape_context_t *c, 69 bool shortest, 70 hb_codepoint_t ab) 71{ 72 hb_codepoint_t a, b, glyph; 73 74 if (!hb_unicode_decompose (c->buffer->unicode, ab, &a, &b) || 75 (b && !hb_font_get_glyph (c->font, b, 0, &glyph))) 76 return FALSE; 77 78 bool has_a = hb_font_get_glyph (c->font, a, 0, &glyph); 79 if (shortest && has_a) { 80 /* Output a and b */ 81 c->buffer->output_glyph (a); 82 if (b) 83 c->buffer->output_glyph (b); 84 return TRUE; 85 } 86 87 if (decompose (c, shortest, a)) { 88 if (b) 89 c->buffer->output_glyph (b); 90 return TRUE; 91 } 92 93 if (has_a) { 94 c->buffer->output_glyph (a); 95 if (b) 96 c->buffer->output_glyph (b); 97 return TRUE; 98 } 99 100 return FALSE; 101} 102 103static bool 104decompose_current_glyph (hb_ot_shape_context_t *c, 105 bool shortest) 106{ 107 if (decompose (c, shortest, c->buffer->info[c->buffer->idx].codepoint)) { 108 c->buffer->skip_glyph (); 109 return TRUE; 110 } else { 111 c->buffer->next_glyph (); 112 return FALSE; 113 } 114} 115 116static bool 117decompose_single_char_cluster (hb_ot_shape_context_t *c, 118 bool will_recompose) 119{ 120 hb_codepoint_t glyph; 121 122 /* If recomposing and font supports this, we're good to go */ 123 if (will_recompose && hb_font_get_glyph (c->font, c->buffer->info[c->buffer->idx].codepoint, 0, &glyph)) { 124 c->buffer->next_glyph (); 125 return FALSE; 126 } 127 128 return decompose_current_glyph (c, will_recompose); 129} 130 131static bool 132decompose_multi_char_cluster (hb_ot_shape_context_t *c, 133 unsigned int end) 134{ 135 bool changed = FALSE; 136 137 /* TODO Currently if there's a variation-selector we give-up, it's just too hard. */ 138 for (unsigned int i = c->buffer->idx; i < end; i++) 139 if (unlikely (is_variation_selector (c->buffer->info[i].codepoint))) 140 return changed; 141 142 while (c->buffer->idx < end) 143 changed |= decompose_current_glyph (c, FALSE); 144 145 return changed; 146} 147 148void 149_hb_ot_shape_normalize (hb_ot_shape_context_t *c) 150{ 151 hb_buffer_t *buffer = c->buffer; 152 bool recompose = !hb_ot_shape_complex_prefer_decomposed (c->plan->shaper); 153 bool changed = FALSE; 154 bool has_multichar_clusters = FALSE; 155 unsigned int count; 156 157 buffer->clear_output (); 158 159 160 /* First round, decompose */ 161 162 count = buffer->len; 163 for (buffer->idx = 0; buffer->idx < count;) 164 { 165 unsigned int end; 166 for (end = buffer->idx + 1; end < count; end++) 167 if (buffer->info[buffer->idx].cluster != buffer->info[end].cluster) 168 break; 169 170 if (buffer->idx + 1 == end) 171 changed |= decompose_single_char_cluster (c, recompose); 172 else { 173 changed |= decompose_multi_char_cluster (c, end); 174 has_multichar_clusters = TRUE; 175 } 176 } 177 buffer->swap_buffers (); 178 179 180 /* Technically speaking, two characters with ccc=0 may combine. But all 181 * those cases are in languages that the indic module handles (which expects 182 * decomposed), or in Hangul jamo, which again, we want decomposed anyway. 183 * So we don't bother combining across cluster boundaries. */ 184 185 if (!has_multichar_clusters) 186 return; /* Done! */ 187 188 if (changed) 189 _hb_set_unicode_props (c->buffer); /* BUFFER: Set general_category and combining_class in var1 */ 190 191 192 /* Second round, reorder (inplace) */ 193 194 count = buffer->len; 195 for (unsigned int i = 0; i < count; i++) 196 { 197 if (buffer->info[i].combining_class() == 0) 198 continue; 199 200 unsigned int end; 201 for (end = i + 1; end < count; end++) 202 if (buffer->info[end].combining_class() == 0) 203 break; 204 205 /* We are going to do a bubble-sort. Only do this if the 206 * sequence is short. Doing it on long sequences can result 207 * in an O(n^2) DoS. */ 208 if (end - i > 10) { 209 i = end; 210 continue; 211 } 212 213 unsigned int k = end - i - 1; 214 do { 215 hb_glyph_info_t *pinfo = buffer->info + i; 216 unsigned int new_k = 0; 217 218 for (unsigned int j = 0; j < k; j++) 219 if (pinfo[j].combining_class() > pinfo[j+1].combining_class()) { 220 hb_glyph_info_t t; 221 t = pinfo[j]; 222 pinfo[j] = pinfo[j + 1]; 223 pinfo[j + 1] = t; 224 225 new_k = j; 226 } 227 k = new_k; 228 } while (k); 229 230 i = end; 231 } 232 233 234 /* Third round, recompose */ 235 236 if (recompose) { 237 238 239 } 240 241} 242 243HB_END_DECLS 244