Home | History | Annotate | Download | only in src 
      1 /*
      2  * Copyright  2007,2008,2009,2010  Red Hat, Inc.
      3  * Copyright  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_OPEN_TYPE_HH
     30 #define HB_OPEN_TYPE_HH
     31 
     32 #include "hb.hh"
     33 #include "hb-blob.hh"
     34 #include "hb-face.hh"
     35 #include "hb-machinery.hh"
     36 #include "hb-subset.hh"
     37 
     38 
     39 namespace OT {
     40 
     41 
     42 /*
     43  *
     44  * The OpenType Font File: Data Types
     45  */
     46 
     47 
     48 /* "The following data types are used in the OpenType font file.
     49  *  All OpenType fonts use Motorola-style byte ordering (Big Endian):" */
     50 
     51 /*
     52  * Int types
     53  */
     54 
     55 template <bool is_signed> struct hb_signedness_int;
     56 template <> struct hb_signedness_int<false> { typedef unsigned int value; };
     57 template <> struct hb_signedness_int<true>  { typedef   signed int value; };
     58 
     59 /* Integer types in big-endian order and no alignment requirement */
     60 template <typename Type, unsigned int Size>
     61 struct IntType
     62 {
     63   typedef Type type;
     64   typedef typename hb_signedness_int<hb_is_signed<Type>::value>::value wide_type;
     65 
     66   void set (wide_type i) { v.set (i); }
     67   operator wide_type () const { return v; }
     68   bool operator == (const IntType<Type,Size> &o) const { return (Type) v == (Type) o.v; }
     69   bool operator != (const IntType<Type,Size> &o) const { return !(*this == o); }
     70   static int cmp (const IntType<Type,Size> *a, const IntType<Type,Size> *b) { return b->cmp (*a); }
     71   template <typename Type2>
     72   int cmp (Type2 a) const
     73   {
     74     Type b = v;
     75     if (sizeof (Type) < sizeof (int) && sizeof (Type2) < sizeof (int))
     76       return (int) a - (int) b;
     77     else
     78       return a < b ? -1 : a == b ? 0 : +1;
     79   }
     80   bool sanitize (hb_sanitize_context_t *c) const
     81   {
     82     TRACE_SANITIZE (this);
     83     return_trace (likely (c->check_struct (this)));
     84   }
     85   protected:
     86   BEInt<Type, Size> v;
     87   public:
     88   DEFINE_SIZE_STATIC (Size);
     89 };
     90 
     91 typedef IntType<uint8_t,  1> HBUINT8;	/* 8-bit unsigned integer. */
     92 typedef IntType<int8_t,   1> HBINT8;	/* 8-bit signed integer. */
     93 typedef IntType<uint16_t, 2> HBUINT16;	/* 16-bit unsigned integer. */
     94 typedef IntType<int16_t,  2> HBINT16;	/* 16-bit signed integer. */
     95 typedef IntType<uint32_t, 4> HBUINT32;	/* 32-bit unsigned integer. */
     96 typedef IntType<int32_t,  4> HBINT32;	/* 32-bit signed integer. */
     97 /* Note: we cannot defined a signed HBINT24 because there's no corresponding C type.
     98  * Works for unsigned, but not signed, since we rely on compiler for sign-extension. */
     99 typedef IntType<uint32_t, 3> HBUINT24;	/* 24-bit unsigned integer. */
    100 
    101 /* 16-bit signed integer (HBINT16) that describes a quantity in FUnits. */
    102 typedef HBINT16 FWORD;
    103 
    104 /* 32-bit signed integer (HBINT32) that describes a quantity in FUnits. */
    105 typedef HBINT32 FWORD32;
    106 
    107 /* 16-bit unsigned integer (HBUINT16) that describes a quantity in FUnits. */
    108 typedef HBUINT16 UFWORD;
    109 
    110 /* 16-bit signed fixed number with the low 14 bits of fraction (2.14). */
    111 struct F2DOT14 : HBINT16
    112 {
    113   // 16384 means 1<<14
    114   float to_float () const  { return ((int32_t) v) / 16384.f; }
    115   void set_float (float f) { v.set (round (f * 16384.f)); }
    116   public:
    117   DEFINE_SIZE_STATIC (2);
    118 };
    119 
    120 /* 32-bit signed fixed-point number (16.16). */
    121 struct Fixed : HBINT32
    122 {
    123   // 65536 means 1<<16
    124   float to_float () const  { return ((int32_t) v) / 65536.f; }
    125   void set_float (float f) { v.set (round (f * 65536.f)); }
    126   public:
    127   DEFINE_SIZE_STATIC (4);
    128 };
    129 
    130 /* Date represented in number of seconds since 12:00 midnight, January 1,
    131  * 1904. The value is represented as a signed 64-bit integer. */
    132 struct LONGDATETIME
    133 {
    134   bool sanitize (hb_sanitize_context_t *c) const
    135   {
    136     TRACE_SANITIZE (this);
    137     return_trace (likely (c->check_struct (this)));
    138   }
    139   protected:
    140   HBINT32 major;
    141   HBUINT32 minor;
    142   public:
    143   DEFINE_SIZE_STATIC (8);
    144 };
    145 
    146 /* Array of four uint8s (length = 32 bits) used to identify a script, language
    147  * system, feature, or baseline */
    148 struct Tag : HBUINT32
    149 {
    150   /* What the char* converters return is NOT nul-terminated.  Print using "%.4s" */
    151   operator const char* () const { return reinterpret_cast<const char *> (&this->v); }
    152   operator char* ()             { return reinterpret_cast<char *> (&this->v); }
    153   public:
    154   DEFINE_SIZE_STATIC (4);
    155 };
    156 
    157 /* Glyph index number, same as uint16 (length = 16 bits) */
    158 typedef HBUINT16 GlyphID;
    159 
    160 /* Script/language-system/feature index */
    161 struct Index : HBUINT16 {
    162   enum { NOT_FOUND_INDEX = 0xFFFFu };
    163 };
    164 DECLARE_NULL_NAMESPACE_BYTES (OT, Index);
    165 
    166 typedef Index NameID;
    167 
    168 /* Offset, Null offset = 0 */
    169 template <typename Type, bool has_null=true>
    170 struct Offset : Type
    171 {
    172   typedef Type type;
    173 
    174   bool is_null () const { return has_null && 0 == *this; }
    175 
    176   void *serialize (hb_serialize_context_t *c, const void *base)
    177   {
    178     void *t = c->start_embed<void> ();
    179     this->set ((char *) t - (char *) base); /* TODO(serialize) Overflow? */
    180     return t;
    181   }
    182 
    183   public:
    184   DEFINE_SIZE_STATIC (sizeof (Type));
    185 };
    186 
    187 typedef Offset<HBUINT16> Offset16;
    188 typedef Offset<HBUINT32> Offset32;
    189 
    190 
    191 /* CheckSum */
    192 struct CheckSum : HBUINT32
    193 {
    194   /* This is reference implementation from the spec. */
    195   static uint32_t CalcTableChecksum (const HBUINT32 *Table, uint32_t Length)
    196   {
    197     uint32_t Sum = 0L;
    198     assert (0 == (Length & 3));
    199     const HBUINT32 *EndPtr = Table + Length / HBUINT32::static_size;
    200 
    201     while (Table < EndPtr)
    202       Sum += *Table++;
    203     return Sum;
    204   }
    205 
    206   /* Note: data should be 4byte aligned and have 4byte padding at the end. */
    207   void set_for_data (const void *data, unsigned int length)
    208   { set (CalcTableChecksum ((const HBUINT32 *) data, length)); }
    209 
    210   public:
    211   DEFINE_SIZE_STATIC (4);
    212 };
    213 
    214 
    215 /*
    216  * Version Numbers
    217  */
    218 
    219 template <typename FixedType=HBUINT16>
    220 struct FixedVersion
    221 {
    222   uint32_t to_int () const { return (major << (sizeof (FixedType) * 8)) + minor; }
    223 
    224   bool sanitize (hb_sanitize_context_t *c) const
    225   {
    226     TRACE_SANITIZE (this);
    227     return_trace (c->check_struct (this));
    228   }
    229 
    230   FixedType major;
    231   FixedType minor;
    232   public:
    233   DEFINE_SIZE_STATIC (2 * sizeof (FixedType));
    234 };
    235 
    236 
    237 /*
    238  * Template subclasses of Offset that do the dereferencing.
    239  * Use: (base+offset)
    240  */
    241 
    242 template <typename Type, bool has_null>
    243 struct _hb_has_null
    244 {
    245   static const Type *get_null () { return nullptr; }
    246   static Type *get_crap ()       { return nullptr; }
    247 };
    248 template <typename Type>
    249 struct _hb_has_null<Type, true>
    250 {
    251   static const Type *get_null () { return &Null(Type); }
    252   static Type *get_crap ()       { return &Crap(Type); }
    253 };
    254 
    255 template <typename Type, typename OffsetType=HBUINT16, bool has_null=true>
    256 struct OffsetTo : Offset<OffsetType, has_null>
    257 {
    258   const Type& operator () (const void *base) const
    259   {
    260     if (unlikely (this->is_null ())) return *_hb_has_null<Type, has_null>::get_null ();
    261     return StructAtOffset<const Type> (base, *this);
    262   }
    263   Type& operator () (void *base) const
    264   {
    265     if (unlikely (this->is_null ())) return *_hb_has_null<Type, has_null>::get_crap ();
    266     return StructAtOffset<Type> (base, *this);
    267   }
    268 
    269   Type& serialize (hb_serialize_context_t *c, const void *base)
    270   {
    271     return * (Type *) Offset<OffsetType>::serialize (c, base);
    272   }
    273 
    274   template <typename T>
    275   void serialize_subset (hb_subset_context_t *c, const T &src, const void *base)
    276   {
    277     if (&src == &Null (T))
    278     {
    279       this->set (0);
    280       return;
    281     }
    282     serialize (c->serializer, base);
    283     if (!src.subset (c))
    284       this->set (0);
    285   }
    286 
    287   bool sanitize_shallow (hb_sanitize_context_t *c, const void *base) const
    288   {
    289     TRACE_SANITIZE (this);
    290     if (unlikely (!c->check_struct (this))) return_trace (false);
    291     if (unlikely (this->is_null ())) return_trace (true);
    292     if (unlikely (!c->check_range (base, *this))) return_trace (false);
    293     return_trace (true);
    294   }
    295 
    296   bool sanitize (hb_sanitize_context_t *c, const void *base) const
    297   {
    298     TRACE_SANITIZE (this);
    299     return_trace (sanitize_shallow (c, base) &&
    300 		  (this->is_null () ||
    301 		   StructAtOffset<Type> (base, *this).sanitize (c) ||
    302 		   neuter (c)));
    303   }
    304   template <typename T1>
    305   bool sanitize (hb_sanitize_context_t *c, const void *base, T1 d1) const
    306   {
    307     TRACE_SANITIZE (this);
    308     return_trace (sanitize_shallow (c, base) &&
    309 		  (this->is_null () ||
    310 		   StructAtOffset<Type> (base, *this).sanitize (c, d1) ||
    311 		   neuter (c)));
    312   }
    313   template <typename T1, typename T2>
    314   bool sanitize (hb_sanitize_context_t *c, const void *base, T1 d1, T2 d2) const
    315   {
    316     TRACE_SANITIZE (this);
    317     return_trace (sanitize_shallow (c, base) &&
    318 		  (this->is_null () ||
    319 		   StructAtOffset<Type> (base, *this).sanitize (c, d1, d2) ||
    320 		   neuter (c)));
    321   }
    322   template <typename T1, typename T2, typename T3>
    323   bool sanitize (hb_sanitize_context_t *c, const void *base, T1 d1, T2 d2, T3 d3) const
    324   {
    325     TRACE_SANITIZE (this);
    326     return_trace (sanitize_shallow (c, base) &&
    327 		  (this->is_null () ||
    328 		   StructAtOffset<Type> (base, *this).sanitize (c, d1, d2, d3) ||
    329 		   neuter (c)));
    330   }
    331 
    332   /* Set the offset to Null */
    333   bool neuter (hb_sanitize_context_t *c) const
    334   {
    335     if (!has_null) return false;
    336     return c->try_set (this, 0);
    337   }
    338   DEFINE_SIZE_STATIC (sizeof (OffsetType));
    339 };
    340 template <typename Type, bool has_null=true> struct LOffsetTo : OffsetTo<Type, HBUINT32, has_null> {};
    341 
    342 template <typename Base, typename OffsetType, bool has_null, typename Type>
    343 static inline const Type& operator + (const Base &base, const OffsetTo<Type, OffsetType, has_null> &offset) { return offset (base); }
    344 template <typename Base, typename OffsetType, bool has_null, typename Type>
    345 static inline Type& operator + (Base &base, OffsetTo<Type, OffsetType, has_null> &offset) { return offset (base); }
    346 
    347 
    348 /*
    349  * Array Types
    350  */
    351 
    352 template <typename Type>
    353 struct UnsizedArrayOf
    354 {
    355   typedef Type ItemType;
    356   enum { item_size = hb_static_size (Type) };
    357 
    358   HB_NO_CREATE_COPY_ASSIGN_TEMPLATE (UnsizedArrayOf, Type);
    359 
    360   const Type& operator [] (int i_) const
    361   {
    362     unsigned int i = (unsigned int) i_;
    363     const Type *p = &arrayZ[i];
    364     if (unlikely (p < arrayZ)) return Null (Type); /* Overflowed. */
    365     return *p;
    366   }
    367   Type& operator [] (int i_)
    368   {
    369     unsigned int i = (unsigned int) i_;
    370     Type *p = &arrayZ[i];
    371     if (unlikely (p < arrayZ)) return Crap (Type); /* Overflowed. */
    372     return *p;
    373   }
    374 
    375   unsigned int get_size (unsigned int len) const
    376   { return len * Type::static_size; }
    377 
    378   template <typename T> operator T * () { return arrayZ; }
    379   template <typename T> operator const T * () const { return arrayZ; }
    380   hb_array_t<Type> as_array (unsigned int len)
    381   { return hb_array (arrayZ, len); }
    382   hb_array_t<const Type> as_array (unsigned int len) const
    383   { return hb_array (arrayZ, len); }
    384   operator hb_array_t<Type> ()             { return as_array (); }
    385   operator hb_array_t<const Type> () const { return as_array (); }
    386 
    387   template <typename T>
    388   Type &lsearch (unsigned int len, const T &x, Type &not_found = Crap (Type))
    389   { return *as_array (len).lsearch (x, &not_found); }
    390   template <typename T>
    391   const Type &lsearch (unsigned int len, const T &x, const Type &not_found = Null (Type)) const
    392   { return *as_array (len).lsearch (x, &not_found); }
    393 
    394   void qsort (unsigned int len, unsigned int start = 0, unsigned int end = (unsigned int) -1)
    395   { as_array (len).qsort (start, end); }
    396 
    397   bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
    398   {
    399     TRACE_SANITIZE (this);
    400     if (unlikely (!sanitize_shallow (c, count))) return_trace (false);
    401 
    402     /* Note: for structs that do not reference other structs,
    403      * we do not need to call their sanitize() as we already did
    404      * a bound check on the aggregate array size.  We just include
    405      * a small unreachable expression to make sure the structs
    406      * pointed to do have a simple sanitize(), ie. they do not
    407      * reference other structs via offsets.
    408      */
    409     (void) (false && arrayZ[0].sanitize (c));
    410 
    411     return_trace (true);
    412   }
    413   bool sanitize (hb_sanitize_context_t *c, unsigned int count, const void *base) const
    414   {
    415     TRACE_SANITIZE (this);
    416     if (unlikely (!sanitize_shallow (c, count))) return_trace (false);
    417     for (unsigned int i = 0; i < count; i++)
    418       if (unlikely (!arrayZ[i].sanitize (c, base)))
    419 	return_trace (false);
    420     return_trace (true);
    421   }
    422   template <typename T>
    423   bool sanitize (hb_sanitize_context_t *c, unsigned int count, const void *base, T user_data) const
    424   {
    425     TRACE_SANITIZE (this);
    426     if (unlikely (!sanitize_shallow (c, count))) return_trace (false);
    427     for (unsigned int i = 0; i < count; i++)
    428       if (unlikely (!arrayZ[i].sanitize (c, base, user_data)))
    429 	return_trace (false);
    430     return_trace (true);
    431   }
    432 
    433   bool sanitize_shallow (hb_sanitize_context_t *c, unsigned int count) const
    434   {
    435     TRACE_SANITIZE (this);
    436     return_trace (c->check_array (arrayZ, count));
    437   }
    438 
    439   public:
    440   Type		arrayZ[VAR];
    441   public:
    442   DEFINE_SIZE_UNBOUNDED (0);
    443 };
    444 
    445 /* Unsized array of offset's */
    446 template <typename Type, typename OffsetType, bool has_null=true>
    447 struct UnsizedOffsetArrayOf : UnsizedArrayOf<OffsetTo<Type, OffsetType, has_null> > {};
    448 
    449 /* Unsized array of offsets relative to the beginning of the array itself. */
    450 template <typename Type, typename OffsetType, bool has_null=true>
    451 struct UnsizedOffsetListOf : UnsizedOffsetArrayOf<Type, OffsetType, has_null>
    452 {
    453   const Type& operator [] (int i_) const
    454   {
    455     unsigned int i = (unsigned int) i_;
    456     const OffsetTo<Type, OffsetType, has_null> *p = &this->arrayZ[i];
    457     if (unlikely (p < this->arrayZ)) return Null (Type); /* Overflowed. */
    458     return this+*p;
    459   }
    460   Type& operator [] (int i_)
    461   {
    462     unsigned int i = (unsigned int) i_;
    463     const OffsetTo<Type, OffsetType, has_null> *p = &this->arrayZ[i];
    464     if (unlikely (p < this->arrayZ)) return Crap (Type); /* Overflowed. */
    465     return this+*p;
    466   }
    467 
    468 
    469   bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
    470   {
    471     TRACE_SANITIZE (this);
    472     return_trace ((UnsizedOffsetArrayOf<Type, OffsetType, has_null>::sanitize (c, count, this)));
    473   }
    474   template <typename T>
    475   bool sanitize (hb_sanitize_context_t *c, unsigned int count, T user_data) const
    476   {
    477     TRACE_SANITIZE (this);
    478     return_trace ((UnsizedOffsetArrayOf<Type, OffsetType, has_null>::sanitize (c, count, this, user_data)));
    479   }
    480 };
    481 
    482 /* An array with sorted elements.  Supports binary searching. */
    483 template <typename Type>
    484 struct SortedUnsizedArrayOf : UnsizedArrayOf<Type>
    485 {
    486   hb_sorted_array_t<Type> as_array (unsigned int len)
    487   { return hb_sorted_array (this->arrayZ, len); }
    488   hb_sorted_array_t<const Type> as_array (unsigned int len) const
    489   { return hb_sorted_array (this->arrayZ, len); }
    490   operator hb_sorted_array_t<Type> ()             { return as_array (); }
    491   operator hb_sorted_array_t<const Type> () const { return as_array (); }
    492 
    493   template <typename T>
    494   Type &bsearch (unsigned int len, const T &x, Type &not_found = Crap (Type))
    495   { return *as_array (len).bsearch (x, &not_found); }
    496   template <typename T>
    497   const Type &bsearch (unsigned int len, const T &x, const Type &not_found = Null (Type)) const
    498   { return *as_array (len).bsearch (x, &not_found); }
    499   template <typename T>
    500   bool bfind (unsigned int len, const T &x, unsigned int *i = nullptr,
    501 		     hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
    502 		     unsigned int to_store = (unsigned int) -1) const
    503   { return as_array (len).bfind (x, i, not_found, to_store); }
    504 };
    505 
    506 
    507 /* An array with a number of elements. */
    508 template <typename Type, typename LenType=HBUINT16>
    509 struct ArrayOf
    510 {
    511   typedef Type ItemType;
    512   enum { item_size = hb_static_size (Type) };
    513 
    514   HB_NO_CREATE_COPY_ASSIGN_TEMPLATE2 (ArrayOf, Type, LenType);
    515 
    516   const Type& operator [] (int i_) const
    517   {
    518     unsigned int i = (unsigned int) i_;
    519     if (unlikely (i >= len)) return Null (Type);
    520     return arrayZ[i];
    521   }
    522   Type& operator [] (int i_)
    523   {
    524     unsigned int i = (unsigned int) i_;
    525     if (unlikely (i >= len)) return Crap (Type);
    526     return arrayZ[i];
    527   }
    528 
    529   unsigned int get_size () const
    530   { return len.static_size + len * Type::static_size; }
    531 
    532   hb_array_t<Type> as_array ()
    533   { return hb_array (arrayZ, len); }
    534   hb_array_t<const Type> as_array () const
    535   { return hb_array (arrayZ, len); }
    536   operator hb_array_t<Type> (void)             { return as_array (); }
    537   operator hb_array_t<const Type> (void) const { return as_array (); }
    538 
    539   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
    540   { return as_array ().sub_array (start_offset, count);}
    541   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
    542   { return as_array ().sub_array (start_offset, count);}
    543   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
    544   { return as_array ().sub_array (start_offset, count);}
    545   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
    546   { return as_array ().sub_array (start_offset, count);}
    547 
    548   bool serialize (hb_serialize_context_t *c, unsigned int items_len)
    549   {
    550     TRACE_SERIALIZE (this);
    551     if (unlikely (!c->extend_min (*this))) return_trace (false);
    552     len.set (items_len); /* TODO(serialize) Overflow? */
    553     if (unlikely (!c->extend (*this))) return_trace (false);
    554     return_trace (true);
    555   }
    556   template <typename T>
    557   bool serialize (hb_serialize_context_t *c, hb_array_t<const T> items)
    558   {
    559     TRACE_SERIALIZE (this);
    560     if (unlikely (!serialize (c, items.len))) return_trace (false);
    561     for (unsigned int i = 0; i < items.len; i++)
    562       hb_assign (arrayZ[i], items[i]);
    563     return_trace (true);
    564   }
    565 
    566   bool sanitize (hb_sanitize_context_t *c) const
    567   {
    568     TRACE_SANITIZE (this);
    569     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    570 
    571     /* Note: for structs that do not reference other structs,
    572      * we do not need to call their sanitize() as we already did
    573      * a bound check on the aggregate array size.  We just include
    574      * a small unreachable expression to make sure the structs
    575      * pointed to do have a simple sanitize(), ie. they do not
    576      * reference other structs via offsets.
    577      */
    578     (void) (false && arrayZ[0].sanitize (c));
    579 
    580     return_trace (true);
    581   }
    582   bool sanitize (hb_sanitize_context_t *c, const void *base) const
    583   {
    584     TRACE_SANITIZE (this);
    585     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    586     unsigned int count = len;
    587     for (unsigned int i = 0; i < count; i++)
    588       if (unlikely (!arrayZ[i].sanitize (c, base)))
    589 	return_trace (false);
    590     return_trace (true);
    591   }
    592   template <typename T>
    593   bool sanitize (hb_sanitize_context_t *c, const void *base, T user_data) const
    594   {
    595     TRACE_SANITIZE (this);
    596     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    597     unsigned int count = len;
    598     for (unsigned int i = 0; i < count; i++)
    599       if (unlikely (!arrayZ[i].sanitize (c, base, user_data)))
    600 	return_trace (false);
    601     return_trace (true);
    602   }
    603 
    604   template <typename T>
    605   Type &lsearch (const T &x, Type &not_found = Crap (Type))
    606   { return *as_array ().lsearch (x, &not_found); }
    607   template <typename T>
    608   const Type &lsearch (const T &x, const Type &not_found = Null (Type)) const
    609   { return *as_array ().lsearch (x, &not_found); }
    610 
    611   void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
    612   { as_array ().qsort (start, end); }
    613 
    614   bool sanitize_shallow (hb_sanitize_context_t *c) const
    615   {
    616     TRACE_SANITIZE (this);
    617     return_trace (len.sanitize (c) && c->check_array (arrayZ, len));
    618   }
    619 
    620   public:
    621   LenType	len;
    622   Type		arrayZ[VAR];
    623   public:
    624   DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ);
    625 };
    626 template <typename Type> struct LArrayOf : ArrayOf<Type, HBUINT32> {};
    627 typedef ArrayOf<HBUINT8, HBUINT8> PString;
    628 
    629 /* Array of Offset's */
    630 template <typename Type>
    631 struct OffsetArrayOf : ArrayOf<OffsetTo<Type, HBUINT16> > {};
    632 template <typename Type>
    633 struct LOffsetArrayOf : ArrayOf<OffsetTo<Type, HBUINT32> > {};
    634 template <typename Type>
    635 struct LOffsetLArrayOf : ArrayOf<OffsetTo<Type, HBUINT32>, HBUINT32> {};
    636 
    637 /* Array of offsets relative to the beginning of the array itself. */
    638 template <typename Type>
    639 struct OffsetListOf : OffsetArrayOf<Type>
    640 {
    641   const Type& operator [] (int i_) const
    642   {
    643     unsigned int i = (unsigned int) i_;
    644     if (unlikely (i >= this->len)) return Null (Type);
    645     return this+this->arrayZ[i];
    646   }
    647   const Type& operator [] (int i_)
    648   {
    649     unsigned int i = (unsigned int) i_;
    650     if (unlikely (i >= this->len)) return Crap (Type);
    651     return this+this->arrayZ[i];
    652   }
    653 
    654   bool subset (hb_subset_context_t *c) const
    655   {
    656     TRACE_SUBSET (this);
    657     struct OffsetListOf<Type> *out = c->serializer->embed (*this);
    658     if (unlikely (!out)) return_trace (false);
    659     unsigned int count = this->len;
    660     for (unsigned int i = 0; i < count; i++)
    661       out->arrayZ[i].serialize_subset (c, (*this)[i], out);
    662     return_trace (true);
    663   }
    664 
    665   bool sanitize (hb_sanitize_context_t *c) const
    666   {
    667     TRACE_SANITIZE (this);
    668     return_trace (OffsetArrayOf<Type>::sanitize (c, this));
    669   }
    670   template <typename T>
    671   bool sanitize (hb_sanitize_context_t *c, T user_data) const
    672   {
    673     TRACE_SANITIZE (this);
    674     return_trace (OffsetArrayOf<Type>::sanitize (c, this, user_data));
    675   }
    676 };
    677 
    678 /* An array starting at second element. */
    679 template <typename Type, typename LenType=HBUINT16>
    680 struct HeadlessArrayOf
    681 {
    682   enum { item_size = Type::static_size };
    683 
    684   HB_NO_CREATE_COPY_ASSIGN_TEMPLATE2 (HeadlessArrayOf, Type, LenType);
    685 
    686   const Type& operator [] (int i_) const
    687   {
    688     unsigned int i = (unsigned int) i_;
    689     if (unlikely (i >= lenP1 || !i)) return Null (Type);
    690     return arrayZ[i-1];
    691   }
    692   Type& operator [] (int i_)
    693   {
    694     unsigned int i = (unsigned int) i_;
    695     if (unlikely (i >= lenP1 || !i)) return Crap (Type);
    696     return arrayZ[i-1];
    697   }
    698   unsigned int get_size () const
    699   { return lenP1.static_size + (lenP1 ? lenP1 - 1 : 0) * Type::static_size; }
    700 
    701   bool serialize (hb_serialize_context_t *c,
    702 		  hb_array_t<const Type> items)
    703   {
    704     TRACE_SERIALIZE (this);
    705     if (unlikely (!c->extend_min (*this))) return_trace (false);
    706     lenP1.set (items.len + 1); /* TODO(serialize) Overflow? */
    707     if (unlikely (!c->extend (*this))) return_trace (false);
    708     for (unsigned int i = 0; i < items.len; i++)
    709       arrayZ[i] = items[i];
    710     return_trace (true);
    711   }
    712 
    713   bool sanitize (hb_sanitize_context_t *c) const
    714   {
    715     TRACE_SANITIZE (this);
    716     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    717 
    718     /* Note: for structs that do not reference other structs,
    719      * we do not need to call their sanitize() as we already did
    720      * a bound check on the aggregate array size.  We just include
    721      * a small unreachable expression to make sure the structs
    722      * pointed to do have a simple sanitize(), ie. they do not
    723      * reference other structs via offsets.
    724      */
    725     (void) (false && arrayZ[0].sanitize (c));
    726 
    727     return_trace (true);
    728   }
    729 
    730   private:
    731   bool sanitize_shallow (hb_sanitize_context_t *c) const
    732   {
    733     TRACE_SANITIZE (this);
    734     return_trace (lenP1.sanitize (c) &&
    735 		  (!lenP1 || c->check_array (arrayZ, lenP1 - 1)));
    736   }
    737 
    738   public:
    739   LenType	lenP1;
    740   Type		arrayZ[VAR];
    741   public:
    742   DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ);
    743 };
    744 
    745 /* An array storing length-1. */
    746 template <typename Type, typename LenType=HBUINT16>
    747 struct ArrayOfM1
    748 {
    749   HB_NO_CREATE_COPY_ASSIGN_TEMPLATE2 (ArrayOfM1, Type, LenType);
    750 
    751   const Type& operator [] (int i_) const
    752   {
    753     unsigned int i = (unsigned int) i_;
    754     if (unlikely (i > lenM1)) return Null (Type);
    755     return arrayZ[i];
    756   }
    757   Type& operator [] (int i_)
    758   {
    759     unsigned int i = (unsigned int) i_;
    760     if (unlikely (i > lenM1)) return Crap (Type);
    761     return arrayZ[i];
    762   }
    763   unsigned int get_size () const
    764   { return lenM1.static_size + (lenM1 + 1) * Type::static_size; }
    765 
    766   template <typename T>
    767   bool sanitize (hb_sanitize_context_t *c, const void *base, T user_data) const
    768   {
    769     TRACE_SANITIZE (this);
    770     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    771     unsigned int count = lenM1 + 1;
    772     for (unsigned int i = 0; i < count; i++)
    773       if (unlikely (!arrayZ[i].sanitize (c, base, user_data)))
    774 	return_trace (false);
    775     return_trace (true);
    776   }
    777 
    778   private:
    779   bool sanitize_shallow (hb_sanitize_context_t *c) const
    780   {
    781     TRACE_SANITIZE (this);
    782     return_trace (lenM1.sanitize (c) &&
    783 		  (c->check_array (arrayZ, lenM1 + 1)));
    784   }
    785 
    786   public:
    787   LenType	lenM1;
    788   Type		arrayZ[VAR];
    789   public:
    790   DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ);
    791 };
    792 
    793 /* An array with sorted elements.  Supports binary searching. */
    794 template <typename Type, typename LenType=HBUINT16>
    795 struct SortedArrayOf : ArrayOf<Type, LenType>
    796 {
    797   hb_sorted_array_t<Type> as_array ()
    798   { return hb_sorted_array (this->arrayZ, this->len); }
    799   hb_sorted_array_t<const Type> as_array () const
    800   { return hb_sorted_array (this->arrayZ, this->len); }
    801   operator hb_sorted_array_t<Type> ()             { return as_array (); }
    802   operator hb_sorted_array_t<const Type> () const { return as_array (); }
    803 
    804   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
    805   { return as_array ().sub_array (start_offset, count);}
    806   hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const
    807   { return as_array ().sub_array (start_offset, count);}
    808   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
    809   { return as_array ().sub_array (start_offset, count);}
    810   hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */)
    811   { return as_array ().sub_array (start_offset, count);}
    812 
    813   template <typename T>
    814   Type &bsearch (const T &x, Type &not_found = Crap (Type))
    815   { return *as_array ().bsearch (x, &not_found); }
    816   template <typename T>
    817   const Type &bsearch (const T &x, const Type &not_found = Null (Type)) const
    818   { return *as_array ().bsearch (x, &not_found); }
    819   template <typename T>
    820   bool bfind (const T &x, unsigned int *i = nullptr,
    821 		     hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE,
    822 		     unsigned int to_store = (unsigned int) -1) const
    823   { return as_array ().bfind (x, i, not_found, to_store); }
    824 };
    825 
    826 /*
    827  * Binary-search arrays
    828  */
    829 
    830 template <typename LenType=HBUINT16>
    831 struct BinSearchHeader
    832 {
    833   operator uint32_t () const { return len; }
    834 
    835   bool sanitize (hb_sanitize_context_t *c) const
    836   {
    837     TRACE_SANITIZE (this);
    838     return_trace (c->check_struct (this));
    839   }
    840 
    841   void set (unsigned int v)
    842   {
    843     len.set (v);
    844     assert (len == v);
    845     entrySelector.set (MAX (1u, hb_bit_storage (v)) - 1);
    846     searchRange.set (16 * (1u << entrySelector));
    847     rangeShift.set (v * 16 > searchRange
    848 		    ? 16 * v - searchRange
    849 		    : 0);
    850   }
    851 
    852   protected:
    853   LenType	len;
    854   LenType	searchRange;
    855   LenType	entrySelector;
    856   LenType	rangeShift;
    857 
    858   public:
    859   DEFINE_SIZE_STATIC (8);
    860 };
    861 
    862 template <typename Type, typename LenType=HBUINT16>
    863 struct BinSearchArrayOf : SortedArrayOf<Type, BinSearchHeader<LenType> > {};
    864 
    865 
    866 struct VarSizedBinSearchHeader
    867 {
    868 
    869   bool sanitize (hb_sanitize_context_t *c) const
    870   {
    871     TRACE_SANITIZE (this);
    872     return_trace (c->check_struct (this));
    873   }
    874 
    875   HBUINT16	unitSize;	/* Size of a lookup unit for this search in bytes. */
    876   HBUINT16	nUnits;		/* Number of units of the preceding size to be searched. */
    877   HBUINT16	searchRange;	/* The value of unitSize times the largest power of 2
    878 				 * that is less than or equal to the value of nUnits. */
    879   HBUINT16	entrySelector;	/* The log base 2 of the largest power of 2 less than
    880 				 * or equal to the value of nUnits. */
    881   HBUINT16	rangeShift;	/* The value of unitSize times the difference of the
    882 				 * value of nUnits minus the largest power of 2 less
    883 				 * than or equal to the value of nUnits. */
    884   public:
    885   DEFINE_SIZE_STATIC (10);
    886 };
    887 
    888 template <typename Type>
    889 struct VarSizedBinSearchArrayOf
    890 {
    891   enum { item_size = Type::static_size };
    892 
    893   HB_NO_CREATE_COPY_ASSIGN_TEMPLATE (VarSizedBinSearchArrayOf, Type);
    894 
    895   bool last_is_terminator () const
    896   {
    897     if (unlikely (!header.nUnits)) return false;
    898 
    899     /* Gah.
    900      *
    901      * "The number of termination values that need to be included is table-specific.
    902      * The value that indicates binary search termination is 0xFFFF." */
    903     const HBUINT16 *words = &StructAtOffset<HBUINT16> (&bytesZ, (header.nUnits - 1) * header.unitSize);
    904     unsigned int count = Type::TerminationWordCount;
    905     for (unsigned int i = 0; i < count; i++)
    906       if (words[i] != 0xFFFFu)
    907         return false;
    908     return true;
    909   }
    910 
    911   const Type& operator [] (int i_) const
    912   {
    913     unsigned int i = (unsigned int) i_;
    914     if (unlikely (i >= get_length ())) return Null (Type);
    915     return StructAtOffset<Type> (&bytesZ, i * header.unitSize);
    916   }
    917   Type& operator [] (int i_)
    918   {
    919     unsigned int i = (unsigned int) i_;
    920     if (unlikely (i >= get_length ())) return Crap (Type);
    921     return StructAtOffset<Type> (&bytesZ, i * header.unitSize);
    922   }
    923   unsigned int get_length () const
    924   { return header.nUnits - last_is_terminator (); }
    925   unsigned int get_size () const
    926   { return header.static_size + header.nUnits * header.unitSize; }
    927 
    928   bool sanitize (hb_sanitize_context_t *c) const
    929   {
    930     TRACE_SANITIZE (this);
    931     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    932 
    933     /* Note: for structs that do not reference other structs,
    934      * we do not need to call their sanitize() as we already did
    935      * a bound check on the aggregate array size.  We just include
    936      * a small unreachable expression to make sure the structs
    937      * pointed to do have a simple sanitize(), ie. they do not
    938      * reference other structs via offsets.
    939      */
    940     (void) (false && StructAtOffset<Type> (&bytesZ, 0).sanitize (c));
    941 
    942     return_trace (true);
    943   }
    944   bool sanitize (hb_sanitize_context_t *c, const void *base) const
    945   {
    946     TRACE_SANITIZE (this);
    947     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    948     unsigned int count = get_length ();
    949     for (unsigned int i = 0; i < count; i++)
    950       if (unlikely (!(*this)[i].sanitize (c, base)))
    951 	return_trace (false);
    952     return_trace (true);
    953   }
    954   template <typename T>
    955   bool sanitize (hb_sanitize_context_t *c, const void *base, T user_data) const
    956   {
    957     TRACE_SANITIZE (this);
    958     if (unlikely (!sanitize_shallow (c))) return_trace (false);
    959     unsigned int count = get_length ();
    960     for (unsigned int i = 0; i < count; i++)
    961       if (unlikely (!(*this)[i].sanitize (c, base, user_data)))
    962 	return_trace (false);
    963     return_trace (true);
    964   }
    965 
    966   template <typename T>
    967   const Type *bsearch (const T &key) const
    968   {
    969     unsigned int size = header.unitSize;
    970     int min = 0, max = (int) get_length () - 1;
    971     while (min <= max)
    972     {
    973       int mid = ((unsigned int) min + (unsigned int) max) / 2;
    974       const Type *p = (const Type *) (((const char *) &bytesZ) + (mid * size));
    975       int c = p->cmp (key);
    976       if (c < 0) max = mid - 1;
    977       else if (c > 0) min = mid + 1;
    978       else return p;
    979     }
    980     return nullptr;
    981   }
    982 
    983   private:
    984   bool sanitize_shallow (hb_sanitize_context_t *c) const
    985   {
    986     TRACE_SANITIZE (this);
    987     return_trace (header.sanitize (c) &&
    988 		  Type::static_size <= header.unitSize &&
    989 		  c->check_range (bytesZ.arrayZ,
    990 				  header.nUnits,
    991 				  header.unitSize));
    992   }
    993 
    994   protected:
    995   VarSizedBinSearchHeader	header;
    996   UnsizedArrayOf<HBUINT8>	bytesZ;
    997   public:
    998   DEFINE_SIZE_ARRAY (10, bytesZ);
    999 };
   1000 
   1001 
   1002 } /* namespace OT */
   1003 
   1004 
   1005 #endif /* HB_OPEN_TYPE_HH */
   1006