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