• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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.hh"
28 #include "hb-ot-shape-complex.hh"
29 #include "hb-ot-shape.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   (void) 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 = 0, b = 0, a_glyph = 0, b_glyph = 0;
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 = 0;
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 HB_UNUSED)216 handle_variation_selector_cluster (const hb_ot_shape_normalize_context_t *c,
217 				   unsigned int end,
218 				   bool short_circuit HB_UNUSED)
219 {
220   /* TODO Currently if there's a variation-selector we give-up, it's just too hard. */
221   hb_buffer_t * const buffer = c->buffer;
222   hb_font_t * const font = c->font;
223   for (; buffer->idx < end - 1 && buffer->successful;) {
224     if (unlikely (buffer->unicode->is_variation_selector (buffer->cur(+1).codepoint))) {
225       if (font->get_variation_glyph (buffer->cur().codepoint, buffer->cur(+1).codepoint, &buffer->cur().glyph_index()))
226       {
227 	hb_codepoint_t unicode = buffer->cur().codepoint;
228 	buffer->replace_glyphs (2, 1, &unicode);
229       }
230       else
231       {
232         /* Just pass on the two characters separately, let GSUB do its magic. */
233 	set_glyph (buffer->cur(), font);
234 	buffer->next_glyph ();
235 	set_glyph (buffer->cur(), font);
236 	buffer->next_glyph ();
237       }
238       /* Skip any further variation selectors. */
239       while (buffer->idx < end && unlikely (buffer->unicode->is_variation_selector (buffer->cur().codepoint)))
240       {
241 	set_glyph (buffer->cur(), font);
242 	buffer->next_glyph ();
243       }
244     } else {
245       set_glyph (buffer->cur(), font);
246       buffer->next_glyph ();
247     }
248   }
249   if (likely (buffer->idx < end)) {
250     set_glyph (buffer->cur(), font);
251     buffer->next_glyph ();
252   }
253 }
254 
255 static inline void
decompose_multi_char_cluster(const hb_ot_shape_normalize_context_t * c,unsigned int end,bool short_circuit)256 decompose_multi_char_cluster (const hb_ot_shape_normalize_context_t *c, unsigned int end, bool short_circuit)
257 {
258   hb_buffer_t * const buffer = c->buffer;
259   for (unsigned int i = buffer->idx; i < end && buffer->successful; i++)
260     if (unlikely (buffer->unicode->is_variation_selector (buffer->info[i].codepoint))) {
261       handle_variation_selector_cluster (c, end, short_circuit);
262       return;
263     }
264 
265   while (buffer->idx < end && buffer->successful)
266     decompose_current_character (c, short_circuit);
267 }
268 
269 
270 static int
compare_combining_class(const hb_glyph_info_t * pa,const hb_glyph_info_t * pb)271 compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb)
272 {
273   unsigned int a = _hb_glyph_info_get_modified_combining_class (pa);
274   unsigned int b = _hb_glyph_info_get_modified_combining_class (pb);
275 
276   return a < b ? -1 : a == b ? 0 : +1;
277 }
278 
279 
280 void
_hb_ot_shape_normalize(const hb_ot_shape_plan_t * plan,hb_buffer_t * buffer,hb_font_t * font)281 _hb_ot_shape_normalize (const hb_ot_shape_plan_t *plan,
282 			hb_buffer_t *buffer,
283 			hb_font_t *font)
284 {
285   if (unlikely (!buffer->len)) return;
286 
287   _hb_buffer_assert_unicode_vars (buffer);
288 
289   hb_ot_shape_normalization_mode_t mode = plan->shaper->normalization_preference;
290   if (mode == HB_OT_SHAPE_NORMALIZATION_MODE_AUTO)
291   {
292     if (plan->has_gpos_mark)
293       // https://github.com/harfbuzz/harfbuzz/issues/653#issuecomment-423905920
294       //mode = HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED;
295       mode = HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS;
296     else
297       mode = HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS;
298   }
299 
300   const hb_ot_shape_normalize_context_t c = {
301     plan,
302     buffer,
303     font,
304     buffer->unicode,
305     plan->shaper->decompose ? plan->shaper->decompose : decompose_unicode,
306     plan->shaper->compose   ? plan->shaper->compose   : compose_unicode
307   };
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 (unlikely (HB_UNICODE_GENERAL_CATEGORY_IS_MARK (_hb_glyph_info_get_general_category (&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().glyph_index(),
346 						      sizeof (buffer->info[0]));
347 	buffer->next_glyphs (done);
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_UNICODE_GENERAL_CATEGORY_IS_MARK (_hb_glyph_info_get_general_category (&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->swap_buffers ();
367   }
368 
369 
370   /* Second round, reorder (inplace) */
371 
372   if (!all_simple)
373   {
374     count = buffer->len;
375     for (unsigned int i = 0; i < count; i++)
376     {
377       if (_hb_glyph_info_get_modified_combining_class (&buffer->info[i]) == 0)
378 	continue;
379 
380       unsigned int end;
381       for (end = i + 1; end < count; end++)
382 	if (_hb_glyph_info_get_modified_combining_class (&buffer->info[end]) == 0)
383 	  break;
384 
385       /* We are going to do a O(n^2).  Only do this if the sequence is short. */
386       if (end - i > HB_OT_SHAPE_COMPLEX_MAX_COMBINING_MARKS) {
387 	i = end;
388 	continue;
389       }
390 
391       buffer->sort (i, end, compare_combining_class);
392 
393       if (plan->shaper->reorder_marks)
394 	plan->shaper->reorder_marks (plan, buffer, i, end);
395 
396       i = end;
397     }
398   }
399   if (buffer->scratch_flags & HB_BUFFER_SCRATCH_FLAG_HAS_CGJ)
400   {
401     /* For all CGJ, check if it prevented any reordering at all.
402      * If it did NOT, then make it skippable.
403      * https://github.com/harfbuzz/harfbuzz/issues/554
404      */
405     for (unsigned int i = 1; i + 1 < buffer->len; i++)
406       if (buffer->info[i].codepoint == 0x034Fu/*CGJ*/ &&
407 	  info_cc(buffer->info[i-1]) <= info_cc(buffer->info[i+1]))
408       {
409 	_hb_glyph_info_unhide (&buffer->info[i]);
410       }
411   }
412 
413 
414   /* Third round, recompose */
415 
416   if (!all_simple &&
417       (mode == HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS ||
418        mode == HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS_NO_SHORT_CIRCUIT))
419   {
420     /* As noted in the comment earlier, we don't try to combine
421      * ccc=0 chars with their previous Starter. */
422 
423     buffer->clear_output ();
424     count = buffer->len;
425     unsigned int starter = 0;
426     buffer->next_glyph ();
427     while (buffer->idx < count && buffer->successful)
428     {
429       hb_codepoint_t composed, glyph;
430       if (/* We don't try to compose a non-mark character with it's preceding starter.
431 	   * This is both an optimization to avoid trying to compose every two neighboring
432 	   * glyphs in most scripts AND a desired feature for Hangul.  Apparently Hangul
433 	   * fonts are not designed to mix-and-match pre-composed syllables and Jamo. */
434 	  HB_UNICODE_GENERAL_CATEGORY_IS_MARK (_hb_glyph_info_get_general_category (&buffer->cur())))
435       {
436 	if (/* If there's anything between the starter and this char, they should have CCC
437 	     * smaller than this character's. */
438 	    (starter == buffer->out_len - 1 ||
439 	     info_cc (buffer->prev()) < info_cc (buffer->cur())) &&
440 	    /* And compose. */
441 	    c.compose (&c,
442 		       buffer->out_info[starter].codepoint,
443 		       buffer->cur().codepoint,
444 		       &composed) &&
445 	    /* And the font has glyph for the composite. */
446 	    font->get_nominal_glyph (composed, &glyph))
447 	{
448 	  /* Composes. */
449 	  buffer->next_glyph (); /* Copy to out-buffer. */
450 	  if (unlikely (!buffer->successful))
451 	    return;
452 	  buffer->merge_out_clusters (starter, buffer->out_len);
453 	  buffer->out_len--; /* Remove the second composable. */
454 	  /* Modify starter and carry on. */
455 	  buffer->out_info[starter].codepoint = composed;
456 	  buffer->out_info[starter].glyph_index() = glyph;
457 	  _hb_glyph_info_set_unicode_props (&buffer->out_info[starter], buffer);
458 
459 	  continue;
460 	}
461       }
462 
463       /* Blocked, or doesn't compose. */
464       buffer->next_glyph ();
465 
466       if (info_cc (buffer->prev()) == 0)
467 	starter = buffer->out_len - 1;
468     }
469     buffer->swap_buffers ();
470   }
471 }
472