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