svn merge -r588:HEAD ^/branches/released .

1 files changed, 385 insertions, 385 deletions

diff --git a/xorg-server/mi/mipolyutil.c b/xorg-server/mi/mipolyutil.c
index 15561b73d..fe0d9e5bf 100644
--- a/xorg-server/mi/mipolyutil.c
+++ b/xorg-server/mi/mipolyutil.c
@@ -1,385 +1,385 @@
-/***********************************************************
-
-Copyright 1987, 1998  The Open Group
-
-Permission to use, copy, modify, distribute, and sell this software and its
-documentation for any purpose is hereby granted without fee, provided that
-the above copyright notice appear in all copies and that both that
-copyright notice and this permission notice appear in supporting
-documentation.
-
-The above copyright notice and this permission notice shall be included in
-all copies or substantial portions of the Software.
-
-THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
-IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
-FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
-OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
-AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
-CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
-
-Except as contained in this notice, the name of The Open Group shall not be
-used in advertising or otherwise to promote the sale, use or other dealings
-in this Software without prior written authorization from The Open Group.
-
-
-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, 
-provided that the above copyright notice appear in all copies and that
-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.  
-
-DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
-ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
-DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
-ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
-WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
-ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
-SOFTWARE.
-
-******************************************************************/
-#ifdef HAVE_DIX_CONFIG_H
-#include <dix-config.h>
-#endif
-
-#include "regionstr.h"
-#include "gc.h"
-#include "miscanfill.h"
-#include "mipoly.h"
-#include "misc.h"	/* MAXINT */
-
-/*
- *     fillUtils.c
- *
- *     Written by Brian Kelleher;  Oct. 1985
- *
- *     This module contains all of the utility functions
- *     needed to scan convert a polygon.
- *
- */
-
-/*
- *     InsertEdgeInET
- *
- *     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 = xalloc(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;
-}
-
-/*
- *     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.
- *
- */
-
-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;
-}
-
-/*
- *     loadAET
- *
- *     This routine moves EdgeTableEntries from the
- *     EdgeTable into the Active Edge Table,
- *     leaving them sorted by smaller x coordinate.
- *
- */
-
-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---> ...
- *
- */
-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;
-}
-
-/*
- *     InsertionSort
- *
- *     Just a simple insertion sort using
- *     pointers and back pointers to sort the Active
- *     Edge Table.
- *
- */
-
-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);
-}
-
-/*
- *     Clean up our act.
- */
-void
-miFreeStorage(ScanLineListBlock *pSLLBlock)
-{
-    ScanLineListBlock   *tmpSLLBlock;
-
-    while (pSLLBlock) 
-    {
-        tmpSLLBlock = pSLLBlock->next;
-        xfree(pSLLBlock);
-        pSLLBlock = tmpSLLBlock;
-    }
-}
+/***********************************************************

+

+Copyright 1987, 1998  The Open Group

+

+Permission to use, copy, modify, distribute, and sell this software and its

+documentation for any purpose is hereby granted without fee, provided that

+the above copyright notice appear in all copies and that both that

+copyright notice and this permission notice appear in supporting

+documentation.

+

+The above copyright notice and this permission notice shall be included in

+all copies or substantial portions of the Software.

+

+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE

+OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN

+AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN

+CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

+

+Except as contained in this notice, the name of The Open Group shall not be

+used in advertising or otherwise to promote the sale, use or other dealings

+in this Software without prior written authorization from The Open Group.

+

+

+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, 

+provided that the above copyright notice appear in all copies and that

+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.  

+

+DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING

+ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL

+DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR

+ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,

+WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,

+ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS

+SOFTWARE.

+

+******************************************************************/

+#ifdef HAVE_DIX_CONFIG_H

+#include <dix-config.h>

+#endif

+

+#include "regionstr.h"

+#include "gc.h"

+#include "miscanfill.h"

+#include "mipoly.h"

+#include "misc.h"	/* MAXINT */

+

+/*

+ *     fillUtils.c

+ *

+ *     Written by Brian Kelleher;  Oct. 1985

+ *

+ *     This module contains all of the utility functions

+ *     needed to scan convert a polygon.

+ *

+ */

+

+/*

+ *     InsertEdgeInET

+ *

+ *     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;

+}

+

+/*

+ *     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.

+ *

+ */

+

+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;

+}

+

+/*

+ *     loadAET

+ *

+ *     This routine moves EdgeTableEntries from the

+ *     EdgeTable into the Active Edge Table,

+ *     leaving them sorted by smaller x coordinate.

+ *

+ */

+

+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---> ...

+ *

+ */

+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;

+}

+

+/*

+ *     InsertionSort

+ *

+ *     Just a simple insertion sort using

+ *     pointers and back pointers to sort the Active

+ *     Edge Table.

+ *

+ */

+

+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);

+}

+

+/*

+ *     Clean up our act.

+ */

+void

+miFreeStorage(ScanLineListBlock *pSLLBlock)

+{

+    ScanLineListBlock   *tmpSLLBlock;

+

+    while (pSLLBlock) 

+    {

+        tmpSLLBlock = pSLLBlock->next;

+        free(pSLLBlock);

+        pSLLBlock = tmpSLLBlock;

+    }

+}