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__ 1404
Indexes created Sat Jul 04 00:25:45 UTC 2026