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

   1 /***********************************************************
   2
   3 Copyright (c) 1989  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 1989 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
  49 /* $XConsortium: mispans.c,v 5.5 94/04/17 20:27:52 dpw Exp $ */
  50 /* $XFree86: xc/programs/Xserver/mi/mispans.c,v 3.0 1995/07/07 15:45:49 dawes Exp $ */
  51
  52 #include "misc.h"
  53 #include "pixmapstr.h"
  54 #include "gcstruct.h"
  55 #include "mispans.h"
  56
  57 /*
  58
  59 These routines maintain lists of Spans, in order to implement the
  60 ``touch-each-pixel-once'' rules of wide lines and arcs.
  61
  62 Written by Joel McCormack, Summer 1989.
  63
  64 */
  65
  66
  67 void miInitSpanGroup(spanGroup)
  68     SpanGroup *spanGroup;
  69 {
  70     spanGroup->size = 0;
  71     spanGroup->count = 0;
  72     spanGroup->group = NULL;
  73     spanGroup->ymin = MAXSHORT;
  74     spanGroup->ymax = MINSHORT;
  75 } /* InitSpanGroup */
  76
  77 #define YMIN(spans) (spans->points[0].y)
  78 #define YMAX(spans)  (spans->points[spans->count-1].y)
  79
  80 void miSubtractSpans (spanGroup, sub)
  81     SpanGroup   *spanGroup;
  82     Spans       *sub;
  83 {
  84     int         i, subCount, spansCount;
  85     int         ymin, ymax, xmin, xmax;
  86     Spans       *spans;
  87     DDXPointPtr subPt, spansPt;
  88     int         *subWid, *spansWid;
  89     int         extra;
  90
  91     ymin = YMIN(sub);
  92     ymax = YMAX(sub);
  93     spans = spanGroup->group;
  94     for (i = spanGroup->count; i; i--, spans++) {
  95         if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
  96             subCount = sub->count;
  97             subPt = sub->points;
  98             subWid = sub->widths;
  99             spansCount = spans->count;
 100             spansPt = spans->points;
 101             spansWid = spans->widths;
 102             extra = 0;
 103             for (;;)
 104             {
 105                 while (spansCount && spansPt->y < subPt->y)
 106                 {
 107                     spansPt++;  spansWid++; spansCount--;
 108                 }
 109                 if (!spansCount)
 110                     break;
 111                 while (subCount && subPt->y < spansPt->y)
 112                 {
 113                     subPt++;    subWid++;   subCount--;
 114                 }
 115                 if (!subCount)
 116                     break;
 117                 if (subPt->y == spansPt->y)
 118                 {
 119                     xmin = subPt->x;
 120                     xmax = xmin + *subWid;
 121                     if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax)
 122                     {
 123                         ;
 124                     }
 125                     else if (xmin <= spansPt->x)
 126                     {
 127                         if (xmax >= spansPt->x + *spansWid)
 128                         {
 129                             memmove (spansPt, spansPt + 1, sizeof *spansPt * (spansCount - 1));
 130                             memmove (spansWid, spansWid + 1, sizeof *spansWid * (spansCount - 1));
 131                             spansPt--;
 132                             spansWid--;
 133                             spans->count--;
 134                             extra++;
 135                         }
 136                         else
 137                         {
 138                             *spansWid = *spansWid - (xmax - spansPt->x);
 139                             spansPt->x = xmax;
 140                         }
 141                     }
 142                     else
 143                     {
 144                         if (xmax >= spansPt->x + *spansWid)
 145                         {
 146                             *spansWid = xmin - spansPt->x;
 147                         }
 148                         else
 149                         {
 150                             if (!extra) {
 151                                 DDXPointPtr newPt;
 152                                 int         *newwid;
 153
 154 #define EXTRA 8
 155                                 newPt = (DDXPointPtr) xrealloc (spans->points, (spans->count + EXTRA) * sizeof (DDXPointRec));
 156                                 if (!newPt)
 157                                     break;
 158                                 spansPt = newPt + (spansPt - spans->points);
 159                                 spans->points = newPt;
 160                                 newwid = (int *) xrealloc (spans->widths, (spans->count + EXTRA) * sizeof (int));
 161                                 if (!newwid)
 162                                     break;
 163                                 spansWid = newwid + (spansWid - spans->widths);
 164                                 spans->widths = newwid;
 165                                 extra = EXTRA;
 166                             }
 167                             memmove (spansPt + 1, spansPt, sizeof *spansPt * (spansCount));
 168                             memmove (spansWid + 1, spansWid, sizeof *spansWid * (spansCount));
 169                             spans->count++;
 170                             extra--;
 171                             *spansWid = xmin - spansPt->x;
 172                             spansWid++;
 173                             spansPt++;
 174                             *spansWid = *spansWid - (xmax - spansPt->x);
 175                             spansPt->x = xmax;
 176                         }
 177                     }
 178                 }
 179                 spansPt++;  spansWid++; spansCount--;
 180             }
 181         }
 182     }
 183 }
 184
 185 void miAppendSpans(spanGroup, otherGroup, spans)
 186     SpanGroup   *spanGroup;
 187     SpanGroup   *otherGroup;
 188     Spans       *spans;
 189 {
 190     register    int ymin, ymax;
 191     register    int spansCount;
 192
 193     spansCount = spans->count;
 194     if (spansCount > 0) {
 195         if (spanGroup->size == spanGroup->count) {
 196             spanGroup->size = (spanGroup->size + 8) * 2;
 197             spanGroup->group = (Spans *)
 198                 xrealloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
 199          }
 200
 201         spanGroup->group[spanGroup->count] = *spans;
 202         (spanGroup->count)++;
 203         ymin = spans->points[0].y;
 204         if (ymin < spanGroup->ymin) spanGroup->ymin = ymin;
 205         ymax = spans->points[spansCount - 1].y;
 206         if (ymax > spanGroup->ymax) spanGroup->ymax = ymax;
 207         if (otherGroup &&
 208             otherGroup->ymin < ymax &&
 209             ymin < otherGroup->ymax)
 210         {
 211             miSubtractSpans (otherGroup, spans);
 212         }
 213     }
 214     else
 215     {
 216         xfree (spans->points);
 217         xfree (spans->widths);
 218     }
 219 } /* AppendSpans */
 220
 221 void miFreeSpanGroup(spanGroup)
 222     SpanGroup   *spanGroup;
 223 {
 224     if (spanGroup->group != NULL) xfree(spanGroup->group);
 225 }
 226
 227 static void QuickSortSpansX(points, widths, numSpans)
 228     register DDXPointRec    points[];
 229     register int            widths[];
 230     register int            numSpans;
 231 {
 232     register int            x;
 233     register int            i, j, m;
 234     register DDXPointPtr    r;
 235
 236 /* Always called with numSpans > 1 */
 237 /* Sorts only by x, as all y should be the same */
 238
 239 #define ExchangeSpans(a, b)                                 \
 240 {                                                           \
 241     DDXPointRec     tpt;                                    \
 242     register int    tw;                                     \
 243                                                             \
 244     tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
 245     tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
 246 }
 247
 248     do {
 249         if (numSpans < 9) {
 250             /* Do insertion sort */
 251             register int xprev;
 252
 253             xprev = points[0].x;
 254             i = 1;
 255             do { /* while i != numSpans */
 256                 x = points[i].x;
 257                 if (xprev > x) {
 258                     /* points[i] is out of order.  Move into proper location. */
 259                     DDXPointRec tpt;
 260                     int     tw, k;
 261
 262                     for (j = 0; x >= points[j].x; j++) {}
 263                     tpt = points[i];
 264                     tw  = widths[i];
 265                     for (k = i; k != j; k--) {
 266                         points[k] = points[k-1];
 267                         widths[k] = widths[k-1];
 268                     }
 269                     points[j] = tpt;
 270                     widths[j] = tw;
 271                     x = points[i].x;
 272                 } /* if out of order */
 273                 xprev = x;
 274                 i++;
 275             } while (i != numSpans);
 276             return;
 277         }
 278
 279         /* Choose partition element, stick in location 0 */
 280         m = numSpans / 2;
 281         if (points[m].x > points[0].x)          ExchangeSpans(m, 0);
 282         if (points[m].x > points[numSpans-1].x) ExchangeSpans(m, numSpans-1);
 283         if (points[m].x > points[0].x)          ExchangeSpans(m, 0);
 284         x = points[0].x;
 285
 286         /* Partition array */
 287         i = 0;
 288         j = numSpans;
 289         do {
 290             r = &(points[i]);
 291             do {
 292                 r++;
 293                 i++;
 294             } while (i != numSpans && r->x < x);
 295             r = &(points[j]);
 296             do {
 297                 r--;
 298                 j--;
 299             } while (x < r->x);
 300             if (i < j) ExchangeSpans(i, j);
 301         } while (i < j);
 302
 303         /* Move partition element back to middle */
 304         ExchangeSpans(0, j);
 305
 306         /* Recurse */
 307         if (numSpans-j-1 > 1)
 308             QuickSortSpansX(&points[j+1], &widths[j+1], numSpans-j-1);
 309         numSpans = j;
 310     } while (numSpans > 1);
 311 } /* QuickSortSpans */
 312
 313
 314 static int UniquifySpansX(spans, newPoints, newWidths)
 315     Spans                   *spans;
 316     register DDXPointRec    *newPoints;
 317     register int            *newWidths;
 318 {
 319     register int newx1, newx2, oldpt, i, y;
 320     register DDXPointRec    *oldPoints;
 321     register int            *oldWidths;
 322     int                     *startNewWidths;
 323
 324 /* Always called with numSpans > 1 */
 325 /* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
 326    number of unique spans. */
 327
 328
 329     startNewWidths = newWidths;
 330
 331     oldPoints = spans->points;
 332     oldWidths = spans->widths;
 333
 334     y = oldPoints->y;
 335     newx1 = oldPoints->x;
 336     newx2 = newx1 + *oldWidths;
 337
 338     for (i = spans->count-1; i != 0; i--) {
 339         oldPoints++;
 340         oldWidths++;
 341         oldpt = oldPoints->x;
 342         if (oldpt > newx2) {
 343             /* Write current span, start a new one */
 344             newPoints->x = newx1;
 345             newPoints->y = y;
 346             *newWidths = newx2 - newx1;
 347             newPoints++;
 348             newWidths++;
 349             newx1 = oldpt;
 350             newx2 = oldpt + *oldWidths;
 351         } else {
 352             /* extend current span, if old extends beyond new */
 353             oldpt = oldpt + *oldWidths;
 354             if (oldpt > newx2) newx2 = oldpt;
 355         }
 356     } /* for */
 357
 358     /* Write final span */
 359     newPoints->x = newx1;
 360     *newWidths = newx2 - newx1;
 361     newPoints->y = y;
 362
 363     return (newWidths - startNewWidths) + 1;
 364 } /* UniquifySpansX */
 365
 366 void
 367 miDisposeSpanGroup (spanGroup)
 368     SpanGroup   *spanGroup;
 369 {
 370     int     i;
 371     Spans   *spans;
 372
 373     for (i = 0; i < spanGroup->count; i++)
 374     {
 375         spans = spanGroup->group + i;
 376         xfree (spans->points);
 377         xfree (spans->widths);
 378     }
 379 }
 380
 381 void miFillUniqueSpanGroup(pDraw, pGC, spanGroup)
 382     DrawablePtr pDraw;
 383     GCPtr       pGC;
 384     SpanGroup   *spanGroup;
 385 {
 386     register int    i;
 387     register Spans  *spans;
 388     register Spans  *yspans;
 389     register int    *ysizes;
 390     register int    ymin, ylength;
 391
 392     /* Outgoing spans for one big call to FillSpans */
 393     register DDXPointPtr    points;
 394     register int            *widths;
 395     register int            count;
 396
 397     if (spanGroup->count == 0) return;
 398
 399     if (spanGroup->count == 1) {
 400         /* Already should be sorted, unique */
 401         spans = spanGroup->group;
 402         (*pGC->ops->FillSpans)
 403             (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
 404         xfree(spans->points);
 405         xfree(spans->widths);
 406     }
 407     else
 408     {
 409         /* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
 410         /* This seems to be the fastest thing to do.  I've tried sorting on
 411            both x and y at the same time rather than creating into all those
 412            y buckets, but it was somewhat slower. */
 413
 414         ymin    = spanGroup->ymin;
 415         ylength = spanGroup->ymax - ymin + 1;
 416
 417         /* Allocate Spans for y buckets */
 418         yspans = (Spans *) xalloc(ylength * sizeof(Spans));
 419         ysizes = (int *) xalloc(ylength * sizeof (int));
 420
 421         if (!yspans || !ysizes)
 422         {
 423             if (yspans)
 424                 xfree (yspans);
 425             if (ysizes)
 426                 xfree (ysizes);
 427             miDisposeSpanGroup (spanGroup);
 428             return;
 429         }
 430
 431         for (i = 0; i != ylength; i++) {
 432             ysizes[i]        = 0;
 433             yspans[i].count  = 0;
 434             yspans[i].points = NULL;
 435             yspans[i].widths = NULL;
 436         }
 437
 438         /* Go through every single span and put it into the correct bucket */
 439         count = 0;
 440         for (i = 0, spans = spanGroup->group;
 441                 i != spanGroup->count;
 442                 i++, spans++) {
 443             int         index;
 444             int         j;
 445
 446             for (j = 0, points = spans->points, widths = spans->widths;
 447                     j != spans->count;
 448                     j++, points++, widths++) {
 449                 index = points->y - ymin;
 450                 if (index >= 0 && index < ylength) {
 451                     Spans *newspans = &(yspans[index]);
 452                     if (newspans->count == ysizes[index]) {
 453                         DDXPointPtr newpoints;
 454                         int         *newwidths;
 455                         ysizes[index] = (ysizes[index] + 8) * 2;
 456                         newpoints = (DDXPointPtr) xrealloc(
 457                             newspans->points,
 458                             ysizes[index] * sizeof(DDXPointRec));
 459                         newwidths = (int *) xrealloc(
 460                             newspans->widths,
 461                             ysizes[index] * sizeof(int));
 462                         if (!newpoints || !newwidths)
 463                         {
 464                             int i;
 465
 466                             for (i = 0; i < ylength; i++)
 467                             {
 468                                 xfree (yspans[i].points);
 469                                 xfree (yspans[i].widths);
 470                             }
 471                             xfree (yspans);
 472                             xfree (ysizes);
 473                             miDisposeSpanGroup (spanGroup);
 474                             return;
 475                         }
 476                         newspans->points = newpoints;
 477                         newspans->widths = newwidths;
 478                     }
 479                     newspans->points[newspans->count] = *points;
 480                     newspans->widths[newspans->count] = *widths;
 481                     (newspans->count)++;
 482                 } /* if y value of span in range */
 483             } /* for j through spans */
 484             count += spans->count;
 485             xfree(spans->points);
 486             spans->points = NULL;
 487             xfree(spans->widths);
 488             spans->widths = NULL;
 489         } /* for i thorough Spans */
 490
 491         /* Now sort by x and uniquify each bucket into the final array */
 492         points = (DDXPointPtr) xalloc(count * sizeof(DDXPointRec));
 493         widths = (int *)       xalloc(count * sizeof(int));
 494         if (!points || !widths)
 495         {
 496             int i;
 497
 498             for (i = 0; i < ylength; i++)
 499             {
 500                 xfree (yspans[i].points);
 501                 xfree (yspans[i].widths);
 502             }
 503             xfree (yspans);
 504             xfree (ysizes);
 505             if (points)
 506                 xfree (points);
 507             if (widths)
 508                 xfree (widths);
 509             return;
 510         }
 511         count = 0;
 512         for (i = 0; i != ylength; i++) {
 513             int ycount = yspans[i].count;
 514             if (ycount > 0) {
 515                 if (ycount > 1) {
 516                     QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
 517                     count += UniquifySpansX
 518                         (&(yspans[i]), &(points[count]), &(widths[count]));
 519                 } else {
 520                     points[count] = yspans[i].points[0];
 521                     widths[count] = yspans[i].widths[0];
 522                     count++;
 523                 }
 524                 xfree(yspans[i].points);
 525                 xfree(yspans[i].widths);
 526             }
 527         }
 528
 529         (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
 530         xfree(points);
 531         xfree(widths);
 532         xfree(yspans);
 533         xfree(ysizes);          /* use (DE)ALLOCATE_LOCAL for these? */
 534     }
 535
 536     spanGroup->count = 0;
 537     spanGroup->ymin = MAXSHORT;
 538     spanGroup->ymax = MINSHORT;
 539 }
 540
 541
 542 void miFillSpanGroup(pDraw, pGC, spanGroup)
 543     DrawablePtr pDraw;
 544     GCPtr       pGC;
 545     SpanGroup   *spanGroup;
 546 {
 547     register int    i;
 548     register Spans  *spans;
 549
 550     for (i = 0, spans = spanGroup->group; i != spanGroup->count; i++, spans++) {
 551         (*pGC->ops->FillSpans)
 552             (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
 553         xfree(spans->points);
 554         xfree(spans->widths);
 555     }
 556
 557     spanGroup->count = 0;
 558     spanGroup->ymin = MAXSHORT;
 559     spanGroup->ymax = MINSHORT;
 560 } /* FillSpanGroup */