Imported Upstream version 1.15.1
[deb_xorg-server.git] / mi / mizerclip.c
CommitLineData
a09e091a
JB
1/***********************************************************
2
3Copyright 1987, 1998 The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
26
27 All Rights Reserved
28
29Permission to use, copy, modify, and distribute this software and its
30documentation for any purpose and without fee is hereby granted,
31provided that the above copyright notice appear in all copies and that
32both that copyright notice and this permission notice appear in
33supporting documentation, and that the name of Digital not be
34used in advertising or publicity pertaining to distribution of the
35software without specific, written prior permission.
36
37DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
38ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
39DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
40ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
41WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
42ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
43SOFTWARE.
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
62The 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
80At the start of the line, we have taken 0 X steps and 0 Y steps,
81so 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
89At the end of the line, we have taken dx X steps and dy Y steps,
90so 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
99Thus, the error term is the same at the start and end of the line.
100
101Let us consider clipping an X coordinate. There are 4 cases which
102represent the two independent cases of clipping the start vs. the
103end of the line and an X major vs. a Y major line. In any of these
104cases, we know the number of X steps (M) and we wish to find the
105number of Y steps (N). Thus, we will solve our error term equation.
106If we are clipping the start of the line, we will find the smallest
107N that satisfies our error term inequality. If we are clipping the
108end of the line, we will find the largest number of Y steps that
109satisfies the inequality. In that case, since we are representing
110the Y steps as (dy - N), we will actually want to solve for the
111smallest N in that equation.
112\f
113Case 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
120Since we are trying to find the smallest N that satisfies these
121equations, 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
127Case 1b: X major, ending X coordinate moved to M steps
128
129Same derivations as Case 1, but we want the largest N that satisfies
130the equations, so we use the <= inequality:
131
132 N = floor((2Mdy + dx - B) / 2dx)
133
134Case 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
143Since we are trying to find the highest number of Y steps that
144satisfies these equations, we need to find the smallest N, so
145we 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
151Case 2b: X major, starting X coordinate moved to M steps from end
152
153Same derivations as Case 2, but we want the smallest number of Y
154steps, 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
161Case 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
168Since we are trying to find the smallest N that satisfies these
169equations, 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
175Case 3b: Y major, ending X coordinate moved to M steps
176
177Same derivations as Case 3, but we want the largest N that satisfies
178the 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
185Case 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
194Since we are trying to find the highest number of Y steps that
195satisfies these equations, we need to find the smallest N, so
196we should use the > inequality to find the smallest:
197
198 N = floor((2Mdy - dy - B) / 2dx) + 1
199
200Case 4b: Y major, starting X coordinate moved to M steps from end
201
202Same analysis as Case 4, but we want the smallest number of Y steps
203which means the largest N, so we use the <= inequality:
204
205 N = floor((2Mdy + dy - B) / 2dx)
206\f
207Now let's try the Y coordinates, we have the same 4 cases.
208
209Case 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
216Since 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
222Case 5b: X major, ending Y coordinate moved to N steps
223
224Same derivations as Case 5, but we want the largest M that satisfies
225the 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
232Case 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
241Largest # of X steps means smallest M, so use the > inequality:
242
243 M = floor((2Ndx - dx - B) / 2dy) + 1
244
245Case 6b: X major, starting Y coordinate moved to N steps from end
246
247Same derivations as Case 6, but we want the smallest # of X steps
248which means the largest M, so use the <= inequality:
249
250 M = floor((2Ndx + dx - B) / 2dy)
251\f
252Case 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
259To 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
265Case 7b: Y major, ending Y coordinate moved to N steps
266
267Same derivations as Case 7, but we want the largest M that satisfies
268the equations, so use the <= inequality:
269
270 M = floor((2Ndx + dy - B) / 2dy)
271
272Case 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
281To 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
287Case 8b: Y major, starting Y coordinate moved to N steps from the end
288
289Same derivations as Case 8, but we want to find the smallest # of X
290steps 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
297So, 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
319We 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
325The floor in all of the above equations can be accomplished with a
326simple C divide operation provided that both numerator and denominator
327are positive.
328
329Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
330and moving a Y coordinate implies dy != 0, we know that the denominators
331are all > 0.
332
333For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
334bias. Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
335or > 0 to prove that the numerators are positive (or zero).
336
337For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
338constraints, the first four equations all have numerators >= 0.
339
340For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
341So (2Mdy - dy) > 0, since they are Y major lines. Also, (2Mdy + dy) >= 3dy
342or (2Mdy + dy) > 0. So all of their numerators are >= 0.
343
344For 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
347For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
348are > 0.
349
350To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy. This
351is 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
355Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
356the numerator is therefore (2^32 - 1), which does not overflow an unsigned
35732 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 */
406int
407miZeroClipLine(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}