[pango/wip-bitmatrix] Compute the coverage order ahead of time

[Matthias Clasen <matthiasc src gnome org>]

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;