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