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