hb-ot-shape-normalize.cc revision 8d1eef3f32fb539de2a72804fa3834acc18daab5 
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-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.
38 *
39 * Each shaper specifies whether it prefers decomposed (NFD) or composed (NFC).
40 * The logic however tries to use whatever the font can support.
41 *
42 * In general what happens is that: each grapheme is decomposed in a chain
43 * of 1:2 decompositions, marks reordered, and then recomposed if desired,
44 * so far it's like Unicode Normalization.  However, the decomposition and
45 * recomposition only happens if the font supports the resulting characters.
46 *
47 * The goals are:
48 *
49 *   - Try to render all canonically equivalent strings similarly.  To really
50 *     achieve this we have to always do the full decomposition and then
51 *     selectively recompose from there.  It's kinda too expensive though, so
52 *     we skip some cases.  For example, if composed is desired, we simply
53 *     don't touch 1-character clusters that are supported by the font, even
54 *     though their NFC may be different.
55 *
56 *   - When a font has a precomposed character for a sequence but the 'ccmp'
57 *     feature in the font is not adequate, use the precomposed character
58 *     which typically has better mark positioning.
59 *
60 *   - When a font does not support a combining mark, but supports it precomposed
61 *     with previous base, use that.  This needs the itemizer to have this
62 *     knowledge too.  We need to provide assistance to the itemizer.
63 *
64 *   - When a font does not support a character but supports its decomposition,
65 *     well, use the decomposition (preferring the canonical decomposition, but
66 *     falling back to the compatibility decomposition if necessary).  The
67 *     compatibility decomposition is really nice to have, for characters like
68 *     ellipsis, or various-sized space characters.
69 *
70 *   - The complex shapers can customize the compose and decompose functions to
71 *     offload some of their requirements to the normalizer.  For example, the
72 *     Indic shaper may want to disallow recomposing of two matras.
73 *
74 *   - We try compatibility decomposition if decomposing through canonical
75 *     decomposition alone failed to find a sequence that the font supports.
76 *     We don't try compatibility decomposition recursively during the canonical
77 *     decomposition phase.  This has minimal impact.  There are only a handful
78 *     of Greek letter that have canonical decompositions that include characters
79 *     with compatibility decomposition.  Those can be found using this command:
80 *
81 *     egrep  "`echo -n ';('; grep ';<' UnicodeData.txt | cut -d';' -f1 | tr '\n' '|'; echo ') '`" UnicodeData.txt
82 */
83
84static hb_bool_t
85decompose_func (hb_unicode_funcs_t *unicode,
86		hb_codepoint_t  ab,
87		hb_codepoint_t *a,
88		hb_codepoint_t *b)
89{
90  /* XXX FIXME, move these to complex shapers and propagage to normalizer.*/
91  switch (ab) {
92    case 0x0AC9  : return false;
93
94    case 0x0931  : return false;
95    case 0x0B94  : return false;
96
97    /* These ones have Unicode decompositions, but we do it
98     * this way to be close to what Uniscribe does. */
99    case 0x0DDA  : *a = 0x0DD9; *b= 0x0DDA; return true;
100    case 0x0DDC  : *a = 0x0DD9; *b= 0x0DDC; return true;
101    case 0x0DDD  : *a = 0x0DD9; *b= 0x0DDD; return true;
102    case 0x0DDE  : *a = 0x0DD9; *b= 0x0DDE; return true;
103
104    case 0x0F77  : *a = 0x0FB2; *b= 0x0F81; return true;
105    case 0x0F79  : *a = 0x0FB3; *b= 0x0F81; return true;
106    case 0x17BE  : *a = 0x17C1; *b= 0x17BE; return true;
107    case 0x17BF  : *a = 0x17C1; *b= 0x17BF; return true;
108    case 0x17C0  : *a = 0x17C1; *b= 0x17C0; return true;
109    case 0x17C4  : *a = 0x17C1; *b= 0x17C4; return true;
110    case 0x17C5  : *a = 0x17C1; *b= 0x17C5; return true;
111    case 0x1925  : *a = 0x1920; *b= 0x1923; return true;
112    case 0x1926  : *a = 0x1920; *b= 0x1924; return true;
113    case 0x1B3C  : *a = 0x1B42; *b= 0x1B3C; return true;
114    case 0x1112E  : *a = 0x11127; *b= 0x11131; return true;
115    case 0x1112F  : *a = 0x11127; *b= 0x11132; return true;
116#if 0
117    case 0x0B57  : *a = 0xno decomp, -> RIGHT; return true;
118    case 0x1C29  : *a = 0xno decomp, -> LEFT; return true;
119    case 0xA9C0  : *a = 0xno decomp, -> RIGHT; return true;
120    case 0x111BF  : *a = 0xno decomp, -> ABOVE; return true;
121#endif
122  }
123  return unicode->decompose (ab, a, b);
124}
125
126static hb_bool_t
127compose_func (hb_unicode_funcs_t *unicode,
128	      hb_codepoint_t  a,
129	      hb_codepoint_t  b,
130	      hb_codepoint_t *ab)
131{
132  /* XXX, this belongs to indic normalizer. */
133  if ((FLAG (unicode->general_category (a)) &
134       (FLAG (HB_UNICODE_GENERAL_CATEGORY_SPACING_MARK) |
135	FLAG (HB_UNICODE_GENERAL_CATEGORY_ENCLOSING_MARK) |
136	FLAG (HB_UNICODE_GENERAL_CATEGORY_NON_SPACING_MARK))))
137    return false;
138  /* XXX, add composition-exclusion exceptions to Indic shaper. */
139  if (a == 0x09AF && b == 0x09BC) { *ab = 0x09DF; return true; }
140
141  /* XXX, these belong to the hebew / default shaper. */
142  /* Hebrew presentation-form shaping.
143   * https://bugzilla.mozilla.org/show_bug.cgi?id=728866 */
144  // Hebrew presentation forms with dagesh, for characters 0x05D0..0x05EA;
145  // note that some letters do not have a dagesh presForm encoded
146  static const hb_codepoint_t sDageshForms[0x05EA - 0x05D0 + 1] = {
147    0xFB30, // ALEF
148    0xFB31, // BET
149    0xFB32, // GIMEL
150    0xFB33, // DALET
151    0xFB34, // HE
152    0xFB35, // VAV
153    0xFB36, // ZAYIN
154    0, // HET
155    0xFB38, // TET
156    0xFB39, // YOD
157    0xFB3A, // FINAL KAF
158    0xFB3B, // KAF
159    0xFB3C, // LAMED
160    0, // FINAL MEM
161    0xFB3E, // MEM
162    0, // FINAL NUN
163    0xFB40, // NUN
164    0xFB41, // SAMEKH
165    0, // AYIN
166    0xFB43, // FINAL PE
167    0xFB44, // PE
168    0, // FINAL TSADI
169    0xFB46, // TSADI
170    0xFB47, // QOF
171    0xFB48, // RESH
172    0xFB49, // SHIN
173    0xFB4A // TAV
174  };
175
176  hb_bool_t found = unicode->compose (a, b, ab);
177
178  if (!found && (b & ~0x7F) == 0x0580) {
179      // special-case Hebrew presentation forms that are excluded from
180      // standard normalization, but wanted for old fonts
181      switch (b) {
182      case 0x05B4: // HIRIQ
183	  if (a == 0x05D9) { // YOD
184	      *ab = 0xFB1D;
185	      found = true;
186	  }
187	  break;
188      case 0x05B7: // patah
189	  if (a == 0x05F2) { // YIDDISH YOD YOD
190	      *ab = 0xFB1F;
191	      found = true;
192	  } else if (a == 0x05D0) { // ALEF
193	      *ab = 0xFB2E;
194	      found = true;
195	  }
196	  break;
197      case 0x05B8: // QAMATS
198	  if (a == 0x05D0) { // ALEF
199	      *ab = 0xFB2F;
200	      found = true;
201	  }
202	  break;
203      case 0x05B9: // HOLAM
204	  if (a == 0x05D5) { // VAV
205	      *ab = 0xFB4B;
206	      found = true;
207	  }
208	  break;
209      case 0x05BC: // DAGESH
210	  if (a >= 0x05D0 && a <= 0x05EA) {
211	      *ab = sDageshForms[a - 0x05D0];
212	      found = (*ab != 0);
213	  } else if (a == 0xFB2A) { // SHIN WITH SHIN DOT
214	      *ab = 0xFB2C;
215	      found = true;
216	  } else if (a == 0xFB2B) { // SHIN WITH SIN DOT
217	      *ab = 0xFB2D;
218	      found = true;
219	  }
220	  break;
221      case 0x05BF: // RAFE
222	  switch (a) {
223	  case 0x05D1: // BET
224	      *ab = 0xFB4C;
225	      found = true;
226	      break;
227	  case 0x05DB: // KAF
228	      *ab = 0xFB4D;
229	      found = true;
230	      break;
231	  case 0x05E4: // PE
232	      *ab = 0xFB4E;
233	      found = true;
234	      break;
235	  }
236	  break;
237      case 0x05C1: // SHIN DOT
238	  if (a == 0x05E9) { // SHIN
239	      *ab = 0xFB2A;
240	      found = true;
241	  } else if (a == 0xFB49) { // SHIN WITH DAGESH
242	      *ab = 0xFB2C;
243	      found = true;
244	  }
245	  break;
246      case 0x05C2: // SIN DOT
247	  if (a == 0x05E9) { // SHIN
248	      *ab = 0xFB2B;
249	      found = true;
250	  } else if (a == 0xFB49) { // SHIN WITH DAGESH
251	      *ab = 0xFB2D;
252	      found = true;
253	  }
254	  break;
255      }
256  }
257
258  return found;
259}
260
261static inline void
262output_char (hb_buffer_t *buffer, hb_codepoint_t unichar)
263{
264  buffer->output_glyph (unichar);
265  _hb_glyph_info_set_unicode_props (&buffer->prev(), buffer->unicode);
266}
267
268static inline void
269next_char (hb_buffer_t *buffer)
270{
271  buffer->next_glyph ();
272}
273
274static inline void
275skip_char (hb_buffer_t *buffer)
276{
277  buffer->skip_glyph ();
278}
279
280static bool
281decompose (hb_font_t *font, hb_buffer_t *buffer,
282	   bool shortest,
283	   hb_codepoint_t ab)
284{
285  hb_codepoint_t a, b, glyph;
286
287  if (!decompose_func (buffer->unicode, ab, &a, &b) ||
288      (b && !font->get_glyph (b, 0, &glyph)))
289    return false;
290
291  bool has_a = font->get_glyph (a, 0, &glyph);
292  if (shortest && has_a) {
293    /* Output a and b */
294    output_char (buffer, a);
295    if (b)
296      output_char (buffer, b);
297    return true;
298  }
299
300  if (decompose (font, buffer, shortest, a)) {
301    if (b)
302      output_char (buffer, b);
303    return true;
304  }
305
306  if (has_a) {
307    output_char (buffer, a);
308    if (b)
309      output_char (buffer, b);
310    return true;
311  }
312
313  return false;
314}
315
316static bool
317decompose_compatibility (hb_font_t *font, hb_buffer_t *buffer,
318			 hb_codepoint_t u)
319{
320  unsigned int len, i;
321  hb_codepoint_t decomposed[HB_UNICODE_MAX_DECOMPOSITION_LEN];
322
323  len = buffer->unicode->decompose_compatibility (u, decomposed);
324  if (!len)
325    return false;
326
327  hb_codepoint_t glyph;
328  for (i = 0; i < len; i++)
329    if (!font->get_glyph (decomposed[i], 0, &glyph))
330      return false;
331
332  for (i = 0; i < len; i++)
333    output_char (buffer, decomposed[i]);
334
335  return true;
336}
337
338static void
339decompose_current_character (hb_font_t *font, hb_buffer_t *buffer,
340			     bool shortest)
341{
342  hb_codepoint_t glyph;
343
344  /* Kind of a cute waterfall here... */
345  if (shortest && font->get_glyph (buffer->cur().codepoint, 0, &glyph))
346    next_char (buffer);
347  else if (decompose (font, buffer, shortest, buffer->cur().codepoint))
348    skip_char (buffer);
349  else if (!shortest && font->get_glyph (buffer->cur().codepoint, 0, &glyph))
350    next_char (buffer);
351  else if (decompose_compatibility (font, buffer, buffer->cur().codepoint))
352    skip_char (buffer);
353  else
354    next_char (buffer);
355}
356
357static void
358decompose_multi_char_cluster (hb_font_t *font, hb_buffer_t *buffer,
359			      unsigned int end)
360{
361  /* TODO Currently if there's a variation-selector we give-up, it's just too hard. */
362  for (unsigned int i = buffer->idx; i < end; i++)
363    if (unlikely (buffer->unicode->is_variation_selector (buffer->info[i].codepoint))) {
364      while (buffer->idx < end)
365	next_char (buffer);
366      return;
367    }
368
369  while (buffer->idx < end)
370    decompose_current_character (font, buffer, false);
371}
372
373static int
374compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb)
375{
376  unsigned int a = _hb_glyph_info_get_modified_combining_class (pa);
377  unsigned int b = _hb_glyph_info_get_modified_combining_class (pb);
378
379  return a < b ? -1 : a == b ? 0 : +1;
380}
381
382void
383_hb_ot_shape_normalize (hb_font_t *font, hb_buffer_t *buffer,
384			hb_ot_shape_normalization_mode_t mode)
385{
386  bool recompose = mode != HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED;
387  bool has_multichar_clusters = false;
388  unsigned int count;
389
390  /* We do a fairly straightforward yet custom normalization process in three
391   * separate rounds: decompose, reorder, recompose (if desired).  Currently
392   * this makes two buffer swaps.  We can make it faster by moving the last
393   * two rounds into the inner loop for the first round, but it's more readable
394   * this way. */
395
396
397  /* First round, decompose */
398
399  buffer->clear_output ();
400  count = buffer->len;
401  for (buffer->idx = 0; buffer->idx < count;)
402  {
403    unsigned int end;
404    for (end = buffer->idx + 1; end < count; end++)
405      if (buffer->cur().cluster != buffer->info[end].cluster)
406        break;
407
408    if (buffer->idx + 1 == end)
409      decompose_current_character (font, buffer, recompose);
410    else {
411      decompose_multi_char_cluster (font, buffer, end);
412      has_multichar_clusters = true;
413    }
414  }
415  buffer->swap_buffers ();
416
417
418  if (mode != HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_FULL && !has_multichar_clusters)
419    return; /* Done! */
420
421
422  /* Second round, reorder (inplace) */
423
424  count = buffer->len;
425  for (unsigned int i = 0; i < count; i++)
426  {
427    if (_hb_glyph_info_get_modified_combining_class (&buffer->info[i]) == 0)
428      continue;
429
430    unsigned int end;
431    for (end = i + 1; end < count; end++)
432      if (_hb_glyph_info_get_modified_combining_class (&buffer->info[end]) == 0)
433        break;
434
435    /* We are going to do a bubble-sort.  Only do this if the
436     * sequence is short.  Doing it on long sequences can result
437     * in an O(n^2) DoS. */
438    if (end - i > 10) {
439      i = end;
440      continue;
441    }
442
443    hb_bubble_sort (buffer->info + i, end - i, compare_combining_class);
444
445    i = end;
446  }
447
448
449  if (!recompose)
450    return;
451
452  /* Third round, recompose */
453
454  /* As noted in the comment earlier, we don't try to combine
455   * ccc=0 chars with their previous Starter. */
456
457  buffer->clear_output ();
458  count = buffer->len;
459  unsigned int starter = 0;
460  next_char (buffer);
461  while (buffer->idx < count)
462  {
463    hb_codepoint_t composed, glyph;
464    if (/* If mode is NOT COMPOSED_FULL (ie. it's COMPOSED_DIACRITICS), we don't try to
465	 * compose a CCC=0 character with it's preceding starter. */
466	(mode == HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_FULL ||
467	 _hb_glyph_info_get_modified_combining_class (&buffer->cur()) != 0) &&
468	/* If there's anything between the starter and this char, they should have CCC
469	 * smaller than this character's. */
470	(starter == buffer->out_len - 1 ||
471	 _hb_glyph_info_get_modified_combining_class (&buffer->prev()) < _hb_glyph_info_get_modified_combining_class (&buffer->cur())) &&
472	/* And compose. */
473	compose_func (buffer->unicode,
474		      buffer->out_info[starter].codepoint,
475		      buffer->cur().codepoint,
476		      &composed) &&
477	/* And the font has glyph for the composite. */
478	font->get_glyph (composed, 0, &glyph))
479    {
480      /* Composes. */
481      next_char (buffer); /* Copy to out-buffer. */
482      if (unlikely (buffer->in_error))
483        return;
484      buffer->merge_out_clusters (starter, buffer->out_len);
485      buffer->out_len--; /* Remove the second composable. */
486      buffer->out_info[starter].codepoint = composed; /* Modify starter and carry on. */
487      _hb_glyph_info_set_unicode_props (&buffer->out_info[starter], buffer->unicode);
488
489      continue;
490    }
491
492    /* Blocked, or doesn't compose. */
493    next_char (buffer);
494
495    if (_hb_glyph_info_get_modified_combining_class (&buffer->prev()) == 0)
496      starter = buffer->out_len - 1;
497  }
498  buffer->swap_buffers ();
499
500}
501