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