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