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