git.sesse.net Git - rdpsrv/blob - Xserver/programs/Xserver/mi/mizerline.c

   1 /***********************************************************
   2
   3 Copyright (c) 1987  X Consortium
   4
   5 Permission is hereby granted, free of charge, to any person obtaining a copy
   6 of this software and associated documentation files (the "Software"), to deal
   7 in the Software without restriction, including without limitation the rights
   8 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
   9 copies of the Software, and to permit persons to whom the Software is
  10 furnished to do so, subject to the following conditions:
  11
  12 The above copyright notice and this permission notice shall be included in
  13 all copies or substantial portions of the Software.
  14
  15 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  16 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  17 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
  18 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  19 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
  20 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  21
  22 Except as contained in this notice, the name of the X Consortium shall not be
  23 used in advertising or otherwise to promote the sale, use or other dealings
  24 in this Software without prior written authorization from the X Consortium.
  25
  26
  27 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
  28
  29                         All Rights Reserved
  30
  31 Permission to use, copy, modify, and distribute this software and its
  32 documentation for any purpose and without fee is hereby granted,
  33 provided that the above copyright notice appear in all copies and that
  34 both that copyright notice and this permission notice appear in
  35 supporting documentation, and that the name of Digital not be
  36 used in advertising or publicity pertaining to distribution of the
  37 software without specific, written prior permission.
  38
  39 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
  40 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
  41 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
  42 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  43 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
  44 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
  45 SOFTWARE.
  46
  47 ******************************************************************/
  48 /* $XConsortium: mizerline.c,v 5.9 94/08/02 15:01:29 dpw Exp $ */
  49 #include "X.h"
  50
  51 #include "misc.h"
  52 #include "scrnintstr.h"
  53 #include "gcstruct.h"
  54 #include "windowstr.h"
  55 #include "pixmap.h"
  56 #include "mi.h"
  57 #include "miline.h"
  58
  59 /*
  60
  61 The bresenham error equation used in the mi/mfb/cfb line routines is:
  62
  63         e = error
  64         dx = difference in raw X coordinates
  65         dy = difference in raw Y coordinates
  66         M = # of steps in X direction
  67         N = # of steps in Y direction
  68         B = 0 to prefer diagonal steps in a given octant,
  69             1 to prefer axial steps in a given octant
  70
  71         For X major lines:
  72                 e = 2Mdy - 2Ndx - dx - B
  73                 -2dx <= e < 0
  74
  75         For Y major lines:
  76                 e = 2Ndx - 2Mdy - dy - B
  77                 -2dy <= e < 0
  78
  79 At the start of the line, we have taken 0 X steps and 0 Y steps,
  80 so M = 0 and N = 0:
  81
  82         X major e = 2Mdy - 2Ndx - dx - B
  83                   = -dx - B
  84
  85         Y major e = 2Ndx - 2Mdy - dy - B
  86                   = -dy - B
  87
  88 At the end of the line, we have taken dx X steps and dy Y steps,
  89 so M = dx and N = dy:
  90
  91         X major e = 2Mdy - 2Ndx - dx - B
  92                   = 2dxdy - 2dydx - dx - B
  93                   = -dx - B
  94         Y major e = 2Ndx - 2Mdy - dy - B
  95                   = 2dydx - 2dxdy - dy - B
  96                   = -dy - B
  97
  98 Thus, the error term is the same at the start and end of the line.
  99
 100 Let us consider clipping an X coordinate.  There are 4 cases which
 101 represent the two independent cases of clipping the start vs. the
 102 end of the line and an X major vs. a Y major line.  In any of these
 103 cases, we know the number of X steps (M) and we wish to find the
 104 number of Y steps (N).  Thus, we will solve our error term equation.
 105 If we are clipping the start of the line, we will find the smallest
 106 N that satisfies our error term inequality.  If we are clipping the
 107 end of the line, we will find the largest number of Y steps that
 108 satisfies the inequality.  In that case, since we are representing
 109 the Y steps as (dy - N), we will actually want to solve for the
 110 smallest N in that equation.
 111 \f
 112 Case 1:  X major, starting X coordinate moved by M steps
 113
 114                 -2dx <= 2Mdy - 2Ndx - dx - B < 0
 115         2Ndx <= 2Mdy - dx - B + 2dx     2Ndx > 2Mdy - dx - B
 116         2Ndx <= 2Mdy + dx - B           N > (2Mdy - dx - B) / 2dx
 117         N <= (2Mdy + dx - B) / 2dx
 118
 119 Since we are trying to find the smallest N that satisfies these
 120 equations, we should use the > inequality to find the smallest:
 121
 122         N = floor((2Mdy - dx - B) / 2dx) + 1
 123           = floor((2Mdy - dx - B + 2dx) / 2dx)
 124           = floor((2Mdy + dx - B) / 2dx)
 125
 126 Case 1b: X major, ending X coordinate moved to M steps
 127
 128 Same derivations as Case 1, but we want the largest N that satisfies
 129 the equations, so we use the <= inequality:
 130
 131         N = floor((2Mdy + dx - B) / 2dx)
 132
 133 Case 2: X major, ending X coordinate moved by M steps
 134
 135                 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
 136                 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
 137                 -2dx <= 2Ndx - 2Mdy - dx - B < 0
 138         2Ndx >= 2Mdy + dx + B - 2dx     2Ndx < 2Mdy + dx + B
 139         2Ndx >= 2Mdy - dx + B           N < (2Mdy + dx + B) / 2dx
 140         N >= (2Mdy - dx + B) / 2dx
 141
 142 Since we are trying to find the highest number of Y steps that
 143 satisfies these equations, we need to find the smallest N, so
 144 we should use the >= inequality to find the smallest:
 145
 146         N = ceiling((2Mdy - dx + B) / 2dx)
 147           = floor((2Mdy - dx + B + 2dx - 1) / 2dx)
 148           = floor((2Mdy + dx + B - 1) / 2dx)
 149
 150 Case 2b: X major, starting X coordinate moved to M steps from end
 151
 152 Same derivations as Case 2, but we want the smallest number of Y
 153 steps, so we want the highest N, so we use the < inequality:
 154
 155         N = ceiling((2Mdy + dx + B) / 2dx) - 1
 156           = floor((2Mdy + dx + B + 2dx - 1) / 2dx) - 1
 157           = floor((2Mdy + dx + B + 2dx - 1 - 2dx) / 2dx)
 158           = floor((2Mdy + dx + B - 1) / 2dx)
 159 \f
 160 Case 3: Y major, starting X coordinate moved by M steps
 161
 162                 -2dy <= 2Ndx - 2Mdy - dy - B < 0
 163         2Ndx >= 2Mdy + dy + B - 2dy     2Ndx < 2Mdy + dy + B
 164         2Ndx >= 2Mdy - dy + B           N < (2Mdy + dy + B) / 2dx
 165         N >= (2Mdy - dy + B) / 2dx
 166
 167 Since we are trying to find the smallest N that satisfies these
 168 equations, we should use the >= inequality to find the smallest:
 169
 170         N = ceiling((2Mdy - dy + B) / 2dx)
 171           = floor((2Mdy - dy + B + 2dx - 1) / 2dx)
 172           = floor((2Mdy - dy + B - 1) / 2dx) + 1
 173
 174 Case 3b: Y major, ending X coordinate moved to M steps
 175
 176 Same derivations as Case 3, but we want the largest N that satisfies
 177 the equations, so we use the < inequality:
 178
 179         N = ceiling((2Mdy + dy + B) / 2dx) - 1
 180           = floor((2Mdy + dy + B + 2dx - 1) / 2dx) - 1
 181           = floor((2Mdy + dy + B + 2dx - 1 - 2dx) / 2dx)
 182           = floor((2Mdy + dy + B - 1) / 2dx)
 183
 184 Case 4: Y major, ending X coordinate moved by M steps
 185
 186                 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
 187                 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
 188                 -2dy <= 2Mdy - 2Ndx - dy - B < 0
 189         2Ndx <= 2Mdy - dy - B + 2dy     2Ndx > 2Mdy - dy - B
 190         2Ndx <= 2Mdy + dy - B           N > (2Mdy - dy - B) / 2dx
 191         N <= (2Mdy + dy - B) / 2dx
 192
 193 Since we are trying to find the highest number of Y steps that
 194 satisfies these equations, we need to find the smallest N, so
 195 we should use the > inequality to find the smallest:
 196
 197         N = floor((2Mdy - dy - B) / 2dx) + 1
 198
 199 Case 4b: Y major, starting X coordinate moved to M steps from end
 200
 201 Same analysis as Case 4, but we want the smallest number of Y steps
 202 which means the largest N, so we use the <= inequality:
 203
 204         N = floor((2Mdy + dy - B) / 2dx)
 205 \f
 206 Now let's try the Y coordinates, we have the same 4 cases.
 207
 208 Case 5: X major, starting Y coordinate moved by N steps
 209
 210                 -2dx <= 2Mdy - 2Ndx - dx - B < 0
 211         2Mdy >= 2Ndx + dx + B - 2dx     2Mdy < 2Ndx + dx + B
 212         2Mdy >= 2Ndx - dx + B           M < (2Ndx + dx + B) / 2dy
 213         M >= (2Ndx - dx + B) / 2dy
 214
 215 Since we are trying to find the smallest M, we use the >= inequality:
 216
 217         M = ceiling((2Ndx - dx + B) / 2dy)
 218           = floor((2Ndx - dx + B + 2dy - 1) / 2dy)
 219           = floor((2Ndx - dx + B - 1) / 2dy) + 1
 220
 221 Case 5b: X major, ending Y coordinate moved to N steps
 222
 223 Same derivations as Case 5, but we want the largest M that satisfies
 224 the equations, so we use the < inequality:
 225
 226         M = ceiling((2Ndx + dx + B) / 2dy) - 1
 227           = floor((2Ndx + dx + B + 2dy - 1) / 2dy) - 1
 228           = floor((2Ndx + dx + B + 2dy - 1 - 2dy) / 2dy)
 229           = floor((2Ndx + dx + B - 1) / 2dy)
 230
 231 Case 6: X major, ending Y coordinate moved by N steps
 232
 233                 -2dx <= 2(dx - M)dy - 2(dy - N)dx - dx - B < 0
 234                 -2dx <= 2dxdy - 2Mdy - 2dxdy + 2Ndx - dx - B < 0
 235                 -2dx <= 2Ndx - 2Mdy - dx - B < 0
 236         2Mdy <= 2Ndx - dx - B + 2dx     2Mdy > 2Ndx - dx - B
 237         2Mdy <= 2Ndx + dx - B           M > (2Ndx - dx - B) / 2dy
 238         M <= (2Ndx + dx - B) / 2dy
 239
 240 Largest # of X steps means smallest M, so use the > inequality:
 241
 242         M = floor((2Ndx - dx - B) / 2dy) + 1
 243
 244 Case 6b: X major, starting Y coordinate moved to N steps from end
 245
 246 Same derivations as Case 6, but we want the smallest # of X steps
 247 which means the largest M, so use the <= inequality:
 248
 249         M = floor((2Ndx + dx - B) / 2dy)
 250 \f
 251 Case 7: Y major, starting Y coordinate moved by N steps
 252
 253                 -2dy <= 2Ndx - 2Mdy - dy - B < 0
 254         2Mdy <= 2Ndx - dy - B + 2dy     2Mdy > 2Ndx - dy - B
 255         2Mdy <= 2Ndx + dy - B           M > (2Ndx - dy - B) / 2dy
 256         M <= (2Ndx + dy - B) / 2dy
 257
 258 To find the smallest M, use the > inequality:
 259
 260         M = floor((2Ndx - dy - B) / 2dy) + 1
 261           = floor((2Ndx - dy - B + 2dy) / 2dy)
 262           = floor((2Ndx + dy - B) / 2dy)
 263
 264 Case 7b: Y major, ending Y coordinate moved to N steps
 265
 266 Same derivations as Case 7, but we want the largest M that satisfies
 267 the equations, so use the <= inequality:
 268
 269         M = floor((2Ndx + dy - B) / 2dy)
 270
 271 Case 8: Y major, ending Y coordinate moved by N steps
 272
 273                 -2dy <= 2(dy - N)dx - 2(dx - M)dy - dy - B < 0
 274                 -2dy <= 2dxdy - 2Ndx - 2dxdy + 2Mdy - dy - B < 0
 275                 -2dy <= 2Mdy - 2Ndx - dy - B < 0
 276         2Mdy >= 2Ndx + dy + B - 2dy     2Mdy < 2Ndx + dy + B
 277         2Mdy >= 2Ndx - dy + B           M < (2Ndx + dy + B) / 2dy
 278         M >= (2Ndx - dy + B) / 2dy
 279
 280 To find the highest X steps, find the smallest M, use the >= inequality:
 281
 282         M = ceiling((2Ndx - dy + B) / 2dy)
 283           = floor((2Ndx - dy + B + 2dy - 1) / 2dy)
 284           = floor((2Ndx + dy + B - 1) / 2dy)
 285
 286 Case 8b: Y major, starting Y coordinate moved to N steps from the end
 287
 288 Same derivations as Case 8, but we want to find the smallest # of X
 289 steps which means the largest M, so we use the < inequality:
 290
 291         M = ceiling((2Ndx + dy + B) / 2dy) - 1
 292           = floor((2Ndx + dy + B + 2dy - 1) / 2dy) - 1
 293           = floor((2Ndx + dy + B + 2dy - 1 - 2dy) / 2dy)
 294           = floor((2Ndx + dy + B - 1) / 2dy)
 295 \f
 296 So, our equations are:
 297
 298         1:  X major move x1 to x1+M     floor((2Mdy + dx - B) / 2dx)
 299         1b: X major move x2 to x1+M     floor((2Mdy + dx - B) / 2dx)
 300         2:  X major move x2 to x2-M     floor((2Mdy + dx + B - 1) / 2dx)
 301         2b: X major move x1 to x2-M     floor((2Mdy + dx + B - 1) / 2dx)
 302
 303         3:  Y major move x1 to x1+M     floor((2Mdy - dy + B - 1) / 2dx) + 1
 304         3b: Y major move x2 to x1+M     floor((2Mdy + dy + B - 1) / 2dx)
 305         4:  Y major move x2 to x2-M     floor((2Mdy - dy - B) / 2dx) + 1
 306         4b: Y major move x1 to x2-M     floor((2Mdy + dy - B) / 2dx)
 307
 308         5:  X major move y1 to y1+N     floor((2Ndx - dx + B - 1) / 2dy) + 1
 309         5b: X major move y2 to y1+N     floor((2Ndx + dx + B - 1) / 2dy)
 310         6:  X major move y2 to y2-N     floor((2Ndx - dx - B) / 2dy) + 1
 311         6b: X major move y1 to y2-N     floor((2Ndx + dx - B) / 2dy)
 312
 313         7:  Y major move y1 to y1+N     floor((2Ndx + dy - B) / 2dy)
 314         7b: Y major move y2 to y1+N     floor((2Ndx + dy - B) / 2dy)
 315         8:  Y major move y2 to y2-N     floor((2Ndx + dy + B - 1) / 2dy)
 316         8b: Y major move y1 to y2-N     floor((2Ndx + dy + B - 1) / 2dy)
 317
 318 We have the following constraints on all of the above terms:
 319
 320         0 < M,N <= 2^15          2^15 can be imposed by miZeroClipLine
 321         0 <= dx/dy <= 2^16 - 1
 322         0 <= B <= 1
 323
 324 The floor in all of the above equations can be accomplished with a
 325 simple C divide operation provided that both numerator and denominator
 326 are positive.
 327
 328 Since dx,dy >= 0 and since moving an X coordinate implies that dx != 0
 329 and moving a Y coordinate implies dy != 0, we know that the denominators
 330 are all > 0.
 331
 332 For all lines, (-B) and (B-1) are both either 0 or -1, depending on the
 333 bias.  Thus, we have to show that the 2MNdxy +/- dxy terms are all >= 1
 334 or > 0 to prove that the numerators are positive (or zero).
 335
 336 For X Major lines we know that dx > 0 and since 2Mdy is >= 0 due to the
 337 constraints, the first four equations all have numerators >= 0.
 338
 339 For the second four equations, M > 0, so 2Mdy >= 2dy so (2Mdy - dy) >= dy
 340 So (2Mdy - dy) > 0, since they are Y major lines.  Also, (2Mdy + dy) >= 3dy
 341 or (2Mdy + dy) > 0.  So all of their numerators are >= 0.
 342
 343 For the third set of four equations, N > 0, so 2Ndx >= 2dx so (2Ndx - dx)
 344 >= dx > 0.  Similarly (2Ndx + dx) >= 3dx > 0.  So all numerators >= 0.
 345
 346 For the fourth set of equations, dy > 0 and 2Ndx >= 0, so all numerators
 347 are > 0.
 348
 349 To consider overflow, consider the case of 2 * M,N * dx,dy + dx,dy.  This
 350 is bounded <= 2 * 2^15 * (2^16 - 1) + (2^16 - 1)
 351            <= 2^16 * (2^16 - 1) + (2^16 - 1)
 352            <= 2^32 - 2^16 + 2^16 - 1
 353            <= 2^32 - 1
 354 Since the (-B) and (B-1) terms are all 0 or -1, the maximum value of
 355 the numerator is therefore (2^32 - 1), which does not overflow an unsigned
 356 32 bit variable.
 357
 358 */
 359
 360 #define MIOUTCODES(outcode, x, y, xmin, ymin, xmax, ymax) \
 361 {\
 362      if (x < xmin) outcode |= OUT_LEFT;\
 363      if (x > xmax) outcode |= OUT_RIGHT;\
 364      if (y < ymin) outcode |= OUT_ABOVE;\
 365      if (y > ymax) outcode |= OUT_BELOW;\
 366 }
 367
 368 /* Bit codes for the terms of the 16 clipping equations defined below. */
 369
 370 #define T_2NDX          (1 << 0)
 371 #define T_2MDY          (0)                             /* implicit term */
 372 #define T_DXNOTY        (1 << 1)
 373 #define T_DYNOTX        (0)                             /* implicit term */
 374 #define T_SUBDXORY      (1 << 2)
 375 #define T_ADDDX         (T_DXNOTY)                      /* composite term */
 376 #define T_SUBDX         (T_DXNOTY | T_SUBDXORY)         /* composite term */
 377 #define T_ADDDY         (T_DYNOTX)                      /* composite term */
 378 #define T_SUBDY         (T_DYNOTX | T_SUBDXORY)         /* composite term */
 379 #define T_BIASSUBONE    (1 << 3)
 380 #define T_SUBBIAS       (0)                             /* implicit term */
 381 #define T_DIV2DX        (1 << 4)
 382 #define T_DIV2DY        (0)                             /* implicit term */
 383 #define T_ADDONE        (1 << 5)
 384
 385 /* Bit masks defining the 16 equations used in miZeroClipLine. */
 386
 387 #define EQN1    (T_2MDY | T_ADDDX | T_SUBBIAS    | T_DIV2DX)
 388 #define EQN1B   (T_2MDY | T_ADDDX | T_SUBBIAS    | T_DIV2DX)
 389 #define EQN2    (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
 390 #define EQN2B   (T_2MDY | T_ADDDX | T_BIASSUBONE | T_DIV2DX)
 391
 392 #define EQN3    (T_2MDY | T_SUBDY | T_BIASSUBONE | T_DIV2DX | T_ADDONE)
 393 #define EQN3B   (T_2MDY | T_ADDDY | T_BIASSUBONE | T_DIV2DX)
 394 #define EQN4    (T_2MDY | T_SUBDY | T_SUBBIAS    | T_DIV2DX | T_ADDONE)
 395 #define EQN4B   (T_2MDY | T_ADDDY | T_SUBBIAS    | T_DIV2DX)
 396
 397 #define EQN5    (T_2NDX | T_SUBDX | T_BIASSUBONE | T_DIV2DY | T_ADDONE)
 398 #define EQN5B   (T_2NDX | T_ADDDX | T_BIASSUBONE | T_DIV2DY)
 399 #define EQN6    (T_2NDX | T_SUBDX | T_SUBBIAS    | T_DIV2DY | T_ADDONE)
 400 #define EQN6B   (T_2NDX | T_ADDDX | T_SUBBIAS    | T_DIV2DY)
 401
 402 #define EQN7    (T_2NDX | T_ADDDY | T_SUBBIAS    | T_DIV2DY)
 403 #define EQN7B   (T_2NDX | T_ADDDY | T_SUBBIAS    | T_DIV2DY)
 404 #define EQN8    (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
 405 #define EQN8B   (T_2NDX | T_ADDDY | T_BIASSUBONE | T_DIV2DY)
 406
 407 /* miZeroClipLine
 408  *
 409  * returns:  1 for partially clipped line
 410  *          -1 for completely clipped line
 411  *
 412  */
 413 int
 414 miZeroClipLine(xmin, ymin, xmax, ymax,
 415                new_x1, new_y1, new_x2, new_y2,
 416                adx, ady,
 417                pt1_clipped, pt2_clipped, octant, bias, oc1, oc2)
 418     int xmin, ymin, xmax, ymax;
 419     int *new_x1, *new_y1, *new_x2, *new_y2;
 420     int *pt1_clipped, *pt2_clipped;
 421     unsigned int adx, ady;
 422     int octant;
 423     unsigned int bias;
 424     int oc1, oc2;
 425 {
 426     int swapped = 0;
 427     int clipDone = 0;
 428     CARD32 utmp;
 429     int clip1, clip2;
 430     int x1, y1, x2, y2;
 431     int x1_orig, y1_orig, x2_orig, y2_orig;
 432     int xmajor;
 433     int negslope, anchorval;
 434     unsigned int eqn;
 435
 436     x1 = x1_orig = *new_x1;
 437     y1 = y1_orig = *new_y1;
 438     x2 = x2_orig = *new_x2;
 439     y2 = y2_orig = *new_y2;
 440
 441     clip1 = 0;
 442     clip2 = 0;
 443
 444     xmajor = IsXMajorOctant(octant);
 445     bias = ((bias >> octant) & 1);
 446
 447     while (1)
 448     {
 449         if ((oc1 & oc2) != 0)                   /* trivial reject */
 450         {
 451             clipDone = -1;
 452             clip1 = oc1;
 453             clip2 = oc2;
 454             break;
 455         }
 456         else if ((oc1 | oc2) == 0)              /* trivial accept */
 457         {
 458             clipDone = 1;
 459             if (swapped)
 460             {
 461                 SWAPINT_PAIR(x1, y1, x2, y2);
 462                 SWAPINT(clip1, clip2);
 463             }
 464             break;
 465         }
 466         else                    /* have to clip */
 467         {
 468             /* only clip one point at a time */
 469             if (oc1 == 0)
 470             {
 471                 SWAPINT_PAIR(x1, y1, x2, y2);
 472                 SWAPINT_PAIR(x1_orig, y1_orig, x2_orig, y2_orig);
 473                 SWAPINT(oc1, oc2);
 474                 SWAPINT(clip1, clip2);
 475                 swapped = !swapped;
 476             }
 477
 478             clip1 |= oc1;
 479             if (oc1 & OUT_LEFT)
 480             {
 481                 negslope = IsYDecreasingOctant(octant);
 482                 utmp = xmin - x1_orig;
 483                 if (utmp <= 32767)              /* clip based on near endpt */
 484                 {
 485                     if (xmajor)
 486                         eqn = (swapped) ? EQN2 : EQN1;
 487                     else
 488                         eqn = (swapped) ? EQN4 : EQN3;
 489                     anchorval = y1_orig;
 490                 }
 491                 else                            /* clip based on far endpt */
 492                 {
 493                     utmp = x2_orig - xmin;
 494                     if (xmajor)
 495                         eqn = (swapped) ? EQN1B : EQN2B;
 496                     else
 497                         eqn = (swapped) ? EQN3B : EQN4B;
 498                     anchorval = y2_orig;
 499                     negslope = !negslope;
 500                 }
 501                 x1 = xmin;
 502             }
 503             else if (oc1 & OUT_ABOVE)
 504             {
 505                 negslope = IsXDecreasingOctant(octant);
 506                 utmp = ymin - y1_orig;
 507                 if (utmp <= 32767)              /* clip based on near endpt */
 508                 {
 509                     if (xmajor)
 510                         eqn = (swapped) ? EQN6 : EQN5;
 511                     else
 512                         eqn = (swapped) ? EQN8 : EQN7;
 513                     anchorval = x1_orig;
 514                 }
 515                 else                            /* clip based on far endpt */
 516                 {
 517                     utmp = y2_orig - ymin;
 518                     if (xmajor)
 519                         eqn = (swapped) ? EQN5B : EQN6B;
 520                     else
 521                         eqn = (swapped) ? EQN7B : EQN8B;
 522                     anchorval = x2_orig;
 523                     negslope = !negslope;
 524                 }
 525                 y1 = ymin;
 526             }
 527             else if (oc1 & OUT_RIGHT)
 528             {
 529                 negslope = IsYDecreasingOctant(octant);
 530                 utmp = x1_orig - xmax;
 531                 if (utmp <= 32767)              /* clip based on near endpt */
 532                 {
 533                     if (xmajor)
 534                         eqn = (swapped) ? EQN2 : EQN1;
 535                     else
 536                         eqn = (swapped) ? EQN4 : EQN3;
 537                     anchorval = y1_orig;
 538                 }
 539                 else                            /* clip based on far endpt */
 540                 {
 541                     /*
 542                      * Technically since the equations can handle
 543                      * utmp == 32768, this overflow code isn't
 544                      * needed since X11 protocol can't generate
 545                      * a line which goes more than 32768 pixels
 546                      * to the right of a clip rectangle.
 547                      */
 548                     utmp = xmax - x2_orig;
 549                     if (xmajor)
 550                         eqn = (swapped) ? EQN1B : EQN2B;
 551                     else
 552                         eqn = (swapped) ? EQN3B : EQN4B;
 553                     anchorval = y2_orig;
 554                     negslope = !negslope;
 555                 }
 556                 x1 = xmax;
 557             }
 558             else if (oc1 & OUT_BELOW)
 559             {
 560                 negslope = IsXDecreasingOctant(octant);
 561                 utmp = y1_orig - ymax;
 562                 if (utmp <= 32767)              /* clip based on near endpt */
 563                 {
 564                     if (xmajor)
 565                         eqn = (swapped) ? EQN6 : EQN5;
 566                     else
 567                         eqn = (swapped) ? EQN8 : EQN7;
 568                     anchorval = x1_orig;
 569                 }
 570                 else                            /* clip based on far endpt */
 571                 {
 572                     /*
 573                      * Technically since the equations can handle
 574                      * utmp == 32768, this overflow code isn't
 575                      * needed since X11 protocol can't generate
 576                      * a line which goes more than 32768 pixels
 577                      * below the bottom of a clip rectangle.
 578                      */
 579                     utmp = ymax - y2_orig;
 580                     if (xmajor)
 581                         eqn = (swapped) ? EQN5B : EQN6B;
 582                     else
 583                         eqn = (swapped) ? EQN7B : EQN8B;
 584                     anchorval = x2_orig;
 585                     negslope = !negslope;
 586                 }
 587                 y1 = ymax;
 588             }
 589
 590             if (swapped)
 591                 negslope = !negslope;
 592
 593             utmp <<= 1;                 /* utmp = 2N or 2M */
 594             if (eqn & T_2NDX)
 595                 utmp = (utmp * adx);
 596             else /* (eqn & T_2MDY) */
 597                 utmp = (utmp * ady);
 598             if (eqn & T_DXNOTY)
 599                 if (eqn & T_SUBDXORY)
 600                     utmp -= adx;
 601                 else
 602                     utmp += adx;
 603             else /* (eqn & T_DYNOTX) */
 604                 if (eqn & T_SUBDXORY)
 605                     utmp -= ady;
 606                 else
 607                     utmp += ady;
 608             if (eqn & T_BIASSUBONE)
 609                 utmp += bias - 1;
 610             else /* (eqn & T_SUBBIAS) */
 611                 utmp -= bias;
 612             if (eqn & T_DIV2DX)
 613                 utmp /= (adx << 1);
 614             else /* (eqn & T_DIV2DY) */
 615                 utmp /= (ady << 1);
 616             if (eqn & T_ADDONE)
 617                 utmp++;
 618
 619             if (negslope)
 620                 utmp = -utmp;
 621
 622             if (eqn & T_2NDX)   /* We are calculating X steps */
 623                 x1 = anchorval + utmp;
 624             else                /* else, Y steps */
 625                 y1 = anchorval + utmp;
 626
 627             oc1 = 0;
 628             MIOUTCODES(oc1, x1, y1, xmin, ymin, xmax, ymax);
 629         }
 630     }
 631
 632     *new_x1 = x1;
 633     *new_y1 = y1;
 634     *new_x2 = x2;
 635     *new_y2 = y2;
 636
 637     *pt1_clipped = clip1;
 638     *pt2_clipped = clip2;
 639
 640     return clipDone;
 641 }
 642
 643
 644 /* Draw lineSolid, fillStyle-independent zero width lines.
 645  *
 646  * Must keep X and Y coordinates in "ints" at least until after they're
 647  * translated and clipped to accomodate CoordModePrevious lines with very
 648  * large coordinates.
 649  *
 650  * Draws the same pixels regardless of sign(dx) or sign(dy).
 651  *
 652  * Ken Whaley
 653  *
 654  */
 655
 656 /* largest positive value that can fit into a component of a point.
 657  * Assumes that the point structure is {type x, y;} where type is
 658  * a signed type.
 659  */
 660 #define MAX_COORDINATE ((1 << (((sizeof(DDXPointRec) >> 1) << 3) - 1)) - 1)
 661
 662 #define MI_OUTPUT_POINT(xx, yy)\
 663 {\
 664     if ( !new_span && yy == current_y)\
 665     {\
 666         if (xx < spans->x)\
 667             spans->x = xx;\
 668         ++*widths;\
 669     }\
 670     else\
 671     {\
 672         ++Nspans;\
 673         ++spans;\
 674         ++widths;\
 675         spans->x = xx;\
 676         spans->y = yy;\
 677         *widths = 1;\
 678         current_y = yy;\
 679         new_span = FALSE;\
 680     }\
 681 }
 682
 683 void
 684 miZeroLine(pDraw, pGC, mode, npt, pptInit)
 685     DrawablePtr pDraw;
 686     GCPtr       pGC;
 687     int         mode;           /* Origin or Previous */
 688     int         npt;            /* number of points */
 689     DDXPointPtr pptInit;
 690 {
 691     int Nspans, current_y;
 692     DDXPointPtr ppt;
 693     DDXPointPtr pspanInit, spans;
 694     int *pwidthInit, *widths, list_len;
 695     int xleft, ytop, xright, ybottom;
 696     int new_x1, new_y1, new_x2, new_y2;
 697     int x, y, x1, y1, x2, y2, xstart, ystart;
 698     int oc1, oc2;
 699     int result;
 700     int pt1_clipped, pt2_clipped = 0;
 701     Bool new_span;
 702     int signdx, signdy;
 703     int clipdx, clipdy;
 704     int width, height;
 705     int adx, ady;
 706     int octant;
 707     unsigned int bias = miGetZeroLineBias(pDraw->pScreen);
 708     int e, e1, e2, e3;  /* Bresenham error terms */
 709     int length;         /* length of lines == # of pixels on major axis */
 710
 711     xleft   = pDraw->x;
 712     ytop    = pDraw->y;
 713     xright  = pDraw->x + pDraw->width - 1;
 714     ybottom = pDraw->y + pDraw->height - 1;
 715
 716     if (!pGC->miTranslate)
 717     {
 718         /* do everything in drawable-relative coordinates */
 719         xleft    = 0;
 720         ytop     = 0;
 721         xright  -= pDraw->x;
 722         ybottom -= pDraw->y;
 723     }
 724
 725     /* it doesn't matter whether we're in drawable or screen coordinates,
 726      * FillSpans simply cannot take starting coordinates outside of the
 727      * range of a DDXPointRec component.
 728      */
 729     if (xright > MAX_COORDINATE)
 730         xright = MAX_COORDINATE;
 731     if (ybottom > MAX_COORDINATE)
 732         ybottom = MAX_COORDINATE;
 733
 734     /* since we're clipping to the drawable's boundaries & coordinate
 735      * space boundaries, we're guaranteed that the larger of width/height
 736      * is the longest span we'll need to output
 737      */
 738     width = xright - xleft + 1;
 739     height = ybottom - ytop + 1;
 740     list_len = (height >= width) ? height : width;
 741     pspanInit = (DDXPointPtr)ALLOCATE_LOCAL(list_len * sizeof(DDXPointRec));
 742     pwidthInit = (int *)ALLOCATE_LOCAL(list_len * sizeof(int));
 743     if (!pspanInit || !pwidthInit)
 744         return;
 745
 746     Nspans = 0;
 747     new_span = TRUE;
 748     spans  = pspanInit - 1;
 749     widths = pwidthInit - 1;
 750     ppt = pptInit;
 751
 752     xstart = ppt->x;
 753     ystart = ppt->y;
 754     if (pGC->miTranslate)
 755     {
 756         xstart += pDraw->x;
 757         ystart += pDraw->y;
 758     }
 759
 760     /* x2, y2, oc2 copied to x1, y1, oc1 at top of loop to simplify
 761      * iteration logic
 762      */
 763     x2 = xstart;
 764     y2 = ystart;
 765     oc2 = 0;
 766     MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
 767
 768     while (--npt > 0)
 769     {
 770         if (Nspans > 0)
 771             (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
 772                                    pwidthInit, FALSE);
 773         Nspans = 0;
 774         new_span = TRUE;
 775         spans  = pspanInit - 1;
 776         widths = pwidthInit - 1;
 777
 778         x1  = x2;
 779         y1  = y2;
 780         oc1 = oc2;
 781         ++ppt;
 782
 783         x2 = ppt->x;
 784         y2 = ppt->y;
 785         if (pGC->miTranslate && (mode != CoordModePrevious))
 786         {
 787             x2 += pDraw->x;
 788             y2 += pDraw->y;
 789         }
 790         else if (mode == CoordModePrevious)
 791         {
 792             x2 += x1;
 793             y2 += y1;
 794         }
 795
 796         oc2 = 0;
 797         MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
 798
 799         CalcLineDeltas(x1, y1, x2, y2, adx, ady, signdx, signdy, 1, 1, octant);
 800
 801         if (adx > ady)
 802         {
 803             e1 = ady << 1;
 804             e2 = e1 - (adx << 1);
 805             e  = e1 - adx;
 806             length  = adx;      /* don't draw endpoint in main loop */
 807
 808             FIXUP_ERROR(e, octant, bias);
 809
 810             new_x1 = x1;
 811             new_y1 = y1;
 812             new_x2 = x2;
 813             new_y2 = y2;
 814             pt1_clipped = 0;
 815             pt2_clipped = 0;
 816
 817             if ((oc1 | oc2) != 0)
 818             {
 819                 result = miZeroClipLine(xleft, ytop, xright, ybottom,
 820                                         &new_x1, &new_y1, &new_x2, &new_y2,
 821                                         adx, ady,
 822                                         &pt1_clipped, &pt2_clipped,
 823                                         octant, bias, oc1, oc2);
 824                 if (result == -1)
 825                     continue;
 826
 827                 length = abs(new_x2 - new_x1);
 828
 829                 /* if we've clipped the endpoint, always draw the full length
 830                  * of the segment, because then the capstyle doesn't matter
 831                  */
 832                 if (pt2_clipped)
 833                     length++;
 834
 835                 if (pt1_clipped)
 836                 {
 837                     /* must calculate new error terms */
 838                     clipdx = abs(new_x1 - x1);
 839                     clipdy = abs(new_y1 - y1);
 840                     e += (clipdy * e2) + ((clipdx - clipdy) * e1);
 841                 }
 842             }
 843
 844             /* draw the segment */
 845
 846             x = new_x1;
 847             y = new_y1;
 848
 849             e3 = e2 - e1;
 850             e  = e - e1;
 851
 852             while (length--)
 853             {
 854                 MI_OUTPUT_POINT(x, y);
 855                 e += e1;
 856                 if (e >= 0)
 857                 {
 858                     y += signdy;
 859                     e += e3;
 860                 }
 861                 x += signdx;
 862             }
 863         }
 864         else    /* Y major line */
 865         {
 866             e1 = adx << 1;
 867             e2 = e1 - (ady << 1);
 868             e  = e1 - ady;
 869             length  = ady;      /* don't draw endpoint in main loop */
 870
 871             SetYMajorOctant(octant);
 872             FIXUP_ERROR(e, octant, bias);
 873
 874             new_x1 = x1;
 875             new_y1 = y1;
 876             new_x2 = x2;
 877             new_y2 = y2;
 878             pt1_clipped = 0;
 879             pt2_clipped = 0;
 880
 881             if ((oc1 | oc2) != 0)
 882             {
 883                 result = miZeroClipLine(xleft, ytop, xright, ybottom,
 884                                         &new_x1, &new_y1, &new_x2, &new_y2,
 885                                         adx, ady,
 886                                         &pt1_clipped, &pt2_clipped,
 887                                         octant, bias, oc1, oc2);
 888                 if (result == -1)
 889                     continue;
 890
 891                 length = abs(new_y2 - new_y1);
 892
 893                 /* if we've clipped the endpoint, always draw the full length
 894                  * of the segment, because then the capstyle doesn't matter
 895                  */
 896                 if (pt2_clipped)
 897                     length++;
 898
 899                 if (pt1_clipped)
 900                 {
 901                     /* must calculate new error terms */
 902                     clipdx = abs(new_x1 - x1);
 903                     clipdy = abs(new_y1 - y1);
 904                     e += (clipdx * e2) + ((clipdy - clipdx) * e1);
 905                 }
 906             }
 907
 908             /* draw the segment */
 909
 910             x = new_x1;
 911             y = new_y1;
 912
 913             e3 = e2 - e1;
 914             e  = e - e1;
 915
 916             while (length--)
 917             {
 918                 MI_OUTPUT_POINT(x, y);
 919                 e += e1;
 920                 if (e >= 0)
 921                 {
 922                     x += signdx;
 923                     e += e3;
 924                 }
 925                 y += signdy;
 926             }
 927         }
 928     }
 929
 930     /* only do the capnotlast check on the last segment
 931      * and only if the endpoint wasn't clipped.  And then, if the last
 932      * point is the same as the first point, do not draw it, unless the
 933      * line is degenerate
 934      */
 935     if ( (! pt2_clipped) && (pGC->capStyle != CapNotLast) &&
 936                 (((xstart != x2) || (ystart != y2)) || (ppt == pptInit + 1)))
 937     {
 938         MI_OUTPUT_POINT(x, y);
 939     }
 940
 941     if (Nspans > 0)
 942         (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
 943                                pwidthInit, FALSE);
 944
 945     DEALLOCATE_LOCAL(pwidthInit);
 946     DEALLOCATE_LOCAL(pspanInit);
 947 }
 948
 949 void
 950 miZeroDashLine(dst, pgc, mode, nptInit, pptInit)
 951 DrawablePtr dst;
 952 GCPtr pgc;
 953 int mode;
 954 int nptInit;            /* number of points in polyline */
 955 DDXPointRec *pptInit;   /* points in the polyline */
 956 {
 957     /* XXX kludge until real zero-width dash code is written */
 958     pgc->lineWidth = 1;
 959     miWideDash (dst, pgc, mode, nptInit, pptInit);
 960     pgc->lineWidth = 0;
 961 }