[Pixman] [PATCH 2/8] Add pixman_glyph_cache_t API

Søren Sandmann sandmann at cs.au.dk
Wed May 30 16:41:39 PDT 2012


From: Søren Sandmann Pedersen <ssp at redhat.com>

This new API allows entire glyph strings to be composited in one go
which reduces overhead compared to multiple calls to
pixman_image_composite32().

The pixman_glyph_cache_t is a hash table that maps two keys (a "font"
and a "glyph" key, but they are just keys; there is no distinction
between them as far as pixman is concerned) to a glyph. Glyphs in the
cache can be composited through two new entry points
pixman_glyph_cache_composite_glyphs() and
pixman_glyph_cache_composite_glyphs_no_mask().

A glyph cache may only be inserted into when it is "frozen", which is
achieved by calling pixman_glyph_cache_freeze(). When
pixman_glyph_cache_thaw() is later called, if the cache has become too
crowded, some glyphs (currently the least-recently-used) will
automatically be evicted. This means that a user must ensure that all
the required glyphs are present in the cache before compositing a
string. The intended way to use the cache is like this:

        pixman_glyph_t glyphs[MAX_GLYPHS];

        pixman_glyph_cache_freeze (cache);

        for (i = 0; i < n_glyphs; ++i)
        {
            const void *g;

            if (!(g = pixman_glyph_cache_lookup (cache, font_key, glyph_key)))
            {
                img = <rasterize glyph as a pixman_image_t>;

                g = pixman_glyph_cache_insert (cache, font_key, glyph_key,
                                               glyph_origin_x, glyph_origin_y,
                                               img);

                if (!g)
                {
                    /* Clean up out-of-memory condition */
                    goto oom;
                }

                glyphs[i].pos_x = glyph_x_pos;
                glyphs[i].pos_y = glyph_y_pos;
                glyphs[i].glyph = g;
            }
        }

        pixman_composite_glyphs (op, src, dest, ..., cache, n_glyphs, glyphs);

        pixman_glyph_cache_thaw (cache);
---
 pixman/Makefile.sources |    1 +
 pixman/pixman-glyph.c   |  439 +++++++++++++++++++++++++++++++++++++++++++++++
 pixman/pixman.h         |   56 ++++++
 3 files changed, 496 insertions(+)
 create mode 100644 pixman/pixman-glyph.c

diff --git a/pixman/Makefile.sources b/pixman/Makefile.sources
index ca3f001..11f959d 100644
--- a/pixman/Makefile.sources
+++ b/pixman/Makefile.sources
@@ -10,6 +10,7 @@ libpixman_sources =			\
 	pixman-edge.c			\
 	pixman-edge-accessors.c		\
 	pixman-fast-path.c		\
+	pixman-glyph.c			\
 	pixman-general.c		\
 	pixman-gradient-walker.c	\
 	pixman-image.c			\
diff --git a/pixman/pixman-glyph.c b/pixman/pixman-glyph.c
new file mode 100644
index 0000000..05aee86
--- /dev/null
+++ b/pixman/pixman-glyph.c
@@ -0,0 +1,439 @@
+/*
+ * Copyright 2010, 2012, Soren Sandmann <sandmann at cs.au.dk>
+ * Copyright 2010, 2011, Red Hat, Inc
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
+ * DEALINGS IN THE SOFTWARE.
+ *
+ * Author: Soren Sandmann <sandmann at cs.au.dk>
+ */
+#include <config.h>
+#include <stdlib.h>
+#include "pixman-private.h"
+
+typedef struct glyph_metrics_t glyph_metrics_t;
+typedef struct glyph_t glyph_t;
+
+#define TOMBSTONE ((glyph_t *)0x1)
+
+/* XXX: These numbers are arbitrary---we've never done any measurements.
+ */
+#define N_GLYPHS_HIGH_WATER  (16384)
+#define N_GLYPHS_LOW_WATER   (8192)
+#define HASH_SIZE (2 * N_GLYPHS_HIGH_WATER)
+#define HASH_MASK (HASH_SIZE - 1)
+
+struct glyph_t
+{
+    void *		font_key;
+    void *		glyph_key;
+    int			origin_x;
+    int			origin_y;
+    pixman_image_t *	image;
+    pixman_link_t	mru_link;
+};
+
+struct pixman_glyph_cache_t
+{
+    int			n_glyphs;
+    int			n_tombstones;
+    int			freeze_count;
+    pixman_list_t	mru;
+    glyph_t *		glyphs[HASH_SIZE];
+};
+
+static void
+free_glyph (glyph_t *glyph)
+{
+    pixman_list_unlink (&glyph->mru_link);
+    pixman_image_unref (glyph->image);
+    free (glyph);
+}
+
+static unsigned int
+hash (const void *font_key, const void *glyph_key)
+{
+    size_t key = (size_t)font_key + (size_t)glyph_key;
+
+    /* This hash function is based on one found on Thomas Wang's
+     * web page at
+     *
+     *    http://www.concentric.net/~Ttwang/tech/inthash.htm
+     *
+     */
+    key = (key << 15) - key - 1;
+    key = key ^ (key >> 12);
+    key = key + (key << 2);
+    key = key ^ (key >> 4);
+    key = key + (key << 3) + (key << 11);
+    key = key ^ (key >> 16);
+
+    return key;
+}
+
+static glyph_t *
+lookup_glyph (pixman_glyph_cache_t *cache,
+	      void                 *font_key,
+	      void                 *glyph_key)
+{
+    unsigned idx;
+    glyph_t *g;
+
+    idx = hash (font_key, glyph_key);
+    while ((g = cache->glyphs[idx++ & HASH_MASK]))
+    {
+	if (g != TOMBSTONE			&&
+	    g->font_key == font_key		&&
+	    g->glyph_key == glyph_key)
+	{
+	    return g;
+	}
+    }
+
+    return NULL;
+}
+
+static void
+insert_glyph (pixman_glyph_cache_t *cache,
+	      glyph_t              *glyph)
+{
+    unsigned idx;
+    glyph_t **loc;
+
+    idx = hash (glyph->font_key, glyph->glyph_key);
+
+    /* Note: we assume that there is room in the table. If there isn't,
+     * this will be an infinite loop.
+     */
+    do
+    {
+	loc = &cache->glyphs[idx++ & HASH_MASK];
+    } while (*loc && *loc != TOMBSTONE);
+
+    if (*loc == TOMBSTONE)
+	cache->n_tombstones--;
+    cache->n_glyphs++;
+
+    *loc = glyph;
+}
+
+static void
+remove_glyph (pixman_glyph_cache_t *cache,
+	      glyph_t              *glyph)
+{
+    unsigned idx;
+
+    idx = hash (glyph->font_key, glyph->glyph_key);
+    while (cache->glyphs[idx & HASH_MASK] != glyph)
+	idx++;
+
+    cache->glyphs[idx & HASH_MASK] = TOMBSTONE;
+    cache->n_tombstones++;
+    cache->n_glyphs--;
+
+    /* Eliminate tombstones if possible */
+    if (cache->glyphs[(idx + 1) & HASH_MASK] == NULL)
+    {
+	while (cache->glyphs[idx & HASH_MASK] == TOMBSTONE)
+	{
+	    cache->glyphs[idx & HASH_MASK] = NULL;
+	    cache->n_tombstones--;
+	    idx--;
+	}
+    }
+}
+
+static void
+clear_table (pixman_glyph_cache_t *cache)
+{
+    int i;
+
+    for (i = 0; i < HASH_SIZE; ++i)
+    {
+	glyph_t *glyph = cache->glyphs[i];
+
+	if (glyph && glyph != TOMBSTONE)
+	    free_glyph (glyph);
+
+	cache->glyphs[i] = NULL;
+    }
+
+    cache->n_glyphs = 0;
+    cache->n_tombstones = 0;
+}
+
+PIXMAN_EXPORT pixman_glyph_cache_t *
+pixman_glyph_cache_create (void)
+{
+    pixman_glyph_cache_t *cache;
+
+    if (!(cache = malloc (sizeof *cache)))
+	return NULL;
+
+    memset (cache->glyphs, 0, sizeof (cache->glyphs));
+    cache->n_glyphs = 0;
+    cache->n_tombstones = 0;
+    cache->freeze_count = 0;
+
+    pixman_list_init (&cache->mru);
+
+    return cache;
+}
+
+PIXMAN_EXPORT void
+pixman_glyph_cache_destroy (pixman_glyph_cache_t *cache)
+{
+    return_if_fail (cache->freeze_count == 0);
+
+    clear_table (cache);
+
+    free (cache);
+}
+
+PIXMAN_EXPORT void
+pixman_glyph_cache_freeze (pixman_glyph_cache_t  *cache)
+{
+    cache->freeze_count++;
+}
+
+PIXMAN_EXPORT void
+pixman_glyph_cache_thaw (pixman_glyph_cache_t  *cache)
+{
+    if (--cache->freeze_count == 0					&&
+	cache->n_glyphs + cache->n_tombstones > N_GLYPHS_HIGH_WATER)
+    {
+	if (cache->n_tombstones > N_GLYPHS_HIGH_WATER)
+	{
+	    /* More than half the entries are
+	     * tombstones. Just dump the whole table.
+	     */
+	    clear_table (cache);
+	}
+
+	while (cache->n_glyphs > N_GLYPHS_LOW_WATER)
+	{
+	    glyph_t *glyph = CONTAINER_OF (glyph_t, mru_link, cache->mru.tail);
+
+	    remove_glyph (cache, glyph);
+	    free_glyph (glyph);
+	}
+    }
+}
+
+PIXMAN_EXPORT const void *
+pixman_glyph_cache_lookup (pixman_glyph_cache_t  *cache,
+			   void                  *font_key,
+			   void                  *glyph_key)
+{
+    return lookup_glyph (cache, font_key, glyph_key);
+}
+
+PIXMAN_EXPORT const void *
+pixman_glyph_cache_insert (pixman_glyph_cache_t  *cache,
+			   void                  *font_key,
+			   void                  *glyph_key,
+			   int			  origin_x,
+			   int                    origin_y,
+			   pixman_image_t        *image)
+{
+    glyph_t *glyph;
+    int32_t width, height;
+
+    return_val_if_fail (cache->freeze_count > 0, NULL);
+    return_val_if_fail (image->type == BITS, NULL);
+
+    width = image->bits.width;
+    height = image->bits.height;
+
+    if (cache->n_glyphs >= HASH_SIZE)
+	return NULL;
+
+    if (!(glyph = malloc (sizeof *glyph)))
+	return NULL;
+
+    glyph->font_key = font_key;
+    glyph->glyph_key = glyph_key;
+    glyph->origin_x = origin_x;
+    glyph->origin_y = origin_y;
+
+    if (!(glyph->image = pixman_image_create_bits (
+	      image->bits.format, width, height, NULL, -1)))
+    {
+	free (glyph);
+	return NULL;
+    }
+
+    pixman_image_composite32 (PIXMAN_OP_SRC,
+			      image, NULL, glyph->image, 0, 0, 0, 0, 0, 0,
+			      width, height);
+
+    if (PIXMAN_FORMAT_A   (glyph->image->bits.format) != 0	&&
+	PIXMAN_FORMAT_RGB (glyph->image->bits.format) != 0)
+    {
+	pixman_image_set_component_alpha (glyph->image, TRUE);
+    }
+
+    pixman_list_prepend (&cache->mru, &glyph->mru_link);
+
+    _pixman_image_validate (glyph->image);
+    insert_glyph (cache, glyph);
+
+    return glyph;
+}
+
+PIXMAN_EXPORT void
+pixman_glyph_cache_remove (pixman_glyph_cache_t  *cache,
+			   void                  *font_key,
+			   void                  *glyph_key)
+{
+    glyph_t *glyph;
+
+    if ((glyph = lookup_glyph (cache, font_key, glyph_key)))
+    {
+	remove_glyph (cache, glyph);
+
+	free_glyph (glyph);
+    }
+}
+
+PIXMAN_EXPORT void
+pixman_glyph_get_extents (pixman_glyph_cache_t *cache,
+			  int                   n_glyphs,
+			  pixman_glyph_t       *glyphs,
+			  pixman_box32_t       *extents)
+{
+    int i;
+
+    extents->x1 = extents->y1 = INT32_MAX;
+    extents->x2 = extents->y2 = INT32_MIN;
+
+    for (i = 0; i < n_glyphs; ++i)
+    {
+	glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
+	int x1, y1, x2, y2;
+
+	x1 = glyphs[i].x - glyph->origin_x;
+	y1 = glyphs[i].y - glyph->origin_y;
+	x2 = glyphs[i].x - glyph->origin_x + glyph->image->bits.width;
+	y2 = glyphs[i].y - glyph->origin_y + glyph->image->bits.height;
+
+	if (x1 < extents->x1)
+	    extents->x1 = x1;
+	if (y1 < extents->y1)
+	    extents->y1 = y1;
+	if (x2 > extents->x2)
+	    extents->x2 = x2;
+	if (y2 > extents->y2)
+	    extents->y2 = y2;
+    }
+}
+
+PIXMAN_EXPORT void
+pixman_composite_glyphs_no_mask (pixman_op_t            op,
+				 pixman_image_t        *src,
+				 pixman_image_t        *dest,
+				 int32_t                src_x,
+				 int32_t                src_y,
+				 int32_t                dest_x,
+				 int32_t                dest_y,
+				 pixman_glyph_cache_t  *cache,
+				 int                    n_glyphs,
+				 pixman_glyph_t        *glyphs)
+{
+    int i;
+
+    for (i = 0; i < n_glyphs; ++i)
+    {
+	glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
+	pixman_image_t *glyph_img = glyph->image;
+
+	pixman_image_composite32 (op, src, glyph_img, dest,
+				  src_x + glyphs[i].x - glyph->origin_x,
+				  src_y + glyphs[i].y - glyph->origin_y,
+				  0, 0,
+				  dest_x + glyphs[i].x - glyph->origin_x,
+				  dest_y + glyphs[i].y - glyph->origin_y,
+				  glyph_img->bits.width,
+				  glyph_img->bits.height);
+    }
+}
+
+/* Conceptually, the glyphs are PIXMAN_OP_ADDed to an infinitely big mask image at
+ * the position such that the glyph origin point is positioned at the
+ * (glyphs[i].x, glyphs[i].y) point. Then the (mask_x, mask_y) point of this image
+ * and the (src_x, src_y) position of the source image are both aligned with (dest_x, dest_y)
+ * in the destination image.
+ *
+ * Finally, compositing takes place in the (dest_x, dest_y, dst_x + width, dst_y + height)
+ * rectangle.
+ *
+ * TODO:
+ *   - Trim the mask to the destination clip/image?
+ *   - Trim composite region based on sources, when the op ignores 0s.
+ */
+PIXMAN_EXPORT void
+pixman_composite_glyphs (pixman_op_t            op,
+			 pixman_image_t        *src,
+			 pixman_image_t        *dest,
+			 pixman_format_code_t   mask_format,
+			 int32_t                src_x,
+			 int32_t                src_y,
+			 int32_t		mask_x,
+			 int32_t		mask_y,
+			 int32_t                dest_x,
+			 int32_t                dest_y,
+			 int32_t                width,
+			 int32_t                height,
+			 pixman_glyph_cache_t  *cache,
+			 int			n_glyphs,
+			 pixman_glyph_t        *glyphs)
+{
+    pixman_image_t *mask;
+    int i;
+
+    if (!(mask = pixman_image_create_bits (mask_format, width, height, NULL, -1)))
+	return;
+
+    if (PIXMAN_FORMAT_A   (mask_format) != 0 &&
+	PIXMAN_FORMAT_RGB (mask_format) != 0)
+    {
+	pixman_image_set_component_alpha (mask, TRUE);
+    }
+
+    for (i = 0; i < n_glyphs; ++i)
+    {
+	glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
+	pixman_image_t *glyph_img = glyph->image;
+
+	pixman_image_composite32 (PIXMAN_OP_ADD, glyph_img, NULL, mask,
+				  0, 0, 0, 0,
+				  glyphs[i].x - glyph->origin_x - mask_x,
+				  glyphs[i].y - glyph->origin_y - mask_y,
+				  glyph->image->bits.width,
+				  glyph->image->bits.height);
+    }
+
+    pixman_image_composite32 (op, src, mask, dest,
+			      src_x, src_y,
+			      0, 0,
+			      dest_x, dest_y,
+			      width, height);
+
+    pixman_image_unref (mask);
+}
diff --git a/pixman/pixman.h b/pixman/pixman.h
index 18d9513..17be98b 100644
--- a/pixman/pixman.h
+++ b/pixman/pixman.h
@@ -868,6 +868,62 @@ void          pixman_image_composite32        (pixman_op_t        op,
 void pixman_disable_out_of_bounds_workaround (void);
 
 /*
+ * Glyphs
+ */
+typedef struct pixman_glyph_cache_t pixman_glyph_cache_t;
+typedef struct
+{
+    int		x, y;
+    const void *glyph;
+} pixman_glyph_t;
+
+pixman_glyph_cache_t *pixman_glyph_cache_create       (void);
+void                  pixman_glyph_cache_destroy      (pixman_glyph_cache_t *cache);
+void                  pixman_glyph_cache_freeze       (pixman_glyph_cache_t *cache);
+void                  pixman_glyph_cache_thaw         (pixman_glyph_cache_t *cache);
+const void *          pixman_glyph_cache_lookup       (pixman_glyph_cache_t *cache,
+						       void                 *font_key,
+						       void                 *glyph_key);
+const void *          pixman_glyph_cache_insert       (pixman_glyph_cache_t *cache,
+						       void                 *font_key,
+						       void                 *glyph_key,
+						       int		     origin_x,
+						       int                   origin_y,
+						       pixman_image_t       *glyph_image);
+void                  pixman_glyph_cache_remove       (pixman_glyph_cache_t *cache,
+						       void                 *font_key,
+						       void                 *glyph_key);
+void                  pixman_glyph_get_extents        (pixman_glyph_cache_t *cache,
+						       int                   n_glyphs,
+						       pixman_glyph_t       *glyphs,
+						       pixman_box32_t       *extents);
+void                  pixman_composite_glyphs         (pixman_op_t           op,
+						       pixman_image_t       *src,
+						       pixman_image_t       *dest,
+						       pixman_format_code_t  mask_format,
+						       int32_t               src_x,
+						       int32_t               src_y,
+						       int32_t		     mask_x,
+						       int32_t		     mask_y,
+						       int32_t               dest_x,
+						       int32_t               dest_y,
+						       int32_t		     width,
+						       int32_t		     height,
+						       pixman_glyph_cache_t *cache,
+						       int		     n_glyphs,
+						       pixman_glyph_t       *glyphs);
+void                  pixman_composite_glyphs_no_mask (pixman_op_t           op,
+						       pixman_image_t       *src,
+						       pixman_image_t       *dest,
+						       int32_t               src_x,
+						       int32_t               src_y,
+						       int32_t               dest_x,
+						       int32_t               dest_y,
+						       pixman_glyph_cache_t *cache,
+						       int		     n_glyphs,
+						       pixman_glyph_t       *glyphs);
+
+/*
  * Trapezoids
  */
 typedef struct pixman_edge pixman_edge_t;
-- 
1.7.10.2



More information about the Pixman mailing list