src/hb-ot-cmap-table.hh

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