Add functionality to allow fontconfig data structure serialization.
[platform/upstream/fontconfig.git] / src / fclang.c
1 /*
2  * $RCSId: xc/lib/fontconfig/src/fclang.c,v 1.7 2002/08/26 23:34:31 keithp Exp $
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 Keith Packard not be used in
11  * advertising or publicity pertaining to distribution of the software without
12  * specific, written prior permission.  Keith Packard makes no
13  * representations about the suitability of this software for any purpose.  It
14  * is provided "as is" without express or implied warranty.
15  *
16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22  * PERFORMANCE OF THIS SOFTWARE.
23  */
24
25 #include <fcntl.h>
26 #include <sys/mman.h>
27 #include "fcint.h"
28
29 typedef struct {
30     FcChar8     *lang;
31     FcCharSet   charset;
32 } FcLangCharSet;
33
34 typedef struct {
35     int begin;
36     int end;
37 } FcLangCharSetRange;
38
39 #include "../fc-lang/fclang.h"
40
41 struct _FcLangSet {
42     FcChar32    map[NUM_LANG_SET_MAP];
43     FcStrSetPtr extra;
44 };
45
46 #define FcLangSetBitSet(ls, id) ((ls)->map[(id)>>5] |= ((FcChar32) 1 << ((id) & 0x1f)))
47 #define FcLangSetBitGet(ls, id) (((ls)->map[(id)>>5] >> ((id) & 0x1f)) & 1)
48
49 FcLangSet *
50 FcFreeTypeLangSet (const FcCharSet  *charset, 
51                    const FcChar8    *exclusiveLang)
52 {
53     int             i, j;
54     FcChar32        missing;
55     const FcCharSet *exclusiveCharset = 0;
56     FcLangSet       *ls;
57     
58
59     if (exclusiveLang)
60         exclusiveCharset = FcCharSetForLang (exclusiveLang);
61     ls = FcLangSetCreate ();
62     if (!ls)
63         return 0;
64     for (i = 0; i < NUM_LANG_CHAR_SET; i++)
65     {
66         /*
67          * Check for Han charsets to make fonts
68          * which advertise support for a single language
69          * not support other Han languages
70          */
71         if (exclusiveCharset &&
72             FcFreeTypeIsExclusiveLang (fcLangCharSets[i].lang))
73         {
74             if (fcLangCharSets[i].charset.num != exclusiveCharset->num)
75                 continue;
76
77             for (j = 0; j < fcLangCharSets[i].charset.num; j++)
78                 if (FcCharSetGetLeaf(&fcLangCharSets[i].charset, j) != 
79                     FcCharSetGetLeaf(exclusiveCharset, j))
80                     continue;
81         }
82         missing = FcCharSetSubtractCount (&fcLangCharSets[i].charset, charset);
83         if (FcDebug() & FC_DBG_SCANV)
84         {
85             if (missing && missing < 10)
86             {
87                 FcCharSet   *missed = FcCharSetSubtract (&fcLangCharSets[i].charset, 
88                                                          charset);
89                 FcChar32    ucs4;
90                 FcChar32    map[FC_CHARSET_MAP_SIZE];
91                 FcChar32    next;
92
93                 printf ("\n%s(%d) ", fcLangCharSets[i].lang, missing);
94                 printf ("{");
95                 for (ucs4 = FcCharSetFirstPage (missed, map, &next);
96                      ucs4 != FC_CHARSET_DONE;
97                      ucs4 = FcCharSetNextPage (missed, map, &next))
98                 {
99                     int     i, j;
100                     for (i = 0; i < FC_CHARSET_MAP_SIZE; i++)
101                         if (map[i])
102                         {
103                             for (j = 0; j < 32; j++)
104                                 if (map[i] & (1 << j))
105                                     printf (" %04x", ucs4 + i * 32 + j);
106                         }
107                 }
108                 printf (" }\n\t");
109                 FcCharSetDestroy (missed);
110             }
111             else
112                 printf ("%s(%d) ", fcLangCharSets[i].lang, missing);
113         }
114         if (!missing)
115             FcLangSetBitSet (ls, i);
116     }
117
118     if (FcDebug() & FC_DBG_SCANV)
119         printf ("\n");
120     
121     
122     return ls;
123 }
124
125 #define FcLangEnd(c)    ((c) == '-' || (c) == '\0')
126
127 FcLangResult
128 FcLangCompare (const FcChar8 *s1, const FcChar8 *s2)
129 {
130     FcChar8         c1, c2;
131     FcLangResult    result = FcLangDifferentLang;
132
133     for (;;)
134     {
135         c1 = *s1++;
136         c2 = *s2++;
137         
138         c1 = FcToLower (c1);
139         c2 = FcToLower (c2);
140         if (c1 != c2)
141         {
142             if (FcLangEnd (c1) && FcLangEnd (c2))
143                 result = FcLangDifferentCountry;
144             return result;
145         }
146         else if (!c1)
147             return FcLangEqual;
148         else if (c1 == '-')
149             result = FcLangDifferentCountry;
150     }
151 }
152
153 /*
154  * Return FcTrue when super contains sub. 
155  *
156  * super contains sub if super and sub have the same
157  * language and either the same country or one
158  * is missing the country
159  */
160
161 static FcBool
162 FcLangContains (const FcChar8 *super, const FcChar8 *sub)
163 {
164     FcChar8         c1, c2;
165
166     for (;;)
167     {
168         c1 = *super++;
169         c2 = *sub++;
170         
171         c1 = FcToLower (c1);
172         c2 = FcToLower (c2);
173         if (c1 != c2)
174         {
175             /* see if super has a country while sub is mising one */
176             if (c1 == '-' && c2 == '\0')
177                 return FcTrue;
178             /* see if sub has a country while super is mising one */
179             if (c1 == '\0' && c2 == '-')
180                 return FcTrue;
181             return FcFalse;
182         }
183         else if (!c1)
184             return FcTrue;
185     }
186 }
187
188 const FcCharSet *
189 FcCharSetForLang (const FcChar8 *lang)
190 {
191     int         i;
192     int         country = -1;
193     for (i = 0; i < NUM_LANG_CHAR_SET; i++)
194     {
195         switch (FcLangCompare (lang, fcLangCharSets[i].lang)) {
196         case FcLangEqual:
197             return &fcLangCharSets[i].charset;
198         case FcLangDifferentCountry:
199             if (country == -1)
200                 country = i;
201         default:
202             break;
203         }
204     }
205     if (country == -1)
206         return 0;
207     return &fcLangCharSets[i].charset;
208 }
209
210 FcLangSet *
211 FcLangSetCreate (void)
212 {
213     FcLangSet   *ls;
214
215     ls = malloc (sizeof (FcLangSet));
216     if (!ls)
217         return 0;
218     FcMemAlloc (FC_MEM_LANGSET, sizeof (FcLangSet));
219     memset (ls->map, '\0', sizeof (ls->map));
220     ls->extra = FcStrSetPtrCreateDynamic(0);
221     return ls;
222 }
223
224 void
225 FcLangSetPtrDestroy (FcLangSetPtr li)
226 {
227     if (li.storage == FcStorageDynamic)
228         FcLangSetDestroy(FcLangSetPtrU(li));
229 }
230
231 void
232 FcLangSetDestroy (FcLangSet *ls)
233 {
234     if (FcStrSetPtrU(ls->extra))
235         FcStrSetDestroy (FcStrSetPtrU(ls->extra));
236     FcMemFree (FC_MEM_LANGSET, sizeof (FcLangSet));
237     free (ls);
238 }
239
240 FcLangSet *
241 FcLangSetCopy (const FcLangSet *ls)
242 {
243     FcLangSet   *new;
244
245     new = FcLangSetCreate ();
246     if (!new)
247         goto bail0;
248     memcpy (new->map, ls->map, sizeof (new->map));
249     if (FcStrSetPtrU(ls->extra))
250     {
251         FcStrList       *list;
252         FcChar8         *extra;
253         
254         new->extra = FcStrSetPtrCreateDynamic(FcStrSetCreate ());
255         if (!FcStrSetPtrU(new->extra))
256             goto bail1;
257
258         list = FcStrListCreate (FcStrSetPtrU(ls->extra));
259         if (!list)
260             goto bail1;
261         
262         while ((extra = FcStrListNext (list)))
263             if (!FcStrSetAdd (FcStrSetPtrU(new->extra), extra))
264             {
265                 FcStrListDone (list);
266                 goto bail1;
267             }
268         FcStrListDone (list);
269     }
270     return new;
271 bail1:
272     FcLangSetDestroy (new);
273 bail0:
274     return 0;
275 }
276
277 static int
278 FcLangSetIndex (const FcChar8 *lang)
279 {
280     int     low, high, mid = 0;
281     int     cmp = 0;
282     FcChar8 firstChar = FcToLower(lang[0]); 
283     FcChar8 secondChar = firstChar ? FcToLower(lang[1]) : '\0';
284     
285     if (firstChar < 'a')
286     {
287         low = 0;
288         high = fcLangCharSetRanges[0].begin;
289     }
290     else if(firstChar > 'z')
291     {
292         low = fcLangCharSetRanges[25].begin;
293         high = NUM_LANG_CHAR_SET - 1;
294     }
295     else
296     {
297         low = fcLangCharSetRanges[firstChar - 'a'].begin;
298         high = fcLangCharSetRanges[firstChar - 'a'].end;
299         /* no matches */
300         if (low > high)
301             return -low; /* next entry after where it would be */
302     }
303
304     while (low <= high)
305     {
306         mid = (high + low) >> 1;
307         if(fcLangCharSets[mid].lang[0] != firstChar)
308             cmp = FcStrCmpIgnoreCase(fcLangCharSets[mid].lang, lang);
309         else
310         {   /* fast path for resolving 2-letter languages (by far the most common) after
311              * finding the first char (probably already true because of the hash table) */
312             cmp = fcLangCharSets[mid].lang[1] - secondChar;
313             if (cmp == 0 && 
314                 (fcLangCharSets[mid].lang[2] != '\0' || 
315                  lang[2] != '\0'))
316             {
317                 cmp = FcStrCmpIgnoreCase(fcLangCharSets[mid].lang+2, 
318                                          lang+2);
319             }
320         }
321         if (cmp == 0)
322             return mid;
323         if (cmp < 0)
324             low = mid + 1;
325         else
326             high = mid - 1;
327     }
328     if (cmp < 0)
329         mid++;
330     return -(mid + 1);
331 }
332
333 FcBool
334 FcLangSetAdd (FcLangSet *ls, const FcChar8 *lang)
335 {
336     int     id;
337
338     id = FcLangSetIndex (lang);
339     if (id >= 0)
340     {
341         FcLangSetBitSet (ls, id);
342         return FcTrue;
343     }
344     if (!FcStrSetPtrU(ls->extra))
345     {
346         ls->extra = FcStrSetPtrCreateDynamic(FcStrSetCreate ());
347         if (!FcStrSetPtrU(ls->extra))
348             return FcFalse;
349     }
350     return FcStrSetAdd (FcStrSetPtrU(ls->extra), lang);
351 }
352
353 FcLangResult
354 FcLangSetHasLang (const FcLangSet *ls, const FcChar8 *lang)
355 {
356     int             id;
357     FcLangResult    best, r;
358     int             i;
359
360     id = FcLangSetIndex (lang);
361     if (id < 0)
362         id = -id - 1;
363     else if (FcLangSetBitGet (ls, id))
364         return FcLangEqual;
365     best = FcLangDifferentLang;
366     for (i = id - 1; i >= 0; i--)
367     {
368         r = FcLangCompare (lang, fcLangCharSets[i].lang);
369         if (r == FcLangDifferentLang)
370             break;
371         if (FcLangSetBitGet (ls, i) && r < best)
372             best = r;
373     }
374     for (i = id; i < NUM_LANG_CHAR_SET; i++)
375     {
376         r = FcLangCompare (lang, fcLangCharSets[i].lang);
377         if (r == FcLangDifferentLang)
378             break;
379         if (FcLangSetBitGet (ls, i) && r < best)
380             best = r;
381     }
382     if (FcStrSetPtrU(ls->extra))
383     {
384         FcStrList       *list = FcStrListCreate (FcStrSetPtrU(ls->extra));
385         FcChar8         *extra;
386         FcLangResult    r;
387         
388         if (list)
389         {
390             while (best > FcLangEqual && (extra = FcStrListNext (list)))
391             {
392                 r = FcLangCompare (lang, extra);
393                 if (r < best)
394                     best = r;
395             }
396             FcStrListDone (list);
397         }
398     }
399     return best;
400 }
401
402 static FcLangResult
403 FcLangSetCompareStrSet (const FcLangSet *ls, FcStrSet *set)
404 {
405     FcStrList       *list = FcStrListCreate (set);
406     FcLangResult    r, best = FcLangDifferentLang;
407     FcChar8         *extra;
408
409     if (list)
410     {
411         while (best > FcLangEqual && (extra = FcStrListNext (list)))
412         {
413             r = FcLangSetHasLang (ls, extra);
414             if (r < best)
415                 best = r;
416         }
417         FcStrListDone (list);
418     }
419     return best;
420 }
421
422 FcLangResult
423 FcLangSetCompare (const FcLangSet *lsa, const FcLangSet *lsb)
424 {
425     int             i, j;
426     FcLangResult    best, r;
427
428     for (i = 0; i < NUM_LANG_SET_MAP; i++)
429         if (lsa->map[i] & lsb->map[i])
430             return FcLangEqual;
431     best = FcLangDifferentLang;
432     for (j = 0; j < NUM_COUNTRY_SET; j++)
433         for (i = 0; i < NUM_LANG_SET_MAP; i++)
434             if ((lsa->map[i] & fcLangCountrySets[j][i]) &&
435                 (lsb->map[i] & fcLangCountrySets[j][i]))
436             {
437                 best = FcLangDifferentCountry;
438                 break;
439             }
440     if (FcStrSetPtrU(lsa->extra))
441     {
442         r = FcLangSetCompareStrSet (lsb, FcStrSetPtrU(lsa->extra));
443         if (r < best)
444             best = r;
445     }
446     if (best > FcLangEqual && FcStrSetPtrU(lsb->extra))
447     {
448         r = FcLangSetCompareStrSet (lsa, FcStrSetPtrU(lsb->extra));
449         if (r < best)
450             best = r;
451     }
452     return best;
453 }
454
455 /*
456  * Used in computing values -- mustn't allocate any storage
457  */
458 FcLangSet *
459 FcLangSetPromote (const FcChar8 *lang)
460 {
461     static FcLangSet    ls;
462     static FcStrSet     strs;
463     static FcChar8      *str;
464     int                 id;
465
466     memset (ls.map, '\0', sizeof (ls.map));
467     ls.extra = FcStrSetPtrCreateDynamic(0);
468     id = FcLangSetIndex (lang);
469     if (id > 0)
470     {
471         FcLangSetBitSet (&ls, id);
472     }
473     else
474     {
475         ls.extra = FcStrSetPtrCreateDynamic(&strs);
476         strs.num = 1;
477         strs.size = 1;
478         strs.storage = FcStorageDynamic;
479         strs.u.strs = &str;
480         strs.ref = 1;
481         str = (FcChar8 *) lang;
482     }
483     return &ls;
484 }
485
486 FcChar32
487 FcLangSetHash (const FcLangSet *ls)
488 {
489     FcChar32    h = 0;
490     int         i;
491
492     for (i = 0; i < NUM_LANG_SET_MAP; i++)
493         h ^= ls->map[i];
494     if (FcStrSetPtrU(ls->extra))
495         h ^= FcStrSetPtrU(ls->extra)->num;
496     return h;
497 }
498
499 FcLangSet *
500 FcNameParseLangSet (const FcChar8 *string)
501 {
502     FcChar8         lang[32],c;
503     int i;
504     FcLangSet       *ls;
505
506     ls = FcLangSetCreate ();
507     if (!ls)
508         goto bail0;
509
510     for(;;)
511     {
512         for(i = 0; i < 31;i++)
513         {
514             c = *string++;
515             if(c == '\0' || c == '|')
516                 break; /* end of this code */
517             lang[i] = c;
518         }
519         lang[i] = '\0';
520         if (!FcLangSetAdd (ls, lang))
521             goto bail1;
522         if(c == '\0')
523             break;
524     }
525     return ls;
526 bail1:
527     FcLangSetDestroy (ls);
528 bail0:
529     return 0;
530 }
531
532 FcBool
533 FcNameUnparseLangSet (FcStrBuf *buf, const FcLangSet *ls)
534 {
535     int         i, bit;
536     FcChar32    bits;
537     FcBool      first = FcTrue;
538
539     for (i = 0; i < NUM_LANG_SET_MAP; i++)
540     {
541         if ((bits = ls->map[i]))
542         {
543             for (bit = 0; bit <= 31; bit++)
544                 if (bits & (1 << bit))
545                 {
546                     int id = (i << 5) | bit;
547                     if (!first)
548                         if (!FcStrBufChar (buf, '|'))
549                             return FcFalse;
550                     if (!FcStrBufString (buf, fcLangCharSets[id].lang))
551                         return FcFalse;
552                     first = FcFalse;
553                 }
554         }
555     }
556     if (FcStrSetPtrU(ls->extra))
557     {
558         FcStrList   *list = FcStrListCreate (FcStrSetPtrU(ls->extra));
559         FcChar8     *extra;
560
561         if (!list)
562             return FcFalse;
563         while ((extra = FcStrListNext (list)))
564         {
565             if (!first)
566                 if (!FcStrBufChar (buf, '|'))
567                     return FcFalse;
568             if (!FcStrBufString (buf, extra))
569                 return FcFalse;
570             first = FcFalse;
571         }
572     }
573     return FcTrue;
574 }
575
576 FcBool
577 FcLangSetEqual (const FcLangSet *lsa, const FcLangSet *lsb)
578 {
579     int     i;
580
581     for (i = 0; i < NUM_LANG_SET_MAP; i++)
582     {
583         if (lsa->map[i] != lsb->map[i])
584             return FcFalse;
585     }
586     if (!FcStrSetPtrU(lsa->extra) && !FcStrSetPtrU(lsb->extra))
587         return FcTrue;
588     if (FcStrSetPtrU(lsa->extra) && FcStrSetPtrU(lsb->extra))
589         return FcStrSetEqual (FcStrSetPtrU(lsa->extra), FcStrSetPtrU(lsb->extra));
590     return FcFalse;
591 }
592
593 static FcBool
594 FcLangSetContainsLang (const FcLangSet *ls, const FcChar8 *lang)
595 {
596     int             id;
597     int             i;
598
599     id = FcLangSetIndex (lang);
600     if (id < 0)
601         id = -id - 1;
602     else if (FcLangSetBitGet (ls, id))
603         return FcTrue;
604     /*
605      * search up and down among equal languages for a match
606      */
607     for (i = id - 1; i >= 0; i--)
608     {
609         if (FcLangCompare (fcLangCharSets[i].lang, lang) == FcLangDifferentLang)
610             break;
611         if (FcLangSetBitGet (ls, i) &&
612             FcLangContains (fcLangCharSets[i].lang, lang))
613             return FcTrue;
614     }
615     for (i = id; i < NUM_LANG_CHAR_SET; i++)
616     {
617         if (FcLangCompare (fcLangCharSets[i].lang, lang) == FcLangDifferentLang)
618             break;
619         if (FcLangSetBitGet (ls, i) &&
620             FcLangContains (fcLangCharSets[i].lang, lang))
621             return FcTrue;
622     }
623     if (FcStrSetPtrU(ls->extra))
624     {
625         FcStrList       *list = FcStrListCreate (FcStrSetPtrU(ls->extra));
626         FcChar8         *extra;
627         
628         if (list)
629         {
630             while ((extra = FcStrListNext (list)))
631             {
632                 if (FcLangContains (extra, lang))
633                     break;
634             }
635             FcStrListDone (list);
636             if (extra)
637                 return FcTrue;
638         }
639     }
640     return FcFalse;
641 }
642
643 /*
644  * return FcTrue if lsa contains every language in lsb
645  */
646 FcBool
647 FcLangSetContains (const FcLangSet *lsa, const FcLangSet *lsb)
648 {
649     int             i, j;
650     FcChar32        missing;
651
652     if (FcDebug() & FC_DBG_MATCHV)
653     {
654         printf ("FcLangSet "); FcLangSetPrint (lsa);
655         printf (" contains "); FcLangSetPrint (lsb);
656         printf ("\n");
657     }
658     /*
659      * check bitmaps for missing language support
660      */
661     for (i = 0; i < NUM_LANG_SET_MAP; i++)
662     {
663         missing = lsb->map[i] & ~lsa->map[i];
664         if (missing)
665         {
666             for (j = 0; j < 32; j++)
667                 if (missing & (1 << j)) 
668                 {
669                     if (!FcLangSetContainsLang (lsa,
670                                                 fcLangCharSets[i*32 + j].lang))
671                     {
672                         if (FcDebug() & FC_DBG_MATCHV)
673                             printf ("\tMissing bitmap %s\n", fcLangCharSets[i*32+j].lang);
674                         return FcFalse;
675                     }
676                 }
677         }
678     }
679     if (FcStrSetPtrU(lsb->extra))
680     {
681         FcStrList   *list = FcStrListCreate (FcStrSetPtrU(lsb->extra));
682         FcChar8     *extra;
683
684         if (list)
685         {
686             while ((extra = FcStrListNext (list)))
687             {
688                 if (!FcLangSetContainsLang (lsa, extra))
689                 {
690                     if (FcDebug() & FC_DBG_MATCHV)
691                         printf ("\tMissing string %s\n", extra);
692                     break;
693                 }
694             }
695             FcStrListDone (list);
696             if (extra)
697                 return FcFalse;
698         }
699     }
700     return FcTrue;
701 }
702
703 static FcLangSet * langsets = 0;
704 static int langset_ptr = 0, langset_count = 0;
705
706 FcLangSet *
707 FcLangSetPtrU (FcLangSetPtr li)
708 {
709     switch (li.storage)
710     {
711     case FcStorageDynamic:
712         return li.u.dyn;
713     case FcStorageStatic:
714         return &langsets[li.u.stat];
715     default:
716         return 0;
717
718     }
719 }
720
721 FcLangSetPtr
722 FcLangSetPtrCreateDynamic (FcLangSet *li)
723 {
724     FcLangSetPtr new;
725     new.storage = FcStorageDynamic;
726     new.u.dyn = li;
727     return new;
728 }
729
730 void
731 FcLangSetClearStatic (void)
732 {
733     FcStrSetClearStatic();
734     langset_ptr = 0;
735     langset_count = 0;
736 }
737
738 /* should only write one copy of any particular FcLangSet */
739 FcBool
740 FcLangSetPrepareSerialize (FcLangSet *l)
741 {
742     langset_count++;
743     if (l && FcStrSetPtrU(l->extra))
744         return FcStrSetPrepareSerialize (FcStrSetPtrU(l->extra));
745     return FcTrue;
746 }
747
748 FcLangSetPtr
749 FcLangSetSerialize(FcLangSet *l)
750 {
751     FcLangSetPtr new;
752     int p = langset_ptr;
753
754     if (!l) return FcLangSetPtrCreateDynamic(0);
755
756     if (!langsets)
757     {
758         FcLangSet* t;
759         t = (FcLangSet *)malloc(langset_count * sizeof(FcLangSet));
760         if (!t)
761             return FcLangSetPtrCreateDynamic(0);
762         langsets = t;
763         langset_ptr = 0;
764     }
765
766     langsets[langset_ptr] = *l;
767     if (FcStrSetPtrU(l->extra))
768         langsets[langset_ptr].extra = 
769             FcStrSetSerialize(FcStrSetPtrU(l->extra));
770     else
771         langsets[langset_ptr].extra = FcStrSetPtrCreateDynamic(0);
772     langset_ptr++;
773     new.storage = FcStorageStatic;
774     new.u.stat = p;
775     return new;
776 }