gfx/harfbuzz/src/hb-aat-layout-common.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_HH
  28 #define HB_AAT_LAYOUT_COMMON_HH
  29
  30 #include "hb-aat-layout.hh"
  31 #include "hb-aat-map.hh"
  32 #include "hb-open-type.hh"
  33
  34 namespace OT {
  35 struct GDEF;
  36 };
  37
  38 namespace AAT {
  39
  40 using namespace OT;
  41
  42
  43 struct ankr;
  44
  45 struct hb_aat_apply_context_t :
  46        hb_dispatch_context_t<hb_aat_apply_context_t, bool, HB_DEBUG_APPLY>
  47 {
  48   const char *get_name () { return "APPLY"; }
  49   template <typename T>
  50   return_t dispatch (const T &obj) { return obj.apply (this); }
  51   static return_t default_return_value () { return false; }
  52   bool stop_sublookup_iteration (return_t r) const { return r; }
  53
  54   const hb_ot_shape_plan_t *plan;
  55   hb_font_t *font;
  56   hb_face_t *face;
  57   hb_buffer_t *buffer;
  58   hb_sanitize_context_t sanitizer;
  59   const ankr *ankr_table;
  60   const OT::GDEF *gdef_table;
  61   const hb_sorted_vector_t<hb_aat_map_t::range_flags_t> *range_flags = nullptr;
  62   hb_mask_t subtable_flags = 0;
  63
  64   /* Unused. For debug tracing only. */
  65   unsigned int lookup_index;
  66
  67   HB_INTERNAL hb_aat_apply_context_t (const hb_ot_shape_plan_t *plan_,
  68                                       hb_font_t *font_,
  69                                       hb_buffer_t *buffer_,
  70                                       hb_blob_t *blob = const_cast<hb_blob_t *> (&Null (hb_blob_t)));
  71
  72   HB_INTERNAL ~hb_aat_apply_context_t ();
  73
  74   HB_INTERNAL void set_ankr_table (const AAT::ankr *ankr_table_);
  75
  76   void set_lookup_index (unsigned int i) { lookup_index = i; }
  77 };
  78
  79
  80 /*
  81  * Lookup Table
  82  */
  83
  84 template <typename T> struct Lookup;
  85
  86 template <typename T>
  87 struct LookupFormat0
  88 {
  89   friend struct Lookup<T>;
  90
  91   private:
  92   const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
  93   {
  94     if (unlikely (glyph_id >= num_glyphs)) return nullptr;
  95     return &arrayZ[glyph_id];
  96   }
  97
  98   bool sanitize (hb_sanitize_context_t *c) const
  99   {
 100     TRACE_SANITIZE (this);
 101     return_trace (arrayZ.sanitize (c, c->get_num_glyphs ()));
 102   }
 103   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 104   {
 105     TRACE_SANITIZE (this);
 106     return_trace (arrayZ.sanitize (c, c->get_num_glyphs (), base));
 107   }
 108
 109   protected:
 110   HBUINT16      format;         /* Format identifier--format = 0 */
 111   UnsizedArrayOf<T>
 112                 arrayZ;         /* Array of lookup values, indexed by glyph index. */
 113   public:
 114   DEFINE_SIZE_UNBOUNDED (2);
 115 };
 116
 117
 118 template <typename T>
 119 struct LookupSegmentSingle
 120 {
 121   static constexpr unsigned TerminationWordCount = 2u;
 122
 123   int cmp (hb_codepoint_t g) const
 124   { return g < first ? -1 : g <= last ? 0 : +1 ; }
 125
 126   bool sanitize (hb_sanitize_context_t *c) const
 127   {
 128     TRACE_SANITIZE (this);
 129     return_trace (c->check_struct (this) && value.sanitize (c));
 130   }
 131   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 132   {
 133     TRACE_SANITIZE (this);
 134     return_trace (c->check_struct (this) && value.sanitize (c, base));
 135   }
 136
 137   HBGlyphID16   last;           /* Last GlyphID in this segment */
 138   HBGlyphID16   first;          /* First GlyphID in this segment */
 139   T             value;          /* The lookup value (only one) */
 140   public:
 141   DEFINE_SIZE_STATIC (4 + T::static_size);
 142 };
 143
 144 template <typename T>
 145 struct LookupFormat2
 146 {
 147   friend struct Lookup<T>;
 148
 149   private:
 150   const T* get_value (hb_codepoint_t glyph_id) const
 151   {
 152     const LookupSegmentSingle<T> *v = segments.bsearch (glyph_id);
 153     return v ? &v->value : nullptr;
 154   }
 155
 156   bool sanitize (hb_sanitize_context_t *c) const
 157   {
 158     TRACE_SANITIZE (this);
 159     return_trace (segments.sanitize (c));
 160   }
 161   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 162   {
 163     TRACE_SANITIZE (this);
 164     return_trace (segments.sanitize (c, base));
 165   }
 166
 167   protected:
 168   HBUINT16      format;         /* Format identifier--format = 2 */
 169   VarSizedBinSearchArrayOf<LookupSegmentSingle<T>>
 170                 segments;       /* The actual segments. These must already be sorted,
 171                                  * according to the first word in each one (the last
 172                                  * glyph in each segment). */
 173   public:
 174   DEFINE_SIZE_ARRAY (8, segments);
 175 };
 176
 177 template <typename T>
 178 struct LookupSegmentArray
 179 {
 180   static constexpr unsigned TerminationWordCount = 2u;
 181
 182   const T* get_value (hb_codepoint_t glyph_id, const void *base) const
 183   {
 184     return first <= glyph_id && glyph_id <= last ? &(base+valuesZ)[glyph_id - first] : nullptr;
 185   }
 186
 187   int cmp (hb_codepoint_t g) const
 188   { return g < first ? -1 : g <= last ? 0 : +1; }
 189
 190   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 191   {
 192     TRACE_SANITIZE (this);
 193     return_trace (c->check_struct (this) &&
 194                   hb_barrier () &&
 195                   first <= last &&
 196                   valuesZ.sanitize (c, base, last - first + 1));
 197   }
 198   template <typename ...Ts>
 199   bool sanitize (hb_sanitize_context_t *c, const void *base, Ts&&... ds) const
 200   {
 201     TRACE_SANITIZE (this);
 202     return_trace (c->check_struct (this) &&
 203                   hb_barrier () &&
 204                   first <= last &&
 205                   valuesZ.sanitize (c, base, last - first + 1, std::forward<Ts> (ds)...));
 206   }
 207
 208   HBGlyphID16   last;           /* Last GlyphID in this segment */
 209   HBGlyphID16   first;          /* First GlyphID in this segment */
 210   NNOffset16To<UnsizedArrayOf<T>>
 211                 valuesZ;        /* A 16-bit offset from the start of
 212                                  * the table to the data. */
 213   public:
 214   DEFINE_SIZE_STATIC (6);
 215 };
 216
 217 template <typename T>
 218 struct LookupFormat4
 219 {
 220   friend struct Lookup<T>;
 221
 222   private:
 223   const T* get_value (hb_codepoint_t glyph_id) const
 224   {
 225     const LookupSegmentArray<T> *v = segments.bsearch (glyph_id);
 226     return v ? v->get_value (glyph_id, this) : nullptr;
 227   }
 228
 229   bool sanitize (hb_sanitize_context_t *c) const
 230   {
 231     TRACE_SANITIZE (this);
 232     return_trace (segments.sanitize (c, this));
 233   }
 234   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 235   {
 236     TRACE_SANITIZE (this);
 237     return_trace (segments.sanitize (c, this, base));
 238   }
 239
 240   protected:
 241   HBUINT16      format;         /* Format identifier--format = 4 */
 242   VarSizedBinSearchArrayOf<LookupSegmentArray<T>>
 243                 segments;       /* The actual segments. These must already be sorted,
 244                                  * according to the first word in each one (the last
 245                                  * glyph in each segment). */
 246   public:
 247   DEFINE_SIZE_ARRAY (8, segments);
 248 };
 249
 250 template <typename T>
 251 struct LookupSingle
 252 {
 253   static constexpr unsigned TerminationWordCount = 1u;
 254
 255   int cmp (hb_codepoint_t g) const { return glyph.cmp (g); }
 256
 257   bool sanitize (hb_sanitize_context_t *c) const
 258   {
 259     TRACE_SANITIZE (this);
 260     return_trace (c->check_struct (this) && value.sanitize (c));
 261   }
 262   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 263   {
 264     TRACE_SANITIZE (this);
 265     return_trace (c->check_struct (this) && value.sanitize (c, base));
 266   }
 267
 268   HBGlyphID16   glyph;          /* Last GlyphID */
 269   T             value;          /* The lookup value (only one) */
 270   public:
 271   DEFINE_SIZE_STATIC (2 + T::static_size);
 272 };
 273
 274 template <typename T>
 275 struct LookupFormat6
 276 {
 277   friend struct Lookup<T>;
 278
 279   private:
 280   const T* get_value (hb_codepoint_t glyph_id) const
 281   {
 282     const LookupSingle<T> *v = entries.bsearch (glyph_id);
 283     return v ? &v->value : nullptr;
 284   }
 285
 286   bool sanitize (hb_sanitize_context_t *c) const
 287   {
 288     TRACE_SANITIZE (this);
 289     return_trace (entries.sanitize (c));
 290   }
 291   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 292   {
 293     TRACE_SANITIZE (this);
 294     return_trace (entries.sanitize (c, base));
 295   }
 296
 297   protected:
 298   HBUINT16      format;         /* Format identifier--format = 6 */
 299   VarSizedBinSearchArrayOf<LookupSingle<T>>
 300                 entries;        /* The actual entries, sorted by glyph index. */
 301   public:
 302   DEFINE_SIZE_ARRAY (8, entries);
 303 };
 304
 305 template <typename T>
 306 struct LookupFormat8
 307 {
 308   friend struct Lookup<T>;
 309
 310   private:
 311   const T* get_value (hb_codepoint_t glyph_id) const
 312   {
 313     return firstGlyph <= glyph_id && glyph_id - firstGlyph < glyphCount ?
 314            &valueArrayZ[glyph_id - firstGlyph] : nullptr;
 315   }
 316
 317   bool sanitize (hb_sanitize_context_t *c) const
 318   {
 319     TRACE_SANITIZE (this);
 320     return_trace (c->check_struct (this) && valueArrayZ.sanitize (c, glyphCount));
 321   }
 322   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 323   {
 324     TRACE_SANITIZE (this);
 325     return_trace (c->check_struct (this) && valueArrayZ.sanitize (c, glyphCount, base));
 326   }
 327
 328   protected:
 329   HBUINT16      format;         /* Format identifier--format = 8 */
 330   HBGlyphID16   firstGlyph;     /* First glyph index included in the trimmed array. */
 331   HBUINT16      glyphCount;     /* Total number of glyphs (equivalent to the last
 332                                  * glyph minus the value of firstGlyph plus 1). */
 333   UnsizedArrayOf<T>
 334                 valueArrayZ;    /* The lookup values (indexed by the glyph index
 335                                  * minus the value of firstGlyph). */
 336   public:
 337   DEFINE_SIZE_ARRAY (6, valueArrayZ);
 338 };
 339
 340 template <typename T>
 341 struct LookupFormat10
 342 {
 343   friend struct Lookup<T>;
 344
 345   private:
 346   const typename T::type get_value_or_null (hb_codepoint_t glyph_id) const
 347   {
 348     if (!(firstGlyph <= glyph_id && glyph_id - firstGlyph < glyphCount))
 349       return Null (T);
 350
 351     const HBUINT8 *p = &valueArrayZ[(glyph_id - firstGlyph) * valueSize];
 352
 353     unsigned int v = 0;
 354     unsigned int count = valueSize;
 355     for (unsigned int i = 0; i < count; i++)
 356       v = (v << 8) | *p++;
 357
 358     return v;
 359   }
 360
 361   bool sanitize (hb_sanitize_context_t *c) const
 362   {
 363     TRACE_SANITIZE (this);
 364     return_trace (c->check_struct (this) &&
 365                   hb_barrier () &&
 366                   valueSize <= 4 &&
 367                   valueArrayZ.sanitize (c, glyphCount * valueSize));
 368   }
 369
 370   protected:
 371   HBUINT16      format;         /* Format identifier--format = 8 */
 372   HBUINT16      valueSize;      /* Byte size of each value. */
 373   HBGlyphID16   firstGlyph;     /* First glyph index included in the trimmed array. */
 374   HBUINT16      glyphCount;     /* Total number of glyphs (equivalent to the last
 375                                  * glyph minus the value of firstGlyph plus 1). */
 376   UnsizedArrayOf<HBUINT8>
 377                 valueArrayZ;    /* The lookup values (indexed by the glyph index
 378                                  * minus the value of firstGlyph). */
 379   public:
 380   DEFINE_SIZE_ARRAY (8, valueArrayZ);
 381 };
 382
 383 template <typename T>
 384 struct Lookup
 385 {
 386   const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 387   {
 388     switch (u.format) {
 389     case 0: return u.format0.get_value (glyph_id, num_glyphs);
 390     case 2: return u.format2.get_value (glyph_id);
 391     case 4: return u.format4.get_value (glyph_id);
 392     case 6: return u.format6.get_value (glyph_id);
 393     case 8: return u.format8.get_value (glyph_id);
 394     default:return nullptr;
 395     }
 396   }
 397
 398   const typename T::type get_value_or_null (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 399   {
 400     switch (u.format) {
 401       /* Format 10 cannot return a pointer. */
 402       case 10: return u.format10.get_value_or_null (glyph_id);
 403       default:
 404       const T *v = get_value (glyph_id, num_glyphs);
 405       return v ? *v : Null (T);
 406     }
 407   }
 408
 409   typename T::type get_class (hb_codepoint_t glyph_id,
 410                               unsigned int num_glyphs,
 411                               unsigned int outOfRange) const
 412   {
 413     const T *v = get_value (glyph_id, num_glyphs);
 414     return v ? *v : outOfRange;
 415   }
 416
 417   bool sanitize (hb_sanitize_context_t *c) const
 418   {
 419     TRACE_SANITIZE (this);
 420     if (!u.format.sanitize (c)) return_trace (false);
 421     hb_barrier ();
 422     switch (u.format) {
 423     case 0: return_trace (u.format0.sanitize (c));
 424     case 2: return_trace (u.format2.sanitize (c));
 425     case 4: return_trace (u.format4.sanitize (c));
 426     case 6: return_trace (u.format6.sanitize (c));
 427     case 8: return_trace (u.format8.sanitize (c));
 428     case 10: return_trace (u.format10.sanitize (c));
 429     default:return_trace (true);
 430     }
 431   }
 432   bool sanitize (hb_sanitize_context_t *c, const void *base) const
 433   {
 434     TRACE_SANITIZE (this);
 435     if (!u.format.sanitize (c)) return_trace (false);
 436     hb_barrier ();
 437     switch (u.format) {
 438     case 0: return_trace (u.format0.sanitize (c, base));
 439     case 2: return_trace (u.format2.sanitize (c, base));
 440     case 4: return_trace (u.format4.sanitize (c, base));
 441     case 6: return_trace (u.format6.sanitize (c, base));
 442     case 8: return_trace (u.format8.sanitize (c, base));
 443     case 10: return_trace (false); /* We don't support format10 here currently. */
 444     default:return_trace (true);
 445     }
 446   }
 447
 448   protected:
 449   union {
 450   HBUINT16              format;         /* Format identifier */
 451   LookupFormat0<T>      format0;
 452   LookupFormat2<T>      format2;
 453   LookupFormat4<T>      format4;
 454   LookupFormat6<T>      format6;
 455   LookupFormat8<T>      format8;
 456   LookupFormat10<T>     format10;
 457   } u;
 458   public:
 459   DEFINE_SIZE_UNION (2, format);
 460 };
 461 DECLARE_NULL_NAMESPACE_BYTES_TEMPLATE1 (AAT, Lookup, 2);
 462
 463 enum { DELETED_GLYPH = 0xFFFF };
 464
 465 /*
 466  * (Extended) State Table
 467  */
 468
 469 template <typename T>
 470 struct Entry
 471 {
 472   // This does seem like it's ever called.
 473   bool sanitize (hb_sanitize_context_t *c) const
 474   {
 475     TRACE_SANITIZE (this);
 476     /* Note, we don't recurse-sanitize data because we don't access it.
 477      * That said, in our DEFINE_SIZE_STATIC we access T::static_size,
 478      * which ensures that data has a simple sanitize(). To be determined
 479      * if I need to remove that as well.
 480      *
 481      * HOWEVER! Because we are a template, our DEFINE_SIZE_STATIC
 482      * assertion wouldn't be checked, hence the line below. */
 483     static_assert (T::static_size, "");
 484
 485     return_trace (c->check_struct (this));
 486   }
 487
 488   public:
 489   HBUINT16      newState;       /* Byte offset from beginning of state table
 490                                  * to the new state. Really?!?! Or just state
 491                                  * number?  The latter in morx for sure. */
 492   HBUINT16      flags;          /* Table specific. */
 493   T             data;           /* Optional offsets to per-glyph tables. */
 494   public:
 495   DEFINE_SIZE_STATIC (4 + T::static_size);
 496 };
 497
 498 template <>
 499 struct Entry<void>
 500 {
 501   // This does seem like it's ever called.
 502   bool sanitize (hb_sanitize_context_t *c) const
 503   {
 504     TRACE_SANITIZE (this);
 505     return_trace (c->check_struct (this));
 506   }
 507
 508   public:
 509   HBUINT16      newState;       /* Byte offset from beginning of state table to the new state. */
 510   HBUINT16      flags;          /* Table specific. */
 511   public:
 512   DEFINE_SIZE_STATIC (4);
 513 };
 514
 515 template <typename Types, typename Extra>
 516 struct StateTable
 517 {
 518   typedef typename Types::HBUINT HBUINT;
 519   typedef typename Types::HBUSHORT HBUSHORT;
 520   typedef typename Types::ClassTypeNarrow ClassType;
 521
 522   enum State
 523   {
 524     STATE_START_OF_TEXT = 0,
 525     STATE_START_OF_LINE = 1,
 526   };
 527   enum Class
 528   {
 529     CLASS_END_OF_TEXT = 0,
 530     CLASS_OUT_OF_BOUNDS = 1,
 531     CLASS_DELETED_GLYPH = 2,
 532     CLASS_END_OF_LINE = 3,
 533   };
 534
 535   int new_state (unsigned int newState) const
 536   { return Types::extended ? newState : ((int) newState - (int) stateArrayTable) / (int) nClasses; }
 537
 538   unsigned int get_class (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
 539   {
 540     if (unlikely (glyph_id == DELETED_GLYPH)) return CLASS_DELETED_GLYPH;
 541     return (this+classTable).get_class (glyph_id, num_glyphs, 1);
 542   }
 543
 544   const Entry<Extra> *get_entries () const
 545   { return (this+entryTable).arrayZ; }
 546
 547   const Entry<Extra> &get_entry (int state, unsigned int klass) const
 548   {
 549     if (unlikely (klass >= nClasses))
 550       klass = StateTable::CLASS_OUT_OF_BOUNDS;
 551
 552     const HBUSHORT *states = (this+stateArrayTable).arrayZ;
 553     const Entry<Extra> *entries = (this+entryTable).arrayZ;
 554
 555     unsigned int entry = states[state * nClasses + klass];
 556     DEBUG_MSG (APPLY, nullptr, "e%u", entry);
 557
 558     return entries[entry];
 559   }
 560
 561   bool sanitize (hb_sanitize_context_t *c,
 562                  unsigned int *num_entries_out = nullptr) const
 563   {
 564     TRACE_SANITIZE (this);
 565     if (unlikely (!(c->check_struct (this) &&
 566                     hb_barrier () &&
 567                     nClasses >= 4 /* Ensure pre-defined classes fit.  */ &&
 568                     classTable.sanitize (c, this)))) return_trace (false);
 569
 570     const HBUSHORT *states = (this+stateArrayTable).arrayZ;
 571     const Entry<Extra> *entries = (this+entryTable).arrayZ;
 572
 573     unsigned int num_classes = nClasses;
 574     if (unlikely (hb_unsigned_mul_overflows (num_classes, states[0].static_size)))
 575       return_trace (false);
 576     unsigned int row_stride = num_classes * states[0].static_size;
 577
 578     /* Apple 'kern' table has this peculiarity:
 579      *
 580      * "Because the stateTableOffset in the state table header is (strictly
 581      * speaking) redundant, some 'kern' tables use it to record an initial
 582      * state where that should not be StartOfText. To determine if this is
 583      * done, calculate what the stateTableOffset should be. If it's different
 584      * from the actual stateTableOffset, use it as the initial state."
 585      *
 586      * We implement this by calling the initial state zero, but allow *negative*
 587      * states if the start state indeed was not the first state.  Since the code
 588      * is shared, this will also apply to 'mort' table.  The 'kerx' / 'morx'
 589      * tables are not affected since those address states by index, not offset.
 590      */
 591
 592     int min_state = 0;
 593     int max_state = 0;
 594     unsigned int num_entries = 0;
 595
 596     int state_pos = 0;
 597     int state_neg = 0;
 598     unsigned int entry = 0;
 599     while (min_state < state_neg || state_pos <= max_state)
 600     {
 601       if (min_state < state_neg)
 602       {
 603         /* Negative states. */
 604         if (unlikely (hb_unsigned_mul_overflows (min_state, num_classes)))
 605           return_trace (false);
 606         if (unlikely (!c->check_range (&states[min_state * num_classes],
 607                                        -min_state,
 608                                        row_stride)))
 609           return_trace (false);
 610         if ((c->max_ops -= state_neg - min_state) <= 0)
 611           return_trace (false);
 612         { /* Sweep new states. */
 613           const HBUSHORT *stop = &states[min_state * num_classes];
 614           if (unlikely (stop > states))
 615             return_trace (false);
 616           for (const HBUSHORT *p = states; stop < p; p--)
 617             num_entries = hb_max (num_entries, *(p - 1) + 1u);
 618           state_neg = min_state;
 619         }
 620       }
 621
 622       if (state_pos <= max_state)
 623       {
 624         /* Positive states. */
 625         if (unlikely (!c->check_range (states,
 626                                        max_state + 1,
 627                                        row_stride)))
 628           return_trace (false);
 629         if ((c->max_ops -= max_state - state_pos + 1) <= 0)
 630           return_trace (false);
 631         { /* Sweep new states. */
 632           if (unlikely (hb_unsigned_mul_overflows ((max_state + 1), num_classes)))
 633             return_trace (false);
 634           const HBUSHORT *stop = &states[(max_state + 1) * num_classes];
 635           if (unlikely (stop < states))
 636             return_trace (false);
 637           for (const HBUSHORT *p = &states[state_pos * num_classes]; p < stop; p++)
 638             num_entries = hb_max (num_entries, *p + 1u);
 639           state_pos = max_state + 1;
 640         }
 641       }
 642
 643       if (unlikely (!c->check_array (entries, num_entries)))
 644         return_trace (false);
 645       if ((c->max_ops -= num_entries - entry) <= 0)
 646         return_trace (false);
 647       { /* Sweep new entries. */
 648         const Entry<Extra> *stop = &entries[num_entries];
 649         for (const Entry<Extra> *p = &entries[entry]; p < stop; p++)
 650         {
 651           int newState = new_state (p->newState);
 652           min_state = hb_min (min_state, newState);
 653           max_state = hb_max (max_state, newState);
 654         }
 655         entry = num_entries;
 656       }
 657     }
 658
 659     if (num_entries_out)
 660       *num_entries_out = num_entries;
 661
 662     return_trace (true);
 663   }
 664
 665   protected:
 666   HBUINT        nClasses;       /* Number of classes, which is the number of indices
 667                                  * in a single line in the state array. */
 668   NNOffsetTo<ClassType, HBUINT>
 669                 classTable;     /* Offset to the class table. */
 670   NNOffsetTo<UnsizedArrayOf<HBUSHORT>, HBUINT>
 671                 stateArrayTable;/* Offset to the state array. */
 672   NNOffsetTo<UnsizedArrayOf<Entry<Extra>>, HBUINT>
 673                 entryTable;     /* Offset to the entry array. */
 674
 675   public:
 676   DEFINE_SIZE_STATIC (4 * sizeof (HBUINT));
 677 };
 678
 679 template <typename HBUCHAR>
 680 struct ClassTable
 681 {
 682   unsigned int get_class (hb_codepoint_t glyph_id, unsigned int outOfRange) const
 683   {
 684     unsigned int i = glyph_id - firstGlyph;
 685     return i >= classArray.len ? outOfRange : classArray.arrayZ[i];
 686   }
 687   unsigned int get_class (hb_codepoint_t glyph_id,
 688                           unsigned int num_glyphs HB_UNUSED,
 689                           unsigned int outOfRange) const
 690   {
 691     return get_class (glyph_id, outOfRange);
 692   }
 693   bool sanitize (hb_sanitize_context_t *c) const
 694   {
 695     TRACE_SANITIZE (this);
 696     return_trace (c->check_struct (this) && classArray.sanitize (c));
 697   }
 698   protected:
 699   HBGlyphID16           firstGlyph;     /* First glyph index included in the trimmed array. */
 700   Array16Of<HBUCHAR>    classArray;     /* The class codes (indexed by glyph index minus
 701                                          * firstGlyph). */
 702   public:
 703   DEFINE_SIZE_ARRAY (4, classArray);
 704 };
 705
 706 struct ObsoleteTypes
 707 {
 708   static constexpr bool extended = false;
 709   typedef HBUINT16 HBUINT;
 710   typedef HBUINT8 HBUSHORT;
 711   typedef ClassTable<HBUINT8> ClassTypeNarrow;
 712   typedef ClassTable<HBUINT16> ClassTypeWide;
 713
 714   template <typename T>
 715   static unsigned int offsetToIndex (unsigned int offset,
 716                                      const void *base,
 717                                      const T *array)
 718   {
 719     /* https://github.com/harfbuzz/harfbuzz/issues/3483 */
 720     /* If offset is less than base, return an offset that would
 721      * result in an address half a 32bit address-space away,
 722      * to make sure sanitize fails even on 32bit builds. */
 723     if (unlikely (offset < unsigned ((const char *) array - (const char *) base)))
 724       return INT_MAX / T::static_size;
 725
 726     /* https://github.com/harfbuzz/harfbuzz/issues/2816 */
 727     return (offset - unsigned ((const char *) array - (const char *) base)) / T::static_size;
 728   }
 729   template <typename T>
 730   static unsigned int byteOffsetToIndex (unsigned int offset,
 731                                          const void *base,
 732                                          const T *array)
 733   {
 734     return offsetToIndex (offset, base, array);
 735   }
 736   template <typename T>
 737   static unsigned int wordOffsetToIndex (unsigned int offset,
 738                                          const void *base,
 739                                          const T *array)
 740   {
 741     return offsetToIndex (2 * offset, base, array);
 742   }
 743 };
 744 struct ExtendedTypes
 745 {
 746   static constexpr bool extended = true;
 747   typedef HBUINT32 HBUINT;
 748   typedef HBUINT16 HBUSHORT;
 749   typedef Lookup<HBUINT16> ClassTypeNarrow;
 750   typedef Lookup<HBUINT16> ClassTypeWide;
 751
 752   template <typename T>
 753   static unsigned int offsetToIndex (unsigned int offset,
 754                                      const void *base HB_UNUSED,
 755                                      const T *array HB_UNUSED)
 756   {
 757     return offset;
 758   }
 759   template <typename T>
 760   static unsigned int byteOffsetToIndex (unsigned int offset,
 761                                          const void *base HB_UNUSED,
 762                                          const T *array HB_UNUSED)
 763   {
 764     return offset / 2;
 765   }
 766   template <typename T>
 767   static unsigned int wordOffsetToIndex (unsigned int offset,
 768                                          const void *base HB_UNUSED,
 769                                          const T *array HB_UNUSED)
 770   {
 771     return offset;
 772   }
 773 };
 774
 775 template <typename Types, typename EntryData>
 776 struct StateTableDriver
 777 {
 778   using StateTableT = StateTable<Types, EntryData>;
 779   using EntryT = Entry<EntryData>;
 780
 781   StateTableDriver (const StateTableT &machine_,
 782                     hb_buffer_t *buffer_,
 783                     hb_face_t *face_) :
 784               machine (machine_),
 785               buffer (buffer_),
 786               num_glyphs (face_->get_num_glyphs ()) {}
 787
 788   template <typename context_t>
 789   void drive (context_t *c, hb_aat_apply_context_t *ac)
 790   {
 791     if (!c->in_place)
 792       buffer->clear_output ();
 793
 794     int state = StateTableT::STATE_START_OF_TEXT;
 795     // If there's only one range, we already checked the flag.
 796     auto *last_range = ac->range_flags && (ac->range_flags->length > 1) ? &(*ac->range_flags)[0] : nullptr;
 797     for (buffer->idx = 0; buffer->successful;)
 798     {
 799       /* This block is copied in NoncontextualSubtable::apply. Keep in sync. */
 800       if (last_range)
 801       {
 802         auto *range = last_range;
 803         if (buffer->idx < buffer->len)
 804         {
 805           unsigned cluster = buffer->cur().cluster;
 806           while (cluster < range->cluster_first)
 807             range--;
 808           while (cluster > range->cluster_last)
 809             range++;
 810
 811
 812           last_range = range;
 813         }
 814         if (!(range->flags & ac->subtable_flags))
 815         {
 816           if (buffer->idx == buffer->len || unlikely (!buffer->successful))
 817             break;
 818
 819           state = StateTableT::STATE_START_OF_TEXT;
 820           (void) buffer->next_glyph ();
 821           continue;
 822         }
 823       }
 824
 825       unsigned int klass = buffer->idx < buffer->len ?
 826                            machine.get_class (buffer->cur().codepoint, num_glyphs) :
 827                            (unsigned) StateTableT::CLASS_END_OF_TEXT;
 828       DEBUG_MSG (APPLY, nullptr, "c%u at %u", klass, buffer->idx);
 829       const EntryT &entry = machine.get_entry (state, klass);
 830       const int next_state = machine.new_state (entry.newState);
 831
 832       /* Conditions under which it's guaranteed safe-to-break before current glyph:
 833        *
 834        * 1. There was no action in this transition; and
 835        *
 836        * 2. If we break before current glyph, the results will be the same. That
 837        *    is guaranteed if:
 838        *
 839        *    2a. We were already in start-of-text state; or
 840        *
 841        *    2b. We are epsilon-transitioning to start-of-text state; or
 842        *
 843        *    2c. Starting from start-of-text state seeing current glyph:
 844        *
 845        *        2c'. There won't be any actions; and
 846        *
 847        *        2c". We would end up in the same state that we were going to end up
 848        *             in now, including whether epsilon-transitioning.
 849        *
 850        *    and
 851        *
 852        * 3. If we break before current glyph, there won't be any end-of-text action
 853        *    after previous glyph.
 854        *
 855        * This triples the transitions we need to look up, but is worth returning
 856        * granular unsafe-to-break results. See eg.:
 857        *
 858        *   https://github.com/harfbuzz/harfbuzz/issues/2860
 859        */
 860
 861       const auto is_safe_to_break_extra = [&]()
 862       {
 863           /* 2c. */
 864           const auto wouldbe_entry = machine.get_entry(StateTableT::STATE_START_OF_TEXT, klass);
 865
 866           /* 2c'. */
 867           if (c->is_actionable (this, wouldbe_entry))
 868               return false;
 869
 870           /* 2c". */
 871           return next_state == machine.new_state(wouldbe_entry.newState)
 872               && (entry.flags & context_t::DontAdvance) == (wouldbe_entry.flags & context_t::DontAdvance);
 873       };
 874
 875       const auto is_safe_to_break = [&]()
 876       {
 877           /* 1. */
 878           if (c->is_actionable (this, entry))
 879               return false;
 880
 881           /* 2. */
 882           // This one is meh, I know...
 883           const auto ok =
 884                  state == StateTableT::STATE_START_OF_TEXT
 885               || ((entry.flags & context_t::DontAdvance) && next_state == StateTableT::STATE_START_OF_TEXT)
 886               || is_safe_to_break_extra();
 887           if (!ok)
 888               return false;
 889
 890           /* 3. */
 891           return !c->is_actionable (this, machine.get_entry (state, StateTableT::CLASS_END_OF_TEXT));
 892       };
 893
 894       if (!is_safe_to_break () && buffer->backtrack_len () && buffer->idx < buffer->len)
 895         buffer->unsafe_to_break_from_outbuffer (buffer->backtrack_len () - 1, buffer->idx + 1);
 896
 897       c->transition (this, entry);
 898
 899       state = next_state;
 900       DEBUG_MSG (APPLY, nullptr, "s%d", state);
 901
 902       if (buffer->idx == buffer->len || unlikely (!buffer->successful))
 903         break;
 904
 905       if (!(entry.flags & context_t::DontAdvance) || buffer->max_ops-- <= 0)
 906         (void) buffer->next_glyph ();
 907     }
 908
 909     if (!c->in_place)
 910       buffer->sync ();
 911   }
 912
 913   public:
 914   const StateTableT &machine;
 915   hb_buffer_t *buffer;
 916   unsigned int num_glyphs;
 917 };
 918
 919
 920 } /* namespace AAT */
 921
 922
 923 #endif /* HB_AAT_LAYOUT_COMMON_HH */