1/*
2 * Copyright © 2017 Google, Inc.
3 *
4 * This is part of HarfBuzz, a text shaping library.
5 *
6 * Permission is hereby granted, without written agreement and without
7 * license or royalty fees, to use, copy, modify, and distribute this
8 * software and its documentation for any purpose, provided that the
9 * above copyright notice and the following two paragraphs appear in
10 * all copies of this software.
11 *
12 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE TO ANY PARTY FOR
13 * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
14 * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN
15 * IF THE COPYRIGHT HOLDER HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH
16 * DAMAGE.
17 *
18 * THE COPYRIGHT HOLDER SPECIFICALLY DISCLAIMS ANY WARRANTIES, INCLUDING,
19 * BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
20 * FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE PROVIDED HEREUNDER IS
21 * ON AN "AS IS" BASIS, AND THE COPYRIGHT HOLDER HAS NO OBLIGATION TO
22 * PROVIDE MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.
23 *
24 * Google Author(s): Behdad Esfahbod
25 */
26
27#ifndef HB_AAT_LAYOUT_COMMON_HH
28#define HB_AAT_LAYOUT_COMMON_HH
29
30#include "hb-aat-layout.hh"
31
32
33namespace AAT {
34
35using namespace OT;
36
37
38/*
39 * Binary Searching Tables
40 */
41
42struct BinSearchHeader
43{
44
45 inline bool sanitize (hb_sanitize_context_t *c) const
46 {
47 TRACE_SANITIZE (this);
48 return_trace (c->check_struct (this));
49 }
50
51 HBUINT16 unitSize; /* Size of a lookup unit for this search in bytes. */
52 HBUINT16 nUnits; /* Number of units of the preceding size to be searched. */
53 HBUINT16 searchRange; /* The value of unitSize times the largest power of 2
54 * that is less than or equal to the value of nUnits. */
55 HBUINT16 entrySelector; /* The log base 2 of the largest power of 2 less than
56 * or equal to the value of nUnits. */
57 HBUINT16 rangeShift; /* The value of unitSize times the difference of the
58 * value of nUnits minus the largest power of 2 less
59 * than or equal to the value of nUnits. */
60 public:
61 DEFINE_SIZE_STATIC (10);
62};
63
64template <typename Type>
65struct BinSearchArrayOf
66{
67 inline const Type& operator [] (unsigned int i) const
68 {
69 if (unlikely (i >= header.nUnits)) return Null(Type);
70 return StructAtOffset<Type> (bytesZ, i * header.unitSize);
71 }
72 inline Type& operator [] (unsigned int i)
73 {
74 return StructAtOffset<Type> (bytesZ, i * header.unitSize);
75 }
76 inline unsigned int get_size (void) const
77 { return header.static_size + header.nUnits * header.unitSize; }
78
79 inline bool sanitize (hb_sanitize_context_t *c) const
80 {
81 TRACE_SANITIZE (this);
82 if (unlikely (!sanitize_shallow (c))) return_trace (false);
83
84 /* Note: for structs that do not reference other structs,
85 * we do not need to call their sanitize() as we already did
86 * a bound check on the aggregate array size. We just include
87 * a small unreachable expression to make sure the structs
88 * pointed to do have a simple sanitize(), ie. they do not
89 * reference other structs via offsets.
90 */
91 (void) (false && StructAtOffset<Type> (bytesZ, 0).sanitize (c));
92
93 return_trace (true);
94 }
95 inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
96 {
97 TRACE_SANITIZE (this);
98 if (unlikely (!sanitize_shallow (c))) return_trace (false);
99 unsigned int count = header.nUnits;
100 for (unsigned int i = 0; i < count; i++)
101 if (unlikely (!(*this)[i].sanitize (c, base)))
102 return_trace (false);
103 return_trace (true);
104 }
105
106 template <typename T>
107 inline const Type *bsearch (const T &key) const
108 {
109 unsigned int size = header.unitSize;
110 int min = 0, max = (int) header.nUnits - 1;
111 while (min <= max)
112 {
113 int mid = (min + max) / 2;
114 const Type *p = (const Type *) (((const char *) bytesZ) + (mid * size));
115 int c = p->cmp (key);
116 if (c < 0)
117 max = mid - 1;
118 else if (c > 0)
119 min = mid + 1;
120 else
121 return p;
122 }
123 return nullptr;
124 }
125
126 private:
127 inline bool sanitize_shallow (hb_sanitize_context_t *c) const
128 {
129 TRACE_SANITIZE (this);
130 return_trace (header.sanitize (c) &&
131 Type::static_size >= header.unitSize &&
132 c->check_array (bytesZ, header.unitSize, header.nUnits));
133 }
134
135 protected:
136 BinSearchHeader header;
137 HBUINT8 bytesZ[VAR];
138 public:
139 DEFINE_SIZE_ARRAY (10, bytesZ);
140};
141
142
143/*
144 * Lookup Table
145 */
146
147template <typename T> struct Lookup;
148
149template <typename T>
150struct LookupFormat0
151{
152 friend struct Lookup<T>;
153
154 private:
155 inline const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
156 {
157 if (unlikely (glyph_id >= num_glyphs)) return nullptr;
158 return &arrayZ[glyph_id];
159 }
160
161 inline bool sanitize (hb_sanitize_context_t *c) const
162 {
163 TRACE_SANITIZE (this);
164 return_trace (arrayZ.sanitize (c, c->get_num_glyphs ()));
165 }
166
167 protected:
168 HBUINT16 format; /* Format identifier--format = 0 */
169 UnsizedArrayOf<T>
170 arrayZ; /* Array of lookup values, indexed by glyph index. */
171 public:
172 DEFINE_SIZE_ARRAY (2, arrayZ);
173};
174
175
176template <typename T>
177struct LookupSegmentSingle
178{
179 inline int cmp (hb_codepoint_t g) const {
180 return g < first ? -1 : g <= last ? 0 : +1 ;
181 }
182
183 inline bool sanitize (hb_sanitize_context_t *c) const
184 {
185 TRACE_SANITIZE (this);
186 return_trace (c->check_struct (this) && value.sanitize (c));
187 }
188
189 GlyphID last; /* Last GlyphID in this segment */
190 GlyphID first; /* First GlyphID in this segment */
191 T value; /* The lookup value (only one) */
192 public:
193 DEFINE_SIZE_STATIC (4 + T::static_size);
194};
195
196template <typename T>
197struct LookupFormat2
198{
199 friend struct Lookup<T>;
200
201 private:
202 inline const T* get_value (hb_codepoint_t glyph_id) const
203 {
204 const LookupSegmentSingle<T> *v = segments.bsearch (glyph_id);
205 return v ? &v->value : nullptr;
206 }
207
208 inline bool sanitize (hb_sanitize_context_t *c) const
209 {
210 TRACE_SANITIZE (this);
211 return_trace (segments.sanitize (c));
212 }
213
214 protected:
215 HBUINT16 format; /* Format identifier--format = 2 */
216 BinSearchArrayOf<LookupSegmentSingle<T> >
217 segments; /* The actual segments. These must already be sorted,
218 * according to the first word in each one (the last
219 * glyph in each segment). */
220 public:
221 DEFINE_SIZE_ARRAY (8, segments);
222};
223
224template <typename T>
225struct LookupSegmentArray
226{
227 inline const T* get_value (hb_codepoint_t glyph_id, const void *base) const
228 {
229 return first <= glyph_id && glyph_id <= last ? &(base+valuesZ)[glyph_id - first] : nullptr;
230 }
231
232 inline int cmp (hb_codepoint_t g) const {
233 return g < first ? -1 : g <= last ? 0 : +1 ;
234 }
235
236 inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
237 {
238 TRACE_SANITIZE (this);
239 return_trace (c->check_struct (this) &&
240 first <= last &&
241 valuesZ.sanitize (c, base, last - first + 1));
242 }
243
244 GlyphID last; /* Last GlyphID in this segment */
245 GlyphID first; /* First GlyphID in this segment */
246 OffsetTo<UnsizedArrayOf<T> >
247 valuesZ; /* A 16-bit offset from the start of
248 * the table to the data. */
249 public:
250 DEFINE_SIZE_STATIC (6);
251};
252
253template <typename T>
254struct LookupFormat4
255{
256 friend struct Lookup<T>;
257
258 private:
259 inline const T* get_value (hb_codepoint_t glyph_id) const
260 {
261 const LookupSegmentArray<T> *v = segments.bsearch (glyph_id);
262 return v ? v->get_value (glyph_id, this) : nullptr;
263 }
264
265 inline bool sanitize (hb_sanitize_context_t *c) const
266 {
267 TRACE_SANITIZE (this);
268 return_trace (segments.sanitize (c, this));
269 }
270
271 protected:
272 HBUINT16 format; /* Format identifier--format = 2 */
273 BinSearchArrayOf<LookupSegmentArray<T> >
274 segments; /* The actual segments. These must already be sorted,
275 * according to the first word in each one (the last
276 * glyph in each segment). */
277 public:
278 DEFINE_SIZE_ARRAY (8, segments);
279};
280
281template <typename T>
282struct LookupSingle
283{
284 inline int cmp (hb_codepoint_t g) const { return glyph.cmp (g); }
285
286 inline bool sanitize (hb_sanitize_context_t *c) const
287 {
288 TRACE_SANITIZE (this);
289 return_trace (c->check_struct (this) && value.sanitize (c));
290 }
291
292 GlyphID glyph; /* Last GlyphID */
293 T value; /* The lookup value (only one) */
294 public:
295 DEFINE_SIZE_STATIC (4 + T::static_size);
296};
297
298template <typename T>
299struct LookupFormat6
300{
301 friend struct Lookup<T>;
302
303 private:
304 inline const T* get_value (hb_codepoint_t glyph_id) const
305 {
306 const LookupSingle<T> *v = entries.bsearch (glyph_id);
307 return v ? &v->value : nullptr;
308 }
309
310 inline bool sanitize (hb_sanitize_context_t *c) const
311 {
312 TRACE_SANITIZE (this);
313 return_trace (entries.sanitize (c));
314 }
315
316 protected:
317 HBUINT16 format; /* Format identifier--format = 6 */
318 BinSearchArrayOf<LookupSingle<T> >
319 entries; /* The actual entries, sorted by glyph index. */
320 public:
321 DEFINE_SIZE_ARRAY (8, entries);
322};
323
324template <typename T>
325struct LookupFormat8
326{
327 friend struct Lookup<T>;
328
329 private:
330 inline const T* get_value (hb_codepoint_t glyph_id) const
331 {
332 return firstGlyph <= glyph_id && glyph_id - firstGlyph < glyphCount ? &valueArrayZ[glyph_id - firstGlyph] : nullptr;
333 }
334
335 inline bool sanitize (hb_sanitize_context_t *c) const
336 {
337 TRACE_SANITIZE (this);
338 return_trace (c->check_struct (this) && valueArrayZ.sanitize (c, glyphCount));
339 }
340
341 protected:
342 HBUINT16 format; /* Format identifier--format = 6 */
343 GlyphID firstGlyph; /* First glyph index included in the trimmed array. */
344 HBUINT16 glyphCount; /* Total number of glyphs (equivalent to the last
345 * glyph minus the value of firstGlyph plus 1). */
346 UnsizedArrayOf<T>
347 valueArrayZ; /* The lookup values (indexed by the glyph index
348 * minus the value of firstGlyph). */
349 public:
350 DEFINE_SIZE_ARRAY (6, valueArrayZ);
351};
352
353template <typename T>
354struct Lookup
355{
356 inline const T* get_value (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
357 {
358 switch (u.format) {
359 case 0: return u.format0.get_value (glyph_id, num_glyphs);
360 case 2: return u.format2.get_value (glyph_id);
361 case 4: return u.format4.get_value (glyph_id);
362 case 6: return u.format6.get_value (glyph_id);
363 case 8: return u.format8.get_value (glyph_id);
364 default:return nullptr;
365 }
366 }
367
368 inline bool sanitize (hb_sanitize_context_t *c) const
369 {
370 TRACE_SANITIZE (this);
371 if (!u.format.sanitize (c)) return_trace (false);
372 switch (u.format) {
373 case 0: return_trace (u.format0.sanitize (c));
374 case 2: return_trace (u.format2.sanitize (c));
375 case 4: return_trace (u.format4.sanitize (c));
376 case 6: return_trace (u.format6.sanitize (c));
377 case 8: return_trace (u.format8.sanitize (c));
378 default:return_trace (true);
379 }
380 }
381
382 protected:
383 union {
384 HBUINT16 format; /* Format identifier */
385 LookupFormat0<T> format0;
386 LookupFormat2<T> format2;
387 LookupFormat4<T> format4;
388 LookupFormat6<T> format6;
389 LookupFormat8<T> format8;
390 } u;
391 public:
392 DEFINE_SIZE_UNION (2, format);
393};
394
395
396/*
397 * Extended State Table
398 */
399
400template <typename T>
401struct Entry
402{
403 inline bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
404 {
405 TRACE_SANITIZE (this);
406 /* Note, we don't recurse-sanitize data because we don't access it.
407 * That said, in our DEFINE_SIZE_STATIC we access T::static_size,
408 * which ensures that data has a simple sanitize(). To be determined
409 * if I need to remove that as well. */
410 return_trace (c->check_struct (this));
411 }
412
413 public:
414 HBUINT16 newState; /* Byte offset from beginning of state table
415 * to the new state. Really?!?! Or just state
416 * number? The latter in morx for sure. */
417 HBUINT16 flags; /* Table specific. */
418 T data; /* Optional offsets to per-glyph tables. */
419 public:
420 DEFINE_SIZE_STATIC (4 + T::static_size);
421};
422
423template <>
424struct Entry<void>
425{
426 inline bool sanitize (hb_sanitize_context_t *c, unsigned int count) const
427 {
428 TRACE_SANITIZE (this);
429 return_trace (c->check_struct (this));
430 }
431
432 public:
433 HBUINT16 newState; /* Byte offset from beginning of state table to the new state. */
434 HBUINT16 flags; /* Table specific. */
435 public:
436 DEFINE_SIZE_STATIC (4);
437};
438
439template <typename Extra>
440struct StateTable
441{
442 inline unsigned int get_class (hb_codepoint_t glyph_id, unsigned int num_glyphs) const
443 {
444 const HBUINT16 *v = (this+classTable).get_value (glyph_id, num_glyphs);
445 return v ? *v : 1;
446 }
447
448 inline const Entry<Extra> *get_entries () const
449 {
450 return (this+entryTable).arrayZ;
451 }
452
453 inline const Entry<Extra> *get_entryZ (unsigned int state, unsigned int klass) const
454 {
455 if (unlikely (klass >= nClasses)) return nullptr;
456
457 const HBUINT16 *states = (this+stateArrayTable).arrayZ;
458 const Entry<Extra> *entries = (this+entryTable).arrayZ;
459
460 unsigned int entry = states[state * nClasses + klass];
461
462 return &entries[entry];
463 }
464
465 inline bool sanitize (hb_sanitize_context_t *c,
466 unsigned int *num_entries_out = nullptr) const
467 {
468 TRACE_SANITIZE (this);
469 if (unlikely (!(c->check_struct (this) &&
470 classTable.sanitize (c, this)))) return_trace (false);
471
472 const HBUINT16 *states = (this+stateArrayTable).arrayZ;
473 const Entry<Extra> *entries = (this+entryTable).arrayZ;
474
475 unsigned int num_states = 1;
476 unsigned int num_entries = 0;
477
478 unsigned int state = 0;
479 unsigned int entry = 0;
480 while (state < num_states)
481 {
482 if (unlikely (!c->check_array (states,
483 states[0].static_size * nClasses,
484 num_states)))
485 return_trace (false);
486 { /* Sweep new states. */
487 const HBUINT16 *stop = &states[num_states * nClasses];
488 for (const HBUINT16 *p = &states[state * nClasses]; p < stop; p++)
489 num_entries = MAX<unsigned int> (num_entries, *p + 1);
490 state = num_states;
491 }
492
493 if (unlikely (!c->check_array (entries,
494 entries[0].static_size,
495 num_entries)))
496 return_trace (false);
497 { /* Sweep new entries. */
498 const Entry<Extra> *stop = &entries[num_entries];
499 for (const Entry<Extra> *p = &entries[entry]; p < stop; p++)
500 num_states = MAX<unsigned int> (num_states, p->newState + 1);
501 entry = num_entries;
502 }
503 }
504
505 if (num_entries_out)
506 *num_entries_out = num_entries;
507
508 return_trace (true);
509 }
510
511 protected:
512 HBUINT32 nClasses; /* Number of classes, which is the number of indices
513 * in a single line in the state array. */
514 LOffsetTo<Lookup<HBUINT16> >
515 classTable; /* Offset to the class table. */
516 LOffsetTo<UnsizedArrayOf<HBUINT16> >
517 stateArrayTable;/* Offset to the state array. */
518 LOffsetTo<UnsizedArrayOf<Entry<Extra> > >
519 entryTable; /* Offset to the entry array. */
520
521 public:
522 DEFINE_SIZE_STATIC (16);
523};
524
525template <typename EntryData>
526struct StateTableDriver
527{
528 inline StateTableDriver (const StateTable<EntryData> &machine_,
529 hb_buffer_t *buffer_,
530 hb_face_t *face_) :
531 machine (machine_),
532 buffer (buffer_),
533 num_glyphs (face_->get_num_glyphs ()) {}
534
535 template <typename context_t>
536 inline void drive (context_t *c)
537 {
538 hb_glyph_info_t *info = buffer->info;
539
540 if (!c->in_place)
541 buffer->clear_output ();
542
543 unsigned int state = 0;
544 bool last_was_dont_advance = false;
545 for (buffer->idx = 0;;)
546 {
547 unsigned int klass = buffer->idx < buffer->len ?
548 machine.get_class (info[buffer->idx].codepoint, num_glyphs) :
549 0 /* End of text */;
550 const Entry<EntryData> *entry = machine.get_entryZ (state, klass);
551 if (unlikely (!entry))
552 break;
553
554 /* Unsafe-to-break before this if not in state 0, as things might
555 * go differently if we start from state 0 here. */
556 if (state && buffer->idx)
557 {
558 /* If there's no action and we're just epsilon-transitioning to state 0,
559 * safe to break. */
560 if (c->is_actionable (this, entry) ||
561 !(entry->newState == 0 && entry->flags == context_t::DontAdvance))
562 buffer->unsafe_to_break (buffer->idx - 1, buffer->idx + 1);
563 }
564
565 /* Unsafe-to-break if end-of-text would kick in here. */
566 if (buffer->idx + 2 <= buffer->len)
567 {
568 const Entry<EntryData> *end_entry = machine.get_entryZ (state, 0);
569 if (c->is_actionable (this, end_entry))
570 buffer->unsafe_to_break (buffer->idx, buffer->idx + 2);
571 }
572
573 if (unlikely (!c->transition (this, entry)))
574 break;
575
576 last_was_dont_advance = (entry->flags & context_t::DontAdvance) && buffer->max_ops-- > 0;
577
578 state = entry->newState;
579
580 if (buffer->idx == buffer->len)
581 break;
582
583 if (!last_was_dont_advance)
584 buffer->next_glyph ();
585 }
586
587 if (!c->in_place)
588 {
589 for (; buffer->idx < buffer->len;)
590 buffer->next_glyph ();
591 buffer->swap_buffers ();
592 }
593 }
594
595 public:
596 const StateTable<EntryData> &machine;
597 hb_buffer_t *buffer;
598 unsigned int num_glyphs;
599};
600
601
602
603struct hb_aat_apply_context_t :
604 hb_dispatch_context_t<hb_aat_apply_context_t, bool, HB_DEBUG_APPLY>
605{
606 inline const char *get_name (void) { return "APPLY"; }
607 template <typename T>
608 inline return_t dispatch (const T &obj) { return obj.apply (this); }
609 static return_t default_return_value (void) { return false; }
610 bool stop_sublookup_iteration (return_t r) const { return r; }
611
612 hb_font_t *font;
613 hb_face_t *face;
614 hb_buffer_t *buffer;
615 hb_sanitize_context_t sanitizer;
616
617 /* Unused. For debug tracing only. */
618 unsigned int lookup_index;
619 unsigned int debug_depth;
620
621 inline hb_aat_apply_context_t (hb_font_t *font_,
622 hb_buffer_t *buffer_,
623 hb_blob_t *table) :
624 font (font_), face (font->face), buffer (buffer_),
625 sanitizer (), lookup_index (0), debug_depth (0)
626 {
627 sanitizer.init (table);
628 sanitizer.set_num_glyphs (face->get_num_glyphs ());
629 sanitizer.start_processing ();
630 }
631
632 inline void set_lookup_index (unsigned int i) { lookup_index = i; }
633
634 inline ~hb_aat_apply_context_t (void)
635 {
636 sanitizer.end_processing ();
637 }
638};
639
640
641} /* namespace AAT */
642
643
644#endif /* HB_AAT_LAYOUT_COMMON_HH */
645