src/hb-buffer.cc

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