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
setOT::IntType66 void set (wide_type i) { v.set (i); }
operator wide_typeOT::IntType67 operator wide_type () const { return v; }
operator ==OT::IntType68 bool operator == (const IntType<Type,Size> &o) const { return (Type) v == (Type) o.v; }
operator !=OT::IntType69 bool operator != (const IntType<Type,Size> &o) const { return !(*this == o); }
cmpOT::IntType70 static int cmp (const IntType<Type,Size> *a, const IntType<Type,Size> *b) { return b->cmp (*a); }
71 template <typename Type2>
cmpOT::IntType72 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 }
sanitizeOT::IntType80 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
to_floatOT::F2DOT14114 float to_float () const { return ((int32_t) v) / 16384.f; }
set_floatOT::F2DOT14115 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
to_floatOT::Fixed124 float to_float () const { return ((int32_t) v) / 65536.f; }
set_floatOT::Fixed125 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 {
sanitizeOT::LONGDATETIME134 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" */
operator const char*OT::Tag151 operator const char* () const { return reinterpret_cast<const char *> (&this->v); }
operator char*OT::Tag152 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
is_nullOT::Offset174 bool is_null () const { return has_null && 0 == *this; }
175
serializeOT::Offset176 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. */
CalcTableChecksumOT::CheckSum195 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. */
set_for_dataOT::CheckSum207 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 {
to_intOT::FixedVersion222 uint32_t to_int () const { return (major << (sizeof (FixedType) * 8)) + minor; }
223
sanitizeOT::FixedVersion224 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 {
get_nullOT::_hb_has_null245 static const Type *get_null () { return nullptr; }
get_crapOT::_hb_has_null246 static Type *get_crap () { return nullptr; }
247 };
248 template <typename Type>
249 struct _hb_has_null<Type, true>
250 {
get_nullOT::_hb_has_null251 static const Type *get_null () { return &Null(Type); }
get_crapOT::_hb_has_null252 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 {
operator ()OT::OffsetTo258 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 }
operator ()OT::OffsetTo263 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
serializeOT::OffsetTo269 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>
serialize_subsetOT::OffsetTo275 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
sanitize_shallowOT::OffsetTo287 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
sanitizeOT::OffsetTo296 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>
sanitizeOT::OffsetTo305 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>
sanitizeOT::OffsetTo314 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>
sanitizeOT::OffsetTo323 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 */
neuterOT::OffsetTo333 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>
operator +(const Base & base,const OffsetTo<Type,OffsetType,has_null> & offset)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>
operator +(Base & base,OffsetTo<Type,OffsetType,has_null> & offset)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
operator []OT::UnsizedArrayOf360 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 }
operator []OT::UnsizedArrayOf367 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
get_sizeOT::UnsizedArrayOf375 unsigned int get_size (unsigned int len) const
376 { return len * Type::static_size; }
377
operator T*OT::UnsizedArrayOf378 template <typename T> operator T * () { return arrayZ; }
operator const T*OT::UnsizedArrayOf379 template <typename T> operator const T * () const { return arrayZ; }
as_arrayOT::UnsizedArrayOf380 hb_array_t<Type> as_array (unsigned int len)
381 { return hb_array (arrayZ, len); }
as_arrayOT::UnsizedArrayOf382 hb_array_t<const Type> as_array (unsigned int len) const
383 { return hb_array (arrayZ, len); }
operator hb_array_t<Type>OT::UnsizedArrayOf384 operator hb_array_t<Type> () { return as_array (); }
operator hb_array_t<const Type>OT::UnsizedArrayOf385 operator hb_array_t<const Type> () const { return as_array (); }
386
387 template <typename T>
lsearchOT::UnsizedArrayOf388 Type &lsearch (unsigned int len, const T &x, Type ¬_found = Crap (Type))
389 { return *as_array (len).lsearch (x, ¬_found); }
390 template <typename T>
lsearchOT::UnsizedArrayOf391 const Type &lsearch (unsigned int len, const T &x, const Type ¬_found = Null (Type)) const
392 { return *as_array (len).lsearch (x, ¬_found); }
393
qsortOT::UnsizedArrayOf394 void qsort (unsigned int len, unsigned int start = 0, unsigned int end = (unsigned int) -1)
395 { as_array (len).qsort (start, end); }
396
sanitizeOT::UnsizedArrayOf397 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 }
sanitizeOT::UnsizedArrayOf413 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>
sanitizeOT::UnsizedArrayOf423 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
sanitize_shallowOT::UnsizedArrayOf433 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 {
operator []OT::UnsizedOffsetListOf453 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 }
operator []OT::UnsizedOffsetListOf460 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
sanitizeOT::UnsizedOffsetListOf469 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>
sanitizeOT::UnsizedOffsetListOf475 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 {
as_arrayOT::SortedUnsizedArrayOf486 hb_sorted_array_t<Type> as_array (unsigned int len)
487 { return hb_sorted_array (this->arrayZ, len); }
as_arrayOT::SortedUnsizedArrayOf488 hb_sorted_array_t<const Type> as_array (unsigned int len) const
489 { return hb_sorted_array (this->arrayZ, len); }
operator hb_sorted_array_t<Type>OT::SortedUnsizedArrayOf490 operator hb_sorted_array_t<Type> () { return as_array (); }
operator hb_sorted_array_t<const Type>OT::SortedUnsizedArrayOf491 operator hb_sorted_array_t<const Type> () const { return as_array (); }
492
493 template <typename T>
bsearchOT::SortedUnsizedArrayOf494 Type &bsearch (unsigned int len, const T &x, Type ¬_found = Crap (Type))
495 { return *as_array (len).bsearch (x, ¬_found); }
496 template <typename T>
bsearchOT::SortedUnsizedArrayOf497 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>
bfindOT::SortedUnsizedArrayOf500 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
operator []OT::ArrayOf516 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 }
operator []OT::ArrayOf522 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
get_sizeOT::ArrayOf529 unsigned int get_size () const
530 { return len.static_size + len * Type::static_size; }
531
as_arrayOT::ArrayOf532 hb_array_t<Type> as_array ()
533 { return hb_array (arrayZ, len); }
as_arrayOT::ArrayOf534 hb_array_t<const Type> as_array () const
535 { return hb_array (arrayZ, len); }
operator hb_array_t<Type>OT::ArrayOf536 operator hb_array_t<Type> (void) { return as_array (); }
operator hb_array_t<const Type>OT::ArrayOf537 operator hb_array_t<const Type> (void) const { return as_array (); }
538
sub_arrayOT::ArrayOf539 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
540 { return as_array ().sub_array (start_offset, count);}
sub_arrayOT::ArrayOf541 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);}
sub_arrayOT::ArrayOf543 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
544 { return as_array ().sub_array (start_offset, count);}
sub_arrayOT::ArrayOf545 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
serializeOT::ArrayOf548 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>
serializeOT::ArrayOf557 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
sanitizeOT::ArrayOf566 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 }
sanitizeOT::ArrayOf582 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>
sanitizeOT::ArrayOf593 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>
lsearchOT::ArrayOf605 Type &lsearch (const T &x, Type ¬_found = Crap (Type))
606 { return *as_array ().lsearch (x, ¬_found); }
607 template <typename T>
lsearchOT::ArrayOf608 const Type &lsearch (const T &x, const Type ¬_found = Null (Type)) const
609 { return *as_array ().lsearch (x, ¬_found); }
610
qsortOT::ArrayOf611 void qsort (unsigned int start = 0, unsigned int end = (unsigned int) -1)
612 { as_array ().qsort (start, end); }
613
sanitize_shallowOT::ArrayOf614 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 {
operator []OT::OffsetListOf641 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 }
operator []OT::OffsetListOf647 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
subsetOT::OffsetListOf654 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
sanitizeOT::OffsetListOf665 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>
sanitizeOT::OffsetListOf671 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
operator []OT::HeadlessArrayOf686 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 }
operator []OT::HeadlessArrayOf692 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 }
get_sizeOT::HeadlessArrayOf698 unsigned int get_size () const
699 { return lenP1.static_size + (lenP1 ? lenP1 - 1 : 0) * Type::static_size; }
700
serializeOT::HeadlessArrayOf701 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
sanitizeOT::HeadlessArrayOf713 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:
sanitize_shallowOT::HeadlessArrayOf731 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
operator []OT::ArrayOfM1751 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 }
operator []OT::ArrayOfM1757 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 }
get_sizeOT::ArrayOfM1763 unsigned int get_size () const
764 { return lenM1.static_size + (lenM1 + 1) * Type::static_size; }
765
766 template <typename T>
sanitizeOT::ArrayOfM1767 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:
sanitize_shallowOT::ArrayOfM1779 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 {
as_arrayOT::SortedArrayOf797 hb_sorted_array_t<Type> as_array ()
798 { return hb_sorted_array (this->arrayZ, this->len); }
as_arrayOT::SortedArrayOf799 hb_sorted_array_t<const Type> as_array () const
800 { return hb_sorted_array (this->arrayZ, this->len); }
operator hb_sorted_array_t<Type>OT::SortedArrayOf801 operator hb_sorted_array_t<Type> () { return as_array (); }
operator hb_sorted_array_t<const Type>OT::SortedArrayOf802 operator hb_sorted_array_t<const Type> () const { return as_array (); }
803
sub_arrayOT::SortedArrayOf804 hb_array_t<const Type> sub_array (unsigned int start_offset, unsigned int count) const
805 { return as_array ().sub_array (start_offset, count);}
sub_arrayOT::SortedArrayOf806 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);}
sub_arrayOT::SortedArrayOf808 hb_array_t<Type> sub_array (unsigned int start_offset, unsigned int count)
809 { return as_array ().sub_array (start_offset, count);}
sub_arrayOT::SortedArrayOf810 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>
bsearchOT::SortedArrayOf814 Type &bsearch (const T &x, Type ¬_found = Crap (Type))
815 { return *as_array ().bsearch (x, ¬_found); }
816 template <typename T>
bsearchOT::SortedArrayOf817 const Type &bsearch (const T &x, const Type ¬_found = Null (Type)) const
818 { return *as_array ().bsearch (x, ¬_found); }
819 template <typename T>
bfindOT::SortedArrayOf820 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 {
operator uint32_tOT::BinSearchHeader833 operator uint32_t () const { return len; }
834
sanitizeOT::BinSearchHeader835 bool sanitize (hb_sanitize_context_t *c) const
836 {
837 TRACE_SANITIZE (this);
838 return_trace (c->check_struct (this));
839 }
840
setOT::BinSearchHeader841 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
sanitizeOT::VarSizedBinSearchHeader869 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
last_is_terminatorOT::VarSizedBinSearchArrayOf895 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
operator []OT::VarSizedBinSearchArrayOf911 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 }
operator []OT::VarSizedBinSearchArrayOf917 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 }
get_lengthOT::VarSizedBinSearchArrayOf923 unsigned int get_length () const
924 { return header.nUnits - last_is_terminator (); }
get_sizeOT::VarSizedBinSearchArrayOf925 unsigned int get_size () const
926 { return header.static_size + header.nUnits * header.unitSize; }
927
sanitizeOT::VarSizedBinSearchArrayOf928 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 }
sanitizeOT::VarSizedBinSearchArrayOf944 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>
sanitizeOT::VarSizedBinSearchArrayOf955 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>
bsearchOT::VarSizedBinSearchArrayOf967 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:
sanitize_shallowOT::VarSizedBinSearchArrayOf984 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