/* 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 .
*
* Authors: Matthias Clasen
*/
#include "config.h"
#include "pangofc-coverageorder-private.h"
#include
/* 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;
}