2 * Copyright 2010, 2012, Soren Sandmann <sandmann@cs.au.dk>
3 * Copyright 2010, 2011, 2012, Red Hat, Inc
5 * Permission is hereby granted, free of charge, to any person obtaining a
6 * copy of this software and associated documentation files (the "Software"),
7 * to deal in the Software without restriction, including without limitation
8 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9 * and/or sell copies of the Software, and to permit persons to whom the
10 * Software is furnished to do so, subject to the following conditions:
12 * The above copyright notice and this permission notice (including the next
13 * paragraph) shall be included in all copies or substantial portions of the
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
19 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
24 * Author: Soren Sandmann <sandmann@cs.au.dk>
30 #include "pixman-private.h"
34 typedef struct glyph_metrics_t glyph_metrics_t
;
35 typedef struct glyph_t glyph_t
;
37 #define TOMBSTONE ((glyph_t *)0x1)
39 /* XXX: These numbers are arbitrary---we've never done any measurements.
41 #define N_GLYPHS_HIGH_WATER (16384)
42 #define N_GLYPHS_LOW_WATER (8192)
43 #define HASH_SIZE (2 * N_GLYPHS_HIGH_WATER)
44 #define HASH_MASK (HASH_SIZE - 1)
52 pixman_image_t
* image
;
53 pixman_link_t mru_link
;
56 struct pixman_glyph_cache_t
62 glyph_t
* glyphs
[HASH_SIZE
];
66 free_glyph (glyph_t
*glyph
)
68 pixman_list_unlink (&glyph
->mru_link
);
69 pixman_image_unref (glyph
->image
);
74 hash (const void *font_key
, const void *glyph_key
)
76 size_t key
= (size_t)font_key
+ (size_t)glyph_key
;
78 /* This hash function is based on one found on Thomas Wang's
81 * http://www.concentric.net/~Ttwang/tech/inthash.htm
84 key
= (key
<< 15) - key
- 1;
85 key
= key
^ (key
>> 12);
86 key
= key
+ (key
<< 2);
87 key
= key
^ (key
>> 4);
88 key
= key
+ (key
<< 3) + (key
<< 11);
89 key
= key
^ (key
>> 16);
95 lookup_glyph (pixman_glyph_cache_t
*cache
,
102 idx
= hash (font_key
, glyph_key
);
103 while ((g
= cache
->glyphs
[idx
++ & HASH_MASK
]))
105 if (g
!= TOMBSTONE
&&
106 g
->font_key
== font_key
&&
107 g
->glyph_key
== glyph_key
)
117 insert_glyph (pixman_glyph_cache_t
*cache
,
123 idx
= hash (glyph
->font_key
, glyph
->glyph_key
);
125 /* Note: we assume that there is room in the table. If there isn't,
126 * this will be an infinite loop.
130 loc
= &cache
->glyphs
[idx
++ & HASH_MASK
];
131 } while (*loc
&& *loc
!= TOMBSTONE
);
133 if (*loc
== TOMBSTONE
)
134 cache
->n_tombstones
--;
141 remove_glyph (pixman_glyph_cache_t
*cache
,
146 idx
= hash (glyph
->font_key
, glyph
->glyph_key
);
147 while (cache
->glyphs
[idx
& HASH_MASK
] != glyph
)
150 cache
->glyphs
[idx
& HASH_MASK
] = TOMBSTONE
;
151 cache
->n_tombstones
++;
154 /* Eliminate tombstones if possible */
155 if (cache
->glyphs
[(idx
+ 1) & HASH_MASK
] == NULL
)
157 while (cache
->glyphs
[idx
& HASH_MASK
] == TOMBSTONE
)
159 cache
->glyphs
[idx
& HASH_MASK
] = NULL
;
160 cache
->n_tombstones
--;
167 clear_table (pixman_glyph_cache_t
*cache
)
171 for (i
= 0; i
< HASH_SIZE
; ++i
)
173 glyph_t
*glyph
= cache
->glyphs
[i
];
175 if (glyph
&& glyph
!= TOMBSTONE
)
178 cache
->glyphs
[i
] = NULL
;
182 cache
->n_tombstones
= 0;
185 PIXMAN_EXPORT pixman_glyph_cache_t
*
186 pixman_glyph_cache_create (void)
188 pixman_glyph_cache_t
*cache
;
190 if (!(cache
= malloc (sizeof *cache
)))
193 memset (cache
->glyphs
, 0, sizeof (cache
->glyphs
));
195 cache
->n_tombstones
= 0;
196 cache
->freeze_count
= 0;
198 pixman_list_init (&cache
->mru
);
204 pixman_glyph_cache_destroy (pixman_glyph_cache_t
*cache
)
206 return_if_fail (cache
->freeze_count
== 0);
214 pixman_glyph_cache_freeze (pixman_glyph_cache_t
*cache
)
216 cache
->freeze_count
++;
220 pixman_glyph_cache_thaw (pixman_glyph_cache_t
*cache
)
222 if (--cache
->freeze_count
== 0 &&
223 cache
->n_glyphs
+ cache
->n_tombstones
> N_GLYPHS_HIGH_WATER
)
225 if (cache
->n_tombstones
> N_GLYPHS_HIGH_WATER
)
227 /* More than half the entries are
228 * tombstones. Just dump the whole table.
233 while (cache
->n_glyphs
> N_GLYPHS_LOW_WATER
)
235 glyph_t
*glyph
= CONTAINER_OF (glyph_t
, mru_link
, cache
->mru
.tail
);
237 remove_glyph (cache
, glyph
);
243 PIXMAN_EXPORT
const void *
244 pixman_glyph_cache_lookup (pixman_glyph_cache_t
*cache
,
248 return lookup_glyph (cache
, font_key
, glyph_key
);
251 PIXMAN_EXPORT
const void *
252 pixman_glyph_cache_insert (pixman_glyph_cache_t
*cache
,
257 pixman_image_t
*image
)
260 int32_t width
, height
;
262 return_val_if_fail (cache
->freeze_count
> 0, NULL
);
263 return_val_if_fail (image
->type
== BITS
, NULL
);
265 width
= image
->bits
.width
;
266 height
= image
->bits
.height
;
268 if (cache
->n_glyphs
>= HASH_SIZE
)
271 if (!(glyph
= malloc (sizeof *glyph
)))
274 glyph
->font_key
= font_key
;
275 glyph
->glyph_key
= glyph_key
;
276 glyph
->origin_x
= origin_x
;
277 glyph
->origin_y
= origin_y
;
279 if (!(glyph
->image
= pixman_image_create_bits (
280 image
->bits
.format
, width
, height
, NULL
, -1)))
286 pixman_image_composite32 (PIXMAN_OP_SRC
,
287 image
, NULL
, glyph
->image
, 0, 0, 0, 0, 0, 0,
290 if (PIXMAN_FORMAT_A (glyph
->image
->bits
.format
) != 0 &&
291 PIXMAN_FORMAT_RGB (glyph
->image
->bits
.format
) != 0)
293 pixman_image_set_component_alpha (glyph
->image
, TRUE
);
296 pixman_list_prepend (&cache
->mru
, &glyph
->mru_link
);
298 _pixman_image_validate (glyph
->image
);
299 insert_glyph (cache
, glyph
);
305 pixman_glyph_cache_remove (pixman_glyph_cache_t
*cache
,
311 if ((glyph
= lookup_glyph (cache
, font_key
, glyph_key
)))
313 remove_glyph (cache
, glyph
);
320 pixman_glyph_get_extents (pixman_glyph_cache_t
*cache
,
322 pixman_glyph_t
*glyphs
,
323 pixman_box32_t
*extents
)
327 extents
->x1
= extents
->y1
= INT32_MAX
;
328 extents
->x2
= extents
->y2
= INT32_MIN
;
330 for (i
= 0; i
< n_glyphs
; ++i
)
332 glyph_t
*glyph
= (glyph_t
*)glyphs
[i
].glyph
;
335 x1
= glyphs
[i
].x
- glyph
->origin_x
;
336 y1
= glyphs
[i
].y
- glyph
->origin_y
;
337 x2
= glyphs
[i
].x
- glyph
->origin_x
+ glyph
->image
->bits
.width
;
338 y2
= glyphs
[i
].y
- glyph
->origin_y
+ glyph
->image
->bits
.height
;
340 if (x1
< extents
->x1
)
342 if (y1
< extents
->y1
)
344 if (x2
> extents
->x2
)
346 if (y2
> extents
->y2
)
351 /* This function returns a format that is suitable for use as a mask for the
352 * set of glyphs in question.
354 PIXMAN_EXPORT pixman_format_code_t
355 pixman_glyph_get_mask_format (pixman_glyph_cache_t
*cache
,
357 const pixman_glyph_t
*glyphs
)
359 pixman_format_code_t format
= PIXMAN_a1
;
362 for (i
= 0; i
< n_glyphs
; ++i
)
364 const glyph_t
*glyph
= glyphs
[i
].glyph
;
365 pixman_format_code_t glyph_format
= glyph
->image
->bits
.format
;
367 if (PIXMAN_FORMAT_TYPE (glyph_format
) == PIXMAN_TYPE_A
)
369 if (PIXMAN_FORMAT_A (glyph_format
) > PIXMAN_FORMAT_A (format
))
370 format
= glyph_format
;
374 return PIXMAN_a8r8g8b8
;
382 box32_intersect (pixman_box32_t
*dest
,
383 const pixman_box32_t
*box1
,
384 const pixman_box32_t
*box2
)
386 dest
->x1
= MAX (box1
->x1
, box2
->x1
);
387 dest
->y1
= MAX (box1
->y1
, box2
->y1
);
388 dest
->x2
= MIN (box1
->x2
, box2
->x2
);
389 dest
->y2
= MIN (box1
->y2
, box2
->y2
);
391 return dest
->x2
> dest
->x1
&& dest
->y2
> dest
->y1
;
394 #if defined(__GNUC__) && !defined(__x86_64__) && !defined(__amd64__)
395 __attribute__((__force_align_arg_pointer__
))
398 pixman_composite_glyphs_no_mask (pixman_op_t op
,
400 pixman_image_t
*dest
,
405 pixman_glyph_cache_t
*cache
,
407 const pixman_glyph_t
*glyphs
)
409 pixman_region32_t region
;
410 pixman_format_code_t glyph_format
= PIXMAN_null
;
411 uint32_t glyph_flags
= 0;
412 pixman_format_code_t dest_format
;
414 pixman_composite_func_t func
= NULL
;
415 pixman_implementation_t
*implementation
= NULL
;
416 pixman_composite_info_t info
;
419 _pixman_image_validate (src
);
420 _pixman_image_validate (dest
);
422 dest_format
= dest
->common
.extended_format_code
;
423 dest_flags
= dest
->common
.flags
;
425 pixman_region32_init (®ion
);
426 if (!_pixman_compute_composite_region32 (
429 src_x
- dest_x
, src_y
- dest_y
, 0, 0, 0, 0,
430 dest
->bits
.width
, dest
->bits
.height
))
436 info
.src_image
= src
;
437 info
.dest_image
= dest
;
438 info
.src_flags
= src
->common
.flags
;
439 info
.dest_flags
= dest
->common
.flags
;
441 for (i
= 0; i
< n_glyphs
; ++i
)
443 glyph_t
*glyph
= (glyph_t
*)glyphs
[i
].glyph
;
444 pixman_image_t
*glyph_img
= glyph
->image
;
445 pixman_box32_t glyph_box
;
446 pixman_box32_t
*pbox
;
447 uint32_t extra
= FAST_PATH_SAMPLES_COVER_CLIP_NEAREST
;
448 pixman_box32_t composite_box
;
451 glyph_box
.x1
= dest_x
+ glyphs
[i
].x
- glyph
->origin_x
;
452 glyph_box
.y1
= dest_y
+ glyphs
[i
].y
- glyph
->origin_y
;
453 glyph_box
.x2
= glyph_box
.x1
+ glyph
->image
->bits
.width
;
454 glyph_box
.y2
= glyph_box
.y1
+ glyph
->image
->bits
.height
;
456 pbox
= pixman_region32_rectangles (®ion
, &n
);
458 info
.mask_image
= glyph_img
;
462 if (box32_intersect (&composite_box
, pbox
, &glyph_box
))
464 if (glyph_img
->common
.extended_format_code
!= glyph_format
||
465 glyph_img
->common
.flags
!= glyph_flags
)
467 glyph_format
= glyph_img
->common
.extended_format_code
;
468 glyph_flags
= glyph_img
->common
.flags
;
470 _pixman_implementation_lookup_composite (
471 get_implementation(), op
,
472 src
->common
.extended_format_code
, src
->common
.flags
,
473 glyph_format
, glyph_flags
| extra
,
474 dest_format
, dest_flags
,
475 &implementation
, &func
);
478 info
.src_x
= src_x
+ composite_box
.x1
- dest_x
;
479 info
.src_y
= src_y
+ composite_box
.y1
- dest_y
;
480 info
.mask_x
= composite_box
.x1
- (dest_x
+ glyphs
[i
].x
- glyph
->origin_x
);
481 info
.mask_y
= composite_box
.y1
- (dest_y
+ glyphs
[i
].y
- glyph
->origin_y
);
482 info
.dest_x
= composite_box
.x1
;
483 info
.dest_y
= composite_box
.y1
;
484 info
.width
= composite_box
.x2
- composite_box
.x1
;
485 info
.height
= composite_box
.y2
- composite_box
.y1
;
487 info
.mask_flags
= glyph_flags
;
489 func (implementation
, &info
);
494 pixman_list_move_to_front (&cache
->mru
, &glyph
->mru_link
);
498 pixman_region32_fini (®ion
);
502 add_glyphs (pixman_glyph_cache_t
*cache
,
503 pixman_image_t
*dest
,
504 int off_x
, int off_y
,
505 int n_glyphs
, const pixman_glyph_t
*glyphs
)
507 pixman_format_code_t glyph_format
= PIXMAN_null
;
508 uint32_t glyph_flags
= 0;
509 pixman_composite_func_t func
= NULL
;
510 pixman_implementation_t
*implementation
= NULL
;
511 pixman_format_code_t dest_format
;
513 pixman_box32_t dest_box
;
514 pixman_composite_info_t info
;
515 pixman_image_t
*white_img
= NULL
;
516 pixman_bool_t white_src
= FALSE
;
519 _pixman_image_validate (dest
);
521 dest_format
= dest
->common
.extended_format_code
;
522 dest_flags
= dest
->common
.flags
;
524 info
.op
= PIXMAN_OP_ADD
;
525 info
.dest_image
= dest
;
528 info
.dest_flags
= dest_flags
;
532 dest_box
.x2
= dest
->bits
.width
;
533 dest_box
.y2
= dest
->bits
.height
;
535 for (i
= 0; i
< n_glyphs
; ++i
)
537 glyph_t
*glyph
= (glyph_t
*)glyphs
[i
].glyph
;
538 pixman_image_t
*glyph_img
= glyph
->image
;
539 pixman_box32_t glyph_box
;
540 pixman_box32_t composite_box
;
542 if (glyph_img
->common
.extended_format_code
!= glyph_format
||
543 glyph_img
->common
.flags
!= glyph_flags
)
545 pixman_format_code_t src_format
, mask_format
;
547 glyph_format
= glyph_img
->common
.extended_format_code
;
548 glyph_flags
= glyph_img
->common
.flags
;
550 if (glyph_format
== dest
->bits
.format
)
552 src_format
= glyph_format
;
553 mask_format
= PIXMAN_null
;
554 info
.src_flags
= glyph_flags
| FAST_PATH_SAMPLES_COVER_CLIP_NEAREST
;
555 info
.mask_flags
= FAST_PATH_IS_OPAQUE
;
556 info
.mask_image
= NULL
;
563 static const pixman_color_t white
= { 0xffff, 0xffff, 0xffff, 0xffff };
565 if (!(white_img
= pixman_image_create_solid_fill (&white
)))
568 _pixman_image_validate (white_img
);
571 src_format
= PIXMAN_solid
;
572 mask_format
= glyph_format
;
573 info
.src_flags
= white_img
->common
.flags
;
574 info
.mask_flags
= glyph_flags
| FAST_PATH_SAMPLES_COVER_CLIP_NEAREST
;
575 info
.src_image
= white_img
;
579 _pixman_implementation_lookup_composite (
580 get_implementation(), PIXMAN_OP_ADD
,
581 src_format
, info
.src_flags
,
582 mask_format
, info
.mask_flags
,
583 dest_format
, dest_flags
,
584 &implementation
, &func
);
587 glyph_box
.x1
= glyphs
[i
].x
- glyph
->origin_x
+ off_x
;
588 glyph_box
.y1
= glyphs
[i
].y
- glyph
->origin_y
+ off_y
;
589 glyph_box
.x2
= glyph_box
.x1
+ glyph
->image
->bits
.width
;
590 glyph_box
.y2
= glyph_box
.y1
+ glyph
->image
->bits
.height
;
592 if (box32_intersect (&composite_box
, &glyph_box
, &dest_box
))
594 int src_x
= composite_box
.x1
- glyph_box
.x1
;
595 int src_y
= composite_box
.y1
- glyph_box
.y1
;
598 info
.mask_image
= glyph_img
;
600 info
.src_image
= glyph_img
;
602 info
.mask_x
= info
.src_x
= src_x
;
603 info
.mask_y
= info
.src_y
= src_y
;
604 info
.dest_x
= composite_box
.x1
;
605 info
.dest_y
= composite_box
.y1
;
606 info
.width
= composite_box
.x2
- composite_box
.x1
;
607 info
.height
= composite_box
.y2
- composite_box
.y1
;
609 func (implementation
, &info
);
611 pixman_list_move_to_front (&cache
->mru
, &glyph
->mru_link
);
617 pixman_image_unref (white_img
);
620 /* Conceptually, for each glyph, (white IN glyph) is PIXMAN_OP_ADDed to an
621 * infinitely big mask image at the position such that the glyph origin point
622 * is positioned at the (glyphs[i].x, glyphs[i].y) point.
624 * Then (mask_x, mask_y) in the infinite mask and (src_x, src_y) in the source
625 * image are both aligned with (dest_x, dest_y) in the destination image. Then
626 * these three images are composited within the
628 * (dest_x, dest_y, dst_x + width, dst_y + height)
633 * - Trim the mask to the destination clip/image?
634 * - Trim composite region based on sources, when the op ignores 0s.
636 #if defined(__GNUC__) && !defined(__x86_64__) && !defined(__amd64__)
637 __attribute__((__force_align_arg_pointer__
))
640 pixman_composite_glyphs (pixman_op_t op
,
642 pixman_image_t
*dest
,
643 pixman_format_code_t mask_format
,
652 pixman_glyph_cache_t
*cache
,
654 const pixman_glyph_t
*glyphs
)
656 pixman_image_t
*mask
;
658 if (!(mask
= pixman_image_create_bits (mask_format
, width
, height
, NULL
, -1)))
661 if (PIXMAN_FORMAT_A (mask_format
) != 0 &&
662 PIXMAN_FORMAT_RGB (mask_format
) != 0)
664 pixman_image_set_component_alpha (mask
, TRUE
);
667 add_glyphs (cache
, mask
, - mask_x
, - mask_y
, n_glyphs
, glyphs
);
669 pixman_image_composite32 (op
, src
, mask
, dest
,
675 pixman_image_unref (mask
);