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__