The Tor Browser / file comparison

comparison: gfx/cairo/libpixman/src/pixman-glyph.c

gfx/cairo/libpixman/src/pixman-glyph.c

changeset 0
6474c204b198
equal deleted inserted replaced
-1:000000000000 0:02317e193051
1 /*
2 * Copyright 2010, 2012, Soren Sandmann <sandmann@cs.au.dk>
3 * Copyright 2010, 2011, 2012, Red Hat, Inc
4 *
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:
11 *
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
14 * Software.
15 *
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.
23 *
24 * Author: Soren Sandmann <sandmann@cs.au.dk>
25 */
26
27 #ifdef HAVE_CONFIG_H
28 #include <config.h>
29 #endif
30 #include "pixman-private.h"
31
32 #include <stdlib.h>
33
34 typedef struct glyph_metrics_t glyph_metrics_t;
35 typedef struct glyph_t glyph_t;
36
37 #define TOMBSTONE ((glyph_t *)0x1)
38
39 /* XXX: These numbers are arbitrary---we've never done any measurements.
40 */
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)
45
46 struct glyph_t
47 {
48 void * font_key;
49 void * glyph_key;
50 int origin_x;
51 int origin_y;
52 pixman_image_t * image;
53 pixman_link_t mru_link;
54 };
55
56 struct pixman_glyph_cache_t
57 {
58 int n_glyphs;
59 int n_tombstones;
60 int freeze_count;
61 pixman_list_t mru;
62 glyph_t * glyphs[HASH_SIZE];
63 };
64
65 static void
66 free_glyph (glyph_t *glyph)
67 {
68 pixman_list_unlink (&glyph->mru_link);
69 pixman_image_unref (glyph->image);
70 free (glyph);
71 }
72
73 static unsigned int
74 hash (const void *font_key, const void *glyph_key)
75 {
76 size_t key = (size_t)font_key + (size_t)glyph_key;
77
78 /* This hash function is based on one found on Thomas Wang's
79 * web page at
80 *
81 * http://www.concentric.net/~Ttwang/tech/inthash.htm
82 *
83 */
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);
90
91 return key;
92 }
93
94 static glyph_t *
95 lookup_glyph (pixman_glyph_cache_t *cache,
96 void *font_key,
97 void *glyph_key)
98 {
99 unsigned idx;
100 glyph_t *g;
101
102 idx = hash (font_key, glyph_key);
103 while ((g = cache->glyphs[idx++ & HASH_MASK]))
104 {
105 if (g != TOMBSTONE &&
106 g->font_key == font_key &&
107 g->glyph_key == glyph_key)
108 {
109 return g;
110 }
111 }
112
113 return NULL;
114 }
115
116 static void
117 insert_glyph (pixman_glyph_cache_t *cache,
118 glyph_t *glyph)
119 {
120 unsigned idx;
121 glyph_t **loc;
122
123 idx = hash (glyph->font_key, glyph->glyph_key);
124
125 /* Note: we assume that there is room in the table. If there isn't,
126 * this will be an infinite loop.
127 */
128 do
129 {
130 loc = &cache->glyphs[idx++ & HASH_MASK];
131 } while (*loc && *loc != TOMBSTONE);
132
133 if (*loc == TOMBSTONE)
134 cache->n_tombstones--;
135 cache->n_glyphs++;
136
137 *loc = glyph;
138 }
139
140 static void
141 remove_glyph (pixman_glyph_cache_t *cache,
142 glyph_t *glyph)
143 {
144 unsigned idx;
145
146 idx = hash (glyph->font_key, glyph->glyph_key);
147 while (cache->glyphs[idx & HASH_MASK] != glyph)
148 idx++;
149
150 cache->glyphs[idx & HASH_MASK] = TOMBSTONE;
151 cache->n_tombstones++;
152 cache->n_glyphs--;
153
154 /* Eliminate tombstones if possible */
155 if (cache->glyphs[(idx + 1) & HASH_MASK] == NULL)
156 {
157 while (cache->glyphs[idx & HASH_MASK] == TOMBSTONE)
158 {
159 cache->glyphs[idx & HASH_MASK] = NULL;
160 cache->n_tombstones--;
161 idx--;
162 }
163 }
164 }
165
166 static void
167 clear_table (pixman_glyph_cache_t *cache)
168 {
169 int i;
170
171 for (i = 0; i < HASH_SIZE; ++i)
172 {
173 glyph_t *glyph = cache->glyphs[i];
174
175 if (glyph && glyph != TOMBSTONE)
176 free_glyph (glyph);
177
178 cache->glyphs[i] = NULL;
179 }
180
181 cache->n_glyphs = 0;
182 cache->n_tombstones = 0;
183 }
184
185 PIXMAN_EXPORT pixman_glyph_cache_t *
186 pixman_glyph_cache_create (void)
187 {
188 pixman_glyph_cache_t *cache;
189
190 if (!(cache = malloc (sizeof *cache)))
191 return NULL;
192
193 memset (cache->glyphs, 0, sizeof (cache->glyphs));
194 cache->n_glyphs = 0;
195 cache->n_tombstones = 0;
196 cache->freeze_count = 0;
197
198 pixman_list_init (&cache->mru);
199
200 return cache;
201 }
202
203 PIXMAN_EXPORT void
204 pixman_glyph_cache_destroy (pixman_glyph_cache_t *cache)
205 {
206 return_if_fail (cache->freeze_count == 0);
207
208 clear_table (cache);
209
210 free (cache);
211 }
212
213 PIXMAN_EXPORT void
214 pixman_glyph_cache_freeze (pixman_glyph_cache_t *cache)
215 {
216 cache->freeze_count++;
217 }
218
219 PIXMAN_EXPORT void
220 pixman_glyph_cache_thaw (pixman_glyph_cache_t *cache)
221 {
222 if (--cache->freeze_count == 0 &&
223 cache->n_glyphs + cache->n_tombstones > N_GLYPHS_HIGH_WATER)
224 {
225 if (cache->n_tombstones > N_GLYPHS_HIGH_WATER)
226 {
227 /* More than half the entries are
228 * tombstones. Just dump the whole table.
229 */
230 clear_table (cache);
231 }
232
233 while (cache->n_glyphs > N_GLYPHS_LOW_WATER)
234 {
235 glyph_t *glyph = CONTAINER_OF (glyph_t, mru_link, cache->mru.tail);
236
237 remove_glyph (cache, glyph);
238 free_glyph (glyph);
239 }
240 }
241 }
242
243 PIXMAN_EXPORT const void *
244 pixman_glyph_cache_lookup (pixman_glyph_cache_t *cache,
245 void *font_key,
246 void *glyph_key)
247 {
248 return lookup_glyph (cache, font_key, glyph_key);
249 }
250
251 PIXMAN_EXPORT const void *
252 pixman_glyph_cache_insert (pixman_glyph_cache_t *cache,
253 void *font_key,
254 void *glyph_key,
255 int origin_x,
256 int origin_y,
257 pixman_image_t *image)
258 {
259 glyph_t *glyph;
260 int32_t width, height;
261
262 return_val_if_fail (cache->freeze_count > 0, NULL);
263 return_val_if_fail (image->type == BITS, NULL);
264
265 width = image->bits.width;
266 height = image->bits.height;
267
268 if (cache->n_glyphs >= HASH_SIZE)
269 return NULL;
270
271 if (!(glyph = malloc (sizeof *glyph)))
272 return NULL;
273
274 glyph->font_key = font_key;
275 glyph->glyph_key = glyph_key;
276 glyph->origin_x = origin_x;
277 glyph->origin_y = origin_y;
278
279 if (!(glyph->image = pixman_image_create_bits (
280 image->bits.format, width, height, NULL, -1)))
281 {
282 free (glyph);
283 return NULL;
284 }
285
286 pixman_image_composite32 (PIXMAN_OP_SRC,
287 image, NULL, glyph->image, 0, 0, 0, 0, 0, 0,
288 width, height);
289
290 if (PIXMAN_FORMAT_A (glyph->image->bits.format) != 0 &&
291 PIXMAN_FORMAT_RGB (glyph->image->bits.format) != 0)
292 {
293 pixman_image_set_component_alpha (glyph->image, TRUE);
294 }
295
296 pixman_list_prepend (&cache->mru, &glyph->mru_link);
297
298 _pixman_image_validate (glyph->image);
299 insert_glyph (cache, glyph);
300
301 return glyph;
302 }
303
304 PIXMAN_EXPORT void
305 pixman_glyph_cache_remove (pixman_glyph_cache_t *cache,
306 void *font_key,
307 void *glyph_key)
308 {
309 glyph_t *glyph;
310
311 if ((glyph = lookup_glyph (cache, font_key, glyph_key)))
312 {
313 remove_glyph (cache, glyph);
314
315 free_glyph (glyph);
316 }
317 }
318
319 PIXMAN_EXPORT void
320 pixman_glyph_get_extents (pixman_glyph_cache_t *cache,
321 int n_glyphs,
322 pixman_glyph_t *glyphs,
323 pixman_box32_t *extents)
324 {
325 int i;
326
327 extents->x1 = extents->y1 = INT32_MAX;
328 extents->x2 = extents->y2 = INT32_MIN;
329
330 for (i = 0; i < n_glyphs; ++i)
331 {
332 glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
333 int x1, y1, x2, y2;
334
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;
339
340 if (x1 < extents->x1)
341 extents->x1 = x1;
342 if (y1 < extents->y1)
343 extents->y1 = y1;
344 if (x2 > extents->x2)
345 extents->x2 = x2;
346 if (y2 > extents->y2)
347 extents->y2 = y2;
348 }
349 }
350
351 /* This function returns a format that is suitable for use as a mask for the
352 * set of glyphs in question.
353 */
354 PIXMAN_EXPORT pixman_format_code_t
355 pixman_glyph_get_mask_format (pixman_glyph_cache_t *cache,
356 int n_glyphs,
357 const pixman_glyph_t *glyphs)
358 {
359 pixman_format_code_t format = PIXMAN_a1;
360 int i;
361
362 for (i = 0; i < n_glyphs; ++i)
363 {
364 const glyph_t *glyph = glyphs[i].glyph;
365 pixman_format_code_t glyph_format = glyph->image->bits.format;
366
367 if (PIXMAN_FORMAT_TYPE (glyph_format) == PIXMAN_TYPE_A)
368 {
369 if (PIXMAN_FORMAT_A (glyph_format) > PIXMAN_FORMAT_A (format))
370 format = glyph_format;
371 }
372 else
373 {
374 return PIXMAN_a8r8g8b8;
375 }
376 }
377
378 return format;
379 }
380
381 static pixman_bool_t
382 box32_intersect (pixman_box32_t *dest,
383 const pixman_box32_t *box1,
384 const pixman_box32_t *box2)
385 {
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);
390
391 return dest->x2 > dest->x1 && dest->y2 > dest->y1;
392 }
393
394 PIXMAN_EXPORT void
395 pixman_composite_glyphs_no_mask (pixman_op_t op,
396 pixman_image_t *src,
397 pixman_image_t *dest,
398 int32_t src_x,
399 int32_t src_y,
400 int32_t dest_x,
401 int32_t dest_y,
402 pixman_glyph_cache_t *cache,
403 int n_glyphs,
404 const pixman_glyph_t *glyphs)
405 {
406 pixman_region32_t region;
407 pixman_format_code_t glyph_format = PIXMAN_null;
408 uint32_t glyph_flags = 0;
409 pixman_format_code_t dest_format;
410 uint32_t dest_flags;
411 pixman_composite_func_t func = NULL;
412 pixman_implementation_t *implementation = NULL;
413 pixman_composite_info_t info;
414 int i;
415
416 _pixman_image_validate (src);
417 _pixman_image_validate (dest);
418
419 dest_format = dest->common.extended_format_code;
420 dest_flags = dest->common.flags;
421
422 pixman_region32_init (&region);
423 if (!_pixman_compute_composite_region32 (
424 &region,
425 src, NULL, dest,
426 src_x - dest_x, src_y - dest_y, 0, 0, 0, 0,
427 dest->bits.width, dest->bits.height))
428 {
429 goto out;
430 }
431
432 info.op = op;
433 info.src_image = src;
434 info.dest_image = dest;
435 info.src_flags = src->common.flags;
436 info.dest_flags = dest->common.flags;
437
438 for (i = 0; i < n_glyphs; ++i)
439 {
440 glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
441 pixman_image_t *glyph_img = glyph->image;
442 pixman_box32_t glyph_box;
443 pixman_box32_t *pbox;
444 uint32_t extra = FAST_PATH_SAMPLES_COVER_CLIP_NEAREST;
445 pixman_box32_t composite_box;
446 int n;
447
448 glyph_box.x1 = dest_x + glyphs[i].x - glyph->origin_x;
449 glyph_box.y1 = dest_y + glyphs[i].y - glyph->origin_y;
450 glyph_box.x2 = glyph_box.x1 + glyph->image->bits.width;
451 glyph_box.y2 = glyph_box.y1 + glyph->image->bits.height;
452
453 pbox = pixman_region32_rectangles (&region, &n);
454
455 info.mask_image = glyph_img;
456
457 while (n--)
458 {
459 if (box32_intersect (&composite_box, pbox, &glyph_box))
460 {
461 if (glyph_img->common.extended_format_code != glyph_format ||
462 glyph_img->common.flags != glyph_flags)
463 {
464 glyph_format = glyph_img->common.extended_format_code;
465 glyph_flags = glyph_img->common.flags;
466
467 _pixman_implementation_lookup_composite (
468 get_implementation(), op,
469 src->common.extended_format_code, src->common.flags,
470 glyph_format, glyph_flags | extra,
471 dest_format, dest_flags,
472 &implementation, &func);
473 }
474
475 info.src_x = src_x + composite_box.x1 - dest_x;
476 info.src_y = src_y + composite_box.y1 - dest_y;
477 info.mask_x = composite_box.x1 - (dest_x + glyphs[i].x - glyph->origin_x);
478 info.mask_y = composite_box.y1 - (dest_y + glyphs[i].y - glyph->origin_y);
479 info.dest_x = composite_box.x1;
480 info.dest_y = composite_box.y1;
481 info.width = composite_box.x2 - composite_box.x1;
482 info.height = composite_box.y2 - composite_box.y1;
483
484 info.mask_flags = glyph_flags;
485
486 func (implementation, &info);
487 }
488
489 pbox++;
490 }
491 pixman_list_move_to_front (&cache->mru, &glyph->mru_link);
492 }
493
494 out:
495 pixman_region32_fini (&region);
496 }
497
498 static void
499 add_glyphs (pixman_glyph_cache_t *cache,
500 pixman_image_t *dest,
501 int off_x, int off_y,
502 int n_glyphs, const pixman_glyph_t *glyphs)
503 {
504 pixman_format_code_t glyph_format = PIXMAN_null;
505 uint32_t glyph_flags = 0;
506 pixman_composite_func_t func = NULL;
507 pixman_implementation_t *implementation = NULL;
508 pixman_format_code_t dest_format;
509 uint32_t dest_flags;
510 pixman_box32_t dest_box;
511 pixman_composite_info_t info;
512 pixman_image_t *white_img = NULL;
513 pixman_bool_t white_src = FALSE;
514 int i;
515
516 _pixman_image_validate (dest);
517
518 dest_format = dest->common.extended_format_code;
519 dest_flags = dest->common.flags;
520
521 info.op = PIXMAN_OP_ADD;
522 info.dest_image = dest;
523 info.src_x = 0;
524 info.src_y = 0;
525 info.dest_flags = dest_flags;
526
527 dest_box.x1 = 0;
528 dest_box.y1 = 0;
529 dest_box.x2 = dest->bits.width;
530 dest_box.y2 = dest->bits.height;
531
532 for (i = 0; i < n_glyphs; ++i)
533 {
534 glyph_t *glyph = (glyph_t *)glyphs[i].glyph;
535 pixman_image_t *glyph_img = glyph->image;
536 pixman_box32_t glyph_box;
537 pixman_box32_t composite_box;
538
539 if (glyph_img->common.extended_format_code != glyph_format ||
540 glyph_img->common.flags != glyph_flags)
541 {
542 pixman_format_code_t src_format, mask_format;
543
544 glyph_format = glyph_img->common.extended_format_code;
545 glyph_flags = glyph_img->common.flags;
546
547 if (glyph_format == dest->bits.format)
548 {
549 src_format = glyph_format;
550 mask_format = PIXMAN_null;
551 info.src_flags = glyph_flags | FAST_PATH_SAMPLES_COVER_CLIP_NEAREST;
552 info.mask_flags = FAST_PATH_IS_OPAQUE;
553 info.mask_image = NULL;
554 white_src = FALSE;
555 }
556 else
557 {
558 if (!white_img)
559 {
560 static const pixman_color_t white = { 0xffff, 0xffff, 0xffff, 0xffff };
561
562 if (!(white_img = pixman_image_create_solid_fill (&white)))
563 goto out;
564
565 _pixman_image_validate (white_img);
566 }
567
568 src_format = PIXMAN_solid;
569 mask_format = glyph_format;
570 info.src_flags = white_img->common.flags;
571 info.mask_flags = glyph_flags | FAST_PATH_SAMPLES_COVER_CLIP_NEAREST;
572 info.src_image = white_img;
573 white_src = TRUE;
574 }
575
576 _pixman_implementation_lookup_composite (
577 get_implementation(), PIXMAN_OP_ADD,
578 src_format, info.src_flags,
579 mask_format, info.mask_flags,
580 dest_format, dest_flags,
581 &implementation, &func);
582 }
583
584 glyph_box.x1 = glyphs[i].x - glyph->origin_x + off_x;
585 glyph_box.y1 = glyphs[i].y - glyph->origin_y + off_y;
586 glyph_box.x2 = glyph_box.x1 + glyph->image->bits.width;
587 glyph_box.y2 = glyph_box.y1 + glyph->image->bits.height;
588
589 if (box32_intersect (&composite_box, &glyph_box, &dest_box))
590 {
591 int src_x = composite_box.x1 - glyph_box.x1;
592 int src_y = composite_box.y1 - glyph_box.y1;
593
594 if (white_src)
595 info.mask_image = glyph_img;
596 else
597 info.src_image = glyph_img;
598
599 info.mask_x = info.src_x = src_x;
600 info.mask_y = info.src_y = src_y;
601 info.dest_x = composite_box.x1;
602 info.dest_y = composite_box.y1;
603 info.width = composite_box.x2 - composite_box.x1;
604 info.height = composite_box.y2 - composite_box.y1;
605
606 func (implementation, &info);
607
608 pixman_list_move_to_front (&cache->mru, &glyph->mru_link);
609 }
610 }
611
612 out:
613 if (white_img)
614 pixman_image_unref (white_img);
615 }
616
617 /* Conceptually, for each glyph, (white IN glyph) is PIXMAN_OP_ADDed to an
618 * infinitely big mask image at the position such that the glyph origin point
619 * is positioned at the (glyphs[i].x, glyphs[i].y) point.
620 *
621 * Then (mask_x, mask_y) in the infinite mask and (src_x, src_y) in the source
622 * image are both aligned with (dest_x, dest_y) in the destination image. Then
623 * these three images are composited within the
624 *
625 * (dest_x, dest_y, dst_x + width, dst_y + height)
626 *
627 * rectangle.
628 *
629 * TODO:
630 * - Trim the mask to the destination clip/image?
631 * - Trim composite region based on sources, when the op ignores 0s.
632 */
633 PIXMAN_EXPORT void
634 pixman_composite_glyphs (pixman_op_t op,
635 pixman_image_t *src,
636 pixman_image_t *dest,
637 pixman_format_code_t mask_format,
638 int32_t src_x,
639 int32_t src_y,
640 int32_t mask_x,
641 int32_t mask_y,
642 int32_t dest_x,
643 int32_t dest_y,
644 int32_t width,
645 int32_t height,
646 pixman_glyph_cache_t *cache,
647 int n_glyphs,
648 const pixman_glyph_t *glyphs)
649 {
650 pixman_image_t *mask;
651
652 if (!(mask = pixman_image_create_bits (mask_format, width, height, NULL, -1)))
653 return;
654
655 if (PIXMAN_FORMAT_A (mask_format) != 0 &&
656 PIXMAN_FORMAT_RGB (mask_format) != 0)
657 {
658 pixman_image_set_component_alpha (mask, TRUE);
659 }
660
661 add_glyphs (cache, mask, - mask_x, - mask_y, n_glyphs, glyphs);
662
663 pixman_image_composite32 (op, src, mask, dest,
664 src_x, src_y,
665 0, 0,
666 dest_x, dest_y,
667 width, height);
668
669 pixman_image_unref (mask);
670 }

Mercurial Repository: The Tor Browser

Europalab SCM Repository Server

mercurial