]> git.wh0rd.org - fontconfig.git/blob - src/fccharset.c
git.wh0rd.org / fontconfig.git / blob
? search:


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