qemu/pixman/pixman/pixman-trap.c

   1 /*
   2  * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
   3  * Copyright © 2004 Keith Packard
   4  *
   5  * Permission to use, copy, modify, distribute, and sell this software and its
   6  * documentation for any purpose is hereby granted without fee, provided that
   7  * the above copyright notice appear in all copies and that both that
   8  * copyright notice and this permission notice appear in supporting
   9  * documentation, and that the name of Keith Packard not be used in
  10  * advertising or publicity pertaining to distribution of the software without
  11  * specific, written prior permission.  Keith Packard makes no
  12  * representations about the suitability of this software for any purpose.  It
  13  * is provided "as is" without express or implied warranty.
  14  *
  15  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  17  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  19  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  20  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  21  * PERFORMANCE OF THIS SOFTWARE.
  22  */
  23
  24 #ifdef HAVE_CONFIG_H
  25 #include <config.h>
  26 #endif
  27
  28 #include <stdio.h>
  29 #include <stdlib.h>
  30 #include "pixman-private.h"
  31
  32 /*
  33  * Compute the smallest value greater than or equal to y which is on a
  34  * grid row.
  35  */
  36
  37 PIXMAN_EXPORT pixman_fixed_t
  38 pixman_sample_ceil_y (pixman_fixed_t y, int n)
  39 {
  40     pixman_fixed_t f = pixman_fixed_frac (y);
  41     pixman_fixed_t i = pixman_fixed_floor (y);
  42
  43     f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
  44         Y_FRAC_FIRST (n);
  45
  46     if (f > Y_FRAC_LAST (n))
  47     {
  48         if (pixman_fixed_to_int (i) == 0x7fff)
  49         {
  50             f = 0xffff; /* saturate */
  51         }
  52         else
  53         {
  54             f = Y_FRAC_FIRST (n);
  55             i += pixman_fixed_1;
  56         }
  57     }
  58     return (i | f);
  59 }
  60
  61 /*
  62  * Compute the largest value strictly less than y which is on a
  63  * grid row.
  64  */
  65 PIXMAN_EXPORT pixman_fixed_t
  66 pixman_sample_floor_y (pixman_fixed_t y,
  67                        int            n)
  68 {
  69     pixman_fixed_t f = pixman_fixed_frac (y);
  70     pixman_fixed_t i = pixman_fixed_floor (y);
  71
  72     f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
  73         Y_FRAC_FIRST (n);
  74
  75     if (f < Y_FRAC_FIRST (n))
  76     {
  77         if (pixman_fixed_to_int (i) == 0x8000)
  78         {
  79             f = 0; /* saturate */
  80         }
  81         else
  82         {
  83             f = Y_FRAC_LAST (n);
  84             i -= pixman_fixed_1;
  85         }
  86     }
  87     return (i | f);
  88 }
  89
  90 /*
  91  * Step an edge by any amount (including negative values)
  92  */
  93 PIXMAN_EXPORT void
  94 pixman_edge_step (pixman_edge_t *e,
  95                   int            n)
  96 {
  97     pixman_fixed_48_16_t ne;
  98
  99     e->x += n * e->stepx;
 100
 101     ne = e->e + n * (pixman_fixed_48_16_t) e->dx;
 102
 103     if (n >= 0)
 104     {
 105         if (ne > 0)
 106         {
 107             int nx = (ne + e->dy - 1) / e->dy;
 108             e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;
 109             e->x += nx * e->signdx;
 110         }
 111     }
 112     else
 113     {
 114         if (ne <= -e->dy)
 115         {
 116             int nx = (-ne) / e->dy;
 117             e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;
 118             e->x -= nx * e->signdx;
 119         }
 120     }
 121 }
 122
 123 /*
 124  * A private routine to initialize the multi-step
 125  * elements of an edge structure
 126  */
 127 static void
 128 _pixman_edge_multi_init (pixman_edge_t * e,
 129                          int             n,
 130                          pixman_fixed_t *stepx_p,
 131                          pixman_fixed_t *dx_p)
 132 {
 133     pixman_fixed_t stepx;
 134     pixman_fixed_48_16_t ne;
 135
 136     ne = n * (pixman_fixed_48_16_t) e->dx;
 137     stepx = n * e->stepx;
 138
 139     if (ne > 0)
 140     {
 141         int nx = ne / e->dy;
 142         ne -= nx * (pixman_fixed_48_16_t)e->dy;
 143         stepx += nx * e->signdx;
 144     }
 145
 146     *dx_p = ne;
 147     *stepx_p = stepx;
 148 }
 149
 150 /*
 151  * Initialize one edge structure given the line endpoints and a
 152  * starting y value
 153  */
 154 PIXMAN_EXPORT void
 155 pixman_edge_init (pixman_edge_t *e,
 156                   int            n,
 157                   pixman_fixed_t y_start,
 158                   pixman_fixed_t x_top,
 159                   pixman_fixed_t y_top,
 160                   pixman_fixed_t x_bot,
 161                   pixman_fixed_t y_bot)
 162 {
 163     pixman_fixed_t dx, dy;
 164
 165     e->x = x_top;
 166     e->e = 0;
 167     dx = x_bot - x_top;
 168     dy = y_bot - y_top;
 169     e->dy = dy;
 170     e->dx = 0;
 171
 172     if (dy)
 173     {
 174         if (dx >= 0)
 175         {
 176             e->signdx = 1;
 177             e->stepx = dx / dy;
 178             e->dx = dx % dy;
 179             e->e = -dy;
 180         }
 181         else
 182         {
 183             e->signdx = -1;
 184             e->stepx = -(-dx / dy);
 185             e->dx = -dx % dy;
 186             e->e = 0;
 187         }
 188
 189         _pixman_edge_multi_init (e, STEP_Y_SMALL (n),
 190                                  &e->stepx_small, &e->dx_small);
 191
 192         _pixman_edge_multi_init (e, STEP_Y_BIG (n),
 193                                  &e->stepx_big, &e->dx_big);
 194     }
 195     pixman_edge_step (e, y_start - y_top);
 196 }
 197
 198 /*
 199  * Initialize one edge structure given a line, starting y value
 200  * and a pixel offset for the line
 201  */
 202 PIXMAN_EXPORT void
 203 pixman_line_fixed_edge_init (pixman_edge_t *            e,
 204                              int                        n,
 205                              pixman_fixed_t             y,
 206                              const pixman_line_fixed_t *line,
 207                              int                        x_off,
 208                              int                        y_off)
 209 {
 210     pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);
 211     pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);
 212     const pixman_point_fixed_t *top, *bot;
 213
 214     if (line->p1.y <= line->p2.y)
 215     {
 216         top = &line->p1;
 217         bot = &line->p2;
 218     }
 219     else
 220     {
 221         top = &line->p2;
 222         bot = &line->p1;
 223     }
 224
 225     pixman_edge_init (e, n, y,
 226                       top->x + x_off_fixed,
 227                       top->y + y_off_fixed,
 228                       bot->x + x_off_fixed,
 229                       bot->y + y_off_fixed);
 230 }
 231
 232 PIXMAN_EXPORT void
 233 pixman_add_traps (pixman_image_t *     image,
 234                   int16_t              x_off,
 235                   int16_t              y_off,
 236                   int                  ntrap,
 237                   const pixman_trap_t *traps)
 238 {
 239     int bpp;
 240     int height;
 241
 242     pixman_fixed_t x_off_fixed;
 243     pixman_fixed_t y_off_fixed;
 244     pixman_edge_t l, r;
 245     pixman_fixed_t t, b;
 246
 247     _pixman_image_validate (image);
 248
 249     height = image->bits.height;
 250     bpp = PIXMAN_FORMAT_BPP (image->bits.format);
 251
 252     x_off_fixed = pixman_int_to_fixed (x_off);
 253     y_off_fixed = pixman_int_to_fixed (y_off);
 254
 255     while (ntrap--)
 256     {
 257         t = traps->top.y + y_off_fixed;
 258         if (t < 0)
 259             t = 0;
 260         t = pixman_sample_ceil_y (t, bpp);
 261
 262         b = traps->bot.y + y_off_fixed;
 263         if (pixman_fixed_to_int (b) >= height)
 264             b = pixman_int_to_fixed (height) - 1;
 265         b = pixman_sample_floor_y (b, bpp);
 266
 267         if (b >= t)
 268         {
 269             /* initialize edge walkers */
 270             pixman_edge_init (&l, bpp, t,
 271                               traps->top.l + x_off_fixed,
 272                               traps->top.y + y_off_fixed,
 273                               traps->bot.l + x_off_fixed,
 274                               traps->bot.y + y_off_fixed);
 275
 276             pixman_edge_init (&r, bpp, t,
 277                               traps->top.r + x_off_fixed,
 278                               traps->top.y + y_off_fixed,
 279                               traps->bot.r + x_off_fixed,
 280                               traps->bot.y + y_off_fixed);
 281
 282             pixman_rasterize_edges (image, &l, &r, t, b);
 283         }
 284
 285         traps++;
 286     }
 287 }
 288
 289 #if 0
 290 static void
 291 dump_image (pixman_image_t *image,
 292             const char *    title)
 293 {
 294     int i, j;
 295
 296     if (!image->type == BITS)
 297         printf ("%s is not a regular image\n", title);
 298
 299     if (!image->bits.format == PIXMAN_a8)
 300         printf ("%s is not an alpha mask\n", title);
 301
 302     printf ("\n\n\n%s: \n", title);
 303
 304     for (i = 0; i < image->bits.height; ++i)
 305     {
 306         uint8_t *line =
 307             (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);
 308
 309         for (j = 0; j < image->bits.width; ++j)
 310             printf ("%c", line[j] ? '#' : ' ');
 311
 312         printf ("\n");
 313     }
 314 }
 315 #endif
 316
 317 PIXMAN_EXPORT void
 318 pixman_add_trapezoids (pixman_image_t *          image,
 319                        int16_t                   x_off,
 320                        int                       y_off,
 321                        int                       ntraps,
 322                        const pixman_trapezoid_t *traps)
 323 {
 324     int i;
 325
 326 #if 0
 327     dump_image (image, "before");
 328 #endif
 329
 330     for (i = 0; i < ntraps; ++i)
 331     {
 332         const pixman_trapezoid_t *trap = &(traps[i]);
 333
 334         if (!pixman_trapezoid_valid (trap))
 335             continue;
 336
 337         pixman_rasterize_trapezoid (image, trap, x_off, y_off);
 338     }
 339
 340 #if 0
 341     dump_image (image, "after");
 342 #endif
 343 }
 344
 345 PIXMAN_EXPORT void
 346 pixman_rasterize_trapezoid (pixman_image_t *          image,
 347                             const pixman_trapezoid_t *trap,
 348                             int                       x_off,
 349                             int                       y_off)
 350 {
 351     int bpp;
 352     int height;
 353
 354     pixman_fixed_t y_off_fixed;
 355     pixman_edge_t l, r;
 356     pixman_fixed_t t, b;
 357
 358     return_if_fail (image->type == BITS);
 359
 360     _pixman_image_validate (image);
 361
 362     if (!pixman_trapezoid_valid (trap))
 363         return;
 364
 365     height = image->bits.height;
 366     bpp = PIXMAN_FORMAT_BPP (image->bits.format);
 367
 368     y_off_fixed = pixman_int_to_fixed (y_off);
 369
 370     t = trap->top + y_off_fixed;
 371     if (t < 0)
 372         t = 0;
 373     t = pixman_sample_ceil_y (t, bpp);
 374
 375     b = trap->bottom + y_off_fixed;
 376     if (pixman_fixed_to_int (b) >= height)
 377         b = pixman_int_to_fixed (height) - 1;
 378     b = pixman_sample_floor_y (b, bpp);
 379
 380     if (b >= t)
 381     {
 382         /* initialize edge walkers */
 383         pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);
 384         pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);
 385
 386         pixman_rasterize_edges (image, &l, &r, t, b);
 387     }
 388 }
 389
 390 static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] =
 391 {
 392     FALSE,      /* Clear                0                       0    */
 393     FALSE,      /* Src                  1                       0    */
 394     TRUE,       /* Dst                  0                       1    */
 395     TRUE,       /* Over                 1                       1-Aa */
 396     TRUE,       /* OverReverse          1-Ab                    1    */
 397     FALSE,      /* In                   Ab                      0    */
 398     FALSE,      /* InReverse            0                       Aa   */
 399     FALSE,      /* Out                  1-Ab                    0    */
 400     TRUE,       /* OutReverse           0                       1-Aa */
 401     TRUE,       /* Atop                 Ab                      1-Aa */
 402     FALSE,      /* AtopReverse          1-Ab                    Aa   */
 403     TRUE,       /* Xor                  1-Ab                    1-Aa */
 404     TRUE,       /* Add                  1                       1    */
 405 };
 406
 407 static pixman_bool_t
 408 get_trap_extents (pixman_op_t op, pixman_image_t *dest,
 409                   const pixman_trapezoid_t *traps, int n_traps,
 410                   pixman_box32_t *box)
 411 {
 412     int i;
 413
 414     /* When the operator is such that a zero source has an
 415      * effect on the underlying image, we have to
 416      * composite across the entire destination
 417      */
 418     if (!zero_src_has_no_effect [op])
 419     {
 420         box->x1 = 0;
 421         box->y1 = 0;
 422         box->x2 = dest->bits.width;
 423         box->y2 = dest->bits.height;
 424         return TRUE;
 425     }
 426
 427     box->x1 = INT32_MAX;
 428     box->y1 = INT32_MAX;
 429     box->x2 = INT32_MIN;
 430     box->y2 = INT32_MIN;
 431
 432     for (i = 0; i < n_traps; ++i)
 433     {
 434         const pixman_trapezoid_t *trap = &(traps[i]);
 435         int y1, y2;
 436
 437         if (!pixman_trapezoid_valid (trap))
 438             continue;
 439
 440         y1 = pixman_fixed_to_int (trap->top);
 441         if (y1 < box->y1)
 442             box->y1 = y1;
 443
 444         y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
 445         if (y2 > box->y2)
 446             box->y2 = y2;
 447
 448 #define EXTEND_MIN(x)                                                   \
 449         if (pixman_fixed_to_int ((x)) < box->x1)                        \
 450             box->x1 = pixman_fixed_to_int ((x));
 451 #define EXTEND_MAX(x)                                                   \
 452         if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2)    \
 453             box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));
 454
 455 #define EXTEND(x)                                                       \
 456         EXTEND_MIN(x);                                                  \
 457         EXTEND_MAX(x);
 458
 459         EXTEND(trap->left.p1.x);
 460         EXTEND(trap->left.p2.x);
 461         EXTEND(trap->right.p1.x);
 462         EXTEND(trap->right.p2.x);
 463     }
 464
 465     if (box->x1 >= box->x2 || box->y1 >= box->y2)
 466         return FALSE;
 467
 468     return TRUE;
 469 }
 470
 471 /*
 472  * pixman_composite_trapezoids()
 473  *
 474  * All the trapezoids are conceptually rendered to an infinitely big image.
 475  * The (0, 0) coordinates of this image are then aligned with the (x, y)
 476  * coordinates of the source image, and then both images are aligned with
 477  * the (x, y) coordinates of the destination. Then these three images are
 478  * composited across the entire destination.
 479  */
 480 PIXMAN_EXPORT void
 481 pixman_composite_trapezoids (pixman_op_t                op,
 482                              pixman_image_t *           src,
 483                              pixman_image_t *           dst,
 484                              pixman_format_code_t       mask_format,
 485                              int                        x_src,
 486                              int                        y_src,
 487                              int                        x_dst,
 488                              int                        y_dst,
 489                              int                        n_traps,
 490                              const pixman_trapezoid_t * traps)
 491 {
 492     int i;
 493
 494     return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);
 495
 496     if (n_traps <= 0)
 497         return;
 498
 499     _pixman_image_validate (src);
 500     _pixman_image_validate (dst);
 501
 502     if (op == PIXMAN_OP_ADD &&
 503         (src->common.flags & FAST_PATH_IS_OPAQUE)               &&
 504         (mask_format == dst->common.extended_format_code)       &&
 505         !(dst->common.have_clip_region))
 506     {
 507         for (i = 0; i < n_traps; ++i)
 508         {
 509             const pixman_trapezoid_t *trap = &(traps[i]);
 510
 511             if (!pixman_trapezoid_valid (trap))
 512                 continue;
 513
 514             pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);
 515         }
 516     }
 517     else
 518     {
 519         pixman_image_t *tmp;
 520         pixman_box32_t box;
 521         int i;
 522
 523         if (!get_trap_extents (op, dst, traps, n_traps, &box))
 524             return;
 525
 526         if (!(tmp = pixman_image_create_bits (
 527                   mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))
 528             return;
 529
 530         for (i = 0; i < n_traps; ++i)
 531         {
 532             const pixman_trapezoid_t *trap = &(traps[i]);
 533
 534             if (!pixman_trapezoid_valid (trap))
 535                 continue;
 536
 537             pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
 538         }
 539
 540         pixman_image_composite (op, src, tmp, dst,
 541                                 x_src + box.x1, y_src + box.y1,
 542                                 0, 0,
 543                                 x_dst + box.x1, y_dst + box.y1,
 544                                 box.x2 - box.x1, box.y2 - box.y1);
 545
 546         pixman_image_unref (tmp);
 547     }
 548 }
 549
 550 static int
 551 greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b)
 552 {
 553     if (a->y == b->y)
 554         return a->x > b->x;
 555     return a->y > b->y;
 556 }
 557
 558 /*
 559  * Note that the definition of this function is a bit odd because
 560  * of the X coordinate space (y increasing downwards).
 561  */
 562 static int
 563 clockwise (const pixman_point_fixed_t *ref,
 564            const pixman_point_fixed_t *a,
 565            const pixman_point_fixed_t *b)
 566 {
 567     pixman_point_fixed_t        ad, bd;
 568
 569     ad.x = a->x - ref->x;
 570     ad.y = a->y - ref->y;
 571     bd.x = b->x - ref->x;
 572     bd.y = b->y - ref->y;
 573
 574     return ((pixman_fixed_32_32_t) bd.y * ad.x -
 575             (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
 576 }
 577
 578 static void
 579 triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps)
 580 {
 581     const pixman_point_fixed_t *top, *left, *right, *tmp;
 582
 583     top = &tri->p1;
 584     left = &tri->p2;
 585     right = &tri->p3;
 586
 587     if (greater_y (top, left))
 588     {
 589         tmp = left;
 590         left = top;
 591         top = tmp;
 592     }
 593
 594     if (greater_y (top, right))
 595     {
 596         tmp = right;
 597         right = top;
 598         top = tmp;
 599     }
 600
 601     if (clockwise (top, right, left))
 602     {
 603         tmp = right;
 604         right = left;
 605         left = tmp;
 606     }
 607
 608     /*
 609      * Two cases:
 610      *
 611      *          +               +
 612      *         / \             / \
 613      *        /   \           /   \
 614      *       /     +         +     \
 615      *      /    --           --    \
 616      *     /   --               --   \
 617      *    / ---                   --- \
 618      *   +--                         --+
 619      */
 620
 621     traps->top = top->y;
 622     traps->left.p1 = *top;
 623     traps->left.p2 = *left;
 624     traps->right.p1 = *top;
 625     traps->right.p2 = *right;
 626
 627     if (right->y < left->y)
 628         traps->bottom = right->y;
 629     else
 630         traps->bottom = left->y;
 631
 632     traps++;
 633
 634     *traps = *(traps - 1);
 635
 636     if (right->y < left->y)
 637     {
 638         traps->top = right->y;
 639         traps->bottom = left->y;
 640         traps->right.p1 = *right;
 641         traps->right.p2 = *left;
 642     }
 643     else
 644     {
 645         traps->top = left->y;
 646         traps->bottom = right->y;
 647         traps->left.p1 = *left;
 648         traps->left.p2 = *right;
 649     }
 650 }
 651
 652 static pixman_trapezoid_t *
 653 convert_triangles (int n_tris, const pixman_triangle_t *tris)
 654 {
 655     pixman_trapezoid_t *traps;
 656     int i;
 657
 658     if (n_tris <= 0)
 659         return NULL;
 660
 661     traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
 662     if (!traps)
 663         return NULL;
 664
 665     for (i = 0; i < n_tris; ++i)
 666         triangle_to_trapezoids (&(tris[i]), traps + 2 * i);
 667
 668     return traps;
 669 }
 670
 671 PIXMAN_EXPORT void
 672 pixman_composite_triangles (pixman_op_t                 op,
 673                             pixman_image_t *            src,
 674                             pixman_image_t *            dst,
 675                             pixman_format_code_t        mask_format,
 676                             int                         x_src,
 677                             int                         y_src,
 678                             int                         x_dst,
 679                             int                         y_dst,
 680                             int                         n_tris,
 681                             const pixman_triangle_t *   tris)
 682 {
 683     pixman_trapezoid_t *traps;
 684
 685     if ((traps = convert_triangles (n_tris, tris)))
 686     {
 687         pixman_composite_trapezoids (op, src, dst, mask_format,
 688                                      x_src, y_src, x_dst, y_dst,
 689                                      n_tris * 2, traps);
 690
 691         free (traps);
 692     }
 693 }
 694
 695 PIXMAN_EXPORT void
 696 pixman_add_triangles (pixman_image_t          *image,
 697                       int32_t                  x_off,
 698                       int32_t                  y_off,
 699                       int                      n_tris,
 700                       const pixman_triangle_t *tris)
 701 {
 702     pixman_trapezoid_t *traps;
 703
 704     if ((traps = convert_triangles (n_tris, tris)))
 705     {
 706         pixman_add_trapezoids (image, x_off, y_off,
 707                                n_tris * 2, traps);
 708
 709         free (traps);
 710     }
 711 }