[PATCH 06/23] mi: Fold mispans.c into miwideline.c
Adam Jackson
ajax at redhat.com
Mon Oct 27 12:51:54 PDT 2014
Reviewed-by: Keith Packard <keithp at keithp.com>
Signed-off-by: Adam Jackson <ajax at redhat.com>
---
hw/xfree86/sdksyms.sh | 1 -
mi/Makefile.am | 2 -
mi/mispans.c | 526 --------------------------------------------------
mi/mispans.h | 83 --------
mi/miwideline.c | 518 +++++++++++++++++++++++++++++++++++++++++++++++++
mi/miwideline.h | 1 -
6 files changed, 518 insertions(+), 613 deletions(-)
delete mode 100644 mi/mispans.c
delete mode 100644 mi/mispans.h
diff --git a/hw/xfree86/sdksyms.sh b/hw/xfree86/sdksyms.sh
index c2a1942..9c3c02f 100755
--- a/hw/xfree86/sdksyms.sh
+++ b/hw/xfree86/sdksyms.sh
@@ -216,7 +216,6 @@ cat > sdksyms.c << EOF
#include "mizerarc.h"
#include "micoord.h"
#include "mifillarc.h"
-#include "mispans.h"
#include "mistruct.h"
#include "mifpoly.h"
#include "mioverlay.h"
diff --git a/mi/Makefile.am b/mi/Makefile.am
index 4466f69..149dc06 100644
--- a/mi/Makefile.am
+++ b/mi/Makefile.am
@@ -47,8 +47,6 @@ libmi_la_SOURCES = \
mipushpxl.c \
miscanfill.h \
miscrinit.c \
- mispans.c \
- mispans.h \
misprite.c \
misprite.h \
mistruct.h \
diff --git a/mi/mispans.c b/mi/mispans.c
deleted file mode 100644
index 11c8a43..0000000
--- a/mi/mispans.c
+++ /dev/null
@@ -1,526 +0,0 @@
-/***********************************************************
-
-Copyright 1989, 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 1989 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 "misc.h"
-#include "pixmapstr.h"
-#include "gcstruct.h"
-#include "mispans.h"
-
-/*
-
-These routines maintain lists of Spans, in order to implement the
-``touch-each-pixel-once'' rules of wide lines and arcs.
-
-Written by Joel McCormack, Summer 1989.
-
-*/
-
-void
-miInitSpanGroup(SpanGroup * spanGroup)
-{
- spanGroup->size = 0;
- spanGroup->count = 0;
- spanGroup->group = NULL;
- spanGroup->ymin = MAXSHORT;
- spanGroup->ymax = MINSHORT;
-} /* InitSpanGroup */
-
-#define YMIN(spans) (spans->points[0].y)
-#define YMAX(spans) (spans->points[spans->count-1].y)
-
-static void
-miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
-{
- int i, subCount, spansCount;
- int ymin, ymax, xmin, xmax;
- Spans *spans;
- DDXPointPtr subPt, spansPt;
- int *subWid, *spansWid;
- int extra;
-
- ymin = YMIN(sub);
- ymax = YMAX(sub);
- spans = spanGroup->group;
- for (i = spanGroup->count; i; i--, spans++) {
- if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
- subCount = sub->count;
- subPt = sub->points;
- subWid = sub->widths;
- spansCount = spans->count;
- spansPt = spans->points;
- spansWid = spans->widths;
- extra = 0;
- for (;;) {
- while (spansCount && spansPt->y < subPt->y) {
- spansPt++;
- spansWid++;
- spansCount--;
- }
- if (!spansCount)
- break;
- while (subCount && subPt->y < spansPt->y) {
- subPt++;
- subWid++;
- subCount--;
- }
- if (!subCount)
- break;
- if (subPt->y == spansPt->y) {
- xmin = subPt->x;
- xmax = xmin + *subWid;
- if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
- ;
- }
- else if (xmin <= spansPt->x) {
- if (xmax >= spansPt->x + *spansWid) {
- memmove(spansPt, spansPt + 1,
- sizeof *spansPt * (spansCount - 1));
- memmove(spansWid, spansWid + 1,
- sizeof *spansWid * (spansCount - 1));
- spansPt--;
- spansWid--;
- spans->count--;
- extra++;
- }
- else {
- *spansWid = *spansWid - (xmax - spansPt->x);
- spansPt->x = xmax;
- }
- }
- else {
- if (xmax >= spansPt->x + *spansWid) {
- *spansWid = xmin - spansPt->x;
- }
- else {
- if (!extra) {
- DDXPointPtr newPt;
- int *newwid;
-
-#define EXTRA 8
- newPt =
- (DDXPointPtr) realloc(spans->points,
- (spans->count +
- EXTRA) *
- sizeof(DDXPointRec));
- if (!newPt)
- break;
- spansPt = newPt + (spansPt - spans->points);
- spans->points = newPt;
- newwid =
- (int *) realloc(spans->widths,
- (spans->count +
- EXTRA) * sizeof(int));
- if (!newwid)
- break;
- spansWid = newwid + (spansWid - spans->widths);
- spans->widths = newwid;
- extra = EXTRA;
- }
- memmove(spansPt + 1, spansPt,
- sizeof *spansPt * (spansCount));
- memmove(spansWid + 1, spansWid,
- sizeof *spansWid * (spansCount));
- spans->count++;
- extra--;
- *spansWid = xmin - spansPt->x;
- spansWid++;
- spansPt++;
- *spansWid = *spansWid - (xmax - spansPt->x);
- spansPt->x = xmax;
- }
- }
- }
- spansPt++;
- spansWid++;
- spansCount--;
- }
- }
- }
-}
-
-void
-miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
-{
- int ymin, ymax;
- int spansCount;
-
- spansCount = spans->count;
- if (spansCount > 0) {
- if (spanGroup->size == spanGroup->count) {
- spanGroup->size = (spanGroup->size + 8) * 2;
- spanGroup->group = (Spans *)
- realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
- }
-
- spanGroup->group[spanGroup->count] = *spans;
- (spanGroup->count)++;
- ymin = spans->points[0].y;
- if (ymin < spanGroup->ymin)
- spanGroup->ymin = ymin;
- ymax = spans->points[spansCount - 1].y;
- if (ymax > spanGroup->ymax)
- spanGroup->ymax = ymax;
- if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
- miSubtractSpans(otherGroup, spans);
- }
- }
- else {
- free(spans->points);
- free(spans->widths);
- }
-} /* AppendSpans */
-
-void
-miFreeSpanGroup(SpanGroup * spanGroup)
-{
- free(spanGroup->group);
-}
-
-static void
-QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
-{
- int x;
- int i, j, m;
- DDXPointPtr r;
-
-/* Always called with numSpans > 1 */
-/* Sorts only by x, as all y should be the same */
-
-#define ExchangeSpans(a, b) \
-{ \
- DDXPointRec tpt; \
- int tw; \
- \
- tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
- tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
-}
-
- do {
- if (numSpans < 9) {
- /* Do insertion sort */
- int xprev;
-
- xprev = points[0].x;
- i = 1;
- do { /* while i != numSpans */
- x = points[i].x;
- if (xprev > x) {
- /* points[i] is out of order. Move into proper location. */
- DDXPointRec tpt;
- int tw, k;
-
- for (j = 0; x >= points[j].x; j++) {
- }
- tpt = points[i];
- tw = widths[i];
- for (k = i; k != j; k--) {
- points[k] = points[k - 1];
- widths[k] = widths[k - 1];
- }
- points[j] = tpt;
- widths[j] = tw;
- x = points[i].x;
- } /* if out of order */
- xprev = x;
- i++;
- } while (i != numSpans);
- return;
- }
-
- /* Choose partition element, stick in location 0 */
- m = numSpans / 2;
- if (points[m].x > points[0].x)
- ExchangeSpans(m, 0);
- if (points[m].x > points[numSpans - 1].x)
- ExchangeSpans(m, numSpans - 1);
- if (points[m].x > points[0].x)
- ExchangeSpans(m, 0);
- x = points[0].x;
-
- /* Partition array */
- i = 0;
- j = numSpans;
- do {
- r = &(points[i]);
- do {
- r++;
- i++;
- } while (i != numSpans && r->x < x);
- r = &(points[j]);
- do {
- r--;
- j--;
- } while (x < r->x);
- if (i < j)
- ExchangeSpans(i, j);
- } while (i < j);
-
- /* Move partition element back to middle */
- ExchangeSpans(0, j);
-
- /* Recurse */
- if (numSpans - j - 1 > 1)
- QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
- numSpans = j;
- } while (numSpans > 1);
-} /* QuickSortSpans */
-
-static int
-UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
-{
- int newx1, newx2, oldpt, i, y;
- DDXPointRec *oldPoints;
- int *oldWidths;
- int *startNewWidths;
-
-/* Always called with numSpans > 1 */
-/* Uniquify the spans, and stash them into newPoints and newWidths. Return the
- number of unique spans. */
-
- startNewWidths = newWidths;
-
- oldPoints = spans->points;
- oldWidths = spans->widths;
-
- y = oldPoints->y;
- newx1 = oldPoints->x;
- newx2 = newx1 + *oldWidths;
-
- for (i = spans->count - 1; i != 0; i--) {
- oldPoints++;
- oldWidths++;
- oldpt = oldPoints->x;
- if (oldpt > newx2) {
- /* Write current span, start a new one */
- newPoints->x = newx1;
- newPoints->y = y;
- *newWidths = newx2 - newx1;
- newPoints++;
- newWidths++;
- newx1 = oldpt;
- newx2 = oldpt + *oldWidths;
- }
- else {
- /* extend current span, if old extends beyond new */
- oldpt = oldpt + *oldWidths;
- if (oldpt > newx2)
- newx2 = oldpt;
- }
- } /* for */
-
- /* Write final span */
- newPoints->x = newx1;
- *newWidths = newx2 - newx1;
- newPoints->y = y;
-
- return (newWidths - startNewWidths) + 1;
-} /* UniquifySpansX */
-
-static void
-miDisposeSpanGroup(SpanGroup * spanGroup)
-{
- int i;
- Spans *spans;
-
- for (i = 0; i < spanGroup->count; i++) {
- spans = spanGroup->group + i;
- free(spans->points);
- free(spans->widths);
- }
-}
-
-void
-miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
-{
- int i;
- Spans *spans;
- Spans *yspans;
- int *ysizes;
- int ymin, ylength;
-
- /* Outgoing spans for one big call to FillSpans */
- DDXPointPtr points;
- int *widths;
- int count;
-
- if (spanGroup->count == 0)
- return;
-
- if (spanGroup->count == 1) {
- /* Already should be sorted, unique */
- spans = spanGroup->group;
- (*pGC->ops->FillSpans)
- (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
- free(spans->points);
- free(spans->widths);
- }
- else {
- /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
- /* This seems to be the fastest thing to do. I've tried sorting on
- both x and y at the same time rather than creating into all those
- y buckets, but it was somewhat slower. */
-
- ymin = spanGroup->ymin;
- ylength = spanGroup->ymax - ymin + 1;
-
- /* Allocate Spans for y buckets */
- yspans = malloc(ylength * sizeof(Spans));
- ysizes = malloc(ylength * sizeof(int));
-
- if (!yspans || !ysizes) {
- free(yspans);
- free(ysizes);
- miDisposeSpanGroup(spanGroup);
- return;
- }
-
- for (i = 0; i != ylength; i++) {
- ysizes[i] = 0;
- yspans[i].count = 0;
- yspans[i].points = NULL;
- yspans[i].widths = NULL;
- }
-
- /* Go through every single span and put it into the correct bucket */
- count = 0;
- for (i = 0, spans = spanGroup->group;
- i != spanGroup->count; i++, spans++) {
- int index;
- int j;
-
- for (j = 0, points = spans->points, widths = spans->widths;
- j != spans->count; j++, points++, widths++) {
- index = points->y - ymin;
- if (index >= 0 && index < ylength) {
- Spans *newspans = &(yspans[index]);
-
- if (newspans->count == ysizes[index]) {
- DDXPointPtr newpoints;
- int *newwidths;
-
- ysizes[index] = (ysizes[index] + 8) * 2;
- newpoints = (DDXPointPtr) realloc(newspans->points,
- ysizes[index] *
- sizeof(DDXPointRec));
- newwidths =
- (int *) realloc(newspans->widths,
- ysizes[index] * sizeof(int));
- if (!newpoints || !newwidths) {
- for (i = 0; i < ylength; i++) {
- free(yspans[i].points);
- free(yspans[i].widths);
- }
- free(yspans);
- free(ysizes);
- free(newpoints);
- free(newwidths);
- miDisposeSpanGroup(spanGroup);
- return;
- }
- newspans->points = newpoints;
- newspans->widths = newwidths;
- }
- newspans->points[newspans->count] = *points;
- newspans->widths[newspans->count] = *widths;
- (newspans->count)++;
- } /* if y value of span in range */
- } /* for j through spans */
- count += spans->count;
- free(spans->points);
- spans->points = NULL;
- free(spans->widths);
- spans->widths = NULL;
- } /* for i thorough Spans */
-
- /* Now sort by x and uniquify each bucket into the final array */
- points = malloc(count * sizeof(DDXPointRec));
- widths = malloc(count * sizeof(int));
- if (!points || !widths) {
- for (i = 0; i < ylength; i++) {
- free(yspans[i].points);
- free(yspans[i].widths);
- }
- free(yspans);
- free(ysizes);
- free(points);
- free(widths);
- return;
- }
- count = 0;
- for (i = 0; i != ylength; i++) {
- int ycount = yspans[i].count;
-
- if (ycount > 0) {
- if (ycount > 1) {
- QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
- count += UniquifySpansX
- (&(yspans[i]), &(points[count]), &(widths[count]));
- }
- else {
- points[count] = yspans[i].points[0];
- widths[count] = yspans[i].widths[0];
- count++;
- }
- free(yspans[i].points);
- free(yspans[i].widths);
- }
- }
-
- (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
- free(points);
- free(widths);
- free(yspans);
- free(ysizes); /* use (DE)xalloc for these? */
- }
-
- spanGroup->count = 0;
- spanGroup->ymin = MAXSHORT;
- spanGroup->ymax = MINSHORT;
-}
diff --git a/mi/mispans.h b/mi/mispans.h
deleted file mode 100644
index 7c3fcef..0000000
--- a/mi/mispans.h
+++ /dev/null
@@ -1,83 +0,0 @@
-/***********************************************************
-
-Copyright 1989, 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 1989 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.
-
-******************************************************************/
-
-#ifndef MISPANS_H
-#define MISPANS_H
-
-typedef struct {
- int count; /* number of spans */
- DDXPointPtr points; /* pointer to list of start points */
- int *widths; /* pointer to list of widths */
-} Spans;
-
-typedef struct {
- int size; /* Total number of *Spans allocated */
- int count; /* Number of *Spans actually in group */
- Spans *group; /* List of Spans */
- int ymin, ymax; /* Min, max y values encountered */
-} SpanGroup;
-
-/* Initialize SpanGroup. MUST BE DONE before use. */
-extern void miInitSpanGroup(SpanGroup * /*spanGroup */);
-
-/* Add a Spans to a SpanGroup. The spans MUST BE in y-sorted order */
-extern void miAppendSpans(SpanGroup * /*spanGroup */ ,
- SpanGroup * /*otherGroup */ ,
- Spans * /*spans */);
-
-/* Paint a span group, insuring that each pixel is painted at most once */
-extern void miFillUniqueSpanGroup(DrawablePtr /*pDraw */ ,
- GCPtr /*pGC */ ,
- SpanGroup * /*spanGroup */);
-
-/* Free up data in a span group. MUST BE DONE or you'll suffer memory leaks */
-extern void miFreeSpanGroup(SpanGroup * /*spanGroup */);
-
-/* Rops which must use span groups */
-#define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
-#define miSpansEasyRop(rop) (!miSpansCarefulRop(rop))
-
-#endif /* MISPANS_H */
diff --git a/mi/miwideline.c b/mi/miwideline.c
index 295a05a..452d74f 100644
--- a/mi/miwideline.c
+++ b/mi/miwideline.c
@@ -24,6 +24,25 @@ 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 1989 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.
*/
/* Author: Keith Packard, MIT X Consortium */
@@ -52,6 +71,505 @@ from The Open Group.
#include "miwideline.h"
#include "mi.h"
+#if 0
+#ifdef HAVE_DIX_CONFIG_H
+#include <dix-config.h>
+#endif
+
+#include "misc.h"
+#include "pixmapstr.h"
+#include "gcstruct.h"
+#endif
+
+typedef struct {
+ int count; /* number of spans */
+ DDXPointPtr points; /* pointer to list of start points */
+ int *widths; /* pointer to list of widths */
+} Spans;
+
+typedef struct {
+ int size; /* Total number of *Spans allocated */
+ int count; /* Number of *Spans actually in group */
+ Spans *group; /* List of Spans */
+ int ymin, ymax; /* Min, max y values encountered */
+} SpanGroup;
+
+/* Rops which must use span groups */
+#define miSpansCarefulRop(rop) (((rop) & 0xc) == 0x8 || ((rop) & 0x3) == 0x2)
+#define miSpansEasyRop(rop) (!miSpansCarefulRop(rop))
+
+/*
+
+These routines maintain lists of Spans, in order to implement the
+``touch-each-pixel-once'' rules of wide lines and arcs.
+
+Written by Joel McCormack, Summer 1989.
+
+*/
+
+static void
+miInitSpanGroup(SpanGroup * spanGroup)
+{
+ spanGroup->size = 0;
+ spanGroup->count = 0;
+ spanGroup->group = NULL;
+ spanGroup->ymin = MAXSHORT;
+ spanGroup->ymax = MINSHORT;
+} /* InitSpanGroup */
+
+#define YMIN(spans) (spans->points[0].y)
+#define YMAX(spans) (spans->points[spans->count-1].y)
+
+static void
+miSubtractSpans(SpanGroup * spanGroup, Spans * sub)
+{
+ int i, subCount, spansCount;
+ int ymin, ymax, xmin, xmax;
+ Spans *spans;
+ DDXPointPtr subPt, spansPt;
+ int *subWid, *spansWid;
+ int extra;
+
+ ymin = YMIN(sub);
+ ymax = YMAX(sub);
+ spans = spanGroup->group;
+ for (i = spanGroup->count; i; i--, spans++) {
+ if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
+ subCount = sub->count;
+ subPt = sub->points;
+ subWid = sub->widths;
+ spansCount = spans->count;
+ spansPt = spans->points;
+ spansWid = spans->widths;
+ extra = 0;
+ for (;;) {
+ while (spansCount && spansPt->y < subPt->y) {
+ spansPt++;
+ spansWid++;
+ spansCount--;
+ }
+ if (!spansCount)
+ break;
+ while (subCount && subPt->y < spansPt->y) {
+ subPt++;
+ subWid++;
+ subCount--;
+ }
+ if (!subCount)
+ break;
+ if (subPt->y == spansPt->y) {
+ xmin = subPt->x;
+ xmax = xmin + *subWid;
+ if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax) {
+ ;
+ }
+ else if (xmin <= spansPt->x) {
+ if (xmax >= spansPt->x + *spansWid) {
+ memmove(spansPt, spansPt + 1,
+ sizeof *spansPt * (spansCount - 1));
+ memmove(spansWid, spansWid + 1,
+ sizeof *spansWid * (spansCount - 1));
+ spansPt--;
+ spansWid--;
+ spans->count--;
+ extra++;
+ }
+ else {
+ *spansWid = *spansWid - (xmax - spansPt->x);
+ spansPt->x = xmax;
+ }
+ }
+ else {
+ if (xmax >= spansPt->x + *spansWid) {
+ *spansWid = xmin - spansPt->x;
+ }
+ else {
+ if (!extra) {
+ DDXPointPtr newPt;
+ int *newwid;
+
+#define EXTRA 8
+ newPt =
+ (DDXPointPtr) realloc(spans->points,
+ (spans->count +
+ EXTRA) *
+ sizeof(DDXPointRec));
+ if (!newPt)
+ break;
+ spansPt = newPt + (spansPt - spans->points);
+ spans->points = newPt;
+ newwid =
+ (int *) realloc(spans->widths,
+ (spans->count +
+ EXTRA) * sizeof(int));
+ if (!newwid)
+ break;
+ spansWid = newwid + (spansWid - spans->widths);
+ spans->widths = newwid;
+ extra = EXTRA;
+ }
+ memmove(spansPt + 1, spansPt,
+ sizeof *spansPt * (spansCount));
+ memmove(spansWid + 1, spansWid,
+ sizeof *spansWid * (spansCount));
+ spans->count++;
+ extra--;
+ *spansWid = xmin - spansPt->x;
+ spansWid++;
+ spansPt++;
+ *spansWid = *spansWid - (xmax - spansPt->x);
+ spansPt->x = xmax;
+ }
+ }
+ }
+ spansPt++;
+ spansWid++;
+ spansCount--;
+ }
+ }
+ }
+}
+
+static void
+miAppendSpans(SpanGroup * spanGroup, SpanGroup * otherGroup, Spans * spans)
+{
+ int ymin, ymax;
+ int spansCount;
+
+ spansCount = spans->count;
+ if (spansCount > 0) {
+ if (spanGroup->size == spanGroup->count) {
+ spanGroup->size = (spanGroup->size + 8) * 2;
+ spanGroup->group = (Spans *)
+ realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
+ }
+
+ spanGroup->group[spanGroup->count] = *spans;
+ (spanGroup->count)++;
+ ymin = spans->points[0].y;
+ if (ymin < spanGroup->ymin)
+ spanGroup->ymin = ymin;
+ ymax = spans->points[spansCount - 1].y;
+ if (ymax > spanGroup->ymax)
+ spanGroup->ymax = ymax;
+ if (otherGroup && otherGroup->ymin < ymax && ymin < otherGroup->ymax) {
+ miSubtractSpans(otherGroup, spans);
+ }
+ }
+ else {
+ free(spans->points);
+ free(spans->widths);
+ }
+} /* AppendSpans */
+
+static void
+miFreeSpanGroup(SpanGroup * spanGroup)
+{
+ free(spanGroup->group);
+}
+
+static void
+QuickSortSpansX(DDXPointRec points[], int widths[], int numSpans)
+{
+ int x;
+ int i, j, m;
+ DDXPointPtr r;
+
+/* Always called with numSpans > 1 */
+/* Sorts only by x, as all y should be the same */
+
+#define ExchangeSpans(a, b) \
+{ \
+ DDXPointRec tpt; \
+ int tw; \
+ \
+ tpt = points[a]; points[a] = points[b]; points[b] = tpt; \
+ tw = widths[a]; widths[a] = widths[b]; widths[b] = tw; \
+}
+
+ do {
+ if (numSpans < 9) {
+ /* Do insertion sort */
+ int xprev;
+
+ xprev = points[0].x;
+ i = 1;
+ do { /* while i != numSpans */
+ x = points[i].x;
+ if (xprev > x) {
+ /* points[i] is out of order. Move into proper location. */
+ DDXPointRec tpt;
+ int tw, k;
+
+ for (j = 0; x >= points[j].x; j++) {
+ }
+ tpt = points[i];
+ tw = widths[i];
+ for (k = i; k != j; k--) {
+ points[k] = points[k - 1];
+ widths[k] = widths[k - 1];
+ }
+ points[j] = tpt;
+ widths[j] = tw;
+ x = points[i].x;
+ } /* if out of order */
+ xprev = x;
+ i++;
+ } while (i != numSpans);
+ return;
+ }
+
+ /* Choose partition element, stick in location 0 */
+ m = numSpans / 2;
+ if (points[m].x > points[0].x)
+ ExchangeSpans(m, 0);
+ if (points[m].x > points[numSpans - 1].x)
+ ExchangeSpans(m, numSpans - 1);
+ if (points[m].x > points[0].x)
+ ExchangeSpans(m, 0);
+ x = points[0].x;
+
+ /* Partition array */
+ i = 0;
+ j = numSpans;
+ do {
+ r = &(points[i]);
+ do {
+ r++;
+ i++;
+ } while (i != numSpans && r->x < x);
+ r = &(points[j]);
+ do {
+ r--;
+ j--;
+ } while (x < r->x);
+ if (i < j)
+ ExchangeSpans(i, j);
+ } while (i < j);
+
+ /* Move partition element back to middle */
+ ExchangeSpans(0, j);
+
+ /* Recurse */
+ if (numSpans - j - 1 > 1)
+ QuickSortSpansX(&points[j + 1], &widths[j + 1], numSpans - j - 1);
+ numSpans = j;
+ } while (numSpans > 1);
+} /* QuickSortSpans */
+
+static int
+UniquifySpansX(Spans * spans, DDXPointRec * newPoints, int *newWidths)
+{
+ int newx1, newx2, oldpt, i, y;
+ DDXPointRec *oldPoints;
+ int *oldWidths;
+ int *startNewWidths;
+
+/* Always called with numSpans > 1 */
+/* Uniquify the spans, and stash them into newPoints and newWidths. Return the
+ number of unique spans. */
+
+ startNewWidths = newWidths;
+
+ oldPoints = spans->points;
+ oldWidths = spans->widths;
+
+ y = oldPoints->y;
+ newx1 = oldPoints->x;
+ newx2 = newx1 + *oldWidths;
+
+ for (i = spans->count - 1; i != 0; i--) {
+ oldPoints++;
+ oldWidths++;
+ oldpt = oldPoints->x;
+ if (oldpt > newx2) {
+ /* Write current span, start a new one */
+ newPoints->x = newx1;
+ newPoints->y = y;
+ *newWidths = newx2 - newx1;
+ newPoints++;
+ newWidths++;
+ newx1 = oldpt;
+ newx2 = oldpt + *oldWidths;
+ }
+ else {
+ /* extend current span, if old extends beyond new */
+ oldpt = oldpt + *oldWidths;
+ if (oldpt > newx2)
+ newx2 = oldpt;
+ }
+ } /* for */
+
+ /* Write final span */
+ newPoints->x = newx1;
+ *newWidths = newx2 - newx1;
+ newPoints->y = y;
+
+ return (newWidths - startNewWidths) + 1;
+} /* UniquifySpansX */
+
+static void
+miDisposeSpanGroup(SpanGroup * spanGroup)
+{
+ int i;
+ Spans *spans;
+
+ for (i = 0; i < spanGroup->count; i++) {
+ spans = spanGroup->group + i;
+ free(spans->points);
+ free(spans->widths);
+ }
+}
+
+static void
+miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup * spanGroup)
+{
+ int i;
+ Spans *spans;
+ Spans *yspans;
+ int *ysizes;
+ int ymin, ylength;
+
+ /* Outgoing spans for one big call to FillSpans */
+ DDXPointPtr points;
+ int *widths;
+ int count;
+
+ if (spanGroup->count == 0)
+ return;
+
+ if (spanGroup->count == 1) {
+ /* Already should be sorted, unique */
+ spans = spanGroup->group;
+ (*pGC->ops->FillSpans)
+ (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
+ free(spans->points);
+ free(spans->widths);
+ }
+ else {
+ /* Yuck. Gross. Radix sort into y buckets, then sort x and uniquify */
+ /* This seems to be the fastest thing to do. I've tried sorting on
+ both x and y at the same time rather than creating into all those
+ y buckets, but it was somewhat slower. */
+
+ ymin = spanGroup->ymin;
+ ylength = spanGroup->ymax - ymin + 1;
+
+ /* Allocate Spans for y buckets */
+ yspans = malloc(ylength * sizeof(Spans));
+ ysizes = malloc(ylength * sizeof(int));
+
+ if (!yspans || !ysizes) {
+ free(yspans);
+ free(ysizes);
+ miDisposeSpanGroup(spanGroup);
+ return;
+ }
+
+ for (i = 0; i != ylength; i++) {
+ ysizes[i] = 0;
+ yspans[i].count = 0;
+ yspans[i].points = NULL;
+ yspans[i].widths = NULL;
+ }
+
+ /* Go through every single span and put it into the correct bucket */
+ count = 0;
+ for (i = 0, spans = spanGroup->group;
+ i != spanGroup->count; i++, spans++) {
+ int index;
+ int j;
+
+ for (j = 0, points = spans->points, widths = spans->widths;
+ j != spans->count; j++, points++, widths++) {
+ index = points->y - ymin;
+ if (index >= 0 && index < ylength) {
+ Spans *newspans = &(yspans[index]);
+
+ if (newspans->count == ysizes[index]) {
+ DDXPointPtr newpoints;
+ int *newwidths;
+
+ ysizes[index] = (ysizes[index] + 8) * 2;
+ newpoints = (DDXPointPtr) realloc(newspans->points,
+ ysizes[index] *
+ sizeof(DDXPointRec));
+ newwidths =
+ (int *) realloc(newspans->widths,
+ ysizes[index] * sizeof(int));
+ if (!newpoints || !newwidths) {
+ for (i = 0; i < ylength; i++) {
+ free(yspans[i].points);
+ free(yspans[i].widths);
+ }
+ free(yspans);
+ free(ysizes);
+ free(newpoints);
+ free(newwidths);
+ miDisposeSpanGroup(spanGroup);
+ return;
+ }
+ newspans->points = newpoints;
+ newspans->widths = newwidths;
+ }
+ newspans->points[newspans->count] = *points;
+ newspans->widths[newspans->count] = *widths;
+ (newspans->count)++;
+ } /* if y value of span in range */
+ } /* for j through spans */
+ count += spans->count;
+ free(spans->points);
+ spans->points = NULL;
+ free(spans->widths);
+ spans->widths = NULL;
+ } /* for i thorough Spans */
+
+ /* Now sort by x and uniquify each bucket into the final array */
+ points = malloc(count * sizeof(DDXPointRec));
+ widths = malloc(count * sizeof(int));
+ if (!points || !widths) {
+ for (i = 0; i < ylength; i++) {
+ free(yspans[i].points);
+ free(yspans[i].widths);
+ }
+ free(yspans);
+ free(ysizes);
+ free(points);
+ free(widths);
+ return;
+ }
+ count = 0;
+ for (i = 0; i != ylength; i++) {
+ int ycount = yspans[i].count;
+
+ if (ycount > 0) {
+ if (ycount > 1) {
+ QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
+ count += UniquifySpansX
+ (&(yspans[i]), &(points[count]), &(widths[count]));
+ }
+ else {
+ points[count] = yspans[i].points[0];
+ widths[count] = yspans[i].widths[0];
+ count++;
+ }
+ free(yspans[i].points);
+ free(yspans[i].widths);
+ }
+ }
+
+ (*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
+ free(points);
+ free(widths);
+ free(yspans);
+ free(ysizes); /* use (DE)xalloc for these? */
+ }
+
+ spanGroup->count = 0;
+ spanGroup->ymin = MAXSHORT;
+ spanGroup->ymax = MINSHORT;
+}
+
static Bool
InitSpans(Spans * spans, size_t nspans)
{
diff --git a/mi/miwideline.h b/mi/miwideline.h
index a9f2740..88bc3d6 100644
--- a/mi/miwideline.h
+++ b/mi/miwideline.h
@@ -28,7 +28,6 @@ from The Open Group.
/* Author: Keith Packard, MIT X Consortium */
-#include "mispans.h"
#include "mifpoly.h" /* for ICEIL */
/*
--
1.9.3
More information about the xorg-devel
mailing list