xorg-server-1.4/mi/mizerclip.c

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