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 
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 
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 
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 
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 
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
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)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 }
615