1/*
2 * Copyright © 1998 Keith Packard
3 * Copyright © 2012 Intel Corporation
4 *
5 * Permission to use, copy, modify, distribute, and sell this software and its
6 * documentation for any purpose is hereby granted without fee, provided that
7 * the above copyright notice appear in all copies and that both that
8 * copyright notice and this permission notice appear in supporting
9 * documentation, and that the name of Keith Packard not be used in
10 * advertising or publicity pertaining to distribution of the software without
11 * specific, written prior permission.  Keith Packard makes no
12 * representations about the suitability of this software for any purpose.  It
13 * is provided "as is" without express or implied warranty.
14 *
15 * KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 * INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
17 * EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
18 * CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
19 * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
20 * TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
21 * PERFORMANCE OF THIS SOFTWARE.
22 */
23
24#include <stdlib.h>
25
26#include "fb.h"
27#include "fbclip.h"
28#include <miline.h>
29#include <scrnintstr.h>
30
31#define FbDashDeclare	\
32    unsigned char	*__dash, *__firstDash, *__lastDash
33
34#define FbDashInit(gc,pgc,dashOffset,dashlen,even) {	    \
35    (even) = TRUE;					    \
36    __firstDash = (gc)->dash;				    \
37    __lastDash = __firstDash + (gc)->numInDashList;	    \
38    (dashOffset) %= (pgc)->dashLength;		    \
39							    \
40    __dash = __firstDash;				    \
41    while ((dashOffset) >= ((dashlen) = *__dash)) {	    \
42	(dashOffset) -= (dashlen);			    \
43	(even) = 1-(even);				    \
44	if (++__dash == __lastDash)			    \
45	    __dash = __firstDash;			    \
46    }							    \
47    (dashlen) -= (dashOffset);				    \
48}
49
50#define FbDashNext(dashlen) {				    \
51    if (++__dash == __lastDash)				    \
52	__dash = __firstDash;				    \
53    (dashlen) = *__dash;				    \
54}
55
56/* as numInDashList is always even, this case can skip a test */
57
58#define FbDashNextEven(dashlen) {			    \
59    (dashlen) = *++__dash;				    \
60}
61
62#define FbDashNextOdd(dashlen)	FbDashNext(dashlen)
63
64#define FbDashStep(dashlen,even) {			    \
65    if (!--(dashlen)) {					    \
66	FbDashNext(dashlen);				    \
67	(even) = 1-(even);				    \
68    }							    \
69}
70
71#define fbBresShiftMask(mask,dir,bpp) ((bpp == FB_STIP_UNIT) ? 0 : \
72					((dir < 0) ? FbStipLeft(mask,bpp) : \
73					 FbStipRight(mask,bpp)))
74
75typedef void FbBres(DrawablePtr drawable,
76                    GCPtr gc,
77                    int dashOffset,
78                    int sdx,
79                    int sdy,
80                    int axis, int x, int y, int e, int e1, int e3, int len);
81
82#define BRESSOLID   fbBresSolid8
83#define BRESSOLIDR  fbBresSolidR8
84#define BRESDASH    fbBresDash8
85#define BITS	    BYTE
86#define BITS2	    CARD16
87#define BITS4	    CARD32
88#include "fbsegbits.h"
89#undef BRESSOLID
90#undef BRESSOLIDR
91#undef BRESDASH
92#undef BITS
93#undef BITS2
94#undef BITS4
95
96#define BRESSOLID   fbBresSolid16
97#define BRESSOLIDR  fbBresSolidR16
98#define BRESDASH    fbBresDash16
99#define BITS	    CARD16
100#define BITS2	    CARD32
101#include "fbsegbits.h"
102#undef BRESSOLID
103#undef BRESSOLIDR
104#undef BRESDASH
105#undef BITS
106#undef BITS2
107
108#define BRESSOLID   fbBresSolid32
109#define BRESSOLIDR  fbBresSolidR32
110#define BRESDASH    fbBresDash32
111#define BITS	    CARD32
112#include "fbsegbits.h"
113#undef BRESSOLID
114#undef BRESSOLIDR
115#undef BRESDASH
116#undef BITS
117
118static void
119fbBresSolid(DrawablePtr drawable, GCPtr gc, int dashOffset,
120            int sdx, int sdy, int axis,
121	    int x1, int y1,
122	    int e, int e1, int e3, int len)
123{
124	FbStip *dst;
125	FbStride stride;
126	int bpp;
127	int dx, dy;
128	FbGCPrivPtr pgc = fb_gc(gc);
129	FbStip and = (FbStip) pgc->and;
130	FbStip xor = (FbStip) pgc->xor;
131	FbStip mask, mask0;
132	FbStip bits;
133
134	fbGetStipDrawable(drawable, dst, stride, bpp, dx, dy);
135	dst += ((y1 + dy) * stride);
136	x1 = (x1 + dx) * bpp;
137	dst += x1 >> FB_STIP_SHIFT;
138	x1 &= FB_STIP_MASK;
139	mask0 = FbStipMask(0, bpp);
140	mask = FbStipRight(mask0, x1);
141	if (sdx < 0)
142		mask0 = FbStipRight(mask0, FB_STIP_UNIT - bpp);
143	if (sdy < 0)
144		stride = -stride;
145	if (axis == X_AXIS) {
146		bits = 0;
147		while (len--) {
148			bits |= mask;
149			mask = fbBresShiftMask(mask, sdx, bpp);
150			if (!mask) {
151				WRITE(dst, FbDoMaskRRop(READ(dst), and, xor, bits));
152				bits = 0;
153				dst += sdx;
154				mask = mask0;
155			}
156			e += e1;
157			if (e >= 0) {
158				WRITE(dst, FbDoMaskRRop(READ(dst), and, xor, bits));
159				bits = 0;
160				dst += stride;
161				e += e3;
162			}
163		}
164		if (bits)
165			WRITE(dst, FbDoMaskRRop(READ(dst), and, xor, bits));
166	} else {
167		while (len--) {
168			WRITE(dst, FbDoMaskRRop(READ(dst), and, xor, mask));
169			dst += stride;
170			e += e1;
171			if (e >= 0) {
172				e += e3;
173				mask = fbBresShiftMask(mask, sdx, bpp);
174				if (!mask) {
175					dst += sdx;
176					mask = mask0;
177				}
178			}
179		}
180	}
181}
182
183static void
184fbBresDash(DrawablePtr drawable, GCPtr gc, int dashOffset,
185           int sdx, int sdy, int axis,
186	   int x1, int y1,
187	   int e, int e1, int e3, int len)
188{
189	FbStip *dst;
190	FbStride stride;
191	int bpp;
192	int dx, dy;
193	FbGCPrivPtr pgc = fb_gc(gc);
194	FbStip and = (FbStip) pgc->and;
195	FbStip xor = (FbStip) pgc->xor;
196	FbStip bgand = (FbStip) pgc->bgand;
197	FbStip bgxor = (FbStip) pgc->bgxor;
198	FbStip mask, mask0;
199
200	FbDashDeclare;
201	int dashlen;
202	bool even;
203	bool doOdd;
204
205	fbGetStipDrawable(drawable, dst, stride, bpp, dx, dy);
206	doOdd = gc->lineStyle == LineDoubleDash;
207
208	FbDashInit(gc, pgc, dashOffset, dashlen, even);
209
210	dst += ((y1 + dy) * stride);
211	x1 = (x1 + dx) * bpp;
212	dst += x1 >> FB_STIP_SHIFT;
213	x1 &= FB_STIP_MASK;
214	mask0 = FbStipMask(0, bpp);
215	mask = FbStipRight(mask0, x1);
216	if (sdx < 0)
217		mask0 = FbStipRight(mask0, FB_STIP_UNIT - bpp);
218	if (sdy < 0)
219		stride = -stride;
220	while (len--) {
221		if (even)
222			WRITE(dst, FbDoMaskRRop(READ(dst), and, xor, mask));
223		else if (doOdd)
224			WRITE(dst, FbDoMaskRRop(READ(dst), bgand, bgxor, mask));
225		if (axis == X_AXIS) {
226			mask = fbBresShiftMask(mask, sdx, bpp);
227			if (!mask) {
228				dst += sdx;
229				mask = mask0;
230			}
231			e += e1;
232			if (e >= 0) {
233				dst += stride;
234				e += e3;
235			}
236		} else {
237			dst += stride;
238			e += e1;
239			if (e >= 0) {
240				e += e3;
241				mask = fbBresShiftMask(mask, sdx, bpp);
242				if (!mask) {
243					dst += sdx;
244					mask = mask0;
245				}
246			}
247		}
248		FbDashStep(dashlen, even);
249	}
250}
251
252static void
253fbBresFill(DrawablePtr drawable, GCPtr gc, int dashOffset,
254           int sdx, int sdy, int axis,
255	   int x1, int y1,
256	   int e, int e1, int e3, int len)
257{
258	while (len--) {
259		fbFill(drawable, gc, x1, y1, 1, 1);
260		if (axis == X_AXIS) {
261			x1 += sdx;
262			e += e1;
263			if (e >= 0) {
264				e += e3;
265				y1 += sdy;
266			}
267		} else {
268			y1 += sdy;
269			e += e1;
270			if (e >= 0) {
271				e += e3;
272				x1 += sdx;
273			}
274		}
275	}
276}
277
278static void
279fbSetFg(DrawablePtr drawable, GCPtr gc, Pixel fg)
280{
281	if (fg != gc->fgPixel) {
282		gc->fgPixel = fg;
283		fbValidateGC(gc, GCForeground, drawable);
284	}
285}
286
287static void
288fbBresFillDash(DrawablePtr drawable,
289               GCPtr gc,
290               int dashOffset,
291               int sdx,
292               int sdy,
293               int axis, int x1, int y1, int e, int e1, int e3, int len)
294{
295	FbGCPrivPtr pgc = fb_gc(gc);
296
297	FbDashDeclare;
298	int dashlen;
299	bool even;
300	bool doOdd;
301	bool doBg;
302	Pixel fg, bg;
303
304	fg = gc->fgPixel;
305	bg = gc->bgPixel;
306
307	/* whether to fill the odd dashes */
308	doOdd = gc->lineStyle == LineDoubleDash;
309	/* whether to switch fg to bg when filling odd dashes */
310	doBg = doOdd && (gc->fillStyle == FillSolid ||
311			 gc->fillStyle == FillStippled);
312
313	/* compute current dash position */
314	FbDashInit(gc, pgc, dashOffset, dashlen, even);
315
316	while (len--) {
317		if (even || doOdd) {
318			if (doBg) {
319				if (even)
320					fbSetFg(drawable, gc, fg);
321				else
322					fbSetFg(drawable, gc, bg);
323			}
324			fbFill(drawable, gc, x1, y1, 1, 1);
325		}
326		if (axis == X_AXIS) {
327			x1 += sdx;
328			e += e1;
329			if (e >= 0) {
330				e += e3;
331				y1 += sdy;
332			}
333		} else {
334			y1 += sdy;
335			e += e1;
336			if (e >= 0) {
337				e += e3;
338				x1 += sdx;
339			}
340		}
341		FbDashStep(dashlen, even);
342	}
343	if (doBg)
344		fbSetFg(drawable, gc, fg);
345}
346
347static FbBres *
348fbSelectBres(DrawablePtr drawable, GCPtr gc)
349{
350	FbGCPrivPtr pgc = fb_gc(gc);
351	int bpp = drawable->bitsPerPixel;
352	FbBres *bres;
353
354	DBG(("%s: line=%d, fill=%d, and=%lx, bgand=%lx\n",
355	     __FUNCTION__, gc->lineStyle, gc->fillStyle,
356	     (long)pgc->and, (long)pgc->bgand));
357	assert(gc->lineWidth == 0);
358
359	if (gc->lineStyle == LineSolid) {
360		bres = fbBresFill;
361		if (gc->fillStyle == FillSolid) {
362			bres = fbBresSolid;
363			if (pgc->and == 0) {
364				switch (bpp) {
365				case 8:
366					bres = fbBresSolid8;
367					break;
368				case 16:
369					bres = fbBresSolid16;
370					break;
371				case 32:
372					bres = fbBresSolid32;
373					break;
374				}
375			} else {
376				switch (bpp) {
377				case 8:
378					bres = fbBresSolidR8;
379					break;
380				case 16:
381					bres = fbBresSolidR16;
382					break;
383				case 32:
384					bres = fbBresSolidR32;
385					break;
386				}
387			}
388		}
389	} else {
390		bres = fbBresFillDash;
391		if (gc->fillStyle == FillSolid) {
392			bres = fbBresDash;
393			if (pgc->and == 0 &&
394			    (gc->lineStyle == LineOnOffDash || pgc->bgand == 0)) {
395				switch (bpp) {
396				case 8:
397					bres = fbBresDash8;
398					break;
399				case 16:
400					bres = fbBresDash16;
401					break;
402				case 32:
403					bres = fbBresDash32;
404					break;
405				}
406			}
407		}
408	}
409	return bres;
410}
411
412struct fbSegment {
413	FbBres *bres;
414	bool drawLast;
415	int *dashOffset;
416	int x1, y1, x2, y2;
417};
418
419static void
420_fbSegment(DrawablePtr drawable, GCPtr gc, const BoxRec *b, void *_data)
421{
422	struct fbSegment *data = _data;
423	const unsigned int bias = miGetZeroLineBias(drawable->pScreen);
424	int adx, ady;               /* abs values of dx and dy */
425	int sdx, sdy;               /* sign of dx and dy */
426	int e, e1, e2, e3;          /* bresenham error and increments */
427	int len, axis, octant;
428	int dashoff, doff;
429	unsigned int oc1, oc2;
430
431	DBG(("%s box=(%d, %d),(%d, %d)\n",
432	     __FUNCTION__, b->x1, b->y1, b->x2, b->y2));
433
434	CalcLineDeltas(data->x1, data->y1, data->x2, data->y2,
435		       adx, ady, sdx, sdy, 1, 1, octant);
436
437	if (adx > ady) {
438		axis = X_AXIS;
439		e1 = ady << 1;
440		e2 = e1 - (adx << 1);
441		e = e1 - adx;
442		len = adx;
443	} else {
444		axis = Y_AXIS;
445		e1 = adx << 1;
446		e2 = e1 - (ady << 1);
447		e = e1 - ady;
448		SetYMajorOctant(octant);
449		len = ady;
450	}
451
452	FIXUP_ERROR(e, octant, bias);
453
454	/*
455	 * Adjust error terms to compare against zero
456	 */
457	e3 = e2 - e1;
458	e = e - e1;
459
460	if (data->drawLast)
461		len++;
462	dashoff = *data->dashOffset;
463	*data->dashOffset = dashoff + len;
464
465	oc1 = 0;
466	oc2 = 0;
467	OUTCODES(oc1, data->x1, data->y1, b);
468	OUTCODES(oc2, data->x2, data->y2, b);
469	if ((oc1 | oc2) == 0) {
470		data->bres(drawable, gc, dashoff,
471			   sdx, sdy, axis, data->x1, data->y1, e, e1, e3, len);
472	} else if (oc1 & oc2) {
473	} else {
474		int new_x1 = data->x1, new_y1 = data->y1;
475		int new_x2 = data->x2, new_y2 = data->y2;
476		int clip1 = 0, clip2 = 0;
477		int clipdx, clipdy;
478		int err;
479
480		if (miZeroClipLine(b->x1, b->y1, b->x2-1, b->y2-1,
481				   &new_x1, &new_y1, &new_x2, &new_y2,
482				   adx, ady, &clip1, &clip2,
483				   octant, bias, oc1, oc2) == -1)
484			return;
485
486		if (axis == X_AXIS)
487			len = abs(new_x2 - new_x1);
488		else
489			len = abs(new_y2 - new_y1);
490		if (clip2 != 0 || data->drawLast)
491			len++;
492		if (len) {
493			/* unwind bresenham error term to first point */
494			doff = dashoff;
495			err = e;
496			if (clip1) {
497				clipdx = abs(new_x1 - data->x1);
498				clipdy = abs(new_y1 - data->y1);
499				if (axis == X_AXIS) {
500					doff += clipdx;
501					err += e3 * clipdy + e1 * clipdx;
502				} else {
503					doff += clipdy;
504					err += e3 * clipdx + e1 * clipdy;
505				}
506			}
507			data->bres(drawable, gc, doff,
508				   sdx, sdy, axis, new_x1, new_y1,
509				   err, e1, e3, len);
510		}
511	}
512}
513
514void
515fbSegment(DrawablePtr drawable, GCPtr gc,
516          int x1, int y1, int x2, int y2,
517	  bool drawLast, int *dashOffset)
518{
519	struct fbSegment data;
520	BoxRec box;
521
522	DBG(("%s (%d, %d), (%d, %d), drawLast?=%d\n",
523	     __FUNCTION__, x1, y1, x2, y2, drawLast));
524
525	/* simple overestimate of line extents for clipping */
526	box.x1 = x1 - 1;
527	box.y1 = y1 - 1;
528	box.x2 = x2 + 1;
529	box.y2 = y2 + 1;
530
531	data.x1 = x1;
532	data.y1 = y1;
533	data.x2 = x2;
534	data.y2 = y2;
535
536	data.dashOffset = dashOffset;
537	data.drawLast = drawLast;
538	data.bres = fbSelectBres(drawable, gc);
539
540	fbDrawableRunUnclipped(drawable, gc, &box, _fbSegment, &data);
541}
542
543void
544fbSegment1(DrawablePtr drawable, GCPtr gc, const BoxRec *b,
545	   int x1, int y1, int x2, int y2,
546	   bool drawLast, int *dashOffset)
547{
548	struct fbSegment data;
549
550	DBG(("%s (%d, %d), (%d, %d), drawLast?=%d\n",
551	     __FUNCTION__, x1, y1, x2, y2, drawLast));
552
553	data.x1 = x1;
554	data.y1 = y1;
555	data.x2 = x2;
556	data.y2 = y2;
557
558	data.dashOffset = dashOffset;
559	data.drawLast = drawLast;
560	data.bres = fbSelectBres(drawable, gc);
561
562	_fbSegment(drawable, gc, b, &data);
563}
564