gfx/cairo/libpixman/src/pixman-trap.c@b8a032363ba2
gfx/cairo/libpixman/src/pixman-trap.c
Thu, 22 Jan 2015 13:21:57 +0100
- author
- Michael Schloh von Bennewitz <michael@schloh.com>
- date
- Thu, 22 Jan 2015 13:21:57 +0100
- branch
- TOR_BUG_9701
- changeset 15
- b8a032363ba2
- permissions
- -rw-r--r--
Incorporate requested changes from Mozilla in review:
https://bugzilla.mozilla.org/show_bug.cgi?id=1123480#c6
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 */
24 #ifdef HAVE_CONFIG_H
25 #include <config.h>
26 #endif
28 #include <stdio.h>
29 #include <stdlib.h>
30 #include "pixman-private.h"
32 /*
33 * Compute the smallest value greater than or equal to y which is on a
34 * grid row.
35 */
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);
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);
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 }
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);
72 f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
73 Y_FRAC_FIRST (n);
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 }
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;
99 e->x += n * e->stepx;
101 ne = e->e + n * (pixman_fixed_48_16_t) e->dx;
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 }
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;
136 ne = n * (pixman_fixed_48_16_t) e->dx;
137 stepx = n * e->stepx;
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 }
146 *dx_p = ne;
147 *stepx_p = stepx;
148 }
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;
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;
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 }
189 _pixman_edge_multi_init (e, STEP_Y_SMALL (n),
190 &e->stepx_small, &e->dx_small);
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 }
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;
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 }
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 }
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;
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;
247 _pixman_image_validate (image);
249 height = image->bits.height;
250 bpp = PIXMAN_FORMAT_BPP (image->bits.format);
252 x_off_fixed = pixman_int_to_fixed (x_off);
253 y_off_fixed = pixman_int_to_fixed (y_off);
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);
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);
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);
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);
282 pixman_rasterize_edges (image, &l, &r, t, b);
283 }
285 traps++;
286 }
287 }
289 #if 0
290 static void
291 dump_image (pixman_image_t *image,
292 const char * title)
293 {
294 int i, j;
296 if (!image->type == BITS)
297 printf ("%s is not a regular image\n", title);
299 if (!image->bits.format == PIXMAN_a8)
300 printf ("%s is not an alpha mask\n", title);
302 printf ("\n\n\n%s: \n", title);
304 for (i = 0; i < image->bits.height; ++i)
305 {
306 uint8_t *line =
307 (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);
309 for (j = 0; j < image->bits.width; ++j)
310 printf ("%c", line[j] ? '#' : ' ');
312 printf ("\n");
313 }
314 }
315 #endif
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;
326 #if 0
327 dump_image (image, "before");
328 #endif
330 for (i = 0; i < ntraps; ++i)
331 {
332 const pixman_trapezoid_t *trap = &(traps[i]);
334 if (!pixman_trapezoid_valid (trap))
335 continue;
337 pixman_rasterize_trapezoid (image, trap, x_off, y_off);
338 }
340 #if 0
341 dump_image (image, "after");
342 #endif
343 }
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;
354 pixman_fixed_t y_off_fixed;
355 pixman_edge_t l, r;
356 pixman_fixed_t t, b;
358 return_if_fail (image->type == BITS);
360 _pixman_image_validate (image);
362 if (!pixman_trapezoid_valid (trap))
363 return;
365 height = image->bits.height;
366 bpp = PIXMAN_FORMAT_BPP (image->bits.format);
368 y_off_fixed = pixman_int_to_fixed (y_off);
370 t = trap->top + y_off_fixed;
371 if (t < 0)
372 t = 0;
373 t = pixman_sample_ceil_y (t, bpp);
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);
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);
386 pixman_rasterize_edges (image, &l, &r, t, b);
387 }
388 }
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 };
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;
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 }
427 box->x1 = INT32_MAX;
428 box->y1 = INT32_MAX;
429 box->x2 = INT32_MIN;
430 box->y2 = INT32_MIN;
432 for (i = 0; i < n_traps; ++i)
433 {
434 const pixman_trapezoid_t *trap = &(traps[i]);
435 int y1, y2;
437 if (!pixman_trapezoid_valid (trap))
438 continue;
440 y1 = pixman_fixed_to_int (trap->top);
441 if (y1 < box->y1)
442 box->y1 = y1;
444 y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
445 if (y2 > box->y2)
446 box->y2 = y2;
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)));
455 #define EXTEND(x) \
456 EXTEND_MIN(x); \
457 EXTEND_MAX(x);
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 }
465 if (box->x1 >= box->x2 || box->y1 >= box->y2)
466 return FALSE;
468 return TRUE;
469 }
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;
494 return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);
496 if (n_traps <= 0)
497 return;
499 _pixman_image_validate (src);
500 _pixman_image_validate (dst);
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]);
511 if (!pixman_trapezoid_valid (trap))
512 continue;
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;
523 if (!get_trap_extents (op, dst, traps, n_traps, &box))
524 return;
526 if (!(tmp = pixman_image_create_bits (
527 mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))
528 return;
530 for (i = 0; i < n_traps; ++i)
531 {
532 const pixman_trapezoid_t *trap = &(traps[i]);
534 if (!pixman_trapezoid_valid (trap))
535 continue;
537 pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
538 }
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);
546 pixman_image_unref (tmp);
547 }
548 }
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 }
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;
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;
574 return ((pixman_fixed_32_32_t) bd.y * ad.x -
575 (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
576 }
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;
583 top = &tri->p1;
584 left = &tri->p2;
585 right = &tri->p3;
587 if (greater_y (top, left))
588 {
589 tmp = left;
590 left = top;
591 top = tmp;
592 }
594 if (greater_y (top, right))
595 {
596 tmp = right;
597 right = top;
598 top = tmp;
599 }
601 if (clockwise (top, right, left))
602 {
603 tmp = right;
604 right = left;
605 left = tmp;
606 }
608 /*
609 * Two cases:
610 *
611 * + +
612 * / \ / \
613 * / \ / \
614 * / + + \
615 * / -- -- \
616 * / -- -- \
617 * / --- --- \
618 * +-- --+
619 */
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;
627 if (right->y < left->y)
628 traps->bottom = right->y;
629 else
630 traps->bottom = left->y;
632 traps++;
634 *traps = *(traps - 1);
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 }
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;
658 if (n_tris <= 0)
659 return NULL;
661 traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
662 if (!traps)
663 return NULL;
665 for (i = 0; i < n_tris; ++i)
666 triangle_to_trapezoids (&(tris[i]), traps + 2 * i);
668 return traps;
669 }
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;
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);
691 free (traps);
692 }
693 }
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;
704 if ((traps = convert_triangles (n_tris, tris)))
705 {
706 pixman_add_trapezoids (image, x_off, y_off,
707 n_tris * 2, traps);
709 free (traps);
710 }
711 }
