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   HBGlyphID     left;
  86   HBGlyphID     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     {
 233       return Format1EntryT::performAction (entry);
 234     }
 235     void transition (StateTableDriver<Types, EntryData> *driver,
 236                      const Entry<EntryData> &entry)
 237     {
 238       hb_buffer_t *buffer = driver->buffer;
 239       unsigned int flags = entry.flags;
 240
 241       if (flags & Format1EntryT::Reset)
 242         depth = 0;
 243
 244       if (flags & Format1EntryT::Push)
 245       {
 246         if (likely (depth < ARRAY_LENGTH (stack)))
 247           stack[depth++] = buffer->idx;
 248         else
 249           depth = 0; /* Probably not what CoreText does, but better? */
 250       }
 251
 252       if (Format1EntryT::performAction (entry) && depth)
 253       {
 254         unsigned int tuple_count = hb_max (1u, table->header.tuple_count ());
 255
 256         unsigned int kern_idx = Format1EntryT::kernActionIndex (entry);
 257         kern_idx = Types::byteOffsetToIndex (kern_idx, &table->machine, kernAction.arrayZ);
 258         const FWORD *actions = &kernAction[kern_idx];
 259         if (!c->sanitizer.check_array (actions, depth, tuple_count))
 260         {
 261           depth = 0;
 262           return;
 263         }
 264
 265         hb_mask_t kern_mask = c->plan->kern_mask;
 266
 267         /* From Apple 'kern' spec:
 268          * "Each pops one glyph from the kerning stack and applies the kerning value to it.
 269          * The end of the list is marked by an odd value... */
 270         bool last = false;
 271         while (!last && depth)
 272         {
 273           unsigned int idx = stack[--depth];
 274           int v = *actions;
 275           actions += tuple_count;
 276           if (idx >= buffer->len) continue;
 277
 278           /* "The end of the list is marked by an odd value..." */
 279           last = v & 1;
 280           v &= ~1;
 281
 282           hb_glyph_position_t &o = buffer->pos[idx];
 283
 284           if (HB_DIRECTION_IS_HORIZONTAL (buffer->props.direction))
 285           {
 286             if (crossStream)
 287             {
 288               /* The following flag is undocumented in the spec, but described
 289                * in the 'kern' table example. */
 290               if (v == -0x8000)
 291               {
 292                 o.attach_type() = ATTACH_TYPE_NONE;
 293                 o.attach_chain() = 0;
 294                 o.y_offset = 0;
 295               }
 296               else if (o.attach_type())
 297               {
 298                 o.y_offset += c->font->em_scale_y (v);
 299                 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 300               }
 301             }
 302             else if (buffer->info[idx].mask & kern_mask)
 303             {
 304               o.x_advance += c->font->em_scale_x (v);
 305               o.x_offset += c->font->em_scale_x (v);
 306             }
 307           }
 308           else
 309           {
 310             if (crossStream)
 311             {
 312               /* CoreText doesn't do crossStream kerning in vertical.  We do. */
 313               if (v == -0x8000)
 314               {
 315                 o.attach_type() = ATTACH_TYPE_NONE;
 316                 o.attach_chain() = 0;
 317                 o.x_offset = 0;
 318               }
 319               else if (o.attach_type())
 320               {
 321                 o.x_offset += c->font->em_scale_x (v);
 322                 buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 323               }
 324             }
 325             else if (buffer->info[idx].mask & kern_mask)
 326             {
 327               o.y_advance += c->font->em_scale_y (v);
 328               o.y_offset += c->font->em_scale_y (v);
 329             }
 330           }
 331         }
 332       }
 333     }
 334
 335     private:
 336     hb_aat_apply_context_t *c;
 337     const KerxSubTableFormat1 *table;
 338     const UnsizedArrayOf<FWORD> &kernAction;
 339     unsigned int stack[8];
 340     unsigned int depth;
 341     bool crossStream;
 342   };
 343
 344   bool apply (hb_aat_apply_context_t *c) const
 345   {
 346     TRACE_APPLY (this);
 347
 348     if (!c->plan->requested_kerning &&
 349         !(header.coverage & header.CrossStream))
 350       return false;
 351
 352     driver_context_t dc (this, c);
 353
 354     StateTableDriver<Types, EntryData> driver (machine, c->buffer, c->font->face);
 355     driver.drive (&dc);
 356
 357     return_trace (true);
 358   }
 359
 360   bool sanitize (hb_sanitize_context_t *c) const
 361   {
 362     TRACE_SANITIZE (this);
 363     /* The rest of array sanitizations are done at run-time. */
 364     return_trace (likely (c->check_struct (this) &&
 365                           machine.sanitize (c)));
 366   }
 367
 368   protected:
 369   KernSubTableHeader                            header;
 370   StateTable<Types, EntryData>                  machine;
 371   NNOffsetTo<UnsizedArrayOf<FWORD>, HBUINT>     kernAction;
 372   public:
 373   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 5 * sizeof (HBUINT));
 374 };
 375
 376 template <typename KernSubTableHeader>
 377 struct KerxSubTableFormat2
 378 {
 379   typedef typename KernSubTableHeader::Types Types;
 380   typedef typename Types::HBUINT HBUINT;
 381
 382   int get_kerning (hb_codepoint_t left, hb_codepoint_t right,
 383                    hb_aat_apply_context_t *c) const
 384   {
 385     unsigned int num_glyphs = c->sanitizer.get_num_glyphs ();
 386     unsigned int l = (this+leftClassTable).get_class (left, num_glyphs, 0);
 387     unsigned int r = (this+rightClassTable).get_class (right, num_glyphs, 0);
 388
 389     const UnsizedArrayOf<FWORD> &arrayZ = this+array;
 390     unsigned int kern_idx = l + r;
 391     kern_idx = Types::offsetToIndex (kern_idx, this, arrayZ.arrayZ);
 392     const FWORD *v = &arrayZ[kern_idx];
 393     if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 394
 395     return kerxTupleKern (*v, header.tuple_count (), this, c);
 396   }
 397
 398   bool apply (hb_aat_apply_context_t *c) const
 399   {
 400     TRACE_APPLY (this);
 401
 402     if (!c->plan->requested_kerning)
 403       return false;
 404
 405     if (header.coverage & header.Backwards)
 406       return false;
 407
 408     accelerator_t accel (*this, c);
 409     hb_kern_machine_t<accelerator_t> machine (accel, header.coverage & header.CrossStream);
 410     machine.kern (c->font, c->buffer, c->plan->kern_mask);
 411
 412     return_trace (true);
 413   }
 414
 415   struct accelerator_t
 416   {
 417     const KerxSubTableFormat2 &table;
 418     hb_aat_apply_context_t *c;
 419
 420     accelerator_t (const KerxSubTableFormat2 &table_,
 421                    hb_aat_apply_context_t *c_) :
 422                      table (table_), c (c_) {}
 423
 424     int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 425     { return table.get_kerning (left, right, c); }
 426   };
 427
 428   bool sanitize (hb_sanitize_context_t *c) const
 429   {
 430     TRACE_SANITIZE (this);
 431     return_trace (likely (c->check_struct (this) &&
 432                           leftClassTable.sanitize (c, this) &&
 433                           rightClassTable.sanitize (c, this) &&
 434                           c->check_range (this, array)));
 435   }
 436
 437   protected:
 438   KernSubTableHeader    header;
 439   HBUINT                rowWidth;       /* The width, in bytes, of a row in the table. */
 440   NNOffsetTo<typename Types::ClassTypeWide, HBUINT>
 441                         leftClassTable; /* Offset from beginning of this subtable to
 442                                          * left-hand class table. */
 443   NNOffsetTo<typename Types::ClassTypeWide, HBUINT>
 444                         rightClassTable;/* Offset from beginning of this subtable to
 445                                          * right-hand class table. */
 446   NNOffsetTo<UnsizedArrayOf<FWORD>, HBUINT>
 447                          array;         /* Offset from beginning of this subtable to
 448                                          * the start of the kerning array. */
 449   public:
 450   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 4 * sizeof (HBUINT));
 451 };
 452
 453 template <typename KernSubTableHeader>
 454 struct KerxSubTableFormat4
 455 {
 456   typedef ExtendedTypes Types;
 457
 458   struct EntryData
 459   {
 460     HBUINT16    ankrActionIndex;/* Either 0xFFFF (for no action) or the index of
 461                                  * the action to perform. */
 462     public:
 463     DEFINE_SIZE_STATIC (2);
 464   };
 465
 466   struct driver_context_t
 467   {
 468     static constexpr bool in_place = true;
 469     enum Flags
 470     {
 471       Mark              = 0x8000,       /* If set, remember this glyph as the marked glyph. */
 472       DontAdvance       = 0x4000,       /* If set, don't advance to the next glyph before
 473                                          * going to the new state. */
 474       Reserved          = 0x3FFF,       /* Not used; set to 0. */
 475     };
 476
 477     enum SubTableFlags
 478     {
 479       ActionType        = 0xC0000000,   /* A two-bit field containing the action type. */
 480       Unused            = 0x3F000000,   /* Unused - must be zero. */
 481       Offset            = 0x00FFFFFF,   /* Masks the offset in bytes from the beginning
 482                                          * of the subtable to the beginning of the control
 483                                          * point table. */
 484     };
 485
 486     driver_context_t (const KerxSubTableFormat4 *table,
 487                              hb_aat_apply_context_t *c_) :
 488         c (c_),
 489         action_type ((table->flags & ActionType) >> 30),
 490         ankrData ((HBUINT16 *) ((const char *) &table->machine + (table->flags & Offset))),
 491         mark_set (false),
 492         mark (0) {}
 493
 494     bool is_actionable (StateTableDriver<Types, EntryData> *driver HB_UNUSED,
 495                         const Entry<EntryData> &entry)
 496     {
 497       return entry.data.ankrActionIndex != 0xFFFF;
 498     }
 499     void transition (StateTableDriver<Types, EntryData> *driver,
 500                      const Entry<EntryData> &entry)
 501     {
 502       hb_buffer_t *buffer = driver->buffer;
 503
 504       if (mark_set && entry.data.ankrActionIndex != 0xFFFF && buffer->idx < buffer->len)
 505       {
 506         hb_glyph_position_t &o = buffer->cur_pos();
 507         switch (action_type)
 508         {
 509           case 0: /* Control Point Actions.*/
 510           {
 511             /* indexed into glyph outline. */
 512             const HBUINT16 *data = &ankrData[entry.data.ankrActionIndex];
 513             if (!c->sanitizer.check_array (data, 2)) return;
 514             HB_UNUSED unsigned int markControlPoint = *data++;
 515             HB_UNUSED unsigned int currControlPoint = *data++;
 516             hb_position_t markX = 0;
 517             hb_position_t markY = 0;
 518             hb_position_t currX = 0;
 519             hb_position_t currY = 0;
 520             if (!c->font->get_glyph_contour_point_for_origin (c->buffer->info[mark].codepoint,
 521                                                               markControlPoint,
 522                                                               HB_DIRECTION_LTR /*XXX*/,
 523                                                               &markX, &markY) ||
 524                 !c->font->get_glyph_contour_point_for_origin (c->buffer->cur ().codepoint,
 525                                                               currControlPoint,
 526                                                               HB_DIRECTION_LTR /*XXX*/,
 527                                                               &currX, &currY))
 528               return;
 529
 530             o.x_offset = markX - currX;
 531             o.y_offset = markY - currY;
 532           }
 533           break;
 534
 535           case 1: /* Anchor Point Actions. */
 536           {
 537            /* Indexed into 'ankr' table. */
 538             const HBUINT16 *data = &ankrData[entry.data.ankrActionIndex];
 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             const FWORD *data = (const FWORD *) &ankrData[entry.data.ankrActionIndex];
 557             if (!c->sanitizer.check_array (data, 4)) return;
 558             int markX = *data++;
 559             int markY = *data++;
 560             int currX = *data++;
 561             int currY = *data++;
 562
 563             o.x_offset = c->font->em_scale_x (markX) - c->font->em_scale_x (currX);
 564             o.y_offset = c->font->em_scale_y (markY) - c->font->em_scale_y (currY);
 565           }
 566           break;
 567         }
 568         o.attach_type() = ATTACH_TYPE_MARK;
 569         o.attach_chain() = (int) mark - (int) buffer->idx;
 570         buffer->scratch_flags |= HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT;
 571       }
 572
 573       if (entry.flags & Mark)
 574       {
 575         mark_set = true;
 576         mark = buffer->idx;
 577       }
 578     }
 579
 580     private:
 581     hb_aat_apply_context_t *c;
 582     unsigned int action_type;
 583     const HBUINT16 *ankrData;
 584     bool mark_set;
 585     unsigned int mark;
 586   };
 587
 588   bool apply (hb_aat_apply_context_t *c) const
 589   {
 590     TRACE_APPLY (this);
 591
 592     driver_context_t dc (this, c);
 593
 594     StateTableDriver<Types, EntryData> driver (machine, c->buffer, c->font->face);
 595     driver.drive (&dc);
 596
 597     return_trace (true);
 598   }
 599
 600   bool sanitize (hb_sanitize_context_t *c) const
 601   {
 602     TRACE_SANITIZE (this);
 603     /* The rest of array sanitizations are done at run-time. */
 604     return_trace (likely (c->check_struct (this) &&
 605                           machine.sanitize (c)));
 606   }
 607
 608   protected:
 609   KernSubTableHeader            header;
 610   StateTable<Types, EntryData>  machine;
 611   HBUINT32                      flags;
 612   public:
 613   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 20);
 614 };
 615
 616 template <typename KernSubTableHeader>
 617 struct KerxSubTableFormat6
 618 {
 619   enum Flags
 620   {
 621     ValuesAreLong       = 0x00000001,
 622   };
 623
 624   bool is_long () const { return flags & ValuesAreLong; }
 625
 626   int get_kerning (hb_codepoint_t left, hb_codepoint_t right,
 627                           hb_aat_apply_context_t *c) const
 628   {
 629     unsigned int num_glyphs = c->sanitizer.get_num_glyphs ();
 630     if (is_long ())
 631     {
 632       const typename U::Long &t = u.l;
 633       unsigned int l = (this+t.rowIndexTable).get_value_or_null (left, num_glyphs);
 634       unsigned int r = (this+t.columnIndexTable).get_value_or_null (right, num_glyphs);
 635       unsigned int offset = l + r;
 636       if (unlikely (offset < l)) return 0; /* Addition overflow. */
 637       if (unlikely (hb_unsigned_mul_overflows (offset, sizeof (FWORD32)))) return 0;
 638       const FWORD32 *v = &StructAtOffset<FWORD32> (&(this+t.array), offset * sizeof (FWORD32));
 639       if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 640       return kerxTupleKern (*v, header.tuple_count (), &(this+vector), c);
 641     }
 642     else
 643     {
 644       const typename U::Short &t = u.s;
 645       unsigned int l = (this+t.rowIndexTable).get_value_or_null (left, num_glyphs);
 646       unsigned int r = (this+t.columnIndexTable).get_value_or_null (right, num_glyphs);
 647       unsigned int offset = l + r;
 648       const FWORD *v = &StructAtOffset<FWORD> (&(this+t.array), offset * sizeof (FWORD));
 649       if (unlikely (!v->sanitize (&c->sanitizer))) return 0;
 650       return kerxTupleKern (*v, header.tuple_count (), &(this+vector), c);
 651     }
 652   }
 653
 654   bool apply (hb_aat_apply_context_t *c) const
 655   {
 656     TRACE_APPLY (this);
 657
 658     if (!c->plan->requested_kerning)
 659       return false;
 660
 661     if (header.coverage & header.Backwards)
 662       return false;
 663
 664     accelerator_t accel (*this, c);
 665     hb_kern_machine_t<accelerator_t> machine (accel, header.coverage & header.CrossStream);
 666     machine.kern (c->font, c->buffer, c->plan->kern_mask);
 667
 668     return_trace (true);
 669   }
 670
 671   bool sanitize (hb_sanitize_context_t *c) const
 672   {
 673     TRACE_SANITIZE (this);
 674     return_trace (likely (c->check_struct (this) &&
 675                           (is_long () ?
 676                            (
 677                              u.l.rowIndexTable.sanitize (c, this) &&
 678                              u.l.columnIndexTable.sanitize (c, this) &&
 679                              c->check_range (this, u.l.array)
 680                            ) : (
 681                              u.s.rowIndexTable.sanitize (c, this) &&
 682                              u.s.columnIndexTable.sanitize (c, this) &&
 683                              c->check_range (this, u.s.array)
 684                            )) &&
 685                           (header.tuple_count () == 0 ||
 686                            c->check_range (this, vector))));
 687   }
 688
 689   struct accelerator_t
 690   {
 691     const KerxSubTableFormat6 &table;
 692     hb_aat_apply_context_t *c;
 693
 694     accelerator_t (const KerxSubTableFormat6 &table_,
 695                    hb_aat_apply_context_t *c_) :
 696                      table (table_), c (c_) {}
 697
 698     int get_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 699     { return table.get_kerning (left, right, c); }
 700   };
 701
 702   protected:
 703   KernSubTableHeader            header;
 704   HBUINT32                      flags;
 705   HBUINT16                      rowCount;
 706   HBUINT16                      columnCount;
 707   union U
 708   {
 709     struct Long
 710     {
 711       LNNOffsetTo<Lookup<HBUINT32>>             rowIndexTable;
 712       LNNOffsetTo<Lookup<HBUINT32>>             columnIndexTable;
 713       LNNOffsetTo<UnsizedArrayOf<FWORD32>>      array;
 714     } l;
 715     struct Short
 716     {
 717       LNNOffsetTo<Lookup<HBUINT16>>             rowIndexTable;
 718       LNNOffsetTo<Lookup<HBUINT16>>             columnIndexTable;
 719       LNNOffsetTo<UnsizedArrayOf<FWORD>>        array;
 720     } s;
 721   } u;
 722   LNNOffsetTo<UnsizedArrayOf<FWORD>>    vector;
 723   public:
 724   DEFINE_SIZE_STATIC (KernSubTableHeader::static_size + 24);
 725 };
 726
 727
 728 struct KerxSubTableHeader
 729 {
 730   typedef ExtendedTypes Types;
 731
 732   unsigned   tuple_count () const { return tupleCount; }
 733   bool     is_horizontal () const { return !(coverage & Vertical); }
 734
 735   enum Coverage
 736   {
 737     Vertical    = 0x80000000u,  /* Set if table has vertical kerning values. */
 738     CrossStream = 0x40000000u,  /* Set if table has cross-stream kerning values. */
 739     Variation   = 0x20000000u,  /* Set if table has variation kerning values. */
 740     Backwards   = 0x10000000u,  /* If clear, process the glyphs forwards, that
 741                                  * is, from first to last in the glyph stream.
 742                                  * If we, process them from last to first.
 743                                  * This flag only applies to state-table based
 744                                  * 'kerx' subtables (types 1 and 4). */
 745     Reserved    = 0x0FFFFF00u,  /* Reserved, set to zero. */
 746     SubtableType= 0x000000FFu,  /* Subtable type. */
 747   };
 748
 749   bool sanitize (hb_sanitize_context_t *c) const
 750   {
 751     TRACE_SANITIZE (this);
 752     return_trace (likely (c->check_struct (this)));
 753   }
 754
 755   public:
 756   HBUINT32      length;
 757   HBUINT32      coverage;
 758   HBUINT32      tupleCount;
 759   public:
 760   DEFINE_SIZE_STATIC (12);
 761 };
 762
 763 struct KerxSubTable
 764 {
 765   friend struct kerx;
 766
 767   unsigned int get_size () const { return u.header.length; }
 768   unsigned int get_type () const { return u.header.coverage & u.header.SubtableType; }
 769
 770   template <typename context_t, typename ...Ts>
 771   typename context_t::return_t dispatch (context_t *c, Ts&&... ds) const
 772   {
 773     unsigned int subtable_type = get_type ();
 774     TRACE_DISPATCH (this, subtable_type);
 775     switch (subtable_type) {
 776     case 0:     return_trace (c->dispatch (u.format0, hb_forward<Ts> (ds)...));
 777     case 1:     return_trace (c->dispatch (u.format1, hb_forward<Ts> (ds)...));
 778     case 2:     return_trace (c->dispatch (u.format2, hb_forward<Ts> (ds)...));
 779     case 4:     return_trace (c->dispatch (u.format4, hb_forward<Ts> (ds)...));
 780     case 6:     return_trace (c->dispatch (u.format6, hb_forward<Ts> (ds)...));
 781     default:    return_trace (c->default_return_value ());
 782     }
 783   }
 784
 785   bool sanitize (hb_sanitize_context_t *c) const
 786   {
 787     TRACE_SANITIZE (this);
 788     if (!u.header.sanitize (c) ||
 789         u.header.length <= u.header.static_size ||
 790         !c->check_range (this, u.header.length))
 791       return_trace (false);
 792
 793     return_trace (dispatch (c));
 794   }
 795
 796   public:
 797   union {
 798   KerxSubTableHeader                            header;
 799   KerxSubTableFormat0<KerxSubTableHeader>       format0;
 800   KerxSubTableFormat1<KerxSubTableHeader>       format1;
 801   KerxSubTableFormat2<KerxSubTableHeader>       format2;
 802   KerxSubTableFormat4<KerxSubTableHeader>       format4;
 803   KerxSubTableFormat6<KerxSubTableHeader>       format6;
 804   } u;
 805   public:
 806   DEFINE_SIZE_MIN (12);
 807 };
 808
 809
 810 /*
 811  * The 'kerx' Table
 812  */
 813
 814 template <typename T>
 815 struct KerxTable
 816 {
 817   /* https://en.wikipedia.org/wiki/Curiously_recurring_template_pattern */
 818   const T* thiz () const { return static_cast<const T *> (this); }
 819
 820   bool has_state_machine () const
 821   {
 822     typedef typename T::SubTable SubTable;
 823
 824     const SubTable *st = &thiz()->firstSubTable;
 825     unsigned int count = thiz()->tableCount;
 826     for (unsigned int i = 0; i < count; i++)
 827     {
 828       if (st->get_type () == 1)
 829         return true;
 830       st = &StructAfter<SubTable> (*st);
 831     }
 832     return false;
 833   }
 834
 835   bool has_cross_stream () const
 836   {
 837     typedef typename T::SubTable SubTable;
 838
 839     const SubTable *st = &thiz()->firstSubTable;
 840     unsigned int count = thiz()->tableCount;
 841     for (unsigned int i = 0; i < count; i++)
 842     {
 843       if (st->u.header.coverage & st->u.header.CrossStream)
 844         return true;
 845       st = &StructAfter<SubTable> (*st);
 846     }
 847     return false;
 848   }
 849
 850   int get_h_kerning (hb_codepoint_t left, hb_codepoint_t right) const
 851   {
 852     typedef typename T::SubTable SubTable;
 853
 854     int v = 0;
 855     const SubTable *st = &thiz()->firstSubTable;
 856     unsigned int count = thiz()->tableCount;
 857     for (unsigned int i = 0; i < count; i++)
 858     {
 859       if ((st->u.header.coverage & (st->u.header.Variation | st->u.header.CrossStream)) ||
 860           !st->u.header.is_horizontal ())
 861         continue;
 862       v += st->get_kerning (left, right);
 863       st = &StructAfter<SubTable> (*st);
 864     }
 865     return v;
 866   }
 867
 868   bool apply (AAT::hb_aat_apply_context_t *c) const
 869   {
 870     typedef typename T::SubTable SubTable;
 871
 872     bool ret = false;
 873     bool seenCrossStream = false;
 874     c->set_lookup_index (0);
 875     const SubTable *st = &thiz()->firstSubTable;
 876     unsigned int count = thiz()->tableCount;
 877     for (unsigned int i = 0; i < count; i++)
 878     {
 879       bool reverse;
 880
 881       if (!T::Types::extended && (st->u.header.coverage & st->u.header.Variation))
 882         goto skip;
 883
 884       if (HB_DIRECTION_IS_HORIZONTAL (c->buffer->props.direction) != st->u.header.is_horizontal ())
 885         goto skip;
 886
 887       reverse = bool (st->u.header.coverage & st->u.header.Backwards) !=
 888                 HB_DIRECTION_IS_BACKWARD (c->buffer->props.direction);
 889
 890       if (!c->buffer->message (c->font, "start %c%c%c%c subtable %d", HB_UNTAG (thiz()->tableTag), c->lookup_index))
 891         goto skip;
 892
 893       if (!seenCrossStream &&
 894           (st->u.header.coverage & st->u.header.CrossStream))
 895       {
 896         /* Attach all glyphs into a chain. */
 897         seenCrossStream = true;
 898         hb_glyph_position_t *pos = c->buffer->pos;
 899         unsigned int count = c->buffer->len;
 900         for (unsigned int i = 0; i < count; i++)
 901         {
 902           pos[i].attach_type() = ATTACH_TYPE_CURSIVE;
 903           pos[i].attach_chain() = HB_DIRECTION_IS_FORWARD (c->buffer->props.direction) ? -1 : +1;
 904           /* We intentionally don't set HB_BUFFER_SCRATCH_FLAG_HAS_GPOS_ATTACHMENT,
 905            * since there needs to be a non-zero attachment for post-positioning to
 906            * be needed. */
 907         }
 908       }
 909
 910       if (reverse)
 911         c->buffer->reverse ();
 912
 913       {
 914         /* See comment in sanitize() for conditional here. */
 915         hb_sanitize_with_object_t with (&c->sanitizer, i < count - 1 ? st : (const SubTable *) nullptr);
 916         ret |= st->dispatch (c);
 917       }
 918
 919       if (reverse)
 920         c->buffer->reverse ();
 921
 922       (void) c->buffer->message (c->font, "end %c%c%c%c subtable %d", HB_UNTAG (thiz()->tableTag), c->lookup_index);
 923
 924     skip:
 925       st = &StructAfter<SubTable> (*st);
 926       c->set_lookup_index (c->lookup_index + 1);
 927     }
 928
 929     return ret;
 930   }
 931
 932   bool sanitize (hb_sanitize_context_t *c) const
 933   {
 934     TRACE_SANITIZE (this);
 935     if (unlikely (!thiz()->version.sanitize (c) ||
 936                   (unsigned) thiz()->version < (unsigned) T::minVersion ||
 937                   !thiz()->tableCount.sanitize (c)))
 938       return_trace (false);
 939
 940     typedef typename T::SubTable SubTable;
 941
 942     const SubTable *st = &thiz()->firstSubTable;
 943     unsigned int count = thiz()->tableCount;
 944     for (unsigned int i = 0; i < count; i++)
 945     {
 946       if (unlikely (!st->u.header.sanitize (c)))
 947         return_trace (false);
 948       /* OpenType kern table has 2-byte subtable lengths.  That's limiting.
 949        * MS implementation also only supports one subtable, of format 0,
 950        * anyway.  Certain versions of some fonts, like Calibry, contain
 951        * kern subtable that exceeds 64kb.  Looks like, the subtable length
 952        * is simply ignored.  Which makes sense.  It's only needed if you
 953        * have multiple subtables.  To handle such fonts, we just ignore
 954        * the length for the last subtable. */
 955       hb_sanitize_with_object_t with (c, i < count - 1 ? st : (const SubTable *) nullptr);
 956
 957       if (unlikely (!st->sanitize (c)))
 958         return_trace (false);
 959
 960       st = &StructAfter<SubTable> (*st);
 961     }
 962
 963     return_trace (true);
 964   }
 965 };
 966
 967 struct kerx : KerxTable<kerx>
 968 {
 969   friend struct KerxTable<kerx>;
 970
 971   static constexpr hb_tag_t tableTag = HB_AAT_TAG_kerx;
 972   static constexpr unsigned minVersion = 2u;
 973
 974   typedef KerxSubTableHeader SubTableHeader;
 975   typedef SubTableHeader::Types Types;
 976   typedef KerxSubTable SubTable;
 977
 978   bool has_data () const { return version; }
 979
 980   protected:
 981   HBUINT16      version;        /* The version number of the extended kerning table
 982                                  * (currently 2, 3, or 4). */
 983   HBUINT16      unused;         /* Set to 0. */
 984   HBUINT32      tableCount;     /* The number of subtables included in the extended kerning
 985                                  * table. */
 986   SubTable      firstSubTable;  /* Subtables. */
 987 /*subtableGlyphCoverageArray*/  /* Only if version >= 3. We don't use. */
 988
 989   public:
 990   DEFINE_SIZE_MIN (8);
 991 };
 992
 993
 994 } /* namespace AAT */
 995
 996
 997 #endif /* HB_AAT_LAYOUT_KERX_TABLE_HH */