1/***********************************************************
2
3Copyright 1989, 1998  The Open Group
4
5Permission to use, copy, modify, distribute, and sell this software and its
6documentation for any purpose is hereby granted without fee, provided that
7the above copyright notice appear in all copies and that both that
8copyright notice and this permission notice appear in supporting
9documentation.
10
11The above copyright notice and this permission notice shall be included in
12all copies or substantial portions of the Software.
13
14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
18AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
19CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
20
21Except as contained in this notice, the name of The Open Group shall not be
22used in advertising or otherwise to promote the sale, use or other dealings
23in this Software without prior written authorization from The Open Group.
24
25
26Copyright 1989 by Digital Equipment Corporation, Maynard, Massachusetts.
27
28                        All Rights Reserved
29
30Permission to use, copy, modify, and distribute this software and its
31documentation for any purpose and without fee is hereby granted,
32provided that the above copyright notice appear in all copies and that
33both that copyright notice and this permission notice appear in
34supporting documentation, and that the name of Digital not be
35used in advertising or publicity pertaining to distribution of the
36software without specific, written prior permission.
37
38DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
39ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
40DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
41ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
42WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
43ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
44SOFTWARE.
45
46******************************************************************/
47
48
49#ifdef HAVE_DIX_CONFIG_H
50#include <dix-config.h>
51#endif
52
53#include "misc.h"
54#include "pixmapstr.h"
55#include "gcstruct.h"
56#include "mispans.h"
57
58/*
59
60These routines maintain lists of Spans, in order to implement the
61``touch-each-pixel-once'' rules of wide lines and arcs.
62
63Written by Joel McCormack, Summer 1989.
64
65*/
66
67
68void miInitSpanGroup(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
80static void miSubtractSpans (SpanGroup *spanGroup, Spans *sub)
81{
82    int		i, subCount, spansCount;
83    int		ymin, ymax, xmin, xmax;
84    Spans	*spans;
85    DDXPointPtr	subPt, spansPt;
86    int		*subWid, *spansWid;
87    int		extra;
88
89    ymin = YMIN(sub);
90    ymax = YMAX(sub);
91    spans = spanGroup->group;
92    for (i = spanGroup->count; i; i--, spans++) {
93	if (YMIN(spans) <= ymax && ymin <= YMAX(spans)) {
94	    subCount = sub->count;
95	    subPt = sub->points;
96	    subWid = sub->widths;
97	    spansCount = spans->count;
98	    spansPt = spans->points;
99	    spansWid = spans->widths;
100	    extra = 0;
101	    for (;;)
102 	    {
103		while (spansCount && spansPt->y < subPt->y)
104		{
105		    spansPt++;  spansWid++; spansCount--;
106		}
107		if (!spansCount)
108		    break;
109		while (subCount && subPt->y < spansPt->y)
110		{
111		    subPt++;	subWid++;   subCount--;
112		}
113		if (!subCount)
114		    break;
115		if (subPt->y == spansPt->y)
116		{
117		    xmin = subPt->x;
118		    xmax = xmin + *subWid;
119		    if (xmin >= spansPt->x + *spansWid || spansPt->x >= xmax)
120		    {
121			;
122		    }
123		    else if (xmin <= spansPt->x)
124		    {
125			if (xmax >= spansPt->x + *spansWid)
126			{
127			    memmove (spansPt, spansPt + 1, sizeof *spansPt * (spansCount - 1));
128			    memmove (spansWid, spansWid + 1, sizeof *spansWid * (spansCount - 1));
129			    spansPt--;
130			    spansWid--;
131			    spans->count--;
132			    extra++;
133			}
134			else
135			{
136			    *spansWid = *spansWid - (xmax - spansPt->x);
137			    spansPt->x = xmax;
138			}
139		    }
140		    else
141		    {
142			if (xmax >= spansPt->x + *spansWid)
143			{
144			    *spansWid = xmin - spansPt->x;
145			}
146			else
147			{
148			    if (!extra) {
149				DDXPointPtr newPt;
150				int	    *newwid;
151
152#define EXTRA 8
153				newPt = (DDXPointPtr) realloc(spans->points, (spans->count + EXTRA) * sizeof (DDXPointRec));
154				if (!newPt)
155				    break;
156				spansPt = newPt + (spansPt - spans->points);
157				spans->points = newPt;
158				newwid = (int *) realloc(spans->widths, (spans->count + EXTRA) * sizeof (int));
159				if (!newwid)
160				    break;
161				spansWid = newwid + (spansWid - spans->widths);
162				spans->widths = newwid;
163				extra = EXTRA;
164			    }
165			    memmove (spansPt + 1, spansPt, sizeof *spansPt * (spansCount));
166			    memmove (spansWid + 1, spansWid, sizeof *spansWid * (spansCount));
167			    spans->count++;
168			    extra--;
169			    *spansWid = xmin - spansPt->x;
170			    spansWid++;
171			    spansPt++;
172			    *spansWid = *spansWid - (xmax - spansPt->x);
173			    spansPt->x = xmax;
174			}
175		    }
176		}
177		spansPt++;  spansWid++; spansCount--;
178	    }
179	}
180    }
181}
182
183void miAppendSpans(SpanGroup *spanGroup, SpanGroup *otherGroup, Spans *spans)
184{
185    int ymin, ymax;
186    int spansCount;
187
188    spansCount = spans->count;
189    if (spansCount > 0) {
190	if (spanGroup->size == spanGroup->count) {
191	    spanGroup->size = (spanGroup->size + 8) * 2;
192	    spanGroup->group = (Spans *)
193		realloc(spanGroup->group, sizeof(Spans) * spanGroup->size);
194	 }
195
196	spanGroup->group[spanGroup->count] = *spans;
197	(spanGroup->count)++;
198	ymin = spans->points[0].y;
199	if (ymin < spanGroup->ymin) spanGroup->ymin = ymin;
200	ymax = spans->points[spansCount - 1].y;
201	if (ymax > spanGroup->ymax) spanGroup->ymax = ymax;
202	if (otherGroup &&
203	    otherGroup->ymin < ymax &&
204	    ymin < otherGroup->ymax)
205	{
206	    miSubtractSpans (otherGroup, spans);
207	}
208    }
209    else
210    {
211	free(spans->points);
212	free(spans->widths);
213    }
214} /* AppendSpans */
215
216void miFreeSpanGroup(SpanGroup *spanGroup)
217{
218    free(spanGroup->group);
219}
220
221static void QuickSortSpansX(
222    DDXPointRec points[],
223    int		widths[],
224    int		numSpans )
225{
226    int	    		x;
227    int	    		i, j, m;
228    DDXPointPtr 	r;
229
230/* Always called with numSpans > 1 */
231/* Sorts only by x, as all y should be the same */
232
233#define ExchangeSpans(a, b)				    \
234{							    \
235    DDXPointRec 	tpt;				    \
236    int    		tw;				    \
237							    \
238    tpt = points[a]; points[a] = points[b]; points[b] = tpt;    \
239    tw = widths[a]; widths[a] = widths[b]; widths[b] = tw;  \
240}
241
242    do {
243	if (numSpans < 9) {
244	    /* Do insertion sort */
245	    int xprev;
246
247	    xprev = points[0].x;
248	    i = 1;
249	    do { /* while i != numSpans */
250		x = points[i].x;
251		if (xprev > x) {
252		    /* points[i] is out of order.  Move into proper location. */
253		    DDXPointRec tpt;
254		    int	    tw, k;
255
256		    for (j = 0; x >= points[j].x; j++) {}
257		    tpt = points[i];
258		    tw  = widths[i];
259		    for (k = i; k != j; k--) {
260			points[k] = points[k-1];
261			widths[k] = widths[k-1];
262		    }
263		    points[j] = tpt;
264		    widths[j] = tw;
265		    x = points[i].x;
266		} /* if out of order */
267		xprev = x;
268		i++;
269	    } while (i != numSpans);
270	    return;
271	}
272
273	/* Choose partition element, stick in location 0 */
274	m = numSpans / 2;
275	if (points[m].x > points[0].x)		ExchangeSpans(m, 0);
276	if (points[m].x > points[numSpans-1].x) ExchangeSpans(m, numSpans-1);
277	if (points[m].x > points[0].x)		ExchangeSpans(m, 0);
278	x = points[0].x;
279
280        /* Partition array */
281        i = 0;
282        j = numSpans;
283        do {
284	    r = &(points[i]);
285	    do {
286		r++;
287		i++;
288            } while (i != numSpans && r->x < x);
289	    r = &(points[j]);
290	    do {
291		r--;
292		j--;
293            } while (x < r->x);
294            if (i < j) ExchangeSpans(i, j);
295        } while (i < j);
296
297        /* Move partition element back to middle */
298        ExchangeSpans(0, j);
299
300	/* Recurse */
301        if (numSpans-j-1 > 1)
302	    QuickSortSpansX(&points[j+1], &widths[j+1], numSpans-j-1);
303        numSpans = j;
304    } while (numSpans > 1);
305} /* QuickSortSpans */
306
307
308static int UniquifySpansX(
309    Spans	    	*spans,
310    DDXPointRec    	*newPoints,
311    int	    		*newWidths )
312{
313    int 		newx1, newx2, oldpt, i, y;
314    DDXPointRec		*oldPoints;
315    int	    		*oldWidths;
316    int			*startNewWidths;
317
318/* Always called with numSpans > 1 */
319/* Uniquify the spans, and stash them into newPoints and newWidths.  Return the
320   number of unique spans. */
321
322
323    startNewWidths = newWidths;
324
325    oldPoints = spans->points;
326    oldWidths = spans->widths;
327
328    y = oldPoints->y;
329    newx1 = oldPoints->x;
330    newx2 = newx1 + *oldWidths;
331
332    for (i = spans->count-1; i != 0; i--) {
333	oldPoints++;
334	oldWidths++;
335	oldpt = oldPoints->x;
336	if (oldpt > newx2) {
337	    /* Write current span, start a new one */
338	    newPoints->x = newx1;
339	    newPoints->y = y;
340	    *newWidths = newx2 - newx1;
341	    newPoints++;
342	    newWidths++;
343	    newx1 = oldpt;
344	    newx2 = oldpt + *oldWidths;
345	} else {
346	    /* extend current span, if old extends beyond new */
347	    oldpt = oldpt + *oldWidths;
348	    if (oldpt > newx2) newx2 = oldpt;
349	}
350    } /* for */
351
352    /* Write final span */
353    newPoints->x = newx1;
354    *newWidths = newx2 - newx1;
355    newPoints->y = y;
356
357    return (newWidths - startNewWidths) + 1;
358} /* UniquifySpansX */
359
360static void
361miDisposeSpanGroup (SpanGroup *spanGroup)
362{
363    int	    i;
364    Spans   *spans;
365
366    for (i = 0; i < spanGroup->count; i++)
367    {
368	spans = spanGroup->group + i;
369	free(spans->points);
370	free(spans->widths);
371    }
372}
373
374void miFillUniqueSpanGroup(DrawablePtr pDraw, GCPtr pGC, SpanGroup *spanGroup)
375{
376    int    		i;
377    Spans  		*spans;
378    Spans  		*yspans;
379    int    		*ysizes;
380    int    		ymin, ylength;
381
382    /* Outgoing spans for one big call to FillSpans */
383    DDXPointPtr    	points;
384    int	    		*widths;
385    int	    		count;
386
387    if (spanGroup->count == 0) return;
388
389    if (spanGroup->count == 1) {
390	/* Already should be sorted, unique */
391	spans = spanGroup->group;
392	(*pGC->ops->FillSpans)
393	    (pDraw, pGC, spans->count, spans->points, spans->widths, TRUE);
394	free(spans->points);
395	free(spans->widths);
396    }
397    else
398    {
399	/* Yuck.  Gross.  Radix sort into y buckets, then sort x and uniquify */
400	/* This seems to be the fastest thing to do.  I've tried sorting on
401	   both x and y at the same time rather than creating into all those
402	   y buckets, but it was somewhat slower. */
403
404	ymin    = spanGroup->ymin;
405	ylength = spanGroup->ymax - ymin + 1;
406
407	/* Allocate Spans for y buckets */
408	yspans = malloc(ylength * sizeof(Spans));
409	ysizes = malloc(ylength * sizeof (int));
410
411	if (!yspans || !ysizes)
412	{
413	    free(yspans);
414	    free(ysizes);
415	    miDisposeSpanGroup (spanGroup);
416	    return;
417	}
418
419	for (i = 0; i != ylength; i++) {
420	    ysizes[i]        = 0;
421	    yspans[i].count  = 0;
422	    yspans[i].points = NULL;
423	    yspans[i].widths = NULL;
424	}
425
426	/* Go through every single span and put it into the correct bucket */
427	count = 0;
428	for (i = 0, spans = spanGroup->group;
429		i != spanGroup->count;
430		i++, spans++) {
431	    int		index;
432	    int		j;
433
434	    for (j = 0, points = spans->points, widths = spans->widths;
435		    j != spans->count;
436		    j++, points++, widths++) {
437		index = points->y - ymin;
438		if (index >= 0 && index < ylength) {
439		    Spans *newspans = &(yspans[index]);
440		    if (newspans->count == ysizes[index]) {
441			DDXPointPtr newpoints;
442			int	    *newwidths;
443			ysizes[index] = (ysizes[index] + 8) * 2;
444			newpoints = (DDXPointPtr) realloc(
445			    newspans->points,
446			    ysizes[index] * sizeof(DDXPointRec));
447			newwidths = (int *) realloc(
448			    newspans->widths,
449			    ysizes[index] * sizeof(int));
450			if (!newpoints || !newwidths)
451			{
452			    int	i;
453
454			    for (i = 0; i < ylength; i++)
455			    {
456				free(yspans[i].points);
457				free(yspans[i].widths);
458			    }
459			    free(yspans);
460			    free(ysizes);
461			    free(newpoints);
462			    free(newwidths);
463			    miDisposeSpanGroup (spanGroup);
464			    return;
465			}
466			newspans->points = newpoints;
467			newspans->widths = newwidths;
468		    }
469		    newspans->points[newspans->count] = *points;
470		    newspans->widths[newspans->count] = *widths;
471		    (newspans->count)++;
472		} /* if y value of span in range */
473	    } /* for j through spans */
474	    count += spans->count;
475	    free(spans->points);
476	    spans->points = NULL;
477	    free(spans->widths);
478	    spans->widths = NULL;
479	} /* for i thorough Spans */
480
481	/* Now sort by x and uniquify each bucket into the final array */
482	points = malloc(count * sizeof(DDXPointRec));
483	widths = malloc(count * sizeof(int));
484	if (!points || !widths)
485	{
486	    int	i;
487
488	    for (i = 0; i < ylength; i++)
489	    {
490		free(yspans[i].points);
491		free(yspans[i].widths);
492	    }
493	    free(yspans);
494	    free(ysizes);
495	    free(points);
496	    free(widths);
497	    return;
498	}
499	count = 0;
500	for (i = 0; i != ylength; i++) {
501	    int ycount = yspans[i].count;
502	    if (ycount > 0) {
503		if (ycount > 1) {
504		    QuickSortSpansX(yspans[i].points, yspans[i].widths, ycount);
505		    count += UniquifySpansX
506			(&(yspans[i]), &(points[count]), &(widths[count]));
507		} else {
508		    points[count] = yspans[i].points[0];
509		    widths[count] = yspans[i].widths[0];
510		    count++;
511		}
512		free(yspans[i].points);
513		free(yspans[i].widths);
514	    }
515	}
516
517	(*pGC->ops->FillSpans) (pDraw, pGC, count, points, widths, TRUE);
518	free(points);
519	free(widths);
520	free(yspans);
521	free(ysizes);		/* use (DE)xalloc for these? */
522    }
523
524    spanGroup->count = 0;
525    spanGroup->ymin = MAXSHORT;
526    spanGroup->ymax = MINSHORT;
527}
528