src/hb-ot-glyf-table.hh

   1 /*
   2  * Copyright © 2015  Google, Inc.
   3  * Copyright © 2019  Adobe Inc.
   4  * Copyright © 2019  Ebrahim Byagowi
   5  *
   6  *  This is part of HarfBuzz, a text shaping library.
   7  *
   8  * Permission is hereby granted, without written agreement and without
   9  * license or royalty fees, to use, copy, modify, and distribute this
  10  * software and its documentation for any purpose, provided that the
  11  * above copyright notice and the following two paragraphs appear in
  12  * all copies of this software.
  13  *
  14  * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
  15  * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
  16  * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
  17  * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
  18  * DAMAGE.
  19  *
  20  * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
  21  * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
  22  * FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS
  23  * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
  24  * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
  25  *
  26  * Google Author(s): Behdad Esfahbod, Garret Rieger, Roderick Sheeter
  27  * Adobe Author(s): Michiharu Ariza
  28  */
  29
  30 #ifndef HB_OT_GLYF_TABLE_HH
  31 #define HB_OT_GLYF_TABLE_HH
  32
  33 #include "hb-open-type.hh"
  34 #include "hb-ot-head-table.hh"
  35 #include "hb-ot-hmtx-table.hh"
  36 #include "hb-ot-var-gvar-table.hh"
  37
  38 #include <float.h>
  39
  40 namespace OT {
  41
  42
  43 /*
  44  * loca -- Index to Location
  45  * https://docs.microsoft.com/en-us/typography/opentype/spec/loca
  46  */
  47 #define HB_OT_TAG_loca HB_TAG('l','o','c','a')
  48
  49
  50 struct loca
  51 {
  52   friend struct glyf;
  53
  54   static constexpr hb_tag_t tableTag = HB_OT_TAG_loca;
  55
  56   bool sanitize (hb_sanitize_context_t *c HB_UNUSED) const
  57   {
  58     TRACE_SANITIZE (this);
  59     return_trace (true);
  60   }
  61
  62   protected:
  63   UnsizedArrayOf<HBUINT8>
  64                 dataZ;  /* Location data. */
  65   public:
  66   DEFINE_SIZE_MIN (0);  /* In reality, this is UNBOUNDED() type; but since we always
  67                          * check the size externally, allow Null() object of it by
  68                          * defining it _MIN instead. */
  69 };
  70
  71
  72 /*
  73  * glyf -- TrueType Glyph Data
  74  * https://docs.microsoft.com/en-us/typography/opentype/spec/glyf
  75  */
  76 #define HB_OT_TAG_glyf HB_TAG('g','l','y','f')
  77
  78
  79 struct glyf
  80 {
  81   static constexpr hb_tag_t tableTag = HB_OT_TAG_glyf;
  82
  83   bool sanitize (hb_sanitize_context_t *c HB_UNUSED) const
  84   {
  85     TRACE_SANITIZE (this);
  86     /* Runtime checks as eager sanitizing each glyph is costy */
  87     return_trace (true);
  88   }
  89
  90   template<typename Iterator,
  91            hb_requires (hb_is_source_of (Iterator, unsigned int))>
  92   static bool
  93   _add_loca_and_head (hb_subset_plan_t * plan, Iterator padded_offsets)
  94   {
  95     unsigned max_offset = + padded_offsets | hb_reduce(hb_add, 0);
  96     unsigned num_offsets = padded_offsets.len () + 1;
  97     bool use_short_loca = max_offset < 0x1FFFF;
  98     unsigned entry_size = use_short_loca ? 2 : 4;
  99     char *loca_prime_data = (char *) calloc (entry_size, num_offsets);
 100
 101     if (unlikely (!loca_prime_data)) return false;
 102
 103     DEBUG_MSG (SUBSET, nullptr, "loca entry_size %d num_offsets %d "
 104                                 "max_offset %d size %d",
 105                entry_size, num_offsets, max_offset, entry_size * num_offsets);
 106
 107     if (use_short_loca)
 108       _write_loca (padded_offsets, 1, hb_array ((HBUINT16*) loca_prime_data, num_offsets));
 109     else
 110       _write_loca (padded_offsets, 0, hb_array ((HBUINT32*) loca_prime_data, num_offsets));
 111
 112     hb_blob_t * loca_blob = hb_blob_create (loca_prime_data,
 113                                             entry_size * num_offsets,
 114                                             HB_MEMORY_MODE_WRITABLE,
 115                                             loca_prime_data,
 116                                             free);
 117
 118     bool result = plan->add_table (HB_OT_TAG_loca, loca_blob)
 119                   && _add_head_and_set_loca_version (plan, use_short_loca);
 120
 121     hb_blob_destroy (loca_blob);
 122     return result;
 123   }
 124
 125   template<typename IteratorIn, typename IteratorOut,
 126            hb_requires (hb_is_source_of (IteratorIn, unsigned int)),
 127            hb_requires (hb_is_sink_of (IteratorOut, unsigned))>
 128   static void
 129   _write_loca (IteratorIn it, unsigned right_shift, IteratorOut dest)
 130   {
 131     unsigned int offset = 0;
 132     dest << 0;
 133     + it
 134     | hb_map ([=, &offset] (unsigned int padded_size)
 135               {
 136                 offset += padded_size;
 137                 DEBUG_MSG (SUBSET, nullptr, "loca entry offset %d", offset);
 138                 return offset >> right_shift;
 139               })
 140     | hb_sink (dest)
 141     ;
 142   }
 143
 144   /* requires source of SubsetGlyph complains the identifier isn't declared */
 145   template <typename Iterator>
 146   bool serialize (hb_serialize_context_t *c,
 147                   Iterator it,
 148                   const hb_subset_plan_t *plan)
 149   {
 150     TRACE_SERIALIZE (this);
 151     for (const auto &_ : it) _.serialize (c, plan);
 152     return_trace (true);
 153   }
 154
 155   /* Byte region(s) per glyph to output
 156      unpadded, hints removed if so requested
 157      If we fail to process a glyph we produce an empty (0-length) glyph */
 158   bool subset (hb_subset_context_t *c) const
 159   {
 160     TRACE_SUBSET (this);
 161
 162     glyf *glyf_prime = c->serializer->start_embed <glyf> ();
 163     if (unlikely (!c->serializer->check_success (glyf_prime))) return_trace (false);
 164
 165     hb_vector_t<SubsetGlyph> glyphs;
 166     _populate_subset_glyphs (c->plan, &glyphs);
 167
 168     glyf_prime->serialize (c->serializer, hb_iter (glyphs), c->plan);
 169
 170     auto padded_offsets =
 171     + hb_iter (glyphs)
 172     | hb_map (&SubsetGlyph::padded_size)
 173     ;
 174
 175     if (c->serializer->in_error ()) return_trace (false);
 176     return_trace (c->serializer->check_success (_add_loca_and_head (c->plan,
 177                                                                     padded_offsets)));
 178   }
 179
 180   template <typename SubsetGlyph>
 181   void
 182   _populate_subset_glyphs (const hb_subset_plan_t   *plan,
 183                            hb_vector_t<SubsetGlyph> *glyphs /* OUT */) const
 184   {
 185     OT::glyf::accelerator_t glyf;
 186     glyf.init (plan->source);
 187
 188     + hb_range (plan->num_output_glyphs ())
 189     | hb_map ([&] (hb_codepoint_t new_gid)
 190               {
 191                 SubsetGlyph subset_glyph = {0};
 192                 subset_glyph.new_gid = new_gid;
 193
 194                 /* should never fail: all old gids should be mapped */
 195                 if (!plan->old_gid_for_new_gid (new_gid, &subset_glyph.old_gid))
 196                   return subset_glyph;
 197
 198                 subset_glyph.source_glyph = glyf.glyph_for_gid (subset_glyph.old_gid, true);
 199                 if (plan->drop_hints) subset_glyph.drop_hints_bytes ();
 200                 else subset_glyph.dest_start = subset_glyph.source_glyph.get_bytes ();
 201
 202                 return subset_glyph;
 203               })
 204     | hb_sink (glyphs)
 205     ;
 206
 207     glyf.fini ();
 208   }
 209
 210   static bool
 211   _add_head_and_set_loca_version (hb_subset_plan_t *plan, bool use_short_loca)
 212   {
 213     hb_blob_t *head_blob = hb_sanitize_context_t ().reference_table<head> (plan->source);
 214     hb_blob_t *head_prime_blob = hb_blob_copy_writable_or_fail (head_blob);
 215     hb_blob_destroy (head_blob);
 216
 217     if (unlikely (!head_prime_blob))
 218       return false;
 219
 220     head *head_prime = (head *) hb_blob_get_data_writable (head_prime_blob, nullptr);
 221     head_prime->indexToLocFormat = use_short_loca ? 0 : 1;
 222     bool success = plan->add_table (HB_OT_TAG_head, head_prime_blob);
 223
 224     hb_blob_destroy (head_prime_blob);
 225     return success;
 226   }
 227
 228   struct CompositeGlyphChain
 229   {
 230     enum composite_glyph_flag_t
 231     {
 232       ARG_1_AND_2_ARE_WORDS =      0x0001,
 233       ARGS_ARE_XY_VALUES =         0x0002,
 234       ROUND_XY_TO_GRID =           0x0004,
 235       WE_HAVE_A_SCALE =            0x0008,
 236       MORE_COMPONENTS =            0x0020,
 237       WE_HAVE_AN_X_AND_Y_SCALE =   0x0040,
 238       WE_HAVE_A_TWO_BY_TWO =       0x0080,
 239       WE_HAVE_INSTRUCTIONS =       0x0100,
 240       USE_MY_METRICS =             0x0200,
 241       OVERLAP_COMPOUND =           0x0400,
 242       SCALED_COMPONENT_OFFSET =    0x0800,
 243       UNSCALED_COMPONENT_OFFSET =  0x1000
 244     };
 245
 246     unsigned int get_size () const
 247     {
 248       unsigned int size = min_size;
 249       /* arg1 and 2 are int16 */
 250       if (flags & ARG_1_AND_2_ARE_WORDS) size += 4;
 251       /* arg1 and 2 are int8 */
 252       else size += 2;
 253
 254       /* One x 16 bit (scale) */
 255       if (flags & WE_HAVE_A_SCALE) size += 2;
 256       /* Two x 16 bit (xscale, yscale) */
 257       else if (flags & WE_HAVE_AN_X_AND_Y_SCALE) size += 4;
 258       /* Four x 16 bit (xscale, scale01, scale10, yscale) */
 259       else if (flags & WE_HAVE_A_TWO_BY_TWO) size += 8;
 260
 261       return size;
 262     }
 263
 264     bool is_use_my_metrics () const { return   flags & USE_MY_METRICS; }
 265     bool is_anchored ()       const { return !(flags & ARGS_ARE_XY_VALUES); }
 266     void get_anchor_points (unsigned int &point1, unsigned int &point2) const
 267     {
 268       const HBUINT8 *p = &StructAfter<const HBUINT8> (glyphIndex);
 269       if (flags & ARG_1_AND_2_ARE_WORDS)
 270       {
 271         point1 = ((const HBUINT16 *) p)[0];
 272         point2 = ((const HBUINT16 *) p)[1];
 273       }
 274       else
 275       {
 276         point1 = p[0];
 277         point2 = p[1];
 278       }
 279     }
 280
 281     void transform_points (contour_point_vector_t &points) const
 282     {
 283       float matrix[4];
 284       contour_point_t trans;
 285       if (get_transformation (matrix, trans))
 286       {
 287         if (scaled_offsets ())
 288         {
 289           points.translate (trans);
 290           points.transform (matrix);
 291         }
 292         else
 293         {
 294           points.transform (matrix);
 295           points.translate (trans);
 296         }
 297       }
 298     }
 299
 300     protected:
 301     bool scaled_offsets () const
 302     { return (flags & (SCALED_COMPONENT_OFFSET | UNSCALED_COMPONENT_OFFSET)) == SCALED_COMPONENT_OFFSET; }
 303
 304     bool get_transformation (float (&matrix)[4], contour_point_t &trans) const
 305     {
 306       matrix[0] = matrix[3] = 1.f;
 307       matrix[1] = matrix[2] = 0.f;
 308
 309       int tx, ty;
 310       const HBINT8 *p = &StructAfter<const HBINT8> (glyphIndex);
 311       if (flags & ARG_1_AND_2_ARE_WORDS)
 312       {
 313         tx = *(const HBINT16 *) p;
 314         p += HBINT16::static_size;
 315         ty = *(const HBINT16 *) p;
 316         p += HBINT16::static_size;
 317       }
 318       else
 319       {
 320         tx = *p++;
 321         ty = *p++;
 322       }
 323       if (is_anchored ()) tx = ty = 0;
 324
 325       trans.init ((float) tx, (float) ty);
 326
 327       {
 328         const F2DOT14 *points = (const F2DOT14 *) p;
 329         if (flags & WE_HAVE_A_SCALE)
 330         {
 331           matrix[0] = matrix[3] = points[0].to_float ();
 332           return true;
 333         }
 334         else if (flags & WE_HAVE_AN_X_AND_Y_SCALE)
 335         {
 336           matrix[0] = points[0].to_float ();
 337           matrix[3] = points[1].to_float ();
 338           return true;
 339         }
 340         else if (flags & WE_HAVE_A_TWO_BY_TWO)
 341         {
 342           matrix[0] = points[0].to_float ();
 343           matrix[1] = points[1].to_float ();
 344           matrix[2] = points[2].to_float ();
 345           matrix[3] = points[3].to_float ();
 346           return true;
 347         }
 348       }
 349       return tx || ty;
 350     }
 351
 352     public:
 353     HBUINT16    flags;
 354     HBGlyphID   glyphIndex;
 355     public:
 356     DEFINE_SIZE_MIN (4);
 357   };
 358
 359   struct composite_iter_t : hb_iter_with_fallback_t<composite_iter_t, const CompositeGlyphChain &>
 360   {
 361     typedef const CompositeGlyphChain *__item_t__;
 362     composite_iter_t (hb_bytes_t glyph_, __item_t__ current_) :
 363       glyph (glyph_), current (current_)
 364     { if (!in_range (current)) current = nullptr; }
 365     composite_iter_t () : glyph (hb_bytes_t ()), current (nullptr) {}
 366
 367     const CompositeGlyphChain &__item__ () const { return *current; }
 368     bool __more__ () const { return current; }
 369     void __next__ ()
 370     {
 371       if (!(current->flags & CompositeGlyphChain::MORE_COMPONENTS)) { current = nullptr; return; }
 372
 373       const CompositeGlyphChain *possible = &StructAfter<CompositeGlyphChain,
 374                                                          CompositeGlyphChain> (*current);
 375       if (!in_range (possible)) { current = nullptr; return; }
 376       current = possible;
 377     }
 378     bool operator != (const composite_iter_t& o) const
 379     { return glyph != o.glyph || current != o.current; }
 380
 381     bool in_range (const CompositeGlyphChain *composite) const
 382     {
 383       return glyph.in_range (composite, CompositeGlyphChain::min_size)
 384           && glyph.in_range (composite, composite->get_size ());
 385     }
 386
 387     private:
 388     hb_bytes_t glyph;
 389     __item_t__ current;
 390   };
 391
 392   struct Glyph
 393   {
 394     private:
 395     struct GlyphHeader
 396     {
 397       bool has_data () const { return numberOfContours; }
 398
 399       bool get_extents (hb_font_t *font, hb_codepoint_t gid, hb_glyph_extents_t *extents) const
 400       {
 401         /* Undocumented rasterizer behavior: shift glyph to the left by (lsb - xMin), i.e., xMin = lsb */
 402         /* extents->x_bearing = hb_min (glyph_header.xMin, glyph_header.xMax); */
 403         extents->x_bearing = font->em_scale_x (font->face->table.hmtx->get_side_bearing (gid));
 404         extents->y_bearing = font->em_scale_y (hb_max (yMin, yMax));
 405         extents->width     = font->em_scale_x (hb_max (xMin, xMax) - hb_min (xMin, xMax));
 406         extents->height    = font->em_scale_y (hb_min (yMin, yMax) - hb_max (yMin, yMax));
 407
 408         return true;
 409       }
 410
 411       HBINT16   numberOfContours;
 412                         /* If the number of contours is
 413                          * greater than or equal to zero,
 414                          * this is a simple glyph; if negative,
 415                          * this is a composite glyph. */
 416       FWORD     xMin;   /* Minimum x for coordinate data. */
 417       FWORD     yMin;   /* Minimum y for coordinate data. */
 418       FWORD     xMax;   /* Maximum x for coordinate data. */
 419       FWORD     yMax;   /* Maximum y for coordinate data. */
 420       public:
 421       DEFINE_SIZE_STATIC (10);
 422     };
 423
 424     struct SimpleGlyph
 425     {
 426       const GlyphHeader &header;
 427       hb_bytes_t bytes;
 428       SimpleGlyph (const GlyphHeader &header_, hb_bytes_t bytes_) :
 429         header (header_), bytes (bytes_) {}
 430
 431       unsigned int instruction_len_offset () const
 432       { return GlyphHeader::static_size + 2 * header.numberOfContours; }
 433
 434       unsigned int length (unsigned int instruction_len) const
 435       { return instruction_len_offset () + 2 + instruction_len; }
 436
 437       unsigned int instructions_length () const
 438       {
 439         unsigned int instruction_length_offset = instruction_len_offset ();
 440         if (unlikely (instruction_length_offset + 2 > bytes.length)) return 0;
 441
 442         const HBUINT16 &instructionLength = StructAtOffset<HBUINT16> (&bytes, instruction_length_offset);
 443         /* Out of bounds of the current glyph */
 444         if (unlikely (length (instructionLength) > bytes.length)) return 0;
 445         return instructionLength;
 446       }
 447
 448       enum simple_glyph_flag_t
 449       {
 450         FLAG_ON_CURVE  = 0x01,
 451         FLAG_X_SHORT   = 0x02,
 452         FLAG_Y_SHORT   = 0x04,
 453         FLAG_REPEAT    = 0x08,
 454         FLAG_X_SAME    = 0x10,
 455         FLAG_Y_SAME    = 0x20,
 456         FLAG_RESERVED1 = 0x40,
 457         FLAG_RESERVED2 = 0x80
 458       };
 459
 460       const Glyph trim_padding () const
 461       {
 462         /* based on FontTools _g_l_y_f.py::trim */
 463         const char *glyph = bytes.arrayZ;
 464         const char *glyph_end = glyph + bytes.length;
 465         /* simple glyph w/contours, possibly trimmable */
 466         glyph += instruction_len_offset ();
 467
 468         if (unlikely (glyph + 2 >= glyph_end)) return Glyph ();
 469         unsigned int num_coordinates = StructAtOffset<HBUINT16> (glyph - 2, 0) + 1;
 470         unsigned int num_instructions = StructAtOffset<HBUINT16> (glyph, 0);
 471
 472         glyph += 2 + num_instructions;
 473         if (unlikely (glyph + 2 >= glyph_end)) return Glyph ();
 474
 475         unsigned int coord_bytes = 0;
 476         unsigned int coords_with_flags = 0;
 477         while (glyph < glyph_end)
 478         {
 479           uint8_t flag = *glyph;
 480           glyph++;
 481
 482           unsigned int repeat = 1;
 483           if (flag & FLAG_REPEAT)
 484           {
 485             if (unlikely (glyph >= glyph_end)) return Glyph ();
 486             repeat = *glyph + 1;
 487             glyph++;
 488           }
 489
 490           unsigned int xBytes, yBytes;
 491           xBytes = yBytes = 0;
 492           if (flag & FLAG_X_SHORT) xBytes = 1;
 493           else if ((flag & FLAG_X_SAME) == 0) xBytes = 2;
 494
 495           if (flag & FLAG_Y_SHORT) yBytes = 1;
 496           else if ((flag & FLAG_Y_SAME) == 0) yBytes = 2;
 497
 498           coord_bytes += (xBytes + yBytes) * repeat;
 499           coords_with_flags += repeat;
 500           if (coords_with_flags >= num_coordinates) break;
 501         }
 502
 503         if (unlikely (coords_with_flags != num_coordinates)) return Glyph ();
 504         return Glyph (bytes.sub_array (0, bytes.length + coord_bytes - (glyph_end - glyph)));
 505       }
 506
 507       /* zero instruction length */
 508       void drop_hints ()
 509       {
 510         GlyphHeader &glyph_header = const_cast<GlyphHeader &> (header);
 511         (HBUINT16 &) StructAtOffset<HBUINT16> (&glyph_header, instruction_len_offset ()) = 0;
 512       }
 513
 514       void drop_hints_bytes (hb_bytes_t &dest_start, hb_bytes_t &dest_end) const
 515       {
 516         unsigned int instructions_len = instructions_length ();
 517         unsigned int glyph_length = length (instructions_len);
 518         dest_start = bytes.sub_array (0, glyph_length - instructions_len);
 519         dest_end = bytes.sub_array (glyph_length, bytes.length - glyph_length);
 520       }
 521
 522       struct x_setter_t
 523       {
 524         void set (contour_point_t &point, float v) const { point.x = v; }
 525         bool is_short (uint8_t flag) const { return flag & FLAG_X_SHORT; }
 526         bool is_same  (uint8_t flag) const { return flag & FLAG_X_SAME; }
 527       };
 528
 529       struct y_setter_t
 530       {
 531         void set (contour_point_t &point, float v) const { point.y = v; }
 532         bool is_short (uint8_t flag) const { return flag & FLAG_Y_SHORT; }
 533         bool is_same  (uint8_t flag) const { return flag & FLAG_Y_SAME; }
 534       };
 535
 536       template <typename T>
 537       static bool read_points (const HBUINT8 *&p /* IN/OUT */,
 538                                contour_point_vector_t &points_ /* IN/OUT */,
 539                                const hb_bytes_t &bytes)
 540       {
 541         T coord_setter;
 542         float v = 0;
 543         for (unsigned int i = 0; i < points_.length - PHANTOM_COUNT; i++)
 544         {
 545           uint8_t flag = points_[i].flag;
 546           if (coord_setter.is_short (flag))
 547           {
 548             if (unlikely (!bytes.in_range (p))) return false;
 549             if (coord_setter.is_same (flag))
 550               v += *p++;
 551             else
 552               v -= *p++;
 553           }
 554           else
 555           {
 556             if (!coord_setter.is_same (flag))
 557             {
 558               if (unlikely (!bytes.in_range ((const HBUINT16 *) p))) return false;
 559               v += *(const HBINT16 *) p;
 560               p += HBINT16::static_size;
 561             }
 562           }
 563           coord_setter.set (points_[i], v);
 564         }
 565         return true;
 566       }
 567
 568       bool get_contour_points (contour_point_vector_t &points_ /* OUT */,
 569                                hb_vector_t<unsigned int> &end_points_ /* OUT */,
 570                                const bool phantom_only=false) const
 571       {
 572         const HBUINT16 *endPtsOfContours = &StructAfter<HBUINT16> (header);
 573         int num_contours = header.numberOfContours;
 574         if (unlikely (!bytes.in_range (&endPtsOfContours[num_contours + 1]))) return false;
 575         unsigned int num_points = endPtsOfContours[num_contours - 1] + 1;
 576
 577         points_.resize (num_points + PHANTOM_COUNT);
 578         for (unsigned int i = 0; i < points_.length; i++) points_[i].init ();
 579         if (phantom_only) return true;
 580
 581         /* Read simple glyph points if !phantom_only */
 582         end_points_.resize (num_contours);
 583
 584         for (int i = 0; i < num_contours; i++)
 585           end_points_[i] = endPtsOfContours[i];
 586
 587         /* Skip instructions */
 588         const HBUINT8 *p = &StructAtOffset<HBUINT8> (&endPtsOfContours[num_contours + 1],
 589                                                      endPtsOfContours[num_contours]);
 590
 591         /* Read flags */
 592         for (unsigned int i = 0; i < num_points; i++)
 593         {
 594           if (unlikely (!bytes.in_range (p))) return false;
 595           uint8_t flag = *p++;
 596           points_[i].flag = flag;
 597           if (flag & FLAG_REPEAT)
 598           {
 599             if (unlikely (!bytes.in_range (p))) return false;
 600             unsigned int repeat_count = *p++;
 601             while ((repeat_count-- > 0) && (++i < num_points))
 602               points_[i].flag = flag;
 603           }
 604         }
 605
 606         /* Read x & y coordinates */
 607         return (read_points<x_setter_t> (p, points_, bytes) &&
 608                 read_points<y_setter_t> (p, points_, bytes));
 609       }
 610     };
 611
 612     struct CompositeGlyph
 613     {
 614       const GlyphHeader &header;
 615       hb_bytes_t bytes;
 616       CompositeGlyph (const GlyphHeader &header_, hb_bytes_t bytes_) :
 617         header (header_), bytes (bytes_) {}
 618
 619       composite_iter_t get_iterator () const
 620       { return composite_iter_t (bytes, &StructAfter<CompositeGlyphChain, GlyphHeader> (header)); }
 621
 622       unsigned int instructions_length (hb_bytes_t bytes) const
 623       {
 624         unsigned int start = bytes.length;
 625         unsigned int end = bytes.length;
 626         const CompositeGlyphChain *last = nullptr;
 627         for (auto &item : get_iterator ())
 628           last = &item;
 629         if (unlikely (!last)) return 0;
 630
 631         if ((uint16_t) last->flags & CompositeGlyphChain::WE_HAVE_INSTRUCTIONS)
 632           start = (char *) last - &bytes + last->get_size ();
 633         if (unlikely (start > end)) return 0;
 634         return end - start;
 635       }
 636
 637       /* Trimming for composites not implemented.
 638        * If removing hints it falls out of that. */
 639       const Glyph trim_padding () const { return Glyph (bytes); }
 640
 641       /* remove WE_HAVE_INSTRUCTIONS flag from composite glyph */
 642       void drop_hints ()
 643       {
 644         for (const auto &_ : get_iterator ())
 645           *const_cast<OT::HBUINT16 *> (&_.flags) = (uint16_t) _.flags & ~OT::glyf::CompositeGlyphChain::WE_HAVE_INSTRUCTIONS;
 646       }
 647
 648       /* Chop instructions off the end */
 649       void drop_hints_bytes (hb_bytes_t &dest_start) const
 650       { dest_start = bytes.sub_array (0, bytes.length - instructions_length (bytes)); }
 651
 652       bool get_contour_points (contour_point_vector_t &points_ /* OUT */,
 653                                hb_vector_t<unsigned int> &end_points_ /* OUT */,
 654                                const bool phantom_only=false) const
 655       {
 656         /* add one pseudo point for each component in composite glyph */
 657         unsigned int num_points = hb_len (get_iterator ());
 658         points_.resize (num_points + PHANTOM_COUNT);
 659         for (unsigned int i = 0; i < points_.length; i++) points_[i].init ();
 660         return true;
 661       }
 662     };
 663
 664     enum glyph_type_t { EMPTY, SIMPLE, COMPOSITE };
 665
 666     enum phantom_point_index_t
 667     {
 668       PHANTOM_LEFT   = 0,
 669       PHANTOM_RIGHT  = 1,
 670       PHANTOM_TOP    = 2,
 671       PHANTOM_BOTTOM = 3,
 672       PHANTOM_COUNT  = 4
 673     };
 674
 675     public:
 676     composite_iter_t get_composite_iterator () const
 677     {
 678       if (type != COMPOSITE) return composite_iter_t ();
 679       return CompositeGlyph (*header, bytes).get_iterator ();
 680     }
 681
 682     const Glyph trim_padding () const
 683     {
 684       switch (type) {
 685       case COMPOSITE: return CompositeGlyph (*header, bytes).trim_padding ();
 686       case SIMPLE:    return SimpleGlyph (*header, bytes).trim_padding ();
 687       default:        return bytes;
 688       }
 689     }
 690
 691     void drop_hints ()
 692     {
 693       switch (type) {
 694       case COMPOSITE: CompositeGlyph (*header, bytes).drop_hints (); return;
 695       case SIMPLE:    SimpleGlyph (*header, bytes).drop_hints (); return;
 696       default:        return;
 697       }
 698     }
 699
 700     void drop_hints_bytes (hb_bytes_t &dest_start, hb_bytes_t &dest_end) const
 701     {
 702       switch (type) {
 703       case COMPOSITE: CompositeGlyph (*header, bytes).drop_hints_bytes (dest_start); return;
 704       case SIMPLE:    SimpleGlyph (*header, bytes).drop_hints_bytes (dest_start, dest_end); return;
 705       default:        return;
 706       }
 707     }
 708
 709     /* for a simple glyph, return contour end points, flags, along with coordinate points
 710      * for a composite glyph, return pseudo component points
 711      * in both cases points trailed with four phantom points
 712      */
 713     bool get_contour_points (contour_point_vector_t &points_ /* OUT */,
 714                              hb_vector_t<unsigned int> &end_points_ /* OUT */,
 715                              const bool phantom_only=false) const
 716     {
 717       switch (type) {
 718       case COMPOSITE: return CompositeGlyph (*header, bytes).get_contour_points (points_, end_points_, phantom_only);
 719       case SIMPLE:    return SimpleGlyph (*header, bytes).get_contour_points (points_, end_points_, phantom_only);
 720       default:
 721         /* empty glyph */
 722         points_.resize (PHANTOM_COUNT);
 723         for (unsigned int i = 0; i < points_.length; i++) points_[i].init ();
 724         return true;
 725       }
 726     }
 727
 728     bool is_simple_glyph ()    const { return type == SIMPLE; }
 729     bool is_composite_glyph () const { return type == COMPOSITE; }
 730
 731     bool get_extents (hb_font_t *font, hb_codepoint_t gid, hb_glyph_extents_t *extents) const
 732     {
 733       if (type == EMPTY) return true; /* Empty glyph; zero extents. */
 734       return header->get_extents (font, gid, extents);
 735     }
 736
 737     hb_bytes_t get_bytes ()          const { return bytes; }
 738     const GlyphHeader &get_header () const { return *header; }
 739
 740     Glyph (hb_bytes_t bytes_ = hb_bytes_t ()) :
 741       bytes (bytes_), header (bytes.as<GlyphHeader> ())
 742     {
 743       int num_contours = header->numberOfContours;
 744       if (unlikely (num_contours == 0)) type = EMPTY;
 745       else if (num_contours > 0) type = SIMPLE;
 746       else type = COMPOSITE; /* negative numbers */
 747     }
 748
 749     protected:
 750     hb_bytes_t bytes;
 751     const GlyphHeader *header;
 752     unsigned type;
 753   };
 754
 755   struct accelerator_t
 756   {
 757     void init (hb_face_t *face_)
 758     {
 759       short_offset = false;
 760       num_glyphs = 0;
 761       loca_table = nullptr;
 762       glyf_table = nullptr;
 763       face = face_;
 764       const OT::head &head = *face->table.head;
 765       if (head.indexToLocFormat > 1 || head.glyphDataFormat > 0)
 766         /* Unknown format.  Leave num_glyphs=0, that takes care of disabling us. */
 767         return;
 768       short_offset = 0 == head.indexToLocFormat;
 769
 770       loca_table = hb_sanitize_context_t ().reference_table<loca> (face);
 771       glyf_table = hb_sanitize_context_t ().reference_table<glyf> (face);
 772
 773       num_glyphs = hb_max (1u, loca_table.get_length () / (short_offset ? 2 : 4)) - 1;
 774     }
 775
 776     void fini ()
 777     {
 778       loca_table.destroy ();
 779       glyf_table.destroy ();
 780     }
 781
 782     enum phantom_point_index_t
 783     {
 784       PHANTOM_LEFT   = 0,
 785       PHANTOM_RIGHT  = 1,
 786       PHANTOM_TOP    = 2,
 787       PHANTOM_BOTTOM = 3,
 788       PHANTOM_COUNT  = 4
 789     };
 790
 791     protected:
 792
 793     void init_phantom_points (hb_codepoint_t gid, hb_array_t<contour_point_t> &phantoms /* IN/OUT */) const
 794     {
 795       const Glyph &glyph = glyph_for_gid (gid);
 796       int h_delta = (int) glyph.get_header ().xMin - face->table.hmtx->get_side_bearing (gid);
 797       int v_orig  = (int) glyph.get_header ().yMax + face->table.vmtx->get_side_bearing (gid);
 798       unsigned int h_adv = face->table.hmtx->get_advance (gid);
 799       unsigned int v_adv = face->table.vmtx->get_advance (gid);
 800
 801       phantoms[PHANTOM_LEFT].x = h_delta;
 802       phantoms[PHANTOM_RIGHT].x = h_adv + h_delta;
 803       phantoms[PHANTOM_TOP].y = v_orig;
 804       phantoms[PHANTOM_BOTTOM].y = v_orig - (int) v_adv;
 805     }
 806
 807     struct contour_bounds_t
 808     {
 809       contour_bounds_t () { min_x = min_y = FLT_MAX; max_x = max_y = -FLT_MAX; }
 810
 811       void add (const contour_point_t &p)
 812       {
 813         min_x = hb_min (min_x, p.x);
 814         min_y = hb_min (min_y, p.y);
 815         max_x = hb_max (max_x, p.x);
 816         max_y = hb_max (max_y, p.y);
 817       }
 818
 819       bool empty () const { return (min_x >= max_x) || (min_y >= max_y); }
 820
 821       void get_extents (hb_font_t *font, hb_glyph_extents_t *extents)
 822       {
 823         if (unlikely (empty ()))
 824         {
 825           extents->width = 0;
 826           extents->x_bearing = 0;
 827           extents->height = 0;
 828           extents->y_bearing = 0;
 829           return;
 830         }
 831         extents->x_bearing = font->em_scalef_x (min_x);
 832         extents->width = font->em_scalef_x (max_x - min_x);
 833         extents->y_bearing = font->em_scalef_y (max_y);
 834         extents->height = font->em_scalef_y (min_y - max_y);
 835       }
 836
 837       protected:
 838       float min_x, min_y, max_x, max_y;
 839     };
 840
 841 #ifndef HB_NO_VAR
 842     /* Note: Recursively calls itself.
 843      * all_points includes phantom points
 844      */
 845     bool get_points_var (hb_codepoint_t gid,
 846                          const int *coords, unsigned int coord_count,
 847                          contour_point_vector_t &all_points /* OUT */,
 848                          unsigned int depth = 0) const
 849     {
 850       if (unlikely (depth++ > HB_MAX_NESTING_LEVEL)) return false;
 851       contour_point_vector_t points;
 852       hb_vector_t<unsigned int> end_points;
 853       const Glyph &glyph = glyph_for_gid (gid);
 854       if (unlikely (!glyph.get_contour_points (points, end_points))) return false;
 855       hb_array_t<contour_point_t> phantoms = points.sub_array (points.length - PHANTOM_COUNT, PHANTOM_COUNT);
 856       init_phantom_points (gid, phantoms);
 857       if (unlikely (!face->table.gvar->apply_deltas_to_points (gid, coords, coord_count, points.as_array (), end_points.as_array ()))) return false;
 858
 859       unsigned int comp_index = 0;
 860       if (glyph.is_simple_glyph ())
 861         all_points.extend (points.as_array ());
 862       else if (glyph.is_composite_glyph ())
 863       {
 864         for (auto &item : glyph.get_composite_iterator ())
 865         {
 866           contour_point_vector_t comp_points;
 867           if (unlikely (!get_points_var (item.glyphIndex, coords, coord_count,
 868                                          comp_points, depth))
 869                         || comp_points.length < PHANTOM_COUNT)
 870             return false;
 871
 872           /* Copy phantom points from component if USE_MY_METRICS flag set */
 873           if (item.is_use_my_metrics ())
 874             for (unsigned int i = 0; i < PHANTOM_COUNT; i++)
 875               phantoms[i] = comp_points[comp_points.length - PHANTOM_COUNT + i];
 876
 877           /* Apply component transformation & translation */
 878           item.transform_points (comp_points);
 879
 880           /* Apply translatation from gvar */
 881           comp_points.translate (points[comp_index]);
 882
 883           if (item.is_anchored ())
 884           {
 885             unsigned int p1, p2;
 886             item.get_anchor_points (p1, p2);
 887             if (likely (p1 < all_points.length && p2 < comp_points.length))
 888             {
 889               contour_point_t delta;
 890               delta.init (all_points[p1].x - comp_points[p2].x,
 891                           all_points[p1].y - comp_points[p2].y);
 892
 893               comp_points.translate (delta);
 894             }
 895           }
 896
 897           all_points.extend (comp_points.sub_array (0, comp_points.length - PHANTOM_COUNT));
 898
 899           comp_index++;
 900         }
 901
 902         all_points.extend (phantoms);
 903       }
 904       else return false;
 905
 906       return true;
 907     }
 908
 909     bool get_points_bearing_applied (hb_font_t *font, hb_codepoint_t gid, contour_point_vector_t &all_points) const
 910     {
 911       if (unlikely (!get_points_var (gid, font->coords, font->num_coords, all_points) ||
 912                     all_points.length < PHANTOM_COUNT)) return false;
 913
 914       /* Undocumented rasterizer behavior:
 915        * Shift points horizontally by the updated left side bearing
 916        */
 917       contour_point_t delta;
 918       delta.init (-all_points[all_points.length - PHANTOM_COUNT + PHANTOM_LEFT].x, 0.f);
 919       if (delta.x) all_points.translate (delta);
 920       return true;
 921     }
 922
 923     protected:
 924
 925     bool get_var_extents_and_phantoms (hb_font_t *font, hb_codepoint_t gid,
 926                                        hb_glyph_extents_t *extents=nullptr /* OUT */,
 927                                        contour_point_vector_t *phantoms=nullptr /* OUT */) const
 928     {
 929       contour_point_vector_t all_points;
 930       if (!unlikely (get_points_bearing_applied (font, gid, all_points))) return false;
 931       if (extents)
 932       {
 933         contour_bounds_t bounds;
 934         for (unsigned int i = 0; i + PHANTOM_COUNT < all_points.length; i++)
 935           bounds.add (all_points[i]);
 936         bounds.get_extents (font, extents);
 937       }
 938       if (phantoms)
 939         for (unsigned int i = 0; i < PHANTOM_COUNT; i++)
 940           (*phantoms)[i] = all_points[all_points.length - PHANTOM_COUNT + i];
 941       return true;
 942     }
 943
 944     bool get_var_metrics (hb_font_t *font, hb_codepoint_t gid,
 945                           contour_point_vector_t &phantoms) const
 946     { return get_var_extents_and_phantoms (font, gid, nullptr, &phantoms); }
 947
 948     bool get_extents_var (hb_font_t *font, hb_codepoint_t gid,
 949                           hb_glyph_extents_t *extents) const
 950     { return get_var_extents_and_phantoms (font, gid, extents); }
 951 #endif
 952
 953     public:
 954 #ifndef HB_NO_VAR
 955     unsigned int get_advance_var (hb_font_t *font, hb_codepoint_t gid,
 956                                   bool is_vertical) const
 957     {
 958       bool success = false;
 959       contour_point_vector_t phantoms;
 960       phantoms.resize (PHANTOM_COUNT);
 961
 962       if (likely (font->num_coords == face->table.gvar->get_axis_count ()))
 963         success = get_var_metrics (font, gid, phantoms);
 964
 965       if (unlikely (!success))
 966         return is_vertical ? face->table.vmtx->get_advance (gid) : face->table.hmtx->get_advance (gid);
 967
 968       if (is_vertical)
 969         return roundf (phantoms[PHANTOM_TOP].y - phantoms[PHANTOM_BOTTOM].y);
 970       else
 971         return roundf (phantoms[PHANTOM_RIGHT].x - phantoms[PHANTOM_LEFT].x);
 972     }
 973
 974     int get_side_bearing_var (hb_font_t *font, hb_codepoint_t gid, bool is_vertical) const
 975     {
 976       hb_glyph_extents_t extents;
 977       contour_point_vector_t phantoms;
 978       phantoms.resize (PHANTOM_COUNT);
 979
 980       if (unlikely (!get_var_extents_and_phantoms (font, gid, &extents, &phantoms)))
 981         return is_vertical ? face->table.vmtx->get_side_bearing (gid) : face->table.hmtx->get_side_bearing (gid);
 982
 983       return is_vertical ? ceil (phantoms[PHANTOM_TOP].y) - extents.y_bearing : floor (phantoms[PHANTOM_LEFT].x);
 984     }
 985 #endif
 986
 987     bool get_extents (hb_font_t *font, hb_codepoint_t gid, hb_glyph_extents_t *extents) const
 988     {
 989 #ifndef HB_NO_VAR
 990       unsigned int coord_count;
 991       const int *coords = hb_font_get_var_coords_normalized (font, &coord_count);
 992       if (coords && coord_count > 0 && coord_count == face->table.gvar->get_axis_count ())
 993         return get_extents_var (font, gid, extents);
 994 #endif
 995
 996       if (unlikely (gid >= num_glyphs)) return false;
 997
 998       return glyph_for_gid (gid).get_extents (font, gid, extents);
 999     }
1000
1001     const Glyph
1002     glyph_for_gid (hb_codepoint_t gid, bool needs_padding_removal = false) const
1003     {
1004       unsigned int start_offset, end_offset;
1005       if (unlikely (gid >= num_glyphs)) return Glyph ();
1006
1007       if (short_offset)
1008       {
1009         const HBUINT16 *offsets = (const HBUINT16 *) loca_table->dataZ.arrayZ;
1010         start_offset = 2 * offsets[gid];
1011         end_offset   = 2 * offsets[gid + 1];
1012       }
1013       else
1014       {
1015         const HBUINT32 *offsets = (const HBUINT32 *) loca_table->dataZ.arrayZ;
1016         start_offset = offsets[gid];
1017         end_offset   = offsets[gid + 1];
1018       }
1019
1020       if (unlikely (start_offset > end_offset || end_offset > glyf_table.get_length ()))
1021         return Glyph ();
1022
1023       Glyph glyph (hb_bytes_t ((const char *) this->glyf_table + start_offset,
1024                                end_offset - start_offset));
1025       return needs_padding_removal ? glyph.trim_padding () : glyph;
1026     }
1027
1028     void
1029     add_gid_and_children (hb_codepoint_t gid, hb_set_t *gids_to_retain,
1030                           unsigned int depth = 0) const
1031     {
1032       if (unlikely (depth++ > HB_MAX_NESTING_LEVEL)) return;
1033       /* Check if is already visited */
1034       if (gids_to_retain->has (gid)) return;
1035
1036       gids_to_retain->add (gid);
1037
1038       for (auto &item : glyph_for_gid (gid).get_composite_iterator ())
1039         add_gid_and_children (item.glyphIndex, gids_to_retain, depth);
1040     }
1041
1042     private:
1043     bool short_offset;
1044     unsigned int num_glyphs;
1045     hb_blob_ptr_t<loca> loca_table;
1046     hb_blob_ptr_t<glyf> glyf_table;
1047     hb_face_t *face;
1048   };
1049
1050   struct SubsetGlyph
1051   {
1052     hb_codepoint_t new_gid;
1053     hb_codepoint_t old_gid;
1054     Glyph source_glyph;
1055     hb_bytes_t dest_start;  /* region of source_glyph to copy first */
1056     hb_bytes_t dest_end;    /* region of source_glyph to copy second */
1057
1058     bool serialize (hb_serialize_context_t *c,
1059                     const hb_subset_plan_t *plan) const
1060     {
1061       TRACE_SERIALIZE (this);
1062
1063       hb_bytes_t dest_glyph = dest_start.copy (c);
1064       dest_glyph = hb_bytes_t (&dest_glyph, dest_glyph.length + dest_end.copy (c).length);
1065       unsigned int pad_length = padding ();
1066       DEBUG_MSG (SUBSET, nullptr, "serialize %d byte glyph, width %d pad %d", dest_glyph.length, dest_glyph.length  + pad_length, pad_length);
1067
1068       HBUINT8 pad;
1069       pad = 0;
1070       while (pad_length > 0)
1071       {
1072         c->embed (pad);
1073         pad_length--;
1074       }
1075
1076       if (!unlikely (dest_glyph.length)) return_trace (true);
1077
1078       /* update components gids */
1079       for (auto &_ : Glyph (dest_glyph).get_composite_iterator ())
1080       {
1081         hb_codepoint_t new_gid;
1082         if (plan->new_gid_for_old_gid (_.glyphIndex, &new_gid))
1083           ((OT::glyf::CompositeGlyphChain *) &_)->glyphIndex = new_gid;
1084       }
1085
1086       if (plan->drop_hints) Glyph (dest_glyph).drop_hints ();
1087
1088       return_trace (true);
1089     }
1090
1091     void drop_hints_bytes ()
1092     { source_glyph.drop_hints_bytes (dest_start, dest_end); }
1093
1094     unsigned int      length () const { return dest_start.length + dest_end.length; }
1095     /* pad to 2 to ensure 2-byte loca will be ok */
1096     unsigned int     padding () const { return length () % 2; }
1097     unsigned int padded_size () const { return length () + padding (); }
1098   };
1099
1100   protected:
1101   UnsizedArrayOf<HBUINT8>
1102                 dataZ;  /* Glyphs data. */
1103   public:
1104   DEFINE_SIZE_MIN (0);  /* In reality, this is UNBOUNDED() type; but since we always
1105                          * check the size externally, allow Null() object of it by
1106                          * defining it _MIN instead. */
1107 };
1108
1109 struct glyf_accelerator_t : glyf::accelerator_t {};
1110
1111 } /* namespace OT */
1112
1113
1114 #endif /* HB_OT_GLYF_TABLE_HH */