Pileus Git - ~andy/gtk/blob - gdk/linux-fb/mizerclip.c

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