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 Xhb_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_buffers() 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_buffers() then
  67  * switches info and out_info.
  68  */
  69
  70
  71
  72 /* Internal API */
  73
  74 bool
  75 hb_buffer_t::enlarge (unsigned int size)
  76 {
  77   if (unlikely (in_error))
  78     return FALSE;
  79
  80   unsigned int new_allocated = allocated;
  81   hb_glyph_position_t *new_pos = NULL;
  82   hb_glyph_info_t *new_info = NULL;
  83   bool separate_out = out_info != info;
  84
  85   if (unlikely (_hb_unsigned_int_mul_overflows (size, sizeof (info[0]))))
  86     goto done;
  87
  88   while (size > new_allocated)
  89     new_allocated += (new_allocated >> 1) + 32;
  90
  91   ASSERT_STATIC (sizeof (info[0]) == sizeof (pos[0]));
  92   if (unlikely (_hb_unsigned_int_mul_overflows (new_allocated, sizeof (info[0]))))
  93     goto done;
  94
  95   new_pos = (hb_glyph_position_t *) realloc (pos, new_allocated * sizeof (pos[0]));
  96   new_info = (hb_glyph_info_t *) realloc (info, new_allocated * sizeof (info[0]));
  97
  98 done:
  99   if (unlikely (!new_pos || !new_info))
 100     in_error = TRUE;
 101
 102   if (likely (new_pos))
 103     pos = new_pos;
 104
 105   if (likely (new_info))
 106     info = new_info;
 107
 108   out_info = separate_out ? (hb_glyph_info_t *) pos : info;
 109   if (likely (!in_error))
 110     allocated = new_allocated;
 111
 112   return likely (!in_error);
 113 }
 114
 115 bool
 116 hb_buffer_t::make_room_for (unsigned int num_in,
 117                             unsigned int num_out)
 118 {
 119   if (unlikely (!ensure (out_len + num_out))) return FALSE;
 120
 121   if (out_info == info &&
 122       out_len + num_out > idx + num_in)
 123   {
 124     assert (have_output);
 125
 126     out_info = (hb_glyph_info_t *) pos;
 127     memcpy (out_info, info, out_len * sizeof (out_info[0]));
 128   }
 129
 130   return TRUE;
 131 }
 132
 133
 134 /* HarfBuzz-Internal API */
 135
 136 void
 137 hb_buffer_t::reset (void)
 138 {
 139   if (unlikely (hb_object_is_inert (this)))
 140     return;
 141
 142   hb_unicode_funcs_destroy (unicode);
 143   unicode = Xhb_buffer_nil.unicode;
 144
 145   props = Xhb_buffer_nil.props;
 146
 147   in_error = FALSE;
 148   have_output = FALSE;
 149   have_positions = FALSE;
 150
 151   idx = 0;
 152   len = 0;
 153   out_len = 0;
 154
 155   serial = 0;
 156
 157   out_info = info;
 158 }
 159
 160 void
 161 hb_buffer_t::add (hb_codepoint_t  codepoint,
 162                   hb_mask_t       mask,
 163                   unsigned int    cluster)
 164 {
 165   hb_glyph_info_t *glyph;
 166
 167   if (unlikely (!ensure (len + 1))) return;
 168
 169   glyph = &info[len];
 170
 171   memset (glyph, 0, sizeof (*glyph));
 172   glyph->codepoint = codepoint;
 173   glyph->mask = mask;
 174   glyph->cluster = cluster;
 175
 176   len++;
 177 }
 178
 179 void
 180 hb_buffer_t::clear_output (void)
 181 {
 182   if (unlikely (hb_object_is_inert (this)))
 183     return;
 184
 185   have_output = TRUE;
 186   have_positions = FALSE;
 187
 188   out_len = 0;
 189   out_info = info;
 190 }
 191
 192 void
 193 hb_buffer_t::clear_positions (void)
 194 {
 195   if (unlikely (hb_object_is_inert (this)))
 196     return;
 197
 198   have_output = FALSE;
 199   have_positions = TRUE;
 200
 201   memset (pos, 0, sizeof (pos[0]) * len);
 202 }
 203
 204 void
 205 hb_buffer_t::swap_buffers (void)
 206 {
 207   if (unlikely (in_error)) return;
 208
 209   assert (have_output);
 210
 211   if (out_info != info)
 212   {
 213     hb_glyph_info_t *tmp_string;
 214     tmp_string = info;
 215     info = out_info;
 216     out_info = tmp_string;
 217     pos = (hb_glyph_position_t *) out_info;
 218   }
 219
 220   unsigned int tmp;
 221   tmp = len;
 222   len = out_len;
 223   out_len = tmp;
 224
 225   idx = 0;
 226 }
 227
 228 void
 229 hb_buffer_t::replace_glyphs_be16 (unsigned int num_in,
 230                                   unsigned int num_out,
 231                                   const uint16_t *glyph_data_be)
 232 {
 233   if (!make_room_for (num_in, num_out)) return;
 234
 235   hb_glyph_info_t orig_info = info[idx];
 236   for (unsigned int i = 1; i < num_in; i++)
 237   {
 238     hb_glyph_info_t *inf = &info[idx + i];
 239     orig_info.cluster = MIN (orig_info.cluster, inf->cluster);
 240   }
 241
 242   hb_glyph_info_t *pinfo = &out_info[out_len];
 243   for (unsigned int i = 0; i < num_out; i++)
 244   {
 245     *pinfo = orig_info;
 246     pinfo->codepoint = hb_be_uint16 (glyph_data_be[i]);
 247     pinfo++;
 248   }
 249
 250   idx  += num_in;
 251   out_len += num_out;
 252 }
 253
 254 void
 255 hb_buffer_t::output_glyph (hb_codepoint_t glyph_index)
 256 {
 257   if (!make_room_for (0, 1)) return;
 258
 259   out_info[out_len] = info[idx];
 260   out_info[out_len].codepoint = glyph_index;
 261
 262   out_len++;
 263 }
 264
 265 void
 266 hb_buffer_t::copy_glyph (void)
 267 {
 268   if (!make_room_for (0, 1)) return;
 269
 270   out_info[out_len] = info[idx];
 271
 272   out_len++;
 273 }
 274
 275 void
 276 hb_buffer_t::replace_glyph (hb_codepoint_t glyph_index)
 277 {
 278   out_info[out_len] = info[idx];
 279   out_info[out_len].codepoint = glyph_index;
 280
 281   idx++;
 282   out_len++;
 283 }
 284
 285 void
 286 hb_buffer_t::next_glyph (void)
 287 {
 288   if (have_output)
 289   {
 290     if (out_info != info)
 291     {
 292       if (unlikely (!ensure (out_len + 1))) return;
 293       out_info[out_len] = info[idx];
 294     }
 295     else if (out_len != idx)
 296       out_info[out_len] = info[idx];
 297
 298     out_len++;
 299   }
 300
 301   idx++;
 302 }
 303
 304 void
 305 hb_buffer_t::set_masks (hb_mask_t    value,
 306                         hb_mask_t    mask,
 307                         unsigned int cluster_start,
 308                         unsigned int cluster_end)
 309 {
 310   hb_mask_t not_mask = ~mask;
 311   value &= mask;
 312
 313   if (!mask)
 314     return;
 315
 316   if (cluster_start == 0 && cluster_end == (unsigned int)-1) {
 317     unsigned int count = len;
 318     for (unsigned int i = 0; i < count; i++)
 319       info[i].mask = (info[i].mask & not_mask) | value;
 320     return;
 321   }
 322
 323   unsigned int count = len;
 324   for (unsigned int i = 0; i < count; i++)
 325     if (cluster_start <= info[i].cluster && info[i].cluster < cluster_end)
 326       info[i].mask = (info[i].mask & not_mask) | value;
 327 }
 328
 329 void
 330 hb_buffer_t::reverse_range (unsigned int start,
 331                             unsigned int end)
 332 {
 333   unsigned int i, j;
 334
 335   if (start == end - 1)
 336     return;
 337
 338   for (i = start, j = end - 1; i < j; i++, j--) {
 339     hb_glyph_info_t t;
 340
 341     t = info[i];
 342     info[i] = info[j];
 343     info[j] = t;
 344   }
 345
 346   if (pos) {
 347     for (i = start, j = end - 1; i < j; i++, j--) {
 348       hb_glyph_position_t t;
 349
 350       t = pos[i];
 351       pos[i] = pos[j];
 352       pos[j] = t;
 353     }
 354   }
 355 }
 356
 357 void
 358 hb_buffer_t::reverse (void)
 359 {
 360   if (unlikely (!len))
 361     return;
 362
 363   reverse_range (0, len);
 364 }
 365
 366 void
 367 hb_buffer_t::reverse_clusters (void)
 368 {
 369   unsigned int i, start, count, last_cluster;
 370
 371   if (unlikely (!len))
 372     return;
 373
 374   reverse ();
 375
 376   count = len;
 377   start = 0;
 378   last_cluster = info[0].cluster;
 379   for (i = 1; i < count; i++) {
 380     if (last_cluster != info[i].cluster) {
 381       reverse_range (start, i);
 382       start = i;
 383       last_cluster = info[i].cluster;
 384     }
 385   }
 386   reverse_range (start, i);
 387 }
 388
 389
 390 /* Public API */
 391
 392 hb_buffer_t *
 393 hb_buffer_create (unsigned int pre_alloc_size)
 394 {
 395   hb_buffer_t *buffer;
 396
 397   if (!(buffer = hb_object_create<hb_buffer_t> ()))
 398     return &Xhb_buffer_nil;
 399
 400   buffer->reset ();
 401
 402   if (pre_alloc_size && !buffer->ensure (pre_alloc_size)) {
 403     hb_buffer_destroy (buffer);
 404     return &Xhb_buffer_nil;
 405   }
 406
 407   return buffer;
 408 }
 409
 410 hb_buffer_t *
 411 hb_buffer_get_empty (void)
 412 {
 413   return &Xhb_buffer_nil;
 414 }
 415
 416 hb_buffer_t *
 417 hb_buffer_reference (hb_buffer_t *buffer)
 418 {
 419   return hb_object_reference (buffer);
 420 }
 421
 422 void
 423 hb_buffer_destroy (hb_buffer_t *buffer)
 424 {
 425   if (!hb_object_destroy (buffer)) return;
 426
 427   hb_unicode_funcs_destroy (buffer->unicode);
 428
 429   free (buffer->info);
 430   free (buffer->pos);
 431
 432   free (buffer);
 433 }
 434
 435 hb_bool_t
 436 hb_buffer_set_user_data (hb_buffer_t        *buffer,
 437                          hb_user_data_key_t *key,
 438                          void *              data,
 439                          hb_destroy_func_t   destroy)
 440 {
 441   return hb_object_set_user_data (buffer, key, data, destroy);
 442 }
 443
 444 void *
 445 hb_buffer_get_user_data (hb_buffer_t        *buffer,
 446                          hb_user_data_key_t *key)
 447 {
 448   return hb_object_get_user_data (buffer, key);
 449 }
 450
 451
 452 void
 453 hb_buffer_set_unicode_funcs (hb_buffer_t        *buffer,
 454                              hb_unicode_funcs_t *unicode)
 455 {
 456   if (unlikely (hb_object_is_inert (buffer)))
 457     return;
 458
 459   if (!unicode)
 460     unicode = Xhb_buffer_nil.unicode;
 461
 462   hb_unicode_funcs_reference (unicode);
 463   hb_unicode_funcs_destroy (buffer->unicode);
 464   buffer->unicode = unicode;
 465 }
 466
 467 hb_unicode_funcs_t *
 468 hb_buffer_get_unicode_funcs (hb_buffer_t        *buffer)
 469 {
 470   return buffer->unicode;
 471 }
 472
 473 void
 474 hb_buffer_set_direction (hb_buffer_t    *buffer,
 475                          hb_direction_t  direction)
 476
 477 {
 478   if (unlikely (hb_object_is_inert (buffer)))
 479     return;
 480
 481   buffer->props.direction = direction;
 482 }
 483
 484 hb_direction_t
 485 hb_buffer_get_direction (hb_buffer_t    *buffer)
 486 {
 487   return buffer->props.direction;
 488 }
 489
 490 void
 491 hb_buffer_set_script (hb_buffer_t *buffer,
 492                       hb_script_t  script)
 493 {
 494   if (unlikely (hb_object_is_inert (buffer)))
 495     return;
 496
 497   buffer->props.script = script;
 498 }
 499
 500 hb_script_t
 501 hb_buffer_get_script (hb_buffer_t *buffer)
 502 {
 503   return buffer->props.script;
 504 }
 505
 506 void
 507 hb_buffer_set_language (hb_buffer_t   *buffer,
 508                         hb_language_t  language)
 509 {
 510   if (unlikely (hb_object_is_inert (buffer)))
 511     return;
 512
 513   buffer->props.language = language;
 514 }
 515
 516 hb_language_t
 517 hb_buffer_get_language (hb_buffer_t *buffer)
 518 {
 519   return buffer->props.language;
 520 }
 521
 522
 523 void
 524 hb_buffer_reset (hb_buffer_t *buffer)
 525 {
 526   buffer->reset ();
 527 }
 528
 529 hb_bool_t
 530 hb_buffer_pre_allocate (hb_buffer_t *buffer, unsigned int size)
 531 {
 532   return buffer->ensure (size);
 533 }
 534
 535 hb_bool_t
 536 hb_buffer_allocation_successful (hb_buffer_t  *buffer)
 537 {
 538   return !buffer->in_error;
 539 }
 540
 541 void
 542 hb_buffer_add (hb_buffer_t    *buffer,
 543                hb_codepoint_t  codepoint,
 544                hb_mask_t       mask,
 545                unsigned int    cluster)
 546 {
 547   buffer->add (codepoint, mask, cluster);
 548 }
 549
 550 hb_bool_t
 551 hb_buffer_set_length (hb_buffer_t  *buffer,
 552                       unsigned int  length)
 553 {
 554   if (!buffer->ensure (length))
 555     return FALSE;
 556
 557   /* Wipe the new space */
 558   if (length > buffer->len) {
 559     memset (buffer->info + buffer->len, 0, sizeof (buffer->info[0]) * (length - buffer->len));
 560     if (buffer->have_positions)
 561       memset (buffer->pos + buffer->len, 0, sizeof (buffer->pos[0]) * (length - buffer->len));
 562   }
 563
 564   buffer->len = length;
 565   return TRUE;
 566 }
 567
 568 unsigned int
 569 hb_buffer_get_length (hb_buffer_t *buffer)
 570 {
 571   return buffer->len;
 572 }
 573
 574 /* Return value valid as long as buffer not modified */
 575 hb_glyph_info_t *
 576 hb_buffer_get_glyph_infos (hb_buffer_t  *buffer,
 577                            unsigned int *length)
 578 {
 579   if (length)
 580     *length = buffer->len;
 581
 582   return (hb_glyph_info_t *) buffer->info;
 583 }
 584
 585 /* Return value valid as long as buffer not modified */
 586 hb_glyph_position_t *
 587 hb_buffer_get_glyph_positions (hb_buffer_t  *buffer,
 588                                unsigned int *length)
 589 {
 590   if (!buffer->have_positions)
 591     buffer->clear_positions ();
 592
 593   if (length)
 594     *length = buffer->len;
 595
 596   return (hb_glyph_position_t *) buffer->pos;
 597 }
 598
 599 void
 600 hb_buffer_reverse (hb_buffer_t *buffer)
 601 {
 602   buffer->reverse ();
 603 }
 604
 605 void
 606 hb_buffer_reverse_clusters (hb_buffer_t *buffer)
 607 {
 608   buffer->reverse_clusters ();
 609 }
 610
 611 #define ADD_UTF(T) \
 612         HB_STMT_START { \
 613           const T *next = (const T *) text + item_offset; \
 614           const T *end = next + item_length; \
 615           while (next < end) { \
 616             hb_codepoint_t u; \
 617             const T *old_next = next; \
 618             next = UTF_NEXT (next, end, u); \
 619             hb_buffer_add (buffer, u, 1,  old_next - (const T *) text); \
 620           } \
 621         } HB_STMT_END
 622
 623
 624 #define UTF8_COMPUTE(Char, Mask, Len) \
 625   if (Char < 128) { Len = 1; Mask = 0x7f; } \
 626   else if ((Char & 0xe0) == 0xc0) { Len = 2; Mask = 0x1f; } \
 627   else if ((Char & 0xf0) == 0xe0) { Len = 3; Mask = 0x0f; } \
 628   else if ((Char & 0xf8) == 0xf0) { Len = 4; Mask = 0x07; } \
 629   else Len = 0;
 630
 631 static inline const uint8_t *
 632 hb_utf8_next (const uint8_t *text,
 633               const uint8_t *end,
 634               hb_codepoint_t *unicode)
 635 {
 636   uint8_t c = *text;
 637   unsigned int mask, len;
 638
 639   /* TODO check for overlong sequences? */
 640
 641   UTF8_COMPUTE (c, mask, len);
 642   if (unlikely (!len || (unsigned int) (end - text) < len)) {
 643     *unicode = -1;
 644     return text + 1;
 645   } else {
 646     hb_codepoint_t result;
 647     unsigned int i;
 648     result = c & mask;
 649     for (i = 1; i < len; i++)
 650       {
 651         if (unlikely ((text[i] & 0xc0) != 0x80))
 652           {
 653             *unicode = -1;
 654             return text + 1;
 655           }
 656         result <<= 6;
 657         result |= (text[i] & 0x3f);
 658       }
 659     *unicode = result;
 660     return text + len;
 661   }
 662 }
 663
 664 void
 665 hb_buffer_add_utf8 (hb_buffer_t  *buffer,
 666                     const char   *text,
 667                     unsigned int  text_length HB_UNUSED,
 668                     unsigned int  item_offset,
 669                     unsigned int  item_length)
 670 {
 671 #define UTF_NEXT(S, E, U)       hb_utf8_next (S, E, &(U))
 672   ADD_UTF (uint8_t);
 673 #undef UTF_NEXT
 674 }
 675
 676 static inline const uint16_t *
 677 hb_utf16_next (const uint16_t *text,
 678                const uint16_t *end,
 679                hb_codepoint_t *unicode)
 680 {
 681   uint16_t c = *text++;
 682
 683   if (unlikely (c >= 0xd800 && c < 0xdc00)) {
 684     /* high surrogate */
 685     uint16_t l;
 686     if (text < end && ((l = *text), likely (l >= 0xdc00 && l < 0xe000))) {
 687       /* low surrogate */
 688       *unicode = ((hb_codepoint_t) ((c) - 0xd800) * 0x400 + (l) - 0xdc00 + 0x10000);
 689        text++;
 690     } else
 691       *unicode = -1;
 692   } else
 693     *unicode = c;
 694
 695   return text;
 696 }
 697
 698 void
 699 hb_buffer_add_utf16 (hb_buffer_t    *buffer,
 700                      const uint16_t *text,
 701                      unsigned int    text_length HB_UNUSED,
 702                      unsigned int    item_offset,
 703                      unsigned int    item_length)
 704 {
 705 #define UTF_NEXT(S, E, U)       hb_utf16_next (S, E, &(U))
 706   ADD_UTF (uint16_t);
 707 #undef UTF_NEXT
 708 }
 709
 710 void
 711 hb_buffer_add_utf32 (hb_buffer_t    *buffer,
 712                      const uint32_t *text,
 713                      unsigned int    text_length HB_UNUSED,
 714                      unsigned int    item_offset,
 715                      unsigned int    item_length)
 716 {
 717 #define UTF_NEXT(S, E, U)       ((U) = *(S), (S)+1)
 718   ADD_UTF (uint32_t);
 719 #undef UTF_NEXT
 720 }
 721
 722
 723 HB_END_DECLS