1 /* 2 * Copyright 2010, 2012, Soren Sandmann <sandmann (at) 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 (at) 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 (®ion); 423 if (!_pixman_compute_composite_region32 ( 424 ®ion, 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 (®ion, &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 (®ion); 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 } 671
