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
37PIXMAN_EXPORT pixman_fixed_t
38pixman_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 */
65PIXMAN_EXPORT pixman_fixed_t
66pixman_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 */
93PIXMAN_EXPORT void
94pixman_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 */
127static 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 */
154PIXMAN_EXPORT void
155pixman_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 */
202PIXMAN_EXPORT void
203pixman_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
232PIXMAN_EXPORT void
233pixman_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
290static void
291dump_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
317PIXMAN_EXPORT void
318pixman_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
345PIXMAN_EXPORT void
346pixman_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
390static 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
407static pixman_bool_t
408get_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 */
480PIXMAN_EXPORT void
481pixman_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
550static int
551greater_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 */
562static int
563clockwise (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
578static void
579triangle_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
652static pixman_trapezoid_t *
653convert_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
671PIXMAN_EXPORT void
672pixman_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
695PIXMAN_EXPORT void
696pixman_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}
712