xserver git update 9/5/2010

1 files changed, 3590 insertions, 3686 deletions

diff --git a/xorg-server/mi/miarc.c b/xorg-server/mi/miarc.c
index 5fd1a678a..d182d2592 100644
--- a/xorg-server/mi/miarc.c
+++ b/xorg-server/mi/miarc.c
@@ -1,3686 +1,3590 @@
-/***********************************************************
-
-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.
-
-******************************************************************/
-/* Author: Keith Packard and Bob Scheifler */
-/* Warning: this code is toxic, do not dally very long here. */
-
-#ifdef HAVE_DIX_CONFIG_H
-#include <dix-config.h>
-#endif
-
-#include <math.h>
-#include <X11/X.h>
-#include <X11/Xprotostr.h>
-#include "misc.h"
-#include "gcstruct.h"
-#include "scrnintstr.h"
-#include "pixmapstr.h"
-#include "windowstr.h"
-#include "mifpoly.h"
-#include "mi.h"
-#include "mifillarc.h"
-#include <X11/Xfuncproto.h>
-
-static double miDsin(double a);
-static double miDcos(double a);
-static double miDasin(double v);
-static double miDatan2(double dy, double dx);
-
-#ifndef HAVE_CBRT
-static double
-cbrt(double x)
-{
-    if (x > 0.0)
-	return pow(x, 1.0/3.0);
-    else
-	return -pow(-x, 1.0/3.0);
-}
-#endif
-
-/*
- * some interesting sematic interpretation of the protocol:
- *
- * 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
- *  first segment, when no caps are drawn)
- *
- * double dash arcs are drawn in two parts, first the
- *  odd dashes (drawn in background) then the even dashes
- *  (drawn in foreground).  This means that overlapping
- *  sections of foreground/background are drawn twice,
- *  first in background then in foreground.  The double-draw
- *  occurs even when the function uses the destination values
- *  (e.g. xor mode).  This is the same way the wide-line
- *  code works and should be "fixed".
- *
- */
-
-#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;
-};
-
-struct ibound {
-	int	min, max;
-};
-
-#define boundedLe(value, bounds)\
-	((bounds).min <= (value) && (value) <= (bounds).max)
-
-struct line {
-	double	m, b;
-	int	valid;
-};
-
-#define intersectLine(y,line) (line.m * (y) + line.b)
-
-/*
- * these are all y value bounds
- */
-
-struct arc_bound {
-	struct bound	ellipse;
-	struct bound	inner;
-	struct bound	outer;
-	struct bound	right;
-	struct bound	left;
-	struct ibound	inneri;
-	struct ibound	outeri;
-};
-
-struct accelerators {
-	double		tail_y;
-	double		h2;
-	double		w2;
-	double		h4;
-	double		w4;
-	double		h2mw2;
-	double		h2l;
-	double		w2l;
-	double		fromIntX;
-	double		fromIntY;
-	struct line	left, right;
-	int		yorgu;
-	int		yorgl;
-	int		xorg;
-};
-
-struct arc_def {
-	double	w, h, l;
-	double	a0, a1;
-};
-
-# define todeg(xAngle)	(((double) (xAngle)) / 64.0)
-
-# define RIGHT_END	0
-# define LEFT_END	1
-
-typedef struct _miArcJoin {
-	int	arcIndex0, arcIndex1;
-	int	phase0, phase1;
-	int	end0, end1;
-} miArcJoinRec, *miArcJoinPtr;
-
-typedef struct _miArcCap {
-	int		arcIndex;
-	int		end;		
-} miArcCapRec, *miArcCapPtr;
-
-typedef struct _miArcFace {
-	SppPointRec	clock;
-	SppPointRec	center;
-	SppPointRec	counterClock;
-} miArcFaceRec, *miArcFacePtr;
-
-typedef struct _miArcData {
-	xArc		arc;
-	int		render;		/* non-zero means render after drawing */
-	int		join;		/* related join */
-	int		cap;		/* related cap */
-	int		selfJoin;	/* final dash meets first dash */
-	miArcFaceRec	bounds[2];
-	double		x0, y0, x1, y1;
-} miArcDataRec, *miArcDataPtr;
-
-/*
- * This is an entire sequence of arcs, computed and categorized according
- * to operation.  miDashArcs generates either one or two of these.
- */
-
-typedef struct _miPolyArc {
-	int		narcs;
-	miArcDataPtr	arcs;
-	int		ncaps;
-	miArcCapPtr	caps;
-	int		njoins;
-	miArcJoinPtr	joins;
-} miPolyArcRec, *miPolyArcPtr;
-
-#define GCValsFunction		0
-#define GCValsForeground 	1
-#define GCValsBackground 	2
-#define GCValsLineWidth 	3
-#define GCValsCapStyle 		4
-#define GCValsJoinStyle		5
-#define GCValsMask		(GCFunction | GCForeground | GCBackground | \
-				 GCLineWidth | GCCapStyle | GCJoinStyle)
-static CARD32 gcvals[6];
-
-static void fillSpans(DrawablePtr pDrawable, GCPtr pGC);
-static void newFinalSpan(int y, int xmin, int xmax);
-static void drawArc(xArc *tarc, int l, int a0, int a1, miArcFacePtr right,
-		    miArcFacePtr left);
-static void drawZeroArc(DrawablePtr pDraw, GCPtr pGC, xArc *tarc, int lw,
-			miArcFacePtr left, miArcFacePtr right);
-static void miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,
-		      miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,
-		      double xFtransLeft, double yFtransLeft,
-		      int xOrgRight, int yOrgRight,
-		      double xFtransRight, double yFtransRight);
-static void miArcCap(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pFace,
-		     int end, int xOrg, int yOrg, double xFtrans,
-		     double yFtrans);
-static void miRoundCap(DrawablePtr pDraw, GCPtr pGC, SppPointRec pCenter,
-		       SppPointRec pEnd, SppPointRec pCorner,
-		       SppPointRec pOtherCorner, int fLineEnd,
-		       int xOrg, int yOrg, double xFtrans, double yFtrans);
-static void miFreeArcs(miPolyArcPtr arcs, GCPtr pGC);
-static miPolyArcPtr miComputeArcs(xArc *parcs, int narcs, GCPtr pGC);
-static int miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts);
-
-# define CUBED_ROOT_2	1.2599210498948732038115849718451499938964
-# define CUBED_ROOT_4	1.5874010519681993173435330390930175781250
-
-/*
- * draw one segment of the arc using the arc spans generation routines
- */
-
-static void
-miArcSegment(
-    DrawablePtr   pDraw,
-    GCPtr         pGC,
-    xArc          tarc,
-    miArcFacePtr	right,
-    miArcFacePtr	left)
-{
-    int l = pGC->lineWidth;
-    int a0, a1, startAngle, endAngle;
-    miArcFacePtr temp;
-
-    if (!l)
-	l = 1;
-
-    if (tarc.width == 0 || tarc.height == 0) {
-    	drawZeroArc (pDraw, pGC, &tarc, l, left, right);
-	return;
-    }
-
-    if (pGC->miTranslate) {
-	tarc.x += pDraw->x;
-	tarc.y += pDraw->y;
-    }
-
-    a0 = tarc.angle1;
-    a1 = tarc.angle2;
-    if (a1 > FULLCIRCLE)
-	a1 = FULLCIRCLE;
-    else if (a1 < -FULLCIRCLE)
-	a1 = -FULLCIRCLE;
-    if (a1 < 0) {
-    	startAngle = a0 + a1;
-	endAngle = a0;
-	temp = right;
-	right = left;
-	left = temp;
-    } else {
-	startAngle = a0;
-	endAngle = a0 + a1;
-    }
-    /*
-     * bounds check the two angles
-     */
-    if (startAngle < 0)
-	startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
-    if (startAngle >= FULLCIRCLE)
-	startAngle = startAngle % FULLCIRCLE;
-    if (endAngle < 0)
-	endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;
-    if (endAngle > FULLCIRCLE)
-	endAngle = (endAngle-1) % FULLCIRCLE + 1;
-    if ((startAngle == endAngle) && a1) {
-	startAngle = 0;
-	endAngle = FULLCIRCLE;
-    }
-
-    drawArc (&tarc, l, startAngle, endAngle, right, left);
-}
-
-/*
-
-Three equations combine to describe the boundaries of the arc
-
-x^2/w^2 + y^2/h^2 = 1			ellipse itself
-(X-x)^2 + (Y-y)^2 = r^2			circle at (x, y) on the ellipse
-(Y-y) = (X-x)*w^2*y/(h^2*x)		normal at (x, y) on the ellipse
-
-These lead to a quartic relating Y and y
-
-y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2
-    - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0
-
-The reducible cubic obtained from this quartic is
-
-z^3 - (3N)z^2 - 2V = 0
-
-where
-
-N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6
-V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)
-
-Let
-
-t = z - N
-p = -N^2
-q = -N^3 - V
-
-Then we get
-
-t^3 + 3pt + 2q = 0
-
-The discriminant of this cubic is
-
-D = q^2 + p^3
-
-When D > 0, a real root is obtained as
-
-z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))
-
-When D < 0, a real root is obtained as
-
-z = N - 2m*cos(acos(-q/m^3)/3)
-
-where
-
-m = sqrt(|p|) * sign(q)
-
-Given a real root Z of the cubic, the roots of the quartic are the roots
-of the two quadratics
-
-y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0
-
-where 
-
-A = +/- sqrt(8Z + b^2 - 4c)
-b, c, d are the cubic, quadratic, and linear coefficients of the quartic
-
-Some experimentation is then required to determine which solutions
-correspond to the inner and outer boundaries.
-
-*/
-
-typedef struct {
-    short lx, lw, rx, rw;
-} miArcSpan;
-
-typedef struct {
-    miArcSpan *spans;
-    int count1, count2, k;
-    char top, bot, hole;
-} miArcSpanData;
-
-typedef struct {
-    unsigned long lrustamp;
-    unsigned short lw;
-    unsigned short width, height;
-    miArcSpanData *spdata;
-} arcCacheRec;
-
-#define CACHESIZE 25
-
-static void drawQuadrant(struct arc_def *def, struct accelerators *acc,
-			 int a0, int a1, int mask, miArcFacePtr right,
-			 miArcFacePtr left, miArcSpanData *spdata);
-
-static arcCacheRec arcCache[CACHESIZE];
-static unsigned long lrustamp;
-static arcCacheRec *lastCacheHit = &arcCache[0];
-static RESTYPE cacheType;
-
-static int
-miFreeArcCache (pointer data, XID id)
-{
-    int k;
-    arcCacheRec *cent;
-
-    if (id)
-	cacheType = 0;
-
-    for (k = CACHESIZE, cent = &arcCache[0]; --k >= 0; cent++)
-    {
-	if (cent->spdata)
-	{
-	    cent->lrustamp = 0;
-	    cent->lw = 0;
-	    xfree(cent->spdata);
-	    cent->spdata = NULL;
-	}
-    }
-    lrustamp = 0;
-    return Success;
-}
-
-static void
-miComputeCircleSpans(
-    int lw,
-    xArc *parc,
-    miArcSpanData *spdata)
-{
-    miArcSpan *span;
-    int doinner;
-    int x, y, e;
-    int xk, yk, xm, ym, dx, dy;
-    int slw, inslw;
-    int inx = 0, iny, ine = 0;
-    int inxk = 0, inyk = 0, inxm = 0, inym = 0;
-
-    doinner = -lw;
-    slw = parc->width - doinner;
-    y = parc->height >> 1;
-    dy = parc->height & 1;
-    dx = 1 - dy;
-    MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);
-    inslw = parc->width + doinner;
-    if (inslw > 0)
-    {
-	spdata->hole = spdata->top;
-	MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);
-    }
-    else
-    {
-	spdata->hole = FALSE;
-	doinner = -y;
-    }
-    spdata->count1 = -doinner - spdata->top;
-    spdata->count2 = y + doinner;
-    span = spdata->spans;
-    while (y)
-    {
-	MIFILLARCSTEP(slw);
-	span->lx = dy - x;
-	if (++doinner <= 0)
- 	{
-	    span->lw = slw;
-	    span->rx = 0;
-	    span->rw = span->lx + slw;
-	}
-	else
-	{
-	    MIFILLINARCSTEP(inslw);
-	    span->lw = x - inx;
-	    span->rx = dy - inx + inslw;
-	    span->rw = inx - x + slw - inslw;
-	}
-	span++;
-    }
-    if (spdata->bot)
-    {
-	if (spdata->count2)
-	    spdata->count2--;
-	else
-	{
-	    if (lw > (int)parc->height)
-		span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);
-	    else
-		span[-1].rw = 0;
-	    spdata->count1--;
-	}
-    }
-}
-
-static void
-miComputeEllipseSpans(
-    int lw,
-    xArc *parc,
-    miArcSpanData *spdata)
-{
-    miArcSpan *span;
-    double w, h, r, xorg;
-    double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
-    double A, T, b, d, x, y, t, inx, outx = 0.0, hepp, hepm;
-    int flip, solution;
-
-    w = (double)parc->width / 2.0;
-    h = (double)parc->height / 2.0;
-    r = lw / 2.0;
-    rs = r * r;
-    Hs = h * h;
-    WH = w * w - Hs;
-    Nk = w * r;
-    Vk = (Nk * Hs) / (WH + WH);
-    Hf = Hs * Hs;
-    Nk = (Hf - Nk * Nk) / WH;
-    Fk = Hf / WH;
-    hepp = h + EPSILON;
-    hepm = h - EPSILON;
-    K = h + ((lw - 1) >> 1);
-    span = spdata->spans;
-    if (parc->width & 1)
-	xorg = .5;
-    else
-	xorg = 0.0;
-    if (spdata->top)
-    {
-	span->lx = 0;
-	span->lw = 1;
-	span++;
-    }
-    spdata->count1 = 0;
-    spdata->count2 = 0;
-    spdata->hole = (spdata->top &&
-		 (int)parc->height * lw <= (int)(parc->width * parc->width) &&
-		    lw < (int)parc->height);
-    for (; K > 0.0; K -= 1.0)
-    {
-	N = (K * K + Nk) / 6.0;
-	Nc = N * N * N;
-	Vr = Vk * K;
-	t = Nc + Vr * Vr;
-	d = Nc + t;
-	if (d < 0.0) {
-	    d = Nc;
-	    b = N;
-	    if ( (b < 0.0) == (t < 0.0) )
-	    {
-		b = -b;
-		d = -d;
-	    }
-	    Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
-	    if ( (Z < 0.0) == (Vr < 0.0) )
-		flip = 2;
-	    else
-		flip = 1;
-	}
-	else
-	{
-	    d = Vr * sqrt(d);
-	    Z = N + cbrt(t + d) + cbrt(t - d);
-	    flip = 0;
-	}
-	A = sqrt((Z + Z) - Nk);
-	T = (Fk - Z) * K / A;
-	inx = 0.0;
-	solution = FALSE;
-	b = -A + K;
-	d = b * b - 4 * (Z + T);
-	if (d >= 0)
-	{
-	    d = sqrt(d);
-	    y = (b + d) / 2;
-	    if ((y >= 0.0) && (y < hepp))
-	    {
-		solution = TRUE;
-		if (y > hepm)
-		    y = h;
-		t = y / h;
-		x = w * sqrt(1 - (t * t));
-		t = K - y;
-		if (rs - (t * t) >= 0)
-		   t = sqrt(rs - (t * t));
-		else
-		   t = 0;
-		if (flip == 2)
-		    inx = x - t;
-		else
-		    outx = x + t;
-	    }
-	}
-	b = A + K;
-	d = b * b - 4 * (Z - T);
-	/* Because of the large magnitudes involved, we lose enough precision
-	 * that sometimes we end up with a negative value near the axis, when
-	 * it should be positive.  This is a workaround.
-	 */
-	if (d < 0 && !solution)
-	    d = 0.0;
-	if (d >= 0) {
-	    d = sqrt(d);
-	    y = (b + d) / 2;
-	    if (y < hepp)
-	    {
-		if (y > hepm)
-		    y = h;
-		t = y / h;
-		x = w * sqrt(1 - (t * t));
-		t = K - y;
-		if (rs - (t * t) >= 0)
-		   inx = x - sqrt(rs - (t * t));
-		else
-		   inx = x;
-	    }
-	    y = (b - d) / 2;
-	    if (y >= 0.0)
-	    {
-		if (y > hepm)
-		    y = h;
-		t = y / h;
-		x = w * sqrt(1 - (t * t));
-		t = K - y;
-		if (rs - (t * t) >= 0)
-		   t = sqrt(rs - (t * t));
-		else 
-		   t = 0;
-		if (flip == 1)
-		    inx = x - t;
-		else
-		    outx = x + t;
-	    }
-	}
-	span->lx = ICEIL(xorg - outx);
-	if (inx <= 0.0)
-	{
-	    spdata->count1++;
-	    span->lw = ICEIL(xorg + outx) - span->lx;
-	    span->rx = ICEIL(xorg + inx);
-	    span->rw = -ICEIL(xorg - inx);
-	}
-	else
-	{
-	    spdata->count2++;
-	    span->lw = ICEIL(xorg - inx) - span->lx;
-	    span->rx = ICEIL(xorg + inx);
-	    span->rw = ICEIL(xorg + outx) - span->rx;
-	}
-	span++;
-    }
-    if (spdata->bot)
-    {
-	outx = w + r;
-	if (r >= h && r <= w)
-	    inx = 0.0;
-	else if (Nk < 0.0 && -Nk < Hs)
-	{
-	    inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
-	    if (inx > w - r)
-		inx = w - r;
-	}
-	else
-	    inx = w - r;
-	span->lx = ICEIL(xorg - outx);
-	if (inx <= 0.0)
-	{
-	    span->lw = ICEIL(xorg + outx) - span->lx;
-	    span->rx = ICEIL(xorg + inx);
-	    span->rw = -ICEIL(xorg - inx);
-	}
-	else
-	{
-	    span->lw = ICEIL(xorg - inx) - span->lx;
-	    span->rx = ICEIL(xorg + inx);
-	    span->rw = ICEIL(xorg + outx) - span->rx;
-	}
-    }
-    if (spdata->hole)
-    {
-	span = &spdata->spans[spdata->count1];
-	span->lw = -span->lx;
-	span->rx = 1;
-	span->rw = span->lw;
-	spdata->count1--;
-	spdata->count2++;
-    }
-}
-
-static double
-tailX(
-    double K,
-    struct arc_def *def,
-    struct arc_bound *bounds,
-    struct accelerators *acc)
-{
-    double w, h, r;
-    double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;
-    double A, T, b, d, x, y, t, hepp, hepm;
-    int flip, solution;
-    double xs[2];
-    double *xp;
-
-    w = def->w;
-    h = def->h;
-    r = def->l;
-    rs = r * r;
-    Hs = acc->h2;
-    WH = -acc->h2mw2;
-    Nk = def->w * r;
-    Vk = (Nk * Hs) / (WH + WH);
-    Hf = acc->h4;
-    Nk = (Hf - Nk * Nk) / WH;
-    if (K == 0.0) {
-	if (Nk < 0.0 && -Nk < Hs) {
-	    xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);
-	    xs[1] = w - r;
-	    if (acc->left.valid && boundedLe(K, bounds->left) &&
-		!boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
-		return xs[1];
-	    if (acc->right.valid && boundedLe(K, bounds->right) &&
-		!boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
-		return xs[1];
-	    return xs[0];
-	}
-	return w - r;
-    }
-    Fk = Hf / WH;
-    hepp = h + EPSILON;
-    hepm = h - EPSILON;
-    N = (K * K + Nk) / 6.0;
-    Nc = N * N * N;
-    Vr = Vk * K;
-    xp = xs;
-    xs[0] = 0.0;
-    t = Nc + Vr * Vr;
-    d = Nc + t;
-    if (d < 0.0) {
-	d = Nc;
-	b = N;
-	if ( (b < 0.0) == (t < 0.0) )
-	{
-	    b = -b;
-	    d = -d;
-	}
-	Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);
-	if ( (Z < 0.0) == (Vr < 0.0) )
-	    flip = 2;
-	else
-	    flip = 1;
-    }
-    else
-    {
-	d = Vr * sqrt(d);
-	Z = N + cbrt(t + d) + cbrt(t - d);
-	flip = 0;
-    }
-    A = sqrt((Z + Z) - Nk);
-    T = (Fk - Z) * K / A;
-    solution = FALSE;
-    b = -A + K;
-    d = b * b - 4 * (Z + T);
-    if (d >= 0 && flip == 2)
-    {
-	d = sqrt(d);
-	y = (b + d) / 2;
-	if ((y >= 0.0) && (y < hepp))
-	{
-	    solution = TRUE;
-	    if (y > hepm)
-		y = h;
-	    t = y / h;
-	    x = w * sqrt(1 - (t * t));
-	    t = K - y;
-	    if (rs - (t * t) >= 0)
-	       t = sqrt(rs - (t * t));
-	    else
-	       t = 0;
-	    *xp++ = x - t;
-	}
-    }
-    b = A + K;
-    d = b * b - 4 * (Z - T);
-    /* Because of the large magnitudes involved, we lose enough precision
-     * that sometimes we end up with a negative value near the axis, when
-     * it should be positive.  This is a workaround.
-     */
-    if (d < 0 && !solution)
-	d = 0.0;
-    if (d >= 0) {
-	d = sqrt(d);
-	y = (b + d) / 2;
-	if (y < hepp)
-	{
-	    if (y > hepm)
-		y = h;
-	    t = y / h;
-	    x = w * sqrt(1 - (t * t));
-	    t = K - y;
-	    if (rs - (t * t) >= 0)
-	       *xp++ = x - sqrt(rs - (t * t));
-	    else
-	       *xp++ = x;
-	}
-	y = (b - d) / 2;
-	if (y >= 0.0 && flip == 1)
-	{
-	    if (y > hepm)
-		y = h;
-	    t = y / h;
-	    x = w * sqrt(1 - (t * t));
-	    t = K - y;
-	    if (rs - (t * t) >= 0)
-	       t = sqrt(rs - (t * t));
-	    else
-	       t = 0;
-	    *xp++ = x - t;
-	}
-    }
-    if (xp > &xs[1]) {
-	if (acc->left.valid && boundedLe(K, bounds->left) &&
-	    !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)
-	    return xs[1];
-	if (acc->right.valid && boundedLe(K, bounds->right) &&
-	    !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)
-	    return xs[1];
-    }
-    return xs[0];
-}
-
-static miArcSpanData *
-miComputeWideEllipse(
-    int  lw,
-    xArc *parc,
-    Bool *mustFree)
-{
-    miArcSpanData *spdata;
-    arcCacheRec *cent, *lruent;
-    int k;
-    arcCacheRec fakeent;
-
-    if (!lw)
-	lw = 1;
-    if (parc->height <= 1500)
-    {
-	*mustFree = FALSE;
-	cent = lastCacheHit;
-	if (cent->lw == lw &&
-	    cent->width == parc->width && cent->height == parc->height)
-	{
-	    cent->lrustamp = ++lrustamp;
-	    return cent->spdata;
-	}
-	lruent = &arcCache[0];
-	for (k = CACHESIZE, cent = lruent; --k >= 0; cent++)
-	{
-	    if (cent->lw == lw &&
-		cent->width == parc->width && cent->height == parc->height)
-	    {
-		cent->lrustamp = ++lrustamp;
-		lastCacheHit = cent;
-		return cent->spdata;
-	    }
-	    if (cent->lrustamp < lruent->lrustamp)
-		lruent = cent;
-	}
-	if (!cacheType)
-	{
-	    cacheType = CreateNewResourceType(miFreeArcCache, "miArcCache");
-	    (void) AddResource(FakeClientID(0), cacheType, NULL);
-	}
-    } else {
-	lruent = &fakeent;
-	lruent->spdata = NULL;
-	*mustFree = TRUE;
-    }
-    k = (parc->height >> 1) + ((lw - 1) >> 1);
-    spdata = lruent->spdata;
-    if (!spdata || spdata->k != k)
-    {
-	if (spdata)
-	    xfree(spdata);
-	spdata = xalloc(sizeof(miArcSpanData) + sizeof(miArcSpan) * (k + 2));
-	lruent->spdata = spdata;
-	if (!spdata)
-	{
-	    lruent->lrustamp = 0;
-	    lruent->lw = 0;
-	    return spdata;
-	}
-	spdata->spans = (miArcSpan *)(spdata + 1);
-	spdata->k = k;
-    }
-    spdata->top = !(lw & 1) && !(parc->width & 1);
-    spdata->bot = !(parc->height & 1);
-    lruent->lrustamp = ++lrustamp;
-    lruent->lw = lw;
-    lruent->width = parc->width;
-    lruent->height = parc->height;
-    if (lruent != &fakeent)
-	lastCacheHit = lruent;
-    if (parc->width == parc->height)
-	miComputeCircleSpans(lw, parc, spdata);
-    else
-	miComputeEllipseSpans(lw, parc, spdata);
-    return spdata;
-}
-
-static void
-miFillWideEllipse(
-    DrawablePtr	pDraw,
-    GCPtr	pGC,
-    xArc	*parc)
-{
-    DDXPointPtr points;
-    DDXPointPtr pts;
-    int *widths;
-    int *wids;
-    miArcSpanData *spdata;
-    Bool mustFree;
-    miArcSpan *span;
-    int xorg, yorgu, yorgl;
-    int n;
-
-    yorgu = parc->height + pGC->lineWidth;
-    n = (sizeof(int) * 2) * yorgu;
-    widths = xalloc(n + (sizeof(DDXPointRec) * 2) * yorgu);
-    if (!widths)
-	return;
-    points = (DDXPointPtr)((char *)widths + n);
-    spdata = miComputeWideEllipse((int)pGC->lineWidth, parc, &mustFree);
-    if (!spdata)
-    {
-	xfree(widths);
-	return;
-    }
-    pts = points;
-    wids = widths;
-    span = spdata->spans;
-    xorg = parc->x + (parc->width >> 1);
-    yorgu = parc->y + (parc->height >> 1);
-    yorgl = yorgu + (parc->height & 1);
-    if (pGC->miTranslate)
-    {
-	xorg += pDraw->x;
-	yorgu += pDraw->y;
-	yorgl += pDraw->y;
-    }
-    yorgu -= spdata->k;
-    yorgl += spdata->k;
-    if (spdata->top)
-    {
-	pts->x = xorg;
-	pts->y = yorgu - 1;
-	pts++;
-	*wids++ = 1;
-	span++;
-    }
-    for (n = spdata->count1; --n >= 0; )
-    {
-	pts[0].x = xorg + span->lx;
-	pts[0].y = yorgu;
-	wids[0] = span->lw;
-	pts[1].x = pts[0].x;
-	pts[1].y = yorgl;
-	wids[1] = wids[0];
-	yorgu++;
-	yorgl--;
-	pts += 2;
-	wids += 2;
-	span++;
-    }
-    if (spdata->hole)
-    {
-	pts[0].x = xorg;
-	pts[0].y = yorgl;
-	wids[0] = 1;
-	pts++;
-	wids++;
-    }
-    for (n = spdata->count2; --n >= 0; )
-    {
-	pts[0].x = xorg + span->lx;
-	pts[0].y = yorgu;
-	wids[0] = span->lw;
-	pts[1].x = xorg + span->rx;
-	pts[1].y = pts[0].y;
-	wids[1] = span->rw;
-	pts[2].x = pts[0].x;
-	pts[2].y = yorgl;
-	wids[2] = wids[0];
-	pts[3].x = pts[1].x;
-	pts[3].y = pts[2].y;
-	wids[3] = wids[1];
-	yorgu++;
-	yorgl--;
-	pts += 4;
-	wids += 4;
-	span++;
-    }
-    if (spdata->bot)
-    {
-	if (span->rw <= 0)
-	{
-	    pts[0].x = xorg + span->lx;
-	    pts[0].y = yorgu;
-	    wids[0] = span->lw;
-	    pts++;
-	    wids++;
-	}	
-	else
-	{
-	    pts[0].x = xorg + span->lx;
-	    pts[0].y = yorgu;
-	    wids[0] = span->lw;
-	    pts[1].x = xorg + span->rx;
-	    pts[1].y = pts[0].y;
-	    wids[1] = span->rw;
-	    pts += 2;
-	    wids += 2;
-	}
-    }
-    if (mustFree)
-	xfree(spdata);
-    (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);
-
-    xfree(widths);
-}
-
-/*
- * miPolyArc strategy:
- *
- * If arc is zero width and solid, we don't have to worry about the rasterop
- * or join styles.  For wide solid circles, we use a fast integer algorithm.
- * For wide solid ellipses, we use special case floating point code.
- * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then
- * draw using pGCTo and pDrawTo.  If the raster-op was "tricky," that is,
- * if it involves the destination, then we use PushPixels to move the bits
- * from the scratch drawable to pDraw. (See the wide line code for a
- * fuller explanation of this.)
- */
-
-void
-miPolyArc(DrawablePtr pDraw, GCPtr pGC, int narcs, xArc *parcs)
-{
-    int		i;
-    xArc	*parc;
-    int		xMin, xMax, yMin, yMax;
-    int		pixmapWidth = 0, pixmapHeight = 0;
-    int		xOrg = 0, yOrg = 0;
-    int		width;
-    Bool	fTricky;
-    DrawablePtr	pDrawTo;
-    CARD32	fg, bg;
-    GCPtr	pGCTo;
-    miPolyArcPtr polyArcs;
-    int		cap[2], join[2];
-    int		iphase;
-    int		halfWidth;
-
-    width = pGC->lineWidth;
-    if(width == 0 && pGC->lineStyle == LineSolid)
-    {
-	for(i = narcs, parc = parcs; --i >= 0; parc++)
-	    miArcSegment( pDraw, pGC, *parc,
- 	    (miArcFacePtr) 0, (miArcFacePtr) 0 );
-	fillSpans (pDraw, pGC);
-    }
-    else 
-    {
-	if ((pGC->lineStyle == LineSolid) && narcs)
-	{
-	    while (parcs->width && parcs->height &&
-		   (parcs->angle2 >= FULLCIRCLE ||
-		    parcs->angle2 <= -FULLCIRCLE))
-	    {
-		miFillWideEllipse(pDraw, pGC, parcs);
-		if (!--narcs)
-		    return;
-		parcs++;
-	    }
-	}
-
-	/* Set up pDrawTo and pGCTo based on the rasterop */
-	switch(pGC->alu)
-	{
-	  case GXclear:		/* 0 */
-	  case GXcopy:		/* src */
-	  case GXcopyInverted:	/* NOT src */
-	  case GXset:		/* 1 */
-	    fTricky = FALSE;
-	    pDrawTo = pDraw;
-	    pGCTo = pGC;
-	    break;
-	  default:
-	    fTricky = TRUE;
-
-	    /* find bounding box around arcs */
-	    xMin = yMin = MAXSHORT;
-	    xMax = yMax = MINSHORT;
-
-	    for(i = narcs, parc = parcs; --i >= 0; parc++)
-	    {
-		xMin = min (xMin, parc->x);
-		yMin = min (yMin, parc->y);
-		xMax = max (xMax, (parc->x + (int) parc->width));
-		yMax = max (yMax, (parc->y + (int) parc->height));
-	    }
-
-	    /* expand box to deal with line widths */
-	    halfWidth = (width + 1)/2;
-	    xMin -= halfWidth;
-	    yMin -= halfWidth;
-	    xMax += halfWidth;
-	    yMax += halfWidth;
-
-	    /* compute pixmap size; limit it to size of drawable */
-	    xOrg = max(xMin, 0);
-	    yOrg = max(yMin, 0);
-	    pixmapWidth = min(xMax, pDraw->width) - xOrg;
-	    pixmapHeight = min(yMax, pDraw->height) - yOrg;
-
-	    /* if nothing left, return */
-	    if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;
-
-	    for(i = narcs, parc = parcs; --i >= 0; parc++)
-	    {
-		parc->x -= xOrg;
-		parc->y -= yOrg;
-	    }
-	    if (pGC->miTranslate)
-	    {
-		xOrg += pDraw->x;
-		yOrg += pDraw->y;
-	    }
-
-	    /* set up scratch GC */
-
-	    pGCTo = GetScratchGC(1, pDraw->pScreen);
-	    if (!pGCTo)
-		return;
-	    gcvals[GCValsFunction] = GXcopy;
-	    gcvals[GCValsForeground] = 1;
-	    gcvals[GCValsBackground] = 0;
-	    gcvals[GCValsLineWidth] = pGC->lineWidth;
-	    gcvals[GCValsCapStyle] = pGC->capStyle;
-	    gcvals[GCValsJoinStyle] = pGC->joinStyle;
-	    dixChangeGC(NullClient, pGCTo, GCValsMask, gcvals, NULL);
-    
-	    /* allocate a 1 bit deep pixmap of the appropriate size, and
-	     * validate it */
-	    pDrawTo = (DrawablePtr)(*pDraw->pScreen->CreatePixmap)
-				(pDraw->pScreen, pixmapWidth, pixmapHeight, 1,
-				 CREATE_PIXMAP_USAGE_SCRATCH);
-	    if (!pDrawTo)
-	    {
-		FreeScratchGC(pGCTo);
-		return;
-	    }
-	    ValidateGC(pDrawTo, pGCTo);
-	    miClearDrawable(pDrawTo, pGCTo);
-	}
-
-	fg = pGC->fgPixel;
-	bg = pGC->bgPixel;
-	if ((pGC->fillStyle == FillTiled) ||
-	    (pGC->fillStyle == FillOpaqueStippled))
-	    bg = fg; /* the protocol sez these don't cause color changes */
-
-	polyArcs = miComputeArcs (parcs, narcs, pGC);
-
-	if (!polyArcs)
-	{
-	    if (fTricky) {
-		(*pDraw->pScreen->DestroyPixmap) ((PixmapPtr)pDrawTo);
-		FreeScratchGC (pGCTo);
-	    }
-	    return;
-	}
-
-	cap[0] = cap[1] = 0;
-	join[0] = join[1] = 0;
-	for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
- 	     iphase >= 0;
-	     iphase--)
-	{
-	    if (iphase == 1) {
-		dixChangeGC (NullClient, pGC, GCForeground, &bg, NULL);
-		ValidateGC (pDraw, pGC);
-	    } else if (pGC->lineStyle == LineDoubleDash) {
-		dixChangeGC (NullClient, pGC, GCForeground, &fg, NULL);
-		ValidateGC (pDraw, pGC);
-	    }
-	    for (i = 0; i < polyArcs[iphase].narcs; i++) {
-		miArcDataPtr	arcData;
-
-		arcData = &polyArcs[iphase].arcs[i];
-		miArcSegment(pDrawTo, pGCTo, arcData->arc,
-			     &arcData->bounds[RIGHT_END],
-			     &arcData->bounds[LEFT_END]);
-		if (polyArcs[iphase].arcs[i].render) {
-		    fillSpans (pDrawTo, pGCTo);
-		    /*
-		     * don't cap self-joining arcs
-		     */
-		    if (polyArcs[iphase].arcs[i].selfJoin &&
-		        cap[iphase] < polyArcs[iphase].arcs[i].cap)
-		    	cap[iphase]++;
-		    while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {
-			int	arcIndex, end;
-			miArcDataPtr	arcData0;
-
-			arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;
-			end = polyArcs[iphase].caps[cap[iphase]].end;
-			arcData0 = &polyArcs[iphase].arcs[arcIndex];
-			miArcCap (pDrawTo, pGCTo,
- 				  &arcData0->bounds[end], end,
-				  arcData0->arc.x, arcData0->arc.y,
-				  (double) arcData0->arc.width / 2.0,
- 				  (double) arcData0->arc.height / 2.0);
-			++cap[iphase];
-		    }
-		    while (join[iphase] < polyArcs[iphase].arcs[i].join) {
-			int	arcIndex0, arcIndex1, end0, end1;
-			int	phase0, phase1;
-			miArcDataPtr	arcData0, arcData1;
-			miArcJoinPtr	joinp;
-
-			joinp = &polyArcs[iphase].joins[join[iphase]];
-			arcIndex0 = joinp->arcIndex0;
-			end0 = joinp->end0;
-			arcIndex1 = joinp->arcIndex1;
-			end1 = joinp->end1;
-			phase0 = joinp->phase0;
-			phase1 = joinp->phase1;
-			arcData0 = &polyArcs[phase0].arcs[arcIndex0];
-			arcData1 = &polyArcs[phase1].arcs[arcIndex1];
-			miArcJoin (pDrawTo, pGCTo,
-				  &arcData0->bounds[end0],
- 				  &arcData1->bounds[end1],
-				  arcData0->arc.x, arcData0->arc.y,
-				  (double) arcData0->arc.width / 2.0,
- 				  (double) arcData0->arc.height / 2.0,
-				  arcData1->arc.x, arcData1->arc.y,
-				  (double) arcData1->arc.width / 2.0,
- 				  (double) arcData1->arc.height / 2.0);
-			++join[iphase];
-		    }
-		    if (fTricky) {
-			if (pGC->serialNumber != pDraw->serialNumber)
-			    ValidateGC (pDraw, pGC);
-		    	(*pGC->ops->PushPixels) (pGC, (PixmapPtr)pDrawTo,
-				 pDraw, pixmapWidth, pixmapHeight, xOrg, yOrg);
-			miClearDrawable ((DrawablePtr) pDrawTo, pGCTo);
-		    }
-		}
-	    }
-	}
-	miFreeArcs(polyArcs, pGC);
-
-	if(fTricky)
-	{
-	    (*pGCTo->pScreen->DestroyPixmap)((PixmapPtr)pDrawTo);
-	    FreeScratchGC(pGCTo);
-	}
-    }
-}
-
-static double
-angleBetween (SppPointRec center, SppPointRec point1, SppPointRec point2)
-{
-	double	a1, a2, a;
-	
-	/*
-	 * reflect from X coordinates back to ellipse
-	 * coordinates -- y increasing upwards
-	 */
-	a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);
-	a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);
-	a = a2 - a1;
-	if (a <= -180.0)
-		a += 360.0;
-	else if (a > 180.0)
-		a -= 360.0;
-	return a;
-}
-
-static void
-translateBounds (
-	miArcFacePtr	b,
-	int		x,
-	int		y,
-	double		fx,
-	double		fy)
-{
-	fx += x;
-	fy += y;
-	b->clock.x -= fx;
-	b->clock.y -= fy;
-	b->center.x -= fx;
-	b->center.y -= fy;
-	b->counterClock.x -= fx;
-	b->counterClock.y -= fy;
-}
-
-static void
-miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,
-	  miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,
-	  double xFtransLeft, double yFtransLeft,
-	  int xOrgRight, int yOrgRight,
-	  double xFtransRight, double yFtransRight)
-{
-	SppPointRec	center, corner, otherCorner;
-	SppPointRec	poly[5], e;
-	SppPointPtr	pArcPts;
-	int		cpt;
-	SppArcRec	arc;
-	miArcFaceRec	Right, Left;
-	int		polyLen = 0;
-	int		xOrg, yOrg;
-	double		xFtrans, yFtrans;
-	double		a;
-	double		ae, ac2, ec2, bc2, de;
-	double		width;
-	
-	xOrg = (xOrgRight + xOrgLeft) / 2;
-	yOrg = (yOrgRight + yOrgLeft) / 2;
-	xFtrans = (xFtransLeft + xFtransRight) / 2;
-	yFtrans = (yFtransLeft + yFtransRight) / 2;
-	Right = *pRight;
-	translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,
-				 xFtrans - xFtransRight, yFtrans - yFtransRight);
-	Left = *pLeft;
-	translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,
-				 xFtrans - xFtransLeft, yFtrans - yFtransLeft);
-	pRight = &Right;
-	pLeft = &Left;
-
-	if (pRight->clock.x == pLeft->counterClock.x &&
-	    pRight->clock.y == pLeft->counterClock.y)
-		return;
-	center = pRight->center;
-	if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))
- 	    && a <= 180.0)
- 	{
-		corner = pRight->clock;
-		otherCorner = pLeft->counterClock;
-	} else {
-		a = angleBetween (center, pLeft->clock, pRight->counterClock);
-		corner = pLeft->clock;
-		otherCorner = pRight->counterClock;
-	}
-	switch (pGC->joinStyle) {
-	case JoinRound:
-		width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
-
-		arc.x = center.x - width/2;
-		arc.y = center.y - width/2;
-		arc.width = width;
-		arc.height = width;
-		arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);
-		arc.angle2 = a;
-		pArcPts = xalloc (3 * sizeof (SppPointRec));
-		if (!pArcPts)
-		    return;
-		pArcPts[0].x = otherCorner.x;
-		pArcPts[0].y = otherCorner.y;
-		pArcPts[1].x = center.x;
-		pArcPts[1].y = center.y;
-		pArcPts[2].x = corner.x;
-		pArcPts[2].y = corner.y;
-		if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )
-		{
-			/* by drawing with miFillSppPoly and setting the endpoints of the arc
-			 * to be the corners, we assure that the cap will meet up with the
-			 * rest of the line */
-			miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);
-		}
-		xfree(pArcPts);
-		return;
-	case JoinMiter:
-		/*
-		 * don't miter arcs with less than 11 degrees between them
-		 */
-		if (a < 169.0) {
-			poly[0] = corner;
-			poly[1] = center;
-			poly[2] = otherCorner;
-			bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +
-			      (corner.y - otherCorner.y) * (corner.y - otherCorner.y);
-			ec2 = bc2 / 4;
-			ac2 = (corner.x - center.x) * (corner.x - center.x) +
-			      (corner.y - center.y) * (corner.y - center.y);
-			ae = sqrt (ac2 - ec2);
-			de = ec2 / ae;
-			e.x = (corner.x + otherCorner.x) / 2;
-			e.y = (corner.y + otherCorner.y) / 2;
-			poly[3].x = e.x + de * (e.x - center.x) / ae;
-			poly[3].y = e.y + de * (e.y - center.y) / ae;
-			poly[4] = corner;
-			polyLen = 5;
-			break;
-		}
-	case JoinBevel:
-		poly[0] = corner;
-		poly[1] = center;
-		poly[2] = otherCorner;
-		poly[3] = corner;
-		polyLen = 4;
-		break;
-	}
-	miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);
-}
-
-/*ARGSUSED*/
-static void
-miArcCap (
-	DrawablePtr	pDraw,
-	GCPtr		pGC,
-	miArcFacePtr	pFace,
-	int		end,
-	int		xOrg,
-	int		yOrg,
-	double		xFtrans,
-	double		yFtrans)
-{
-	SppPointRec	corner, otherCorner, center, endPoint, poly[5];
-
-	corner = pFace->clock;
-	otherCorner = pFace->counterClock;
-	center = pFace->center;
-	switch (pGC->capStyle) {
-	case CapProjecting:
-		poly[0].x = otherCorner.x;
-		poly[0].y = otherCorner.y;
-		poly[1].x = corner.x;
-		poly[1].y = corner.y;
-		poly[2].x = corner.x -
- 				(center.y - corner.y);
-		poly[2].y = corner.y +
- 				(center.x - corner.x);
-		poly[3].x = otherCorner.x -
- 				(otherCorner.y - center.y);
-		poly[3].y = otherCorner.y +
- 				(otherCorner.x - center.x);
-		poly[4].x = otherCorner.x;
-		poly[4].y = otherCorner.y;
-		miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);
-		break;
-	case CapRound:
-		/*
-		 * miRoundCap just needs these to be unequal.
-		 */
-		endPoint = center;
-		endPoint.x = endPoint.x + 100;
-		miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,
-			    -xOrg, -yOrg, xFtrans, yFtrans);
-		break;
-	}
-}
-
-/* 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.  
- * NOTE:  pOtherCorner must be counter-clockwise from pCorner.
- */
-/*ARGSUSED*/
-static void
-miRoundCap(
-    DrawablePtr	pDraw,
-    GCPtr	pGC,
-    SppPointRec	pCenter,
-    SppPointRec	pEnd,
-    SppPointRec	pCorner,
-    SppPointRec	pOtherCorner,
-    int		fLineEnd,
-    int		xOrg,
-    int		yOrg,
-    double	xFtrans,
-    double	yFtrans)
-{
-    int		cpt;
-    double	width;
-    SppArcRec	arc;
-    SppPointPtr	pArcPts;
-
-    width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);
-
-    arc.x = pCenter.x - width/2;
-    arc.y = pCenter.y - width/2;
-    arc.width = width;
-    arc.height = width;
-    arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);
-    if(PTISEQUAL(pCenter, pEnd))
-	arc.angle2 = - 180.0;
-    else {
-	arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;
-	if (arc.angle2 < 0)
-	    arc.angle2 += 360.0;
-    }
-    pArcPts = (SppPointPtr) NULL;
-    if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )
-    {
-	/* by drawing with miFillSppPoly and setting the endpoints of the arc
-	 * to be the corners, we assure that the cap will meet up with the
-	 * rest of the line */
-	miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);
-    }
-    xfree(pArcPts);
-}
-
-/*
- * To avoid inaccuracy at the cardinal points, use trig functions
- * which are exact for those angles
- */
-
-#ifndef M_PI
-#define M_PI	3.14159265358979323846
-#endif
-#ifndef M_PI_2
-#define M_PI_2	1.57079632679489661923
-#endif
-
-# define Dsin(d)	((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))
-# define Dcos(d)	((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))
-# define mod(a,b)	((a) >= 0 ? (a) % (b) : (b) - (-a) % (b))
-
-static double
-miDcos (double a)
-{
-	int	i;
-
-	if (floor (a/90) == a/90) {
-		i = (int) (a/90.0);
-		switch (mod (i, 4)) {
-		case 0: return 1;
-		case 1: return 0;
-		case 2: return -1;
-		case 3: return 0;
-		}
-	}
-	return cos (a * M_PI / 180.0);
-}
-
-static double
-miDsin (double a)
-{
-	int	i;
-
-	if (floor (a/90) == a/90) {
-		i = (int) (a/90.0);
-		switch (mod (i, 4)) {
-		case 0: return 0;
-		case 1: return 1;
-		case 2: return 0;
-		case 3: return -1;
-		}
-	}
-	return sin (a * M_PI / 180.0);
-}
-
-static double
-miDasin (double v)
-{
-    if (v == 0)
-	return 0.0;
-    if (v == 1.0)
-	return 90.0;
-    if (v == -1.0)
-	return -90.0;
-    return asin(v) * (180.0 / M_PI);
-}
-
-static double
-miDatan2 (double dy, double dx)
-{
-    if (dy == 0) {
-	if (dx >= 0)
-	    return 0.0;
-	return 180.0;
-    } else if (dx == 0) {
-	if (dy > 0)
-	    return 90.0;
-	return -90.0;
-    } else if (Fabs (dy) == Fabs (dx)) {
-	if (dy > 0) {
-	    if (dx > 0)
-		return 45.0;
-	    return 135.0;
-	} else {
-	    if (dx > 0)
-		return 315.0;
-	    return 225.0;
-	}
-    } else {
-	return atan2 (dy, dx) * (180.0 / M_PI);
-    }
-}
-
-/* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper
- * routine for filled arc and line (round cap) code.
- * Returns the number of points in the arc.  Note that it takes a pointer
- * to a pointer to where it should put the points and an index (cpt).
- * This procedure allocates the space necessary to fit the arc points.
- * Sometimes it's convenient for those points to be at the end of an existing
- * array. (For example, if we want to leave a spare point to make sectors
- * instead of segments.)  So we pass in the xalloc()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 
- * count on xrealloc() to handle the null pointer correctly.
- */
-static int
-miGetArcPts(
-    SppArcPtr	parc,	/* points to an arc */
-    int		cpt,	/* number of points already in arc list */
-    SppPointPtr	*ppPts) /* pointer to pointer to arc-list -- modified */
-{
-    double 	st,	/* Start Theta, start angle */
-                et,	/* End Theta, offset from start theta */
-		dt,	/* Delta Theta, angle to sweep ellipse */
-		cdt,	/* Cos Delta Theta, actually 2 cos(dt) */
-    		x0, y0,	/* the recurrence formula needs two points to start */
-		x1, y1,
-		x2, y2, /* this will be the new point generated */
-		xc, yc; /* the center point */
-    int		count, i;
-    SppPointPtr	poly;
-
-    /* The spec says that positive angles indicate counterclockwise motion.
-     * 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 */
-    
-    st = - parc->angle1;
-
-    et = - parc->angle2;
-
-    /* Try to get a delta theta that is within 1/2 pixel.  Then adjust it
-     * so that it divides evenly into the total.
-     * I'm just using cdt 'cause I'm lazy.
-     */
-    cdt = parc->width;
-    if (parc->height > cdt)
-	cdt = parc->height;
-    cdt /= 2.0;
-    if(cdt <= 0)
-	return 0;
-    if (cdt < 1.0)
-	cdt = 1.0;
-    dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */
-    count = et/dt;
-    count = abs(count) + 1;
-    dt = et/count;	
-    count++;
-
-    cdt = 2 * miDcos(dt);
-    if (!(poly = (SppPointPtr) xrealloc((pointer)*ppPts,
-					(cpt + count) * sizeof(SppPointRec))))
-	return(0);
-    *ppPts = poly;
-
-    xc = parc->width/2.0;		/* store half width and half height */
-    yc = parc->height/2.0;
-    
-    x0 = xc * miDcos(st);
-    y0 = yc * miDsin(st);
-    x1 = xc * miDcos(st + dt);
-    y1 = yc * miDsin(st + dt);
-    xc += parc->x;		/* by adding initial point, these become */
-    yc += parc->y;		/* the center point */
-
-    poly[cpt].x = (xc + x0);
-    poly[cpt].y = (yc + y0);
-    poly[cpt + 1].x = (xc + x1);
-    poly[cpt + 1].y = (yc + y1);
-
-    for(i = 2; i < count; i++)
-    {
-	x2 = cdt * x1 - x0;
-	y2 = cdt * y1 - y0;
-
- 	poly[cpt + i].x = (xc + x2);
- 	poly[cpt + i].y = (yc + y2);
-
-	x0 = x1; y0 = y1;
-	x1 = x2; y1 = y2;
-    }
-    /* adjust the last point */
-    if (abs(parc->angle2) >= 360.0)
-	poly[cpt +i -1] = poly[0];
-    else {
-	poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);
-	poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);
-    }
-
-    return(count);
-}
-
-struct arcData {
-	double	x0, y0, x1, y1;
-	int	selfJoin;
-};
-
-# define ADD_REALLOC_STEP	20
-
-static void
-addCap (
-	miArcCapPtr	*capsp,
-	int		*ncapsp,
-	int		*sizep,
-	int		end,
-	int		arcIndex)
-{
-	int newsize;
-	miArcCapPtr	cap;
-
-	if (*ncapsp == *sizep)
-	{
-	    newsize = *sizep + ADD_REALLOC_STEP;
-	    cap = (miArcCapPtr) xrealloc (*capsp,
-					  newsize * sizeof (**capsp));
-	    if (!cap)
-		return;
-	    *sizep = newsize;
-	    *capsp = cap;
-	}
-	cap = &(*capsp)[*ncapsp];
-	cap->end = end;
-	cap->arcIndex = arcIndex;
-	++*ncapsp;
-}
-
-static void
-addJoin (
-	miArcJoinPtr	*joinsp,
-	int		*njoinsp,
-	int		*sizep,
-	int		end0,
-	int		index0,
-	int		phase0,
-	int		end1,
-	int		index1,
-	int		phase1)
-{
-	int newsize;
-	miArcJoinPtr	join;
-
-	if (*njoinsp == *sizep)
-	{
-	    newsize = *sizep + ADD_REALLOC_STEP;
-	    join = (miArcJoinPtr) xrealloc (*joinsp,
-					    newsize * sizeof (**joinsp));
-	    if (!join)
-		return;
-	    *sizep = newsize;
-	    *joinsp = join;
-	}
-	join = &(*joinsp)[*njoinsp];
-	join->end0 = end0;
-	join->arcIndex0 = index0;
-	join->phase0 = phase0;
-	join->end1 = end1;
-	join->arcIndex1 = index1;
-	join->phase1 = phase1;
-	++*njoinsp;
-}
-
-static miArcDataPtr
-addArc (
-	miArcDataPtr	*arcsp,
-	int		*narcsp,
-	int		*sizep,
-	xArc		*xarc)
-{
-	int newsize;
-	miArcDataPtr	arc;
-
-	if (*narcsp == *sizep)
-	{
-	    newsize = *sizep + ADD_REALLOC_STEP;
-	    arc = (miArcDataPtr) xrealloc (*arcsp,
-					   newsize * sizeof (**arcsp));
-	    if (!arc)
-		return NULL;
-	    *sizep = newsize;
-	    *arcsp = arc;
-	}
-	arc = &(*arcsp)[*narcsp];
-	arc->arc = *xarc;
-	++*narcsp;
-	return arc;
-}
-
-static void
-miFreeArcs(
-    miPolyArcPtr arcs,
-    GCPtr pGC)
-{
-	int iphase;
-
-	for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);
- 	     iphase >= 0;
-	     iphase--)
-	{
-	    if (arcs[iphase].narcs > 0)
-		xfree(arcs[iphase].arcs);
-	    if (arcs[iphase].njoins > 0)
-		xfree(arcs[iphase].joins);
-	    if (arcs[iphase].ncaps > 0)
-		xfree(arcs[iphase].caps);
-	}
-	xfree(arcs);
-}
-
-/*
- * map angles to radial distance.  This only deals with the first quadrant
- */
-
-/*
- * a polygonal approximation to the arc for computing arc lengths
- */
-
-# define DASH_MAP_SIZE	91
-
-# define dashIndexToAngle(di)	((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))
-# define xAngleToDashIndex(xa)	((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))
-# define dashIndexToXAngle(di)	((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))
-# define dashXAngleStep	(((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))
-
-typedef struct {
-	double	map[DASH_MAP_SIZE];
-} dashMap;
-
-static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map,
-				int *lenp, int backwards);
-
-static void
-computeDashMap (
-	xArc	*arcp,
-	dashMap	*map)
-{
-	int	di;
-	double	a, x, y, prevx = 0.0, prevy = 0.0, dist;
-
-	for (di = 0; di < DASH_MAP_SIZE; di++) {
-		a = dashIndexToAngle (di);
-		x = ((double) arcp->width / 2.0) * miDcos (a);
-		y = ((double) arcp->height / 2.0) * miDsin (a);
-		if (di == 0) {
-			map->map[di] = 0.0;
-		} else {
-			dist = hypot (x - prevx, y - prevy);
-			map->map[di] = map->map[di - 1] + dist;
-		}
-		prevx = x;
-		prevy = y;
-	}
-}
-
-typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;
-
-/* this routine is a bit gory */
-
-static miPolyArcPtr
-miComputeArcs (
-	xArc	*parcs,
-	int	narcs,
-	GCPtr	pGC)
-{
-	int		isDashed, isDoubleDash;
-	int		dashOffset;
-	miPolyArcPtr	arcs;
-	int		start, i, j, k = 0, nexti, nextk = 0;
-	int		joinSize[2];
-	int		capSize[2];
-	int		arcSize[2];
-	int		angle2;
-	double		a0, a1;
-	struct arcData	*data;
-	miArcDataPtr	arc;
-	xArc		xarc;
-	int		iphase, prevphase = 0, joinphase;
-	int		arcsJoin;
-	int		selfJoin;
-
-	int		iDash = 0, dashRemaining = 0;
-	int		iDashStart = 0, dashRemainingStart = 0, iphaseStart;
-	int		startAngle, spanAngle, endAngle, backwards = 0;
-	int		prevDashAngle, dashAngle;
-	dashMap		map;
-
-	isDashed = !(pGC->lineStyle == LineSolid);
-	isDoubleDash = (pGC->lineStyle == LineDoubleDash);
-	dashOffset = pGC->dashOffset;
-
-	data = xalloc (narcs * sizeof (struct arcData));
-	if (!data)
-	    return NULL;
-	arcs = xalloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));
-	if (!arcs)
-	{
-	    xfree(data);
-	    return NULL;
-	}
-	for (i = 0; i < narcs; i++) {
-		a0 = todeg (parcs[i].angle1);
-		angle2 = parcs[i].angle2;
-		if (angle2 > FULLCIRCLE)
-			angle2 = FULLCIRCLE;
-		else if (angle2 < -FULLCIRCLE)
-			angle2 = -FULLCIRCLE;
-		data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;
-		a1 = todeg (parcs[i].angle1 + angle2);
-		data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));
-		data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));
-		data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));
-		data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));
-	}
-
-	for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {
-		arcs[iphase].njoins = 0;
-		arcs[iphase].joins = 0;
-		joinSize[iphase] = 0;
-		
-		arcs[iphase].ncaps = 0;
-		arcs[iphase].caps = 0;
-		capSize[iphase] = 0;
-		
-		arcs[iphase].narcs = 0;
-		arcs[iphase].arcs = 0;
-		arcSize[iphase] = 0;
-	}
-
-	iphase = 0;
-	if (isDashed) {
-		iDash = 0;
-		dashRemaining = pGC->dash[0];
-	 	while (dashOffset > 0) {
-			if (dashOffset >= dashRemaining) {
-				dashOffset -= dashRemaining;
-				iphase = iphase ? 0 : 1;
-				iDash++;
-				if (iDash == pGC->numInDashList)
-				    iDash = 0;
-				dashRemaining = pGC->dash[iDash];
-			} else {
-				dashRemaining -= dashOffset;
-				dashOffset = 0;
-			}
-		}
-		iDashStart = iDash;
-		dashRemainingStart = dashRemaining;
-	}
-	iphaseStart = iphase;
-
-	for (i = narcs - 1; i >= 0; i--) {
-		j = i + 1;
-		if (j == narcs)
-			j = 0;
-		if (data[i].selfJoin || i == j ||
-		     (UNEQUAL (data[i].x1, data[j].x0) ||
-		      UNEQUAL (data[i].y1, data[j].y0)))
- 		{
-			if (iphase == 0 || isDoubleDash)
-				addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
-	 				&capSize[iphase], RIGHT_END, 0);
-			break;
-		}
-	}
-	start = i + 1;
-	if (start == narcs)
-		start = 0;
-	i = start;
-	for (;;) {
-		j = i + 1;
-		if (j == narcs)
-			j = 0;
-		nexti = i+1;
-		if (nexti == narcs)
-			nexti = 0;
-		if (isDashed) {
-			/*
-			** deal with dashed arcs.  Use special rules for certain 0 area arcs.
-			** Presumably, the other 0 area arcs still aren't done right.
-			*/
-			arcTypes	arcType = OTHER;
-			CARD16		thisLength;
-
-			if (parcs[i].height == 0
-			    && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00
-			    && parcs[i].angle2 == 0x2d00) 
-				arcType = HORIZONTAL;
-			else if (parcs[i].width == 0
-			    && (parcs[i].angle1 % FULLCIRCLE) == 0x1680
-			    && parcs[i].angle2 == 0x2d00)
-				arcType = VERTICAL;
-			if (arcType == OTHER) {
-				/*
-				 * precompute an approximation map
-				 */
-				computeDashMap (&parcs[i], &map);
-				/*
-				 * compute each individual dash segment using the path
-				 * length function
-				 */
-				startAngle = parcs[i].angle1;
-				spanAngle = parcs[i].angle2;
-				if (spanAngle > FULLCIRCLE)
-					spanAngle = FULLCIRCLE;
-				else if (spanAngle < -FULLCIRCLE)
-					spanAngle = -FULLCIRCLE;
-				if (startAngle < 0)
-					startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;
-				if (startAngle >= FULLCIRCLE)
-					startAngle = startAngle % FULLCIRCLE;
-				endAngle = startAngle + spanAngle;
-				backwards = spanAngle < 0;
-			} else {
-				xarc = parcs[i];
-				if (arcType == VERTICAL) {
-					xarc.angle1 = 0x1680;
-					startAngle = parcs[i].y;
-					endAngle = startAngle + parcs[i].height;
-				} else {
-					xarc.angle1 = 0x2d00;
-					startAngle = parcs[i].x;
-					endAngle = startAngle + parcs[i].width;
-				}
-			}
-			dashAngle = startAngle;
-			selfJoin = data[i].selfJoin &&
- 				    (iphase == 0 || isDoubleDash);
-			/*
-			 * add dashed arcs to each bucket
-			 */
-			arc = 0;
-			while (dashAngle != endAngle) {
-				prevDashAngle = dashAngle;
-				if (arcType == OTHER) {
-					dashAngle = computeAngleFromPath (prevDashAngle, endAngle,
-								&map, &dashRemaining, backwards);
-					/* avoid troubles with huge arcs and small dashes */
-					if (dashAngle == prevDashAngle) {
-						if (backwards)
-							dashAngle--;
-						else
-							dashAngle++;
-					}
-				} else {
-					thisLength = (dashAngle + dashRemaining <= endAngle) ? 
-					    dashRemaining : endAngle - dashAngle;
-					if (arcType == VERTICAL) {
-						xarc.y = dashAngle;
-						xarc.height = thisLength;
-					} else {
-						xarc.x = dashAngle;
-						xarc.width = thisLength;
-					}
-					dashAngle += thisLength;
-					dashRemaining -= thisLength;
-				}
-				if (iphase == 0 || isDoubleDash) {
-					if (arcType == OTHER) {
-						xarc = parcs[i];
-						spanAngle = prevDashAngle;
-						if (spanAngle < 0)
-						    spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;
-						if (spanAngle >= FULLCIRCLE)
-						    spanAngle = spanAngle % FULLCIRCLE;
-						xarc.angle1 = spanAngle;
-						spanAngle = dashAngle - prevDashAngle;
-						if (backwards) {
-							if (dashAngle > prevDashAngle)
-								spanAngle = - FULLCIRCLE + spanAngle;
-						} else {
-							if (dashAngle < prevDashAngle)
-								spanAngle = FULLCIRCLE + spanAngle;
-						}
-						if (spanAngle > FULLCIRCLE)
-						    spanAngle = FULLCIRCLE;
-						if (spanAngle < -FULLCIRCLE)
-						    spanAngle = -FULLCIRCLE;
-						xarc.angle2 = spanAngle;
-					}
-					arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
- 							&arcSize[iphase], &xarc);
-					if (!arc)
-					    goto arcfail;
-					/*
-					 * cap each end of an on/off dash
-					 */
-					if (!isDoubleDash) {
-						if (prevDashAngle != startAngle) {
-							addCap (&arcs[iphase].caps,
- 								&arcs[iphase].ncaps,
- 								&capSize[iphase], RIGHT_END,
- 								arc - arcs[iphase].arcs);
-							
-						}
-						if (dashAngle != endAngle) {
-							addCap (&arcs[iphase].caps,
- 								&arcs[iphase].ncaps,
- 								&capSize[iphase], LEFT_END,
- 								arc - arcs[iphase].arcs);
-						}
-					}
-					arc->cap = arcs[iphase].ncaps;
-					arc->join = arcs[iphase].njoins;
-					arc->render = 0;
-					arc->selfJoin = 0;
-					if (dashAngle == endAngle)
-						arc->selfJoin = selfJoin;
-				}
-				prevphase = iphase;
-				if (dashRemaining <= 0) {
-					++iDash;
-					if (iDash == pGC->numInDashList)
-						iDash = 0;
-					iphase = iphase ? 0:1;
-					dashRemaining = pGC->dash[iDash];
-				}
-			}
-			/*
-			 * make sure a place exists for the position data when
-			 * drawing a zero-length arc
-			 */
-			if (startAngle == endAngle) {
-				prevphase = iphase;
-				if (!isDoubleDash && iphase == 1)
-					prevphase = 0;
-				arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,
-					      &arcSize[prevphase], &parcs[i]);
-				if (!arc)
-				    goto arcfail;
-				arc->join = arcs[prevphase].njoins;
-				arc->cap = arcs[prevphase].ncaps;
-				arc->selfJoin = data[i].selfJoin;
-			}
-		} else {
-			arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,
- 				      &arcSize[iphase], &parcs[i]);
-			if (!arc)
-			    goto arcfail;
-			arc->join = arcs[iphase].njoins;
-			arc->cap = arcs[iphase].ncaps;
-			arc->selfJoin = data[i].selfJoin;
-			prevphase = iphase;
-		}
-		if (prevphase == 0 || isDoubleDash)
-			k = arcs[prevphase].narcs - 1;
-		if (iphase == 0 || isDoubleDash)
-			nextk = arcs[iphase].narcs;
-		if (nexti == start) {
-			nextk = 0;
-			if (isDashed) {
-				iDash = iDashStart;
-				iphase = iphaseStart;
-				dashRemaining = dashRemainingStart;
-			}
-		}
-		arcsJoin = narcs > 1 && i != j &&
-	 		    ISEQUAL (data[i].x1, data[j].x0) &&
-			    ISEQUAL (data[i].y1, data[j].y0) &&
-			    !data[i].selfJoin && !data[j].selfJoin;
-		if (arc)
-		{
-			if (arcsJoin)
-				arc->render = 0;
-			else
-				arc->render = 1;
-		}
-		if (arcsJoin &&
-		    (prevphase == 0 || isDoubleDash) &&
-		    (iphase == 0 || isDoubleDash))
- 		{
-			joinphase = iphase;
-			if (isDoubleDash) {
-				if (nexti == start)
-					joinphase = iphaseStart;
-				/*
-				 * if the join is right at the dash,
-				 * draw the join in foreground
-				 * This is because the foreground
-				 * arcs are computed second, the results
-				 * of which are needed to draw the join
-				 */
-				if (joinphase != prevphase)
-					joinphase = 0;
-			}
-			if (joinphase == 0 || isDoubleDash) {
-				addJoin (&arcs[joinphase].joins,
- 					 &arcs[joinphase].njoins,
- 					 &joinSize[joinphase],
-	 				 LEFT_END, k, prevphase,
-	 				 RIGHT_END, nextk, iphase);
-				arc->join = arcs[prevphase].njoins;
-			}
-		} else {
-			/*
-			 * cap the left end of this arc
-			 * unless it joins itself
-			 */
-			if ((prevphase == 0 || isDoubleDash) &&
-			    !arc->selfJoin)
-			{
-				addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,
- 					&capSize[prevphase], LEFT_END, k);
-				arc->cap = arcs[prevphase].ncaps;
-			}
-			if (isDashed && !arcsJoin) {
-				iDash = iDashStart;
-				iphase = iphaseStart;
-				dashRemaining = dashRemainingStart;
-			}
-			nextk = arcs[iphase].narcs;
-			if (nexti == start) {
-				nextk = 0;
-				iDash = iDashStart;
-				iphase = iphaseStart;
-				dashRemaining = dashRemainingStart;
-			}
-			/*
-			 * cap the right end of the next arc.  If the
-			 * next arc is actually the first arc, only
-			 * cap it if it joins with this arc.  This
-			 * case will occur when the final dash segment
-			 * of an on/off dash is off.  Of course, this
-			 * cap will be drawn at a strange time, but that
-			 * hardly matters...
-			 */
-			if ((iphase == 0 || isDoubleDash) &&
-			    (nexti != start || (arcsJoin && isDashed)))
-				addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,
- 					&capSize[iphase], RIGHT_END, nextk);
-		}
-		i = nexti;
-		if (i == start)
-			break;
-	}
-	/*
-	 * make sure the last section is rendered
-	 */
-	for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)
-		if (arcs[iphase].narcs > 0) {
-			arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;
-			arcs[iphase].arcs[arcs[iphase].narcs-1].join =
-			         arcs[iphase].njoins;
-			arcs[iphase].arcs[arcs[iphase].narcs-1].cap =
-			         arcs[iphase].ncaps;
-		}
-	xfree(data);
-	return arcs;
-arcfail:
-	miFreeArcs(arcs, pGC);
-	xfree(data);
-	return NULL;
-}
-
-static double
-angleToLength (
-	int	angle,
-	dashMap	*map)
-{
-	double	len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;
-	int	di;
-	int	excess;
-	Bool	oddSide = FALSE;
-
-	totallen = 0;
-	if (angle >= 0) {
-		while (angle >= 90 * 64) {
-			angle -= 90 * 64;
-			totallen += sidelen;
-			oddSide = !oddSide;
-		}
-	} else {
-		while (angle < 0) {
-			angle += 90 * 64;
-			totallen -= sidelen;
-			oddSide = !oddSide;
-		}
-	}
-	if (oddSide)
-		angle = 90 * 64 - angle;
-		
-	di = xAngleToDashIndex (angle);
-	excess = angle - dashIndexToXAngle (di);
-
-	len = map->map[di];
-	/*
-	 * linearly interpolate between this point and the next
-	 */
-	if (excess > 0) {
-		excesslen = (map->map[di + 1] - map->map[di]) *
-				((double) excess) / dashXAngleStep;
-		len += excesslen;
-	}
-	if (oddSide)
-		totallen += (sidelen - len);
-	else
-		totallen += len;
-	return totallen;
-}
-
-/*
- * len is along the arc, but may be more than one rotation
- */
-
-static int
-lengthToAngle (
-	double	len,
-	dashMap	*map)
-{
-	double	sidelen = map->map[DASH_MAP_SIZE - 1];
-	int	angle, angleexcess;
-	Bool	oddSide = FALSE;
-	int	a0, a1, a;
-
-	angle = 0;
-	/*
-	 * step around the ellipse, subtracting sidelens and
-	 * adding 90 degrees.  oddSide will tell if the
-	 * map should be interpolated in reverse
-	 */
-	if (len >= 0) {
-		if (sidelen == 0)
-			return 2 * FULLCIRCLE;	/* infinity */
-		while (len >= sidelen) {
-			angle += 90 * 64;
-			len -= sidelen;
-			oddSide = !oddSide;
-		}
-	} else {
-		if (sidelen == 0)
-			return -2 * FULLCIRCLE;	/* infinity */
-		while (len < 0) {
-			angle -= 90 * 64;
-			len += sidelen;
-			oddSide = !oddSide;
-		}
-	}
-	if (oddSide)
-		len = sidelen - len;
-	a0 = 0;
-	a1 = DASH_MAP_SIZE - 1;
-	/*
-	 * binary search for the closest pre-computed length
-	 */
-	while (a1 - a0 > 1) {
-		a = (a0 + a1) / 2;
-		if (len > map->map[a])
-			a0 = a;
-		else
-			a1 = a;
-	}
-	angleexcess = dashIndexToXAngle (a0);
-	/*
-	 * linearly interpolate to the next point
-	 */
-	angleexcess += (len - map->map[a0]) /
-			(map->map[a0+1] - map->map[a0]) * dashXAngleStep;
-	if (oddSide)
-		angle += (90 * 64) - angleexcess;
-	else
-		angle += angleexcess;
-	return angle;
-}
-
-/*
- * compute the angle of an ellipse which cooresponds to
- * the given path length.  Note that the correct solution
- * to this problem is an eliptic integral, we'll punt and
- * approximate (it's only for dashes anyway).  This
- * approximation uses a polygon.
- *
- * The remaining portion of len is stored in *lenp -
- * this will be negative if the arc extends beyond
- * len and positive if len extends beyond the arc.
- */
-
-static int
-computeAngleFromPath (
-	int	startAngle,
-	int	endAngle,	/* normalized absolute angles in *64 degrees */
-	dashMap	*map,
-	int	*lenp,
-	int	backwards)
-{
-	int	a0, a1, a;
-	double	len0;
-	int	len;
-
-	a0 = startAngle;
-	a1 = endAngle;
-	len = *lenp;
-	if (backwards) {
-		/*
-		 * flip the problem around to always be
-		 * forwards
-		 */
-		a0 = FULLCIRCLE - a0;
-		a1 = FULLCIRCLE - a1;
-	}
-	if (a1 < a0)
-		a1 += FULLCIRCLE;
-	len0 = angleToLength (a0, map);
-	a = lengthToAngle (len0 + len, map);
-	if (a > a1) {
-		a = a1;
-		len -= angleToLength (a1, map) - len0;
-	} else
-		len = 0;
-	if (backwards)
-		a = FULLCIRCLE - a;
-	*lenp = len;
-	return a;
-}
-
-/*
- * scan convert wide arcs.
- */
-
-/*
- * draw zero width/height arcs
- */
-
-static void
-drawZeroArc (
-    DrawablePtr   pDraw,
-    GCPtr         pGC,
-    xArc          *tarc,
-    int		  lw,
-    miArcFacePtr	left,
-    miArcFacePtr	right)
-{
-	double	x0 = 0.0, y0 = 0.0, x1 = 0.0, y1 = 0.0, w, h, x, y;
-	double	xmax, ymax, xmin, ymin;
-	int	a0, a1;
-	double	a, startAngle, endAngle;
-	double	l, lx, ly;
-
-	l = lw / 2.0;
-	a0 = tarc->angle1;
-	a1 = tarc->angle2;
-	if (a1 > FULLCIRCLE)
-		a1 = FULLCIRCLE;
-	else if (a1 < -FULLCIRCLE)
-		a1 = -FULLCIRCLE;
-	w = (double)tarc->width / 2.0;
-	h = (double)tarc->height / 2.0;
-	/*
-	 * play in X coordinates right away
-	 */
-	startAngle = - ((double) a0 / 64.0);
-	endAngle = - ((double) (a0 + a1) / 64.0);
-	
-	xmax = -w;
-	xmin = w;
-	ymax = -h;
-	ymin = h;
-	a = startAngle;
-	for (;;)
-	{
-		x = w * miDcos(a);
-		y = h * miDsin(a);
-		if (a == startAngle)
-		{
-			x0 = x;
-			y0 = y;
-		}
-		if (a == endAngle)
-		{
-			x1 = x;
-			y1 = y;
-		}
-		if (x > xmax)
-			xmax = x;
-		if (x < xmin)
-			xmin = x;
-		if (y > ymax)
-			ymax = y;
-		if (y < ymin)
-			ymin = y;
-		if (a == endAngle)
-			break;
-		if (a1 < 0)	/* clockwise */
-		{
-			if (floor (a / 90.0) == floor (endAngle / 90.0))
-				a = endAngle;
-			else
-				a = 90 * (floor (a/90.0) + 1);
-		}
-		else
-		{
-			if (ceil (a / 90.0) == ceil (endAngle / 90.0))
-				a = endAngle;
-			else
-				a = 90 * (ceil (a/90.0) - 1);
-		}
-	}
-	lx = ly = l;
-	if ((x1 - x0) + (y1 - y0) < 0)
-	    lx = ly = -l;
-	if (h)
-	{
-	    ly = 0.0;
-	    lx = -lx;
-	}
-	else
-	    lx = 0.0;
-	if (right)
-	{
-	    right->center.x = x0;
-	    right->center.y = y0;
-	    right->clock.x = x0 - lx;
-	    right->clock.y = y0 - ly;
-	    right->counterClock.x = x0 + lx;
-	    right->counterClock.y = y0 + ly;
-	}
-	if (left)
- 	{
-	    left->center.x = x1;
-	    left->center.y = y1;
-	    left->clock.x = x1 + lx;
-	    left->clock.y = y1 + ly;
-	    left->counterClock.x = x1 - lx;
-	    left->counterClock.y = y1 - ly;
-	}
-	
-	x0 = xmin;
-	x1 = xmax;
-	y0 = ymin;
-	y1 = ymax;
-	if (ymin != y1) {
-		xmin = -l;
-		xmax = l;
-	} else {
-		ymin = -l;
-		ymax = l;
-	}
-	if (xmax != xmin && ymax != ymin) {
-		int	minx, maxx, miny, maxy;
-		xRectangle  rect;
-
-		minx = ICEIL (xmin + w) + tarc->x;
-		maxx = ICEIL (xmax + w) + tarc->x;
-		miny = ICEIL (ymin + h) + tarc->y;
-		maxy = ICEIL (ymax + h) + tarc->y;
-		rect.x = minx;
-		rect.y = miny;
-		rect.width = maxx - minx;
-		rect.height = maxy - miny;
-		(*pGC->ops->PolyFillRect) (pDraw, pGC, 1, &rect);
-	}
-}
-
-/*
- * this computes the ellipse y value associated with the
- * bottom of the tail.
- */
-
-static void
-tailEllipseY (
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	double		t;
-
-	acc->tail_y = 0.0;
-	if (def->w == def->h)
-	    return;
-	t = def->l * def->w;
-	if (def->w > def->h) {
-	    if (t < acc->h2)
-		return;
-	} else {
-	    if (t > acc->h2)
-		return;
-	}
-	t = 2.0 * def->h * t;
-	t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;
-	if (t > 0.0)
-	    acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);
-}
-
-/*
- * inverse functions -- compute edge coordinates
- * from the ellipse
- */
-
-static double
-outerXfromXY (
-	double			x,
-	double			y,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
-}
-
-static double
-outerYfromXY (
-	double		x,
-	double		y,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
-}
-
-static double
-innerXfromXY (
-	double			x,
-	double			y,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
-}
-
-static double
-innerYfromXY (
-	double			x,
-	double			y,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
-}
-
-static double
-innerYfromY (
-	double	y,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	double	x;
-
-	x = (def->w / def->h) * sqrt (acc->h2 - y*y);
-
-	return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);
-}
-
-static void
-computeLine (
-	double		x1,
-	double		y1,
-	double		x2,
-	double		y2,
-	struct line	*line)
-{
-	if (y1 == y2)
-		line->valid = 0;
-	else {
-		line->m = (x1 - x2) / (y1 - y2);
-		line->b = x1  - y1 * line->m;
-		line->valid = 1;
-	}
-}
-
-/*
- * compute various accelerators for an ellipse.  These
- * are simply values that are used repeatedly in
- * the computations
- */
-
-static void
-computeAcc (
-	xArc			*tarc,
-	int			lw,
-	struct arc_def		*def,
-	struct accelerators	*acc)
-{
-	def->w = ((double) tarc->width) / 2.0;
-	def->h = ((double) tarc->height) / 2.0;
-	def->l = ((double) lw) / 2.0;
-	acc->h2 = def->h * def->h;
-	acc->w2 = def->w * def->w;
-	acc->h4 = acc->h2 * acc->h2;
-	acc->w4 = acc->w2 * acc->w2;
-	acc->h2l = acc->h2 * def->l;
-	acc->w2l = acc->w2 * def->l;
-	acc->h2mw2 = acc->h2 - acc->w2;
-	acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;
-	acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;
-	acc->xorg = tarc->x + (tarc->width >> 1);
-	acc->yorgu = tarc->y + (tarc->height >> 1);
-	acc->yorgl = acc->yorgu + (tarc->height & 1);
-	tailEllipseY (def, acc);
-}
-		
-/*
- * compute y value bounds of various portions of the arc,
- * the outer edge, the ellipse and the inner edge.
- */
-
-static void
-computeBound (
-	struct arc_def		*def,
-	struct arc_bound	*bound,
-	struct accelerators	*acc,
-	miArcFacePtr		right,
-	miArcFacePtr		left)
-{
-	double		t;
-	double		innerTaily;
-	double		tail_y;
-	struct bound	innerx, outerx;
-	struct bound	ellipsex;
-
-	bound->ellipse.min = Dsin (def->a0) * def->h;
-	bound->ellipse.max = Dsin (def->a1) * def->h;
-	if (def->a0 == 45 && def->w == def->h)
-		ellipsex.min = bound->ellipse.min;
-	else
-		ellipsex.min = Dcos (def->a0) * def->w;
-	if (def->a1 == 45 && def->w == def->h)
-		ellipsex.max = bound->ellipse.max;
-	else
-		ellipsex.max = Dcos (def->a1) * def->w;
-	bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
-	bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
-	bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);
-	bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);
-
-	outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
-	outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
-	innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);
-	innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);
-	
-	/*
-	 * save the line end points for the
-	 * cap code to use.  Careful here, these are
-	 * in cartesean coordinates (y increasing upwards)
-	 * while the cap code uses inverted coordinates
-	 * (y increasing downwards)
-	 */
-
-	if (right) {
-		right->counterClock.y = bound->outer.min;
-		right->counterClock.x = outerx.min;
-		right->center.y = bound->ellipse.min;
-		right->center.x = ellipsex.min;
-		right->clock.y = bound->inner.min;
-		right->clock.x = innerx.min;
-	}
-
-	if (left) {
-		left->clock.y = bound->outer.max;
-		left->clock.x = outerx.max;
-		left->center.y = bound->ellipse.max;
-		left->center.x = ellipsex.max;
-		left->counterClock.y = bound->inner.max;
-		left->counterClock.x = innerx.max;
-	}
-
-	bound->left.min = bound->inner.max;
-	bound->left.max = bound->outer.max;
-	bound->right.min = bound->inner.min;
-	bound->right.max = bound->outer.min;
-
-	computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,
-		      &acc->right);
-	computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,
-		     &acc->left);
-
-	if (bound->inner.min > bound->inner.max) {
-		t = bound->inner.min;
-		bound->inner.min = bound->inner.max;
-		bound->inner.max = t;
-	}
-	tail_y = acc->tail_y;
-	if (tail_y > bound->ellipse.max)
-		tail_y = bound->ellipse.max;
-	else if (tail_y < bound->ellipse.min)
-		tail_y = bound->ellipse.min;
-	innerTaily = innerYfromY (tail_y, def, acc);
-	if (bound->inner.min > innerTaily)
-		bound->inner.min = innerTaily;
-	if (bound->inner.max < innerTaily)
-		bound->inner.max = innerTaily;
-	bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);
-	bound->inneri.max = floor(bound->inner.max - acc->fromIntY);
-	bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);
-	bound->outeri.max = floor(bound->outer.max - acc->fromIntY);
-}
-
-/*
- * 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
- * lines to the entire ellipse,  the equation of the
- * normal lines is:
- *
- *     ellipse_x h^2                   h^2
- * x = ------------ y + ellipse_x (1 - --- )
- *     ellipse_y w^2                   w^2
- *
- * 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)
- *
- *             (   h^4 y     )
- * ellipse_y = ( ----------  ) ^ (1/3)
- *             ( (h^2 - w^2) )
- *
- * The other two solutions to the equation are imaginary.
- *
- * This gives the position on the ellipse which generates
- * the normal with the largest/smallest x intersection point.
- *
- * Now compute the second derivative to check whether
- * the intersection is a minimum or maximum:
- *
- *    h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
- * -  -------------------------------------------
- *          w y0^3 (sqrt (h^2 - y^2)) ^ 3
- *
- * as we only care about the sign,
- *
- * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))
- *
- * or (to use accelerators),
- *
- * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) 
- *
- */
-
-/*
- * computes the position on the ellipse whose normal line
- * intersects the given scan line maximally
- */
-
-static double
-hookEllipseY (
-	double			scan_y,
-	struct arc_bound	*bound,
-	struct accelerators	*acc,
-	int			left)
-{
-	double	ret;
-
-	if (acc->h2mw2 == 0) {
-		if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )
-			return bound->ellipse.min;
-		return bound->ellipse.max;
-	}
-	ret = (acc->h4 * scan_y) / (acc->h2mw2);
-	if (ret >= 0)
-		return cbrt (ret);
-	else
-		return -cbrt (-ret);
-}
-
-/*
- * computes the X value of the intersection of the
- * given scan line with the right side of the lower hook
- */
-
-static double
-hookX (
-	double			scan_y,
-	struct arc_def		*def,
-	struct arc_bound	*bound,
-	struct accelerators	*acc,
-	int			left)
-{
-	double	ellipse_y, x;
-	double	maxMin;
-
-	if (def->w != def->h) {
-		ellipse_y = hookEllipseY (scan_y, bound, acc, left);
-		if (boundedLe (ellipse_y, bound->ellipse)) {
-			/*
-		 	 * compute the value of the second
-		 	 * derivative
-		 	 */
-			maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -
-		 	 acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);
-			if ((left && maxMin > 0) || (!left && maxMin < 0)) {
-				if (ellipse_y == 0)
-					return def->w + left ? -def->l : def->l;
-				x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *
-					sqrt (acc->h2 - ellipse_y * ellipse_y) /
-			 		(def->h * def->w * ellipse_y);
-				return x;
-			}
-		}
-	}
-	if (left) {
-		if (acc->left.valid && boundedLe (scan_y, bound->left)) {
-			x = intersectLine (scan_y, acc->left);
-		} else {
-			if (acc->right.valid)
-				x = intersectLine (scan_y, acc->right);
-			else
-				x = def->w - def->l;
-		}
-	} else {
-		if (acc->right.valid && boundedLe (scan_y, bound->right)) {
-			x = intersectLine (scan_y, acc->right);
-		} else {
-			if (acc->left.valid)
-				x = intersectLine (scan_y, acc->left);
-			else
-				x = def->w - def->l;
-		}
-	}
-	return x;
-}
-
-/*
- * generate the set of spans with
- * the given y coordinate
- */
-
-static void
-arcSpan (
-	int			y,
-	int			lx,
-	int			lw,
-	int			rx,
-	int			rw,
-	struct arc_def		*def,
-	struct arc_bound	*bounds,
-	struct accelerators	*acc,
-	int			mask)
-{
-	int linx, loutx, rinx, routx;
-	double x, altx;
-
-	if (boundedLe (y, bounds->inneri)) {
-	    linx = -(lx + lw);
-	    rinx = rx;
-	} else {
-	    /*
-	     * intersection with left face
-	     */
-	    x = hookX (y + acc->fromIntY, def, bounds, acc, 1);
-	    if (acc->right.valid &&
-		boundedLe (y + acc->fromIntY, bounds->right))
-	    {
-		altx = intersectLine (y + acc->fromIntY, acc->right);
-		if (altx < x)
-		    x = altx;
-	    }
-	    linx = -ICEIL(acc->fromIntX - x);
-	    rinx = ICEIL(acc->fromIntX + x);
-	}
-	if (boundedLe (y, bounds->outeri)) {
-	    loutx = -lx;
-	    routx = rx + rw;
-	} else {
-	    /*
-	     * intersection with right face
-	     */
-	    x = hookX (y + acc->fromIntY, def, bounds, acc, 0);
-	    if (acc->left.valid &&
-		boundedLe (y + acc->fromIntY, bounds->left))
-	    {
-		altx = x;
-		x = intersectLine (y + acc->fromIntY, acc->left);
-		if (x < altx)
-		    x = altx;
-	    }
-	    loutx = -ICEIL(acc->fromIntX - x);
-	    routx = ICEIL(acc->fromIntX + x);
-	}
-	if (routx > rinx) {
-	    if (mask & 1)
-		newFinalSpan (acc->yorgu - y,
-			      acc->xorg + rinx, acc->xorg + routx);
-	    if (mask & 8)
-		newFinalSpan (acc->yorgl + y,
-			      acc->xorg + rinx, acc->xorg + routx);
-	}
-	if (loutx > linx) {
-	    if (mask & 2)
-		newFinalSpan (acc->yorgu - y,
-			      acc->xorg - loutx, acc->xorg - linx);
-	    if (mask & 4)
-		newFinalSpan (acc->yorgl + y,
-			      acc->xorg - loutx, acc->xorg - linx);
-	}
-}
-
-static void
-arcSpan0 (
-	int			lx,
-	int			lw,
-	int			rx,
-	int			rw,
-	struct arc_def		*def,
-	struct arc_bound	*bounds,
-	struct accelerators	*acc,
-	int			mask)
-{
-    double x;
-
-    if (boundedLe (0, bounds->inneri) &&
-	acc->left.valid && boundedLe (0, bounds->left) &&
-	acc->left.b > 0)
-    {
-	x = def->w - def->l;
-	if (acc->left.b < x)
-	    x = acc->left.b;
-	lw = ICEIL(acc->fromIntX - x) - lx;
-	rw += rx;
-	rx = ICEIL(acc->fromIntX + x);
-	rw -= rx;
-    }
-    arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);
-}
-
-static void
-tailSpan (
-	int			y,
-	int			lw,
-	int			rw,
-	struct arc_def		*def,
-	struct arc_bound	*bounds,
-	struct accelerators	*acc,
-	int			mask)
-{
-    double yy, xalt, x, lx, rx;
-    int n;
-
-    if (boundedLe(y, bounds->outeri))
-	arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);
-    else if (def->w != def->h) {
-	yy = y + acc->fromIntY;
-	x = tailX(yy, def, bounds, acc);
-	if (yy == 0.0 && x == -rw - acc->fromIntX)
-	    return;
-	if (acc->right.valid && boundedLe (yy, bounds->right)) {
-	    rx = x;
-	    lx = -x;
-	    xalt = intersectLine (yy, acc->right);
-	    if (xalt >= -rw - acc->fromIntX && xalt <= rx)
-		rx = xalt;
-	    n = ICEIL(acc->fromIntX + lx);
-	    if (lw > n) {
-		if (mask & 2)
-		    newFinalSpan (acc->yorgu - y,
-				  acc->xorg + n, acc->xorg + lw);
-		if (mask & 4)
-		    newFinalSpan (acc->yorgl + y,
-				  acc->xorg + n, acc->xorg + lw);
-	    }
-	    n = ICEIL(acc->fromIntX + rx);
-	    if (n > -rw) {
-		if (mask & 1)
-		    newFinalSpan (acc->yorgu - y,
-				  acc->xorg - rw, acc->xorg + n);
-		if (mask & 8)
-		    newFinalSpan (acc->yorgl + y,
-				  acc->xorg - rw, acc->xorg + n);
-	    }
-	}
-	arcSpan (y,
-		 ICEIL(acc->fromIntX - x), 0,
-		 ICEIL(acc->fromIntX + x), 0,
-		 def, bounds, acc, mask);
-    }
-}
-
-/*
- * create whole arcs out of pieces.  This code is
- * very bad.
- */
-
-static struct finalSpan	**finalSpans = NULL;
-static int		finalMiny = 0, finalMaxy = -1;
-static int		finalSize = 0;
-
-static int		nspans = 0;	/* total spans, not just y coords */
-
-struct finalSpan {
-	struct finalSpan	*next;
-	int			min, max;	/* x values */
-};
-
-static struct finalSpan    *freeFinalSpans, *tmpFinalSpan;
-
-# define allocFinalSpan()   (freeFinalSpans ?\
-				((tmpFinalSpan = freeFinalSpans), \
-				 (freeFinalSpans = freeFinalSpans->next), \
-				 (tmpFinalSpan->next = 0), \
-				 tmpFinalSpan) : \
-			     realAllocSpan ())
-
-# define SPAN_CHUNK_SIZE    128
-
-struct finalSpanChunk {
-	struct finalSpan	data[SPAN_CHUNK_SIZE];
-	struct finalSpanChunk	*next;
-};
-
-static struct finalSpanChunk	*chunks;
-
-static struct finalSpan *
-realAllocSpan (void)
-{
-	struct finalSpanChunk	*newChunk;
-	struct finalSpan	*span;
-	int			i;
-
-	newChunk = xalloc (sizeof (struct finalSpanChunk));
-	if (!newChunk)
-		return (struct finalSpan *) NULL;
-	newChunk->next = chunks;
-	chunks = newChunk;
-	freeFinalSpans = span = newChunk->data + 1;
-	for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {
-		span->next = span+1;
-		span++;
-	}
-	span->next = 0;
-	span = newChunk->data;
-	span->next = 0;
-	return span;
-}
-
-static void
-disposeFinalSpans (void)
-{
-	struct finalSpanChunk	*chunk, *next;
-
-	for (chunk = chunks; chunk; chunk = next) {
-		next = chunk->next;
-		xfree (chunk);
-	}
-	chunks = 0;
-	freeFinalSpans = 0;
-	xfree(finalSpans);
-	finalSpans = 0;
-}
-
-static void
-fillSpans (
-    DrawablePtr	pDrawable,
-    GCPtr	pGC)
-{
-	struct finalSpan	*span;
-	DDXPointPtr		xSpan;
-	int			*xWidth;
-	int			i;
-	struct finalSpan	**f;
-	int			spany;
-	DDXPointPtr		xSpans;
-	int			*xWidths;
-
-	if (nspans == 0)
-		return;
-	xSpan = xSpans = xalloc (nspans * sizeof (DDXPointRec));
-	xWidth = xWidths = xalloc (nspans * sizeof (int));
-	if (xSpans && xWidths)
-	{
-	    i = 0;
-	    f = finalSpans;
-	    for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {
-		    for (span = *f; span; span=span->next) {
-			    if (span->max <= span->min)
-				    continue;
-			    xSpan->x = span->min;
-			    xSpan->y = spany;
-			    ++xSpan;
-			    *xWidth++ = span->max - span->min;
-			    ++i;
-		    }
-	    }
-	    (*pGC->ops->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);
-	}
-	disposeFinalSpans ();
-	if (xSpans)
-	    xfree (xSpans);
-	if (xWidths)
-	    xfree (xWidths);
-	finalMiny = 0;
-	finalMaxy = -1;
-	finalSize = 0;
-	nspans = 0;
-}
-
-# define SPAN_REALLOC	100
-
-# define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \
-			  &finalSpans[(y) - finalMiny] : \
-			  realFindSpan (y))
-
-static struct finalSpan **
-realFindSpan (int y)
-{
-	struct finalSpan	**newSpans;
-	int			newSize, newMiny, newMaxy;
-	int			change;
-	int			i;
-
-	if (y < finalMiny || y > finalMaxy) {
-		if (!finalSize) {
-			finalMiny = y;
-			finalMaxy = y - 1;
-		}
-		if (y < finalMiny)
-			change = finalMiny - y;
-		else
-			change = y - finalMaxy;
-		if (change >= SPAN_REALLOC)
-			change += SPAN_REALLOC;
-		else
-			change = SPAN_REALLOC;
-		newSize = finalSize + change;
-		newSpans = xalloc(newSize * sizeof (struct finalSpan *));
-		if (!newSpans)
-		    return NULL;
-		newMiny = finalMiny;
-		newMaxy = finalMaxy;
-		if (y < finalMiny)
-			newMiny = finalMiny - change;
-		else
-			newMaxy = finalMaxy + change;
-		if (finalSpans) {
-			memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),
-				(char *) finalSpans,
-			       finalSize * sizeof (struct finalSpan *));
-			xfree (finalSpans);
-		}
-		if ((i = finalMiny - newMiny) > 0)
-			bzero ((char *)newSpans, i * sizeof (struct finalSpan *));
-		if ((i = newMaxy - finalMaxy) > 0)
-			bzero ((char *)(newSpans + newSize - i),
-			       i * sizeof (struct finalSpan *));
-		finalSpans = newSpans;
-		finalMaxy = newMaxy;
-		finalMiny = newMiny;
-		finalSize = newSize;
-	}
-	return &finalSpans[y - finalMiny];
-}
-
-static void
-newFinalSpan (
-    int		y,
-    int	xmin,
-    int	xmax)
-{
-	struct finalSpan	*x;
-	struct finalSpan	**f;
-	struct finalSpan	*oldx;
-	struct finalSpan	*prev;
-
-	f = findSpan (y);
-	if (!f)
-	    return;
-	oldx = 0;
-	for (;;) {
-		prev = 0;
-		for (x = *f; x; x=x->next) {
-			if (x == oldx) {
-				prev = x;
-				continue;
-			}
-			if (x->min <= xmax && xmin <= x->max) {
-				if (oldx) {
-					oldx->min = min (x->min, xmin);
-					oldx->max = max (x->max, xmax);
-					if (prev)
-						prev->next = x->next;
-					else
-						*f = x->next;
-					--nspans;
-				} else {
-					x->min = min (x->min, xmin);
-					x->max = max (x->max, xmax);
-					oldx = x;
-				}
-				xmin = oldx->min;
-				xmax = oldx->max;
-				break;
-			}
-			prev = x;
-		}
-		if (!x)
-			break;
-	}
-	if (!oldx) {
-		x = allocFinalSpan ();
-		if (x)
-		{
-		    x->min = xmin;
-		    x->max = xmax;
-		    x->next = *f;
-		    *f = x;
-		    ++nspans;
-		}
-	}
-}
-
-static void
-mirrorSppPoint (
-	int		quadrant,
-	SppPointPtr	sppPoint)
-{
-	switch (quadrant) {
-	case 0:
-		break;
-	case 1:
-		sppPoint->x = -sppPoint->x;
-		break;
-	case 2:
-		sppPoint->x = -sppPoint->x;
-		sppPoint->y = -sppPoint->y;
-		break;
-	case 3:
-		sppPoint->y = -sppPoint->y;
-		break;
-	}
-	/*
-	 * and translate to X coordinate system
-	 */
-	sppPoint->y = -sppPoint->y;
-}
-
-/*
- * split an arc into pieces which are scan-converted
- * in the first-quadrant and mirrored into position.
- * This is necessary as the scan-conversion code can
- * only deal with arcs completely contained in the
- * first quadrant.
- */
-
-static void
-drawArc (
-	xArc *tarc,
-	int	l,
-	int	a0,
-	int	a1,
-	miArcFacePtr	right,
-	miArcFacePtr	left)	/* save end line points */
-{
-	struct arc_def		def;
-	struct accelerators	acc;
-	int			startq, endq, curq;
-	int			rightq, leftq = 0, righta = 0, lefta = 0;
-	miArcFacePtr		passRight, passLeft;
-	int			q0 = 0, q1 = 0, mask;
-	struct band {
-		int	a0, a1;
-		int	mask;
-	}	band[5], sweep[20];
-	int			bandno, sweepno;
-	int			i, j;
-	int			flipRight = 0, flipLeft = 0;			
-	int			copyEnd = 0;
-	miArcSpanData		*spdata;
-	Bool			mustFree;
-
-	spdata = miComputeWideEllipse(l, tarc, &mustFree);
-	if (!spdata)
-	    return;
-
-	if (a1 < a0)
-		a1 += 360 * 64;
-	startq = a0 / (90 * 64);
-	if (a0 == a1)
-	    endq = startq;
-	else
-	    endq = (a1-1) / (90 * 64);
-	bandno = 0;
-	curq = startq;
-	rightq = -1;
-	for (;;) {
-		switch (curq) {
-		case 0:
-			if (a0 > 90 * 64)
-				q0 = 0;
-			else
-				q0 = a0;
-			if (a1 < 360 * 64)
-				q1 = min (a1, 90 * 64);
-			else
-				q1 = 90 * 64;
-			if (curq == startq && a0 == q0 && rightq < 0) {
-				righta = q0;
-				rightq = curq;
-			}
-			if (curq == endq && a1 == q1) {
-				lefta = q1;
-				leftq = curq;
-			}
-			break;
-		case 1:
-			if (a1 < 90 * 64)
-				q0 = 0;
-			else
-				q0 = 180 * 64 - min (a1, 180 * 64);
-			if (a0 > 180 * 64)
-				q1 = 90 * 64;
-			else
-				q1 = 180 * 64 - max (a0, 90 * 64);
-			if (curq == startq && 180 * 64 - a0 == q1) {
-				righta = q1;
-				rightq = curq;
-			}
-			if (curq == endq && 180 * 64 - a1 == q0) {
-				lefta = q0;
-				leftq = curq;
-			}
-			break;
-		case 2:
-			if (a0 > 270 * 64)
-				q0 = 0;
-			else
-				q0 = max (a0, 180 * 64) - 180 * 64;
-			if (a1 < 180 * 64)
-				q1 = 90 * 64;
-			else
-				q1 = min (a1, 270 * 64) - 180 * 64;
-			if (curq == startq && a0 - 180*64 == q0) {
-				righta = q0;
-				rightq = curq;
-			}
-			if (curq == endq && a1 - 180 * 64 == q1) {
-				lefta = q1;
-				leftq = curq;
-			}
-			break;
-		case 3:
-			if (a1 < 270 * 64)
-				q0 = 0;
-			else
-				q0 = 360 * 64 - min (a1, 360 * 64);
-			q1 = 360 * 64 - max (a0, 270 * 64);
-			if (curq == startq && 360 * 64 - a0 == q1) {
-				righta = q1;
-				rightq = curq;
-			}
-			if (curq == endq && 360 * 64 - a1 == q0) {
-				lefta = q0;
-				leftq = curq;
-			}
-			break;
-		}
-		band[bandno].a0 = q0;
-		band[bandno].a1 = q1;
-		band[bandno].mask = 1 << curq;
-		bandno++;
-		if (curq == endq)
-			break;
-		curq++;
-		if (curq == 4) {
-			a0 = 0;
-			a1 -= 360 * 64;
-			curq = 0;
-			endq -= 4;
-		}
-	}
-	sweepno = 0;
-	for (;;) {
-		q0 = 90 * 64;
-		mask = 0;
-		/*
-		 * find left-most point
-		 */
-		for (i = 0; i < bandno; i++)
-			if (band[i].a0 <= q0) {
-				q0 = band[i].a0;
-				q1 = band[i].a1;
-				mask = band[i].mask;
-			}
-		if (!mask)
-			break;
-		/*
-		 * locate next point of change
-		 */
-		for (i = 0; i < bandno; i++)
-			if (!(mask & band[i].mask)) {
-				if (band[i].a0 == q0) {
-					if (band[i].a1 < q1)
-						q1 = band[i].a1;
-					mask |= band[i].mask;
- 				} else if (band[i].a0 < q1)
-					q1 = band[i].a0;
-			}
-		/*
-		 * create a new sweep
-		 */
-		sweep[sweepno].a0 = q0;
-		sweep[sweepno].a1 = q1;
-		sweep[sweepno].mask = mask;
-		sweepno++;
-		/*
-		 * subtract the sweep from the affected bands
-		 */
-		for (i = 0; i < bandno; i++)
-			if (band[i].a0 == q0) {
-				band[i].a0 = q1;
-				/*
-				 * check if this band is empty
-				 */
-				if (band[i].a0 == band[i].a1)
-					band[i].a1 = band[i].a0 = 90 * 64 + 1;
-			}
-	}
-	computeAcc (tarc, l, &def, &acc);
-	for (j = 0; j < sweepno; j++) {
-		mask = sweep[j].mask;
-		passRight = passLeft = 0;
- 		if (mask & (1 << rightq)) {
-			if (sweep[j].a0 == righta)
-				passRight = right;
-			else if (sweep[j].a1 == righta) {
-				passLeft = right;
-				flipRight = 1;
-			}
-		}
-		if (mask & (1 << leftq)) {
-			if (sweep[j].a1 == lefta)
-			{
-				if (passLeft)
-					copyEnd = 1;
-				passLeft = left;
-			}
-			else if (sweep[j].a0 == lefta) {
-				if (passRight)
-					copyEnd = 1;
-				passRight = left;
-				flipLeft = 1;
-			}
-		}
-		drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask, 
- 			      passRight, passLeft, spdata);
-	}
-	/*
-	 * when copyEnd is set, both ends of the arc were computed
-	 * at the same time; drawQuadrant only takes one end though,
-	 * so the left end will be the only one holding the data.  Copy
-	 * it from there.
-	 */
-	if (copyEnd)
-		*right = *left;
-	/*
-	 * mirror the coordinates generated for the
-	 * faces of the arc
-	 */
-	if (right) {
-		mirrorSppPoint (rightq, &right->clock);
-		mirrorSppPoint (rightq, &right->center);
-		mirrorSppPoint (rightq, &right->counterClock);
-		if (flipRight) {
-			SppPointRec	temp;
-
-			temp = right->clock;
-			right->clock = right->counterClock;
-			right->counterClock = temp;
-		}
-	}
-	if (left) {
-		mirrorSppPoint (leftq,  &left->counterClock);
-		mirrorSppPoint (leftq,  &left->center);
-		mirrorSppPoint (leftq,  &left->clock);
-		if (flipLeft) {
-			SppPointRec	temp;
-
-			temp = left->clock;
-			left->clock = left->counterClock;
-			left->counterClock = temp;
-		}
-	}
-	if (mustFree)
-	    xfree(spdata);
-}
-
-static void
-drawQuadrant (
-	struct arc_def		*def,
-	struct accelerators	*acc,
-	int			a0,
-	int			a1,
-	int			mask,
-	miArcFacePtr		right,
-	miArcFacePtr		left,
-	miArcSpanData		*spdata)
-{
-	struct arc_bound	bound;
-	double			yy, x, xalt;
-	int			y, miny, maxy;
-	int			n;
-	miArcSpan		*span;
-
-	def->a0 = ((double) a0) / 64.0;
-	def->a1 = ((double) a1) / 64.0;
-	computeBound (def, &bound, acc, right, left);
-	yy = bound.inner.min;
-	if (bound.outer.min < yy)
-	    yy = bound.outer.min;
-	miny = ICEIL(yy - acc->fromIntY);
-	yy = bound.inner.max;
-	if (bound.outer.max > yy)
-	    yy = bound.outer.max;
-	maxy = floor(yy - acc->fromIntY);
-	y = spdata->k;
-	span = spdata->spans;
-	if (spdata->top)
-	{
-	    if (a1 == 90 * 64 && (mask & 1))
-		newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);
-	    span++;
-	}
-	for (n = spdata->count1; --n >= 0; )
-	{
-	    if (y < miny)
-		return;
-	    if (y <= maxy) {
-		arcSpan (y,
-			 span->lx, -span->lx, 0, span->lx + span->lw,
-			 def, &bound, acc, mask);
-		if (span->rw + span->rx)
-		    tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);
-	    }
-	    y--;
-	    span++;
-	}
-	if (y < miny)
-	    return;
-	if (spdata->hole)
-	{
-	    if (y <= maxy)
-		arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);
-	}
-	for (n = spdata->count2; --n >= 0; )
-	{
-	    if (y < miny)
-		return;
-	    if (y <= maxy)
-		arcSpan (y, span->lx, span->lw, span->rx, span->rw,
-			 def, &bound, acc, mask);
-	    y--;
-	    span++;
-	}
-	if (spdata->bot && miny <= y && y <= maxy)
-	{
-	    n = mask;
-	    if (y == miny)
-		n &= 0xc;
-	    if (span->rw <= 0) {
-		arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,
-			  def, &bound, acc, n);
-		if (span->rw + span->rx)
-		    tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);
-	    }
-	    else
-		arcSpan0 (span->lx, span->lw, span->rx, span->rw,
-			  def, &bound, acc, n);
-	    y--;
-	}
-	while (y >= miny) {
-	    yy = y + acc->fromIntY;
-	    if (def->w == def->h) {
-		xalt = def->w - def->l;
-		x = -sqrt(xalt * xalt - yy * yy);
-	    } else {
-		x = tailX(yy, def, &bound, acc);
-		if (acc->left.valid && boundedLe (yy, bound.left)) {
-		    xalt = intersectLine (yy, acc->left);
-		    if (xalt < x)
-			x = xalt;
-		}
-		if (acc->right.valid && boundedLe (yy, bound.right)) {
-		    xalt = intersectLine (yy, acc->right);
-		    if (xalt < x)
-			x = xalt;
-		}
-	    }
-	    arcSpan (y,
-		     ICEIL(acc->fromIntX - x), 0,
-		     ICEIL(acc->fromIntX + x), 0,
-		     def, &bound, acc, mask);
-	    y--;
-	}
-}
+/***********************************************************

+

+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.

+

+******************************************************************/

+/* Author: Keith Packard and Bob Scheifler */

+/* Warning: this code is toxic, do not dally very long here. */

+

+#ifdef HAVE_DIX_CONFIG_H

+#include <dix-config.h>

+#endif

+

+#include <math.h>

+#include <X11/X.h>

+#include <X11/Xprotostr.h>

+#include "misc.h"

+#include "gcstruct.h"

+#include "scrnintstr.h"

+#include "pixmapstr.h"

+#include "windowstr.h"

+#include "mifpoly.h"

+#include "mi.h"

+#include "mifillarc.h"

+#include <X11/Xfuncproto.h>

+

+static double miDsin(double a);

+static double miDcos(double a);

+static double miDasin(double v);

+static double miDatan2(double dy, double dx);

+

+#ifndef HAVE_CBRT

+static double

+cbrt(double x)

+{

+    if (x > 0.0)

+	return pow(x, 1.0/3.0);

+    else

+	return -pow(-x, 1.0/3.0);

+}

+#endif

+

+/*

+ * some interesting sematic interpretation of the protocol:

+ *

+ * 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

+ *  first segment, when no caps are drawn)

+ *

+ * double dash arcs are drawn in two parts, first the

+ *  odd dashes (drawn in background) then the even dashes

+ *  (drawn in foreground).  This means that overlapping

+ *  sections of foreground/background are drawn twice,

+ *  first in background then in foreground.  The double-draw

+ *  occurs even when the function uses the destination values

+ *  (e.g. xor mode).  This is the same way the wide-line

+ *  code works and should be "fixed".

+ *

+ */

+

+#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;

+};

+

+struct ibound {

+	int	min, max;

+};

+

+#define boundedLe(value, bounds)\

+	((bounds).min <= (value) && (value) <= (bounds).max)

+

+struct line {

+	double	m, b;

+	int	valid;

+};

+

+#define intersectLine(y,line) (line.m * (y) + line.b)

+

+/*

+ * these are all y value bounds

+ */

+

+struct arc_bound {

+	struct bound	ellipse;

+	struct bound	inner;

+	struct bound	outer;

+	struct bound	right;

+	struct bound	left;

+	struct ibound	inneri;

+	struct ibound	outeri;

+};

+

+struct accelerators {

+	double		tail_y;

+	double		h2;

+	double		w2;

+	double		h4;

+	double		w4;

+	double		h2mw2;

+	double		h2l;

+	double		w2l;

+	double		fromIntX;

+	double		fromIntY;

+	struct line	left, right;

+	int		yorgu;

+	int		yorgl;

+	int		xorg;

+};

+

+struct arc_def {

+	double	w, h, l;

+	double	a0, a1;

+};

+

+# define todeg(xAngle)	(((double) (xAngle)) / 64.0)

+

+# define RIGHT_END	0

+# define LEFT_END	1

+

+typedef struct _miArcJoin {

+	int	arcIndex0, arcIndex1;

+	int	phase0, phase1;

+	int	end0, end1;

+} miArcJoinRec, *miArcJoinPtr;

+

+typedef struct _miArcCap {

+	int		arcIndex;

+	int		end;		

+} miArcCapRec, *miArcCapPtr;

+

+typedef struct _miArcFace {

+	SppPointRec	clock;

+	SppPointRec	center;

+	SppPointRec	counterClock;

+} miArcFaceRec, *miArcFacePtr;

+

+typedef struct _miArcData {

+	xArc		arc;

+	int		render;		/* non-zero means render after drawing */

+	int		join;		/* related join */

+	int		cap;		/* related cap */

+	int		selfJoin;	/* final dash meets first dash */

+	miArcFaceRec	bounds[2];

+	double		x0, y0, x1, y1;

+} miArcDataRec, *miArcDataPtr;

+

+/*

+ * This is an entire sequence of arcs, computed and categorized according

+ * to operation.  miDashArcs generates either one or two of these.

+ */

+

+typedef struct _miPolyArc {

+	int		narcs;

+	miArcDataPtr	arcs;

+	int		ncaps;

+	miArcCapPtr	caps;

+	int		njoins;

+	miArcJoinPtr	joins;

+} miPolyArcRec, *miPolyArcPtr;

+

+#define GCValsFunction		0

+#define GCValsForeground 	1

+#define GCValsBackground 	2

+#define GCValsLineWidth 	3

+#define GCValsCapStyle 		4

+#define GCValsJoinStyle		5

+#define GCValsMask		(GCFunction | GCForeground | GCBackground | \

+				 GCLineWidth | GCCapStyle | GCJoinStyle)

+static CARD32 gcvals[6];

+

+static void fillSpans(DrawablePtr pDrawable, GCPtr pGC);

+static void newFinalSpan(int y, int xmin, int xmax);

+static void drawArc(xArc *tarc, int l, int a0, int a1, miArcFacePtr right,

+		    miArcFacePtr left);

+static void drawZeroArc(DrawablePtr pDraw, GCPtr pGC, xArc *tarc, int lw,

+			miArcFacePtr left, miArcFacePtr right);

+static void miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,

+		      miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,

+		      double xFtransLeft, double yFtransLeft,

+		      int xOrgRight, int yOrgRight,

+		      double xFtransRight, double yFtransRight);

+static void miArcCap(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pFace,

+		     int end, int xOrg, int yOrg, double xFtrans,

+		     double yFtrans);

+static void miRoundCap(DrawablePtr pDraw, GCPtr pGC, SppPointRec pCenter,

+		       SppPointRec pEnd, SppPointRec pCorner,

+		       SppPointRec pOtherCorner, int fLineEnd,

+		       int xOrg, int yOrg, double xFtrans, double yFtrans);

+static void miFreeArcs(miPolyArcPtr arcs, GCPtr pGC);

+static miPolyArcPtr miComputeArcs(xArc *parcs, int narcs, GCPtr pGC);

+static int miGetArcPts(SppArcPtr parc, int cpt, SppPointPtr *ppPts);

+

+# define CUBED_ROOT_2	1.2599210498948732038115849718451499938964

+# define CUBED_ROOT_4	1.5874010519681993173435330390930175781250

+

+/*

+ * draw one segment of the arc using the arc spans generation routines

+ */

+

+static void

+miArcSegment(

+    DrawablePtr   pDraw,

+    GCPtr         pGC,

+    xArc          tarc,

+    miArcFacePtr	right,

+    miArcFacePtr	left)

+{

+    int l = pGC->lineWidth;

+    int a0, a1, startAngle, endAngle;

+    miArcFacePtr temp;

+

+    if (!l)

+	l = 1;

+

+    if (tarc.width == 0 || tarc.height == 0) {

+    	drawZeroArc (pDraw, pGC, &tarc, l, left, right);

+	return;

+    }

+

+    if (pGC->miTranslate) {

+	tarc.x += pDraw->x;

+	tarc.y += pDraw->y;

+    }

+

+    a0 = tarc.angle1;

+    a1 = tarc.angle2;

+    if (a1 > FULLCIRCLE)

+	a1 = FULLCIRCLE;

+    else if (a1 < -FULLCIRCLE)

+	a1 = -FULLCIRCLE;

+    if (a1 < 0) {

+    	startAngle = a0 + a1;

+	endAngle = a0;

+	temp = right;

+	right = left;

+	left = temp;

+    } else {

+	startAngle = a0;

+	endAngle = a0 + a1;

+    }

+    /*

+     * bounds check the two angles

+     */

+    if (startAngle < 0)

+	startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;

+    if (startAngle >= FULLCIRCLE)

+	startAngle = startAngle % FULLCIRCLE;

+    if (endAngle < 0)

+	endAngle = FULLCIRCLE - (-endAngle) % FULLCIRCLE;

+    if (endAngle > FULLCIRCLE)

+	endAngle = (endAngle-1) % FULLCIRCLE + 1;

+    if ((startAngle == endAngle) && a1) {

+	startAngle = 0;

+	endAngle = FULLCIRCLE;

+    }

+

+    drawArc (&tarc, l, startAngle, endAngle, right, left);

+}

+

+/*

+

+Three equations combine to describe the boundaries of the arc

+

+x^2/w^2 + y^2/h^2 = 1			ellipse itself

+(X-x)^2 + (Y-y)^2 = r^2			circle at (x, y) on the ellipse

+(Y-y) = (X-x)*w^2*y/(h^2*x)		normal at (x, y) on the ellipse

+

+These lead to a quartic relating Y and y

+

+y^4 - (2Y)y^3 + (Y^2 + (h^4 - w^2*r^2)/(w^2 - h^2))y^2

+    - (2Y*h^4/(w^2 - h^2))y + (Y^2*h^4)/(w^2 - h^2) = 0

+

+The reducible cubic obtained from this quartic is

+

+z^3 - (3N)z^2 - 2V = 0

+

+where

+

+N = (Y^2 + (h^4 - w^2*r^2/(w^2 - h^2)))/6

+V = w^2*r^2*Y^2*h^4/(4 *(w^2 - h^2)^2)

+

+Let

+

+t = z - N

+p = -N^2

+q = -N^3 - V

+

+Then we get

+

+t^3 + 3pt + 2q = 0

+

+The discriminant of this cubic is

+

+D = q^2 + p^3

+

+When D > 0, a real root is obtained as

+

+z = N + cbrt(-q+sqrt(D)) + cbrt(-q-sqrt(D))

+

+When D < 0, a real root is obtained as

+

+z = N - 2m*cos(acos(-q/m^3)/3)

+

+where

+

+m = sqrt(|p|) * sign(q)

+

+Given a real root Z of the cubic, the roots of the quartic are the roots

+of the two quadratics

+

+y^2 + ((b+A)/2)y + (Z + (bZ - d)/A) = 0

+

+where 

+

+A = +/- sqrt(8Z + b^2 - 4c)

+b, c, d are the cubic, quadratic, and linear coefficients of the quartic

+

+Some experimentation is then required to determine which solutions

+correspond to the inner and outer boundaries.

+

+*/

+

+typedef struct {

+    short lx, lw, rx, rw;

+} miArcSpan;

+

+typedef struct {

+    miArcSpan *spans;

+    int count1, count2, k;

+    char top, bot, hole;

+} miArcSpanData;

+

+static void drawQuadrant(struct arc_def *def, struct accelerators *acc,

+			 int a0, int a1, int mask, miArcFacePtr right,

+			 miArcFacePtr left, miArcSpanData *spdata);

+

+static void

+miComputeCircleSpans(

+    int lw,

+    xArc *parc,

+    miArcSpanData *spdata)

+{

+    miArcSpan *span;

+    int doinner;

+    int x, y, e;

+    int xk, yk, xm, ym, dx, dy;

+    int slw, inslw;

+    int inx = 0, iny, ine = 0;

+    int inxk = 0, inyk = 0, inxm = 0, inym = 0;

+

+    doinner = -lw;

+    slw = parc->width - doinner;

+    y = parc->height >> 1;

+    dy = parc->height & 1;

+    dx = 1 - dy;

+    MIWIDEARCSETUP(x, y, dy, slw, e, xk, xm, yk, ym);

+    inslw = parc->width + doinner;

+    if (inslw > 0)

+    {

+	spdata->hole = spdata->top;

+	MIWIDEARCSETUP(inx, iny, dy, inslw, ine, inxk, inxm, inyk, inym);

+    }

+    else

+    {

+	spdata->hole = FALSE;

+	doinner = -y;

+    }

+    spdata->count1 = -doinner - spdata->top;

+    spdata->count2 = y + doinner;

+    span = spdata->spans;

+    while (y)

+    {

+	MIFILLARCSTEP(slw);

+	span->lx = dy - x;

+	if (++doinner <= 0)

+ 	{

+	    span->lw = slw;

+	    span->rx = 0;

+	    span->rw = span->lx + slw;

+	}

+	else

+	{

+	    MIFILLINARCSTEP(inslw);

+	    span->lw = x - inx;

+	    span->rx = dy - inx + inslw;

+	    span->rw = inx - x + slw - inslw;

+	}

+	span++;

+    }

+    if (spdata->bot)

+    {

+	if (spdata->count2)

+	    spdata->count2--;

+	else

+	{

+	    if (lw > (int)parc->height)

+		span[-1].rx = span[-1].rw = -((lw - (int)parc->height) >> 1);

+	    else

+		span[-1].rw = 0;

+	    spdata->count1--;

+	}

+    }

+}

+

+static void

+miComputeEllipseSpans(

+    int lw,

+    xArc *parc,

+    miArcSpanData *spdata)

+{

+    miArcSpan *span;

+    double w, h, r, xorg;

+    double Hs, Hf, WH, K, Vk, Nk, Fk, Vr, N, Nc, Z, rs;

+    double A, T, b, d, x, y, t, inx, outx = 0.0, hepp, hepm;

+    int flip, solution;

+

+    w = (double)parc->width / 2.0;

+    h = (double)parc->height / 2.0;

+    r = lw / 2.0;

+    rs = r * r;

+    Hs = h * h;

+    WH = w * w - Hs;

+    Nk = w * r;

+    Vk = (Nk * Hs) / (WH + WH);

+    Hf = Hs * Hs;

+    Nk = (Hf - Nk * Nk) / WH;

+    Fk = Hf / WH;

+    hepp = h + EPSILON;

+    hepm = h - EPSILON;

+    K = h + ((lw - 1) >> 1);

+    span = spdata->spans;

+    if (parc->width & 1)

+	xorg = .5;

+    else

+	xorg = 0.0;

+    if (spdata->top)

+    {

+	span->lx = 0;

+	span->lw = 1;

+	span++;

+    }

+    spdata->count1 = 0;

+    spdata->count2 = 0;

+    spdata->hole = (spdata->top &&

+		 (int)parc->height * lw <= (int)(parc->width * parc->width) &&

+		    lw < (int)parc->height);

+    for (; K > 0.0; K -= 1.0)

+    {

+	N = (K * K + Nk) / 6.0;

+	Nc = N * N * N;

+	Vr = Vk * K;

+	t = Nc + Vr * Vr;

+	d = Nc + t;

+	if (d < 0.0) {

+	    d = Nc;

+	    b = N;

+	    if ( (b < 0.0) == (t < 0.0) )

+	    {

+		b = -b;

+		d = -d;

+	    }

+	    Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);

+	    if ( (Z < 0.0) == (Vr < 0.0) )

+		flip = 2;

+	    else

+		flip = 1;

+	}

+	else

+	{

+	    d = Vr * sqrt(d);

+	    Z = N + cbrt(t + d) + cbrt(t - d);

+	    flip = 0;

+	}

+	A = sqrt((Z + Z) - Nk);

+	T = (Fk - Z) * K / A;

+	inx = 0.0;

+	solution = FALSE;

+	b = -A + K;

+	d = b * b - 4 * (Z + T);

+	if (d >= 0)

+	{

+	    d = sqrt(d);

+	    y = (b + d) / 2;

+	    if ((y >= 0.0) && (y < hepp))

+	    {

+		solution = TRUE;

+		if (y > hepm)

+		    y = h;

+		t = y / h;

+		x = w * sqrt(1 - (t * t));

+		t = K - y;

+		if (rs - (t * t) >= 0)

+		   t = sqrt(rs - (t * t));

+		else

+		   t = 0;

+		if (flip == 2)

+		    inx = x - t;

+		else

+		    outx = x + t;

+	    }

+	}

+	b = A + K;

+	d = b * b - 4 * (Z - T);

+	/* Because of the large magnitudes involved, we lose enough precision

+	 * that sometimes we end up with a negative value near the axis, when

+	 * it should be positive.  This is a workaround.

+	 */

+	if (d < 0 && !solution)

+	    d = 0.0;

+	if (d >= 0) {

+	    d = sqrt(d);

+	    y = (b + d) / 2;

+	    if (y < hepp)

+	    {

+		if (y > hepm)

+		    y = h;

+		t = y / h;

+		x = w * sqrt(1 - (t * t));

+		t = K - y;

+		if (rs - (t * t) >= 0)

+		   inx = x - sqrt(rs - (t * t));

+		else

+		   inx = x;

+	    }

+	    y = (b - d) / 2;

+	    if (y >= 0.0)

+	    {

+		if (y > hepm)

+		    y = h;

+		t = y / h;

+		x = w * sqrt(1 - (t * t));

+		t = K - y;

+		if (rs - (t * t) >= 0)

+		   t = sqrt(rs - (t * t));

+		else 

+		   t = 0;

+		if (flip == 1)

+		    inx = x - t;

+		else

+		    outx = x + t;

+	    }

+	}

+	span->lx = ICEIL(xorg - outx);

+	if (inx <= 0.0)

+	{

+	    spdata->count1++;

+	    span->lw = ICEIL(xorg + outx) - span->lx;

+	    span->rx = ICEIL(xorg + inx);

+	    span->rw = -ICEIL(xorg - inx);

+	}

+	else

+	{

+	    spdata->count2++;

+	    span->lw = ICEIL(xorg - inx) - span->lx;

+	    span->rx = ICEIL(xorg + inx);

+	    span->rw = ICEIL(xorg + outx) - span->rx;

+	}

+	span++;

+    }

+    if (spdata->bot)

+    {

+	outx = w + r;

+	if (r >= h && r <= w)

+	    inx = 0.0;

+	else if (Nk < 0.0 && -Nk < Hs)

+	{

+	    inx = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);

+	    if (inx > w - r)

+		inx = w - r;

+	}

+	else

+	    inx = w - r;

+	span->lx = ICEIL(xorg - outx);

+	if (inx <= 0.0)

+	{

+	    span->lw = ICEIL(xorg + outx) - span->lx;

+	    span->rx = ICEIL(xorg + inx);

+	    span->rw = -ICEIL(xorg - inx);

+	}

+	else

+	{

+	    span->lw = ICEIL(xorg - inx) - span->lx;

+	    span->rx = ICEIL(xorg + inx);

+	    span->rw = ICEIL(xorg + outx) - span->rx;

+	}

+    }

+    if (spdata->hole)

+    {

+	span = &spdata->spans[spdata->count1];

+	span->lw = -span->lx;

+	span->rx = 1;

+	span->rw = span->lw;

+	spdata->count1--;

+	spdata->count2++;

+    }

+}

+

+static double

+tailX(

+    double K,

+    struct arc_def *def,

+    struct arc_bound *bounds,

+    struct accelerators *acc)

+{

+    double w, h, r;

+    double Hs, Hf, WH, Vk, Nk, Fk, Vr, N, Nc, Z, rs;

+    double A, T, b, d, x, y, t, hepp, hepm;

+    int flip, solution;

+    double xs[2];

+    double *xp;

+

+    w = def->w;

+    h = def->h;

+    r = def->l;

+    rs = r * r;

+    Hs = acc->h2;

+    WH = -acc->h2mw2;

+    Nk = def->w * r;

+    Vk = (Nk * Hs) / (WH + WH);

+    Hf = acc->h4;

+    Nk = (Hf - Nk * Nk) / WH;

+    if (K == 0.0) {

+	if (Nk < 0.0 && -Nk < Hs) {

+	    xs[0] = w * sqrt(1 + Nk / Hs) - sqrt(rs + Nk);

+	    xs[1] = w - r;

+	    if (acc->left.valid && boundedLe(K, bounds->left) &&

+		!boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)

+		return xs[1];

+	    if (acc->right.valid && boundedLe(K, bounds->right) &&

+		!boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)

+		return xs[1];

+	    return xs[0];

+	}

+	return w - r;

+    }

+    Fk = Hf / WH;

+    hepp = h + EPSILON;

+    hepm = h - EPSILON;

+    N = (K * K + Nk) / 6.0;

+    Nc = N * N * N;

+    Vr = Vk * K;

+    xp = xs;

+    xs[0] = 0.0;

+    t = Nc + Vr * Vr;

+    d = Nc + t;

+    if (d < 0.0) {

+	d = Nc;

+	b = N;

+	if ( (b < 0.0) == (t < 0.0) )

+	{

+	    b = -b;

+	    d = -d;

+	}

+	Z = N - 2.0 * b * cos(acos(-t / d) / 3.0);

+	if ( (Z < 0.0) == (Vr < 0.0) )

+	    flip = 2;

+	else

+	    flip = 1;

+    }

+    else

+    {

+	d = Vr * sqrt(d);

+	Z = N + cbrt(t + d) + cbrt(t - d);

+	flip = 0;

+    }

+    A = sqrt((Z + Z) - Nk);

+    T = (Fk - Z) * K / A;

+    solution = FALSE;

+    b = -A + K;

+    d = b * b - 4 * (Z + T);

+    if (d >= 0 && flip == 2)

+    {

+	d = sqrt(d);

+	y = (b + d) / 2;

+	if ((y >= 0.0) && (y < hepp))

+	{

+	    solution = TRUE;

+	    if (y > hepm)

+		y = h;

+	    t = y / h;

+	    x = w * sqrt(1 - (t * t));

+	    t = K - y;

+	    if (rs - (t * t) >= 0)

+	       t = sqrt(rs - (t * t));

+	    else

+	       t = 0;

+	    *xp++ = x - t;

+	}

+    }

+    b = A + K;

+    d = b * b - 4 * (Z - T);

+    /* Because of the large magnitudes involved, we lose enough precision

+     * that sometimes we end up with a negative value near the axis, when

+     * it should be positive.  This is a workaround.

+     */

+    if (d < 0 && !solution)

+	d = 0.0;

+    if (d >= 0) {

+	d = sqrt(d);

+	y = (b + d) / 2;

+	if (y < hepp)

+	{

+	    if (y > hepm)

+		y = h;

+	    t = y / h;

+	    x = w * sqrt(1 - (t * t));

+	    t = K - y;

+	    if (rs - (t * t) >= 0)

+	       *xp++ = x - sqrt(rs - (t * t));

+	    else

+	       *xp++ = x;

+	}

+	y = (b - d) / 2;

+	if (y >= 0.0 && flip == 1)

+	{

+	    if (y > hepm)

+		y = h;

+	    t = y / h;

+	    x = w * sqrt(1 - (t * t));

+	    t = K - y;

+	    if (rs - (t * t) >= 0)

+	       t = sqrt(rs - (t * t));

+	    else

+	       t = 0;

+	    *xp++ = x - t;

+	}

+    }

+    if (xp > &xs[1]) {

+	if (acc->left.valid && boundedLe(K, bounds->left) &&

+	    !boundedLe(K, bounds->outer) && xs[0] >= 0.0 && xs[1] >= 0.0)

+	    return xs[1];

+	if (acc->right.valid && boundedLe(K, bounds->right) &&

+	    !boundedLe(K, bounds->inner) && xs[0] <= 0.0 && xs[1] <= 0.0)

+	    return xs[1];

+    }

+    return xs[0];

+}

+

+static miArcSpanData *

+miComputeWideEllipse(int lw, xArc *parc)

+{

+    miArcSpanData *spdata = NULL;

+    int k;

+

+    if (!lw)

+	lw = 1;

+    k = (parc->height >> 1) + ((lw - 1) >> 1);

+    spdata = xalloc(sizeof(miArcSpanData) + sizeof(miArcSpan) * (k + 2));

+    if (!spdata)

+	return NULL;

+    spdata->spans = (miArcSpan *)(spdata + 1);

+    spdata->k = k;

+    spdata->top = !(lw & 1) && !(parc->width & 1);

+    spdata->bot = !(parc->height & 1);

+    if (parc->width == parc->height)

+	miComputeCircleSpans(lw, parc, spdata);

+    else

+	miComputeEllipseSpans(lw, parc, spdata);

+    return spdata;

+}

+

+static void

+miFillWideEllipse(

+    DrawablePtr	pDraw,

+    GCPtr	pGC,

+    xArc	*parc)

+{

+    DDXPointPtr points;

+    DDXPointPtr pts;

+    int *widths;

+    int *wids;

+    miArcSpanData *spdata;

+    miArcSpan *span;

+    int xorg, yorgu, yorgl;

+    int n;

+

+    yorgu = parc->height + pGC->lineWidth;

+    n = (sizeof(int) * 2) * yorgu;

+    widths = xalloc(n + (sizeof(DDXPointRec) * 2) * yorgu);

+    if (!widths)

+	return;

+    points = (DDXPointPtr)((char *)widths + n);

+    spdata = miComputeWideEllipse((int)pGC->lineWidth, parc);

+    if (!spdata)

+    {

+	xfree(widths);

+	return;

+    }

+    pts = points;

+    wids = widths;

+    span = spdata->spans;

+    xorg = parc->x + (parc->width >> 1);

+    yorgu = parc->y + (parc->height >> 1);

+    yorgl = yorgu + (parc->height & 1);

+    if (pGC->miTranslate)

+    {

+	xorg += pDraw->x;

+	yorgu += pDraw->y;

+	yorgl += pDraw->y;

+    }

+    yorgu -= spdata->k;

+    yorgl += spdata->k;

+    if (spdata->top)

+    {

+	pts->x = xorg;

+	pts->y = yorgu - 1;

+	pts++;

+	*wids++ = 1;

+	span++;

+    }

+    for (n = spdata->count1; --n >= 0; )

+    {

+	pts[0].x = xorg + span->lx;

+	pts[0].y = yorgu;

+	wids[0] = span->lw;

+	pts[1].x = pts[0].x;

+	pts[1].y = yorgl;

+	wids[1] = wids[0];

+	yorgu++;

+	yorgl--;

+	pts += 2;

+	wids += 2;

+	span++;

+    }

+    if (spdata->hole)

+    {

+	pts[0].x = xorg;

+	pts[0].y = yorgl;

+	wids[0] = 1;

+	pts++;

+	wids++;

+    }

+    for (n = spdata->count2; --n >= 0; )

+    {

+	pts[0].x = xorg + span->lx;

+	pts[0].y = yorgu;

+	wids[0] = span->lw;

+	pts[1].x = xorg + span->rx;

+	pts[1].y = pts[0].y;

+	wids[1] = span->rw;

+	pts[2].x = pts[0].x;

+	pts[2].y = yorgl;

+	wids[2] = wids[0];

+	pts[3].x = pts[1].x;

+	pts[3].y = pts[2].y;

+	wids[3] = wids[1];

+	yorgu++;

+	yorgl--;

+	pts += 4;

+	wids += 4;

+	span++;

+    }

+    if (spdata->bot)

+    {

+	if (span->rw <= 0)

+	{

+	    pts[0].x = xorg + span->lx;

+	    pts[0].y = yorgu;

+	    wids[0] = span->lw;

+	    pts++;

+	    wids++;

+	}	

+	else

+	{

+	    pts[0].x = xorg + span->lx;

+	    pts[0].y = yorgu;

+	    wids[0] = span->lw;

+	    pts[1].x = xorg + span->rx;

+	    pts[1].y = pts[0].y;

+	    wids[1] = span->rw;

+	    pts += 2;

+	    wids += 2;

+	}

+    }

+    xfree(spdata);

+    (*pGC->ops->FillSpans)(pDraw, pGC, pts - points, points, widths, FALSE);

+

+    xfree(widths);

+}

+

+/*

+ * miPolyArc strategy:

+ *

+ * If arc is zero width and solid, we don't have to worry about the rasterop

+ * or join styles.  For wide solid circles, we use a fast integer algorithm.

+ * For wide solid ellipses, we use special case floating point code.

+ * Otherwise, we set up pDrawTo and pGCTo according to the rasterop, then

+ * draw using pGCTo and pDrawTo.  If the raster-op was "tricky," that is,

+ * if it involves the destination, then we use PushPixels to move the bits

+ * from the scratch drawable to pDraw. (See the wide line code for a

+ * fuller explanation of this.)

+ */

+

+void

+miPolyArc(DrawablePtr pDraw, GCPtr pGC, int narcs, xArc *parcs)

+{

+    int		i;

+    xArc	*parc;

+    int		xMin, xMax, yMin, yMax;

+    int		pixmapWidth = 0, pixmapHeight = 0;

+    int		xOrg = 0, yOrg = 0;

+    int		width;

+    Bool	fTricky;

+    DrawablePtr	pDrawTo;

+    CARD32	fg, bg;

+    GCPtr	pGCTo;

+    miPolyArcPtr polyArcs;

+    int		cap[2], join[2];

+    int		iphase;

+    int		halfWidth;

+

+    width = pGC->lineWidth;

+    if(width == 0 && pGC->lineStyle == LineSolid)

+    {

+	for(i = narcs, parc = parcs; --i >= 0; parc++)

+	    miArcSegment( pDraw, pGC, *parc,

+ 	    (miArcFacePtr) 0, (miArcFacePtr) 0 );

+	fillSpans (pDraw, pGC);

+    }

+    else 

+    {

+	if ((pGC->lineStyle == LineSolid) && narcs)

+	{

+	    while (parcs->width && parcs->height &&

+		   (parcs->angle2 >= FULLCIRCLE ||

+		    parcs->angle2 <= -FULLCIRCLE))

+	    {

+		miFillWideEllipse(pDraw, pGC, parcs);

+		if (!--narcs)

+		    return;

+		parcs++;

+	    }

+	}

+

+	/* Set up pDrawTo and pGCTo based on the rasterop */

+	switch(pGC->alu)

+	{

+	  case GXclear:		/* 0 */

+	  case GXcopy:		/* src */

+	  case GXcopyInverted:	/* NOT src */

+	  case GXset:		/* 1 */

+	    fTricky = FALSE;

+	    pDrawTo = pDraw;

+	    pGCTo = pGC;

+	    break;

+	  default:

+	    fTricky = TRUE;

+

+	    /* find bounding box around arcs */

+	    xMin = yMin = MAXSHORT;

+	    xMax = yMax = MINSHORT;

+

+	    for(i = narcs, parc = parcs; --i >= 0; parc++)

+	    {

+		xMin = min (xMin, parc->x);

+		yMin = min (yMin, parc->y);

+		xMax = max (xMax, (parc->x + (int) parc->width));

+		yMax = max (yMax, (parc->y + (int) parc->height));

+	    }

+

+	    /* expand box to deal with line widths */

+	    halfWidth = (width + 1)/2;

+	    xMin -= halfWidth;

+	    yMin -= halfWidth;

+	    xMax += halfWidth;

+	    yMax += halfWidth;

+

+	    /* compute pixmap size; limit it to size of drawable */

+	    xOrg = max(xMin, 0);

+	    yOrg = max(yMin, 0);

+	    pixmapWidth = min(xMax, pDraw->width) - xOrg;

+	    pixmapHeight = min(yMax, pDraw->height) - yOrg;

+

+	    /* if nothing left, return */

+	    if ( (pixmapWidth <= 0) || (pixmapHeight <= 0) ) return;

+

+	    for(i = narcs, parc = parcs; --i >= 0; parc++)

+	    {

+		parc->x -= xOrg;

+		parc->y -= yOrg;

+	    }

+	    if (pGC->miTranslate)

+	    {

+		xOrg += pDraw->x;

+		yOrg += pDraw->y;

+	    }

+

+	    /* set up scratch GC */

+

+	    pGCTo = GetScratchGC(1, pDraw->pScreen);

+	    if (!pGCTo)

+		return;

+	    gcvals[GCValsFunction] = GXcopy;

+	    gcvals[GCValsForeground] = 1;

+	    gcvals[GCValsBackground] = 0;

+	    gcvals[GCValsLineWidth] = pGC->lineWidth;

+	    gcvals[GCValsCapStyle] = pGC->capStyle;

+	    gcvals[GCValsJoinStyle] = pGC->joinStyle;

+	    dixChangeGC(NullClient, pGCTo, GCValsMask, gcvals, NULL);

+    

+	    /* allocate a 1 bit deep pixmap of the appropriate size, and

+	     * validate it */

+	    pDrawTo = (DrawablePtr)(*pDraw->pScreen->CreatePixmap)

+				(pDraw->pScreen, pixmapWidth, pixmapHeight, 1,

+				 CREATE_PIXMAP_USAGE_SCRATCH);

+	    if (!pDrawTo)

+	    {

+		FreeScratchGC(pGCTo);

+		return;

+	    }

+	    ValidateGC(pDrawTo, pGCTo);

+	    miClearDrawable(pDrawTo, pGCTo);

+	}

+

+	fg = pGC->fgPixel;

+	bg = pGC->bgPixel;

+	if ((pGC->fillStyle == FillTiled) ||

+	    (pGC->fillStyle == FillOpaqueStippled))

+	    bg = fg; /* the protocol sez these don't cause color changes */

+

+	polyArcs = miComputeArcs (parcs, narcs, pGC);

+

+	if (!polyArcs)

+	{

+	    if (fTricky) {

+		(*pDraw->pScreen->DestroyPixmap) ((PixmapPtr)pDrawTo);

+		FreeScratchGC (pGCTo);

+	    }

+	    return;

+	}

+

+	cap[0] = cap[1] = 0;

+	join[0] = join[1] = 0;

+	for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);

+ 	     iphase >= 0;

+	     iphase--)

+	{

+	    if (iphase == 1) {

+		dixChangeGC (NullClient, pGC, GCForeground, &bg, NULL);

+		ValidateGC (pDraw, pGC);

+	    } else if (pGC->lineStyle == LineDoubleDash) {

+		dixChangeGC (NullClient, pGC, GCForeground, &fg, NULL);

+		ValidateGC (pDraw, pGC);

+	    }

+	    for (i = 0; i < polyArcs[iphase].narcs; i++) {

+		miArcDataPtr	arcData;

+

+		arcData = &polyArcs[iphase].arcs[i];

+		miArcSegment(pDrawTo, pGCTo, arcData->arc,

+			     &arcData->bounds[RIGHT_END],

+			     &arcData->bounds[LEFT_END]);

+		if (polyArcs[iphase].arcs[i].render) {

+		    fillSpans (pDrawTo, pGCTo);

+		    /*

+		     * don't cap self-joining arcs

+		     */

+		    if (polyArcs[iphase].arcs[i].selfJoin &&

+		        cap[iphase] < polyArcs[iphase].arcs[i].cap)

+		    	cap[iphase]++;

+		    while (cap[iphase] < polyArcs[iphase].arcs[i].cap) {

+			int	arcIndex, end;

+			miArcDataPtr	arcData0;

+

+			arcIndex = polyArcs[iphase].caps[cap[iphase]].arcIndex;

+			end = polyArcs[iphase].caps[cap[iphase]].end;

+			arcData0 = &polyArcs[iphase].arcs[arcIndex];

+			miArcCap (pDrawTo, pGCTo,

+ 				  &arcData0->bounds[end], end,

+				  arcData0->arc.x, arcData0->arc.y,

+				  (double) arcData0->arc.width / 2.0,

+ 				  (double) arcData0->arc.height / 2.0);

+			++cap[iphase];

+		    }

+		    while (join[iphase] < polyArcs[iphase].arcs[i].join) {

+			int	arcIndex0, arcIndex1, end0, end1;

+			int	phase0, phase1;

+			miArcDataPtr	arcData0, arcData1;

+			miArcJoinPtr	joinp;

+

+			joinp = &polyArcs[iphase].joins[join[iphase]];

+			arcIndex0 = joinp->arcIndex0;

+			end0 = joinp->end0;

+			arcIndex1 = joinp->arcIndex1;

+			end1 = joinp->end1;

+			phase0 = joinp->phase0;

+			phase1 = joinp->phase1;

+			arcData0 = &polyArcs[phase0].arcs[arcIndex0];

+			arcData1 = &polyArcs[phase1].arcs[arcIndex1];

+			miArcJoin (pDrawTo, pGCTo,

+				  &arcData0->bounds[end0],

+ 				  &arcData1->bounds[end1],

+				  arcData0->arc.x, arcData0->arc.y,

+				  (double) arcData0->arc.width / 2.0,

+ 				  (double) arcData0->arc.height / 2.0,

+				  arcData1->arc.x, arcData1->arc.y,

+				  (double) arcData1->arc.width / 2.0,

+ 				  (double) arcData1->arc.height / 2.0);

+			++join[iphase];

+		    }

+		    if (fTricky) {

+			if (pGC->serialNumber != pDraw->serialNumber)

+			    ValidateGC (pDraw, pGC);

+		    	(*pGC->ops->PushPixels) (pGC, (PixmapPtr)pDrawTo,

+				 pDraw, pixmapWidth, pixmapHeight, xOrg, yOrg);

+			miClearDrawable ((DrawablePtr) pDrawTo, pGCTo);

+		    }

+		}

+	    }

+	}

+	miFreeArcs(polyArcs, pGC);

+

+	if(fTricky)

+	{

+	    (*pGCTo->pScreen->DestroyPixmap)((PixmapPtr)pDrawTo);

+	    FreeScratchGC(pGCTo);

+	}

+    }

+}

+

+static double

+angleBetween (SppPointRec center, SppPointRec point1, SppPointRec point2)

+{

+	double	a1, a2, a;

+	

+	/*

+	 * reflect from X coordinates back to ellipse

+	 * coordinates -- y increasing upwards

+	 */

+	a1 = miDatan2 (- (point1.y - center.y), point1.x - center.x);

+	a2 = miDatan2 (- (point2.y - center.y), point2.x - center.x);

+	a = a2 - a1;

+	if (a <= -180.0)

+		a += 360.0;

+	else if (a > 180.0)

+		a -= 360.0;

+	return a;

+}

+

+static void

+translateBounds (

+	miArcFacePtr	b,

+	int		x,

+	int		y,

+	double		fx,

+	double		fy)

+{

+	fx += x;

+	fy += y;

+	b->clock.x -= fx;

+	b->clock.y -= fy;

+	b->center.x -= fx;

+	b->center.y -= fy;

+	b->counterClock.x -= fx;

+	b->counterClock.y -= fy;

+}

+

+static void

+miArcJoin(DrawablePtr pDraw, GCPtr pGC, miArcFacePtr pLeft,

+	  miArcFacePtr pRight, int xOrgLeft, int yOrgLeft,

+	  double xFtransLeft, double yFtransLeft,

+	  int xOrgRight, int yOrgRight,

+	  double xFtransRight, double yFtransRight)

+{

+	SppPointRec	center, corner, otherCorner;

+	SppPointRec	poly[5], e;

+	SppPointPtr	pArcPts;

+	int		cpt;

+	SppArcRec	arc;

+	miArcFaceRec	Right, Left;

+	int		polyLen = 0;

+	int		xOrg, yOrg;

+	double		xFtrans, yFtrans;

+	double		a;

+	double		ae, ac2, ec2, bc2, de;

+	double		width;

+	

+	xOrg = (xOrgRight + xOrgLeft) / 2;

+	yOrg = (yOrgRight + yOrgLeft) / 2;

+	xFtrans = (xFtransLeft + xFtransRight) / 2;

+	yFtrans = (yFtransLeft + yFtransRight) / 2;

+	Right = *pRight;

+	translateBounds (&Right, xOrg - xOrgRight, yOrg - yOrgRight,

+				 xFtrans - xFtransRight, yFtrans - yFtransRight);

+	Left = *pLeft;

+	translateBounds (&Left, xOrg - xOrgLeft, yOrg - yOrgLeft,

+				 xFtrans - xFtransLeft, yFtrans - yFtransLeft);

+	pRight = &Right;

+	pLeft = &Left;

+

+	if (pRight->clock.x == pLeft->counterClock.x &&

+	    pRight->clock.y == pLeft->counterClock.y)

+		return;

+	center = pRight->center;

+	if (0 <= (a = angleBetween (center, pRight->clock, pLeft->counterClock))

+ 	    && a <= 180.0)

+ 	{

+		corner = pRight->clock;

+		otherCorner = pLeft->counterClock;

+	} else {

+		a = angleBetween (center, pLeft->clock, pRight->counterClock);

+		corner = pLeft->clock;

+		otherCorner = pRight->counterClock;

+	}

+	switch (pGC->joinStyle) {

+	case JoinRound:

+		width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);

+

+		arc.x = center.x - width/2;

+		arc.y = center.y - width/2;

+		arc.width = width;

+		arc.height = width;

+		arc.angle1 = -miDatan2 (corner.y - center.y, corner.x - center.x);

+		arc.angle2 = a;

+		pArcPts = xalloc (3 * sizeof (SppPointRec));

+		if (!pArcPts)

+		    return;

+		pArcPts[0].x = otherCorner.x;

+		pArcPts[0].y = otherCorner.y;

+		pArcPts[1].x = center.x;

+		pArcPts[1].y = center.y;

+		pArcPts[2].x = corner.x;

+		pArcPts[2].y = corner.y;

+		if( (cpt = miGetArcPts(&arc, 3, &pArcPts)) )

+		{

+			/* by drawing with miFillSppPoly and setting the endpoints of the arc

+			 * to be the corners, we assure that the cap will meet up with the

+			 * rest of the line */

+			miFillSppPoly(pDraw, pGC, cpt, pArcPts, xOrg, yOrg, xFtrans, yFtrans);

+		}

+		xfree(pArcPts);

+		return;

+	case JoinMiter:

+		/*

+		 * don't miter arcs with less than 11 degrees between them

+		 */

+		if (a < 169.0) {

+			poly[0] = corner;

+			poly[1] = center;

+			poly[2] = otherCorner;

+			bc2 = (corner.x - otherCorner.x) * (corner.x - otherCorner.x) +

+			      (corner.y - otherCorner.y) * (corner.y - otherCorner.y);

+			ec2 = bc2 / 4;

+			ac2 = (corner.x - center.x) * (corner.x - center.x) +

+			      (corner.y - center.y) * (corner.y - center.y);

+			ae = sqrt (ac2 - ec2);

+			de = ec2 / ae;

+			e.x = (corner.x + otherCorner.x) / 2;

+			e.y = (corner.y + otherCorner.y) / 2;

+			poly[3].x = e.x + de * (e.x - center.x) / ae;

+			poly[3].y = e.y + de * (e.y - center.y) / ae;

+			poly[4] = corner;

+			polyLen = 5;

+			break;

+		}

+	case JoinBevel:

+		poly[0] = corner;

+		poly[1] = center;

+		poly[2] = otherCorner;

+		poly[3] = corner;

+		polyLen = 4;

+		break;

+	}

+	miFillSppPoly (pDraw, pGC, polyLen, poly, xOrg, yOrg, xFtrans, yFtrans);

+}

+

+/*ARGSUSED*/

+static void

+miArcCap (

+	DrawablePtr	pDraw,

+	GCPtr		pGC,

+	miArcFacePtr	pFace,

+	int		end,

+	int		xOrg,

+	int		yOrg,

+	double		xFtrans,

+	double		yFtrans)

+{

+	SppPointRec	corner, otherCorner, center, endPoint, poly[5];

+

+	corner = pFace->clock;

+	otherCorner = pFace->counterClock;

+	center = pFace->center;

+	switch (pGC->capStyle) {

+	case CapProjecting:

+		poly[0].x = otherCorner.x;

+		poly[0].y = otherCorner.y;

+		poly[1].x = corner.x;

+		poly[1].y = corner.y;

+		poly[2].x = corner.x -

+ 				(center.y - corner.y);

+		poly[2].y = corner.y +

+ 				(center.x - corner.x);

+		poly[3].x = otherCorner.x -

+ 				(otherCorner.y - center.y);

+		poly[3].y = otherCorner.y +

+ 				(otherCorner.x - center.x);

+		poly[4].x = otherCorner.x;

+		poly[4].y = otherCorner.y;

+		miFillSppPoly (pDraw, pGC, 5, poly, xOrg, yOrg, xFtrans, yFtrans);

+		break;

+	case CapRound:

+		/*

+		 * miRoundCap just needs these to be unequal.

+		 */

+		endPoint = center;

+		endPoint.x = endPoint.x + 100;

+		miRoundCap (pDraw, pGC, center, endPoint, corner, otherCorner, 0,

+			    -xOrg, -yOrg, xFtrans, yFtrans);

+		break;

+	}

+}

+

+/* 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.  

+ * NOTE:  pOtherCorner must be counter-clockwise from pCorner.

+ */

+/*ARGSUSED*/

+static void

+miRoundCap(

+    DrawablePtr	pDraw,

+    GCPtr	pGC,

+    SppPointRec	pCenter,

+    SppPointRec	pEnd,

+    SppPointRec	pCorner,

+    SppPointRec	pOtherCorner,

+    int		fLineEnd,

+    int		xOrg,

+    int		yOrg,

+    double	xFtrans,

+    double	yFtrans)

+{

+    int		cpt;

+    double	width;

+    SppArcRec	arc;

+    SppPointPtr	pArcPts;

+

+    width = (pGC->lineWidth ? (double)pGC->lineWidth : (double)1);

+

+    arc.x = pCenter.x - width/2;

+    arc.y = pCenter.y - width/2;

+    arc.width = width;

+    arc.height = width;

+    arc.angle1 = -miDatan2 (pCorner.y - pCenter.y, pCorner.x - pCenter.x);

+    if(PTISEQUAL(pCenter, pEnd))

+	arc.angle2 = - 180.0;

+    else {

+	arc.angle2 = -miDatan2 (pOtherCorner.y - pCenter.y, pOtherCorner.x - pCenter.x) - arc.angle1;

+	if (arc.angle2 < 0)

+	    arc.angle2 += 360.0;

+    }

+    pArcPts = (SppPointPtr) NULL;

+    if( (cpt = miGetArcPts(&arc, 0, &pArcPts)) )

+    {

+	/* by drawing with miFillSppPoly and setting the endpoints of the arc

+	 * to be the corners, we assure that the cap will meet up with the

+	 * rest of the line */

+	miFillSppPoly(pDraw, pGC, cpt, pArcPts, -xOrg, -yOrg, xFtrans, yFtrans);

+    }

+    xfree(pArcPts);

+}

+

+/*

+ * To avoid inaccuracy at the cardinal points, use trig functions

+ * which are exact for those angles

+ */

+

+#ifndef M_PI

+#define M_PI	3.14159265358979323846

+#endif

+#ifndef M_PI_2

+#define M_PI_2	1.57079632679489661923

+#endif

+

+# define Dsin(d)	((d) == 0.0 ? 0.0 : ((d) == 90.0 ? 1.0 : sin(d*M_PI/180.0)))

+# define Dcos(d)	((d) == 0.0 ? 1.0 : ((d) == 90.0 ? 0.0 : cos(d*M_PI/180.0)))

+# define mod(a,b)	((a) >= 0 ? (a) % (b) : (b) - (-(a)) % (b))

+

+static double

+miDcos (double a)

+{

+	int	i;

+

+	if (floor (a/90) == a/90) {

+		i = (int) (a/90.0);

+		switch (mod (i, 4)) {

+		case 0: return 1;

+		case 1: return 0;

+		case 2: return -1;

+		case 3: return 0;

+		}

+	}

+	return cos (a * M_PI / 180.0);

+}

+

+static double

+miDsin (double a)

+{

+	int	i;

+

+	if (floor (a/90) == a/90) {

+		i = (int) (a/90.0);

+		switch (mod (i, 4)) {

+		case 0: return 0;

+		case 1: return 1;

+		case 2: return 0;

+		case 3: return -1;

+		}

+	}

+	return sin (a * M_PI / 180.0);

+}

+

+static double

+miDasin (double v)

+{

+    if (v == 0)

+	return 0.0;

+    if (v == 1.0)

+	return 90.0;

+    if (v == -1.0)

+	return -90.0;

+    return asin(v) * (180.0 / M_PI);

+}

+

+static double

+miDatan2 (double dy, double dx)

+{

+    if (dy == 0) {

+	if (dx >= 0)

+	    return 0.0;

+	return 180.0;

+    } else if (dx == 0) {

+	if (dy > 0)

+	    return 90.0;

+	return -90.0;

+    } else if (Fabs (dy) == Fabs (dx)) {

+	if (dy > 0) {

+	    if (dx > 0)

+		return 45.0;

+	    return 135.0;

+	} else {

+	    if (dx > 0)

+		return 315.0;

+	    return 225.0;

+	}

+    } else {

+	return atan2 (dy, dx) * (180.0 / M_PI);

+    }

+}

+

+/* MIGETARCPTS -- Converts an arc into a set of line segments -- a helper

+ * routine for filled arc and line (round cap) code.

+ * Returns the number of points in the arc.  Note that it takes a pointer

+ * to a pointer to where it should put the points and an index (cpt).

+ * This procedure allocates the space necessary to fit the arc points.

+ * Sometimes it's convenient for those points to be at the end of an existing

+ * array. (For example, if we want to leave a spare point to make sectors

+ * instead of segments.)  So we pass in the xalloc()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 

+ * count on xrealloc() to handle the null pointer correctly.

+ */

+static int

+miGetArcPts(

+    SppArcPtr	parc,	/* points to an arc */

+    int		cpt,	/* number of points already in arc list */

+    SppPointPtr	*ppPts) /* pointer to pointer to arc-list -- modified */

+{

+    double 	st,	/* Start Theta, start angle */

+                et,	/* End Theta, offset from start theta */

+		dt,	/* Delta Theta, angle to sweep ellipse */

+		cdt,	/* Cos Delta Theta, actually 2 cos(dt) */

+    		x0, y0,	/* the recurrence formula needs two points to start */

+		x1, y1,

+		x2, y2, /* this will be the new point generated */

+		xc, yc; /* the center point */

+    int		count, i;

+    SppPointPtr	poly;

+

+    /* The spec says that positive angles indicate counterclockwise motion.

+     * 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 */

+    

+    st = - parc->angle1;

+

+    et = - parc->angle2;

+

+    /* Try to get a delta theta that is within 1/2 pixel.  Then adjust it

+     * so that it divides evenly into the total.

+     * I'm just using cdt 'cause I'm lazy.

+     */

+    cdt = parc->width;

+    if (parc->height > cdt)

+	cdt = parc->height;

+    cdt /= 2.0;

+    if(cdt <= 0)

+	return 0;

+    if (cdt < 1.0)

+	cdt = 1.0;

+    dt = miDasin ( 1.0 / cdt ); /* minimum step necessary */

+    count = et/dt;

+    count = abs(count) + 1;

+    dt = et/count;	

+    count++;

+

+    cdt = 2 * miDcos(dt);

+    if (!(poly = (SppPointPtr) xrealloc((pointer)*ppPts,

+					(cpt + count) * sizeof(SppPointRec))))

+	return(0);

+    *ppPts = poly;

+

+    xc = parc->width/2.0;		/* store half width and half height */

+    yc = parc->height/2.0;

+    

+    x0 = xc * miDcos(st);

+    y0 = yc * miDsin(st);

+    x1 = xc * miDcos(st + dt);

+    y1 = yc * miDsin(st + dt);

+    xc += parc->x;		/* by adding initial point, these become */

+    yc += parc->y;		/* the center point */

+

+    poly[cpt].x = (xc + x0);

+    poly[cpt].y = (yc + y0);

+    poly[cpt + 1].x = (xc + x1);

+    poly[cpt + 1].y = (yc + y1);

+

+    for(i = 2; i < count; i++)

+    {

+	x2 = cdt * x1 - x0;

+	y2 = cdt * y1 - y0;

+

+ 	poly[cpt + i].x = (xc + x2);

+ 	poly[cpt + i].y = (yc + y2);

+

+	x0 = x1; y0 = y1;

+	x1 = x2; y1 = y2;

+    }

+    /* adjust the last point */

+    if (abs(parc->angle2) >= 360.0)

+	poly[cpt +i -1] = poly[0];

+    else {

+	poly[cpt +i -1].x = (miDcos(st + et) * parc->width/2.0 + xc);

+	poly[cpt +i -1].y = (miDsin(st + et) * parc->height/2.0 + yc);

+    }

+

+    return(count);

+}

+

+struct arcData {

+	double	x0, y0, x1, y1;

+	int	selfJoin;

+};

+

+# define ADD_REALLOC_STEP	20

+

+static void

+addCap (

+	miArcCapPtr	*capsp,

+	int		*ncapsp,

+	int		*sizep,

+	int		end,

+	int		arcIndex)

+{

+	int newsize;

+	miArcCapPtr	cap;

+

+	if (*ncapsp == *sizep)

+	{

+	    newsize = *sizep + ADD_REALLOC_STEP;

+	    cap = (miArcCapPtr) xrealloc (*capsp,

+					  newsize * sizeof (**capsp));

+	    if (!cap)

+		return;

+	    *sizep = newsize;

+	    *capsp = cap;

+	}

+	cap = &(*capsp)[*ncapsp];

+	cap->end = end;

+	cap->arcIndex = arcIndex;

+	++*ncapsp;

+}

+

+static void

+addJoin (

+	miArcJoinPtr	*joinsp,

+	int		*njoinsp,

+	int		*sizep,

+	int		end0,

+	int		index0,

+	int		phase0,

+	int		end1,

+	int		index1,

+	int		phase1)

+{

+	int newsize;

+	miArcJoinPtr	join;

+

+	if (*njoinsp == *sizep)

+	{

+	    newsize = *sizep + ADD_REALLOC_STEP;

+	    join = (miArcJoinPtr) xrealloc (*joinsp,

+					    newsize * sizeof (**joinsp));

+	    if (!join)

+		return;

+	    *sizep = newsize;

+	    *joinsp = join;

+	}

+	join = &(*joinsp)[*njoinsp];

+	join->end0 = end0;

+	join->arcIndex0 = index0;

+	join->phase0 = phase0;

+	join->end1 = end1;

+	join->arcIndex1 = index1;

+	join->phase1 = phase1;

+	++*njoinsp;

+}

+

+static miArcDataPtr

+addArc (

+	miArcDataPtr	*arcsp,

+	int		*narcsp,

+	int		*sizep,

+	xArc		*xarc)

+{

+	int newsize;

+	miArcDataPtr	arc;

+

+	if (*narcsp == *sizep)

+	{

+	    newsize = *sizep + ADD_REALLOC_STEP;

+	    arc = (miArcDataPtr) xrealloc (*arcsp,

+					   newsize * sizeof (**arcsp));

+	    if (!arc)

+		return NULL;

+	    *sizep = newsize;

+	    *arcsp = arc;

+	}

+	arc = &(*arcsp)[*narcsp];

+	arc->arc = *xarc;

+	++*narcsp;

+	return arc;

+}

+

+static void

+miFreeArcs(

+    miPolyArcPtr arcs,

+    GCPtr pGC)

+{

+	int iphase;

+

+	for (iphase = ((pGC->lineStyle == LineDoubleDash) ? 1 : 0);

+ 	     iphase >= 0;

+	     iphase--)

+	{

+	    if (arcs[iphase].narcs > 0)

+		xfree(arcs[iphase].arcs);

+	    if (arcs[iphase].njoins > 0)

+		xfree(arcs[iphase].joins);

+	    if (arcs[iphase].ncaps > 0)

+		xfree(arcs[iphase].caps);

+	}

+	xfree(arcs);

+}

+

+/*

+ * map angles to radial distance.  This only deals with the first quadrant

+ */

+

+/*

+ * a polygonal approximation to the arc for computing arc lengths

+ */

+

+# define DASH_MAP_SIZE	91

+

+# define dashIndexToAngle(di)	((((double) (di)) * 90.0) / ((double) DASH_MAP_SIZE - 1))

+# define xAngleToDashIndex(xa)	((((long) (xa)) * (DASH_MAP_SIZE - 1)) / (90 * 64))

+# define dashIndexToXAngle(di)	((((long) (di)) * (90 * 64)) / (DASH_MAP_SIZE - 1))

+# define dashXAngleStep	(((double) (90 * 64)) / ((double) (DASH_MAP_SIZE - 1)))

+

+typedef struct {

+	double	map[DASH_MAP_SIZE];

+} dashMap;

+

+static int computeAngleFromPath(int startAngle, int endAngle, dashMap *map,

+				int *lenp, int backwards);

+

+static void

+computeDashMap (

+	xArc	*arcp,

+	dashMap	*map)

+{

+	int	di;

+	double	a, x, y, prevx = 0.0, prevy = 0.0, dist;

+

+	for (di = 0; di < DASH_MAP_SIZE; di++) {

+		a = dashIndexToAngle (di);

+		x = ((double) arcp->width / 2.0) * miDcos (a);

+		y = ((double) arcp->height / 2.0) * miDsin (a);

+		if (di == 0) {

+			map->map[di] = 0.0;

+		} else {

+			dist = hypot (x - prevx, y - prevy);

+			map->map[di] = map->map[di - 1] + dist;

+		}

+		prevx = x;

+		prevy = y;

+	}

+}

+

+typedef enum {HORIZONTAL, VERTICAL, OTHER} arcTypes;

+

+/* this routine is a bit gory */

+

+static miPolyArcPtr

+miComputeArcs (

+	xArc	*parcs,

+	int	narcs,

+	GCPtr	pGC)

+{

+	int		isDashed, isDoubleDash;

+	int		dashOffset;

+	miPolyArcPtr	arcs;

+	int		start, i, j, k = 0, nexti, nextk = 0;

+	int		joinSize[2];

+	int		capSize[2];

+	int		arcSize[2];

+	int		angle2;

+	double		a0, a1;

+	struct arcData	*data;

+	miArcDataPtr	arc;

+	xArc		xarc;

+	int		iphase, prevphase = 0, joinphase;

+	int		arcsJoin;

+	int		selfJoin;

+

+	int		iDash = 0, dashRemaining = 0;

+	int		iDashStart = 0, dashRemainingStart = 0, iphaseStart;

+	int		startAngle, spanAngle, endAngle, backwards = 0;

+	int		prevDashAngle, dashAngle;

+	dashMap		map;

+

+	isDashed = !(pGC->lineStyle == LineSolid);

+	isDoubleDash = (pGC->lineStyle == LineDoubleDash);

+	dashOffset = pGC->dashOffset;

+

+	data = xalloc (narcs * sizeof (struct arcData));

+	if (!data)

+	    return NULL;

+	arcs = xalloc (sizeof (*arcs) * (isDoubleDash ? 2 : 1));

+	if (!arcs)

+	{

+	    xfree(data);

+	    return NULL;

+	}

+	for (i = 0; i < narcs; i++) {

+		a0 = todeg (parcs[i].angle1);

+		angle2 = parcs[i].angle2;

+		if (angle2 > FULLCIRCLE)

+			angle2 = FULLCIRCLE;

+		else if (angle2 < -FULLCIRCLE)

+			angle2 = -FULLCIRCLE;

+		data[i].selfJoin = angle2 == FULLCIRCLE || angle2 == -FULLCIRCLE;

+		a1 = todeg (parcs[i].angle1 + angle2);

+		data[i].x0 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a0));

+		data[i].y0 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a0));

+		data[i].x1 = parcs[i].x + (double) parcs[i].width / 2 * (1 + miDcos (a1));

+		data[i].y1 = parcs[i].y + (double) parcs[i].height / 2 * (1 - miDsin (a1));

+	}

+

+	for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++) {

+		arcs[iphase].njoins = 0;

+		arcs[iphase].joins = 0;

+		joinSize[iphase] = 0;

+		

+		arcs[iphase].ncaps = 0;

+		arcs[iphase].caps = 0;

+		capSize[iphase] = 0;

+		

+		arcs[iphase].narcs = 0;

+		arcs[iphase].arcs = 0;

+		arcSize[iphase] = 0;

+	}

+

+	iphase = 0;

+	if (isDashed) {

+		iDash = 0;

+		dashRemaining = pGC->dash[0];

+	 	while (dashOffset > 0) {

+			if (dashOffset >= dashRemaining) {

+				dashOffset -= dashRemaining;

+				iphase = iphase ? 0 : 1;

+				iDash++;

+				if (iDash == pGC->numInDashList)

+				    iDash = 0;

+				dashRemaining = pGC->dash[iDash];

+			} else {

+				dashRemaining -= dashOffset;

+				dashOffset = 0;

+			}

+		}

+		iDashStart = iDash;

+		dashRemainingStart = dashRemaining;

+	}

+	iphaseStart = iphase;

+

+	for (i = narcs - 1; i >= 0; i--) {

+		j = i + 1;

+		if (j == narcs)

+			j = 0;

+		if (data[i].selfJoin || i == j ||

+		     (UNEQUAL (data[i].x1, data[j].x0) ||

+		      UNEQUAL (data[i].y1, data[j].y0)))

+ 		{

+			if (iphase == 0 || isDoubleDash)

+				addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,

+	 				&capSize[iphase], RIGHT_END, 0);

+			break;

+		}

+	}

+	start = i + 1;

+	if (start == narcs)

+		start = 0;

+	i = start;

+	for (;;) {

+		j = i + 1;

+		if (j == narcs)

+			j = 0;

+		nexti = i+1;

+		if (nexti == narcs)

+			nexti = 0;

+		if (isDashed) {

+			/*

+			** deal with dashed arcs.  Use special rules for certain 0 area arcs.

+			** Presumably, the other 0 area arcs still aren't done right.

+			*/

+			arcTypes	arcType = OTHER;

+			CARD16		thisLength;

+

+			if (parcs[i].height == 0

+			    && (parcs[i].angle1 % FULLCIRCLE) == 0x2d00

+			    && parcs[i].angle2 == 0x2d00) 

+				arcType = HORIZONTAL;

+			else if (parcs[i].width == 0

+			    && (parcs[i].angle1 % FULLCIRCLE) == 0x1680

+			    && parcs[i].angle2 == 0x2d00)

+				arcType = VERTICAL;

+			if (arcType == OTHER) {

+				/*

+				 * precompute an approximation map

+				 */

+				computeDashMap (&parcs[i], &map);

+				/*

+				 * compute each individual dash segment using the path

+				 * length function

+				 */

+				startAngle = parcs[i].angle1;

+				spanAngle = parcs[i].angle2;

+				if (spanAngle > FULLCIRCLE)

+					spanAngle = FULLCIRCLE;

+				else if (spanAngle < -FULLCIRCLE)

+					spanAngle = -FULLCIRCLE;

+				if (startAngle < 0)

+					startAngle = FULLCIRCLE - (-startAngle) % FULLCIRCLE;

+				if (startAngle >= FULLCIRCLE)

+					startAngle = startAngle % FULLCIRCLE;

+				endAngle = startAngle + spanAngle;

+				backwards = spanAngle < 0;

+			} else {

+				xarc = parcs[i];

+				if (arcType == VERTICAL) {

+					xarc.angle1 = 0x1680;

+					startAngle = parcs[i].y;

+					endAngle = startAngle + parcs[i].height;

+				} else {

+					xarc.angle1 = 0x2d00;

+					startAngle = parcs[i].x;

+					endAngle = startAngle + parcs[i].width;

+				}

+			}

+			dashAngle = startAngle;

+			selfJoin = data[i].selfJoin &&

+ 				    (iphase == 0 || isDoubleDash);

+			/*

+			 * add dashed arcs to each bucket

+			 */

+			arc = 0;

+			while (dashAngle != endAngle) {

+				prevDashAngle = dashAngle;

+				if (arcType == OTHER) {

+					dashAngle = computeAngleFromPath (prevDashAngle, endAngle,

+								&map, &dashRemaining, backwards);

+					/* avoid troubles with huge arcs and small dashes */

+					if (dashAngle == prevDashAngle) {

+						if (backwards)

+							dashAngle--;

+						else

+							dashAngle++;

+					}

+				} else {

+					thisLength = (dashAngle + dashRemaining <= endAngle) ? 

+					    dashRemaining : endAngle - dashAngle;

+					if (arcType == VERTICAL) {

+						xarc.y = dashAngle;

+						xarc.height = thisLength;

+					} else {

+						xarc.x = dashAngle;

+						xarc.width = thisLength;

+					}

+					dashAngle += thisLength;

+					dashRemaining -= thisLength;

+				}

+				if (iphase == 0 || isDoubleDash) {

+					if (arcType == OTHER) {

+						xarc = parcs[i];

+						spanAngle = prevDashAngle;

+						if (spanAngle < 0)

+						    spanAngle = FULLCIRCLE - (-spanAngle) % FULLCIRCLE;

+						if (spanAngle >= FULLCIRCLE)

+						    spanAngle = spanAngle % FULLCIRCLE;

+						xarc.angle1 = spanAngle;

+						spanAngle = dashAngle - prevDashAngle;

+						if (backwards) {

+							if (dashAngle > prevDashAngle)

+								spanAngle = - FULLCIRCLE + spanAngle;

+						} else {

+							if (dashAngle < prevDashAngle)

+								spanAngle = FULLCIRCLE + spanAngle;

+						}

+						if (spanAngle > FULLCIRCLE)

+						    spanAngle = FULLCIRCLE;

+						if (spanAngle < -FULLCIRCLE)

+						    spanAngle = -FULLCIRCLE;

+						xarc.angle2 = spanAngle;

+					}

+					arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,

+ 							&arcSize[iphase], &xarc);

+					if (!arc)

+					    goto arcfail;

+					/*

+					 * cap each end of an on/off dash

+					 */

+					if (!isDoubleDash) {

+						if (prevDashAngle != startAngle) {

+							addCap (&arcs[iphase].caps,

+ 								&arcs[iphase].ncaps,

+ 								&capSize[iphase], RIGHT_END,

+ 								arc - arcs[iphase].arcs);

+							

+						}

+						if (dashAngle != endAngle) {

+							addCap (&arcs[iphase].caps,

+ 								&arcs[iphase].ncaps,

+ 								&capSize[iphase], LEFT_END,

+ 								arc - arcs[iphase].arcs);

+						}

+					}

+					arc->cap = arcs[iphase].ncaps;

+					arc->join = arcs[iphase].njoins;

+					arc->render = 0;

+					arc->selfJoin = 0;

+					if (dashAngle == endAngle)

+						arc->selfJoin = selfJoin;

+				}

+				prevphase = iphase;

+				if (dashRemaining <= 0) {

+					++iDash;

+					if (iDash == pGC->numInDashList)

+						iDash = 0;

+					iphase = iphase ? 0:1;

+					dashRemaining = pGC->dash[iDash];

+				}

+			}

+			/*

+			 * make sure a place exists for the position data when

+			 * drawing a zero-length arc

+			 */

+			if (startAngle == endAngle) {

+				prevphase = iphase;

+				if (!isDoubleDash && iphase == 1)

+					prevphase = 0;

+				arc = addArc (&arcs[prevphase].arcs, &arcs[prevphase].narcs,

+					      &arcSize[prevphase], &parcs[i]);

+				if (!arc)

+				    goto arcfail;

+				arc->join = arcs[prevphase].njoins;

+				arc->cap = arcs[prevphase].ncaps;

+				arc->selfJoin = data[i].selfJoin;

+			}

+		} else {

+			arc = addArc (&arcs[iphase].arcs, &arcs[iphase].narcs,

+ 				      &arcSize[iphase], &parcs[i]);

+			if (!arc)

+			    goto arcfail;

+			arc->join = arcs[iphase].njoins;

+			arc->cap = arcs[iphase].ncaps;

+			arc->selfJoin = data[i].selfJoin;

+			prevphase = iphase;

+		}

+		if (prevphase == 0 || isDoubleDash)

+			k = arcs[prevphase].narcs - 1;

+		if (iphase == 0 || isDoubleDash)

+			nextk = arcs[iphase].narcs;

+		if (nexti == start) {

+			nextk = 0;

+			if (isDashed) {

+				iDash = iDashStart;

+				iphase = iphaseStart;

+				dashRemaining = dashRemainingStart;

+			}

+		}

+		arcsJoin = narcs > 1 && i != j &&

+	 		    ISEQUAL (data[i].x1, data[j].x0) &&

+			    ISEQUAL (data[i].y1, data[j].y0) &&

+			    !data[i].selfJoin && !data[j].selfJoin;

+		if (arc)

+		{

+			if (arcsJoin)

+				arc->render = 0;

+			else

+				arc->render = 1;

+		}

+		if (arcsJoin &&

+		    (prevphase == 0 || isDoubleDash) &&

+		    (iphase == 0 || isDoubleDash))

+ 		{

+			joinphase = iphase;

+			if (isDoubleDash) {

+				if (nexti == start)

+					joinphase = iphaseStart;

+				/*

+				 * if the join is right at the dash,

+				 * draw the join in foreground

+				 * This is because the foreground

+				 * arcs are computed second, the results

+				 * of which are needed to draw the join

+				 */

+				if (joinphase != prevphase)

+					joinphase = 0;

+			}

+			if (joinphase == 0 || isDoubleDash) {

+				addJoin (&arcs[joinphase].joins,

+ 					 &arcs[joinphase].njoins,

+ 					 &joinSize[joinphase],

+	 				 LEFT_END, k, prevphase,

+	 				 RIGHT_END, nextk, iphase);

+				arc->join = arcs[prevphase].njoins;

+			}

+		} else {

+			/*

+			 * cap the left end of this arc

+			 * unless it joins itself

+			 */

+			if ((prevphase == 0 || isDoubleDash) &&

+			    !arc->selfJoin)

+			{

+				addCap (&arcs[prevphase].caps, &arcs[prevphase].ncaps,

+ 					&capSize[prevphase], LEFT_END, k);

+				arc->cap = arcs[prevphase].ncaps;

+			}

+			if (isDashed && !arcsJoin) {

+				iDash = iDashStart;

+				iphase = iphaseStart;

+				dashRemaining = dashRemainingStart;

+			}

+			nextk = arcs[iphase].narcs;

+			if (nexti == start) {

+				nextk = 0;

+				iDash = iDashStart;

+				iphase = iphaseStart;

+				dashRemaining = dashRemainingStart;

+			}

+			/*

+			 * cap the right end of the next arc.  If the

+			 * next arc is actually the first arc, only

+			 * cap it if it joins with this arc.  This

+			 * case will occur when the final dash segment

+			 * of an on/off dash is off.  Of course, this

+			 * cap will be drawn at a strange time, but that

+			 * hardly matters...

+			 */

+			if ((iphase == 0 || isDoubleDash) &&

+			    (nexti != start || (arcsJoin && isDashed)))

+				addCap (&arcs[iphase].caps, &arcs[iphase].ncaps,

+ 					&capSize[iphase], RIGHT_END, nextk);

+		}

+		i = nexti;

+		if (i == start)

+			break;

+	}

+	/*

+	 * make sure the last section is rendered

+	 */

+	for (iphase = 0; iphase < (isDoubleDash ? 2 : 1); iphase++)

+		if (arcs[iphase].narcs > 0) {

+			arcs[iphase].arcs[arcs[iphase].narcs-1].render = 1;

+			arcs[iphase].arcs[arcs[iphase].narcs-1].join =

+			         arcs[iphase].njoins;

+			arcs[iphase].arcs[arcs[iphase].narcs-1].cap =

+			         arcs[iphase].ncaps;

+		}

+	xfree(data);

+	return arcs;

+arcfail:

+	miFreeArcs(arcs, pGC);

+	xfree(data);

+	return NULL;

+}

+

+static double

+angleToLength (

+	int	angle,

+	dashMap	*map)

+{

+	double	len, excesslen, sidelen = map->map[DASH_MAP_SIZE - 1], totallen;

+	int	di;

+	int	excess;

+	Bool	oddSide = FALSE;

+

+	totallen = 0;

+	if (angle >= 0) {

+		while (angle >= 90 * 64) {

+			angle -= 90 * 64;

+			totallen += sidelen;

+			oddSide = !oddSide;

+		}

+	} else {

+		while (angle < 0) {

+			angle += 90 * 64;

+			totallen -= sidelen;

+			oddSide = !oddSide;

+		}

+	}

+	if (oddSide)

+		angle = 90 * 64 - angle;

+		

+	di = xAngleToDashIndex (angle);

+	excess = angle - dashIndexToXAngle (di);

+

+	len = map->map[di];

+	/*

+	 * linearly interpolate between this point and the next

+	 */

+	if (excess > 0) {

+		excesslen = (map->map[di + 1] - map->map[di]) *

+				((double) excess) / dashXAngleStep;

+		len += excesslen;

+	}

+	if (oddSide)

+		totallen += (sidelen - len);

+	else

+		totallen += len;

+	return totallen;

+}

+

+/*

+ * len is along the arc, but may be more than one rotation

+ */

+

+static int

+lengthToAngle (

+	double	len,

+	dashMap	*map)

+{

+	double	sidelen = map->map[DASH_MAP_SIZE - 1];

+	int	angle, angleexcess;

+	Bool	oddSide = FALSE;

+	int	a0, a1, a;

+

+	angle = 0;

+	/*

+	 * step around the ellipse, subtracting sidelens and

+	 * adding 90 degrees.  oddSide will tell if the

+	 * map should be interpolated in reverse

+	 */

+	if (len >= 0) {

+		if (sidelen == 0)

+			return 2 * FULLCIRCLE;	/* infinity */

+		while (len >= sidelen) {

+			angle += 90 * 64;

+			len -= sidelen;

+			oddSide = !oddSide;

+		}

+	} else {

+		if (sidelen == 0)

+			return -2 * FULLCIRCLE;	/* infinity */

+		while (len < 0) {

+			angle -= 90 * 64;

+			len += sidelen;

+			oddSide = !oddSide;

+		}

+	}

+	if (oddSide)

+		len = sidelen - len;

+	a0 = 0;

+	a1 = DASH_MAP_SIZE - 1;

+	/*

+	 * binary search for the closest pre-computed length

+	 */

+	while (a1 - a0 > 1) {

+		a = (a0 + a1) / 2;

+		if (len > map->map[a])

+			a0 = a;

+		else

+			a1 = a;

+	}

+	angleexcess = dashIndexToXAngle (a0);

+	/*

+	 * linearly interpolate to the next point

+	 */

+	angleexcess += (len - map->map[a0]) /

+			(map->map[a0+1] - map->map[a0]) * dashXAngleStep;

+	if (oddSide)

+		angle += (90 * 64) - angleexcess;

+	else

+		angle += angleexcess;

+	return angle;

+}

+

+/*

+ * compute the angle of an ellipse which cooresponds to

+ * the given path length.  Note that the correct solution

+ * to this problem is an eliptic integral, we'll punt and

+ * approximate (it's only for dashes anyway).  This

+ * approximation uses a polygon.

+ *

+ * The remaining portion of len is stored in *lenp -

+ * this will be negative if the arc extends beyond

+ * len and positive if len extends beyond the arc.

+ */

+

+static int

+computeAngleFromPath (

+	int	startAngle,

+	int	endAngle,	/* normalized absolute angles in *64 degrees */

+	dashMap	*map,

+	int	*lenp,

+	int	backwards)

+{

+	int	a0, a1, a;

+	double	len0;

+	int	len;

+

+	a0 = startAngle;

+	a1 = endAngle;

+	len = *lenp;

+	if (backwards) {

+		/*

+		 * flip the problem around to always be

+		 * forwards

+		 */

+		a0 = FULLCIRCLE - a0;

+		a1 = FULLCIRCLE - a1;

+	}

+	if (a1 < a0)

+		a1 += FULLCIRCLE;

+	len0 = angleToLength (a0, map);

+	a = lengthToAngle (len0 + len, map);

+	if (a > a1) {

+		a = a1;

+		len -= angleToLength (a1, map) - len0;

+	} else

+		len = 0;

+	if (backwards)

+		a = FULLCIRCLE - a;

+	*lenp = len;

+	return a;

+}

+

+/*

+ * scan convert wide arcs.

+ */

+

+/*

+ * draw zero width/height arcs

+ */

+

+static void

+drawZeroArc (

+    DrawablePtr   pDraw,

+    GCPtr         pGC,

+    xArc          *tarc,

+    int		  lw,

+    miArcFacePtr	left,

+    miArcFacePtr	right)

+{

+	double	x0 = 0.0, y0 = 0.0, x1 = 0.0, y1 = 0.0, w, h, x, y;

+	double	xmax, ymax, xmin, ymin;

+	int	a0, a1;

+	double	a, startAngle, endAngle;

+	double	l, lx, ly;

+

+	l = lw / 2.0;

+	a0 = tarc->angle1;

+	a1 = tarc->angle2;

+	if (a1 > FULLCIRCLE)

+		a1 = FULLCIRCLE;

+	else if (a1 < -FULLCIRCLE)

+		a1 = -FULLCIRCLE;

+	w = (double)tarc->width / 2.0;

+	h = (double)tarc->height / 2.0;

+	/*

+	 * play in X coordinates right away

+	 */

+	startAngle = - ((double) a0 / 64.0);

+	endAngle = - ((double) (a0 + a1) / 64.0);

+	

+	xmax = -w;

+	xmin = w;

+	ymax = -h;

+	ymin = h;

+	a = startAngle;

+	for (;;)

+	{

+		x = w * miDcos(a);

+		y = h * miDsin(a);

+		if (a == startAngle)

+		{

+			x0 = x;

+			y0 = y;

+		}

+		if (a == endAngle)

+		{

+			x1 = x;

+			y1 = y;

+		}

+		if (x > xmax)

+			xmax = x;

+		if (x < xmin)

+			xmin = x;

+		if (y > ymax)

+			ymax = y;

+		if (y < ymin)

+			ymin = y;

+		if (a == endAngle)

+			break;

+		if (a1 < 0)	/* clockwise */

+		{

+			if (floor (a / 90.0) == floor (endAngle / 90.0))

+				a = endAngle;

+			else

+				a = 90 * (floor (a/90.0) + 1);

+		}

+		else

+		{

+			if (ceil (a / 90.0) == ceil (endAngle / 90.0))

+				a = endAngle;

+			else

+				a = 90 * (ceil (a/90.0) - 1);

+		}

+	}

+	lx = ly = l;

+	if ((x1 - x0) + (y1 - y0) < 0)

+	    lx = ly = -l;

+	if (h)

+	{

+	    ly = 0.0;

+	    lx = -lx;

+	}

+	else

+	    lx = 0.0;

+	if (right)

+	{

+	    right->center.x = x0;

+	    right->center.y = y0;

+	    right->clock.x = x0 - lx;

+	    right->clock.y = y0 - ly;

+	    right->counterClock.x = x0 + lx;

+	    right->counterClock.y = y0 + ly;

+	}

+	if (left)

+ 	{

+	    left->center.x = x1;

+	    left->center.y = y1;

+	    left->clock.x = x1 + lx;

+	    left->clock.y = y1 + ly;

+	    left->counterClock.x = x1 - lx;

+	    left->counterClock.y = y1 - ly;

+	}

+	

+	x0 = xmin;

+	x1 = xmax;

+	y0 = ymin;

+	y1 = ymax;

+	if (ymin != y1) {

+		xmin = -l;

+		xmax = l;

+	} else {

+		ymin = -l;

+		ymax = l;

+	}

+	if (xmax != xmin && ymax != ymin) {

+		int	minx, maxx, miny, maxy;

+		xRectangle  rect;

+

+		minx = ICEIL (xmin + w) + tarc->x;

+		maxx = ICEIL (xmax + w) + tarc->x;

+		miny = ICEIL (ymin + h) + tarc->y;

+		maxy = ICEIL (ymax + h) + tarc->y;

+		rect.x = minx;

+		rect.y = miny;

+		rect.width = maxx - minx;

+		rect.height = maxy - miny;

+		(*pGC->ops->PolyFillRect) (pDraw, pGC, 1, &rect);

+	}

+}

+

+/*

+ * this computes the ellipse y value associated with the

+ * bottom of the tail.

+ */

+

+static void

+tailEllipseY (

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	double		t;

+

+	acc->tail_y = 0.0;

+	if (def->w == def->h)

+	    return;

+	t = def->l * def->w;

+	if (def->w > def->h) {

+	    if (t < acc->h2)

+		return;

+	} else {

+	    if (t > acc->h2)

+		return;

+	}

+	t = 2.0 * def->h * t;

+	t = (CUBED_ROOT_4 * acc->h2 - cbrt(t * t)) / acc->h2mw2;

+	if (t > 0.0)

+	    acc->tail_y = def->h / CUBED_ROOT_2 * sqrt(t);

+}

+

+/*

+ * inverse functions -- compute edge coordinates

+ * from the ellipse

+ */

+

+static double

+outerXfromXY (

+	double			x,

+	double			y,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	return x + (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);

+}

+

+static double

+outerYfromXY (

+	double		x,

+	double		y,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	return y + (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);

+}

+

+static double

+innerXfromXY (

+	double			x,

+	double			y,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	return x - (x * acc->h2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);

+}

+

+static double

+innerYfromXY (

+	double			x,

+	double			y,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);

+}

+

+static double

+innerYfromY (

+	double	y,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	double	x;

+

+	x = (def->w / def->h) * sqrt (acc->h2 - y*y);

+

+	return y - (y * acc->w2l) / sqrt (x*x * acc->h4 + y*y * acc->w4);

+}

+

+static void

+computeLine (

+	double		x1,

+	double		y1,

+	double		x2,

+	double		y2,

+	struct line	*line)

+{

+	if (y1 == y2)

+		line->valid = 0;

+	else {

+		line->m = (x1 - x2) / (y1 - y2);

+		line->b = x1  - y1 * line->m;

+		line->valid = 1;

+	}

+}

+

+/*

+ * compute various accelerators for an ellipse.  These

+ * are simply values that are used repeatedly in

+ * the computations

+ */

+

+static void

+computeAcc (

+	xArc			*tarc,

+	int			lw,

+	struct arc_def		*def,

+	struct accelerators	*acc)

+{

+	def->w = ((double) tarc->width) / 2.0;

+	def->h = ((double) tarc->height) / 2.0;

+	def->l = ((double) lw) / 2.0;

+	acc->h2 = def->h * def->h;

+	acc->w2 = def->w * def->w;

+	acc->h4 = acc->h2 * acc->h2;

+	acc->w4 = acc->w2 * acc->w2;

+	acc->h2l = acc->h2 * def->l;

+	acc->w2l = acc->w2 * def->l;

+	acc->h2mw2 = acc->h2 - acc->w2;

+	acc->fromIntX = (tarc->width & 1) ? 0.5 : 0.0;

+	acc->fromIntY = (tarc->height & 1) ? 0.5 : 0.0;

+	acc->xorg = tarc->x + (tarc->width >> 1);

+	acc->yorgu = tarc->y + (tarc->height >> 1);

+	acc->yorgl = acc->yorgu + (tarc->height & 1);

+	tailEllipseY (def, acc);

+}

+		

+/*

+ * compute y value bounds of various portions of the arc,

+ * the outer edge, the ellipse and the inner edge.

+ */

+

+static void

+computeBound (

+	struct arc_def		*def,

+	struct arc_bound	*bound,

+	struct accelerators	*acc,

+	miArcFacePtr		right,

+	miArcFacePtr		left)

+{

+	double		t;

+	double		innerTaily;

+	double		tail_y;

+	struct bound	innerx, outerx;

+	struct bound	ellipsex;

+

+	bound->ellipse.min = Dsin (def->a0) * def->h;

+	bound->ellipse.max = Dsin (def->a1) * def->h;

+	if (def->a0 == 45 && def->w == def->h)

+		ellipsex.min = bound->ellipse.min;

+	else

+		ellipsex.min = Dcos (def->a0) * def->w;

+	if (def->a1 == 45 && def->w == def->h)

+		ellipsex.max = bound->ellipse.max;

+	else

+		ellipsex.max = Dcos (def->a1) * def->w;

+	bound->outer.min = outerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);

+	bound->outer.max = outerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);

+	bound->inner.min = innerYfromXY (ellipsex.min, bound->ellipse.min, def, acc);

+	bound->inner.max = innerYfromXY (ellipsex.max, bound->ellipse.max, def, acc);

+

+	outerx.min = outerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);

+	outerx.max = outerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);

+	innerx.min = innerXfromXY (ellipsex.min, bound->ellipse.min, def, acc);

+	innerx.max = innerXfromXY (ellipsex.max, bound->ellipse.max, def, acc);

+	

+	/*

+	 * save the line end points for the

+	 * cap code to use.  Careful here, these are

+	 * in cartesean coordinates (y increasing upwards)

+	 * while the cap code uses inverted coordinates

+	 * (y increasing downwards)

+	 */

+

+	if (right) {

+		right->counterClock.y = bound->outer.min;

+		right->counterClock.x = outerx.min;

+		right->center.y = bound->ellipse.min;

+		right->center.x = ellipsex.min;

+		right->clock.y = bound->inner.min;

+		right->clock.x = innerx.min;

+	}

+

+	if (left) {

+		left->clock.y = bound->outer.max;

+		left->clock.x = outerx.max;

+		left->center.y = bound->ellipse.max;

+		left->center.x = ellipsex.max;

+		left->counterClock.y = bound->inner.max;

+		left->counterClock.x = innerx.max;

+	}

+

+	bound->left.min = bound->inner.max;

+	bound->left.max = bound->outer.max;

+	bound->right.min = bound->inner.min;

+	bound->right.max = bound->outer.min;

+

+	computeLine (innerx.min, bound->inner.min, outerx.min, bound->outer.min,

+		      &acc->right);

+	computeLine (innerx.max, bound->inner.max, outerx.max, bound->outer.max,

+		     &acc->left);

+

+	if (bound->inner.min > bound->inner.max) {

+		t = bound->inner.min;

+		bound->inner.min = bound->inner.max;

+		bound->inner.max = t;

+	}

+	tail_y = acc->tail_y;

+	if (tail_y > bound->ellipse.max)

+		tail_y = bound->ellipse.max;

+	else if (tail_y < bound->ellipse.min)

+		tail_y = bound->ellipse.min;

+	innerTaily = innerYfromY (tail_y, def, acc);

+	if (bound->inner.min > innerTaily)

+		bound->inner.min = innerTaily;

+	if (bound->inner.max < innerTaily)

+		bound->inner.max = innerTaily;

+	bound->inneri.min = ICEIL(bound->inner.min - acc->fromIntY);

+	bound->inneri.max = floor(bound->inner.max - acc->fromIntY);

+	bound->outeri.min = ICEIL(bound->outer.min - acc->fromIntY);

+	bound->outeri.max = floor(bound->outer.max - acc->fromIntY);

+}

+

+/*

+ * 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

+ * lines to the entire ellipse,  the equation of the

+ * normal lines is:

+ *

+ *     ellipse_x h^2                   h^2

+ * x = ------------ y + ellipse_x (1 - --- )

+ *     ellipse_y w^2                   w^2

+ *

+ * 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)

+ *

+ *             (   h^4 y     )

+ * ellipse_y = ( ----------  ) ^ (1/3)

+ *             ( (h^2 - w^2) )

+ *

+ * The other two solutions to the equation are imaginary.

+ *

+ * This gives the position on the ellipse which generates

+ * the normal with the largest/smallest x intersection point.

+ *

+ * Now compute the second derivative to check whether

+ * the intersection is a minimum or maximum:

+ *

+ *    h (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))

+ * -  -------------------------------------------

+ *          w y0^3 (sqrt (h^2 - y^2)) ^ 3

+ *

+ * as we only care about the sign,

+ *

+ * - (y0^3 (w^2 - h^2) + h^2 y (3y0^2 - 2h^2))

+ *

+ * or (to use accelerators),

+ *

+ * y0^3 (h^2 - w^2) - h^2 y (3y0^2 - 2h^2) 

+ *

+ */

+

+/*

+ * computes the position on the ellipse whose normal line

+ * intersects the given scan line maximally

+ */

+

+static double

+hookEllipseY (

+	double			scan_y,

+	struct arc_bound	*bound,

+	struct accelerators	*acc,

+	int			left)

+{

+	double	ret;

+

+	if (acc->h2mw2 == 0) {

+		if ( (scan_y > 0 && !left) || (scan_y < 0 && left) )

+			return bound->ellipse.min;

+		return bound->ellipse.max;

+	}

+	ret = (acc->h4 * scan_y) / (acc->h2mw2);

+	if (ret >= 0)

+		return cbrt (ret);

+	else

+		return -cbrt (-ret);

+}

+

+/*

+ * computes the X value of the intersection of the

+ * given scan line with the right side of the lower hook

+ */

+

+static double

+hookX (

+	double			scan_y,

+	struct arc_def		*def,

+	struct arc_bound	*bound,

+	struct accelerators	*acc,

+	int			left)

+{

+	double	ellipse_y, x;

+	double	maxMin;

+

+	if (def->w != def->h) {

+		ellipse_y = hookEllipseY (scan_y, bound, acc, left);

+		if (boundedLe (ellipse_y, bound->ellipse)) {

+			/*

+		 	 * compute the value of the second

+		 	 * derivative

+		 	 */

+			maxMin = ellipse_y*ellipse_y*ellipse_y * acc->h2mw2 -

+		 	 acc->h2 * scan_y * (3 * ellipse_y*ellipse_y - 2*acc->h2);

+			if ((left && maxMin > 0) || (!left && maxMin < 0)) {

+				if (ellipse_y == 0)

+					return def->w + left ? -def->l : def->l;

+				x = (acc->h2 * scan_y - ellipse_y * acc->h2mw2) *

+					sqrt (acc->h2 - ellipse_y * ellipse_y) /

+			 		(def->h * def->w * ellipse_y);

+				return x;

+			}

+		}

+	}

+	if (left) {

+		if (acc->left.valid && boundedLe (scan_y, bound->left)) {

+			x = intersectLine (scan_y, acc->left);

+		} else {

+			if (acc->right.valid)

+				x = intersectLine (scan_y, acc->right);

+			else

+				x = def->w - def->l;

+		}

+	} else {

+		if (acc->right.valid && boundedLe (scan_y, bound->right)) {

+			x = intersectLine (scan_y, acc->right);

+		} else {

+			if (acc->left.valid)

+				x = intersectLine (scan_y, acc->left);

+			else

+				x = def->w - def->l;

+		}

+	}

+	return x;

+}

+

+/*

+ * generate the set of spans with

+ * the given y coordinate

+ */

+

+static void

+arcSpan (

+	int			y,

+	int			lx,

+	int			lw,

+	int			rx,

+	int			rw,

+	struct arc_def		*def,

+	struct arc_bound	*bounds,

+	struct accelerators	*acc,

+	int			mask)

+{

+	int linx, loutx, rinx, routx;

+	double x, altx;

+

+	if (boundedLe (y, bounds->inneri)) {

+	    linx = -(lx + lw);

+	    rinx = rx;

+	} else {

+	    /*

+	     * intersection with left face

+	     */

+	    x = hookX (y + acc->fromIntY, def, bounds, acc, 1);

+	    if (acc->right.valid &&

+		boundedLe (y + acc->fromIntY, bounds->right))

+	    {

+		altx = intersectLine (y + acc->fromIntY, acc->right);

+		if (altx < x)

+		    x = altx;

+	    }

+	    linx = -ICEIL(acc->fromIntX - x);

+	    rinx = ICEIL(acc->fromIntX + x);

+	}

+	if (boundedLe (y, bounds->outeri)) {

+	    loutx = -lx;

+	    routx = rx + rw;

+	} else {

+	    /*

+	     * intersection with right face

+	     */

+	    x = hookX (y + acc->fromIntY, def, bounds, acc, 0);

+	    if (acc->left.valid &&

+		boundedLe (y + acc->fromIntY, bounds->left))

+	    {

+		altx = x;

+		x = intersectLine (y + acc->fromIntY, acc->left);

+		if (x < altx)

+		    x = altx;

+	    }

+	    loutx = -ICEIL(acc->fromIntX - x);

+	    routx = ICEIL(acc->fromIntX + x);

+	}

+	if (routx > rinx) {

+	    if (mask & 1)

+		newFinalSpan (acc->yorgu - y,

+			      acc->xorg + rinx, acc->xorg + routx);

+	    if (mask & 8)

+		newFinalSpan (acc->yorgl + y,

+			      acc->xorg + rinx, acc->xorg + routx);

+	}

+	if (loutx > linx) {

+	    if (mask & 2)

+		newFinalSpan (acc->yorgu - y,

+			      acc->xorg - loutx, acc->xorg - linx);

+	    if (mask & 4)

+		newFinalSpan (acc->yorgl + y,

+			      acc->xorg - loutx, acc->xorg - linx);

+	}

+}

+

+static void

+arcSpan0 (

+	int			lx,

+	int			lw,

+	int			rx,

+	int			rw,

+	struct arc_def		*def,

+	struct arc_bound	*bounds,

+	struct accelerators	*acc,

+	int			mask)

+{

+    double x;

+

+    if (boundedLe (0, bounds->inneri) &&

+	acc->left.valid && boundedLe (0, bounds->left) &&

+	acc->left.b > 0)

+    {

+	x = def->w - def->l;

+	if (acc->left.b < x)

+	    x = acc->left.b;

+	lw = ICEIL(acc->fromIntX - x) - lx;

+	rw += rx;

+	rx = ICEIL(acc->fromIntX + x);

+	rw -= rx;

+    }

+    arcSpan (0, lx, lw, rx, rw, def, bounds, acc, mask);

+}

+

+static void

+tailSpan (

+	int			y,

+	int			lw,

+	int			rw,

+	struct arc_def		*def,

+	struct arc_bound	*bounds,

+	struct accelerators	*acc,

+	int			mask)

+{

+    double yy, xalt, x, lx, rx;

+    int n;

+

+    if (boundedLe(y, bounds->outeri))

+	arcSpan (y, 0, lw, -rw, rw, def, bounds, acc, mask);

+    else if (def->w != def->h) {

+	yy = y + acc->fromIntY;

+	x = tailX(yy, def, bounds, acc);

+	if (yy == 0.0 && x == -rw - acc->fromIntX)

+	    return;

+	if (acc->right.valid && boundedLe (yy, bounds->right)) {

+	    rx = x;

+	    lx = -x;

+	    xalt = intersectLine (yy, acc->right);

+	    if (xalt >= -rw - acc->fromIntX && xalt <= rx)

+		rx = xalt;

+	    n = ICEIL(acc->fromIntX + lx);

+	    if (lw > n) {

+		if (mask & 2)

+		    newFinalSpan (acc->yorgu - y,

+				  acc->xorg + n, acc->xorg + lw);

+		if (mask & 4)

+		    newFinalSpan (acc->yorgl + y,

+				  acc->xorg + n, acc->xorg + lw);

+	    }

+	    n = ICEIL(acc->fromIntX + rx);

+	    if (n > -rw) {

+		if (mask & 1)

+		    newFinalSpan (acc->yorgu - y,

+				  acc->xorg - rw, acc->xorg + n);

+		if (mask & 8)

+		    newFinalSpan (acc->yorgl + y,

+				  acc->xorg - rw, acc->xorg + n);

+	    }

+	}

+	arcSpan (y,

+		 ICEIL(acc->fromIntX - x), 0,

+		 ICEIL(acc->fromIntX + x), 0,

+		 def, bounds, acc, mask);

+    }

+}

+

+/*

+ * create whole arcs out of pieces.  This code is

+ * very bad.

+ */

+

+static struct finalSpan	**finalSpans = NULL;

+static int		finalMiny = 0, finalMaxy = -1;

+static int		finalSize = 0;

+

+static int		nspans = 0;	/* total spans, not just y coords */

+

+struct finalSpan {

+	struct finalSpan	*next;

+	int			min, max;	/* x values */

+};

+

+static struct finalSpan    *freeFinalSpans, *tmpFinalSpan;

+

+# define allocFinalSpan()   (freeFinalSpans ?\

+				((tmpFinalSpan = freeFinalSpans), \

+				 (freeFinalSpans = freeFinalSpans->next), \

+				 (tmpFinalSpan->next = 0), \

+				 tmpFinalSpan) : \

+			     realAllocSpan ())

+

+# define SPAN_CHUNK_SIZE    128

+

+struct finalSpanChunk {

+	struct finalSpan	data[SPAN_CHUNK_SIZE];

+	struct finalSpanChunk	*next;

+};

+

+static struct finalSpanChunk	*chunks;

+

+static struct finalSpan *

+realAllocSpan (void)

+{

+	struct finalSpanChunk	*newChunk;

+	struct finalSpan	*span;

+	int			i;

+

+	newChunk = xalloc (sizeof (struct finalSpanChunk));

+	if (!newChunk)

+		return (struct finalSpan *) NULL;

+	newChunk->next = chunks;

+	chunks = newChunk;

+	freeFinalSpans = span = newChunk->data + 1;

+	for (i = 1; i < SPAN_CHUNK_SIZE-1; i++) {

+		span->next = span+1;

+		span++;

+	}

+	span->next = 0;

+	span = newChunk->data;

+	span->next = 0;

+	return span;

+}

+

+static void

+disposeFinalSpans (void)

+{

+	struct finalSpanChunk	*chunk, *next;

+

+	for (chunk = chunks; chunk; chunk = next) {

+		next = chunk->next;

+		xfree (chunk);

+	}

+	chunks = 0;

+	freeFinalSpans = 0;

+	xfree(finalSpans);

+	finalSpans = 0;

+}

+

+static void

+fillSpans (

+    DrawablePtr	pDrawable,

+    GCPtr	pGC)

+{

+	struct finalSpan	*span;

+	DDXPointPtr		xSpan;

+	int			*xWidth;

+	int			i;

+	struct finalSpan	**f;

+	int			spany;

+	DDXPointPtr		xSpans;

+	int			*xWidths;

+

+	if (nspans == 0)

+		return;

+	xSpan = xSpans = xalloc (nspans * sizeof (DDXPointRec));

+	xWidth = xWidths = xalloc (nspans * sizeof (int));

+	if (xSpans && xWidths)

+	{

+	    i = 0;

+	    f = finalSpans;

+	    for (spany = finalMiny; spany <= finalMaxy; spany++, f++) {

+		    for (span = *f; span; span=span->next) {

+			    if (span->max <= span->min)

+				    continue;

+			    xSpan->x = span->min;

+			    xSpan->y = spany;

+			    ++xSpan;

+			    *xWidth++ = span->max - span->min;

+			    ++i;

+		    }

+	    }

+	    (*pGC->ops->FillSpans) (pDrawable, pGC, i, xSpans, xWidths, TRUE);

+	}

+	disposeFinalSpans ();

+	if (xSpans)

+	    xfree (xSpans);

+	if (xWidths)

+	    xfree (xWidths);

+	finalMiny = 0;

+	finalMaxy = -1;

+	finalSize = 0;

+	nspans = 0;

+}

+

+# define SPAN_REALLOC	100

+

+# define findSpan(y) ((finalMiny <= (y) && (y) <= finalMaxy) ? \

+			  &finalSpans[(y) - finalMiny] : \

+			  realFindSpan (y))

+

+static struct finalSpan **

+realFindSpan (int y)

+{

+	struct finalSpan	**newSpans;

+	int			newSize, newMiny, newMaxy;

+	int			change;

+	int			i;

+

+	if (y < finalMiny || y > finalMaxy) {

+		if (!finalSize) {

+			finalMiny = y;

+			finalMaxy = y - 1;

+		}

+		if (y < finalMiny)

+			change = finalMiny - y;

+		else

+			change = y - finalMaxy;

+		if (change >= SPAN_REALLOC)

+			change += SPAN_REALLOC;

+		else

+			change = SPAN_REALLOC;

+		newSize = finalSize + change;

+		newSpans = xalloc(newSize * sizeof (struct finalSpan *));

+		if (!newSpans)

+		    return NULL;

+		newMiny = finalMiny;

+		newMaxy = finalMaxy;

+		if (y < finalMiny)

+			newMiny = finalMiny - change;

+		else

+			newMaxy = finalMaxy + change;

+		if (finalSpans) {

+			memmove(((char *) newSpans) + (finalMiny-newMiny) * sizeof (struct finalSpan *),

+				(char *) finalSpans,

+			       finalSize * sizeof (struct finalSpan *));

+			xfree (finalSpans);

+		}

+		if ((i = finalMiny - newMiny) > 0)

+			bzero ((char *)newSpans, i * sizeof (struct finalSpan *));

+		if ((i = newMaxy - finalMaxy) > 0)

+			bzero ((char *)(newSpans + newSize - i),

+			       i * sizeof (struct finalSpan *));

+		finalSpans = newSpans;

+		finalMaxy = newMaxy;

+		finalMiny = newMiny;

+		finalSize = newSize;

+	}

+	return &finalSpans[y - finalMiny];

+}

+

+static void

+newFinalSpan (

+    int		y,

+    int	xmin,

+    int	xmax)

+{

+	struct finalSpan	*x;

+	struct finalSpan	**f;

+	struct finalSpan	*oldx;

+	struct finalSpan	*prev;

+

+	f = findSpan (y);

+	if (!f)

+	    return;

+	oldx = 0;

+	for (;;) {

+		prev = 0;

+		for (x = *f; x; x=x->next) {

+			if (x == oldx) {

+				prev = x;

+				continue;

+			}

+			if (x->min <= xmax && xmin <= x->max) {

+				if (oldx) {

+					oldx->min = min (x->min, xmin);

+					oldx->max = max (x->max, xmax);

+					if (prev)

+						prev->next = x->next;

+					else

+						*f = x->next;

+					--nspans;

+				} else {

+					x->min = min (x->min, xmin);

+					x->max = max (x->max, xmax);

+					oldx = x;

+				}

+				xmin = oldx->min;

+				xmax = oldx->max;

+				break;

+			}

+			prev = x;

+		}

+		if (!x)

+			break;

+	}

+	if (!oldx) {

+		x = allocFinalSpan ();

+		if (x)

+		{

+		    x->min = xmin;

+		    x->max = xmax;

+		    x->next = *f;

+		    *f = x;

+		    ++nspans;

+		}

+	}

+}

+

+static void

+mirrorSppPoint (

+	int		quadrant,

+	SppPointPtr	sppPoint)

+{

+	switch (quadrant) {

+	case 0:

+		break;

+	case 1:

+		sppPoint->x = -sppPoint->x;

+		break;

+	case 2:

+		sppPoint->x = -sppPoint->x;

+		sppPoint->y = -sppPoint->y;

+		break;

+	case 3:

+		sppPoint->y = -sppPoint->y;

+		break;

+	}

+	/*

+	 * and translate to X coordinate system

+	 */

+	sppPoint->y = -sppPoint->y;

+}

+

+/*

+ * split an arc into pieces which are scan-converted

+ * in the first-quadrant and mirrored into position.

+ * This is necessary as the scan-conversion code can

+ * only deal with arcs completely contained in the

+ * first quadrant.

+ */

+

+static void

+drawArc (

+	xArc *tarc,

+	int	l,

+	int	a0,

+	int	a1,

+	miArcFacePtr	right,

+	miArcFacePtr	left)	/* save end line points */

+{

+	struct arc_def		def;

+	struct accelerators	acc;

+	int			startq, endq, curq;

+	int			rightq, leftq = 0, righta = 0, lefta = 0;

+	miArcFacePtr		passRight, passLeft;

+	int			q0 = 0, q1 = 0, mask;

+	struct band {

+		int	a0, a1;

+		int	mask;

+	}	band[5], sweep[20];

+	int			bandno, sweepno;

+	int			i, j;

+	int			flipRight = 0, flipLeft = 0;			

+	int			copyEnd = 0;

+	miArcSpanData		*spdata;

+

+	spdata = miComputeWideEllipse(l, tarc);

+	if (!spdata)

+	    return;

+

+	if (a1 < a0)

+		a1 += 360 * 64;

+	startq = a0 / (90 * 64);

+	if (a0 == a1)

+	    endq = startq;

+	else

+	    endq = (a1-1) / (90 * 64);

+	bandno = 0;

+	curq = startq;

+	rightq = -1;

+	for (;;) {

+		switch (curq) {

+		case 0:

+			if (a0 > 90 * 64)

+				q0 = 0;

+			else

+				q0 = a0;

+			if (a1 < 360 * 64)

+				q1 = min (a1, 90 * 64);

+			else

+				q1 = 90 * 64;

+			if (curq == startq && a0 == q0 && rightq < 0) {

+				righta = q0;

+				rightq = curq;

+			}

+			if (curq == endq && a1 == q1) {

+				lefta = q1;

+				leftq = curq;

+			}

+			break;

+		case 1:

+			if (a1 < 90 * 64)

+				q0 = 0;

+			else

+				q0 = 180 * 64 - min (a1, 180 * 64);

+			if (a0 > 180 * 64)

+				q1 = 90 * 64;

+			else

+				q1 = 180 * 64 - max (a0, 90 * 64);

+			if (curq == startq && 180 * 64 - a0 == q1) {

+				righta = q1;

+				rightq = curq;

+			}

+			if (curq == endq && 180 * 64 - a1 == q0) {

+				lefta = q0;

+				leftq = curq;

+			}

+			break;

+		case 2:

+			if (a0 > 270 * 64)

+				q0 = 0;

+			else

+				q0 = max (a0, 180 * 64) - 180 * 64;

+			if (a1 < 180 * 64)

+				q1 = 90 * 64;

+			else

+				q1 = min (a1, 270 * 64) - 180 * 64;

+			if (curq == startq && a0 - 180*64 == q0) {

+				righta = q0;

+				rightq = curq;

+			}

+			if (curq == endq && a1 - 180 * 64 == q1) {

+				lefta = q1;

+				leftq = curq;

+			}

+			break;

+		case 3:

+			if (a1 < 270 * 64)

+				q0 = 0;

+			else

+				q0 = 360 * 64 - min (a1, 360 * 64);

+			q1 = 360 * 64 - max (a0, 270 * 64);

+			if (curq == startq && 360 * 64 - a0 == q1) {

+				righta = q1;

+				rightq = curq;

+			}

+			if (curq == endq && 360 * 64 - a1 == q0) {

+				lefta = q0;

+				leftq = curq;

+			}

+			break;

+		}

+		band[bandno].a0 = q0;

+		band[bandno].a1 = q1;

+		band[bandno].mask = 1 << curq;

+		bandno++;

+		if (curq == endq)

+			break;

+		curq++;

+		if (curq == 4) {

+			a0 = 0;

+			a1 -= 360 * 64;

+			curq = 0;

+			endq -= 4;

+		}

+	}

+	sweepno = 0;

+	for (;;) {

+		q0 = 90 * 64;

+		mask = 0;

+		/*

+		 * find left-most point

+		 */

+		for (i = 0; i < bandno; i++)

+			if (band[i].a0 <= q0) {

+				q0 = band[i].a0;

+				q1 = band[i].a1;

+				mask = band[i].mask;

+			}

+		if (!mask)

+			break;

+		/*

+		 * locate next point of change

+		 */

+		for (i = 0; i < bandno; i++)

+			if (!(mask & band[i].mask)) {

+				if (band[i].a0 == q0) {

+					if (band[i].a1 < q1)

+						q1 = band[i].a1;

+					mask |= band[i].mask;

+ 				} else if (band[i].a0 < q1)

+					q1 = band[i].a0;

+			}

+		/*

+		 * create a new sweep

+		 */

+		sweep[sweepno].a0 = q0;

+		sweep[sweepno].a1 = q1;

+		sweep[sweepno].mask = mask;

+		sweepno++;

+		/*

+		 * subtract the sweep from the affected bands

+		 */

+		for (i = 0; i < bandno; i++)

+			if (band[i].a0 == q0) {

+				band[i].a0 = q1;

+				/*

+				 * check if this band is empty

+				 */

+				if (band[i].a0 == band[i].a1)

+					band[i].a1 = band[i].a0 = 90 * 64 + 1;

+			}

+	}

+	computeAcc (tarc, l, &def, &acc);

+	for (j = 0; j < sweepno; j++) {

+		mask = sweep[j].mask;

+		passRight = passLeft = 0;

+ 		if (mask & (1 << rightq)) {

+			if (sweep[j].a0 == righta)

+				passRight = right;

+			else if (sweep[j].a1 == righta) {

+				passLeft = right;

+				flipRight = 1;

+			}

+		}

+		if (mask & (1 << leftq)) {

+			if (sweep[j].a1 == lefta)

+			{

+				if (passLeft)

+					copyEnd = 1;

+				passLeft = left;

+			}

+			else if (sweep[j].a0 == lefta) {

+				if (passRight)

+					copyEnd = 1;

+				passRight = left;

+				flipLeft = 1;

+			}

+		}

+		drawQuadrant (&def, &acc, sweep[j].a0, sweep[j].a1, mask, 

+ 			      passRight, passLeft, spdata);

+	}

+	/*

+	 * when copyEnd is set, both ends of the arc were computed

+	 * at the same time; drawQuadrant only takes one end though,

+	 * so the left end will be the only one holding the data.  Copy

+	 * it from there.

+	 */

+	if (copyEnd)

+		*right = *left;

+	/*

+	 * mirror the coordinates generated for the

+	 * faces of the arc

+	 */

+	if (right) {

+		mirrorSppPoint (rightq, &right->clock);

+		mirrorSppPoint (rightq, &right->center);

+		mirrorSppPoint (rightq, &right->counterClock);

+		if (flipRight) {

+			SppPointRec	temp;

+

+			temp = right->clock;

+			right->clock = right->counterClock;

+			right->counterClock = temp;

+		}

+	}

+	if (left) {

+		mirrorSppPoint (leftq,  &left->counterClock);

+		mirrorSppPoint (leftq,  &left->center);

+		mirrorSppPoint (leftq,  &left->clock);

+		if (flipLeft) {

+			SppPointRec	temp;

+

+			temp = left->clock;

+			left->clock = left->counterClock;

+			left->counterClock = temp;

+		}

+	}

+	xfree(spdata);

+}

+

+static void

+drawQuadrant (

+	struct arc_def		*def,

+	struct accelerators	*acc,

+	int			a0,

+	int			a1,

+	int			mask,

+	miArcFacePtr		right,

+	miArcFacePtr		left,

+	miArcSpanData		*spdata)

+{

+	struct arc_bound	bound;

+	double			yy, x, xalt;

+	int			y, miny, maxy;

+	int			n;

+	miArcSpan		*span;

+

+	def->a0 = ((double) a0) / 64.0;

+	def->a1 = ((double) a1) / 64.0;

+	computeBound (def, &bound, acc, right, left);

+	yy = bound.inner.min;

+	if (bound.outer.min < yy)

+	    yy = bound.outer.min;

+	miny = ICEIL(yy - acc->fromIntY);

+	yy = bound.inner.max;

+	if (bound.outer.max > yy)

+	    yy = bound.outer.max;

+	maxy = floor(yy - acc->fromIntY);

+	y = spdata->k;

+	span = spdata->spans;

+	if (spdata->top)

+	{

+	    if (a1 == 90 * 64 && (mask & 1))

+		newFinalSpan (acc->yorgu - y - 1, acc->xorg, acc->xorg + 1);

+	    span++;

+	}

+	for (n = spdata->count1; --n >= 0; )

+	{

+	    if (y < miny)

+		return;

+	    if (y <= maxy) {

+		arcSpan (y,

+			 span->lx, -span->lx, 0, span->lx + span->lw,

+			 def, &bound, acc, mask);

+		if (span->rw + span->rx)

+		    tailSpan (y, -span->rw, -span->rx, def, &bound, acc, mask);

+	    }

+	    y--;

+	    span++;

+	}

+	if (y < miny)

+	    return;

+	if (spdata->hole)

+	{

+	    if (y <= maxy)

+		arcSpan (y, 0, 0, 0, 1, def, &bound, acc, mask & 0xc);

+	}

+	for (n = spdata->count2; --n >= 0; )

+	{

+	    if (y < miny)

+		return;

+	    if (y <= maxy)

+		arcSpan (y, span->lx, span->lw, span->rx, span->rw,

+			 def, &bound, acc, mask);

+	    y--;

+	    span++;

+	}

+	if (spdata->bot && miny <= y && y <= maxy)

+	{

+	    n = mask;

+	    if (y == miny)

+		n &= 0xc;

+	    if (span->rw <= 0) {

+		arcSpan0 (span->lx, -span->lx, 0, span->lx + span->lw,

+			  def, &bound, acc, n);

+		if (span->rw + span->rx)

+		    tailSpan (y, -span->rw, -span->rx, def, &bound, acc, n);

+	    }

+	    else

+		arcSpan0 (span->lx, span->lw, span->rx, span->rw,

+			  def, &bound, acc, n);

+	    y--;

+	}

+	while (y >= miny) {

+	    yy = y + acc->fromIntY;

+	    if (def->w == def->h) {

+		xalt = def->w - def->l;

+		x = -sqrt(xalt * xalt - yy * yy);

+	    } else {

+		x = tailX(yy, def, &bound, acc);

+		if (acc->left.valid && boundedLe (yy, bound.left)) {

+		    xalt = intersectLine (yy, acc->left);

+		    if (xalt < x)

+			x = xalt;

+		}

+		if (acc->right.valid && boundedLe (yy, bound.right)) {

+		    xalt = intersectLine (yy, acc->right);

+		    if (xalt < x)

+			x = xalt;

+		}

+	    }

+	    arcSpan (y,

+		     ICEIL(acc->fromIntX - x), 0,

+		     ICEIL(acc->fromIntX + x), 0,

+		     def, &bound, acc, mask);

+	    y--;

+	}

+}