pixman-region.c

嵌入式图形库

/***********************************************************

Copyright 1987, 1988, 1989, 1998  The Open Group

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.

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Except as contained in this notice, the name of The Open Group shall not be
used in advertising or otherwise to promote the sale, use or other dealings
in this Software without prior written authorization from The Open Group.

Copyright 1987, 1988, 1989 by
Digital Equipment Corporation, Maynard, Massachusetts.

                        All Rights Reserved

Permission to use, copy, modify, and distribute this software and its
documentation for any purpose and without fee is hereby granted,
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 Digital not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.

DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
DIGITAL 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 <stdlib.h>
#include <limits.h>
#include <string.h>
#include <stdio.h>

#include "pixman-private.h"

typedef struct pixman_region16_point {
    int x, y;
} pixman_region16_point_t;

#define PIXREGION_NIL(reg) ((reg)->data && !(reg)->data->numRects)
/* not a region */
#define PIXREGION_NAR(reg)	((reg)->data == pixman_brokendata)
#define PIXREGION_NUM_RECTS(reg) ((reg)->data ? (reg)->data->numRects : 1)
#define PIXREGION_SIZE(reg) ((reg)->data ? (reg)->data->size : 0)
#define PIXREGION_RECTS(reg) ((reg)->data ? (pixman_box16_t *)((reg)->data + 1) \
			               : &(reg)->extents)
#define PIXREGION_BOXPTR(reg) ((pixman_box16_t *)((reg)->data + 1))
#define PIXREGION_BOX(reg,i) (&PIXREGION_BOXPTR(reg)[i])
#define PIXREGION_TOP(reg) PIXREGION_BOX(reg, (reg)->data->numRects)
#define PIXREGION_END(reg) PIXREGION_BOX(reg, (reg)->data->numRects - 1)


#undef assert
#ifdef DEBUG_PIXREGION
#define assert(expr) {if (!(expr)) \
		FatalError("Assertion failed file %s, line %d: expr\n", \
			__FILE__, __LINE__); }
#else
#define assert(expr)
#endif

#define good(reg) assert(pixman_region_selfcheck(reg))

#undef MIN
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#undef MAX
#define MAX(a,b) ((a) > (b) ? (a) : (b))

static const pixman_box16_t _pixman_region_emptyBox = {0, 0, 0, 0};
static const pixman_region16_data_t _pixman_region_emptyData = {0, 0};
static const pixman_region16_data_t _pixman_brokendata = {0, 0};

static pixman_box16_t *pixman_region_emptyBox = (pixman_box16_t *)&_pixman_region_emptyBox;
static pixman_region16_data_t *pixman_region_emptyData = (pixman_region16_data_t *)&_pixman_region_emptyData;
static pixman_region16_data_t *pixman_brokendata = (pixman_region16_data_t *)&_pixman_brokendata;

/* This function exists only to make it possible to preserve the X ABI - it should
 * go away at first opportunity.
 *
 * The problem is that the X ABI exports the three structs and has used
 * them through macros. So the X server calls this function with
 * the addresses of those structs which makes the existing code continue to
 * work.
 */
void
pixman_region_set_static_pointers (pixman_box16_t *empty_box,
				   pixman_region16_data_t *empty_data,
				   pixman_region16_data_t *broken_data)
{
    pixman_region_emptyBox = empty_box;
    pixman_region_emptyData = empty_data;
    pixman_brokendata = broken_data;
}

static pixman_bool_t
pixman_break (pixman_region16_t *pReg);

/*
 * The functions in this file implement the Region abstraction used extensively
 * throughout the X11 sample server. A Region is simply a set of disjoint
 * (non-overlapping) rectangles, plus an "extent" rectangle which is the
 * smallest single rectangle that contains all the non-overlapping rectangles.
 *
 * A Region is implemented as a "y-x-banded" array of rectangles.  This array
 * imposes two degrees of order.  First, all rectangles are sorted by top side
 * y coordinate first (y1), and then by left side x coordinate (x1).
 *
 * Furthermore, the rectangles are grouped into "bands".  Each rectangle in a
 * band has the same top y coordinate (y1), and each has the same bottom y
 * coordinate (y2).  Thus all rectangles in a band differ only in their left
 * and right side (x1 and x2).  Bands are implicit in the array of rectangles:
 * there is no separate list of band start pointers.
 *
 * The y-x band representation does not minimize rectangles.  In particular,
 * if a rectangle vertically crosses a band (the rectangle has scanlines in
 * the y1 to y2 area spanned by the band), then the rectangle may be broken
 * down into two or more smaller rectangles stacked one atop the other.
 *
 *  -----------				    -----------
 *  |         |				    |         |		    band 0
 *  |         |  --------		    -----------  --------
 *  |         |  |      |  in y-x banded    |         |  |      |   band 1
 *  |         |  |      |  form is	    |         |  |      |
 *  -----------  |      |		    -----------  --------
 *               |      |				 |      |   band 2
 *               --------				 --------
 *
 * An added constraint on the rectangles is that they must cover as much
 * horizontal area as possible: no two rectangles within a band are allowed
 * to touch.
 *
 * Whenever possible, bands will be merged together to cover a greater vertical
 * distance (and thus reduce the number of rectangles). Two bands can be merged
 * only if the bottom of one touches the top of the other and they have
 * rectangles in the same places (of the same width, of course).
 *
 * Adam de Boor wrote most of the original region code.  Joel McCormack
 * substantially modified or rewrote most of the core arithmetic routines, and
 * added pixman_region_validate in order to support several speed improvements to
 * pixman_region_validateTree.  Bob Scheifler changed the representation to be more
 * compact when empty or a single rectangle, and did a bunch of gratuitous
 * reformatting. Carl Worth did further gratuitous reformatting while re-merging
 * the server and client region code into libpixregion.
 */

/*  true iff two Boxes overlap */
#define EXTENTCHECK(r1,r2) \
      (!( ((r1)->x2 <= (r2)->x1)  || \
          ((r1)->x1 >= (r2)->x2)  || \
          ((r1)->y2 <= (r2)->y1)  || \
          ((r1)->y1 >= (r2)->y2) ) )

/* true iff (x,y) is in Box */
#define INBOX(r,x,y) \
      ( ((r)->x2 >  x) && \
        ((r)->x1 <= x) && \
        ((r)->y2 >  y) && \
        ((r)->y1 <= y) )

/* true iff Box r1 contains Box r2 */
#define SUBSUMES(r1,r2) \
      ( ((r1)->x1 <= (r2)->x1) && \
        ((r1)->x2 >= (r2)->x2) && \
        ((r1)->y1 <= (r2)->y1) && \
        ((r1)->y2 >= (r2)->y2) )

static size_t
PIXREGION_SZOF(size_t n)
{
    size_t size = n * sizeof(pixman_box16_t);
    if (n > UINT32_MAX / sizeof(pixman_box16_t))
        return 0;

    if (sizeof(pixman_region16_data_t) > UINT32_MAX - size)
        return 0;

    return size + sizeof(pixman_region16_data_t);
}

static void *
allocData(size_t n)
{
    size_t sz = PIXREGION_SZOF(n);
    if (!sz)
	return NULL;

    return malloc(sz);
}

#define freeData(reg) if ((reg)->data && (reg)->data->size) free((reg)->data)

#define RECTALLOC_BAIL(pReg,n,bail) \
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
    if (!pixman_rect_alloc(pReg, n)) { goto bail; }

#define RECTALLOC(pReg,n) \
if (!(pReg)->data || (((pReg)->data->numRects + (n)) > (pReg)->data->size)) \
    if (!pixman_rect_alloc(pReg, n)) { return FALSE; }

#define ADDRECT(pNextRect,nx1,ny1,nx2,ny2)	\
{						\
    pNextRect->x1 = nx1;			\
    pNextRect->y1 = ny1;			\
    pNextRect->x2 = nx2;			\
    pNextRect->y2 = ny2;			\
    pNextRect++;				\
}

#define NEWRECT(pReg,pNextRect,nx1,ny1,nx2,ny2)			\
{									\
    if (!(pReg)->data || ((pReg)->data->numRects == (pReg)->data->size))\
    {									\
	if (!pixman_rect_alloc(pReg, 1))					\
	    return FALSE;						\
	pNextRect = PIXREGION_TOP(pReg);					\
    }									\
    ADDRECT(pNextRect,nx1,ny1,nx2,ny2);					\
    pReg->data->numRects++;						\
    assert(pReg->data->numRects<=pReg->data->size);			\
}

#define DOWNSIZE(reg,numRects)						\
    if (((numRects) < ((reg)->data->size >> 1)) && ((reg)->data->size > 50)) \
    {									\
	pixman_region16_data_t * NewData;				\
	size_t data_size = PIXREGION_SZOF(numRects);			\
	if (!data_size)							\
	    NewData = NULL;						\
	else								\
	    NewData = (pixman_region16_data_t *)realloc((reg)->data, data_size); \
	if (NewData)							\
	{								\
	    NewData->size = (numRects);					\
	    (reg)->data = NewData;					\
	}								\
    }

pixman_bool_t
pixman_region_equal(reg1, reg2)
    pixman_region16_t * reg1;
    pixman_region16_t * reg2;
{
    int i;
    pixman_box16_t *rects1;
    pixman_box16_t *rects2;

    if (reg1->extents.x1 != reg2->extents.x1) return FALSE;
    if (reg1->extents.x2 != reg2->extents.x2) return FALSE;
    if (reg1->extents.y1 != reg2->extents.y1) return FALSE;
    if (reg1->extents.y2 != reg2->extents.y2) return FALSE;
    if (PIXREGION_NUM_RECTS(reg1) != PIXREGION_NUM_RECTS(reg2)) return FALSE;

    rects1 = PIXREGION_RECTS(reg1);
    rects2 = PIXREGION_RECTS(reg2);
    for (i = 0; i != PIXREGION_NUM_RECTS(reg1); i++) {
	if (rects1[i].x1 != rects2[i].x1) return FALSE;
	if (rects1[i].x2 != rects2[i].x2) return FALSE;
	if (rects1[i].y1 != rects2[i].y1) return FALSE;
	if (rects1[i].y2 != rects2[i].y2) return FALSE;
    }
    return TRUE;
}

int
pixman_region16_print(rgn)
    pixman_region16_t * rgn;
{
    int num, size;
    int i;
    pixman_box16_t * rects;

    num = PIXREGION_NUM_RECTS(rgn);
    size = PIXREGION_SIZE(rgn);
    rects = PIXREGION_RECTS(rgn);
    fprintf(stderr, "num: %d size: %d\n", num, size);
    fprintf(stderr, "extents: %d %d %d %d\n",
	   rgn->extents.x1, rgn->extents.y1, rgn->extents.x2, rgn->extents.y2);
    for (i = 0; i < num; i++)
	fprintf(stderr, "%d %d %d %d \n",
		rects[i].x1, rects[i].y1, rects[i].x2, rects[i].y2);
    fprintf(stderr, "\n");
    return(num);
}


void
pixman_region_init (pixman_region16_t *region)
{
    region->extents = *pixman_region_emptyBox;
    region->data = pixman_region_emptyData;
}

void
pixman_region_init_rect (pixman_region16_t *region,
			 int x, int y, unsigned int width, unsigned int height)
{
    region->extents.x1 = x;
    region->extents.y1 = y;
    region->extents.x2 = x + width;
    region->extents.y2 = y + height;
    region->data = NULL;
}

void
pixman_region_init_with_extents (pixman_region16_t *region, pixman_box16_t *extents)
{
    region->extents = *extents;
    region->data = NULL;
}

void
pixman_region_fini (pixman_region16_t *region)
{
    good (region);
    freeData (region);
}

int
pixman_region_n_rects (pixman_region16_t *region)
{
    return PIXREGION_NUM_RECTS (region);
}

pixman_box16_t *
pixman_region_rects (pixman_region16_t *region)
{
    return PIXREGION_RECTS (region);
}

pixman_box16_t *
pixman_region_rectangles (pixman_region16_t *region,
			  int		    *n_rects)
{
    if (n_rects)
	*n_rects = PIXREGION_NUM_RECTS (region);

    return PIXREGION_RECTS (region);
}

static pixman_bool_t
pixman_break (pixman_region16_t *region)
{
    freeData (region);
    region->extents = *pixman_region_emptyBox;
    region->data = pixman_brokendata;
    return FALSE;
}

static pixman_bool_t
pixman_rect_alloc (pixman_region16_t * region, int n)
{
    pixman_region16_data_t *data;

    if (!region->data)
    {
	n++;
	region->data = allocData(n);
	if (!region->data)
	    return pixman_break (region);
	region->data->numRects = 1;
	*PIXREGION_BOXPTR(region) = region->extents;
    }
    else if (!region->data->size)
    {
	region->data = allocData(n);
	if (!region->data)
	    return pixman_break (region);
	region->data->numRects = 0;
    }
    else
    {
	size_t data_size;
	if (n == 1)
	{
	    n = region->data->numRects;
	    if (n > 500) /* XXX pick numbers out of a hat */
		n = 250;
	}
	n += region->data->numRects;
	data_size = PIXREGION_SZOF(n);
	if (!data_size)
	    data = NULL;
	else
	    data = (pixman_region16_data_t *)realloc(region->data, PIXREGION_SZOF(n));
	if (!data)
	    return pixman_break (region);
	region->data = data;
    }
    region->data->size = n;
    return TRUE;
}

pixman_bool_t
pixman_region_copy (pixman_region16_t *dst, pixman_region16_t *src)
{
    good(dst);
    good(src);
    if (dst == src)
	return TRUE;
    dst->extents = src->extents;
    if (!src->data || !src->data->size)
    {
	freeData(dst);
	dst->data = src->data;
	return TRUE;
    }
    if (!dst->data || (dst->data->size < src->data->numRects))
    {
	freeData(dst);
	dst->data = allocData(src->data->numRects);
	if (!dst->data)
	    return pixman_break (dst);
	dst->data->size = src->data->numRects;
    }
    dst->data->numRects = src->data->numRects;
    memmove((char *)PIXREGION_BOXPTR(dst),(char *)PIXREGION_BOXPTR(src),
	  dst->data->numRects * sizeof(pixman_box16_t));
    return TRUE;
}

/*======================================================================
 *	    Generic Region Operator
 *====================================================================*/

/*-
 *-----------------------------------------------------------------------
 * pixman_coalesce --
 *	Attempt to merge the boxes in the current band with those in the
 *	previous one.  We are guaranteed that the current band extends to
 *      the end of the rects array.  Used only by pixman_op.
 *
 * Results:
 *	The new index for the previous band.
 *
 * Side Effects:
 *	If coalescing takes place:
 *	    - rectangles in the previous band will have their y2 fields
 *	      altered.
 *	    - region->data->numRects will be decreased.
 *
 *-----------------------------------------------------------------------
 */
static inline int