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