fc-glyphname/fc-glyphname.c

   1 /*
   2  * $Id$
   3  *
   4  * Copyright © 2003 Keith Packard
   5  *
   6  * Permission to use, copy, modify, distribute, and sell this software and its
   7  * documentation for any purpose is hereby granted without fee, provided that
   8  * the above copyright notice appear in all copies and that both that
   9  * copyright notice and this permission notice appear in supporting
  10  * documentation, and that the name of Keith Packard not be used in
  11  * advertising or publicity pertaining to distribution of the software without
  12  * specific, written prior permission.  Keith Packard makes no
  13  * representations about the suitability of this software for any purpose.  It
  14  * is provided "as is" without express or implied warranty.
  15  *
  16  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  17  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  18  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  19  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  20  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  21  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  22  * PERFORMANCE OF THIS SOFTWARE.
  23  */
  24
  25 #include "fcint.h"
  26
  27 /* stub definitions for declarations from fcint.h.. */
  28 int * _fcBankId = 0, * _fcBankIdx = 0;
  29
  30 int
  31 FcCacheBankToIndexMTF (int bank)
  32 {
  33     return 0;
  34 }
  35 /* end stub definitions */
  36
  37 static int
  38 rawindex (const FcGlyphName *gn);
  39
  40 static void
  41 scan (FILE *f, char *filename);
  42
  43 static int
  44 isprime (int i);
  45
  46 static void
  47 find_hash (void);
  48
  49 static FcChar32
  50 FcHashGlyphName (const FcChar8 *name);
  51
  52 static void
  53 insert (FcGlyphName *gn, FcGlyphName **table, FcChar32 h);
  54
  55 static void
  56 dump (FcGlyphName * const *table, const char *name);
  57
  58 static FcGlyphName *
  59 FcAllocGlyphName (FcChar32 ucs, FcChar8 *name)
  60 {
  61     FcGlyphName *gn;
  62
  63     gn = malloc (sizeof (FcGlyphName) + strlen ((char *) name));
  64     if (!gn)
  65         return 0;
  66     gn->ucs = ucs;
  67     strcpy ((char *) gn->name, (char *) name);
  68     return gn;
  69 }
  70
  71 static void
  72 fatal (const char *file, int lineno, const char *msg)
  73 {
  74     if (lineno)
  75         fprintf (stderr, "%s:%d: %s\n", file, lineno, msg);
  76     else
  77         fprintf (stderr, "%s: %s\n", file, msg);
  78
  79     exit (1);
  80 }
  81
  82 #define MAX_GLYPHFILE       256
  83 #define MAX_GLYPHNAME       10240
  84 #define MAX_NAMELEN         1024
  85
  86 FcGlyphName *raw[MAX_GLYPHNAME];
  87 int         nraw;
  88 int         max_name_len;
  89 FcGlyphName *name_to_ucs[MAX_GLYPHNAME*2];
  90 FcGlyphName *ucs_to_name[MAX_GLYPHNAME*2];
  91 int         hash, rehash;
  92
  93 static int
  94 rawindex (const FcGlyphName *gn)
  95 {
  96     int i;
  97
  98     for (i = 0; i < nraw; i++)
  99         if (raw[i] == gn)
 100             return i;
 101     return -1;
 102 }
 103
 104 static void
 105 scan (FILE *f, char *filename)
 106 {
 107     char            buf[MAX_NAMELEN];
 108     char            name[MAX_NAMELEN];
 109     unsigned long   ucs;
 110     FcGlyphName     *gn;
 111     int             lineno = 0;
 112     int             len;
 113
 114     while (fgets (buf, sizeof (buf), f))
 115     {
 116         lineno++;
 117         if (sscanf (buf, "%[^;];%lx\n", name, &ucs) != 2)
 118             continue;
 119         gn = FcAllocGlyphName ((FcChar32) ucs, (FcChar8 *) name);
 120         if (!gn)
 121             fatal (filename, lineno, "out of memory");
 122         len = strlen (name);
 123         if (len > max_name_len)
 124             max_name_len = len;
 125         raw[nraw++] = gn;
 126     }
 127 }
 128
 129 static int compare_string (const void *a, const void *b)
 130 {
 131     const char    *const *as = a, *const *bs = b;
 132     return strcmp (*as, *bs);
 133 }
 134
 135 static int compare_glyphname (const void *a, const void *b)
 136 {
 137     const FcGlyphName   *const *ag = a, *const *bg = b;
 138
 139     return strcmp ((char *) (*ag)->name, (char *) (*bg)->name);
 140 }
 141
 142 static int
 143 isqrt (int a)
 144 {
 145     int     l, h, m;
 146
 147     l = 2;
 148     h = a/2;
 149     while ((h-l) > 1)
 150     {
 151         m = (h+l) >> 1;
 152         if (m * m < a)
 153             l = m;
 154         else
 155             h = m;
 156     }
 157     return h;
 158 }
 159
 160 static int
 161 isprime (int i)
 162 {
 163     int l, t;
 164
 165     if (i < 2)
 166         return FcFalse;
 167     if ((i & 1) == 0)
 168     {
 169         if (i == 2)
 170             return FcTrue;
 171         return FcFalse;
 172     }
 173     l = isqrt (i) + 1;
 174     for (t = 3; t <= l; t += 2)
 175         if (i % t == 0)
 176             return 0;
 177     return 1;
 178 }
 179
 180 /*
 181  * Find a prime pair that leaves at least 25% of the hash table empty
 182  */
 183
 184 static void
 185 find_hash (void)
 186 {
 187     int h;
 188
 189     h = nraw + nraw / 4;
 190     if ((h & 1) == 0)
 191         h++;
 192     while (!isprime(h-2) || !isprime(h))
 193         h += 2;
 194     hash = h;
 195     rehash = h-2;
 196 }
 197
 198 static FcChar32
 199 FcHashGlyphName (const FcChar8 *name)
 200 {
 201     FcChar32    h = 0;
 202     FcChar8     c;
 203
 204     while ((c = *name++))
 205     {
 206         h = ((h << 1) | (h >> 31)) ^ c;
 207     }
 208     return h;
 209 }
 210
 211 static void
 212 insert (FcGlyphName *gn, FcGlyphName **table, FcChar32 h)
 213 {
 214     int         i, r = 0;
 215
 216     i = (int) (h % hash);
 217     while (table[i])
 218     {
 219         if (!r) r = (int) (h % rehash);
 220         i += r;
 221         if (i >= hash)
 222             i -= hash;
 223     }
 224     table[i] = gn;
 225 }
 226
 227 static void
 228 dump (FcGlyphName * const *table, const char *name)
 229 {
 230     int i;
 231
 232     printf ("static const FcGlyphName   *%s[%d] = {\n", name, hash);
 233
 234     for (i = 0; i < hash; i++)
 235         if (table[i])
 236             printf ("(FcGlyphName *) &glyph%d,\n", rawindex(table[i]));
 237         else
 238             printf ("0,\n");
 239
 240     printf ("};\n");
 241 }
 242
 243 int
 244 main (int argc, char **argv)
 245 {
 246     char        *files[MAX_GLYPHFILE];
 247     char        line[1024];
 248     FILE        *f;
 249     int         i;
 250
 251     i = 0;
 252     while (argv[i+1])
 253     {
 254         if (i == MAX_GLYPHFILE)
 255             fatal (*argv, 0, "Too many glyphname files");
 256         files[i] = argv[i+1];
 257         i++;
 258     }
 259     files[i] = 0;
 260     qsort (files, i, sizeof (char *), compare_string);
 261     for (i = 0; files[i]; i++)
 262     {
 263         f = fopen (files[i], "r");
 264         if (!f)
 265             fatal (files[i], 0, strerror (errno));
 266         scan (f, files[i]);
 267         fclose (f);
 268     }
 269     qsort (raw, nraw, sizeof (FcGlyphName *), compare_glyphname);
 270
 271     find_hash ();
 272
 273     for (i = 0; i < nraw; i++)
 274     {
 275         insert (raw[i], name_to_ucs, FcHashGlyphName (raw[i]->name));
 276         insert (raw[i], ucs_to_name, raw[i]->ucs);
 277     }
 278
 279     /*
 280      * Scan the input until the marker is found
 281      */
 282
 283     while (fgets (line, sizeof (line), stdin))
 284     {
 285         if (!strncmp (line, "@@@", 3))
 286             break;
 287         fputs (line, stdout);
 288     }
 289
 290     printf ("/* %d glyphnames in %d entries, %d%% occupancy */\n\n",
 291             nraw, hash, nraw * 100 / hash);
 292
 293     printf ("#define FC_GLYPHNAME_HASH %u\n", hash);
 294     printf ("#define FC_GLYPHNAME_REHASH %u\n", rehash);
 295     printf ("#define FC_GLYPHNAME_MAXLEN %d\n\n", max_name_len);
 296
 297     /*
 298      * Dump out entries
 299      */
 300
 301     for (i = 0; i < nraw; i++)
 302         printf ("static const struct { const FcChar32 ucs; const FcChar8 name[%d]; }"
 303                 " glyph%d = { 0x%lx, \"%s\" };\n",
 304                 (int) strlen ((char *) raw[i]->name) + 1,
 305                 i, (unsigned long) raw[i]->ucs, raw[i]->name);
 306
 307     /*
 308      * Dump out name_to_ucs table
 309      */
 310
 311     dump (name_to_ucs, "name_to_ucs");
 312
 313     /*
 314      * Dump out ucs_to_name table
 315      */
 316     dump (ucs_to_name, "ucs_to_name");
 317
 318     while (fgets (line, sizeof (line), stdin))
 319         fputs (line, stdout);
 320
 321     fflush (stdout);
 322     exit (ferror (stdout));
 323 }