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