1 /*
2 * Copyright © 2014 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_OT_CMAP_TABLE_HH
28 #define HB_OT_CMAP_TABLE_HH
29
30 #include "hb-open-type.hh"
31 #include "hb-set.hh"
32
33 /*
34 * cmap -- Character to Glyph Index Mapping
35 * https://docs.microsoft.com/en-us/typography/opentype/spec/cmap
36 */
37 #define HB_OT_TAG_cmap HB_TAG('c','m','a','p')
38
39 namespace OT {
40
41
42 struct CmapSubtableFormat0
43 {
44 bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
45 {
46 hb_codepoint_t gid = codepoint < 256 ? glyphIdArray[codepoint] : 0;
47 if (!gid)
48 return false;
49 *glyph = gid;
50 return true;
51 }
52 void collect_unicodes (hb_set_t *out) const
53 {
54 for (unsigned int i = 0; i < 256; i++)
55 if (glyphIdArray[i])
56 out->add (i);
57 }
58
59 bool sanitize (hb_sanitize_context_t *c) const
60 {
61 TRACE_SANITIZE (this);
62 return_trace (c->check_struct (this));
63 }
64
65 protected:
66 HBUINT16 format; /* Format number is set to 0. */
67 HBUINT16 length; /* Byte length of this subtable. */
68 HBUINT16 language; /* Ignore. */
69 HBUINT8 glyphIdArray[256];/* An array that maps character
70 * code to glyph index values. */
71 public:
72 DEFINE_SIZE_STATIC (6 + 256);
73 };
74
75 struct CmapSubtableFormat4
76 {
77 struct segment_plan
78 {
79 HBUINT16 start_code;
80 HBUINT16 end_code;
81 bool use_delta;
82 };
83
84 bool serialize (hb_serialize_context_t *c,
85 const hb_subset_plan_t *plan,
86 const hb_vector_t<segment_plan> &segments)
87 {
88 TRACE_SERIALIZE (this);
89
90 if (unlikely (!c->extend_min (*this))) return_trace (false);
91
92 this->format.set (4);
93 this->length.set (get_sub_table_size (segments));
94
95 this->segCountX2.set (segments.length * 2);
96 this->entrySelector.set (MAX (1u, hb_bit_storage (segments.length)) - 1);
97 this->searchRange.set (2 * (1u << this->entrySelector));
98 this->rangeShift.set (segments.length * 2 > this->searchRange
99 ? 2 * segments.length - this->searchRange
100 : 0);
101
102 HBUINT16 *end_count = c->allocate_size<HBUINT16> (HBUINT16::static_size * segments.length);
103 c->allocate_size<HBUINT16> (HBUINT16::static_size); // 2 bytes of padding.
104 HBUINT16 *start_count = c->allocate_size<HBUINT16> (HBUINT16::static_size * segments.length);
105 HBINT16 *id_delta = c->allocate_size<HBINT16> (HBUINT16::static_size * segments.length);
106 HBUINT16 *id_range_offset = c->allocate_size<HBUINT16> (HBUINT16::static_size * segments.length);
107
108 if (id_range_offset == nullptr)
109 return_trace (false);
110
111 for (unsigned int i = 0; i < segments.length; i++)
112 {
113 end_count[i].set (segments[i].end_code);
114 start_count[i].set (segments[i].start_code);
115 if (segments[i].use_delta)
116 {
117 hb_codepoint_t cp = segments[i].start_code;
118 hb_codepoint_t start_gid = 0;
119 if (unlikely (!plan->new_gid_for_codepoint (cp, &start_gid) && cp != 0xFFFF))
120 return_trace (false);
121 id_delta[i].set (start_gid - segments[i].start_code);
122 } else {
123 id_delta[i].set (0);
124 unsigned int num_codepoints = segments[i].end_code - segments[i].start_code + 1;
125 HBUINT16 *glyph_id_array = c->allocate_size<HBUINT16> (HBUINT16::static_size * num_codepoints);
126 if (glyph_id_array == nullptr)
127 return_trace (false);
128 // From the cmap spec:
129 //
130 // id_range_offset[i]/2
131 // + (cp - segments[i].start_code)
132 // + (id_range_offset + i)
133 // =
134 // glyph_id_array + (cp - segments[i].start_code)
135 //
136 // So, solve for id_range_offset[i]:
137 //
138 // id_range_offset[i]
139 // =
140 // 2 * (glyph_id_array - id_range_offset - i)
141 id_range_offset[i].set (2 * (
142 glyph_id_array - id_range_offset - i));
143 for (unsigned int j = 0; j < num_codepoints; j++)
144 {
145 hb_codepoint_t cp = segments[i].start_code + j;
146 hb_codepoint_t new_gid;
147 if (unlikely (!plan->new_gid_for_codepoint (cp, &new_gid)))
148 return_trace (false);
149 glyph_id_array[j].set (new_gid);
150 }
151 }
152 }
153
154 return_trace (true);
155 }
156
157 static size_t get_sub_table_size (const hb_vector_t<segment_plan> &segments)
158 {
159 size_t segment_size = 0;
160 for (unsigned int i = 0; i < segments.length; i++)
161 {
162 // Parallel array entries
163 segment_size +=
164 2 // end count
165 + 2 // start count
166 + 2 // delta
167 + 2; // range offset
168
169 if (!segments[i].use_delta)
170 // Add bytes for the glyph index array entries for this segment.
171 segment_size += (segments[i].end_code - segments[i].start_code + 1) * 2;
172 }
173
174 return min_size
175 + 2 // Padding
176 + segment_size;
177 }
178
179 static bool create_sub_table_plan (const hb_subset_plan_t *plan,
180 hb_vector_t<segment_plan> *segments)
181 {
182 segment_plan *segment = nullptr;
183 hb_codepoint_t last_gid = 0;
184
185 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
186 while (plan->unicodes->next (&cp)) {
187 hb_codepoint_t new_gid;
188 if (unlikely (!plan->new_gid_for_codepoint (cp, &new_gid)))
189 {
190 DEBUG_MSG(SUBSET, nullptr, "Unable to find new gid for %04x", cp);
191 return false;
192 }
193
194 /* Stop adding to cmap if we are now outside of unicode BMP. */
195 if (cp > 0xFFFF) break;
196
197 if (!segment ||
198 cp != segment->end_code + 1u)
199 {
200 segment = segments->push ();
201 segment->start_code.set (cp);
202 segment->end_code.set (cp);
203 segment->use_delta = true;
204 } else {
205 segment->end_code.set (cp);
206 if (last_gid + 1u != new_gid)
207 // gid's are not consecutive in this segment so delta
208 // cannot be used.
209 segment->use_delta = false;
210 }
211
212 last_gid = new_gid;
213 }
214
215 // There must be a final entry with end_code == 0xFFFF. Check if we need to add one.
216 if (segment == nullptr || segment->end_code != 0xFFFF)
217 {
218 segment = segments->push ();
219 segment->start_code.set (0xFFFF);
220 segment->end_code.set (0xFFFF);
221 segment->use_delta = true;
222 }
223
224 return true;
225 }
226
227 struct accelerator_t
228 {
229 accelerator_t () {}
230 accelerator_t (const CmapSubtableFormat4 *subtable) { init (subtable); }
231 ~accelerator_t () { fini (); }
232
233 void init (const CmapSubtableFormat4 *subtable)
234 {
235 segCount = subtable->segCountX2 / 2;
236 endCount = subtable->values.arrayZ;
237 startCount = endCount + segCount + 1;
238 idDelta = startCount + segCount;
239 idRangeOffset = idDelta + segCount;
240 glyphIdArray = idRangeOffset + segCount;
241 glyphIdArrayLength = (subtable->length - 16 - 8 * segCount) / 2;
242 }
243 void fini () {}
244
245 bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
246 {
247 /* Custom two-array bsearch. */
248 int min = 0, max = (int) this->segCount - 1;
249 const HBUINT16 *startCount = this->startCount;
250 const HBUINT16 *endCount = this->endCount;
251 unsigned int i;
252 while (min <= max)
253 {
254 int mid = ((unsigned int) min + (unsigned int) max) / 2;
255 if (codepoint < startCount[mid])
256 max = mid - 1;
257 else if (codepoint > endCount[mid])
258 min = mid + 1;
259 else
260 {
261 i = mid;
262 goto found;
263 }
264 }
265 return false;
266
267 found:
268 hb_codepoint_t gid;
269 unsigned int rangeOffset = this->idRangeOffset[i];
270 if (rangeOffset == 0)
271 gid = codepoint + this->idDelta[i];
272 else
273 {
274 /* Somebody has been smoking... */
275 unsigned int index = rangeOffset / 2 + (codepoint - this->startCount[i]) + i - this->segCount;
276 if (unlikely (index >= this->glyphIdArrayLength))
277 return false;
278 gid = this->glyphIdArray[index];
279 if (unlikely (!gid))
280 return false;
281 gid += this->idDelta[i];
282 }
283 gid &= 0xFFFFu;
284 if (!gid)
285 return false;
286 *glyph = gid;
287 return true;
288 }
289 static bool get_glyph_func (const void *obj, hb_codepoint_t codepoint, hb_codepoint_t *glyph)
290 {
291 return ((const accelerator_t *) obj)->get_glyph (codepoint, glyph);
292 }
293 void collect_unicodes (hb_set_t *out) const
294 {
295 unsigned int count = this->segCount;
296 if (count && this->startCount[count - 1] == 0xFFFFu)
297 count--; /* Skip sentinel segment. */
298 for (unsigned int i = 0; i < count; i++)
299 {
300 unsigned int rangeOffset = this->idRangeOffset[i];
301 if (rangeOffset == 0)
302 out->add_range (this->startCount[i], this->endCount[i]);
303 else
304 {
305 for (hb_codepoint_t codepoint = this->startCount[i];
306 codepoint <= this->endCount[i];
307 codepoint++)
308 {
309 unsigned int index = rangeOffset / 2 + (codepoint - this->startCount[i]) + i - this->segCount;
310 if (unlikely (index >= this->glyphIdArrayLength))
311 break;
312 hb_codepoint_t gid = this->glyphIdArray[index];
313 if (unlikely (!gid))
314 continue;
315 out->add (codepoint);
316 }
317 }
318 }
319 }
320
321 const HBUINT16 *endCount;
322 const HBUINT16 *startCount;
323 const HBUINT16 *idDelta;
324 const HBUINT16 *idRangeOffset;
325 const HBUINT16 *glyphIdArray;
326 unsigned int segCount;
327 unsigned int glyphIdArrayLength;
328 };
329
330 bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
331 {
332 accelerator_t accel (this);
333 return accel.get_glyph_func (&accel, codepoint, glyph);
334 }
335 void collect_unicodes (hb_set_t *out) const
336 {
337 accelerator_t accel (this);
338 accel.collect_unicodes (out);
339 }
340
341 bool sanitize (hb_sanitize_context_t *c) const
342 {
343 TRACE_SANITIZE (this);
344 if (unlikely (!c->check_struct (this)))
345 return_trace (false);
346
347 if (unlikely (!c->check_range (this, length)))
348 {
349 /* Some broken fonts have too long of a "length" value.
350 * If that is the case, just change the value to truncate
351 * the subtable at the end of the blob. */
352 uint16_t new_length = (uint16_t) MIN ((uintptr_t) 65535,
353 (uintptr_t) (c->end -
354 (char *) this));
355 if (!c->try_set (&length, new_length))
356 return_trace (false);
357 }
358
359 return_trace (16 + 4 * (unsigned int) segCountX2 <= length);
360 }
361
362
363
364 protected:
365 HBUINT16 format; /* Format number is set to 4. */
366 HBUINT16 length; /* This is the length in bytes of the
367 * subtable. */
368 HBUINT16 language; /* Ignore. */
369 HBUINT16 segCountX2; /* 2 x segCount. */
370 HBUINT16 searchRange; /* 2 * (2**floor(log2(segCount))) */
371 HBUINT16 entrySelector; /* log2(searchRange/2) */
372 HBUINT16 rangeShift; /* 2 x segCount - searchRange */
373
374 UnsizedArrayOf<HBUINT16>
375 values;
376 #if 0
377 HBUINT16 endCount[segCount]; /* End characterCode for each segment,
378 * last=0xFFFFu. */
379 HBUINT16 reservedPad; /* Set to 0. */
380 HBUINT16 startCount[segCount]; /* Start character code for each segment. */
381 HBINT16 idDelta[segCount]; /* Delta for all character codes in segment. */
382 HBUINT16 idRangeOffset[segCount];/* Offsets into glyphIdArray or 0 */
383 UnsizedArrayOf<HBUINT16>
384 glyphIdArray; /* Glyph index array (arbitrary length) */
385 #endif
386
387 public:
388 DEFINE_SIZE_ARRAY (14, values);
389 };
390
391 struct CmapSubtableLongGroup
392 {
393 friend struct CmapSubtableFormat12;
394 friend struct CmapSubtableFormat13;
395 template<typename U>
396 friend struct CmapSubtableLongSegmented;
397 friend struct cmap;
398
399 int cmp (hb_codepoint_t codepoint) const
400 {
401 if (codepoint < startCharCode) return -1;
402 if (codepoint > endCharCode) return +1;
403 return 0;
404 }
405
406 bool sanitize (hb_sanitize_context_t *c) const
407 {
408 TRACE_SANITIZE (this);
409 return_trace (c->check_struct (this));
410 }
411
412 private:
413 HBUINT32 startCharCode; /* First character code in this group. */
414 HBUINT32 endCharCode; /* Last character code in this group. */
415 HBUINT32 glyphID; /* Glyph index; interpretation depends on
416 * subtable format. */
417 public:
418 DEFINE_SIZE_STATIC (12);
419 };
420 DECLARE_NULL_NAMESPACE_BYTES (OT, CmapSubtableLongGroup);
421
422 template <typename UINT>
423 struct CmapSubtableTrimmed
424 {
425 bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
426 {
427 /* Rely on our implicit array bound-checking. */
428 hb_codepoint_t gid = glyphIdArray[codepoint - startCharCode];
429 if (!gid)
430 return false;
431 *glyph = gid;
432 return true;
433 }
434 void collect_unicodes (hb_set_t *out) const
435 {
436 hb_codepoint_t start = startCharCode;
437 unsigned int count = glyphIdArray.len;
438 for (unsigned int i = 0; i < count; i++)
439 if (glyphIdArray[i])
440 out->add (start + i);
441 }
442
443 bool sanitize (hb_sanitize_context_t *c) const
444 {
445 TRACE_SANITIZE (this);
446 return_trace (c->check_struct (this) && glyphIdArray.sanitize (c));
447 }
448
449 protected:
450 UINT formatReserved; /* Subtable format and (maybe) padding. */
451 UINT length; /* Byte length of this subtable. */
452 UINT language; /* Ignore. */
453 UINT startCharCode; /* First character code covered. */
454 ArrayOf<GlyphID, UINT>
455 glyphIdArray; /* Array of glyph index values for character
456 * codes in the range. */
457 public:
458 DEFINE_SIZE_ARRAY (5 * sizeof (UINT), glyphIdArray);
459 };
460
461 struct CmapSubtableFormat6 : CmapSubtableTrimmed<HBUINT16> {};
462 struct CmapSubtableFormat10 : CmapSubtableTrimmed<HBUINT32 > {};
463
464 template <typename T>
465 struct CmapSubtableLongSegmented
466 {
467 friend struct cmap;
468
469 bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
470 {
471 hb_codepoint_t gid = T::group_get_glyph (groups.bsearch (codepoint), codepoint);
472 if (!gid)
473 return false;
474 *glyph = gid;
475 return true;
476 }
477
478 void collect_unicodes (hb_set_t *out) const
479 {
480 for (unsigned int i = 0; i < this->groups.len; i++) {
481 out->add_range (this->groups[i].startCharCode,
482 MIN ((hb_codepoint_t) this->groups[i].endCharCode,
483 (hb_codepoint_t) HB_UNICODE_MAX));
484 }
485 }
486
487 bool sanitize (hb_sanitize_context_t *c) const
488 {
489 TRACE_SANITIZE (this);
490 return_trace (c->check_struct (this) && groups.sanitize (c));
491 }
492
493 bool serialize (hb_serialize_context_t *c,
494 const hb_vector_t<CmapSubtableLongGroup> &group_data)
495 {
496 TRACE_SERIALIZE (this);
497 if (unlikely (!c->extend_min (*this))) return_trace (false);
498 if (unlikely (!groups.serialize (c, group_data.as_array ()))) return_trace (false);
499 return true;
500 }
501
502 protected:
503 HBUINT16 format; /* Subtable format; set to 12. */
504 HBUINT16 reserved; /* Reserved; set to 0. */
505 HBUINT32 length; /* Byte length of this subtable. */
506 HBUINT32 language; /* Ignore. */
507 SortedArrayOf<CmapSubtableLongGroup, HBUINT32>
508 groups; /* Groupings. */
509 public:
510 DEFINE_SIZE_ARRAY (16, groups);
511 };
512
513 struct CmapSubtableFormat12 : CmapSubtableLongSegmented<CmapSubtableFormat12>
514 {
515 static hb_codepoint_t group_get_glyph (const CmapSubtableLongGroup &group,
516 hb_codepoint_t u)
517 { return likely (group.startCharCode <= group.endCharCode) ?
518 group.glyphID + (u - group.startCharCode) : 0; }
519
520
521 bool serialize (hb_serialize_context_t *c,
522 const hb_vector_t<CmapSubtableLongGroup> &groups)
523 {
524 if (unlikely (!c->extend_min (*this))) return false;
525
526 this->format.set (12);
527 this->reserved.set (0);
528 this->length.set (get_sub_table_size (groups));
529
530 return CmapSubtableLongSegmented<CmapSubtableFormat12>::serialize (c, groups);
531 }
532
533 static size_t get_sub_table_size (const hb_vector_t<CmapSubtableLongGroup> &groups)
534 {
535 return 16 + 12 * groups.length;
536 }
537
538 static bool create_sub_table_plan (const hb_subset_plan_t *plan,
539 hb_vector_t<CmapSubtableLongGroup> *groups)
540 {
541 CmapSubtableLongGroup *group = nullptr;
542
543 hb_codepoint_t cp = HB_SET_VALUE_INVALID;
544 while (plan->unicodes->next (&cp)) {
545 hb_codepoint_t new_gid;
546 if (unlikely (!plan->new_gid_for_codepoint (cp, &new_gid)))
547 {
548 DEBUG_MSG(SUBSET, nullptr, "Unable to find new gid for %04x", cp);
549 return false;
550 }
551
552 if (!group || !_is_gid_consecutive (group, cp, new_gid))
553 {
554 group = groups->push ();
555 group->startCharCode.set (cp);
556 group->endCharCode.set (cp);
557 group->glyphID.set (new_gid);
558 }
559 else group->endCharCode.set (cp);
560 }
561
562 DEBUG_MSG(SUBSET, nullptr, "cmap");
563 for (unsigned int i = 0; i < groups->length; i++) {
564 CmapSubtableLongGroup& group = (*groups)[i];
565 DEBUG_MSG(SUBSET, nullptr, " %d: U+%04X-U+%04X, gid %d-%d", i, (uint32_t) group.startCharCode, (uint32_t) group.endCharCode, (uint32_t) group.glyphID, (uint32_t) group.glyphID + ((uint32_t) group.endCharCode - (uint32_t) group.startCharCode));
566 }
567
568 return true;
569 }
570
571 private:
572 static bool _is_gid_consecutive (CmapSubtableLongGroup *group,
573 hb_codepoint_t cp,
574 hb_codepoint_t new_gid)
575 {
576 return (cp - 1 == group->endCharCode) &&
577 new_gid == group->glyphID + (cp - group->startCharCode);
578 }
579
580 };
581
582 struct CmapSubtableFormat13 : CmapSubtableLongSegmented<CmapSubtableFormat13>
583 {
584 static hb_codepoint_t group_get_glyph (const CmapSubtableLongGroup &group,
585 hb_codepoint_t u HB_UNUSED)
586 { return group.glyphID; }
587 };
588
589 typedef enum
590 {
591 GLYPH_VARIANT_NOT_FOUND = 0,
592 GLYPH_VARIANT_FOUND = 1,
593 GLYPH_VARIANT_USE_DEFAULT = 2
594 } glyph_variant_t;
595
596 struct UnicodeValueRange
597 {
598 int cmp (const hb_codepoint_t &codepoint) const
599 {
600 if (codepoint < startUnicodeValue) return -1;
601 if (codepoint > startUnicodeValue + additionalCount) return +1;
602 return 0;
603 }
604
605 bool sanitize (hb_sanitize_context_t *c) const
606 {
607 TRACE_SANITIZE (this);
608 return_trace (c->check_struct (this));
609 }
610
611 HBUINT24 startUnicodeValue; /* First value in this range. */
612 HBUINT8 additionalCount; /* Number of additional values in this
613 * range. */
614 public:
615 DEFINE_SIZE_STATIC (4);
616 };
617
618 struct DefaultUVS : SortedArrayOf<UnicodeValueRange, HBUINT32>
619 {
620 void collect_unicodes (hb_set_t *out) const
621 {
622 unsigned int count = len;
623 for (unsigned int i = 0; i < count; i++)
624 {
625 hb_codepoint_t first = arrayZ[i].startUnicodeValue;
626 hb_codepoint_t last = MIN ((hb_codepoint_t) (first + arrayZ[i].additionalCount),
627 (hb_codepoint_t) HB_UNICODE_MAX);
628 out->add_range (first, last);
629 }
630 }
631
632 public:
633 DEFINE_SIZE_ARRAY (4, *this);
634 };
635
636 struct UVSMapping
637 {
638 int cmp (const hb_codepoint_t &codepoint) const
639 {
640 return unicodeValue.cmp (codepoint);
641 }
642
643 bool sanitize (hb_sanitize_context_t *c) const
644 {
645 TRACE_SANITIZE (this);
646 return_trace (c->check_struct (this));
647 }
648
649 HBUINT24 unicodeValue; /* Base Unicode value of the UVS */
650 GlyphID glyphID; /* Glyph ID of the UVS */
651 public:
652 DEFINE_SIZE_STATIC (5);
653 };
654
655 struct NonDefaultUVS : SortedArrayOf<UVSMapping, HBUINT32>
656 {
657 void collect_unicodes (hb_set_t *out) const
658 {
659 unsigned int count = len;
660 for (unsigned int i = 0; i < count; i++)
661 out->add (arrayZ[i].glyphID);
662 }
663
664 public:
665 DEFINE_SIZE_ARRAY (4, *this);
666 };
667
668 struct VariationSelectorRecord
669 {
670 glyph_variant_t get_glyph (hb_codepoint_t codepoint,
671 hb_codepoint_t *glyph,
672 const void *base) const
673 {
674 if ((base+defaultUVS).bfind (codepoint))
675 return GLYPH_VARIANT_USE_DEFAULT;
676 const UVSMapping &nonDefault = (base+nonDefaultUVS).bsearch (codepoint);
677 if (nonDefault.glyphID)
678 {
679 *glyph = nonDefault.glyphID;
680 return GLYPH_VARIANT_FOUND;
681 }
682 return GLYPH_VARIANT_NOT_FOUND;
683 }
684
685 void collect_unicodes (hb_set_t *out, const void *base) const
686 {
687 (base+defaultUVS).collect_unicodes (out);
688 (base+nonDefaultUVS).collect_unicodes (out);
689 }
690
691 int cmp (const hb_codepoint_t &variation_selector) const
692 {
693 return varSelector.cmp (variation_selector);
694 }
695
696 bool sanitize (hb_sanitize_context_t *c, const void *base) const
697 {
698 TRACE_SANITIZE (this);
699 return_trace (c->check_struct (this) &&
700 defaultUVS.sanitize (c, base) &&
701 nonDefaultUVS.sanitize (c, base));
702 }
703
704 HBUINT24 varSelector; /* Variation selector. */
705 LOffsetTo<DefaultUVS>
706 defaultUVS; /* Offset to Default UVS Table. May be 0. */
707 LOffsetTo<NonDefaultUVS>
708 nonDefaultUVS; /* Offset to Non-Default UVS Table. May be 0. */
709 public:
710 DEFINE_SIZE_STATIC (11);
711 };
712
713 struct CmapSubtableFormat14
714 {
715 glyph_variant_t get_glyph_variant (hb_codepoint_t codepoint,
716 hb_codepoint_t variation_selector,
717 hb_codepoint_t *glyph) const
718 {
719 return record.bsearch (variation_selector).get_glyph (codepoint, glyph, this);
720 }
721
722 void collect_variation_selectors (hb_set_t *out) const
723 {
724 unsigned int count = record.len;
725 for (unsigned int i = 0; i < count; i++)
726 out->add (record.arrayZ[i].varSelector);
727 }
728 void collect_variation_unicodes (hb_codepoint_t variation_selector,
729 hb_set_t *out) const
730 {
731 record.bsearch (variation_selector).collect_unicodes (out, this);
732 }
733
734 bool sanitize (hb_sanitize_context_t *c) const
735 {
736 TRACE_SANITIZE (this);
737 return_trace (c->check_struct (this) &&
738 record.sanitize (c, this));
739 }
740
741 protected:
742 HBUINT16 format; /* Format number is set to 14. */
743 HBUINT32 length; /* Byte length of this subtable. */
744 SortedArrayOf<VariationSelectorRecord, HBUINT32>
745 record; /* Variation selector records; sorted
746 * in increasing order of `varSelector'. */
747 public:
748 DEFINE_SIZE_ARRAY (10, record);
749 };
750
751 struct CmapSubtable
752 {
753 /* Note: We intentionally do NOT implement subtable formats 2 and 8. */
754
755 bool get_glyph (hb_codepoint_t codepoint,
756 hb_codepoint_t *glyph) const
757 {
758 switch (u.format) {
759 case 0: return u.format0 .get_glyph (codepoint, glyph);
760 case 4: return u.format4 .get_glyph (codepoint, glyph);
761 case 6: return u.format6 .get_glyph (codepoint, glyph);
762 case 10: return u.format10.get_glyph (codepoint, glyph);
763 case 12: return u.format12.get_glyph (codepoint, glyph);
764 case 13: return u.format13.get_glyph (codepoint, glyph);
765 case 14:
766 default: return false;
767 }
768 }
769 void collect_unicodes (hb_set_t *out) const
770 {
771 switch (u.format) {
772 case 0: u.format0 .collect_unicodes (out); return;
773 case 4: u.format4 .collect_unicodes (out); return;
774 case 6: u.format6 .collect_unicodes (out); return;
775 case 10: u.format10.collect_unicodes (out); return;
776 case 12: u.format12.collect_unicodes (out); return;
777 case 13: u.format13.collect_unicodes (out); return;
778 case 14:
779 default: return;
780 }
781 }
782
783 bool sanitize (hb_sanitize_context_t *c) const
784 {
785 TRACE_SANITIZE (this);
786 if (!u.format.sanitize (c)) return_trace (false);
787 switch (u.format) {
788 case 0: return_trace (u.format0 .sanitize (c));
789 case 4: return_trace (u.format4 .sanitize (c));
790 case 6: return_trace (u.format6 .sanitize (c));
791 case 10: return_trace (u.format10.sanitize (c));
792 case 12: return_trace (u.format12.sanitize (c));
793 case 13: return_trace (u.format13.sanitize (c));
794 case 14: return_trace (u.format14.sanitize (c));
795 default:return_trace (true);
796 }
797 }
798
799 public:
800 union {
801 HBUINT16 format; /* Format identifier */
802 CmapSubtableFormat0 format0;
803 CmapSubtableFormat4 format4;
804 CmapSubtableFormat6 format6;
805 CmapSubtableFormat10 format10;
806 CmapSubtableFormat12 format12;
807 CmapSubtableFormat13 format13;
808 CmapSubtableFormat14 format14;
809 } u;
810 public:
811 DEFINE_SIZE_UNION (2, format);
812 };
813
814
815 struct EncodingRecord
816 {
817 int cmp (const EncodingRecord &other) const
818 {
819 int ret;
820 ret = platformID.cmp (other.platformID);
821 if (ret) return ret;
822 ret = encodingID.cmp (other.encodingID);
823 if (ret) return ret;
824 return 0;
825 }
826
827 bool sanitize (hb_sanitize_context_t *c, const void *base) const
828 {
829 TRACE_SANITIZE (this);
830 return_trace (c->check_struct (this) &&
831 subtable.sanitize (c, base));
832 }
833
834 HBUINT16 platformID; /* Platform ID. */
835 HBUINT16 encodingID; /* Platform-specific encoding ID. */
836 LOffsetTo<CmapSubtable>
837 subtable; /* Byte offset from beginning of table to the subtable for this encoding. */
838 public:
839 DEFINE_SIZE_STATIC (8);
840 };
841
842 struct cmap
843 {
844 static constexpr hb_tag_t tableTag = HB_OT_TAG_cmap;
845
846 struct subset_plan
847 {
848 size_t final_size () const
849 {
850 return 4 // header
851 + 8 * 3 // 3 EncodingRecord
852 + CmapSubtableFormat4::get_sub_table_size (this->format4_segments)
853 + CmapSubtableFormat12::get_sub_table_size (this->format12_groups);
854 }
855
856 hb_vector_t<CmapSubtableFormat4::segment_plan> format4_segments;
857 hb_vector_t<CmapSubtableLongGroup> format12_groups;
858 };
859
860 bool _create_plan (const hb_subset_plan_t *plan,
861 subset_plan *cmap_plan) const
862 {
863 if (unlikely (!CmapSubtableFormat4::create_sub_table_plan (plan, &cmap_plan->format4_segments)))
864 return false;
865
866 return CmapSubtableFormat12::create_sub_table_plan (plan, &cmap_plan->format12_groups);
867 }
868
869 bool _subset (const hb_subset_plan_t *plan,
870 const subset_plan &cmap_subset_plan,
871 size_t dest_sz,
872 void *dest) const
873 {
874 hb_serialize_context_t c (dest, dest_sz);
875
876 cmap *table = c.start_serialize<cmap> ();
877 if (unlikely (!c.extend_min (*table)))
878 {
879 return false;
880 }
881
882 table->version.set (0);
883
884 if (unlikely (!table->encodingRecord.serialize (&c, /* numTables */ 3)))
885 return false;
886
887 // TODO(grieger): Convert the below to a for loop
888
889 // Format 4, Plat 0 Encoding Record
890 EncodingRecord &format4_plat0_rec = table->encodingRecord[0];
891 format4_plat0_rec.platformID.set (0); // Unicode
892 format4_plat0_rec.encodingID.set (3);
893
894 // Format 4, Plat 3 Encoding Record
895 EncodingRecord &format4_plat3_rec = table->encodingRecord[1];
896 format4_plat3_rec.platformID.set (3); // Windows
897 format4_plat3_rec.encodingID.set (1); // Unicode BMP
898
899 // Format 12 Encoding Record
900 EncodingRecord &format12_rec = table->encodingRecord[2];
901 format12_rec.platformID.set (3); // Windows
902 format12_rec.encodingID.set (10); // Unicode UCS-4
903
904 // Write out format 4 sub table
905 {
906 CmapSubtable &subtable = format4_plat0_rec.subtable.serialize (&c, table);
907 format4_plat3_rec.subtable.set (format4_plat0_rec.subtable);
908 subtable.u.format.set (4);
909
910 CmapSubtableFormat4 &format4 = subtable.u.format4;
911 if (unlikely (!format4.serialize (&c, plan, cmap_subset_plan.format4_segments)))
912 return false;
913 }
914
915 // Write out format 12 sub table.
916 {
917 CmapSubtable &subtable = format12_rec.subtable.serialize (&c, table);
918 subtable.u.format.set (12);
919
920 CmapSubtableFormat12 &format12 = subtable.u.format12;
921 if (unlikely (!format12.serialize (&c, cmap_subset_plan.format12_groups)))
922 return false;
923 }
924
925 c.end_serialize ();
926
927 return true;
928 }
929
930 bool subset (hb_subset_plan_t *plan) const
931 {
932 subset_plan cmap_subset_plan;
933
934 if (unlikely (!_create_plan (plan, &cmap_subset_plan)))
935 {
936 DEBUG_MSG(SUBSET, nullptr, "Failed to generate a cmap subsetting plan.");
937 return false;
938 }
939
940 // We now know how big our blob needs to be
941 size_t dest_sz = cmap_subset_plan.final_size ();
942 void *dest = malloc (dest_sz);
943 if (unlikely (!dest)) {
944 DEBUG_MSG(SUBSET, nullptr, "Unable to alloc %lu for cmap subset output", (unsigned long) dest_sz);
945 return false;
946 }
947
948 if (unlikely (!_subset (plan, cmap_subset_plan, dest_sz, dest)))
949 {
950 DEBUG_MSG(SUBSET, nullptr, "Failed to perform subsetting of cmap.");
951 free (dest);
952 return false;
953 }
954
955 // all done, write the blob into dest
956 hb_blob_t *cmap_prime = hb_blob_create ((const char *) dest,
957 dest_sz,
958 HB_MEMORY_MODE_READONLY,
959 dest,
960 free);
961 bool result = plan->add_table (HB_OT_TAG_cmap, cmap_prime);
962 hb_blob_destroy (cmap_prime);
963 return result;
964 }
965
966 const CmapSubtable *find_best_subtable (bool *symbol = nullptr) const
967 {
968 if (symbol) *symbol = false;
969
970 const CmapSubtable *subtable;
971
972 /* 32-bit subtables. */
973 if ((subtable = this->find_subtable (3, 10))) return subtable;
974 if ((subtable = this->find_subtable (0, 6))) return subtable;
975 if ((subtable = this->find_subtable (0, 4))) return subtable;
976
977 /* 16-bit subtables. */
978 if ((subtable = this->find_subtable (3, 1))) return subtable;
979 if ((subtable = this->find_subtable (0, 3))) return subtable;
980 if ((subtable = this->find_subtable (0, 2))) return subtable;
981 if ((subtable = this->find_subtable (0, 1))) return subtable;
982 if ((subtable = this->find_subtable (0, 0))) return subtable;
983
984 /* Symbol subtable. */
985 if ((subtable = this->find_subtable (3, 0)))
986 {
987 if (symbol) *symbol = true;
988 return subtable;
989 }
990
991 /* Meh. */
992 return &Null (CmapSubtable);
993 }
994
995 struct accelerator_t
996 {
997 void init (hb_face_t *face)
998 {
999 this->table = hb_sanitize_context_t ().reference_table<cmap> (face);
1000 bool symbol;
1001 this->subtable = table->find_best_subtable (&symbol);
1002 this->subtable_uvs = &Null (CmapSubtableFormat14);
1003 {
1004 const CmapSubtable *st = table->find_subtable (0, 5);
1005 if (st && st->u.format == 14)
1006 subtable_uvs = &st->u.format14;
1007 }
1008
1009 this->get_glyph_data = subtable;
1010 if (unlikely (symbol))
1011 {
1012 this->get_glyph_funcZ = get_glyph_from_symbol<CmapSubtable>;
1013 } else {
1014 switch (subtable->u.format) {
1015 /* Accelerate format 4 and format 12. */
1016 default:
1017 this->get_glyph_funcZ = get_glyph_from<CmapSubtable>;
1018 break;
1019 case 12:
1020 this->get_glyph_funcZ = get_glyph_from<CmapSubtableFormat12>;
1021 break;
1022 case 4:
1023 {
1024 this->format4_accel.init (&subtable->u.format4);
1025 this->get_glyph_data = &this->format4_accel;
1026 this->get_glyph_funcZ = this->format4_accel.get_glyph_func;
1027 }
1028 break;
1029 }
1030 }
1031 }
1032
1033 void fini () { this->table.destroy (); }
1034
1035 bool get_nominal_glyph (hb_codepoint_t unicode,
1036 hb_codepoint_t *glyph) const
1037 {
1038 if (unlikely (!this->get_glyph_funcZ)) return false;
1039 return this->get_glyph_funcZ (this->get_glyph_data, unicode, glyph);
1040 }
1041 unsigned int get_nominal_glyphs (unsigned int count,
1042 const hb_codepoint_t *first_unicode,
1043 unsigned int unicode_stride,
1044 hb_codepoint_t *first_glyph,
1045 unsigned int glyph_stride) const
1046 {
1047 if (unlikely (!this->get_glyph_funcZ)) return 0;
1048
1049 hb_cmap_get_glyph_func_t get_glyph_funcZ = this->get_glyph_funcZ;
1050 const void *get_glyph_data = this->get_glyph_data;
1051
1052 unsigned int done;
1053 for (done = 0;
1054 done < count && get_glyph_funcZ (get_glyph_data, *first_unicode, first_glyph);
1055 done++)
1056 {
1057 first_unicode = &StructAtOffsetUnaligned<hb_codepoint_t> (first_unicode, unicode_stride);
1058 first_glyph = &StructAtOffsetUnaligned<hb_codepoint_t> (first_glyph, glyph_stride);
1059 }
1060 return done;
1061 }
1062
1063 bool get_variation_glyph (hb_codepoint_t unicode,
1064 hb_codepoint_t variation_selector,
1065 hb_codepoint_t *glyph) const
1066 {
1067 switch (this->subtable_uvs->get_glyph_variant (unicode,
1068 variation_selector,
1069 glyph))
1070 {
1071 case GLYPH_VARIANT_NOT_FOUND: return false;
1072 case GLYPH_VARIANT_FOUND: return true;
1073 case GLYPH_VARIANT_USE_DEFAULT: break;
1074 }
1075
1076 return get_nominal_glyph (unicode, glyph);
1077 }
1078
1079 void collect_unicodes (hb_set_t *out) const
1080 {
1081 subtable->collect_unicodes (out);
1082 }
1083 void collect_variation_selectors (hb_set_t *out) const
1084 {
1085 subtable_uvs->collect_variation_selectors (out);
1086 }
1087 void collect_variation_unicodes (hb_codepoint_t variation_selector,
1088 hb_set_t *out) const
1089 {
1090 subtable_uvs->collect_variation_unicodes (variation_selector, out);
1091 }
1092
1093 protected:
1094 typedef bool (*hb_cmap_get_glyph_func_t) (const void *obj,
1095 hb_codepoint_t codepoint,
1096 hb_codepoint_t *glyph);
1097
1098 template <typename Type>
1099 static bool get_glyph_from (const void *obj,
1100 hb_codepoint_t codepoint,
1101 hb_codepoint_t *glyph)
1102 {
1103 const Type *typed_obj = (const Type *) obj;
1104 return typed_obj->get_glyph (codepoint, glyph);
1105 }
1106
1107 template <typename Type>
1108 static bool get_glyph_from_symbol (const void *obj,
1109 hb_codepoint_t codepoint,
1110 hb_codepoint_t *glyph)
1111 {
1112 const Type *typed_obj = (const Type *) obj;
1113 if (likely (typed_obj->get_glyph (codepoint, glyph)))
1114 return true;
1115
1116 if (codepoint <= 0x00FFu)
1117 {
1118 /* For symbol-encoded OpenType fonts, we duplicate the
1119 * U+F000..F0FF range at U+0000..U+00FF. That's what
1120 * Windows seems to do, and that's hinted about at:
1121 * https://docs.microsoft.com/en-us/typography/opentype/spec/recom
1122 * under "Non-Standard (Symbol) Fonts". */
1123 return typed_obj->get_glyph (0xF000u + codepoint, glyph);
1124 }
1125
1126 return false;
1127 }
1128
1129 private:
1130 hb_nonnull_ptr_t<const CmapSubtable> subtable;
1131 hb_nonnull_ptr_t<const CmapSubtableFormat14> subtable_uvs;
1132
1133 hb_cmap_get_glyph_func_t get_glyph_funcZ;
1134 const void *get_glyph_data;
1135
1136 CmapSubtableFormat4::accelerator_t format4_accel;
1137
1138 hb_blob_ptr_t<cmap> table;
1139 };
1140
1141 protected:
1142
1143 const CmapSubtable *find_subtable (unsigned int platform_id,
1144 unsigned int encoding_id) const
1145 {
1146 EncodingRecord key;
1147 key.platformID.set (platform_id);
1148 key.encodingID.set (encoding_id);
1149
1150 const EncodingRecord &result = encodingRecord.bsearch (key);
1151 if (!result.subtable)
1152 return nullptr;
1153
1154 return &(this+result.subtable);
1155 }
1156
1157 public:
1158
1159 bool sanitize (hb_sanitize_context_t *c) const
1160 {
1161 TRACE_SANITIZE (this);
1162 return_trace (c->check_struct (this) &&
1163 likely (version == 0) &&
1164 encodingRecord.sanitize (c, this));
1165 }
1166
1167 protected:
1168 HBUINT16 version; /* Table version number (0). */
1169 SortedArrayOf<EncodingRecord>
1170 encodingRecord; /* Encoding tables. */
1171 public:
1172 DEFINE_SIZE_ARRAY (4, encodingRecord);
1173 };
1174
1175 struct cmap_accelerator_t : cmap::accelerator_t {};
1176
1177 } /* namespace OT */
1178
1179
1180 #endif /* HB_OT_CMAP_TABLE_HH */