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 FcValueList ** _fcValueLists = 0;
  30 FcPatternElt ** _fcPatternElts = 0;
  31 int FcDebugVal = 0;
  32
  33 int
  34 FcCacheBankToIndexMTF (int bank)
  35 {
  36     return 0;
  37 }
  38 /* end stub definitions */
  39
  40 static int
  41 rawindex (const FcGlyphName *gn);
  42
  43 static void
  44 scan (FILE *f, char *filename);
  45
  46 static int
  47 isprime (int i);
  48
  49 static void
  50 find_hash (void);
  51
  52 static FcChar32
  53 FcHashGlyphName (const FcChar8 *name);
  54
  55 static void
  56 insert (FcGlyphName *gn, FcGlyphName **table, FcChar32 h);
  57
  58 static void
  59 dump (FcGlyphName * const *table, const char *name);
  60
  61 static FcGlyphName *
  62 FcAllocGlyphName (FcChar32 ucs, FcChar8 *name)
  63 {
  64     FcGlyphName *gn;
  65
  66     gn = malloc (sizeof (FcGlyphName) + strlen ((char *) name));
  67     if (!gn)
  68         return 0;
  69     gn->ucs = ucs;
  70     strcpy ((char *) gn->name, (char *) name);
  71     return gn;
  72 }
  73
  74 static void
  75 fatal (const char *file, int lineno, const char *msg)
  76 {
  77     if (lineno)
  78         fprintf (stderr, "%s:%d: %s\n", file, lineno, msg);
  79     else
  80         fprintf (stderr, "%s: %s\n", file, msg);
  81
  82     exit (1);
  83 }
  84
  85 #define MAX_GLYPHFILE       256
  86 #define MAX_GLYPHNAME       10240
  87 #define MAX_NAMELEN         1024
  88
  89 static FcGlyphName *raw[MAX_GLYPHNAME];
  90 static int          nraw;
  91 static int          max_name_len;
  92 static FcGlyphName *name_to_ucs[MAX_GLYPHNAME*2];
  93 static FcGlyphName *ucs_to_name[MAX_GLYPHNAME*2];
  94 static unsigned int hash, rehash;
  95
  96 static int
  97 rawindex (const FcGlyphName *gn)
  98 {
  99     int i;
 100
 101     for (i = 0; i < nraw; i++)
 102         if (raw[i] == gn)
 103             return i;
 104     return -1;
 105 }
 106
 107 static void
 108 scan (FILE *f, char *filename)
 109 {
 110     char            buf[MAX_NAMELEN];
 111     char            name[MAX_NAMELEN];
 112     unsigned long   ucs;
 113     FcGlyphName     *gn;
 114     int             lineno = 0;
 115     int             len;
 116
 117     while (fgets (buf, sizeof (buf), f))
 118     {
 119         lineno++;
 120         if (sscanf (buf, "%[^;];%lx\n", name, &ucs) != 2)
 121             continue;
 122         gn = FcAllocGlyphName ((FcChar32) ucs, (FcChar8 *) name);
 123         if (!gn)
 124             fatal (filename, lineno, "out of memory");
 125         len = strlen (name);
 126         if (len > max_name_len)
 127             max_name_len = len;
 128         raw[nraw++] = gn;
 129     }
 130 }
 131
 132 static int compare_string (const void *a, const void *b)
 133 {
 134     const char    *const *as = a, *const *bs = b;
 135     return strcmp (*as, *bs);
 136 }
 137
 138 static int compare_glyphname (const void *a, const void *b)
 139 {
 140     const FcGlyphName   *const *ag = a, *const *bg = b;
 141
 142     return strcmp ((char *) (*ag)->name, (char *) (*bg)->name);
 143 }
 144
 145 static int
 146 isqrt (int a)
 147 {
 148     int     l, h, m;
 149
 150     l = 2;
 151     h = a/2;
 152     while ((h-l) > 1)
 153     {
 154         m = (h+l) >> 1;
 155         if (m * m < a)
 156             l = m;
 157         else
 158             h = m;
 159     }
 160     return h;
 161 }
 162
 163 static int
 164 isprime (int i)
 165 {
 166     int l, t;
 167
 168     if (i < 2)
 169         return FcFalse;
 170     if ((i & 1) == 0)
 171     {
 172         if (i == 2)
 173             return FcTrue;
 174         return FcFalse;
 175     }
 176     l = isqrt (i) + 1;
 177     for (t = 3; t <= l; t += 2)
 178         if (i % t == 0)
 179             return 0;
 180     return 1;
 181 }
 182
 183 /*
 184  * Find a prime pair that leaves at least 25% of the hash table empty
 185  */
 186
 187 static void
 188 find_hash (void)
 189 {
 190     int h;
 191
 192     h = nraw + nraw / 4;
 193     if ((h & 1) == 0)
 194         h++;
 195     while (!isprime(h-2) || !isprime(h))
 196         h += 2;
 197     hash = h;
 198     rehash = h-2;
 199 }
 200
 201 static FcChar32
 202 FcHashGlyphName (const FcChar8 *name)
 203 {
 204     FcChar32    h = 0;
 205     FcChar8     c;
 206
 207     while ((c = *name++))
 208     {
 209         h = ((h << 1) | (h >> 31)) ^ c;
 210     }
 211     return h;
 212 }
 213
 214 static void
 215 insert (FcGlyphName *gn, FcGlyphName **table, FcChar32 h)
 216 {
 217     int         i, r = 0;
 218
 219     i = (int) (h % hash);
 220     while (table[i])
 221     {
 222         if (!r) r = (int) (h % rehash);
 223         i += r;
 224         if (i >= hash)
 225             i -= hash;
 226     }
 227     table[i] = gn;
 228 }
 229
 230 static void
 231 dump (FcGlyphName * const *table, const char *name)
 232 {
 233     int i;
 234
 235     printf ("static const FcGlyphName   *%s[%d] = {\n", name, hash);
 236
 237     for (i = 0; i < hash; i++)
 238         if (table[i])
 239             printf ("(FcGlyphName *) &glyph%d,\n", rawindex(table[i]));
 240         else
 241             printf ("0,\n");
 242
 243     printf ("};\n");
 244 }
 245
 246 int
 247 main (int argc, char **argv)
 248 {
 249     char        *files[MAX_GLYPHFILE];
 250     char        line[1024];
 251     FILE        *f;
 252     int         i;
 253
 254     i = 0;
 255     while (argv[i+1])
 256     {
 257         if (i == MAX_GLYPHFILE)
 258             fatal (*argv, 0, "Too many glyphname files");
 259         files[i] = argv[i+1];
 260         i++;
 261     }
 262     files[i] = 0;
 263     qsort (files, i, sizeof (char *), compare_string);
 264     for (i = 0; files[i]; i++)
 265     {
 266         f = fopen (files[i], "r");
 267         if (!f)
 268             fatal (files[i], 0, strerror (errno));
 269         scan (f, files[i]);
 270         fclose (f);
 271     }
 272     qsort (raw, nraw, sizeof (FcGlyphName *), compare_glyphname);
 273
 274     find_hash ();
 275
 276     for (i = 0; i < nraw; i++)
 277     {
 278         insert (raw[i], name_to_ucs, FcHashGlyphName (raw[i]->name));
 279         insert (raw[i], ucs_to_name, raw[i]->ucs);
 280     }
 281
 282     /*
 283      * Scan the input until the marker is found
 284      */
 285
 286     while (fgets (line, sizeof (line), stdin))
 287     {
 288         if (!strncmp (line, "@@@", 3))
 289             break;
 290         fputs (line, stdout);
 291     }
 292
 293     printf ("/* %d glyphnames in %d entries, %d%% occupancy */\n\n",
 294             nraw, hash, nraw * 100 / hash);
 295
 296     printf ("#define FC_GLYPHNAME_HASH %u\n", hash);
 297     printf ("#define FC_GLYPHNAME_REHASH %u\n", rehash);
 298     printf ("#define FC_GLYPHNAME_MAXLEN %d\n\n", max_name_len);
 299
 300     /*
 301      * Dump out entries
 302      */
 303
 304     for (i = 0; i < nraw; i++)
 305         printf ("static const struct { const FcChar32 ucs; const FcChar8 name[%d]; }"
 306                 " glyph%d = { 0x%lx, \"%s\" };\n",
 307                 (int) strlen ((char *) raw[i]->name) + 1,
 308                 i, (unsigned long) raw[i]->ucs, raw[i]->name);
 309
 310     /*
 311      * Dump out name_to_ucs table
 312      */
 313
 314     dump (name_to_ucs, "name_to_ucs");
 315
 316     /*
 317      * Dump out ucs_to_name table
 318      */
 319     dump (ucs_to_name, "ucs_to_name");
 320
 321     while (fgets (line, sizeof (line), stdin))
 322         fputs (line, stdout);
 323
 324     fflush (stdout);
 325     exit (ferror (stdout));
 326 }