[pango/wip-bitmatrix] Compute the coverage order ahead of time
- From: Matthias Clasen <matthiasc src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [pango/wip-bitmatrix] Compute the coverage order ahead of time
- Date: Sat, 22 Aug 2020 19:46:20 +0000 (UTC)
commit 99b0d9a635b630eefa694b8fb1d6996f29c482d0
Author: Matthias Clasen <mclasen redhat com>
Date: Sat Aug 22 13:50:55 2020 -0400
Compute the coverage order ahead of time
Store a full matrix for the partial order of
coverage subsets. To avoid this growing too large,
add an indirection for identical charsets.
On my system, with 4000 fonts, I see ~300 different
charsets, so this saves quite a bit. Computing the
full matrix takes too long - ~240ms. But we only have
to do this once, and we can possibly store it and
load it from disk.
pango/pangofc-fontmap.c | 223 +++++++++++++++++++++++++++++++++++++++++++++---
1 file changed, 211 insertions(+), 12 deletions(-)
---
diff --git a/pango/pangofc-fontmap.c b/pango/pangofc-fontmap.c
index 46d8f4c7..29cb748c 100644
--- a/pango/pangofc-fontmap.c
+++ b/pango/pangofc-fontmap.c
@@ -138,6 +138,14 @@ typedef struct _PangoFcFontset PangoFcFontset;
#define PANGO_FC_FONTSET(object) (G_TYPE_CHECK_INSTANCE_CAST ((object), PANGO_FC_TYPE_FONTSET,
PangoFcFontset))
#define PANGO_FC_IS_FONTSET(object) (G_TYPE_CHECK_INSTANCE_TYPE ((object), PANGO_FC_TYPE_FONTSET))
+typedef struct _CoverageOrder CoverageOrder;
+
+static CoverageOrder *coverage_order_new (FcFontSet *fonts);
+static void coverage_order_free (CoverageOrder *co);
+static gboolean coverage_order_is_subset (CoverageOrder *co,
+ FcPattern *p1,
+ FcPattern *p2);
+
struct _PangoFcFontMapPrivate
{
GHashTable *fontset_hash; /* Maps PangoFcFontsetKey -> PangoFcFontset */
@@ -167,6 +175,8 @@ struct _PangoFcFontMapPrivate
FcConfig *config;
FcFontSet *fonts;
+
+ CoverageOrder *coverage_order;
};
struct _PangoFcFontFaceData
@@ -1073,10 +1083,7 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
{
int f, k;
- /* Find the i'th fontset skipping the ones that are
- * not adding coverage.
- */
-
+ /* Find the i'th fontset while doing coverage trimming. */
if (!pats->skip)
{
pats->skip = g_new0 (int, fontset->nfont);
@@ -1087,14 +1094,30 @@ pango_fc_patterns_get_font_pattern (PangoFcPatterns *pats, int i, gboolean *prep
{
if (pats->skip[f] == 0) /* calculate whether to skip */
{
- FcCharSet *fcs;
- FcBool added = FcFalse;
-
- FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
-
- FcCharSetMerge (pats->cs, fcs, &added);
-
- pats->skip[f] = added ? 2 : 1;
+ int l;
+
+ for (l = 0; l < f; l++) /* see if a previous font covers it */
+ {
+ if (coverage_order_is_subset (pats->fontmap->priv->coverage_order,
+ fontset->fonts[f],
+ fontset->fonts[l]))
+ {
+ pats->skip[f] = 1;
+ break;
+ }
+ }
+
+ if (pats->skip[f] == 0) /* have to do it the hard way */
+ {
+ FcCharSet *fcs;
+ FcBool added = FcFalse;
+
+ FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs);
+
+ FcCharSetMerge (pats->cs, fcs, &added);
+
+ pats->skip[f] = added ? 2 : 1;
+ }
}
if (pats->skip[f] == 2) /* don't skip */
@@ -1465,6 +1488,7 @@ pango_fc_font_map_fini (PangoFcFontMap *fcfontmap)
PangoFcFontMapPrivate *priv = fcfontmap->priv;
int i;
+ g_clear_pointer (&priv->coverage_order, coverage_order_free);
g_clear_pointer (&priv->fonts, FcFontSetDestroy);
g_queue_free (priv->fontset_cache);
@@ -2319,6 +2343,7 @@ pango_fc_font_map_set_config (PangoFcFontMap *fcfontmap,
fcfontmap->priv->config = fcconfig;
+ g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free);
g_clear_pointer (&fcfontmap->priv->fonts, FcFontSetDestroy);
if (oldconfig != fcconfig)
@@ -2354,11 +2379,180 @@ pango_fc_font_map_get_config (PangoFcFontMap *fcfontmap)
return fcfontmap->priv->config;
}
+typedef struct _BitMatrix BitMatrix;
+
+struct _BitMatrix
+{
+ int rows;
+ int cols;
+ char *bits;
+};
+
+static void
+bit_matrix_free (BitMatrix *b)
+{
+ g_free (b->bits);
+ g_free (b);
+}
+
+static BitMatrix *
+bit_matrix_new (int rows, int cols)
+{
+ BitMatrix *b = g_new (BitMatrix, 1);
+
+ b->rows = rows;
+ b->cols = cols;
+ b->bits = g_new0 (char, (rows * cols) / 8 + 1);
+
+ return b;
+}
+
+static gboolean
+bit_matrix_get (BitMatrix *b, int i, int j)
+{
+ int pos = i * b->cols + j;
+
+ return (b->bits[pos / 8] & (1 << (pos % 8))) != 0;
+}
+
+static void
+bit_matrix_set (BitMatrix *b, int i, int j, gboolean value)
+{
+ int pos = i * b->cols + j;
+
+ if (value)
+ b->bits[pos / 8] = b->bits[pos / 8] | (1 << (pos % 8));
+ else
+ b->bits[pos / 8] = b->bits[pos / 8] & ~(1 << (pos % 8));
+}
+
+struct _CoverageOrder
+{
+ GHashTable *idx;
+ BitMatrix *order;
+};
+
+static void
+coverage_order_free (CoverageOrder *co)
+{
+ g_hash_table_unref (co->idx);
+ bit_matrix_free (co->order);
+ g_free (co);
+}
+
+static gboolean
+coverage_order_is_subset (CoverageOrder *co,
+ FcPattern *p1,
+ FcPattern *p2)
+{
+ int idx1, idx2;
+
+ idx1 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p1)) - 1;
+ idx2 = GPOINTER_TO_INT (g_hash_table_lookup (co->idx, p2)) - 1;
+
+ return bit_matrix_get (co->order, idx1, idx2);
+}
+
+static CoverageOrder *
+coverage_order_new (FcFontSet *fonts)
+{
+ CoverageOrder *co;
+ int *idx;
+ GPtrArray *coverages;
+ int max, i, j;
+
+ co = g_new (CoverageOrder, 1);
+
+ co->idx = g_hash_table_new (g_direct_hash, g_direct_equal);
+
+ idx = g_new (int, fonts->nfont);
+ coverages = g_ptr_array_new ();
+
+ max = -1;
+ for (i = 0; i < fonts->nfont; i++)
+ {
+ FcPattern *p1 = fonts->fonts[i];
+ FcCharSet *c1;
+
+ FcPatternGetCharSet (p1, "charset", 0, &c1);
+ idx[i] = max + 1;
+ for (j = 0; j < i; j++)
+ {
+ FcPattern *p2 = fonts->fonts[j];
+ FcCharSet *c2;
+
+ FcPatternGetCharSet (p2, "charset", 0, &c2);
+
+ if (FcCharSetEqual (c1, c2))
+ {
+ idx[i] = idx[j];
+ break;
+ }
+ }
+
+ g_hash_table_insert (co->idx, p1, GINT_TO_POINTER (idx[i] + 1));
+ if (idx[i] > max)
+ {
+ g_ptr_array_add (coverages, c1);
+ max = idx[i];
+ }
+ }
+
+ co->order = bit_matrix_new (coverages->len, coverages->len);
+
+ for (i = 0; i < coverages->len; i++)
+ {
+ FcCharSet *ci = g_ptr_array_index (coverages, i);
+ bit_matrix_set (co->order, i, i, TRUE);
+ for (j = 0; j < i; j++)
+ {
+ FcCharSet *cj = g_ptr_array_index (coverages, j);
+ gboolean v;
+ int k;
+
+ v = FALSE;
+ for (k = 0; k < coverages->len; k++)
+ {
+ if (bit_matrix_get (co->order, j, k) &&
+ bit_matrix_get (co->order, k, i))
+ {
+ v = TRUE;
+ break;
+ }
+ }
+
+ if (v || FcCharSetIsSubset (cj, ci))
+ bit_matrix_set (co->order, j, i, TRUE);
+
+ v = FALSE;
+ for (k = 0; k < coverages->len; k++)
+ {
+ if (bit_matrix_get (co->order, i, k) &&
+ bit_matrix_get (co->order, k, j))
+ {
+ v = TRUE;
+ break;
+ }
+ }
+
+ if (v || FcCharSetIsSubset (ci, cj))
+ bit_matrix_set (co->order, i, j, TRUE);
+ }
+ }
+
+ g_ptr_array_unref (coverages);
+ g_free (idx);
+
+ return co;
+}
+
static FcFontSet *
pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
{
if (fcfontmap->priv->fonts == NULL)
{
+ gint64 before;
+
FcFontSet *sets[2];
wait_for_fc_init ();
@@ -2366,6 +2560,11 @@ pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap)
sets[0] = FcConfigGetFonts (fcfontmap->priv->config, 0);
sets[1] = FcConfigGetFonts (fcfontmap->priv->config, 1);
fcfontmap->priv->fonts = filter_by_format (sets, 2);
+
+ before = g_get_monotonic_time ();
+ fcfontmap->priv->coverage_order = coverage_order_new (fcfontmap->priv->fonts);
+ g_print ("Computed coverage order in %.1f milliseconds\n",
+ (g_get_monotonic_time () - before) / ((double)G_TIME_SPAN_MILLISECOND));
}
return fcfontmap->priv->fonts;
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]