src/fccharset.c

   1 /*
   2  * $XFree86: xc/lib/fontconfig/src/fccharset.c,v 1.15 2002/07/06 23:47:43 keithp Exp $
   3  *
   4  * Copyright © 2001 Keith Packard, member of The XFree86 Project, Inc.
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 #include <stdlib.h>
  26 #include "fcint.h"
  27
  28 /* #define CHECK */
  29
  30 /* #define CHATTY */
  31
  32 FcCharSet *
  33 FcCharSetCreate (void)
  34 {
  35     FcCharSet   *fcs;
  36
  37     fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
  38     if (!fcs)
  39         return 0;
  40     FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
  41     fcs->ref = 1;
  42     fcs->num = 0;
  43     fcs->leaves = 0;
  44     fcs->numbers = 0;
  45     fcs->constant = FcFalse;
  46     return fcs;
  47 }
  48
  49 FcCharSet *
  50 FcCharSetNew (void);
  51
  52 FcCharSet *
  53 FcCharSetNew (void)
  54 {
  55     return FcCharSetCreate ();
  56 }
  57
  58
  59 void
  60 FcCharSetDestroy (FcCharSet *fcs)
  61 {
  62     if (!fcs->constant && --fcs->ref <= 0)
  63     {
  64         int i;
  65
  66         for (i = 0; i < fcs->num; i++)
  67         {
  68             FcMemFree (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
  69             free (fcs->leaves[i]);
  70         }
  71         if (fcs->leaves)
  72         {
  73             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
  74             free (fcs->leaves);
  75         }
  76         if (fcs->numbers)
  77         {
  78             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
  79             free (fcs->numbers);
  80         }
  81         FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
  82         free (fcs);
  83     }
  84 }
  85
  86 /*
  87  * Locate the leaf containing the specified char, return
  88  * its index if it exists, otherwise return negative of
  89  * the (position + 1) where it should be inserted
  90  */
  91
  92 static int
  93 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
  94 {
  95     FcChar16            *numbers = fcs->numbers;
  96     FcChar16            page;
  97     int                 low = 0;
  98     int                 high = fcs->num - 1;
  99
 100     if (!numbers)
 101         return -1;
 102     ucs4 >>= 8;
 103     while (low <= high)
 104     {
 105         int mid = (low + high) >> 1;
 106         page = numbers[mid];
 107         if (page == ucs4)
 108             return mid;
 109         if (page < ucs4)
 110             low = mid + 1;
 111         else
 112             high = mid - 1;
 113     }
 114     if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
 115         high++;
 116     return -(high + 1);
 117 }
 118
 119 static FcCharLeaf *
 120 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 121 {
 122     int pos = FcCharSetFindLeafPos (fcs, ucs4);
 123     if (pos >= 0)
 124         return fcs->leaves[pos];
 125     return 0;
 126 }
 127
 128 static FcBool
 129 FcCharSetPutLeaf (FcCharSet     *fcs,
 130                   FcChar32      ucs4,
 131                   FcCharLeaf    *leaf,
 132                   int           pos)
 133 {
 134     FcCharLeaf  **leaves;
 135     FcChar16    *numbers;
 136
 137     ucs4 >>= 8;
 138     if (ucs4 >= 0x10000)
 139         return FcFalse;
 140     if (!fcs->leaves)
 141         leaves = malloc (sizeof (FcCharLeaf *));
 142     else
 143         leaves = realloc (fcs->leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
 144     if (!leaves)
 145         return FcFalse;
 146     fcs->leaves = leaves;
 147     if (!fcs->numbers)
 148         numbers = malloc (sizeof (FcChar16));
 149     else
 150         numbers = realloc (fcs->numbers, (fcs->num + 1) * sizeof (FcChar16));
 151     if (!numbers)
 152         return FcFalse;
 153     fcs->numbers = numbers;
 154
 155     memmove (fcs->leaves + pos + 1, fcs->leaves + pos,
 156              (fcs->num - pos) * sizeof (FcCharLeaf *));
 157     memmove (fcs->numbers + pos + 1, fcs->numbers + pos,
 158              (fcs->num - pos) * sizeof (FcChar16));
 159     fcs->numbers[pos] = (FcChar16) ucs4;
 160     fcs->leaves[pos] = leaf;
 161     fcs->num++;
 162     return FcTrue;
 163 }
 164
 165 /*
 166  * Locate the leaf containing the specified char, creating it
 167  * if desired
 168  */
 169
 170 static FcCharLeaf *
 171 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 172 {
 173     int                 pos;
 174     FcCharLeaf          *leaf;
 175
 176     pos = FcCharSetFindLeafPos (fcs, ucs4);
 177     if (pos >= 0)
 178         return fcs->leaves[pos];
 179
 180     leaf = calloc (1, sizeof (FcCharLeaf));
 181     if (!leaf)
 182         return 0;
 183
 184     pos = -pos - 1;
 185     if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
 186     {
 187         free (leaf);
 188         return 0;
 189     }
 190     return leaf;
 191 }
 192
 193 static FcBool
 194 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
 195 {
 196     int             pos;
 197
 198     pos = FcCharSetFindLeafPos (fcs, ucs4);
 199     if (pos >= 0)
 200     {
 201         FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
 202         free (fcs->leaves[pos]);
 203         fcs->leaves[pos] = leaf;
 204         return FcTrue;
 205     }
 206     pos = -pos - 1;
 207     return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
 208 }
 209
 210 FcBool
 211 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 212 {
 213     FcCharLeaf  *leaf;
 214     FcChar32    *b;
 215
 216     if (fcs->constant)
 217         return FcFalse;
 218     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
 219     if (!leaf)
 220         return FcFalse;
 221     b = &leaf->map[(ucs4 & 0xff) >> 5];
 222     *b |= (1 << (ucs4 & 0x1f));
 223     return FcTrue;
 224 }
 225
 226 /*
 227  * An iterator for the leaves of a charset
 228  */
 229
 230 typedef struct _fcCharSetIter {
 231     FcCharLeaf      *leaf;
 232     FcChar32        ucs4;
 233     int             pos;
 234 } FcCharSetIter;
 235
 236 /*
 237  * Set iter->leaf to the leaf containing iter->ucs4 or higher
 238  */
 239
 240 static void
 241 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 242 {
 243     int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
 244
 245     if (pos < 0)
 246     {
 247         pos = -pos - 1;
 248         if (pos == fcs->num)
 249         {
 250             iter->ucs4 = ~0;
 251             iter->leaf = 0;
 252             return;
 253         }
 254         iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
 255     }
 256     iter->leaf = fcs->leaves[pos];
 257     iter->pos = pos;
 258 #ifdef CHATTY
 259     printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
 260 #endif
 261 }
 262
 263 static void
 264 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 265 {
 266     int pos = iter->pos + 1;
 267     if (pos >= fcs->num)
 268     {
 269         iter->ucs4 = ~0;
 270         iter->leaf = 0;
 271     }
 272     else
 273     {
 274         iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
 275         iter->leaf = fcs->leaves[pos];
 276         iter->pos = pos;
 277     }
 278 }
 279
 280 #ifdef CHATTY
 281 static void
 282 FcCharSetDump (const FcCharSet *fcs)
 283 {
 284     int         pos;
 285
 286     printf ("fcs %08x:\n", (FcChar32) fcs);
 287     for (pos = 0; pos < fcs->num; pos++)
 288     {
 289         FcCharLeaf      *leaf = fcs->leaves[pos];
 290         FcChar32        ucs4 = (FcChar32) fcs->numbers[pos] << 8;
 291
 292         printf ("    %08x: %08x\n", ucs4, (FcChar32) leaf);
 293     }
 294 }
 295 #endif
 296
 297 static void
 298 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 299 {
 300 #ifdef CHATTY
 301     FcCharSetDump (fcs);
 302 #endif
 303     iter->ucs4 = 0;
 304     FcCharSetIterSet (fcs, iter);
 305 }
 306
 307 FcCharSet *
 308 FcCharSetCopy (FcCharSet *src)
 309 {
 310     src->ref++;
 311     return src;
 312 }
 313
 314 FcBool
 315 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
 316 {
 317     FcCharSetIter   ai, bi;
 318     int             i;
 319
 320     if (a == b)
 321         return FcTrue;
 322     for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
 323          ai.leaf && bi.leaf;
 324          FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
 325     {
 326         if (ai.ucs4 != bi.ucs4)
 327             return FcFalse;
 328         for (i = 0; i < 256/32; i++)
 329             if (ai.leaf->map[i] != bi.leaf->map[i])
 330                 return FcFalse;
 331     }
 332     return ai.leaf == bi.leaf;
 333 }
 334
 335 static FcBool
 336 FcCharSetAddLeaf (FcCharSet     *fcs,
 337                   FcChar32      ucs4,
 338                   FcCharLeaf    *leaf)
 339 {
 340     FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
 341     if (!new)
 342         return FcFalse;
 343     *new = *leaf;
 344     return FcTrue;
 345 }
 346
 347 static FcCharSet *
 348 FcCharSetOperate (const FcCharSet   *a,
 349                   const FcCharSet   *b,
 350                   FcBool            (*overlap) (FcCharLeaf          *result,
 351                                                 const FcCharLeaf    *al,
 352                                                 const FcCharLeaf    *bl),
 353                   FcBool        aonly,
 354                   FcBool        bonly)
 355 {
 356     FcCharSet       *fcs;
 357     FcCharSetIter   ai, bi;
 358
 359     fcs = FcCharSetCreate ();
 360     if (!fcs)
 361         goto bail0;
 362     FcCharSetIterStart (a, &ai);
 363     FcCharSetIterStart (b, &bi);
 364     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
 365     {
 366         if (ai.ucs4 < bi.ucs4)
 367         {
 368             if (aonly)
 369             {
 370                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
 371                     goto bail1;
 372                 FcCharSetIterNext (a, &ai);
 373             }
 374             else
 375             {
 376                 ai.ucs4 = bi.ucs4;
 377                 FcCharSetIterSet (a, &ai);
 378             }
 379         }
 380         else if (bi.ucs4 < ai.ucs4 )
 381         {
 382             if (bonly)
 383             {
 384                 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
 385                     goto bail1;
 386                 FcCharSetIterNext (b, &bi);
 387             }
 388             else
 389             {
 390                 bi.ucs4 = ai.ucs4;
 391                 FcCharSetIterSet (b, &bi);
 392             }
 393         }
 394         else
 395         {
 396             FcCharLeaf  leaf;
 397
 398             if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 399             {
 400                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
 401                     goto bail1;
 402             }
 403             FcCharSetIterNext (a, &ai);
 404             FcCharSetIterNext (b, &bi);
 405         }
 406     }
 407     return fcs;
 408 bail1:
 409     FcCharSetDestroy (fcs);
 410 bail0:
 411     return 0;
 412 }
 413
 414 static FcBool
 415 FcCharSetIntersectLeaf (FcCharLeaf *result,
 416                         const FcCharLeaf *al,
 417                         const FcCharLeaf *bl)
 418 {
 419     int     i;
 420     FcBool  nonempty = FcFalse;
 421
 422     for (i = 0; i < 256/32; i++)
 423         if ((result->map[i] = al->map[i] & bl->map[i]))
 424             nonempty = FcTrue;
 425     return nonempty;
 426 }
 427
 428 FcCharSet *
 429 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 430 {
 431     return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 432 }
 433
 434 static FcBool
 435 FcCharSetUnionLeaf (FcCharLeaf *result,
 436                     const FcCharLeaf *al,
 437                     const FcCharLeaf *bl)
 438 {
 439     int i;
 440
 441     for (i = 0; i < 256/32; i++)
 442         result->map[i] = al->map[i] | bl->map[i];
 443     return FcTrue;
 444 }
 445
 446 FcCharSet *
 447 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 448 {
 449     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 450 }
 451
 452 static FcBool
 453 FcCharSetSubtractLeaf (FcCharLeaf *result,
 454                        const FcCharLeaf *al,
 455                        const FcCharLeaf *bl)
 456 {
 457     int     i;
 458     FcBool  nonempty = FcFalse;
 459
 460     for (i = 0; i < 256/32; i++)
 461         if ((result->map[i] = al->map[i] & ~bl->map[i]))
 462             nonempty = FcTrue;
 463     return nonempty;
 464 }
 465
 466 FcCharSet *
 467 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 468 {
 469     return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 470 }
 471
 472 FcBool
 473 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 474 {
 475     FcCharLeaf  *leaf = FcCharSetFindLeaf (fcs, ucs4);
 476     if (!leaf)
 477         return FcFalse;
 478     return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
 479 }
 480
 481 static FcChar32
 482 FcCharSetPopCount (FcChar32 c1)
 483 {
 484     /* hackmem 169 */
 485     FcChar32    c2 = (c1 >> 1) & 033333333333;
 486     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
 487     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
 488 }
 489
 490 FcChar32
 491 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
 492 {
 493     FcCharSetIter   ai, bi;
 494     FcChar32        count = 0;
 495
 496     FcCharSetIterStart (a, &ai);
 497     FcCharSetIterStart (b, &bi);
 498     while (ai.leaf && bi.leaf)
 499     {
 500         if (ai.ucs4 == bi.ucs4)
 501         {
 502             FcChar32    *am = ai.leaf->map;
 503             FcChar32    *bm = bi.leaf->map;
 504             int         i = 256/32;
 505             while (i--)
 506                 count += FcCharSetPopCount (*am++ & *bm++);
 507             FcCharSetIterNext (a, &ai);
 508         }
 509         else if (ai.ucs4 < bi.ucs4)
 510         {
 511             ai.ucs4 = bi.ucs4;
 512             FcCharSetIterSet (a, &ai);
 513         }
 514         if (bi.ucs4 < ai.ucs4)
 515         {
 516             bi.ucs4 = ai.ucs4;
 517             FcCharSetIterSet (b, &bi);
 518         }
 519     }
 520     return count;
 521 }
 522
 523 FcChar32
 524 FcCharSetCount (const FcCharSet *a)
 525 {
 526     FcCharSetIter   ai;
 527     FcChar32        count = 0;
 528
 529     for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
 530     {
 531         int                 i = 256/32;
 532         FcChar32            *am = ai.leaf->map;
 533
 534         while (i--)
 535             count += FcCharSetPopCount (*am++);
 536     }
 537     return count;
 538 }
 539
 540 FcChar32
 541 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
 542 {
 543     FcCharSetIter   ai, bi;
 544     FcChar32        count = 0;
 545
 546     FcCharSetIterStart (a, &ai);
 547     FcCharSetIterStart (b, &bi);
 548     while (ai.leaf)
 549     {
 550         if (ai.ucs4 <= bi.ucs4)
 551         {
 552             FcChar32    *am = ai.leaf->map;
 553             int         i = 256/32;
 554             if (ai.ucs4 == bi.ucs4)
 555             {
 556                 FcChar32        *bm = bi.leaf->map;;
 557                 while (i--)
 558                     count += FcCharSetPopCount (*am++ & ~*bm++);
 559             }
 560             else
 561             {
 562                 while (i--)
 563                     count += FcCharSetPopCount (*am++);
 564             }
 565             FcCharSetIterNext (a, &ai);
 566         }
 567         else if (bi.leaf)
 568         {
 569             bi.ucs4 = ai.ucs4;
 570             FcCharSetIterSet (b, &bi);
 571         }
 572     }
 573     return count;
 574 }
 575
 576 /*
 577  * return FcTrue iff a is a subset of b
 578  */
 579 FcBool
 580 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 581 {
 582     int         ai, bi;
 583     FcChar16    an, bn;
 584
 585     if (a == b) return FcTrue;
 586     bi = 0;
 587     ai = 0;
 588     while (ai < a->num && bi < b->num)
 589     {
 590         an = a->numbers[ai];
 591         bn = b->numbers[bi];
 592         if (an == bn)
 593         {
 594             FcChar32    *am = a->leaves[ai]->map;
 595             FcChar32    *bm = b->leaves[bi]->map;
 596
 597             if (am != bm)
 598             {
 599                 int     i = 256/32;
 600                 while (i--)
 601                     if (*am++ & ~*bm++)
 602                         return FcFalse;
 603             }
 604             ai++;
 605             bi++;
 606         }
 607         else if (an < bn)
 608             return FcFalse;
 609         else
 610         {
 611             int     low = bi + 1;
 612             int     high = b->num - 1;
 613
 614             while (low <= high)
 615             {
 616                 int mid = (low + high) >> 1;
 617                 bn = b->numbers[mid];
 618                 if (bn == an)
 619                 {
 620                     high = mid;
 621                     break;
 622                 }
 623                 if (bn < an)
 624                     low = mid + 1;
 625                 else
 626                     high = mid - 1;
 627             }
 628             bi = high;
 629             while (bi < b->num && b->numbers[bi] < an)
 630                 bi++;
 631         }
 632     }
 633     return FcTrue;
 634 }
 635
 636 /*
 637  * These two functions efficiently walk the entire charmap for
 638  * other software (like pango) that want their own copy
 639  */
 640
 641 FcChar32
 642 FcCharSetNextPage (const FcCharSet  *a,
 643                    FcChar32         map[FC_CHARSET_MAP_SIZE],
 644                    FcChar32         *next)
 645 {
 646     FcCharSetIter   ai;
 647     FcChar32        page;
 648
 649     ai.ucs4 = *next;
 650     FcCharSetIterSet (a, &ai);
 651     if (!ai.leaf)
 652         return FC_CHARSET_DONE;
 653
 654     /*
 655      * Save current information
 656      */
 657     page = ai.ucs4;
 658     memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
 659     /*
 660      * Step to next page
 661      */
 662     FcCharSetIterNext (a, &ai);
 663     *next = ai.ucs4;
 664
 665     return page;
 666 }
 667
 668 FcChar32
 669 FcCharSetFirstPage (const FcCharSet *a,
 670                     FcChar32        map[FC_CHARSET_MAP_SIZE],
 671                     FcChar32        *next)
 672 {
 673     *next = 0;
 674     return FcCharSetNextPage (a, map, next);
 675 }
 676
 677 /*
 678  * old coverage API, rather hard to use correctly
 679  */
 680 FcChar32
 681 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
 682
 683 FcChar32
 684 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
 685 {
 686     FcCharSetIter   ai;
 687
 688     ai.ucs4 = page;
 689     FcCharSetIterSet (a, &ai);
 690     if (!ai.leaf)
 691     {
 692         memset (result, '\0', 256 / 8);
 693         page = 0;
 694     }
 695     else
 696     {
 697         memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
 698         FcCharSetIterNext (a, &ai);
 699         page = ai.ucs4;
 700     }
 701     return page;
 702 }
 703
 704 /*
 705  * ASCII representation of charsets.
 706  *
 707  * Each leaf is represented as 9 32-bit values, the code of the first character followed
 708  * by 8 32 bit values for the leaf itself.  Each value is encoded as 5 ASCII characters,
 709  * only 85 different values are used to avoid control characters as well as the other
 710  * characters used to encode font names.  85**5 > 2^32 so things work out, but
 711  * it's not exactly human readable output.  As a special case, 0 is encoded as a space
 712  */
 713
 714 static const unsigned char      charToValue[256] = {
 715     /*     "" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 716     /*   "\b" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 717     /* "\020" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 718     /* "\030" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 719     /*    " " */ 0xff,  0x00,  0xff,  0x01,  0x02,  0x03,  0x04,  0xff,
 720     /*    "(" */ 0x05,  0x06,  0x07,  0x08,  0xff,  0xff,  0x09,  0x0a,
 721     /*    "0" */ 0x0b,  0x0c,  0x0d,  0x0e,  0x0f,  0x10,  0x11,  0x12,
 722     /*    "8" */ 0x13,  0x14,  0xff,  0x15,  0x16,  0xff,  0x17,  0x18,
 723     /*    "@" */ 0x19,  0x1a,  0x1b,  0x1c,  0x1d,  0x1e,  0x1f,  0x20,
 724     /*    "H" */ 0x21,  0x22,  0x23,  0x24,  0x25,  0x26,  0x27,  0x28,
 725     /*    "P" */ 0x29,  0x2a,  0x2b,  0x2c,  0x2d,  0x2e,  0x2f,  0x30,
 726     /*    "X" */ 0x31,  0x32,  0x33,  0x34,  0xff,  0x35,  0x36,  0xff,
 727     /*    "`" */ 0xff,  0x37,  0x38,  0x39,  0x3a,  0x3b,  0x3c,  0x3d,
 728     /*    "h" */ 0x3e,  0x3f,  0x40,  0x41,  0x42,  0x43,  0x44,  0x45,
 729     /*    "p" */ 0x46,  0x47,  0x48,  0x49,  0x4a,  0x4b,  0x4c,  0x4d,
 730     /*    "x" */ 0x4e,  0x4f,  0x50,  0x51,  0x52,  0x53,  0x54,  0xff,
 731     /* "\200" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 732     /* "\210" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 733     /* "\220" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 734     /* "\230" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 735     /* "\240" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 736     /* "\250" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 737     /* "\260" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 738     /* "\270" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 739     /* "\300" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 740     /* "\310" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 741     /* "\320" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 742     /* "\330" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 743     /* "\340" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 744     /* "\350" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 745     /* "\360" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 746     /* "\370" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 747 };
 748
 749 static const FcChar8 valueToChar[0x55] = {
 750     /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
 751     /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
 752     /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
 753     /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
 754     /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 755     /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
 756     /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
 757     /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
 758     /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
 759     /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
 760     /* 0x50 */ 'z', '{', '|', '}', '~',
 761 };
 762
 763 static FcChar8 *
 764 FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
 765 {
 766     int         i;
 767     FcChar32    v;
 768     FcChar32    c;
 769
 770     if (*string == ' ')
 771     {
 772         v = 0;
 773         string++;
 774     }
 775     else
 776     {
 777         v = 0;
 778         for (i = 0; i < 5; i++)
 779         {
 780             if (!(c = (FcChar32) (unsigned char) *string++))
 781                 return 0;
 782             c = charToValue[c];
 783             if (c == 0xff)
 784                 return 0;
 785             v = v * 85 + c;
 786         }
 787     }
 788     *value = v;
 789     return string;
 790 }
 791
 792 static FcBool
 793 FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
 794 {
 795     int     i;
 796     if (value == 0)
 797     {
 798         return FcStrBufChar (buf, ' ');
 799     }
 800     else
 801     {
 802         FcChar8 string[6];
 803         FcChar8 *s = string + 5;
 804         string[5] = '\0';
 805         for (i = 0; i < 5; i++)
 806         {
 807             *--s = valueToChar[value % 85];
 808             value /= 85;
 809         }
 810         for (i = 0; i < 5; i++)
 811             if (!FcStrBufChar (buf, *s++))
 812                 return FcFalse;
 813     }
 814     return FcTrue;
 815 }
 816
 817 typedef struct _FcCharLeafEnt FcCharLeafEnt;
 818
 819 struct _FcCharLeafEnt {
 820     FcCharLeafEnt   *next;
 821     FcChar32        hash;
 822     FcCharLeaf      leaf;
 823 };
 824
 825 #define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
 826
 827 static FcCharLeafEnt *
 828 FcCharLeafEntCreate (void)
 829 {
 830     static FcCharLeafEnt    *block;
 831     static int              remain;
 832
 833     if (!remain)
 834     {
 835         block = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
 836         if (!block)
 837             return 0;
 838         remain = FC_CHAR_LEAF_BLOCK;
 839     }
 840     remain--;
 841     return block++;
 842 }
 843
 844 #define FC_CHAR_LEAF_HASH_SIZE  257
 845
 846 static FcChar32
 847 FcCharLeafHash (FcCharLeaf *leaf)
 848 {
 849     FcChar32    hash = 0;
 850     int         i;
 851
 852     for (i = 0; i < 256/32; i++)
 853         hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
 854     return hash;
 855 }
 856
 857 static int      FcCharLeafTotal;
 858 static int      FcCharLeafUsed;
 859
 860 static FcCharLeaf *
 861 FcCharSetFreezeLeaf (FcCharLeaf *leaf)
 862 {
 863     static FcCharLeafEnt        *hashTable[FC_CHAR_LEAF_HASH_SIZE];
 864     FcChar32                    hash = FcCharLeafHash (leaf);
 865     FcCharLeafEnt               **bucket = &hashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
 866     FcCharLeafEnt               *ent;
 867
 868     FcCharLeafTotal++;
 869     for (ent = *bucket; ent; ent = ent->next)
 870     {
 871         if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
 872             return &ent->leaf;
 873     }
 874
 875     ent = FcCharLeafEntCreate();
 876     if (!ent)
 877         return 0;
 878     FcCharLeafUsed++;
 879     ent->leaf = *leaf;
 880     ent->hash = hash;
 881     ent->next = *bucket;
 882     *bucket = ent;
 883     return &ent->leaf;
 884 }
 885
 886 typedef struct _FcCharSetEnt FcCharSetEnt;
 887
 888 struct _FcCharSetEnt {
 889     FcCharSetEnt        *next;
 890     FcChar32            hash;
 891     FcCharSet           set;
 892 };
 893
 894 #define FC_CHAR_SET_HASH_SIZE    67
 895
 896 static FcChar32
 897 FcCharSetHash (FcCharSet *fcs)
 898 {
 899     FcChar32    hash = 0;
 900     FcChar32    *p;
 901     int         i;
 902
 903     /* hash in leaves */
 904     p = (FcChar32 *) fcs->leaves;
 905     for (i = 0; i < fcs->num * sizeof (FcCharLeaf *) / sizeof (FcChar32); i++)
 906         hash = ((hash << 1) | (hash >> 31)) ^ *p++;
 907     /* hash in numbers */
 908     for (i = 0; i < fcs->num; i++)
 909         hash = ((hash << 1) | (hash >> 31)) ^ fcs->numbers[i];
 910     return hash;
 911 }
 912
 913 static int      FcCharSetTotal;
 914 static int      FcCharSetUsed;
 915 static int      FcCharSetTotalEnts, FcCharSetUsedEnts;
 916
 917 static FcCharSet *
 918 FcCharSetFreezeBase (FcCharSet *fcs)
 919 {
 920     static FcCharSetEnt *hashTable[FC_CHAR_SET_HASH_SIZE];
 921     FcChar32            hash = FcCharSetHash (fcs);
 922     FcCharSetEnt        **bucket = &hashTable[hash % FC_CHAR_SET_HASH_SIZE];
 923     FcCharSetEnt        *ent;
 924
 925     FcCharSetTotal++;
 926     FcCharSetTotalEnts += fcs->num;
 927     for (ent = *bucket; ent; ent = ent->next)
 928     {
 929         if (ent->hash == hash &&
 930             ent->set.num == fcs->num &&
 931             !memcmp (ent->set.leaves, fcs->leaves,
 932                      fcs->num * sizeof (FcCharLeaf *)) &&
 933             !memcmp (ent->set.numbers, fcs->numbers,
 934                      fcs->num * sizeof (FcChar16)))
 935         {
 936             return &ent->set;
 937         }
 938     }
 939
 940     ent = malloc (sizeof (FcCharSetEnt) +
 941                   fcs->num * sizeof (FcCharLeaf *) +
 942                   fcs->num * sizeof (FcChar16));
 943     if (!ent)
 944         return 0;
 945     FcCharSetUsed++;
 946     FcCharSetUsedEnts += fcs->num;
 947
 948     ent->set.ref = 0;
 949     ent->set.constant = FcTrue;
 950     ent->set.num = fcs->num;
 951     if (fcs->num)
 952     {
 953         ent->set.leaves = (FcCharLeaf **) (ent + 1);
 954         ent->set.numbers = (FcChar16 *) (ent->set.leaves + fcs->num);
 955         memcpy (ent->set.leaves, fcs->leaves, fcs->num * sizeof (FcCharLeaf *));
 956         memcpy (ent->set.numbers, fcs->numbers, fcs->num * sizeof (FcChar16));
 957     }
 958     else
 959     {
 960         ent->set.leaves = 0;
 961         ent->set.numbers = 0;
 962     }
 963
 964     ent->hash = hash;
 965     ent->next = *bucket;
 966     *bucket = ent;
 967     return &ent->set;
 968 }
 969
 970 FcCharSet *
 971 FcCharSetFreeze (FcCharSet *fcs)
 972 {
 973     FcCharSet   *b;
 974     FcCharSet   *n = 0;
 975     FcCharLeaf  *l;
 976     int         i;
 977
 978     b = FcCharSetCreate ();
 979     if (!b)
 980         goto bail0;
 981     for (i = 0; i < fcs->num; i++)
 982     {
 983         l = FcCharSetFreezeLeaf (fcs->leaves[i]);
 984         if (!l)
 985             goto bail1;
 986         if (!FcCharSetInsertLeaf (b, fcs->numbers[i] << 8, l))
 987             goto bail1;
 988     }
 989     n = FcCharSetFreezeBase (b);
 990 bail1:
 991     if (b->leaves)
 992         free (b->leaves);
 993     if (b->numbers)
 994         free (b->numbers);
 995     free (b);
 996 bail0:
 997     return n;
 998 }
 999
1000 FcCharSet *
1001 FcNameParseCharSet (FcChar8 *string)
1002 {
1003     FcCharSet   *c, *n = 0;
1004     FcChar32    ucs4;
1005     FcCharLeaf  *leaf;
1006     FcCharLeaf  temp;
1007     FcChar32    bits;
1008     int         i;
1009
1010     c = FcCharSetCreate ();
1011     if (!c)
1012         goto bail0;
1013     while (*string)
1014     {
1015         string = FcCharSetParseValue (string, &ucs4);
1016         if (!string)
1017             goto bail1;
1018         bits = 0;
1019         for (i = 0; i < 256/32; i++)
1020         {
1021             string = FcCharSetParseValue (string, &temp.map[i]);
1022             if (!string)
1023                 goto bail1;
1024             bits |= temp.map[i];
1025         }
1026         if (bits)
1027         {
1028             leaf = FcCharSetFreezeLeaf (&temp);
1029             if (!leaf)
1030                 goto bail1;
1031             if (!FcCharSetInsertLeaf (c, ucs4, leaf))
1032                 goto bail1;
1033         }
1034     }
1035 #ifdef CHATTY
1036     printf ("          %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
1037     printf ("Leaves:   %8d %8d %8d %8d\n",
1038             FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
1039             FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
1040     printf ("Charsets: %8d %8d %8d %8d\n",
1041             FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
1042             FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
1043     printf ("Tables:   %8d %8d %8d %8d\n",
1044             FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1045             FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1046     printf ("Total:    %8s %8d %8s %8d\n",
1047             "",
1048             sizeof (FcCharLeaf) * FcCharLeafTotal +
1049             sizeof (FcCharSet) * FcCharSetTotal +
1050             FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1051             "",
1052             sizeof (FcCharLeaf) * FcCharLeafUsed +
1053             sizeof (FcCharSet) * FcCharSetUsed +
1054             FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1055 #endif
1056     n = FcCharSetFreezeBase (c);
1057 bail1:
1058     if (c->leaves)
1059         free (c->leaves);
1060     if (c->numbers)
1061         free (c->numbers);
1062     free (c);
1063 bail0:
1064     return n;
1065 }
1066
1067 FcBool
1068 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
1069 {
1070     FcCharSetIter   ci;
1071     int             i;
1072 #ifdef CHECK
1073     int             len = buf->len;
1074 #endif
1075
1076     for (FcCharSetIterStart (c, &ci);
1077          ci.leaf;
1078          FcCharSetIterNext (c, &ci))
1079     {
1080         if (!FcCharSetUnparseValue (buf, ci.ucs4))
1081             return FcFalse;
1082         for (i = 0; i < 256/32; i++)
1083             if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
1084                 return FcFalse;
1085     }
1086 #ifdef CHECK
1087     {
1088         FcCharSet       *check;
1089         FcChar32        missing;
1090         FcCharSetIter   ci, checki;
1091
1092         /* null terminate for parser */
1093         FcStrBufChar (buf, '\0');
1094         /* step back over null for life after test */
1095         buf->len--;
1096         check = FcNameParseCharSet (buf->buf + len);
1097         FcCharSetIterStart (c, &ci);
1098         FcCharSetIterStart (check, &checki);
1099         while (ci.leaf || checki.leaf)
1100         {
1101             if (ci.ucs4 < checki.ucs4)
1102             {
1103                 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
1104                 FcCharSetIterNext (c, &ci);
1105             }
1106             else if (checki.ucs4 < ci.ucs4)
1107             {
1108                 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
1109                 FcCharSetIterNext (check, &checki);
1110             }
1111             else
1112             {
1113                 int         i = 256/32;
1114                 FcChar32    *cm = ci.leaf->map;
1115                 FcChar32    *checkm = checki.leaf->map;
1116
1117                 for (i = 0; i < 256; i += 32)
1118                 {
1119                     if (*cm != *checkm)
1120                         printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
1121                                 ci.ucs4 + i, *cm, *checkm);
1122                     cm++;
1123                     checkm++;
1124                 }
1125                 FcCharSetIterNext (c, &ci);
1126                 FcCharSetIterNext (check, &checki);
1127             }
1128         }
1129         if ((missing = FcCharSetSubtractCount (c, check)))
1130             printf ("%d missing in reparsed result\n", missing);
1131         if ((missing = FcCharSetSubtractCount (check, c)))
1132             printf ("%d extra in reparsed result\n", missing);
1133         FcCharSetDestroy (check);
1134     }
1135 #endif
1136
1137     return FcTrue;
1138 }
1139
1140 /*
1141  * Figure out whether the available freetype has FT_Get_Next_Char
1142  */
1143
1144 #if FREETYPE_MAJOR > 2
1145 # define HAS_NEXT_CHAR
1146 #else
1147 # if FREETYPE_MAJOR == 2
1148 #  if FREETYPE_MINOR > 0
1149 #   define HAS_NEXT_CHAR
1150 #  else
1151 #   if FREETYPE_MINOR == 0
1152 #    if FREETYPE_PATCH >= 9
1153 #     define HAS_NEXT_CHAR
1154 #    endif
1155 #   endif
1156 #  endif
1157 # endif
1158 #endif
1159
1160 /*
1161  * For our purposes, this approximation is sufficient
1162  */
1163 #ifndef HAS_NEXT_CHAR
1164 #define FT_Get_First_Char(face, gi) ((*(gi) = 1), 1)
1165 #define FT_Get_Next_Char(face, ucs4, gi) ((ucs4) >= 0xffffff ? \
1166                                           (*(gi) = 0), 0 : \
1167                                           (*(gi) = 1), (ucs4) + 1)
1168 #warning "No FT_Get_Next_Char"
1169 #endif
1170
1171 typedef struct _FcCharEnt {
1172     FcChar16        bmp;
1173     unsigned char   encode;
1174 } FcCharEnt;
1175
1176 typedef struct _FcCharMap {
1177     const FcCharEnt *ent;
1178     int             nent;
1179 } FcCharMap;
1180
1181 typedef struct _FcFontDecode {
1182     FT_Encoding     encoding;
1183     const FcCharMap *map;
1184     FcChar32        max;
1185 } FcFontDecode;
1186
1187 static const FcCharEnt AppleRomanEnt[] = {
1188     { 0x0020, 0x20 }, /* SPACE */
1189     { 0x0021, 0x21 }, /* EXCLAMATION MARK */
1190     { 0x0022, 0x22 }, /* QUOTATION MARK */
1191     { 0x0023, 0x23 }, /* NUMBER SIGN */
1192     { 0x0024, 0x24 }, /* DOLLAR SIGN */
1193     { 0x0025, 0x25 }, /* PERCENT SIGN */
1194     { 0x0026, 0x26 }, /* AMPERSAND */
1195     { 0x0027, 0x27 }, /* APOSTROPHE */
1196     { 0x0028, 0x28 }, /* LEFT PARENTHESIS */
1197     { 0x0029, 0x29 }, /* RIGHT PARENTHESIS */
1198     { 0x002A, 0x2A }, /* ASTERISK */
1199     { 0x002B, 0x2B }, /* PLUS SIGN */
1200     { 0x002C, 0x2C }, /* COMMA */
1201     { 0x002D, 0x2D }, /* HYPHEN-MINUS */
1202     { 0x002E, 0x2E }, /* FULL STOP */
1203     { 0x002F, 0x2F }, /* SOLIDUS */
1204     { 0x0030, 0x30 }, /* DIGIT ZERO */
1205     { 0x0031, 0x31 }, /* DIGIT ONE */
1206     { 0x0032, 0x32 }, /* DIGIT TWO */
1207     { 0x0033, 0x33 }, /* DIGIT THREE */
1208     { 0x0034, 0x34 }, /* DIGIT FOUR */
1209     { 0x0035, 0x35 }, /* DIGIT FIVE */
1210     { 0x0036, 0x36 }, /* DIGIT SIX */
1211     { 0x0037, 0x37 }, /* DIGIT SEVEN */
1212     { 0x0038, 0x38 }, /* DIGIT EIGHT */
1213     { 0x0039, 0x39 }, /* DIGIT NINE */
1214     { 0x003A, 0x3A }, /* COLON */
1215     { 0x003B, 0x3B }, /* SEMICOLON */
1216     { 0x003C, 0x3C }, /* LESS-THAN SIGN */
1217     { 0x003D, 0x3D }, /* EQUALS SIGN */
1218     { 0x003E, 0x3E }, /* GREATER-THAN SIGN */
1219     { 0x003F, 0x3F }, /* QUESTION MARK */
1220     { 0x0040, 0x40 }, /* COMMERCIAL AT */
1221     { 0x0041, 0x41 }, /* LATIN CAPITAL LETTER A */
1222     { 0x0042, 0x42 }, /* LATIN CAPITAL LETTER B */
1223     { 0x0043, 0x43 }, /* LATIN CAPITAL LETTER C */
1224     { 0x0044, 0x44 }, /* LATIN CAPITAL LETTER D */
1225     { 0x0045, 0x45 }, /* LATIN CAPITAL LETTER E */
1226     { 0x0046, 0x46 }, /* LATIN CAPITAL LETTER F */
1227     { 0x0047, 0x47 }, /* LATIN CAPITAL LETTER G */
1228     { 0x0048, 0x48 }, /* LATIN CAPITAL LETTER H */
1229     { 0x0049, 0x49 }, /* LATIN CAPITAL LETTER I */
1230     { 0x004A, 0x4A }, /* LATIN CAPITAL LETTER J */
1231     { 0x004B, 0x4B }, /* LATIN CAPITAL LETTER K */
1232     { 0x004C, 0x4C }, /* LATIN CAPITAL LETTER L */
1233     { 0x004D, 0x4D }, /* LATIN CAPITAL LETTER M */
1234     { 0x004E, 0x4E }, /* LATIN CAPITAL LETTER N */
1235     { 0x004F, 0x4F }, /* LATIN CAPITAL LETTER O */
1236     { 0x0050, 0x50 }, /* LATIN CAPITAL LETTER P */
1237     { 0x0051, 0x51 }, /* LATIN CAPITAL LETTER Q */
1238     { 0x0052, 0x52 }, /* LATIN CAPITAL LETTER R */
1239     { 0x0053, 0x53 }, /* LATIN CAPITAL LETTER S */
1240     { 0x0054, 0x54 }, /* LATIN CAPITAL LETTER T */
1241     { 0x0055, 0x55 }, /* LATIN CAPITAL LETTER U */
1242     { 0x0056, 0x56 }, /* LATIN CAPITAL LETTER V */
1243     { 0x0057, 0x57 }, /* LATIN CAPITAL LETTER W */
1244     { 0x0058, 0x58 }, /* LATIN CAPITAL LETTER X */
1245     { 0x0059, 0x59 }, /* LATIN CAPITAL LETTER Y */
1246     { 0x005A, 0x5A }, /* LATIN CAPITAL LETTER Z */
1247     { 0x005B, 0x5B }, /* LEFT SQUARE BRACKET */
1248     { 0x005C, 0x5C }, /* REVERSE SOLIDUS */
1249     { 0x005D, 0x5D }, /* RIGHT SQUARE BRACKET */
1250     { 0x005E, 0x5E }, /* CIRCUMFLEX ACCENT */
1251     { 0x005F, 0x5F }, /* LOW LINE */
1252     { 0x0060, 0x60 }, /* GRAVE ACCENT */
1253     { 0x0061, 0x61 }, /* LATIN SMALL LETTER A */
1254     { 0x0062, 0x62 }, /* LATIN SMALL LETTER B */
1255     { 0x0063, 0x63 }, /* LATIN SMALL LETTER C */
1256     { 0x0064, 0x64 }, /* LATIN SMALL LETTER D */
1257     { 0x0065, 0x65 }, /* LATIN SMALL LETTER E */
1258     { 0x0066, 0x66 }, /* LATIN SMALL LETTER F */
1259     { 0x0067, 0x67 }, /* LATIN SMALL LETTER G */
1260     { 0x0068, 0x68 }, /* LATIN SMALL LETTER H */
1261     { 0x0069, 0x69 }, /* LATIN SMALL LETTER I */
1262     { 0x006A, 0x6A }, /* LATIN SMALL LETTER J */
1263     { 0x006B, 0x6B }, /* LATIN SMALL LETTER K */
1264     { 0x006C, 0x6C }, /* LATIN SMALL LETTER L */
1265     { 0x006D, 0x6D }, /* LATIN SMALL LETTER M */
1266     { 0x006E, 0x6E }, /* LATIN SMALL LETTER N */
1267     { 0x006F, 0x6F }, /* LATIN SMALL LETTER O */
1268     { 0x0070, 0x70 }, /* LATIN SMALL LETTER P */
1269     { 0x0071, 0x71 }, /* LATIN SMALL LETTER Q */
1270     { 0x0072, 0x72 }, /* LATIN SMALL LETTER R */
1271     { 0x0073, 0x73 }, /* LATIN SMALL LETTER S */
1272     { 0x0074, 0x74 }, /* LATIN SMALL LETTER T */
1273     { 0x0075, 0x75 }, /* LATIN SMALL LETTER U */
1274     { 0x0076, 0x76 }, /* LATIN SMALL LETTER V */
1275     { 0x0077, 0x77 }, /* LATIN SMALL LETTER W */
1276     { 0x0078, 0x78 }, /* LATIN SMALL LETTER X */
1277     { 0x0079, 0x79 }, /* LATIN SMALL LETTER Y */
1278     { 0x007A, 0x7A }, /* LATIN SMALL LETTER Z */
1279     { 0x007B, 0x7B }, /* LEFT CURLY BRACKET */
1280     { 0x007C, 0x7C }, /* VERTICAL LINE */
1281     { 0x007D, 0x7D }, /* RIGHT CURLY BRACKET */
1282     { 0x007E, 0x7E }, /* TILDE */
1283     { 0x00A0, 0xCA }, /* NO-BREAK SPACE */
1284     { 0x00A1, 0xC1 }, /* INVERTED EXCLAMATION MARK */
1285     { 0x00A2, 0xA2 }, /* CENT SIGN */
1286     { 0x00A3, 0xA3 }, /* POUND SIGN */
1287     { 0x00A5, 0xB4 }, /* YEN SIGN */
1288     { 0x00A7, 0xA4 }, /* SECTION SIGN */
1289     { 0x00A8, 0xAC }, /* DIAERESIS */
1290     { 0x00A9, 0xA9 }, /* COPYRIGHT SIGN */
1291     { 0x00AA, 0xBB }, /* FEMININE ORDINAL INDICATOR */
1292     { 0x00AB, 0xC7 }, /* LEFT-POINTING DOUBLE ANGLE QUOTATION MARK */
1293     { 0x00AC, 0xC2 }, /* NOT SIGN */
1294     { 0x00AE, 0xA8 }, /* REGISTERED SIGN */
1295     { 0x00AF, 0xF8 }, /* MACRON */
1296     { 0x00B0, 0xA1 }, /* DEGREE SIGN */
1297     { 0x00B1, 0xB1 }, /* PLUS-MINUS SIGN */
1298     { 0x00B4, 0xAB }, /* ACUTE ACCENT */
1299     { 0x00B5, 0xB5 }, /* MICRO SIGN */
1300     { 0x00B6, 0xA6 }, /* PILCROW SIGN */
1301     { 0x00B7, 0xE1 }, /* MIDDLE DOT */
1302     { 0x00B8, 0xFC }, /* CEDILLA */
1303     { 0x00BA, 0xBC }, /* MASCULINE ORDINAL INDICATOR */
1304     { 0x00BB, 0xC8 }, /* RIGHT-POINTING DOUBLE ANGLE QUOTATION MARK */
1305     { 0x00BF, 0xC0 }, /* INVERTED QUESTION MARK */
1306     { 0x00C0, 0xCB }, /* LATIN CAPITAL LETTER A WITH GRAVE */
1307     { 0x00C1, 0xE7 }, /* LATIN CAPITAL LETTER A WITH ACUTE */
1308     { 0x00C2, 0xE5 }, /* LATIN CAPITAL LETTER A WITH CIRCUMFLEX */
1309     { 0x00C3, 0xCC }, /* LATIN CAPITAL LETTER A WITH TILDE */
1310     { 0x00C4, 0x80 }, /* LATIN CAPITAL LETTER A WITH DIAERESIS */
1311     { 0x00C5, 0x81 }, /* LATIN CAPITAL LETTER A WITH RING ABOVE */
1312     { 0x00C6, 0xAE }, /* LATIN CAPITAL LETTER AE */
1313     { 0x00C7, 0x82 }, /* LATIN CAPITAL LETTER C WITH CEDILLA */
1314     { 0x00C8, 0xE9 }, /* LATIN CAPITAL LETTER E WITH GRAVE */
1315     { 0x00C9, 0x83 }, /* LATIN CAPITAL LETTER E WITH ACUTE */
1316     { 0x00CA, 0xE6 }, /* LATIN CAPITAL LETTER E WITH CIRCUMFLEX */
1317     { 0x00CB, 0xE8 }, /* LATIN CAPITAL LETTER E WITH DIAERESIS */
1318     { 0x00CC, 0xED }, /* LATIN CAPITAL LETTER I WITH GRAVE */
1319     { 0x00CD, 0xEA }, /* LATIN CAPITAL LETTER I WITH ACUTE */
1320     { 0x00CE, 0xEB }, /* LATIN CAPITAL LETTER I WITH CIRCUMFLEX */
1321     { 0x00CF, 0xEC }, /* LATIN CAPITAL LETTER I WITH DIAERESIS */
1322     { 0x00D1, 0x84 }, /* LATIN CAPITAL LETTER N WITH TILDE */
1323     { 0x00D2, 0xF1 }, /* LATIN CAPITAL LETTER O WITH GRAVE */
1324     { 0x00D3, 0xEE }, /* LATIN CAPITAL LETTER O WITH ACUTE */
1325     { 0x00D4, 0xEF }, /* LATIN CAPITAL LETTER O WITH CIRCUMFLEX */
1326     { 0x00D5, 0xCD }, /* LATIN CAPITAL LETTER O WITH TILDE */
1327     { 0x00D6, 0x85 }, /* LATIN CAPITAL LETTER O WITH DIAERESIS */
1328     { 0x00D8, 0xAF }, /* LATIN CAPITAL LETTER O WITH STROKE */
1329     { 0x00D9, 0xF4 }, /* LATIN CAPITAL LETTER U WITH GRAVE */
1330     { 0x00DA, 0xF2 }, /* LATIN CAPITAL LETTER U WITH ACUTE */
1331     { 0x00DB, 0xF3 }, /* LATIN CAPITAL LETTER U WITH CIRCUMFLEX */
1332     { 0x00DC, 0x86 }, /* LATIN CAPITAL LETTER U WITH DIAERESIS */
1333     { 0x00DF, 0xA7 }, /* LATIN SMALL LETTER SHARP S */
1334     { 0x00E0, 0x88 }, /* LATIN SMALL LETTER A WITH GRAVE */
1335     { 0x00E1, 0x87 }, /* LATIN SMALL LETTER A WITH ACUTE */
1336     { 0x00E2, 0x89 }, /* LATIN SMALL LETTER A WITH CIRCUMFLEX */
1337     { 0x00E3, 0x8B }, /* LATIN SMALL LETTER A WITH TILDE */
1338     { 0x00E4, 0x8A }, /* LATIN SMALL LETTER A WITH DIAERESIS */
1339     { 0x00E5, 0x8C }, /* LATIN SMALL LETTER A WITH RING ABOVE */
1340     { 0x00E6, 0xBE }, /* LATIN SMALL LETTER AE */
1341     { 0x00E7, 0x8D }, /* LATIN SMALL LETTER C WITH CEDILLA */
1342     { 0x00E8, 0x8F }, /* LATIN SMALL LETTER E WITH GRAVE */
1343     { 0x00E9, 0x8E }, /* LATIN SMALL LETTER E WITH ACUTE */
1344     { 0x00EA, 0x90 }, /* LATIN SMALL LETTER E WITH CIRCUMFLEX */
1345     { 0x00EB, 0x91 }, /* LATIN SMALL LETTER E WITH DIAERESIS */
1346     { 0x00EC, 0x93 }, /* LATIN SMALL LETTER I WITH GRAVE */
1347     { 0x00ED, 0x92 }, /* LATIN SMALL LETTER I WITH ACUTE */
1348     { 0x00EE, 0x94 }, /* LATIN SMALL LETTER I WITH CIRCUMFLEX */
1349     { 0x00EF, 0x95 }, /* LATIN SMALL LETTER I WITH DIAERESIS */
1350     { 0x00F1, 0x96 }, /* LATIN SMALL LETTER N WITH TILDE */
1351     { 0x00F2, 0x98 }, /* LATIN SMALL LETTER O WITH GRAVE */
1352     { 0x00F3, 0x97 }, /* LATIN SMALL LETTER O WITH ACUTE */
1353     { 0x00F4, 0x99 }, /* LATIN SMALL LETTER O WITH CIRCUMFLEX */
1354     { 0x00F5, 0x9B }, /* LATIN SMALL LETTER O WITH TILDE */
1355     { 0x00F6, 0x9A }, /* LATIN SMALL LETTER O WITH DIAERESIS */
1356     { 0x00F7, 0xD6 }, /* DIVISION SIGN */
1357     { 0x00F8, 0xBF }, /* LATIN SMALL LETTER O WITH STROKE */
1358     { 0x00F9, 0x9D }, /* LATIN SMALL LETTER U WITH GRAVE */
1359     { 0x00FA, 0x9C }, /* LATIN SMALL LETTER U WITH ACUTE */
1360     { 0x00FB, 0x9E }, /* LATIN SMALL LETTER U WITH CIRCUMFLEX */
1361     { 0x00FC, 0x9F }, /* LATIN SMALL LETTER U WITH DIAERESIS */
1362     { 0x00FF, 0xD8 }, /* LATIN SMALL LETTER Y WITH DIAERESIS */
1363     { 0x0131, 0xF5 }, /* LATIN SMALL LETTER DOTLESS I */
1364     { 0x0152, 0xCE }, /* LATIN CAPITAL LIGATURE OE */
1365     { 0x0153, 0xCF }, /* LATIN SMALL LIGATURE OE */
1366     { 0x0178, 0xD9 }, /* LATIN CAPITAL LETTER Y WITH DIAERESIS */
1367     { 0x0192, 0xC4 }, /* LATIN SMALL LETTER F WITH HOOK */
1368     { 0x02C6, 0xF6 }, /* MODIFIER LETTER CIRCUMFLEX ACCENT */
1369     { 0x02C7, 0xFF }, /* CARON */
1370     { 0x02D8, 0xF9 }, /* BREVE */
1371     { 0x02D9, 0xFA }, /* DOT ABOVE */
1372     { 0x02DA, 0xFB }, /* RING ABOVE */
1373     { 0x02DB, 0xFE }, /* OGONEK */
1374     { 0x02DC, 0xF7 }, /* SMALL TILDE */
1375     { 0x02DD, 0xFD }, /* DOUBLE ACUTE ACCENT */
1376     { 0x03A9, 0xBD }, /* GREEK CAPITAL LETTER OMEGA */
1377     { 0x03C0, 0xB9 }, /* GREEK SMALL LETTER PI */
1378     { 0x2013, 0xD0 }, /* EN DASH */
1379     { 0x2014, 0xD1 }, /* EM DASH */
1380     { 0x2018, 0xD4 }, /* LEFT SINGLE QUOTATION MARK */
1381     { 0x2019, 0xD5 }, /* RIGHT SINGLE QUOTATION MARK */
1382     { 0x201A, 0xE2 }, /* SINGLE LOW-9 QUOTATION MARK */
1383     { 0x201C, 0xD2 }, /* LEFT DOUBLE QUOTATION MARK */
1384     { 0x201D, 0xD3 }, /* RIGHT DOUBLE QUOTATION MARK */
1385     { 0x201E, 0xE3 }, /* DOUBLE LOW-9 QUOTATION MARK */
1386     { 0x2020, 0xA0 }, /* DAGGER */
1387     { 0x2021, 0xE0 }, /* DOUBLE DAGGER */
1388     { 0x2022, 0xA5 }, /* BULLET */
1389     { 0x2026, 0xC9 }, /* HORIZONTAL ELLIPSIS */
1390     { 0x2030, 0xE4 }, /* PER MILLE SIGN */
1391     { 0x2039, 0xDC }, /* SINGLE LEFT-POINTING ANGLE QUOTATION MARK */
1392     { 0x203A, 0xDD }, /* SINGLE RIGHT-POINTING ANGLE QUOTATION MARK */
1393     { 0x2044, 0xDA }, /* FRACTION SLASH */
1394     { 0x20AC, 0xDB }, /* EURO SIGN */
1395     { 0x2122, 0xAA }, /* TRADE MARK SIGN */
1396     { 0x2202, 0xB6 }, /* PARTIAL DIFFERENTIAL */
1397     { 0x2206, 0xC6 }, /* INCREMENT */
1398     { 0x220F, 0xB8 }, /* N-ARY PRODUCT */
1399     { 0x2211, 0xB7 }, /* N-ARY SUMMATION */
1400     { 0x221A, 0xC3 }, /* SQUARE ROOT */
1401     { 0x221E, 0xB0 }, /* INFINITY */
1402     { 0x222B, 0xBA }, /* INTEGRAL */
1403     { 0x2248, 0xC5 }, /* ALMOST EQUAL TO */
1404     { 0x2260, 0xAD }, /* NOT EQUAL TO */
1405     { 0x2264, 0xB2 }, /* LESS-THAN OR EQUAL TO */
1406     { 0x2265, 0xB3 }, /* GREATER-THAN OR EQUAL TO */
1407     { 0x25CA, 0xD7 }, /* LOZENGE */
1408     { 0xF8FF, 0xF0 }, /* Apple logo */
1409     { 0xFB01, 0xDE }, /* LATIN SMALL LIGATURE FI */
1410     { 0xFB02, 0xDF }, /* LATIN SMALL LIGATURE FL */
1411 };
1412
1413 static const FcCharMap AppleRoman = {
1414     AppleRomanEnt,
1415     sizeof (AppleRomanEnt) / sizeof (AppleRomanEnt[0])
1416 };
1417
1418 static const FcCharEnt AdobeSymbolEnt[] = {
1419     { 0x0020, 0x20 }, /* SPACE  # space */
1420     { 0x0021, 0x21 }, /* EXCLAMATION MARK       # exclam */
1421     { 0x0023, 0x23 }, /* NUMBER SIGN    # numbersign */
1422     { 0x0025, 0x25 }, /* PERCENT SIGN   # percent */
1423     { 0x0026, 0x26 }, /* AMPERSAND      # ampersand */
1424     { 0x0028, 0x28 }, /* LEFT PARENTHESIS       # parenleft */
1425     { 0x0029, 0x29 }, /* RIGHT PARENTHESIS      # parenright */
1426     { 0x002B, 0x2B }, /* PLUS SIGN      # plus */
1427     { 0x002C, 0x2C }, /* COMMA  # comma */
1428     { 0x002E, 0x2E }, /* FULL STOP      # period */
1429     { 0x002F, 0x2F }, /* SOLIDUS        # slash */
1430     { 0x0030, 0x30 }, /* DIGIT ZERO     # zero */
1431     { 0x0031, 0x31 }, /* DIGIT ONE      # one */
1432     { 0x0032, 0x32 }, /* DIGIT TWO      # two */
1433     { 0x0033, 0x33 }, /* DIGIT THREE    # three */
1434     { 0x0034, 0x34 }, /* DIGIT FOUR     # four */
1435     { 0x0035, 0x35 }, /* DIGIT FIVE     # five */
1436     { 0x0036, 0x36 }, /* DIGIT SIX      # six */
1437     { 0x0037, 0x37 }, /* DIGIT SEVEN    # seven */
1438     { 0x0038, 0x38 }, /* DIGIT EIGHT    # eight */
1439     { 0x0039, 0x39 }, /* DIGIT NINE     # nine */
1440     { 0x003A, 0x3A }, /* COLON  # colon */
1441     { 0x003B, 0x3B }, /* SEMICOLON      # semicolon */
1442     { 0x003C, 0x3C }, /* LESS-THAN SIGN # less */
1443     { 0x003D, 0x3D }, /* EQUALS SIGN    # equal */
1444     { 0x003E, 0x3E }, /* GREATER-THAN SIGN      # greater */
1445     { 0x003F, 0x3F }, /* QUESTION MARK  # question */
1446     { 0x005B, 0x5B }, /* LEFT SQUARE BRACKET    # bracketleft */
1447     { 0x005D, 0x5D }, /* RIGHT SQUARE BRACKET   # bracketright */
1448     { 0x005F, 0x5F }, /* LOW LINE       # underscore */
1449     { 0x007B, 0x7B }, /* LEFT CURLY BRACKET     # braceleft */
1450     { 0x007C, 0x7C }, /* VERTICAL LINE  # bar */
1451     { 0x007D, 0x7D }, /* RIGHT CURLY BRACKET    # braceright */
1452     { 0x00A0, 0x20 }, /* NO-BREAK SPACE # space */
1453     { 0x00AC, 0xD8 }, /* NOT SIGN       # logicalnot */
1454     { 0x00B0, 0xB0 }, /* DEGREE SIGN    # degree */
1455     { 0x00B1, 0xB1 }, /* PLUS-MINUS SIGN        # plusminus */
1456     { 0x00B5, 0x6D }, /* MICRO SIGN     # mu */
1457     { 0x00D7, 0xB4 }, /* MULTIPLICATION SIGN    # multiply */
1458     { 0x00F7, 0xB8 }, /* DIVISION SIGN  # divide */
1459     { 0x0192, 0xA6 }, /* LATIN SMALL LETTER F WITH HOOK # florin */
1460     { 0x0391, 0x41 }, /* GREEK CAPITAL LETTER ALPHA     # Alpha */
1461     { 0x0392, 0x42 }, /* GREEK CAPITAL LETTER BETA      # Beta */
1462     { 0x0393, 0x47 }, /* GREEK CAPITAL LETTER GAMMA     # Gamma */
1463     { 0x0394, 0x44 }, /* GREEK CAPITAL LETTER DELTA     # Delta */
1464     { 0x0395, 0x45 }, /* GREEK CAPITAL LETTER EPSILON   # Epsilon */
1465     { 0x0396, 0x5A }, /* GREEK CAPITAL LETTER ZETA      # Zeta */
1466     { 0x0397, 0x48 }, /* GREEK CAPITAL LETTER ETA       # Eta */
1467     { 0x0398, 0x51 }, /* GREEK CAPITAL LETTER THETA     # Theta */
1468     { 0x0399, 0x49 }, /* GREEK CAPITAL LETTER IOTA      # Iota */
1469     { 0x039A, 0x4B }, /* GREEK CAPITAL LETTER KAPPA     # Kappa */
1470     { 0x039B, 0x4C }, /* GREEK CAPITAL LETTER LAMDA     # Lambda */
1471     { 0x039C, 0x4D }, /* GREEK CAPITAL LETTER MU        # Mu */
1472     { 0x039D, 0x4E }, /* GREEK CAPITAL LETTER NU        # Nu */
1473     { 0x039E, 0x58 }, /* GREEK CAPITAL LETTER XI        # Xi */
1474     { 0x039F, 0x4F }, /* GREEK CAPITAL LETTER OMICRON   # Omicron */
1475     { 0x03A0, 0x50 }, /* GREEK CAPITAL LETTER PI        # Pi */
1476     { 0x03A1, 0x52 }, /* GREEK CAPITAL LETTER RHO       # Rho */
1477     { 0x03A3, 0x53 }, /* GREEK CAPITAL LETTER SIGMA     # Sigma */
1478     { 0x03A4, 0x54 }, /* GREEK CAPITAL LETTER TAU       # Tau */
1479     { 0x03A5, 0x55 }, /* GREEK CAPITAL LETTER UPSILON   # Upsilon */
1480     { 0x03A6, 0x46 }, /* GREEK CAPITAL LETTER PHI       # Phi */
1481     { 0x03A7, 0x43 }, /* GREEK CAPITAL LETTER CHI       # Chi */
1482     { 0x03A8, 0x59 }, /* GREEK CAPITAL LETTER PSI       # Psi */
1483     { 0x03A9, 0x57 }, /* GREEK CAPITAL LETTER OMEGA     # Omega */
1484     { 0x03B1, 0x61 }, /* GREEK SMALL LETTER ALPHA       # alpha */
1485     { 0x03B2, 0x62 }, /* GREEK SMALL LETTER BETA        # beta */
1486     { 0x03B3, 0x67 }, /* GREEK SMALL LETTER GAMMA       # gamma */
1487     { 0x03B4, 0x64 }, /* GREEK SMALL LETTER DELTA       # delta */
1488     { 0x03B5, 0x65 }, /* GREEK SMALL LETTER EPSILON     # epsilon */
1489     { 0x03B6, 0x7A }, /* GREEK SMALL LETTER ZETA        # zeta */
1490     { 0x03B7, 0x68 }, /* GREEK SMALL LETTER ETA # eta */
1491     { 0x03B8, 0x71 }, /* GREEK SMALL LETTER THETA       # theta */
1492     { 0x03B9, 0x69 }, /* GREEK SMALL LETTER IOTA        # iota */
1493     { 0x03BA, 0x6B }, /* GREEK SMALL LETTER KAPPA       # kappa */
1494     { 0x03BB, 0x6C }, /* GREEK SMALL LETTER LAMDA       # lambda */
1495     { 0x03BC, 0x6D }, /* GREEK SMALL LETTER MU  # mu */
1496     { 0x03BD, 0x6E }, /* GREEK SMALL LETTER NU  # nu */
1497     { 0x03BE, 0x78 }, /* GREEK SMALL LETTER XI  # xi */
1498     { 0x03BF, 0x6F }, /* GREEK SMALL LETTER OMICRON     # omicron */
1499     { 0x03C0, 0x70 }, /* GREEK SMALL LETTER PI  # pi */
1500     { 0x03C1, 0x72 }, /* GREEK SMALL LETTER RHO # rho */
1501     { 0x03C2, 0x56 }, /* GREEK SMALL LETTER FINAL SIGMA # sigma1 */
1502     { 0x03C3, 0x73 }, /* GREEK SMALL LETTER SIGMA       # sigma */
1503     { 0x03C4, 0x74 }, /* GREEK SMALL LETTER TAU # tau */
1504     { 0x03C5, 0x75 }, /* GREEK SMALL LETTER UPSILON     # upsilon */
1505     { 0x03C6, 0x66 }, /* GREEK SMALL LETTER PHI # phi */
1506     { 0x03C7, 0x63 }, /* GREEK SMALL LETTER CHI # chi */
1507     { 0x03C8, 0x79 }, /* GREEK SMALL LETTER PSI # psi */
1508     { 0x03C9, 0x77 }, /* GREEK SMALL LETTER OMEGA       # omega */
1509     { 0x03D1, 0x4A }, /* GREEK THETA SYMBOL     # theta1 */
1510     { 0x03D2, 0xA1 }, /* GREEK UPSILON WITH HOOK SYMBOL # Upsilon1 */
1511     { 0x03D5, 0x6A }, /* GREEK PHI SYMBOL       # phi1 */
1512     { 0x03D6, 0x76 }, /* GREEK PI SYMBOL        # omega1 */
1513     { 0x2022, 0xB7 }, /* BULLET # bullet */
1514     { 0x2026, 0xBC }, /* HORIZONTAL ELLIPSIS    # ellipsis */
1515     { 0x2032, 0xA2 }, /* PRIME  # minute */
1516     { 0x2033, 0xB2 }, /* DOUBLE PRIME   # second */
1517     { 0x2044, 0xA4 }, /* FRACTION SLASH # fraction */
1518     { 0x20AC, 0xA0 }, /* EURO SIGN      # Euro */
1519     { 0x2111, 0xC1 }, /* BLACK-LETTER CAPITAL I # Ifraktur */
1520     { 0x2118, 0xC3 }, /* SCRIPT CAPITAL P       # weierstrass */
1521     { 0x211C, 0xC2 }, /* BLACK-LETTER CAPITAL R # Rfraktur */
1522     { 0x2126, 0x57 }, /* OHM SIGN       # Omega */
1523     { 0x2135, 0xC0 }, /* ALEF SYMBOL    # aleph */
1524     { 0x2190, 0xAC }, /* LEFTWARDS ARROW        # arrowleft */
1525     { 0x2191, 0xAD }, /* UPWARDS ARROW  # arrowup */
1526     { 0x2192, 0xAE }, /* RIGHTWARDS ARROW       # arrowright */
1527     { 0x2193, 0xAF }, /* DOWNWARDS ARROW        # arrowdown */
1528     { 0x2194, 0xAB }, /* LEFT RIGHT ARROW       # arrowboth */
1529     { 0x21B5, 0xBF }, /* DOWNWARDS ARROW WITH CORNER LEFTWARDS  # carriagereturn */
1530     { 0x21D0, 0xDC }, /* LEFTWARDS DOUBLE ARROW # arrowdblleft */
1531     { 0x21D1, 0xDD }, /* UPWARDS DOUBLE ARROW   # arrowdblup */
1532     { 0x21D2, 0xDE }, /* RIGHTWARDS DOUBLE ARROW        # arrowdblright */
1533     { 0x21D3, 0xDF }, /* DOWNWARDS DOUBLE ARROW # arrowdbldown */
1534     { 0x21D4, 0xDB }, /* LEFT RIGHT DOUBLE ARROW        # arrowdblboth */
1535     { 0x2200, 0x22 }, /* FOR ALL        # universal */
1536     { 0x2202, 0xB6 }, /* PARTIAL DIFFERENTIAL   # partialdiff */
1537     { 0x2203, 0x24 }, /* THERE EXISTS   # existential */
1538     { 0x2205, 0xC6 }, /* EMPTY SET      # emptyset */
1539     { 0x2206, 0x44 }, /* INCREMENT      # Delta */
1540     { 0x2207, 0xD1 }, /* NABLA  # gradient */
1541     { 0x2208, 0xCE }, /* ELEMENT OF     # element */
1542     { 0x2209, 0xCF }, /* NOT AN ELEMENT OF      # notelement */
1543     { 0x220B, 0x27 }, /* CONTAINS AS MEMBER     # suchthat */
1544     { 0x220F, 0xD5 }, /* N-ARY PRODUCT  # product */
1545     { 0x2211, 0xE5 }, /* N-ARY SUMMATION        # summation */
1546     { 0x2212, 0x2D }, /* MINUS SIGN     # minus */
1547     { 0x2215, 0xA4 }, /* DIVISION SLASH # fraction */
1548     { 0x2217, 0x2A }, /* ASTERISK OPERATOR      # asteriskmath */
1549     { 0x221A, 0xD6 }, /* SQUARE ROOT    # radical */
1550     { 0x221D, 0xB5 }, /* PROPORTIONAL TO        # proportional */
1551     { 0x221E, 0xA5 }, /* INFINITY       # infinity */
1552     { 0x2220, 0xD0 }, /* ANGLE  # angle */
1553     { 0x2227, 0xD9 }, /* LOGICAL AND    # logicaland */
1554     { 0x2228, 0xDA }, /* LOGICAL OR     # logicalor */
1555     { 0x2229, 0xC7 }, /* INTERSECTION   # intersection */
1556     { 0x222A, 0xC8 }, /* UNION  # union */
1557     { 0x222B, 0xF2 }, /* INTEGRAL       # integral */
1558     { 0x2234, 0x5C }, /* THEREFORE      # therefore */
1559     { 0x223C, 0x7E }, /* TILDE OPERATOR # similar */
1560     { 0x2245, 0x40 }, /* APPROXIMATELY EQUAL TO # congruent */
1561     { 0x2248, 0xBB }, /* ALMOST EQUAL TO        # approxequal */
1562     { 0x2260, 0xB9 }, /* NOT EQUAL TO   # notequal */
1563     { 0x2261, 0xBA }, /* IDENTICAL TO   # equivalence */
1564     { 0x2264, 0xA3 }, /* LESS-THAN OR EQUAL TO  # lessequal */
1565     { 0x2265, 0xB3 }, /* GREATER-THAN OR EQUAL TO       # greaterequal */
1566     { 0x2282, 0xCC }, /* SUBSET OF      # propersubset */
1567     { 0x2283, 0xC9 }, /* SUPERSET OF    # propersuperset */
1568     { 0x2284, 0xCB }, /* NOT A SUBSET OF        # notsubset */
1569     { 0x2286, 0xCD }, /* SUBSET OF OR EQUAL TO  # reflexsubset */
1570     { 0x2287, 0xCA }, /* SUPERSET OF OR EQUAL TO        # reflexsuperset */
1571     { 0x2295, 0xC5 }, /* CIRCLED PLUS   # circleplus */
1572     { 0x2297, 0xC4 }, /* CIRCLED TIMES  # circlemultiply */
1573     { 0x22A5, 0x5E }, /* UP TACK        # perpendicular */
1574     { 0x22C5, 0xD7 }, /* DOT OPERATOR   # dotmath */
1575     { 0x2320, 0xF3 }, /* TOP HALF INTEGRAL      # integraltp */
1576     { 0x2321, 0xF5 }, /* BOTTOM HALF INTEGRAL   # integralbt */
1577     { 0x2329, 0xE1 }, /* LEFT-POINTING ANGLE BRACKET    # angleleft */
1578     { 0x232A, 0xF1 }, /* RIGHT-POINTING ANGLE BRACKET   # angleright */
1579     { 0x25CA, 0xE0 }, /* LOZENGE        # lozenge */
1580     { 0x2660, 0xAA }, /* BLACK SPADE SUIT       # spade */
1581     { 0x2663, 0xA7 }, /* BLACK CLUB SUIT        # club */
1582     { 0x2665, 0xA9 }, /* BLACK HEART SUIT       # heart */
1583     { 0x2666, 0xA8 }, /* BLACK DIAMOND SUIT     # diamond */
1584     { 0xF6D9, 0xD3 }, /* COPYRIGHT SIGN SERIF   # copyrightserif (CUS) */
1585     { 0xF6DA, 0xD2 }, /* REGISTERED SIGN SERIF  # registerserif (CUS) */
1586     { 0xF6DB, 0xD4 }, /* TRADE MARK SIGN SERIF  # trademarkserif (CUS) */
1587     { 0xF8E5, 0x60 }, /* RADICAL EXTENDER       # radicalex (CUS) */
1588     { 0xF8E6, 0xBD }, /* VERTICAL ARROW EXTENDER        # arrowvertex (CUS) */
1589     { 0xF8E7, 0xBE }, /* HORIZONTAL ARROW EXTENDER      # arrowhorizex (CUS) */
1590     { 0xF8E8, 0xE2 }, /* REGISTERED SIGN SANS SERIF     # registersans (CUS) */
1591     { 0xF8E9, 0xE3 }, /* COPYRIGHT SIGN SANS SERIF      # copyrightsans (CUS) */
1592     { 0xF8EA, 0xE4 }, /* TRADE MARK SIGN SANS SERIF     # trademarksans (CUS) */
1593     { 0xF8EB, 0xE6 }, /* LEFT PAREN TOP # parenlefttp (CUS) */
1594     { 0xF8EC, 0xE7 }, /* LEFT PAREN EXTENDER    # parenleftex (CUS) */
1595     { 0xF8ED, 0xE8 }, /* LEFT PAREN BOTTOM      # parenleftbt (CUS) */
1596     { 0xF8EE, 0xE9 }, /* LEFT SQUARE BRACKET TOP        # bracketlefttp (CUS) */
1597     { 0xF8EF, 0xEA }, /* LEFT SQUARE BRACKET EXTENDER   # bracketleftex (CUS) */
1598     { 0xF8F0, 0xEB }, /* LEFT SQUARE BRACKET BOTTOM     # bracketleftbt (CUS) */
1599     { 0xF8F1, 0xEC }, /* LEFT CURLY BRACKET TOP # bracelefttp (CUS) */
1600     { 0xF8F2, 0xED }, /* LEFT CURLY BRACKET MID # braceleftmid (CUS) */
1601     { 0xF8F3, 0xEE }, /* LEFT CURLY BRACKET BOTTOM      # braceleftbt (CUS) */
1602     { 0xF8F4, 0xEF }, /* CURLY BRACKET EXTENDER # braceex (CUS) */
1603     { 0xF8F5, 0xF4 }, /* INTEGRAL EXTENDER      # integralex (CUS) */
1604     { 0xF8F6, 0xF6 }, /* RIGHT PAREN TOP        # parenrighttp (CUS) */
1605     { 0xF8F7, 0xF7 }, /* RIGHT PAREN EXTENDER   # parenrightex (CUS) */
1606     { 0xF8F8, 0xF8 }, /* RIGHT PAREN BOTTOM     # parenrightbt (CUS) */
1607     { 0xF8F9, 0xF9 }, /* RIGHT SQUARE BRACKET TOP       # bracketrighttp (CUS) */
1608     { 0xF8FA, 0xFA }, /* RIGHT SQUARE BRACKET EXTENDER  # bracketrightex (CUS) */
1609     { 0xF8FB, 0xFB }, /* RIGHT SQUARE BRACKET BOTTOM    # bracketrightbt (CUS) */
1610     { 0xF8FC, 0xFC }, /* RIGHT CURLY BRACKET TOP        # bracerighttp (CUS) */
1611     { 0xF8FD, 0xFD }, /* RIGHT CURLY BRACKET MID        # bracerightmid (CUS) */
1612     { 0xF8FE, 0xFE }, /* RIGHT CURLY BRACKET BOTTOM     # bracerightbt (CUS) */
1613 };
1614
1615 static const FcCharMap AdobeSymbol = {
1616     AdobeSymbolEnt,
1617     sizeof (AdobeSymbolEnt) / sizeof (AdobeSymbolEnt[0]),
1618 };
1619
1620 static const FcFontDecode fcFontDecoders[] = {
1621     { ft_encoding_unicode,      0,              (1 << 21) - 1 },
1622     { ft_encoding_symbol,       &AdobeSymbol,   (1 << 16) - 1 },
1623     { ft_encoding_apple_roman,  &AppleRoman,    (1 << 16) - 1 },
1624 };
1625
1626 #define NUM_DECODE  (sizeof (fcFontDecoders) / sizeof (fcFontDecoders[0]))
1627
1628 static FT_ULong
1629 FcFreeTypeMapChar (FcChar32 ucs4, const FcCharMap *map)
1630 {
1631     int         low, high, mid;
1632     FcChar16    bmp;
1633
1634     low = 0;
1635     high = map->nent - 1;
1636     if (ucs4 < map->ent[low].bmp || map->ent[high].bmp < ucs4)
1637         return ~0;
1638     while (low <= high)
1639     {
1640         mid = (high + low) >> 1;
1641         bmp = map->ent[mid].bmp;
1642         if (ucs4 == bmp)
1643             return (FT_ULong) map->ent[mid].encode;
1644         if (ucs4 < bmp)
1645             high = mid - 1;
1646         else
1647             low = mid + 1;
1648     }
1649     return ~0;
1650 }
1651
1652 /*
1653  * Map a UCS4 glyph to a glyph index.  Use all available encoding
1654  * tables to try and find one that works.  This information is expected
1655  * to be cached by higher levels, so performance isn't critical
1656  */
1657
1658 FT_UInt
1659 FcFreeTypeCharIndex (FT_Face face, FcChar32 ucs4)
1660 {
1661     int             initial, offset, decode;
1662     FT_UInt         glyphindex;
1663     FT_ULong        charcode;
1664
1665     initial = 0;
1666     /*
1667      * Find the current encoding
1668      */
1669     if (face->charmap)
1670     {
1671         for (; initial < NUM_DECODE; initial++)
1672             if (fcFontDecoders[initial].encoding == face->charmap->encoding)
1673                 break;
1674         if (initial == NUM_DECODE)
1675             initial = 0;
1676     }
1677     /*
1678      * Check each encoding for the glyph, starting with the current one
1679      */
1680     for (offset = 0; offset < NUM_DECODE; offset++)
1681     {
1682         decode = (initial + offset) % NUM_DECODE;
1683         if (!face->charmap || face->charmap->encoding != fcFontDecoders[decode].encoding)
1684             if (FT_Select_Charmap (face, fcFontDecoders[decode].encoding) != 0)
1685                 continue;
1686         if (fcFontDecoders[decode].map)
1687         {
1688             charcode = FcFreeTypeMapChar (ucs4, fcFontDecoders[decode].map);
1689             if (charcode == ~0)
1690                 continue;
1691         }
1692         else
1693             charcode = (FT_ULong) ucs4;
1694         glyphindex = FT_Get_Char_Index (face, charcode);
1695         if (glyphindex)
1696             return glyphindex;
1697     }
1698     return 0;
1699 }
1700
1701 static FcBool
1702 FcFreeTypeCheckGlyph (FT_Face face, FcChar32 ucs4,
1703                       FT_UInt glyph, FcBlanks *blanks)
1704 {
1705     FT_Int          load_flags = FT_LOAD_NO_SCALE | FT_LOAD_NO_HINTING;
1706     FT_GlyphSlot    slot;
1707
1708     /*
1709      * When using scalable fonts, only report those glyphs
1710      * which can be scaled; otherwise those fonts will
1711      * only be available at some sizes, and never when
1712      * transformed.  Avoid this by simply reporting bitmap-only
1713      * glyphs as missing
1714      */
1715     if (face->face_flags & FT_FACE_FLAG_SCALABLE)
1716         load_flags |= FT_LOAD_NO_BITMAP;
1717
1718     if (FT_Load_Glyph (face, glyph, load_flags))
1719         return FcFalse;
1720
1721     slot = face->glyph;
1722     if (!glyph)
1723         return FcFalse;
1724
1725     switch (slot->format) {
1726     case ft_glyph_format_bitmap:
1727         /*
1728          * Bitmaps are assumed to be reasonable; if
1729          * this proves to be a rash assumption, this
1730          * code can be easily modified
1731          */
1732         return FcTrue;
1733     case ft_glyph_format_outline:
1734         /*
1735          * Glyphs with contours are always OK
1736          */
1737         if (slot->outline.n_contours != 0)
1738             return FcTrue;
1739         /*
1740          * Glyphs with no contours are only OK if
1741          * they're members of the Blanks set specified
1742          * in the configuration.  If blanks isn't set,
1743          * then allow any glyph to be blank
1744          */
1745         if (!blanks || FcBlanksIsMember (blanks, ucs4))
1746             return FcTrue;
1747         /* fall through ... */
1748     default:
1749         break;
1750     }
1751     return FcFalse;
1752 }
1753
1754 FcCharSet *
1755 FcFreeTypeCharSet (FT_Face face, FcBlanks *blanks)
1756 {
1757     FcChar32        page, off, max, ucs4;
1758 #ifdef CHECK
1759     FcChar32        font_max = 0;
1760 #endif
1761     FcCharSet       *fcs;
1762     FcCharLeaf      *leaf;
1763     const FcCharMap *map;
1764     int             o;
1765     int             i;
1766     FT_UInt         glyph;
1767
1768     fcs = FcCharSetCreate ();
1769     if (!fcs)
1770         goto bail0;
1771
1772     for (o = 0; o < NUM_DECODE; o++)
1773     {
1774         if (FT_Select_Charmap (face, fcFontDecoders[o].encoding) != 0)
1775             continue;
1776         map = fcFontDecoders[o].map;
1777         if (map)
1778         {
1779             /*
1780              * Non-Unicode tables are easy; there's a list of all possible
1781              * characters
1782              */
1783             for (i = 0; i < map->nent; i++)
1784             {
1785                 ucs4 = map->ent[i].bmp;
1786                 glyph = FT_Get_Char_Index (face, map->ent[i].encode);
1787                 if (glyph && FcFreeTypeCheckGlyph (face, ucs4, glyph, blanks))
1788                 {
1789                     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
1790                     if (!leaf)
1791                         goto bail1;
1792                     leaf->map[(ucs4 & 0xff) >> 5] |= (1 << (ucs4 & 0x1f));
1793 #ifdef CHECK
1794                     if (ucs4 > font_max)
1795                         font_max = ucs4;
1796 #endif
1797                 }
1798             }
1799         }
1800         else
1801         {
1802             FT_UInt gindex;
1803
1804             max = fcFontDecoders[o].max;
1805             /*
1806              * Find the first encoded character in the font
1807              */
1808             if (FT_Get_Char_Index (face, 0))
1809             {
1810                 ucs4 = 0;
1811                 gindex = 1;
1812             }
1813             else
1814             {
1815                 ucs4 = FT_Get_Next_Char (face, 0, &gindex);
1816                 if (!ucs4)
1817                     gindex = 0;
1818             }
1819
1820             while (gindex)
1821             {
1822                 page = ucs4 >> 8;
1823                 leaf = 0;
1824                 while ((ucs4 >> 8) == page)
1825                 {
1826                     glyph = FT_Get_Char_Index (face, ucs4);
1827                     if (glyph && FcFreeTypeCheckGlyph (face, ucs4,
1828                                                        glyph, blanks))
1829                     {
1830                         if (!leaf)
1831                         {
1832                             leaf = FcCharSetFindLeafCreate (fcs, ucs4);
1833                             if (!leaf)
1834                                 goto bail1;
1835                         }
1836                         off = ucs4 & 0xff;
1837                         leaf->map[off >> 5] |= (1 << (off & 0x1f));
1838 #ifdef CHECK
1839                         if (ucs4 > font_max)
1840                             font_max = ucs4;
1841 #endif
1842                     }
1843                     ucs4++;
1844                 }
1845                 ucs4 = FT_Get_Next_Char (face, ucs4 - 1, &gindex);
1846                 if (!ucs4)
1847                     gindex = 0;
1848             }
1849 #ifdef CHECK
1850             for (ucs4 = 0; ucs4 < 0x10000; ucs4++)
1851             {
1852                 FcBool      FT_Has, FC_Has;
1853
1854                 FT_Has = FT_Get_Char_Index (face, ucs4) != 0;
1855                 FC_Has = FcCharSetHasChar (fcs, ucs4);
1856                 if (FT_Has != FC_Has)
1857                 {
1858                     printf ("0x%08x FT says %d FC says %d\n", ucs4, FT_Has, FC_Has);
1859                 }
1860             }
1861 #endif
1862         }
1863     }
1864 #ifdef CHECK
1865     printf ("%d glyphs %d encoded\n", (int) face->num_glyphs, FcCharSetCount (fcs));
1866     for (ucs4 = 0; ucs4 <= font_max; ucs4++)
1867     {
1868         FcBool  has_char = FcFreeTypeCharIndex (face, ucs4) != 0;
1869         FcBool  has_bit = FcCharSetHasChar (fcs, ucs4);
1870
1871         if (has_char && !has_bit)
1872             printf ("Bitmap missing char 0x%x\n", ucs4);
1873         else if (!has_char && has_bit)
1874             printf ("Bitmap extra char 0x%x\n", ucs4);
1875     }
1876 #endif
1877     return fcs;
1878 bail1:
1879     FcCharSetDestroy (fcs);
1880 bail0:
1881     return 0;
1882 }
1883