Add qemu 2.4.0
[kvmfornfv.git] / qemu / pixman / pixman / pixman-glyph.c
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 #if defined(__GNUC__) && !defined(__x86_64__) && !defined(__amd64__)
395 __attribute__((__force_align_arg_pointer__))
396 #endif
397 PIXMAN_EXPORT void
398 pixman_composite_glyphs_no_mask (pixman_op_t            op,
399                                  pixman_image_t        *src,
400                                  pixman_image_t        *dest,
401                                  int32_t                src_x,
402                                  int32_t                src_y,
403                                  int32_t                dest_x,
404                                  int32_t                dest_y,
405                                  pixman_glyph_cache_t  *cache,
406                                  int                    n_glyphs,
407                                  const pixman_glyph_t  *glyphs)
408 {
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;
413     uint32_t dest_flags;
414     pixman_composite_func_t func = NULL;
415     pixman_implementation_t *implementation = NULL;
416     pixman_composite_info_t info;
417     int i;
418
419     _pixman_image_validate (src);
420     _pixman_image_validate (dest);
421     
422     dest_format = dest->common.extended_format_code;
423     dest_flags = dest->common.flags;
424     
425     pixman_region32_init (&region);
426     if (!_pixman_compute_composite_region32 (
427             &region,
428             src, NULL, dest,
429             src_x - dest_x, src_y - dest_y, 0, 0, 0, 0,
430             dest->bits.width, dest->bits.height))
431     {
432         goto out;
433     }
434
435     info.op = op;
436     info.src_image = src;
437     info.dest_image = dest;
438     info.src_flags = src->common.flags;
439     info.dest_flags = dest->common.flags;
440
441     for (i = 0; i < n_glyphs; ++i)
442     {
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;
449         int n;
450
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;
455         
456         pbox = pixman_region32_rectangles (&region, &n);
457         
458         info.mask_image = glyph_img;
459
460         while (n--)
461         {
462             if (box32_intersect (&composite_box, pbox, &glyph_box))
463             {
464                 if (glyph_img->common.extended_format_code != glyph_format      ||
465                     glyph_img->common.flags != glyph_flags)
466                 {
467                     glyph_format = glyph_img->common.extended_format_code;
468                     glyph_flags = glyph_img->common.flags;
469
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);
476                 }
477
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;
486
487                 info.mask_flags = glyph_flags;
488
489                 func (implementation, &info);
490             }
491
492             pbox++;
493         }
494         pixman_list_move_to_front (&cache->mru, &glyph->mru_link);
495     }
496
497 out:
498     pixman_region32_fini (&region);
499 }
500
501 static void
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)
506 {
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;
512     uint32_t dest_flags;
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;
517     int i;
518
519     _pixman_image_validate (dest);
520
521     dest_format = dest->common.extended_format_code;
522     dest_flags = dest->common.flags;
523
524     info.op = PIXMAN_OP_ADD;
525     info.dest_image = dest;
526     info.src_x = 0;
527     info.src_y = 0;
528     info.dest_flags = dest_flags;
529
530     dest_box.x1 = 0;
531     dest_box.y1 = 0;
532     dest_box.x2 = dest->bits.width;
533     dest_box.y2 = dest->bits.height;
534
535     for (i = 0; i < n_glyphs; ++i)
536     {
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;
541
542         if (glyph_img->common.extended_format_code != glyph_format      ||
543             glyph_img->common.flags != glyph_flags)
544         {
545             pixman_format_code_t src_format, mask_format;
546
547             glyph_format = glyph_img->common.extended_format_code;
548             glyph_flags = glyph_img->common.flags;
549
550             if (glyph_format == dest->bits.format)
551             {
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;
557                 white_src = FALSE;
558             }
559             else
560             {
561                 if (!white_img)
562                 {
563                     static const pixman_color_t white = { 0xffff, 0xffff, 0xffff, 0xffff };
564
565                     if (!(white_img = pixman_image_create_solid_fill (&white)))
566                         goto out;
567
568                     _pixman_image_validate (white_img);
569                 }
570
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;
576                 white_src = TRUE;
577             }
578
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);
585         }
586
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;
591         
592         if (box32_intersect (&composite_box, &glyph_box, &dest_box))
593         {
594             int src_x = composite_box.x1 - glyph_box.x1;
595             int src_y = composite_box.y1 - glyph_box.y1;
596
597             if (white_src)
598                 info.mask_image = glyph_img;
599             else
600                 info.src_image = glyph_img;
601
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;
608
609             func (implementation, &info);
610
611             pixman_list_move_to_front (&cache->mru, &glyph->mru_link);
612         }
613     }
614
615 out:
616     if (white_img)
617         pixman_image_unref (white_img);
618 }
619
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.
623  *
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 
627  *
628  *       (dest_x, dest_y, dst_x + width, dst_y + height)
629  *
630  * rectangle.
631  *
632  * TODO:
633  *   - Trim the mask to the destination clip/image?
634  *   - Trim composite region based on sources, when the op ignores 0s.
635  */
636 #if defined(__GNUC__) && !defined(__x86_64__) && !defined(__amd64__)
637 __attribute__((__force_align_arg_pointer__))
638 #endif
639 PIXMAN_EXPORT void
640 pixman_composite_glyphs (pixman_op_t            op,
641                          pixman_image_t        *src,
642                          pixman_image_t        *dest,
643                          pixman_format_code_t   mask_format,
644                          int32_t                src_x,
645                          int32_t                src_y,
646                          int32_t                mask_x,
647                          int32_t                mask_y,
648                          int32_t                dest_x,
649                          int32_t                dest_y,
650                          int32_t                width,
651                          int32_t                height,
652                          pixman_glyph_cache_t  *cache,
653                          int                    n_glyphs,
654                          const pixman_glyph_t  *glyphs)
655 {
656     pixman_image_t *mask;
657
658     if (!(mask = pixman_image_create_bits (mask_format, width, height, NULL, -1)))
659         return;
660
661     if (PIXMAN_FORMAT_A   (mask_format) != 0 &&
662         PIXMAN_FORMAT_RGB (mask_format) != 0)
663     {
664         pixman_image_set_component_alpha (mask, TRUE);
665     }
666
667     add_glyphs (cache, mask, - mask_x, - mask_y, n_glyphs, glyphs);
668
669     pixman_image_composite32 (op, src, mask, dest,
670                               src_x, src_y,
671                               0, 0,
672                               dest_x, dest_y,
673                               width, height);
674
675     pixman_image_unref (mask);
676 }