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         int slen;
  96         dest[size] = '\0';
  97         slen = strlen (dest);
  98
  99         lseek (fd, slen - size + 1, SEEK_CUR);
 100         return slen < len ? dest : 0;
 101     }
 102
 103     return 0;
 104 }
 105
 106 static void
 107 FcCacheSkipString (int fd)
 108 {
 109     char buf[256];
 110     int  size;
 111     int  slen;
 112
 113     while ( (size = read (fd, buf, sizeof (buf)-1)) > 0)
 114     {
 115         buf [size] = '\0';
 116         slen = strlen (buf);
 117         if (slen < size)
 118         {
 119             lseek (fd, slen - size + 1, SEEK_CUR);
 120             return;
 121         }
 122     }
 123 }
 124
 125 static FcBool
 126 FcCacheWriteString (int fd, const char *chars)
 127 {
 128     if (write (fd, chars, strlen(chars)+1) != strlen(chars)+1)
 129         return FcFalse;
 130     return FcTrue;
 131 }
 132
 133 static void
 134 FcGlobalCacheDirDestroy (FcGlobalCacheDir *d)
 135 {
 136     FcStrSetDestroy (d->subdirs);
 137     FcMemFree (FC_MEM_STRING, strlen (d->name)+1);
 138     free (d->name);
 139     FcMemFree (FC_MEM_CACHE, sizeof (FcGlobalCacheDir));
 140     free (d);
 141 }
 142
 143 FcGlobalCache *
 144 FcGlobalCacheCreate (void)
 145 {
 146     FcGlobalCache   *cache;
 147
 148     cache = malloc (sizeof (FcGlobalCache));
 149     if (!cache)
 150         return 0;
 151     FcMemAlloc (FC_MEM_CACHE, sizeof (FcGlobalCache));
 152     cache->dirs = 0;
 153     cache->updated = FcFalse;
 154     cache->fd = -1;
 155     return cache;
 156 }
 157
 158 void
 159 FcGlobalCacheDestroy (FcGlobalCache *cache)
 160 {
 161     FcGlobalCacheDir    *d, *next;
 162
 163     for (d = cache->dirs; d; d = next)
 164     {
 165         next = d->next;
 166         FcGlobalCacheDirDestroy (d);
 167     }
 168     FcMemFree (FC_MEM_CACHE, sizeof (FcGlobalCache));
 169     free (cache);
 170 }
 171
 172 void
 173 FcGlobalCacheLoad (FcGlobalCache    *cache,
 174                    FcStrSet         *staleDirs,
 175                    const FcChar8    *cache_file,
 176                    FcConfig         *config)
 177 {
 178     char                name_buf[FC_MAX_FILE_LEN];
 179     FcGlobalCacheDir    *d, *next;
 180     FcFileTime          config_time = FcConfigModifiedTime (config);
 181     char                * current_arch_machine_name;
 182     char                candidate_arch_machine_name[MACHINE_SIGNATURE_SIZE + 9];
 183     off_t               current_arch_start;
 184
 185     struct stat         cache_stat, dir_stat;
 186     char                subdirName[FC_MAX_FILE_LEN + 1 + 12 + 1];
 187
 188     if (stat ((char *) cache_file, &cache_stat) < 0)
 189         return;
 190
 191     cache->fd = open ((char *) cache_file, O_RDONLY);
 192     if (cache->fd == -1)
 193         return;
 194
 195     cache->updated = FcFalse;
 196
 197     if (!FcCacheReadString (cache->fd, name_buf, sizeof (name_buf)))
 198         goto bail_and_destroy;
 199     if (strcmp (name_buf, FC_GLOBAL_MAGIC_COOKIE) != 0)
 200         goto bail_and_destroy;
 201
 202     current_arch_machine_name = FcCacheMachineSignature ();
 203     current_arch_start = FcCacheSkipToArch(cache->fd,
 204                                            current_arch_machine_name);
 205     if (current_arch_start < 0)
 206         goto bail_and_destroy;
 207
 208     lseek (cache->fd, current_arch_start, SEEK_SET);
 209     if (!FcCacheReadString (cache->fd, candidate_arch_machine_name,
 210                             sizeof (candidate_arch_machine_name)))
 211         goto bail_and_destroy;
 212     if (strlen(candidate_arch_machine_name) == 0)
 213         goto bail_and_destroy;
 214
 215     while (1)
 216     {
 217         off_t targ;
 218
 219         if (!FcCacheReadString (cache->fd, name_buf, sizeof (name_buf)) ||
 220             !strlen(name_buf))
 221             break;
 222
 223         /* Directory must be older than the global cache file; also
 224            cache must be newer than the config file. */
 225         if (stat ((char *) name_buf, &dir_stat) < 0 ||
 226             dir_stat.st_mtime > cache_stat.st_mtime ||
 227             (config_time.set && cache_stat.st_mtime < config_time.time))
 228         {
 229             FcCache md;
 230             off_t off;
 231
 232             FcStrSetAdd (staleDirs, FcStrCopy ((FcChar8 *)name_buf));
 233
 234             /* skip subdirs */
 235             while (FcCacheReadString (cache->fd, subdirName,
 236                                       sizeof (subdirName)) &&
 237                    strlen (subdirName))
 238                 ;
 239
 240             if (read (cache->fd, &md, sizeof (FcCache)) != sizeof(FcCache))
 241             {
 242                 perror ("read metadata");
 243                 goto bail1;
 244             }
 245             off = FcCacheNextOffset (lseek(cache->fd, 0, SEEK_CUR)) + md.count;
 246             if (lseek (cache->fd, off, SEEK_SET) != off)
 247             {
 248                 perror ("lseek");
 249                 goto bail1;
 250             }
 251             continue;
 252         }
 253
 254         d = malloc (sizeof (FcGlobalCacheDir));
 255         if (!d)
 256             goto bail1;
 257
 258         d->next = cache->dirs;
 259         cache->dirs = d;
 260
 261         d->name = (char *)FcStrCopy ((FcChar8 *)name_buf);
 262         d->ent = 0;
 263         d->state = FcGCDirFileRead;
 264
 265         d->subdirs = FcStrSetCreate();
 266         do
 267         {
 268             if (!FcCacheReadString (cache->fd, subdirName,
 269                                     sizeof (subdirName)) ||
 270                 !strlen (subdirName))
 271                 break;
 272             FcStrSetAdd (d->subdirs, (FcChar8 *)subdirName);
 273         } while (1);
 274
 275         d->offset = lseek (cache->fd, 0, SEEK_CUR);
 276         if (read (cache->fd, &d->metadata, sizeof (FcCache)) != sizeof (FcCache))
 277             goto bail1;
 278         targ = FcCacheNextOffset (lseek(cache->fd, 0, SEEK_CUR)) + d->metadata.count;
 279         if (lseek (cache->fd, targ, SEEK_SET) != targ)
 280             goto bail1;
 281     }
 282     return;
 283
 284  bail1:
 285     for (d = cache->dirs; d; d = next)
 286     {
 287         next = d->next;
 288         free (d);
 289     }
 290     cache->dirs = 0;
 291
 292     close (cache->fd);
 293     cache->fd = -1;
 294     return;
 295
 296  bail_and_destroy:
 297     close (cache->fd);
 298     cache->fd = -1;
 299
 300     if (stat ((char *) cache_file, &cache_stat) == 0)
 301         unlink ((char *)cache_file);
 302
 303     return;
 304
 305 }
 306
 307 FcBool
 308 FcGlobalCacheReadDir (FcFontSet *set, FcStrSet *dirs, FcGlobalCache * cache, const char *dir, FcConfig *config)
 309 {
 310     FcGlobalCacheDir    *d;
 311     int                 i;
 312
 313     if (cache->fd == -1)
 314         return FcFalse;
 315
 316     if (!(dir = (char *)FcConfigNormalizeFontDir (config, (FcChar8 *)dir)))
 317         return FcFalse; /* non-existing directory */
 318
 319     for (d = cache->dirs; d; d = d->next)
 320     {
 321         if (strcmp (d->name, dir) == 0)
 322         {
 323             if (d->state == FcGCDirDisabled)
 324                 return FcFalse;
 325
 326             if (d->state == FcGCDirFileRead)
 327             {
 328                 lseek (cache->fd, d->offset, SEEK_SET);
 329                 if (!FcDirCacheConsume (cache->fd, d->name, set, config))
 330                     return FcFalse;
 331
 332                 for (i = 0; i < d->subdirs->num; i++)
 333                     FcStrSetAdd (dirs, (FcChar8 *)d->subdirs->strs[i]);
 334
 335                 d->state = FcGCDirConsumed;
 336             }
 337             return FcTrue;
 338         }
 339     }
 340
 341     return FcFalse;
 342 }
 343
 344 static FcGlobalCacheDir *
 345 FcGlobalCacheDirFind (FcGlobalCache *cache, const char *name)
 346 {
 347     FcGlobalCacheDir * d;
 348
 349     if (!cache || !name)
 350         return NULL;
 351
 352     for (d = cache->dirs; d; d = d->next)
 353         if (strcmp((const char *)d->name, (const char *)name) == 0)
 354             return d;
 355
 356     return NULL;
 357  }
 358
 359 FcBool
 360 FcGlobalCacheUpdate (FcGlobalCache  *cache,
 361                      FcStrSet       *dirs,
 362                      const char     *orig_name,
 363                      FcFontSet      *set,
 364                      FcConfig       *config)
 365 {
 366     FcGlobalCacheDir    *d;
 367     int                 i;
 368     const char *name;
 369
 370     name = (char *)FcConfigNormalizeFontDir (config, (FcChar8 *)orig_name);
 371     if (!name)
 372     {
 373         fprintf(stderr, "Invalid directory name %s\n", orig_name);
 374         return FcFalse;
 375     }
 376
 377     d = FcGlobalCacheDirFind (cache, name);
 378
 379     if (!d)
 380     {
 381         d = malloc (sizeof (FcGlobalCacheDir));
 382         if (!d)
 383             return FcFalse;
 384         d->next = cache->dirs;
 385         cache->dirs = d;
 386     } else {
 387         /* free old resources */
 388         FcStrFree ((FcChar8 *)d->name);
 389         free (d->ent);
 390         FcStrSetDestroy (d->subdirs);
 391     }
 392
 393     cache->updated = FcTrue;
 394
 395     d->name = (char *)FcStrCopy ((FcChar8 *)name);
 396     d->ent = FcDirCacheProduce (set, &d->metadata);
 397     d->offset = 0;
 398     d->subdirs = FcStrSetCreate();
 399     d->state = FcGCDirUpdated;
 400     for (i = 0; i < dirs->num; i++)
 401         FcStrSetAdd (d->subdirs, dirs->strs[i]);
 402     return FcTrue;
 403 }
 404
 405 FcBool
 406 FcGlobalCacheSave (FcGlobalCache    *cache,
 407                    const FcChar8    *cache_file,
 408                    FcConfig         *config)
 409 {
 410     int                 fd, fd_orig, i;
 411     FcGlobalCacheDir    *dir;
 412     FcAtomic            *atomic;
 413     off_t               current_arch_start = 0, truncate_to;
 414     char                * current_arch_machine_name, * header;
 415
 416     if (!cache->updated)
 417         return FcTrue;
 418
 419 #if defined (HAVE_GETUID) && defined (HAVE_GETEUID)
 420     /* Set-UID programs can't safely update the cache */
 421     if (getuid () != geteuid ())
 422         return FcFalse;
 423 #endif
 424
 425     atomic = FcAtomicCreate (cache_file);
 426     if (!atomic)
 427         return FcFalse;
 428
 429     if (!FcAtomicLock (atomic))
 430         goto bail1;
 431     fd = open ((char *) FcAtomicNewFile(atomic), O_RDWR | O_CREAT,
 432                S_IRUSR | S_IWUSR);
 433     if (fd == -1)
 434         goto bail2;
 435     FcCacheWriteString (fd, FC_GLOBAL_MAGIC_COOKIE);
 436
 437     fd_orig = open ((char *) FcAtomicOrigFile(atomic), O_RDONLY);
 438
 439     current_arch_machine_name = FcCacheMachineSignature ();
 440     if (fd_orig == -1)
 441         current_arch_start = 0;
 442     else
 443         current_arch_start = FcCacheSkipToArch (fd_orig,
 444                                                 current_arch_machine_name);
 445
 446     if (current_arch_start < 0)
 447     {
 448         off_t i = lseek(fd_orig, 0, SEEK_END);
 449         if (i < strlen (FC_GLOBAL_MAGIC_COOKIE)+1)
 450             i = strlen (FC_GLOBAL_MAGIC_COOKIE)+1;
 451         current_arch_start = FcCacheNextOffset (i);
 452     }
 453
 454     if (!FcCacheCopyOld(fd, fd_orig, current_arch_start))
 455         goto bail3;
 456
 457     current_arch_start = lseek(fd, 0, SEEK_CUR);
 458     if (ftruncate (fd, current_arch_start) == -1)
 459         goto bail3;
 460
 461     header = malloc (10 + strlen (current_arch_machine_name));
 462     if (!header)
 463         goto bail3;
 464
 465     truncate_to = current_arch_start + strlen(current_arch_machine_name) + 11;
 466     for (dir = cache->dirs; dir; dir = dir->next)
 467     {
 468         if (dir->state == FcGCDirDisabled)
 469             continue;
 470         truncate_to += strlen(dir->name) + 1;
 471         truncate_to += sizeof (FcCache);
 472         truncate_to = FcCacheNextOffset (truncate_to);
 473         truncate_to += dir->metadata.count;
 474
 475         for (i = 0; i < dir->subdirs->size; i++)
 476             truncate_to += strlen((char *)dir->subdirs->strs[i]) + 1;
 477         truncate_to ++;
 478     }
 479     truncate_to -= current_arch_start;
 480
 481     sprintf (header, "%8x ", (int)truncate_to);
 482     strcat (header, current_arch_machine_name);
 483     if (!FcCacheWriteString (fd, header))
 484         goto bail4;
 485
 486     for (dir = cache->dirs; dir; dir = dir->next)
 487     {
 488         const char * d;
 489         off_t off;
 490
 491         if (!dir->name || dir->state == FcGCDirDisabled)
 492             continue;
 493         d = (const char *)FcConfigNormalizeFontDir (config, (const FcChar8 *)dir->name);
 494         if (!d)
 495             continue;
 496
 497         if (dir->metadata.count && !dir->ent)
 498         {
 499             if (dir->state == FcGCDirUpdated || fd_orig < 0)
 500             {
 501                 fprintf(stderr, "Invalid metadata entry for %s, skipping...\n", d);
 502                 continue;
 503             }
 504             /* copy the old content */
 505             dir->ent = malloc (dir->metadata.count);
 506             if (!dir->ent)
 507             {
 508                 perror("malloc error");
 509                 continue;
 510             }
 511             off = FcCacheNextOffset (dir->offset + sizeof(FcCache));
 512             if (lseek (fd_orig, off, SEEK_SET) != off)
 513             {
 514                 perror("lseek");
 515                 free(dir->ent);
 516                 continue;
 517             }
 518             if (read (fd_orig, dir->ent, dir->metadata.count)
 519                 != dir->metadata.count)
 520             {
 521                 perror("read");
 522                 free(dir->ent);
 523                 continue;
 524             }
 525         }
 526
 527         FcCacheWriteString (fd, d);
 528
 529         for (i = 0; i < dir->subdirs->size; i++)
 530             FcCacheWriteString (fd, (char *)dir->subdirs->strs[i]);
 531         FcCacheWriteString (fd, "");
 532
 533         if (write (fd, &dir->metadata, sizeof(FcCache)) != sizeof(FcCache))
 534         {
 535             perror ("write metadata");
 536             free (dir->ent);
 537             continue;
 538         }
 539         off = FcCacheNextOffset (lseek(fd, 0, SEEK_CUR));
 540         if (lseek (fd, off, SEEK_SET) != off)
 541         {
 542             perror ("lseek");
 543             free (dir->ent);
 544             continue;
 545         }
 546         if (dir->metadata.count)
 547         {
 548             if (write (fd, dir->ent, dir->metadata.count) != dir->metadata.count)
 549             {
 550                 perror ("write dirent");
 551                 free (dir->ent);
 552                 continue;
 553             }
 554         }
 555         free (dir->ent);
 556     }
 557     FcCacheWriteString (fd, "");
 558
 559     if (close (fd) == -1)
 560         goto bail25;
 561
 562     close (fd_orig);
 563     fd_orig = -1;
 564
 565     if (!FcAtomicReplaceOrig (atomic))
 566         goto bail25;
 567
 568     FcAtomicUnlock (atomic);
 569     FcAtomicDestroy (atomic);
 570
 571     cache->updated = FcFalse;
 572     return FcTrue;
 573
 574  bail4:
 575     free (header);
 576  bail3:
 577     if (fd_orig != -1)
 578         close (fd_orig);
 579
 580     close (fd);
 581  bail25:
 582     FcAtomicDeleteNew (atomic);
 583  bail2:
 584     FcAtomicUnlock (atomic);
 585  bail1:
 586     FcAtomicDestroy (atomic);
 587     return FcFalse;
 588 }
 589
 590 /*
 591  * Find the next presumably-mmapable offset after the supplied file
 592  * position.
 593  */
 594 static int
 595 FcCacheNextOffset(off_t w)
 596 {
 597     static long pagesize = -1;
 598     if (pagesize == -1)
 599         pagesize = sysconf(_SC_PAGESIZE);
 600     if (w % pagesize == 0)
 601         return w;
 602     else
 603         return ((w / pagesize)+1)*pagesize;
 604 }
 605
 606 /* return the address of the segment for the provided arch,
 607  * or -1 if arch not found */
 608 static off_t
 609 FcCacheSkipToArch (int fd, const char * arch)
 610 {
 611     char candidate_arch_machine_name_count[MACHINE_SIGNATURE_SIZE + 9];
 612     char * candidate_arch;
 613     off_t current_arch_start = 0;
 614
 615     lseek (fd, 0, SEEK_SET);
 616     FcCacheSkipString (fd);
 617     current_arch_start = lseek (fd, 0, SEEK_CUR);
 618
 619     /* skip arches that are not the current arch */
 620     while (1)
 621     {
 622         long bs;
 623
 624         if (lseek (fd, current_arch_start, SEEK_SET) != current_arch_start)
 625             return -1;
 626
 627         if (FcCacheReadString (fd, candidate_arch_machine_name_count,
 628                                 sizeof (candidate_arch_machine_name_count)) == 0)
 629             return -1;
 630         if (!strlen(candidate_arch_machine_name_count))
 631             return -1;
 632         bs = strtol(candidate_arch_machine_name_count, &candidate_arch, 16);
 633
 634         // count = 0 should probably be distinguished from the !bs condition
 635         if (!bs || bs < strlen (candidate_arch_machine_name_count))
 636             return -1;
 637
 638         candidate_arch++; /* skip leading space */
 639
 640         if (strcmp (candidate_arch, arch)==0)
 641             return current_arch_start;
 642         current_arch_start += bs;
 643     }
 644
 645     return -1;
 646 }
 647
 648 /* Cuts out the segment at the file pointer (moves everything else
 649  * down to cover it), and leaves the file pointer at the end of the
 650  * file. */
 651 static FcBool
 652 FcCacheCopyOld (int fd, int fd_orig, off_t start)
 653 {
 654     char * buf = malloc (8192);
 655     char candidate_arch_machine_name[MACHINE_SIGNATURE_SIZE + 9];
 656     long bs;
 657     int c, bytes_skipped;
 658     off_t loc;
 659
 660     if (!buf)
 661         return FcFalse;
 662
 663     loc = 0;
 664     lseek (fd, 0, SEEK_SET); lseek (fd_orig, 0, SEEK_SET);
 665     do
 666     {
 667         int b = 8192;
 668         if (loc + b > start)
 669             b = start - loc;
 670
 671         if ((c = read (fd_orig, buf, b)) <= 0)
 672             break;
 673         if (write (fd, buf, c) < 0)
 674             goto bail;
 675
 676         loc += c;
 677     }
 678     while (c > 0);
 679
 680     lseek (fd, start, SEEK_SET);
 681     if (FcCacheReadString (fd, candidate_arch_machine_name,
 682                            sizeof (candidate_arch_machine_name)) == 0)
 683         goto done;
 684     if (!strlen(candidate_arch_machine_name))
 685         goto done;
 686
 687     bs = strtol(candidate_arch_machine_name, 0, 16);
 688     if (bs == 0)
 689         goto done;
 690
 691     bytes_skipped = 0;
 692     do
 693     {
 694         lseek (fd, start+bs+bytes_skipped, SEEK_SET);
 695         if ((c = read (fd, buf, 8192)) <= 0)
 696             break;
 697         lseek (fd, start+bytes_skipped, SEEK_SET);
 698         if (write (fd, buf, c) < 0)
 699             goto bail;
 700         bytes_skipped += c;
 701     }
 702     while (c > 0);
 703     lseek (fd, start+bytes_skipped, SEEK_SET);
 704
 705  done:
 706     free (buf);
 707     return FcTrue;
 708
 709  bail:
 710     free (buf);
 711     return FcFalse;
 712 }
 713
 714 /* Does not check that the cache has the appropriate arch section. */
 715 /* Also, this can be fooled if the original location has a stale
 716  * cache, and the hashed location has an up-to-date cache.  Oh well,
 717  * sucks to be you in that case! */
 718 FcBool
 719 FcDirCacheValid (const FcChar8 *dir)
 720 {
 721     struct stat file_stat, dir_stat;
 722     int         fd;
 723
 724     if (stat ((char *) dir, &dir_stat) < 0)
 725         return FcFalse;
 726
 727     fd = FcDirCacheOpen (dir);
 728
 729     if (fd < 0)
 730         goto bail;
 731     if (fstat (fd, &file_stat) < 0)
 732         goto bail;
 733
 734     close (fd);
 735
 736     /*
 737      * If the directory has been modified more recently than
 738      * the cache file, the cache is not valid
 739      */
 740     if (dir_stat.st_mtime > file_stat.st_mtime)
 741         return FcFalse;
 742
 743     return FcTrue;
 744
 745  bail:
 746     close (fd);
 747     return FcFalse;
 748 }
 749
 750 /* Assumes that the cache file in 'dir' exists.
 751  * Checks that the cache has the appropriate arch section. */
 752 FcBool
 753 FcDirCacheHasCurrentArch (const FcChar8 *dir)
 754 {
 755     int         fd;
 756     off_t       current_arch_start;
 757     char        *current_arch_machine_name;
 758
 759     fd = FcDirCacheOpen (dir);
 760     if (fd < 0)
 761         goto bail;
 762
 763     current_arch_machine_name = FcCacheMachineSignature();
 764     current_arch_start = FcCacheSkipToArch(fd, current_arch_machine_name);
 765     close (fd);
 766
 767     if (current_arch_start < 0)
 768         return FcFalse;
 769
 770     return FcTrue;
 771
 772  bail:
 773     return FcFalse;
 774 }
 775
 776 FcBool
 777 FcDirCacheUnlink (const FcChar8 *dir, FcConfig *config)
 778 {
 779     char        *cache_file;
 780     char        *cache_hashed = 0;
 781     int         fd, collisions;
 782     struct stat cache_stat;
 783     char        name_buf[FC_MAX_FILE_LEN];
 784
 785     dir = FcConfigNormalizeFontDir (config, dir);
 786     cache_file = (char *)FcStrPlus (dir, (FcChar8 *) "/" FC_DIR_CACHE_FILE);
 787     if (!cache_file)
 788         return FcFalse;
 789
 790     /* First remove normal cache file. */
 791     if (stat ((char *) cache_file, &cache_stat) == 0 &&
 792         unlink ((char *)cache_file) != 0)
 793         goto bail;
 794
 795     /* Next remove any applicable hashed files. */
 796     fd = -1; collisions = 0;
 797     do
 798     {
 799         if (cache_hashed)
 800             FcStrFree ((FcChar8 *)cache_hashed);
 801
 802         cache_hashed = FcDirCacheHashName (cache_file, collisions++);
 803         if (!cache_hashed)
 804             goto bail;
 805
 806         if (fd > 0)
 807             close (fd);
 808         fd = open(cache_hashed, O_RDONLY);
 809         if (fd == -1)
 810         {
 811             FcStrFree ((FcChar8 *)cache_file);
 812             return FcTrue;
 813         }
 814
 815         if (!FcCacheReadString (fd, name_buf, sizeof (name_buf)) || !strlen(name_buf))
 816         {
 817             FcStrFree ((FcChar8 *)cache_hashed);
 818             goto bail;
 819         }
 820     } while (strcmp (name_buf, cache_file) != 0);
 821
 822     close (fd);
 823
 824     if (stat ((char *) cache_hashed, &cache_stat) == 0 &&
 825         unlink ((char *)cache_hashed) != 0)
 826     {
 827         FcStrFree ((FcChar8 *)cache_hashed);
 828         goto bail;
 829     }
 830
 831     FcStrFree ((FcChar8 *)cache_file);
 832     FcStrFree ((FcChar8 *)cache_hashed);
 833     return FcTrue;
 834
 835  bail:
 836     FcStrFree ((FcChar8 *)cache_file);
 837     return FcFalse;
 838 }
 839
 840 static int
 841 FcCacheReadDirs (FcConfig * config, FcGlobalCache * cache,
 842                  FcStrList *list, FcFontSet * set, FcStrSet *processed_dirs)
 843 {
 844     int                 ret = 0;
 845     FcChar8             *dir;
 846     const FcChar8       *name;
 847     FcStrSet            *subdirs;
 848     FcStrList           *sublist;
 849     struct stat         statb;
 850     FcGlobalCacheDir   *d;
 851
 852     /*
 853      * Read in the results from 'list'.
 854      */
 855     while ((dir = FcStrListNext (list)))
 856     {
 857         if (!FcConfigAcceptFilename (config, dir))
 858             continue;
 859
 860         /* Skip this directory if already updated
 861          * to avoid the looped directories via symlinks
 862          */
 863         name = FcConfigNormalizeFontDir (config, dir);
 864         if (name)
 865         {
 866             if (FcStrSetMember (processed_dirs, dir))
 867                 continue;
 868             FcStrSetAdd (processed_dirs, dir);
 869         }
 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 *)name)) != 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 }