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