fclang.c revision 953daeba 
1/*
2 * fontconfig/src/fclang.c
3 *
4 * Copyright © 2002 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 "fcftint.h"
27
28/* Objects MT-safe for readonly access. */
29
30typedef struct {
31    const FcChar8    	lang[8];
32    const FcCharSet	charset;
33} FcLangCharSet;
34
35typedef struct {
36    int begin;
37    int end;
38} FcLangCharSetRange;
39
40#include "../fc-lang/fclang.h"
41
42struct _FcLangSet {
43    FcStrSet	*extra;
44    FcChar32    map_size;
45    FcChar32	map[NUM_LANG_SET_MAP];
46};
47
48static int FcLangSetIndex (const FcChar8 *lang);
49
50
51static void
52FcLangSetBitSet (FcLangSet    *ls,
53		 unsigned int  id)
54{
55  unsigned int bucket;
56
57  id = fcLangCharSetIndices[id];
58  bucket = id >> 5;
59  if (bucket >= ls->map_size)
60    return; /* shouldn't happen really */
61
62  ls->map[bucket] |= ((FcChar32) 1 << (id & 0x1f));
63}
64
65static FcBool
66FcLangSetBitGet (const FcLangSet *ls,
67		 unsigned int     id)
68{
69  unsigned int bucket;
70
71  id = fcLangCharSetIndices[id];
72  bucket = id >> 5;
73  if (bucket >= ls->map_size)
74    return FcFalse;
75
76  return ((ls->map[bucket] >> (id & 0x1f)) & 1) ? FcTrue : FcFalse;
77}
78
79static void
80FcLangSetBitReset (FcLangSet    *ls,
81		   unsigned int  id)
82{
83  unsigned int bucket;
84
85  id = fcLangCharSetIndices[id];
86  bucket = id >> 5;
87  if (bucket >= ls->map_size)
88    return; /* shouldn't happen really */
89
90  ls->map[bucket] &= ~((FcChar32) 1 << (id & 0x1f));
91}
92
93FcLangSet *
94FcFreeTypeLangSet (const FcCharSet  *charset,
95		   const FcChar8    *exclusiveLang)
96{
97    int		    i, j;
98    FcChar32	    missing;
99    const FcCharSet *exclusiveCharset = 0;
100    FcLangSet	    *ls;
101
102    if (exclusiveLang)
103	exclusiveCharset = FcLangGetCharSet (exclusiveLang);
104    ls = FcLangSetCreate ();
105    if (!ls)
106	return 0;
107    if (FcDebug() & FC_DBG_LANGSET)
108    {
109	printf ("font charset");
110	FcCharSetPrint (charset);
111	printf ("\n");
112    }
113    for (i = 0; i < NUM_LANG_CHAR_SET; i++)
114    {
115	if (FcDebug() & FC_DBG_LANGSET)
116	{
117	    printf ("%s charset", fcLangCharSets[i].lang);
118	    FcCharSetPrint (&fcLangCharSets[i].charset);
119	    printf ("\n");
120	}
121
122	/*
123	 * Check for Han charsets to make fonts
124	 * which advertise support for a single language
125	 * not support other Han languages
126	 */
127	if (exclusiveCharset &&
128	    FcFreeTypeIsExclusiveLang (fcLangCharSets[i].lang))
129	{
130	    if (fcLangCharSets[i].charset.num != exclusiveCharset->num)
131		continue;
132
133	    for (j = 0; j < fcLangCharSets[i].charset.num; j++)
134		if (FcCharSetLeaf(&fcLangCharSets[i].charset, j) !=
135		    FcCharSetLeaf(exclusiveCharset, j))
136		    continue;
137	}
138	missing = FcCharSetSubtractCount (&fcLangCharSets[i].charset, charset);
139        if (FcDebug() & FC_DBG_SCANV)
140	{
141	    if (missing && missing < 10)
142	    {
143		FcCharSet   *missed = FcCharSetSubtract (&fcLangCharSets[i].charset,
144							 charset);
145		FcChar32    ucs4;
146		FcChar32    map[FC_CHARSET_MAP_SIZE];
147		FcChar32    next;
148
149		printf ("\n%s(%u) ", fcLangCharSets[i].lang, missing);
150		printf ("{");
151		for (ucs4 = FcCharSetFirstPage (missed, map, &next);
152		     ucs4 != FC_CHARSET_DONE;
153		     ucs4 = FcCharSetNextPage (missed, map, &next))
154		{
155		    int	    i, j;
156		    for (i = 0; i < FC_CHARSET_MAP_SIZE; i++)
157			if (map[i])
158			{
159			    for (j = 0; j < 32; j++)
160				if (map[i] & (1 << j))
161				    printf (" %04x", ucs4 + i * 32 + j);
162			}
163		}
164		printf (" }\n\t");
165		FcCharSetDestroy (missed);
166	    }
167	    else
168		printf ("%s(%u) ", fcLangCharSets[i].lang, missing);
169	}
170	if (!missing)
171	    FcLangSetBitSet (ls, i);
172    }
173
174    if (FcDebug() & FC_DBG_SCANV)
175	printf ("\n");
176
177
178    return ls;
179}
180
181FcChar8 *
182FcLangNormalize (const FcChar8 *lang)
183{
184    FcChar8 *result = NULL, *s, *orig;
185    char *territory, *encoding, *modifier;
186    size_t llen, tlen = 0, mlen = 0;
187
188    if (!lang || !*lang)
189	return NULL;
190
191    if (FcStrCmpIgnoreCase (lang, (const FcChar8 *)"C") == 0 ||
192	FcStrCmpIgnoreCase (lang, (const FcChar8 *)"C.UTF-8") == 0 ||
193	FcStrCmpIgnoreCase (lang, (const FcChar8 *)"C.utf8") == 0 ||
194	FcStrCmpIgnoreCase (lang, (const FcChar8 *)"POSIX") == 0)
195    {
196	result = FcStrCopy ((const FcChar8 *)"en");
197	goto bail;
198    }
199
200    s = FcStrCopy (lang);
201    if (!s)
202	goto bail;
203
204    /* from the comments in glibc:
205     *
206     * LOCALE can consist of up to four recognized parts for the XPG syntax:
207     *
208     *            language[_territory[.codeset]][@modifier]
209     *
210     * Beside the first all of them are allowed to be missing.  If the
211     * full specified locale is not found, the less specific one are
212     * looked for.  The various part will be stripped off according to
213     * the following order:
214     *            (1) codeset
215     *            (2) normalized codeset
216     *            (3) territory
217     *            (4) modifier
218     *
219     * So since we don't take care of the codeset part here, what patterns
220     * we need to deal with is:
221     *
222     *   1. language_territory@modifier
223     *   2. language@modifier
224     *   3. language
225     *
226     * then. and maybe no need to try language_territory here.
227     */
228    modifier = strchr ((const char *) s, '@');
229    if (modifier)
230    {
231	*modifier = 0;
232	modifier++;
233	mlen = strlen (modifier);
234    }
235    encoding = strchr ((const char *) s, '.');
236    if (encoding)
237    {
238	*encoding = 0;
239	encoding++;
240	if (modifier)
241	{
242	    memmove (encoding, modifier, mlen + 1);
243	    modifier = encoding;
244	}
245    }
246    territory = strchr ((const char *) s, '_');
247    if (!territory)
248	territory = strchr ((const char *) s, '-');
249    if (territory)
250    {
251	*territory = 0;
252	territory++;
253	tlen = strlen (territory);
254    }
255    llen = strlen ((const char *) s);
256    if (llen < 2 || llen > 3)
257    {
258	fprintf (stderr, "Fontconfig warning: ignoring %s: not a valid language tag\n",
259		 lang);
260	goto bail0;
261    }
262    if (territory && (tlen < 2 || tlen > 3))
263    {
264	fprintf (stderr, "Fontconfig warning: ignoring %s: not a valid region tag\n",
265		 lang);
266	goto bail0;
267    }
268    if (territory)
269	territory[-1] = '-';
270    if (modifier)
271	modifier[-1] = '@';
272    orig = FcStrDowncase (s);
273    if (!orig)
274	goto bail0;
275    if (territory)
276    {
277	if (FcDebug () & FC_DBG_LANGSET)
278	    printf("Checking the existence of %s.orth\n", s);
279	if (FcLangSetIndex (s) < 0)
280	{
281	    memmove (territory - 1, territory + tlen, (mlen > 0 ? mlen + 1 : 0) + 1);
282	    if (modifier)
283		modifier = territory;
284	}
285	else
286	{
287	    result = s;
288	    /* we'll miss the opportunity to reduce the correct size
289	     * of the allocated memory for the string after that.
290	     */
291	    s = NULL;
292	    goto bail1;
293	}
294    }
295    if (modifier)
296    {
297	if (FcDebug () & FC_DBG_LANGSET)
298	    printf("Checking the existence of %s.orth\n", s);
299	if (FcLangSetIndex (s) < 0)
300	    modifier[-1] = 0;
301	else
302	{
303	    result = s;
304	    /* we'll miss the opportunity to reduce the correct size
305	     * of the allocated memory for the string after that.
306	     */
307	    s = NULL;
308	    goto bail1;
309	}
310    }
311    if (FcDebug () & FC_DBG_LANGSET)
312	printf("Checking the existence of %s.orth\n", s);
313    if (FcLangSetIndex (s) < 0)
314    {
315	/* there seems no languages matched in orth.
316	 * add the language as is for fallback.
317	 */
318	result = orig;
319	orig = NULL;
320    }
321    else
322    {
323	result = s;
324	/* we'll miss the opportunity to reduce the correct size
325	 * of the allocated memory for the string after that.
326	 */
327	s = NULL;
328    }
329  bail1:
330    if (orig)
331	FcStrFree (orig);
332  bail0:
333    if (s)
334	free (s);
335  bail:
336    if (FcDebug () & FC_DBG_LANGSET)
337    {
338	if (result)
339	    printf ("normalized: %s -> %s\n", lang, result);
340	else
341	    printf ("Unable to normalize %s\n", lang);
342    }
343
344    return result;
345}
346
347#define FcLangEnd(c)	((c) == '-' || (c) == '\0')
348
349FcLangResult
350FcLangCompare (const FcChar8 *s1, const FcChar8 *s2)
351{
352    FcChar8	    c1, c2;
353    FcLangResult    result = FcLangDifferentLang;
354
355    for (;;)
356    {
357	c1 = *s1++;
358	c2 = *s2++;
359
360	c1 = FcToLower (c1);
361	c2 = FcToLower (c2);
362	if (c1 != c2)
363	{
364	    if (FcLangEnd (c1) && FcLangEnd (c2))
365		result = FcLangDifferentTerritory;
366	    return result;
367	}
368	else if (!c1)
369	    return FcLangEqual;
370	else if (c1 == '-')
371	    result = FcLangDifferentTerritory;
372    }
373}
374
375/*
376 * Return FcTrue when super contains sub.
377 *
378 * super contains sub if super and sub have the same
379 * language and either the same country or one
380 * is missing the country
381 */
382
383static FcBool
384FcLangContains (const FcChar8 *super, const FcChar8 *sub)
385{
386    FcChar8	    c1, c2;
387
388    for (;;)
389    {
390	c1 = *super++;
391	c2 = *sub++;
392
393	c1 = FcToLower (c1);
394	c2 = FcToLower (c2);
395	if (c1 != c2)
396	{
397	    /* see if super has a country while sub is mising one */
398	    if (c1 == '-' && c2 == '\0')
399		return FcTrue;
400	    /* see if sub has a country while super is mising one */
401	    if (c1 == '\0' && c2 == '-')
402		return FcTrue;
403	    return FcFalse;
404	}
405	else if (!c1)
406	    return FcTrue;
407    }
408}
409
410const FcCharSet *
411FcLangGetCharSet (const FcChar8 *lang)
412{
413    int		i;
414    int		country = -1;
415
416    for (i = 0; i < NUM_LANG_CHAR_SET; i++)
417    {
418	switch (FcLangCompare (lang, fcLangCharSets[i].lang)) {
419	case FcLangEqual:
420	    return &fcLangCharSets[i].charset;
421	case FcLangDifferentTerritory:
422	    if (country == -1)
423		country = i;
424	case FcLangDifferentLang:
425	default:
426	    break;
427	}
428    }
429    if (country == -1)
430	return 0;
431    return &fcLangCharSets[country].charset;
432}
433
434FcStrSet *
435FcGetLangs (void)
436{
437    FcStrSet *langs;
438    int	i;
439
440    langs = FcStrSetCreate();
441    if (!langs)
442	return 0;
443
444    for (i = 0; i < NUM_LANG_CHAR_SET; i++)
445	FcStrSetAdd (langs, fcLangCharSets[i].lang);
446
447    return langs;
448}
449
450FcLangSet *
451FcLangSetCreate (void)
452{
453    FcLangSet	*ls;
454
455    ls = malloc (sizeof (FcLangSet));
456    if (!ls)
457	return 0;
458    memset (ls->map, '\0', sizeof (ls->map));
459    ls->map_size = NUM_LANG_SET_MAP;
460    ls->extra = 0;
461    return ls;
462}
463
464void
465FcLangSetDestroy (FcLangSet *ls)
466{
467    if (ls->extra)
468	FcStrSetDestroy (ls->extra);
469    free (ls);
470}
471
472FcLangSet *
473FcLangSetCopy (const FcLangSet *ls)
474{
475    FcLangSet	*new;
476
477    new = FcLangSetCreate ();
478    if (!new)
479	goto bail0;
480    memset (new->map, '\0', sizeof (new->map));
481    memcpy (new->map, ls->map, FC_MIN (sizeof (new->map), ls->map_size * sizeof (ls->map[0])));
482    if (ls->extra)
483    {
484	FcStrList	*list;
485	FcChar8		*extra;
486
487	new->extra = FcStrSetCreate ();
488	if (!new->extra)
489	    goto bail1;
490
491	list = FcStrListCreate (ls->extra);
492	if (!list)
493	    goto bail1;
494
495	while ((extra = FcStrListNext (list)))
496	    if (!FcStrSetAdd (new->extra, extra))
497	    {
498		FcStrListDone (list);
499		goto bail1;
500	    }
501	FcStrListDone (list);
502    }
503    return new;
504bail1:
505    FcLangSetDestroy (new);
506bail0:
507    return 0;
508}
509
510/* When the language isn't found, the return value r is such that:
511 *  1) r < 0
512 *  2) -r -1 is the index of the first language in fcLangCharSets that comes
513 *     after the 'lang' argument in lexicographic order.
514 *
515 *  The -1 is necessary to avoid problems with language id 0 (otherwise, we
516 *  wouldn't be able to distinguish between “language found, id is 0” and
517 *  “language not found, sorts right before the language with id 0”).
518 */
519static int
520FcLangSetIndex (const FcChar8 *lang)
521{
522    int	    low, high, mid = 0;
523    int	    cmp = 0;
524    FcChar8 firstChar = FcToLower(lang[0]);
525    FcChar8 secondChar = firstChar ? FcToLower(lang[1]) : '\0';
526
527    if (firstChar < 'a')
528    {
529	low = 0;
530	high = fcLangCharSetRanges[0].begin;
531    }
532    else if(firstChar > 'z')
533    {
534	low = fcLangCharSetRanges[25].begin;
535	high = NUM_LANG_CHAR_SET - 1;
536    }
537    else
538    {
539	low = fcLangCharSetRanges[firstChar - 'a'].begin;
540	high = fcLangCharSetRanges[firstChar - 'a'].end;
541	/* no matches */
542	if (low > high)
543	    return -(low+1); /* one past next entry after where it would be */
544    }
545
546    while (low <= high)
547    {
548	mid = (high + low) >> 1;
549	if(fcLangCharSets[mid].lang[0] != firstChar)
550	    cmp = FcStrCmpIgnoreCase(fcLangCharSets[mid].lang, lang);
551	else
552	{   /* fast path for resolving 2-letter languages (by far the most common) after
553	     * finding the first char (probably already true because of the hash table) */
554	    cmp = fcLangCharSets[mid].lang[1] - secondChar;
555	    if (cmp == 0 &&
556		(fcLangCharSets[mid].lang[2] != '\0' ||
557		 lang[2] != '\0'))
558	    {
559		cmp = FcStrCmpIgnoreCase(fcLangCharSets[mid].lang+2,
560					 lang+2);
561	    }
562	}
563	if (cmp == 0)
564	    return mid;
565	if (cmp < 0)
566	    low = mid + 1;
567	else
568	    high = mid - 1;
569    }
570    if (cmp < 0)
571	mid++;
572    return -(mid + 1);
573}
574
575FcBool
576FcLangSetAdd (FcLangSet *ls, const FcChar8 *lang)
577{
578    int	    id;
579
580    id = FcLangSetIndex (lang);
581    if (id >= 0)
582    {
583	FcLangSetBitSet (ls, id);
584	return FcTrue;
585    }
586    if (!ls->extra)
587    {
588	ls->extra = FcStrSetCreate ();
589	if (!ls->extra)
590	    return FcFalse;
591    }
592    return FcStrSetAdd (ls->extra, lang);
593}
594
595FcBool
596FcLangSetDel (FcLangSet *ls, const FcChar8 *lang)
597{
598    int	id;
599
600    id = FcLangSetIndex (lang);
601    if (id >= 0)
602    {
603	FcLangSetBitReset (ls, id);
604    }
605    else if (ls->extra)
606    {
607	FcStrSetDel (ls->extra, lang);
608    }
609    return FcTrue;
610}
611
612FcLangResult
613FcLangSetHasLang (const FcLangSet *ls, const FcChar8 *lang)
614{
615    int		    id;
616    FcLangResult    best, r;
617    int		    i;
618
619    id = FcLangSetIndex (lang);
620    if (id < 0)
621	id = -id - 1;
622    else if (FcLangSetBitGet (ls, id))
623	return FcLangEqual;
624    best = FcLangDifferentLang;
625    for (i = id - 1; i >= 0; i--)
626    {
627	r = FcLangCompare (lang, fcLangCharSets[i].lang);
628	if (r == FcLangDifferentLang)
629	    break;
630	if (FcLangSetBitGet (ls, i) && r < best)
631	    best = r;
632    }
633    for (i = id; i < NUM_LANG_CHAR_SET; i++)
634    {
635	r = FcLangCompare (lang, fcLangCharSets[i].lang);
636	if (r == FcLangDifferentLang)
637	    break;
638	if (FcLangSetBitGet (ls, i) && r < best)
639	    best = r;
640    }
641    if (ls->extra)
642    {
643	FcStrList	*list = FcStrListCreate (ls->extra);
644	FcChar8		*extra;
645
646	if (list)
647	{
648	    while (best > FcLangEqual && (extra = FcStrListNext (list)))
649	    {
650		r = FcLangCompare (lang, extra);
651		if (r < best)
652		    best = r;
653	    }
654	    FcStrListDone (list);
655	}
656    }
657    return best;
658}
659
660static FcLangResult
661FcLangSetCompareStrSet (const FcLangSet *ls, FcStrSet *set)
662{
663    FcStrList	    *list = FcStrListCreate (set);
664    FcLangResult    r, best = FcLangDifferentLang;
665    FcChar8	    *extra;
666
667    if (list)
668    {
669	while (best > FcLangEqual && (extra = FcStrListNext (list)))
670	{
671	    r = FcLangSetHasLang (ls, extra);
672	    if (r < best)
673		best = r;
674	}
675	FcStrListDone (list);
676    }
677    return best;
678}
679
680FcLangResult
681FcLangSetCompare (const FcLangSet *lsa, const FcLangSet *lsb)
682{
683    int		    i, j, count;
684    FcLangResult    best, r;
685    FcChar32 aInCountrySet, bInCountrySet;
686
687    count = FC_MIN (lsa->map_size, lsb->map_size);
688    count = FC_MIN (NUM_LANG_SET_MAP, count);
689    for (i = 0; i < count; i++)
690	if (lsa->map[i] & lsb->map[i])
691	    return FcLangEqual;
692    best = FcLangDifferentLang;
693    for (j = 0; j < NUM_COUNTRY_SET; j++)
694    {
695	aInCountrySet = 0;
696	bInCountrySet = 0;
697
698	for (i = 0; i < count; i++)
699	{
700	    aInCountrySet |= lsa->map[i] & fcLangCountrySets[j][i];
701	    bInCountrySet |= lsb->map[i] & fcLangCountrySets[j][i];
702
703	    if (aInCountrySet && bInCountrySet)
704	    {
705		best = FcLangDifferentTerritory;
706		break;
707	    }
708	}
709    }
710    if (lsa->extra)
711    {
712	r = FcLangSetCompareStrSet (lsb, lsa->extra);
713	if (r < best)
714	    best = r;
715    }
716    if (best > FcLangEqual && lsb->extra)
717    {
718	r = FcLangSetCompareStrSet (lsa, lsb->extra);
719	if (r < best)
720	    best = r;
721    }
722    return best;
723}
724
725/*
726 * Used in computing values -- mustn't allocate any storage
727 */
728FcLangSet *
729FcLangSetPromote (const FcChar8 *lang, FcValuePromotionBuffer *vbuf)
730{
731    int		id;
732    typedef struct {
733	FcLangSet  ls;
734	FcStrSet   strs;
735	FcChar8   *str;
736    } FcLangSetPromotionBuffer;
737    FcLangSetPromotionBuffer *buf = (FcLangSetPromotionBuffer *) vbuf;
738
739    FC_ASSERT_STATIC (sizeof (FcLangSetPromotionBuffer) <= sizeof (FcValuePromotionBuffer));
740
741    memset (buf->ls.map, '\0', sizeof (buf->ls.map));
742    buf->ls.map_size = NUM_LANG_SET_MAP;
743    buf->ls.extra = 0;
744    if (lang)
745    {
746	id = FcLangSetIndex (lang);
747	if (id >= 0)
748	{
749	    FcLangSetBitSet (&buf->ls, id);
750	}
751	else
752	{
753	    buf->ls.extra = &buf->strs;
754	    buf->strs.num = 1;
755	    buf->strs.size = 1;
756	    buf->strs.strs = &buf->str;
757	    FcRefInit (&buf->strs.ref, 1);
758	    buf->str = (FcChar8 *) lang;
759	}
760    }
761    return &buf->ls;
762}
763
764FcChar32
765FcLangSetHash (const FcLangSet *ls)
766{
767    FcChar32	h = 0;
768    int		i, count;
769
770    count = FC_MIN (ls->map_size, NUM_LANG_SET_MAP);
771    for (i = 0; i < count; i++)
772	h ^= ls->map[i];
773    if (ls->extra)
774	h ^= ls->extra->num;
775    return h;
776}
777
778FcLangSet *
779FcNameParseLangSet (const FcChar8 *string)
780{
781    FcChar8	    lang[32], c = 0;
782    int i;
783    FcLangSet	    *ls;
784
785    ls = FcLangSetCreate ();
786    if (!ls)
787	goto bail0;
788
789    for(;;)
790    {
791	for(i = 0; i < 31;i++)
792	{
793	    c = *string++;
794	    if(c == '\0' || c == '|')
795		break; /* end of this code */
796	    lang[i] = c;
797	}
798	lang[i] = '\0';
799	if (!FcLangSetAdd (ls, lang))
800	    goto bail1;
801	if(c == '\0')
802	    break;
803    }
804    return ls;
805bail1:
806    FcLangSetDestroy (ls);
807bail0:
808    return 0;
809}
810
811FcBool
812FcNameUnparseLangSet (FcStrBuf *buf, const FcLangSet *ls)
813{
814    int		i, bit, count;
815    FcChar32	bits;
816    FcBool	first = FcTrue;
817
818    count = FC_MIN (ls->map_size, NUM_LANG_SET_MAP);
819    for (i = 0; i < count; i++)
820    {
821	if ((bits = ls->map[i]))
822	{
823	    for (bit = 0; bit <= 31; bit++)
824		if (bits & (1 << bit))
825		{
826		    int id = (i << 5) | bit;
827		    if (!first)
828			if (!FcStrBufChar (buf, '|'))
829			    return FcFalse;
830		    if (!FcStrBufString (buf, fcLangCharSets[fcLangCharSetIndicesInv[id]].lang))
831			return FcFalse;
832		    first = FcFalse;
833		}
834	}
835    }
836    if (ls->extra)
837    {
838	FcStrList   *list = FcStrListCreate (ls->extra);
839	FcChar8	    *extra;
840
841	if (!list)
842	    return FcFalse;
843	while ((extra = FcStrListNext (list)))
844	{
845	    if (!first)
846		if (!FcStrBufChar (buf, '|'))
847                {
848                    FcStrListDone (list);
849		    return FcFalse;
850                }
851	    if (!FcStrBufString (buf, extra))
852                {
853                    FcStrListDone (list);
854                    return FcFalse;
855                }
856	    first = FcFalse;
857	}
858        FcStrListDone (list);
859    }
860    return FcTrue;
861}
862
863FcBool
864FcLangSetEqual (const FcLangSet *lsa, const FcLangSet *lsb)
865{
866    int	    i, count;
867
868    count = FC_MIN (lsa->map_size, lsb->map_size);
869    count = FC_MIN (NUM_LANG_SET_MAP, count);
870    for (i = 0; i < count; i++)
871    {
872	if (lsa->map[i] != lsb->map[i])
873	    return FcFalse;
874    }
875    if (!lsa->extra && !lsb->extra)
876	return FcTrue;
877    if (lsa->extra && lsb->extra)
878	return FcStrSetEqual (lsa->extra, lsb->extra);
879    return FcFalse;
880}
881
882static FcBool
883FcLangSetContainsLang (const FcLangSet *ls, const FcChar8 *lang)
884{
885    int		    id;
886    int		    i;
887
888    id = FcLangSetIndex (lang);
889    if (id < 0)
890	id = -id - 1;
891    else if (FcLangSetBitGet (ls, id))
892	return FcTrue;
893    /*
894     * search up and down among equal languages for a match
895     */
896    for (i = id - 1; i >= 0; i--)
897    {
898	if (FcLangCompare (fcLangCharSets[i].lang, lang) == FcLangDifferentLang)
899	    break;
900	if (FcLangSetBitGet (ls, i) &&
901	    FcLangContains (fcLangCharSets[i].lang, lang))
902	    return FcTrue;
903    }
904    for (i = id; i < NUM_LANG_CHAR_SET; i++)
905    {
906	if (FcLangCompare (fcLangCharSets[i].lang, lang) == FcLangDifferentLang)
907	    break;
908	if (FcLangSetBitGet (ls, i) &&
909	    FcLangContains (fcLangCharSets[i].lang, lang))
910	    return FcTrue;
911    }
912    if (ls->extra)
913    {
914	FcStrList	*list = FcStrListCreate (ls->extra);
915	FcChar8		*extra;
916
917	if (list)
918	{
919	    while ((extra = FcStrListNext (list)))
920	    {
921		if (FcLangContains (extra, lang))
922		    break;
923	    }
924	    FcStrListDone (list);
925    	    if (extra)
926		return FcTrue;
927	}
928    }
929    return FcFalse;
930}
931
932/*
933 * return FcTrue if lsa contains every language in lsb
934 */
935FcBool
936FcLangSetContains (const FcLangSet *lsa, const FcLangSet *lsb)
937{
938    int		    i, j, count;
939    FcChar32	    missing;
940
941    if (FcDebug() & FC_DBG_MATCHV)
942    {
943	printf ("FcLangSet "); FcLangSetPrint (lsa);
944	printf (" contains "); FcLangSetPrint (lsb);
945	printf ("\n");
946    }
947    /*
948     * check bitmaps for missing language support
949     */
950    count = FC_MIN (lsa->map_size, lsb->map_size);
951    count = FC_MIN (NUM_LANG_SET_MAP, count);
952    for (i = 0; i < count; i++)
953    {
954	missing = lsb->map[i] & ~lsa->map[i];
955	if (missing)
956	{
957	    for (j = 0; j < 32; j++)
958		if (missing & (1 << j))
959		{
960		    if (!FcLangSetContainsLang (lsa,
961						fcLangCharSets[fcLangCharSetIndicesInv[i*32 + j]].lang))
962		    {
963			if (FcDebug() & FC_DBG_MATCHV)
964			    printf ("\tMissing bitmap %s\n", fcLangCharSets[fcLangCharSetIndicesInv[i*32+j]].lang);
965			return FcFalse;
966		    }
967		}
968	}
969    }
970    if (lsb->extra)
971    {
972	FcStrList   *list = FcStrListCreate (lsb->extra);
973	FcChar8	    *extra;
974
975	if (list)
976	{
977	    while ((extra = FcStrListNext (list)))
978	    {
979		if (!FcLangSetContainsLang (lsa, extra))
980		{
981		    if (FcDebug() & FC_DBG_MATCHV)
982			printf ("\tMissing string %s\n", extra);
983		    break;
984		}
985	    }
986	    FcStrListDone (list);
987	    if (extra)
988		return FcFalse;
989	}
990    }
991    return FcTrue;
992}
993
994FcBool
995FcLangSetSerializeAlloc (FcSerialize *serialize, const FcLangSet *l)
996{
997    if (!FcSerializeAlloc (serialize, l, sizeof (FcLangSet)))
998	return FcFalse;
999    return FcTrue;
1000}
1001
1002FcLangSet *
1003FcLangSetSerialize(FcSerialize *serialize, const FcLangSet *l)
1004{
1005    FcLangSet	*l_serialize = FcSerializePtr (serialize, l);
1006
1007    if (!l_serialize)
1008	return NULL;
1009    memset (l_serialize->map, '\0', sizeof (l_serialize->map));
1010    memcpy (l_serialize->map, l->map, FC_MIN (sizeof (l_serialize->map), l->map_size * sizeof (l->map[0])));
1011    l_serialize->map_size = NUM_LANG_SET_MAP;
1012    l_serialize->extra = NULL; /* We don't serialize ls->extra */
1013    return l_serialize;
1014}
1015
1016FcStrSet *
1017FcLangSetGetLangs (const FcLangSet *ls)
1018{
1019    FcStrSet *langs;
1020    int	      i;
1021
1022    langs = FcStrSetCreate();
1023    if (!langs)
1024	return 0;
1025
1026    for (i = 0; i < NUM_LANG_CHAR_SET; i++)
1027	if (FcLangSetBitGet (ls, i))
1028	    FcStrSetAdd (langs, fcLangCharSets[i].lang);
1029
1030    if (ls->extra)
1031    {
1032	FcStrList	*list = FcStrListCreate (ls->extra);
1033	FcChar8		*extra;
1034
1035	if (list)
1036	{
1037	    while ((extra = FcStrListNext (list)))
1038		FcStrSetAdd (langs, extra);
1039
1040	    FcStrListDone (list);
1041	}
1042    }
1043
1044    return langs;
1045}
1046
1047static FcLangSet *
1048FcLangSetOperate(const FcLangSet	*a,
1049		 const FcLangSet	*b,
1050		 FcBool			(*func) (FcLangSet 	*ls,
1051						 const FcChar8	*s))
1052{
1053    FcLangSet	*langset = FcLangSetCopy (a);
1054    FcStrSet	*set = FcLangSetGetLangs (b);
1055    FcStrList	*sl = FcStrListCreate (set);
1056    FcChar8	*str;
1057
1058    FcStrSetDestroy (set);
1059    while ((str = FcStrListNext (sl)))
1060    {
1061	func (langset, str);
1062    }
1063    FcStrListDone (sl);
1064
1065    return langset;
1066}
1067
1068FcLangSet *
1069FcLangSetUnion (const FcLangSet *a, const FcLangSet *b)
1070{
1071    return FcLangSetOperate(a, b, FcLangSetAdd);
1072}
1073
1074FcLangSet *
1075FcLangSetSubtract (const FcLangSet *a, const FcLangSet *b)
1076{
1077    return FcLangSetOperate(a, b, FcLangSetDel);
1078}
1079
1080#define __fclang__
1081#include "fcaliastail.h"
1082#include "fcftaliastail.h"
1083#undef __fclang__
1084