0 < M,N <= 2^15		 2^15 can be imposed by miZeroClipLine	0 <= dx/dy <= 2^16 - 1	0 <= B <= 1The floor in all of the above equations can be accomplished with asimple C divide operation provided that both numerator and denominatorare positive.Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0and moving a Y coordinate implies dy != 0, we know that the denominatorsare all > 0.For all lines, (-B) and (B-1) are both either 0 or -1, depending on thebias.  Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1or > 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 theconstraints, the first four equations all have numerators >= 0.For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dySo (2Mdy - dy) > 0, since they are Y major lines.  Also, (2Mdy + dy) >= 3dyor (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 numeratorsare > 0.To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy.  Thisis 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 - 1Since the (-B) and (B-1) terms are all 0 or -1, the maximum value ofthe numerator is therefore (2^32 - 1), which does not overflow an unsigned32 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 * */intmiZeroClipLine(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;    guint32 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;}