diff options
-rw-r--r-- | pango/meson.build | 1 | ||||
-rw-r--r-- | pango/pangofc-coverageorder-private.h | 40 | ||||
-rw-r--r-- | pango/pangofc-coverageorder.c | 239 | ||||
-rw-r--r-- | pango/pangofc-fontmap.c | 89 |
4 files changed, 360 insertions, 9 deletions
diff --git a/pango/meson.build b/pango/meson.build index 777f5374..79dabe77 100644 --- a/pango/meson.build +++ b/pango/meson.build @@ -185,6 +185,7 @@ if build_pangoft2 'pangofc-font.c', 'pangofc-fontmap.c', 'pangofc-decoder.c', + 'pangofc-coverageorder.c', 'pango-trace.c', ] diff --git a/pango/pangofc-coverageorder-private.h b/pango/pangofc-coverageorder-private.h new file mode 100644 index 00000000..6537ed06 --- /dev/null +++ b/pango/pangofc-coverageorder-private.h @@ -0,0 +1,40 @@ +/* Pango + * coverageorder.h: + * + * Copyright (C) 2020 Red Hat, Inc. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see <http://www.gnu.org/licenses/>. + * + * Authors: Matthias Clasen + */ + +#ifndef __COVERAGE_ORDER_H__ +#define __COVERAGE_ORDER_H__ + +#include <glib.h> +#include <fontconfig/fontconfig.h> + +G_BEGIN_DECLS + +typedef struct _CoverageOrder CoverageOrder; + +CoverageOrder * coverage_order_new (FcFontSet *fonts); +void coverage_order_free (CoverageOrder *co); +gboolean coverage_order_is_subset (CoverageOrder *co, + FcPattern *p1, + FcPattern *p2); + +G_END_DECLS + +#endif /* __COVERAGE_ORDER_H__ */ diff --git a/pango/pangofc-coverageorder.c b/pango/pangofc-coverageorder.c new file mode 100644 index 00000000..86114b38 --- /dev/null +++ b/pango/pangofc-coverageorder.c @@ -0,0 +1,239 @@ +/* Pango + * coverageorder.c: + * + * Copyright (C) 2020 Red Hat, Inc. + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Library General Public + * License as published by the Free Software Foundation; either + * version 2 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Library General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library. If not, see <http://www.gnu.org/licenses/>. + * + * Authors: Matthias Clasen + */ + +#include "config.h" + +#include "pangofc-coverageorder-private.h" +#include <glib.h> + +/* BitMatrix is a simple matrix of bits that can be + * addressed by their row and column. + */ +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; + int byte = pos / 8; + int bit = pos % 8; + + return (b->bits[byte] & (1 << bit)) != 0; +} + +static void +bit_matrix_set (BitMatrix *b, int i, int j, gboolean value) +{ + int pos = i * b->cols + j; + int byte = pos / 8; + int bit = pos % 8; + + if (value) + b->bits[byte] = b->bits[byte] | (1 << bit); + else + b->bits[byte] = b->bits[byte] & ~(1 << bit); +} + +/* By coverage order, we mean the partial order that is defined on + * the fonts by the subset relation on their charsets. This order + * only depends on the font configuration, and can be computed + * ahead of time or even saved to disk. + * + * An important aspect of why this works is that in practice, + * many fonts have the same coverage, so our matrix stays much + * smaller than |fonts| * |fonts|. + */ + +struct _CoverageOrder +{ + GHashTable *idx; + BitMatrix *order; +}; + +/* + * coverage_order_free: + * + * Frees a CoverageOrder struct and all associated memory. + */ +void +coverage_order_free (CoverageOrder *co) +{ + g_hash_table_unref (co->idx); + bit_matrix_free (co->order); + g_free (co); +} + +/* + * coverage_order_is_subset: + * @co: a #CoverageOrder + * @p1: a pattern + * @p2: another pattern + * + * Determines if the charset of @p1 is a subset + * of the charset of @p2. + * + * Returns: %TRUE if @p1 is a subset of @p2 + */ +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); +} + +/* + * coverage_order_new: + * @fonts: a set of fonts + * + * Compute the coverage order for the fonts in @fonts. + * + * Returns: a new #CoverageOrder + */ +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 (); + + /* First group the fonts that have the same + * charset, by giving them the same 'index'. + */ + 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]; + } + } + + /* Now compute the full incidence matrix for the + * remaining charsets. + */ + 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; +} diff --git a/pango/pangofc-fontmap.c b/pango/pangofc-fontmap.c index d859c493..a2aefcf3 100644 --- a/pango/pangofc-fontmap.c +++ b/pango/pangofc-fontmap.c @@ -55,6 +55,7 @@ #include "pango-enum-types.h" #include "pango-coverage-private.h" #include "pango-trace-private.h" +#include "pangofc-coverageorder-private.h" #include <hb-ft.h> @@ -167,6 +168,9 @@ struct _PangoFcFontMapPrivate FcConfig *config; FcFontSet *fonts; + + CoverageOrder *coverage_order; + GCancellable *coverage_cancellable; }; struct _PangoFcFontFaceData @@ -1077,10 +1081,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 (char, fontset->nfont); @@ -1091,14 +1092,33 @@ 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; + int l; - FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs); + if (pats->fontmap->priv->coverage_order) + { + 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; - FcCharSetMerge (pats->cs, fcs, &added); + FcPatternGetCharSet (fontset->fonts[f], "charset", 0, &fcs); - pats->skip[f] = added ? 2 : 1; + FcCharSetMerge (pats->cs, fcs, &added); + + pats->skip[f] = added ? 2 : 1; + } } if (pats->skip[f] == 2) /* don't skip */ @@ -1469,6 +1489,12 @@ pango_fc_font_map_fini (PangoFcFontMap *fcfontmap) PangoFcFontMapPrivate *priv = fcfontmap->priv; int i; + if (priv->coverage_cancellable) + { + g_cancellable_cancel (priv->coverage_cancellable); + g_clear_object (&priv->coverage_cancellable); + } + g_clear_pointer (&priv->coverage_order, coverage_order_free); g_clear_pointer (&priv->fonts, FcFontSetDestroy); g_queue_free (priv->fontset_cache); @@ -2346,6 +2372,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) @@ -2381,11 +2408,39 @@ pango_fc_font_map_get_config (PangoFcFontMap *fcfontmap) return fcfontmap->priv->config; } +static void +compute_coverage_order_in_thread (GTask *task, + gpointer source_object, + gpointer task_data, + GCancellable *cancellable) +{ + FcFontSet *fonts = task_data; + CoverageOrder *coverage_order; + gint64 before = PANGO_TRACE_CURRENT_TIME; + + coverage_order = coverage_order_new (fonts); + + pango_trace_mark (before, "compute_coverage_order", NULL); + + g_task_return_pointer (task, coverage_order, (GDestroyNotify)coverage_order_free); +} + +static void +coverage_computed (GObject *source_object, + GAsyncResult *result, + gpointer data) +{ + PangoFcFontMap *fcfontmap = PANGO_FC_FONT_MAP (source_object); + + fcfontmap->priv->coverage_order = g_task_propagate_pointer (G_TASK (result), NULL); +} + static FcFontSet * pango_fc_font_map_get_config_fonts (PangoFcFontMap *fcfontmap) { if (fcfontmap->priv->fonts == NULL) { + GTask *task; FcFontSet *sets[2]; wait_for_fc_init (); @@ -2393,6 +2448,22 @@ 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); + + g_clear_pointer (&fcfontmap->priv->coverage_order, coverage_order_free); + + if (fcfontmap->priv->coverage_cancellable) + { + g_cancellable_cancel (fcfontmap->priv->coverage_cancellable); + g_clear_object (&fcfontmap->priv->coverage_cancellable); + } + + fcfontmap->priv->coverage_cancellable = g_cancellable_new (); + + task = g_task_new (fcfontmap, fcfontmap->priv->coverage_cancellable, coverage_computed, NULL); + g_task_set_name (task, "[pango] compute_coverage_order"); + g_task_set_task_data (task, font_set_copy (fcfontmap->priv->fonts), (GDestroyNotify)FcFontSetDestroy); + g_task_run_in_thread (task, compute_coverage_order_in_thread); + g_object_unref (task); } return fcfontmap->priv->fonts; |