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