/* 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
#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 int
bit_matrix_get_length (BitMatrix *b)
{
return (b->rows * b->cols) / 8 + 1;
}
static void
bit_matrix_get_size (BitMatrix *b,
int *rows,
int *cols)
{
*rows = b->rows;
*cols = b->cols;
}
static char *
bit_matrix_get_bits (BitMatrix *b)
{
return b->bits;
}
static BitMatrix *
bit_matrix_new (int rows, int cols, char *bits)
{
BitMatrix *b = g_new (BitMatrix, 1);
int len;
b->rows = rows;
b->cols = cols;
len = (rows * cols) / 8 + 1;
b->bits = g_new (char, len);
if (bits)
memcpy (b->bits, bits, len);
else
memset (b->bits, 0, len);
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, NULL);
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;
}
gboolean
coverage_order_save (CoverageOrder *co,
FcFontSet *fonts,
const char *filename,
GError **error)
{
char *prefix;
gsize prefix_len;
gsize idx_len;
gsize len;
char *contents;
gboolean retval;
guint32 *idx;
int i;
int rows, cols;
bit_matrix_get_size (co->order, &rows, &cols);
prefix = g_strdup_printf ("%d %d\n", rows, fonts->nfont);
prefix_len = strlen (prefix);
idx_len = sizeof (guint32) * fonts->nfont * 2;
idx = g_new (guint32, idx_len);
for (i = 0; i < fonts->nfont; i++)
{
FcPattern *p = fonts->fonts[i];
idx[2*i] = FcPatternHash (p);
idx[2*i+1] = GPOINTER_TO_UINT (g_hash_table_lookup (co->idx, p)) - 1;
}
len = prefix_len + idx_len + bit_matrix_get_length (co->order);
contents = malloc (len);
memcpy (contents, prefix, prefix_len);
memcpy (contents + prefix_len, idx, idx_len);
memcpy (contents + prefix_len + idx_len, bit_matrix_get_bits (co->order), bit_matrix_get_length (co->order));
retval = g_file_set_contents (filename, contents, len, error);
g_free (contents);
g_free (prefix);
g_free (idx);
g_debug ("Wrote %ld bytes to %s.", len, filename);
if (g_getenv ("EXIT")) exit (0);
return retval;
}
CoverageOrder *
coverage_order_load (FcFontSet *fonts,
const char *filename,
GError **error)
{
CoverageOrder *co = NULL;
GMappedFile *file;
char *contents;
char *prefix;
char **parts;
int size;
int nfont;
int prefix_len;
int idx_len;
guint32 *idx;
GHashTable *table;
int i;
file = g_mapped_file_new (filename, FALSE, error);
if (!file)
return NULL;
contents = g_mapped_file_get_contents (file);
prefix = NULL;
for (i = 0; i < 100; i++)
{
if (contents[i] == '\n')
prefix = g_strndup (contents, i);
}
if (prefix == NULL)
{
g_set_error (error,
G_IO_ERROR, G_IO_ERROR_FAILED,
"%s: Didn't find prefix", filename);
goto out;
}
parts = g_strsplit (prefix, " ", -1);
if (g_strv_length (parts) != 2)
{
g_set_error (error,
G_IO_ERROR, G_IO_ERROR_FAILED,
"%s: Prefix looks bad", filename);
g_free (prefix);
g_strfreev (parts);
goto out;
}
prefix_len = strlen (prefix) + 1;
size = (int) g_ascii_strtoll (parts[0], NULL, 10);
nfont = (int) g_ascii_strtoll (parts[1], NULL, 10);
g_strfreev (parts);
g_free (prefix);
if (size <= 0 || nfont <= size)
{
g_set_error (error,
G_IO_ERROR, G_IO_ERROR_FAILED,
"%s: Numbers don't add up", filename);
goto out;
}
if (nfont != fonts->nfont)
{
g_set_error (error,
G_IO_ERROR, G_IO_ERROR_FAILED,
"%s: Wrong number of fonts", filename);
goto out;
}
table = g_hash_table_new (g_direct_hash, g_direct_equal);
idx_len = sizeof (guint32) * nfont * 2;
idx = (guint32 *)(contents + prefix_len);
for (i = 0; i < fonts->nfont; i++)
{
FcPattern *p = fonts->fonts[i];
guint32 hash = idx[2*i];
guint32 index = idx[2*i+1];
if (hash != FcPatternHash (p))
{
g_set_error (error,
G_IO_ERROR, G_IO_ERROR_FAILED,
"%s: Fonts changed", filename);
g_hash_table_unref (table);
goto out;
}
g_hash_table_insert (table, p, GUINT_TO_POINTER (index + 1));
}
co = g_new (CoverageOrder, 1);
co->idx = table;
co->order = bit_matrix_new (size, size, contents + prefix_len + idx_len);
out:
g_mapped_file_unref (file);
return co;
}