1/***********************************************************
2
3Copyright 1987, 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 1987 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#ifdef HAVE_DIX_CONFIG_H
48#include <dix-config.h>
49#endif
50
51#include <X11/X.h>
52
53#include "misc.h"
54#include "scrnintstr.h"
55#include "gcstruct.h"
56#include "windowstr.h"
57#include "pixmap.h"
58#include "mi.h"
59#include "miline.h"
60
61/* Draw lineSolid, fillStyle-independent zero width lines.
62 *
63 * Must keep X and Y coordinates in "ints" at least until after they're
64 * translated and clipped to accomodate CoordModePrevious lines with very
65 * large coordinates.
66 *
67 * Draws the same pixels regardless of sign(dx) or sign(dy).
68 *
69 * Ken Whaley
70 *
71 */
72
73/* largest positive value that can fit into a component of a point.
74 * Assumes that the point structure is {type x, y;} where type is
75 * a signed type.
76 */
77#define MAX_COORDINATE ((1 << (((sizeof(DDXPointRec) >> 1) << 3) - 1)) - 1)
78
79#define MI_OUTPUT_POINT(xx, yy)\
80{\
81    if ( !new_span && yy == current_y)\
82    {\
83        if (xx < spans->x)\
84	    spans->x = xx;\
85	++*widths;\
86    }\
87    else\
88    {\
89        ++Nspans;\
90	++spans;\
91	++widths;\
92	spans->x = xx;\
93	spans->y = yy;\
94	*widths = 1;\
95	current_y = yy;\
96        new_span = FALSE;\
97    }\
98}
99
100void
101miZeroLine(
102    DrawablePtr pDraw,
103    GCPtr	pGC,
104    int		mode,		/* Origin or Previous */
105    int		npt,		/* number of points */
106    DDXPointPtr pptInit)
107{
108    int Nspans, current_y = 0;
109    DDXPointPtr ppt;
110    DDXPointPtr pspanInit, spans;
111    int *pwidthInit, *widths, list_len;
112    int xleft, ytop, xright, ybottom;
113    int new_x1, new_y1, new_x2, new_y2;
114    int x = 0, y = 0, x1, y1, x2, y2, xstart, ystart;
115    int oc1, oc2;
116    int result;
117    int pt1_clipped, pt2_clipped = 0;
118    Bool new_span;
119    int signdx, signdy;
120    int clipdx, clipdy;
121    int width, height;
122    int adx, ady;
123    int octant;
124    unsigned int bias = miGetZeroLineBias(pDraw->pScreen);
125    int e, e1, e2, e3;	/* Bresenham error terms */
126    int length;		/* length of lines == # of pixels on major axis */
127
128    xleft   = pDraw->x;
129    ytop    = pDraw->y;
130    xright  = pDraw->x + pDraw->width - 1;
131    ybottom = pDraw->y + pDraw->height - 1;
132
133    if (!pGC->miTranslate)
134    {
135	/* do everything in drawable-relative coordinates */
136	xleft    = 0;
137	ytop     = 0;
138	xright  -= pDraw->x;
139	ybottom -= pDraw->y;
140    }
141
142    /* it doesn't matter whether we're in drawable or screen coordinates,
143     * FillSpans simply cannot take starting coordinates outside of the
144     * range of a DDXPointRec component.
145     */
146    if (xright > MAX_COORDINATE)
147	xright = MAX_COORDINATE;
148    if (ybottom > MAX_COORDINATE)
149	ybottom = MAX_COORDINATE;
150
151    /* since we're clipping to the drawable's boundaries & coordinate
152     * space boundaries, we're guaranteed that the larger of width/height
153     * is the longest span we'll need to output
154     */
155    width = xright - xleft + 1;
156    height = ybottom - ytop + 1;
157    list_len = (height >= width) ? height : width;
158    pspanInit = malloc(list_len * sizeof(DDXPointRec));
159    pwidthInit = malloc(list_len * sizeof(int));
160    if (!pspanInit || !pwidthInit) {
161	free(pspanInit);
162	free(pwidthInit);
163	return;
164    }
165    Nspans = 0;
166    new_span = TRUE;
167    spans  = pspanInit - 1;
168    widths = pwidthInit - 1;
169    ppt = pptInit;
170
171    xstart = ppt->x;
172    ystart = ppt->y;
173    if (pGC->miTranslate)
174    {
175	xstart += pDraw->x;
176	ystart += pDraw->y;
177    }
178
179    /* x2, y2, oc2 copied to x1, y1, oc1 at top of loop to simplify
180     * iteration logic
181     */
182    x2 = xstart;
183    y2 = ystart;
184    oc2 = 0;
185    MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
186
187    while (--npt > 0)
188    {
189	if (Nspans > 0)
190	    (*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
191				   pwidthInit, FALSE);
192	Nspans = 0;
193	new_span = TRUE;
194	spans  = pspanInit - 1;
195	widths = pwidthInit - 1;
196
197	x1  = x2;
198	y1  = y2;
199	oc1 = oc2;
200	++ppt;
201
202	x2 = ppt->x;
203	y2 = ppt->y;
204	if (pGC->miTranslate && (mode != CoordModePrevious))
205	{
206	    x2 += pDraw->x;
207	    y2 += pDraw->y;
208	}
209	else if (mode == CoordModePrevious)
210	{
211	    x2 += x1;
212	    y2 += y1;
213	}
214
215	oc2 = 0;
216	MIOUTCODES(oc2, x2, y2, xleft, ytop, xright, ybottom);
217
218	CalcLineDeltas(x1, y1, x2, y2, adx, ady, signdx, signdy, 1, 1, octant);
219
220	if (adx > ady)
221	{
222	    e1 = ady << 1;
223	    e2 = e1 - (adx << 1);
224	    e  = e1 - adx;
225	    length  = adx;	/* don't draw endpoint in main loop */
226
227	    FIXUP_ERROR(e, octant, bias);
228
229	    new_x1 = x1;
230	    new_y1 = y1;
231	    new_x2 = x2;
232	    new_y2 = y2;
233	    pt1_clipped = 0;
234	    pt2_clipped = 0;
235
236	    if ((oc1 | oc2) != 0)
237	    {
238		result = miZeroClipLine(xleft, ytop, xright, ybottom,
239					&new_x1, &new_y1, &new_x2, &new_y2,
240					adx, ady,
241					&pt1_clipped, &pt2_clipped,
242					octant, bias, oc1, oc2);
243		if (result == -1)
244		    continue;
245
246		length = abs(new_x2 - new_x1);
247
248		/* if we've clipped the endpoint, always draw the full length
249		 * of the segment, because then the capstyle doesn't matter
250		 */
251		if (pt2_clipped)
252		    length++;
253
254		if (pt1_clipped)
255		{
256		    /* must calculate new error terms */
257		    clipdx = abs(new_x1 - x1);
258		    clipdy = abs(new_y1 - y1);
259		    e += (clipdy * e2) + ((clipdx - clipdy) * e1);
260		}
261	    }
262
263	    /* draw the segment */
264
265	    x = new_x1;
266	    y = new_y1;
267
268	    e3 = e2 - e1;
269	    e  = e - e1;
270
271	    while (length--)
272	    {
273		MI_OUTPUT_POINT(x, y);
274		e += e1;
275		if (e >= 0)
276		{
277		    y += signdy;
278		    e += e3;
279		}
280		x += signdx;
281	    }
282	}
283	else    /* Y major line */
284	{
285	    e1 = adx << 1;
286	    e2 = e1 - (ady << 1);
287	    e  = e1 - ady;
288	    length  = ady;	/* don't draw endpoint in main loop */
289
290	    SetYMajorOctant(octant);
291	    FIXUP_ERROR(e, octant, bias);
292
293	    new_x1 = x1;
294	    new_y1 = y1;
295	    new_x2 = x2;
296	    new_y2 = y2;
297	    pt1_clipped = 0;
298	    pt2_clipped = 0;
299
300	    if ((oc1 | oc2) != 0)
301	    {
302		result = miZeroClipLine(xleft, ytop, xright, ybottom,
303					&new_x1, &new_y1, &new_x2, &new_y2,
304					adx, ady,
305					&pt1_clipped, &pt2_clipped,
306					octant, bias, oc1, oc2);
307		if (result == -1)
308		    continue;
309
310		length = abs(new_y2 - new_y1);
311
312		/* if we've clipped the endpoint, always draw the full length
313		 * of the segment, because then the capstyle doesn't matter
314		 */
315		if (pt2_clipped)
316		    length++;
317
318		if (pt1_clipped)
319		{
320		    /* must calculate new error terms */
321		    clipdx = abs(new_x1 - x1);
322		    clipdy = abs(new_y1 - y1);
323		    e += (clipdx * e2) + ((clipdy - clipdx) * e1);
324		}
325	    }
326
327	    /* draw the segment */
328
329	    x = new_x1;
330	    y = new_y1;
331
332	    e3 = e2 - e1;
333	    e  = e - e1;
334
335	    while (length--)
336	    {
337		MI_OUTPUT_POINT(x, y);
338		e += e1;
339		if (e >= 0)
340		{
341		    x += signdx;
342		    e += e3;
343		}
344		y += signdy;
345	    }
346	}
347    }
348
349    /* only do the capnotlast check on the last segment
350     * and only if the endpoint wasn't clipped.  And then, if the last
351     * point is the same as the first point, do not draw it, unless the
352     * line is degenerate
353     */
354    if ( (! pt2_clipped) && (pGC->capStyle != CapNotLast) &&
355		(((xstart != x2) || (ystart != y2)) || (ppt == pptInit + 1)))
356    {
357	MI_OUTPUT_POINT(x, y);
358    }
359
360    if (Nspans > 0)
361	(*pGC->ops->FillSpans)(pDraw, pGC, Nspans, pspanInit,
362			       pwidthInit, FALSE);
363
364    free(pwidthInit);
365    free(pspanInit);
366}
367
368void
369miZeroDashLine(
370            DrawablePtr dst,
371            GCPtr pgc,
372            int mode,
373            int nptInit,		/* number of points in polyline */
374            DDXPointRec *pptInit	/* points in the polyline */
375        )
376{
377    /* XXX kludge until real zero-width dash code is written */
378    pgc->lineWidth = 1;
379    miWideDash (dst, pgc, mode, nptInit, pptInit);
380    pgc->lineWidth = 0;
381}
382