michael@0: /*
michael@0:  * Copyright © 2011,2012  Google, Inc.
michael@0:  *
michael@0:  *  This is part of HarfBuzz, a text shaping library.
michael@0:  *
michael@0:  * Permission is hereby granted, without written agreement and without
michael@0:  * license or royalty fees, to use, copy, modify, and distribute this
michael@0:  * software and its documentation for any purpose, provided that the
michael@0:  * above copyright notice and the following two paragraphs appear in
michael@0:  * all copies of this software.
michael@0:  *
michael@0:  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
michael@0:  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
michael@0:  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
michael@0:  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
michael@0:  * DAMAGE.
michael@0:  *
michael@0:  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
michael@0:  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
michael@0:  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
michael@0:  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
michael@0:  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
michael@0:  *
michael@0:  * Google Author(s): Behdad Esfahbod
michael@0:  */
michael@0: 
michael@0: #include "hb-ot-shape-normalize-private.hh"
michael@0: #include "hb-ot-shape-complex-private.hh"
michael@0: #include "hb-ot-shape-private.hh"
michael@0: 
michael@0: 
michael@0: /*
michael@0:  * HIGHLEVEL DESIGN:
michael@0:  *
michael@0:  * This file exports one main function: _hb_ot_shape_normalize().
michael@0:  *
michael@0:  * This function closely reflects the Unicode Normalization Algorithm,
michael@0:  * yet it's different.
michael@0:  *
michael@0:  * Each shaper specifies whether it prefers decomposed (NFD) or composed (NFC).
michael@0:  * The logic however tries to use whatever the font can support.
michael@0:  *
michael@0:  * In general what happens is that: each grapheme is decomposed in a chain
michael@0:  * of 1:2 decompositions, marks reordered, and then recomposed if desired,
michael@0:  * so far it's like Unicode Normalization.  However, the decomposition and
michael@0:  * recomposition only happens if the font supports the resulting characters.
michael@0:  *
michael@0:  * The goals are:
michael@0:  *
michael@0:  *   - Try to render all canonically equivalent strings similarly.  To really
michael@0:  *     achieve this we have to always do the full decomposition and then
michael@0:  *     selectively recompose from there.  It's kinda too expensive though, so
michael@0:  *     we skip some cases.  For example, if composed is desired, we simply
michael@0:  *     don't touch 1-character clusters that are supported by the font, even
michael@0:  *     though their NFC may be different.
michael@0:  *
michael@0:  *   - When a font has a precomposed character for a sequence but the 'ccmp'
michael@0:  *     feature in the font is not adequate, use the precomposed character
michael@0:  *     which typically has better mark positioning.
michael@0:  *
michael@0:  *   - When a font does not support a combining mark, but supports it precomposed
michael@0:  *     with previous base, use that.  This needs the itemizer to have this
michael@0:  *     knowledge too.  We need to provide assistance to the itemizer.
michael@0:  *
michael@0:  *   - When a font does not support a character but supports its decomposition,
michael@0:  *     well, use the decomposition (preferring the canonical decomposition, but
michael@0:  *     falling back to the compatibility decomposition if necessary).  The
michael@0:  *     compatibility decomposition is really nice to have, for characters like
michael@0:  *     ellipsis, or various-sized space characters.
michael@0:  *
michael@0:  *   - The complex shapers can customize the compose and decompose functions to
michael@0:  *     offload some of their requirements to the normalizer.  For example, the
michael@0:  *     Indic shaper may want to disallow recomposing of two matras.
michael@0:  *
michael@0:  *   - We try compatibility decomposition if decomposing through canonical
michael@0:  *     decomposition alone failed to find a sequence that the font supports.
michael@0:  *     We don't try compatibility decomposition recursively during the canonical
michael@0:  *     decomposition phase.  This has minimal impact.  There are only a handful
michael@0:  *     of Greek letter that have canonical decompositions that include characters
michael@0:  *     with compatibility decomposition.  Those can be found using this command:
michael@0:  *
michael@0:  *     egrep  "`echo -n ';('; grep ';<' UnicodeData.txt | cut -d';' -f1 | tr '\n' '|'; echo ') '`" UnicodeData.txt
michael@0:  */
michael@0: 
michael@0: static bool
michael@0: decompose_unicode (const hb_ot_shape_normalize_context_t *c,
michael@0: 		   hb_codepoint_t  ab,
michael@0: 		   hb_codepoint_t *a,
michael@0: 		   hb_codepoint_t *b)
michael@0: {
michael@0:   return c->unicode->decompose (ab, a, b);
michael@0: }
michael@0: 
michael@0: static bool
michael@0: compose_unicode (const hb_ot_shape_normalize_context_t *c,
michael@0: 		 hb_codepoint_t  a,
michael@0: 		 hb_codepoint_t  b,
michael@0: 		 hb_codepoint_t *ab)
michael@0: {
michael@0:   return c->unicode->compose (a, b, ab);
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: set_glyph (hb_glyph_info_t &info, hb_font_t *font)
michael@0: {
michael@0:   font->get_glyph (info.codepoint, 0, &info.glyph_index());
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: output_char (hb_buffer_t *buffer, hb_codepoint_t unichar, hb_codepoint_t glyph)
michael@0: {
michael@0:   buffer->cur().glyph_index() = glyph;
michael@0:   buffer->output_glyph (unichar);
michael@0:   _hb_glyph_info_set_unicode_props (&buffer->prev(), buffer->unicode);
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: next_char (hb_buffer_t *buffer, hb_codepoint_t glyph)
michael@0: {
michael@0:   buffer->cur().glyph_index() = glyph;
michael@0:   buffer->next_glyph ();
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: skip_char (hb_buffer_t *buffer)
michael@0: {
michael@0:   buffer->skip_glyph ();
michael@0: }
michael@0: 
michael@0: /* Returns 0 if didn't decompose, number of resulting characters otherwise. */
michael@0: static inline unsigned int
michael@0: decompose (const hb_ot_shape_normalize_context_t *c, bool shortest, hb_codepoint_t ab)
michael@0: {
michael@0:   hb_codepoint_t a, b, a_glyph, b_glyph;
michael@0:   hb_buffer_t * const buffer = c->buffer;
michael@0:   hb_font_t * const font = c->font;
michael@0: 
michael@0:   if (!c->decompose (c, ab, &a, &b) ||
michael@0:       (b && !font->get_glyph (b, 0, &b_glyph)))
michael@0:     return 0;
michael@0: 
michael@0:   bool has_a = font->get_glyph (a, 0, &a_glyph);
michael@0:   if (shortest && has_a) {
michael@0:     /* Output a and b */
michael@0:     output_char (buffer, a, a_glyph);
michael@0:     if (likely (b)) {
michael@0:       output_char (buffer, b, b_glyph);
michael@0:       return 2;
michael@0:     }
michael@0:     return 1;
michael@0:   }
michael@0: 
michael@0:   unsigned int ret;
michael@0:   if ((ret = decompose (c, shortest, a))) {
michael@0:     if (b) {
michael@0:       output_char (buffer, b, b_glyph);
michael@0:       return ret + 1;
michael@0:     }
michael@0:     return ret;
michael@0:   }
michael@0: 
michael@0:   if (has_a) {
michael@0:     output_char (buffer, a, a_glyph);
michael@0:     if (likely (b)) {
michael@0:       output_char (buffer, b, b_glyph);
michael@0:       return 2;
michael@0:     }
michael@0:     return 1;
michael@0:   }
michael@0: 
michael@0:   return 0;
michael@0: }
michael@0: 
michael@0: /* Returns 0 if didn't decompose, number of resulting characters otherwise. */
michael@0: static inline unsigned int
michael@0: decompose_compatibility (const hb_ot_shape_normalize_context_t *c, hb_codepoint_t u)
michael@0: {
michael@0:   unsigned int len, i;
michael@0:   hb_codepoint_t decomposed[HB_UNICODE_MAX_DECOMPOSITION_LEN];
michael@0:   hb_codepoint_t glyphs[HB_UNICODE_MAX_DECOMPOSITION_LEN];
michael@0: 
michael@0:   len = c->buffer->unicode->decompose_compatibility (u, decomposed);
michael@0:   if (!len)
michael@0:     return 0;
michael@0: 
michael@0:   for (i = 0; i < len; i++)
michael@0:     if (!c->font->get_glyph (decomposed[i], 0, &glyphs[i]))
michael@0:       return 0;
michael@0: 
michael@0:   for (i = 0; i < len; i++)
michael@0:     output_char (c->buffer, decomposed[i], glyphs[i]);
michael@0: 
michael@0:   return len;
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: decompose_current_character (const hb_ot_shape_normalize_context_t *c, bool shortest)
michael@0: {
michael@0:   hb_buffer_t * const buffer = c->buffer;
michael@0:   hb_codepoint_t glyph;
michael@0: 
michael@0:   /* Kind of a cute waterfall here... */
michael@0:   if (shortest && c->font->get_glyph (buffer->cur().codepoint, 0, &glyph))
michael@0:     next_char (buffer, glyph);
michael@0:   else if (decompose (c, shortest, buffer->cur().codepoint))
michael@0:     skip_char (buffer);
michael@0:   else if (!shortest && c->font->get_glyph (buffer->cur().codepoint, 0, &glyph))
michael@0:     next_char (buffer, glyph);
michael@0:   else if (decompose_compatibility (c, buffer->cur().codepoint))
michael@0:     skip_char (buffer);
michael@0:   else
michael@0:     next_char (buffer, glyph); /* glyph is initialized in earlier branches. */
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: handle_variation_selector_cluster (const hb_ot_shape_normalize_context_t *c, unsigned int end, bool short_circuit)
michael@0: {
michael@0:   /* TODO Currently if there's a variation-selector we give-up, it's just too hard. */
michael@0:   hb_buffer_t * const buffer = c->buffer;
michael@0:   hb_font_t * const font = c->font;
michael@0:   for (; buffer->idx < end - 1;) {
michael@0:     if (unlikely (buffer->unicode->is_variation_selector (buffer->cur(+1).codepoint))) {
michael@0:       /* The next two lines are some ugly lines... But work. */
michael@0:       if (font->get_glyph (buffer->cur().codepoint, buffer->cur(+1).codepoint, &buffer->cur().glyph_index()))
michael@0:       {
michael@0: 	buffer->replace_glyphs (2, 1, &buffer->cur().codepoint);
michael@0:       }
michael@0:       else
michael@0:       {
michael@0:         /* Just pass on the two characters separately, let GSUB do its magic. */
michael@0: 	set_glyph (buffer->cur(), font);
michael@0: 	buffer->next_glyph ();
michael@0: 	set_glyph (buffer->cur(), font);
michael@0: 	buffer->next_glyph ();
michael@0:       }
michael@0:       /* Skip any further variation selectors. */
michael@0:       while (buffer->idx < end && unlikely (buffer->unicode->is_variation_selector (buffer->cur().codepoint)))
michael@0:       {
michael@0: 	set_glyph (buffer->cur(), font);
michael@0: 	buffer->next_glyph ();
michael@0:       }
michael@0:     } else {
michael@0:       set_glyph (buffer->cur(), font);
michael@0:       buffer->next_glyph ();
michael@0:     }
michael@0:   }
michael@0:   if (likely (buffer->idx < end)) {
michael@0:     set_glyph (buffer->cur(), font);
michael@0:     buffer->next_glyph ();
michael@0:   }
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: decompose_multi_char_cluster (const hb_ot_shape_normalize_context_t *c, unsigned int end, bool short_circuit)
michael@0: {
michael@0:   hb_buffer_t * const buffer = c->buffer;
michael@0:   for (unsigned int i = buffer->idx; i < end; i++)
michael@0:     if (unlikely (buffer->unicode->is_variation_selector (buffer->info[i].codepoint))) {
michael@0:       handle_variation_selector_cluster (c, end, short_circuit);
michael@0:       return;
michael@0:     }
michael@0: 
michael@0:   while (buffer->idx < end)
michael@0:     decompose_current_character (c, short_circuit);
michael@0: }
michael@0: 
michael@0: static inline void
michael@0: decompose_cluster (const hb_ot_shape_normalize_context_t *c, unsigned int end, bool might_short_circuit, bool always_short_circuit)
michael@0: {
michael@0:   if (likely (c->buffer->idx + 1 == end))
michael@0:     decompose_current_character (c, might_short_circuit);
michael@0:   else
michael@0:     decompose_multi_char_cluster (c, end, always_short_circuit);
michael@0: }
michael@0: 
michael@0: 
michael@0: static int
michael@0: compare_combining_class (const hb_glyph_info_t *pa, const hb_glyph_info_t *pb)
michael@0: {
michael@0:   unsigned int a = _hb_glyph_info_get_modified_combining_class (pa);
michael@0:   unsigned int b = _hb_glyph_info_get_modified_combining_class (pb);
michael@0: 
michael@0:   return a < b ? -1 : a == b ? 0 : +1;
michael@0: }
michael@0: 
michael@0: 
michael@0: void
michael@0: _hb_ot_shape_normalize (const hb_ot_shape_plan_t *plan,
michael@0: 			hb_buffer_t *buffer,
michael@0: 			hb_font_t *font)
michael@0: {
michael@0:   hb_ot_shape_normalization_mode_t mode = plan->shaper->normalization_preference;
michael@0:   const hb_ot_shape_normalize_context_t c = {
michael@0:     plan,
michael@0:     buffer,
michael@0:     font,
michael@0:     buffer->unicode,
michael@0:     plan->shaper->decompose ? plan->shaper->decompose : decompose_unicode,
michael@0:     plan->shaper->compose   ? plan->shaper->compose   : compose_unicode
michael@0:   };
michael@0: 
michael@0:   bool always_short_circuit = mode == HB_OT_SHAPE_NORMALIZATION_MODE_NONE;
michael@0:   bool might_short_circuit = always_short_circuit ||
michael@0: 			     (mode != HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED &&
michael@0: 			      mode != HB_OT_SHAPE_NORMALIZATION_MODE_COMPOSED_DIACRITICS_NO_SHORT_CIRCUIT);
michael@0:   unsigned int count;
michael@0: 
michael@0:   /* We do a fairly straightforward yet custom normalization process in three
michael@0:    * separate rounds: decompose, reorder, recompose (if desired).  Currently
michael@0:    * this makes two buffer swaps.  We can make it faster by moving the last
michael@0:    * two rounds into the inner loop for the first round, but it's more readable
michael@0:    * this way. */
michael@0: 
michael@0: 
michael@0:   /* First round, decompose */
michael@0: 
michael@0:   buffer->clear_output ();
michael@0:   count = buffer->len;
michael@0:   for (buffer->idx = 0; buffer->idx < count;)
michael@0:   {
michael@0:     unsigned int end;
michael@0:     for (end = buffer->idx + 1; end < count; end++)
michael@0:       if (buffer->cur().cluster != buffer->info[end].cluster)
michael@0:         break;
michael@0: 
michael@0:     decompose_cluster (&c, end, might_short_circuit, always_short_circuit);
michael@0:   }
michael@0:   buffer->swap_buffers ();
michael@0: 
michael@0: 
michael@0:   /* Second round, reorder (inplace) */
michael@0: 
michael@0:   count = buffer->len;
michael@0:   for (unsigned int i = 0; i < count; i++)
michael@0:   {
michael@0:     if (_hb_glyph_info_get_modified_combining_class (&buffer->info[i]) == 0)
michael@0:       continue;
michael@0: 
michael@0:     unsigned int end;
michael@0:     for (end = i + 1; end < count; end++)
michael@0:       if (_hb_glyph_info_get_modified_combining_class (&buffer->info[end]) == 0)
michael@0:         break;
michael@0: 
michael@0:     /* We are going to do a bubble-sort.  Only do this if the
michael@0:      * sequence is short.  Doing it on long sequences can result
michael@0:      * in an O(n^2) DoS. */
michael@0:     if (end - i > 10) {
michael@0:       i = end;
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     hb_bubble_sort (buffer->info + i, end - i, compare_combining_class);
michael@0: 
michael@0:     i = end;
michael@0:   }
michael@0: 
michael@0: 
michael@0:   if (mode == HB_OT_SHAPE_NORMALIZATION_MODE_NONE ||
michael@0:       mode == HB_OT_SHAPE_NORMALIZATION_MODE_DECOMPOSED)
michael@0:     return;
michael@0: 
michael@0:   /* Third round, recompose */
michael@0: 
michael@0:   /* As noted in the comment earlier, we don't try to combine
michael@0:    * ccc=0 chars with their previous Starter. */
michael@0: 
michael@0:   buffer->clear_output ();
michael@0:   count = buffer->len;
michael@0:   unsigned int starter = 0;
michael@0:   buffer->next_glyph ();
michael@0:   while (buffer->idx < count)
michael@0:   {
michael@0:     hb_codepoint_t composed, glyph;
michael@0:     if (/* We don't try to compose a non-mark character with it's preceding starter.
michael@0: 	 * This is both an optimization to avoid trying to compose every two neighboring
michael@0: 	 * glyphs in most scripts AND a desired feature for Hangul.  Apparently Hangul
michael@0: 	 * fonts are not designed to mix-and-match pre-composed syllables and Jamo. */
michael@0: 	HB_UNICODE_GENERAL_CATEGORY_IS_MARK (_hb_glyph_info_get_general_category (&buffer->cur())) &&
michael@0: 	/* If there's anything between the starter and this char, they should have CCC
michael@0: 	 * smaller than this character's. */
michael@0: 	(starter == buffer->out_len - 1 ||
michael@0: 	 _hb_glyph_info_get_modified_combining_class (&buffer->prev()) < _hb_glyph_info_get_modified_combining_class (&buffer->cur())) &&
michael@0: 	/* And compose. */
michael@0: 	c.compose (&c,
michael@0: 		   buffer->out_info[starter].codepoint,
michael@0: 		   buffer->cur().codepoint,
michael@0: 		   &composed) &&
michael@0: 	/* And the font has glyph for the composite. */
michael@0: 	font->get_glyph (composed, 0, &glyph))
michael@0:     {
michael@0:       /* Composes. */
michael@0:       buffer->next_glyph (); /* Copy to out-buffer. */
michael@0:       if (unlikely (buffer->in_error))
michael@0:         return;
michael@0:       buffer->merge_out_clusters (starter, buffer->out_len);
michael@0:       buffer->out_len--; /* Remove the second composable. */
michael@0:       /* Modify starter and carry on. */
michael@0:       buffer->out_info[starter].codepoint = composed;
michael@0:       buffer->out_info[starter].glyph_index() = glyph;
michael@0:       _hb_glyph_info_set_unicode_props (&buffer->out_info[starter], buffer->unicode);
michael@0: 
michael@0:       continue;
michael@0:     }
michael@0: 
michael@0:     /* Blocked, or doesn't compose. */
michael@0:     buffer->next_glyph ();
michael@0: 
michael@0:     if (_hb_glyph_info_get_modified_combining_class (&buffer->prev()) == 0)
michael@0:       starter = buffer->out_len - 1;
michael@0:   }
michael@0:   buffer->swap_buffers ();
michael@0: 
michael@0: }