src/third_party/harfbuzz-ng/src/hb-ot-layout-common-private.hh

   1 /*
   2  * Copyright © 2007,2008,2009  Red Hat, Inc.
   3  * Copyright © 2010,2012  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  * Red Hat Author(s): Behdad Esfahbod
  26  * Google Author(s): Behdad Esfahbod
  27  */
  28
  29 #ifndef HB_OT_LAYOUT_COMMON_PRIVATE_HH
  30 #define HB_OT_LAYOUT_COMMON_PRIVATE_HH
  31
  32 #include "hb-ot-layout-private.hh"
  33 #include "hb-open-type-private.hh"
  34 #include "hb-set-private.hh"
  35
  36
  37 namespace OT {
  38
  39
  40 #define NOT_COVERED             ((unsigned int) -1)
  41 #define MAX_NESTING_LEVEL       8
  42 #define MAX_CONTEXT_LENGTH      64
  43
  44
  45
  46 /*
  47  *
  48  * OpenType Layout Common Table Formats
  49  *
  50  */
  51
  52
  53 /*
  54  * Script, ScriptList, LangSys, Feature, FeatureList, Lookup, LookupList
  55  */
  56
  57 template <typename Type>
  58 struct Record
  59 {
  60   inline int cmp (hb_tag_t a) const {
  61     return tag.cmp (a);
  62   }
  63
  64   struct sanitize_closure_t {
  65     hb_tag_t tag;
  66     void *list_base;
  67   };
  68   inline bool sanitize (hb_sanitize_context_t *c, void *base) {
  69     TRACE_SANITIZE (this);
  70     const sanitize_closure_t closure = {tag, base};
  71     return TRACE_RETURN (c->check_struct (this) && offset.sanitize (c, base, &closure));
  72   }
  73
  74   Tag           tag;            /* 4-byte Tag identifier */
  75   OffsetTo<Type>
  76                 offset;         /* Offset from beginning of object holding
  77                                  * the Record */
  78   public:
  79   DEFINE_SIZE_STATIC (6);
  80 };
  81
  82 template <typename Type>
  83 struct RecordArrayOf : SortedArrayOf<Record<Type> > {
  84   inline const Tag& get_tag (unsigned int i) const
  85   {
  86     /* We cheat slightly and don't define separate Null objects
  87      * for Record types.  Instead, we return the correct Null(Tag)
  88      * here. */
  89     if (unlikely (i >= this->len)) return Null(Tag);
  90     return (*this)[i].tag;
  91   }
  92   inline unsigned int get_tags (unsigned int start_offset,
  93                                 unsigned int *record_count /* IN/OUT */,
  94                                 hb_tag_t     *record_tags /* OUT */) const
  95   {
  96     if (record_count) {
  97       const Record<Type> *arr = this->sub_array (start_offset, record_count);
  98       unsigned int count = *record_count;
  99       for (unsigned int i = 0; i < count; i++)
 100         record_tags[i] = arr[i].tag;
 101     }
 102     return this->len;
 103   }
 104   inline bool find_index (hb_tag_t tag, unsigned int *index) const
 105   {
 106     int i = this->search (tag);
 107     if (i != -1) {
 108         if (index) *index = i;
 109         return true;
 110     } else {
 111       if (index) *index = Index::NOT_FOUND_INDEX;
 112       return false;
 113     }
 114   }
 115 };
 116
 117 template <typename Type>
 118 struct RecordListOf : RecordArrayOf<Type>
 119 {
 120   inline const Type& operator [] (unsigned int i) const
 121   { return this+RecordArrayOf<Type>::operator [](i).offset; }
 122
 123   inline bool sanitize (hb_sanitize_context_t *c) {
 124     TRACE_SANITIZE (this);
 125     return TRACE_RETURN (RecordArrayOf<Type>::sanitize (c, this));
 126   }
 127 };
 128
 129
 130 struct RangeRecord
 131 {
 132   inline int cmp (hb_codepoint_t g) const {
 133     return g < start ? -1 : g <= end ? 0 : +1 ;
 134   }
 135
 136   inline bool sanitize (hb_sanitize_context_t *c) {
 137     TRACE_SANITIZE (this);
 138     return TRACE_RETURN (c->check_struct (this));
 139   }
 140
 141   inline bool intersects (const hb_set_t *glyphs) const {
 142     return glyphs->intersects (start, end);
 143   }
 144
 145   template <typename set_t>
 146   inline void add_coverage (set_t *glyphs) const {
 147     glyphs->add_range (start, end);
 148   }
 149
 150   GlyphID       start;          /* First GlyphID in the range */
 151   GlyphID       end;            /* Last GlyphID in the range */
 152   USHORT        value;          /* Value */
 153   public:
 154   DEFINE_SIZE_STATIC (6);
 155 };
 156 DEFINE_NULL_DATA (RangeRecord, "\000\001");
 157
 158
 159 struct IndexArray : ArrayOf<Index>
 160 {
 161   inline unsigned int get_indexes (unsigned int start_offset,
 162                                    unsigned int *_count /* IN/OUT */,
 163                                    unsigned int *_indexes /* OUT */) const
 164   {
 165     if (_count) {
 166       const USHORT *arr = this->sub_array (start_offset, _count);
 167       unsigned int count = *_count;
 168       for (unsigned int i = 0; i < count; i++)
 169         _indexes[i] = arr[i];
 170     }
 171     return this->len;
 172   }
 173 };
 174
 175
 176 struct Script;
 177 struct LangSys;
 178 struct Feature;
 179
 180
 181 struct LangSys
 182 {
 183   inline unsigned int get_feature_count (void) const
 184   { return featureIndex.len; }
 185   inline hb_tag_t get_feature_index (unsigned int i) const
 186   { return featureIndex[i]; }
 187   inline unsigned int get_feature_indexes (unsigned int start_offset,
 188                                            unsigned int *feature_count /* IN/OUT */,
 189                                            unsigned int *feature_indexes /* OUT */) const
 190   { return featureIndex.get_indexes (start_offset, feature_count, feature_indexes); }
 191
 192   inline bool has_required_feature (void) const { return reqFeatureIndex != 0xffff; }
 193   inline unsigned int get_required_feature_index (void) const
 194   {
 195     if (reqFeatureIndex == 0xffff)
 196       return Index::NOT_FOUND_INDEX;
 197    return reqFeatureIndex;;
 198   }
 199
 200   inline bool sanitize (hb_sanitize_context_t *c,
 201                         const Record<LangSys>::sanitize_closure_t * = NULL) {
 202     TRACE_SANITIZE (this);
 203     return TRACE_RETURN (c->check_struct (this) && featureIndex.sanitize (c));
 204   }
 205
 206   Offset        lookupOrder;    /* = Null (reserved for an offset to a
 207                                  * reordering table) */
 208   USHORT        reqFeatureIndex;/* Index of a feature required for this
 209                                  * language system--if no required features
 210                                  * = 0xFFFF */
 211   IndexArray    featureIndex;   /* Array of indices into the FeatureList */
 212   public:
 213   DEFINE_SIZE_ARRAY (6, featureIndex);
 214 };
 215 DEFINE_NULL_DATA (LangSys, "\0\0\xFF\xFF");
 216
 217
 218 struct Script
 219 {
 220   inline unsigned int get_lang_sys_count (void) const
 221   { return langSys.len; }
 222   inline const Tag& get_lang_sys_tag (unsigned int i) const
 223   { return langSys.get_tag (i); }
 224   inline unsigned int get_lang_sys_tags (unsigned int start_offset,
 225                                          unsigned int *lang_sys_count /* IN/OUT */,
 226                                          hb_tag_t     *lang_sys_tags /* OUT */) const
 227   { return langSys.get_tags (start_offset, lang_sys_count, lang_sys_tags); }
 228   inline const LangSys& get_lang_sys (unsigned int i) const
 229   {
 230     if (i == Index::NOT_FOUND_INDEX) return get_default_lang_sys ();
 231     return this+langSys[i].offset;
 232   }
 233   inline bool find_lang_sys_index (hb_tag_t tag, unsigned int *index) const
 234   { return langSys.find_index (tag, index); }
 235
 236   inline bool has_default_lang_sys (void) const { return defaultLangSys != 0; }
 237   inline const LangSys& get_default_lang_sys (void) const { return this+defaultLangSys; }
 238
 239   inline bool sanitize (hb_sanitize_context_t *c,
 240                         const Record<Script>::sanitize_closure_t * = NULL) {
 241     TRACE_SANITIZE (this);
 242     return TRACE_RETURN (defaultLangSys.sanitize (c, this) && langSys.sanitize (c, this));
 243   }
 244
 245   protected:
 246   OffsetTo<LangSys>
 247                 defaultLangSys; /* Offset to DefaultLangSys table--from
 248                                  * beginning of Script table--may be Null */
 249   RecordArrayOf<LangSys>
 250                 langSys;        /* Array of LangSysRecords--listed
 251                                  * alphabetically by LangSysTag */
 252   public:
 253   DEFINE_SIZE_ARRAY (4, langSys);
 254 };
 255
 256 typedef RecordListOf<Script> ScriptList;
 257
 258
 259 /* http://www.microsoft.com/typography/otspec/features_pt.htm#size */
 260 struct FeatureParamsSize
 261 {
 262   inline bool sanitize (hb_sanitize_context_t *c) {
 263     TRACE_SANITIZE (this);
 264     if (unlikely (!c->check_struct (this))) return TRACE_RETURN (false);
 265
 266     /* This subtable has some "history", if you will.  Some earlier versions of
 267      * Adobe tools calculated the offset of the FeatureParams sutable from the
 268      * beginning of the FeatureList table!  Now, that is dealt with in the
 269      * Feature implementation.  But we still need to be able to tell junk from
 270      * real data.  Note: We don't check that the nameID actually exists.
 271      *
 272      * Read Roberts wrote on 9/15/06 on opentype-list@indx.co.uk :
 273      *
 274      * Yes, it is correct that a new version of the AFDKO (version 2.0) will be
 275      * coming out soon, and that the makeotf program will build a font with a
 276      * 'size' feature that is correct by the specification.
 277      *
 278      * The specification for this feature tag is in the "OpenType Layout Tag
 279      * Registry". You can see a copy of this at:
 280      * http://partners.adobe.com/public/developer/opentype/index_tag8.html#size
 281      *
 282      * Here is one set of rules to determine if the 'size' feature is built
 283      * correctly, or as by the older versions of MakeOTF. You may be able to do
 284      * better.
 285      *
 286      * Assume that the offset to the size feature is according to specification,
 287      * and make the following value checks. If it fails, assume the the size
 288      * feature is calculated as versions of MakeOTF before the AFDKO 2.0 built it.
 289      * If this fails, reject the 'size' feature. The older makeOTF's calculated the
 290      * offset from the beginning of the FeatureList table, rather than from the
 291      * beginning of the 'size' Feature table.
 292      *
 293      * If "design size" == 0:
 294      *     fails check
 295      *
 296      * Else if ("subfamily identifier" == 0 and
 297      *     "range start" == 0 and
 298      *     "range end" == 0 and
 299      *     "range start" == 0 and
 300      *     "menu name ID" == 0)
 301      *     passes check: this is the format used when there is a design size
 302      * specified, but there is no recommended size range.
 303      *
 304      * Else if ("design size" <  "range start" or
 305      *     "design size" >   "range end" or
 306      *     "range end" <= "range start" or
 307      *     "menu name ID"  < 256 or
 308      *     "menu name ID"  > 32767 or
 309      *     menu name ID is not a name ID which is actually in the name table)
 310      *     fails test
 311      * Else
 312      *     passes test.
 313      */
 314
 315     if (!designSize)
 316       return TRACE_RETURN (false);
 317     else if (subfamilyID == 0 &&
 318              subfamilyNameID == 0 &&
 319              rangeStart == 0 &&
 320              rangeEnd == 0)
 321       return TRACE_RETURN (true);
 322     else if (designSize < rangeStart ||
 323              designSize > rangeEnd ||
 324              subfamilyNameID < 256 ||
 325              subfamilyNameID > 32767)
 326       return TRACE_RETURN (false);
 327     else
 328       return TRACE_RETURN (true);
 329   }
 330
 331   USHORT        designSize;     /* Represents the design size in 720/inch
 332                                  * units (decipoints).  The design size entry
 333                                  * must be non-zero.  When there is a design
 334                                  * size but no recommended size range, the
 335                                  * rest of the array will consist of zeros. */
 336   USHORT        subfamilyID;    /* Has no independent meaning, but serves
 337                                  * as an identifier that associates fonts
 338                                  * in a subfamily. All fonts which share a
 339                                  * Preferred or Font Family name and which
 340                                  * differ only by size range shall have the
 341                                  * same subfamily value, and no fonts which
 342                                  * differ in weight or style shall have the
 343                                  * same subfamily value. If this value is
 344                                  * zero, the remaining fields in the array
 345                                  * will be ignored. */
 346   USHORT        subfamilyNameID;/* If the preceding value is non-zero, this
 347                                  * value must be set in the range 256 - 32767
 348                                  * (inclusive). It records the value of a
 349                                  * field in the name table, which must
 350                                  * contain English-language strings encoded
 351                                  * in Windows Unicode and Macintosh Roman,
 352                                  * and may contain additional strings
 353                                  * localized to other scripts and languages.
 354                                  * Each of these strings is the name an
 355                                  * application should use, in combination
 356                                  * with the family name, to represent the
 357                                  * subfamily in a menu.  Applications will
 358                                  * choose the appropriate version based on
 359                                  * their selection criteria. */
 360   USHORT        rangeStart;     /* Large end of the recommended usage range
 361                                  * (inclusive), stored in 720/inch units
 362                                  * (decipoints). */
 363   USHORT        rangeEnd;       /* Small end of the recommended usage range
 364                                    (exclusive), stored in 720/inch units
 365                                  * (decipoints). */
 366   public:
 367   DEFINE_SIZE_STATIC (10);
 368 };
 369
 370 /* http://www.microsoft.com/typography/otspec/features_pt.htm#ssxx */
 371 struct FeatureParamsStylisticSet
 372 {
 373   inline bool sanitize (hb_sanitize_context_t *c) {
 374     TRACE_SANITIZE (this);
 375     /* Right now minorVersion is at zero.  Which means, any table supports
 376      * the uiNameID field. */
 377     return TRACE_RETURN (c->check_struct (this));
 378   }
 379
 380   USHORT        version;        /* (set to 0): This corresponds to a “minor”
 381                                  * version number. Additional data may be
 382                                  * added to the end of this Feature Parameters
 383                                  * table in the future. */
 384
 385   USHORT        uiNameID;       /* The 'name' table name ID that specifies a
 386                                  * string (or strings, for multiple languages)
 387                                  * for a user-interface label for this
 388                                  * feature.  The values of uiLabelNameId and
 389                                  * sampleTextNameId are expected to be in the
 390                                  * font-specific name ID range (256-32767),
 391                                  * though that is not a requirement in this
 392                                  * Feature Parameters specification. The
 393                                  * user-interface label for the feature can
 394                                  * be provided in multiple languages. An
 395                                  * English string should be included as a
 396                                  * fallback. The string should be kept to a
 397                                  * minimal length to fit comfortably with
 398                                  * different application interfaces. */
 399   public:
 400   DEFINE_SIZE_STATIC (4);
 401 };
 402
 403 /* http://www.microsoft.com/typography/otspec/features_ae.htm#cv01-cv99 */
 404 struct FeatureParamsCharacterVariants
 405 {
 406   inline bool sanitize (hb_sanitize_context_t *c) {
 407     TRACE_SANITIZE (this);
 408     return TRACE_RETURN (c->check_struct (this) &&
 409                          characters.sanitize (c));
 410   }
 411
 412   USHORT        format;                 /* Format number is set to 0. */
 413   USHORT        featUILableNameID;      /* The ‘name’ table name ID that
 414                                          * specifies a string (or strings,
 415                                          * for multiple languages) for a
 416                                          * user-interface label for this
 417                                          * feature. (May be NULL.) */
 418   USHORT        featUITooltipTextNameID;/* The ‘name’ table name ID that
 419                                          * specifies a string (or strings,
 420                                          * for multiple languages) that an
 421                                          * application can use for tooltip
 422                                          * text for this feature. (May be
 423                                          * NULL.) */
 424   USHORT        sampleTextNameID;       /* The ‘name’ table name ID that
 425                                          * specifies sample text that
 426                                          * illustrates the effect of this
 427                                          * feature. (May be NULL.) */
 428   USHORT        numNamedParameters;     /* Number of named parameters. (May
 429                                          * be zero.) */
 430   USHORT        firstParamUILabelNameID;/* The first ‘name’ table name ID
 431                                          * used to specify strings for
 432                                          * user-interface labels for the
 433                                          * feature parameters. (Must be zero
 434                                          * if numParameters is zero.) */
 435   ArrayOf<UINT24>
 436                 characters;             /* Array of the Unicode Scalar Value
 437                                          * of the characters for which this
 438                                          * feature provides glyph variants.
 439                                          * (May be zero.) */
 440   public:
 441   DEFINE_SIZE_ARRAY (14, characters);
 442 };
 443
 444 struct FeatureParams
 445 {
 446   inline bool sanitize (hb_sanitize_context_t *c, hb_tag_t tag) {
 447     TRACE_SANITIZE (this);
 448     if (tag == HB_TAG ('s','i','z','e'))
 449       return TRACE_RETURN (u.size.sanitize (c));
 450     if ((tag & 0xFFFF0000) == HB_TAG ('s','s','\0','\0')) /* ssXX */
 451       return TRACE_RETURN (u.stylisticSet.sanitize (c));
 452     if ((tag & 0xFFFF0000) == HB_TAG ('c','v','\0','\0')) /* cvXX */
 453       return TRACE_RETURN (u.characterVariants.sanitize (c));
 454     return TRACE_RETURN (true);
 455   }
 456
 457   inline const FeatureParamsSize& get_size_params (hb_tag_t tag) const
 458   {
 459     if (tag == HB_TAG ('s','i','z','e'))
 460       return u.size;
 461     return Null(FeatureParamsSize);
 462   }
 463
 464   private:
 465   union {
 466   FeatureParamsSize                     size;
 467   FeatureParamsStylisticSet             stylisticSet;
 468   FeatureParamsCharacterVariants        characterVariants;
 469   } u;
 470   DEFINE_SIZE_STATIC (17);
 471 };
 472
 473 struct Feature
 474 {
 475   inline unsigned int get_lookup_count (void) const
 476   { return lookupIndex.len; }
 477   inline hb_tag_t get_lookup_index (unsigned int i) const
 478   { return lookupIndex[i]; }
 479   inline unsigned int get_lookup_indexes (unsigned int start_index,
 480                                           unsigned int *lookup_count /* IN/OUT */,
 481                                           unsigned int *lookup_tags /* OUT */) const
 482   { return lookupIndex.get_indexes (start_index, lookup_count, lookup_tags); }
 483
 484   inline const FeatureParams &get_feature_params (void) const
 485   { return this+featureParams; }
 486
 487   inline bool sanitize (hb_sanitize_context_t *c,
 488                         const Record<Feature>::sanitize_closure_t *closure) {
 489     TRACE_SANITIZE (this);
 490     if (unlikely (!(c->check_struct (this) && lookupIndex.sanitize (c))))
 491       return TRACE_RETURN (false);
 492
 493     /* Some earlier versions of Adobe tools calculated the offset of the
 494      * FeatureParams subtable from the beginning of the FeatureList table!
 495      *
 496      * If sanitizing "failed" for the FeatureParams subtable, try it with the
 497      * alternative location.  We would know sanitize "failed" if old value
 498      * of the offset was non-zero, but it's zeroed now.
 499      *
 500      * Only do this for the 'size' feature, since at the time of the faulty
 501      * Adobe tools, only the 'size' feature had FeatureParams defined.
 502      */
 503
 504     Offset orig_offset = featureParams;
 505     if (unlikely (!featureParams.sanitize (c, this, closure ? closure->tag : HB_TAG_NONE)))
 506       return TRACE_RETURN (false);
 507
 508     if (likely (!orig_offset))
 509       return TRACE_RETURN (true);
 510
 511     if (featureParams == 0 && closure &&
 512         closure->tag == HB_TAG ('s','i','z','e') &&
 513         closure->list_base && closure->list_base < this)
 514     {
 515       unsigned int new_offset_int = (unsigned int) orig_offset -
 516                                     ((char *) this - (char *) closure->list_base);
 517
 518       Offset new_offset;
 519       /* Check that it did not overflow. */
 520       new_offset.set (new_offset_int);
 521       if (new_offset == new_offset_int &&
 522           featureParams.try_set (c, new_offset) &&
 523           !featureParams.sanitize (c, this, closure ? closure->tag : HB_TAG_NONE))
 524         return TRACE_RETURN (false);
 525     }
 526
 527     return TRACE_RETURN (true);
 528   }
 529
 530   OffsetTo<FeatureParams>
 531                  featureParams; /* Offset to Feature Parameters table (if one
 532                                  * has been defined for the feature), relative
 533                                  * to the beginning of the Feature Table; = Null
 534                                  * if not required */
 535   IndexArray     lookupIndex;   /* Array of LookupList indices */
 536   public:
 537   DEFINE_SIZE_ARRAY (4, lookupIndex);
 538 };
 539
 540 typedef RecordListOf<Feature> FeatureList;
 541
 542
 543 struct LookupFlag : USHORT
 544 {
 545   enum Flags {
 546     RightToLeft         = 0x0001u,
 547     IgnoreBaseGlyphs    = 0x0002u,
 548     IgnoreLigatures     = 0x0004u,
 549     IgnoreMarks         = 0x0008u,
 550     IgnoreFlags         = 0x000Eu,
 551     UseMarkFilteringSet = 0x0010u,
 552     Reserved            = 0x00E0u,
 553     MarkAttachmentType  = 0xFF00u
 554   };
 555   public:
 556   DEFINE_SIZE_STATIC (2);
 557 };
 558
 559 struct Lookup
 560 {
 561   inline unsigned int get_subtable_count (void) const { return subTable.len; }
 562
 563   inline unsigned int get_type (void) const { return lookupType; }
 564
 565   /* lookup_props is a 32-bit integer where the lower 16-bit is LookupFlag and
 566    * higher 16-bit is mark-filtering-set if the lookup uses one.
 567    * Not to be confused with glyph_props which is very similar. */
 568   inline uint32_t get_props (void) const
 569   {
 570     unsigned int flag = lookupFlag;
 571     if (unlikely (flag & LookupFlag::UseMarkFilteringSet))
 572     {
 573       const USHORT &markFilteringSet = StructAfter<USHORT> (subTable);
 574       flag += (markFilteringSet << 16);
 575     }
 576     return flag;
 577   }
 578
 579   inline bool serialize (hb_serialize_context_t *c,
 580                          unsigned int lookup_type,
 581                          uint32_t lookup_props,
 582                          unsigned int num_subtables)
 583   {
 584     TRACE_SERIALIZE (this);
 585     if (unlikely (!c->extend_min (*this))) return TRACE_RETURN (false);
 586     lookupType.set (lookup_type);
 587     lookupFlag.set (lookup_props & 0xFFFF);
 588     if (unlikely (!subTable.serialize (c, num_subtables))) return TRACE_RETURN (false);
 589     if (lookupFlag & LookupFlag::UseMarkFilteringSet)
 590     {
 591       USHORT &markFilteringSet = StructAfter<USHORT> (subTable);
 592       markFilteringSet.set (lookup_props >> 16);
 593     }
 594     return TRACE_RETURN (true);
 595   }
 596
 597   inline bool sanitize (hb_sanitize_context_t *c) {
 598     TRACE_SANITIZE (this);
 599     /* Real sanitize of the subtables is done by GSUB/GPOS/... */
 600     if (!(c->check_struct (this) && subTable.sanitize (c))) return TRACE_RETURN (false);
 601     if (lookupFlag & LookupFlag::UseMarkFilteringSet)
 602     {
 603       USHORT &markFilteringSet = StructAfter<USHORT> (subTable);
 604       if (!markFilteringSet.sanitize (c)) return TRACE_RETURN (false);
 605     }
 606     return TRACE_RETURN (true);
 607   }
 608
 609   USHORT        lookupType;             /* Different enumerations for GSUB and GPOS */
 610   USHORT        lookupFlag;             /* Lookup qualifiers */
 611   ArrayOf<Offset>
 612                 subTable;               /* Array of SubTables */
 613   USHORT        markFilteringSetX[VAR]; /* Index (base 0) into GDEF mark glyph sets
 614                                          * structure. This field is only present if bit
 615                                          * UseMarkFilteringSet of lookup flags is set. */
 616   public:
 617   DEFINE_SIZE_ARRAY2 (6, subTable, markFilteringSetX);
 618 };
 619
 620 typedef OffsetListOf<Lookup> LookupList;
 621
 622
 623 /*
 624  * Coverage Table
 625  */
 626
 627 struct CoverageFormat1
 628 {
 629   friend struct Coverage;
 630
 631   private:
 632   inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
 633   {
 634     int i = glyphArray.search (glyph_id);
 635     ASSERT_STATIC (((unsigned int) -1) == NOT_COVERED);
 636     return i;
 637   }
 638
 639   inline bool serialize (hb_serialize_context_t *c,
 640                          Supplier<GlyphID> &glyphs,
 641                          unsigned int num_glyphs)
 642   {
 643     TRACE_SERIALIZE (this);
 644     if (unlikely (!c->extend_min (*this))) return TRACE_RETURN (false);
 645     glyphArray.len.set (num_glyphs);
 646     if (unlikely (!c->extend (glyphArray))) return TRACE_RETURN (false);
 647     for (unsigned int i = 0; i < num_glyphs; i++)
 648       glyphArray[i] = glyphs[i];
 649     glyphs.advance (num_glyphs);
 650     return TRACE_RETURN (true);
 651   }
 652
 653   inline bool sanitize (hb_sanitize_context_t *c) {
 654     TRACE_SANITIZE (this);
 655     return TRACE_RETURN (glyphArray.sanitize (c));
 656   }
 657
 658   inline bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const {
 659     return glyphs->has (glyphArray[index]);
 660   }
 661
 662   template <typename set_t>
 663   inline void add_coverage (set_t *glyphs) const {
 664     unsigned int count = glyphArray.len;
 665     for (unsigned int i = 0; i < count; i++)
 666       glyphs->add (glyphArray[i]);
 667   }
 668
 669   public:
 670   /* Older compilers need this to be public. */
 671   struct Iter {
 672     inline void init (const struct CoverageFormat1 &c_) { c = &c_; i = 0; };
 673     inline bool more (void) { return i < c->glyphArray.len; }
 674     inline void next (void) { i++; }
 675     inline uint16_t get_glyph (void) { return c->glyphArray[i]; }
 676     inline uint16_t get_coverage (void) { return i; }
 677
 678     private:
 679     const struct CoverageFormat1 *c;
 680     unsigned int i;
 681   };
 682   private:
 683
 684   protected:
 685   USHORT        coverageFormat; /* Format identifier--format = 1 */
 686   SortedArrayOf<GlyphID>
 687                 glyphArray;     /* Array of GlyphIDs--in numerical order */
 688   public:
 689   DEFINE_SIZE_ARRAY (4, glyphArray);
 690 };
 691
 692 struct CoverageFormat2
 693 {
 694   friend struct Coverage;
 695
 696   private:
 697   inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
 698   {
 699     int i = rangeRecord.search (glyph_id);
 700     if (i != -1) {
 701       const RangeRecord &range = rangeRecord[i];
 702       return (unsigned int) range.value + (glyph_id - range.start);
 703     }
 704     return NOT_COVERED;
 705   }
 706
 707   inline bool serialize (hb_serialize_context_t *c,
 708                          Supplier<GlyphID> &glyphs,
 709                          unsigned int num_glyphs)
 710   {
 711     TRACE_SERIALIZE (this);
 712     if (unlikely (!c->extend_min (*this))) return TRACE_RETURN (false);
 713
 714     if (unlikely (!num_glyphs)) return TRACE_RETURN (true);
 715
 716     unsigned int num_ranges = 1;
 717     for (unsigned int i = 1; i < num_glyphs; i++)
 718       if (glyphs[i - 1] + 1 != glyphs[i])
 719         num_ranges++;
 720     rangeRecord.len.set (num_ranges);
 721     if (unlikely (!c->extend (rangeRecord))) return TRACE_RETURN (false);
 722
 723     unsigned int range = 0;
 724     rangeRecord[range].start = glyphs[0];
 725     rangeRecord[range].value.set (0);
 726     for (unsigned int i = 1; i < num_glyphs; i++)
 727       if (glyphs[i - 1] + 1 != glyphs[i]) {
 728         range++;
 729         rangeRecord[range].start = glyphs[i];
 730         rangeRecord[range].value.set (i);
 731         rangeRecord[range].end = glyphs[i];
 732       } else {
 733         rangeRecord[range].end = glyphs[i];
 734       }
 735     glyphs.advance (num_glyphs);
 736     return TRACE_RETURN (true);
 737   }
 738
 739   inline bool sanitize (hb_sanitize_context_t *c) {
 740     TRACE_SANITIZE (this);
 741     return TRACE_RETURN (rangeRecord.sanitize (c));
 742   }
 743
 744   inline bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const {
 745     unsigned int i;
 746     unsigned int count = rangeRecord.len;
 747     for (i = 0; i < count; i++) {
 748       const RangeRecord &range = rangeRecord[i];
 749       if (range.value <= index &&
 750           index < (unsigned int) range.value + (range.end - range.start) &&
 751           range.intersects (glyphs))
 752         return true;
 753       else if (index < range.value)
 754         return false;
 755     }
 756     return false;
 757   }
 758
 759   template <typename set_t>
 760   inline void add_coverage (set_t *glyphs) const {
 761     unsigned int count = rangeRecord.len;
 762     for (unsigned int i = 0; i < count; i++)
 763       rangeRecord[i].add_coverage (glyphs);
 764   }
 765
 766   public:
 767   /* Older compilers need this to be public. */
 768   struct Iter {
 769     inline void init (const CoverageFormat2 &c_) {
 770       c = &c_;
 771       coverage = 0;
 772       i = 0;
 773       j = c->rangeRecord.len ? c_.rangeRecord[0].start : 0;
 774     }
 775     inline bool more (void) { return i < c->rangeRecord.len; }
 776     inline void next (void) {
 777       coverage++;
 778       if (j == c->rangeRecord[i].end) {
 779         i++;
 780         if (more ())
 781           j = c->rangeRecord[i].start;
 782         return;
 783       }
 784       j++;
 785     }
 786     inline uint16_t get_glyph (void) { return j; }
 787     inline uint16_t get_coverage (void) { return coverage; }
 788
 789     private:
 790     const struct CoverageFormat2 *c;
 791     unsigned int i, j, coverage;
 792   };
 793   private:
 794
 795   protected:
 796   USHORT        coverageFormat; /* Format identifier--format = 2 */
 797   SortedArrayOf<RangeRecord>
 798                 rangeRecord;    /* Array of glyph ranges--ordered by
 799                                  * Start GlyphID. rangeCount entries
 800                                  * long */
 801   public:
 802   DEFINE_SIZE_ARRAY (4, rangeRecord);
 803 };
 804
 805 struct Coverage
 806 {
 807   inline unsigned int get_coverage (hb_codepoint_t glyph_id) const
 808   {
 809     switch (u.format) {
 810     case 1: return u.format1.get_coverage(glyph_id);
 811     case 2: return u.format2.get_coverage(glyph_id);
 812     default:return NOT_COVERED;
 813     }
 814   }
 815
 816   inline bool serialize (hb_serialize_context_t *c,
 817                          Supplier<GlyphID> &glyphs,
 818                          unsigned int num_glyphs)
 819   {
 820     TRACE_SERIALIZE (this);
 821     if (unlikely (!c->extend_min (*this))) return TRACE_RETURN (false);
 822     unsigned int num_ranges = 1;
 823     for (unsigned int i = 1; i < num_glyphs; i++)
 824       if (glyphs[i - 1] + 1 != glyphs[i])
 825         num_ranges++;
 826     u.format.set (num_glyphs * 2 < num_ranges * 3 ? 1 : 2);
 827     switch (u.format) {
 828     case 1: return TRACE_RETURN (u.format1.serialize (c, glyphs, num_glyphs));
 829     case 2: return TRACE_RETURN (u.format2.serialize (c, glyphs, num_glyphs));
 830     default:return TRACE_RETURN (false);
 831     }
 832   }
 833
 834   inline bool sanitize (hb_sanitize_context_t *c) {
 835     TRACE_SANITIZE (this);
 836     if (!u.format.sanitize (c)) return TRACE_RETURN (false);
 837     switch (u.format) {
 838     case 1: return TRACE_RETURN (u.format1.sanitize (c));
 839     case 2: return TRACE_RETURN (u.format2.sanitize (c));
 840     default:return TRACE_RETURN (true);
 841     }
 842   }
 843
 844   inline bool intersects (const hb_set_t *glyphs) const {
 845     /* TODO speed this up */
 846     Coverage::Iter iter;
 847     for (iter.init (*this); iter.more (); iter.next ()) {
 848       if (glyphs->has (iter.get_glyph ()))
 849         return true;
 850     }
 851     return false;
 852   }
 853
 854   inline bool intersects_coverage (const hb_set_t *glyphs, unsigned int index) const {
 855     switch (u.format) {
 856     case 1: return u.format1.intersects_coverage (glyphs, index);
 857     case 2: return u.format2.intersects_coverage (glyphs, index);
 858     default:return false;
 859     }
 860   }
 861
 862   template <typename set_t>
 863   inline void add_coverage (set_t *glyphs) const {
 864     switch (u.format) {
 865     case 1: u.format1.add_coverage (glyphs); break;
 866     case 2: u.format2.add_coverage (glyphs); break;
 867     default:                                 break;
 868     }
 869   }
 870
 871   struct Iter {
 872     Iter (void) : format (0) {};
 873     inline void init (const Coverage &c_) {
 874       format = c_.u.format;
 875       switch (format) {
 876       case 1: u.format1.init (c_.u.format1); return;
 877       case 2: u.format2.init (c_.u.format2); return;
 878       default:                               return;
 879       }
 880     }
 881     inline bool more (void) {
 882       switch (format) {
 883       case 1: return u.format1.more ();
 884       case 2: return u.format2.more ();
 885       default:return false;
 886       }
 887     }
 888     inline void next (void) {
 889       switch (format) {
 890       case 1: u.format1.next (); break;
 891       case 2: u.format2.next (); break;
 892       default:                   break;
 893       }
 894     }
 895     inline uint16_t get_glyph (void) {
 896       switch (format) {
 897       case 1: return u.format1.get_glyph ();
 898       case 2: return u.format2.get_glyph ();
 899       default:return 0;
 900       }
 901     }
 902     inline uint16_t get_coverage (void) {
 903       switch (format) {
 904       case 1: return u.format1.get_coverage ();
 905       case 2: return u.format2.get_coverage ();
 906       default:return -1;
 907       }
 908     }
 909
 910     private:
 911     unsigned int format;
 912     union {
 913     CoverageFormat1::Iter       format1;
 914     CoverageFormat2::Iter       format2;
 915     } u;
 916   };
 917
 918   protected:
 919   union {
 920   USHORT                format;         /* Format identifier */
 921   CoverageFormat1       format1;
 922   CoverageFormat2       format2;
 923   } u;
 924   public:
 925   DEFINE_SIZE_UNION (2, format);
 926 };
 927
 928
 929 /*
 930  * Class Definition Table
 931  */
 932
 933 struct ClassDefFormat1
 934 {
 935   friend struct ClassDef;
 936
 937   private:
 938   inline unsigned int get_class (hb_codepoint_t glyph_id) const
 939   {
 940     if (unlikely ((unsigned int) (glyph_id - startGlyph) < classValue.len))
 941       return classValue[glyph_id - startGlyph];
 942     return 0;
 943   }
 944
 945   inline bool sanitize (hb_sanitize_context_t *c) {
 946     TRACE_SANITIZE (this);
 947     return TRACE_RETURN (c->check_struct (this) && classValue.sanitize (c));
 948   }
 949
 950   template <typename set_t>
 951   inline void add_class (set_t *glyphs, unsigned int klass) const {
 952     unsigned int count = classValue.len;
 953     for (unsigned int i = 0; i < count; i++)
 954       if (classValue[i] == klass)
 955         glyphs->add (startGlyph + i);
 956   }
 957
 958   inline bool intersects_class (const hb_set_t *glyphs, unsigned int klass) const {
 959     unsigned int count = classValue.len;
 960     if (klass == 0)
 961     {
 962       /* Match if there's any glyph that is not listed! */
 963       hb_codepoint_t g = -1;
 964       if (!hb_set_next (glyphs, &g))
 965         return false;
 966       if (g < startGlyph)
 967         return true;
 968       g = startGlyph + count - 1;
 969       if (hb_set_next (glyphs, &g))
 970         return true;
 971       /* Fall through. */
 972     }
 973     for (unsigned int i = 0; i < count; i++)
 974       if (classValue[i] == klass && glyphs->has (startGlyph + i))
 975         return true;
 976     return false;
 977   }
 978
 979   protected:
 980   USHORT        classFormat;            /* Format identifier--format = 1 */
 981   GlyphID       startGlyph;             /* First GlyphID of the classValueArray */
 982   ArrayOf<USHORT>
 983                 classValue;             /* Array of Class Values--one per GlyphID */
 984   public:
 985   DEFINE_SIZE_ARRAY (6, classValue);
 986 };
 987
 988 struct ClassDefFormat2
 989 {
 990   friend struct ClassDef;
 991
 992   private:
 993   inline unsigned int get_class (hb_codepoint_t glyph_id) const
 994   {
 995     int i = rangeRecord.search (glyph_id);
 996     if (i != -1)
 997       return rangeRecord[i].value;
 998     return 0;
 999   }
1000
1001   inline bool sanitize (hb_sanitize_context_t *c) {
1002     TRACE_SANITIZE (this);
1003     return TRACE_RETURN (rangeRecord.sanitize (c));
1004   }
1005
1006   template <typename set_t>
1007   inline void add_class (set_t *glyphs, unsigned int klass) const {
1008     unsigned int count = rangeRecord.len;
1009     for (unsigned int i = 0; i < count; i++)
1010       if (rangeRecord[i].value == klass)
1011         rangeRecord[i].add_coverage (glyphs);
1012   }
1013
1014   inline bool intersects_class (const hb_set_t *glyphs, unsigned int klass) const {
1015     unsigned int count = rangeRecord.len;
1016     if (klass == 0)
1017     {
1018       /* Match if there's any glyph that is not listed! */
1019       hb_codepoint_t g = (hb_codepoint_t) -1;
1020       for (unsigned int i = 0; i < count; i++)
1021       {
1022         if (!hb_set_next (glyphs, &g))
1023           break;
1024         if (g < rangeRecord[i].start)
1025           return true;
1026         g = rangeRecord[i].end;
1027       }
1028       if (g != (hb_codepoint_t) -1 && hb_set_next (glyphs, &g))
1029         return true;
1030       /* Fall through. */
1031     }
1032     for (unsigned int i = 0; i < count; i++)
1033       if (rangeRecord[i].value == klass && rangeRecord[i].intersects (glyphs))
1034         return true;
1035     return false;
1036   }
1037
1038   protected:
1039   USHORT        classFormat;    /* Format identifier--format = 2 */
1040   SortedArrayOf<RangeRecord>
1041                 rangeRecord;    /* Array of glyph ranges--ordered by
1042                                  * Start GlyphID */
1043   public:
1044   DEFINE_SIZE_ARRAY (4, rangeRecord);
1045 };
1046
1047 struct ClassDef
1048 {
1049   inline unsigned int get_class (hb_codepoint_t glyph_id) const
1050   {
1051     switch (u.format) {
1052     case 1: return u.format1.get_class(glyph_id);
1053     case 2: return u.format2.get_class(glyph_id);
1054     default:return 0;
1055     }
1056   }
1057
1058   inline bool sanitize (hb_sanitize_context_t *c) {
1059     TRACE_SANITIZE (this);
1060     if (!u.format.sanitize (c)) return TRACE_RETURN (false);
1061     switch (u.format) {
1062     case 1: return TRACE_RETURN (u.format1.sanitize (c));
1063     case 2: return TRACE_RETURN (u.format2.sanitize (c));
1064     default:return TRACE_RETURN (true);
1065     }
1066   }
1067
1068   inline void add_class (hb_set_t *glyphs, unsigned int klass) const {
1069     switch (u.format) {
1070     case 1: u.format1.add_class (glyphs, klass); return;
1071     case 2: u.format2.add_class (glyphs, klass); return;
1072     default:return;
1073     }
1074   }
1075
1076   inline bool intersects_class (const hb_set_t *glyphs, unsigned int klass) const {
1077     switch (u.format) {
1078     case 1: return u.format1.intersects_class (glyphs, klass);
1079     case 2: return u.format2.intersects_class (glyphs, klass);
1080     default:return false;
1081     }
1082   }
1083
1084   protected:
1085   union {
1086   USHORT                format;         /* Format identifier */
1087   ClassDefFormat1       format1;
1088   ClassDefFormat2       format2;
1089   } u;
1090   public:
1091   DEFINE_SIZE_UNION (2, format);
1092 };
1093
1094
1095 /*
1096  * Device Tables
1097  */
1098
1099 struct Device
1100 {
1101
1102   inline hb_position_t get_x_delta (hb_font_t *font) const
1103   { return get_delta (font->x_ppem, font->x_scale); }
1104
1105   inline hb_position_t get_y_delta (hb_font_t *font) const
1106   { return get_delta (font->y_ppem, font->y_scale); }
1107
1108   inline int get_delta (unsigned int ppem, int scale) const
1109   {
1110     if (!ppem) return 0;
1111
1112     int pixels = get_delta_pixels (ppem);
1113
1114     if (!pixels) return 0;
1115
1116     return (int) (pixels * (int64_t) scale / ppem);
1117   }
1118
1119
1120   inline int get_delta_pixels (unsigned int ppem_size) const
1121   {
1122     unsigned int f = deltaFormat;
1123     if (unlikely (f < 1 || f > 3))
1124       return 0;
1125
1126     if (ppem_size < startSize || ppem_size > endSize)
1127       return 0;
1128
1129     unsigned int s = ppem_size - startSize;
1130
1131     unsigned int byte = deltaValue[s >> (4 - f)];
1132     unsigned int bits = (byte >> (16 - (((s & ((1 << (4 - f)) - 1)) + 1) << f)));
1133     unsigned int mask = (0xFFFF >> (16 - (1 << f)));
1134
1135     int delta = bits & mask;
1136
1137     if ((unsigned int) delta >= ((mask + 1) >> 1))
1138       delta -= mask + 1;
1139
1140     return delta;
1141   }
1142
1143   inline unsigned int get_size (void) const
1144   {
1145     unsigned int f = deltaFormat;
1146     if (unlikely (f < 1 || f > 3 || startSize > endSize)) return 3 * USHORT::static_size;
1147     return USHORT::static_size * (4 + ((endSize - startSize) >> (4 - f)));
1148   }
1149
1150   inline bool sanitize (hb_sanitize_context_t *c) {
1151     TRACE_SANITIZE (this);
1152     return TRACE_RETURN (c->check_struct (this) && c->check_range (this, this->get_size ()));
1153   }
1154
1155   protected:
1156   USHORT        startSize;              /* Smallest size to correct--in ppem */
1157   USHORT        endSize;                /* Largest size to correct--in ppem */
1158   USHORT        deltaFormat;            /* Format of DeltaValue array data: 1, 2, or 3
1159                                          * 1    Signed 2-bit value, 8 values per uint16
1160                                          * 2    Signed 4-bit value, 4 values per uint16
1161                                          * 3    Signed 8-bit value, 2 values per uint16
1162                                          */
1163   USHORT        deltaValue[VAR];        /* Array of compressed data */
1164   public:
1165   DEFINE_SIZE_ARRAY (6, deltaValue);
1166 };
1167
1168
1169 } /* namespace OT */
1170
1171
1172 #endif /* HB_OT_LAYOUT_COMMON_PRIVATE_HH */