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