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 ¬_found = Crap (Type)) 389 { return *as_array (len).lsearch (x, ¬_found); } 390 template <typename T> 391 const Type &lsearch (unsigned int len, const T &x, const Type ¬_found = Null (Type)) const 392 { return *as_array (len).lsearch (x, ¬_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 ¬_found = Crap (Type)) 495 { return *as_array (len).bsearch (x, ¬_found); } 496 template <typename T> 497 const Type &bsearch (unsigned int len, const T &x, const Type ¬_found = Null (Type)) const 498 { return *as_array (len).bsearch (x, ¬_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 ¬_found = Crap (Type)) 606 { return *as_array ().lsearch (x, ¬_found); } 607 template <typename T> 608 const Type &lsearch (const T &x, const Type ¬_found = Null (Type)) const 609 { return *as_array ().lsearch (x, ¬_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 ¬_found = Crap (Type)) 815 { return *as_array ().bsearch (x, ¬_found); } 816 template <typename T> 817 const Type &bsearch (const T &x, const Type ¬_found = Null (Type)) const 818 { return *as_array ().bsearch (x, ¬_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
