[deb_xorg-server.git] / mi / mizerclip.c

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

Copyright 1987, 1998  The Open Group

Permission to use, copy, modify, distribute, and sell this software and its
documentation for any purpose is hereby granted without fee, provided that
the above copyright notice appear in all copies and that both that
copyright notice and this permission notice appear in supporting
documentation.

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

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

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

Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.

                        All Rights Reserved

Permission to use, copy, modify, and distribute this software and its 
documentation for any purpose and without fee is hereby granted, 
provided that the above copyright notice appear in all copies and that
both that copyright notice and this permission notice appear in 
supporting documentation, and that the name of Digital not be
used in advertising or publicity pertaining to distribution of the
software without specific, written prior permission.  

DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
SOFTWARE.

******************************************************************/
#ifdef HAVE_DIX_CONFIG_H
#include <dix-config.h>
#endif

#include <X11/X.h>

#include "misc.h"
#include "scrnintstr.h"
#include "gcstruct.h"
#include "windowstr.h"
#include "pixmap.h"
#include "mi.h"
#include "miline.h"

/*

The bresenham error equation used in the mi/mfb/cfb line routines is:

	e = error
	dx = difference in raw X coordinates
	dy = difference in raw Y coordinates
	M = # of steps in X direction
	N = # of steps in Y direction
	B = 0 to prefer diagonal steps in a given octant,
	    1 to prefer axial steps in a given octant

	For X major lines:
		e = 2Mdy - 2Ndx - dx - B
		-2dx <= e < 0

	For Y major lines:
		e = 2Ndx - 2Mdy - dy - B
		-2dy <= e < 0

At the start of the line, we have taken 0 X steps and 0 Y steps,
so M = 0 and N = 0:

	X major	e = 2Mdy - 2Ndx - dx - B
		  = -dx - B

	Y major	e = 2Ndx - 2Mdy - dy - B
		  = -dy - B

At the end of the line, we have taken dx X steps and dy Y steps,
so M = dx and N = dy:

	X major	e = 2Mdy - 2Ndx - dx - B
		  = 2dxdy - 2dydx - dx - B
		  = -dx - B
	Y major e = 2Ndx - 2Mdy - dy - B
		  = 2dydx - 2dxdy - dy - B
		  = -dy - B

Thus, the error term is the same at the start and end of the line.

Let us consider clipping an X coordinate.  There are 4 cases which
represent the two independent cases of clipping the start vs. the
end of the line and an X major vs. a Y major line.  In any of these
cases, we know the number of X steps (M) and we wish to find the
number of Y steps (N).  Thus, we will solve our error term equation.
If we are clipping the start of the line, we will find the smallest
N that satisfies our error term inequality.  If we are clipping the
end of the line, we will find the largest number of Y steps that
satisfies the inequality.  In that case, since we are representing
the Y steps as (dy - N), we will actually want to solve for the
smallest N in that equation.
\f
Case 1:  X major, starting X coordinate moved by M steps

		-2dx <= 2Mdy - 2Ndx - dx - B < 0
	2Ndx <= 2Mdy - dx - B + 2dx	2Ndx > 2Mdy - dx - B
	2Ndx <= 2Mdy + dx - B		N > (2Mdy - dx - B) / 2dx
	N <= (2Mdy + dx - B) / 2dx

Since we are trying to find the smallest N that satisfies these
equations, we should use the > inequality to find the smallest:

	N = floor((2Mdy - dx - B) / 2dx) + 1
	  = floor((2Mdy - dx - B + 2dx) / 2dx)
	  = floor((2Mdy + dx - B) / 2dx)

Case 1b: X major, ending X coordinate moved to M steps

Same derivations as Case 1, but we want the largest N that satisfies
the equations, so we use the <= inequality:

	N = floor((2Mdy + dx - B) / 2dx)

Case 2: X major, ending X coordinate moved by M steps

		-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
		-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
		-2dx <= 2Ndx - 2Mdy - dx - B < 0
	2Ndx >= 2Mdy + dx + B - 2dx	2Ndx < 2Mdy + dx + B
	2Ndx >= 2Mdy - dx + B		N < (2Mdy + dx + B) / 2dx
	N >= (2Mdy - dx + B) / 2dx

Since we are trying to find the highest number of Y steps that
satisfies these equations, we need to find the smallest N, so
we should use the >= inequality to find the smallest:

	N = ceiling((2Mdy - dx + B) / 2dx)
	  = floor((2Mdy - dx + B + 2dx - 1) / 2dx)
	  = floor((2Mdy + dx + B - 1) / 2dx)

Case 2b: X major, starting X coordinate moved to M steps from end

Same derivations as Case 2, but we want the smallest number of Y
steps, so we want the highest N, so we use the < inequality:

	N = ceiling((2Mdy + dx + B) / 2dx) - 1
	  = floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
	  = floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
	  = floor((2Mdy + dx + B - 1) / 2dx)
\f
Case 3: Y major, starting X coordinate moved by M steps

		-2dy <= 2Ndx - 2Mdy - dy - B < 0
	2Ndx >= 2Mdy + dy + B - 2dy	2Ndx < 2Mdy + dy + B
	2Ndx >= 2Mdy - dy + B		N < (2Mdy + dy + B) / 2dx
	N >= (2Mdy - dy + B) / 2dx

Since we are trying to find the smallest N that satisfies these
equations, we should use the >= inequality to find the smallest:

	N = ceiling((2Mdy - dy + B) / 2dx)
	  = floor((2Mdy - dy + B + 2dx - 1) / 2dx)
	  = floor((2Mdy - dy + B - 1) / 2dx) + 1

Case 3b: Y major, ending X coordinate moved to M steps

Same derivations as Case 3, but we want the largest N that satisfies
the equations, so we use the < inequality:

	N = ceiling((2Mdy + dy + B) / 2dx) - 1
	  = floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
	  = floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
	  = floor((2Mdy + dy + B - 1) / 2dx)

Case 4: Y major, ending X coordinate moved by M steps

		-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
		-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
		-2dy <= 2Mdy - 2Ndx - dy - B < 0
	2Ndx <= 2Mdy - dy - B + 2dy	2Ndx > 2Mdy - dy - B
	2Ndx <= 2Mdy + dy - B		N > (2Mdy - dy - B) / 2dx
	N <= (2Mdy + dy - B) / 2dx

Since we are trying to find the highest number of Y steps that
satisfies these equations, we need to find the smallest N, so
we should use the > inequality to find the smallest:

	N = floor((2Mdy - dy - B) / 2dx) + 1

Case 4b: Y major, starting X coordinate moved to M steps from end

Same analysis as Case 4, but we want the smallest number of Y steps
which means the largest N, so we use the <= inequality:

	N = floor((2Mdy + dy - B) / 2dx)
\f
Now let's try the Y coordinates, we have the same 4 cases.

Case 5: X major, starting Y coordinate moved by N steps

		-2dx <= 2Mdy - 2Ndx - dx - B < 0
	2Mdy >= 2Ndx + dx + B - 2dx	2Mdy < 2Ndx + dx + B
	2Mdy >= 2Ndx - dx + B		M < (2Ndx + dx + B) / 2dy
	M >= (2Ndx - dx + B) / 2dy

Since we are trying to find the smallest M, we use the >= inequality:

	M = ceiling((2Ndx - dx + B) / 2dy)
	  = floor((2Ndx - dx + B + 2dy - 1) / 2dy)
	  = floor((2Ndx - dx + B - 1) / 2dy) + 1

Case 5b: X major, ending Y coordinate moved to N steps

Same derivations as Case 5, but we want the largest M that satisfies
the equations, so we use the < inequality:

	M = ceiling((2Ndx + dx + B) / 2dy) - 1
	  = floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
	  = floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
	  = floor((2Ndx + dx + B - 1) / 2dy)

Case 6: X major, ending Y coordinate moved by N steps

		-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
		-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
		-2dx <= 2Ndx - 2Mdy - dx - B < 0
	2Mdy <= 2Ndx - dx - B + 2dx	2Mdy > 2Ndx - dx - B
	2Mdy <= 2Ndx + dx - B		M > (2Ndx - dx - B) / 2dy
	M <= (2Ndx + dx - B) / 2dy

Largest # of X steps means smallest M, so use the > inequality:

	M = floor((2Ndx - dx - B) / 2dy) + 1

Case 6b: X major, starting Y coordinate moved to N steps from end

Same derivations as Case 6, but we want the smallest # of X steps
which means the largest M, so use the <= inequality:

	M = floor((2Ndx + dx - B) / 2dy)
\f
Case 7: Y major, starting Y coordinate moved by N steps

		-2dy <= 2Ndx - 2Mdy - dy - B < 0
	2Mdy <= 2Ndx - dy - B + 2dy	2Mdy > 2Ndx - dy - B
	2Mdy <= 2Ndx + dy - B		M > (2Ndx - dy - B) / 2dy
	M <= (2Ndx + dy - B) / 2dy

To find the smallest M, use the > inequality:

	M = floor((2Ndx - dy - B) / 2dy) + 1
	  = floor((2Ndx - dy - B + 2dy) / 2dy)
	  = floor((2Ndx + dy - B) / 2dy)

Case 7b: Y major, ending Y coordinate moved to N steps

Same derivations as Case 7, but we want the largest M that satisfies
the equations, so use the <= inequality:

	M = floor((2Ndx + dy - B) / 2dy)

Case 8: Y major, ending Y coordinate moved by N steps

		-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
		-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
		-2dy <= 2Mdy - 2Ndx - dy - B < 0
	2Mdy >= 2Ndx + dy + B - 2dy	2Mdy < 2Ndx + dy + B
	2Mdy >= 2Ndx - dy + B		M < (2Ndx + dy + B) / 2dy
	M >= (2Ndx - dy + B) / 2dy

To find the highest X steps, find the smallest M, use the >= inequality:

	M = ceiling((2Ndx - dy + B) / 2dy)
	  = floor((2Ndx - dy + B + 2dy - 1) / 2dy)
	  = floor((2Ndx + dy + B - 1) / 2dy)

Case 8b: Y major, starting Y coordinate moved to N steps from the end

Same derivations as Case 8, but we want to find the smallest # of X
steps which means the largest M, so we use the < inequality:

	M = ceiling((2Ndx + dy + B) / 2dy) - 1
	  = floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
	  = floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
	  = floor((2Ndx + dy + B - 1) / 2dy)
\f
So, our equations are:

	1:  X major move x1 to x1+M	floor((2Mdy + dx - B) / 2dx)
	1b: X major move x2 to x1+M	floor((2Mdy + dx - B) / 2dx)
	2:  X major move x2 to x2-M	floor((2Mdy + dx + B - 1) / 2dx)
	2b: X major move x1 to x2-M	floor((2Mdy + dx + B - 1) / 2dx)

	3:  Y major move x1 to x1+M	floor((2Mdy - dy + B - 1) / 2dx) + 1
	3b: Y major move x2 to x1+M	floor((2Mdy + dy + B - 1) / 2dx)
	4:  Y major move x2 to x2-M	floor((2Mdy - dy - B) / 2dx) + 1
	4b: Y major move x1 to x2-M	floor((2Mdy + dy - B) / 2dx)

	5:  X major move y1 to y1+N	floor((2Ndx - dx + B - 1) / 2dy) + 1
	5b: X major move y2 to y1+N	floor((2Ndx + dx + B - 1) / 2dy)
	6:  X major move y2 to y2-N	floor((2Ndx - dx - B) / 2dy) + 1
	6b: X major move y1 to y2-N	floor((2Ndx + dx - B) / 2dy)

	7:  Y major move y1 to y1+N	floor((2Ndx + dy - B) / 2dy)
	7b: Y major move y2 to y1+N	floor((2Ndx + dy - B) / 2dy)
	8:  Y major move y2 to y2-N	floor((2Ndx + dy + B - 1) / 2dy)
	8b: Y major move y1 to y2-N	floor((2Ndx + dy + B - 1) / 2dy)

We have the following constraints on all of the above terms:

	0 < M,N <= 2^15		 2^15 can be imposed by miZeroClipLine
	0 <= dx/dy <= 2^16 - 1
	0 <= B <= 1

The floor in all of the above equations can be accomplished with a
simple C divide operation provided that both numerator and denominator
are positive.

Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
and moving a Y coordinate implies dy != 0, we know that the denominators
are all > 0.

For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
bias.  Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
or > 0 to prove that the numerators are positive (or zero).

For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
constraints, the first four equations all have numerators >= 0.

For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
So (2Mdy - dy) > 0, since they are Y major lines.  Also, (2Mdy + dy) >= 3dy
or (2Mdy + dy) > 0.  So all of their numerators are >= 0.

For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
>= dx > 0.  Similarly (2Ndx + dx) >= 3dx > 0.  So all numerators >= 0.

For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
are > 0.

To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy.  This
is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
	   <= 2^16 * (2^16 - 1) + (2^16 - 1)
	   <= 2^32 - 2^16 + 2^16 - 1
	   <= 2^32 - 1
Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
the numerator is therefore (2^32 - 1), which does not overflow an unsigned
32 bit variable.

*/

/* Bit codes for the terms of the 16 clipping equations defined below. */

#define T_2NDX		(1 << 0)
#define T_2MDY		(0)     /* implicit term */
#define T_DXNOTY	(1 << 1)
#define T_DYNOTX	(0)     /* implicit term */
#define T_SUBDXORY	(1 << 2)
#define T_ADDDX		(T_DXNOTY)      /* composite term */
#define T_SUBDX		(T_DXNOTY | T_SUBDXORY) /* composite term */
#define T_ADDDY		(T_DYNOTX)      /* composite term */
#define T_SUBDY		(T_DYNOTX | T_SUBDXORY) /* composite term */
#define T_BIASSUBONE	(1 << 3)
#define T_SUBBIAS	(0)     /* implicit term */
#define T_DIV2DX	(1 << 4)
#define T_DIV2DY	(0)     /* implicit term */
#define T_ADDONE	(1 << 5)

/* Bit masks defining the 16 equations used in miZeroClipLine. */

#define EQN1	(T_2MDY | T_ADDDX | T_SUBBIAS    | T_DIV2DX)
#define EQN1B	(T_2MDY | T_ADDDX | T_SUBBIAS    | T_DIV2DX)
#define EQN2	(T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
#define EQN2B	(T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)

#define EQN3	(T_2MDY | T_SUBDY | T_BIASSUBONE | T_DIV2DX | T_ADDONE)
#define EQN3B	(T_2MDY | T_ADDDY | T_BIASSUBONE | T_DIV2DX)
#define EQN4	(T_2MDY | T_SUBDY | T_SUBBIAS    | T_DIV2DX | T_ADDONE)
#define EQN4B	(T_2MDY | T_ADDDY | T_SUBBIAS    | T_DIV2DX)

#define EQN5	(T_2NDX | T_SUBDX | T_BIASSUBONE | T_DIV2DY | T_ADDONE)
#define EQN5B	(T_2NDX | T_ADDDX | T_BIASSUBONE | T_DIV2DY)
#define EQN6	(T_2NDX | T_SUBDX | T_SUBBIAS    | T_DIV2DY | T_ADDONE)
#define EQN6B	(T_2NDX | T_ADDDX | T_SUBBIAS    | T_DIV2DY)

#define EQN7	(T_2NDX | T_ADDDY | T_SUBBIAS    | T_DIV2DY)
#define EQN7B	(T_2NDX | T_ADDDY | T_SUBBIAS    | T_DIV2DY)
#define EQN8	(T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
#define EQN8B	(T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)

/* miZeroClipLine
 *
 * returns:  1 for partially clipped line
 *          -1 for completely clipped line
 *
 */
int
miZeroClipLine(int xmin, int ymin, int xmax, int ymax,
               int *new_x1, int *new_y1, int *new_x2, int *new_y2,
               unsigned int adx, unsigned int ady,
               int *pt1_clipped, int *pt2_clipped,
               int octant, unsigned int bias, int oc1, int oc2)
{
    int swapped = 0;
    int clipDone = 0;
    CARD32 utmp = 0;
    int clip1, clip2;
    int x1, y1, x2, y2;
    int x1_orig, y1_orig, x2_orig, y2_orig;
    int xmajor;
    int negslope = 0, anchorval = 0;
    unsigned int eqn = 0;

    x1 = x1_orig = *new_x1;
    y1 = y1_orig = *new_y1;
    x2 = x2_orig = *new_x2;
    y2 = y2_orig = *new_y2;

    clip1 = 0;
    clip2 = 0;

    xmajor = IsXMajorOctant(octant);
    bias = ((bias >> octant) & 1);

    while (1) {
        if ((oc1 & oc2) != 0) { /* trivial reject */
            clipDone = -1;
            clip1 = oc1;
            clip2 = oc2;
            break;
        }
        else if ((oc1 | oc2) == 0) {    /* trivial accept */
            clipDone = 1;
            if (swapped) {
                SWAPINT_PAIR(x1, y1, x2, y2);
                SWAPINT(clip1, clip2);
            }
            break;
        }
        else {                  /* have to clip */

            /* only clip one point at a time */
            if (oc1 == 0) {
                SWAPINT_PAIR(x1, y1, x2, y2);
                SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
                SWAPINT(oc1, oc2);
                SWAPINT(clip1, clip2);
                swapped = !swapped;
            }

            clip1 |= oc1;
            if (oc1 & OUT_LEFT) {
                negslope = IsYDecreasingOctant(octant);
                utmp = xmin - x1_orig;
                if (utmp <= 32767) {    /* clip based on near endpt */
                    if (xmajor)
                        eqn = (swapped) ? EQN2 : EQN1;
                    else
                        eqn = (swapped) ? EQN4 : EQN3;
                    anchorval = y1_orig;
                }
                else {          /* clip based on far endpt */

                    utmp = x2_orig - xmin;
                    if (xmajor)
                        eqn = (swapped) ? EQN1B : EQN2B;
                    else
                        eqn = (swapped) ? EQN3B : EQN4B;
                    anchorval = y2_orig;
                    negslope = !negslope;
                }
                x1 = xmin;
            }
            else if (oc1 & OUT_ABOVE) {
                negslope = IsXDecreasingOctant(octant);
                utmp = ymin - y1_orig;
                if (utmp <= 32767) {    /* clip based on near endpt */
                    if (xmajor)
                        eqn = (swapped) ? EQN6 : EQN5;
                    else
                        eqn = (swapped) ? EQN8 : EQN7;
                    anchorval = x1_orig;
                }
                else {          /* clip based on far endpt */

                    utmp = y2_orig - ymin;
                    if (xmajor)
                        eqn = (swapped) ? EQN5B : EQN6B;
                    else
                        eqn = (swapped) ? EQN7B : EQN8B;
                    anchorval = x2_orig;
                    negslope = !negslope;
                }
                y1 = ymin;
            }
            else if (oc1 & OUT_RIGHT) {
                negslope = IsYDecreasingOctant(octant);
                utmp = x1_orig - xmax;
                if (utmp <= 32767) {    /* clip based on near endpt */
                    if (xmajor)
                        eqn = (swapped) ? EQN2 : EQN1;
                    else
                        eqn = (swapped) ? EQN4 : EQN3;
                    anchorval = y1_orig;
                }
                else {          /* clip based on far endpt */

                    /*
                     * Technically since the equations can handle
                     * utmp == 32768, this overflow code isn't
                     * needed since X11 protocol can't generate
                     * a line which goes more than 32768 pixels
                     * to the right of a clip rectangle.
                     */
                    utmp = xmax - x2_orig;
                    if (xmajor)
                        eqn = (swapped) ? EQN1B : EQN2B;
                    else
                        eqn = (swapped) ? EQN3B : EQN4B;
                    anchorval = y2_orig;
                    negslope = !negslope;
                }
                x1 = xmax;
            }
            else if (oc1 & OUT_BELOW) {
                negslope = IsXDecreasingOctant(octant);
                utmp = y1_orig - ymax;
                if (utmp <= 32767) {    /* clip based on near endpt */
                    if (xmajor)
                        eqn = (swapped) ? EQN6 : EQN5;
                    else
                        eqn = (swapped) ? EQN8 : EQN7;
                    anchorval = x1_orig;
                }
                else {          /* clip based on far endpt */

                    /*
                     * Technically since the equations can handle
                     * utmp == 32768, this overflow code isn't
                     * needed since X11 protocol can't generate
                     * a line which goes more than 32768 pixels
                     * below the bottom of a clip rectangle.
                     */
                    utmp = ymax - y2_orig;
                    if (xmajor)
                        eqn = (swapped) ? EQN5B : EQN6B;
                    else
                        eqn = (swapped) ? EQN7B : EQN8B;
                    anchorval = x2_orig;
                    negslope = !negslope;
                }
                y1 = ymax;
            }

            if (swapped)
                negslope = !negslope;

            utmp <<= 1;         /* utmp = 2N or 2M */
            if (eqn & T_2NDX)
                utmp = (utmp * adx);
            else                /* (eqn & T_2MDY) */
                utmp = (utmp * ady);
            if (eqn & T_DXNOTY)
                if (eqn & T_SUBDXORY)
                    utmp -= adx;
                else
                    utmp += adx;
            else /* (eqn & T_DYNOTX) */ if (eqn & T_SUBDXORY)
                utmp -= ady;
            else
                utmp += ady;
            if (eqn & T_BIASSUBONE)
                utmp += bias - 1;
            else                /* (eqn & T_SUBBIAS) */
                utmp -= bias;
            if (eqn & T_DIV2DX)
                utmp /= (adx << 1);
            else                /* (eqn & T_DIV2DY) */
                utmp /= (ady << 1);
            if (eqn & T_ADDONE)
                utmp++;

            if (negslope)
                utmp = -utmp;

            if (eqn & T_2NDX)   /* We are calculating X steps */
                x1 = anchorval + utmp;
            else                /* else, Y steps */
                y1 = anchorval + utmp;

            oc1 = 0;
            MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
        }
    }

    *new_x1 = x1;
    *new_y1 = y1;
    *new_x2 = x2;
    *new_y2 = y2;

    *pt1_clipped = clip1;
    *pt2_clipped = clip2;

    return clipDone;
}
Commit	Line	Data
a09e091a JB	1	/***********************************************************
	2
	3	Copyright 1987, 1998 The Open Group
	4
	5	Permission to use, copy, modify, distribute, and sell this software and its
	6	documentation for any purpose is hereby granted without fee, provided that
	7	the above copyright notice appear in all copies and that both that
	8	copyright notice and this permission notice appear in supporting
	9	documentation.
	10
	11	The above copyright notice and this permission notice shall be included in
	12	all copies or substantial portions of the Software.
	13
	14	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
	15	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
	16	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
	17	OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
	18	AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
	19	CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
	20
	21	Except as contained in this notice, the name of The Open Group shall not be
	22	used in advertising or otherwise to promote the sale, use or other dealings
	23	in this Software without prior written authorization from The Open Group.
	24
	25	Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
	26
	27	All Rights Reserved
	28
	29	Permission to use, copy, modify, and distribute this software and its
	30	documentation for any purpose and without fee is hereby granted,
	31	provided that the above copyright notice appear in all copies and that
	32	both that copyright notice and this permission notice appear in
	33	supporting documentation, and that the name of Digital not be
	34	used in advertising or publicity pertaining to distribution of the
	35	software without specific, written prior permission.
	36
	37	DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
	38	ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
	39	DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
	40	ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
	41	WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
	42	ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
	43	SOFTWARE.
	44
	45	******************************************************************/
	46	#ifdef HAVE_DIX_CONFIG_H
	47	#include <dix-config.h>
	48	#endif
	49
	50	#include <X11/X.h>
	51
	52	#include "misc.h"
	53	#include "scrnintstr.h"
	54	#include "gcstruct.h"
	55	#include "windowstr.h"
	56	#include "pixmap.h"
	57	#include "mi.h"
	58	#include "miline.h"
	59
	60	/*
	61
	62	The bresenham error equation used in the mi/mfb/cfb line routines is:
	63
	64	e = error
65	dx = difference in raw X coordinates
66	dy = difference in raw Y coordinates
67	M = # of steps in X direction
68	N = # of steps in Y direction
69	B = 0 to prefer diagonal steps in a given octant,
70	1 to prefer axial steps in a given octant
71
72	For X major lines:
73	e = 2Mdy - 2Ndx - dx - B
74	-2dx <= e < 0
75
76	For Y major lines:
77	e = 2Ndx - 2Mdy - dy - B
78	-2dy <= e < 0
79
80	At the start of the line, we have taken 0 X steps and 0 Y steps,
81	so M = 0 and N = 0:
82
83	X major e = 2Mdy - 2Ndx - dx - B
84	= -dx - B
85
86	Y major e = 2Ndx - 2Mdy - dy - B
87	= -dy - B
88
89	At the end of the line, we have taken dx X steps and dy Y steps,
90	so M = dx and N = dy:
91
92	X major e = 2Mdy - 2Ndx - dx - B
93	= 2dxdy - 2dydx - dx - B
94	= -dx - B
95	Y major e = 2Ndx - 2Mdy - dy - B
96	= 2dydx - 2dxdy - dy - B
97	= -dy - B
98
99	Thus, the error term is the same at the start and end of the line.
100
101	Let us consider clipping an X coordinate. There are 4 cases which
102	represent the two independent cases of clipping the start vs. the
103	end of the line and an X major vs. a Y major line. In any of these
104	cases, we know the number of X steps (M) and we wish to find the
105	number of Y steps (N). Thus, we will solve our error term equation.
106	If we are clipping the start of the line, we will find the smallest
107	N that satisfies our error term inequality. If we are clipping the
108	end of the line, we will find the largest number of Y steps that
109	satisfies the inequality. In that case, since we are representing
110	the Y steps as (dy - N), we will actually want to solve for the
111	smallest N in that equation.
112	\f
113	Case 1: X major, starting X coordinate moved by M steps
114
115	-2dx <= 2Mdy - 2Ndx - dx - B < 0
116	2Ndx <= 2Mdy - dx - B + 2dx 2Ndx > 2Mdy - dx - B
117	2Ndx <= 2Mdy + dx - B N > (2Mdy - dx - B) / 2dx
118	N <= (2Mdy + dx - B) / 2dx
119
120	Since we are trying to find the smallest N that satisfies these
121	equations, we should use the > inequality to find the smallest:
122
123	N = floor((2Mdy - dx - B) / 2dx) + 1
124	= floor((2Mdy - dx - B + 2dx) / 2dx)
125	= floor((2Mdy + dx - B) / 2dx)
126
127	Case 1b: X major, ending X coordinate moved to M steps
128
129	Same derivations as Case 1, but we want the largest N that satisfies
130	the equations, so we use the <= inequality:
131
132	N = floor((2Mdy + dx - B) / 2dx)
133
134	Case 2: X major, ending X coordinate moved by M steps
135
136	-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
137	-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
138	-2dx <= 2Ndx - 2Mdy - dx - B < 0
139	2Ndx >= 2Mdy + dx + B - 2dx 2Ndx < 2Mdy + dx + B
140	2Ndx >= 2Mdy - dx + B N < (2Mdy + dx + B) / 2dx
141	N >= (2Mdy - dx + B) / 2dx
142
143	Since we are trying to find the highest number of Y steps that
144	satisfies these equations, we need to find the smallest N, so
145	we should use the >= inequality to find the smallest:
146
147	N = ceiling((2Mdy - dx + B) / 2dx)
148	= floor((2Mdy - dx + B + 2dx - 1) / 2dx)
149	= floor((2Mdy + dx + B - 1) / 2dx)
150
151	Case 2b: X major, starting X coordinate moved to M steps from end
152
153	Same derivations as Case 2, but we want the smallest number of Y
154	steps, so we want the highest N, so we use the < inequality:
155
156	N = ceiling((2Mdy + dx + B) / 2dx) - 1
157	= floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
158	= floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
159	= floor((2Mdy + dx + B - 1) / 2dx)
160	\f
161	Case 3: Y major, starting X coordinate moved by M steps
162
163	-2dy <= 2Ndx - 2Mdy - dy - B < 0
164	2Ndx >= 2Mdy + dy + B - 2dy 2Ndx < 2Mdy + dy + B
165	2Ndx >= 2Mdy - dy + B N < (2Mdy + dy + B) / 2dx
166	N >= (2Mdy - dy + B) / 2dx
167
168	Since we are trying to find the smallest N that satisfies these
169	equations, we should use the >= inequality to find the smallest:
170
171	N = ceiling((2Mdy - dy + B) / 2dx)
172	= floor((2Mdy - dy + B + 2dx - 1) / 2dx)
173	= floor((2Mdy - dy + B - 1) / 2dx) + 1
174
175	Case 3b: Y major, ending X coordinate moved to M steps
176
177	Same derivations as Case 3, but we want the largest N that satisfies
178	the equations, so we use the < inequality:
179
180	N = ceiling((2Mdy + dy + B) / 2dx) - 1
181	= floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
182	= floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
183	= floor((2Mdy + dy + B - 1) / 2dx)
184
185	Case 4: Y major, ending X coordinate moved by M steps
186
187	-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
188	-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
189	-2dy <= 2Mdy - 2Ndx - dy - B < 0
190	2Ndx <= 2Mdy - dy - B + 2dy 2Ndx > 2Mdy - dy - B
191	2Ndx <= 2Mdy + dy - B N > (2Mdy - dy - B) / 2dx
192	N <= (2Mdy + dy - B) / 2dx
193
194	Since we are trying to find the highest number of Y steps that
195	satisfies these equations, we need to find the smallest N, so
196	we should use the > inequality to find the smallest:
197
198	N = floor((2Mdy - dy - B) / 2dx) + 1
199
200	Case 4b: Y major, starting X coordinate moved to M steps from end
201
202	Same analysis as Case 4, but we want the smallest number of Y steps
203	which means the largest N, so we use the <= inequality:
204
205	N = floor((2Mdy + dy - B) / 2dx)
206	\f
207	Now let's try the Y coordinates, we have the same 4 cases.
208
209	Case 5: X major, starting Y coordinate moved by N steps
210
211	-2dx <= 2Mdy - 2Ndx - dx - B < 0
212	2Mdy >= 2Ndx + dx + B - 2dx 2Mdy < 2Ndx + dx + B
213	2Mdy >= 2Ndx - dx + B M < (2Ndx + dx + B) / 2dy
214	M >= (2Ndx - dx + B) / 2dy
215
216	Since we are trying to find the smallest M, we use the >= inequality:
217
218	M = ceiling((2Ndx - dx + B) / 2dy)
219	= floor((2Ndx - dx + B + 2dy - 1) / 2dy)
220	= floor((2Ndx - dx + B - 1) / 2dy) + 1
221
222	Case 5b: X major, ending Y coordinate moved to N steps
223
224	Same derivations as Case 5, but we want the largest M that satisfies
225	the equations, so we use the < inequality:
226
227	M = ceiling((2Ndx + dx + B) / 2dy) - 1
228	= floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
229	= floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
230	= floor((2Ndx + dx + B - 1) / 2dy)
231
232	Case 6: X major, ending Y coordinate moved by N steps
233
234	-2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
235	-2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
236	-2dx <= 2Ndx - 2Mdy - dx - B < 0
237	2Mdy <= 2Ndx - dx - B + 2dx 2Mdy > 2Ndx - dx - B
238	2Mdy <= 2Ndx + dx - B M > (2Ndx - dx - B) / 2dy
239	M <= (2Ndx + dx - B) / 2dy
240
241	Largest # of X steps means smallest M, so use the > inequality:
242
243	M = floor((2Ndx - dx - B) / 2dy) + 1
244
245	Case 6b: X major, starting Y coordinate moved to N steps from end
246
247	Same derivations as Case 6, but we want the smallest # of X steps
248	which means the largest M, so use the <= inequality:
249
250	M = floor((2Ndx + dx - B) / 2dy)
251	\f
252	Case 7: Y major, starting Y coordinate moved by N steps
253
254	-2dy <= 2Ndx - 2Mdy - dy - B < 0
255	2Mdy <= 2Ndx - dy - B + 2dy 2Mdy > 2Ndx - dy - B
256	2Mdy <= 2Ndx + dy - B M > (2Ndx - dy - B) / 2dy
257	M <= (2Ndx + dy - B) / 2dy
258
259	To find the smallest M, use the > inequality:
260
261	M = floor((2Ndx - dy - B) / 2dy) + 1
262	= floor((2Ndx - dy - B + 2dy) / 2dy)
263	= floor((2Ndx + dy - B) / 2dy)
264
265	Case 7b: Y major, ending Y coordinate moved to N steps
266
267	Same derivations as Case 7, but we want the largest M that satisfies
268	the equations, so use the <= inequality:
269
270	M = floor((2Ndx + dy - B) / 2dy)
271
272	Case 8: Y major, ending Y coordinate moved by N steps
273
274	-2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
275	-2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
276	-2dy <= 2Mdy - 2Ndx - dy - B < 0
277	2Mdy >= 2Ndx + dy + B - 2dy 2Mdy < 2Ndx + dy + B
278	2Mdy >= 2Ndx - dy + B M < (2Ndx + dy + B) / 2dy
279	M >= (2Ndx - dy + B) / 2dy
280
281	To find the highest X steps, find the smallest M, use the >= inequality:
282
283	M = ceiling((2Ndx - dy + B) / 2dy)
284	= floor((2Ndx - dy + B + 2dy - 1) / 2dy)
285	= floor((2Ndx + dy + B - 1) / 2dy)
286
287	Case 8b: Y major, starting Y coordinate moved to N steps from the end
288
289	Same derivations as Case 8, but we want to find the smallest # of X
290	steps which means the largest M, so we use the < inequality:
291
292	M = ceiling((2Ndx + dy + B) / 2dy) - 1
293	= floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
294	= floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
295	= floor((2Ndx + dy + B - 1) / 2dy)
296	\f
297	So, our equations are:
298
299	1: X major move x1 to x1+M floor((2Mdy + dx - B) / 2dx)
300	1b: X major move x2 to x1+M floor((2Mdy + dx - B) / 2dx)
301	2: X major move x2 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
302	2b: X major move x1 to x2-M floor((2Mdy + dx + B - 1) / 2dx)
303
304	3: Y major move x1 to x1+M floor((2Mdy - dy + B - 1) / 2dx) + 1
305	3b: Y major move x2 to x1+M floor((2Mdy + dy + B - 1) / 2dx)
306	4: Y major move x2 to x2-M floor((2Mdy - dy - B) / 2dx) + 1
307	4b: Y major move x1 to x2-M floor((2Mdy + dy - B) / 2dx)
308
309	5: X major move y1 to y1+N floor((2Ndx - dx + B - 1) / 2dy) + 1
310	5b: X major move y2 to y1+N floor((2Ndx + dx + B - 1) / 2dy)
311	6: X major move y2 to y2-N floor((2Ndx - dx - B) / 2dy) + 1
312	6b: X major move y1 to y2-N floor((2Ndx + dx - B) / 2dy)
313
314	7: Y major move y1 to y1+N floor((2Ndx + dy - B) / 2dy)
315	7b: Y major move y2 to y1+N floor((2Ndx + dy - B) / 2dy)
316	8: Y major move y2 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
317	8b: Y major move y1 to y2-N floor((2Ndx + dy + B - 1) / 2dy)
318
319	We have the following constraints on all of the above terms:
320
321	0 < M,N <= 2^15 2^15 can be imposed by miZeroClipLine
322	0 <= dx/dy <= 2^16 - 1
323	0 <= B <= 1
324
325	The floor in all of the above equations can be accomplished with a
326	simple C divide operation provided that both numerator and denominator
327	are positive.
328
329	Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
330	and moving a Y coordinate implies dy != 0, we know that the denominators
331	are all > 0.
332
333	For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
334	bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
335	or > 0 to prove that the numerators are positive (or zero).
336
337	For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
338	constraints, the first four equations all have numerators >= 0.
339
340	For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
341	So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy
342	or (2Mdy + dy) > 0. So all of their numerators are >= 0.
343
344	For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
345	>= dx > 0. Similarly (2Ndx + dx) >= 3dx > 0. So all numerators >= 0.
346
347	For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
348	are > 0.
349
350	To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This
351	is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
352	<= 2^16 * (2^16 - 1) + (2^16 - 1)
353	<= 2^32 - 2^16 + 2^16 - 1
354	<= 2^32 - 1
355	Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
356	the numerator is therefore (2^32 - 1), which does not overflow an unsigned
357	32 bit variable.
358
359	*/
360
361	/* Bit codes for the terms of the 16 clipping equations defined below. */
362
363	#define T_2NDX (1 << 0)
364	#define T_2MDY (0) /* implicit term */
365	#define T_DXNOTY (1 << 1)
366	#define T_DYNOTX (0) /* implicit term */
367	#define T_SUBDXORY (1 << 2)
368	#define T_ADDDX (T_DXNOTY) /* composite term */
369	#define T_SUBDX (T_DXNOTY \| T_SUBDXORY) /* composite term */
370	#define T_ADDDY (T_DYNOTX) /* composite term */
371	#define T_SUBDY (T_DYNOTX \| T_SUBDXORY) /* composite term */
372	#define T_BIASSUBONE (1 << 3)
373	#define T_SUBBIAS (0) /* implicit term */
374	#define T_DIV2DX (1 << 4)
375	#define T_DIV2DY (0) /* implicit term */
376	#define T_ADDONE (1 << 5)
377
378	/* Bit masks defining the 16 equations used in miZeroClipLine. */
379
380	#define EQN1 (T_2MDY \| T_ADDDX \| T_SUBBIAS \| T_DIV2DX)
381	#define EQN1B (T_2MDY \| T_ADDDX \| T_SUBBIAS \| T_DIV2DX)
382	#define EQN2 (T_2MDY \| T_ADDDX \| T_BIASSUBONE \| T_DIV2DX)
383	#define EQN2B (T_2MDY \| T_ADDDX \| T_BIASSUBONE \| T_DIV2DX)
384
385	#define EQN3 (T_2MDY \| T_SUBDY \| T_BIASSUBONE \| T_DIV2DX \| T_ADDONE)
386	#define EQN3B (T_2MDY \| T_ADDDY \| T_BIASSUBONE \| T_DIV2DX)
387	#define EQN4 (T_2MDY \| T_SUBDY \| T_SUBBIAS \| T_DIV2DX \| T_ADDONE)
388	#define EQN4B (T_2MDY \| T_ADDDY \| T_SUBBIAS \| T_DIV2DX)
389
390	#define EQN5 (T_2NDX \| T_SUBDX \| T_BIASSUBONE \| T_DIV2DY \| T_ADDONE)
391	#define EQN5B (T_2NDX \| T_ADDDX \| T_BIASSUBONE \| T_DIV2DY)
392	#define EQN6 (T_2NDX \| T_SUBDX \| T_SUBBIAS \| T_DIV2DY \| T_ADDONE)
393	#define EQN6B (T_2NDX \| T_ADDDX \| T_SUBBIAS \| T_DIV2DY)
394
395	#define EQN7 (T_2NDX \| T_ADDDY \| T_SUBBIAS \| T_DIV2DY)
396	#define EQN7B (T_2NDX \| T_ADDDY \| T_SUBBIAS \| T_DIV2DY)
397	#define EQN8 (T_2NDX \| T_ADDDY \| T_BIASSUBONE \| T_DIV2DY)
398	#define EQN8B (T_2NDX \| T_ADDDY \| T_BIASSUBONE \| T_DIV2DY)
399
400	/* miZeroClipLine
401	*
402	* returns: 1 for partially clipped line
403	* -1 for completely clipped line
404	*
405	*/
406	int
407	miZeroClipLine(int xmin, int ymin, int xmax, int ymax,
408	int new_x1, int new_y1, int new_x2, int new_y2,
409	unsigned int adx, unsigned int ady,
410	int pt1_clipped, int pt2_clipped,
411	int octant, unsigned int bias, int oc1, int oc2)
412	{
413	int swapped = 0;
414	int clipDone = 0;
415	CARD32 utmp = 0;
416	int clip1, clip2;
417	int x1, y1, x2, y2;
418	int x1_orig, y1_orig, x2_orig, y2_orig;
419	int xmajor;
420	int negslope = 0, anchorval = 0;
421	unsigned int eqn = 0;
422
423	x1 = x1_orig = *new_x1;
424	y1 = y1_orig = *new_y1;
425	x2 = x2_orig = *new_x2;
426	y2 = y2_orig = *new_y2;
427
428	clip1 = 0;
429	clip2 = 0;
430
431	xmajor = IsXMajorOctant(octant);
432	bias = ((bias >> octant) & 1);
433
434	while (1) {
435	if ((oc1 & oc2) != 0) { /* trivial reject */
436	clipDone = -1;
437	clip1 = oc1;
438	clip2 = oc2;
439	break;
440	}
441	else if ((oc1 \| oc2) == 0) { /* trivial accept */
442	clipDone = 1;
443	if (swapped) {
444	SWAPINT_PAIR(x1, y1, x2, y2);
445	SWAPINT(clip1, clip2);
446	}
447	break;
448	}
449	else { /* have to clip */
450
451	/* only clip one point at a time */
452	if (oc1 == 0) {
453	SWAPINT_PAIR(x1, y1, x2, y2);
454	SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
455	SWAPINT(oc1, oc2);
456	SWAPINT(clip1, clip2);
457	swapped = !swapped;
458	}
459
460	clip1 \|= oc1;
461	if (oc1 & OUT_LEFT) {
462	negslope = IsYDecreasingOctant(octant);
463	utmp = xmin - x1_orig;
464	if (utmp <= 32767) { /* clip based on near endpt */
465	if (xmajor)
466	eqn = (swapped) ? EQN2 : EQN1;
467	else
468	eqn = (swapped) ? EQN4 : EQN3;
469	anchorval = y1_orig;
470	}
471	else { /* clip based on far endpt */
472
473	utmp = x2_orig - xmin;
474	if (xmajor)
475	eqn = (swapped) ? EQN1B : EQN2B;
476	else
477	eqn = (swapped) ? EQN3B : EQN4B;
478	anchorval = y2_orig;
479	negslope = !negslope;
480	}
481	x1 = xmin;
482	}
483	else if (oc1 & OUT_ABOVE) {
484	negslope = IsXDecreasingOctant(octant);
485	utmp = ymin - y1_orig;
486	if (utmp <= 32767) { /* clip based on near endpt */
487	if (xmajor)
488	eqn = (swapped) ? EQN6 : EQN5;
489	else
490	eqn = (swapped) ? EQN8 : EQN7;
491	anchorval = x1_orig;
492	}
493	else { /* clip based on far endpt */
494
495	utmp = y2_orig - ymin;
496	if (xmajor)
497	eqn = (swapped) ? EQN5B : EQN6B;
498	else
499	eqn = (swapped) ? EQN7B : EQN8B;
500	anchorval = x2_orig;
501	negslope = !negslope;
502	}
503	y1 = ymin;
504	}
505	else if (oc1 & OUT_RIGHT) {
506	negslope = IsYDecreasingOctant(octant);
507	utmp = x1_orig - xmax;
508	if (utmp <= 32767) { /* clip based on near endpt */
509	if (xmajor)
510	eqn = (swapped) ? EQN2 : EQN1;
511	else
512	eqn = (swapped) ? EQN4 : EQN3;
513	anchorval = y1_orig;
514	}
515	else { /* clip based on far endpt */
516
517	/*
518	* Technically since the equations can handle
519	* utmp == 32768, this overflow code isn't
520	* needed since X11 protocol can't generate
521	* a line which goes more than 32768 pixels
522	* to the right of a clip rectangle.
523	*/
524	utmp = xmax - x2_orig;
525	if (xmajor)
526	eqn = (swapped) ? EQN1B : EQN2B;
527	else
528	eqn = (swapped) ? EQN3B : EQN4B;
529	anchorval = y2_orig;
530	negslope = !negslope;
531	}
532	x1 = xmax;
533	}
534	else if (oc1 & OUT_BELOW) {
535	negslope = IsXDecreasingOctant(octant);
536	utmp = y1_orig - ymax;
537	if (utmp <= 32767) { /* clip based on near endpt */
538	if (xmajor)
539	eqn = (swapped) ? EQN6 : EQN5;
540	else
541	eqn = (swapped) ? EQN8 : EQN7;
542	anchorval = x1_orig;
543	}
544	else { /* clip based on far endpt */
545
546	/*
547	* Technically since the equations can handle
548	* utmp == 32768, this overflow code isn't
549	* needed since X11 protocol can't generate
550	* a line which goes more than 32768 pixels
551	* below the bottom of a clip rectangle.
552	*/
553	utmp = ymax - y2_orig;
554	if (xmajor)
555	eqn = (swapped) ? EQN5B : EQN6B;
556	else
557	eqn = (swapped) ? EQN7B : EQN8B;
558	anchorval = x2_orig;
559	negslope = !negslope;
560	}
561	y1 = ymax;
562	}
563
564	if (swapped)
565	negslope = !negslope;
566
567	utmp <<= 1; /* utmp = 2N or 2M */
568	if (eqn & T_2NDX)
569	utmp = (utmp * adx);
570	else /* (eqn & T_2MDY) */
571	utmp = (utmp * ady);
572	if (eqn & T_DXNOTY)
573	if (eqn & T_SUBDXORY)
574	utmp -= adx;
575	else
576	utmp += adx;
577	else /* (eqn & T_DYNOTX) */ if (eqn & T_SUBDXORY)
578	utmp -= ady;
579	else
580	utmp += ady;
581	if (eqn & T_BIASSUBONE)
582	utmp += bias - 1;
583	else /* (eqn & T_SUBBIAS) */
584	utmp -= bias;
585	if (eqn & T_DIV2DX)
586	utmp /= (adx << 1);
587	else /* (eqn & T_DIV2DY) */
588	utmp /= (ady << 1);
589	if (eqn & T_ADDONE)
590	utmp++;
591
592	if (negslope)
593	utmp = -utmp;
594
595	if (eqn & T_2NDX) /* We are calculating X steps */
596	x1 = anchorval + utmp;
597	else /* else, Y steps */
598	y1 = anchorval + utmp;
599
600	oc1 = 0;
601	MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
602	}
603	}
604
605	*new_x1 = x1;
606	*new_y1 = y1;
607	*new_x2 = x2;
608	*new_y2 = y2;
609
610	*pt1_clipped = clip1;
611	*pt2_clipped = clip2;
612
613	return clipDone;
614	}