src/hb-aat-layout-kerx-table.hh

   1 /*
   2  * Copyright © 2018  Ebrahim Byagowi
   3  * Copyright © 2018  Google, 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  * Google Author(s): Behdad Esfahbod
  26  */
  27
  28 #ifndef HB_AAT_LAYOUT_KERX_TABLE_HH
  29 #define HB_AAT_LAYOUT_KERX_TABLE_HH
  30
  31 #include "hb-kern.hh"
  32 #include "hb-aat-layout-ankr-table.hh"
  33
  34 /*
  35  * kerx -- Extended Kerning
  36  * https://developer.apple.com/fonts/TrueType-Reference-Manual/RM06/Chap6kerx.html
  37  */
  38 #define HB_AAT_TAG_kerx HB_TAG('k','e','r','x')
  39
  40
  41 namespace AAT {
  42
  43 using namespace OT;
  44
  45
  46 static inline int
  47 kerxTupleKern (int value,
  48                unsigned int tupleCount,
  49                const void *base,
  50                hb_aat_apply_context_t *c)
  51 {
  52   if (likely (!tupleCount || !c)) return value;
  53
  54   unsigned int offset = value;
  55   const FWORD *pv = &StructAtOffset<FWORD> (base, offset);
  56   if (unlikely (!c->sanitizer.check_array (pv, tupleCount))) return 0;
  57   return *pv;
  58 }
  59
  60
  61 struct hb_glyph_pair_t
  62 {
  63   hb_codepoint_t left;
  64   hb_codepoint_t right;
  65 };
  66
  67 struct KernPair
  68 {
  69   int get_kerning () const { return value; }
  70
  71   int cmp (const hb_glyph_pair_t &o) const
  72   {
  73     int ret = left.cmp (o.left);
  74     if (ret) return ret;
  75     return right.cmp (o.right);
  76   }
  77
  78   bool sanitize (hb_sanitize_context_t *c) const
  79   {
  80     TRACE_SANITIZE (this);
  81     return_trace (c->check_struct (this));
  82   }
  83
  84   protected:
  85   HBGlyphID16   left;
  86   HBGlyphID16   right;
  87   FWORD         value;
  88   public:
  89   DEFINE_SIZE_STATIC (6);
  90 };
  91
  92 template <typename KernSubTableHeader>
  93 struct KerxSubTableFormat0
  94 {
  95   int get_kerning (hb_codepoint_t left, hb_codepoint_t right,
  96                    hb_aat_apply_context_t *c = nullptr) const
  97   {
  98     hb_glyph_pair_t pair = {left, right};
  99     int v = pairs.bsearch (pair).get_kerning ();
 100     return kerxTupleKern (v, header.tuple_count (), this, c);
 101   }
 102
 103   bool apply (hb_aat_apply_context_t *c) const
 104   {
 105     TRACE_APPLY (this);
 106
 107     if (!c->plan->requested_kerning)
 108       return false;
 109
 110     if (header.coverage & header.Backwards)
 111       return false;
 112
 113     accelerator_t accel (*this, c);
 114     hb_kern_machine_t<accelerator_t> machine (accel, header.coverage & header.CrossStream);
 115     machine.kern (c->font, c->buffer, c->plan->kern_mask);
 116
 117     return_trace (true);
 118   }
 119
 120   struct accelerator_t
 121   {
 122     const KerxSubTableFormat0 &table;
 123     hb_aat_apply_context_t *c;
 124
 125     accelerator_t (const KerxSubTableFormat0 &table_,
 126                    hb_aat_apply_context_t *c_) :
 127                      table (table_), c (c_) {}
 128
 129     int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 130     { return table.get_kerning (left, right, c); }
 131   };
 132
 133
 134   bool sanitize (hb_sanitize_context_t *c) const
 135   {
 136     TRACE_SANITIZE (this);
 137     return_trace (likely (pairs.sanitize (c)));
 138   }
 139
 140   protected:
 141   KernSubTableHeader    header;
 142   BinSearchArrayOf<KernPair, typename KernSubTableHeader::Types::HBUINT>
 143                         pairs;  /* Sorted kern records. */
 144   public:
 145   DEFINE_SIZE_ARRAY (KernSubTableHeader::static_size + 16, pairs);
 146 };
 147
 148
 149 template <bool extended>
 150 struct Format1Entry;
 151
 152 template <>
 153 struct Format1Entry<true>
 154 {
 155   enum Flags
 156   {
 157     Push                = 0x8000,       /* If set, push this glyph on the kerning stack. */
 158     DontAdvance         = 0x4000,       /* If set, don't advance to the next glyph
 159                                          * before going to the new state. */
 160     Reset               = 0x2000,       /* If set, reset the kerning data (clear the stack) */
 161     Reserved            = 0x1FFF,       /* Not used; set to 0. */
 162   };
 163
 164   struct EntryData
 165   {
 166     HBUINT16    kernActionIndex;/* Index into the kerning value array. If
 167                                  * this index is 0xFFFF, then no kerning
 168                                  * is to be performed. */
 169     public:
 170     DEFINE_SIZE_STATIC (2);
 171   };
 172
 173   static bool performAction (const Entry<EntryData> &entry)
 174   { return entry.data.kernActionIndex != 0xFFFF; }
 175
 176   static unsigned int kernActionIndex (const Entry<EntryData> &entry)
 177   { return entry.data.kernActionIndex; }
 178 };
 179 template <>
 180 struct Format1Entry<false>
 181 {
 182   enum Flags
 183   {
 184     Push                = 0x8000,       /* If set, push this glyph on the kerning stack. */
 185     DontAdvance         = 0x4000,       /* If set, don't advance to the next glyph
 186                                          * before going to the new state. */
 187     Offset              = 0x3FFF,       /* Byte offset from beginning of subtable to the
 188                                          * value table for the glyphs on the kerning stack. */
 189
 190     Reset               = 0x0000,       /* Not supported? */
 191   };
 192
 193   typedef void EntryData;
 194
 195   static bool performAction (const Entry<EntryData> &entry)
 196   { return entry.flags & Offset; }
 197
 198   static unsigned int kernActionIndex (const Entry<EntryData> &entry)
 199   { return entry.flags & Offset; }
 200 };
 201
 202 template <typename KernSubTableHeader>
 203 struct KerxSubTableFormat1
 204 {
 205   typedef typename KernSubTableHeader::Types Types;
 206   typedef typename Types::HBUINT HBUINT;
 207
 208   typedef Format1Entry<Types::extended> Format1EntryT;
 209   typedef typename Format1EntryT::EntryData EntryData;
 210
 211   struct driver_context_t
 212   {
 213     static constexpr bool in_place = true;
 214     enum
 215     {
 216       DontAdvance       = Format1EntryT::DontAdvance,
 217     };
 218
 219     driver_context_t (const KerxSubTableFormat1 *table_,
 220                       hb_aat_apply_context_t *c_) :
 221         c (c_),
 222         table (table_),
 223         /* Apparently the offset kernAction is from the beginning of the state-machine,
 224          * similar to offsets in morx table, NOT from beginning of this table, like
 225          * other subtables in kerx.  Discovered via testing. */
 226         kernAction (&table->machine + table->kernAction),
 227         depth (0),
 228         crossStream (table->header.coverage & table->header.CrossStream) {}
 229
 230     bool is_actionable (StateTableDriver<Types, EntryData> *driver HB_UNUSED,
 231                         const Entry<EntryData> &entry)
 232     { return Format1EntryT::performAction (entry); }
 233     void transition (StateTableDriver<Types, EntryData> *driver,
 234                      const Entry<EntryData> &entry)
 235     {
 236       hb_buffer_t *buffer = driver->buffer;
 237       unsigned int flags = entry.flags;
 238
 239       if (flags & Format1EntryT::Reset)
 240         depth = 0;
 241
 242       if (flags & Format1EntryT::Push)
 243       {
 244         if (likely (depth < ARRAY_LENGTH (stack)))
 245           stack[depth++] = buffer->idx;
 246         else
 247           depth = 0; /* Probably not what CoreText does, but better? */
 248       }
 249
 250       if (Format1EntryT::performAction (entry) && depth)
 251       {
 252         unsigned int tuple_count = hb_max (1u, table->header.tuple_count ());
 253
 254         unsigned int kern_idx = Format1EntryT::kernActionIndex (entry);
 255         kern_idx = Types::byteOffsetToIndex (kern_idx, &table->machine, kernAction.arrayZ);
 256         const FWORD *actions = &kernAction[kern_idx];
 257         if (!c->sanitizer.check_array (actions, depth, tuple_count))
 258         {
 259           depth = 0;
 260           return;
 261         }
 262
 263         hb_mask_t kern_mask = c->plan->kern_mask;
 264
 265         /* From Apple 'kern' spec:
 266          * "Each pops one glyph from the kerning stack and applies the kerning value to it.
 267          * The end of the list is marked by an odd value... */
 268         bool last = false;
 269         while (!last && depth)
 270         {
 271           unsigned int idx = stack[--depth];
 272           int v = *actions;
 273           actions += tuple_count;
 274           if (idx >= buffer->len) continue;
 275
 276           /* "The end of the list is marked by an odd value..." */
 277           last = v & 1;
 278           v &= ~1;
 279
 280           hb_glyph_position_t &o = buffer->pos[idx];
 281
 282           if (HB_DIRECTION_IS_HORIZONTAL (buffer->props.direction))
 283           {
 284             if (crossStream)
 285             {
 286               /* The following flag is undocumented in the spec, but described
 287                * in the 'kern' table example. */
 288               if (v == -0x8000)
 289               {
 290                 o.attach_type() = ATTACH_TYPE_NONE;
 291                 o.attach_chain() = 0;
 292                 o.y_offset = 0;
 293               }
 294               else if (o.attach_type())
 295               {
 296                 o.y_offset += c->font->em_scale_y (v);
 297                 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 298               }
 299             }
 300             else if (buffer->info[idx].mask & kern_mask)
 301             {
 302               o.x_advance += c->font->em_scale_x (v);
 303               o.x_offset += c->font->em_scale_x (v);
 304             }
 305           }
 306           else
 307           {
 308             if (crossStream)
 309             {
 310               /* CoreText doesn't do crossStream kerning in vertical.  We do. */
 311               if (v == -0x8000)
 312               {
 313                 o.attach_type() = ATTACH_TYPE_NONE;
 314                 o.attach_chain() = 0;
 315                 o.x_offset = 0;
 316               }
 317               else if (o.attach_type())
 318               {
 319                 o.x_offset += c->font->em_scale_x (v);
 320                 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 321               }
 322             }
 323             else if (buffer->info[idx].mask & kern_mask)
 324             {
 325               o.y_advance += c->font->em_scale_y (v);
 326               o.y_offset += c->font->em_scale_y (v);
 327             }
 328           }
 329         }
 330       }
 331     }
 332
 333     private:
 334     hb_aat_apply_context_t *c;
 335     const KerxSubTableFormat1 *table;
 336     const UnsizedArrayOf<FWORD> &kernAction;
 337     unsigned int stack[8];
 338     unsigned int depth;
 339     bool crossStream;
 340   };
 341
 342   bool apply (hb_aat_apply_context_t *c) const
 343   {
 344     TRACE_APPLY (this);
 345
 346     if (!c->plan->requested_kerning &&
 347         !(header.coverage & header.CrossStream))
 348       return false;
 349
 350     driver_context_t dc (this, c);
 351
 352     StateTableDriver<Types, EntryData> driver (machine, c->buffer, c->font->face);
 353     driver.drive (&dc);
 354
 355     return_trace (true);
 356   }
 357
 358   bool sanitize (hb_sanitize_context_t *c) const
 359   {
 360     TRACE_SANITIZE (this);
 361     /* The rest of array sanitizations are done at run-time. */
 362     return_trace (likely (c->check_struct (this) &&
 363                           machine.sanitize (c)));
 364   }
 365
 366   protected:
 367   KernSubTableHeader                            header;
 368   StateTable<Types, EntryData>                  machine;
 369   NNOffsetTo<UnsizedArrayOf<FWORD>, HBUINT>     kernAction;
 370   public:
 371   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 5 * sizeof (HBUINT));
 372 };
 373
 374 template <typename KernSubTableHeader>
 375 struct KerxSubTableFormat2
 376 {
 377   typedef typename KernSubTableHeader::Types Types;
 378   typedef typename Types::HBUINT HBUINT;
 379
 380   int get_kerning (hb_codepoint_t left, hb_codepoint_t right,
 381                    hb_aat_apply_context_t *c) const
 382   {
 383     unsigned int num_glyphs = c->sanitizer.get_num_glyphs ();
 384     unsigned int l = (this+leftClassTable).get_class (left, num_glyphs, 0);
 385     unsigned int r = (this+rightClassTable).get_class (right, num_glyphs, 0);
 386
 387     const UnsizedArrayOf<FWORD> &arrayZ = this+array;
 388     unsigned int kern_idx = l + r;
 389     kern_idx = Types::offsetToIndex (kern_idx, this, arrayZ.arrayZ);
 390     const FWORD *v = &arrayZ[kern_idx];
 391     if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 392
 393     return kerxTupleKern (*v, header.tuple_count (), this, c);
 394   }
 395
 396   bool apply (hb_aat_apply_context_t *c) const
 397   {
 398     TRACE_APPLY (this);
 399
 400     if (!c->plan->requested_kerning)
 401       return false;
 402
 403     if (header.coverage & header.Backwards)
 404       return false;
 405
 406     accelerator_t accel (*this, c);
 407     hb_kern_machine_t<accelerator_t> machine (accel, header.coverage & header.CrossStream);
 408     machine.kern (c->font, c->buffer, c->plan->kern_mask);
 409
 410     return_trace (true);
 411   }
 412
 413   struct accelerator_t
 414   {
 415     const KerxSubTableFormat2 &table;
 416     hb_aat_apply_context_t *c;
 417
 418     accelerator_t (const KerxSubTableFormat2 &table_,
 419                    hb_aat_apply_context_t *c_) :
 420                      table (table_), c (c_) {}
 421
 422     int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 423     { return table.get_kerning (left, right, c); }
 424   };
 425
 426   bool sanitize (hb_sanitize_context_t *c) const
 427   {
 428     TRACE_SANITIZE (this);
 429     return_trace (likely (c->check_struct (this) &&
 430                           leftClassTable.sanitize (c, this) &&
 431                           rightClassTable.sanitize (c, this) &&
 432                           c->check_range (this, array)));
 433   }
 434
 435   protected:
 436   KernSubTableHeader    header;
 437   HBUINT                rowWidth;       /* The width, in bytes, of a row in the table. */
 438   NNOffsetTo<typename Types::ClassTypeWide, HBUINT>
 439                         leftClassTable; /* Offset from beginning of this subtable to
 440                                          * left-hand class table. */
 441   NNOffsetTo<typename Types::ClassTypeWide, HBUINT>
 442                         rightClassTable;/* Offset from beginning of this subtable to
 443                                          * right-hand class table. */
 444   NNOffsetTo<UnsizedArrayOf<FWORD>, HBUINT>
 445                          array;         /* Offset from beginning of this subtable to
 446                                          * the start of the kerning array. */
 447   public:
 448   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 4 * sizeof (HBUINT));
 449 };
 450
 451 template <typename KernSubTableHeader>
 452 struct KerxSubTableFormat4
 453 {
 454   typedef ExtendedTypes Types;
 455
 456   struct EntryData
 457   {
 458     HBUINT16    ankrActionIndex;/* Either 0xFFFF (for no action) or the index of
 459                                  * the action to perform. */
 460     public:
 461     DEFINE_SIZE_STATIC (2);
 462   };
 463
 464   struct driver_context_t
 465   {
 466     static constexpr bool in_place = true;
 467     enum Flags
 468     {
 469       Mark              = 0x8000,       /* If set, remember this glyph as the marked glyph. */
 470       DontAdvance       = 0x4000,       /* If set, don't advance to the next glyph before
 471                                          * going to the new state. */
 472       Reserved          = 0x3FFF,       /* Not used; set to 0. */
 473     };
 474
 475     enum SubTableFlags
 476     {
 477       ActionType        = 0xC0000000,   /* A two-bit field containing the action type. */
 478       Unused            = 0x3F000000,   /* Unused - must be zero. */
 479       Offset            = 0x00FFFFFF,   /* Masks the offset in bytes from the beginning
 480                                          * of the subtable to the beginning of the control
 481                                          * point table. */
 482     };
 483
 484     driver_context_t (const KerxSubTableFormat4 *table,
 485                       hb_aat_apply_context_t *c_) :
 486         c (c_),
 487         action_type ((table->flags & ActionType) >> 30),
 488         ankrData ((HBUINT16 *) ((const char *) &table->machine + (table->flags & Offset))),
 489         mark_set (false),
 490         mark (0) {}
 491
 492     bool is_actionable (StateTableDriver<Types, EntryData> *driver HB_UNUSED,
 493                         const Entry<EntryData> &entry)
 494     { return entry.data.ankrActionIndex != 0xFFFF; }
 495     void transition (StateTableDriver<Types, EntryData> *driver,
 496                      const Entry<EntryData> &entry)
 497     {
 498       hb_buffer_t *buffer = driver->buffer;
 499
 500       if (mark_set && entry.data.ankrActionIndex != 0xFFFF && buffer->idx < buffer->len)
 501       {
 502         hb_glyph_position_t &o = buffer->cur_pos();
 503         switch (action_type)
 504         {
 505           case 0: /* Control Point Actions.*/
 506           {
 507             /* Indexed into glyph outline. */
 508             /* Each action (record in ankrData) contains two 16-bit fields, so we must
 509                double the ankrActionIndex to get the correct offset here. */
 510             const HBUINT16 *data = &ankrData[entry.data.ankrActionIndex * 2];
 511             if (!c->sanitizer.check_array (data, 2)) return;
 512             unsigned int markControlPoint = *data++;
 513             unsigned int currControlPoint = *data++;
 514             hb_position_t markX = 0;
 515             hb_position_t markY = 0;
 516             hb_position_t currX = 0;
 517             hb_position_t currY = 0;
 518             if (!c->font->get_glyph_contour_point_for_origin (c->buffer->info[mark].codepoint,
 519                                                               markControlPoint,
 520                                                               HB_DIRECTION_LTR /*XXX*/,
 521                                                               &markX, &markY) ||
 522                 !c->font->get_glyph_contour_point_for_origin (c->buffer->cur ().codepoint,
 523                                                               currControlPoint,
 524                                                               HB_DIRECTION_LTR /*XXX*/,
 525                                                               &currX, &currY))
 526               return;
 527
 528             o.x_offset = markX - currX;
 529             o.y_offset = markY - currY;
 530           }
 531           break;
 532
 533           case 1: /* Anchor Point Actions. */
 534           {
 535             /* Indexed into 'ankr' table. */
 536             /* Each action (record in ankrData) contains two 16-bit fields, so we must
 537                double the ankrActionIndex to get the correct offset here. */
 538             const HBUINT16 *data = &ankrData[entry.data.ankrActionIndex * 2];
 539             if (!c->sanitizer.check_array (data, 2)) return;
 540             unsigned int markAnchorPoint = *data++;
 541             unsigned int currAnchorPoint = *data++;
 542             const Anchor &markAnchor = c->ankr_table->get_anchor (c->buffer->info[mark].codepoint,
 543                                                                   markAnchorPoint,
 544                                                                   c->sanitizer.get_num_glyphs ());
 545             const Anchor &currAnchor = c->ankr_table->get_anchor (c->buffer->cur ().codepoint,
 546                                                                   currAnchorPoint,
 547                                                                   c->sanitizer.get_num_glyphs ());
 548
 549             o.x_offset = c->font->em_scale_x (markAnchor.xCoordinate) - c->font->em_scale_x (currAnchor.xCoordinate);
 550             o.y_offset = c->font->em_scale_y (markAnchor.yCoordinate) - c->font->em_scale_y (currAnchor.yCoordinate);
 551           }
 552           break;
 553
 554           case 2: /* Control Point Coordinate Actions. */
 555           {
 556             /* Each action contains four 16-bit fields, so we multiply the ankrActionIndex
 557                by 4 to get the correct offset for the given action. */
 558             const FWORD *data = (const FWORD *) &ankrData[entry.data.ankrActionIndex * 4];
 559             if (!c->sanitizer.check_array (data, 4)) return;
 560             int markX = *data++;
 561             int markY = *data++;
 562             int currX = *data++;
 563             int currY = *data++;
 564
 565             o.x_offset = c->font->em_scale_x (markX) - c->font->em_scale_x (currX);
 566             o.y_offset = c->font->em_scale_y (markY) - c->font->em_scale_y (currY);
 567           }
 568           break;
 569         }
 570         o.attach_type() = ATTACH_TYPE_MARK;
 571         o.attach_chain() = (int) mark - (int) buffer->idx;
 572         buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 573       }
 574
 575       if (entry.flags & Mark)
 576       {
 577         mark_set = true;
 578         mark = buffer->idx;
 579       }
 580     }
 581
 582     private:
 583     hb_aat_apply_context_t *c;
 584     unsigned int action_type;
 585     const HBUINT16 *ankrData;
 586     bool mark_set;
 587     unsigned int mark;
 588   };
 589
 590   bool apply (hb_aat_apply_context_t *c) const
 591   {
 592     TRACE_APPLY (this);
 593
 594     driver_context_t dc (this, c);
 595
 596     StateTableDriver<Types, EntryData> driver (machine, c->buffer, c->font->face);
 597     driver.drive (&dc);
 598
 599     return_trace (true);
 600   }
 601
 602   bool sanitize (hb_sanitize_context_t *c) const
 603   {
 604     TRACE_SANITIZE (this);
 605     /* The rest of array sanitizations are done at run-time. */
 606     return_trace (likely (c->check_struct (this) &&
 607                           machine.sanitize (c)));
 608   }
 609
 610   protected:
 611   KernSubTableHeader            header;
 612   StateTable<Types, EntryData>  machine;
 613   HBUINT32                      flags;
 614   public:
 615   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 20);
 616 };
 617
 618 template <typename KernSubTableHeader>
 619 struct KerxSubTableFormat6
 620 {
 621   enum Flags
 622   {
 623     ValuesAreLong       = 0x00000001,
 624   };
 625
 626   bool is_long () const { return flags & ValuesAreLong; }
 627
 628   int get_kerning (hb_codepoint_t left, hb_codepoint_t right,
 629                    hb_aat_apply_context_t *c) const
 630   {
 631     unsigned int num_glyphs = c->sanitizer.get_num_glyphs ();
 632     if (is_long ())
 633     {
 634       const typename U::Long &t = u.l;
 635       unsigned int l = (this+t.rowIndexTable).get_value_or_null (left, num_glyphs);
 636       unsigned int r = (this+t.columnIndexTable).get_value_or_null (right, num_glyphs);
 637       unsigned int offset = l + r;
 638       if (unlikely (offset < l)) return 0; /* Addition overflow. */
 639       if (unlikely (hb_unsigned_mul_overflows (offset, sizeof (FWORD32)))) return 0;
 640       const FWORD32 *v = &StructAtOffset<FWORD32> (&(this+t.array), offset * sizeof (FWORD32));
 641       if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 642       return kerxTupleKern (*v, header.tuple_count (), &(this+vector), c);
 643     }
 644     else
 645     {
 646       const typename U::Short &t = u.s;
 647       unsigned int l = (this+t.rowIndexTable).get_value_or_null (left, num_glyphs);
 648       unsigned int r = (this+t.columnIndexTable).get_value_or_null (right, num_glyphs);
 649       unsigned int offset = l + r;
 650       const FWORD *v = &StructAtOffset<FWORD> (&(this+t.array), offset * sizeof (FWORD));
 651       if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 652       return kerxTupleKern (*v, header.tuple_count (), &(this+vector), c);
 653     }
 654   }
 655
 656   bool apply (hb_aat_apply_context_t *c) const
 657   {
 658     TRACE_APPLY (this);
 659
 660     if (!c->plan->requested_kerning)
 661       return false;
 662
 663     if (header.coverage & header.Backwards)
 664       return false;
 665
 666     accelerator_t accel (*this, c);
 667     hb_kern_machine_t<accelerator_t> machine (accel, header.coverage & header.CrossStream);
 668     machine.kern (c->font, c->buffer, c->plan->kern_mask);
 669
 670     return_trace (true);
 671   }
 672
 673   bool sanitize (hb_sanitize_context_t *c) const
 674   {
 675     TRACE_SANITIZE (this);
 676     return_trace (likely (c->check_struct (this) &&
 677                           (is_long () ?
 678                            (
 679                              u.l.rowIndexTable.sanitize (c, this) &&
 680                              u.l.columnIndexTable.sanitize (c, this) &&
 681                              c->check_range (this, u.l.array)
 682                            ) : (
 683                              u.s.rowIndexTable.sanitize (c, this) &&
 684                              u.s.columnIndexTable.sanitize (c, this) &&
 685                              c->check_range (this, u.s.array)
 686                            )) &&
 687                           (header.tuple_count () == 0 ||
 688                            c->check_range (this, vector))));
 689   }
 690
 691   struct accelerator_t
 692   {
 693     const KerxSubTableFormat6 &table;
 694     hb_aat_apply_context_t *c;
 695
 696     accelerator_t (const KerxSubTableFormat6 &table_,
 697                    hb_aat_apply_context_t *c_) :
 698                      table (table_), c (c_) {}
 699
 700     int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 701     { return table.get_kerning (left, right, c); }
 702   };
 703
 704   protected:
 705   KernSubTableHeader            header;
 706   HBUINT32                      flags;
 707   HBUINT16                      rowCount;
 708   HBUINT16                      columnCount;
 709   union U
 710   {
 711     struct Long
 712     {
 713       NNOffset32To<Lookup<HBUINT32>>            rowIndexTable;
 714       NNOffset32To<Lookup<HBUINT32>>            columnIndexTable;
 715       NNOffset32To<UnsizedArrayOf<FWORD32>>     array;
 716     } l;
 717     struct Short
 718     {
 719       NNOffset32To<Lookup<HBUINT16>>            rowIndexTable;
 720       NNOffset32To<Lookup<HBUINT16>>            columnIndexTable;
 721       NNOffset32To<UnsizedArrayOf<FWORD>>       array;
 722     } s;
 723   } u;
 724   NNOffset32To<UnsizedArrayOf<FWORD>>   vector;
 725   public:
 726   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 24);
 727 };
 728
 729
 730 struct KerxSubTableHeader
 731 {
 732   typedef ExtendedTypes Types;
 733
 734   unsigned   tuple_count () const { return tupleCount; }
 735   bool     is_horizontal () const { return !(coverage & Vertical); }
 736
 737   enum Coverage
 738   {
 739     Vertical    = 0x80000000u,  /* Set if table has vertical kerning values. */
 740     CrossStream = 0x40000000u,  /* Set if table has cross-stream kerning values. */
 741     Variation   = 0x20000000u,  /* Set if table has variation kerning values. */
 742     Backwards   = 0x10000000u,  /* If clear, process the glyphs forwards, that
 743                                  * is, from first to last in the glyph stream.
 744                                  * If we, process them from last to first.
 745                                  * This flag only applies to state-table based
 746                                  * 'kerx' subtables (types 1 and 4). */
 747     Reserved    = 0x0FFFFF00u,  /* Reserved, set to zero. */
 748     SubtableType= 0x000000FFu,  /* Subtable type. */
 749   };
 750
 751   bool sanitize (hb_sanitize_context_t *c) const
 752   {
 753     TRACE_SANITIZE (this);
 754     return_trace (likely (c->check_struct (this)));
 755   }
 756
 757   public:
 758   HBUINT32      length;
 759   HBUINT32      coverage;
 760   HBUINT32      tupleCount;
 761   public:
 762   DEFINE_SIZE_STATIC (12);
 763 };
 764
 765 struct KerxSubTable
 766 {
 767   friend struct kerx;
 768
 769   unsigned int get_size () const { return u.header.length; }
 770   unsigned int get_type () const { return u.header.coverage & u.header.SubtableType; }
 771
 772   template <typename context_t, typename ...Ts>
 773   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
 774   {
 775     unsigned int subtable_type = get_type ();
 776     TRACE_DISPATCH (this, subtable_type);
 777     switch (subtable_type) {
 778     case 0:     return_trace (c->dispatch (u.format0, std::forward<Ts> (ds)...));
 779     case 1:     return_trace (c->dispatch (u.format1, std::forward<Ts> (ds)...));
 780     case 2:     return_trace (c->dispatch (u.format2, std::forward<Ts> (ds)...));
 781     case 4:     return_trace (c->dispatch (u.format4, std::forward<Ts> (ds)...));
 782     case 6:     return_trace (c->dispatch (u.format6, std::forward<Ts> (ds)...));
 783     default:    return_trace (c->default_return_value ());
 784     }
 785   }
 786
 787   bool sanitize (hb_sanitize_context_t *c) const
 788   {
 789     TRACE_SANITIZE (this);
 790     if (!u.header.sanitize (c) ||
 791         u.header.length <= u.header.static_size ||
 792         !c->check_range (this, u.header.length))
 793       return_trace (false);
 794
 795     return_trace (dispatch (c));
 796   }
 797
 798   public:
 799   union {
 800   KerxSubTableHeader                            header;
 801   KerxSubTableFormat0<KerxSubTableHeader>       format0;
 802   KerxSubTableFormat1<KerxSubTableHeader>       format1;
 803   KerxSubTableFormat2<KerxSubTableHeader>       format2;
 804   KerxSubTableFormat4<KerxSubTableHeader>       format4;
 805   KerxSubTableFormat6<KerxSubTableHeader>       format6;
 806   } u;
 807   public:
 808   DEFINE_SIZE_MIN (12);
 809 };
 810
 811
 812 /*
 813  * The 'kerx' Table
 814  */
 815
 816 template <typename T>
 817 struct KerxTable
 818 {
 819   /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
 820   const T* thiz () const { return static_cast<const T *> (this); }
 821
 822   bool has_state_machine () const
 823   {
 824     typedef typename T::SubTable SubTable;
 825
 826     const SubTable *st = &thiz()->firstSubTable;
 827     unsigned int count = thiz()->tableCount;
 828     for (unsigned int i = 0; i < count; i++)
 829     {
 830       if (st->get_type () == 1)
 831         return true;
 832       st = &StructAfter<SubTable> (*st);
 833     }
 834     return false;
 835   }
 836
 837   bool has_cross_stream () const
 838   {
 839     typedef typename T::SubTable SubTable;
 840
 841     const SubTable *st = &thiz()->firstSubTable;
 842     unsigned int count = thiz()->tableCount;
 843     for (unsigned int i = 0; i < count; i++)
 844     {
 845       if (st->u.header.coverage & st->u.header.CrossStream)
 846         return true;
 847       st = &StructAfter<SubTable> (*st);
 848     }
 849     return false;
 850   }
 851
 852   int get_h_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 853   {
 854     typedef typename T::SubTable SubTable;
 855
 856     int v = 0;
 857     const SubTable *st = &thiz()->firstSubTable;
 858     unsigned int count = thiz()->tableCount;
 859     for (unsigned int i = 0; i < count; i++)
 860     {
 861       if ((st->u.header.coverage & (st->u.header.Variation | st->u.header.CrossStream)) ||
 862           !st->u.header.is_horizontal ())
 863         continue;
 864       v += st->get_kerning (left, right);
 865       st = &StructAfter<SubTable> (*st);
 866     }
 867     return v;
 868   }
 869
 870   bool apply (AAT::hb_aat_apply_context_t *c) const
 871   {
 872     typedef typename T::SubTable SubTable;
 873
 874     bool ret = false;
 875     bool seenCrossStream = false;
 876     c->set_lookup_index (0);
 877     const SubTable *st = &thiz()->firstSubTable;
 878     unsigned int count = thiz()->tableCount;
 879     for (unsigned int i = 0; i < count; i++)
 880     {
 881       bool reverse;
 882
 883       if (!T::Types::extended && (st->u.header.coverage & st->u.header.Variation))
 884         goto skip;
 885
 886       if (HB_DIRECTION_IS_HORIZONTAL (c->buffer->props.direction) != st->u.header.is_horizontal ())
 887         goto skip;
 888
 889       reverse = bool (st->u.header.coverage & st->u.header.Backwards) !=
 890                 HB_DIRECTION_IS_BACKWARD (c->buffer->props.direction);
 891
 892       if (!c->buffer->message (c->font, "start subtable %d", c->lookup_index))
 893         goto skip;
 894
 895       if (!seenCrossStream &&
 896           (st->u.header.coverage & st->u.header.CrossStream))
 897       {
 898         /* Attach all glyphs into a chain. */
 899         seenCrossStream = true;
 900         hb_glyph_position_t *pos = c->buffer->pos;
 901         unsigned int count = c->buffer->len;
 902         for (unsigned int i = 0; i < count; i++)
 903         {
 904           pos[i].attach_type() = ATTACH_TYPE_CURSIVE;
 905           pos[i].attach_chain() = HB_DIRECTION_IS_FORWARD (c->buffer->props.direction) ? -1 : +1;
 906           /* We intentionally don't set HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT,
 907            * since there needs to be a non-zero attachment for post-positioning to
 908            * be needed. */
 909         }
 910       }
 911
 912       if (reverse)
 913         c->buffer->reverse ();
 914
 915       {
 916         /* See comment in sanitize() for conditional here. */
 917         hb_sanitize_with_object_t with (&c->sanitizer, i < count - 1 ? st : (const SubTable *) nullptr);
 918         ret |= st->dispatch (c);
 919       }
 920
 921       if (reverse)
 922         c->buffer->reverse ();
 923
 924       (void) c->buffer->message (c->font, "end subtable %d", c->lookup_index);
 925
 926     skip:
 927       st = &StructAfter<SubTable> (*st);
 928       c->set_lookup_index (c->lookup_index + 1);
 929     }
 930
 931     return ret;
 932   }
 933
 934   bool sanitize (hb_sanitize_context_t *c) const
 935   {
 936     TRACE_SANITIZE (this);
 937     if (unlikely (!thiz()->version.sanitize (c) ||
 938                   (unsigned) thiz()->version < (unsigned) T::minVersion ||
 939                   !thiz()->tableCount.sanitize (c)))
 940       return_trace (false);
 941
 942     typedef typename T::SubTable SubTable;
 943
 944     const SubTable *st = &thiz()->firstSubTable;
 945     unsigned int count = thiz()->tableCount;
 946     for (unsigned int i = 0; i < count; i++)
 947     {
 948       if (unlikely (!st->u.header.sanitize (c)))
 949         return_trace (false);
 950       /* OpenType kern table has 2-byte subtable lengths.  That's limiting.
 951        * MS implementation also only supports one subtable, of format 0,
 952        * anyway.  Certain versions of some fonts, like Calibry, contain
 953        * kern subtable that exceeds 64kb.  Looks like, the subtable length
 954        * is simply ignored.  Which makes sense.  It's only needed if you
 955        * have multiple subtables.  To handle such fonts, we just ignore
 956        * the length for the last subtable. */
 957       hb_sanitize_with_object_t with (c, i < count - 1 ? st : (const SubTable *) nullptr);
 958
 959       if (unlikely (!st->sanitize (c)))
 960         return_trace (false);
 961
 962       st = &StructAfter<SubTable> (*st);
 963     }
 964
 965     return_trace (true);
 966   }
 967 };
 968
 969 struct kerx : KerxTable<kerx>
 970 {
 971   friend struct KerxTable<kerx>;
 972
 973   static constexpr hb_tag_t tableTag = HB_AAT_TAG_kerx;
 974   static constexpr unsigned minVersion = 2u;
 975
 976   typedef KerxSubTableHeader SubTableHeader;
 977   typedef SubTableHeader::Types Types;
 978   typedef KerxSubTable SubTable;
 979
 980   bool has_data () const { return version; }
 981
 982   protected:
 983   HBUINT16      version;        /* The version number of the extended kerning table
 984                                  * (currently 2, 3, or 4). */
 985   HBUINT16      unused;         /* Set to 0. */
 986   HBUINT32      tableCount;     /* The number of subtables included in the extended kerning
 987                                  * table. */
 988   SubTable      firstSubTable;  /* Subtables. */
 989 /*subtableGlyphCoverageArray*/  /* Only if version >= 3. We don't use. */
 990
 991   public:
 992   DEFINE_SIZE_MIN (8);
 993 };
 994
 995
 996 } /* namespace AAT */
 997
 998
 999 #endif /* HB_AAT_LAYOUT_KERX_TABLE_HH */