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