/* Combined Purdue/PurduePlus patches, level 2.0, 1/17/89 */
/***********************************************************
Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
and the Massachusetts Institute of Technology, Cambridge, 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 names of Digital or MIT 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.

******************************************************************/
/* $XConsortium: mfbline.c,v 1.38 88/09/06 14:53:23 jim Exp $ */
#include "X.h"

#include "gcstruct.h"
#include "windowstr.h"
#include "pixmapstr.h"
#include "regionstr.h"
#include "scrnintstr.h"
#include "../../mi/mistruct.h"
#include "../../../os/msdos/msdos.h"

#include "ega.h"
#include "../common/mouse.h"

#include "../../mi/mifpoly.h"

/* single-pixel lines on a monochrome frame buffer

   NON-SLOPED LINES
   horizontal lines are always drawn left to right; we have to
move the endpoints right by one after they're swapped.
   horizontal lines will be confined to a single band of a
region.  the code finds that band (giving up if the lower
bound of the band is above the line we're drawing); then it
finds the first box in that band that contains part of the
line.  we clip the line to subsequent boxes in that band.
   vertical lines are always drawn top to bottom (y-increasing.)
this requires adding one to the y-coordinate of each endpoint
after swapping.

   SLOPED LINES
   when clipping a sloped line, we bring the second point inside
the clipping box, rather than one beyond it, and then add 1 to
the length of the line before drawing it.  this lets us use
the same box for finding the outcodes for both endpoints.  since
the equation for clipping the second endpoint to an edge gives us
1 beyond the edge, we then have to move the point towards the
first point by one step on the major axis.
   eventually, there will be a diagram here to explain what's going
on.  the method uses Cohen-Sutherland outcodes to determine
outsideness, and a method similar to Pike's layers for doing the
actual clipping.

   DIVISION
   when clipping the lines, we want to round the answer, rather
than truncating.  We want to avoid floating point; we also
want to avoid the special code required when the dividend
and divisor have different signs.

    we work a little to make all the numbers in the division
positive.  we then use the signs of the major and minor axes
decide whether to add or subtract.  this takes the special-case 
code out of the rounding division (making it easier for a 
compiler or inline to do something clever).

   CEILING
   someties, we want the ceiling.  ceil(m/n) == floor((m+n-1)/n),
for n > 0.  in C, integer division results in floor.]

   MULTIPLICATION
   when multiplying by signdx or signdy, we KNOW that it will
be a multiplication by 1 or -1, but most compilers can't
figure this out.  if your compiler/hardware combination
does better at the ?: operator and 'move negated' instructions
that it does at multiplication, you should consider using
the alternate macros.

   OPTIMIZATION
   there has been no attempt to optimize this code.  there
are obviously many special cases, at the cost of increased
code space.  a few inline procedures (e.g. round, SignTimes,
ceiling, abs) would be very useful, since the macro expansions
are not very intelligent.

   NOTE
   maybe OUTCODES should take box (the one that includes all
edges) instead of pbox (the standard no-right-or-lower-edge one)?
*/
#define OUTCODES(result, x, y, pbox) \
    if (x < pbox->x1) \
	result |= OUT_LEFT; \
    if (y < pbox->y1) \
	result |= OUT_ABOVE; \
    if (x >= pbox->x2) \
	result |= OUT_RIGHT; \
    if (y >= pbox->y2) \
	result |= OUT_BELOW;

#define round(dividend, divisor) \
( (((dividend)<<1) + (divisor)) / ((divisor)<<1) )

#define ceiling(m,n)  (((m)-1)/(n) + 1)

/*
#define SignTimes(sign, n) ((sign) * ((int)(n)))
*/

#define SignTimes(sign, n) \
    ( ((sign)<0) ? -(n) : (n) )

#define SWAPPT(p1, p2, pttmp) \
pttmp = p1; \
p1 = p2; \
p2 = pttmp;

#define SWAPINT(i, j, t) \
t = i; \
i = j; \
j = t;

static int near mfbClipLine(BoxPtr, BoxRec,
	    DDXPointPtr, DDXPointPtr, DDXPointPtr, 
	    int, int, int, int, int,
	    int *, int *);

void
mfbLineSS(pDrawable, pGC, mode, npt, pptInit)
    DrawablePtr pDrawable;
    GCPtr pGC;
    int mode;		/* Origin or Previous */
    int npt;		/* number of points */
    DDXPointPtr pptInit;
{
    int nboxInit;
    register int nbox;
    RegBoxPtr pboxInit;
    register RegBoxPtr pbox;
    int nptTmp;
    DDXPointPtr ppt;		/* pointer to list of translated points */
    int iswin;

    DDXPointRec pt1;
    DDXPointRec pt2;

    unsigned int oc1;		/* outcode of point 1 */
    unsigned int oc2;		/* outcode of point 2 */

    _segment base;
    char _based(base) *addrl;		/* address of first point */
    int nlwidth;		/* width in longwords of destination bitmap */
    int xorg, yorg;		/* origin of window */

    int adx;		/* abs values of dx and dy */
    int ady;
    int signdx;		/* sign of dx and dy */
    int signdy;
    int e, e1, e2;		/* bresenham error and increments */
    int len;			/* length of segment */
    int axis;			/* major axis */

    int clipDone;		/* flag for clipping loop */
    DDXPointRec pt1Orig;	/* unclipped start point */
    DDXPointRec pt2Orig;	/* unclipped end point */
    int err;			/* modified bresenham error term */
    int clip1, clip2;		/* clippedness of the endpoints */

    int clipdx, clipdy;		/* difference between clipped and
				   unclipped start point */

				/* a bunch of temporaries */
    int tmp;
    int x1, x2, y1, y2;

    pboxInit = REGION_RECTS(((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->pCompositeClip);
    nboxInit = REGION_NUM_RECTS(((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->pCompositeClip);

    if (pDrawable->type == DRAWABLE_WINDOW)
    {
	iswin = 1;
	base = egapriv.fb;
	addrl = 0;
	nlwidth = (int)
		((egaPrivScr *)(pDrawable->pScreen->devPrivate))->devKind;

    }
    else
    {
	iswin = 0;
	base = (u_short)((u_long)(((PixmapPtr)pDrawable)->devPrivate.ptr) >> 16);
	addrl = (u_char _based(base) *)(u_short)(u_long)(((PixmapPtr)pDrawable)->devPrivate.ptr);
	nlwidth = (int)((PixmapPtr)pDrawable)->devKind;
    }
    xorg = pDrawable->x;
    yorg = pDrawable->y;

    /* translate the point list */
    ppt = pptInit;
    nptTmp = npt;
    if (mode == CoordModeOrigin)
    {
	while(nptTmp--)
	{
	    ppt->x += xorg;
	    ppt++->y += yorg;
	}
    }
    else
    {
	ppt->x += xorg;
	ppt->y += yorg;
	nptTmp--;
	while(nptTmp--)
	{
	    ppt++;
	    ppt->x += (ppt-1)->x;
	    ppt->y += (ppt-1)->y;
	}
    }

    ppt = pptInit;
    while(--npt)
    {
	nbox = nboxInit;
	pbox = pboxInit;

	pt1 = *ppt++;
	pt2 = *ppt;

	if (pt1.x == pt2.x)
	{
	    /* make the line go top to bottom of screen, keeping
	       endpoint semantics
	    */
	    if (pt1.y > pt2.y)
	    {
		tmp = pt2.y;
		pt2.y = pt1.y + 1;
		pt1.y = tmp + 1;
	    }

	    /* get to first band that might contain part of line */
	    while ((nbox) && (pbox->y2 <= pt1.y))
	    {
		pbox++;
		nbox--;
	    }

	    if (nbox)
	    {
		/* stop when lower edge of box is beyond end of line */
		while((nbox) && (pt2.y >= pbox->y1))
		{
		    if ((pt1.x >= pbox->x1) && (pt1.x < pbox->x2))
		    {
			/* this box has part of the line in it */
			y1 = max(pt1.y, pbox->y1);
			y2 = min(pt2.y, pbox->y2);
			if (y1 != y2)
			{
			    /* Turn cursor off */
			    if (iswin) {
#ifdef DIRECT_MOUSE
				ConditionalOff(pt1.x, y1, pt1.x+1, y2);
#else
				if (CUR_OVERLAP(pt1.x, y1, pt1.x+1, y2))
				    HideCursor();
#endif
			    }
			    mfbVertS( ((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->rop,
				      addrl, base, nlwidth, 
				      pt1.x, y1, y2-y1);
#ifdef DIRECT_MOUSE
			    if (iswin) {
				ShowCursor();
			    }
#endif
			}
		    }
		    nbox--;
		    pbox++;
		}
	    }

	}
	else if (pt1.y == pt2.y)
	{
	    /* force line from left to right, keeping
	       endpoint semantics
	    */
	    if (pt1.x > pt2.x)
	    {
		tmp = pt2.x;
		pt2.x = pt1.x + 1;
		pt1.x = tmp + 1;
	    }

	    /* find the correct band */
	    while( (nbox) && (pbox->y2 <= pt1.y))
	    {
		pbox++;
		nbox--;
	    }

	    /* try to draw the line, if we haven't gone beyond it */
	    if ((nbox) && (pbox->y1 <= pt1.y))
	    {
		/* when we leave this band, we're done */
		tmp = pbox->y1;
		while((nbox) && (pbox->y1 == tmp))
		{
		    if (pbox->x2 <= pt1.x)
		    {
			/* skip boxes until one might contain start point */
			nbox--;
			pbox++;
			continue;
		    }

		    /* stop if left of box is beyond right of line */
		    if (pbox->x1 >= pt2.x)
		    {
			nbox = 0;
			continue;
		    }

		    x1 = max(pt1.x, pbox->x1);
		    x2 = min(pt2.x, pbox->x2);
		    if (x1 != x2)
		    {
			if (iswin) {
#ifdef DIRECT_MOUSE
			    ConditionalOff(x1, pt1.y, x2, pt1.y+1);
#else
			    if (CUR_OVERLAP(x1, pt1.y, x2, pt1.y+1))
				HideCursor();
#endif
			}
			mfbHorzS( ((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->rop,
				  addrl, base, nlwidth, 
				  x1, pt1.y, x2-x1);
#ifdef DIRECT_MOUSE
			if (iswin) {
			    ShowCursor();
			}
#endif
		    }
		    nbox--;
		    pbox++;
		}
	    }
	}
	else	/* sloped line */
	{

	    adx = pt2.x - pt1.x;
	    ady = pt2.y - pt1.y;
	    signdx = sign(adx);
	    signdy = sign(ady);
	    adx = abs(adx);
	    ady = abs(ady);

	    if (adx > ady)
	    {
		axis = X_AXIS;
		e1 = ady*2;
		e2 = e1 - 2*adx;
		e = e1 - adx;

	    }
	    else
	    {
		axis = Y_AXIS;
		e1 = adx*2;
		e2 = e1 - 2*ady;
		e = e1 - ady;
	    }

	    /* we have bresenham parameters and two points.
	       all we have to do now is clip and draw.
	    */

	    pt1Orig = pt1;
	    pt2Orig = pt2;

	    while(nbox--)
	    {

		BoxRec box;

		pt1 = pt1Orig;
		pt2 = pt2Orig;
		clipDone = 0;
		box.x1 = pbox->x1;
		box.y1 = pbox->y1;
		box.x2 = pbox->x2-1;
		box.y2 = pbox->y2-1;
		clip1 = 0;
		clip2 = 0;

		oc1 = 0;
		oc2 = 0;
		OUTCODES(oc1, pt1.x, pt1.y, pbox);
		OUTCODES(oc2, pt2.x, pt2.y, pbox);

		if (oc1 & oc2)
		    clipDone = -1;
		else if ((oc1 | oc2) == 0)
		    clipDone = 1;
		else /* have to clip */
		    clipDone = mfbClipLine(pbox, box,
					   &pt1Orig, &pt1, &pt2, 
					   adx, ady, signdx, signdy, axis,
					   &clip1, &clip2);

		if (clipDone == -1)
		{
		    pbox++;
		}
		else
		{

		    if (axis == X_AXIS)
			len = abs(pt2.x - pt1.x);
		    else
			len = abs(pt2.y - pt1.y);

		    len += (clip2 != 0);
		    if (len)
		    {
			/* unwind bresenham error term to first point */
			if (clip1)
			{
			    clipdx = abs(pt1.x - pt1Orig.x);
			    clipdy = abs(pt1.y - pt1Orig.y);
			    if (axis == X_AXIS)
				err = e+((clipdy*e2) + ((clipdx-clipdy)*e1));
			    else
				err = e+((clipdx*e2) + ((clipdy-clipdx)*e1));
			}
			else
			    err = e;
			if (iswin) {
#ifdef DIRECT_MOUSE
			    {
			    _asm	push	si
			    _asm	push	di
			    }
			    if (pt1.x < pt2.x) {
				_asm	mov	cx,pt1.x
				_asm	mov	si,pt2.x
			    } else {
				_asm	mov	cx,pt2.x
				_asm	mov	si,pt2.x
			    }
			    if (pt1.y < pt2.y) {
				_asm	mov	dx,pt1.y
				_asm	mov	di,pt2.y
			    } else {
				_asm	mov	dx,pt2.y
				_asm	mov	di,pt1.y
			    }

			    {
			    _asm	mov	ax,16
			    _asm	int	0x33
			    _asm	pop	di
			    _asm	pop	si
			    }
#else
			    int x1, y1, x2, y2;

			    if (pt1.x < pt2.x) {
				x1 = pt1.x;
				x2 = pt2.x;
			    } else {
				x1 = pt2.x;
				x2 = pt1.x;
			    }
			    if (pt1.y < pt2.y) {
				y1 = pt1.y;
				y2 = pt2.y;
			    } else {
				y1 = pt2.y;
				y2 = pt1.y;
			    }
			    if (CUR_OVERLAP(x1, y1, x2, y2))
				HideCursor();
#endif
			}
			mfbBresS( ((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->rop,
				  addrl, base, nlwidth,
				  signdx, signdy, axis, pt1.x, pt1.y,
				  err, e1, e2, len);
#ifdef DIRECT_MOUSE
			if (iswin) {
			    ShowCursor();
			}
#endif
		    }

		    /* if segment is unclipped, skip remaining rectangles */
		    if (!(clip1 || clip2))
			break;
		    else
			pbox++;
		}
	    } /* while (nbox--) */
	} /* sloped line */
    } /* while (nline--) */

    /* paint the last point if the end style isn't CapNotLast.
       (Assume that a projecting, butt, or round cap that is one
        pixel wide is the same as the single pixel of the endpoint.)
    */

    if ((pGC->capStyle != CapNotLast) &&
	((ppt->x != pptInit->x) ||
	 (ppt->y != pptInit->y) ||
	 (ppt == pptInit + 1)))
    {
	pt1 = *ppt;

	nbox = nboxInit;
	pbox = pboxInit;
	while (nbox--)
	{
	    if ((pt1.x >= pbox->x1) &&
		(pt1.y >= pbox->y1) &&
		(pt1.x <  pbox->x2) &&
		(pt1.y <  pbox->y2))
	    {
		addrl += (pt1.y * nlwidth) + (pt1.x >> 3);
		if (iswin) {
#ifdef DIRECT_MOUSE
			ConditionalOff(pt1.x, pt1.y, pt1.x+1, pt1.y+1);
#else
			if (CUR_OVERLAP(pt1.x, pt1.y, pt1.x+1, pt1.y+1))
			    HideCursor();
#endif
		}
		switch( ((egaPrivGC *)(pGC->devPrivates[egaGCPrivateIndex].ptr))->rop)
		{
		    case RROP_BLACK:
			*addrl &= ~(0x80>>(pt1.x&7));
			break;
		    case RROP_WHITE:
			*addrl |= 0x80>>(pt1.x&7);
			break;
		    case RROP_INVERT:
			*addrl ^= 0x80>>(pt1.x&7);
			break;
		}
#ifdef DIRECT_MOUSE
		if (iswin) {
			ShowCursor();
		}
#endif
		break;
	    }
	    else
		pbox++;
	}
    }
}

/*
    the clipping code could be cleaned up some; most of its
mess derives from originally being inline in the line code,
then pulled out to make clipping dashes easier.
*/

static int near
mfbClipLine(pbox, box,
	    ppt1Orig, ppt1, ppt2, 
	    adx, ady, signdx, signdy, axis,
	    pclip1, pclip2)
BoxPtr pbox;			/* box to clip to */
BoxRec box;			/* box to do calculations with */
DDXPointPtr ppt1Orig, ppt1, ppt2;
register int adx, ady;
register int signdx, signdy;
int axis;
int *pclip1, *pclip2;
{
    DDXPointRec pt1Orig, pt1, pt2, ptTmp;
    int swapped = 0;
    int clipDone = 0;
    int tmp;
    register unsigned long utmp;
    int oc1, oc2;
    int clip1, clip2;

    pt1Orig = *ppt1Orig;
    pt1 = *ppt1;
    pt2 = *ppt2;
    clip1 = 0;
    clip2 = 0;

    do
    {
        oc1 = 0;
        oc2 = 0;
        OUTCODES(oc1, pt1.x, pt1.y, pbox);
        OUTCODES(oc2, pt2.x, pt2.y, pbox);

        if (oc1 & oc2)
	    clipDone = -1;
        else if ((oc1 | oc2) == 0)
        {
	    clipDone = 1;
	    if (swapped)
	    {
	        SWAPPT(pt1, pt2, ptTmp);
	        SWAPINT(oc1, oc2, tmp);
	        SWAPINT(clip1, clip2, tmp);
	    }
        }
        else /* have to clip */
        {
	    /* only clip one point at a time */
	    if (!oc1)
	    {
	        SWAPPT(pt1, pt2, ptTmp);
	        SWAPINT(oc1, oc2, tmp);
	        SWAPINT(clip1, clip2, tmp);
	        swapped = !swapped;
	    }
    
	    clip1 |= oc1;
	    if (oc1 & OUT_LEFT)
	    {
	      pt1.x = box.x1;
	      utmp = abs(box.x1 - pt1Orig.x);
	      utmp *= ady;
	      if(axis==X_AXIS)
	      {
	        pt1.y = pt1Orig.y + (int)SignTimes(signdy, round(utmp, adx));
	      }
	      else
	      {
		utmp <<= 1;
		if (swapped)
		    utmp += ady;
		else
		    utmp -= ady;
		pt1.y = pt1Orig.y + SignTimes(signdy, ceiling(utmp, 2*adx));
		if (swapped)
		    pt1.y -= signdy;
	      }
	    }
	    else if (oc1 & OUT_ABOVE)
	    {
	      pt1.y = box.y1;
	      utmp = abs(box.y1 - pt1Orig.y);
	      utmp *= adx;
	      if (axis == Y_AXIS)
	      {
	        pt1.x = pt1Orig.x + SignTimes(signdx, round(utmp, ady));
	      }
	      else
	      {
		utmp <<= 1;
		if (swapped)
		    utmp += adx;
		else
		    utmp -= adx;
		pt1.x = pt1Orig.x + SignTimes(signdx, ceiling(utmp, 2*ady));
		if (swapped)
		    pt1.x -= signdx;
	      }
	    }
	    else if (oc1 & OUT_RIGHT)
	    {
	      pt1.x = box.x2;
	      utmp = abs(pt1Orig.x - box.x2);
	      utmp *= ady;
	      if (axis == X_AXIS)
	      {
	        pt1.y = pt1Orig.y + SignTimes(signdy, round(utmp, adx));
	      }
	      else
	      {
		utmp <<= 1;
		if (swapped)
		    utmp += ady;
		else
		    utmp -= ady;
		pt1.y = pt1Orig.y + SignTimes(signdy, ceiling(utmp, 2*adx));
		if (swapped)
		    pt1.y -= signdy;
	      }
	    }
	    else if (oc1 & OUT_BELOW)
	    {
	      pt1.y = box.y2;
	      utmp = abs(pt1Orig.y - box.y2);
	      utmp *= adx;
	      if (axis == Y_AXIS)
	      {
	        pt1.x = pt1Orig.x + SignTimes(signdx, round(utmp, ady));
	      }
	      else
	      {
		utmp <<= 1;
		if (swapped)
		    utmp += adx;
		else
		    utmp -= adx;
		pt1.x = pt1Orig.x + SignTimes(signdx, ceiling(utmp, 2*ady));
		if (swapped)
		    pt1.x -= signdx;
	      }
	    }
        } /* else have to clip */
    } while(!clipDone);
    *ppt1 = pt1;
    *ppt2 = pt2;
    *pclip1 = clip1;
    *pclip2 = clip2;

    return clipDone;
}

/* XXX */
void
miRoundCap(pDraw, pGC, pCenter, pEnd, pCorner, pOtherCorner, fLineEnd,
     xOrg, yOrg, xFtrans, yFtrans)
    DrawablePtr	pDraw;
    GCPtr	pGC;
    SppPointRec	pCenter, pEnd;
    SppPointRec	pCorner, pOtherCorner;
    int		fLineEnd, xOrg, yOrg;
    double	xFtrans, yFtrans;
{
printf("miRoundCap - \n");
}

int
mfbMiter(pDrawable, pGC, a, b, pPoint, c, d)
DrawablePtr pDrawable;
GCPtr pGC;
Bool a;
int b;
SppPointRec *pPoint;
int c, d;
{
printf("mfbMiter -\n");
return FALSE;
}
