diff options
Diffstat (limited to 'xorg-server/mi')
39 files changed, 1494 insertions, 2053 deletions
diff --git a/xorg-server/mi/Makefile.am b/xorg-server/mi/Makefile.am index 0cef7798f..110c3f5dd 100644 --- a/xorg-server/mi/Makefile.am +++ b/xorg-server/mi/Makefile.am @@ -2,8 +2,8 @@ noinst_LTLIBRARIES = libmi.la if XORG sdk_HEADERS = micmap.h miline.h mipointer.h mi.h \ - migc.h mipointrst.h mizerarc.h micoord.h mifillarc.h \ - mispans.h miwideline.h mistruct.h mifpoly.h mioverlay.h + migc.h mipointrst.h mizerarc.h micoord.h \ + mistruct.h mioverlay.h endif AM_CFLAGS = $(DIX_CFLAGS) @@ -16,7 +16,6 @@ libmi_la_SOURCES = \ micmap.h \ micoord.h \ micopy.c \ - micursor.c \ midash.c \ midispcur.c \ mieq.c \ @@ -24,7 +23,6 @@ libmi_la_SOURCES = \ mifillarc.c \ mifillarc.h \ mifillrct.c \ - mifpolycon.c \ mifpoly.h \ migc.c \ migc.h \ @@ -37,18 +35,13 @@ libmi_la_SOURCES = \ mipointrst.h \ mipoly.c \ mipoly.h \ - mipolycon.c \ - mipolygen.c \ mipolypnt.c \ mipolyrect.c \ mipolyseg.c \ mipolytext.c \ - mipolyutil.c \ mipushpxl.c \ miscanfill.h \ miscrinit.c \ - mispans.c \ - mispans.h \ misprite.c \ misprite.h \ mistruct.h \ diff --git a/xorg-server/mi/mi.h b/xorg-server/mi/mi.h index 5a455c910..db62c9166 100644 --- a/xorg-server/mi/mi.h +++ b/xorg-server/mi/mi.h @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -288,22 +288,6 @@ extern _X_EXPORT void miFillPolygon(DrawablePtr /*dst */ , DDXPointPtr /*pPts */ ); -/* mipolycon.c */ - -extern _X_EXPORT Bool miFillConvexPoly(DrawablePtr /*dst */ , - GCPtr /*pgc */ , - int /*count */ , - DDXPointPtr /*ptsIn */ - ); - -/* mipolygen.c */ - -extern _X_EXPORT Bool miFillGeneralPoly(DrawablePtr /*dst */ , - GCPtr /*pgc */ , - int /*count */ , - DDXPointPtr /*ptsIn */ - ); - /* mipolypnt.c */ extern _X_EXPORT void miPolyPoint(DrawablePtr /*pDrawable */ , diff --git a/xorg-server/mi/miarc.c b/xorg-server/mi/miarc.c index e55108a44..e8bc87e3e 100644 --- a/xorg-server/mi/miarc.c +++ b/xorg-server/mi/miarc.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -63,6 +63,22 @@ SOFTWARE. #include "mifillarc.h" #include <X11/Xfuncproto.h> +#define EPSILON 0.000001 +#define ISEQUAL(a,b) (fabs((a) - (b)) <= EPSILON) +#define UNEQUAL(a,b) (fabs((a) - (b)) > EPSILON) +#define PTISEQUAL(a,b) (ISEQUAL(a.x,b.x) && ISEQUAL(a.y,b.y)) +#define SQSECANT 108.856472512142 /* 1/sin^2(11/2) - for 11o miter cutoff */ + +/* Point with sub-pixel positioning. */ +typedef struct _SppPoint { + double x, y; +} SppPointRec, *SppPointPtr; + +typedef struct _SppArc { + double x, y, width, height; + double angle1, angle2; +} SppArcRec, *SppArcPtr; + static double miDsin(double a); static double miDcos(double a); static double miDasin(double v); @@ -82,7 +98,7 @@ cbrt(double x) /* * some interesting sematic interpretation of the protocol: * - * Self intersecting arcs (i.e. those spanning 360 degrees) + * Self intersecting arcs (i.e. those spanning 360 degrees) * never join with other arcs, and are drawn without caps * (unless on/off dashed, in which case each dash segment * is capped, except when the last segment meets the @@ -99,21 +115,6 @@ cbrt(double x) * */ -#undef max -#undef min - -_X_INLINE static int -max(const int x, const int y) -{ - return x > y ? x : y; -} - -_X_INLINE static int -min(const int x, const int y) -{ - return x < y ? x : y; -} - struct bound { double min, max; }; @@ -353,7 +354,7 @@ of the two quadratics y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0 -where +where A = +/- sqrt(8Z + b^2 - 4c) b, c, d are the cubic, quadratic, and linear coefficients of the quartic @@ -1110,6 +1111,195 @@ miWideArc(DrawablePtr pDraw, GCPtr pGC, int narcs, xArc * parcs) } } +/* Find the index of the point with the smallest y.also return the + * smallest and largest y */ +static int +GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, int *by, int *ty) +{ + SppPointPtr ptMin; + double ymin, ymax; + SppPointPtr ptsStart = pts; + + ptMin = pts; + ymin = ymax = (pts++)->y; + + while (--n > 0) { + if (pts->y < ymin) { + ptMin = pts; + ymin = pts->y; + } + if (pts->y > ymax) + ymax = pts->y; + + pts++; + } + + *by = ICEIL(ymin + yFtrans); + *ty = ICEIL(ymax + yFtrans - 1); + return ptMin - ptsStart; +} + +/* + * miFillSppPoly written by Todd Newman; April. 1987. + * + * Fill a convex polygon. If the given polygon + * is not convex, then the result is undefined. + * The algorithm is to order the edges from smallest + * y to largest by partitioning the array into a left + * edge list and a right edge list. The algorithm used + * to traverse each edge is digital differencing analyzer + * line algorithm with y as the major axis. There's some funny linear + * interpolation involved because of the subpixel postioning. + */ +static void +miFillSppPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ + SppPointPtr ptsIn, /* the points */ + int xTrans, int yTrans, /* Translate each point by this */ + double xFtrans, double yFtrans /* translate before conversion + by this amount. This provides + a mechanism to match rounding + errors with any shape that must + meet the polygon exactly. + */ + ) +{ + double xl = 0.0, xr = 0.0, /* x vals of left and right edges */ + ml = 0.0, /* left edge slope */ + mr = 0.0, /* right edge slope */ + dy, /* delta y */ + i; /* loop counter */ + int y, /* current scanline */ + j, imin, /* index of vertex with smallest y */ + ymin, /* y-extents of polygon */ + ymax, *width, *FirstWidth, /* output buffer */ + *Marked; /* set if this vertex has been used */ + int left, right, /* indices to first endpoints */ + nextleft, nextright; /* indices to second endpoints */ + DDXPointPtr ptsOut, FirstPoint; /* output buffer */ + + if (pgc->miTranslate) { + xTrans += dst->x; + yTrans += dst->y; + } + + imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax); + + y = ymax - ymin + 1; + if ((count < 3) || (y <= 0)) + return; + ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * y); + width = FirstWidth = malloc(sizeof(int) * y); + Marked = malloc(sizeof(int) * count); + + if (!ptsOut || !width || !Marked) { + free(Marked); + free(width); + free(ptsOut); + return; + } + + for (j = 0; j < count; j++) + Marked[j] = 0; + nextleft = nextright = imin; + Marked[imin] = -1; + y = ICEIL(ptsIn[nextleft].y + yFtrans); + + /* + * loop through all edges of the polygon + */ + do { + /* add a left edge if we need to */ + if ((y > (ptsIn[nextleft].y + yFtrans) || + ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) && + Marked[nextleft] != 1) { + Marked[nextleft]++; + left = nextleft++; + + /* find the next edge, considering the end conditions */ + if (nextleft >= count) + nextleft = 0; + + /* now compute the starting point and slope */ + dy = ptsIn[nextleft].y - ptsIn[left].y; + if (dy != 0.0) { + ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy; + dy = y - (ptsIn[left].y + yFtrans); + xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0); + } + } + + /* add a right edge if we need to */ + if ((y > ptsIn[nextright].y + yFtrans) || + (ISEQUAL(y, ptsIn[nextright].y + yFtrans) + && Marked[nextright] != 1)) { + Marked[nextright]++; + right = nextright--; + + /* find the next edge, considering the end conditions */ + if (nextright < 0) + nextright = count - 1; + + /* now compute the starting point and slope */ + dy = ptsIn[nextright].y - ptsIn[right].y; + if (dy != 0.0) { + mr = (ptsIn[nextright].x - ptsIn[right].x) / dy; + dy = y - (ptsIn[right].y + yFtrans); + xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0); + } + } + + /* + * generate scans to fill while we still have + * a right edge as well as a left edge. + */ + i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y; + + if (i < EPSILON) { + if (Marked[nextleft] && Marked[nextright]) { + /* Arrgh, we're trapped! (no more points) + * Out, we've got to get out of here before this decadence saps + * our will completely! */ + break; + } + continue; + } + else { + j = (int) i; + if (!j) + j++; + } + while (j > 0) { + int cxl, cxr; + + ptsOut->y = (y) + yTrans; + + cxl = ICEIL(xl); + cxr = ICEIL(xr); + /* reverse the edges if necessary */ + if (xl < xr) { + *(width++) = cxr - cxl; + (ptsOut++)->x = cxl + xTrans; + } + else { + *(width++) = cxl - cxr; + (ptsOut++)->x = cxr + xTrans; + } + y++; + + /* increment down the edges */ + xl += ml; + xr += mr; + j--; + } + } while (y <= ymax); + + /* Finally, fill the spans we've collected */ + (*pgc->ops->FillSpans) (dst, pgc, + ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); + free(Marked); + free(FirstWidth); + free(FirstPoint); +} static double angleBetween(SppPointRec center, SppPointRec point1, SppPointRec point2) { @@ -1291,7 +1481,7 @@ miArcCap(DrawablePtr pDraw, /* MIROUNDCAP -- a private helper function * Put Rounded cap on end. pCenter is the center of this end of the line * pEnd is the center of the other end of the line. pCorner is one of the - * two corners at this end of the line. + * two corners at this end of the line. * NOTE: pOtherCorner must be counter-clockwise from pCorner. */ /*ARGSUSED*/ static void @@ -1443,7 +1633,7 @@ miDatan2(double dy, double dx) * array. (For example, if we want to leave a spare point to make sectors * instead of segments.) So we pass in the malloc()ed chunk that contains the * array and an index saying where we should start stashing the points. - * If there isn't an array already, we just pass in a null pointer and + * If there isn't an array already, we just pass in a null pointer and * count on realloc() to handle the null pointer correctly. */ static int @@ -1462,7 +1652,7 @@ miGetArcPts(SppArcPtr parc, /* points to an arc */ SppPointPtr poly; /* The spec says that positive angles indicate counterclockwise motion. - * Given our coordinate system (with 0,0 in the upper left corner), + * Given our coordinate system (with 0,0 in the upper left corner), * the screen appears flipped in Y. The easiest fix is to negate the * angles given */ @@ -2548,7 +2738,7 @@ computeBound(struct arc_def *def, } /* - * this section computes the x value of the span at y + * this section computes the x value of the span at y * intersected with the specified face of the ellipse. * * this is the min/max X value over the set of normal @@ -2561,7 +2751,7 @@ computeBound(struct arc_def *def, * * compute the derivative with-respect-to ellipse_y and solve * for zero: - * + * * (w^2 - h^2) ellipse_y^3 + h^4 y * 0 = - ---------------------------------- * h w ellipse_y^2 sqrt (h^2 - ellipse_y^2) @@ -2588,7 +2778,7 @@ computeBound(struct arc_def *def, * * or (to use accelerators), * - * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) + * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) * */ diff --git a/xorg-server/mi/mibitblt.c b/xorg-server/mi/mibitblt.c index 114f72d5b..724396333 100644 --- a/xorg-server/mi/mibitblt.c +++ b/xorg-server/mi/mibitblt.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -66,7 +66,7 @@ SOFTWARE. extern int ffs(int); #endif -/* MICOPYAREA -- public entry for the CopyArea request +/* MICOPYAREA -- public entry for the CopyArea request * For each rectangle in the source region * get the pixels with GetSpans * set them in the destination with SetSpans @@ -253,7 +253,7 @@ miCopyArea(DrawablePtr pSrcDrawable, } /* MIGETPLANE -- gets a bitmap representing one plane of pDraw - * A helper used for CopyPlane and XY format GetImage + * A helper used for CopyPlane and XY format GetImage * No clever strategy here, we grab a scanline at a time, pull out the * bits and then stuff them in a 1 bit deep map. */ @@ -358,9 +358,9 @@ miGetPlane(DrawablePtr pDraw, int planeNum, /* number of the bitPlane */ } /* MIOPQSTIPDRAWABLE -- use pbits as an opaque stipple for pDraw. - * Drawing through the clip mask we SetSpans() the bits into a + * Drawing through the clip mask we SetSpans() the bits into a * bitmap and stipple those bits onto the destination drawable by doing a - * PolyFillRect over the whole drawable, + * PolyFillRect over the whole drawable, * then we invert the bitmap by copying it onto itself with an alu of * GXinvert, invert the foreground/background colors of the gc, and draw * the background bits. @@ -504,10 +504,10 @@ miOpqStipDrawable(DrawablePtr pDraw, GCPtr pGC, RegionPtr prgnSrc, } /* MICOPYPLANE -- public entry for the CopyPlane request. - * strategy: - * First build up a bitmap out of the bits requested + * strategy: + * First build up a bitmap out of the bits requested * build a source clip - * Use the bitmap we've built up as a Stipple for the destination + * Use the bitmap we've built up as a Stipple for the destination */ _X_COLD RegionPtr miCopyPlane(DrawablePtr pSrcDrawable, @@ -670,16 +670,16 @@ miGetImage(DrawablePtr pDraw, int sx, int sy, int w, int h, /* MIPUTIMAGE -- public entry for the PutImage request * Here we benefit from knowing the format of the bits pointed to by pImage, - * even if we don't know how pDraw represents them. - * Three different strategies are used depending on the format + * even if we don't know how pDraw represents them. + * Three different strategies are used depending on the format * XYBitmap Format: * we just use the Opaque Stipple helper function to cover the destination - * Note that this covers all the planes of the drawable with the + * Note that this covers all the planes of the drawable with the * foreground color (masked with the GC planemask) where there are 1 bits * and the background color (masked with the GC planemask) where there are * 0 bits * XYPixmap format: - * what we're called with is a series of XYBitmaps, but we only want + * what we're called with is a series of XYBitmaps, but we only want * each XYPixmap to update 1 plane, instead of updating all of them. * we set the foreground color to be all 1s and the background to all 0s * then for each plane, we set the plane mask to only effect that one diff --git a/xorg-server/mi/micopy.c b/xorg-server/mi/micopy.c index a52b0a786..2409c7880 100644 --- a/xorg-server/mi/micopy.c +++ b/xorg-server/mi/micopy.c @@ -167,7 +167,7 @@ miDoCopy(DrawablePtr pSrcDrawable, /* Compute source clip region */ if (pSrcDrawable->type == DRAWABLE_PIXMAP) { - if ((pSrcDrawable == pDstDrawable) && (pGC->clientClipType == CT_NONE)) + if ((pSrcDrawable == pDstDrawable) && (!pGC->clientClip)) prgnSrcClip = miGetCompositeClip(pGC); else fastSrc = TRUE; @@ -186,8 +186,7 @@ miDoCopy(DrawablePtr pSrcDrawable, */ fastSrc = TRUE; } - else if ((pSrcDrawable == pDstDrawable) && - (pGC->clientClipType == CT_NONE)) { + else if ((pSrcDrawable == pDstDrawable) && (!pGC->clientClip)) { prgnSrcClip = miGetCompositeClip(pGC); } else { diff --git a/xorg-server/mi/micursor.c b/xorg-server/mi/micursor.c deleted file mode 100644 index 13ce776db..000000000 --- a/xorg-server/mi/micursor.c +++ /dev/null @@ -1,68 +0,0 @@ -/*********************************************************** - -Copyright 1987, 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include "scrnintstr.h" -#include "cursor.h" -#include "misc.h" -#include "mi.h" -#include "inputstr.h" - -void -miRecolorCursor(DeviceIntPtr pDev, ScreenPtr pScr, - CursorPtr pCurs, Bool displayed) -{ - /* - * This is guaranteed to correct any color-dependent state which may have - * been bound up in private state created by RealizeCursor - */ - pScr->UnrealizeCursor(pDev, pScr, pCurs); - pScr->RealizeCursor(pDev, pScr, pCurs); - if (displayed) - pScr->DisplayCursor(pDev, pScr, pCurs); -} diff --git a/xorg-server/mi/midash.c b/xorg-server/mi/midash.c index 78cbaf25e..08f11aa38 100644 --- a/xorg-server/mi/midash.c +++ b/xorg-server/mi/midash.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -49,7 +49,6 @@ SOFTWARE. #include "regionstr.h" #include "mistruct.h" -#include "mifpoly.h" void miStepDash(int dist, /* distance to step */ diff --git a/xorg-server/mi/midispcur.c b/xorg-server/mi/midispcur.c index 8cca5fe6e..50f0dd212 100644 --- a/xorg-server/mi/midispcur.c +++ b/xorg-server/mi/midispcur.c @@ -78,9 +78,9 @@ typedef struct { (miDCBufferPtr)dixLookupScreenPrivate(&dev->devPrivates, miDCDeviceKey, screen) : \ (miDCBufferPtr)dixLookupScreenPrivate(&GetMaster(dev, MASTER_POINTER)->devPrivates, miDCDeviceKey, screen)) -/* +/* * The core pointer buffer will point to the index of the virtual pointer - * in the pCursorBuffers array. + * in the pCursorBuffers array. */ typedef struct { CloseScreenProcPtr CloseScreen; diff --git a/xorg-server/mi/miexpose.c b/xorg-server/mi/miexpose.c index de8ee6c2a..fc4dbc071 100644 --- a/xorg-server/mi/miexpose.c +++ b/xorg-server/mi/miexpose.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -107,7 +107,7 @@ the region package can call this. #define RECTLIMIT 25 /* pick a number, any number > 8 */ #endif -/* miHandleExposures +/* miHandleExposures generate a region for exposures for areas that were copied from obscured or non-existent areas to non-obscured areas of the destination. Paint the background for the region, if the destination is a window. @@ -131,8 +131,8 @@ miHandleExposures(DrawablePtr pSrcDrawable, DrawablePtr pDstDrawable, RegionRec rgnExposed; /* exposed region, calculated source- relative, made dst relative to intersect with visible parts of - dest and send events to client, - and then screen relative to paint + dest and send events to client, + and then screen relative to paint the window background */ WindowPtr pSrcWin; @@ -230,7 +230,7 @@ miHandleExposures(DrawablePtr pSrcDrawable, DrawablePtr pDstDrawable, RegionIntersect(&rgnExposed, &rgnExposed, prgnDstClip); /* intersect with client clip region. */ - if (pGC->clientClipType == CT_REGION) + if (pGC->clientClip) RegionIntersect(&rgnExposed, &rgnExposed, pGC->clientClip); /* @@ -564,7 +564,7 @@ miPaintWindow(WindowPtr pWin, RegionPtr prgn, int what) } /* MICLEARDRAWABLE -- sets the entire drawable to the background color of - * the GC. Useful when we have a scratch drawable and need to initialize + * the GC. Useful when we have a scratch drawable and need to initialize * it. */ void miClearDrawable(DrawablePtr pDraw, GCPtr pGC) diff --git a/xorg-server/mi/mifillarc.c b/xorg-server/mi/mifillarc.c index 08484d703..246d70ff4 100644 --- a/xorg-server/mi/mifillarc.c +++ b/xorg-server/mi/mifillarc.c @@ -36,7 +36,6 @@ Author: Bob Scheifler, MIT X Consortium #include "regionstr.h" #include "gcstruct.h" #include "pixmapstr.h" -#include "mifpoly.h" #include "mi.h" #include "mifillarc.h" @@ -51,7 +50,7 @@ Author: Bob Scheifler, MIT X Consortium #define Dsin(d) sin((double)d*(M_PI/11520.0)) #define Dcos(d) cos((double)d*(M_PI/11520.0)) -void +static void miFillArcSetup(xArc * arc, miFillArcRec * info) { info->y = arc->height >> 1; @@ -277,7 +276,7 @@ miGetPieEdge(xArc * arc, int angle, miSliceEdgePtr edge, Bool top, Bool left) miGetArcEdge(arc, edge, k, top, left); } -void +static void miFillArcSliceSetup(xArc * arc, miArcSliceRec * slice, GCPtr pGC) { int angle1, angle2; diff --git a/xorg-server/mi/mifillarc.h b/xorg-server/mi/mifillarc.h index 1478d1850..61ab2538d 100644 --- a/xorg-server/mi/mifillarc.h +++ b/xorg-server/mi/mifillarc.h @@ -175,13 +175,4 @@ typedef struct _miArcSlice { #define miFillInArcLower(slw) (((iny + dy) != 0) && \ ((slw > 1) || (ine != inxk))) -extern _X_EXPORT void miFillArcSetup(xArc * /*arc */ , - miFillArcRec * /*info */ - ); - -extern _X_EXPORT void miFillArcSliceSetup(xArc * /*arc */ , - miArcSliceRec * /*slice */ , - GCPtr /*pGC */ - ); - #endif /* __MIFILLARC_H__ */ diff --git a/xorg-server/mi/mifillrct.c b/xorg-server/mi/mifillrct.c index faf60498b..28f2322e6 100644 --- a/xorg-server/mi/mifillrct.c +++ b/xorg-server/mi/mifillrct.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mifpoly.h b/xorg-server/mi/mifpoly.h index f853fb46b..3202476b2 100644 --- a/xorg-server/mi/mifpoly.h +++ b/xorg-server/mi/mifpoly.h @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -49,24 +49,6 @@ SOFTWARE. #include <X11/Xfuncproto.h> -#define EPSILON 0.000001 -#define ISEQUAL(a,b) (fabs((a) - (b)) <= EPSILON) -#define UNEQUAL(a,b) (fabs((a) - (b)) > EPSILON) -#define WITHINHALF(a, b) (((a) - (b) > 0.0) ? (a) - (b) < 0.5 : \ - (b) - (a) <= 0.5) -#define ROUNDTOINT(x) ((int) (((x) > 0.0) ? ((x) + 0.5) : ((x) - 0.5))) -#define ISZERO(x) (fabs((x)) <= EPSILON) -#define PTISEQUAL(a,b) (ISEQUAL(a.x,b.x) && ISEQUAL(a.y,b.y)) -#define PTUNEQUAL(a,b) (UNEQUAL(a.x,b.x) || UNEQUAL(a.y,b.y)) -#define PtEqual(a, b) (((a).x == (b).x) && ((a).y == (b).y)) - -#define NotEnd 0 -#define FirstEnd 1 -#define SecondEnd 2 - -#define SQSECANT 108.856472512142 /* 1/sin^2(11/2) - for 11o miter cutoff */ -#define D2SECANT 5.21671526231167 /* 1/2*sin(11/2) - max extension per width */ - static _X_INLINE int ICEIL(double x) { @@ -75,28 +57,4 @@ ICEIL(double x) return ((x == _cTmp) || (x < 0.0)) ? _cTmp : _cTmp + 1; } -/* Point with sub-pixel positioning. In this case we use doubles, but - * see mifpolycon.c for other suggestions - */ -typedef struct _SppPoint { - double x, y; -} SppPointRec, *SppPointPtr; - -typedef struct _SppArc { - double x, y, width, height; - double angle1, angle2; -} SppArcRec, *SppArcPtr; - -/* mifpolycon.c */ - -extern _X_EXPORT void miFillSppPoly(DrawablePtr /*dst */ , - GCPtr /*pgc */ , - int /*count */ , - SppPointPtr /*ptsIn */ , - int /*xTrans */ , - int /*yTrans */ , - double /*xFtrans */ , - double /*yFtrans */ - ); - #endif /* __MIFPOLY_H__ */ diff --git a/xorg-server/mi/mifpolycon.c b/xorg-server/mi/mifpolycon.c deleted file mode 100644 index b1337315b..000000000 --- a/xorg-server/mi/mifpolycon.c +++ /dev/null @@ -1,249 +0,0 @@ -/*********************************************************** - -Copyright 1987, 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include <math.h> -#include <X11/X.h> -#include "gcstruct.h" -#include "windowstr.h" -#include "pixmapstr.h" -#include "mifpoly.h" - -static int GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, - int *by, int *ty); - -/* - * Written by Todd Newman; April. 1987. - * - * Fill a convex polygon. If the given polygon - * is not convex, then the result is undefined. - * The algorithm is to order the edges from smallest - * y to largest by partitioning the array into a left - * edge list and a right edge list. The algorithm used - * to traverse each edge is digital differencing analyzer - * line algorithm with y as the major axis. There's some funny linear - * interpolation involved because of the subpixel postioning. - */ -void -miFillSppPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ - SppPointPtr ptsIn, /* the points */ - int xTrans, int yTrans, /* Translate each point by this */ - double xFtrans, double yFtrans /* translate before conversion - by this amount. This provides - a mechanism to match rounding - errors with any shape that must - meet the polygon exactly. - */ - ) -{ - double xl = 0.0, xr = 0.0, /* x vals of left and right edges */ - ml = 0.0, /* left edge slope */ - mr = 0.0, /* right edge slope */ - dy, /* delta y */ - i; /* loop counter */ - int y, /* current scanline */ - j, imin, /* index of vertex with smallest y */ - ymin, /* y-extents of polygon */ - ymax, *width, *FirstWidth, /* output buffer */ - *Marked; /* set if this vertex has been used */ - int left, right, /* indices to first endpoints */ - nextleft, nextright; /* indices to second endpoints */ - DDXPointPtr ptsOut, FirstPoint; /* output buffer */ - - if (pgc->miTranslate) { - xTrans += dst->x; - yTrans += dst->y; - } - - imin = GetFPolyYBounds(ptsIn, count, yFtrans, &ymin, &ymax); - - y = ymax - ymin + 1; - if ((count < 3) || (y <= 0)) - return; - ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * y); - width = FirstWidth = malloc(sizeof(int) * y); - Marked = malloc(sizeof(int) * count); - - if (!ptsOut || !width || !Marked) { - free(Marked); - free(width); - free(ptsOut); - return; - } - - for (j = 0; j < count; j++) - Marked[j] = 0; - nextleft = nextright = imin; - Marked[imin] = -1; - y = ICEIL(ptsIn[nextleft].y + yFtrans); - - /* - * loop through all edges of the polygon - */ - do { - /* add a left edge if we need to */ - if ((y > (ptsIn[nextleft].y + yFtrans) || - ISEQUAL(y, ptsIn[nextleft].y + yFtrans)) && - Marked[nextleft] != 1) { - Marked[nextleft]++; - left = nextleft++; - - /* find the next edge, considering the end conditions */ - if (nextleft >= count) - nextleft = 0; - - /* now compute the starting point and slope */ - dy = ptsIn[nextleft].y - ptsIn[left].y; - if (dy != 0.0) { - ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy; - dy = y - (ptsIn[left].y + yFtrans); - xl = (ptsIn[left].x + xFtrans) + ml * max(dy, 0); - } - } - - /* add a right edge if we need to */ - if ((y > ptsIn[nextright].y + yFtrans) || - (ISEQUAL(y, ptsIn[nextright].y + yFtrans) - && Marked[nextright] != 1)) { - Marked[nextright]++; - right = nextright--; - - /* find the next edge, considering the end conditions */ - if (nextright < 0) - nextright = count - 1; - - /* now compute the starting point and slope */ - dy = ptsIn[nextright].y - ptsIn[right].y; - if (dy != 0.0) { - mr = (ptsIn[nextright].x - ptsIn[right].x) / dy; - dy = y - (ptsIn[right].y + yFtrans); - xr = (ptsIn[right].x + xFtrans) + mr * max(dy, 0); - } - } - - /* - * generate scans to fill while we still have - * a right edge as well as a left edge. - */ - i = (min(ptsIn[nextleft].y, ptsIn[nextright].y) + yFtrans) - y; - - if (i < EPSILON) { - if (Marked[nextleft] && Marked[nextright]) { - /* Arrgh, we're trapped! (no more points) - * Out, we've got to get out of here before this decadence saps - * our will completely! */ - break; - } - continue; - } - else { - j = (int) i; - if (!j) - j++; - } - while (j > 0) { - int cxl, cxr; - - ptsOut->y = (y) + yTrans; - - cxl = ICEIL(xl); - cxr = ICEIL(xr); - /* reverse the edges if necessary */ - if (xl < xr) { - *(width++) = cxr - cxl; - (ptsOut++)->x = cxl + xTrans; - } - else { - *(width++) = cxl - cxr; - (ptsOut++)->x = cxr + xTrans; - } - y++; - - /* increment down the edges */ - xl += ml; - xr += mr; - j--; - } - } while (y <= ymax); - - /* Finally, fill the spans we've collected */ - (*pgc->ops->FillSpans) (dst, pgc, - ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); - free(Marked); - free(FirstWidth); - free(FirstPoint); -} - -/* Find the index of the point with the smallest y.also return the - * smallest and largest y */ -static - int -GetFPolyYBounds(SppPointPtr pts, int n, double yFtrans, int *by, int *ty) -{ - SppPointPtr ptMin; - double ymin, ymax; - SppPointPtr ptsStart = pts; - - ptMin = pts; - ymin = ymax = (pts++)->y; - - while (--n > 0) { - if (pts->y < ymin) { - ptMin = pts; - ymin = pts->y; - } - if (pts->y > ymax) - ymax = pts->y; - - pts++; - } - - *by = ICEIL(ymin + yFtrans); - *ty = ICEIL(ymax + yFtrans - 1); - return ptMin - ptsStart; -} diff --git a/xorg-server/mi/migc.c b/xorg-server/mi/migc.c index 9bbe8846e..8fdd4810c 100644 --- a/xorg-server/mi/migc.c +++ b/xorg-server/mi/migc.c @@ -55,20 +55,9 @@ miDestroyGC(GCPtr pGC) void miDestroyClip(GCPtr pGC) { - if (pGC->clientClipType == CT_NONE) - return; - else if (pGC->clientClipType == CT_PIXMAP) { - (*pGC->pScreen->DestroyPixmap) ((PixmapPtr) (pGC->clientClip)); - } - else { - /* - * we know we'll never have a list of rectangles, since ChangeClip - * immediately turns them into a region - */ + if (pGC->clientClip) RegionDestroy(pGC->clientClip); - } pGC->clientClip = NULL; - pGC->clientClipType = CT_NONE; } void @@ -77,8 +66,7 @@ miChangeClip(GCPtr pGC, int type, void *pvalue, int nrects) (*pGC->funcs->DestroyClip) (pGC); if (type == CT_PIXMAP) { /* convert the pixmap to a region */ - pGC->clientClip = (void *) BitmapToRegion(pGC->pScreen, - (PixmapPtr) pvalue); + pGC->clientClip = BitmapToRegion(pGC->pScreen, (PixmapPtr) pvalue); (*pGC->pScreen->DestroyPixmap) (pvalue); } else if (type == CT_REGION) { @@ -86,34 +74,21 @@ miChangeClip(GCPtr pGC, int type, void *pvalue, int nrects) pGC->clientClip = pvalue; } else if (type != CT_NONE) { - pGC->clientClip = (void *) RegionFromRects(nrects, - (xRectangle *) pvalue, - type); + pGC->clientClip = RegionFromRects(nrects, (xRectangle *) pvalue, type); free(pvalue); } - pGC->clientClipType = (type != CT_NONE && - pGC->clientClip) ? CT_REGION : CT_NONE; pGC->stateChanges |= GCClipMask; } void miCopyClip(GCPtr pgcDst, GCPtr pgcSrc) { - RegionPtr prgnNew; - - switch (pgcSrc->clientClipType) { - case CT_PIXMAP: - ((PixmapPtr) pgcSrc->clientClip)->refcnt++; - /* Fall through !! */ - case CT_NONE: - (*pgcDst->funcs->ChangeClip) (pgcDst, (int) pgcSrc->clientClipType, - pgcSrc->clientClip, 0); - break; - case CT_REGION: - prgnNew = RegionCreate(NULL, 1); + if (pgcSrc->clientClip) { + RegionPtr prgnNew = RegionCreate(NULL, 1); RegionCopy(prgnNew, (RegionPtr) (pgcSrc->clientClip)); - (*pgcDst->funcs->ChangeClip) (pgcDst, CT_REGION, (void *) prgnNew, 0); - break; + (*pgcDst->funcs->ChangeClip) (pgcDst, CT_REGION, prgnNew, 0); + } else { + (*pgcDst->funcs->ChangeClip) (pgcDst, CT_NONE, NULL, 0); } } @@ -149,7 +124,7 @@ miComputeCompositeClip(GCPtr pGC, DrawablePtr pDrawable) * regions. (this wins especially if many clients clip by children * and have no client clip.) */ - if (pGC->clientClipType == CT_NONE) { + if (!pGC->clientClip) { if (freeCompClip) RegionDestroy(pGC->pCompositeClip); pGC->pCompositeClip = pregWin; @@ -206,7 +181,7 @@ miComputeCompositeClip(GCPtr pGC, DrawablePtr pDrawable) pGC->pCompositeClip = RegionCreate(&pixbounds, 1); } - if (pGC->clientClipType == CT_REGION) { + if (pGC->clientClip) { if (pDrawable->x || pDrawable->y) { RegionTranslate(pGC->clientClip, pDrawable->x + pGC->clipOrg.x, diff --git a/xorg-server/mi/miglblt.c b/xorg-server/mi/miglblt.c index b53ab9c0e..0183e998b 100644 --- a/xorg-server/mi/miglblt.c +++ b/xorg-server/mi/miglblt.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/miinitext.c b/xorg-server/mi/miinitext.c index 1d905167e..5872bf534 100644 --- a/xorg-server/mi/miinitext.c +++ b/xorg-server/mi/miinitext.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mioverlay.c b/xorg-server/mi/mioverlay.c index eb8dda133..2b20fd72f 100644 --- a/xorg-server/mi/mioverlay.c +++ b/xorg-server/mi/mioverlay.c @@ -1667,7 +1667,7 @@ miOverlayComputeCompositeClip(GCPtr pGC, WindowPtr pWin) freeTmpClip = FALSE; } freeCompClip = pGC->freeCompClip; - if (pGC->clientClipType == CT_NONE) { + if (!pGC->clientClip) { if (freeCompClip) RegionDestroy(pGC->pCompositeClip); pGC->pCompositeClip = pregWin; diff --git a/xorg-server/mi/mipointer.c b/xorg-server/mi/mipointer.c index 6fa416d9d..2bdd6ca98 100644 --- a/xorg-server/mi/mipointer.c +++ b/xorg-server/mi/mipointer.c @@ -273,6 +273,20 @@ miPointerSetCursorPosition(DeviceIntPtr pDev, ScreenPtr pScreen, return TRUE; } +void +miRecolorCursor(DeviceIntPtr pDev, ScreenPtr pScr, + CursorPtr pCurs, Bool displayed) +{ + /* + * This is guaranteed to correct any color-dependent state which may have + * been bound up in private state created by RealizeCursor + */ + pScr->UnrealizeCursor(pDev, pScr, pCurs); + pScr->RealizeCursor(pDev, pScr, pCurs); + if (displayed) + pScr->DisplayCursor(pDev, pScr, pCurs); +} + /** * Set up sprite information for the device. * This function will be called once for each device after it is initialized @@ -539,10 +553,15 @@ miPointerMoveNoEvent(DeviceIntPtr pDev, ScreenPtr pScreen, int x, int y) * The coordinates provided are always absolute. The parameter mode whether * it was relative or absolute movement that landed us at those coordinates. * + * If the cursor was constrained by a barrier, ET_Barrier* events may be + * generated and appended to the InternalEvent list provided. + * * @param pDev The device to move * @param mode Movement mode (Absolute or Relative) * @param[in,out] screenx The x coordinate in desktop coordinates * @param[in,out] screeny The y coordinate in desktop coordinates + * @param[in,out] nevents The number of events in events (before/after) + * @param[in,out] events The list of events before/after being constrained */ ScreenPtr miPointerSetPosition(DeviceIntPtr pDev, int mode, double *screenx, diff --git a/xorg-server/mi/mipoly.c b/xorg-server/mi/mipoly.c index 07d981845..a332376d1 100644 --- a/xorg-server/mi/mipoly.c +++ b/xorg-server/mi/mipoly.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -47,11 +47,6 @@ SOFTWARE. * mipoly.c * * Written by Brian Kelleher; June 1986 - * - * Draw polygons. This routine translates the point by the - * origin if pGC->miTranslate is non-zero, and calls - * to the appropriate routine to actually scan convert the - * polygon. */ #ifdef HAVE_DIX_CONFIG_H #include <dix-config.h> @@ -62,8 +57,622 @@ SOFTWARE. #include "gcstruct.h" #include "pixmapstr.h" #include "mi.h" +#include "miscanfill.h" +#include "mipoly.h" #include "regionstr.h" +/* + * Insert the given edge into the edge table. First we must find the correct + * bucket in the Edge table, then find the right slot in the bucket. Finally, + * we can insert it. + */ +static Bool +miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, + ScanLineListBlock ** SLLBlock, int *iSLLBlock) +{ + EdgeTableEntry *start, *prev; + ScanLineList *pSLL, *pPrevSLL; + ScanLineListBlock *tmpSLLBlock; + + /* + * find the right bucket to put the edge into + */ + pPrevSLL = &ET->scanlines; + pSLL = pPrevSLL->next; + while (pSLL && (pSLL->scanline < scanline)) { + pPrevSLL = pSLL; + pSLL = pSLL->next; + } + + /* + * reassign pSLL (pointer to ScanLineList) if necessary + */ + if ((!pSLL) || (pSLL->scanline > scanline)) { + if (*iSLLBlock > SLLSPERBLOCK - 1) { + tmpSLLBlock = malloc(sizeof(ScanLineListBlock)); + if (!tmpSLLBlock) + return FALSE; + (*SLLBlock)->next = tmpSLLBlock; + tmpSLLBlock->next = NULL; + *SLLBlock = tmpSLLBlock; + *iSLLBlock = 0; + } + pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); + + pSLL->next = pPrevSLL->next; + pSLL->edgelist = NULL; + pPrevSLL->next = pSLL; + } + pSLL->scanline = scanline; + + /* + * now insert the edge in the right bucket + */ + prev = NULL; + start = pSLL->edgelist; + while (start && (start->bres.minor < ETE->bres.minor)) { + prev = start; + start = start->next; + } + ETE->next = start; + + if (prev) + prev->next = ETE; + else + pSLL->edgelist = ETE; + return TRUE; +} + +static void +miFreeStorage(ScanLineListBlock * pSLLBlock) +{ + ScanLineListBlock *tmpSLLBlock; + + while (pSLLBlock) { + tmpSLLBlock = pSLLBlock->next; + free(pSLLBlock); + pSLLBlock = tmpSLLBlock; + } +} + +/* + * CreateEdgeTable + * + * This routine creates the edge table for scan converting polygons. + * The Edge Table (ET) looks like: + * + * EdgeTable + * -------- + * | ymax | ScanLineLists + * |scanline|-->------------>-------------->... + * -------- |scanline| |scanline| + * |edgelist| |edgelist| + * --------- --------- + * | | + * | | + * V V + * list of ETEs list of ETEs + * + * where ETE is an EdgeTableEntry data structure, and there is one ScanLineList + * per scanline at which an edge is initially entered. + */ + +static Bool +miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET, + EdgeTableEntry * AET, EdgeTableEntry * pETEs, + ScanLineListBlock * pSLLBlock) +{ + DDXPointPtr top, bottom; + DDXPointPtr PrevPt, CurrPt; + int iSLLBlock = 0; + + int dy; + + if (count < 2) + return TRUE; + + /* + * initialize the Active Edge Table + */ + AET->next = NULL; + AET->back = NULL; + AET->nextWETE = NULL; + AET->bres.minor = MININT; + + /* + * initialize the Edge Table. + */ + ET->scanlines.next = NULL; + ET->ymax = MININT; + ET->ymin = MAXINT; + pSLLBlock->next = NULL; + + PrevPt = &pts[count - 1]; + + /* + * for each vertex in the array of points. + * In this loop we are dealing with two vertices at + * a time -- these make up one edge of the polygon. + */ + while (count--) { + CurrPt = pts++; + + /* + * find out which point is above and which is below. + */ + if (PrevPt->y > CurrPt->y) { + bottom = PrevPt, top = CurrPt; + pETEs->ClockWise = 0; + } + else { + bottom = CurrPt, top = PrevPt; + pETEs->ClockWise = 1; + } + + /* + * don't add horizontal edges to the Edge table. + */ + if (bottom->y != top->y) { + pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */ + + /* + * initialize integer edge algorithm + */ + dy = bottom->y - top->y; + BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres); + + if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) { + miFreeStorage(pSLLBlock->next); + return FALSE; + } + + ET->ymax = max(ET->ymax, PrevPt->y); + ET->ymin = min(ET->ymin, PrevPt->y); + pETEs++; + } + + PrevPt = CurrPt; + } + return TRUE; +} + +/* + * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge + * Table, leaving them sorted by smaller x coordinate. + */ + +static void +miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs) +{ + EdgeTableEntry *pPrevAET; + EdgeTableEntry *tmp; + + pPrevAET = AET; + AET = AET->next; + while (ETEs) { + while (AET && (AET->bres.minor < ETEs->bres.minor)) { + pPrevAET = AET; + AET = AET->next; + } + tmp = ETEs->next; + ETEs->next = AET; + if (AET) + AET->back = ETEs; + ETEs->back = pPrevAET; + pPrevAET->next = ETEs; + pPrevAET = ETEs; + + ETEs = tmp; + } +} + +/* + * computeWAET + * + * This routine links the AET by the nextWETE (winding EdgeTableEntry) link for + * use by the winding number rule. The final Active Edge Table (AET) might + * look something like: + * + * AET + * ---------- --------- --------- + * |ymax | |ymax | |ymax | + * | ... | |... | |... | + * |next |->|next |->|next |->... + * |nextWETE| |nextWETE| |nextWETE| + * --------- --------- ^-------- + * | | | + * V-------------------> V---> ... + * + */ +static void +micomputeWAET(EdgeTableEntry * AET) +{ + EdgeTableEntry *pWETE; + int inside = 1; + int isInside = 0; + + AET->nextWETE = NULL; + pWETE = AET; + AET = AET->next; + while (AET) { + if (AET->ClockWise) + isInside++; + else + isInside--; + + if ((!inside && !isInside) || (inside && isInside)) { + pWETE->nextWETE = AET; + pWETE = AET; + inside = !inside; + } + AET = AET->next; + } + pWETE->nextWETE = NULL; +} + +/* + * Just a simple insertion sort using pointers and back pointers to sort the + * Active Edge Table. + */ + +static int +miInsertionSort(EdgeTableEntry * AET) +{ + EdgeTableEntry *pETEchase; + EdgeTableEntry *pETEinsert; + EdgeTableEntry *pETEchaseBackTMP; + int changed = 0; + + AET = AET->next; + while (AET) { + pETEinsert = AET; + pETEchase = AET; + while (pETEchase->back->bres.minor > AET->bres.minor) + pETEchase = pETEchase->back; + + AET = AET->next; + if (pETEchase != pETEinsert) { + pETEchaseBackTMP = pETEchase->back; + pETEinsert->back->next = AET; + if (AET) + AET->back = pETEinsert->back; + pETEinsert->next = pETEchase; + pETEchase->back->next = pETEinsert; + pETEchase->back = pETEinsert; + pETEinsert->back = pETEchaseBackTMP; + changed = 1; + } + } + return changed; +} + +/* Find the index of the point with the smallest y */ +static int +getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty) +{ + DDXPointPtr ptMin; + int ymin, ymax; + DDXPointPtr ptsStart = pts; + + ptMin = pts; + ymin = ymax = (pts++)->y; + + while (--n > 0) { + if (pts->y < ymin) { + ptMin = pts; + ymin = pts->y; + } + if (pts->y > ymax) + ymax = pts->y; + + pts++; + } + + *by = ymin; + *ty = ymax; + return ptMin - ptsStart; +} + +/* + * Written by Brian Kelleher; Dec. 1985. + * + * Fill a convex polygon. If the given polygon is not convex, then the result + * is undefined. The algorithm is to order the edges from smallest y to + * largest by partitioning the array into a left edge list and a right edge + * list. The algorithm used to traverse each edge is an extension of + * Bresenham's line algorithm with y as the major axis. For a derivation of + * the algorithm, see the author of this code. + */ +static Bool +miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) +{ + int xl = 0, xr = 0; /* x vals of left and right edges */ + int dl = 0, dr = 0; /* decision variables */ + int ml = 0, m1l = 0; /* left edge slope and slope+1 */ + int mr = 0, m1r = 0; /* right edge slope and slope+1 */ + int incr1l = 0, incr2l = 0; /* left edge error increments */ + int incr1r = 0, incr2r = 0; /* right edge error increments */ + int dy; /* delta y */ + int y; /* current scanline */ + int left, right; /* indices to first endpoints */ + int i; /* loop counter */ + int nextleft, nextright; /* indices to second endpoints */ + DDXPointPtr ptsOut, FirstPoint; /* output buffer */ + int *width, *FirstWidth; /* output buffer */ + int imin; /* index of smallest vertex (in y) */ + int ymin; /* y-extents of polygon */ + int ymax; + + /* + * find leftx, bottomy, rightx, topy, and the index + * of bottomy. Also translate the points. + */ + imin = getPolyYBounds(ptsIn, count, &ymin, &ymax); + + dy = ymax - ymin + 1; + if ((count < 3) || (dy < 0)) + return TRUE; + ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * dy); + width = FirstWidth = malloc(sizeof(int) * dy); + if (!FirstPoint || !FirstWidth) { + free(FirstWidth); + free(FirstPoint); + return FALSE; + } + + nextleft = nextright = imin; + y = ptsIn[nextleft].y; + + /* + * loop through all edges of the polygon + */ + do { + /* + * add a left edge if we need to + */ + if (ptsIn[nextleft].y == y) { + left = nextleft; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextleft++; + if (nextleft >= count) + nextleft = 0; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y, + ptsIn[left].x, ptsIn[nextleft].x, + xl, dl, ml, m1l, incr1l, incr2l); + } + + /* + * add a right edge if we need to + */ + if (ptsIn[nextright].y == y) { + right = nextright; + + /* + * find the next edge, considering the end + * conditions of the array. + */ + nextright--; + if (nextright < 0) + nextright = count - 1; + + /* + * now compute all of the random information + * needed to run the iterative algorithm. + */ + BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y, + ptsIn[right].x, ptsIn[nextright].x, + xr, dr, mr, m1r, incr1r, incr2r); + } + + /* + * generate scans to fill while we still have + * a right edge as well as a left edge. + */ + i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y; + /* in case we're called with non-convex polygon */ + if (i < 0) { + free(FirstWidth); + free(FirstPoint); + return TRUE; + } + while (i-- > 0) { + ptsOut->y = y; + + /* + * reverse the edges if necessary + */ + if (xl < xr) { + *(width++) = xr - xl; + (ptsOut++)->x = xl; + } + else { + *(width++) = xl - xr; + (ptsOut++)->x = xr; + } + y++; + + /* increment down the edges */ + BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l); + BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r); + } + } while (y != ymax); + + /* + * Finally, fill the <remaining> spans + */ + (*pgc->ops->FillSpans) (dst, pgc, + ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); + free(FirstWidth); + free(FirstPoint); + return TRUE; +} + +/* + * Written by Brian Kelleher; Oct. 1985 + * + * Routine to fill a polygon. Two fill rules are supported: frWINDING and + * frEVENODD. + */ +static Bool +miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn) +{ + EdgeTableEntry *pAET; /* the Active Edge Table */ + int y; /* the current scanline */ + int nPts = 0; /* number of pts in buffer */ + EdgeTableEntry *pWETE; /* Winding Edge Table */ + ScanLineList *pSLL; /* Current ScanLineList */ + DDXPointPtr ptsOut; /* ptr to output buffers */ + int *width; + DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ + int FirstWidth[NUMPTSTOBUFFER]; + EdgeTableEntry *pPrevAET; /* previous AET entry */ + EdgeTable ET; /* Edge Table header node */ + EdgeTableEntry AET; /* Active ET header node */ + EdgeTableEntry *pETEs; /* Edge Table Entries buff */ + ScanLineListBlock SLLBlock; /* header for ScanLineList */ + int fixWAET = 0; + + if (count < 3) + return TRUE; + + if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count))) + return FALSE; + ptsOut = FirstPoint; + width = FirstWidth; + if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { + free(pETEs); + return FALSE; + } + pSLL = ET.scanlines.next; + + if (pgc->fillRule == EvenOddRule) { + /* + * for each scanline + */ + for (y = ET.ymin; y < ET.ymax; y++) { + /* + * Add a new edge to the active edge table when we + * get to the next edge. + */ + if (pSLL && y == pSLL->scanline) { + miloadAET(&AET, pSLL->edgelist); + pSLL = pSLL->next; + } + pPrevAET = &AET; + pAET = AET.next; + + /* + * for each active edge + */ + while (pAET) { + ptsOut->x = pAET->bres.minor; + ptsOut++->y = y; + *width++ = pAET->next->bres.minor - pAET->bres.minor; + nPts++; + + /* + * send out the buffer when its full + */ + if (nPts == NUMPTSTOBUFFER) { + (*pgc->ops->FillSpans) (dst, pgc, + nPts, FirstPoint, FirstWidth, 1); + ptsOut = FirstPoint; + width = FirstWidth; + nPts = 0; + } + EVALUATEEDGEEVENODD(pAET, pPrevAET, y); + EVALUATEEDGEEVENODD(pAET, pPrevAET, y); + } + miInsertionSort(&AET); + } + } + else { /* default to WindingNumber */ + + /* + * for each scanline + */ + for (y = ET.ymin; y < ET.ymax; y++) { + /* + * Add a new edge to the active edge table when we + * get to the next edge. + */ + if (pSLL && y == pSLL->scanline) { + miloadAET(&AET, pSLL->edgelist); + micomputeWAET(&AET); + pSLL = pSLL->next; + } + pPrevAET = &AET; + pAET = AET.next; + pWETE = pAET; + + /* + * for each active edge + */ + while (pAET) { + /* + * if the next edge in the active edge table is + * also the next edge in the winding active edge + * table. + */ + if (pWETE == pAET) { + ptsOut->x = pAET->bres.minor; + ptsOut++->y = y; + *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor; + nPts++; + + /* + * send out the buffer + */ + if (nPts == NUMPTSTOBUFFER) { + (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, + FirstWidth, 1); + ptsOut = FirstPoint; + width = FirstWidth; + nPts = 0; + } + + pWETE = pWETE->nextWETE; + while (pWETE != pAET) + EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); + pWETE = pWETE->nextWETE; + } + EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); + } + + /* + * reevaluate the Winding active edge table if we + * just had to resort it or if we just exited an edge. + */ + if (miInsertionSort(&AET) || fixWAET) { + micomputeWAET(&AET); + fixWAET = 0; + } + } + } + + /* + * Get any spans that we missed by buffering + */ + (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1); + free(pETEs); + miFreeStorage(SLLBlock.next); + return TRUE; +} + +/* + * Draw polygons. This routine translates the point by the origin if + * pGC->miTranslate is non-zero, and calls to the appropriate routine to + * actually scan convert the polygon. + */ void miFillPolygon(DrawablePtr dst, GCPtr pgc, int shape, int mode, int count, DDXPointPtr pPts) diff --git a/xorg-server/mi/mipoly.h b/xorg-server/mi/mipoly.h index e37fb48a2..d67a5249e 100644 --- a/xorg-server/mi/mipoly.h +++ b/xorg-server/mi/mipoly.h @@ -55,7 +55,7 @@ from The Open Group. * the polygon by incrementing the y coordinate. We * keep a list of edges which the current scanline crosses, * sorted by x. This list is called the Active Edge Table (AET) - * As we change the y-coordinate, we update each entry in + * As we change the y-coordinate, we update each entry in * in the active edge table to reflect the edges new xcoord. * This list must be sorted at each scanline in case * two edges intersect. @@ -171,23 +171,3 @@ typedef struct _ScanLineListBlock { pAET = pAET->next; \ } \ } - -/* mipolyutil.c */ - -extern _X_EXPORT Bool miCreateETandAET(int /*count */ , - DDXPointPtr /*pts */ , - EdgeTable * /*ET*/, - EdgeTableEntry * /*AET*/, - EdgeTableEntry * /*pETEs */ , - ScanLineListBlock * /*pSLLBlock */ - ); - -extern _X_EXPORT void miloadAET(EdgeTableEntry * /*AET*/, EdgeTableEntry * /*ETEs */ - ); - -extern _X_EXPORT void micomputeWAET(EdgeTableEntry * /*AET*/); - -extern _X_EXPORT int miInsertionSort(EdgeTableEntry * /*AET*/); - -extern _X_EXPORT void miFreeStorage(ScanLineListBlock * /*pSLLBlock */ - ); diff --git a/xorg-server/mi/mipolycon.c b/xorg-server/mi/mipolycon.c deleted file mode 100644 index e831633fe..000000000 --- a/xorg-server/mi/mipolycon.c +++ /dev/null @@ -1,235 +0,0 @@ -/*********************************************************** - -Copyright 1987, 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include "gcstruct.h" -#include "pixmap.h" -#include "mi.h" -#include "miscanfill.h" - -static int getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty); - -/* - * convexpoly.c - * - * Written by Brian Kelleher; Dec. 1985. - * - * Fill a convex polygon. If the given polygon - * is not convex, then the result is undefined. - * The algorithm is to order the edges from smallest - * y to largest by partitioning the array into a left - * edge list and a right edge list. The algorithm used - * to traverse each edge is an extension of Bresenham's - * line algorithm with y as the major axis. - * For a derivation of the algorithm, see the author of - * this code. - */ -Bool -miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ - DDXPointPtr ptsIn /* the points */ - ) -{ - int xl = 0, xr = 0; /* x vals of left and right edges */ - int dl = 0, dr = 0; /* decision variables */ - int ml = 0, m1l = 0; /* left edge slope and slope+1 */ - int mr = 0, m1r = 0; /* right edge slope and slope+1 */ - int incr1l = 0, incr2l = 0; /* left edge error increments */ - int incr1r = 0, incr2r = 0; /* right edge error increments */ - int dy; /* delta y */ - int y; /* current scanline */ - int left, right; /* indices to first endpoints */ - int i; /* loop counter */ - int nextleft, nextright; /* indices to second endpoints */ - DDXPointPtr ptsOut, FirstPoint; /* output buffer */ - int *width, *FirstWidth; /* output buffer */ - int imin; /* index of smallest vertex (in y) */ - int ymin; /* y-extents of polygon */ - int ymax; - - /* - * find leftx, bottomy, rightx, topy, and the index - * of bottomy. Also translate the points. - */ - imin = getPolyYBounds(ptsIn, count, &ymin, &ymax); - - dy = ymax - ymin + 1; - if ((count < 3) || (dy < 0)) - return TRUE; - ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * dy); - width = FirstWidth = malloc(sizeof(int) * dy); - if (!FirstPoint || !FirstWidth) { - free(FirstWidth); - free(FirstPoint); - return FALSE; - } - - nextleft = nextright = imin; - y = ptsIn[nextleft].y; - - /* - * loop through all edges of the polygon - */ - do { - /* - * add a left edge if we need to - */ - if (ptsIn[nextleft].y == y) { - left = nextleft; - - /* - * find the next edge, considering the end - * conditions of the array. - */ - nextleft++; - if (nextleft >= count) - nextleft = 0; - - /* - * now compute all of the random information - * needed to run the iterative algorithm. - */ - BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y, - ptsIn[left].x, ptsIn[nextleft].x, - xl, dl, ml, m1l, incr1l, incr2l); - } - - /* - * add a right edge if we need to - */ - if (ptsIn[nextright].y == y) { - right = nextright; - - /* - * find the next edge, considering the end - * conditions of the array. - */ - nextright--; - if (nextright < 0) - nextright = count - 1; - - /* - * now compute all of the random information - * needed to run the iterative algorithm. - */ - BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y, - ptsIn[right].x, ptsIn[nextright].x, - xr, dr, mr, m1r, incr1r, incr2r); - } - - /* - * generate scans to fill while we still have - * a right edge as well as a left edge. - */ - i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y; - /* in case we're called with non-convex polygon */ - if (i < 0) { - free(FirstWidth); - free(FirstPoint); - return TRUE; - } - while (i-- > 0) { - ptsOut->y = y; - - /* - * reverse the edges if necessary - */ - if (xl < xr) { - *(width++) = xr - xl; - (ptsOut++)->x = xl; - } - else { - *(width++) = xl - xr; - (ptsOut++)->x = xr; - } - y++; - - /* increment down the edges */ - BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l); - BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r); - } - } while (y != ymax); - - /* - * Finally, fill the <remaining> spans - */ - (*pgc->ops->FillSpans) (dst, pgc, - ptsOut - FirstPoint, FirstPoint, FirstWidth, 1); - free(FirstWidth); - free(FirstPoint); - return TRUE; -} - -/* - * Find the index of the point with the smallest y. - */ -static int -getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty) -{ - DDXPointPtr ptMin; - int ymin, ymax; - DDXPointPtr ptsStart = pts; - - ptMin = pts; - ymin = ymax = (pts++)->y; - - while (--n > 0) { - if (pts->y < ymin) { - ptMin = pts; - ymin = pts->y; - } - if (pts->y > ymax) - ymax = pts->y; - - pts++; - } - - *by = ymin; - *ty = ymax; - return ptMin - ptsStart; -} diff --git a/xorg-server/mi/mipolygen.c b/xorg-server/mi/mipolygen.c deleted file mode 100644 index 2031b42b7..000000000 --- a/xorg-server/mi/mipolygen.c +++ /dev/null @@ -1,213 +0,0 @@ -/*********************************************************** - -Copyright 1987, 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include <X11/X.h> -#include "gcstruct.h" -#include "miscanfill.h" -#include "mipoly.h" -#include "pixmap.h" -#include "mi.h" - -/* - * - * Written by Brian Kelleher; Oct. 1985 - * - * Routine to fill a polygon. Two fill rules are - * supported: frWINDING and frEVENODD. - * - * See fillpoly.h for a complete description of the algorithm. - */ - -Bool -miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, /* number of points */ - DDXPointPtr ptsIn /* the points */ - ) -{ - EdgeTableEntry *pAET; /* the Active Edge Table */ - int y; /* the current scanline */ - int nPts = 0; /* number of pts in buffer */ - EdgeTableEntry *pWETE; /* Winding Edge Table */ - ScanLineList *pSLL; /* Current ScanLineList */ - DDXPointPtr ptsOut; /* ptr to output buffers */ - int *width; - DDXPointRec FirstPoint[NUMPTSTOBUFFER]; /* the output buffers */ - int FirstWidth[NUMPTSTOBUFFER]; - EdgeTableEntry *pPrevAET; /* previous AET entry */ - EdgeTable ET; /* Edge Table header node */ - EdgeTableEntry AET; /* Active ET header node */ - EdgeTableEntry *pETEs; /* Edge Table Entries buff */ - ScanLineListBlock SLLBlock; /* header for ScanLineList */ - int fixWAET = 0; - - if (count < 3) - return TRUE; - - if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count))) - return FALSE; - ptsOut = FirstPoint; - width = FirstWidth; - if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) { - free(pETEs); - return FALSE; - } - pSLL = ET.scanlines.next; - - if (pgc->fillRule == EvenOddRule) { - /* - * for each scanline - */ - for (y = ET.ymin; y < ET.ymax; y++) { - /* - * Add a new edge to the active edge table when we - * get to the next edge. - */ - if (pSLL && y == pSLL->scanline) { - miloadAET(&AET, pSLL->edgelist); - pSLL = pSLL->next; - } - pPrevAET = &AET; - pAET = AET.next; - - /* - * for each active edge - */ - while (pAET) { - ptsOut->x = pAET->bres.minor; - ptsOut++->y = y; - *width++ = pAET->next->bres.minor - pAET->bres.minor; - nPts++; - - /* - * send out the buffer when its full - */ - if (nPts == NUMPTSTOBUFFER) { - (*pgc->ops->FillSpans) (dst, pgc, - nPts, FirstPoint, FirstWidth, 1); - ptsOut = FirstPoint; - width = FirstWidth; - nPts = 0; - } - EVALUATEEDGEEVENODD(pAET, pPrevAET, y) - EVALUATEEDGEEVENODD(pAET, pPrevAET, y); - } - miInsertionSort(&AET); - } - } - else { /* default to WindingNumber */ - - /* - * for each scanline - */ - for (y = ET.ymin; y < ET.ymax; y++) { - /* - * Add a new edge to the active edge table when we - * get to the next edge. - */ - if (pSLL && y == pSLL->scanline) { - miloadAET(&AET, pSLL->edgelist); - micomputeWAET(&AET); - pSLL = pSLL->next; - } - pPrevAET = &AET; - pAET = AET.next; - pWETE = pAET; - - /* - * for each active edge - */ - while (pAET) { - /* - * if the next edge in the active edge table is - * also the next edge in the winding active edge - * table. - */ - if (pWETE == pAET) { - ptsOut->x = pAET->bres.minor; - ptsOut++->y = y; - *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor; - nPts++; - - /* - * send out the buffer - */ - if (nPts == NUMPTSTOBUFFER) { - (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, - FirstWidth, 1); - ptsOut = FirstPoint; - width = FirstWidth; - nPts = 0; - } - - pWETE = pWETE->nextWETE; - while (pWETE != pAET) - EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); - pWETE = pWETE->nextWETE; - } - EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET); - } - - /* - * reevaluate the Winding active edge table if we - * just had to resort it or if we just exited an edge. - */ - if (miInsertionSort(&AET) || fixWAET) { - micomputeWAET(&AET); - fixWAET = 0; - } - } - } - - /* - * Get any spans that we missed by buffering - */ - (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1); - free(pETEs); - miFreeStorage(SLLBlock.next); - return TRUE; -} diff --git a/xorg-server/mi/mipolypnt.c b/xorg-server/mi/mipolypnt.c index 086502b26..4fa521d07 100644 --- a/xorg-server/mi/mipolypnt.c +++ b/xorg-server/mi/mipolypnt.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mipolyrect.c b/xorg-server/mi/mipolyrect.c index e316ae053..830822513 100644 --- a/xorg-server/mi/mipolyrect.c +++ b/xorg-server/mi/mipolyrect.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mipolyseg.c b/xorg-server/mi/mipolyseg.c index d6f18076c..7909b398b 100644 --- a/xorg-server/mi/mipolyseg.c +++ b/xorg-server/mi/mipolyseg.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -61,7 +61,7 @@ SOFTWARE. * lines are drawn in the order listed. * * Walks the segments, compressing them into format for PolyLines. - * + * *****************************************************************/ void diff --git a/xorg-server/mi/mipolytext.c b/xorg-server/mi/mipolytext.c index 02c45882f..f1e5ed867 100644 --- a/xorg-server/mi/mipolytext.c +++ b/xorg-server/mi/mipolytext.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mipolyutil.c b/xorg-server/mi/mipolyutil.c deleted file mode 100644 index 5e6301d43..000000000 --- a/xorg-server/mi/mipolyutil.c +++ /dev/null @@ -1,369 +0,0 @@ -/*********************************************************** - -Copyright 1987, 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include "regionstr.h" -#include "gc.h" -#include "miscanfill.h" -#include "mipoly.h" -#include "misc.h" /* MAXINT */ - -/* - * fillUtils.c - * - * Written by Brian Kelleher; Oct. 1985 - * - * This module contains all of the utility functions - * needed to scan convert a polygon. - * - */ - -/* - * InsertEdgeInET - * - * Insert the given edge into the edge table. - * First we must find the correct bucket in the - * Edge table, then find the right slot in the - * bucket. Finally, we can insert it. - * - */ -static Bool -miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline, - ScanLineListBlock ** SLLBlock, int *iSLLBlock) -{ - EdgeTableEntry *start, *prev; - ScanLineList *pSLL, *pPrevSLL; - ScanLineListBlock *tmpSLLBlock; - - /* - * find the right bucket to put the edge into - */ - pPrevSLL = &ET->scanlines; - pSLL = pPrevSLL->next; - while (pSLL && (pSLL->scanline < scanline)) { - pPrevSLL = pSLL; - pSLL = pSLL->next; - } - - /* - * reassign pSLL (pointer to ScanLineList) if necessary - */ - if ((!pSLL) || (pSLL->scanline > scanline)) { - if (*iSLLBlock > SLLSPERBLOCK - 1) { - tmpSLLBlock = malloc(sizeof(ScanLineListBlock)); - if (!tmpSLLBlock) - return FALSE; - (*SLLBlock)->next = tmpSLLBlock; - tmpSLLBlock->next = NULL; - *SLLBlock = tmpSLLBlock; - *iSLLBlock = 0; - } - pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]); - - pSLL->next = pPrevSLL->next; - pSLL->edgelist = NULL; - pPrevSLL->next = pSLL; - } - pSLL->scanline = scanline; - - /* - * now insert the edge in the right bucket - */ - prev = NULL; - start = pSLL->edgelist; - while (start && (start->bres.minor < ETE->bres.minor)) { - prev = start; - start = start->next; - } - ETE->next = start; - - if (prev) - prev->next = ETE; - else - pSLL->edgelist = ETE; - return TRUE; -} - -/* - * CreateEdgeTable - * - * This routine creates the edge table for - * scan converting polygons. - * The Edge Table (ET) looks like: - * - * EdgeTable - * -------- - * | ymax | ScanLineLists - * |scanline|-->------------>-------------->... - * -------- |scanline| |scanline| - * |edgelist| |edgelist| - * --------- --------- - * | | - * | | - * V V - * list of ETEs list of ETEs - * - * where ETE is an EdgeTableEntry data structure, - * and there is one ScanLineList per scanline at - * which an edge is initially entered. - * - */ - -Bool -miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET, - EdgeTableEntry * AET, EdgeTableEntry * pETEs, - ScanLineListBlock * pSLLBlock) -{ - DDXPointPtr top, bottom; - DDXPointPtr PrevPt, CurrPt; - int iSLLBlock = 0; - - int dy; - - if (count < 2) - return TRUE; - - /* - * initialize the Active Edge Table - */ - AET->next = NULL; - AET->back = NULL; - AET->nextWETE = NULL; - AET->bres.minor = MININT; - - /* - * initialize the Edge Table. - */ - ET->scanlines.next = NULL; - ET->ymax = MININT; - ET->ymin = MAXINT; - pSLLBlock->next = NULL; - - PrevPt = &pts[count - 1]; - - /* - * for each vertex in the array of points. - * In this loop we are dealing with two vertices at - * a time -- these make up one edge of the polygon. - */ - while (count--) { - CurrPt = pts++; - - /* - * find out which point is above and which is below. - */ - if (PrevPt->y > CurrPt->y) { - bottom = PrevPt, top = CurrPt; - pETEs->ClockWise = 0; - } - else { - bottom = CurrPt, top = PrevPt; - pETEs->ClockWise = 1; - } - - /* - * don't add horizontal edges to the Edge table. - */ - if (bottom->y != top->y) { - pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */ - - /* - * initialize integer edge algorithm - */ - dy = bottom->y - top->y; - BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres); - - if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) { - miFreeStorage(pSLLBlock->next); - return FALSE; - } - - ET->ymax = max(ET->ymax, PrevPt->y); - ET->ymin = min(ET->ymin, PrevPt->y); - pETEs++; - } - - PrevPt = CurrPt; - } - return TRUE; -} - -/* - * loadAET - * - * This routine moves EdgeTableEntries from the - * EdgeTable into the Active Edge Table, - * leaving them sorted by smaller x coordinate. - * - */ - -void -miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs) -{ - EdgeTableEntry *pPrevAET; - EdgeTableEntry *tmp; - - pPrevAET = AET; - AET = AET->next; - while (ETEs) { - while (AET && (AET->bres.minor < ETEs->bres.minor)) { - pPrevAET = AET; - AET = AET->next; - } - tmp = ETEs->next; - ETEs->next = AET; - if (AET) - AET->back = ETEs; - ETEs->back = pPrevAET; - pPrevAET->next = ETEs; - pPrevAET = ETEs; - - ETEs = tmp; - } -} - -/* - * computeWAET - * - * This routine links the AET by the - * nextWETE (winding EdgeTableEntry) link for - * use by the winding number rule. The final - * Active Edge Table (AET) might look something - * like: - * - * AET - * ---------- --------- --------- - * |ymax | |ymax | |ymax | - * | ... | |... | |... | - * |next |->|next |->|next |->... - * |nextWETE| |nextWETE| |nextWETE| - * --------- --------- ^-------- - * | | | - * V-------------------> V---> ... - * - */ -void -micomputeWAET(EdgeTableEntry * AET) -{ - EdgeTableEntry *pWETE; - int inside = 1; - int isInside = 0; - - AET->nextWETE = NULL; - pWETE = AET; - AET = AET->next; - while (AET) { - if (AET->ClockWise) - isInside++; - else - isInside--; - - if ((!inside && !isInside) || (inside && isInside)) { - pWETE->nextWETE = AET; - pWETE = AET; - inside = !inside; - } - AET = AET->next; - } - pWETE->nextWETE = NULL; -} - -/* - * InsertionSort - * - * Just a simple insertion sort using - * pointers and back pointers to sort the Active - * Edge Table. - * - */ - -int -miInsertionSort(EdgeTableEntry * AET) -{ - EdgeTableEntry *pETEchase; - EdgeTableEntry *pETEinsert; - EdgeTableEntry *pETEchaseBackTMP; - int changed = 0; - - AET = AET->next; - while (AET) { - pETEinsert = AET; - pETEchase = AET; - while (pETEchase->back->bres.minor > AET->bres.minor) - pETEchase = pETEchase->back; - - AET = AET->next; - if (pETEchase != pETEinsert) { - pETEchaseBackTMP = pETEchase->back; - pETEinsert->back->next = AET; - if (AET) - AET->back = pETEinsert->back; - pETEinsert->next = pETEchase; - pETEchase->back->next = pETEinsert; - pETEchase->back = pETEinsert; - pETEinsert->back = pETEchaseBackTMP; - changed = 1; - } - } - return changed; -} - -/* - * Clean up our act. - */ -void -miFreeStorage(ScanLineListBlock * pSLLBlock) -{ - ScanLineListBlock *tmpSLLBlock; - - while (pSLLBlock) { - tmpSLLBlock = pSLLBlock->next; - free(pSLLBlock); - pSLLBlock = tmpSLLBlock; - } -} diff --git a/xorg-server/mi/mipushpxl.c b/xorg-server/mi/mipushpxl.c index 9a78f4050..f6a1b5259 100644 --- a/xorg-server/mi/mipushpxl.c +++ b/xorg-server/mi/mipushpxl.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/miscrinit.c b/xorg-server/mi/miscrinit.c index 327bd1540..b53c7e41a 100644 --- a/xorg-server/mi/miscrinit.c +++ b/xorg-server/mi/miscrinit.c @@ -45,7 +45,7 @@ from The Open Group. /* We use this structure to propogate some information from miScreenInit to * miCreateScreenResources. miScreenInit allocates the structure, fills it - * in, and puts it into pScreen->devPrivate. miCreateScreenResources + * in, and puts it into pScreen->devPrivate. miCreateScreenResources * extracts the info and frees the structure. We could've accomplished the * same thing by adding fields to the screen structure, but they would have * ended up being redundant, and would have exposed this mi implementation diff --git a/xorg-server/mi/mispans.c b/xorg-server/mi/mispans.c deleted file mode 100644 index 11c8a43d0..000000000 --- a/xorg-server/mi/mispans.c +++ /dev/null @@ -1,526 +0,0 @@ -/*********************************************************** - -Copyright 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 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_DIX_CONFIG_H -#include <dix-config.h> -#endif - -#include "misc.h" -#include "pixmapstr.h" -#include "gcstruct.h" -#include "mispans.h" - -/* - -These routines maintain lists of Spans, in order to implement the -``touch-each-pixel-once'' rules of wide lines and arcs. - -Written by Joel McCormack, Summer 1989. - -*/ - -void -miInitSpanGroup(SpanGroup * spanGroup) -{ - spanGroup->size = 0; - spanGroup->count = 0; - spanGroup->group = NULL; - spanGroup->ymin = MAXSHORT; - spanGroup->ymax = MINSHORT; -} /* InitSpanGroup */ - -#define YMIN(spans) (spans->points[0].y) -#define YMAX(spans) (spans->points[spans->count-1].y) - -static void -miSubtractSpans(SpanGroup * spanGroup, Spans * sub) -{ - int i, subCount, spansCount; - int ymin, ymax, xmin, xmax; - Spans *spans; - DDXPointPtr subPt, spansPt; - int *subWid, *spansWid; - int extra; - - ymin = YMIN(sub); - ymax = YMAX(sub); - spans = spanGroup->group; - for (i = spanGroup->count; i; i--, spans++) { - if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) { - subCount = sub->count; - subPt = sub->points; - subWid = sub->widths; - spansCount = spans->count; - spansPt = spans->points; - spansWid = spans->widths; - extra = 0; - for (;;) { - while (spansCount && spansPt->y < subPt->y) { - spansPt++; - spansWid++; - spansCount--; - } - if (!spansCount) - break; - while (subCount && subPt->y < spansPt->y) { - subPt++; - subWid++; - subCount--; - } - if (!subCount) - break; - if (subPt->y == spansPt->y) { - xmin = subPt->x; - xmax = xmin + *subWid; - if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) { - ; - } - else if (xmin <= spansPt->x) { - if (xmax >= spansPt->x + *spansWid) { - memmove(spansPt, spansPt + 1, - sizeof *spansPt * (spansCount - 1)); - memmove(spansWid, spansWid + 1, - sizeof *spansWid * (spansCount - 1)); - spansPt--; - spansWid--; - spans->count--; - extra++; - } - else { - *spansWid = *spansWid - (xmax - spansPt->x); - spansPt->x = xmax; - } - } - else { - if (xmax >= spansPt->x + *spansWid) { - *spansWid = xmin - spansPt->x; - } - else { - if (!extra) { - DDXPointPtr newPt; - int *newwid; - -#define EXTRA 8 - newPt = - (DDXPointPtr) realloc(spans->points, - (spans->count + - EXTRA) * - sizeof(DDXPointRec)); - if (!newPt) - break; - spansPt = newPt + (spansPt - spans->points); - spans->points = newPt; - newwid = - (int *) realloc(spans->widths, - (spans->count + - EXTRA) * sizeof(int)); - if (!newwid) - break; - spansWid = newwid + (spansWid - spans->widths); - spans->widths = newwid; - extra = EXTRA; - } - memmove(spansPt + 1, spansPt, - sizeof *spansPt * (spansCount)); - memmove(spansWid + 1, spansWid, - sizeof *spansWid * (spansCount)); - spans->count++; - extra--; - *spansWid = xmin - spansPt->x; - spansWid++; - spansPt++; - *spansWid = *spansWid - (xmax - spansPt->x); - spansPt->x = xmax; - } - } - } - spansPt++; - spansWid++; - spansCount--; - } - } - } -} - -void -miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans) -{ - int ymin, ymax; - int spansCount; - - spansCount = spans->count; - if (spansCount > 0) { - if (spanGroup->size == spanGroup->count) { - spanGroup->size = (spanGroup->size + 8) * 2; - spanGroup->group = (Spans *) - realloc(spanGroup->group, sizeof(Spans) * spanGroup->size); - } - - spanGroup->group[spanGroup->count] = *spans; - (spanGroup->count)++; - ymin = spans->points[0].y; - if (ymin < spanGroup->ymin) - spanGroup->ymin = ymin; - ymax = spans->points[spansCount - 1].y; - if (ymax > spanGroup->ymax) - spanGroup->ymax = ymax; - if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) { - miSubtractSpans(otherGroup, spans); - } - } - else { - free(spans->points); - free(spans->widths); - } -} /* AppendSpans */ - -void -miFreeSpanGroup(SpanGroup * spanGroup) -{ - free(spanGroup->group); -} - -static void -QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans) -{ - int x; - int i, j, m; - DDXPointPtr r; - -/* Always called with numSpans > 1 */ -/* Sorts only by x, as all y should be the same */ - -#define ExchangeSpans(a, b) \ -{ \ - DDXPointRec tpt; \ - int tw; \ - \ - tpt = points[a]; points[a] = points[b]; points[b] = tpt; \ - tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ -} - - do { - if (numSpans < 9) { - /* Do insertion sort */ - int xprev; - - xprev = points[0].x; - i = 1; - do { /* while i != numSpans */ - x = points[i].x; - if (xprev > x) { - /* points[i] is out of order. Move into proper location. */ - DDXPointRec tpt; - int tw, k; - - for (j = 0; x >= points[j].x; j++) { - } - tpt = points[i]; - tw = widths[i]; - for (k = i; k != j; k--) { - points[k] = points[k - 1]; - widths[k] = widths[k - 1]; - } - points[j] = tpt; - widths[j] = tw; - x = points[i].x; - } /* if out of order */ - xprev = x; - i++; - } while (i != numSpans); - return; - } - - /* Choose partition element, stick in location 0 */ - m = numSpans / 2; - if (points[m].x > points[0].x) - ExchangeSpans(m, 0); - if (points[m].x > points[numSpans - 1].x) - ExchangeSpans(m, numSpans - 1); - if (points[m].x > points[0].x) - ExchangeSpans(m, 0); - x = points[0].x; - - /* Partition array */ - i = 0; - j = numSpans; - do { - r = &(points[i]); - do { - r++; - i++; - } while (i != numSpans && r->x < x); - r = &(points[j]); - do { - r--; - j--; - } while (x < r->x); - if (i < j) - ExchangeSpans(i, j); - } while (i < j); - - /* Move partition element back to middle */ - ExchangeSpans(0, j); - - /* Recurse */ - if (numSpans - j - 1 > 1) - QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1); - numSpans = j; - } while (numSpans > 1); -} /* QuickSortSpans */ - -static int -UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths) -{ - int newx1, newx2, oldpt, i, y; - DDXPointRec *oldPoints; - int *oldWidths; - int *startNewWidths; - -/* Always called with numSpans > 1 */ -/* Uniquify the spans, and stash them into newPoints and newWidths. Return the - number of unique spans. */ - - startNewWidths = newWidths; - - oldPoints = spans->points; - oldWidths = spans->widths; - - y = oldPoints->y; - newx1 = oldPoints->x; - newx2 = newx1 + *oldWidths; - - for (i = spans->count - 1; i != 0; i--) { - oldPoints++; - oldWidths++; - oldpt = oldPoints->x; - if (oldpt > newx2) { - /* Write current span, start a new one */ - newPoints->x = newx1; - newPoints->y = y; - *newWidths = newx2 - newx1; - newPoints++; - newWidths++; - newx1 = oldpt; - newx2 = oldpt + *oldWidths; - } - else { - /* extend current span, if old extends beyond new */ - oldpt = oldpt + *oldWidths; - if (oldpt > newx2) - newx2 = oldpt; - } - } /* for */ - - /* Write final span */ - newPoints->x = newx1; - *newWidths = newx2 - newx1; - newPoints->y = y; - - return (newWidths - startNewWidths) + 1; -} /* UniquifySpansX */ - -static void -miDisposeSpanGroup(SpanGroup * spanGroup) -{ - int i; - Spans *spans; - - for (i = 0; i < spanGroup->count; i++) { - spans = spanGroup->group + i; - free(spans->points); - free(spans->widths); - } -} - -void -miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup) -{ - int i; - Spans *spans; - Spans *yspans; - int *ysizes; - int ymin, ylength; - - /* Outgoing spans for one big call to FillSpans */ - DDXPointPtr points; - int *widths; - int count; - - if (spanGroup->count == 0) - return; - - if (spanGroup->count == 1) { - /* Already should be sorted, unique */ - spans = spanGroup->group; - (*pGC->ops->FillSpans) - (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE); - free(spans->points); - free(spans->widths); - } - else { - /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */ - /* This seems to be the fastest thing to do. I've tried sorting on - both x and y at the same time rather than creating into all those - y buckets, but it was somewhat slower. */ - - ymin = spanGroup->ymin; - ylength = spanGroup->ymax - ymin + 1; - - /* Allocate Spans for y buckets */ - yspans = malloc(ylength * sizeof(Spans)); - ysizes = malloc(ylength * sizeof(int)); - - if (!yspans || !ysizes) { - free(yspans); - free(ysizes); - miDisposeSpanGroup(spanGroup); - return; - } - - for (i = 0; i != ylength; i++) { - ysizes[i] = 0; - yspans[i].count = 0; - yspans[i].points = NULL; - yspans[i].widths = NULL; - } - - /* Go through every single span and put it into the correct bucket */ - count = 0; - for (i = 0, spans = spanGroup->group; - i != spanGroup->count; i++, spans++) { - int index; - int j; - - for (j = 0, points = spans->points, widths = spans->widths; - j != spans->count; j++, points++, widths++) { - index = points->y - ymin; - if (index >= 0 && index < ylength) { - Spans *newspans = &(yspans[index]); - - if (newspans->count == ysizes[index]) { - DDXPointPtr newpoints; - int *newwidths; - - ysizes[index] = (ysizes[index] + 8) * 2; - newpoints = (DDXPointPtr) realloc(newspans->points, - ysizes[index] * - sizeof(DDXPointRec)); - newwidths = - (int *) realloc(newspans->widths, - ysizes[index] * sizeof(int)); - if (!newpoints || !newwidths) { - for (i = 0; i < ylength; i++) { - free(yspans[i].points); - free(yspans[i].widths); - } - free(yspans); - free(ysizes); - free(newpoints); - free(newwidths); - miDisposeSpanGroup(spanGroup); - return; - } - newspans->points = newpoints; - newspans->widths = newwidths; - } - newspans->points[newspans->count] = *points; - newspans->widths[newspans->count] = *widths; - (newspans->count)++; - } /* if y value of span in range */ - } /* for j through spans */ - count += spans->count; - free(spans->points); - spans->points = NULL; - free(spans->widths); - spans->widths = NULL; - } /* for i thorough Spans */ - - /* Now sort by x and uniquify each bucket into the final array */ - points = malloc(count * sizeof(DDXPointRec)); - widths = malloc(count * sizeof(int)); - if (!points || !widths) { - for (i = 0; i < ylength; i++) { - free(yspans[i].points); - free(yspans[i].widths); - } - free(yspans); - free(ysizes); - free(points); - free(widths); - return; - } - count = 0; - for (i = 0; i != ylength; i++) { - int ycount = yspans[i].count; - - if (ycount > 0) { - if (ycount > 1) { - QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount); - count += UniquifySpansX - (&(yspans[i]), &(points[count]), &(widths[count])); - } - else { - points[count] = yspans[i].points[0]; - widths[count] = yspans[i].widths[0]; - count++; - } - free(yspans[i].points); - free(yspans[i].widths); - } - } - - (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE); - free(points); - free(widths); - free(yspans); - free(ysizes); /* use (DE)xalloc for these? */ - } - - spanGroup->count = 0; - spanGroup->ymin = MAXSHORT; - spanGroup->ymax = MINSHORT; -} diff --git a/xorg-server/mi/mispans.h b/xorg-server/mi/mispans.h deleted file mode 100644 index f3148ff19..000000000 --- a/xorg-server/mi/mispans.h +++ /dev/null @@ -1,87 +0,0 @@ -/*********************************************************** - -Copyright 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 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. - -******************************************************************/ - -#ifndef MISPANS_H -#define MISPANS_H - -typedef struct { - int count; /* number of spans */ - DDXPointPtr points; /* pointer to list of start points */ - int *widths; /* pointer to list of widths */ -} Spans; - -typedef struct { - int size; /* Total number of *Spans allocated */ - int count; /* Number of *Spans actually in group */ - Spans *group; /* List of Spans */ - int ymin, ymax; /* Min, max y values encountered */ -} SpanGroup; - -/* Initialize SpanGroup. MUST BE DONE before use. */ -extern _X_EXPORT void miInitSpanGroup(SpanGroup * /*spanGroup */ - ); - -/* Add a Spans to a SpanGroup. The spans MUST BE in y-sorted order */ -extern _X_EXPORT void miAppendSpans(SpanGroup * /*spanGroup */ , - SpanGroup * /*otherGroup */ , - Spans * /*spans */ - ); - -/* Paint a span group, insuring that each pixel is painted at most once */ -extern _X_EXPORT void miFillUniqueSpanGroup(DrawablePtr /*pDraw */ , - GCPtr /*pGC */ , - SpanGroup * /*spanGroup */ - ); - -/* Free up data in a span group. MUST BE DONE or you'll suffer memory leaks */ -extern _X_EXPORT void miFreeSpanGroup(SpanGroup * /*spanGroup */ - ); - -/* Rops which must use span groups */ -#define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2) -#define miSpansEasyRop(rop) (!miSpansCarefulRop(rop)) - -#endif /* MISPANS_H */ diff --git a/xorg-server/mi/mistruct.h b/xorg-server/mi/mistruct.h index 17f7d8329..00856f191 100644 --- a/xorg-server/mi/mistruct.h +++ b/xorg-server/mi/mistruct.h @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mivaltree.c b/xorg-server/mi/mivaltree.c index 8e4e9a9e0..ea6889fdc 100644 --- a/xorg-server/mi/mivaltree.c +++ b/xorg-server/mi/mivaltree.c @@ -27,19 +27,19 @@ 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 + * 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, + * + * 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 + * 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. - * + * 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 @@ -47,7 +47,7 @@ in this Software without prior written authorization from The Open Group. * 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. - * + * ******************************************************************/ /* The panoramix components contained the following notice */ @@ -79,7 +79,7 @@ Equipment Corporation. ******************************************************************/ - /* + /* * Aug '86: Susan Angebranndt -- original code * July '87: Adam de Boor -- substantially modified and commented * Summer '89: Joel McCormack -- so fast you wouldn't believe it possible. diff --git a/xorg-server/mi/miwideline.c b/xorg-server/mi/miwideline.c index 29ba12c69..452d74fc1 100644 --- a/xorg-server/mi/miwideline.c +++ b/xorg-server/mi/miwideline.c @@ -24,6 +24,25 @@ 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 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. */ /* Author: Keith Packard, MIT X Consortium */ @@ -52,6 +71,505 @@ from The Open Group. #include "miwideline.h" #include "mi.h" +#if 0 +#ifdef HAVE_DIX_CONFIG_H +#include <dix-config.h> +#endif + +#include "misc.h" +#include "pixmapstr.h" +#include "gcstruct.h" +#endif + +typedef struct { + int count; /* number of spans */ + DDXPointPtr points; /* pointer to list of start points */ + int *widths; /* pointer to list of widths */ +} Spans; + +typedef struct { + int size; /* Total number of *Spans allocated */ + int count; /* Number of *Spans actually in group */ + Spans *group; /* List of Spans */ + int ymin, ymax; /* Min, max y values encountered */ +} SpanGroup; + +/* Rops which must use span groups */ +#define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2) +#define miSpansEasyRop(rop) (!miSpansCarefulRop(rop)) + +/* + +These routines maintain lists of Spans, in order to implement the +``touch-each-pixel-once'' rules of wide lines and arcs. + +Written by Joel McCormack, Summer 1989. + +*/ + +static void +miInitSpanGroup(SpanGroup * spanGroup) +{ + spanGroup->size = 0; + spanGroup->count = 0; + spanGroup->group = NULL; + spanGroup->ymin = MAXSHORT; + spanGroup->ymax = MINSHORT; +} /* InitSpanGroup */ + +#define YMIN(spans) (spans->points[0].y) +#define YMAX(spans) (spans->points[spans->count-1].y) + +static void +miSubtractSpans(SpanGroup * spanGroup, Spans * sub) +{ + int i, subCount, spansCount; + int ymin, ymax, xmin, xmax; + Spans *spans; + DDXPointPtr subPt, spansPt; + int *subWid, *spansWid; + int extra; + + ymin = YMIN(sub); + ymax = YMAX(sub); + spans = spanGroup->group; + for (i = spanGroup->count; i; i--, spans++) { + if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) { + subCount = sub->count; + subPt = sub->points; + subWid = sub->widths; + spansCount = spans->count; + spansPt = spans->points; + spansWid = spans->widths; + extra = 0; + for (;;) { + while (spansCount && spansPt->y < subPt->y) { + spansPt++; + spansWid++; + spansCount--; + } + if (!spansCount) + break; + while (subCount && subPt->y < spansPt->y) { + subPt++; + subWid++; + subCount--; + } + if (!subCount) + break; + if (subPt->y == spansPt->y) { + xmin = subPt->x; + xmax = xmin + *subWid; + if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) { + ; + } + else if (xmin <= spansPt->x) { + if (xmax >= spansPt->x + *spansWid) { + memmove(spansPt, spansPt + 1, + sizeof *spansPt * (spansCount - 1)); + memmove(spansWid, spansWid + 1, + sizeof *spansWid * (spansCount - 1)); + spansPt--; + spansWid--; + spans->count--; + extra++; + } + else { + *spansWid = *spansWid - (xmax - spansPt->x); + spansPt->x = xmax; + } + } + else { + if (xmax >= spansPt->x + *spansWid) { + *spansWid = xmin - spansPt->x; + } + else { + if (!extra) { + DDXPointPtr newPt; + int *newwid; + +#define EXTRA 8 + newPt = + (DDXPointPtr) realloc(spans->points, + (spans->count + + EXTRA) * + sizeof(DDXPointRec)); + if (!newPt) + break; + spansPt = newPt + (spansPt - spans->points); + spans->points = newPt; + newwid = + (int *) realloc(spans->widths, + (spans->count + + EXTRA) * sizeof(int)); + if (!newwid) + break; + spansWid = newwid + (spansWid - spans->widths); + spans->widths = newwid; + extra = EXTRA; + } + memmove(spansPt + 1, spansPt, + sizeof *spansPt * (spansCount)); + memmove(spansWid + 1, spansWid, + sizeof *spansWid * (spansCount)); + spans->count++; + extra--; + *spansWid = xmin - spansPt->x; + spansWid++; + spansPt++; + *spansWid = *spansWid - (xmax - spansPt->x); + spansPt->x = xmax; + } + } + } + spansPt++; + spansWid++; + spansCount--; + } + } + } +} + +static void +miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans) +{ + int ymin, ymax; + int spansCount; + + spansCount = spans->count; + if (spansCount > 0) { + if (spanGroup->size == spanGroup->count) { + spanGroup->size = (spanGroup->size + 8) * 2; + spanGroup->group = (Spans *) + realloc(spanGroup->group, sizeof(Spans) * spanGroup->size); + } + + spanGroup->group[spanGroup->count] = *spans; + (spanGroup->count)++; + ymin = spans->points[0].y; + if (ymin < spanGroup->ymin) + spanGroup->ymin = ymin; + ymax = spans->points[spansCount - 1].y; + if (ymax > spanGroup->ymax) + spanGroup->ymax = ymax; + if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) { + miSubtractSpans(otherGroup, spans); + } + } + else { + free(spans->points); + free(spans->widths); + } +} /* AppendSpans */ + +static void +miFreeSpanGroup(SpanGroup * spanGroup) +{ + free(spanGroup->group); +} + +static void +QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans) +{ + int x; + int i, j, m; + DDXPointPtr r; + +/* Always called with numSpans > 1 */ +/* Sorts only by x, as all y should be the same */ + +#define ExchangeSpans(a, b) \ +{ \ + DDXPointRec tpt; \ + int tw; \ + \ + tpt = points[a]; points[a] = points[b]; points[b] = tpt; \ + tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \ +} + + do { + if (numSpans < 9) { + /* Do insertion sort */ + int xprev; + + xprev = points[0].x; + i = 1; + do { /* while i != numSpans */ + x = points[i].x; + if (xprev > x) { + /* points[i] is out of order. Move into proper location. */ + DDXPointRec tpt; + int tw, k; + + for (j = 0; x >= points[j].x; j++) { + } + tpt = points[i]; + tw = widths[i]; + for (k = i; k != j; k--) { + points[k] = points[k - 1]; + widths[k] = widths[k - 1]; + } + points[j] = tpt; + widths[j] = tw; + x = points[i].x; + } /* if out of order */ + xprev = x; + i++; + } while (i != numSpans); + return; + } + + /* Choose partition element, stick in location 0 */ + m = numSpans / 2; + if (points[m].x > points[0].x) + ExchangeSpans(m, 0); + if (points[m].x > points[numSpans - 1].x) + ExchangeSpans(m, numSpans - 1); + if (points[m].x > points[0].x) + ExchangeSpans(m, 0); + x = points[0].x; + + /* Partition array */ + i = 0; + j = numSpans; + do { + r = &(points[i]); + do { + r++; + i++; + } while (i != numSpans && r->x < x); + r = &(points[j]); + do { + r--; + j--; + } while (x < r->x); + if (i < j) + ExchangeSpans(i, j); + } while (i < j); + + /* Move partition element back to middle */ + ExchangeSpans(0, j); + + /* Recurse */ + if (numSpans - j - 1 > 1) + QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1); + numSpans = j; + } while (numSpans > 1); +} /* QuickSortSpans */ + +static int +UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths) +{ + int newx1, newx2, oldpt, i, y; + DDXPointRec *oldPoints; + int *oldWidths; + int *startNewWidths; + +/* Always called with numSpans > 1 */ +/* Uniquify the spans, and stash them into newPoints and newWidths. Return the + number of unique spans. */ + + startNewWidths = newWidths; + + oldPoints = spans->points; + oldWidths = spans->widths; + + y = oldPoints->y; + newx1 = oldPoints->x; + newx2 = newx1 + *oldWidths; + + for (i = spans->count - 1; i != 0; i--) { + oldPoints++; + oldWidths++; + oldpt = oldPoints->x; + if (oldpt > newx2) { + /* Write current span, start a new one */ + newPoints->x = newx1; + newPoints->y = y; + *newWidths = newx2 - newx1; + newPoints++; + newWidths++; + newx1 = oldpt; + newx2 = oldpt + *oldWidths; + } + else { + /* extend current span, if old extends beyond new */ + oldpt = oldpt + *oldWidths; + if (oldpt > newx2) + newx2 = oldpt; + } + } /* for */ + + /* Write final span */ + newPoints->x = newx1; + *newWidths = newx2 - newx1; + newPoints->y = y; + + return (newWidths - startNewWidths) + 1; +} /* UniquifySpansX */ + +static void +miDisposeSpanGroup(SpanGroup * spanGroup) +{ + int i; + Spans *spans; + + for (i = 0; i < spanGroup->count; i++) { + spans = spanGroup->group + i; + free(spans->points); + free(spans->widths); + } +} + +static void +miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup) +{ + int i; + Spans *spans; + Spans *yspans; + int *ysizes; + int ymin, ylength; + + /* Outgoing spans for one big call to FillSpans */ + DDXPointPtr points; + int *widths; + int count; + + if (spanGroup->count == 0) + return; + + if (spanGroup->count == 1) { + /* Already should be sorted, unique */ + spans = spanGroup->group; + (*pGC->ops->FillSpans) + (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE); + free(spans->points); + free(spans->widths); + } + else { + /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */ + /* This seems to be the fastest thing to do. I've tried sorting on + both x and y at the same time rather than creating into all those + y buckets, but it was somewhat slower. */ + + ymin = spanGroup->ymin; + ylength = spanGroup->ymax - ymin + 1; + + /* Allocate Spans for y buckets */ + yspans = malloc(ylength * sizeof(Spans)); + ysizes = malloc(ylength * sizeof(int)); + + if (!yspans || !ysizes) { + free(yspans); + free(ysizes); + miDisposeSpanGroup(spanGroup); + return; + } + + for (i = 0; i != ylength; i++) { + ysizes[i] = 0; + yspans[i].count = 0; + yspans[i].points = NULL; + yspans[i].widths = NULL; + } + + /* Go through every single span and put it into the correct bucket */ + count = 0; + for (i = 0, spans = spanGroup->group; + i != spanGroup->count; i++, spans++) { + int index; + int j; + + for (j = 0, points = spans->points, widths = spans->widths; + j != spans->count; j++, points++, widths++) { + index = points->y - ymin; + if (index >= 0 && index < ylength) { + Spans *newspans = &(yspans[index]); + + if (newspans->count == ysizes[index]) { + DDXPointPtr newpoints; + int *newwidths; + + ysizes[index] = (ysizes[index] + 8) * 2; + newpoints = (DDXPointPtr) realloc(newspans->points, + ysizes[index] * + sizeof(DDXPointRec)); + newwidths = + (int *) realloc(newspans->widths, + ysizes[index] * sizeof(int)); + if (!newpoints || !newwidths) { + for (i = 0; i < ylength; i++) { + free(yspans[i].points); + free(yspans[i].widths); + } + free(yspans); + free(ysizes); + free(newpoints); + free(newwidths); + miDisposeSpanGroup(spanGroup); + return; + } + newspans->points = newpoints; + newspans->widths = newwidths; + } + newspans->points[newspans->count] = *points; + newspans->widths[newspans->count] = *widths; + (newspans->count)++; + } /* if y value of span in range */ + } /* for j through spans */ + count += spans->count; + free(spans->points); + spans->points = NULL; + free(spans->widths); + spans->widths = NULL; + } /* for i thorough Spans */ + + /* Now sort by x and uniquify each bucket into the final array */ + points = malloc(count * sizeof(DDXPointRec)); + widths = malloc(count * sizeof(int)); + if (!points || !widths) { + for (i = 0; i < ylength; i++) { + free(yspans[i].points); + free(yspans[i].widths); + } + free(yspans); + free(ysizes); + free(points); + free(widths); + return; + } + count = 0; + for (i = 0; i != ylength; i++) { + int ycount = yspans[i].count; + + if (ycount > 0) { + if (ycount > 1) { + QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount); + count += UniquifySpansX + (&(yspans[i]), &(points[count]), &(widths[count])); + } + else { + points[count] = yspans[i].points[0]; + widths[count] = yspans[i].widths[0]; + count++; + } + free(yspans[i].points); + free(yspans[i].widths); + } + } + + (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE); + free(points); + free(widths); + free(yspans); + free(ysizes); /* use (DE)xalloc for these? */ + } + + spanGroup->count = 0; + spanGroup->ymin = MAXSHORT; + spanGroup->ymax = MINSHORT; +} + static Bool InitSpans(Spans * spans, size_t nspans) { @@ -273,7 +791,7 @@ miFillRectPolyHelper(DrawablePtr pDrawable, } } -/* static */ int +static int miPolyBuildEdge(double x0, double y0, double k, /* x0 * dy - y0 * dx */ int dx, int dy, int xi, int yi, int left, PolyEdgePtr edge) { @@ -325,7 +843,7 @@ miPolyBuildEdge(double x0, double y0, double k, /* x0 * dy - y0 * dx */ #define StepAround(v, incr, max) (((v) + (incr) < 0) ? (max - 1) : ((v) + (incr) == max) ? 0 : ((v) + (incr))) -/* static */ int +static int miPolyBuildPoly(PolyVertexPtr vertices, PolySlopePtr slopes, int count, @@ -865,7 +1383,7 @@ miRoundJoinFace(LineFacePtr face, PolyEdgePtr edge, Bool *leftEdge) return y; } -void +static void miRoundJoinClip(LineFacePtr pLeft, LineFacePtr pRight, PolyEdgePtr edge1, PolyEdgePtr edge2, int *y1, int *y2, Bool *left1, Bool *left2) @@ -886,7 +1404,7 @@ miRoundJoinClip(LineFacePtr pLeft, LineFacePtr pRight, *y2 = miRoundJoinFace(pRight, edge2, left2); } -int +static int miRoundCapClip(LineFacePtr face, Bool isInt, PolyEdgePtr edge, Bool *leftEdge) { int y; diff --git a/xorg-server/mi/miwideline.h b/xorg-server/mi/miwideline.h index 110541120..88bc3d6c8 100644 --- a/xorg-server/mi/miwideline.h +++ b/xorg-server/mi/miwideline.h @@ -28,7 +28,6 @@ from The Open Group. /* Author: Keith Packard, MIT X Consortium */ -#include "mispans.h" #include "mifpoly.h" /* for ICEIL */ /* @@ -92,28 +91,3 @@ typedef struct _LineFace { ValidateGC (pDrawable, pGC); \ } \ } - -extern _X_EXPORT void miRoundJoinClip(LineFacePtr /*pLeft */ , - LineFacePtr /*pRight */ , - PolyEdgePtr /*edge1 */ , - PolyEdgePtr /*edge2 */ , - int * /*y1 */ , - int * /*y2 */ , - Bool * /*left1 */ , - Bool * /*left2 */ - ); - -extern _X_EXPORT int miRoundCapClip(LineFacePtr /*face */ , - Bool /*isInt */ , - PolyEdgePtr /*edge */ , - Bool * /*leftEdge */ - ); - -extern _X_EXPORT int miPolyBuildEdge(double x0, double y0, double k, int dx, - int dy, int xi, int yi, int left, - PolyEdgePtr edge); -extern _X_EXPORT int miPolyBuildPoly(PolyVertexPtr vertices, - PolySlopePtr slopes, int count, int xi, - int yi, PolyEdgePtr left, - PolyEdgePtr right, int *pnleft, - int *pnright, int *h); diff --git a/xorg-server/mi/miwindow.c b/xorg-server/mi/miwindow.c index 0cf50465a..a1af3a770 100644 --- a/xorg-server/mi/miwindow.c +++ b/xorg-server/mi/miwindow.c @@ -27,13 +27,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mizerclip.c b/xorg-server/mi/mizerclip.c index d05bf6788..0ae964190 100644 --- a/xorg-server/mi/mizerclip.c +++ b/xorg-server/mi/mizerclip.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 diff --git a/xorg-server/mi/mizerline.c b/xorg-server/mi/mizerline.c index f30e01239..5a2447014 100644 --- a/xorg-server/mi/mizerline.c +++ b/xorg-server/mi/mizerline.c @@ -26,13 +26,13 @@ Copyright 1987 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, +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 +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. +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 @@ -235,7 +235,7 @@ miZeroLine(DrawablePtr pDraw, GCPtr pGC, int mode, /* Origin or Previous */ length = abs(new_x2 - new_x1); /* if we've clipped the endpoint, always draw the full length - * of the segment, because then the capstyle doesn't matter + * of the segment, because then the capstyle doesn't matter */ if (pt2_clipped) length++; @@ -295,7 +295,7 @@ miZeroLine(DrawablePtr pDraw, GCPtr pGC, int mode, /* Origin or Previous */ length = abs(new_y2 - new_y1); /* if we've clipped the endpoint, always draw the full length - * of the segment, because then the capstyle doesn't matter + * of the segment, because then the capstyle doesn't matter */ if (pt2_clipped) length++; |