Update to xserver 1.17.2. tested by dcoppa@, jsg@, jasper@ & naddy@

1 files changed, 618 insertions, 9 deletions

diff --git a/xserver/mi/mipoly.c b/xserver/mi/mipoly.c
index 07d981845..a332376d1 100644
--- a/xserver/mi/mipoly.c
+++ b/xserver/mi/mipoly.c
@@ -26,13 +26,13 @@ Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
 
                         All Rights Reserved
 
-Permission to use, copy, modify, and distribute this software and its 
-documentation for any purpose and without fee is hereby granted, 
+Permission to use, copy, modify, and distribute this software and its
+documentation for any purpose and without fee is hereby granted,
 provided that the above copyright notice appear in all copies and that
-both that copyright notice and this permission notice appear in 
+both that copyright notice and this permission notice appear in
 supporting documentation, and that the name of Digital not be
 used in advertising or publicity pertaining to distribution of the
-software without specific, written prior permission.  
+software without specific, written prior permission.
 
 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
@@ -47,11 +47,6 @@ SOFTWARE.
  *  mipoly.c
  *
  *  Written by Brian Kelleher; June 1986
- *
- *  Draw polygons.  This routine translates the point by the
- *  origin if pGC->miTranslate is non-zero, and calls
- *  to the appropriate routine to actually scan convert the
- *  polygon.
  */
 #ifdef HAVE_DIX_CONFIG_H
 #include <dix-config.h>
@@ -62,8 +57,622 @@ SOFTWARE.
 #include "gcstruct.h"
 #include "pixmapstr.h"
 #include "mi.h"
+#include "miscanfill.h"
+#include "mipoly.h"
 #include "regionstr.h"
 
+/*
+ * Insert the given edge into the edge table.  First we must find the correct
+ * bucket in the Edge table, then find the right slot in the bucket.  Finally,
+ * we can insert it.
+ */
+static Bool
+miInsertEdgeInET(EdgeTable * ET, EdgeTableEntry * ETE, int scanline,
+                 ScanLineListBlock ** SLLBlock, int *iSLLBlock)
+{
+    EdgeTableEntry *start, *prev;
+    ScanLineList *pSLL, *pPrevSLL;
+    ScanLineListBlock *tmpSLLBlock;
+
+    /*
+     * find the right bucket to put the edge into
+     */
+    pPrevSLL = &ET->scanlines;
+    pSLL = pPrevSLL->next;
+    while (pSLL && (pSLL->scanline < scanline)) {
+        pPrevSLL = pSLL;
+        pSLL = pSLL->next;
+    }
+
+    /*
+     * reassign pSLL (pointer to ScanLineList) if necessary
+     */
+    if ((!pSLL) || (pSLL->scanline > scanline)) {
+        if (*iSLLBlock > SLLSPERBLOCK - 1) {
+            tmpSLLBlock = malloc(sizeof(ScanLineListBlock));
+            if (!tmpSLLBlock)
+                return FALSE;
+            (*SLLBlock)->next = tmpSLLBlock;
+            tmpSLLBlock->next = NULL;
+            *SLLBlock = tmpSLLBlock;
+            *iSLLBlock = 0;
+        }
+        pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
+
+        pSLL->next = pPrevSLL->next;
+        pSLL->edgelist = NULL;
+        pPrevSLL->next = pSLL;
+    }
+    pSLL->scanline = scanline;
+
+    /*
+     * now insert the edge in the right bucket
+     */
+    prev = NULL;
+    start = pSLL->edgelist;
+    while (start && (start->bres.minor < ETE->bres.minor)) {
+        prev = start;
+        start = start->next;
+    }
+    ETE->next = start;
+
+    if (prev)
+        prev->next = ETE;
+    else
+        pSLL->edgelist = ETE;
+    return TRUE;
+}
+
+static void
+miFreeStorage(ScanLineListBlock * pSLLBlock)
+{
+    ScanLineListBlock *tmpSLLBlock;
+
+    while (pSLLBlock) {
+        tmpSLLBlock = pSLLBlock->next;
+        free(pSLLBlock);
+        pSLLBlock = tmpSLLBlock;
+    }
+}
+
+/*
+ * CreateEdgeTable
+ *
+ * This routine creates the edge table for scan converting polygons.
+ * The Edge Table (ET) looks like:
+ *
+ * EdgeTable
+ *  --------
+ * |  ymax  |        ScanLineLists
+ * |scanline|-->------------>-------------->...
+ *  --------   |scanline|   |scanline|
+ *             |edgelist|   |edgelist|
+ *             ---------    ---------
+ *                 |             |
+ *                 |             |
+ *                 V             V
+ *           list of ETEs   list of ETEs
+ *
+ * where ETE is an EdgeTableEntry data structure, and there is one ScanLineList
+ * per scanline at which an edge is initially entered.
+ */
+
+static Bool
+miCreateETandAET(int count, DDXPointPtr pts, EdgeTable * ET,
+                 EdgeTableEntry * AET, EdgeTableEntry * pETEs,
+                 ScanLineListBlock * pSLLBlock)
+{
+    DDXPointPtr top, bottom;
+    DDXPointPtr PrevPt, CurrPt;
+    int iSLLBlock = 0;
+
+    int dy;
+
+    if (count < 2)
+        return TRUE;
+
+    /*
+     *  initialize the Active Edge Table
+     */
+    AET->next = NULL;
+    AET->back = NULL;
+    AET->nextWETE = NULL;
+    AET->bres.minor = MININT;
+
+    /*
+     *  initialize the Edge Table.
+     */
+    ET->scanlines.next = NULL;
+    ET->ymax = MININT;
+    ET->ymin = MAXINT;
+    pSLLBlock->next = NULL;
+
+    PrevPt = &pts[count - 1];
+
+    /*
+     *  for each vertex in the array of points.
+     *  In this loop we are dealing with two vertices at
+     *  a time -- these make up one edge of the polygon.
+     */
+    while (count--) {
+        CurrPt = pts++;
+
+        /*
+         *  find out which point is above and which is below.
+         */
+        if (PrevPt->y > CurrPt->y) {
+            bottom = PrevPt, top = CurrPt;
+            pETEs->ClockWise = 0;
+        }
+        else {
+            bottom = CurrPt, top = PrevPt;
+            pETEs->ClockWise = 1;
+        }
+
+        /*
+         * don't add horizontal edges to the Edge table.
+         */
+        if (bottom->y != top->y) {
+            pETEs->ymax = bottom->y - 1; /* -1 so we don't get last scanline */
+
+            /*
+             *  initialize integer edge algorithm
+             */
+            dy = bottom->y - top->y;
+            BRESINITPGONSTRUCT(dy, top->x, bottom->x, pETEs->bres);
+
+            if (!miInsertEdgeInET(ET, pETEs, top->y, &pSLLBlock, &iSLLBlock)) {
+                miFreeStorage(pSLLBlock->next);
+                return FALSE;
+            }
+
+            ET->ymax = max(ET->ymax, PrevPt->y);
+            ET->ymin = min(ET->ymin, PrevPt->y);
+            pETEs++;
+        }
+
+        PrevPt = CurrPt;
+    }
+    return TRUE;
+}
+
+/*
+ * This routine moves EdgeTableEntries from the EdgeTable into the Active Edge
+ * Table, leaving them sorted by smaller x coordinate.
+ */
+
+static void
+miloadAET(EdgeTableEntry * AET, EdgeTableEntry * ETEs)
+{
+    EdgeTableEntry *pPrevAET;
+    EdgeTableEntry *tmp;
+
+    pPrevAET = AET;
+    AET = AET->next;
+    while (ETEs) {
+        while (AET && (AET->bres.minor < ETEs->bres.minor)) {
+            pPrevAET = AET;
+            AET = AET->next;
+        }
+        tmp = ETEs->next;
+        ETEs->next = AET;
+        if (AET)
+            AET->back = ETEs;
+        ETEs->back = pPrevAET;
+        pPrevAET->next = ETEs;
+        pPrevAET = ETEs;
+
+        ETEs = tmp;
+    }
+}
+
+/*
+ * computeWAET
+ *
+ * This routine links the AET by the nextWETE (winding EdgeTableEntry) link for
+ * use by the winding number rule.  The final Active Edge Table (AET) might
+ * look something like:
+ *
+ * AET
+ * ----------  ---------   ---------
+ * |ymax    |  |ymax    |  |ymax    |
+ * | ...    |  |...     |  |...     |
+ * |next    |->|next    |->|next    |->...
+ * |nextWETE|  |nextWETE|  |nextWETE|
+ * ---------   ---------   ^--------
+ *     |                   |       |
+ *     V------------------->       V---> ...
+ *
+ */
+static void
+micomputeWAET(EdgeTableEntry * AET)
+{
+    EdgeTableEntry *pWETE;
+    int inside = 1;
+    int isInside = 0;
+
+    AET->nextWETE = NULL;
+    pWETE = AET;
+    AET = AET->next;
+    while (AET) {
+        if (AET->ClockWise)
+            isInside++;
+        else
+            isInside--;
+
+        if ((!inside && !isInside) || (inside && isInside)) {
+            pWETE->nextWETE = AET;
+            pWETE = AET;
+            inside = !inside;
+        }
+        AET = AET->next;
+    }
+    pWETE->nextWETE = NULL;
+}
+
+/*
+ * Just a simple insertion sort using pointers and back pointers to sort the
+ * Active Edge Table.
+ */
+
+static int
+miInsertionSort(EdgeTableEntry * AET)
+{
+    EdgeTableEntry *pETEchase;
+    EdgeTableEntry *pETEinsert;
+    EdgeTableEntry *pETEchaseBackTMP;
+    int changed = 0;
+
+    AET = AET->next;
+    while (AET) {
+        pETEinsert = AET;
+        pETEchase = AET;
+        while (pETEchase->back->bres.minor > AET->bres.minor)
+            pETEchase = pETEchase->back;
+
+        AET = AET->next;
+        if (pETEchase != pETEinsert) {
+            pETEchaseBackTMP = pETEchase->back;
+            pETEinsert->back->next = AET;
+            if (AET)
+                AET->back = pETEinsert->back;
+            pETEinsert->next = pETEchase;
+            pETEchase->back->next = pETEinsert;
+            pETEchase->back = pETEinsert;
+            pETEinsert->back = pETEchaseBackTMP;
+            changed = 1;
+        }
+    }
+    return changed;
+}
+
+/* Find the index of the point with the smallest y */
+static int
+getPolyYBounds(DDXPointPtr pts, int n, int *by, int *ty)
+{
+    DDXPointPtr ptMin;
+    int ymin, ymax;
+    DDXPointPtr ptsStart = pts;
+
+    ptMin = pts;
+    ymin = ymax = (pts++)->y;
+
+    while (--n > 0) {
+        if (pts->y < ymin) {
+            ptMin = pts;
+            ymin = pts->y;
+        }
+        if (pts->y > ymax)
+            ymax = pts->y;
+
+        pts++;
+    }
+
+    *by = ymin;
+    *ty = ymax;
+    return ptMin - ptsStart;
+}
+
+/*
+ * Written by Brian Kelleher; Dec. 1985.
+ *
+ * Fill a convex polygon.  If the given polygon is not convex, then the result
+ * is undefined.  The algorithm is to order the edges from smallest y to
+ * largest by partitioning the array into a left edge list and a right edge
+ * list.  The algorithm used to traverse each edge is an extension of
+ * Bresenham's line algorithm with y as the major axis.  For a derivation of
+ * the algorithm, see the author of this code.
+ */
+static Bool
+miFillConvexPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn)
+{
+    int xl = 0, xr = 0;         /* x vals of left and right edges */
+    int dl = 0, dr = 0;         /* decision variables             */
+    int ml = 0, m1l = 0;        /* left edge slope and slope+1    */
+    int mr = 0, m1r = 0;        /* right edge slope and slope+1   */
+    int incr1l = 0, incr2l = 0; /* left edge error increments     */
+    int incr1r = 0, incr2r = 0; /* right edge error increments    */
+    int dy;                     /* delta y                        */
+    int y;                      /* current scanline               */
+    int left, right;            /* indices to first endpoints     */
+    int i;                      /* loop counter                   */
+    int nextleft, nextright;    /* indices to second endpoints    */
+    DDXPointPtr ptsOut, FirstPoint;     /* output buffer               */
+    int *width, *FirstWidth;    /* output buffer                  */
+    int imin;                   /* index of smallest vertex (in y) */
+    int ymin;                   /* y-extents of polygon            */
+    int ymax;
+
+    /*
+     *  find leftx, bottomy, rightx, topy, and the index
+     *  of bottomy. Also translate the points.
+     */
+    imin = getPolyYBounds(ptsIn, count, &ymin, &ymax);
+
+    dy = ymax - ymin + 1;
+    if ((count < 3) || (dy < 0))
+        return TRUE;
+    ptsOut = FirstPoint = malloc(sizeof(DDXPointRec) * dy);
+    width = FirstWidth = malloc(sizeof(int) * dy);
+    if (!FirstPoint || !FirstWidth) {
+        free(FirstWidth);
+        free(FirstPoint);
+        return FALSE;
+    }
+
+    nextleft = nextright = imin;
+    y = ptsIn[nextleft].y;
+
+    /*
+     *  loop through all edges of the polygon
+     */
+    do {
+        /*
+         *  add a left edge if we need to
+         */
+        if (ptsIn[nextleft].y == y) {
+            left = nextleft;
+
+            /*
+             *  find the next edge, considering the end
+             *  conditions of the array.
+             */
+            nextleft++;
+            if (nextleft >= count)
+                nextleft = 0;
+
+            /*
+             *  now compute all of the random information
+             *  needed to run the iterative algorithm.
+             */
+            BRESINITPGON(ptsIn[nextleft].y - ptsIn[left].y,
+                         ptsIn[left].x, ptsIn[nextleft].x,
+                         xl, dl, ml, m1l, incr1l, incr2l);
+        }
+
+        /*
+         *  add a right edge if we need to
+         */
+        if (ptsIn[nextright].y == y) {
+            right = nextright;
+
+            /*
+             *  find the next edge, considering the end
+             *  conditions of the array.
+             */
+            nextright--;
+            if (nextright < 0)
+                nextright = count - 1;
+
+            /*
+             *  now compute all of the random information
+             *  needed to run the iterative algorithm.
+             */
+            BRESINITPGON(ptsIn[nextright].y - ptsIn[right].y,
+                         ptsIn[right].x, ptsIn[nextright].x,
+                         xr, dr, mr, m1r, incr1r, incr2r);
+        }
+
+        /*
+         *  generate scans to fill while we still have
+         *  a right edge as well as a left edge.
+         */
+        i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
+        /* in case we're called with non-convex polygon */
+        if (i < 0) {
+            free(FirstWidth);
+            free(FirstPoint);
+            return TRUE;
+        }
+        while (i-- > 0) {
+            ptsOut->y = y;
+
+            /*
+             *  reverse the edges if necessary
+             */
+            if (xl < xr) {
+                *(width++) = xr - xl;
+                (ptsOut++)->x = xl;
+            }
+            else {
+                *(width++) = xl - xr;
+                (ptsOut++)->x = xr;
+            }
+            y++;
+
+            /* increment down the edges */
+            BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
+            BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
+        }
+    } while (y != ymax);
+
+    /*
+     * Finally, fill the <remaining> spans
+     */
+    (*pgc->ops->FillSpans) (dst, pgc,
+                            ptsOut - FirstPoint, FirstPoint, FirstWidth, 1);
+    free(FirstWidth);
+    free(FirstPoint);
+    return TRUE;
+}
+
+/*
+ * Written by Brian Kelleher;  Oct. 1985
+ *
+ * Routine to fill a polygon.  Two fill rules are supported: frWINDING and
+ * frEVENODD.
+ */
+static Bool
+miFillGeneralPoly(DrawablePtr dst, GCPtr pgc, int count, DDXPointPtr ptsIn)
+{
+    EdgeTableEntry *pAET;       /* the Active Edge Table   */
+    int y;                      /* the current scanline    */
+    int nPts = 0;               /* number of pts in buffer */
+    EdgeTableEntry *pWETE;      /* Winding Edge Table      */
+    ScanLineList *pSLL;         /* Current ScanLineList    */
+    DDXPointPtr ptsOut;         /* ptr to output buffers   */
+    int *width;
+    DDXPointRec FirstPoint[NUMPTSTOBUFFER];     /* the output buffers */
+    int FirstWidth[NUMPTSTOBUFFER];
+    EdgeTableEntry *pPrevAET;   /* previous AET entry      */
+    EdgeTable ET;               /* Edge Table header node  */
+    EdgeTableEntry AET;         /* Active ET header node   */
+    EdgeTableEntry *pETEs;      /* Edge Table Entries buff */
+    ScanLineListBlock SLLBlock; /* header for ScanLineList */
+    int fixWAET = 0;
+
+    if (count < 3)
+        return TRUE;
+
+    if (!(pETEs = malloc(sizeof(EdgeTableEntry) * count)))
+        return FALSE;
+    ptsOut = FirstPoint;
+    width = FirstWidth;
+    if (!miCreateETandAET(count, ptsIn, &ET, &AET, pETEs, &SLLBlock)) {
+        free(pETEs);
+        return FALSE;
+    }
+    pSLL = ET.scanlines.next;
+
+    if (pgc->fillRule == EvenOddRule) {
+        /*
+         *  for each scanline
+         */
+        for (y = ET.ymin; y < ET.ymax; y++) {
+            /*
+             *  Add a new edge to the active edge table when we
+             *  get to the next edge.
+             */
+            if (pSLL && y == pSLL->scanline) {
+                miloadAET(&AET, pSLL->edgelist);
+                pSLL = pSLL->next;
+            }
+            pPrevAET = &AET;
+            pAET = AET.next;
+
+            /*
+             *  for each active edge
+             */
+            while (pAET) {
+                ptsOut->x = pAET->bres.minor;
+                ptsOut++->y = y;
+                *width++ = pAET->next->bres.minor - pAET->bres.minor;
+                nPts++;
+
+                /*
+                 *  send out the buffer when its full
+                 */
+                if (nPts == NUMPTSTOBUFFER) {
+                    (*pgc->ops->FillSpans) (dst, pgc,
+                                            nPts, FirstPoint, FirstWidth, 1);
+                    ptsOut = FirstPoint;
+                    width = FirstWidth;
+                    nPts = 0;
+                }
+                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
+                EVALUATEEDGEEVENODD(pAET, pPrevAET, y);
+            }
+            miInsertionSort(&AET);
+        }
+    }
+    else {                      /* default to WindingNumber */
+
+        /*
+         *  for each scanline
+         */
+        for (y = ET.ymin; y < ET.ymax; y++) {
+            /*
+             *  Add a new edge to the active edge table when we
+             *  get to the next edge.
+             */
+            if (pSLL && y == pSLL->scanline) {
+                miloadAET(&AET, pSLL->edgelist);
+                micomputeWAET(&AET);
+                pSLL = pSLL->next;
+            }
+            pPrevAET = &AET;
+            pAET = AET.next;
+            pWETE = pAET;
+
+            /*
+             *  for each active edge
+             */
+            while (pAET) {
+                /*
+                 *  if the next edge in the active edge table is
+                 *  also the next edge in the winding active edge
+                 *  table.
+                 */
+                if (pWETE == pAET) {
+                    ptsOut->x = pAET->bres.minor;
+                    ptsOut++->y = y;
+                    *width++ = pAET->nextWETE->bres.minor - pAET->bres.minor;
+                    nPts++;
+
+                    /*
+                     *  send out the buffer
+                     */
+                    if (nPts == NUMPTSTOBUFFER) {
+                        (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint,
+                                                FirstWidth, 1);
+                        ptsOut = FirstPoint;
+                        width = FirstWidth;
+                        nPts = 0;
+                    }
+
+                    pWETE = pWETE->nextWETE;
+                    while (pWETE != pAET)
+                        EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
+                    pWETE = pWETE->nextWETE;
+                }
+                EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET);
+            }
+
+            /*
+             *  reevaluate the Winding active edge table if we
+             *  just had to resort it or if we just exited an edge.
+             */
+            if (miInsertionSort(&AET) || fixWAET) {
+                micomputeWAET(&AET);
+                fixWAET = 0;
+            }
+        }
+    }
+
+    /*
+     *     Get any spans that we missed by buffering
+     */
+    (*pgc->ops->FillSpans) (dst, pgc, nPts, FirstPoint, FirstWidth, 1);
+    free(pETEs);
+    miFreeStorage(SLLBlock.next);
+    return TRUE;
+}
+
+/*
+ *  Draw polygons.  This routine translates the point by the origin if
+ *  pGC->miTranslate is non-zero, and calls to the appropriate routine to
+ *  actually scan convert the polygon.
+ */
 void
 miFillPolygon(DrawablePtr dst, GCPtr pgc,
               int shape, int mode, int count, DDXPointPtr pPts)