/*
- * $XFree86: xc/lib/fontconfig/src/fccharset.c,v 1.2 2002/02/15 06:01:28 keithp Exp $
+ * $XFree86: xc/lib/fontconfig/src/fccharset.c,v 1.13 2002/06/26 22:56:51 keithp Exp $
*
* Copyright © 2001 Keith Packard, member of The XFree86 Project, Inc.
*
/* #define CHECK */
-static int
-FcCharSetLevels (FcChar32 ucs4)
-{
- if (ucs4 <= 0xff)
- return 1;
- if (ucs4 <= 0xffff)
- return 2;
- if (ucs4 <= 0xffffff)
- return 3;
- return 4;
-}
-
-static FcBool
-FcCharSetCheckLevel (FcCharSet *fcs, FcChar32 ucs4)
-{
- int level = FcCharSetLevels (ucs4);
-
- if (level <= fcs->levels)
- return FcTrue;
- while (fcs->levels < level)
- {
- if (fcs->levels == 0)
- {
- FcCharLeaf *leaf;
-
- leaf = (FcCharLeaf *) calloc (1, sizeof (FcCharLeaf));
- if (!leaf)
- return FcFalse;
- FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
- fcs->node.leaf = leaf;
- }
- else
- {
- FcCharBranch *branch;
-
- branch = (FcCharBranch *) calloc (1, sizeof (FcCharBranch));
- if (!branch)
- return FcFalse;
- FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharBranch));
- branch->nodes[0] = fcs->node;
- fcs->node.branch = branch;
- }
- ++fcs->levels;
- }
- return FcTrue;
-}
+/* #define CHATTY */
FcCharSet *
FcCharSetCreate (void)
return 0;
FcMemAlloc (FC_MEM_CHARSET, sizeof (FcCharSet));
fcs->ref = 1;
- fcs->levels = 0;
- fcs->node.leaf = 0;
+ fcs->num = 0;
+ fcs->leaves = 0;
+ fcs->numbers = 0;
fcs->constant = FcFalse;
return fcs;
}
return FcCharSetCreate ();
}
-static void
-FcCharNodeDestroy (FcCharNode node, int level)
-{
- int i;
-
- switch (level) {
- case 0:
- break;
- case 1:
- FcMemFree (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
- free (node.leaf);
- break;
- default:
- for (i = 0; i < 256; i++)
- if (node.branch->nodes[i].branch)
- FcCharNodeDestroy (node.branch->nodes[i], level - 1);
- FcMemFree (FC_MEM_CHARNODE, sizeof (FcCharBranch));
- free (node.branch);
- }
-}
void
FcCharSetDestroy (FcCharSet *fcs)
{
- if (fcs->constant)
- return;
- if (--fcs->ref <= 0)
+ if (!fcs->constant && --fcs->ref <= 0)
{
- FcCharNodeDestroy (fcs->node, fcs->levels);
+ int i;
+
+ for (i = 0; i < fcs->num; i++)
+ {
+ FcMemFree (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
+ free (fcs->leaves[i]);
+ }
+ if (fcs->leaves)
+ {
+ FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcCharLeaf *));
+ free (fcs->leaves);
+ }
+ if (fcs->numbers)
+ {
+ FcMemFree (FC_MEM_CHARSET, fcs->num * sizeof (FcChar16));
+ free (fcs->numbers);
+ }
FcMemFree (FC_MEM_CHARSET, sizeof (FcCharSet));
free (fcs);
}
}
/*
- * Locate the leaf containing the specified char, returning
- * null if it doesn't exist
+ * Locate the leaf containing the specified char, return
+ * its index if it exists, otherwise return negative of
+ * the (position + 1) where it should be inserted
*/
-static FcCharLeaf *
-FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
+static int
+FcCharSetFindLeafPos (const FcCharSet *fcs, FcChar32 ucs4)
{
- int l;
- const FcCharNode *prev;
- FcCharNode node;
- FcChar32 i;
-
- prev = &fcs->node;
- l = fcs->levels;
- while (--l > 0)
+ FcChar16 *numbers = fcs->numbers;
+ FcChar16 page;
+ int low = 0;
+ int high = fcs->num - 1;
+
+ if (!numbers)
+ return -1;
+ ucs4 >>= 8;
+ while (low <= high)
{
- node = *prev;
- if (!node.branch)
- return 0;
- i = (ucs4 >> (l << 3)) & 0xff;
- prev = &node.branch->nodes[i];
+ int mid = (low + high) >> 1;
+ page = numbers[mid];
+ if (page == ucs4)
+ return mid;
+ if (page < ucs4)
+ low = mid + 1;
+ else
+ high = mid - 1;
}
- return prev->leaf;
+ if (numbers[high] < ucs4)
+ high++;
+ return -(high + 1);
+}
+
+static FcCharLeaf *
+FcCharSetFindLeaf (const FcCharSet *fcs, FcChar32 ucs4)
+{
+ int pos = FcCharSetFindLeafPos (fcs, ucs4);
+ if (pos >= 0)
+ return fcs->leaves[pos];
+ return 0;
+}
+
+static FcBool
+FcCharSetPutLeaf (FcCharSet *fcs,
+ FcChar32 ucs4,
+ FcCharLeaf *leaf,
+ int pos)
+{
+ FcCharLeaf **leaves;
+ FcChar16 *numbers;
+
+ ucs4 >>= 8;
+ if (ucs4 >= 0x10000)
+ return FcFalse;
+ if (!fcs->leaves)
+ leaves = malloc (sizeof (FcCharLeaf *));
+ else
+ leaves = realloc (fcs->leaves, (fcs->num + 1) * sizeof (FcCharLeaf *));
+ if (!leaves)
+ return FcFalse;
+ fcs->leaves = leaves;
+ if (!fcs->numbers)
+ numbers = malloc (sizeof (FcChar16));
+ else
+ numbers = realloc (fcs->numbers, (fcs->num + 1) * sizeof (FcChar16));
+ if (!numbers)
+ return FcFalse;
+ fcs->numbers = numbers;
+
+ memmove (fcs->leaves + pos + 1, fcs->leaves + pos,
+ (fcs->num - pos) * sizeof (FcCharLeaf *));
+ memmove (fcs->numbers + pos + 1, fcs->numbers + pos,
+ (fcs->num - pos) * sizeof (FcChar16));
+ fcs->numbers[pos] = (FcChar16) ucs4;
+ fcs->leaves[pos] = leaf;
+ fcs->num++;
+ return FcTrue;
}
/*
static FcCharLeaf *
FcCharSetFindLeafCreate (FcCharSet *fcs, FcChar32 ucs4)
{
- int l;
- FcCharNode *prev, node;
- FcChar32 i;
+ int pos;
+ FcCharLeaf *leaf;
- if (!FcCharSetCheckLevel (fcs, ucs4))
- return FcFalse;
- prev = &fcs->node;
- l = fcs->levels;
- while (--l > 0)
+ pos = FcCharSetFindLeafPos (fcs, ucs4);
+ if (pos >= 0)
+ return fcs->leaves[pos];
+
+ leaf = calloc (1, sizeof (FcCharLeaf));
+ if (!leaf)
+ return 0;
+
+ pos = -pos - 1;
+ if (!FcCharSetPutLeaf (fcs, ucs4, leaf, pos))
{
- node = *prev;
- if (!node.branch)
- {
- node.branch = calloc (1, sizeof (FcCharBranch));
- if (!node.branch)
- return 0;
- FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharBranch));
- *prev = node;
- }
- i = (ucs4 >> (l << 3)) & 0xff;
- prev = &node.branch->nodes[i];
+ free (leaf);
+ return 0;
}
- node = *prev;
- if (!node.leaf)
+ return leaf;
+}
+
+static FcBool
+FcCharSetInsertLeaf (FcCharSet *fcs, FcChar32 ucs4, FcCharLeaf *leaf)
+{
+ int pos;
+
+ pos = FcCharSetFindLeafPos (fcs, ucs4);
+ if (pos >= 0)
{
- node.leaf = calloc (1, sizeof (FcCharLeaf));
- if (!node.leaf)
- return 0;
FcMemAlloc (FC_MEM_CHARNODE, sizeof (FcCharLeaf));
- *prev = node;
+ free (fcs->leaves[pos]);
+ fcs->leaves[pos] = leaf;
+ return FcTrue;
}
- return node.leaf;
+ pos = -pos - 1;
+ return FcCharSetPutLeaf (fcs, ucs4, leaf, pos);
}
FcBool
typedef struct _fcCharSetIter {
FcCharLeaf *leaf;
FcChar32 ucs4;
+ int pos;
} FcCharSetIter;
/*
- * Find the nearest leaf at or beyond *ucs4, return 0 if no leaf
- * exists
+ * Set iter->leaf to the leaf containing iter->ucs4 or higher
*/
-static FcCharLeaf *
-FcCharSetIterLeaf (FcCharNode node, int level, FcChar32 *ucs4)
+
+static void
+FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
{
- if (level <= 1)
- return node.leaf;
- else if (!node.branch)
- return 0;
- else
- {
- int shift = ((level - 1) << 3);
- FcChar32 inc = 1 << shift;
- FcChar32 mask = ~(inc - 1);
- FcChar32 byte = (*ucs4 >> shift) & 0xff;
- FcCharLeaf *leaf;
+ int pos = FcCharSetFindLeafPos (fcs, iter->ucs4);
- for (;;)
+ if (pos < 0)
+ {
+ pos = -pos - 1;
+ if (pos == fcs->num)
{
- leaf = FcCharSetIterLeaf (node.branch->nodes[byte],
- level - 1,
- ucs4);
- if (leaf)
- break;
- /* step to next branch, resetting lower indices */
- *ucs4 = (*ucs4 & mask) + inc;
- byte = (byte + 1) & 0xff;
- if (byte == 0)
- break;
+ iter->ucs4 = ~0;
+ iter->leaf = 0;
+ return;
}
- return leaf;
+ iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
}
+ iter->leaf = fcs->leaves[pos];
+ iter->pos = pos;
+#ifdef CHATTY
+ printf ("set %08x: %08x\n", iter->ucs4, (FcChar32) iter->leaf);
+#endif
}
static void
-FcCharSetIterSet (const FcCharSet *fcs, FcCharSetIter *iter)
+FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
{
- if (FcCharSetLevels (iter->ucs4) > fcs->levels)
+ int pos = iter->pos + 1;
+ if (pos >= fcs->num)
+ {
+ iter->ucs4 = ~0;
iter->leaf = 0;
+ }
else
- iter->leaf = FcCharSetIterLeaf (fcs->node, fcs->levels,
- &iter->ucs4);
- if (!iter->leaf)
- iter->ucs4 = ~0;
+ {
+ iter->ucs4 = (FcChar32) fcs->numbers[pos] << 8;
+ iter->leaf = fcs->leaves[pos];
+ iter->pos = pos;
+ }
}
+#ifdef CHATTY
static void
-FcCharSetIterNext (const FcCharSet *fcs, FcCharSetIter *iter)
+FcCharSetDump (const FcCharSet *fcs)
{
- iter->ucs4 += 0x100;
- FcCharSetIterSet (fcs, iter);
+ int pos;
+
+ printf ("fcs %08x:\n", (FcChar32) fcs);
+ for (pos = 0; pos < fcs->num; pos++)
+ {
+ FcCharLeaf *leaf = fcs->leaves[pos];
+ FcChar32 ucs4 = (FcChar32) fcs->numbers[pos] << 8;
+
+ printf (" %08x: %08x\n", ucs4, (FcChar32) leaf);
+ }
}
+#endif
static void
FcCharSetIterStart (const FcCharSet *fcs, FcCharSetIter *iter)
{
+#ifdef CHATTY
+ FcCharSetDump (fcs);
+#endif
iter->ucs4 = 0;
FcCharSetIterSet (fcs, iter);
}
goto bail0;
FcCharSetIterStart (a, &ai);
FcCharSetIterStart (b, &bi);
- while ((ai.leaf || bonly) && (bi.leaf || aonly))
+ while ((ai.leaf || (bonly && bi.leaf)) && (bi.leaf || (aonly && ai.leaf)))
{
if (ai.ucs4 < bi.ucs4)
{
return count;
}
+/*
+ * return FcTrue iff a is a subset of b
+ */
+FcBool
+FcCharSetIsSubset (const FcCharSet *a, const FcCharSet *b)
+{
+ int ai, bi;
+ FcChar16 an, bn;
+
+ if (a == b) return FcTrue;
+ bi = 0;
+ ai = 0;
+ while (ai < a->num && bi < b->num)
+ {
+ an = a->numbers[ai];
+ bn = b->numbers[bi];
+ if (an == bn)
+ {
+ FcChar32 *am = a->leaves[ai]->map;
+ FcChar32 *bm = b->leaves[bi]->map;
+
+ if (am != bm)
+ {
+ int i = 256/32;
+ while (i--)
+ if (*am++ & ~*bm++)
+ return FcFalse;
+ }
+ ai++;
+ bi++;
+ }
+ else if (an < bn)
+ return FcFalse;
+ else
+ {
+ int low = bi + 1;
+ int high = b->num - 1;
+
+ while (low <= high)
+ {
+ int mid = (low + high) >> 1;
+ bn = b->numbers[mid];
+ if (bn == an)
+ {
+ high = mid;
+ break;
+ }
+ if (bn < an)
+ low = mid + 1;
+ else
+ high = mid - 1;
+ }
+ bi = high;
+ while (bi < b->num && b->numbers[bi] < an)
+ bi++;
+ }
+ }
+ return FcTrue;
+}
+
+/*
+ * These two functions efficiently walk the entire charmap for
+ * other software (like pango) that want their own copy
+ */
+
+FcChar32
+FcCharSetNextPage (const FcCharSet *a,
+ FcChar32 map[FC_CHARSET_MAP_SIZE],
+ FcChar32 *next)
+{
+ FcCharSetIter ai;
+ FcChar32 page;
+
+ ai.ucs4 = *next;
+ FcCharSetIterSet (a, &ai);
+ if (!ai.leaf)
+ return FC_CHARSET_DONE;
+
+ /*
+ * Save current information
+ */
+ page = ai.ucs4;
+ memcpy (map, ai.leaf->map, sizeof (ai.leaf->map));
+ /*
+ * Step to next page
+ */
+ FcCharSetIterNext (a, &ai);
+ *next = ai.ucs4;
+
+ return page;
+}
+
+FcChar32
+FcCharSetFirstPage (const FcCharSet *a,
+ FcChar32 map[FC_CHARSET_MAP_SIZE],
+ FcChar32 *next)
+{
+ *next = 0;
+ return FcCharSetNextPage (a, map, next);
+}
+
+/*
+ * old coverage API, rather hard to use correctly
+ */
+FcChar32
+FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result);
+
+FcChar32
+FcCharSetCoverage (const FcCharSet *a, FcChar32 page, FcChar32 *result)
+{
+ FcCharSetIter ai;
+
+ ai.ucs4 = page;
+ FcCharSetIterSet (a, &ai);
+ if (!ai.leaf)
+ {
+ memset (result, '\0', 256 / 8);
+ page = 0;
+ }
+ else
+ {
+ memcpy (result, ai.leaf->map, sizeof (ai.leaf->map));
+ FcCharSetIterNext (a, &ai);
+ page = ai.ucs4;
+ }
+ return page;
+}
+
/*
* ASCII representation of charsets.
*
return FcTrue;
}
+typedef struct _FcCharLeafEnt FcCharLeafEnt;
+
+struct _FcCharLeafEnt {
+ FcCharLeafEnt *next;
+ FcChar32 hash;
+ FcCharLeaf leaf;
+};
+
+#define FC_CHAR_LEAF_BLOCK (4096 / sizeof (FcCharLeafEnt))
+
+static FcCharLeafEnt *
+FcCharLeafEntCreate (void)
+{
+ static FcCharLeafEnt *block;
+ static int remain;
+
+ if (!remain)
+ {
+ block = malloc (FC_CHAR_LEAF_BLOCK * sizeof (FcCharLeafEnt));
+ if (!block)
+ return 0;
+ remain = FC_CHAR_LEAF_BLOCK;
+ }
+ remain--;
+ return block++;
+}
+
+#define FC_CHAR_LEAF_HASH_SIZE 257
+
+static FcChar32
+FcCharLeafHash (FcCharLeaf *leaf)
+{
+ FcChar32 hash = 0;
+ int i;
+
+ for (i = 0; i < 256/32; i++)
+ hash = ((hash << 1) | (hash >> 31)) ^ leaf->map[i];
+ return hash;
+}
+
+static int FcCharLeafTotal;
+static int FcCharLeafUsed;
+
+static FcCharLeaf *
+FcCharSetFreezeLeaf (FcCharLeaf *leaf)
+{
+ static FcCharLeafEnt *hashTable[FC_CHAR_LEAF_HASH_SIZE];
+ FcChar32 hash = FcCharLeafHash (leaf);
+ FcCharLeafEnt **bucket = &hashTable[hash % FC_CHAR_LEAF_HASH_SIZE];
+ FcCharLeafEnt *ent;
+
+ FcCharLeafTotal++;
+ for (ent = *bucket; ent; ent = ent->next)
+ {
+ if (ent->hash == hash && !memcmp (&ent->leaf, leaf, sizeof (FcCharLeaf)))
+ return &ent->leaf;
+ }
+
+ ent = FcCharLeafEntCreate();
+ if (!ent)
+ return 0;
+ FcCharLeafUsed++;
+ ent->leaf = *leaf;
+ ent->hash = hash;
+ ent->next = *bucket;
+ *bucket = ent;
+ return &ent->leaf;
+}
+
+typedef struct _FcCharSetEnt FcCharSetEnt;
+
+struct _FcCharSetEnt {
+ FcCharSetEnt *next;
+ FcChar32 hash;
+ FcCharSet set;
+};
+
+#define FC_CHAR_SET_HASH_SIZE 67
+
+static FcChar32
+FcCharSetHash (FcCharSet *fcs)
+{
+ FcChar32 hash = 0;
+ FcChar32 *p;
+ int i;
+
+ /* hash in leaves */
+ p = (FcChar32 *) fcs->leaves;
+ for (i = 0; i < fcs->num * sizeof (FcCharLeaf *) / sizeof (FcChar32); i++)
+ hash = ((hash << 1) | (hash >> 31)) ^ *p++;
+ /* hash in numbers */
+ for (i = 0; i < fcs->num; i++)
+ hash = ((hash << 1) | (hash >> 31)) ^ fcs->numbers[i];
+ return hash;
+}
+
+static int FcCharSetTotal;
+static int FcCharSetUsed;
+static int FcCharSetTotalEnts, FcCharSetUsedEnts;
+
+static FcCharSet *
+FcCharSetFreezeBase (FcCharSet *fcs)
+{
+ static FcCharSetEnt *hashTable[FC_CHAR_SET_HASH_SIZE];
+ FcChar32 hash = FcCharSetHash (fcs);
+ FcCharSetEnt **bucket = &hashTable[hash % FC_CHAR_SET_HASH_SIZE];
+ FcCharSetEnt *ent;
+
+ FcCharSetTotal++;
+ FcCharSetTotalEnts += fcs->num;
+ for (ent = *bucket; ent; ent = ent->next)
+ {
+ if (ent->hash == hash &&
+ ent->set.num == fcs->num &&
+ !memcmp (ent->set.leaves, fcs->leaves,
+ fcs->num * sizeof (FcCharLeaf *)) &&
+ !memcmp (ent->set.numbers, fcs->numbers,
+ fcs->num * sizeof (FcChar16)))
+ {
+ return &ent->set;
+ }
+ }
+
+ ent = malloc (sizeof (FcCharSetEnt) +
+ fcs->num * sizeof (FcCharLeaf *) +
+ fcs->num * sizeof (FcChar16));
+ if (!ent)
+ return 0;
+ FcCharSetUsed++;
+ FcCharSetUsedEnts += fcs->num;
+
+ ent->set.ref = 0;
+ ent->set.constant = FcTrue;
+ ent->set.num = fcs->num;
+ if (fcs->num)
+ {
+ ent->set.leaves = (FcCharLeaf **) (ent + 1);
+ ent->set.numbers = (FcChar16 *) (ent->set.leaves + fcs->num);
+ memcpy (ent->set.leaves, fcs->leaves, fcs->num * sizeof (FcCharLeaf *));
+ memcpy (ent->set.numbers, fcs->numbers, fcs->num * sizeof (FcChar16));
+ }
+ else
+ {
+ ent->set.leaves = 0;
+ ent->set.numbers = 0;
+ }
+
+ ent->hash = hash;
+ ent->next = *bucket;
+ *bucket = ent;
+ return &ent->set;
+}
+
+FcCharSet *
+FcCharSetFreeze (FcCharSet *fcs)
+{
+ FcCharSet *b;
+ FcCharSet *n = 0;
+ FcCharLeaf *l;
+ int i;
+
+ b = FcCharSetCreate ();
+ if (!b)
+ goto bail0;
+ for (i = 0; i < fcs->num; i++)
+ {
+ l = FcCharSetFreezeLeaf (fcs->leaves[i]);
+ if (!l)
+ goto bail1;
+ if (!FcCharSetInsertLeaf (b, fcs->numbers[i] << 8, l))
+ goto bail1;
+ }
+ n = FcCharSetFreezeBase (b);
+bail1:
+ if (b->leaves)
+ free (b->leaves);
+ if (b->numbers)
+ free (b->numbers);
+ free (b);
+bail0:
+ return n;
+}
+
FcCharSet *
FcNameParseCharSet (FcChar8 *string)
{
- FcCharSet *c;
+ FcCharSet *c, *n = 0;
FcChar32 ucs4;
FcCharLeaf *leaf;
+ FcCharLeaf temp;
+ FcChar32 bits;
int i;
c = FcCharSetCreate ();
string = FcCharSetParseValue (string, &ucs4);
if (!string)
goto bail1;
- leaf = FcCharSetFindLeafCreate (c, ucs4);
- if (!leaf)
- goto bail1;
+ bits = 0;
for (i = 0; i < 256/32; i++)
{
- string = FcCharSetParseValue (string, &leaf->map[i]);
+ string = FcCharSetParseValue (string, &temp.map[i]);
if (!string)
goto bail1;
+ bits |= temp.map[i];
+ }
+ if (bits)
+ {
+ leaf = FcCharSetFreezeLeaf (&temp);
+ if (!leaf)
+ goto bail1;
+ if (!FcCharSetInsertLeaf (c, ucs4, leaf))
+ goto bail1;
}
}
- return c;
+#ifdef CHATTY
+ printf (" %8s %8s %8s %8s\n", "total", "totalmem", "new", "newmem");
+ printf ("Leaves: %8d %8d %8d %8d\n",
+ FcCharLeafTotal, sizeof (FcCharLeaf) * FcCharLeafTotal,
+ FcCharLeafUsed, sizeof (FcCharLeaf) * FcCharLeafUsed);
+ printf ("Charsets: %8d %8d %8d %8d\n",
+ FcCharSetTotal, sizeof (FcCharSet) * FcCharSetTotal,
+ FcCharSetUsed, sizeof (FcCharSet) * FcCharSetUsed);
+ printf ("Tables: %8d %8d %8d %8d\n",
+ FcCharSetTotalEnts, FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
+ FcCharSetUsedEnts, FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
+ printf ("Total: %8s %8d %8s %8d\n",
+ "",
+ sizeof (FcCharLeaf) * FcCharLeafTotal +
+ sizeof (FcCharSet) * FcCharSetTotal +
+ FcCharSetTotalEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)),
+ "",
+ sizeof (FcCharLeaf) * FcCharLeafUsed +
+ sizeof (FcCharSet) * FcCharSetUsed +
+ FcCharSetUsedEnts * (sizeof (FcCharLeaf *) + sizeof (FcChar16)));
+#endif
+ n = FcCharSetFreezeBase (c);
bail1:
- FcCharSetDestroy (c);
+ if (c->leaves)
+ free (c->leaves);
+ if (c->numbers)
+ free (c->numbers);
+ free (c);
bail0:
- return 0;
+ return n;
}
FcBool
return FcTrue;
}
-#include <freetype/freetype.h>
-#include <fontconfig/fcfreetype.h>
-
/*
* Figure out whether the available freetype has FT_Get_Next_Char
*/
# define HAS_NEXT_CHAR
# else
# if FREETYPE_MINOR == 0
-# if FREETYPE_PATCH >= 8
+# if FREETYPE_PATCH >= 9
# define HAS_NEXT_CHAR
# endif
# endif
* For our purposes, this approximation is sufficient
*/
#ifndef HAS_NEXT_CHAR
-#define FT_Get_Next_Char(face, ucs4) ((ucs4) >= 0xffffff ? 0 : (ucs4) + 1)
+#define FT_Get_First_Char(face, gi) ((*(gi) = 1), 1)
+#define FT_Get_Next_Char(face, ucs4, gi) ((ucs4) >= 0xffffff ? \
+ (*(gi) = 0), 0 : \
+ (*(gi) = 1), (ucs4) + 1)
#warning "No FT_Get_Next_Char"
#endif
FcChar32 max;
} FcFontDecode;
-static const FcCharMap AppleRoman;
-static const FcCharMap AdobeSymbol;
-
-static const FcFontDecode fcFontDecoders[] = {
- { ft_encoding_unicode, 0, (1 << 21) - 1 },
- { ft_encoding_symbol, &AdobeSymbol, (1 << 16) - 1 },
- { ft_encoding_apple_roman, &AppleRoman, (1 << 16) - 1 },
-};
-
-#define NUM_DECODE (sizeof (fcFontDecoders) / sizeof (fcFontDecoders[0]))
-
-static FT_ULong
-FcFreeTypeMapChar (FcChar32 ucs4, const FcCharMap *map)
-{
- int low, high, mid;
- FcChar16 bmp;
-
- low = 0;
- high = map->nent - 1;
- if (ucs4 < map->ent[low].bmp || map->ent[high].bmp < ucs4)
- return ~0;
- while (high - low > 1)
- {
- mid = (high + low) >> 1;
- bmp = map->ent[mid].bmp;
- if (ucs4 == bmp)
- return (FT_ULong) map->ent[mid].encode;
- if (ucs4 < bmp)
- high = mid;
- else
- low = mid;
- }
- for (mid = low; mid <= high; mid++)
- {
- if (ucs4 == map->ent[mid].bmp)
- return (FT_ULong) map->ent[mid].encode;
- }
- return ~0;
-}
-
-/*
- * Map a UCS4 glyph to a glyph index. Use all available encoding
- * tables to try and find one that works. This information is expected
- * to be cached by higher levels, so performance isn't critical
- */
-
-FT_UInt
-FcFreeTypeCharIndex (FT_Face face, FcChar32 ucs4)
-{
- int initial, offset, decode;
- FT_UInt glyphindex;
- FT_ULong charcode;
-
- initial = 0;
- /*
- * Find the current encoding
- */
- if (face->charmap)
- {
- for (; initial < NUM_DECODE; initial++)
- if (fcFontDecoders[initial].encoding == face->charmap->encoding)
- break;
- if (initial == NUM_DECODE)
- initial = 0;
- }
- /*
- * Check each encoding for the glyph, starting with the current one
- */
- for (offset = 0; offset < NUM_DECODE; offset++)
- {
- decode = (initial + offset) % NUM_DECODE;
- if (!face->charmap || face->charmap->encoding != fcFontDecoders[decode].encoding)
- if (FT_Select_Charmap (face, fcFontDecoders[decode].encoding) != 0)
- continue;
- if (fcFontDecoders[decode].map)
- {
- charcode = FcFreeTypeMapChar (ucs4, fcFontDecoders[decode].map);
- if (charcode == ~0)
- continue;
- }
- else
- charcode = (FT_ULong) ucs4;
- glyphindex = FT_Get_Char_Index (face, charcode);
- if (glyphindex)
- return glyphindex;
- }
- return 0;
-}
-
-static FcBool
-FcFreeTypeCheckGlyph (FT_Face face, FcChar32 ucs4,
- FT_UInt glyph, FcBlanks *blanks)
-{
- FT_Int load_flags = FT_LOAD_NO_SCALE | FT_LOAD_NO_HINTING;
- FT_GlyphSlot slot;
-
- /*
- * When using scalable fonts, only report those glyphs
- * which can be scaled; otherwise those fonts will
- * only be available at some sizes, and never when
- * transformed. Avoid this by simply reporting bitmap-only
- * glyphs as missing
- */
- if (face->face_flags & FT_FACE_FLAG_SCALABLE)
- load_flags |= FT_LOAD_NO_BITMAP;
-
- if (FT_Load_Glyph (face, glyph, load_flags))
- return FcFalse;
-
- slot = face->glyph;
- if (!glyph)
- return FcFalse;
-
- switch (slot->format) {
- case ft_glyph_format_bitmap:
- /*
- * Bitmaps are assumed to be reasonable; if
- * this proves to be a rash assumption, this
- * code can be easily modified
- */
- return FcTrue;
- case ft_glyph_format_outline:
- /*
- * Glyphs with contours are always OK
- */
- if (slot->outline.n_contours != 0)
- return FcTrue;
- /*
- * Glyphs with no contours are only OK if
- * they're members of the Blanks set specified
- * in the configuration. If blanks isn't set,
- * then allow any glyph to be blank
- */
- if (!blanks || FcBlanksIsMember (blanks, ucs4))
- return FcTrue;
- /* fall through ... */
- default:
- break;
- }
- return FcFalse;
-}
-
-FcCharSet *
-FcFreeTypeCharSet (FT_Face face, FcBlanks *blanks)
-{
- FcChar32 page, off, max, ucs4;
-#ifdef CHECK
- FcChar32 font_max = 0;
-#endif
- FcCharSet *fcs;
- FcCharLeaf *leaf;
- const FcCharMap *map;
- int o;
- int i;
- FT_UInt glyph;
-
- fcs = FcCharSetCreate ();
- if (!fcs)
- goto bail0;
-
- for (o = 0; o < NUM_DECODE; o++)
- {
- if (FT_Select_Charmap (face, fcFontDecoders[o].encoding) != 0)
- continue;
- map = fcFontDecoders[o].map;
- if (map)
- {
- /*
- * Non-Unicode tables are easy; there's a list of all possible
- * characters
- */
- for (i = 0; i < map->nent; i++)
- {
- ucs4 = map->ent[i].bmp;
- glyph = FT_Get_Char_Index (face, map->ent[i].encode);
- if (glyph && FcFreeTypeCheckGlyph (face, ucs4, glyph, blanks))
- {
- leaf = FcCharSetFindLeafCreate (fcs, ucs4);
- if (!leaf)
- goto bail1;
- leaf->map[(ucs4 & 0xff) >> 5] |= (1 << (ucs4 & 0x1f));
-#ifdef CHECK
- if (ucs4 > font_max)
- font_max = ucs4;
-#endif
- }
- }
- }
- else
- {
- max = fcFontDecoders[o].max;
-
- /*
- * Find the first encoded character in the font
- */
- ucs4 = 0;
- if (FT_Get_Char_Index (face, 0))
- ucs4 = 0;
- else
- ucs4 = FT_Get_Next_Char (face, 0);
-
- for (;;)
- {
- page = ucs4 >> 8;
- leaf = 0;
- while ((ucs4 >> 8) == page)
- {
- glyph = FT_Get_Char_Index (face, ucs4);
- if (glyph && FcFreeTypeCheckGlyph (face, ucs4,
- glyph, blanks))
- {
- if (!leaf)
- {
- leaf = FcCharSetFindLeafCreate (fcs, ucs4);
- if (!leaf)
- goto bail1;
- }
- off = ucs4 & 0xff;
- leaf->map[off >> 5] |= (1 << (off & 0x1f));
-#ifdef CHECK
- if (ucs4 > font_max)
- font_max = ucs4;
-#endif
- }
- ucs4++;
- }
- ucs4 = FT_Get_Next_Char (face, ucs4 - 1);
- if (!ucs4)
- break;
- }
-#ifdef CHECK
- for (ucs4 = 0; ucs4 < 0x10000; ucs4++)
- {
- FcBool FT_Has, FC_Has;
-
- FT_Has = FT_Get_Char_Index (face, ucs4) != 0;
- FC_Has = FcCharSetHasChar (fcs, ucs4);
- if (FT_Has != FC_Has)
- {
- printf ("0x%08x FT says %d FC says %d\n", ucs4, FT_Has, FC_Has);
- }
- }
-#endif
- }
- }
-#ifdef CHECK
- printf ("%d glyphs %d encoded\n", (int) face->num_glyphs, FcCharSetCount (fcs));
- for (ucs4 = 0; ucs4 <= font_max; ucs4++)
- {
- FcBool has_char = FcFreeTypeCharIndex (face, ucs4) != 0;
- FcBool has_bit = FcCharSetHasChar (fcs, ucs4);
-
- if (has_char && !has_bit)
- printf ("Bitmap missing char 0x%x\n", ucs4);
- else if (!has_char && has_bit)
- printf ("Bitmap extra char 0x%x\n", ucs4);
- }
-#endif
- return fcs;
-bail1:
- FcCharSetDestroy (fcs);
-bail0:
- return 0;
-}
-
static const FcCharEnt AppleRomanEnt[] = {
{ 0x0020, 0x20 }, /* SPACE */
{ 0x0021, 0x21 }, /* EXCLAMATION MARK */
AdobeSymbolEnt,
sizeof (AdobeSymbolEnt) / sizeof (AdobeSymbolEnt[0]),
};
+
+static const FcFontDecode fcFontDecoders[] = {
+ { ft_encoding_unicode, 0, (1 << 21) - 1 },
+ { ft_encoding_symbol, &AdobeSymbol, (1 << 16) - 1 },
+ { ft_encoding_apple_roman, &AppleRoman, (1 << 16) - 1 },
+};
+
+#define NUM_DECODE (sizeof (fcFontDecoders) / sizeof (fcFontDecoders[0]))
+
+static FT_ULong
+FcFreeTypeMapChar (FcChar32 ucs4, const FcCharMap *map)
+{
+ int low, high, mid;
+ FcChar16 bmp;
+
+ low = 0;
+ high = map->nent - 1;
+ if (ucs4 < map->ent[low].bmp || map->ent[high].bmp < ucs4)
+ return ~0;
+ while (low <= high)
+ {
+ mid = (high + low) >> 1;
+ bmp = map->ent[mid].bmp;
+ if (ucs4 == bmp)
+ return (FT_ULong) map->ent[mid].encode;
+ if (ucs4 < bmp)
+ high = mid - 1;
+ else
+ low = mid + 1;
+ }
+ return ~0;
+}
+
+/*
+ * Map a UCS4 glyph to a glyph index. Use all available encoding
+ * tables to try and find one that works. This information is expected
+ * to be cached by higher levels, so performance isn't critical
+ */
+
+FT_UInt
+FcFreeTypeCharIndex (FT_Face face, FcChar32 ucs4)
+{
+ int initial, offset, decode;
+ FT_UInt glyphindex;
+ FT_ULong charcode;
+
+ initial = 0;
+ /*
+ * Find the current encoding
+ */
+ if (face->charmap)
+ {
+ for (; initial < NUM_DECODE; initial++)
+ if (fcFontDecoders[initial].encoding == face->charmap->encoding)
+ break;
+ if (initial == NUM_DECODE)
+ initial = 0;
+ }
+ /*
+ * Check each encoding for the glyph, starting with the current one
+ */
+ for (offset = 0; offset < NUM_DECODE; offset++)
+ {
+ decode = (initial + offset) % NUM_DECODE;
+ if (!face->charmap || face->charmap->encoding != fcFontDecoders[decode].encoding)
+ if (FT_Select_Charmap (face, fcFontDecoders[decode].encoding) != 0)
+ continue;
+ if (fcFontDecoders[decode].map)
+ {
+ charcode = FcFreeTypeMapChar (ucs4, fcFontDecoders[decode].map);
+ if (charcode == ~0)
+ continue;
+ }
+ else
+ charcode = (FT_ULong) ucs4;
+ glyphindex = FT_Get_Char_Index (face, charcode);
+ if (glyphindex)
+ return glyphindex;
+ }
+ return 0;
+}
+
+static FcBool
+FcFreeTypeCheckGlyph (FT_Face face, FcChar32 ucs4,
+ FT_UInt glyph, FcBlanks *blanks)
+{
+ FT_Int load_flags = FT_LOAD_NO_SCALE | FT_LOAD_NO_HINTING;
+ FT_GlyphSlot slot;
+
+ /*
+ * When using scalable fonts, only report those glyphs
+ * which can be scaled; otherwise those fonts will
+ * only be available at some sizes, and never when
+ * transformed. Avoid this by simply reporting bitmap-only
+ * glyphs as missing
+ */
+ if (face->face_flags & FT_FACE_FLAG_SCALABLE)
+ load_flags |= FT_LOAD_NO_BITMAP;
+
+ if (FT_Load_Glyph (face, glyph, load_flags))
+ return FcFalse;
+
+ slot = face->glyph;
+ if (!glyph)
+ return FcFalse;
+
+ switch (slot->format) {
+ case ft_glyph_format_bitmap:
+ /*
+ * Bitmaps are assumed to be reasonable; if
+ * this proves to be a rash assumption, this
+ * code can be easily modified
+ */
+ return FcTrue;
+ case ft_glyph_format_outline:
+ /*
+ * Glyphs with contours are always OK
+ */
+ if (slot->outline.n_contours != 0)
+ return FcTrue;
+ /*
+ * Glyphs with no contours are only OK if
+ * they're members of the Blanks set specified
+ * in the configuration. If blanks isn't set,
+ * then allow any glyph to be blank
+ */
+ if (!blanks || FcBlanksIsMember (blanks, ucs4))
+ return FcTrue;
+ /* fall through ... */
+ default:
+ break;
+ }
+ return FcFalse;
+}
+
+FcCharSet *
+FcFreeTypeCharSet (FT_Face face, FcBlanks *blanks)
+{
+ FcChar32 page, off, max, ucs4;
+#ifdef CHECK
+ FcChar32 font_max = 0;
+#endif
+ FcCharSet *fcs;
+ FcCharLeaf *leaf;
+ const FcCharMap *map;
+ int o;
+ int i;
+ FT_UInt glyph;
+
+ fcs = FcCharSetCreate ();
+ if (!fcs)
+ goto bail0;
+
+ for (o = 0; o < NUM_DECODE; o++)
+ {
+ if (FT_Select_Charmap (face, fcFontDecoders[o].encoding) != 0)
+ continue;
+ map = fcFontDecoders[o].map;
+ if (map)
+ {
+ /*
+ * Non-Unicode tables are easy; there's a list of all possible
+ * characters
+ */
+ for (i = 0; i < map->nent; i++)
+ {
+ ucs4 = map->ent[i].bmp;
+ glyph = FT_Get_Char_Index (face, map->ent[i].encode);
+ if (glyph && FcFreeTypeCheckGlyph (face, ucs4, glyph, blanks))
+ {
+ leaf = FcCharSetFindLeafCreate (fcs, ucs4);
+ if (!leaf)
+ goto bail1;
+ leaf->map[(ucs4 & 0xff) >> 5] |= (1 << (ucs4 & 0x1f));
+#ifdef CHECK
+ if (ucs4 > font_max)
+ font_max = ucs4;
+#endif
+ }
+ }
+ }
+ else
+ {
+ FT_UInt gindex;
+
+ max = fcFontDecoders[o].max;
+ /*
+ * Find the first encoded character in the font
+ */
+ if (FT_Get_Char_Index (face, 0))
+ {
+ ucs4 = 0;
+ gindex = 1;
+ }
+ else
+ {
+ ucs4 = FT_Get_Next_Char (face, 0, &gindex);
+ if (!ucs4)
+ gindex = 0;
+ }
+
+ while (gindex)
+ {
+ page = ucs4 >> 8;
+ leaf = 0;
+ while ((ucs4 >> 8) == page)
+ {
+ glyph = FT_Get_Char_Index (face, ucs4);
+ if (glyph && FcFreeTypeCheckGlyph (face, ucs4,
+ glyph, blanks))
+ {
+ if (!leaf)
+ {
+ leaf = FcCharSetFindLeafCreate (fcs, ucs4);
+ if (!leaf)
+ goto bail1;
+ }
+ off = ucs4 & 0xff;
+ leaf->map[off >> 5] |= (1 << (off & 0x1f));
+#ifdef CHECK
+ if (ucs4 > font_max)
+ font_max = ucs4;
+#endif
+ }
+ ucs4++;
+ }
+ ucs4 = FT_Get_Next_Char (face, ucs4 - 1, &gindex);
+ if (!ucs4)
+ gindex = 0;
+ }
+#ifdef CHECK
+ for (ucs4 = 0; ucs4 < 0x10000; ucs4++)
+ {
+ FcBool FT_Has, FC_Has;
+
+ FT_Has = FT_Get_Char_Index (face, ucs4) != 0;
+ FC_Has = FcCharSetHasChar (fcs, ucs4);
+ if (FT_Has != FC_Has)
+ {
+ printf ("0x%08x FT says %d FC says %d\n", ucs4, FT_Has, FC_Has);
+ }
+ }
+#endif
+ }
+ }
+#ifdef CHECK
+ printf ("%d glyphs %d encoded\n", (int) face->num_glyphs, FcCharSetCount (fcs));
+ for (ucs4 = 0; ucs4 <= font_max; ucs4++)
+ {
+ FcBool has_char = FcFreeTypeCharIndex (face, ucs4) != 0;
+ FcBool has_bit = FcCharSetHasChar (fcs, ucs4);
+
+ if (has_char && !has_bit)
+ printf ("Bitmap missing char 0x%x\n", ucs4);
+ else if (!has_char && has_bit)
+ printf ("Bitmap extra char 0x%x\n", ucs4);
+ }
+#endif
+ return fcs;
+bail1:
+ FcCharSetDestroy (fcs);
+bail0:
+ return 0;
+}
+