src/hb-open-type.hh

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