src/fccharset.c

   1 /*
   2  * fontconfig/src/fccharset.c
   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 the author(s) not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  The authors make 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  * THE AUTHOR(S) DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL THE AUTHOR(S) 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 "fcint.h"
  26 #include <stdlib.h>
  27
  28 /* #define CHECK */
  29
  30 FcCharSet *
  31 FcCharSetCreate (void)
  32 {
  33     FcCharSet   *fcs;
  34
  35     fcs = (FcCharSet *) malloc (sizeof (FcCharSet));
  36     if (!fcs)
  37         return 0;
  38     FcRefInit (&fcs->ref, 1);
  39     fcs->num = 0;
  40     fcs->leaves_offset = 0;
  41     fcs->numbers_offset = 0;
  42     return fcs;
  43 }
  44
  45 FcCharSet *
  46 FcCharSetPromote (FcValuePromotionBuffer *vbuf)
  47 {
  48     FcCharSet *fcs = (FcCharSet *) vbuf;
  49
  50     FC_ASSERT_STATIC (sizeof (FcCharSet) <= sizeof (FcValuePromotionBuffer));
  51
  52     FcRefSetConst (&fcs->ref);
  53     fcs->num = 0;
  54     fcs->leaves_offset = 0;
  55     fcs->numbers_offset = 0;
  56
  57     return fcs;
  58 }
  59
  60 FcCharSet *
  61 FcCharSetNew (void)
  62 {
  63     return FcCharSetCreate ();
  64 }
  65
  66 void
  67 FcCharSetDestroy (FcCharSet *fcs)
  68 {
  69     int i;
  70
  71     if (fcs)
  72     {
  73         if (FcRefIsConst (&fcs->ref))
  74         {
  75             FcCacheObjectDereference (fcs);
  76             return;
  77         }
  78         if (FcRefDec (&fcs->ref) != 1)
  79             return;
  80         for (i = 0; i < fcs->num; i++)
  81             free (FcCharSetLeaf (fcs, i));
  82         if (fcs->num)
  83         {
  84             free (FcCharSetLeaves (fcs));
  85             free (FcCharSetNumbers (fcs));
  86         }
  87         free (fcs);
  88     }
  89 }
  90
  91 /*
  92  * Search for the leaf containing with the specified num.
  93  * Return its index if it exists, otherwise return negative of
  94  * the (position + 1) where it should be inserted
  95  */
  96
  97
  98 static int
  99 FcCharSetFindLeafForward (const FcCharSet *fcs, int start, FcChar16 num)
 100 {
 101     FcChar16            *numbers = FcCharSetNumbers(fcs);
 102     FcChar16            page;
 103     int                 low = start;
 104     int                 high = fcs->num - 1;
 105
 106     if (!numbers)
 107         return -1;
 108     while (low <= high)
 109     {
 110         int mid = (low + high) >> 1;
 111         page = numbers[mid];
 112         if (page == num)
 113             return mid;
 114         if (page < num)
 115             low = mid + 1;
 116         else
 117             high = mid - 1;
 118     }
 119     if (high < 0 || (high < fcs->num && numbers[high] < num))
 120         high++;
 121     return -(high + 1);
 122 }
 123
 124 /*
 125  * Locate the leaf containing the specified char, return
 126  * its index if it exists, otherwise return negative of
 127  * the (position + 1) where it should be inserted
 128  */
 129
 130 static int
 131 FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
 132 {
 133     return FcCharSetFindLeafForward (fcs, 0, ucs4 >> 8);
 134 }
 135
 136 static FcCharLeaf *
 137 FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
 138 {
 139     int pos = FcCharSetFindLeafPos (fcs, ucs4);
 140     if (pos >= 0)
 141         return FcCharSetLeaf(fcs, pos);
 142     return 0;
 143 }
 144
 145 #define FC_IS_ZERO_OR_POWER_OF_TWO(x) (!((x) & ((x)-1)))
 146
 147 static FcBool
 148 FcCharSetPutLeaf (FcCharSet     *fcs,
 149                   FcChar32      ucs4,
 150                   FcCharLeaf    *leaf,
 151                   int           pos)
 152 {
 153     intptr_t    *leaves = FcCharSetLeaves (fcs);
 154     FcChar16    *numbers = FcCharSetNumbers (fcs);
 155
 156     ucs4 >>= 8;
 157     if (ucs4 >= 0x10000)
 158         return FcFalse;
 159
 160     if (FC_IS_ZERO_OR_POWER_OF_TWO (fcs->num))
 161     {
 162       if (!fcs->num)
 163       {
 164         unsigned int alloced = 8;
 165         leaves = malloc (alloced * sizeof (*leaves));
 166         numbers = malloc (alloced * sizeof (*numbers));
 167         if (!leaves || !numbers)
 168         {
 169             if (leaves)
 170                 free (leaves);
 171             if (numbers)
 172                 free (numbers);
 173             return FcFalse;
 174         }
 175       }
 176       else
 177       {
 178         int i;
 179         unsigned int alloced = fcs->num;
 180         intptr_t *new_leaves;
 181         ptrdiff_t distance;
 182
 183         alloced *= 2;
 184         numbers = realloc (numbers, alloced * sizeof (*numbers));
 185         if (!numbers)
 186             return FcFalse;
 187         new_leaves = realloc (leaves, alloced * sizeof (*leaves));
 188         if (!new_leaves)
 189         {
 190             /*
 191              * Revert the reallocation of numbers. We update numbers_offset
 192              * first in case realloc() fails.
 193              */
 194             fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
 195             numbers = realloc (numbers, (alloced / 2) * sizeof (*numbers));
 196             /* unlikely to fail though */
 197             if (!numbers)
 198                 return FcFalse;
 199             fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
 200             return FcFalse;
 201         }
 202         distance = (char *) new_leaves - (char *) leaves;
 203         for (i = 0; i < fcs->num; i++) {
 204             new_leaves[i] -= distance;
 205         }
 206         leaves = new_leaves;
 207       }
 208
 209       fcs->leaves_offset = FcPtrToOffset (fcs, leaves);
 210       fcs->numbers_offset = FcPtrToOffset (fcs, numbers);
 211     }
 212
 213     memmove (leaves + pos + 1, leaves + pos,
 214              (fcs->num - pos) * sizeof (*leaves));
 215     memmove (numbers + pos + 1, numbers + pos,
 216              (fcs->num - pos) * sizeof (*numbers));
 217     numbers[pos] = (FcChar16) ucs4;
 218     leaves[pos] = FcPtrToOffset (leaves, leaf);
 219     fcs->num++;
 220     return FcTrue;
 221 }
 222
 223 /*
 224  * Locate the leaf containing the specified char, creating it
 225  * if desired
 226  */
 227
 228 FcCharLeaf *
 229 FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
 230 {
 231     int                 pos;
 232     FcCharLeaf          *leaf;
 233
 234     pos = FcCharSetFindLeafPos (fcs, ucs4);
 235     if (pos >= 0)
 236         return FcCharSetLeaf(fcs, pos);
 237
 238     leaf = calloc (1, sizeof (FcCharLeaf));
 239     if (!leaf)
 240         return 0;
 241
 242     pos = -pos - 1;
 243     if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
 244     {
 245         free (leaf);
 246         return 0;
 247     }
 248     return leaf;
 249 }
 250
 251 static FcBool
 252 FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
 253 {
 254     int             pos;
 255
 256     pos = FcCharSetFindLeafPos (fcs, ucs4);
 257     if (pos >= 0)
 258     {
 259         free (FcCharSetLeaf (fcs, pos));
 260         FcCharSetLeaves(fcs)[pos] = FcPtrToOffset (FcCharSetLeaves(fcs),
 261                                                    leaf);
 262         return FcTrue;
 263     }
 264     pos = -pos - 1;
 265     return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
 266 }
 267
 268 FcBool
 269 FcCharSetAddChar (FcCharSet *fcs, FcChar32 ucs4)
 270 {
 271     FcCharLeaf  *leaf;
 272     FcChar32    *b;
 273
 274     if (fcs == NULL || FcRefIsConst (&fcs->ref))
 275         return FcFalse;
 276     leaf = FcCharSetFindLeafCreate (fcs, ucs4);
 277     if (!leaf)
 278         return FcFalse;
 279     b = &leaf->map[(ucs4 & 0xff) >> 5];
 280     *b |= (1U << (ucs4 & 0x1f));
 281     return FcTrue;
 282 }
 283
 284 FcBool
 285 FcCharSetDelChar (FcCharSet *fcs, FcChar32 ucs4)
 286 {
 287     FcCharLeaf  *leaf;
 288     FcChar32    *b;
 289
 290     if (fcs == NULL || FcRefIsConst (&fcs->ref))
 291         return FcFalse;
 292     leaf = FcCharSetFindLeaf (fcs, ucs4);
 293     if (!leaf)
 294         return FcTrue;
 295     b = &leaf->map[(ucs4 & 0xff) >> 5];
 296     *b &= ~(1U << (ucs4 & 0x1f));
 297     /* We don't bother removing the leaf if it's empty */
 298     return FcTrue;
 299 }
 300
 301 /*
 302  * An iterator for the leaves of a charset
 303  */
 304
 305 typedef struct _fcCharSetIter {
 306     FcCharLeaf      *leaf;
 307     FcChar32        ucs4;
 308     int             pos;
 309 } FcCharSetIter;
 310
 311 /*
 312  * Set iter->leaf to the leaf containing iter->ucs4 or higher
 313  */
 314
 315 static void
 316 FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
 317 {
 318     int             pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
 319
 320     if (pos < 0)
 321     {
 322         pos = -pos - 1;
 323         if (pos == fcs->num)
 324         {
 325             iter->ucs4 = ~0;
 326             iter->leaf = 0;
 327             return;
 328         }
 329         iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
 330     }
 331     iter->leaf = FcCharSetLeaf(fcs, pos);
 332     iter->pos = pos;
 333 }
 334
 335 static void
 336 FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
 337 {
 338     int pos = iter->pos + 1;
 339     if (pos >= fcs->num)
 340     {
 341         iter->ucs4 = ~0;
 342         iter->leaf = 0;
 343     }
 344     else
 345     {
 346         iter->ucs4 = (FcChar32) FcCharSetNumbers(fcs)[pos] << 8;
 347         iter->leaf = FcCharSetLeaf(fcs, pos);
 348         iter->pos = pos;
 349     }
 350 }
 351
 352
 353 static void
 354 FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
 355 {
 356     iter->ucs4 = 0;
 357     iter->pos = 0;
 358     FcCharSetIterSet (fcs, iter);
 359 }
 360
 361 FcCharSet *
 362 FcCharSetCopy (FcCharSet *src)
 363 {
 364     if (src)
 365     {
 366         if (!FcRefIsConst (&src->ref))
 367             FcRefInc (&src->ref);
 368         else
 369             FcCacheObjectReference (src);
 370     }
 371     return src;
 372 }
 373
 374 FcBool
 375 FcCharSetEqual (const FcCharSet *a, const FcCharSet *b)
 376 {
 377     FcCharSetIter   ai, bi;
 378     int             i;
 379
 380     if (a == b)
 381         return FcTrue;
 382     if (!a || !b)
 383         return FcFalse;
 384     for (FcCharSetIterStart (a, &ai), FcCharSetIterStart (b, &bi);
 385          ai.leaf && bi.leaf;
 386          FcCharSetIterNext (a, &ai), FcCharSetIterNext (b, &bi))
 387     {
 388         if (ai.ucs4 != bi.ucs4)
 389             return FcFalse;
 390         for (i = 0; i < 256/32; i++)
 391             if (ai.leaf->map[i] != bi.leaf->map[i])
 392                 return FcFalse;
 393     }
 394     return ai.leaf == bi.leaf;
 395 }
 396
 397 static FcBool
 398 FcCharSetAddLeaf (FcCharSet     *fcs,
 399                   FcChar32      ucs4,
 400                   FcCharLeaf    *leaf)
 401 {
 402     FcCharLeaf   *new = FcCharSetFindLeafCreate (fcs, ucs4);
 403     if (!new)
 404         return FcFalse;
 405     *new = *leaf;
 406     return FcTrue;
 407 }
 408
 409 static FcCharSet *
 410 FcCharSetOperate (const FcCharSet   *a,
 411                   const FcCharSet   *b,
 412                   FcBool            (*overlap) (FcCharLeaf          *result,
 413                                                 const FcCharLeaf    *al,
 414                                                 const FcCharLeaf    *bl),
 415                   FcBool        aonly,
 416                   FcBool        bonly)
 417 {
 418     FcCharSet       *fcs;
 419     FcCharSetIter   ai, bi;
 420
 421     if (!a || !b)
 422         goto bail0;
 423     fcs = FcCharSetCreate ();
 424     if (!fcs)
 425         goto bail0;
 426     FcCharSetIterStart (a, &ai);
 427     FcCharSetIterStart (b, &bi);
 428     while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
 429     {
 430         if (ai.ucs4 < bi.ucs4)
 431         {
 432             if (aonly)
 433             {
 434                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, ai.leaf))
 435                     goto bail1;
 436                 FcCharSetIterNext (a, &ai);
 437             }
 438             else
 439             {
 440                 ai.ucs4 = bi.ucs4;
 441                 FcCharSetIterSet (a, &ai);
 442             }
 443         }
 444         else if (bi.ucs4 < ai.ucs4 )
 445         {
 446             if (bonly)
 447             {
 448                 if (!FcCharSetAddLeaf (fcs, bi.ucs4, bi.leaf))
 449                     goto bail1;
 450                 FcCharSetIterNext (b, &bi);
 451             }
 452             else
 453             {
 454                 bi.ucs4 = ai.ucs4;
 455                 FcCharSetIterSet (b, &bi);
 456             }
 457         }
 458         else
 459         {
 460             FcCharLeaf  leaf;
 461
 462             if ((*overlap) (&leaf, ai.leaf, bi.leaf))
 463             {
 464                 if (!FcCharSetAddLeaf (fcs, ai.ucs4, &leaf))
 465                     goto bail1;
 466             }
 467             FcCharSetIterNext (a, &ai);
 468             FcCharSetIterNext (b, &bi);
 469         }
 470     }
 471     return fcs;
 472 bail1:
 473     FcCharSetDestroy (fcs);
 474 bail0:
 475     return 0;
 476 }
 477
 478 static FcBool
 479 FcCharSetIntersectLeaf (FcCharLeaf *result,
 480                         const FcCharLeaf *al,
 481                         const FcCharLeaf *bl)
 482 {
 483     int     i;
 484     FcBool  nonempty = FcFalse;
 485
 486     for (i = 0; i < 256/32; i++)
 487         if ((result->map[i] = al->map[i] & bl->map[i]))
 488             nonempty = FcTrue;
 489     return nonempty;
 490 }
 491
 492 FcCharSet *
 493 FcCharSetIntersect (const FcCharSet *a, const FcCharSet *b)
 494 {
 495     return FcCharSetOperate (a, b, FcCharSetIntersectLeaf, FcFalse, FcFalse);
 496 }
 497
 498 static FcBool
 499 FcCharSetUnionLeaf (FcCharLeaf *result,
 500                     const FcCharLeaf *al,
 501                     const FcCharLeaf *bl)
 502 {
 503     int i;
 504
 505     for (i = 0; i < 256/32; i++)
 506         result->map[i] = al->map[i] | bl->map[i];
 507     return FcTrue;
 508 }
 509
 510 FcCharSet *
 511 FcCharSetUnion (const FcCharSet *a, const FcCharSet *b)
 512 {
 513     return FcCharSetOperate (a, b, FcCharSetUnionLeaf, FcTrue, FcTrue);
 514 }
 515
 516 FcBool
 517 FcCharSetMerge (FcCharSet *a, const FcCharSet *b, FcBool *changed)
 518 {
 519     int         ai = 0, bi = 0;
 520     FcChar16    an, bn;
 521
 522     if (!a || !b)
 523         return FcFalse;
 524
 525     if (FcRefIsConst (&a->ref)) {
 526         if (changed)
 527             *changed = FcFalse;
 528         return FcFalse;
 529     }
 530
 531     if (changed) {
 532         *changed = !FcCharSetIsSubset(b, a);
 533         if (!*changed)
 534             return FcTrue;
 535     }
 536
 537     while (bi < b->num)
 538     {
 539         an = ai < a->num ? FcCharSetNumbers(a)[ai] : ~0;
 540         bn = FcCharSetNumbers(b)[bi];
 541
 542         if (an < bn)
 543         {
 544             ai = FcCharSetFindLeafForward (a, ai + 1, bn);
 545             if (ai < 0)
 546                 ai = -ai - 1;
 547         }
 548         else
 549         {
 550             FcCharLeaf *bl = FcCharSetLeaf(b, bi);
 551             if (bn < an)
 552             {
 553                 if (!FcCharSetAddLeaf (a, bn << 8, bl))
 554                     return FcFalse;
 555             }
 556             else
 557             {
 558                 FcCharLeaf *al = FcCharSetLeaf(a, ai);
 559                 FcCharSetUnionLeaf (al, al, bl);
 560             }
 561
 562             ai++;
 563             bi++;
 564         }
 565     }
 566
 567     return FcTrue;
 568 }
 569
 570 static FcBool
 571 FcCharSetSubtractLeaf (FcCharLeaf *result,
 572                        const FcCharLeaf *al,
 573                        const FcCharLeaf *bl)
 574 {
 575     int     i;
 576     FcBool  nonempty = FcFalse;
 577
 578     for (i = 0; i < 256/32; i++)
 579         if ((result->map[i] = al->map[i] & ~bl->map[i]))
 580             nonempty = FcTrue;
 581     return nonempty;
 582 }
 583
 584 FcCharSet *
 585 FcCharSetSubtract (const FcCharSet *a, const FcCharSet *b)
 586 {
 587     return FcCharSetOperate (a, b, FcCharSetSubtractLeaf, FcTrue, FcFalse);
 588 }
 589
 590 FcBool
 591 FcCharSetHasChar (const FcCharSet *fcs, FcChar32 ucs4)
 592 {
 593     FcCharLeaf  *leaf;
 594
 595     if (!fcs)
 596         return FcFalse;
 597     leaf = FcCharSetFindLeaf (fcs, ucs4);
 598     if (!leaf)
 599         return FcFalse;
 600     return (leaf->map[(ucs4 & 0xff) >> 5] & (1U << (ucs4 & 0x1f))) != 0;
 601 }
 602
 603 static FcChar32
 604 FcCharSetPopCount (FcChar32 c1)
 605 {
 606 #if __GNUC__ > 3 || (__GNUC__ == 3 && __GNUC_MINOR__ >= 4)
 607     return __builtin_popcount (c1);
 608 #else
 609     /* hackmem 169 */
 610     FcChar32    c2 = (c1 >> 1) & 033333333333;
 611     c2 = c1 - c2 - ((c2 >> 1) & 033333333333);
 612     return (((c2 + (c2 >> 3)) & 030707070707) % 077);
 613 #endif
 614 }
 615
 616 FcChar32
 617 FcCharSetIntersectCount (const FcCharSet *a, const FcCharSet *b)
 618 {
 619     FcCharSetIter   ai, bi;
 620     FcChar32        count = 0;
 621
 622     if (a && b)
 623     {
 624         FcCharSetIterStart (a, &ai);
 625         FcCharSetIterStart (b, &bi);
 626         while (ai.leaf && bi.leaf)
 627         {
 628             if (ai.ucs4 == bi.ucs4)
 629             {
 630                 FcChar32        *am = ai.leaf->map;
 631                 FcChar32        *bm = bi.leaf->map;
 632                 int             i = 256/32;
 633                 while (i--)
 634                     count += FcCharSetPopCount (*am++ & *bm++);
 635                 FcCharSetIterNext (a, &ai);
 636             }
 637             else if (ai.ucs4 < bi.ucs4)
 638             {
 639                 ai.ucs4 = bi.ucs4;
 640                 FcCharSetIterSet (a, &ai);
 641             }
 642             if (bi.ucs4 < ai.ucs4)
 643             {
 644                 bi.ucs4 = ai.ucs4;
 645                 FcCharSetIterSet (b, &bi);
 646             }
 647         }
 648     }
 649     return count;
 650 }
 651
 652 FcChar32
 653 FcCharSetCount (const FcCharSet *a)
 654 {
 655     FcCharSetIter   ai;
 656     FcChar32        count = 0;
 657
 658     if (a)
 659     {
 660         for (FcCharSetIterStart (a, &ai); ai.leaf; FcCharSetIterNext (a, &ai))
 661         {
 662             int             i = 256/32;
 663             FcChar32        *am = ai.leaf->map;
 664
 665             while (i--)
 666                 count += FcCharSetPopCount (*am++);
 667         }
 668     }
 669     return count;
 670 }
 671
 672 FcChar32
 673 FcCharSetSubtractCount (const FcCharSet *a, const FcCharSet *b)
 674 {
 675     FcCharSetIter   ai, bi;
 676     FcChar32        count = 0;
 677
 678     if (a && b)
 679     {
 680         FcCharSetIterStart (a, &ai);
 681         FcCharSetIterStart (b, &bi);
 682         while (ai.leaf)
 683         {
 684             if (ai.ucs4 <= bi.ucs4)
 685             {
 686                 FcChar32        *am = ai.leaf->map;
 687                 int             i = 256/32;
 688                 if (ai.ucs4 == bi.ucs4)
 689                 {
 690                     FcChar32    *bm = bi.leaf->map;
 691                     while (i--)
 692                         count += FcCharSetPopCount (*am++ & ~*bm++);
 693                 }
 694                 else
 695                 {
 696                     while (i--)
 697                         count += FcCharSetPopCount (*am++);
 698                 }
 699                 FcCharSetIterNext (a, &ai);
 700             }
 701             else if (bi.leaf)
 702             {
 703                 bi.ucs4 = ai.ucs4;
 704                 FcCharSetIterSet (b, &bi);
 705             }
 706         }
 707     }
 708     return count;
 709 }
 710
 711 /*
 712  * return FcTrue iff a is a subset of b
 713  */
 714 FcBool
 715 FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
 716 {
 717     int         ai, bi;
 718     FcChar16    an, bn;
 719
 720     if (a == b)
 721         return FcTrue;
 722     if (!a || !b)
 723         return FcFalse;
 724     bi = 0;
 725     ai = 0;
 726     while (ai < a->num && bi < b->num)
 727     {
 728         an = FcCharSetNumbers(a)[ai];
 729         bn = FcCharSetNumbers(b)[bi];
 730         /*
 731          * Check matching pages
 732          */
 733         if (an == bn)
 734         {
 735             FcChar32    *am = FcCharSetLeaf(a, ai)->map;
 736             FcChar32    *bm = FcCharSetLeaf(b, bi)->map;
 737
 738             if (am != bm)
 739             {
 740                 int     i = 256/32;
 741                 /*
 742                  * Does am have any bits not in bm?
 743                  */
 744                 while (i--)
 745                     if (*am++ & ~*bm++)
 746                         return FcFalse;
 747             }
 748             ai++;
 749             bi++;
 750         }
 751         /*
 752          * Does a have any pages not in b?
 753          */
 754         else if (an < bn)
 755             return FcFalse;
 756         else
 757         {
 758             bi = FcCharSetFindLeafForward (b, bi + 1, an);
 759             if (bi < 0)
 760                 bi = -bi - 1;
 761         }
 762     }
 763     /*
 764      * did we look at every page?
 765      */
 766     return ai >= a->num;
 767 }
 768
 769 /*
 770  * These two functions efficiently walk the entire charmap for
 771  * other software (like pango) that want their own copy
 772  */
 773
 774 FcChar32
 775 FcCharSetNextPage (const FcCharSet  *a,
 776                    FcChar32         map[FC_CHARSET_MAP_SIZE],
 777                    FcChar32         *next)
 778 {
 779     FcCharSetIter   ai;
 780     FcChar32        page;
 781
 782     if (!a)
 783         return FC_CHARSET_DONE;
 784     ai.ucs4 = *next;
 785     FcCharSetIterSet (a, &ai);
 786     if (!ai.leaf)
 787         return FC_CHARSET_DONE;
 788
 789     /*
 790      * Save current information
 791      */
 792     page = ai.ucs4;
 793     memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
 794     /*
 795      * Step to next page
 796      */
 797     FcCharSetIterNext (a, &ai);
 798     *next = ai.ucs4;
 799
 800     return page;
 801 }
 802
 803 FcChar32
 804 FcCharSetFirstPage (const FcCharSet *a,
 805                     FcChar32        map[FC_CHARSET_MAP_SIZE],
 806                     FcChar32        *next)
 807 {
 808     *next = 0;
 809     return FcCharSetNextPage (a, map, next);
 810 }
 811
 812 /*
 813  * old coverage API, rather hard to use correctly
 814  */
 815
 816 FcChar32
 817 FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
 818 {
 819     FcCharSetIter   ai;
 820
 821     ai.ucs4 = page;
 822     FcCharSetIterSet (a, &ai);
 823     if (!ai.leaf)
 824     {
 825         memset (result, '\0', 256 / 8);
 826         page = 0;
 827     }
 828     else
 829     {
 830         memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
 831         FcCharSetIterNext (a, &ai);
 832         page = ai.ucs4;
 833     }
 834     return page;
 835 }
 836
 837 static FcBool
 838 FcNameParseRange (FcChar8 **string, FcChar32 *pfirst, FcChar32 *plast)
 839 {
 840         char *s = (char *) *string;
 841         char *t;
 842         long first, last;
 843
 844         while (isspace((unsigned char) *s))
 845             s++;
 846         t = s;
 847         errno = 0;
 848         first = last = strtol (s, &s, 16);
 849         if (errno)
 850             return FcFalse;
 851         while (isspace((unsigned char) *s))
 852             s++;
 853         if (*s == '-')
 854         {
 855             s++;
 856             errno = 0;
 857             last = strtol (s, &s, 16);
 858             if (errno)
 859                 return FcFalse;
 860         }
 861
 862         if (s == t || first < 0 || last < 0 || last < first || last > 0x10ffff)
 863              return FcFalse;
 864
 865         *string = (FcChar8 *) s;
 866         *pfirst = first;
 867         *plast = last;
 868         return FcTrue;
 869 }
 870
 871 FcCharSet *
 872 FcNameParseCharSet (FcChar8 *string)
 873 {
 874     FcCharSet   *c;
 875     FcChar32    first, last;
 876
 877     c = FcCharSetCreate ();
 878     if (!c)
 879         goto bail0;
 880     while (*string)
 881     {
 882         FcChar32 u;
 883
 884         if (!FcNameParseRange (&string, &first, &last))
 885                 goto bail1;
 886
 887         for (u = first; u < last + 1; u++)
 888             FcCharSetAddChar (c, u);
 889     }
 890     return c;
 891 bail1:
 892     FcCharSetDestroy (c);
 893 bail0:
 894     return NULL;
 895 }
 896
 897 static void
 898 FcNameUnparseUnicode (FcStrBuf *buf, FcChar32 u)
 899 {
 900     FcChar8         buf_static[64];
 901     snprintf ((char *) buf_static, sizeof (buf_static), "%x", u);
 902     FcStrBufString (buf, buf_static);
 903 }
 904
 905 FcBool
 906 FcNameUnparseCharSet (FcStrBuf *buf, const FcCharSet *c)
 907 {
 908     FcCharSetIter   ci;
 909     FcChar32        first, last;
 910     int             i;
 911 #ifdef CHECK
 912     int             len = buf->len;
 913 #endif
 914
 915     first = last = 0x7FFFFFFF;
 916
 917     for (FcCharSetIterStart (c, &ci);
 918          ci.leaf;
 919          FcCharSetIterNext (c, &ci))
 920     {
 921         for (i = 0; i < 256/32; i++)
 922         {
 923             FcChar32 bits = ci.leaf->map[i];
 924             FcChar32 u = ci.ucs4 + i * 32;
 925
 926             while (bits)
 927             {
 928                 if (bits & 1)
 929                 {
 930                         if (u != last + 1)
 931                         {
 932                             if (last != first)
 933                             {
 934                                 FcStrBufChar (buf, '-');
 935                                 FcNameUnparseUnicode (buf, last);
 936                             }
 937                             if (last != 0x7FFFFFFF)
 938                                 FcStrBufChar (buf, ' ');
 939                             /* Start new range. */
 940                             first = u;
 941                             FcNameUnparseUnicode (buf, u);
 942                         }
 943                         last = u;
 944                 }
 945                 bits >>= 1;
 946                 u++;
 947             }
 948         }
 949     }
 950     if (last != first)
 951     {
 952         FcStrBufChar (buf, '-');
 953         FcNameUnparseUnicode (buf, last);
 954     }
 955 #ifdef CHECK
 956     {
 957         FcCharSet       *check;
 958         FcChar32        missing;
 959         FcCharSetIter   ci, checki;
 960
 961         /* null terminate for parser */
 962         FcStrBufChar (buf, '\0');
 963         /* step back over null for life after test */
 964         buf->len--;
 965         check = FcNameParseCharSet (buf->buf + len);
 966         FcCharSetIterStart (c, &ci);
 967         FcCharSetIterStart (check, &checki);
 968         while (ci.leaf || checki.leaf)
 969         {
 970             if (ci.ucs4 < checki.ucs4)
 971             {
 972                 printf ("Missing leaf node at 0x%x\n", ci.ucs4);
 973                 FcCharSetIterNext (c, &ci);
 974             }
 975             else if (checki.ucs4 < ci.ucs4)
 976             {
 977                 printf ("Extra leaf node at 0x%x\n", checki.ucs4);
 978                 FcCharSetIterNext (check, &checki);
 979             }
 980             else
 981             {
 982                 int         i = 256/32;
 983                 FcChar32    *cm = ci.leaf->map;
 984                 FcChar32    *checkm = checki.leaf->map;
 985
 986                 for (i = 0; i < 256; i += 32)
 987                 {
 988                     if (*cm != *checkm)
 989                         printf ("Mismatching sets at 0x%08x: 0x%08x != 0x%08x\n",
 990                                 ci.ucs4 + i, *cm, *checkm);
 991                     cm++;
 992                     checkm++;
 993                 }
 994                 FcCharSetIterNext (c, &ci);
 995                 FcCharSetIterNext (check, &checki);
 996             }
 997         }
 998         if ((missing = FcCharSetSubtractCount (c, check)))
 999             printf ("%d missing in reparsed result\n", missing);
1000         if ((missing = FcCharSetSubtractCount (check, c)))
1001             printf ("%d extra in reparsed result\n", missing);
1002         FcCharSetDestroy (check);
1003     }
1004 #endif
1005
1006     return FcTrue;
1007 }
1008
1009 typedef struct _FcCharLeafEnt FcCharLeafEnt;
1010
1011 struct _FcCharLeafEnt {
1012     FcCharLeafEnt   *next;
1013     FcChar32        hash;
1014     FcCharLeaf      leaf;
1015 };
1016
1017 #define FC_CHAR_LEAF_BLOCK      (4096 / sizeof (FcCharLeafEnt))
1018 #define FC_CHAR_LEAF_HASH_SIZE  257
1019
1020 typedef struct _FcCharSetEnt FcCharSetEnt;
1021
1022 struct _FcCharSetEnt {
1023     FcCharSetEnt        *next;
1024     FcChar32            hash;
1025     FcCharSet           set;
1026 };
1027
1028 typedef struct _FcCharSetOrigEnt FcCharSetOrigEnt;
1029
1030 struct _FcCharSetOrigEnt {
1031     FcCharSetOrigEnt    *next;
1032     const FcCharSet     *orig;
1033     const FcCharSet     *frozen;
1034 };
1035
1036 #define FC_CHAR_SET_HASH_SIZE    67
1037
1038 struct _FcCharSetFreezer {
1039     FcCharLeafEnt   *leaf_hash_table[FC_CHAR_LEAF_HASH_SIZE];
1040     FcCharLeafEnt   **leaf_blocks;
1041     int             leaf_block_count;
1042     FcCharSetEnt    *set_hash_table[FC_CHAR_SET_HASH_SIZE];
1043     FcCharSetOrigEnt    *orig_hash_table[FC_CHAR_SET_HASH_SIZE];
1044     FcCharLeafEnt   *current_block;
1045     int             leaf_remain;
1046     int             leaves_seen;
1047     int             charsets_seen;
1048     int             leaves_allocated;
1049     int             charsets_allocated;
1050 };
1051
1052 static FcCharLeafEnt *
1053 FcCharLeafEntCreate (FcCharSetFreezer *freezer)
1054 {
1055     if (!freezer->leaf_remain)
1056     {
1057         FcCharLeafEnt **newBlocks;
1058
1059         freezer->leaf_block_count++;
1060         newBlocks = realloc (freezer->leaf_blocks, freezer->leaf_block_count * sizeof (FcCharLeafEnt *));
1061         if (!newBlocks)
1062             return 0;
1063         freezer->leaf_blocks = newBlocks;
1064         freezer->current_block = freezer->leaf_blocks[freezer->leaf_block_count-1] = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
1065         if (!freezer->current_block)
1066             return 0;
1067         freezer->leaf_remain = FC_CHAR_LEAF_BLOCK;
1068     }
1069     freezer->leaf_remain--;
1070     freezer->leaves_allocated++;
1071     return freezer->current_block++;
1072 }
1073
1074 static FcChar32
1075 FcCharLeafHash (FcCharLeaf *leaf)
1076 {
1077     FcChar32    hash = 0;
1078     int         i;
1079
1080     for (i = 0; i < 256/32; i++)
1081         hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
1082     return hash;
1083 }
1084
1085 static FcCharLeaf *
1086 FcCharSetFreezeLeaf (FcCharSetFreezer *freezer, FcCharLeaf *leaf)
1087 {
1088     FcChar32                    hash = FcCharLeafHash (leaf);
1089     FcCharLeafEnt               **bucket = &freezer->leaf_hash_table[hash % FC_CHAR_LEAF_HASH_SIZE];
1090     FcCharLeafEnt               *ent;
1091
1092     for (ent = *bucket; ent; ent = ent->next)
1093     {
1094         if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
1095             return &ent->leaf;
1096     }
1097
1098     ent = FcCharLeafEntCreate(freezer);
1099     if (!ent)
1100         return 0;
1101     ent->leaf = *leaf;
1102     ent->hash = hash;
1103     ent->next = *bucket;
1104     *bucket = ent;
1105     return &ent->leaf;
1106 }
1107
1108 static FcChar32
1109 FcCharSetHash (FcCharSet *fcs)
1110 {
1111     FcChar32    hash = 0;
1112     int         i;
1113
1114     /* hash in leaves */
1115     for (i = 0; i < fcs->num; i++)
1116         hash = ((hash << 1) | (hash >> 31)) ^ FcCharLeafHash (FcCharSetLeaf(fcs,i));
1117     /* hash in numbers */
1118     for (i = 0; i < fcs->num; i++)
1119         hash = ((hash << 1) | (hash >> 31)) ^ FcCharSetNumbers(fcs)[i];
1120     return hash;
1121 }
1122
1123 static FcBool
1124 FcCharSetFreezeOrig (FcCharSetFreezer *freezer, const FcCharSet *orig, const FcCharSet *frozen)
1125 {
1126     FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) % FC_CHAR_SET_HASH_SIZE];
1127     FcCharSetOrigEnt    *ent;
1128
1129     ent = malloc (sizeof (FcCharSetOrigEnt));
1130     if (!ent)
1131         return FcFalse;
1132     ent->orig = orig;
1133     ent->frozen = frozen;
1134     ent->next = *bucket;
1135     *bucket = ent;
1136     return FcTrue;
1137 }
1138
1139 static FcCharSet *
1140 FcCharSetFreezeBase (FcCharSetFreezer *freezer, FcCharSet *fcs)
1141 {
1142     FcChar32            hash = FcCharSetHash (fcs);
1143     FcCharSetEnt        **bucket = &freezer->set_hash_table[hash % FC_CHAR_SET_HASH_SIZE];
1144     FcCharSetEnt        *ent;
1145     int                 size;
1146     int                 i;
1147
1148     for (ent = *bucket; ent; ent = ent->next)
1149     {
1150         if (ent->hash == hash &&
1151             ent->set.num == fcs->num &&
1152             !memcmp (FcCharSetNumbers(&ent->set),
1153                      FcCharSetNumbers(fcs),
1154                      fcs->num * sizeof (FcChar16)))
1155         {
1156             FcBool ok = FcTrue;
1157             int i;
1158
1159             for (i = 0; i < fcs->num; i++)
1160                 if (FcCharSetLeaf(&ent->set, i) != FcCharSetLeaf(fcs, i))
1161                     ok = FcFalse;
1162             if (ok)
1163                 return &ent->set;
1164         }
1165     }
1166
1167     size = (sizeof (FcCharSetEnt) +
1168             fcs->num * sizeof (FcCharLeaf *) +
1169             fcs->num * sizeof (FcChar16));
1170     ent = malloc (size);
1171     if (!ent)
1172         return 0;
1173
1174     freezer->charsets_allocated++;
1175
1176     FcRefSetConst (&ent->set.ref);
1177     ent->set.num = fcs->num;
1178     if (fcs->num)
1179     {
1180         intptr_t    *ent_leaves;
1181
1182         ent->set.leaves_offset = sizeof (ent->set);
1183         ent->set.numbers_offset = (ent->set.leaves_offset +
1184                                    fcs->num * sizeof (intptr_t));
1185
1186         ent_leaves = FcCharSetLeaves (&ent->set);
1187         for (i = 0; i < fcs->num; i++)
1188             ent_leaves[i] = FcPtrToOffset (ent_leaves,
1189                                            FcCharSetLeaf (fcs, i));
1190         memcpy (FcCharSetNumbers (&ent->set),
1191                 FcCharSetNumbers (fcs),
1192                 fcs->num * sizeof (FcChar16));
1193     }
1194     else
1195     {
1196         ent->set.leaves_offset = 0;
1197         ent->set.numbers_offset = 0;
1198     }
1199
1200     ent->hash = hash;
1201     ent->next = *bucket;
1202     *bucket = ent;
1203
1204     return &ent->set;
1205 }
1206
1207 static const FcCharSet *
1208 FcCharSetFindFrozen (FcCharSetFreezer *freezer, const FcCharSet *orig)
1209 {
1210     FcCharSetOrigEnt    **bucket = &freezer->orig_hash_table[((uintptr_t) orig) % FC_CHAR_SET_HASH_SIZE];
1211     FcCharSetOrigEnt    *ent;
1212
1213     for (ent = *bucket; ent; ent = ent->next)
1214         if (ent->orig == orig)
1215             return ent->frozen;
1216     return NULL;
1217 }
1218
1219 const FcCharSet *
1220 FcCharSetFreeze (FcCharSetFreezer *freezer, const FcCharSet *fcs)
1221 {
1222     FcCharSet       *b;
1223     const FcCharSet *n = 0;
1224     FcCharLeaf      *l;
1225     int             i;
1226
1227     b = FcCharSetCreate ();
1228     if (!b)
1229         goto bail0;
1230     for (i = 0; i < fcs->num; i++)
1231     {
1232         l = FcCharSetFreezeLeaf (freezer, FcCharSetLeaf(fcs, i));
1233         if (!l)
1234             goto bail1;
1235         if (!FcCharSetInsertLeaf (b, FcCharSetNumbers(fcs)[i] << 8, l))
1236             goto bail1;
1237     }
1238     n = FcCharSetFreezeBase (freezer, b);
1239     if (!FcCharSetFreezeOrig (freezer, fcs, n))
1240     {
1241         n = NULL;
1242         goto bail1;
1243     }
1244     freezer->charsets_seen++;
1245     freezer->leaves_seen += fcs->num;
1246 bail1:
1247     if (b->num)
1248         free (FcCharSetLeaves (b));
1249     if (b->num)
1250         free (FcCharSetNumbers (b));
1251     free (b);
1252 bail0:
1253     return n;
1254 }
1255
1256 FcCharSetFreezer *
1257 FcCharSetFreezerCreate (void)
1258 {
1259     FcCharSetFreezer    *freezer;
1260
1261     freezer = calloc (1, sizeof (FcCharSetFreezer));
1262     return freezer;
1263 }
1264
1265 void
1266 FcCharSetFreezerDestroy (FcCharSetFreezer *freezer)
1267 {
1268     int i;
1269
1270     if (FcDebug() & FC_DBG_CACHE)
1271     {
1272         printf ("\ncharsets %d -> %d leaves %d -> %d\n",
1273                 freezer->charsets_seen, freezer->charsets_allocated,
1274                 freezer->leaves_seen, freezer->leaves_allocated);
1275     }
1276     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1277     {
1278         FcCharSetEnt    *ent, *next;
1279         for (ent = freezer->set_hash_table[i]; ent; ent = next)
1280         {
1281             next = ent->next;
1282             free (ent);
1283         }
1284     }
1285
1286     for (i = 0; i < FC_CHAR_SET_HASH_SIZE; i++)
1287     {
1288         FcCharSetOrigEnt        *ent, *next;
1289         for (ent = freezer->orig_hash_table[i]; ent; ent = next)
1290         {
1291             next = ent->next;
1292             free (ent);
1293         }
1294     }
1295
1296     for (i = 0; i < freezer->leaf_block_count; i++)
1297         free (freezer->leaf_blocks[i]);
1298
1299     free (freezer->leaf_blocks);
1300     free (freezer);
1301 }
1302
1303 FcBool
1304 FcCharSetSerializeAlloc (FcSerialize *serialize, const FcCharSet *cs)
1305 {
1306     intptr_t        *leaves;
1307     FcChar16        *numbers;
1308     int             i;
1309
1310     if (!FcRefIsConst (&cs->ref))
1311     {
1312         if (!serialize->cs_freezer)
1313         {
1314             serialize->cs_freezer = FcCharSetFreezerCreate ();
1315             if (!serialize->cs_freezer)
1316                 return FcFalse;
1317         }
1318         if (FcCharSetFindFrozen (serialize->cs_freezer, cs))
1319             return FcTrue;
1320
1321         cs = FcCharSetFreeze (serialize->cs_freezer, cs);
1322     }
1323
1324     leaves = FcCharSetLeaves (cs);
1325     numbers = FcCharSetNumbers (cs);
1326
1327     if (!FcSerializeAlloc (serialize, cs, sizeof (FcCharSet)))
1328         return FcFalse;
1329     if (!FcSerializeAlloc (serialize, leaves, cs->num * sizeof (intptr_t)))
1330         return FcFalse;
1331     if (!FcSerializeAlloc (serialize, numbers, cs->num * sizeof (FcChar16)))
1332         return FcFalse;
1333     for (i = 0; i < cs->num; i++)
1334         if (!FcSerializeAlloc (serialize, FcCharSetLeaf(cs, i),
1335                                sizeof (FcCharLeaf)))
1336             return FcFalse;
1337     return FcTrue;
1338 }
1339
1340 FcCharSet *
1341 FcCharSetSerialize(FcSerialize *serialize, const FcCharSet *cs)
1342 {
1343     FcCharSet   *cs_serialized;
1344     intptr_t    *leaves, *leaves_serialized;
1345     FcChar16    *numbers, *numbers_serialized;
1346     FcCharLeaf  *leaf, *leaf_serialized;
1347     int         i;
1348
1349     if (!FcRefIsConst (&cs->ref) && serialize->cs_freezer)
1350     {
1351         cs = FcCharSetFindFrozen (serialize->cs_freezer, cs);
1352         if (!cs)
1353             return NULL;
1354     }
1355
1356     cs_serialized = FcSerializePtr (serialize, cs);
1357     if (!cs_serialized)
1358         return NULL;
1359
1360     FcRefSetConst (&cs_serialized->ref);
1361     cs_serialized->num = cs->num;
1362
1363     if (cs->num)
1364     {
1365         leaves = FcCharSetLeaves (cs);
1366         leaves_serialized = FcSerializePtr (serialize, leaves);
1367         if (!leaves_serialized)
1368             return NULL;
1369
1370         cs_serialized->leaves_offset = FcPtrToOffset (cs_serialized,
1371                                                       leaves_serialized);
1372
1373         numbers = FcCharSetNumbers (cs);
1374         numbers_serialized = FcSerializePtr (serialize, numbers);
1375         if (!numbers)
1376             return NULL;
1377
1378         cs_serialized->numbers_offset = FcPtrToOffset (cs_serialized,
1379                                                        numbers_serialized);
1380
1381         for (i = 0; i < cs->num; i++)
1382         {
1383             leaf = FcCharSetLeaf (cs, i);
1384             leaf_serialized = FcSerializePtr (serialize, leaf);
1385             if (!leaf_serialized)
1386                 return NULL;
1387             *leaf_serialized = *leaf;
1388             leaves_serialized[i] = FcPtrToOffset (leaves_serialized,
1389                                                   leaf_serialized);
1390             numbers_serialized[i] = numbers[i];
1391         }
1392     }
1393     else
1394     {
1395         cs_serialized->leaves_offset = 0;
1396         cs_serialized->numbers_offset = 0;
1397     }
1398
1399     return cs_serialized;
1400 }
1401 #define __fccharset__
1402 #include "fcaliastail.h"
1403 #undef __fccharset__