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