src/fccharset.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fccharset.c,v 1.18 2002/08/22 07:36:44 keithp Exp $
   3  *
   4  * Copyright © 2001 Keith Packard
   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 static FcCharSet ** charsets = 0;
  33 static FcChar16 ** numbers = 0;
  34 static int charset_bank_count = 0, charset_ptr, charset_count;
  35 static int charset_numbers_ptr, charset_numbers_count;
  36 static FcCharLeaf ** leaves = 0;
  37 static int charset_leaf_ptr, charset_leaf_count;
  38 static int ** leaf_idx = 0;
  39 static int charset_leaf_idx_ptr, charset_leaf_idx_count;
  40
  41 extern const FcChar16 *langBankNumbers;
  42 extern const FcCharLeaf *langBankLeaves;
  43 extern const int *langBankLeafIdx;
  44
  45 static FcBool
  46 FcCharSetEnsureBank (int bi);
  47
  48 void
  49 FcLangCharSetPopulate (void)
  50 {
  51     int bi = FcCacheBankToIndex (FC_BANK_LANGS);
  52     FcCharSetEnsureBank (bi);
  53     charsets[bi] = 0;
  54     numbers[bi] = (FcChar16 *)&langBankNumbers;
  55     leaves[bi] = (FcCharLeaf *)&langBankLeaves;
  56     leaf_idx[bi] = (int *)&langBankLeafIdx;
  57 }
  58
  59 FcCharSet *
  60 FcCharSetCreate (void)
  61 {
  62     FcCharSet   *fcs;
  63
  64     fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
  65     if (!fcs)
  66         return 0;
  67     FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
  68     fcs->ref = 1;
  69     fcs->num = 0;
  70     fcs->bank = FC_BANK_DYNAMIC;
  71     fcs->u.dyn.leaves = 0;
  72     fcs->u.dyn.numbers = 0;
  73     return fcs;
  74 }
  75
  76 FcCharSet *
  77 FcCharSetNew (void);
  78
  79 FcCharSet *
  80 FcCharSetNew (void)
  81 {
  82     return FcCharSetCreate ();
  83 }
  84
  85 void
  86 FcCharSetDestroy (FcCharSet *fcs)
  87 {
  88     int i;
  89     if (fcs->ref == FC_REF_CONSTANT)
  90         return;
  91     if (--fcs->ref > 0)
  92         return;
  93     if (fcs->bank == FC_BANK_DYNAMIC)
  94     {
  95         for (i = 0; i < fcs->num; i++)
  96         {
  97             FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
  98             free (fcs->u.dyn.leaves[i]);
  99         }
 100         if (fcs->u.dyn.leaves)
 101         {
 102             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
 103             free (fcs->u.dyn.leaves);
 104         }
 105         if (fcs->u.dyn.numbers)
 106         {
 107             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 108             free (fcs->u.dyn.numbers);
 109         }
 110     }
 111     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
 112     free (fcs);
 113 }
 114
 115 /*
 116  * Locate the leaf containing the specified char, return
 117  * its index if it exists, otherwise return negative of
 118  * the (position + 1) where it should be inserted
 119  */
 120
 121 static int
 122 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
 123 {
 124     FcChar16            *numbers = FcCharSetGetNumbers(fcs);
 125     FcChar16            page;
 126     int                 low = 0;
 127     int                 high = fcs->num - 1;
 128
 129     if (!numbers)
 130         return -1;
 131     ucs4 >>= 8;
 132     while (low <= high)
 133     {
 134         int mid = (low + high) >> 1;
 135         page = numbers[mid];
 136         if (page == ucs4)
 137             return mid;
 138         if (page < ucs4)
 139             low = mid + 1;
 140         else
 141             high = mid - 1;
 142     }
 143     if (high < 0 || (high < fcs->num && numbers[high] < ucs4))
 144         high++;
 145     return -(high + 1);
 146 }
 147
 148 static FcCharLeaf *
 149 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 150 {
 151     int pos = FcCharSetFindLeafPos (fcs, ucs4);
 152     if (pos >= 0)
 153         return FcCharSetGetLeaf(fcs, pos);
 154     return 0;
 155 }
 156
 157 static FcBool
 158 FcCharSetPutLeaf (FcCharSet     *fcs,
 159                   FcChar32      ucs4,
 160                   FcCharLeaf    *leaf,
 161                   int           pos)
 162 {
 163     FcCharLeaf  **leaves;
 164     FcChar16    *numbers;
 165
 166     ucs4 >>= 8;
 167     if (ucs4 >= 0x10000)
 168         return FcFalse;
 169     if (fcs->bank != FC_BANK_DYNAMIC)
 170     {
 171         int i;
 172
 173         leaves = malloc ((fcs->num + 1) * sizeof (FcCharLeaf *));
 174         if (!leaves)
 175             return FcFalse;
 176         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
 177         numbers = malloc ((fcs->num + 1) * sizeof (FcChar16));
 178         if (!numbers)
 179             return FcFalse;
 180         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
 181
 182         for (i = 0; i < fcs->num; i++)
 183             leaves[i] = FcCharSetGetLeaf(fcs, i);
 184         memcpy (numbers, FcCharSetGetNumbers(fcs),
 185                 fcs->num * sizeof (FcChar16));
 186     }
 187     else
 188     {
 189         if (!fcs->u.dyn.leaves)
 190             leaves = malloc (sizeof (FcCharLeaf *));
 191         else
 192             leaves = realloc (fcs->u.dyn.leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
 193         if (!leaves)
 194             return FcFalse;
 195         if (fcs->num)
 196             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
 197         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcCharLeaf *));
 198         fcs->u.dyn.leaves = leaves;
 199         if (!fcs->u.dyn.numbers)
 200             numbers = malloc (sizeof (FcChar16));
 201         else
 202             numbers = realloc (fcs->u.dyn.numbers, (fcs->num + 1) * sizeof (FcChar16));
 203         if (!numbers)
 204             return FcFalse;
 205         if (fcs->num)
 206             FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
 207         FcMemAlloc (FC_MEM_CHARSET, (fcs->num + 1) * sizeof (FcChar16));
 208         fcs->u.dyn.numbers = numbers;
 209     }
 210
 211     memmove (fcs->u.dyn.leaves + pos + 1, fcs->u.dyn.leaves + pos,
 212              (fcs->num - pos) * sizeof (FcCharLeaf *));
 213     memmove (fcs->u.dyn.numbers + pos + 1, fcs->u.dyn.numbers + pos,
 214              (fcs->num - pos) * sizeof (FcChar16));
 215     fcs->u.dyn.numbers[pos] = (FcChar16) ucs4;
 216     fcs->u.dyn.leaves[pos] = leaf;
 217     fcs->num++;
 218     return FcTrue;
 219 }
 220
 221 /*
 222  * Locate the leaf containing the specified char, creating it
 223  * if desired
 224  */
 225
 226 FcCharLeaf *
 227 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 228 {
 229     int                 pos;
 230     FcCharLeaf          *leaf;
 231
 232     pos = FcCharSetFindLeafPos (fcs, ucs4);
 233     if (pos >= 0)
 234         return FcCharSetGetLeaf(fcs, pos);
 235
 236     leaf = calloc (1, sizeof (FcCharLeaf));
 237     if (!leaf)
 238         return 0;
 239
 240     pos = -pos - 1;
 241     if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
 242     {
 243         free (leaf);
 244         return 0;
 245     }
 246     FcMemAlloc (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 247     return leaf;
 248 }
 249
 250 static FcBool
 251 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
 252 {
 253     int             pos;
 254
 255     pos = FcCharSetFindLeafPos (fcs, ucs4);
 256     if (pos >= 0)
 257     {
 258         FcMemFree (FC_MEM_CHARLEAF, sizeof (FcCharLeaf));
 259         if (fcs->bank == FC_BANK_DYNAMIC)
 260         {
 261             free (fcs->u.dyn.leaves[pos]);
 262             fcs->u.dyn.leaves[pos] = leaf;
 263         }
 264         else
 265         {
 266             leaves[fcs->bank][leaf_idx[fcs->bank][fcs->u.stat.leafidx_offset]+pos] = *leaf;
 267         }
 268         return FcTrue;
 269     }
 270     pos = -pos - 1;
 271     return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
 272 }
 273
 274 FcBool
 275 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 276 {
 277     FcCharLeaf  *leaf;
 278     FcChar32    *b;
 279
 280     if (fcs->ref == FC_REF_CONSTANT)
 281         return FcFalse;
 282     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
 283     if (!leaf)
 284         return FcFalse;
 285     b = &leaf->map[(ucs4 & 0xff) >> 5];
 286     *b |= (1 << (ucs4 & 0x1f));
 287     return FcTrue;
 288 }
 289
 290 /*
 291  * An iterator for the leaves of a charset
 292  */
 293
 294 typedef struct _fcCharSetIter {
 295     FcCharLeaf      *leaf;
 296     FcChar32        ucs4;
 297     int             pos;
 298 } FcCharSetIter;
 299
 300 /*
 301  * Set iter->leaf to the leaf containing iter->ucs4 or higher
 302  */
 303
 304 static void
 305 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 306 {
 307     int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
 308
 309     if (pos < 0)
 310     {
 311         pos = -pos - 1;
 312         if (pos == fcs->num)
 313         {
 314             iter->ucs4 = ~0;
 315             iter->leaf = 0;
 316             return;
 317         }
 318         iter->ucs4 = (FcChar32) FcCharSetGetNumbers(fcs)[pos] << 8;
 319     }
 320     iter->leaf = FcCharSetGetLeaf(fcs, pos);
 321     iter->pos = pos;
 322 #ifdef CHATTY
 323     printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
 324 #endif
 325 }
 326
 327 static void
 328 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 329 {
 330     int pos = iter->pos + 1;
 331     if (pos >= fcs->num)
 332     {
 333         iter->ucs4 = ~0;
 334         iter->leaf = 0;
 335     }
 336     else
 337     {
 338         iter->ucs4 = (FcChar32) FcCharSetGetNumbers(fcs)[pos] << 8;
 339         iter->leaf = FcCharSetGetLeaf(fcs, pos);
 340         iter->pos = pos;
 341     }
 342 }
 343
 344 #ifdef CHATTY
 345 static void
 346 FcCharSetDump (const FcCharSet *fcs)
 347 {
 348     int         pos;
 349
 350     printf ("fcs %08x:\n", (FcChar32) fcs);
 351     for (pos = 0; pos < fcs->num; pos++)
 352     {
 353         FcCharLeaf      *leaf = fcs->leaves[pos];
 354         FcChar32        ucs4 = (FcChar32) fcs->numbers[pos] << 8;
 355
 356         printf ("    %08x: %08x\n", ucs4, (FcChar32) leaf);
 357     }
 358 }
 359 #endif
 360
 361 static void
 362 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 363 {
 364 #ifdef CHATTY
 365     FcCharSetDump (fcs);
 366 #endif
 367     iter->ucs4 = 0;
 368     iter->pos = 0;
 369     FcCharSetIterSet (fcs, iter);
 370 }
 371
 372 FcCharSet *
 373 FcCharSetCopy (FcCharSet *src)
 374 {
 375     if (src->ref != FC_REF_CONSTANT)
 376         src->ref++;
 377     return src;
 378 }
 379
 380 FcBool
 381 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
 382 {
 383     FcCharSetIter   ai, bi;
 384     int             i;
 385
 386     if (a == b)
 387         return FcTrue;
 388     for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
 389          ai.leaf && bi.leaf;
 390          FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
 391     {
 392         if (ai.ucs4 != bi.ucs4)
 393             return FcFalse;
 394         for (i = 0; i < 256/32; i++)
 395             if (ai.leaf->map[i] != bi.leaf->map[i])
 396                 return FcFalse;
 397     }
 398     return ai.leaf == bi.leaf;
 399 }
 400
 401 static FcBool
 402 FcCharSetAddLeaf (FcCharSet     *fcs,
 403                   FcChar32      ucs4,
 404                   FcCharLeaf    *leaf)
 405 {
 406     FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
 407     if (!new)
 408         return FcFalse;
 409     *new = *leaf;
 410     return FcTrue;
 411 }
 412
 413 static FcCharSet *
 414 FcCharSetOperate (const FcCharSet   *a,
 415                   const FcCharSet   *b,
 416                   FcBool            (*overlap) (FcCharLeaf          *result,
 417                                                 const FcCharLeaf    *al,
 418                                                 const FcCharLeaf    *bl),
 419                   FcBool        aonly,
 420                   FcBool        bonly)
 421 {
 422     FcCharSet       *fcs;
 423     FcCharSetIter   ai, bi;
 424
 425     fcs = FcCharSetCreate ();
 426     if (!fcs)
 427         goto bail0;
 428     FcCharSetIterStart (a, &ai);
 429     FcCharSetIterStart (b, &bi);
 430     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
 431     {
 432         if (ai.ucs4 < bi.ucs4)
 433         {
 434             if (aonly)
 435             {
 436                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
 437                     goto bail1;
 438                 FcCharSetIterNext (a, &ai);
 439             }
 440             else
 441             {
 442                 ai.ucs4 = bi.ucs4;
 443                 FcCharSetIterSet (a, &ai);
 444             }
 445         }
 446         else if (bi.ucs4 < ai.ucs4 )
 447         {
 448             if (bonly)
 449             {
 450                 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
 451                     goto bail1;
 452                 FcCharSetIterNext (b, &bi);
 453             }
 454             else
 455             {
 456                 bi.ucs4 = ai.ucs4;
 457                 FcCharSetIterSet (b, &bi);
 458             }
 459         }
 460         else
 461         {
 462             FcCharLeaf  leaf;
 463
 464             if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 465             {
 466                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
 467                     goto bail1;
 468             }
 469             FcCharSetIterNext (a, &ai);
 470             FcCharSetIterNext (b, &bi);
 471         }
 472     }
 473     return fcs;
 474 bail1:
 475     FcCharSetDestroy (fcs);
 476 bail0:
 477     return 0;
 478 }
 479
 480 static FcBool
 481 FcCharSetIntersectLeaf (FcCharLeaf *result,
 482                         const FcCharLeaf *al,
 483                         const FcCharLeaf *bl)
 484 {
 485     int     i;
 486     FcBool  nonempty = FcFalse;
 487
 488     for (i = 0; i < 256/32; i++)
 489         if ((result->map[i] = al->map[i] & bl->map[i]))
 490             nonempty = FcTrue;
 491     return nonempty;
 492 }
 493
 494 FcCharSet *
 495 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 496 {
 497     return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 498 }
 499
 500 static FcBool
 501 FcCharSetUnionLeaf (FcCharLeaf *result,
 502                     const FcCharLeaf *al,
 503                     const FcCharLeaf *bl)
 504 {
 505     int i;
 506
 507     for (i = 0; i < 256/32; i++)
 508         result->map[i] = al->map[i] | bl->map[i];
 509     return FcTrue;
 510 }
 511
 512 FcCharSet *
 513 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 514 {
 515     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 516 }
 517
 518 static FcBool
 519 FcCharSetSubtractLeaf (FcCharLeaf *result,
 520                        const FcCharLeaf *al,
 521                        const FcCharLeaf *bl)
 522 {
 523     int     i;
 524     FcBool  nonempty = FcFalse;
 525
 526     for (i = 0; i < 256/32; i++)
 527         if ((result->map[i] = al->map[i] & ~bl->map[i]))
 528             nonempty = FcTrue;
 529     return nonempty;
 530 }
 531
 532 FcCharSet *
 533 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 534 {
 535     return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 536 }
 537
 538 FcBool
 539 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 540 {
 541     FcCharLeaf  *leaf = FcCharSetFindLeaf (fcs, ucs4);
 542     if (!leaf)
 543         return FcFalse;
 544     return (leaf->map[(ucs4 & 0xff) >> 5] & (1 << (ucs4 & 0x1f))) != 0;
 545 }
 546
 547 static FcChar32
 548 FcCharSetPopCount (FcChar32 c1)
 549 {
 550     /* hackmem 169 */
 551     FcChar32    c2 = (c1 >> 1) & 033333333333;
 552     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
 553     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
 554 }
 555
 556 FcChar32
 557 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
 558 {
 559     FcCharSetIter   ai, bi;
 560     FcChar32        count = 0;
 561
 562     FcCharSetIterStart (a, &ai);
 563     FcCharSetIterStart (b, &bi);
 564     while (ai.leaf && bi.leaf)
 565     {
 566         if (ai.ucs4 == bi.ucs4)
 567         {
 568             FcChar32    *am = ai.leaf->map;
 569             FcChar32    *bm = bi.leaf->map;
 570             int         i = 256/32;
 571             while (i--)
 572                 count += FcCharSetPopCount (*am++ & *bm++);
 573             FcCharSetIterNext (a, &ai);
 574         }
 575         else if (ai.ucs4 < bi.ucs4)
 576         {
 577             ai.ucs4 = bi.ucs4;
 578             FcCharSetIterSet (a, &ai);
 579         }
 580         if (bi.ucs4 < ai.ucs4)
 581         {
 582             bi.ucs4 = ai.ucs4;
 583             FcCharSetIterSet (b, &bi);
 584         }
 585     }
 586     return count;
 587 }
 588
 589 FcChar32
 590 FcCharSetCount (const FcCharSet *a)
 591 {
 592     FcCharSetIter   ai;
 593     FcChar32        count = 0;
 594
 595     for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
 596     {
 597         int                 i = 256/32;
 598         FcChar32            *am = ai.leaf->map;
 599
 600         while (i--)
 601             count += FcCharSetPopCount (*am++);
 602     }
 603     return count;
 604 }
 605
 606 FcChar32
 607 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
 608 {
 609     FcCharSetIter   ai, bi;
 610     FcChar32        count = 0;
 611
 612     FcCharSetIterStart (a, &ai);
 613     FcCharSetIterStart (b, &bi);
 614     while (ai.leaf)
 615     {
 616         if (ai.ucs4 <= bi.ucs4)
 617         {
 618             FcChar32    *am = ai.leaf->map;
 619             int         i = 256/32;
 620             if (ai.ucs4 == bi.ucs4)
 621             {
 622                 FcChar32        *bm = bi.leaf->map;;
 623                 while (i--)
 624                     count += FcCharSetPopCount (*am++ & ~*bm++);
 625             }
 626             else
 627             {
 628                 while (i--)
 629                     count += FcCharSetPopCount (*am++);
 630             }
 631             FcCharSetIterNext (a, &ai);
 632         }
 633         else if (bi.leaf)
 634         {
 635             bi.ucs4 = ai.ucs4;
 636             FcCharSetIterSet (b, &bi);
 637         }
 638     }
 639     return count;
 640 }
 641
 642 /*
 643  * return FcTrue iff a is a subset of b
 644  */
 645 FcBool
 646 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 647 {
 648     int         ai, bi;
 649     FcChar16    an, bn;
 650
 651     if (a == b) return FcTrue;
 652     bi = 0;
 653     ai = 0;
 654     while (ai < a->num && bi < b->num)
 655     {
 656         an = FcCharSetGetNumbers(a)[ai];
 657         bn = FcCharSetGetNumbers(b)[bi];
 658         /*
 659          * Check matching pages
 660          */
 661         if (an == bn)
 662         {
 663             FcChar32    *am = FcCharSetGetLeaf(a, ai)->map;
 664             FcChar32    *bm = FcCharSetGetLeaf(b, bi)->map;
 665
 666             if (am != bm)
 667             {
 668                 int     i = 256/32;
 669                 /*
 670                  * Does am have any bits not in bm?
 671                  */
 672                 while (i--)
 673                     if (*am++ & ~*bm++)
 674                         return FcFalse;
 675             }
 676             ai++;
 677             bi++;
 678         }
 679         /*
 680          * Does a have any pages not in b?
 681          */
 682         else if (an < bn)
 683             return FcFalse;
 684         else
 685         {
 686             int     low = bi + 1;
 687             int     high = b->num - 1;
 688
 689             /*
 690              * Search for page 'an' in 'b'
 691              */
 692             while (low <= high)
 693             {
 694                 int mid = (low + high) >> 1;
 695                 bn = FcCharSetGetNumbers(b)[mid];
 696                 if (bn == an)
 697                 {
 698                     high = mid;
 699                     break;
 700                 }
 701                 if (bn < an)
 702                     low = mid + 1;
 703                 else
 704                     high = mid - 1;
 705             }
 706             bi = high;
 707             while (bi < b->num && FcCharSetGetNumbers(b)[bi] < an)
 708                 bi++;
 709         }
 710     }
 711     /*
 712      * did we look at every page?
 713      */
 714     return ai >= a->num;
 715 }
 716
 717 /*
 718  * These two functions efficiently walk the entire charmap for
 719  * other software (like pango) that want their own copy
 720  */
 721
 722 FcChar32
 723 FcCharSetNextPage (const FcCharSet  *a,
 724                    FcChar32         map[FC_CHARSET_MAP_SIZE],
 725                    FcChar32         *next)
 726 {
 727     FcCharSetIter   ai;
 728     FcChar32        page;
 729
 730     ai.ucs4 = *next;
 731     FcCharSetIterSet (a, &ai);
 732     if (!ai.leaf)
 733         return FC_CHARSET_DONE;
 734
 735     /*
 736      * Save current information
 737      */
 738     page = ai.ucs4;
 739     memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
 740     /*
 741      * Step to next page
 742      */
 743     FcCharSetIterNext (a, &ai);
 744     *next = ai.ucs4;
 745
 746     return page;
 747 }
 748
 749 FcChar32
 750 FcCharSetFirstPage (const FcCharSet *a,
 751                     FcChar32        map[FC_CHARSET_MAP_SIZE],
 752                     FcChar32        *next)
 753 {
 754     *next = 0;
 755     return FcCharSetNextPage (a, map, next);
 756 }
 757
 758 /*
 759  * old coverage API, rather hard to use correctly
 760  */
 761 FcChar32
 762 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
 763
 764 FcChar32
 765 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
 766 {
 767     FcCharSetIter   ai;
 768
 769     ai.ucs4 = page;
 770     FcCharSetIterSet (a, &ai);
 771     if (!ai.leaf)
 772     {
 773         memset (result, '\0', 256 / 8);
 774         page = 0;
 775     }
 776     else
 777     {
 778         memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
 779         FcCharSetIterNext (a, &ai);
 780         page = ai.ucs4;
 781     }
 782     return page;
 783 }
 784
 785 /*
 786  * ASCII representation of charsets.
 787  *
 788  * Each leaf is represented as 9 32-bit values, the code of the first character followed
 789  * by 8 32 bit values for the leaf itself.  Each value is encoded as 5 ASCII characters,
 790  * only 85 different values are used to avoid control characters as well as the other
 791  * characters used to encode font names.  85**5 > 2^32 so things work out, but
 792  * it's not exactly human readable output.  As a special case, 0 is encoded as a space
 793  */
 794
 795 static const unsigned char      charToValue[256] = {
 796     /*     "" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 797     /*   "\b" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 798     /* "\020" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 799     /* "\030" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 800     /*    " " */ 0xff,  0x00,  0xff,  0x01,  0x02,  0x03,  0x04,  0xff,
 801     /*    "(" */ 0x05,  0x06,  0x07,  0x08,  0xff,  0xff,  0x09,  0x0a,
 802     /*    "0" */ 0x0b,  0x0c,  0x0d,  0x0e,  0x0f,  0x10,  0x11,  0x12,
 803     /*    "8" */ 0x13,  0x14,  0xff,  0x15,  0x16,  0xff,  0x17,  0x18,
 804     /*    "@" */ 0x19,  0x1a,  0x1b,  0x1c,  0x1d,  0x1e,  0x1f,  0x20,
 805     /*    "H" */ 0x21,  0x22,  0x23,  0x24,  0x25,  0x26,  0x27,  0x28,
 806     /*    "P" */ 0x29,  0x2a,  0x2b,  0x2c,  0x2d,  0x2e,  0x2f,  0x30,
 807     /*    "X" */ 0x31,  0x32,  0x33,  0x34,  0xff,  0x35,  0x36,  0xff,
 808     /*    "`" */ 0xff,  0x37,  0x38,  0x39,  0x3a,  0x3b,  0x3c,  0x3d,
 809     /*    "h" */ 0x3e,  0x3f,  0x40,  0x41,  0x42,  0x43,  0x44,  0x45,
 810     /*    "p" */ 0x46,  0x47,  0x48,  0x49,  0x4a,  0x4b,  0x4c,  0x4d,
 811     /*    "x" */ 0x4e,  0x4f,  0x50,  0x51,  0x52,  0x53,  0x54,  0xff,
 812     /* "\200" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 813     /* "\210" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 814     /* "\220" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 815     /* "\230" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 816     /* "\240" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 817     /* "\250" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 818     /* "\260" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 819     /* "\270" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 820     /* "\300" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 821     /* "\310" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 822     /* "\320" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 823     /* "\330" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 824     /* "\340" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 825     /* "\350" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 826     /* "\360" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 827     /* "\370" */ 0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,  0xff,
 828 };
 829
 830 static const FcChar8 valueToChar[0x55] = {
 831     /* 0x00 */ '!', '#', '$', '%', '&', '(', ')', '*',
 832     /* 0x08 */ '+', '.', '/', '0', '1', '2', '3', '4',
 833     /* 0x10 */ '5', '6', '7', '8', '9', ';', '<', '>',
 834     /* 0x18 */ '?', '@', 'A', 'B', 'C', 'D', 'E', 'F',
 835     /* 0x20 */ 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N',
 836     /* 0x28 */ 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V',
 837     /* 0x30 */ 'W', 'X', 'Y', 'Z', '[', ']', '^', 'a',
 838     /* 0x38 */ 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i',
 839     /* 0x40 */ 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q',
 840     /* 0x48 */ 'r', 's', 't', 'u', 'v', 'w', 'x', 'y',
 841     /* 0x50 */ 'z', '{', '|', '}', '~',
 842 };
 843
 844 static FcChar8 *
 845 FcCharSetParseValue (FcChar8 *string, FcChar32 *value)
 846 {
 847     int         i;
 848     FcChar32    v;
 849     FcChar32    c;
 850
 851     if (*string == ' ')
 852     {
 853         v = 0;
 854         string++;
 855     }
 856     else
 857     {
 858         v = 0;
 859         for (i = 0; i < 5; i++)
 860         {
 861             if (!(c = (FcChar32) (unsigned char) *string++))
 862                 return 0;
 863             c = charToValue[c];
 864             if (c == 0xff)
 865                 return 0;
 866             v = v * 85 + c;
 867         }
 868     }
 869     *value = v;
 870     return string;
 871 }
 872
 873 static FcBool
 874 FcCharSetUnparseValue (FcStrBuf *buf, FcChar32 value)
 875 {
 876     int     i;
 877     if (value == 0)
 878     {
 879         return FcStrBufChar (buf, ' ');
 880     }
 881     else
 882     {
 883         FcChar8 string[6];
 884         FcChar8 *s = string + 5;
 885         string[5] = '\0';
 886         for (i = 0; i < 5; i++)
 887         {
 888             *--s = valueToChar[value % 85];
 889             value /= 85;
 890         }
 891         for (i = 0; i < 5; i++)
 892             if (!FcStrBufChar (buf, *s++))
 893                 return FcFalse;
 894     }
 895     return FcTrue;
 896 }
 897
 898 typedef struct _FcCharLeafEnt FcCharLeafEnt;
 899
 900 struct _FcCharLeafEnt {
 901     FcCharLeafEnt   *next;
 902     FcChar32        hash;
 903     FcCharLeaf      leaf;
 904 };
 905
 906 #define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
 907 static FcCharLeafEnt **FcCharLeafBlocks;
 908 static int FcCharLeafBlockCount;
 909
 910 static FcCharLeafEnt *
 911 FcCharLeafEntCreate (void)
 912 {
 913     static FcCharLeafEnt    *block;
 914     static int              remain;
 915
 916     if (!remain)
 917     {
 918         FcCharLeafEnt **newBlocks;
 919
 920         FcCharLeafBlockCount++;
 921         newBlocks = realloc (FcCharLeafBlocks, FcCharLeafBlockCount * sizeof (FcCharLeafEnt *));
 922         if (!newBlocks)
 923             return 0;
 924         FcCharLeafBlocks = newBlocks;
 925         block = FcCharLeafBlocks[FcCharLeafBlockCount-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
 926         if (!block)
 927             return 0;
 928         FcMemAlloc (FC_MEM_CHARLEAF, FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
 929         remain = FC_CHAR_LEAF_BLOCK;
 930     }
 931     remain--;
 932     return block++;
 933 }
 934
 935 #define FC_CHAR_LEAF_HASH_SIZE  257
 936
 937 static FcChar32
 938 FcCharLeafHash (FcCharLeaf *leaf)
 939 {
 940     FcChar32    hash = 0;
 941     int         i;
 942
 943     for (i = 0; i < 256/32; i++)
 944         hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
 945     return hash;
 946 }
 947
 948 static int      FcCharLeafTotal;
 949 static int      FcCharLeafUsed;
 950
 951 static FcCharLeafEnt    *FcCharLeafHashTable[FC_CHAR_LEAF_HASH_SIZE];
 952
 953 static FcCharLeaf *
 954 FcCharSetFreezeLeaf (FcCharLeaf *leaf)
 955 {
 956     FcChar32                    hash = FcCharLeafHash (leaf);
 957     FcCharLeafEnt               **bucket = &FcCharLeafHashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
 958     FcCharLeafEnt               *ent;
 959
 960     FcCharLeafTotal++;
 961     for (ent = *bucket; ent; ent = ent->next)
 962     {
 963         if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
 964             return &ent->leaf;
 965     }
 966
 967     ent = FcCharLeafEntCreate();
 968     if (!ent)
 969         return 0;
 970     FcCharLeafUsed++;
 971     ent->leaf = *leaf;
 972     ent->hash = hash;
 973     ent->next = *bucket;
 974     *bucket = ent;
 975     return &ent->leaf;
 976 }
 977
 978 static void
 979 FcCharSetThawAllLeaf (void)
 980 {
 981     int i;
 982
 983     for (i = 0; i < FC_CHAR_LEAF_HASH_SIZE; i++)
 984         FcCharLeafHashTable[i] = 0;
 985
 986     FcCharLeafTotal = 0;
 987     FcCharLeafUsed = 0;
 988
 989     for (i = 0; i < FcCharLeafBlockCount; i++)
 990         free (FcCharLeafBlocks[i]);
 991
 992     free (FcCharLeafBlocks);
 993     FcCharLeafBlocks = 0;
 994     FcCharLeafBlockCount = 0;
 995 }
 996
 997 typedef struct _FcCharSetEnt FcCharSetEnt;
 998
 999 struct _FcCharSetEnt {
1000     FcCharSetEnt        *next;
1001     FcChar32            hash;
1002     FcCharSet           set;
1003 };
1004
1005 #define FC_CHAR_SET_HASH_SIZE    67
1006
1007 static FcChar32
1008 FcCharSetHash (FcCharSet *fcs)
1009 {
1010     FcChar32    hash = 0;
1011     int         i;
1012
1013     /* hash in leaves */
1014     for (i = 0; i < fcs->num * (int) (sizeof (FcCharLeaf *) / sizeof (FcChar32)); i++)
1015         hash = ((hash << 1) | (hash >> 31)) ^ (FcChar32)(FcCharSetGetLeaf(fcs, i)->map);
1016     /* hash in numbers */
1017     for (i = 0; i < fcs->num; i++)
1018         hash = ((hash << 1) | (hash >> 31)) ^ *FcCharSetGetNumbers(fcs);
1019     return hash;
1020 }
1021
1022 static int      FcCharSetTotal;
1023 static int      FcCharSetUsed;
1024 static int      FcCharSetTotalEnts, FcCharSetUsedEnts;
1025
1026 static FcCharSetEnt     *FcCharSetHashTable[FC_CHAR_SET_HASH_SIZE];
1027
1028 static FcCharSet *
1029 FcCharSetFreezeBase (FcCharSet *fcs)
1030 {
1031     FcChar32            hash = FcCharSetHash (fcs);
1032     FcCharSetEnt        **bucket = &FcCharSetHashTable[hash % FC_CHAR_SET_HASH_SIZE];
1033     FcCharSetEnt        *ent;
1034     int                 size;
1035
1036     FcCharSetTotal++;
1037     FcCharSetTotalEnts += fcs->num;
1038     for (ent = *bucket; ent; ent = ent->next)
1039     {
1040         if (ent->hash == hash &&
1041             ent->set.num == fcs->num &&
1042             !memcmp (FcCharSetGetNumbers(&ent->set),
1043                      FcCharSetGetNumbers(fcs),
1044                      fcs->num * sizeof (FcChar16)))
1045         {
1046             FcBool ok = FcTrue;
1047             int i;
1048
1049             for (i = 0; i < fcs->num; i++)
1050                 if (FcCharSetGetLeaf(&ent->set, i) != FcCharSetGetLeaf(fcs, i))
1051                     ok = FcFalse;
1052             if (ok)
1053                 return &ent->set;
1054         }
1055     }
1056
1057     size = (sizeof (FcCharSetEnt) +
1058             fcs->num * sizeof (FcCharLeaf *) +
1059             fcs->num * sizeof (FcChar16));
1060     ent = malloc (size);
1061     if (!ent)
1062         return 0;
1063     FcMemAlloc (FC_MEM_CHARSET, size);
1064     FcCharSetUsed++;
1065     FcCharSetUsedEnts += fcs->num;
1066
1067     ent->set.ref = FC_REF_CONSTANT;
1068     ent->set.num = fcs->num;
1069     ent->set.bank = fcs->bank;
1070     if (fcs->bank == FC_BANK_DYNAMIC)
1071     {
1072         if (fcs->num)
1073         {
1074             ent->set.u.dyn.leaves = (FcCharLeaf **) (ent + 1);
1075             ent->set.u.dyn.numbers = (FcChar16 *) (ent->set.u.dyn.leaves + fcs->num);
1076             memcpy (ent->set.u.dyn.leaves, fcs->u.dyn.leaves, fcs->num * sizeof (FcCharLeaf *));
1077             memcpy (ent->set.u.dyn.numbers, fcs->u.dyn.numbers, fcs->num * sizeof (FcChar16));
1078         }
1079         else
1080         {
1081             ent->set.u.dyn.leaves = 0;
1082             ent->set.u.dyn.numbers = 0;
1083         }
1084     }
1085     else
1086     {
1087         ent->set.u.stat.leafidx_offset = fcs->u.stat.leafidx_offset;
1088         ent->set.u.stat.numbers_offset = fcs->u.stat.numbers_offset;
1089     }
1090
1091     ent->hash = hash;
1092     ent->next = *bucket;
1093     *bucket = ent;
1094     return &ent->set;
1095 }
1096
1097 void
1098 FcCharSetThawAll (void)
1099 {
1100     int i;
1101     FcCharSetEnt        *ent, *next;
1102
1103     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1104     {
1105         for (ent = FcCharSetHashTable[i]; ent; ent = next)
1106         {
1107             next = ent->next;
1108             free (ent);
1109         }
1110         FcCharSetHashTable[i] = 0;
1111     }
1112
1113     FcCharSetTotal = 0;
1114     FcCharSetTotalEnts = 0;
1115     FcCharSetUsed = 0;
1116     FcCharSetUsedEnts = 0;
1117
1118     FcCharSetThawAllLeaf ();
1119 }
1120
1121 FcCharSet *
1122 FcCharSetFreeze (FcCharSet *fcs)
1123 {
1124     FcCharSet   *b;
1125     FcCharSet   *n = 0;
1126     FcCharLeaf  *l;
1127     int         i;
1128
1129     b = FcCharSetCreate ();
1130     if (!b)
1131         goto bail0;
1132     for (i = 0; i < fcs->num; i++)
1133     {
1134         l = FcCharSetFreezeLeaf (FcCharSetGetLeaf(fcs, i));
1135         if (!l)
1136             goto bail1;
1137         if (!FcCharSetInsertLeaf (b, FcCharSetGetNumbers(fcs)[i] << 8, l))
1138             goto bail1;
1139     }
1140     n = FcCharSetFreezeBase (b);
1141 bail1:
1142     if (b->bank == FC_BANK_DYNAMIC)
1143     {
1144         if (b->u.dyn.leaves)
1145         {
1146             FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcCharLeaf *));
1147             free (b->u.dyn.leaves);
1148         }
1149         if (b->u.dyn.numbers)
1150         {
1151             FcMemFree (FC_MEM_CHARSET, b->num * sizeof (FcChar16));
1152             free (b->u.dyn.numbers);
1153         }
1154     }
1155     FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1156     free (b);
1157 bail0:
1158     return n;
1159 }
1160
1161 FcCharSet *
1162 FcNameParseCharSet (FcChar8 *string)
1163 {
1164     FcCharSet   *c, *n = 0;
1165     FcChar32    ucs4;
1166     FcCharLeaf  *leaf;
1167     FcCharLeaf  temp;
1168     FcChar32    bits;
1169     int         i;
1170
1171     c = FcCharSetCreate ();
1172     if (!c)
1173         goto bail0;
1174     while (*string)
1175     {
1176         string = FcCharSetParseValue (string, &ucs4);
1177         if (!string)
1178             goto bail1;
1179         bits = 0;
1180         for (i = 0; i < 256/32; i++)
1181         {
1182             string = FcCharSetParseValue (string, &temp.map[i]);
1183             if (!string)
1184                 goto bail1;
1185             bits |= temp.map[i];
1186         }
1187         if (bits)
1188         {
1189             leaf = FcCharSetFreezeLeaf (&temp);
1190             if (!leaf)
1191                 goto bail1;
1192             if (!FcCharSetInsertLeaf (c, ucs4, leaf))
1193                 goto bail1;
1194         }
1195     }
1196 #ifdef CHATTY
1197     printf ("          %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
1198     printf ("Leaves:   %8d %8d %8d %8d\n",
1199             FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
1200             FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
1201     printf ("Charsets: %8d %8d %8d %8d\n",
1202             FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
1203             FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
1204     printf ("Tables:   %8d %8d %8d %8d\n",
1205             FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1206             FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1207     printf ("Total:    %8s %8d %8s %8d\n",
1208             "",
1209             sizeof (FcCharLeaf) * FcCharLeafTotal +
1210             sizeof (FcCharSet) * FcCharSetTotal +
1211             FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
1212             "",
1213             sizeof (FcCharLeaf) * FcCharLeafUsed +
1214             sizeof (FcCharSet) * FcCharSetUsed +
1215             FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
1216 #endif
1217     n = FcCharSetFreezeBase (c);
1218 bail1:
1219     if (c->bank == FC_BANK_DYNAMIC)
1220     {
1221         if (c->u.dyn.leaves)
1222         {
1223             FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcCharLeaf *));
1224             free (c->u.dyn.leaves);
1225         }
1226         if (c->u.dyn.numbers)
1227         {
1228             FcMemFree (FC_MEM_CHARSET, c->num * sizeof (FcChar16));
1229             free (c->u.dyn.numbers);
1230         }
1231         FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
1232     }
1233     free (c);
1234 bail0:
1235     return n;
1236 }
1237
1238 FcBool
1239 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
1240 {
1241     FcCharSetIter   ci;
1242     int             i;
1243 #ifdef CHECK
1244     int             len = buf->len;
1245 #endif
1246
1247     for (FcCharSetIterStart (c, &ci);
1248          ci.leaf;
1249          FcCharSetIterNext (c, &ci))
1250     {
1251         if (!FcCharSetUnparseValue (buf, ci.ucs4))
1252             return FcFalse;
1253         for (i = 0; i < 256/32; i++)
1254             if (!FcCharSetUnparseValue (buf, ci.leaf->map[i]))
1255                 return FcFalse;
1256     }
1257 #ifdef CHECK
1258     {
1259         FcCharSet       *check;
1260         FcChar32        missing;
1261         FcCharSetIter   ci, checki;
1262
1263         /* null terminate for parser */
1264         FcStrBufChar (buf, '\0');
1265         /* step back over null for life after test */
1266         buf->len--;
1267         check = FcNameParseCharSet (buf->buf + len);
1268         FcCharSetIterStart (c, &ci);
1269         FcCharSetIterStart (check, &checki);
1270         while (ci.leaf || checki.leaf)
1271         {
1272             if (ci.ucs4 < checki.ucs4)
1273             {
1274                 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
1275                 FcCharSetIterNext (c, &ci);
1276             }
1277             else if (checki.ucs4 < ci.ucs4)
1278             {
1279                 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
1280                 FcCharSetIterNext (check, &checki);
1281             }
1282             else
1283             {
1284                 int         i = 256/32;
1285                 FcChar32    *cm = ci.leaf->map;
1286                 FcChar32    *checkm = checki.leaf->map;
1287
1288                 for (i = 0; i < 256; i += 32)
1289                 {
1290                     if (*cm != *checkm)
1291                         printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
1292                                 ci.ucs4 + i, *cm, *checkm);
1293                     cm++;
1294                     checkm++;
1295                 }
1296                 FcCharSetIterNext (c, &ci);
1297                 FcCharSetIterNext (check, &checki);
1298             }
1299         }
1300         if ((missing = FcCharSetSubtractCount (c, check)))
1301             printf ("%d missing in reparsed result\n", missing);
1302         if ((missing = FcCharSetSubtractCount (check, c)))
1303             printf ("%d extra in reparsed result\n", missing);
1304         FcCharSetDestroy (check);
1305     }
1306 #endif
1307
1308     return FcTrue;
1309 }
1310
1311 void
1312 FcCharSetNewBank(void)
1313 {
1314     charset_count = 0;
1315     charset_numbers_count = 0;
1316     charset_leaf_count = 0;
1317     charset_leaf_idx_count = 0;
1318 }
1319
1320 int
1321 FcCharSetNeededBytes (const FcCharSet *c)
1322 {
1323     /* yes, there's redundancy */
1324     charset_count++;
1325     charset_leaf_idx_count++;
1326     charset_leaf_count += c->num;
1327     charset_numbers_count += c->num;
1328     return sizeof (FcCharSet) +
1329         sizeof (int) +                  /* leaf_idx */
1330         sizeof (FcCharLeaf) * c->num +  /* leaf */
1331         sizeof (FcChar16) * c->num;     /* number */
1332 }
1333
1334 int
1335 FcCharSetNeededBytesAlign (void)
1336 {
1337     return __alignof__ (FcCharSet) + __alignof__ (int) +
1338         __alignof__ (FcCharLeaf) + __alignof__ (FcChar16);
1339 }
1340
1341 static FcBool
1342 FcCharSetEnsureBank (int bi)
1343 {
1344     if (!charsets || charset_bank_count <= bi)
1345     {
1346         int new_count = charset_bank_count + 2;
1347         FcCharSet ** cs;
1348         FcChar16 ** n;
1349         FcCharLeaf ** lvs;
1350         int ** lvi;
1351         int i;
1352
1353         cs = realloc(charsets, sizeof(FcCharSet*) * new_count);
1354         if (!cs) return 0;
1355         n = realloc(numbers, sizeof(FcChar16*) * new_count);
1356         if (!n) return 0;
1357         lvs = realloc(leaves, sizeof(FcCharLeaf*) * new_count);
1358         if (!lvs) return 0;
1359         lvi = realloc(leaf_idx, sizeof(int*) * new_count);
1360         if (!lvi) return 0;
1361
1362         charsets = cs; numbers = n; leaves = lvs; leaf_idx = lvi;
1363         for (i = charset_bank_count; i < new_count; i++)
1364         {
1365             charsets[i] = 0;
1366             numbers[i] = 0;
1367             leaves[i] = 0;
1368             leaf_idx[i] = 0;
1369         }
1370         charset_bank_count = new_count;
1371     }
1372     return FcTrue;
1373 }
1374
1375 void *
1376 FcCharSetDistributeBytes (FcCache * metadata, void * block_ptr)
1377 {
1378     int bi = FcCacheBankToIndex(metadata->bank);
1379     if (!FcCharSetEnsureBank(bi))
1380         return 0;
1381
1382     block_ptr = ALIGN (block_ptr, FcCharSet);
1383     charsets[bi] = (FcCharSet *)block_ptr;
1384     block_ptr = (void *)((char *)block_ptr +
1385                      (sizeof (FcCharSet) * charset_count));
1386     block_ptr = ALIGN (block_ptr, FcChar16);
1387     numbers[bi] = (FcChar16 *)block_ptr;
1388     block_ptr = (void *)((char *)block_ptr +
1389                      (sizeof(FcChar16) * charset_numbers_count));
1390     block_ptr = ALIGN (block_ptr, FcCharLeaf);
1391     leaves[bi] = (FcCharLeaf *)block_ptr;
1392     block_ptr = (void *)((char *)block_ptr +
1393                      (sizeof(FcCharLeaf) * charset_leaf_count));
1394     block_ptr = ALIGN (block_ptr, int);
1395     leaf_idx[bi] = (int *)block_ptr;
1396     block_ptr = (void *)((char *)block_ptr +
1397                      (sizeof(int) * charset_leaf_idx_count));
1398
1399     metadata->charset_count = charset_count;
1400     metadata->charset_numbers_count = charset_numbers_count;
1401     metadata->charset_leaf_count = charset_leaf_count;
1402     metadata->charset_leaf_idx_count = charset_leaf_idx_count;
1403     charset_ptr = 0; charset_leaf_ptr = 0;
1404     charset_leaf_idx_ptr = 0; charset_numbers_ptr = 0;
1405     return block_ptr;
1406 }
1407
1408 FcCharSet *
1409 FcCharSetSerialize(int bank, FcCharSet *c)
1410 {
1411     int i;
1412     FcCharSet new;
1413     int bi = FcCacheBankToIndex(bank), cp = charset_ptr;
1414
1415     new.ref = FC_REF_CONSTANT;
1416     new.bank = bank;
1417     new.u.stat.leafidx_offset = charset_leaf_idx_ptr;
1418     new.u.stat.numbers_offset = charset_numbers_ptr;
1419     new.num = c->num;
1420
1421     charsets[bi][charset_ptr++] = new;
1422
1423     leaf_idx[bi][charset_leaf_idx_ptr++] = charset_leaf_ptr;
1424     for (i = 0; i < c->num; i++)
1425     {
1426         memcpy (&leaves[bi][charset_leaf_ptr++],
1427                 c->u.dyn.leaves[i], sizeof(FcCharLeaf));
1428         numbers[bi][charset_numbers_ptr++] = c->u.dyn.numbers[i];
1429     }
1430
1431     return &charsets[bi][cp];
1432 }
1433
1434 void *
1435 FcCharSetUnserialize (FcCache metadata, void *block_ptr)
1436 {
1437     int bi = FcCacheBankToIndex(metadata.bank);
1438     if (!FcCharSetEnsureBank(bi))
1439         return 0;
1440
1441     block_ptr = ALIGN (block_ptr, FcCharSet);
1442     charsets[bi] = (FcCharSet *)block_ptr;
1443     block_ptr = (void *)((char *)block_ptr +
1444                      (sizeof (FcCharSet) * metadata.charset_count));
1445     block_ptr = ALIGN (block_ptr, FcChar16);
1446     numbers[bi] = (FcChar16 *)block_ptr;
1447     block_ptr = (void *)((char *)block_ptr +
1448                      (sizeof(FcChar16) * metadata.charset_numbers_count));
1449     block_ptr = ALIGN (block_ptr, FcCharLeaf);
1450     leaves[bi] = (FcCharLeaf *)block_ptr;
1451     block_ptr = (void *)((char *)block_ptr +
1452                      (sizeof(FcCharLeaf) * metadata.charset_leaf_count));
1453     block_ptr = ALIGN (block_ptr, int);
1454     leaf_idx[bi] = (int *)block_ptr;
1455     block_ptr = (void *)((char *)block_ptr +
1456                      (sizeof(int) * metadata.charset_leaf_idx_count));
1457
1458     return block_ptr;
1459 }
1460
1461 FcCharLeaf *
1462 FcCharSetGetLeaf(const FcCharSet *c, int i)
1463 {
1464     int bi;
1465     if (c->bank == FC_BANK_DYNAMIC)
1466         return c->u.dyn.leaves[i];
1467     bi = FcCacheBankToIndex(c->bank);
1468
1469     return &leaves[bi][leaf_idx[bi][c->u.stat.leafidx_offset]+i];
1470 }
1471
1472 FcChar16 *
1473 FcCharSetGetNumbers(const FcCharSet *c)
1474 {
1475     int bi;
1476     if (c->bank == FC_BANK_DYNAMIC)
1477         return c->u.dyn.numbers;
1478     bi = FcCacheBankToIndex(c->bank);
1479
1480     return &numbers[bi][c->u.stat.numbers_offset];
1481 }
1482