Towards normalization
[framework/uifw/harfbuzz.git] / src / hb-buffer.cc
1 /*
2  * Copyright © 1998-2004  David Turner and Werner Lemberg
3  * Copyright © 2004,2007,2009,2010  Red Hat, Inc.
4  * Copyright © 2011  Google, Inc.
5  *
6  *  This is part of HarfBuzz, a text shaping library.
7  *
8  * Permission is hereby granted, without written agreement and without
9  * license or royalty fees, to use, copy, modify, and distribute this
10  * software and its documentation for any purpose, provided that the
11  * above copyright notice and the following two paragraphs appear in
12  * all copies of this software.
13  *
14  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
15  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
16  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
17  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
18  * DAMAGE.
19  *
20  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
21  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
22  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
23  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
24  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
25  *
26  * Red Hat Author(s): Owen Taylor, Behdad Esfahbod
27  * Google Author(s): Behdad Esfahbod
28  */
29
30 #include "hb-buffer-private.hh"
31
32 #include <string.h>
33
34 HB_BEGIN_DECLS
35
36
37 static hb_buffer_t _hb_buffer_nil = {
38   HB_OBJECT_HEADER_STATIC,
39
40   &_hb_unicode_funcs_default,
41   {
42     HB_DIRECTION_INVALID,
43     HB_SCRIPT_INVALID,
44     NULL,
45   },
46
47   TRUE, /* in_error */
48   TRUE, /* have_output */
49   TRUE  /* have_positions */
50 };
51
52 /* Here is how the buffer works internally:
53  *
54  * There are two info pointers: info and out_info.  They always have
55  * the same allocated size, but different lengths.
56  *
57  * As an optimization, both info and out_info may point to the
58  * same piece of memory, which is owned by info.  This remains the
59  * case as long as out_len doesn't exceed i at any time.
60  * In that case, swap() is no-op and the glyph operations operate
61  * mostly in-place.
62  *
63  * As soon as out_info gets longer than info, out_info is moved over
64  * to an alternate buffer (which we reuse the pos buffer for!), and its
65  * current contents (out_len entries) are copied to the new place.
66  * This should all remain transparent to the user.  swap() then
67  * switches info and out_info.
68  */
69
70
71 static hb_bool_t
72 _hb_buffer_enlarge (hb_buffer_t *buffer, unsigned int size)
73 {
74   if (unlikely (buffer->in_error))
75     return FALSE;
76
77   unsigned int new_allocated = buffer->allocated;
78   hb_glyph_position_t *new_pos = NULL;
79   hb_glyph_info_t *new_info = NULL;
80   bool separate_out = buffer->out_info != buffer->info;
81
82   if (unlikely (_hb_unsigned_int_mul_overflows (size, sizeof (buffer->info[0]))))
83     goto done;
84
85   while (size > new_allocated)
86     new_allocated += (new_allocated >> 1) + 32;
87
88   ASSERT_STATIC (sizeof (buffer->info[0]) == sizeof (buffer->pos[0]));
89   if (unlikely (_hb_unsigned_int_mul_overflows (new_allocated, sizeof (buffer->info[0]))))
90     goto done;
91
92   new_pos = (hb_glyph_position_t *) realloc (buffer->pos, new_allocated * sizeof (buffer->pos[0]));
93   new_info = (hb_glyph_info_t *) realloc (buffer->info, new_allocated * sizeof (buffer->info[0]));
94
95 done:
96   if (unlikely (!new_pos || !new_info))
97     buffer->in_error = TRUE;
98
99   if (likely (new_pos))
100     buffer->pos = new_pos;
101
102   if (likely (new_info))
103     buffer->info = new_info;
104
105   buffer->out_info = separate_out ? (hb_glyph_info_t *) buffer->pos : buffer->info;
106   if (likely (!buffer->in_error))
107     buffer->allocated = new_allocated;
108
109   return likely (!buffer->in_error);
110 }
111
112 static inline hb_bool_t
113 _hb_buffer_ensure (hb_buffer_t *buffer, unsigned int size)
114 {
115   return likely (size <= buffer->allocated) ? TRUE : _hb_buffer_enlarge (buffer, size);
116 }
117
118 static inline hb_bool_t
119 _hb_buffer_ensure_separate (hb_buffer_t *buffer, unsigned int size)
120 {
121   if (unlikely (!size || !_hb_buffer_ensure (buffer, size))) return FALSE;
122
123   if (buffer->out_info == buffer->info)
124   {
125     assert (buffer->have_output);
126
127     buffer->out_info = (hb_glyph_info_t *) buffer->pos;
128     memcpy (buffer->out_info, buffer->info, buffer->out_len * sizeof (buffer->out_info[0]));
129   }
130
131   return TRUE;
132 }
133
134
135 /* Public API */
136
137 hb_buffer_t *
138 hb_buffer_create (unsigned int pre_alloc_size)
139 {
140   hb_buffer_t *buffer;
141
142   if (!(buffer = hb_object_create<hb_buffer_t> ()))
143     return &_hb_buffer_nil;
144
145   hb_buffer_reset (buffer);
146
147   if (pre_alloc_size && !_hb_buffer_ensure (buffer, pre_alloc_size)) {
148     hb_buffer_destroy (buffer);
149     return &_hb_buffer_nil;
150   }
151
152   return buffer;
153 }
154
155 hb_buffer_t *
156 hb_buffer_get_empty (void)
157 {
158   return &_hb_buffer_nil;
159 }
160
161 hb_buffer_t *
162 hb_buffer_reference (hb_buffer_t *buffer)
163 {
164   return hb_object_reference (buffer);
165 }
166
167 void
168 hb_buffer_destroy (hb_buffer_t *buffer)
169 {
170   if (!hb_object_destroy (buffer)) return;
171
172   hb_unicode_funcs_destroy (buffer->unicode);
173
174   free (buffer->info);
175   free (buffer->pos);
176
177   free (buffer);
178 }
179
180 hb_bool_t
181 hb_buffer_set_user_data (hb_buffer_t        *buffer,
182                          hb_user_data_key_t *key,
183                          void *              data,
184                          hb_destroy_func_t   destroy)
185 {
186   return hb_object_set_user_data (buffer, key, data, destroy);
187 }
188
189 void *
190 hb_buffer_get_user_data (hb_buffer_t        *buffer,
191                          hb_user_data_key_t *key)
192 {
193   return hb_object_get_user_data (buffer, key);
194 }
195
196
197 void
198 hb_buffer_set_unicode_funcs (hb_buffer_t        *buffer,
199                              hb_unicode_funcs_t *unicode)
200 {
201   if (unlikely (hb_object_is_inert (buffer)))
202     return;
203
204   if (!unicode)
205     unicode = _hb_buffer_nil.unicode;
206
207   hb_unicode_funcs_reference (unicode);
208   hb_unicode_funcs_destroy (buffer->unicode);
209   buffer->unicode = unicode;
210 }
211
212 hb_unicode_funcs_t *
213 hb_buffer_get_unicode_funcs (hb_buffer_t        *buffer)
214 {
215   return buffer->unicode;
216 }
217
218 void
219 hb_buffer_set_direction (hb_buffer_t    *buffer,
220                          hb_direction_t  direction)
221
222 {
223   if (unlikely (hb_object_is_inert (buffer)))
224     return;
225
226   buffer->props.direction = direction;
227 }
228
229 hb_direction_t
230 hb_buffer_get_direction (hb_buffer_t    *buffer)
231 {
232   return buffer->props.direction;
233 }
234
235 void
236 hb_buffer_set_script (hb_buffer_t *buffer,
237                       hb_script_t  script)
238 {
239   if (unlikely (hb_object_is_inert (buffer)))
240     return;
241
242   buffer->props.script = script;
243 }
244
245 hb_script_t
246 hb_buffer_get_script (hb_buffer_t *buffer)
247 {
248   return buffer->props.script;
249 }
250
251 void
252 hb_buffer_set_language (hb_buffer_t   *buffer,
253                         hb_language_t  language)
254 {
255   if (unlikely (hb_object_is_inert (buffer)))
256     return;
257
258   buffer->props.language = language;
259 }
260
261 hb_language_t
262 hb_buffer_get_language (hb_buffer_t *buffer)
263 {
264   return buffer->props.language;
265 }
266
267
268 void
269 hb_buffer_reset (hb_buffer_t *buffer)
270 {
271   if (unlikely (hb_object_is_inert (buffer)))
272     return;
273
274   hb_unicode_funcs_destroy (buffer->unicode);
275   buffer->unicode = _hb_buffer_nil.unicode;
276
277   buffer->props = _hb_buffer_nil.props;
278
279   buffer->in_error = FALSE;
280   buffer->have_output = FALSE;
281   buffer->have_positions = FALSE;
282
283   buffer->i = 0;
284   buffer->len = 0;
285   buffer->out_len = 0;
286
287   buffer->serial = 0;
288
289   buffer->out_info = buffer->info;
290 }
291
292 hb_bool_t
293 hb_buffer_pre_allocate (hb_buffer_t *buffer, unsigned int size)
294 {
295   return _hb_buffer_ensure (buffer, size);
296 }
297
298 hb_bool_t
299 hb_buffer_allocation_successful (hb_buffer_t  *buffer)
300 {
301   return !buffer->in_error;
302 }
303
304 void
305 hb_buffer_add (hb_buffer_t    *buffer,
306                hb_codepoint_t  codepoint,
307                hb_mask_t       mask,
308                unsigned int    cluster)
309 {
310   hb_glyph_info_t *glyph;
311
312   if (unlikely (!_hb_buffer_ensure (buffer, buffer->len + 1))) return;
313
314   glyph = &buffer->info[buffer->len];
315
316   memset (glyph, 0, sizeof (*glyph));
317   glyph->codepoint = codepoint;
318   glyph->mask = mask;
319   glyph->cluster = cluster;
320
321   buffer->len++;
322 }
323
324 /* HarfBuzz-Internal API */
325
326 void
327 _hb_buffer_clear_output (hb_buffer_t *buffer)
328 {
329   if (unlikely (hb_object_is_inert (buffer)))
330     return;
331
332   buffer->have_output = TRUE;
333   buffer->have_positions = FALSE;
334
335   buffer->out_len = 0;
336   buffer->out_info = buffer->info;
337 }
338
339 void
340 _hb_buffer_clear_positions (hb_buffer_t *buffer)
341 {
342   if (unlikely (hb_object_is_inert (buffer)))
343     return;
344
345   buffer->have_output = FALSE;
346   buffer->have_positions = TRUE;
347
348   memset (buffer->pos, 0, sizeof (buffer->pos[0]) * buffer->len);
349 }
350
351 void
352 _hb_buffer_swap (hb_buffer_t *buffer)
353 {
354   if (unlikely (buffer->in_error)) return;
355
356   assert (buffer->have_output);
357
358   if (buffer->out_info != buffer->info)
359   {
360     hb_glyph_info_t *tmp_string;
361     tmp_string = buffer->info;
362     buffer->info = buffer->out_info;
363     buffer->out_info = tmp_string;
364     buffer->pos = (hb_glyph_position_t *) buffer->out_info;
365   }
366
367   unsigned int tmp;
368   tmp = buffer->len;
369   buffer->len = buffer->out_len;
370   buffer->out_len = tmp;
371
372   buffer->i = 0;
373 }
374
375 void
376 _hb_buffer_replace_glyphs_be16 (hb_buffer_t *buffer,
377                                 unsigned int num_in,
378                                 unsigned int num_out,
379                                 const uint16_t *glyph_data_be)
380 {
381   if (buffer->out_info != buffer->info ||
382       buffer->out_len + num_out > buffer->i + num_in)
383   {
384     if (unlikely (!_hb_buffer_ensure_separate (buffer, buffer->out_len + num_out)))
385       return;
386   }
387
388   hb_glyph_info_t orig_info = buffer->info[buffer->i];
389   for (unsigned int i = 1; i < num_in; i++)
390   {
391     hb_glyph_info_t *info = &buffer->info[buffer->i + i];
392     orig_info.cluster = MIN (orig_info.cluster, info->cluster);
393   }
394
395   for (unsigned int i = 0; i < num_out; i++)
396   {
397     hb_glyph_info_t *info = &buffer->out_info[buffer->out_len + i];
398     *info = orig_info;
399     info->codepoint = hb_be_uint16 (glyph_data_be[i]);
400   }
401
402   buffer->i  += num_in;
403   buffer->out_len += num_out;
404 }
405
406 void
407 _hb_buffer_output_glyph (hb_buffer_t *buffer,
408                          hb_codepoint_t glyph_index)
409 {
410   hb_glyph_info_t *info;
411
412   if (buffer->out_info != buffer->info)
413   {
414     if (unlikely (!_hb_buffer_ensure (buffer, buffer->out_len + 1))) return;
415     buffer->out_info[buffer->out_len] = buffer->info[buffer->i];
416   }
417   else if (buffer->out_len != buffer->i)
418     buffer->out_info[buffer->out_len] = buffer->info[buffer->i];
419
420   info = &buffer->out_info[buffer->out_len];
421   info->codepoint = glyph_index;
422
423   buffer->out_len++;
424 }
425
426 void
427 _hb_buffer_replace_glyph (hb_buffer_t *buffer,
428                           hb_codepoint_t glyph_index)
429 {
430   _hb_buffer_output_glyph (buffer, glyph_index);
431   _hb_buffer_skip_glyph (buffer);
432 }
433
434 void
435 _hb_buffer_skip_glyph (hb_buffer_t *buffer)
436 {
437   buffer->i++;
438 }
439
440 void
441 _hb_buffer_next_glyph (hb_buffer_t *buffer)
442 {
443   if (buffer->have_output)
444   {
445     if (buffer->out_info != buffer->info)
446     {
447       if (unlikely (!_hb_buffer_ensure (buffer, buffer->out_len + 1))) return;
448       buffer->out_info[buffer->out_len] = buffer->info[buffer->i];
449     }
450     else if (buffer->out_len != buffer->i)
451       buffer->out_info[buffer->out_len] = buffer->info[buffer->i];
452
453     buffer->out_len++;
454   }
455
456   buffer->i++;
457 }
458
459 void
460 _hb_buffer_reset_masks (hb_buffer_t *buffer,
461                         hb_mask_t    mask)
462 {
463   unsigned int count = buffer->len;
464   for (unsigned int i = 0; i < count; i++)
465     buffer->info[i].mask = mask;
466 }
467
468 void
469 _hb_buffer_add_masks (hb_buffer_t *buffer,
470                       hb_mask_t    mask)
471 {
472   unsigned int count = buffer->len;
473   for (unsigned int i = 0; i < count; i++)
474     buffer->info[i].mask |= mask;
475 }
476
477 void
478 _hb_buffer_set_masks (hb_buffer_t *buffer,
479                       hb_mask_t    value,
480                       hb_mask_t    mask,
481                       unsigned int cluster_start,
482                       unsigned int cluster_end)
483 {
484   hb_mask_t not_mask = ~mask;
485   value &= mask;
486
487   if (!mask)
488     return;
489
490   if (cluster_start == 0 && cluster_end == (unsigned int)-1) {
491     unsigned int count = buffer->len;
492     for (unsigned int i = 0; i < count; i++)
493       buffer->info[i].mask = (buffer->info[i].mask & not_mask) | value;
494     return;
495   }
496
497   unsigned int count = buffer->len;
498   for (unsigned int i = 0; i < count; i++)
499     if (cluster_start <= buffer->info[i].cluster && buffer->info[i].cluster < cluster_end)
500       buffer->info[i].mask = (buffer->info[i].mask & not_mask) | value;
501 }
502
503
504 /* Public API again */
505
506 hb_bool_t
507 hb_buffer_set_length (hb_buffer_t  *buffer,
508                       unsigned int  length)
509 {
510   if (!_hb_buffer_ensure (buffer, length))
511     return FALSE;
512
513   /* Wipe the new space */
514   if (length > buffer->len) {
515     memset (buffer->info + buffer->len, 0, sizeof (buffer->info[0]) * (length - buffer->len));
516     if (buffer->have_positions)
517       memset (buffer->pos + buffer->len, 0, sizeof (buffer->pos[0]) * (length - buffer->len));
518   }
519
520   buffer->len = length;
521   return TRUE;
522 }
523
524 unsigned int
525 hb_buffer_get_length (hb_buffer_t *buffer)
526 {
527   return buffer->len;
528 }
529
530 /* Return value valid as long as buffer not modified */
531 hb_glyph_info_t *
532 hb_buffer_get_glyph_infos (hb_buffer_t  *buffer,
533                            unsigned int *length)
534 {
535   if (length)
536     *length = buffer->len;
537
538   return (hb_glyph_info_t *) buffer->info;
539 }
540
541 /* Return value valid as long as buffer not modified */
542 hb_glyph_position_t *
543 hb_buffer_get_glyph_positions (hb_buffer_t  *buffer,
544                                unsigned int *length)
545 {
546   if (!buffer->have_positions)
547     _hb_buffer_clear_positions (buffer);
548
549   if (length)
550     *length = buffer->len;
551
552   return (hb_glyph_position_t *) buffer->pos;
553 }
554
555
556 static inline void
557 reverse_range (hb_buffer_t *buffer,
558                unsigned int start,
559                unsigned int end)
560 {
561   unsigned int i, j;
562
563   if (start == end - 1)
564     return;
565
566   for (i = start, j = end - 1; i < j; i++, j--) {
567     hb_glyph_info_t t;
568
569     t = buffer->info[i];
570     buffer->info[i] = buffer->info[j];
571     buffer->info[j] = t;
572   }
573
574   if (buffer->pos) {
575     for (i = start, j = end - 1; i < j; i++, j--) {
576       hb_glyph_position_t t;
577
578       t = buffer->pos[i];
579       buffer->pos[i] = buffer->pos[j];
580       buffer->pos[j] = t;
581     }
582   }
583 }
584
585 void
586 hb_buffer_reverse (hb_buffer_t *buffer)
587 {
588   if (unlikely (!buffer->len))
589     return;
590
591   reverse_range (buffer, 0, buffer->len);
592 }
593
594 void
595 hb_buffer_reverse_clusters (hb_buffer_t *buffer)
596 {
597   unsigned int i, start, count, last_cluster;
598
599   if (unlikely (!buffer->len))
600     return;
601
602   hb_buffer_reverse (buffer);
603
604   count = buffer->len;
605   start = 0;
606   last_cluster = buffer->info[0].cluster;
607   for (i = 1; i < count; i++) {
608     if (last_cluster != buffer->info[i].cluster) {
609       reverse_range (buffer, start, i);
610       start = i;
611       last_cluster = buffer->info[i].cluster;
612     }
613   }
614   reverse_range (buffer, start, i);
615 }
616
617
618 #define ADD_UTF(T) \
619         HB_STMT_START { \
620           const T *next = (const T *) text + item_offset; \
621           const T *end = next + item_length; \
622           while (next < end) { \
623             hb_codepoint_t u; \
624             const T *old_next = next; \
625             next = UTF_NEXT (next, end, u); \
626             hb_buffer_add (buffer, u, 1,  old_next - (const T *) text); \
627           } \
628         } HB_STMT_END
629
630
631 #define UTF8_COMPUTE(Char, Mask, Len) \
632   if (Char < 128) { Len = 1; Mask = 0x7f; } \
633   else if ((Char & 0xe0) == 0xc0) { Len = 2; Mask = 0x1f; } \
634   else if ((Char & 0xf0) == 0xe0) { Len = 3; Mask = 0x0f; } \
635   else if ((Char & 0xf8) == 0xf0) { Len = 4; Mask = 0x07; } \
636   else Len = 0;
637
638 static inline const uint8_t *
639 hb_utf8_next (const uint8_t *text,
640               const uint8_t *end,
641               hb_codepoint_t *unicode)
642 {
643   uint8_t c = *text;
644   unsigned int mask, len;
645
646   /* TODO check for overlong sequences? */
647
648   UTF8_COMPUTE (c, mask, len);
649   if (unlikely (!len || (unsigned int) (end - text) < len)) {
650     *unicode = -1;
651     return text + 1;
652   } else {
653     hb_codepoint_t result;
654     unsigned int i;
655     result = c & mask;
656     for (i = 1; i < len; i++)
657       {
658         if (unlikely ((text[i] & 0xc0) != 0x80))
659           {
660             *unicode = -1;
661             return text + 1;
662           }
663         result <<= 6;
664         result |= (text[i] & 0x3f);
665       }
666     *unicode = result;
667     return text + len;
668   }
669 }
670
671 void
672 hb_buffer_add_utf8 (hb_buffer_t  *buffer,
673                     const char   *text,
674                     unsigned int  text_length HB_UNUSED,
675                     unsigned int  item_offset,
676                     unsigned int  item_length)
677 {
678 #define UTF_NEXT(S, E, U)       hb_utf8_next (S, E, &(U))
679   ADD_UTF (uint8_t);
680 #undef UTF_NEXT
681 }
682
683 static inline const uint16_t *
684 hb_utf16_next (const uint16_t *text,
685                const uint16_t *end,
686                hb_codepoint_t *unicode)
687 {
688   uint16_t c = *text++;
689
690   if (unlikely (c >= 0xd800 && c < 0xdc00)) {
691     /* high surrogate */
692     uint16_t l;
693     if (text < end && ((l = *text), likely (l >= 0xdc00 && l < 0xe000))) {
694       /* low surrogate */
695       *unicode = ((hb_codepoint_t) ((c) - 0xd800) * 0x400 + (l) - 0xdc00 + 0x10000);
696        text++;
697     } else
698       *unicode = -1;
699   } else
700     *unicode = c;
701
702   return text;
703 }
704
705 void
706 hb_buffer_add_utf16 (hb_buffer_t    *buffer,
707                      const uint16_t *text,
708                      unsigned int    text_length HB_UNUSED,
709                      unsigned int    item_offset,
710                      unsigned int    item_length)
711 {
712 #define UTF_NEXT(S, E, U)       hb_utf16_next (S, E, &(U))
713   ADD_UTF (uint16_t);
714 #undef UTF_NEXT
715 }
716
717 void
718 hb_buffer_add_utf32 (hb_buffer_t    *buffer,
719                      const uint32_t *text,
720                      unsigned int    text_length HB_UNUSED,
721                      unsigned int    item_offset,
722                      unsigned int    item_length)
723 {
724 #define UTF_NEXT(S, E, U)       ((U) = *(S), (S)+1)
725   ADD_UTF (uint32_t);
726 #undef UTF_NEXT
727 }
728
729
730 HB_END_DECLS