pixman/pixman-trap.c - third_party/pixman - Git at Google

 /*
  * Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
  * Copyright © 2004 Keith Packard
  *
  * Permission to use, copy, modify, distribute, and sell this software and its
  * documentation for any purpose is hereby granted without fee, provided that
  * the above copyright notice appear in all copies and that both that
  * copyright notice and this permission notice appear in supporting
  * documentation, and that the name of Keith Packard not be used in
  * advertising or publicity pertaining to distribution of the software without
  * specific, written prior permission.  Keith Packard makes no
  * representations about the suitability of this software for any purpose.  It
  * is provided "as is" without express or implied warranty.
  *
  * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
  * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  * PERFORMANCE OF THIS SOFTWARE.
  */

 #ifdef HAVE_CONFIG_H
 #include <config.h>
 #endif

 #include <stdio.h>
 #include <stdlib.h>
 #include "pixman-private.h"

 /*
  * Compute the smallest value greater than or equal to y which is on a
  * grid row.
  */

 PIXMAN_EXPORT pixman_fixed_t
 pixman_sample_ceil_y (pixman_fixed_t y, int n)
 {
     pixman_fixed_t f = pixman_fixed_frac (y);
     pixman_fixed_t i = pixman_fixed_floor (y);

     f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
 	Y_FRAC_FIRST (n);

     if (f > Y_FRAC_LAST (n))
     {
 	if (pixman_fixed_to_int (i) == 0x7fff)
 	{
 	    f = 0xffff; /* saturate */
 	}
 	else
 	{
 	    f = Y_FRAC_FIRST (n);
 	    i += pixman_fixed_1;
 	}
     }
     return (i | f);
 }

 /*
  * Compute the largest value strictly less than y which is on a
  * grid row.
  */
 PIXMAN_EXPORT pixman_fixed_t
 pixman_sample_floor_y (pixman_fixed_t y,
                        int            n)
 {
     pixman_fixed_t f = pixman_fixed_frac (y);
     pixman_fixed_t i = pixman_fixed_floor (y);

     f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
 	Y_FRAC_FIRST (n);

     if (f < Y_FRAC_FIRST (n))
     {
 	if (pixman_fixed_to_int (i) == 0x8000)
 	{
 	    f = 0; /* saturate */
 	}
 	else
 	{
 	    f = Y_FRAC_LAST (n);
 	    i -= pixman_fixed_1;
 	}
     }
     return (i | f);
 }

 /*
  * Step an edge by any amount (including negative values)
  */
 PIXMAN_EXPORT void
 pixman_edge_step (pixman_edge_t *e,
                   int            n)
 {
     pixman_fixed_48_16_t ne;

     e->x += n * e->stepx;

     ne = e->e + n * (pixman_fixed_48_16_t) e->dx;

     if (n >= 0)
     {
 	if (ne > 0)
 	{
 	    int nx = (ne + e->dy - 1) / e->dy;
 	    e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;
 	    e->x += nx * e->signdx;
 	}
     }
     else
     {
 	if (ne <= -e->dy)
 	{
 	    int nx = (-ne) / e->dy;
 	    e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;
 	    e->x -= nx * e->signdx;
 	}
     }
 }

 /*
  * A private routine to initialize the multi-step
  * elements of an edge structure
  */
 static void
 _pixman_edge_multi_init (pixman_edge_t * e,
                          int             n,
                          pixman_fixed_t *stepx_p,
                          pixman_fixed_t *dx_p)
 {
     pixman_fixed_t stepx;
     pixman_fixed_48_16_t ne;

     ne = n * (pixman_fixed_48_16_t) e->dx;
     stepx = n * e->stepx;

     if (ne > 0)
     {
 	int nx = ne / e->dy;
 	ne -= nx * (pixman_fixed_48_16_t)e->dy;
 	stepx += nx * e->signdx;
     }

     *dx_p = ne;
     *stepx_p = stepx;
 }

 /*
  * Initialize one edge structure given the line endpoints and a
  * starting y value
  */
 PIXMAN_EXPORT void
 pixman_edge_init (pixman_edge_t *e,
                   int            n,
                   pixman_fixed_t y_start,
                   pixman_fixed_t x_top,
                   pixman_fixed_t y_top,
                   pixman_fixed_t x_bot,
                   pixman_fixed_t y_bot)
 {
     pixman_fixed_t dx, dy;

     e->x = x_top;
     e->e = 0;
     dx = x_bot - x_top;
     dy = y_bot - y_top;
     e->dy = dy;
     e->dx = 0;

     if (dy)
     {
 	if (dx >= 0)
 	{
 	    e->signdx = 1;
 	    e->stepx = dx / dy;
 	    e->dx = dx % dy;
 	    e->e = -dy;
 	}
 	else
 	{
 	    e->signdx = -1;
 	    e->stepx = -(-dx / dy);
 	    e->dx = -dx % dy;
 	    e->e = 0;
 	}

 	_pixman_edge_multi_init (e, STEP_Y_SMALL (n),
 				 &e->stepx_small, &e->dx_small);

 	_pixman_edge_multi_init (e, STEP_Y_BIG (n),
 				 &e->stepx_big, &e->dx_big);
     }
     pixman_edge_step (e, y_start - y_top);
 }

 /*
  * Initialize one edge structure given a line, starting y value
  * and a pixel offset for the line
  */
 PIXMAN_EXPORT void
 pixman_line_fixed_edge_init (pixman_edge_t *            e,
                              int                        n,
                              pixman_fixed_t             y,
                              const pixman_line_fixed_t *line,
                              int                        x_off,
                              int                        y_off)
 {
     pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);
     pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);
     const pixman_point_fixed_t *top, *bot;

     if (line->p1.y <= line->p2.y)
     {
 	top = &line->p1;
 	bot = &line->p2;
     }
     else
     {
 	top = &line->p2;
 	bot = &line->p1;
     }

     pixman_edge_init (e, n, y,
                       top->x + x_off_fixed,
                       top->y + y_off_fixed,
                       bot->x + x_off_fixed,
                       bot->y + y_off_fixed);
 }

 PIXMAN_EXPORT void
 pixman_add_traps (pixman_image_t *     image,
                   int16_t              x_off,
                   int16_t              y_off,
                   int                  ntrap,
                   const pixman_trap_t *traps)
 {
     int bpp;
     int height;

     pixman_fixed_t x_off_fixed;
     pixman_fixed_t y_off_fixed;
     pixman_edge_t l, r;
     pixman_fixed_t t, b;

     _pixman_image_validate (image);

     height = image->bits.height;
     bpp = PIXMAN_FORMAT_BPP (image->bits.format);

     x_off_fixed = pixman_int_to_fixed (x_off);
     y_off_fixed = pixman_int_to_fixed (y_off);

     while (ntrap--)
     {
 	t = traps->top.y + y_off_fixed;
 	if (t < 0)
 	    t = 0;
 	t = pixman_sample_ceil_y (t, bpp);

 	b = traps->bot.y + y_off_fixed;
 	if (pixman_fixed_to_int (b) >= height)
 	    b = pixman_int_to_fixed (height) - 1;
 	b = pixman_sample_floor_y (b, bpp);

 	if (b >= t)
 	{
 	    /* initialize edge walkers */
 	    pixman_edge_init (&l, bpp, t,
 	                      traps->top.l + x_off_fixed,
 	                      traps->top.y + y_off_fixed,
 	                      traps->bot.l + x_off_fixed,
 	                      traps->bot.y + y_off_fixed);

 	    pixman_edge_init (&r, bpp, t,
 	                      traps->top.r + x_off_fixed,
 	                      traps->top.y + y_off_fixed,
 	                      traps->bot.r + x_off_fixed,
 	                      traps->bot.y + y_off_fixed);

 	    pixman_rasterize_edges (image, &l, &r, t, b);
 	}

 	traps++;
     }
 }

 #if 0
 static void
 dump_image (pixman_image_t *image,
             const char *    title)
 {
     int i, j;

     if (!image->type == BITS)
 	printf ("%s is not a regular image\n", title);

     if (!image->bits.format == PIXMAN_a8)
 	printf ("%s is not an alpha mask\n", title);

     printf ("\n\n\n%s: \n", title);

     for (i = 0; i < image->bits.height; ++i)
     {
 	uint8_t *line =
 	    (uint8_t *)&(image->bits.bits[i * image->bits.rowstride]);

 	for (j = 0; j < image->bits.width; ++j)
 	    printf ("%c", line[j] ? '#' : ' ');

 	printf ("\n");
     }
 }
 #endif

 PIXMAN_EXPORT void
 pixman_add_trapezoids (pixman_image_t *          image,
                        int16_t                   x_off,
                        int                       y_off,
                        int                       ntraps,
                        const pixman_trapezoid_t *traps)
 {
     int i;

 #if 0
     dump_image (image, "before");
 #endif

     for (i = 0; i < ntraps; ++i)
     {
 	const pixman_trapezoid_t *trap = &(traps[i]);

 	if (!pixman_trapezoid_valid (trap))
 	    continue;

 	pixman_rasterize_trapezoid (image, trap, x_off, y_off);
     }

 #if 0
     dump_image (image, "after");
 #endif
 }

 PIXMAN_EXPORT void
 pixman_rasterize_trapezoid (pixman_image_t *          image,
                             const pixman_trapezoid_t *trap,
                             int                       x_off,
                             int                       y_off)
 {
     int bpp;
     int height;

     pixman_fixed_t y_off_fixed;
     pixman_edge_t l, r;
     pixman_fixed_t t, b;

     return_if_fail (image->type == BITS);

     _pixman_image_validate (image);

     if (!pixman_trapezoid_valid (trap))
 	return;

     height = image->bits.height;
     bpp = PIXMAN_FORMAT_BPP (image->bits.format);

     y_off_fixed = pixman_int_to_fixed (y_off);

     t = trap->top + y_off_fixed;
     if (t < 0)
 	t = 0;
     t = pixman_sample_ceil_y (t, bpp);

     b = trap->bottom + y_off_fixed;
     if (pixman_fixed_to_int (b) >= height)
 	b = pixman_int_to_fixed (height) - 1;
     b = pixman_sample_floor_y (b, bpp);

     if (b >= t)
     {
 	/* initialize edge walkers */
 	pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);
 	pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);

 	pixman_rasterize_edges (image, &l, &r, t, b);
     }
 }

 static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] =
 {
     FALSE,	/* Clear		0			0    */
     FALSE,	/* Src			1			0    */
     TRUE,	/* Dst			0			1    */
     TRUE,	/* Over			1			1-Aa */
     TRUE,	/* OverReverse		1-Ab			1    */
     FALSE,	/* In			Ab			0    */
     FALSE,	/* InReverse		0			Aa   */
     FALSE,	/* Out			1-Ab			0    */
     TRUE,	/* OutReverse		0			1-Aa */
     TRUE,	/* Atop			Ab			1-Aa */
     FALSE,	/* AtopReverse		1-Ab			Aa   */
     TRUE,	/* Xor			1-Ab			1-Aa */
     TRUE,	/* Add			1			1    */
 };

 static pixman_bool_t
 get_trap_extents (pixman_op_t op, pixman_image_t *dest,
 		  const pixman_trapezoid_t *traps, int n_traps,
 		  pixman_box32_t *box)
 {
     int i;

     /* When the operator is such that a zero source has an
      * effect on the underlying image, we have to
      * composite across the entire destination
      */
     if (!zero_src_has_no_effect [op])
     {
 	box->x1 = 0;
 	box->y1 = 0;
 	box->x2 = dest->bits.width;
 	box->y2 = dest->bits.height;
 	return TRUE;
     }

     box->x1 = INT32_MAX;
     box->y1 = INT32_MAX;
     box->x2 = INT32_MIN;
     box->y2 = INT32_MIN;

     for (i = 0; i < n_traps; ++i)
     {
 	const pixman_trapezoid_t *trap = &(traps[i]);
 	int y1, y2;

 	if (!pixman_trapezoid_valid (trap))
 	    continue;

 	y1 = pixman_fixed_to_int (trap->top);
 	if (y1 < box->y1)
 	    box->y1 = y1;

 	y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
 	if (y2 > box->y2)
 	    box->y2 = y2;

 #define EXTEND_MIN(x)							\
 	if (pixman_fixed_to_int ((x)) < box->x1)			\
 	    box->x1 = pixman_fixed_to_int ((x));
 #define EXTEND_MAX(x)							\
 	if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2)	\
 	    box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));

 #define EXTEND(x)							\
 	EXTEND_MIN(x);							\
 	EXTEND_MAX(x);

 	EXTEND(trap->left.p1.x);
 	EXTEND(trap->left.p2.x);
 	EXTEND(trap->right.p1.x);
 	EXTEND(trap->right.p2.x);
     }

     if (box->x1 >= box->x2 || box->y1 >= box->y2)
 	return FALSE;

     return TRUE;
 }

 /*
  * pixman_composite_trapezoids()
  *
  * All the trapezoids are conceptually rendered to an infinitely big image.
  * The (0, 0) coordinates of this image are then aligned with the (x, y)
  * coordinates of the source image, and then both images are aligned with
  * the (x, y) coordinates of the destination. Then these three images are
  * composited across the entire destination.
  */
 PIXMAN_EXPORT void
 pixman_composite_trapezoids (pixman_op_t		op,
 			     pixman_image_t *		src,
 			     pixman_image_t *		dst,
 			     pixman_format_code_t	mask_format,
 			     int			x_src,
 			     int			y_src,
 			     int			x_dst,
 			     int			y_dst,
 			     int			n_traps,
 			     const pixman_trapezoid_t *	traps)
 {
     int i;

     return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);

     if (n_traps <= 0)
 	return;

     _pixman_image_validate (src);
     _pixman_image_validate (dst);

     if (op == PIXMAN_OP_ADD &&
 	(src->common.flags & FAST_PATH_IS_OPAQUE)		&&
 	(mask_format == dst->common.extended_format_code)	&&
 	!(dst->common.have_clip_region))
     {
 	for (i = 0; i < n_traps; ++i)
 	{
 	    const pixman_trapezoid_t *trap = &(traps[i]);

 	    if (!pixman_trapezoid_valid (trap))
 		continue;

 	    pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);
 	}
     }
     else
     {
 	pixman_image_t *tmp;
 	pixman_box32_t box;
 	int i;

 	if (!get_trap_extents (op, dst, traps, n_traps, &box))
 	    return;

 	if (!(tmp = pixman_image_create_bits (
 		  mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))
 	    return;

 	for (i = 0; i < n_traps; ++i)
 	{
 	    const pixman_trapezoid_t *trap = &(traps[i]);

 	    if (!pixman_trapezoid_valid (trap))
 		continue;

 	    pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
 	}

 	pixman_image_composite (op, src, tmp, dst,
 				x_src + box.x1, y_src + box.y1,
 				0, 0,
 				x_dst + box.x1, y_dst + box.y1,
 				box.x2 - box.x1, box.y2 - box.y1);

 	pixman_image_unref (tmp);
     }
 }

 static int
 greater_y (const pixman_point_fixed_t *a, const pixman_point_fixed_t *b)
 {
     if (a->y == b->y)
 	return a->x > b->x;
     return a->y > b->y;
 }

 /*
  * Note that the definition of this function is a bit odd because
  * of the X coordinate space (y increasing downwards).
  */
 static int
 clockwise (const pixman_point_fixed_t *ref,
 	   const pixman_point_fixed_t *a,
 	   const pixman_point_fixed_t *b)
 {
     pixman_point_fixed_t	ad, bd;

     ad.x = a->x - ref->x;
     ad.y = a->y - ref->y;
     bd.x = b->x - ref->x;
     bd.y = b->y - ref->y;

     return ((pixman_fixed_32_32_t) bd.y * ad.x -
 	    (pixman_fixed_32_32_t) ad.y * bd.x) < 0;
 }

 static void
 triangle_to_trapezoids (const pixman_triangle_t *tri, pixman_trapezoid_t *traps)
 {
     const pixman_point_fixed_t *top, *left, *right, *tmp;

     top = &tri->p1;
     left = &tri->p2;
     right = &tri->p3;

     if (greater_y (top, left))
     {
 	tmp = left;
 	left = top;
 	top = tmp;
     }

     if (greater_y (top, right))
     {
 	tmp = right;
 	right = top;
 	top = tmp;
     }

     if (clockwise (top, right, left))
     {
 	tmp = right;
 	right = left;
 	left = tmp;
     }

     /*
      * Two cases:
      *
      *		+		+
      *	       / \             / \
      *	      /   \           /	  \
      *	     /     +         +	   \
      *      /    --           --    \
      *     /   --               --   \
      *    / ---                   --- \
      *	 +--                         --+
      */

     traps->top = top->y;
     traps->left.p1 = *top;
     traps->left.p2 = *left;
     traps->right.p1 = *top;
     traps->right.p2 = *right;

     if (right->y < left->y)
 	traps->bottom = right->y;
     else
 	traps->bottom = left->y;

     traps++;

     *traps = *(traps - 1);

     if (right->y < left->y)
     {
 	traps->top = right->y;
 	traps->bottom = left->y;
 	traps->right.p1 = *right;
 	traps->right.p2 = *left;
     }
     else
     {
 	traps->top = left->y;
 	traps->bottom = right->y;
 	traps->left.p1 = *left;
 	traps->left.p2 = *right;
     }
 }

 static pixman_trapezoid_t *
 convert_triangles (int n_tris, const pixman_triangle_t *tris)
 {
     pixman_trapezoid_t *traps;
     int i;

     if (n_tris <= 0)
 	return NULL;

     traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
     if (!traps)
 	return NULL;

     for (i = 0; i < n_tris; ++i)
 	triangle_to_trapezoids (&(tris[i]), traps + 2 * i);

     return traps;
 }

 PIXMAN_EXPORT void
 pixman_composite_triangles (pixman_op_t			op,
 			    pixman_image_t *		src,
 			    pixman_image_t *		dst,
 			    pixman_format_code_t	mask_format,
 			    int				x_src,
 			    int				y_src,
 			    int				x_dst,
 			    int				y_dst,
 			    int				n_tris,
 			    const pixman_triangle_t *	tris)
 {
     pixman_trapezoid_t *traps;

     if ((traps = convert_triangles (n_tris, tris)))
     {
 	pixman_composite_trapezoids (op, src, dst, mask_format,
 				     x_src, y_src, x_dst, y_dst,
 				     n_tris * 2, traps);

 	free (traps);
     }
 }

 PIXMAN_EXPORT void
 pixman_add_triangles (pixman_image_t          *image,
 		      int32_t	               x_off,
 		      int32_t	               y_off,
 		      int	               n_tris,
 		      const pixman_triangle_t *tris)
 {
     pixman_trapezoid_t *traps;

     if ((traps = convert_triangles (n_tris, tris)))
     {
 	pixman_add_trapezoids (image, x_off, y_off,
 			       n_tris * 2, traps);

 	free (traps);
     }
 }
	/*
	* Copyright © 2002 Keith Packard, member of The XFree86 Project, Inc.
	* Copyright © 2004 Keith Packard
	*
	* Permission to use, copy, modify, distribute, and sell this software and its
	* documentation for any purpose is hereby granted without fee, provided that
	* the above copyright notice appear in all copies and that both that
	* copyright notice and this permission notice appear in supporting
	* documentation, and that the name of Keith Packard not be used in
	* advertising or publicity pertaining to distribution of the software without
	* specific, written prior permission. Keith Packard makes no
	* representations about the suitability of this software for any purpose. It
	* is provided "as is" without express or implied warranty.
	*
	* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
	* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
	* EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
	* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
	* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
	* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
	* PERFORMANCE OF THIS SOFTWARE.
	*/

	#ifdef HAVE_CONFIG_H
	#include <config.h>
	#endif

	#include <stdio.h>
	#include <stdlib.h>
	#include "pixman-private.h"

	/*
	* Compute the smallest value greater than or equal to y which is on a
	* grid row.
	*/

	PIXMAN_EXPORT pixman_fixed_t
	pixman_sample_ceil_y (pixman_fixed_t y, int n)
	{
	pixman_fixed_t f = pixman_fixed_frac (y);
	pixman_fixed_t i = pixman_fixed_floor (y);

	f = DIV (f - Y_FRAC_FIRST (n) + (STEP_Y_SMALL (n) - pixman_fixed_e), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
	Y_FRAC_FIRST (n);

	if (f > Y_FRAC_LAST (n))
	{
	if (pixman_fixed_to_int (i) == 0x7fff)
	{
	f = 0xffff; /* saturate */
	}
	else
	{
	f = Y_FRAC_FIRST (n);
	i += pixman_fixed_1;
	}
	}
	return (i \| f);
	}

	/*
	* Compute the largest value strictly less than y which is on a
	* grid row.
	*/
	PIXMAN_EXPORT pixman_fixed_t
	pixman_sample_floor_y (pixman_fixed_t y,
	int n)
	{
	pixman_fixed_t f = pixman_fixed_frac (y);
	pixman_fixed_t i = pixman_fixed_floor (y);

	f = DIV (f - pixman_fixed_e - Y_FRAC_FIRST (n), STEP_Y_SMALL (n)) * STEP_Y_SMALL (n) +
	Y_FRAC_FIRST (n);

	if (f < Y_FRAC_FIRST (n))
	{
	if (pixman_fixed_to_int (i) == 0x8000)
	{
	f = 0; /* saturate */
	}
	else
	{
	f = Y_FRAC_LAST (n);
	i -= pixman_fixed_1;
	}
	}
	return (i \| f);
	}

	/*
	* Step an edge by any amount (including negative values)
	*/
	PIXMAN_EXPORT void
	pixman_edge_step (pixman_edge_t *e,
	int n)
	{
	pixman_fixed_48_16_t ne;

	e->x += n * e->stepx;

	ne = e->e + n * (pixman_fixed_48_16_t) e->dx;

	if (n >= 0)
	{
	if (ne > 0)
	{
	int nx = (ne + e->dy - 1) / e->dy;
	e->e = ne - nx * (pixman_fixed_48_16_t) e->dy;
	e->x += nx * e->signdx;
	}
	}
	else
	{
	if (ne <= -e->dy)
	{
	int nx = (-ne) / e->dy;
	e->e = ne + nx * (pixman_fixed_48_16_t) e->dy;
	e->x -= nx * e->signdx;
	}
	}
	}

	/*
	* A private routine to initialize the multi-step
	* elements of an edge structure
	*/
	static void
	_pixman_edge_multi_init (pixman_edge_t * e,
	int n,
	pixman_fixed_t *stepx_p,
	pixman_fixed_t *dx_p)
	{
	pixman_fixed_t stepx;
	pixman_fixed_48_16_t ne;

	ne = n * (pixman_fixed_48_16_t) e->dx;
	stepx = n * e->stepx;

	if (ne > 0)
	{
	int nx = ne / e->dy;
	ne -= nx * (pixman_fixed_48_16_t)e->dy;
	stepx += nx * e->signdx;
	}

	*dx_p = ne;
	*stepx_p = stepx;
	}

	/*
	* Initialize one edge structure given the line endpoints and a
	* starting y value
	*/
	PIXMAN_EXPORT void
	pixman_edge_init (pixman_edge_t *e,
	int n,
	pixman_fixed_t y_start,
	pixman_fixed_t x_top,
	pixman_fixed_t y_top,
	pixman_fixed_t x_bot,
	pixman_fixed_t y_bot)
	{
	pixman_fixed_t dx, dy;

	e->x = x_top;
	e->e = 0;
	dx = x_bot - x_top;
	dy = y_bot - y_top;
	e->dy = dy;
	e->dx = 0;

	if (dy)
	{
	if (dx >= 0)
	{
	e->signdx = 1;
	e->stepx = dx / dy;
	e->dx = dx % dy;
	e->e = -dy;
	}
	else
	{
	e->signdx = -1;
	e->stepx = -(-dx / dy);
	e->dx = -dx % dy;
	e->e = 0;
	}

	_pixman_edge_multi_init (e, STEP_Y_SMALL (n),
	&e->stepx_small, &e->dx_small);

	_pixman_edge_multi_init (e, STEP_Y_BIG (n),
	&e->stepx_big, &e->dx_big);
	}
	pixman_edge_step (e, y_start - y_top);
	}

	/*
	* Initialize one edge structure given a line, starting y value
	* and a pixel offset for the line
	*/
	PIXMAN_EXPORT void
	pixman_line_fixed_edge_init (pixman_edge_t * e,
	int n,
	pixman_fixed_t y,
	const pixman_line_fixed_t *line,
	int x_off,
	int y_off)
	{
	pixman_fixed_t x_off_fixed = pixman_int_to_fixed (x_off);
	pixman_fixed_t y_off_fixed = pixman_int_to_fixed (y_off);
	const pixman_point_fixed_t top, bot;

	if (line->p1.y <= line->p2.y)
	{
	top = &line->p1;
	bot = &line->p2;
	}
	else
	{
	top = &line->p2;
	bot = &line->p1;
	}

	pixman_edge_init (e, n, y,
	top->x + x_off_fixed,
	top->y + y_off_fixed,
	bot->x + x_off_fixed,
	bot->y + y_off_fixed);
	}

	PIXMAN_EXPORT void
	pixman_add_traps (pixman_image_t * image,
	int16_t x_off,
	int16_t y_off,
	int ntrap,
	const pixman_trap_t *traps)
	{
	int bpp;
	int height;

	pixman_fixed_t x_off_fixed;
	pixman_fixed_t y_off_fixed;
	pixman_edge_t l, r;
	pixman_fixed_t t, b;

	_pixman_image_validate (image);

	height = image->bits.height;
	bpp = PIXMAN_FORMAT_BPP (image->bits.format);

	x_off_fixed = pixman_int_to_fixed (x_off);
	y_off_fixed = pixman_int_to_fixed (y_off);

	while (ntrap--)
	{
	t = traps->top.y + y_off_fixed;
	if (t < 0)
	t = 0;
	t = pixman_sample_ceil_y (t, bpp);

	b = traps->bot.y + y_off_fixed;
	if (pixman_fixed_to_int (b) >= height)
	b = pixman_int_to_fixed (height) - 1;
	b = pixman_sample_floor_y (b, bpp);

	if (b >= t)
	{
	/* initialize edge walkers */
	pixman_edge_init (&l, bpp, t,
	traps->top.l + x_off_fixed,
	traps->top.y + y_off_fixed,
	traps->bot.l + x_off_fixed,
	traps->bot.y + y_off_fixed);

	pixman_edge_init (&r, bpp, t,
	traps->top.r + x_off_fixed,
	traps->top.y + y_off_fixed,
	traps->bot.r + x_off_fixed,
	traps->bot.y + y_off_fixed);

	pixman_rasterize_edges (image, &l, &r, t, b);
	}

	traps++;
	}
	}

	#if 0
	static void
	dump_image (pixman_image_t *image,
	const char * title)
	{
	int i, j;

	if (!image->type == BITS)
	printf ("%s is not a regular image\n", title);

	if (!image->bits.format == PIXMAN_a8)
	printf ("%s is not an alpha mask\n", title);

	printf ("\n\n\n%s: \n", title);

	for (i = 0; i < image->bits.height; ++i)
	{
	uint8_t *line =
	(uint8_t )&(image->bits.bits[i image->bits.rowstride]);

	for (j = 0; j < image->bits.width; ++j)
	printf ("%c", line[j] ? '#' : ' ');

	printf ("\n");
	}
	}
	#endif

	PIXMAN_EXPORT void
	pixman_add_trapezoids (pixman_image_t * image,
	int16_t x_off,
	int y_off,
	int ntraps,
	const pixman_trapezoid_t *traps)
	{
	int i;

	#if 0
	dump_image (image, "before");
	#endif

	for (i = 0; i < ntraps; ++i)
	{
	const pixman_trapezoid_t *trap = &(traps[i]);

	if (!pixman_trapezoid_valid (trap))
	continue;

	pixman_rasterize_trapezoid (image, trap, x_off, y_off);
	}

	#if 0
	dump_image (image, "after");
	#endif
	}

	PIXMAN_EXPORT void
	pixman_rasterize_trapezoid (pixman_image_t * image,
	const pixman_trapezoid_t *trap,
	int x_off,
	int y_off)
	{
	int bpp;
	int height;

	pixman_fixed_t y_off_fixed;
	pixman_edge_t l, r;
	pixman_fixed_t t, b;

	return_if_fail (image->type == BITS);

	_pixman_image_validate (image);

	if (!pixman_trapezoid_valid (trap))
	return;

	height = image->bits.height;
	bpp = PIXMAN_FORMAT_BPP (image->bits.format);

	y_off_fixed = pixman_int_to_fixed (y_off);

	t = trap->top + y_off_fixed;
	if (t < 0)
	t = 0;
	t = pixman_sample_ceil_y (t, bpp);

	b = trap->bottom + y_off_fixed;
	if (pixman_fixed_to_int (b) >= height)
	b = pixman_int_to_fixed (height) - 1;
	b = pixman_sample_floor_y (b, bpp);

	if (b >= t)
	{
	/* initialize edge walkers */
	pixman_line_fixed_edge_init (&l, bpp, t, &trap->left, x_off, y_off);
	pixman_line_fixed_edge_init (&r, bpp, t, &trap->right, x_off, y_off);

	pixman_rasterize_edges (image, &l, &r, t, b);
	}
	}

	static const pixman_bool_t zero_src_has_no_effect[PIXMAN_N_OPERATORS] =
	{
	FALSE, /* Clear 0 0 */
	FALSE, /* Src 1 0 */
	TRUE, /* Dst 0 1 */
	TRUE, /* Over 1 1-Aa */
	TRUE, /* OverReverse 1-Ab 1 */
	FALSE, /* In Ab 0 */
	FALSE, /* InReverse 0 Aa */
	FALSE, /* Out 1-Ab 0 */
	TRUE, /* OutReverse 0 1-Aa */
	TRUE, /* Atop Ab 1-Aa */
	FALSE, /* AtopReverse 1-Ab Aa */
	TRUE, /* Xor 1-Ab 1-Aa */
	TRUE, /* Add 1 1 */
	};

	static pixman_bool_t
	get_trap_extents (pixman_op_t op, pixman_image_t *dest,
	const pixman_trapezoid_t *traps, int n_traps,
	pixman_box32_t *box)
	{
	int i;

	/* When the operator is such that a zero source has an
	* effect on the underlying image, we have to
	* composite across the entire destination
	*/
	if (!zero_src_has_no_effect [op])
	{
	box->x1 = 0;
	box->y1 = 0;
	box->x2 = dest->bits.width;
	box->y2 = dest->bits.height;
	return TRUE;
	}

	box->x1 = INT32_MAX;
	box->y1 = INT32_MAX;
	box->x2 = INT32_MIN;
	box->y2 = INT32_MIN;

	for (i = 0; i < n_traps; ++i)
	{
	const pixman_trapezoid_t *trap = &(traps[i]);
	int y1, y2;

	if (!pixman_trapezoid_valid (trap))
	continue;

	y1 = pixman_fixed_to_int (trap->top);
	if (y1 < box->y1)
	box->y1 = y1;

	y2 = pixman_fixed_to_int (pixman_fixed_ceil (trap->bottom));
	if (y2 > box->y2)
	box->y2 = y2;

	#define EXTEND_MIN(x) \
	if (pixman_fixed_to_int ((x)) < box->x1) \
	box->x1 = pixman_fixed_to_int ((x));
	#define EXTEND_MAX(x) \
	if (pixman_fixed_to_int (pixman_fixed_ceil ((x))) > box->x2) \
	box->x2 = pixman_fixed_to_int (pixman_fixed_ceil ((x)));

	#define EXTEND(x) \
	EXTEND_MIN(x); \
	EXTEND_MAX(x);

	EXTEND(trap->left.p1.x);
	EXTEND(trap->left.p2.x);
	EXTEND(trap->right.p1.x);
	EXTEND(trap->right.p2.x);
	}

	if (box->x1 >= box->x2 \|\| box->y1 >= box->y2)
	return FALSE;

	return TRUE;
	}

	/*
	* pixman_composite_trapezoids()
	*
	* All the trapezoids are conceptually rendered to an infinitely big image.
	* The (0, 0) coordinates of this image are then aligned with the (x, y)
	* coordinates of the source image, and then both images are aligned with
	* the (x, y) coordinates of the destination. Then these three images are
	* composited across the entire destination.
	*/
	PIXMAN_EXPORT void
	pixman_composite_trapezoids (pixman_op_t op,
	pixman_image_t * src,
	pixman_image_t * dst,
	pixman_format_code_t mask_format,
	int x_src,
	int y_src,
	int x_dst,
	int y_dst,
	int n_traps,
	const pixman_trapezoid_t * traps)
	{
	int i;

	return_if_fail (PIXMAN_FORMAT_TYPE (mask_format) == PIXMAN_TYPE_A);

	if (n_traps <= 0)
	return;

	_pixman_image_validate (src);
	_pixman_image_validate (dst);

	if (op == PIXMAN_OP_ADD &&
	(src->common.flags & FAST_PATH_IS_OPAQUE) &&
	(mask_format == dst->common.extended_format_code) &&
	!(dst->common.have_clip_region))
	{
	for (i = 0; i < n_traps; ++i)
	{
	const pixman_trapezoid_t *trap = &(traps[i]);

	if (!pixman_trapezoid_valid (trap))
	continue;

	pixman_rasterize_trapezoid (dst, trap, x_dst, y_dst);
	}
	}
	else
	{
	pixman_image_t *tmp;
	pixman_box32_t box;
	int i;

	if (!get_trap_extents (op, dst, traps, n_traps, &box))
	return;

	if (!(tmp = pixman_image_create_bits (
	mask_format, box.x2 - box.x1, box.y2 - box.y1, NULL, -1)))
	return;

	for (i = 0; i < n_traps; ++i)
	{
	const pixman_trapezoid_t *trap = &(traps[i]);

	if (!pixman_trapezoid_valid (trap))
	continue;

	pixman_rasterize_trapezoid (tmp, trap, - box.x1, - box.y1);
	}

	pixman_image_composite (op, src, tmp, dst,
	x_src + box.x1, y_src + box.y1,
	0, 0,
	x_dst + box.x1, y_dst + box.y1,
	box.x2 - box.x1, box.y2 - box.y1);

	pixman_image_unref (tmp);
	}
	}

	static int
	greater_y (const pixman_point_fixed_t a, const pixman_point_fixed_t b)
	{
	if (a->y == b->y)
	return a->x > b->x;
	return a->y > b->y;
	}

	/*
	* Note that the definition of this function is a bit odd because
	* of the X coordinate space (y increasing downwards).
	*/
	static int
	clockwise (const pixman_point_fixed_t *ref,
	const pixman_point_fixed_t *a,
	const pixman_point_fixed_t *b)
	{
	pixman_point_fixed_t ad, bd;

	ad.x = a->x - ref->x;
	ad.y = a->y - ref->y;
	bd.x = b->x - ref->x;
	bd.y = b->y - ref->y;

	return ((pixman_fixed_32_32_t) bd.y * ad.x -
	(pixman_fixed_32_32_t) ad.y * bd.x) < 0;
	}

	static void
	triangle_to_trapezoids (const pixman_triangle_t tri, pixman_trapezoid_t traps)
	{
	const pixman_point_fixed_t top, left, right, tmp;

	top = &tri->p1;
	left = &tri->p2;
	right = &tri->p3;

	if (greater_y (top, left))
	{
	tmp = left;
	left = top;
	top = tmp;
	}

	if (greater_y (top, right))
	{
	tmp = right;
	right = top;
	top = tmp;
	}

	if (clockwise (top, right, left))
	{
	tmp = right;
	right = left;
	left = tmp;
	}

	/*
	* Two cases:
	*
	* + +
	* / \ / \
	* / \ / \
	* / + + \
	* / -- -- \
	* / -- -- \
	* / --- --- \
	* +-- --+
	*/

	traps->top = top->y;
	traps->left.p1 = *top;
	traps->left.p2 = *left;
	traps->right.p1 = *top;
	traps->right.p2 = *right;

	if (right->y < left->y)
	traps->bottom = right->y;
	else
	traps->bottom = left->y;

	traps++;

	traps = (traps - 1);

	if (right->y < left->y)
	{
	traps->top = right->y;
	traps->bottom = left->y;
	traps->right.p1 = *right;
	traps->right.p2 = *left;
	}
	else
	{
	traps->top = left->y;
	traps->bottom = right->y;
	traps->left.p1 = *left;
	traps->left.p2 = *right;
	}
	}

	static pixman_trapezoid_t *
	convert_triangles (int n_tris, const pixman_triangle_t *tris)
	{
	pixman_trapezoid_t *traps;
	int i;

	if (n_tris <= 0)
	return NULL;

	traps = pixman_malloc_ab (n_tris, 2 * sizeof (pixman_trapezoid_t));
	if (!traps)
	return NULL;

	for (i = 0; i < n_tris; ++i)
	triangle_to_trapezoids (&(tris[i]), traps + 2 * i);

	return traps;
	}

	PIXMAN_EXPORT void
	pixman_composite_triangles (pixman_op_t op,
	pixman_image_t * src,
	pixman_image_t * dst,
	pixman_format_code_t mask_format,
	int x_src,
	int y_src,
	int x_dst,
	int y_dst,
	int n_tris,
	const pixman_triangle_t * tris)
	{
	pixman_trapezoid_t *traps;

	if ((traps = convert_triangles (n_tris, tris)))
	{
	pixman_composite_trapezoids (op, src, dst, mask_format,
	x_src, y_src, x_dst, y_dst,
	n_tris * 2, traps);

	free (traps);
	}
	}

	PIXMAN_EXPORT void
	pixman_add_triangles (pixman_image_t *image,
	int32_t x_off,
	int32_t y_off,
	int n_tris,
	const pixman_triangle_t *tris)
	{
	pixman_trapezoid_t *traps;

	if ((traps = convert_triangles (n_tris, tris)))
	{
	pixman_add_trapezoids (image, x_off, y_off,
	n_tris * 2, traps);

	free (traps);
	}
	}