text: /*
   * 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 = (int)((ne + e->dy - 1) / e->dy);
  	    e->e = (pixman_fixed_t)(ne - nx * (pixman_fixed_48_16_t) e->dy);
  	    e->x += nx * e->signdx;
  	}
      }
      else
      {
  	if (ne <= -e->dy)
  	{
  	    int nx = (int)((-ne) / e->dy);
  	    e->e = (pixman_fixed_t)(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 = (int)(ne / e->dy);
  	ne -= nx * (pixman_fixed_48_16_t)e->dy;
  	stepx += nx * e->signdx;
      }
  
      *dx_p = (pixman_fixed_t)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);
      }
  }
  