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, 57 unsigned int Size = sizeof (Type)> 58 struct IntType 59 { 60 typedef Type type; 61 62 IntType () = default; IntTypeOT::IntType63 explicit constexpr IntType (Type V) : v {V} {} operator =OT::IntType64 IntType& operator = (Type i) { v = i; return *this; } 65 /* For reason we define cast out operator for signed/unsigned, instead of Type, see: 66 * https://github.com/harfbuzz/harfbuzz/pull/2875/commits/09836013995cab2b9f07577a179ad7b024130467 */ operator hb_conditional<hb_is_signed(Type),signed,unsigned>OT::IntType67 operator hb_conditional<hb_is_signed (Type), signed, unsigned> () const { return v; } 68 operator ==OT::IntType69 bool operator == (const IntType &o) const { return (Type) v == (Type) o.v; } operator !=OT::IntType70 bool operator != (const IntType &o) const { return !(*this == o); } 71 operator +=OT::IntType72 IntType& operator += (unsigned count) { *this = *this + count; return *this; } operator -=OT::IntType73 IntType& operator -= (unsigned count) { *this = *this - count; return *this; } operator ++OT::IntType74 IntType& operator ++ () { *this += 1; return *this; } operator --OT::IntType75 IntType& operator -- () { *this -= 1; return *this; } operator ++OT::IntType76 IntType operator ++ (int) { IntType c (*this); ++*this; return c; } operator --OT::IntType77 IntType operator -- (int) { IntType c (*this); --*this; return c; } 78 cmpOT::IntType79 HB_INTERNAL static int cmp (const IntType *a, const IntType *b) 80 { return b->cmp (*a); } cmpOT::IntType81 HB_INTERNAL static int cmp (const void *a, const void *b) 82 { 83 IntType *pa = (IntType *) a; 84 IntType *pb = (IntType *) b; 85 86 return pb->cmp (*pa); 87 } 88 template <typename Type2, 89 hb_enable_if (hb_is_integral (Type2) && 90 sizeof (Type2) < sizeof (int) && 91 sizeof (Type) < sizeof (int))> cmpOT::IntType92 int cmp (Type2 a) const 93 { 94 Type b = v; 95 return (int) a - (int) b; 96 } 97 template <typename Type2, 98 hb_enable_if (hb_is_convertible (Type2, Type))> cmpOT::IntType99 int cmp (Type2 a) const 100 { 101 Type b = v; 102 return a < b ? -1 : a == b ? 0 : +1; 103 } sanitizeOT::IntType104 bool sanitize (hb_sanitize_context_t *c) const 105 { 106 TRACE_SANITIZE (this); 107 return_trace (likely (c->check_struct (this))); 108 } 109 protected: 110 BEInt<Type, Size> v; 111 public: 112 DEFINE_SIZE_STATIC (Size); 113 }; 114 115 typedef IntType<uint8_t> HBUINT8; /* 8-bit unsigned integer. */ 116 typedef IntType<int8_t> HBINT8; /* 8-bit signed integer. */ 117 typedef IntType<uint16_t> HBUINT16; /* 16-bit unsigned integer. */ 118 typedef IntType<int16_t> HBINT16; /* 16-bit signed integer. */ 119 typedef IntType<uint32_t> HBUINT32; /* 32-bit unsigned integer. */ 120 typedef IntType<int32_t> HBINT32; /* 32-bit signed integer. */ 121 /* Note: we cannot defined a signed HBINT24 because there's no corresponding C type. 122 * Works for unsigned, but not signed, since we rely on compiler for sign-extension. */ 123 typedef IntType<uint32_t, 3> HBUINT24; /* 24-bit unsigned integer. */ 124 125 /* 16-bit signed integer (HBINT16) that describes a quantity in FUnits. */ 126 typedef HBINT16 FWORD; 127 128 /* 32-bit signed integer (HBINT32) that describes a quantity in FUnits. */ 129 typedef HBINT32 FWORD32; 130 131 /* 16-bit unsigned integer (HBUINT16) that describes a quantity in FUnits. */ 132 typedef HBUINT16 UFWORD; 133 134 /* 16-bit signed fixed number with the low 14 bits of fraction (2.14). */ 135 struct F2DOT14 : HBINT16 136 { operator =OT::F2DOT14137 F2DOT14& operator = (uint16_t i ) { HBINT16::operator= (i); return *this; } 138 // 16384 means 1<<14 to_floatOT::F2DOT14139 float to_float () const { return ((int32_t) v) / 16384.f; } set_floatOT::F2DOT14140 void set_float (float f) { v = roundf (f * 16384.f); } 141 public: 142 DEFINE_SIZE_STATIC (2); 143 }; 144 145 /* 32-bit signed fixed-point number (16.16). */ 146 struct HBFixed : HBINT32 147 { operator =OT::HBFixed148 HBFixed& operator = (uint32_t i) { HBINT32::operator= (i); return *this; } 149 // 65536 means 1<<16 to_floatOT::HBFixed150 float to_float () const { return ((int32_t) v) / 65536.f; } set_floatOT::HBFixed151 void set_float (float f) { v = roundf (f * 65536.f); } 152 public: 153 DEFINE_SIZE_STATIC (4); 154 }; 155 156 /* Date represented in number of seconds since 12:00 midnight, January 1, 157 * 1904. The value is represented as a signed 64-bit integer. */ 158 struct LONGDATETIME 159 { sanitizeOT::LONGDATETIME160 bool sanitize (hb_sanitize_context_t *c) const 161 { 162 TRACE_SANITIZE (this); 163 return_trace (likely (c->check_struct (this))); 164 } 165 protected: 166 HBINT32 major; 167 HBUINT32 minor; 168 public: 169 DEFINE_SIZE_STATIC (8); 170 }; 171 172 /* Array of four uint8s (length = 32 bits) used to identify a script, language 173 * system, feature, or baseline */ 174 struct Tag : HBUINT32 175 { operator =OT::Tag176 Tag& operator = (hb_tag_t i) { HBUINT32::operator= (i); return *this; } 177 /* What the char* converters return is NOT nul-terminated. Print using "%.4s" */ operator const char*OT::Tag178 operator const char* () const { return reinterpret_cast<const char *> (this); } operator char*OT::Tag179 operator char* () { return reinterpret_cast<char *> (this); } 180 public: 181 DEFINE_SIZE_STATIC (4); 182 }; 183 184 /* Glyph index number, same as uint16 (length = 16 bits) */ 185 struct HBGlyphID : HBUINT16 186 { operator =OT::HBGlyphID187 HBGlyphID& operator = (uint16_t i) { HBUINT16::operator= (i); return *this; } 188 }; 189 190 /* Script/language-system/feature index */ 191 struct Index : HBUINT16 { 192 static constexpr unsigned NOT_FOUND_INDEX = 0xFFFFu; operator =OT::Index193 Index& operator = (uint16_t i) { HBUINT16::operator= (i); return *this; } 194 }; 195 DECLARE_NULL_NAMESPACE_BYTES (OT, Index); 196 197 typedef Index NameID; 198 199 /* Offset, Null offset = 0 */ 200 template <typename Type, bool has_null=true> 201 struct Offset : Type 202 { operator =OT::Offset203 Offset& operator = (typename Type::type i) { Type::operator= (i); return *this; } 204 205 typedef Type type; 206 is_nullOT::Offset207 bool is_null () const { return has_null && 0 == *this; } 208 serializeOT::Offset209 void *serialize (hb_serialize_context_t *c, const void *base) 210 { 211 void *t = c->start_embed<void> (); 212 c->check_assign (*this, (unsigned) ((char *) t - (char *) base)); 213 return t; 214 } 215 216 public: 217 DEFINE_SIZE_STATIC (sizeof (Type)); 218 }; 219 220 typedef Offset<HBUINT16> Offset16; 221 typedef Offset<HBUINT32> Offset32; 222 223 224 /* CheckSum */ 225 struct CheckSum : HBUINT32 226 { operator =OT::CheckSum227 CheckSum& operator = (uint32_t i) { HBUINT32::operator= (i); return *this; } 228 229 /* This is reference implementation from the spec. */ CalcTableChecksumOT::CheckSum230 static uint32_t CalcTableChecksum (const HBUINT32 *Table, uint32_t Length) 231 { 232 uint32_t Sum = 0L; 233 assert (0 == (Length & 3)); 234 const HBUINT32 *EndPtr = Table + Length / HBUINT32::static_size; 235 236 while (Table < EndPtr) 237 Sum += *Table++; 238 return Sum; 239 } 240 241 /* Note: data should be 4byte aligned and have 4byte padding at the end. */ set_for_dataOT::CheckSum242 void set_for_data (const void *data, unsigned int length) 243 { *this = CalcTableChecksum ((const HBUINT32 *) data, length); } 244 245 public: 246 DEFINE_SIZE_STATIC (4); 247 }; 248 249 250 /* 251 * Version Numbers 252 */ 253 254 template <typename FixedType=HBUINT16> 255 struct FixedVersion 256 { to_intOT::FixedVersion257 uint32_t to_int () const { return (major << (sizeof (FixedType) * 8)) + minor; } 258 sanitizeOT::FixedVersion259 bool sanitize (hb_sanitize_context_t *c) const 260 { 261 TRACE_SANITIZE (this); 262 return_trace (c->check_struct (this)); 263 } 264 265 FixedType major; 266 FixedType minor; 267 public: 268 DEFINE_SIZE_STATIC (2 * sizeof (FixedType)); 269 }; 270 271 272 /* 273 * Template subclasses of Offset that do the dereferencing. 274 * Use: (base+offset) 275 */ 276 277 template <typename Type, bool has_null> 278 struct _hb_has_null 279 { get_nullOT::_hb_has_null280 static const Type *get_null () { return nullptr; } get_crapOT::_hb_has_null281 static Type *get_crap () { return nullptr; } 282 }; 283 template <typename Type> 284 struct _hb_has_null<Type, true> 285 { get_nullOT::_hb_has_null286 static const Type *get_null () { return &Null (Type); } get_crapOT::_hb_has_null287 static Type *get_crap () { return &Crap (Type); } 288 }; 289 290 template <typename Type, typename OffsetType=HBUINT16, bool has_null=true> 291 struct OffsetTo : Offset<OffsetType, has_null> 292 { 293 HB_DELETE_COPY_ASSIGN (OffsetTo); 294 OffsetTo () = default; 295 operator =OT::OffsetTo296 OffsetTo& operator = (typename OffsetType::type i) { OffsetType::operator= (i); return *this; } 297 operator ()OT::OffsetTo298 const Type& operator () (const void *base) const 299 { 300 if (unlikely (this->is_null ())) return *_hb_has_null<Type, has_null>::get_null (); 301 return StructAtOffset<const Type> (base, *this); 302 } operator ()OT::OffsetTo303 Type& operator () (void *base) const 304 { 305 if (unlikely (this->is_null ())) return *_hb_has_null<Type, has_null>::get_crap (); 306 return StructAtOffset<Type> (base, *this); 307 } 308 309 template <typename Base, 310 hb_enable_if (hb_is_convertible (const Base, const void *))> operator +(const Base & base,const OffsetTo & offset)311 friend const Type& operator + (const Base &base, const OffsetTo &offset) { return offset ((const void *) base); } 312 template <typename Base, 313 hb_enable_if (hb_is_convertible (const Base, const void *))> operator +(const OffsetTo & offset,const Base & base)314 friend const Type& operator + (const OffsetTo &offset, const Base &base) { return offset ((const void *) base); } 315 template <typename Base, 316 hb_enable_if (hb_is_convertible (Base, void *))> operator +(Base && base,OffsetTo & offset)317 friend Type& operator + (Base &&base, OffsetTo &offset) { return offset ((void *) base); } 318 template <typename Base, 319 hb_enable_if (hb_is_convertible (Base, void *))> operator +(OffsetTo & offset,Base && base)320 friend Type& operator + (OffsetTo &offset, Base &&base) { return offset ((void *) base); } 321 serializeOT::OffsetTo322 Type& serialize (hb_serialize_context_t *c, const void *base) 323 { 324 return * (Type *) Offset<OffsetType>::serialize (c, base); 325 } 326 327 template <typename ...Ts> serialize_subsetOT::OffsetTo328 bool serialize_subset (hb_subset_context_t *c, const OffsetTo& src, 329 const void *src_base, Ts&&... ds) 330 { 331 *this = 0; 332 if (src.is_null ()) 333 return false; 334 335 auto *s = c->serializer; 336 337 s->push (); 338 339 bool ret = c->dispatch (src_base+src, hb_forward<Ts> (ds)...); 340 341 if (ret || !has_null) 342 s->add_link (*this, s->pop_pack ()); 343 else 344 s->pop_discard (); 345 346 return ret; 347 } 348 349 /* TODO: Somehow merge this with previous function into a serialize_dispatch(). */ 350 /* Workaround clang bug: https://bugs.llvm.org/show_bug.cgi?id=23029 351 * Can't compile: whence = hb_serialize_context_t::Head followed by Ts&&... 352 */ 353 template <typename ...Ts> serialize_copyOT::OffsetTo354 bool serialize_copy (hb_serialize_context_t *c, const OffsetTo& src, 355 const void *src_base, unsigned dst_bias, 356 hb_serialize_context_t::whence_t whence, 357 Ts&&... ds) 358 { 359 *this = 0; 360 if (src.is_null ()) 361 return false; 362 363 c->push (); 364 365 bool ret = c->copy (src_base+src, hb_forward<Ts> (ds)...); 366 367 c->add_link (*this, c->pop_pack (), whence, dst_bias); 368 369 return ret; 370 } 371 serialize_copyOT::OffsetTo372 bool serialize_copy (hb_serialize_context_t *c, const OffsetTo& src, 373 const void *src_base, unsigned dst_bias = 0) 374 { return serialize_copy (c, src, src_base, dst_bias, hb_serialize_context_t::Head); } 375 sanitize_shallowOT::OffsetTo376 bool sanitize_shallow (hb_sanitize_context_t *c, const void *base) const 377 { 378 TRACE_SANITIZE (this); 379 if (unlikely (!c->check_struct (this))) return_trace (false); 380 if (unlikely (this->is_null ())) return_trace (true); 381 if (unlikely (!c->check_range (base, *this))) return_trace (false); 382 return_trace (true); 383 } 384 385 template <typename ...Ts> sanitizeOT::OffsetTo386 bool sanitize (hb_sanitize_context_t *c, const void *base, Ts&&... ds) const 387 { 388 TRACE_SANITIZE (this); 389 return_trace (sanitize_shallow (c, base) && 390 (this->is_null () || 391 c->dispatch (StructAtOffset<Type> (base, *this), hb_forward<Ts> (ds)...) || 392 neuter (c))); 393 } 394 395 /* Set the offset to Null */ neuterOT::OffsetTo396 bool neuter (hb_sanitize_context_t *c) const 397 { 398 if (!has_null) return false; 399 return c->try_set (this, 0); 400 } 401 DEFINE_SIZE_STATIC (sizeof (OffsetType)); 402 }; 403 /* Partial specializations. */ 404 template <typename Type, bool has_null=true> 405 using LOffsetTo = OffsetTo<Type, HBUINT32, has_null>; 406 template <typename Type, typename OffsetType=HBUINT16> 407 using NNOffsetTo = OffsetTo<Type, OffsetType, false>; 408 template <typename Type> 409 using LNNOffsetTo = LOffsetTo<Type, false>; 410 411 412 /* 413 * Array Types 414 */ 415 416 template <typename Type> 417 struct UnsizedArrayOf 418 { 419 typedef Type item_t; 420 static constexpr unsigned item_size = hb_static_size (Type); 421 422 HB_DELETE_CREATE_COPY_ASSIGN (UnsizedArrayOf); 423 operator []OT::UnsizedArrayOf424 const Type& operator [] (int i_) const 425 { 426 unsigned int i = (unsigned int) i_; 427 const Type *p = &arrayZ[i]; 428 if (unlikely (p < arrayZ)) return Null (Type); /* Overflowed. */ 429 return *p; 430 } operator []OT::UnsizedArrayOf431 Type& operator [] (int i_) 432 { 433 unsigned int i = (unsigned int) i_; 434 Type *p = &arrayZ[i]; 435 if (unlikely (p < arrayZ)) return Crap (Type); /* Overflowed. */ 436 return *p; 437 } 438 get_sizeOT::UnsizedArrayOf439 unsigned int get_size (unsigned int len) const 440 { return len * Type::static_size; } 441 operator T*OT::UnsizedArrayOf442 template <typename T> operator T * () { return arrayZ; } operator const T*OT::UnsizedArrayOf443 template <typename T> operator const T * () const { return arrayZ; } as_arrayOT::UnsizedArrayOf444 hb_array_t<Type> as_array (unsigned int len) 445 { return hb_array (arrayZ, len); } as_arrayOT::UnsizedArrayOf446 hb_array_t<const Type> as_array (unsigned int len) const 447 { return hb_array (arrayZ, len); } 448 449 template <typename T> lsearchOT::UnsizedArrayOf450 Type &lsearch (unsigned int len, const T &x, Type ¬_found = Crap (Type)) 451 { return *as_array (len).lsearch (x, ¬_found); } 452 template <typename T> lsearchOT::UnsizedArrayOf453 const Type &lsearch (unsigned int len, const T &x, const Type ¬_found = Null (Type)) const 454 { return *as_array (len).lsearch (x, ¬_found); } 455 template <typename T> lfindOT::UnsizedArrayOf456 bool lfind (unsigned int len, const T &x, unsigned *pos = nullptr) const 457 { return as_array (len).lfind (x, pos); } 458 qsortOT::UnsizedArrayOf459 void qsort (unsigned int len, unsigned int start = 0, unsigned int end = (unsigned int) -1) 460 { as_array (len).qsort (start, end); } 461 serializeOT::UnsizedArrayOf462 bool serialize (hb_serialize_context_t *c, unsigned int items_len) 463 { 464 TRACE_SERIALIZE (this); 465 if (unlikely (!c->extend (*this, items_len))) return_trace (false); 466 return_trace (true); 467 } 468 template <typename Iterator, 469 hb_requires (hb_is_source_of (Iterator, Type))> serializeOT::UnsizedArrayOf470 bool serialize (hb_serialize_context_t *c, Iterator items) 471 { 472 TRACE_SERIALIZE (this); 473 unsigned count = items.len (); 474 if (unlikely (!serialize (c, count))) return_trace (false); 475 /* TODO Umm. Just exhaust the iterator instead? Being extra 476 * cautious right now.. */ 477 for (unsigned i = 0; i < count; i++, ++items) 478 arrayZ[i] = *items; 479 return_trace (true); 480 } 481 copyOT::UnsizedArrayOf482 UnsizedArrayOf* copy (hb_serialize_context_t *c, unsigned count) const 483 { 484 TRACE_SERIALIZE (this); 485 auto *out = c->start_embed (this); 486 if (unlikely (!as_array (count).copy (c))) return_trace (nullptr); 487 return_trace (out); 488 } 489 490 template <typename ...Ts> sanitizeOT::UnsizedArrayOf491 bool sanitize (hb_sanitize_context_t *c, unsigned int count, Ts&&... ds) const 492 { 493 TRACE_SANITIZE (this); 494 if (unlikely (!sanitize_shallow (c, count))) return_trace (false); 495 if (!sizeof... (Ts) && hb_is_trivially_copyable (Type)) return_trace (true); 496 for (unsigned int i = 0; i < count; i++) 497 if (unlikely (!c->dispatch (arrayZ[i], hb_forward<Ts> (ds)...))) 498 return_trace (false); 499 return_trace (true); 500 } 501 sanitize_shallowOT::UnsizedArrayOf502 bool sanitize_shallow (hb_sanitize_context_t *c, unsigned int count) const 503 { 504 TRACE_SANITIZE (this); 505 return_trace (c->check_array (arrayZ, count)); 506 } 507 508 public: 509 Type arrayZ[HB_VAR_ARRAY]; 510 public: 511 DEFINE_SIZE_UNBOUNDED (0); 512 }; 513 514 /* Unsized array of offset's */ 515 template <typename Type, typename OffsetType, bool has_null=true> 516 using UnsizedOffsetArrayOf = UnsizedArrayOf<OffsetTo<Type, OffsetType, has_null>>; 517 518 /* Unsized array of offsets relative to the beginning of the array itself. */ 519 template <typename Type, typename OffsetType, bool has_null=true> 520 struct UnsizedOffsetListOf : UnsizedOffsetArrayOf<Type, OffsetType, has_null> 521 { operator []OT::UnsizedOffsetListOf522 const Type& operator [] (int i_) const 523 { 524 unsigned int i = (unsigned int) i_; 525 const OffsetTo<Type, OffsetType, has_null> *p = &this->arrayZ[i]; 526 if (unlikely (p < this->arrayZ)) return Null (Type); /* Overflowed. */ 527 return this+*p; 528 } operator []OT::UnsizedOffsetListOf529 Type& operator [] (int i_) 530 { 531 unsigned int i = (unsigned int) i_; 532 const OffsetTo<Type, OffsetType, has_null> *p = &this->arrayZ[i]; 533 if (unlikely (p < this->arrayZ)) return Crap (Type); /* Overflowed. */ 534 return this+*p; 535 } 536 537 template <typename ...Ts> sanitizeOT::UnsizedOffsetListOf538 bool sanitize (hb_sanitize_context_t *c, unsigned int count, Ts&&... ds) const 539 { 540 TRACE_SANITIZE (this); 541 return_trace ((UnsizedOffsetArrayOf<Type, OffsetType, has_null> 542 ::sanitize (c, count, this, hb_forward<Ts> (ds)...))); 543 } 544 }; 545 546 /* An array with sorted elements. Supports binary searching. */ 547 template <typename Type> 548 struct SortedUnsizedArrayOf : UnsizedArrayOf<Type> 549 { as_arrayOT::SortedUnsizedArrayOf550 hb_sorted_array_t<Type> as_array (unsigned int len) 551 { return hb_sorted_array (this->arrayZ, len); } as_arrayOT::SortedUnsizedArrayOf552 hb_sorted_array_t<const Type> as_array (unsigned int len) const 553 { return hb_sorted_array (this->arrayZ, len); } operator hb_sorted_array_t<Type>OT::SortedUnsizedArrayOf554 operator hb_sorted_array_t<Type> () { return as_array (); } operator hb_sorted_array_t<const Type>OT::SortedUnsizedArrayOf555 operator hb_sorted_array_t<const Type> () const { return as_array (); } 556 557 template <typename T> bsearchOT::SortedUnsizedArrayOf558 Type &bsearch (unsigned int len, const T &x, Type ¬_found = Crap (Type)) 559 { return *as_array (len).bsearch (x, ¬_found); } 560 template <typename T> bsearchOT::SortedUnsizedArrayOf561 const Type &bsearch (unsigned int len, const T &x, const Type ¬_found = Null (Type)) const 562 { return *as_array (len).bsearch (x, ¬_found); } 563 template <typename T> bfindOT::SortedUnsizedArrayOf564 bool bfind (unsigned int len, const T &x, unsigned int *i = nullptr, 565 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, 566 unsigned int to_store = (unsigned int) -1) const 567 { return as_array (len).bfind (x, i, not_found, to_store); } 568 }; 569 570 571 /* An array with a number of elements. */ 572 template <typename Type, typename LenType=HBUINT16> 573 struct ArrayOf 574 { 575 typedef Type item_t; 576 static constexpr unsigned item_size = hb_static_size (Type); 577 578 HB_DELETE_CREATE_COPY_ASSIGN (ArrayOf); 579 operator []OT::ArrayOf580 const Type& operator [] (int i_) const 581 { 582 unsigned int i = (unsigned int) i_; 583 if (unlikely (i >= len)) return Null (Type); 584 return arrayZ[i]; 585 } operator []OT::ArrayOf586 Type& operator [] (int i_) 587 { 588 unsigned int i = (unsigned int) i_; 589 if (unlikely (i >= len)) return Crap (Type); 590 return arrayZ[i]; 591 } 592 get_sizeOT::ArrayOf593 unsigned int get_size () const 594 { return len.static_size + len * Type::static_size; } 595 operator boolOT::ArrayOf596 explicit operator bool () const { return len; } 597 popOT::ArrayOf598 void pop () { len--; } 599 as_arrayOT::ArrayOf600 hb_array_t< Type> as_array () { return hb_array (arrayZ, len); } as_arrayOT::ArrayOf601 hb_array_t<const Type> as_array () const { return hb_array (arrayZ, len); } 602 603 /* Iterator. */ 604 typedef hb_array_t<const Type> iter_t; 605 typedef hb_array_t< Type> writer_t; iterOT::ArrayOf606 iter_t iter () const { return as_array (); } writerOT::ArrayOf607 writer_t writer () { return as_array (); } operator iter_tOT::ArrayOf608 operator iter_t () const { return iter (); } operator writer_tOT::ArrayOf609 operator writer_t () { return writer (); } 610 sub_arrayOT::ArrayOf611 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 612 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::ArrayOf613 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 614 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::ArrayOf615 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 616 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::ArrayOf617 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 618 { return as_array ().sub_array (start_offset, count); } 619 serializeOT::ArrayOf620 hb_success_t serialize (hb_serialize_context_t *c, unsigned items_len) 621 { 622 TRACE_SERIALIZE (this); 623 if (unlikely (!c->extend_min (*this))) return_trace (false); 624 c->check_assign (len, items_len); 625 if (unlikely (!c->extend (*this))) return_trace (false); 626 return_trace (true); 627 } 628 template <typename Iterator, 629 hb_requires (hb_is_source_of (Iterator, Type))> serializeOT::ArrayOf630 hb_success_t serialize (hb_serialize_context_t *c, Iterator items) 631 { 632 TRACE_SERIALIZE (this); 633 unsigned count = items.len (); 634 if (unlikely (!serialize (c, count))) return_trace (false); 635 /* TODO Umm. Just exhaust the iterator instead? Being extra 636 * cautious right now.. */ 637 for (unsigned i = 0; i < count; i++, ++items) 638 arrayZ[i] = *items; 639 return_trace (true); 640 } 641 serialize_appendOT::ArrayOf642 Type* serialize_append (hb_serialize_context_t *c) 643 { 644 TRACE_SERIALIZE (this); 645 len++; 646 if (unlikely (!len || !c->extend (*this))) 647 { 648 len--; 649 return_trace (nullptr); 650 } 651 return_trace (&arrayZ[len - 1]); 652 } 653 copyOT::ArrayOf654 ArrayOf* copy (hb_serialize_context_t *c) const 655 { 656 TRACE_SERIALIZE (this); 657 auto *out = c->start_embed (this); 658 if (unlikely (!c->extend_min (out))) return_trace (nullptr); 659 c->check_assign (out->len, len); 660 if (unlikely (!as_array ().copy (c))) return_trace (nullptr); 661 return_trace (out); 662 } 663 664 template <typename ...Ts> sanitizeOT::ArrayOf665 bool sanitize (hb_sanitize_context_t *c, Ts&&... ds) const 666 { 667 TRACE_SANITIZE (this); 668 if (unlikely (!sanitize_shallow (c))) return_trace (false); 669 if (!sizeof... (Ts) && hb_is_trivially_copyable (Type)) return_trace (true); 670 unsigned int count = len; 671 for (unsigned int i = 0; i < count; i++) 672 if (unlikely (!c->dispatch (arrayZ[i], hb_forward<Ts> (ds)...))) 673 return_trace (false); 674 return_trace (true); 675 } 676 677 template <typename T> lsearchOT::ArrayOf678 Type &lsearch (const T &x, Type ¬_found = Crap (Type)) 679 { return *as_array ().lsearch (x, ¬_found); } 680 template <typename T> lsearchOT::ArrayOf681 const Type &lsearch (const T &x, const Type ¬_found = Null (Type)) const 682 { return *as_array ().lsearch (x, ¬_found); } 683 template <typename T> lfindOT::ArrayOf684 bool lfind (const T &x, unsigned *pos = nullptr) const 685 { return as_array ().lfind (x, pos); } 686 qsortOT::ArrayOf687 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1) 688 { as_array ().qsort (start, end); } 689 sanitize_shallowOT::ArrayOf690 bool sanitize_shallow (hb_sanitize_context_t *c) const 691 { 692 TRACE_SANITIZE (this); 693 return_trace (len.sanitize (c) && c->check_array (arrayZ, len)); 694 } 695 696 public: 697 LenType len; 698 Type arrayZ[HB_VAR_ARRAY]; 699 public: 700 DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ); 701 }; 702 template <typename Type> 703 using LArrayOf = ArrayOf<Type, HBUINT32>; 704 using PString = ArrayOf<HBUINT8, HBUINT8>; 705 706 /* Array of Offset's */ 707 template <typename Type> 708 using OffsetArrayOf = ArrayOf<OffsetTo<Type, HBUINT16>>; 709 template <typename Type> 710 using LOffsetArrayOf = ArrayOf<OffsetTo<Type, HBUINT32>>; 711 template <typename Type> 712 using LOffsetLArrayOf = ArrayOf<OffsetTo<Type, HBUINT32>, HBUINT32>; 713 714 /* Array of offsets relative to the beginning of the array itself. */ 715 template <typename Type> 716 struct OffsetListOf : OffsetArrayOf<Type> 717 { operator []OT::OffsetListOf718 const Type& operator [] (int i_) const 719 { 720 unsigned int i = (unsigned int) i_; 721 if (unlikely (i >= this->len)) return Null (Type); 722 return this+this->arrayZ[i]; 723 } operator []OT::OffsetListOf724 const Type& operator [] (int i_) 725 { 726 unsigned int i = (unsigned int) i_; 727 if (unlikely (i >= this->len)) return Crap (Type); 728 return this+this->arrayZ[i]; 729 } 730 subsetOT::OffsetListOf731 bool subset (hb_subset_context_t *c) const 732 { 733 TRACE_SUBSET (this); 734 struct OffsetListOf<Type> *out = c->serializer->embed (*this); 735 if (unlikely (!out)) return_trace (false); 736 unsigned int count = this->len; 737 for (unsigned int i = 0; i < count; i++) 738 out->arrayZ[i].serialize_subset (c, this->arrayZ[i], this, out); 739 return_trace (true); 740 } 741 742 template <typename ...Ts> sanitizeOT::OffsetListOf743 bool sanitize (hb_sanitize_context_t *c, Ts&&... ds) const 744 { 745 TRACE_SANITIZE (this); 746 return_trace (OffsetArrayOf<Type>::sanitize (c, this, hb_forward<Ts> (ds)...)); 747 } 748 }; 749 750 /* An array starting at second element. */ 751 template <typename Type, typename LenType=HBUINT16> 752 struct HeadlessArrayOf 753 { 754 static constexpr unsigned item_size = Type::static_size; 755 756 HB_DELETE_CREATE_COPY_ASSIGN (HeadlessArrayOf); 757 operator []OT::HeadlessArrayOf758 const Type& operator [] (int i_) const 759 { 760 unsigned int i = (unsigned int) i_; 761 if (unlikely (i >= lenP1 || !i)) return Null (Type); 762 return arrayZ[i-1]; 763 } operator []OT::HeadlessArrayOf764 Type& operator [] (int i_) 765 { 766 unsigned int i = (unsigned int) i_; 767 if (unlikely (i >= lenP1 || !i)) return Crap (Type); 768 return arrayZ[i-1]; 769 } get_sizeOT::HeadlessArrayOf770 unsigned int get_size () const 771 { return lenP1.static_size + get_length () * Type::static_size; } 772 get_lengthOT::HeadlessArrayOf773 unsigned get_length () const { return lenP1 ? lenP1 - 1 : 0; } 774 as_arrayOT::HeadlessArrayOf775 hb_array_t< Type> as_array () { return hb_array (arrayZ, get_length ()); } as_arrayOT::HeadlessArrayOf776 hb_array_t<const Type> as_array () const { return hb_array (arrayZ, get_length ()); } 777 778 /* Iterator. */ 779 typedef hb_array_t<const Type> iter_t; 780 typedef hb_array_t< Type> writer_t; iterOT::HeadlessArrayOf781 iter_t iter () const { return as_array (); } writerOT::HeadlessArrayOf782 writer_t writer () { return as_array (); } operator iter_tOT::HeadlessArrayOf783 operator iter_t () const { return iter (); } operator writer_tOT::HeadlessArrayOf784 operator writer_t () { return writer (); } 785 serializeOT::HeadlessArrayOf786 bool serialize (hb_serialize_context_t *c, unsigned int items_len) 787 { 788 TRACE_SERIALIZE (this); 789 if (unlikely (!c->extend_min (*this))) return_trace (false); 790 c->check_assign (lenP1, items_len + 1); 791 if (unlikely (!c->extend (*this))) return_trace (false); 792 return_trace (true); 793 } 794 template <typename Iterator, 795 hb_requires (hb_is_source_of (Iterator, Type))> serializeOT::HeadlessArrayOf796 bool serialize (hb_serialize_context_t *c, Iterator items) 797 { 798 TRACE_SERIALIZE (this); 799 unsigned count = items.len (); 800 if (unlikely (!serialize (c, count))) return_trace (false); 801 /* TODO Umm. Just exhaust the iterator instead? Being extra 802 * cautious right now.. */ 803 for (unsigned i = 0; i < count; i++, ++items) 804 arrayZ[i] = *items; 805 return_trace (true); 806 } 807 808 template <typename ...Ts> sanitizeOT::HeadlessArrayOf809 bool sanitize (hb_sanitize_context_t *c, Ts&&... ds) const 810 { 811 TRACE_SANITIZE (this); 812 if (unlikely (!sanitize_shallow (c))) return_trace (false); 813 if (!sizeof... (Ts) && hb_is_trivially_copyable (Type)) return_trace (true); 814 unsigned int count = get_length (); 815 for (unsigned int i = 0; i < count; i++) 816 if (unlikely (!c->dispatch (arrayZ[i], hb_forward<Ts> (ds)...))) 817 return_trace (false); 818 return_trace (true); 819 } 820 821 private: sanitize_shallowOT::HeadlessArrayOf822 bool sanitize_shallow (hb_sanitize_context_t *c) const 823 { 824 TRACE_SANITIZE (this); 825 return_trace (lenP1.sanitize (c) && 826 (!lenP1 || c->check_array (arrayZ, lenP1 - 1))); 827 } 828 829 public: 830 LenType lenP1; 831 Type arrayZ[HB_VAR_ARRAY]; 832 public: 833 DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ); 834 }; 835 836 /* An array storing length-1. */ 837 template <typename Type, typename LenType=HBUINT16> 838 struct ArrayOfM1 839 { 840 HB_DELETE_CREATE_COPY_ASSIGN (ArrayOfM1); 841 operator []OT::ArrayOfM1842 const Type& operator [] (int i_) const 843 { 844 unsigned int i = (unsigned int) i_; 845 if (unlikely (i > lenM1)) return Null (Type); 846 return arrayZ[i]; 847 } operator []OT::ArrayOfM1848 Type& operator [] (int i_) 849 { 850 unsigned int i = (unsigned int) i_; 851 if (unlikely (i > lenM1)) return Crap (Type); 852 return arrayZ[i]; 853 } get_sizeOT::ArrayOfM1854 unsigned int get_size () const 855 { return lenM1.static_size + (lenM1 + 1) * Type::static_size; } 856 857 template <typename ...Ts> sanitizeOT::ArrayOfM1858 bool sanitize (hb_sanitize_context_t *c, Ts&&... ds) const 859 { 860 TRACE_SANITIZE (this); 861 if (unlikely (!sanitize_shallow (c))) return_trace (false); 862 unsigned int count = lenM1 + 1; 863 for (unsigned int i = 0; i < count; i++) 864 if (unlikely (!c->dispatch (arrayZ[i], hb_forward<Ts> (ds)...))) 865 return_trace (false); 866 return_trace (true); 867 } 868 869 private: sanitize_shallowOT::ArrayOfM1870 bool sanitize_shallow (hb_sanitize_context_t *c) const 871 { 872 TRACE_SANITIZE (this); 873 return_trace (lenM1.sanitize (c) && 874 (c->check_array (arrayZ, lenM1 + 1))); 875 } 876 877 public: 878 LenType lenM1; 879 Type arrayZ[HB_VAR_ARRAY]; 880 public: 881 DEFINE_SIZE_ARRAY (sizeof (LenType), arrayZ); 882 }; 883 884 /* An array with sorted elements. Supports binary searching. */ 885 template <typename Type, typename LenType=HBUINT16> 886 struct SortedArrayOf : ArrayOf<Type, LenType> 887 { as_arrayOT::SortedArrayOf888 hb_sorted_array_t< Type> as_array () { return hb_sorted_array (this->arrayZ, this->len); } as_arrayOT::SortedArrayOf889 hb_sorted_array_t<const Type> as_array () const { return hb_sorted_array (this->arrayZ, this->len); } 890 891 /* Iterator. */ 892 typedef hb_sorted_array_t<const Type> iter_t; 893 typedef hb_sorted_array_t< Type> writer_t; iterOT::SortedArrayOf894 iter_t iter () const { return as_array (); } writerOT::SortedArrayOf895 writer_t writer () { return as_array (); } operator iter_tOT::SortedArrayOf896 operator iter_t () const { return iter (); } operator writer_tOT::SortedArrayOf897 operator writer_t () { return writer (); } 898 sub_arrayOT::SortedArrayOf899 hb_sorted_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const 900 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::SortedArrayOf901 hb_sorted_array_t<const Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) const 902 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::SortedArrayOf903 hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int count) 904 { return as_array ().sub_array (start_offset, count); } sub_arrayOT::SortedArrayOf905 hb_sorted_array_t<Type> sub_array (unsigned int start_offset, unsigned int *count = nullptr /* IN/OUT */) 906 { return as_array ().sub_array (start_offset, count); } 907 serializeOT::SortedArrayOf908 bool serialize (hb_serialize_context_t *c, unsigned int items_len) 909 { 910 TRACE_SERIALIZE (this); 911 bool ret = ArrayOf<Type, LenType>::serialize (c, items_len); 912 return_trace (ret); 913 } 914 template <typename Iterator, 915 hb_requires (hb_is_sorted_source_of (Iterator, Type))> serializeOT::SortedArrayOf916 bool serialize (hb_serialize_context_t *c, Iterator items) 917 { 918 TRACE_SERIALIZE (this); 919 bool ret = ArrayOf<Type, LenType>::serialize (c, items); 920 return_trace (ret); 921 } 922 923 template <typename T> bsearchOT::SortedArrayOf924 Type &bsearch (const T &x, Type ¬_found = Crap (Type)) 925 { return *as_array ().bsearch (x, ¬_found); } 926 template <typename T> bsearchOT::SortedArrayOf927 const Type &bsearch (const T &x, const Type ¬_found = Null (Type)) const 928 { return *as_array ().bsearch (x, ¬_found); } 929 template <typename T> bfindOT::SortedArrayOf930 bool bfind (const T &x, unsigned int *i = nullptr, 931 hb_bfind_not_found_t not_found = HB_BFIND_NOT_FOUND_DONT_STORE, 932 unsigned int to_store = (unsigned int) -1) const 933 { return as_array ().bfind (x, i, not_found, to_store); } 934 }; 935 936 /* 937 * Binary-search arrays 938 */ 939 940 template <typename LenType=HBUINT16> 941 struct BinSearchHeader 942 { operator uint32_tOT::BinSearchHeader943 operator uint32_t () const { return len; } 944 sanitizeOT::BinSearchHeader945 bool sanitize (hb_sanitize_context_t *c) const 946 { 947 TRACE_SANITIZE (this); 948 return_trace (c->check_struct (this)); 949 } 950 operator =OT::BinSearchHeader951 BinSearchHeader& operator = (unsigned int v) 952 { 953 len = v; 954 assert (len == v); 955 entrySelector = hb_max (1u, hb_bit_storage (v)) - 1; 956 searchRange = 16 * (1u << entrySelector); 957 rangeShift = v * 16 > searchRange 958 ? 16 * v - searchRange 959 : 0; 960 return *this; 961 } 962 963 protected: 964 LenType len; 965 LenType searchRange; 966 LenType entrySelector; 967 LenType rangeShift; 968 969 public: 970 DEFINE_SIZE_STATIC (8); 971 }; 972 973 template <typename Type, typename LenType=HBUINT16> 974 using BinSearchArrayOf = SortedArrayOf<Type, BinSearchHeader<LenType>>; 975 976 977 struct VarSizedBinSearchHeader 978 { 979 sanitizeOT::VarSizedBinSearchHeader980 bool sanitize (hb_sanitize_context_t *c) const 981 { 982 TRACE_SANITIZE (this); 983 return_trace (c->check_struct (this)); 984 } 985 986 HBUINT16 unitSize; /* Size of a lookup unit for this search in bytes. */ 987 HBUINT16 nUnits; /* Number of units of the preceding size to be searched. */ 988 HBUINT16 searchRange; /* The value of unitSize times the largest power of 2 989 * that is less than or equal to the value of nUnits. */ 990 HBUINT16 entrySelector; /* The log base 2 of the largest power of 2 less than 991 * or equal to the value of nUnits. */ 992 HBUINT16 rangeShift; /* The value of unitSize times the difference of the 993 * value of nUnits minus the largest power of 2 less 994 * than or equal to the value of nUnits. */ 995 public: 996 DEFINE_SIZE_STATIC (10); 997 }; 998 999 template <typename Type> 1000 struct VarSizedBinSearchArrayOf 1001 { 1002 static constexpr unsigned item_size = Type::static_size; 1003 1004 HB_DELETE_CREATE_COPY_ASSIGN (VarSizedBinSearchArrayOf); 1005 last_is_terminatorOT::VarSizedBinSearchArrayOf1006 bool last_is_terminator () const 1007 { 1008 if (unlikely (!header.nUnits)) return false; 1009 1010 /* Gah. 1011 * 1012 * "The number of termination values that need to be included is table-specific. 1013 * The value that indicates binary search termination is 0xFFFF." */ 1014 const HBUINT16 *words = &StructAtOffset<HBUINT16> (&bytesZ, (header.nUnits - 1) * header.unitSize); 1015 unsigned int count = Type::TerminationWordCount; 1016 for (unsigned int i = 0; i < count; i++) 1017 if (words[i] != 0xFFFFu) 1018 return false; 1019 return true; 1020 } 1021 operator []OT::VarSizedBinSearchArrayOf1022 const Type& operator [] (int i_) const 1023 { 1024 unsigned int i = (unsigned int) i_; 1025 if (unlikely (i >= get_length ())) return Null (Type); 1026 return StructAtOffset<Type> (&bytesZ, i * header.unitSize); 1027 } operator []OT::VarSizedBinSearchArrayOf1028 Type& operator [] (int i_) 1029 { 1030 unsigned int i = (unsigned int) i_; 1031 if (unlikely (i >= get_length ())) return Crap (Type); 1032 return StructAtOffset<Type> (&bytesZ, i * header.unitSize); 1033 } get_lengthOT::VarSizedBinSearchArrayOf1034 unsigned int get_length () const 1035 { return header.nUnits - last_is_terminator (); } get_sizeOT::VarSizedBinSearchArrayOf1036 unsigned int get_size () const 1037 { return header.static_size + header.nUnits * header.unitSize; } 1038 1039 template <typename ...Ts> sanitizeOT::VarSizedBinSearchArrayOf1040 bool sanitize (hb_sanitize_context_t *c, Ts&&... ds) const 1041 { 1042 TRACE_SANITIZE (this); 1043 if (unlikely (!sanitize_shallow (c))) return_trace (false); 1044 if (!sizeof... (Ts) && hb_is_trivially_copyable (Type)) return_trace (true); 1045 unsigned int count = get_length (); 1046 for (unsigned int i = 0; i < count; i++) 1047 if (unlikely (!(*this)[i].sanitize (c, hb_forward<Ts> (ds)...))) 1048 return_trace (false); 1049 return_trace (true); 1050 } 1051 1052 template <typename T> bsearchOT::VarSizedBinSearchArrayOf1053 const Type *bsearch (const T &key) const 1054 { 1055 unsigned pos; 1056 return hb_bsearch_impl (&pos, 1057 key, 1058 (const void *) bytesZ, 1059 get_length (), 1060 header.unitSize, 1061 _hb_cmp_method<T, Type>) 1062 ? (const Type *) (((const char *) &bytesZ) + (pos * header.unitSize)) 1063 : nullptr; 1064 } 1065 1066 private: sanitize_shallowOT::VarSizedBinSearchArrayOf1067 bool sanitize_shallow (hb_sanitize_context_t *c) const 1068 { 1069 TRACE_SANITIZE (this); 1070 return_trace (header.sanitize (c) && 1071 Type::static_size <= header.unitSize && 1072 c->check_range (bytesZ.arrayZ, 1073 header.nUnits, 1074 header.unitSize)); 1075 } 1076 1077 protected: 1078 VarSizedBinSearchHeader header; 1079 UnsizedArrayOf<HBUINT8> bytesZ; 1080 public: 1081 DEFINE_SIZE_ARRAY (10, bytesZ); 1082 }; 1083 1084 1085 } /* namespace OT */ 1086 1087 1088 #endif /* HB_OPEN_TYPE_HH */ 1089