tor-browser

pixman-trap.c (16865B)

---

/*
* 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 <pixman-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) == 0xffff8000)
{
    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);
   }
}