src/hb-aat-layout-common-private.hh

   1 /*
   2  * Copyright © 2017  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 #ifndef HB_AAT_LAYOUT_COMMON_PRIVATE_HH
  28 #define HB_AAT_LAYOUT_COMMON_PRIVATE_HH
  29
  30 #include "hb-aat-layout-private.hh"
  31
  32
  33 namespace AAT {
  34
  35 using namespace OT;
  36
  37
  38 /*
  39  * Binary Searching Tables
  40  */
  41
  42 struct BinSearchHeader
  43 {
  44
  45   inline bool sanitize (hb_sanitize_context_t *c) const
  46   {
  47     TRACE_SANITIZE (this);
  48     return_trace (c->check_struct (this));
  49   }
  50
  51   HBUINT16      unitSize;       /* Size of a lookup unit for this search in bytes. */
  52   HBUINT16      nUnits;         /* Number of units of the preceding size to be searched. */
  53   HBUINT16      searchRange;    /* The value of unitSize times the largest power of 2
  54                                  * that is less than or equal to the value of nUnits. */
  55   HBUINT16      entrySelector;  /* The log base 2 of the largest power of 2 less than
  56                                  * or equal to the value of nUnits. */
  57   HBUINT16      rangeShift;     /* The value of unitSize times the difference of the
  58                                  * value of nUnits minus the largest power of 2 less
  59                                  * than or equal to the value of nUnits. */
  60   public:
  61   DEFINE_SIZE_STATIC (10);
  62 };
  63
  64 template <typename Type>
  65 struct BinSearchArrayOf
  66 {
  67   inline const Type& operator [] (unsigned int i) const
  68   {
  69     if (unlikely (i >= header.nUnits)) return Null(Type);
  70     return StructAtOffset<Type> (bytesZ, i * header.unitSize);
  71   }
  72   inline Type& operator [] (unsigned int i)
  73   {
  74     return StructAtOffset<Type> (bytesZ, i * header.unitSize);
  75   }
  76   inline unsigned int get_size (void) const
  77   { return header.static_size + header.nUnits * header.unitSize; }
  78
  79   inline bool sanitize (hb_sanitize_context_t *c) const
  80   {
  81     TRACE_SANITIZE (this);
  82     if (unlikely (!sanitize_shallow (c))) return_trace (false);
  83
  84     /* Note: for structs that do not reference other structs,
  85      * we do not need to call their sanitize() as we already did
  86      * a bound check on the aggregate array size.  We just include
  87      * a small unreachable expression to make sure the structs
  88      * pointed to do have a simple sanitize(), ie. they do not
  89      * reference other structs via offsets.
  90      */
  91     (void) (false && StructAtOffset<Type> (bytesZ, 0).sanitize (c));
  92
  93     return_trace (true);
  94   }
  95   inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
  96   {
  97     TRACE_SANITIZE (this);
  98     if (unlikely (!sanitize_shallow (c))) return_trace (false);
  99     unsigned int count = header.nUnits;
 100     for (unsigned int i = 0; i < count; i++)
 101       if (unlikely (!(*this)[i].sanitize (c, base)))
 102         return_trace (false);
 103     return_trace (true);
 104   }
 105
 106   template <typename T>
 107   inline const Type *bsearch (const T &key) const
 108   {
 109     unsigned int size = header.unitSize;
 110     int min = 0, max = (int) header.nUnits - 1;
 111     while (min <= max)
 112     {
 113       int mid = (min + max) / 2;
 114       const Type *p = (const Type *) (((const char *) bytesZ) + (mid * size));
 115       int c = p->cmp (key);
 116       if (c < 0)
 117         max = mid - 1;
 118       else if (c > 0)
 119         min = mid + 1;
 120       else
 121         return p;
 122     }
 123     return nullptr;
 124   }
 125
 126   private:
 127   inline bool sanitize_shallow (hb_sanitize_context_t *c) const
 128   {
 129     TRACE_SANITIZE (this);
 130     return_trace (header.sanitize (c) &&
 131                   Type::static_size >= header.unitSize &&
 132                   c->check_array (bytesZ, header.unitSize, header.nUnits));
 133   }
 134
 135   protected:
 136   BinSearchHeader       header;
 137   HBUINT8               bytesZ[VAR];
 138   public:
 139   DEFINE_SIZE_ARRAY (10, bytesZ);
 140 };
 141
 142
 143 /*
 144  * Lookup Table
 145  */
 146
 147 template <typename T> struct Lookup;
 148
 149 template <typename T>
 150 struct LookupFormat0
 151 {
 152   friend struct Lookup<T>;
 153
 154   private:
 155   inline const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 156   {
 157     if (unlikely (glyph_id >= num_glyphs)) return nullptr;
 158     return &arrayZ[glyph_id];
 159   }
 160
 161   inline bool sanitize (hb_sanitize_context_t *c) const
 162   {
 163     TRACE_SANITIZE (this);
 164     return_trace (arrayZ.sanitize (c, c->num_glyphs));
 165   }
 166
 167   protected:
 168   HBUINT16      format;         /* Format identifier--format = 0 */
 169   UnsizedArrayOf<T>
 170                 arrayZ;         /* Array of lookup values, indexed by glyph index. */
 171   public:
 172   DEFINE_SIZE_ARRAY (2, arrayZ);
 173 };
 174
 175
 176 template <typename T>
 177 struct LookupSegmentSingle
 178 {
 179   inline int cmp (hb_codepoint_t g) const {
 180     return g < first ? -1 : g <= last ? 0 : +1 ;
 181   }
 182
 183   inline bool sanitize (hb_sanitize_context_t *c) const
 184   {
 185     TRACE_SANITIZE (this);
 186     return_trace (c->check_struct (this) && value.sanitize (c));
 187   }
 188
 189   GlyphID       last;           /* Last GlyphID in this segment */
 190   GlyphID       first;          /* First GlyphID in this segment */
 191   T             value;          /* The lookup value (only one) */
 192   public:
 193   DEFINE_SIZE_STATIC (4 + T::static_size);
 194 };
 195
 196 template <typename T>
 197 struct LookupFormat2
 198 {
 199   friend struct Lookup<T>;
 200
 201   private:
 202   inline const T* get_value (hb_codepoint_t glyph_id) const
 203   {
 204     const LookupSegmentSingle<T> *v = segments.bsearch (glyph_id);
 205     return v ? &v->value : nullptr;
 206   }
 207
 208   inline bool sanitize (hb_sanitize_context_t *c) const
 209   {
 210     TRACE_SANITIZE (this);
 211     return_trace (segments.sanitize (c));
 212   }
 213
 214   protected:
 215   HBUINT16      format;         /* Format identifier--format = 2 */
 216   BinSearchArrayOf<LookupSegmentSingle<T> >
 217                 segments;       /* The actual segments. These must already be sorted,
 218                                  * according to the first word in each one (the last
 219                                  * glyph in each segment). */
 220   public:
 221   DEFINE_SIZE_ARRAY (8, segments);
 222 };
 223
 224 template <typename T>
 225 struct LookupSegmentArray
 226 {
 227   inline const T* get_value (hb_codepoint_t glyph_id, const void *base) const
 228   {
 229     return first <= glyph_id && glyph_id <= last ? &(base+valuesZ)[glyph_id - first] : nullptr;
 230   }
 231
 232   inline int cmp (hb_codepoint_t g) const {
 233     return g < first ? -1 : g <= last ? 0 : +1 ;
 234   }
 235
 236   inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
 237   {
 238     TRACE_SANITIZE (this);
 239     return_trace (c->check_struct (this) &&
 240                   first <= last &&
 241                   valuesZ.sanitize (c, base, last - first + 1));
 242   }
 243
 244   GlyphID       last;           /* Last GlyphID in this segment */
 245   GlyphID       first;          /* First GlyphID in this segment */
 246   OffsetTo<UnsizedArrayOf<T> >
 247                 valuesZ;        /* A 16-bit offset from the start of
 248                                  * the table to the data. */
 249   public:
 250   DEFINE_SIZE_STATIC (6);
 251 };
 252
 253 template <typename T>
 254 struct LookupFormat4
 255 {
 256   friend struct Lookup<T>;
 257
 258   private:
 259   inline const T* get_value (hb_codepoint_t glyph_id) const
 260   {
 261     const LookupSegmentArray<T> *v = segments.bsearch (glyph_id);
 262     return v ? v->get_value (glyph_id, this) : nullptr;
 263   }
 264
 265   inline bool sanitize (hb_sanitize_context_t *c) const
 266   {
 267     TRACE_SANITIZE (this);
 268     return_trace (segments.sanitize (c, this));
 269   }
 270
 271   protected:
 272   HBUINT16      format;         /* Format identifier--format = 2 */
 273   BinSearchArrayOf<LookupSegmentArray<T> >
 274                 segments;       /* The actual segments. These must already be sorted,
 275                                  * according to the first word in each one (the last
 276                                  * glyph in each segment). */
 277   public:
 278   DEFINE_SIZE_ARRAY (8, segments);
 279 };
 280
 281 template <typename T>
 282 struct LookupSingle
 283 {
 284   inline int cmp (hb_codepoint_t g) const { return glyph.cmp (g); }
 285
 286   inline bool sanitize (hb_sanitize_context_t *c) const
 287   {
 288     TRACE_SANITIZE (this);
 289     return_trace (c->check_struct (this) && value.sanitize (c));
 290   }
 291
 292   GlyphID       glyph;          /* Last GlyphID */
 293   T             value;          /* The lookup value (only one) */
 294   public:
 295   DEFINE_SIZE_STATIC (4 + T::static_size);
 296 };
 297
 298 template <typename T>
 299 struct LookupFormat6
 300 {
 301   friend struct Lookup<T>;
 302
 303   private:
 304   inline const T* get_value (hb_codepoint_t glyph_id) const
 305   {
 306     const LookupSingle<T> *v = entries.bsearch (glyph_id);
 307     return v ? &v->value : nullptr;
 308   }
 309
 310   inline bool sanitize (hb_sanitize_context_t *c) const
 311   {
 312     TRACE_SANITIZE (this);
 313     return_trace (entries.sanitize (c));
 314   }
 315
 316   protected:
 317   HBUINT16      format;         /* Format identifier--format = 6 */
 318   BinSearchArrayOf<LookupSingle<T> >
 319                 entries;        /* The actual entries, sorted by glyph index. */
 320   public:
 321   DEFINE_SIZE_ARRAY (8, entries);
 322 };
 323
 324 template <typename T>
 325 struct LookupFormat8
 326 {
 327   friend struct Lookup<T>;
 328
 329   private:
 330   inline const T* get_value (hb_codepoint_t glyph_id) const
 331   {
 332     return firstGlyph <= glyph_id && glyph_id - firstGlyph < glyphCount ? &valueArrayZ[glyph_id - firstGlyph] : nullptr;
 333   }
 334
 335   inline bool sanitize (hb_sanitize_context_t *c) const
 336   {
 337     TRACE_SANITIZE (this);
 338     return_trace (c->check_struct (this) && valueArrayZ.sanitize (c, glyphCount));
 339   }
 340
 341   protected:
 342   HBUINT16      format;         /* Format identifier--format = 6 */
 343   GlyphID       firstGlyph;     /* First glyph index included in the trimmed array. */
 344   HBUINT16      glyphCount;     /* Total number of glyphs (equivalent to the last
 345                                  * glyph minus the value of firstGlyph plus 1). */
 346   UnsizedArrayOf<T>
 347                 valueArrayZ;    /* The lookup values (indexed by the glyph index
 348                                  * minus the value of firstGlyph). */
 349   public:
 350   DEFINE_SIZE_ARRAY (6, valueArrayZ);
 351 };
 352
 353 template <typename T>
 354 struct Lookup
 355 {
 356   inline const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 357   {
 358     switch (u.format) {
 359     case 0: return u.format0.get_value (glyph_id, num_glyphs);
 360     case 2: return u.format2.get_value (glyph_id);
 361     case 4: return u.format4.get_value (glyph_id);
 362     case 6: return u.format6.get_value (glyph_id);
 363     case 8: return u.format8.get_value (glyph_id);
 364     default:return nullptr;
 365     }
 366   }
 367
 368   inline bool sanitize (hb_sanitize_context_t *c) const
 369   {
 370     TRACE_SANITIZE (this);
 371     if (!u.format.sanitize (c)) return_trace (false);
 372     switch (u.format) {
 373     case 0: return_trace (u.format0.sanitize (c));
 374     case 2: return_trace (u.format2.sanitize (c));
 375     case 4: return_trace (u.format4.sanitize (c));
 376     case 6: return_trace (u.format6.sanitize (c));
 377     case 8: return_trace (u.format8.sanitize (c));
 378     default:return_trace (true);
 379     }
 380   }
 381
 382   protected:
 383   union {
 384   HBUINT16              format;         /* Format identifier */
 385   LookupFormat0<T>      format0;
 386   LookupFormat2<T>      format2;
 387   LookupFormat4<T>      format4;
 388   LookupFormat6<T>      format6;
 389   LookupFormat8<T>      format8;
 390   } u;
 391   public:
 392   DEFINE_SIZE_UNION (2, format);
 393 };
 394
 395
 396 /*
 397  * Extended State Table
 398  */
 399
 400 template <typename T>
 401 struct Entry
 402 {
 403   inline bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
 404   {
 405     TRACE_SANITIZE (this);
 406     /* Note, we don't recurse-sanitize data because we don't access it.
 407      * That said, in our DEFINE_SIZE_STATIC we access T::static_size,
 408      * which ensures that data has a simple sanitize(). To be determined
 409      * if I need to remove that as well. */
 410     return_trace (c->check_struct (this));
 411   }
 412
 413   public:
 414   HBUINT16      newState;       /* Byte offset from beginning of state table
 415                                  * to the new state. Really?!?! Or just state
 416                                  * number?  The latter in morx for sure. */
 417   HBUINT16      flags;          /* Table specific. */
 418   T             data;           /* Optional offsets to per-glyph tables. */
 419   public:
 420   DEFINE_SIZE_STATIC (4 + T::static_size);
 421 };
 422
 423 template <>
 424 struct Entry<void>
 425 {
 426   inline bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
 427   {
 428     TRACE_SANITIZE (this);
 429     return_trace (c->check_struct (this));
 430   }
 431
 432   public:
 433   HBUINT16      newState;       /* Byte offset from beginning of state table to the new state. */
 434   HBUINT16      flags;          /* Table specific. */
 435   public:
 436   DEFINE_SIZE_STATIC (4);
 437 };
 438
 439 template <typename Extra>
 440 struct StateTable
 441 {
 442   inline unsigned int get_class (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 443   {
 444     const HBUINT16 *v = (this+classTable).get_value (glyph_id, num_glyphs);
 445     return v ? *v : 1;
 446   }
 447
 448   inline const Entry<Extra> *get_entries () const
 449   {
 450     return (this+entryTable).arrayZ;
 451   }
 452
 453   inline const Entry<Extra> *get_entryZ (unsigned int state, unsigned int klass) const
 454   {
 455     if (unlikely (klass >= nClasses)) return nullptr;
 456
 457     const HBUINT16 *states = (this+stateArrayTable).arrayZ;
 458     const Entry<Extra> *entries = (this+entryTable).arrayZ;
 459
 460     unsigned int entry = states[state * nClasses + klass];
 461
 462     return &entries[entry];
 463   }
 464
 465   inline bool sanitize (hb_sanitize_context_t *c,
 466                         unsigned int *num_entries_out = nullptr) const
 467   {
 468     TRACE_SANITIZE (this);
 469     if (unlikely (!(c->check_struct (this) &&
 470                     classTable.sanitize (c, this)))) return_trace (false);
 471
 472     const HBUINT16 *states = (this+stateArrayTable).arrayZ;
 473     const Entry<Extra> *entries = (this+entryTable).arrayZ;
 474
 475     unsigned int num_states = 1;
 476     unsigned int num_entries = 0;
 477
 478     unsigned int state = 0;
 479     unsigned int entry = 0;
 480     while (state < num_states)
 481     {
 482       if (unlikely (!c->check_array (states,
 483                                      states[0].static_size * nClasses,
 484                                      num_states)))
 485         return_trace (false);
 486       { /* Sweep new states. */
 487         const HBUINT16 *stop = &states[num_states * nClasses];
 488         for (const HBUINT16 *p = &states[state * nClasses]; p < stop; p++)
 489           num_entries = MAX<unsigned int> (num_entries, *p + 1);
 490         state = num_states;
 491       }
 492
 493       if (unlikely (!c->check_array (entries,
 494                                      entries[0].static_size,
 495                                      num_entries)))
 496         return_trace (false);
 497       { /* Sweep new entries. */
 498         const Entry<Extra> *stop = &entries[num_entries];
 499         for (const Entry<Extra> *p = &entries[entry]; p < stop; p++)
 500           num_states = MAX<unsigned int> (num_states, p->newState + 1);
 501         entry = num_entries;
 502       }
 503     }
 504
 505     if (num_entries_out)
 506       *num_entries_out = num_entries;
 507
 508     return_trace (true);
 509   }
 510
 511   protected:
 512   HBUINT32      nClasses;       /* Number of classes, which is the number of indices
 513                                  * in a single line in the state array. */
 514   LOffsetTo<Lookup<HBUINT16> >
 515                 classTable;     /* Offset to the class table. */
 516   LOffsetTo<UnsizedArrayOf<HBUINT16> >
 517                 stateArrayTable;/* Offset to the state array. */
 518   LOffsetTo<UnsizedArrayOf<Entry<Extra> > >
 519                 entryTable;     /* Offset to the entry array. */
 520
 521   public:
 522   DEFINE_SIZE_STATIC (16);
 523 };
 524
 525 template <typename EntryData>
 526 struct StateTableDriver
 527 {
 528   inline StateTableDriver (const StateTable<EntryData> &machine_,
 529                            hb_buffer_t *buffer_,
 530                            hb_face_t *face_) :
 531               machine (machine_),
 532               buffer (buffer_),
 533               num_glyphs (face_->get_num_glyphs ()) {}
 534
 535   template <typename context_t>
 536   inline void drive (context_t *c)
 537   {
 538     hb_glyph_info_t *info = buffer->info;
 539
 540     if (!c->in_place)
 541       buffer->clear_output ();
 542
 543     unsigned int state = 0;
 544     bool last_was_dont_advance = false;
 545     for (buffer->idx = 0;;)
 546     {
 547       unsigned int klass = buffer->idx < buffer->len ?
 548                            machine.get_class (info[buffer->idx].codepoint, num_glyphs) :
 549                            0 /* End of text */;
 550       const Entry<EntryData> *entry = machine.get_entryZ (state, klass);
 551       if (unlikely (!entry))
 552         break;
 553
 554       /* Unsafe-to-break before this if not in state 0, as things might
 555        * go differently if we start from state 0 here. */
 556       if (state && buffer->idx)
 557       {
 558         /* If there's no action and we're just epsilon-transitioning to state 0,
 559          * safe to break. */
 560         if (c->is_actionable (this, entry) ||
 561             !(entry->newState == 0 && entry->flags == context_t::DontAdvance))
 562           buffer->unsafe_to_break (buffer->idx - 1, buffer->idx + 1);
 563       }
 564
 565       /* Unsafe-to-break if end-of-text would kick in here. */
 566       if (buffer->idx + 2 <= buffer->len)
 567       {
 568         const Entry<EntryData> *end_entry = machine.get_entryZ (state, 0);
 569         if (c->is_actionable (this, end_entry))
 570           buffer->unsafe_to_break (buffer->idx, buffer->idx + 2);
 571       }
 572
 573       if (unlikely (!c->transition (this, entry)))
 574         break;
 575
 576       last_was_dont_advance = (entry->flags & context_t::DontAdvance) && buffer->max_ops-- > 0;
 577
 578       state = entry->newState;
 579
 580       if (buffer->idx == buffer->len)
 581         break;
 582
 583       if (!last_was_dont_advance)
 584         buffer->next_glyph ();
 585     }
 586
 587     if (!c->in_place)
 588     {
 589       for (; buffer->idx < buffer->len;)
 590         buffer->next_glyph ();
 591       buffer->swap_buffers ();
 592     }
 593   }
 594
 595   public:
 596   const StateTable<EntryData> &machine;
 597   hb_buffer_t *buffer;
 598   unsigned int num_glyphs;
 599 };
 600
 601
 602
 603 struct hb_aat_apply_context_t :
 604        hb_dispatch_context_t<hb_aat_apply_context_t, bool, HB_DEBUG_APPLY>
 605 {
 606   inline const char *get_name (void) { return "APPLY"; }
 607   template <typename T>
 608   inline return_t dispatch (const T &obj) { return obj.apply (this); }
 609   static return_t default_return_value (void) { return false; }
 610   bool stop_sublookup_iteration (return_t r) const { return r; }
 611
 612   hb_font_t *font;
 613   hb_face_t *face;
 614   hb_buffer_t *buffer;
 615   hb_sanitize_context_t sanitizer;
 616
 617   /* Unused. For debug tracing only. */
 618   unsigned int lookup_index;
 619   unsigned int debug_depth;
 620
 621   inline hb_aat_apply_context_t (hb_font_t *font_,
 622                                  hb_buffer_t *buffer_,
 623                                  hb_blob_t *table) :
 624                 font (font_), face (font->face), buffer (buffer_),
 625                 sanitizer (), lookup_index (0), debug_depth (0)
 626   {
 627     sanitizer.init (table);
 628     sanitizer.num_glyphs = face->get_num_glyphs ();
 629     sanitizer.start_processing ();
 630   }
 631
 632   inline void set_lookup_index (unsigned int i) { lookup_index = i; }
 633
 634   inline ~hb_aat_apply_context_t (void)
 635   {
 636     sanitizer.end_processing ();
 637   }
 638 };
 639
 640
 641 } /* namespace AAT */
 642
 643
 644 #endif /* HB_AAT_LAYOUT_COMMON_PRIVATE_HH */