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