Implement Unicode Canonical Reordering Algorithm
[framework/uifw/harfbuzz.git] / src / hb-ot-shape-normalize.cc
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 HB_BEGIN_DECLS
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.  The shaper an either prefer decomposed (NFD) or
39  * composed (NFC).
40  *
41  * In general what happens is that: each grapheme is decomposed in a chain
42  * of 1:2 decompositions, marks reordered, and then recomposed if desires,
43  * so far it's like Unicode Normalization.  However, the decomposition and
44  * recomposition only happens if the font supports the resulting characters.
45  *
46  * The goals are:
47  *
48  *   - Try to render all canonically equivalent strings similarly.  To really
49  *     achieve this we have to always do the full decomposition and then
50  *     selectively recompose from there.  It's kinda too expensive though, so
51  *     we skip some cases.  For example, if composed is desired, we simply
52  *     don't touch 1-character clusters that are supported by the font, even
53  *     though their NFC may be different.
54  *
55  *   - When a font has a precomposed character for a sequence but the 'ccmp'
56  *     feature in the font is not adequate, form use the precomposed character
57  *     which typically has better mark positioning.
58  *
59  *   - When a font does not support a character but supports its decomposition,
60  *     well, use the decomposition.
61  *
62  *   - The Indic shaper requests decomposed output.  This will handle splitting
63  *     matra for the Indic shaper.
64  */
65
66
67 static bool
68 decompose (hb_ot_shape_context_t *c,
69            bool shortest,
70            hb_codepoint_t ab)
71 {
72   hb_codepoint_t a, b, glyph;
73
74   if (!hb_unicode_decompose (c->buffer->unicode, ab, &a, &b) ||
75       !hb_font_get_glyph (c->font, b, 0, &glyph))
76     return FALSE;
77
78   /* XXX handle singleton decompositions */
79   bool has_a = hb_font_get_glyph (c->font, a, 0, &glyph);
80   if (shortest && has_a) {
81     /* Output a and b */
82     c->buffer->output_glyph (a);
83     c->buffer->output_glyph (b);
84     return TRUE;
85   }
86
87   if (decompose (c, shortest, a)) {
88     c->buffer->output_glyph (b);
89     return TRUE;
90   }
91
92   if (has_a) {
93     c->buffer->output_glyph (a);
94     c->buffer->output_glyph (b);
95     return TRUE;
96   }
97
98   return FALSE;
99 }
100
101 static bool
102 decompose_current_glyph (hb_ot_shape_context_t *c,
103                          bool shortest)
104 {
105   if (decompose (c, shortest, c->buffer->info[c->buffer->idx].codepoint)) {
106     c->buffer->skip_glyph ();
107     return TRUE;
108   } else {
109     c->buffer->next_glyph ();
110     return FALSE;
111   }
112 }
113
114 static bool
115 decompose_single_char_cluster (hb_ot_shape_context_t *c,
116                                bool will_recompose)
117 {
118   hb_codepoint_t glyph;
119
120   /* If recomposing and font supports this, we're good to go */
121   if (will_recompose && hb_font_get_glyph (c->font, c->buffer->info[c->buffer->idx].codepoint, 0, &glyph)) {
122     c->buffer->next_glyph ();
123     return FALSE;
124   }
125
126   return decompose_current_glyph (c, will_recompose);
127 }
128
129 static bool
130 decompose_multi_char_cluster (hb_ot_shape_context_t *c,
131                               unsigned int end)
132 {
133   bool changed = FALSE;
134
135   /* TODO Currently if there's a variation-selector we give-up, it's just too hard. */
136   for (unsigned int i = c->buffer->idx; i < end; i++)
137     if (unlikely (is_variation_selector (c->buffer->info[i].codepoint)))
138       return changed;
139
140   while (c->buffer->idx < end)
141     changed |= decompose_current_glyph (c, FALSE);
142
143   return changed;
144 }
145
146 void
147 _hb_ot_shape_normalize (hb_ot_shape_context_t *c)
148 {
149   hb_buffer_t *buffer = c->buffer;
150   bool recompose = !hb_ot_shape_complex_prefer_decomposed (c->plan->shaper);
151   bool changed = FALSE;
152   bool has_multichar_clusters = FALSE;
153   unsigned int count;
154
155   buffer->clear_output ();
156
157
158   /* First round, decompose */
159
160   count = buffer->len;
161   for (buffer->idx = 0; buffer->idx < count;)
162   {
163     unsigned int end;
164     for (end = buffer->idx + 1; end < count; end++)
165       if (buffer->info[buffer->idx].cluster != buffer->info[end].cluster)
166         break;
167
168     if (buffer->idx + 1 == end)
169       changed |= decompose_single_char_cluster (c, recompose);
170     else {
171       changed |= decompose_multi_char_cluster (c, end);
172       has_multichar_clusters = TRUE;
173     }
174   }
175   buffer->swap_buffers ();
176
177
178   /* Technically speaking, two characters with ccc=0 may combine.  But all
179    * those cases are in languages that the indic module handles (which expects
180    * decomposed), or in Hangul jamo, which again, we want decomposed anyway.
181    * So we don't bother combining across cluster boundaries. */
182
183   if (!has_multichar_clusters)
184     return; /* Done! */
185
186   if (changed)
187     _hb_set_unicode_props (c->buffer); /* BUFFER: Set general_category and combining_class in var1 */
188
189
190   /* Second round, reorder (inplace) */
191
192   count = buffer->len;
193   for (unsigned int i = 0; i < count; i++)
194   {
195     if (buffer->info[i].combining_class() == 0)
196       continue;
197
198     unsigned int end;
199     for (end = i + 1; end < count; end++)
200       if (buffer->info[end].combining_class() == 0)
201         break;
202
203     /* We are going to do a bubble-sort.  Only do this if the
204      * sequence is short.  Doing it on long sequences can result
205      * in an O(n^2) DoS. */
206     if (end - i > 10) {
207       i = end;
208       continue;
209     }
210
211     unsigned int k = end - i - 1;
212     do {
213       hb_glyph_info_t *pinfo = buffer->info + i;
214       unsigned int new_k = 0;
215
216       for (unsigned int j = 0; j < k; j++)
217         if (pinfo[j].combining_class() > pinfo[j+1].combining_class()) {
218           hb_glyph_info_t t;
219           t = pinfo[j];
220           pinfo[j] = pinfo[j + 1];
221           pinfo[j + 1] = t;
222
223           new_k = j;
224         }
225       k = new_k;
226     } while (k);
227
228     i = end;
229   }
230
231
232   /* Third round, recompose */
233
234   if (recompose) {
235
236
237   }
238
239 }
240
241 HB_END_DECLS