src/fccharset.c

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