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-subset-plan.hh"
  32
  33 namespace OT {
  34
  35
  36 /*
  37  * cmap -- Character To Glyph Index Mapping Table
  38  */
  39
  40 #define HB_OT_TAG_cmap HB_TAG('c','m','a','p')
  41
  42
  43 struct CmapSubtableFormat0
  44 {
  45   inline bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
  46   {
  47     hb_codepoint_t gid = codepoint < 256 ? glyphIdArray[codepoint] : 0;
  48     if (!gid)
  49       return false;
  50     *glyph = gid;
  51     return true;
  52   }
  53
  54   inline bool sanitize (hb_sanitize_context_t *c) const
  55   {
  56     TRACE_SANITIZE (this);
  57     return_trace (c->check_struct (this));
  58   }
  59
  60   protected:
  61   HBUINT16      format;         /* Format number is set to 0. */
  62   HBUINT16      lengthZ;        /* Byte length of this subtable. */
  63   HBUINT16      languageZ;      /* Ignore. */
  64   HBUINT8       glyphIdArray[256];/* An array that maps character
  65                                  * code to glyph index values. */
  66   public:
  67   DEFINE_SIZE_STATIC (6 + 256);
  68 };
  69
  70 struct CmapSubtableFormat4
  71 {
  72   struct accelerator_t
  73   {
  74     inline void init (const CmapSubtableFormat4 *subtable)
  75     {
  76       segCount = subtable->segCountX2 / 2;
  77       endCount = subtable->values;
  78       startCount = endCount + segCount + 1;
  79       idDelta = startCount + segCount;
  80       idRangeOffset = idDelta + segCount;
  81       glyphIdArray = idRangeOffset + segCount;
  82       glyphIdArrayLength = (subtable->length - 16 - 8 * segCount) / 2;
  83     }
  84
  85     static inline bool get_glyph_func (const void *obj, hb_codepoint_t codepoint, hb_codepoint_t *glyph)
  86     {
  87       const accelerator_t *thiz = (const accelerator_t *) obj;
  88
  89       /* Custom two-array bsearch. */
  90       int min = 0, max = (int) thiz->segCount - 1;
  91       const HBUINT16 *startCount = thiz->startCount;
  92       const HBUINT16 *endCount = thiz->endCount;
  93       unsigned int i;
  94       while (min <= max)
  95       {
  96         int mid = (min + max) / 2;
  97         if (codepoint < startCount[mid])
  98           max = mid - 1;
  99         else if (codepoint > endCount[mid])
 100           min = mid + 1;
 101         else
 102         {
 103           i = mid;
 104           goto found;
 105         }
 106       }
 107       return false;
 108
 109     found:
 110       hb_codepoint_t gid;
 111       unsigned int rangeOffset = thiz->idRangeOffset[i];
 112       if (rangeOffset == 0)
 113         gid = codepoint + thiz->idDelta[i];
 114       else
 115       {
 116         /* Somebody has been smoking... */
 117         unsigned int index = rangeOffset / 2 + (codepoint - thiz->startCount[i]) + i - thiz->segCount;
 118         if (unlikely (index >= thiz->glyphIdArrayLength))
 119           return false;
 120         gid = thiz->glyphIdArray[index];
 121         if (unlikely (!gid))
 122           return false;
 123         gid += thiz->idDelta[i];
 124       }
 125
 126       *glyph = gid & 0xFFFFu;
 127       return true;
 128     }
 129
 130     const HBUINT16 *endCount;
 131     const HBUINT16 *startCount;
 132     const HBUINT16 *idDelta;
 133     const HBUINT16 *idRangeOffset;
 134     const HBUINT16 *glyphIdArray;
 135     unsigned int segCount;
 136     unsigned int glyphIdArrayLength;
 137   };
 138
 139   inline bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
 140   {
 141     accelerator_t accel;
 142     accel.init (this);
 143     return accel.get_glyph_func (&accel, codepoint, glyph);
 144   }
 145
 146   inline bool sanitize (hb_sanitize_context_t *c) const
 147   {
 148     TRACE_SANITIZE (this);
 149     if (unlikely (!c->check_struct (this)))
 150       return_trace (false);
 151
 152     if (unlikely (!c->check_range (this, length)))
 153     {
 154       /* Some broken fonts have too long of a "length" value.
 155        * If that is the case, just change the value to truncate
 156        * the subtable at the end of the blob. */
 157       uint16_t new_length = (uint16_t) MIN ((uintptr_t) 65535,
 158                                             (uintptr_t) (c->end -
 159                                                          (char *) this));
 160       if (!c->try_set (&length, new_length))
 161         return_trace (false);
 162     }
 163
 164     return_trace (16 + 4 * (unsigned int) segCountX2 <= length);
 165   }
 166
 167   protected:
 168   HBUINT16      format;         /* Format number is set to 4. */
 169   HBUINT16      length;         /* This is the length in bytes of the
 170                                  * subtable. */
 171   HBUINT16      languageZ;      /* Ignore. */
 172   HBUINT16      segCountX2;     /* 2 x segCount. */
 173   HBUINT16      searchRangeZ;   /* 2 * (2**floor(log2(segCount))) */
 174   HBUINT16      entrySelectorZ; /* log2(searchRange/2) */
 175   HBUINT16      rangeShiftZ;    /* 2 x segCount - searchRange */
 176
 177   HBUINT16      values[VAR];
 178 #if 0
 179   HBUINT16      endCount[segCount];     /* End characterCode for each segment,
 180                                          * last=0xFFFFu. */
 181   HBUINT16      reservedPad;            /* Set to 0. */
 182   HBUINT16      startCount[segCount];   /* Start character code for each segment. */
 183   HBINT16               idDelta[segCount];      /* Delta for all character codes in segment. */
 184   HBUINT16      idRangeOffset[segCount];/* Offsets into glyphIdArray or 0 */
 185   HBUINT16      glyphIdArray[VAR];      /* Glyph index array (arbitrary length) */
 186 #endif
 187
 188   public:
 189   DEFINE_SIZE_ARRAY (14, values);
 190 };
 191
 192 struct CmapSubtableLongGroup
 193 {
 194   friend struct CmapSubtableFormat12;
 195   friend struct CmapSubtableFormat13;
 196   friend struct cmap;
 197
 198   int cmp (hb_codepoint_t codepoint) const
 199   {
 200     if (codepoint < startCharCode) return -1;
 201     if (codepoint > endCharCode)   return +1;
 202     return 0;
 203   }
 204
 205   inline bool sanitize (hb_sanitize_context_t *c) const
 206   {
 207     TRACE_SANITIZE (this);
 208     return_trace (c->check_struct (this));
 209   }
 210
 211   private:
 212   HBUINT32              startCharCode;  /* First character code in this group. */
 213   HBUINT32              endCharCode;    /* Last character code in this group. */
 214   HBUINT32              glyphID;        /* Glyph index; interpretation depends on
 215                                  * subtable format. */
 216   public:
 217   DEFINE_SIZE_STATIC (12);
 218 };
 219
 220 template <typename UINT>
 221 struct CmapSubtableTrimmed
 222 {
 223   inline bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
 224   {
 225     /* Rely on our implicit array bound-checking. */
 226     hb_codepoint_t gid = glyphIdArray[codepoint - startCharCode];
 227     if (!gid)
 228       return false;
 229     *glyph = gid;
 230     return true;
 231   }
 232
 233   inline bool sanitize (hb_sanitize_context_t *c) const
 234   {
 235     TRACE_SANITIZE (this);
 236     return_trace (c->check_struct (this) && glyphIdArray.sanitize (c));
 237   }
 238
 239   protected:
 240   UINT          formatReserved; /* Subtable format and (maybe) padding. */
 241   UINT          lengthZ;        /* Byte length of this subtable. */
 242   UINT          languageZ;      /* Ignore. */
 243   UINT          startCharCode;  /* First character code covered. */
 244   ArrayOf<GlyphID, UINT>
 245                 glyphIdArray;   /* Array of glyph index values for character
 246                                  * codes in the range. */
 247   public:
 248   DEFINE_SIZE_ARRAY (5 * sizeof (UINT), glyphIdArray);
 249 };
 250
 251 struct CmapSubtableFormat6  : CmapSubtableTrimmed<HBUINT16> {};
 252 struct CmapSubtableFormat10 : CmapSubtableTrimmed<HBUINT32 > {};
 253
 254 template <typename T>
 255 struct CmapSubtableLongSegmented
 256 {
 257   friend struct cmap;
 258
 259   inline bool get_glyph (hb_codepoint_t codepoint, hb_codepoint_t *glyph) const
 260   {
 261     int i = groups.bsearch (codepoint);
 262     if (i == -1)
 263       return false;
 264     *glyph = T::group_get_glyph (groups[i], codepoint);
 265     return true;
 266   }
 267
 268   inline bool sanitize (hb_sanitize_context_t *c) const
 269   {
 270     TRACE_SANITIZE (this);
 271     return_trace (c->check_struct (this) && groups.sanitize (c));
 272   }
 273
 274   inline bool serialize (hb_serialize_context_t *c,
 275                          hb_prealloced_array_t<CmapSubtableLongGroup> &group_data)
 276   {
 277     TRACE_SERIALIZE (this);
 278     if (unlikely (!c->extend_min (*this))) return_trace (false);
 279     Supplier<CmapSubtableLongGroup> supplier (group_data.array, group_data.len);
 280     if (unlikely (!groups.serialize (c, supplier, group_data.len))) return_trace (false);
 281     return true;
 282   }
 283
 284   protected:
 285   HBUINT16      format;         /* Subtable format; set to 12. */
 286   HBUINT16      reservedZ;      /* Reserved; set to 0. */
 287   HBUINT32              lengthZ;        /* Byte length of this subtable. */
 288   HBUINT32              languageZ;      /* Ignore. */
 289   SortedArrayOf<CmapSubtableLongGroup, HBUINT32>
 290                 groups;         /* Groupings. */
 291   public:
 292   DEFINE_SIZE_ARRAY (16, groups);
 293 };
 294
 295 struct CmapSubtableFormat12 : CmapSubtableLongSegmented<CmapSubtableFormat12>
 296 {
 297   static inline hb_codepoint_t group_get_glyph (const CmapSubtableLongGroup &group,
 298                                                 hb_codepoint_t u)
 299   { return group.glyphID + (u - group.startCharCode); }
 300 };
 301
 302 struct CmapSubtableFormat13 : CmapSubtableLongSegmented<CmapSubtableFormat13>
 303 {
 304   static inline hb_codepoint_t group_get_glyph (const CmapSubtableLongGroup &group,
 305                                                 hb_codepoint_t u HB_UNUSED)
 306   { return group.glyphID; }
 307 };
 308
 309 typedef enum
 310 {
 311   GLYPH_VARIANT_NOT_FOUND = 0,
 312   GLYPH_VARIANT_FOUND = 1,
 313   GLYPH_VARIANT_USE_DEFAULT = 2
 314 } glyph_variant_t;
 315
 316 struct UnicodeValueRange
 317 {
 318   inline int cmp (const hb_codepoint_t &codepoint) const
 319   {
 320     if (codepoint < startUnicodeValue) return -1;
 321     if (codepoint > startUnicodeValue + additionalCount) return +1;
 322     return 0;
 323   }
 324
 325   inline bool sanitize (hb_sanitize_context_t *c) const
 326   {
 327     TRACE_SANITIZE (this);
 328     return_trace (c->check_struct (this));
 329   }
 330
 331   UINT24        startUnicodeValue;      /* First value in this range. */
 332   HBUINT8               additionalCount;        /* Number of additional values in this
 333                                          * range. */
 334   public:
 335   DEFINE_SIZE_STATIC (4);
 336 };
 337
 338 typedef SortedArrayOf<UnicodeValueRange, HBUINT32> DefaultUVS;
 339
 340 struct UVSMapping
 341 {
 342   inline int cmp (const hb_codepoint_t &codepoint) const
 343   {
 344     return unicodeValue.cmp (codepoint);
 345   }
 346
 347   inline bool sanitize (hb_sanitize_context_t *c) const
 348   {
 349     TRACE_SANITIZE (this);
 350     return_trace (c->check_struct (this));
 351   }
 352
 353   UINT24        unicodeValue;   /* Base Unicode value of the UVS */
 354   GlyphID       glyphID;        /* Glyph ID of the UVS */
 355   public:
 356   DEFINE_SIZE_STATIC (5);
 357 };
 358
 359 typedef SortedArrayOf<UVSMapping, HBUINT32> NonDefaultUVS;
 360
 361 struct VariationSelectorRecord
 362 {
 363   inline glyph_variant_t get_glyph (hb_codepoint_t codepoint,
 364                                     hb_codepoint_t *glyph,
 365                                     const void *base) const
 366   {
 367     int i;
 368     const DefaultUVS &defaults = base+defaultUVS;
 369     i = defaults.bsearch (codepoint);
 370     if (i != -1)
 371       return GLYPH_VARIANT_USE_DEFAULT;
 372     const NonDefaultUVS &nonDefaults = base+nonDefaultUVS;
 373     i = nonDefaults.bsearch (codepoint);
 374     if (i != -1)
 375     {
 376       *glyph = nonDefaults[i].glyphID;
 377        return GLYPH_VARIANT_FOUND;
 378     }
 379     return GLYPH_VARIANT_NOT_FOUND;
 380   }
 381
 382   inline int cmp (const hb_codepoint_t &variation_selector) const
 383   {
 384     return varSelector.cmp (variation_selector);
 385   }
 386
 387   inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
 388   {
 389     TRACE_SANITIZE (this);
 390     return_trace (c->check_struct (this) &&
 391                   defaultUVS.sanitize (c, base) &&
 392                   nonDefaultUVS.sanitize (c, base));
 393   }
 394
 395   UINT24        varSelector;    /* Variation selector. */
 396   LOffsetTo<DefaultUVS>
 397                 defaultUVS;     /* Offset to Default UVS Table. May be 0. */
 398   LOffsetTo<NonDefaultUVS>
 399                 nonDefaultUVS;  /* Offset to Non-Default UVS Table. May be 0. */
 400   public:
 401   DEFINE_SIZE_STATIC (11);
 402 };
 403
 404 struct CmapSubtableFormat14
 405 {
 406   inline glyph_variant_t get_glyph_variant (hb_codepoint_t codepoint,
 407                                             hb_codepoint_t variation_selector,
 408                                             hb_codepoint_t *glyph) const
 409   {
 410     return record[record.bsearch(variation_selector)].get_glyph (codepoint, glyph, this);
 411   }
 412
 413   inline bool sanitize (hb_sanitize_context_t *c) const
 414   {
 415     TRACE_SANITIZE (this);
 416     return_trace (c->check_struct (this) &&
 417                   record.sanitize (c, this));
 418   }
 419
 420   protected:
 421   HBUINT16      format;         /* Format number is set to 14. */
 422   HBUINT32              lengthZ;        /* Byte length of this subtable. */
 423   SortedArrayOf<VariationSelectorRecord, HBUINT32>
 424                 record;         /* Variation selector records; sorted
 425                                  * in increasing order of `varSelector'. */
 426   public:
 427   DEFINE_SIZE_ARRAY (10, record);
 428 };
 429
 430 struct CmapSubtable
 431 {
 432   /* Note: We intentionally do NOT implement subtable formats 2 and 8. */
 433
 434   inline bool get_glyph (hb_codepoint_t codepoint,
 435                          hb_codepoint_t *glyph) const
 436   {
 437     switch (u.format) {
 438     case  0: return u.format0 .get_glyph (codepoint, glyph);
 439     case  4: return u.format4 .get_glyph (codepoint, glyph);
 440     case  6: return u.format6 .get_glyph (codepoint, glyph);
 441     case 10: return u.format10.get_glyph (codepoint, glyph);
 442     case 12: return u.format12.get_glyph (codepoint, glyph);
 443     case 13: return u.format13.get_glyph (codepoint, glyph);
 444     case 14:
 445     default: return false;
 446     }
 447   }
 448
 449   inline bool sanitize (hb_sanitize_context_t *c) const
 450   {
 451     TRACE_SANITIZE (this);
 452     if (!u.format.sanitize (c)) return_trace (false);
 453     switch (u.format) {
 454     case  0: return_trace (u.format0 .sanitize (c));
 455     case  4: return_trace (u.format4 .sanitize (c));
 456     case  6: return_trace (u.format6 .sanitize (c));
 457     case 10: return_trace (u.format10.sanitize (c));
 458     case 12: return_trace (u.format12.sanitize (c));
 459     case 13: return_trace (u.format13.sanitize (c));
 460     case 14: return_trace (u.format14.sanitize (c));
 461     default:return_trace (true);
 462     }
 463   }
 464
 465   public:
 466   union {
 467   HBUINT16              format;         /* Format identifier */
 468   CmapSubtableFormat0   format0;
 469   CmapSubtableFormat4   format4;
 470   CmapSubtableFormat6   format6;
 471   CmapSubtableFormat10  format10;
 472   CmapSubtableFormat12  format12;
 473   CmapSubtableFormat13  format13;
 474   CmapSubtableFormat14  format14;
 475   } u;
 476   public:
 477   DEFINE_SIZE_UNION (2, format);
 478 };
 479
 480
 481 struct EncodingRecord
 482 {
 483   inline int cmp (const EncodingRecord &other) const
 484   {
 485     int ret;
 486     ret = platformID.cmp (other.platformID);
 487     if (ret) return ret;
 488     ret = encodingID.cmp (other.encodingID);
 489     if (ret) return ret;
 490     return 0;
 491   }
 492
 493   inline bool sanitize (hb_sanitize_context_t *c, const void *base) const
 494   {
 495     TRACE_SANITIZE (this);
 496     return_trace (c->check_struct (this) &&
 497                   subtable.sanitize (c, base));
 498   }
 499
 500   HBUINT16      platformID;     /* Platform ID. */
 501   HBUINT16      encodingID;     /* Platform-specific encoding ID. */
 502   LOffsetTo<CmapSubtable>
 503                 subtable;       /* Byte offset from beginning of table to the subtable for this encoding. */
 504   public:
 505   DEFINE_SIZE_STATIC (8);
 506 };
 507
 508 struct cmap
 509 {
 510   static const hb_tag_t tableTag        = HB_OT_TAG_cmap;
 511
 512   inline bool sanitize (hb_sanitize_context_t *c) const
 513   {
 514     TRACE_SANITIZE (this);
 515     return_trace (c->check_struct (this) &&
 516                   likely (version == 0) &&
 517                   encodingRecord.sanitize (c, this));
 518   }
 519
 520   inline bool populate_groups (hb_subset_plan_t *plan,
 521                                hb_prealloced_array_t<CmapSubtableLongGroup> *groups) const
 522   {
 523     CmapSubtableLongGroup *group = nullptr;
 524     for (unsigned int i = 0; i < plan->codepoints.len; i++) {
 525
 526       hb_codepoint_t cp = plan->codepoints[i];
 527       if (!group || cp - 1 != group->endCharCode)
 528       {
 529         group = groups->push ();
 530         group->startCharCode.set (cp);
 531         group->endCharCode.set (cp);
 532         hb_codepoint_t new_gid;
 533         if (unlikely (!hb_subset_plan_new_gid_for_codepoint (plan, cp, &new_gid)))
 534         {
 535           DEBUG_MSG(SUBSET, nullptr, "Unable to find new gid for %04x", cp);
 536           return false;
 537         }
 538         group->glyphID.set (new_gid);
 539       } else
 540       {
 541         group->endCharCode.set (cp);
 542       }
 543     }
 544
 545     DEBUG_MSG(SUBSET, nullptr, "cmap");
 546     for (unsigned int i = 0; i < groups->len; i++) {
 547       CmapSubtableLongGroup& group = (*groups)[i];
 548       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));
 549     }
 550
 551     return true;
 552   }
 553
 554   inline bool _subset (hb_prealloced_array_t<CmapSubtableLongGroup> &groups,
 555                        size_t dest_sz,
 556                        void *dest) const
 557   {
 558     hb_serialize_context_t c (dest, dest_sz);
 559
 560     OT::cmap *cmap = c.start_serialize<OT::cmap> ();
 561     if (unlikely (!c.extend_min (*cmap)))
 562     {
 563       return false;
 564     }
 565
 566     cmap->version.set (0);
 567
 568     if (unlikely (!cmap->encodingRecord.serialize (&c, /* numTables */ 1))) return false;
 569
 570     EncodingRecord &rec = cmap->encodingRecord[0];
 571     rec.platformID.set (3); // Windows
 572     rec.encodingID.set (10); // Unicode UCS-4
 573
 574     /* capture offset to subtable */
 575     CmapSubtable &subtable = rec.subtable.serialize (&c, cmap);
 576
 577     subtable.u.format.set (12);
 578
 579     CmapSubtableFormat12 &format12 = subtable.u.format12;
 580     if (unlikely (!c.extend_min (format12))) return false;
 581
 582     format12.format.set (12);
 583     format12.reservedZ.set (0);
 584     format12.lengthZ.set (16 + 12 * groups.len);
 585
 586     if (unlikely (!format12.serialize (&c, groups))) return false;
 587
 588     c.end_serialize ();
 589
 590     return true;
 591   }
 592
 593   inline bool subset (hb_subset_plan_t *plan) const
 594   {
 595     hb_auto_array_t<CmapSubtableLongGroup> groups;
 596
 597     if (unlikely (!populate_groups (plan, &groups))) return false;
 598
 599     // We now know how big our blob needs to be
 600     // TODO use APIs from the structs to get size?
 601     size_t dest_sz = 4 // header
 602                    + 8 // 1 EncodingRecord
 603                    + 16 // Format 12 header
 604                    + 12 * groups.len; // SequentialMapGroup records
 605     void *dest = malloc (dest_sz);
 606     if (unlikely (!dest)) {
 607       DEBUG_MSG(SUBSET, nullptr, "Unable to alloc %lu for cmap subset output", (unsigned long) dest_sz);
 608       return false;
 609     }
 610
 611     if (unlikely (!_subset (groups, dest_sz, dest)))
 612     {
 613       free (dest);
 614       return false;
 615     }
 616
 617     // all done, write the blob into dest
 618     hb_blob_t *cmap_prime = hb_blob_create ((const char *)dest,
 619                                             dest_sz,
 620                                             HB_MEMORY_MODE_READONLY,
 621                                             dest,
 622                                             free);
 623     bool result =  hb_subset_plan_add_table (plan, HB_OT_TAG_cmap, cmap_prime);
 624     hb_blob_destroy (cmap_prime);
 625     return result;
 626   }
 627
 628   struct accelerator_t
 629   {
 630     inline void init (hb_face_t *face)
 631     {
 632       this->blob = OT::Sanitizer<OT::cmap>().sanitize (face->reference_table (HB_OT_TAG_cmap));
 633       const OT::cmap *cmap = OT::Sanitizer<OT::cmap>::lock_instance (this->blob);
 634       const OT::CmapSubtable *subtable = nullptr;
 635       const OT::CmapSubtableFormat14 *subtable_uvs = nullptr;
 636
 637       bool symbol = false;
 638       /* 32-bit subtables. */
 639       if (!subtable) subtable = cmap->find_subtable (3, 10);
 640       if (!subtable) subtable = cmap->find_subtable (0, 6);
 641       if (!subtable) subtable = cmap->find_subtable (0, 4);
 642       /* 16-bit subtables. */
 643       if (!subtable) subtable = cmap->find_subtable (3, 1);
 644       if (!subtable) subtable = cmap->find_subtable (0, 3);
 645       if (!subtable) subtable = cmap->find_subtable (0, 2);
 646       if (!subtable) subtable = cmap->find_subtable (0, 1);
 647       if (!subtable) subtable = cmap->find_subtable (0, 0);
 648       if (!subtable)
 649       {
 650         subtable = cmap->find_subtable (3, 0);
 651         if (subtable) symbol = true;
 652       }
 653       /* Meh. */
 654       if (!subtable) subtable = &OT::Null(OT::CmapSubtable);
 655
 656       /* UVS subtable. */
 657       if (!subtable_uvs)
 658       {
 659         const OT::CmapSubtable *st = cmap->find_subtable (0, 5);
 660         if (st && st->u.format == 14)
 661           subtable_uvs = &st->u.format14;
 662       }
 663       /* Meh. */
 664       if (!subtable_uvs) subtable_uvs = &OT::Null(OT::CmapSubtableFormat14);
 665
 666       this->uvs_table = subtable_uvs;
 667
 668       this->get_glyph_data = subtable;
 669       if (unlikely (symbol))
 670         this->get_glyph_func = get_glyph_from_symbol<OT::CmapSubtable>;
 671       else
 672         switch (subtable->u.format) {
 673         /* Accelerate format 4 and format 12. */
 674         default: this->get_glyph_func = get_glyph_from<OT::CmapSubtable>;               break;
 675         case 12: this->get_glyph_func = get_glyph_from<OT::CmapSubtableFormat12>;       break;
 676         case  4:
 677           {
 678             this->format4_accel.init (&subtable->u.format4);
 679             this->get_glyph_data = &this->format4_accel;
 680             this->get_glyph_func = this->format4_accel.get_glyph_func;
 681           }
 682           break;
 683         }
 684     }
 685
 686     inline void fini (void)
 687     {
 688       hb_blob_destroy (this->blob);
 689     }
 690
 691     inline bool get_nominal_glyph (hb_codepoint_t  unicode,
 692                                    hb_codepoint_t *glyph) const
 693     {
 694       return this->get_glyph_func (this->get_glyph_data, unicode, glyph);
 695     }
 696
 697     inline bool get_variation_glyph (hb_codepoint_t  unicode,
 698                                      hb_codepoint_t  variation_selector,
 699                                      hb_codepoint_t *glyph) const
 700     {
 701       switch (this->uvs_table->get_glyph_variant (unicode,
 702                                                   variation_selector,
 703                                                   glyph))
 704       {
 705         case OT::GLYPH_VARIANT_NOT_FOUND:               return false;
 706         case OT::GLYPH_VARIANT_FOUND:           return true;
 707         case OT::GLYPH_VARIANT_USE_DEFAULT:     break;
 708       }
 709
 710       return get_nominal_glyph (unicode, glyph);
 711     }
 712
 713     protected:
 714     typedef bool (*hb_cmap_get_glyph_func_t) (const void *obj,
 715                                               hb_codepoint_t codepoint,
 716                                               hb_codepoint_t *glyph);
 717
 718     template <typename Type>
 719     static inline bool get_glyph_from (const void *obj,
 720                                        hb_codepoint_t codepoint,
 721                                        hb_codepoint_t *glyph)
 722     {
 723       const Type *typed_obj = (const Type *) obj;
 724       return typed_obj->get_glyph (codepoint, glyph);
 725     }
 726
 727     template <typename Type>
 728     static inline bool get_glyph_from_symbol (const void *obj,
 729                                               hb_codepoint_t codepoint,
 730                                               hb_codepoint_t *glyph)
 731     {
 732       const Type *typed_obj = (const Type *) obj;
 733       if (likely (typed_obj->get_glyph (codepoint, glyph)))
 734         return true;
 735
 736       if (codepoint <= 0x00FFu)
 737       {
 738         /* For symbol-encoded OpenType fonts, we duplicate the
 739          * U+F000..F0FF range at U+0000..U+00FF.  That's what
 740          * Windows seems to do, and that's hinted about at:
 741          * http://www.microsoft.com/typography/otspec/recom.htm
 742          * under "Non-Standard (Symbol) Fonts". */
 743         return typed_obj->get_glyph (0xF000u + codepoint, glyph);
 744       }
 745
 746       return false;
 747     }
 748
 749     private:
 750     hb_cmap_get_glyph_func_t get_glyph_func;
 751     const void *get_glyph_data;
 752     OT::CmapSubtableFormat4::accelerator_t format4_accel;
 753
 754     const OT::CmapSubtableFormat14 *uvs_table;
 755     hb_blob_t *blob;
 756   };
 757
 758   protected:
 759
 760   inline const CmapSubtable *find_subtable (unsigned int platform_id,
 761                                             unsigned int encoding_id) const
 762   {
 763     EncodingRecord key;
 764     key.platformID.set (platform_id);
 765     key.encodingID.set (encoding_id);
 766
 767     /* Note: We can use bsearch, but since it has no performance
 768      * implications, we use lsearch and as such accept fonts with
 769      * unsorted subtable list. */
 770     int result = encodingRecord./*bsearch*/lsearch (key);
 771     if (result == -1 || !encodingRecord[result].subtable)
 772       return nullptr;
 773
 774     return &(this+encodingRecord[result].subtable);
 775   }
 776
 777   protected:
 778   HBUINT16              version;        /* Table version number (0). */
 779   SortedArrayOf<EncodingRecord>
 780                         encodingRecord; /* Encoding tables. */
 781   public:
 782   DEFINE_SIZE_ARRAY (4, encodingRecord);
 783 };
 784
 785
 786 } /* namespace OT */
 787
 788
 789 #endif /* HB_OT_CMAP_TABLE_HH */