src/fccache.c

   1 /*
   2  * $RCSId: xc/lib/fontconfig/src/fccache.c,v 1.12 2002/08/22 07:36:44 keithp Exp $
   3  *
   4  * Copyright © 2000 Keith Packard
   5  * Copyright © 2005 Patrick Lam
   6  *
   7  * Permission to use, copy, modify, distribute, and sell this software and its
   8  * documentation for any purpose is hereby granted without fee, provided that
   9  * the above copyright notice appear in all copies and that both that
  10  * copyright notice and this permission notice appear in supporting
  11  * documentation, and that the name of Keith Packard not be used in
  12  * advertising or publicity pertaining to distribution of the software without
  13  * specific, written prior permission.  Keith Packard makes no
  14  * representations about the suitability of this software for any purpose.  It
  15  * is provided "as is" without express or implied warranty.
  16  *
  17  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  18  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  19  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  20  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  21  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  22  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  23  * PERFORMANCE OF THIS SOFTWARE.
  24  */
  25
  26 #include <fcntl.h>
  27 #include <dirent.h>
  28 #include <string.h>
  29 #include <sys/mman.h>
  30 #include <sys/utsname.h>
  31 #include <sys/types.h>
  32 #include <unistd.h>
  33 #include "fcint.h"
  34 #include <unistd.h>
  35
  36 #define ENDIAN_TEST 0x12345678
  37 #define MACHINE_SIGNATURE_SIZE 9 + 5*20 + 1
  38
  39 static int
  40 FcDirCacheOpen (const FcChar8 * dir);
  41
  42 static char *
  43 FcDirCacheHashName (char * cache_file, int collisions);
  44
  45 static off_t
  46 FcCacheSkipToArch (int fd, const char * arch);
  47
  48 static FcBool
  49 FcCacheCopyOld (int fd, int fd_orig, off_t start);
  50
  51 static void *
  52 FcDirCacheProduce (FcFontSet *set, FcCache * metadata);
  53
  54 static FcBool
  55 FcDirCacheConsume (int fd, const char * dir, FcFontSet *set, FcConfig *config);
  56
  57 static int
  58 FcCacheNextOffset(off_t w);
  59
  60 static char *
  61 FcCacheMachineSignature (void);
  62
  63 static FcBool
  64 FcCacheHaveBank (int bank);
  65
  66 static void
  67 FcCacheAddBankDir (int bank, const char * dir);
  68
  69 struct MD5Context {
  70         FcChar32 buf[4];
  71         FcChar32 bits[2];
  72         unsigned char in[64];
  73 };
  74
  75 static void MD5Init(struct MD5Context *ctx);
  76 static void MD5Update(struct MD5Context *ctx, unsigned char *buf, unsigned len);
  77 static void MD5Final(unsigned char digest[16], struct MD5Context *ctx);
  78 static void MD5Transform(FcChar32 buf[4], FcChar32 in[16]);
  79
  80 #define FC_DBG_CACHE_REF    1024
  81
  82 static char *
  83 FcCacheReadString (int fd, char *dest, int len)
  84 {
  85     int    size;
  86     int    slen;
  87
  88     if (len == 0)
  89         return 0;
  90
  91     size = read (fd, dest, len-1);
  92
  93     if (size > 0)
  94     {
  95         dest[size] = '\0';
  96         slen = strlen (dest);
  97
  98         lseek (fd, slen - size + 1, SEEK_CUR);
  99         return slen < len ? dest : 0;
 100     }
 101
 102     return 0;
 103 }
 104
 105 static void
 106 FcCacheSkipString (int fd)
 107 {
 108     char buf[256];
 109     int  size;
 110     int  slen;
 111
 112     while ( (size = read (fd, buf, sizeof (buf)-1)) > 0)
 113     {
 114         buf [size] = '\0';
 115         slen = strlen (buf);
 116         if (slen < size)
 117         {
 118             lseek (fd, slen - size + 1, SEEK_CUR);
 119             return;
 120         }
 121     }
 122 }
 123
 124 static FcBool
 125 FcCacheWriteString (int fd, const char *chars)
 126 {
 127     if (write (fd, chars, strlen(chars)+1) != strlen(chars)+1)
 128         return FcFalse;
 129     return FcTrue;
 130 }
 131
 132 static void
 133 FcGlobalCacheDirDestroy (FcGlobalCacheDir *d)
 134 {
 135     FcStrSetDestroy (d->subdirs);
 136     FcMemFree (FC_MEM_STRING, strlen (d->name)+1);
 137     free (d->name);
 138     FcMemFree (FC_MEM_CACHE, sizeof (FcGlobalCacheDir));
 139     free (d);
 140 }
 141
 142 FcGlobalCache *
 143 FcGlobalCacheCreate (void)
 144 {
 145     FcGlobalCache   *cache;
 146
 147     cache = malloc (sizeof (FcGlobalCache));
 148     if (!cache)
 149         return 0;
 150     FcMemAlloc (FC_MEM_CACHE, sizeof (FcGlobalCache));
 151     cache->dirs = 0;
 152     cache->updated = FcFalse;
 153     cache->fd = -1;
 154     return cache;
 155 }
 156
 157 void
 158 FcGlobalCacheDestroy (FcGlobalCache *cache)
 159 {
 160     FcGlobalCacheDir    *d, *next;
 161
 162     for (d = cache->dirs; d; d = next)
 163     {
 164         next = d->next;
 165         FcGlobalCacheDirDestroy (d);
 166     }
 167     FcMemFree (FC_MEM_CACHE, sizeof (FcGlobalCache));
 168     free (cache);
 169 }
 170
 171 void
 172 FcGlobalCacheLoad (FcGlobalCache    *cache,
 173                    FcStrSet         *staleDirs,
 174                    const FcChar8    *cache_file,
 175                    FcConfig         *config)
 176 {
 177     char                name_buf[FC_MAX_FILE_LEN];
 178     FcGlobalCacheDir    *d, *next;
 179     FcFileTime          config_time = FcConfigModifiedTime (config);
 180     char                * current_arch_machine_name;
 181     char                candidate_arch_machine_name[MACHINE_SIGNATURE_SIZE + 9];
 182     off_t               current_arch_start;
 183
 184     struct stat         cache_stat, dir_stat;
 185     char                subdirName[FC_MAX_FILE_LEN + 1 + 12 + 1];
 186
 187     if (stat ((char *) cache_file, &cache_stat) < 0)
 188         return;
 189
 190     cache->fd = open ((char *) cache_file, O_RDONLY);
 191     if (cache->fd == -1)
 192         return;
 193
 194     cache->updated = FcFalse;
 195
 196     if (!FcCacheReadString (cache->fd, name_buf, sizeof (name_buf)))
 197         goto bail_and_destroy;
 198     if (strcmp (name_buf, FC_GLOBAL_MAGIC_COOKIE) != 0)
 199         goto bail_and_destroy;
 200
 201     current_arch_machine_name = FcCacheMachineSignature ();
 202     current_arch_start = FcCacheSkipToArch(cache->fd,
 203                                            current_arch_machine_name);
 204     if (current_arch_start < 0)
 205         goto bail_and_destroy;
 206
 207     lseek (cache->fd, current_arch_start, SEEK_SET);
 208     if (!FcCacheReadString (cache->fd, candidate_arch_machine_name,
 209                             sizeof (candidate_arch_machine_name)))
 210         goto bail_and_destroy;
 211     if (strlen(candidate_arch_machine_name) == 0)
 212         goto bail_and_destroy;
 213
 214     while (1)
 215     {
 216         off_t targ;
 217
 218         if (!FcCacheReadString (cache->fd, name_buf, sizeof (name_buf)) ||
 219             !strlen(name_buf))
 220             break;
 221
 222         /* Directory must be older than the global cache file; also
 223            cache must be newer than the config file. */
 224         if (stat ((char *) name_buf, &dir_stat) < 0 ||
 225             dir_stat.st_mtime > cache_stat.st_mtime ||
 226             (config_time.set && cache_stat.st_mtime < config_time.time))
 227         {
 228             FcCache md;
 229             off_t off;
 230
 231             FcStrSetAdd (staleDirs, FcStrCopy ((FcChar8 *)name_buf));
 232
 233             /* skip subdirs */
 234             while (FcCacheReadString (cache->fd, subdirName,
 235                                       sizeof (subdirName)) &&
 236                    strlen (subdirName))
 237                 ;
 238
 239             if (read (cache->fd, &md, sizeof (FcCache)) != sizeof(FcCache))
 240             {
 241                 perror ("read metadata");
 242                 goto bail1;
 243             }
 244             off = FcCacheNextOffset (lseek(cache->fd, 0, SEEK_CUR)) + md.count;
 245             if (lseek (cache->fd, off, SEEK_SET) != off)
 246             {
 247                 perror ("lseek");
 248                 goto bail1;
 249             }
 250             continue;
 251         }
 252
 253         d = malloc (sizeof (FcGlobalCacheDir));
 254         if (!d)
 255             goto bail1;
 256
 257         d->next = cache->dirs;
 258         cache->dirs = d;
 259
 260         d->name = (char *)FcStrCopy ((FcChar8 *)name_buf);
 261         d->ent = 0;
 262         d->state = FcGCDirFileRead;
 263
 264         d->subdirs = FcStrSetCreate();
 265         do
 266         {
 267             if (!FcCacheReadString (cache->fd, subdirName,
 268                                     sizeof (subdirName)) ||
 269                 !strlen (subdirName))
 270                 break;
 271             FcStrSetAdd (d->subdirs, (FcChar8 *)subdirName);
 272         } while (1);
 273
 274         d->offset = lseek (cache->fd, 0, SEEK_CUR);
 275         if (read (cache->fd, &d->metadata, sizeof (FcCache)) != sizeof (FcCache))
 276             goto bail1;
 277         targ = FcCacheNextOffset (lseek(cache->fd, 0, SEEK_CUR)) + d->metadata.count;
 278         if (lseek (cache->fd, targ, SEEK_SET) != targ)
 279             goto bail1;
 280     }
 281     return;
 282
 283  bail1:
 284     for (d = cache->dirs; d; d = next)
 285     {
 286         next = d->next;
 287         free (d);
 288     }
 289     cache->dirs = 0;
 290
 291     close (cache->fd);
 292     cache->fd = -1;
 293     return;
 294
 295  bail_and_destroy:
 296     close (cache->fd);
 297     cache->fd = -1;
 298
 299     if (stat ((char *) cache_file, &cache_stat) == 0)
 300         unlink ((char *)cache_file);
 301
 302     return;
 303
 304 }
 305
 306 FcBool
 307 FcGlobalCacheReadDir (FcFontSet *set, FcStrSet *dirs, FcGlobalCache * cache, const char *dir, FcConfig *config)
 308 {
 309     FcGlobalCacheDir    *d;
 310     int                 i;
 311
 312     if (cache->fd == -1)
 313         return FcFalse;
 314
 315     if (!(dir = (char *)FcConfigNormalizeFontDir (config, (FcChar8 *)dir)))
 316         return FcFalse; /* non-existing directory */
 317
 318     for (d = cache->dirs; d; d = d->next)
 319     {
 320         if (strcmp (d->name, dir) == 0)
 321         {
 322             if (d->state == FcGCDirDisabled)
 323                 return FcFalse;
 324
 325             if (d->state == FcGCDirFileRead)
 326             {
 327                 lseek (cache->fd, d->offset, SEEK_SET);
 328                 if (!FcDirCacheConsume (cache->fd, d->name, set, config))
 329                     return FcFalse;
 330
 331                 for (i = 0; i < d->subdirs->num; i++)
 332                     FcStrSetAdd (dirs, (FcChar8 *)d->subdirs->strs[i]);
 333
 334                 d->state = FcGCDirConsumed;
 335             }
 336             return FcTrue;
 337         }
 338     }
 339
 340     return FcFalse;
 341 }
 342
 343 static FcGlobalCacheDir *
 344 FcGlobalCacheDirFind (FcGlobalCache *cache, const char *name)
 345 {
 346     FcGlobalCacheDir * d;
 347
 348     if (!cache || !name)
 349         return NULL;
 350
 351     for (d = cache->dirs; d; d = d->next)
 352         if (strcmp((const char *)d->name, (const char *)name) == 0)
 353             return d;
 354
 355     return NULL;
 356  }
 357
 358 FcBool
 359 FcGlobalCacheUpdate (FcGlobalCache  *cache,
 360                      FcStrSet       *dirs,
 361                      const char     *orig_name,
 362                      FcFontSet      *set,
 363                      FcConfig       *config)
 364 {
 365     FcGlobalCacheDir    *d;
 366     int                 i;
 367     const char *name;
 368
 369     name = (char *)FcConfigNormalizeFontDir (config, (FcChar8 *)orig_name);
 370     if (!name)
 371     {
 372         fprintf(stderr, "Invalid directory name %s\n", orig_name);
 373         return FcFalse;
 374     }
 375
 376     d = FcGlobalCacheDirFind (cache, name);
 377
 378     if (!d)
 379     {
 380         d = malloc (sizeof (FcGlobalCacheDir));
 381         if (!d)
 382             return FcFalse;
 383         d->next = cache->dirs;
 384         cache->dirs = d;
 385     } else {
 386         /* free old resources */
 387         FcStrFree ((FcChar8 *)d->name);
 388         free (d->ent);
 389         FcStrSetDestroy (d->subdirs);
 390     }
 391
 392     cache->updated = FcTrue;
 393
 394     d->name = (char *)FcStrCopy ((FcChar8 *)name);
 395     d->ent = FcDirCacheProduce (set, &d->metadata);
 396     d->offset = 0;
 397     d->subdirs = FcStrSetCreate();
 398     d->state = FcGCDirUpdated;
 399     for (i = 0; i < dirs->num; i++)
 400         FcStrSetAdd (d->subdirs, dirs->strs[i]);
 401     return FcTrue;
 402 }
 403
 404 FcBool
 405 FcGlobalCacheSave (FcGlobalCache    *cache,
 406                    const FcChar8    *cache_file,
 407                    FcConfig         *config)
 408 {
 409     int                 fd, fd_orig, i;
 410     FcGlobalCacheDir    *dir;
 411     FcAtomic            *atomic;
 412     off_t               current_arch_start = 0, truncate_to;
 413     char                * current_arch_machine_name, * header;
 414
 415     if (!cache->updated)
 416         return FcTrue;
 417
 418 #if defined (HAVE_GETUID) && defined (HAVE_GETEUID)
 419     /* Set-UID programs can't safely update the cache */
 420     if (getuid () != geteuid ())
 421         return FcFalse;
 422 #endif
 423
 424     atomic = FcAtomicCreate (cache_file);
 425     if (!atomic)
 426         return FcFalse;
 427
 428     if (!FcAtomicLock (atomic))
 429         goto bail1;
 430     fd = open ((char *) FcAtomicNewFile(atomic), O_RDWR | O_CREAT,
 431                S_IRUSR | S_IWUSR);
 432     if (fd == -1)
 433         goto bail2;
 434     FcCacheWriteString (fd, FC_GLOBAL_MAGIC_COOKIE);
 435
 436     fd_orig = open ((char *) FcAtomicOrigFile(atomic), O_RDONLY);
 437
 438     current_arch_machine_name = FcCacheMachineSignature ();
 439     if (fd_orig == -1)
 440         current_arch_start = 0;
 441     else
 442         current_arch_start = FcCacheSkipToArch (fd_orig,
 443                                                 current_arch_machine_name);
 444
 445     if (current_arch_start < 0)
 446     {
 447         off_t i = lseek(fd_orig, 0, SEEK_END);
 448         if (i < strlen (FC_GLOBAL_MAGIC_COOKIE)+1)
 449             i = strlen (FC_GLOBAL_MAGIC_COOKIE)+1;
 450         current_arch_start = FcCacheNextOffset (i);
 451     }
 452
 453     if (!FcCacheCopyOld(fd, fd_orig, current_arch_start))
 454         goto bail3;
 455
 456     current_arch_start = lseek(fd, 0, SEEK_CUR);
 457     if (ftruncate (fd, current_arch_start) == -1)
 458         goto bail3;
 459
 460     header = malloc (10 + strlen (current_arch_machine_name));
 461     if (!header)
 462         goto bail3;
 463
 464     truncate_to = current_arch_start + strlen(current_arch_machine_name) + 11;
 465     for (dir = cache->dirs; dir; dir = dir->next)
 466     {
 467         if (dir->state == FcGCDirDisabled)
 468             continue;
 469         truncate_to += strlen(dir->name) + 1;
 470         truncate_to += sizeof (FcCache);
 471         truncate_to = FcCacheNextOffset (truncate_to);
 472         truncate_to += dir->metadata.count;
 473
 474         for (i = 0; i < dir->subdirs->size; i++)
 475             truncate_to += strlen((char *)dir->subdirs->strs[i]) + 1;
 476         truncate_to ++;
 477     }
 478     truncate_to -= current_arch_start;
 479
 480     sprintf (header, "%8x ", (int)truncate_to);
 481     strcat (header, current_arch_machine_name);
 482     if (!FcCacheWriteString (fd, header))
 483         goto bail4;
 484
 485     for (dir = cache->dirs; dir; dir = dir->next)
 486     {
 487         const char * d;
 488         off_t off;
 489
 490         if (!dir->name || dir->state == FcGCDirDisabled)
 491             continue;
 492         d = (const char *)FcConfigNormalizeFontDir (config, (const FcChar8 *)dir->name);
 493         if (!d)
 494             continue;
 495
 496         if (dir->metadata.count && !dir->ent)
 497         {
 498             if (dir->state == FcGCDirUpdated || fd_orig < 0)
 499             {
 500                 fprintf(stderr, "Invalid metadata entry for %s, skipping...\n", d);
 501                 continue;
 502             }
 503             /* copy the old content */
 504             dir->ent = malloc (dir->metadata.count);
 505             if (!dir->ent)
 506             {
 507                 perror("malloc error");
 508                 continue;
 509             }
 510             off = FcCacheNextOffset (dir->offset + sizeof(FcCache));
 511             if (lseek (fd_orig, off, SEEK_SET) != off)
 512             {
 513                 perror("lseek");
 514                 free(dir->ent);
 515                 continue;
 516             }
 517             if (read (fd_orig, dir->ent, dir->metadata.count)
 518                 != dir->metadata.count)
 519             {
 520                 perror("read");
 521                 free(dir->ent);
 522                 continue;
 523             }
 524         }
 525
 526         FcCacheWriteString (fd, d);
 527
 528         for (i = 0; i < dir->subdirs->size; i++)
 529             FcCacheWriteString (fd, (char *)dir->subdirs->strs[i]);
 530         FcCacheWriteString (fd, "");
 531
 532         if (write (fd, &dir->metadata, sizeof(FcCache)) != sizeof(FcCache))
 533         {
 534             perror ("write metadata");
 535             free (dir->ent);
 536             continue;
 537         }
 538         off = FcCacheNextOffset (lseek(fd, 0, SEEK_CUR));
 539         if (lseek (fd, off, SEEK_SET) != off)
 540         {
 541             perror ("lseek");
 542             free (dir->ent);
 543             continue;
 544         }
 545         if (dir->metadata.count)
 546         {
 547             if (write (fd, dir->ent, dir->metadata.count) != dir->metadata.count)
 548             {
 549                 perror ("write dirent");
 550                 free (dir->ent);
 551                 continue;
 552             }
 553         }
 554         free (dir->ent);
 555     }
 556     FcCacheWriteString (fd, "");
 557
 558     if (close (fd) == -1)
 559         goto bail25;
 560
 561     close (fd_orig);
 562     fd_orig = -1;
 563
 564     if (!FcAtomicReplaceOrig (atomic))
 565         goto bail25;
 566
 567     FcAtomicUnlock (atomic);
 568     FcAtomicDestroy (atomic);
 569
 570     cache->updated = FcFalse;
 571     return FcTrue;
 572
 573  bail4:
 574     free (header);
 575  bail3:
 576     if (fd_orig != -1)
 577         close (fd_orig);
 578
 579     close (fd);
 580  bail25:
 581     FcAtomicDeleteNew (atomic);
 582  bail2:
 583     FcAtomicUnlock (atomic);
 584  bail1:
 585     FcAtomicDestroy (atomic);
 586     return FcFalse;
 587 }
 588
 589 /*
 590  * Find the next presumably-mmapable offset after the supplied file
 591  * position.
 592  */
 593 static int
 594 FcCacheNextOffset(off_t w)
 595 {
 596     static long pagesize = -1;
 597     if (pagesize == -1)
 598         pagesize = sysconf(_SC_PAGESIZE);
 599     if (w % pagesize == 0)
 600         return w;
 601     else
 602         return ((w / pagesize)+1)*pagesize;
 603 }
 604
 605 /* return the address of the segment for the provided arch,
 606  * or -1 if arch not found */
 607 static off_t
 608 FcCacheSkipToArch (int fd, const char * arch)
 609 {
 610     char candidate_arch_machine_name_count[MACHINE_SIGNATURE_SIZE + 9];
 611     char * candidate_arch;
 612     off_t current_arch_start = 0;
 613
 614     lseek (fd, 0, SEEK_SET);
 615     FcCacheSkipString (fd);
 616     current_arch_start = lseek (fd, 0, SEEK_CUR);
 617
 618     /* skip arches that are not the current arch */
 619     while (1)
 620     {
 621         long bs;
 622
 623         if (lseek (fd, current_arch_start, SEEK_SET) != current_arch_start)
 624             return -1;
 625
 626         if (FcCacheReadString (fd, candidate_arch_machine_name_count,
 627                                 sizeof (candidate_arch_machine_name_count)) == 0)
 628             return -1;
 629         if (!strlen(candidate_arch_machine_name_count))
 630             return -1;
 631         bs = strtol(candidate_arch_machine_name_count, &candidate_arch, 16);
 632
 633         // count = 0 should probably be distinguished from the !bs condition
 634         if (!bs || bs < strlen (candidate_arch_machine_name_count))
 635             return -1;
 636
 637         candidate_arch++; /* skip leading space */
 638
 639         if (strcmp (candidate_arch, arch)==0)
 640             return current_arch_start;
 641         current_arch_start += bs;
 642     }
 643
 644     return -1;
 645 }
 646
 647 /* Cuts out the segment at the file pointer (moves everything else
 648  * down to cover it), and leaves the file pointer at the end of the
 649  * file. */
 650 static FcBool
 651 FcCacheCopyOld (int fd, int fd_orig, off_t start)
 652 {
 653     char * buf = malloc (8192);
 654     char candidate_arch_machine_name[MACHINE_SIGNATURE_SIZE + 9];
 655     long bs;
 656     int c, bytes_skipped;
 657     off_t loc;
 658
 659     if (!buf)
 660         return FcFalse;
 661
 662     loc = 0;
 663     lseek (fd, 0, SEEK_SET); lseek (fd_orig, 0, SEEK_SET);
 664     do
 665     {
 666         int b = 8192;
 667         if (loc + b > start)
 668             b = start - loc;
 669
 670         if ((c = read (fd_orig, buf, b)) <= 0)
 671             break;
 672         if (write (fd, buf, c) < 0)
 673             goto bail;
 674
 675         loc += c;
 676     }
 677     while (c > 0);
 678
 679     lseek (fd, start, SEEK_SET);
 680     if (FcCacheReadString (fd, candidate_arch_machine_name,
 681                            sizeof (candidate_arch_machine_name)) == 0)
 682         goto done;
 683     if (!strlen(candidate_arch_machine_name))
 684         goto done;
 685
 686     bs = strtol(candidate_arch_machine_name, 0, 16);
 687     if (bs == 0)
 688         goto done;
 689
 690     bytes_skipped = 0;
 691     do
 692     {
 693         lseek (fd, start+bs+bytes_skipped, SEEK_SET);
 694         if ((c = read (fd, buf, 8192)) <= 0)
 695             break;
 696         lseek (fd, start+bytes_skipped, SEEK_SET);
 697         if (write (fd, buf, c) < 0)
 698             goto bail;
 699         bytes_skipped += c;
 700     }
 701     while (c > 0);
 702     lseek (fd, start+bytes_skipped, SEEK_SET);
 703
 704  done:
 705     free (buf);
 706     return FcTrue;
 707
 708  bail:
 709     free (buf);
 710     return FcFalse;
 711 }
 712
 713 /* Does not check that the cache has the appropriate arch section. */
 714 /* Also, this can be fooled if the original location has a stale
 715  * cache, and the hashed location has an up-to-date cache.  Oh well,
 716  * sucks to be you in that case! */
 717 FcBool
 718 FcDirCacheValid (const FcChar8 *dir)
 719 {
 720     struct stat file_stat, dir_stat;
 721     int         fd;
 722
 723     if (stat ((char *) dir, &dir_stat) < 0)
 724         return FcFalse;
 725
 726     fd = FcDirCacheOpen (dir);
 727
 728     if (fd < 0)
 729         goto bail;
 730     if (fstat (fd, &file_stat) < 0)
 731         goto bail;
 732
 733     close (fd);
 734
 735     /*
 736      * If the directory has been modified more recently than
 737      * the cache file, the cache is not valid
 738      */
 739     if (dir_stat.st_mtime > file_stat.st_mtime)
 740         return FcFalse;
 741
 742     return FcTrue;
 743
 744  bail:
 745     close (fd);
 746     return FcFalse;
 747 }
 748
 749 /* Assumes that the cache file in 'dir' exists.
 750  * Checks that the cache has the appropriate arch section. */
 751 FcBool
 752 FcDirCacheHasCurrentArch (const FcChar8 *dir)
 753 {
 754     int         fd;
 755     off_t       current_arch_start;
 756     char        *current_arch_machine_name;
 757
 758     fd = FcDirCacheOpen (dir);
 759     if (fd < 0)
 760         goto bail;
 761
 762     current_arch_machine_name = FcCacheMachineSignature();
 763     current_arch_start = FcCacheSkipToArch(fd, current_arch_machine_name);
 764     close (fd);
 765
 766     if (current_arch_start < 0)
 767         return FcFalse;
 768
 769     return FcTrue;
 770
 771  bail:
 772     return FcFalse;
 773 }
 774
 775 FcBool
 776 FcDirCacheUnlink (const FcChar8 *dir, FcConfig *config)
 777 {
 778     char        *cache_file;
 779     char        *cache_hashed = 0;
 780     int         fd, collisions;
 781     struct stat cache_stat;
 782     char        name_buf[FC_MAX_FILE_LEN];
 783
 784     dir = FcConfigNormalizeFontDir (config, dir);
 785     cache_file = (char *)FcStrPlus (dir, (FcChar8 *) "/" FC_DIR_CACHE_FILE);
 786     if (!cache_file)
 787         return FcFalse;
 788
 789     /* First remove normal cache file. */
 790     if (stat ((char *) cache_file, &cache_stat) == 0 &&
 791         unlink ((char *)cache_file) != 0)
 792         goto bail;
 793
 794     /* Next remove any applicable hashed files. */
 795     fd = -1; collisions = 0;
 796     do
 797     {
 798         if (cache_hashed)
 799             FcStrFree ((FcChar8 *)cache_hashed);
 800
 801         cache_hashed = FcDirCacheHashName (cache_file, collisions++);
 802         if (!cache_hashed)
 803             goto bail;
 804
 805         if (fd > 0)
 806             close (fd);
 807         fd = open(cache_hashed, O_RDONLY);
 808         if (fd == -1)
 809         {
 810             FcStrFree ((FcChar8 *)cache_file);
 811             return FcTrue;
 812         }
 813
 814         if (!FcCacheReadString (fd, name_buf, sizeof (name_buf)) || !strlen(name_buf))
 815         {
 816             FcStrFree ((FcChar8 *)cache_hashed);
 817             goto bail;
 818         }
 819     } while (strcmp (name_buf, cache_file) != 0);
 820
 821     close (fd);
 822
 823     if (stat ((char *) cache_hashed, &cache_stat) == 0 &&
 824         unlink ((char *)cache_hashed) != 0)
 825     {
 826         FcStrFree ((FcChar8 *)cache_hashed);
 827         goto bail;
 828     }
 829
 830     FcStrFree ((FcChar8 *)cache_file);
 831     FcStrFree ((FcChar8 *)cache_hashed);
 832     return FcTrue;
 833
 834  bail:
 835     FcStrFree ((FcChar8 *)cache_file);
 836     return FcFalse;
 837 }
 838
 839 static int
 840 FcCacheReadDirs (FcConfig * config, FcGlobalCache * cache,
 841                  FcStrList *list, FcFontSet * set, FcStrSet *processed_dirs)
 842 {
 843     int                 ret = 0;
 844     FcChar8             *dir;
 845     FcStrSet            *subdirs;
 846     FcStrList           *sublist;
 847     struct stat         statb;
 848     FcGlobalCacheDir   *d;
 849
 850     /*
 851      * Read in the results from 'list'.
 852      */
 853     while ((dir = FcStrListNext (list)))
 854     {
 855         if (!FcConfigAcceptFilename (config, dir))
 856             continue;
 857
 858         /* Skip this directory if already updated
 859          * to avoid the looped directories via symlinks
 860          * Clearly a dir not in fonts.conf shouldn't be globally cached.
 861          */
 862         dir = FcConfigNormalizeFontDir (config, dir);
 863         if (!dir)
 864             continue;
 865
 866         if (FcStrSetMember (processed_dirs, dir))
 867             continue;
 868         if (!FcStrSetAdd (processed_dirs, dir))
 869             continue;
 870
 871         subdirs = FcStrSetCreate ();
 872         if (!subdirs)
 873         {
 874             fprintf (stderr, "Can't create directory set\n");
 875             ret++;
 876             continue;
 877         }
 878
 879         if (access ((char *) dir, X_OK) < 0)
 880         {
 881             switch (errno) {
 882             case ENOENT:
 883             case ENOTDIR:
 884             case EACCES:
 885                 break;
 886             default:
 887                 fprintf (stderr, "\"%s\": ", dir);
 888                 perror ("");
 889                 ret++;
 890             }
 891             FcStrSetDestroy (subdirs);
 892             continue;
 893         }
 894         if (stat ((char *) dir, &statb) == -1)
 895         {
 896             fprintf (stderr, "\"%s\": ", dir);
 897             perror ("");
 898             FcStrSetDestroy (subdirs);
 899             ret++;
 900             continue;
 901         }
 902         if (!S_ISDIR (statb.st_mode))
 903         {
 904             fprintf (stderr, "\"%s\": not a directory, skipping\n", dir);
 905             FcStrSetDestroy (subdirs);
 906             continue;
 907         }
 908         if (FcDirCacheValid (dir) && FcDirCacheRead (set, subdirs, dir, config))
 909         {
 910             /* if an old entry is found in the global cache, disable it */
 911             if ((d = FcGlobalCacheDirFind (cache, (const char *)dir)) != NULL)
 912             {
 913                 d->state = FcGCDirDisabled;
 914                 /* save the updated config later without this entry */
 915                 cache->updated = FcTrue;
 916             }
 917         }
 918         else
 919         {
 920             if (FcDebug () & FC_DBG_FONTSET)
 921                 printf ("cache scan dir %s\n", dir);
 922
 923             FcDirScanConfig (set, subdirs, cache,
 924                              config->blanks, dir, FcFalse, config);
 925         }
 926         sublist = FcStrListCreate (subdirs);
 927         FcStrSetDestroy (subdirs);
 928         if (!sublist)
 929         {
 930             fprintf (stderr, "Can't create subdir list in \"%s\"\n", dir);
 931             ret++;
 932             continue;
 933         }
 934         ret += FcCacheReadDirs (config, cache, sublist, set, processed_dirs);
 935     }
 936     FcStrListDone (list);
 937     return ret;
 938 }
 939
 940 FcFontSet *
 941 FcCacheRead (FcConfig *config, FcGlobalCache * cache)
 942 {
 943     FcFontSet   *s = FcFontSetCreate();
 944     FcStrSet    *processed_dirs;
 945
 946     if (!s)
 947         return 0;
 948
 949     processed_dirs = FcStrSetCreate();
 950     if (!processed_dirs)
 951         goto bail;
 952
 953     if (FcCacheReadDirs (config, cache, FcConfigGetConfigDirs (config), s, processed_dirs))
 954         goto bail1;
 955
 956     FcStrSetDestroy (processed_dirs);
 957     return s;
 958
 959  bail1:
 960     FcStrSetDestroy (processed_dirs);
 961  bail:
 962     FcFontSetDestroy (s);
 963     return 0;
 964 }
 965
 966 static const char bin2hex[] = { '0', '1', '2', '3',
 967                                 '4', '5', '6', '7',
 968                                 '8', '9', 'a', 'b',
 969                                 'c', 'd', 'e', 'f' };
 970
 971 static char *
 972 FcDirCacheHashName (char * cache_file, int collisions)
 973 {
 974     unsigned char       hash[16], hex_hash[33];
 975     char                *cache_hashed;
 976     unsigned char       uscore = '_';
 977     int                 cnt, i;
 978     FcChar8             *tmp;
 979     struct MD5Context   ctx;
 980
 981     MD5Init (&ctx);
 982     MD5Update (&ctx, (unsigned char *)cache_file, strlen (cache_file));
 983
 984     for (i = 0; i < collisions; i++)
 985         MD5Update (&ctx, &uscore, 1);
 986
 987     MD5Final (hash, &ctx);
 988
 989     for (cnt = 0; cnt < 16; ++cnt)
 990     {
 991         hex_hash[2*cnt] = bin2hex[hash[cnt] >> 4];
 992         hex_hash[2*cnt+1] = bin2hex[hash[cnt] & 0xf];
 993     }
 994     hex_hash[32] = 0;
 995
 996     tmp = FcStrPlus ((FcChar8 *)hex_hash, (FcChar8 *)FC_CACHE_SUFFIX);
 997     if (!tmp)
 998         return 0;
 999
1000     cache_hashed = (char *)FcStrPlus ((FcChar8 *)PKGCACHEDIR"/", tmp);
1001     free (tmp);
1002
1003     return cache_hashed;
1004 }
1005
1006 /* Opens the hashed name for cache_file.
1007  * This would fail in the unlikely event of a collision and subsequent
1008  * removal of the file which originally caused the collision. */
1009 static int
1010 FcDirCacheOpen (const FcChar8 *dir)
1011 {
1012     FcBool      found;
1013     int         fd = -1, collisions = 0;
1014     char        *cache_file, *cache_hashed;
1015     char        name_buf[FC_MAX_FILE_LEN];
1016     struct stat dir_stat;
1017
1018     cache_file = (char *)FcStrPlus (dir, (FcChar8 *) "/" FC_DIR_CACHE_FILE);
1019     if (!cache_file)
1020         return -1;
1021
1022     fd = open(cache_file, O_RDONLY);
1023     if (fd != -1)
1024         return fd;
1025
1026     if (stat ((char *)dir, &dir_stat) == -1)
1027         return -1;
1028
1029     found = FcFalse;
1030     do
1031     {
1032         struct stat c;
1033         FcChar8 * name_buf_dir;
1034
1035         cache_hashed = FcDirCacheHashName (cache_file, collisions++);
1036         if (!cache_hashed)
1037         {
1038             FcStrFree ((FcChar8 *)cache_file);
1039             return -1;
1040         }
1041
1042         if (fd > 0)
1043             close (fd);
1044         fd = open(cache_hashed, O_RDONLY);
1045         FcStrFree ((FcChar8 *)cache_hashed);
1046
1047         if (fd == -1)
1048         {
1049             FcStrFree ((FcChar8 *)cache_file);
1050             return -1;
1051         }
1052         if (!FcCacheReadString (fd, name_buf, sizeof (name_buf)) || !strlen(name_buf))
1053             goto bail;
1054
1055         name_buf_dir = FcStrDirname ((FcChar8 *)name_buf);
1056         if (stat ((char *)name_buf_dir, &c) == -1)
1057         {
1058             FcStrFree (name_buf_dir);
1059             continue;
1060         }
1061         FcStrFree (name_buf_dir);
1062         found = (c.st_ino == dir_stat.st_ino) && (c.st_dev == dir_stat.st_dev);
1063     } while (!found);
1064     FcStrFree ((FcChar8 *)cache_file);
1065     return fd;
1066
1067  bail:
1068     FcStrFree ((FcChar8 *)cache_file);
1069     close (fd);
1070     return -1;
1071 }
1072
1073 /* read serialized state from the cache file */
1074 FcBool
1075 FcDirCacheRead (FcFontSet * set, FcStrSet * dirs, const FcChar8 *dir, FcConfig *config)
1076 {
1077     int         fd;
1078     char        *current_arch_machine_name;
1079     char        candidate_arch_machine_name[9+MACHINE_SIGNATURE_SIZE];
1080     off_t       current_arch_start = 0;
1081     char        subdirName[FC_MAX_FILE_LEN + 1 + 12 + 1];
1082
1083     fd = FcDirCacheOpen (dir);
1084     if (fd < 0)
1085         goto bail;
1086
1087     current_arch_machine_name = FcCacheMachineSignature();
1088     current_arch_start = FcCacheSkipToArch(fd,
1089                                            current_arch_machine_name);
1090     if (current_arch_start < 0)
1091         goto bail1;
1092
1093     lseek (fd, current_arch_start, SEEK_SET);
1094     if (FcCacheReadString (fd, candidate_arch_machine_name,
1095                            sizeof (candidate_arch_machine_name)) == 0)
1096         goto bail1;
1097
1098     while (FcCacheReadString (fd, subdirName, sizeof (subdirName)) && strlen (subdirName) > 0)
1099         FcStrSetAdd (dirs, (FcChar8 *)subdirName);
1100
1101     if (!FcDirCacheConsume (fd, (const char *)dir, set, config))
1102         goto bail1;
1103
1104     close(fd);
1105     return FcTrue;
1106
1107  bail1:
1108     close (fd);
1109  bail:
1110     return FcFalse;
1111 }
1112
1113 static FcBool
1114 FcDirCacheConsume (int fd, const char * dir, FcFontSet *set, FcConfig *config)
1115 {
1116     FcCache metadata;
1117     void * current_dir_block;
1118     off_t pos;
1119
1120     if (read(fd, &metadata, sizeof(FcCache)) != sizeof(FcCache))
1121         return FcFalse;
1122     if (metadata.magic != FC_CACHE_MAGIC)
1123         return FcFalse;
1124
1125     if (!metadata.count)
1126     {
1127         pos = FcCacheNextOffset (lseek(fd, 0, SEEK_CUR));
1128         lseek (fd, pos, SEEK_SET);
1129         if (config)
1130             FcConfigAddFontDir (config, (FcChar8 *)dir);
1131         return FcTrue;
1132     }
1133
1134     pos = FcCacheNextOffset (lseek(fd, 0, SEEK_CUR));
1135     current_dir_block = mmap (0, metadata.count,
1136                               PROT_READ, MAP_SHARED, fd, pos);
1137     lseek (fd, pos+metadata.count, SEEK_SET);
1138     if (current_dir_block == MAP_FAILED)
1139         return FcFalse;
1140
1141     FcCacheAddBankDir (metadata.bank, dir);
1142     if (config)
1143         FcConfigAddFontDir (config, (FcChar8 *)dir);
1144
1145     if (!FcFontSetUnserialize (&metadata, set, current_dir_block))
1146         return FcFalse;
1147
1148     return FcTrue;
1149 }
1150
1151 static void *
1152 FcDirCacheProduce (FcFontSet *set, FcCache *metadata)
1153 {
1154     void * current_dir_block, * final_dir_block;
1155     static unsigned int rand_state = 0;
1156     int bank, needed_bytes_no_align;
1157
1158     if (!rand_state)
1159         rand_state = time(0L);
1160     bank = rand_r(&rand_state);
1161
1162     while (FcCacheHaveBank(bank))
1163         bank = rand_r(&rand_state);
1164
1165     memset (metadata, 0, sizeof(FcCache));
1166     FcFontSetNewBank();
1167     needed_bytes_no_align = FcFontSetNeededBytes (set);
1168     metadata->count = needed_bytes_no_align +
1169         FcFontSetNeededBytesAlign ();
1170     metadata->magic = FC_CACHE_MAGIC;
1171     metadata->bank = bank;
1172
1173     if (!needed_bytes_no_align) /* not a failure, no fonts to write */
1174     {
1175         /* no, you don't really need to write any bytes at all. */
1176         metadata->count = 0;
1177         return 0;
1178     }
1179
1180     current_dir_block = malloc (metadata->count);
1181     if (!current_dir_block)
1182         goto bail;
1183     // shut up valgrind
1184     memset (current_dir_block, 0, metadata->count);
1185     final_dir_block = FcFontSetDistributeBytes (metadata, current_dir_block);
1186
1187     if ((void *)((char *)current_dir_block+metadata->count) < final_dir_block)
1188         goto bail;
1189
1190     if (!FcFontSetSerialize (bank, set))
1191         goto bail;
1192
1193     return current_dir_block;
1194
1195  bail:
1196     free (current_dir_block);
1197     return 0;
1198 }
1199
1200 /* write serialized state to the cache file */
1201 FcBool
1202 FcDirCacheWrite (FcFontSet *set, FcStrSet *dirs, const FcChar8 *dir)
1203 {
1204     char            *cache_file;
1205     char            *cache_hashed;
1206     int             fd, fd_orig, i, dirs_count;
1207     FcAtomic        *atomic;
1208     FcCache         metadata;
1209     off_t           current_arch_start = 0, truncate_to;
1210     char            name_buf[FC_MAX_FILE_LEN];
1211     int             collisions;
1212
1213     char            *current_arch_machine_name, * header;
1214     void            *current_dir_block = 0;
1215
1216     dir = FcConfigNormalizeFontDir (FcConfigGetCurrent(), dir);
1217     if (!dir)
1218         return FcFalse;
1219
1220     cache_file = (char *)FcStrPlus (dir, (FcChar8 *) "/" FC_DIR_CACHE_FILE);
1221     if (!cache_file)
1222         goto bail;
1223
1224     /* Ensure that we're not trampling a cache for some other dir. */
1225     /* This is slightly different from FcDirCacheOpen, since it
1226      * needs the filename, not the file descriptor. */
1227     fd = -1; collisions = 0;
1228     do
1229     {
1230         cache_hashed = FcDirCacheHashName (cache_file, collisions++);
1231         if (!cache_hashed)
1232             goto bail0;
1233
1234         if (fd > 0)
1235             close (fd);
1236         fd = open(cache_hashed, O_RDONLY);
1237         if (fd == -1)
1238             break;
1239         if(!FcCacheReadString (fd, name_buf, sizeof (name_buf)) || !strlen(name_buf))
1240         {
1241             close (fd);
1242             break;
1243         }
1244         close (fd);
1245
1246         if (strcmp (name_buf, cache_file) != 0)
1247             continue;
1248     } while (0);
1249
1250     current_dir_block = FcDirCacheProduce (set, &metadata);
1251
1252     if (metadata.count && !current_dir_block)
1253         goto bail1;
1254
1255     if (FcDebug () & FC_DBG_CACHE)
1256         printf ("FcDirCacheWriteDir cache_file \"%s\"\n", cache_file);
1257
1258     atomic = FcAtomicCreate ((FcChar8 *)cache_hashed);
1259     if (!atomic)
1260         goto bail1;
1261
1262     if (!FcAtomicLock (atomic))
1263     {
1264         /* Now try rewriting the original version of the file. */
1265         FcAtomicDestroy (atomic);
1266
1267         atomic = FcAtomicCreate ((FcChar8 *)cache_file);
1268         fd_orig = open (cache_file, O_RDONLY);
1269         if (fd_orig == -1)
1270             fd_orig = open((char *)FcAtomicOrigFile (atomic), O_RDONLY);
1271
1272         fd = open((char *)FcAtomicNewFile (atomic), O_RDWR | O_CREAT, 0666);
1273         if (fd == -1)
1274             goto bail2;
1275     }
1276
1277     /* In all cases, try opening the real location of the cache file first. */
1278     /* (even if that's not atomic.) */
1279     fd_orig = open (cache_file, O_RDONLY);
1280     if (fd_orig == -1)
1281         fd_orig = open((char *)FcAtomicOrigFile (atomic), O_RDONLY);
1282
1283     fd = open((char *)FcAtomicNewFile (atomic), O_RDWR | O_CREAT, 0666);
1284     if (fd == -1)
1285         goto bail3;
1286
1287     FcCacheWriteString (fd, cache_file);
1288
1289     current_arch_machine_name = FcCacheMachineSignature ();
1290     current_arch_start = 0;
1291
1292     if (fd_orig != -1)
1293         current_arch_start =
1294             FcCacheSkipToArch(fd_orig, current_arch_machine_name);
1295
1296     if (current_arch_start < 0)
1297     {
1298         off_t i = lseek(fd_orig, 0, SEEK_END);
1299         if (i < strlen (FC_GLOBAL_MAGIC_COOKIE)+1)
1300             i = strlen (FC_GLOBAL_MAGIC_COOKIE)+1;
1301         current_arch_start = FcCacheNextOffset (i);
1302     }
1303
1304     if (fd_orig != -1 && !FcCacheCopyOld(fd, fd_orig, current_arch_start))
1305         goto bail4;
1306
1307     if (fd_orig != -1)
1308         close (fd_orig);
1309
1310     current_arch_start = lseek(fd, 0, SEEK_CUR);
1311     if (ftruncate (fd, current_arch_start) == -1)
1312         goto bail4;
1313
1314     /* allocate space for subdir names in this block */
1315     dirs_count = 0;
1316     for (i = 0; i < dirs->size; i++)
1317         dirs_count += strlen((char *)dirs->strs[i]) + 1;
1318     dirs_count ++;
1319
1320     /* now write the address of the next offset */
1321     truncate_to = FcCacheNextOffset (FcCacheNextOffset (current_arch_start + sizeof (FcCache) + dirs_count) + metadata.count) - current_arch_start;
1322     header = malloc (10 + strlen (current_arch_machine_name));
1323     if (!header)
1324         goto bail4;
1325     sprintf (header, "%8x ", (int)truncate_to);
1326     strcat (header, current_arch_machine_name);
1327     if (!FcCacheWriteString (fd, header))
1328         goto bail5;
1329
1330     for (i = 0; i < dirs->size; i++)
1331         FcCacheWriteString (fd, (char *)dirs->strs[i]);
1332     FcCacheWriteString (fd, "");
1333
1334     if (write (fd, &metadata, sizeof(FcCache)) != sizeof(FcCache))
1335     {
1336         perror("write metadata");
1337         goto bail5;
1338     }
1339     if (metadata.count)
1340     {
1341         off_t off = FcCacheNextOffset (lseek(fd, 0, SEEK_END));
1342         if (lseek (fd, off, SEEK_SET) != off)
1343             perror("lseek");
1344         else if (write (fd, current_dir_block, metadata.count) !=
1345                  metadata.count)
1346             perror("write current_dir_block");
1347         free (current_dir_block);
1348     }
1349
1350     /* this actually serves to pad out the cache file, if needed */
1351     if (ftruncate (fd, current_arch_start + truncate_to) == -1)
1352         goto bail5;
1353
1354     free (header);
1355     close(fd);
1356     if (!FcAtomicReplaceOrig(atomic))
1357         goto bail5;
1358     FcStrFree ((FcChar8 *)cache_hashed);
1359     FcStrFree ((FcChar8 *)cache_file);
1360     FcAtomicUnlock (atomic);
1361     FcAtomicDestroy (atomic);
1362     return FcTrue;
1363
1364  bail5:
1365     free (header);
1366  bail4:
1367     close (fd);
1368  bail3:
1369     FcAtomicUnlock (atomic);
1370  bail2:
1371     FcAtomicDestroy (atomic);
1372  bail1:
1373     FcStrFree ((FcChar8 *)cache_hashed);
1374  bail0:
1375     unlink ((char *)cache_file);
1376     FcStrFree ((FcChar8 *)cache_file);
1377     if (current_dir_block)
1378         free (current_dir_block);
1379  bail:
1380     return FcFalse;
1381 }
1382
1383 static char *
1384 FcCacheMachineSignature ()
1385 {
1386     static char buf[MACHINE_SIGNATURE_SIZE];
1387     int32_t magic = ENDIAN_TEST;
1388     char * m = (char *)&magic;
1389
1390     sprintf (buf, "%2x%2x%2x%2x "
1391              "%4x %4x %4x %4x %4x %4x %4x %4x %4x %4x %4x %4x "
1392              "%4x %4x %4x %4x %4x %4x %4x %4x\n",
1393              m[0], m[1], m[2], m[3],
1394              (unsigned int)sizeof (char),
1395              (unsigned int)sizeof (char *),
1396              (unsigned int)sizeof (int),
1397              (unsigned int)sizeof (FcPattern),
1398              (unsigned int)sizeof (FcPatternEltPtr),
1399              (unsigned int)sizeof (struct _FcPatternElt *),
1400              (unsigned int)sizeof (FcPatternElt),
1401              (unsigned int)sizeof (FcObjectPtr),
1402              (unsigned int)sizeof (FcValueListPtr),
1403              (unsigned int)sizeof (FcValue),
1404              (unsigned int)sizeof (FcValueBinding),
1405              (unsigned int)sizeof (struct _FcValueList *),
1406              (unsigned int)sizeof (FcCharSet),
1407              (unsigned int)sizeof (FcCharLeaf **),
1408              (unsigned int)sizeof (FcChar16 *),
1409              (unsigned int)sizeof (FcChar16),
1410              (unsigned int)sizeof (FcCharLeaf),
1411              (unsigned int)sizeof (FcChar32),
1412              (unsigned int)sizeof (FcCache),
1413              (unsigned int)sysconf(_SC_PAGESIZE));
1414
1415     return buf;
1416 }
1417
1418 static int banks_ptr = 0, banks_alloc = 0;
1419 int * _fcBankId = 0, * _fcBankIdx = 0;
1420 static const char ** bankDirs = 0;
1421
1422 static FcBool
1423 FcCacheHaveBank (int bank)
1424 {
1425     int i;
1426
1427     if (bank < FC_BANK_FIRST)
1428         return FcTrue;
1429
1430     for (i = 0; i < banks_ptr; i++)
1431         if (_fcBankId[i] == bank)
1432             return FcTrue;
1433
1434     return FcFalse;
1435 }
1436
1437 int
1438 FcCacheBankToIndexMTF (int bank)
1439 {
1440     int i, j;
1441
1442     for (i = 0; i < banks_ptr; i++)
1443         if (_fcBankId[_fcBankIdx[i]] == bank)
1444         {
1445             int t = _fcBankIdx[i];
1446
1447             for (j = i; j > 0; j--)
1448                 _fcBankIdx[j] = _fcBankIdx[j-1];
1449             _fcBankIdx[0] = t;
1450             return t;
1451         }
1452
1453     if (banks_ptr >= banks_alloc)
1454     {
1455         int * b, * bidx;
1456         const char ** bds;
1457
1458         b = realloc (_fcBankId, (banks_alloc + 4) * sizeof(int));
1459         if (!b)
1460             return -1;
1461         _fcBankId = b;
1462
1463         bidx = realloc (_fcBankIdx, (banks_alloc + 4) * sizeof(int));
1464         if (!bidx)
1465             return -1;
1466         _fcBankIdx = bidx;
1467
1468         bds = realloc (bankDirs, (banks_alloc + 4) * sizeof (char *));
1469         if (!bds)
1470             return -1;
1471         bankDirs = bds;
1472
1473         banks_alloc += 4;
1474     }
1475
1476     i = banks_ptr++;
1477     _fcBankId[i] = bank;
1478     _fcBankIdx[i] = i;
1479     return i;
1480 }
1481
1482 static void
1483 FcCacheAddBankDir (int bank, const char * dir)
1484 {
1485     int bi = FcCacheBankToIndexMTF (bank);
1486
1487     if (bi < 0)
1488         return;
1489
1490     bankDirs[bi] = (const char *)FcStrCopy ((FcChar8 *)dir);
1491 }
1492
1493 const char *
1494 FcCacheFindBankDir (int bank)
1495 {
1496     int bi = FcCacheBankToIndex (bank);
1497     return bankDirs[bi];
1498 }
1499
1500 /*
1501  * This code implements the MD5 message-digest algorithm.
1502  * The algorithm is due to Ron Rivest.  This code was
1503  * written by Colin Plumb in 1993, no copyright is claimed.
1504  * This code is in the public domain; do with it what you wish.
1505  *
1506  * Equivalent code is available from RSA Data Security, Inc.
1507  * This code has been tested against that, and is equivalent,
1508  * except that you don't need to include two pages of legalese
1509  * with every copy.
1510  *
1511  * To compute the message digest of a chunk of bytes, declare an
1512  * MD5Context structure, pass it to MD5Init, call MD5Update as
1513  * needed on buffers full of bytes, and then call MD5Final, which
1514  * will fill a supplied 16-byte array with the digest.
1515  */
1516
1517 #ifndef HIGHFIRST
1518 #define byteReverse(buf, len)   /* Nothing */
1519 #else
1520 /*
1521  * Note: this code is harmless on little-endian machines.
1522  */
1523 void byteReverse(unsigned char *buf, unsigned longs)
1524 {
1525     FcChar32 t;
1526     do {
1527         t = (FcChar32) ((unsigned) buf[3] << 8 | buf[2]) << 16 |
1528             ((unsigned) buf[1] << 8 | buf[0]);
1529         *(FcChar32 *) buf = t;
1530         buf += 4;
1531     } while (--longs);
1532 }
1533 #endif
1534
1535 /*
1536  * Start MD5 accumulation.  Set bit count to 0 and buffer to mysterious
1537  * initialization constants.
1538  */
1539 static void MD5Init(struct MD5Context *ctx)
1540 {
1541     ctx->buf[0] = 0x67452301;
1542     ctx->buf[1] = 0xefcdab89;
1543     ctx->buf[2] = 0x98badcfe;
1544     ctx->buf[3] = 0x10325476;
1545
1546     ctx->bits[0] = 0;
1547     ctx->bits[1] = 0;
1548 }
1549
1550 /*
1551  * Update context to reflect the concatenation of another buffer full
1552  * of bytes.
1553  */
1554 static void MD5Update(struct MD5Context *ctx, unsigned char *buf, unsigned len)
1555 {
1556     FcChar32 t;
1557
1558     /* Update bitcount */
1559
1560     t = ctx->bits[0];
1561     if ((ctx->bits[0] = t + ((FcChar32) len << 3)) < t)
1562         ctx->bits[1]++;         /* Carry from low to high */
1563     ctx->bits[1] += len >> 29;
1564
1565     t = (t >> 3) & 0x3f;        /* Bytes already in shsInfo->data */
1566
1567     /* Handle any leading odd-sized chunks */
1568
1569     if (t) {
1570         unsigned char *p = (unsigned char *) ctx->in + t;
1571
1572         t = 64 - t;
1573         if (len < t) {
1574             memcpy(p, buf, len);
1575             return;
1576         }
1577         memcpy(p, buf, t);
1578         byteReverse(ctx->in, 16);
1579         MD5Transform(ctx->buf, (FcChar32 *) ctx->in);
1580         buf += t;
1581         len -= t;
1582     }
1583     /* Process data in 64-byte chunks */
1584
1585     while (len >= 64) {
1586         memcpy(ctx->in, buf, 64);
1587         byteReverse(ctx->in, 16);
1588         MD5Transform(ctx->buf, (FcChar32 *) ctx->in);
1589         buf += 64;
1590         len -= 64;
1591     }
1592
1593     /* Handle any remaining bytes of data. */
1594
1595     memcpy(ctx->in, buf, len);
1596 }
1597
1598 /*
1599  * Final wrapup - pad to 64-byte boundary with the bit pattern
1600  * 1 0* (64-bit count of bits processed, MSB-first)
1601  */
1602 static void MD5Final(unsigned char digest[16], struct MD5Context *ctx)
1603 {
1604     unsigned count;
1605     unsigned char *p;
1606
1607     /* Compute number of bytes mod 64 */
1608     count = (ctx->bits[0] >> 3) & 0x3F;
1609
1610     /* Set the first char of padding to 0x80.  This is safe since there is
1611        always at least one byte free */
1612     p = ctx->in + count;
1613     *p++ = 0x80;
1614
1615     /* Bytes of padding needed to make 64 bytes */
1616     count = 64 - 1 - count;
1617
1618     /* Pad out to 56 mod 64 */
1619     if (count < 8) {
1620         /* Two lots of padding:  Pad the first block to 64 bytes */
1621         memset(p, 0, count);
1622         byteReverse(ctx->in, 16);
1623         MD5Transform(ctx->buf, (FcChar32 *) ctx->in);
1624
1625         /* Now fill the next block with 56 bytes */
1626         memset(ctx->in, 0, 56);
1627     } else {
1628         /* Pad block to 56 bytes */
1629         memset(p, 0, count - 8);
1630     }
1631     byteReverse(ctx->in, 14);
1632
1633     /* Append length in bits and transform */
1634     ((FcChar32 *) ctx->in)[14] = ctx->bits[0];
1635     ((FcChar32 *) ctx->in)[15] = ctx->bits[1];
1636
1637     MD5Transform(ctx->buf, (FcChar32 *) ctx->in);
1638     byteReverse((unsigned char *) ctx->buf, 4);
1639     memcpy(digest, ctx->buf, 16);
1640     memset(ctx, 0, sizeof(ctx));        /* In case it's sensitive */
1641 }
1642
1643
1644 /* The four core functions - F1 is optimized somewhat */
1645
1646 /* #define F1(x, y, z) (x & y | ~x & z) */
1647 #define F1(x, y, z) (z ^ (x & (y ^ z)))
1648 #define F2(x, y, z) F1(z, x, y)
1649 #define F3(x, y, z) (x ^ y ^ z)
1650 #define F4(x, y, z) (y ^ (x | ~z))
1651
1652 /* This is the central step in the MD5 algorithm. */
1653 #define MD5STEP(f, w, x, y, z, data, s) \
1654         ( w += f(x, y, z) + data,  w = w<<s | w>>(32-s),  w += x )
1655
1656 /*
1657  * The core of the MD5 algorithm, this alters an existing MD5 hash to
1658  * reflect the addition of 16 longwords of new data.  MD5Update blocks
1659  * the data and converts bytes into longwords for this routine.
1660  */
1661 static void MD5Transform(FcChar32 buf[4], FcChar32 in[16])
1662 {
1663     register FcChar32 a, b, c, d;
1664
1665     a = buf[0];
1666     b = buf[1];
1667     c = buf[2];
1668     d = buf[3];
1669
1670     MD5STEP(F1, a, b, c, d, in[0] + 0xd76aa478, 7);
1671     MD5STEP(F1, d, a, b, c, in[1] + 0xe8c7b756, 12);
1672     MD5STEP(F1, c, d, a, b, in[2] + 0x242070db, 17);
1673     MD5STEP(F1, b, c, d, a, in[3] + 0xc1bdceee, 22);
1674     MD5STEP(F1, a, b, c, d, in[4] + 0xf57c0faf, 7);
1675     MD5STEP(F1, d, a, b, c, in[5] + 0x4787c62a, 12);
1676     MD5STEP(F1, c, d, a, b, in[6] + 0xa8304613, 17);
1677     MD5STEP(F1, b, c, d, a, in[7] + 0xfd469501, 22);
1678     MD5STEP(F1, a, b, c, d, in[8] + 0x698098d8, 7);
1679     MD5STEP(F1, d, a, b, c, in[9] + 0x8b44f7af, 12);
1680     MD5STEP(F1, c, d, a, b, in[10] + 0xffff5bb1, 17);
1681     MD5STEP(F1, b, c, d, a, in[11] + 0x895cd7be, 22);
1682     MD5STEP(F1, a, b, c, d, in[12] + 0x6b901122, 7);
1683     MD5STEP(F1, d, a, b, c, in[13] + 0xfd987193, 12);
1684     MD5STEP(F1, c, d, a, b, in[14] + 0xa679438e, 17);
1685     MD5STEP(F1, b, c, d, a, in[15] + 0x49b40821, 22);
1686
1687     MD5STEP(F2, a, b, c, d, in[1] + 0xf61e2562, 5);
1688     MD5STEP(F2, d, a, b, c, in[6] + 0xc040b340, 9);
1689     MD5STEP(F2, c, d, a, b, in[11] + 0x265e5a51, 14);
1690     MD5STEP(F2, b, c, d, a, in[0] + 0xe9b6c7aa, 20);
1691     MD5STEP(F2, a, b, c, d, in[5] + 0xd62f105d, 5);
1692     MD5STEP(F2, d, a, b, c, in[10] + 0x02441453, 9);
1693     MD5STEP(F2, c, d, a, b, in[15] + 0xd8a1e681, 14);
1694     MD5STEP(F2, b, c, d, a, in[4] + 0xe7d3fbc8, 20);
1695     MD5STEP(F2, a, b, c, d, in[9] + 0x21e1cde6, 5);
1696     MD5STEP(F2, d, a, b, c, in[14] + 0xc33707d6, 9);
1697     MD5STEP(F2, c, d, a, b, in[3] + 0xf4d50d87, 14);
1698     MD5STEP(F2, b, c, d, a, in[8] + 0x455a14ed, 20);
1699     MD5STEP(F2, a, b, c, d, in[13] + 0xa9e3e905, 5);
1700     MD5STEP(F2, d, a, b, c, in[2] + 0xfcefa3f8, 9);
1701     MD5STEP(F2, c, d, a, b, in[7] + 0x676f02d9, 14);
1702     MD5STEP(F2, b, c, d, a, in[12] + 0x8d2a4c8a, 20);
1703
1704     MD5STEP(F3, a, b, c, d, in[5] + 0xfffa3942, 4);
1705     MD5STEP(F3, d, a, b, c, in[8] + 0x8771f681, 11);
1706     MD5STEP(F3, c, d, a, b, in[11] + 0x6d9d6122, 16);
1707     MD5STEP(F3, b, c, d, a, in[14] + 0xfde5380c, 23);
1708     MD5STEP(F3, a, b, c, d, in[1] + 0xa4beea44, 4);
1709     MD5STEP(F3, d, a, b, c, in[4] + 0x4bdecfa9, 11);
1710     MD5STEP(F3, c, d, a, b, in[7] + 0xf6bb4b60, 16);
1711     MD5STEP(F3, b, c, d, a, in[10] + 0xbebfbc70, 23);
1712     MD5STEP(F3, a, b, c, d, in[13] + 0x289b7ec6, 4);
1713     MD5STEP(F3, d, a, b, c, in[0] + 0xeaa127fa, 11);
1714     MD5STEP(F3, c, d, a, b, in[3] + 0xd4ef3085, 16);
1715     MD5STEP(F3, b, c, d, a, in[6] + 0x04881d05, 23);
1716     MD5STEP(F3, a, b, c, d, in[9] + 0xd9d4d039, 4);
1717     MD5STEP(F3, d, a, b, c, in[12] + 0xe6db99e5, 11);
1718     MD5STEP(F3, c, d, a, b, in[15] + 0x1fa27cf8, 16);
1719     MD5STEP(F3, b, c, d, a, in[2] + 0xc4ac5665, 23);
1720
1721     MD5STEP(F4, a, b, c, d, in[0] + 0xf4292244, 6);
1722     MD5STEP(F4, d, a, b, c, in[7] + 0x432aff97, 10);
1723     MD5STEP(F4, c, d, a, b, in[14] + 0xab9423a7, 15);
1724     MD5STEP(F4, b, c, d, a, in[5] + 0xfc93a039, 21);
1725     MD5STEP(F4, a, b, c, d, in[12] + 0x655b59c3, 6);
1726     MD5STEP(F4, d, a, b, c, in[3] + 0x8f0ccc92, 10);
1727     MD5STEP(F4, c, d, a, b, in[10] + 0xffeff47d, 15);
1728     MD5STEP(F4, b, c, d, a, in[1] + 0x85845dd1, 21);
1729     MD5STEP(F4, a, b, c, d, in[8] + 0x6fa87e4f, 6);
1730     MD5STEP(F4, d, a, b, c, in[15] + 0xfe2ce6e0, 10);
1731     MD5STEP(F4, c, d, a, b, in[6] + 0xa3014314, 15);
1732     MD5STEP(F4, b, c, d, a, in[13] + 0x4e0811a1, 21);
1733     MD5STEP(F4, a, b, c, d, in[4] + 0xf7537e82, 6);
1734     MD5STEP(F4, d, a, b, c, in[11] + 0xbd3af235, 10);
1735     MD5STEP(F4, c, d, a, b, in[2] + 0x2ad7d2bb, 15);
1736     MD5STEP(F4, b, c, d, a, in[9] + 0xeb86d391, 21);
1737
1738     buf[0] += a;
1739     buf[1] += b;
1740     buf[2] += c;
1741     buf[3] += d;
1742 }