OLD | NEW |
(Empty) | |
| 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 |
| 30 |
| 31 /* |
| 32 * HIGHLEVEL DESIGN: |
| 33 * |
| 34 * This file exports one main function: _hb_ot_shape_normalize(). |
| 35 * |
| 36 * This function closely reflects the Unicode Normalization Algorithm, |
| 37 * yet it's different. The shaper an either prefer decomposed (NFD) or |
| 38 * composed (NFC). |
| 39 * |
| 40 * In general what happens is that: each grapheme is decomposed in a chain |
| 41 * of 1:2 decompositions, marks reordered, and then recomposed if desired, |
| 42 * so far it's like Unicode Normalization. However, the decomposition and |
| 43 * recomposition only happens if the font supports the resulting characters. |
| 44 * |
| 45 * The goals are: |
| 46 * |
| 47 * - Try to render all canonically equivalent strings similarly. To really |
| 48 * achieve this we have to always do the full decomposition and then |
| 49 * selectively recompose from there. It's kinda too expensive though, so |
| 50 * we skip some cases. For example, if composed is desired, we simply |
| 51 * don't touch 1-character clusters that are supported by the font, even |
| 52 * though their NFC may be different. |
| 53 * |
| 54 * - When a font has a precomposed character for a sequence but the 'ccmp' |
| 55 * feature in the font is not adequate, use the precomposed character |
| 56 * which typically has better mark positioning. |
| 57 * |
| 58 * - When a font does not support a combining mark, but supports it precompose
d |
| 59 * with previous base. This needs the itemizer to have this knowledge too. |
| 60 * We need ot provide assistance to the itemizer. |
| 61 * |
| 62 * - When a font does not support a character but supports its decomposition, |
| 63 * well, use the decomposition. |
| 64 * |
| 65 * - The Indic shaper requests decomposed output. This will handle splitting |
| 66 * matra for the Indic shaper. |
| 67 */ |
| 68 |
| 69 static void |
| 70 output_glyph (hb_ot_shape_context_t *c, |
| 71 hb_codepoint_t glyph) |
| 72 { |
| 73 hb_buffer_t *buffer = c->buffer; |
| 74 |
| 75 buffer->output_glyph (glyph); |
| 76 hb_glyph_info_set_unicode_props (&buffer->out_info[buffer->out_len - 1], buffe
r->unicode); |
| 77 } |
| 78 |
| 79 static bool |
| 80 decompose (hb_ot_shape_context_t *c, |
| 81 bool shortest, |
| 82 hb_codepoint_t ab) |
| 83 { |
| 84 hb_codepoint_t a, b, glyph; |
| 85 |
| 86 if (!hb_unicode_decompose (c->buffer->unicode, ab, &a, &b) || |
| 87 (b && !hb_font_get_glyph (c->font, b, 0, &glyph))) |
| 88 return FALSE; |
| 89 |
| 90 bool has_a = hb_font_get_glyph (c->font, a, 0, &glyph); |
| 91 if (shortest && has_a) { |
| 92 /* Output a and b */ |
| 93 output_glyph (c, a); |
| 94 if (b) |
| 95 output_glyph (c, b); |
| 96 return TRUE; |
| 97 } |
| 98 |
| 99 if (decompose (c, shortest, a)) { |
| 100 if (b) |
| 101 output_glyph (c, b); |
| 102 return TRUE; |
| 103 } |
| 104 |
| 105 if (has_a) { |
| 106 output_glyph (c, a); |
| 107 if (b) |
| 108 output_glyph (c, b); |
| 109 return TRUE; |
| 110 } |
| 111 |
| 112 return FALSE; |
| 113 } |
| 114 |
| 115 static void |
| 116 decompose_current_glyph (hb_ot_shape_context_t *c, |
| 117 bool shortest) |
| 118 { |
| 119 if (decompose (c, shortest, c->buffer->info[c->buffer->idx].codepoint)) |
| 120 c->buffer->skip_glyph (); |
| 121 else |
| 122 c->buffer->next_glyph (); |
| 123 } |
| 124 |
| 125 static void |
| 126 decompose_single_char_cluster (hb_ot_shape_context_t *c, |
| 127 bool will_recompose) |
| 128 { |
| 129 hb_codepoint_t glyph; |
| 130 |
| 131 /* If recomposing and font supports this, we're good to go */ |
| 132 if (will_recompose && hb_font_get_glyph (c->font, c->buffer->info[c->buffer->i
dx].codepoint, 0, &glyph)) { |
| 133 c->buffer->next_glyph (); |
| 134 return; |
| 135 } |
| 136 |
| 137 decompose_current_glyph (c, will_recompose); |
| 138 } |
| 139 |
| 140 static void |
| 141 decompose_multi_char_cluster (hb_ot_shape_context_t *c, |
| 142 unsigned int end) |
| 143 { |
| 144 /* TODO Currently if there's a variation-selector we give-up, it's just too ha
rd. */ |
| 145 for (unsigned int i = c->buffer->idx; i < end; i++) |
| 146 if (unlikely (is_variation_selector (c->buffer->info[i].codepoint))) { |
| 147 while (c->buffer->idx < end) |
| 148 c->buffer->next_glyph (); |
| 149 return; |
| 150 } |
| 151 |
| 152 while (c->buffer->idx < end) |
| 153 decompose_current_glyph (c, FALSE); |
| 154 } |
| 155 |
| 156 static int |
| 157 compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb) |
| 158 { |
| 159 unsigned int a = pa->combining_class(); |
| 160 unsigned int b = pb->combining_class(); |
| 161 |
| 162 return a < b ? -1 : a == b ? 0 : +1; |
| 163 } |
| 164 |
| 165 void |
| 166 _hb_ot_shape_normalize (hb_ot_shape_context_t *c) |
| 167 { |
| 168 hb_buffer_t *buffer = c->buffer; |
| 169 bool recompose = !hb_ot_shape_complex_prefer_decomposed (c->plan->shaper); |
| 170 bool has_multichar_clusters = FALSE; |
| 171 unsigned int count; |
| 172 |
| 173 /* We do a fairly straightforward yet custom normalization process in three |
| 174 * separate rounds: decompose, reorder, recompose (if desired). Currently |
| 175 * this makes two buffer swaps. We can make it faster by moving the last |
| 176 * two rounds into the inner loop for the first round, but it's more readable |
| 177 * this way. */ |
| 178 |
| 179 |
| 180 /* First round, decompose */ |
| 181 |
| 182 buffer->clear_output (); |
| 183 count = buffer->len; |
| 184 for (buffer->idx = 0; buffer->idx < count;) |
| 185 { |
| 186 unsigned int end; |
| 187 for (end = buffer->idx + 1; end < count; end++) |
| 188 if (buffer->info[buffer->idx].cluster != buffer->info[end].cluster) |
| 189 break; |
| 190 |
| 191 if (buffer->idx + 1 == end) |
| 192 decompose_single_char_cluster (c, recompose); |
| 193 else { |
| 194 decompose_multi_char_cluster (c, end); |
| 195 has_multichar_clusters = TRUE; |
| 196 } |
| 197 } |
| 198 buffer->swap_buffers (); |
| 199 |
| 200 |
| 201 /* Technically speaking, two characters with ccc=0 may combine. But all |
| 202 * those cases are in languages that the indic module handles (which expects |
| 203 * decomposed), or in Hangul jamo, which again, we want decomposed anyway. |
| 204 * So we don't bother combining across cluster boundaries. This is a huge |
| 205 * performance saver if the compose() callback is slow. |
| 206 * |
| 207 * TODO: Am I right about Hangul? If I am, we should add a Hangul module |
| 208 * that requests decomposed. If for Hangul we end up wanting composed, we |
| 209 * can do that in the Hangul module. |
| 210 */ |
| 211 |
| 212 if (!has_multichar_clusters) |
| 213 return; /* Done! */ |
| 214 |
| 215 |
| 216 /* Second round, reorder (inplace) */ |
| 217 |
| 218 count = buffer->len; |
| 219 for (unsigned int i = 0; i < count; i++) |
| 220 { |
| 221 if (buffer->info[i].combining_class() == 0) |
| 222 continue; |
| 223 |
| 224 unsigned int end; |
| 225 for (end = i + 1; end < count; end++) |
| 226 if (buffer->info[end].combining_class() == 0) |
| 227 break; |
| 228 |
| 229 /* We are going to do a bubble-sort. Only do this if the |
| 230 * sequence is short. Doing it on long sequences can result |
| 231 * in an O(n^2) DoS. */ |
| 232 if (end - i > 10) { |
| 233 i = end; |
| 234 continue; |
| 235 } |
| 236 |
| 237 hb_bubble_sort (buffer->info + i, end - i, compare_combining_class); |
| 238 |
| 239 i = end; |
| 240 } |
| 241 |
| 242 |
| 243 if (!recompose) |
| 244 return; |
| 245 |
| 246 /* Third round, recompose */ |
| 247 |
| 248 /* As noted in the comment earlier, we don't try to combine |
| 249 * ccc=0 chars with their previous Starter. */ |
| 250 |
| 251 buffer->clear_output (); |
| 252 count = buffer->len; |
| 253 unsigned int starter = 0; |
| 254 buffer->next_glyph (); |
| 255 while (buffer->idx < count) |
| 256 { |
| 257 if (buffer->info[buffer->idx].combining_class() == 0) { |
| 258 starter = buffer->out_len; |
| 259 buffer->next_glyph (); |
| 260 continue; |
| 261 } |
| 262 |
| 263 hb_codepoint_t composed, glyph; |
| 264 if ((buffer->out_info[buffer->out_len - 1].combining_class() >= |
| 265 buffer->info[buffer->idx].combining_class()) || |
| 266 !hb_unicode_compose (c->buffer->unicode, |
| 267 buffer->out_info[starter].codepoint, |
| 268 buffer->info[buffer->idx].codepoint, |
| 269 &composed) || |
| 270 !hb_font_get_glyph (c->font, composed, 0, &glyph)) |
| 271 { |
| 272 /* Blocked, or doesn't compose. */ |
| 273 buffer->next_glyph (); |
| 274 continue; |
| 275 } |
| 276 |
| 277 /* Composes. Modify starter and carry on. */ |
| 278 buffer->out_info[starter].codepoint = composed; |
| 279 hb_glyph_info_set_unicode_props (&buffer->out_info[starter], buffer->unicode
); |
| 280 |
| 281 buffer->skip_glyph (); |
| 282 } |
| 283 buffer->swap_buffers (); |
| 284 |
| 285 } |
| 286 |
OLD | NEW |