Looks nice. I don't see you updating the mru list though. behdad
On 05/30/2012 07:41 PM, Søren Sandmann wrote: > From: Søren Sandmann Pedersen <s...@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 <sandm...@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 <sandm...@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; _______________________________________________ Pixman mailing list Pixman@lists.freedesktop.org http://lists.freedesktop.org/mailman/listinfo/pixman