1 324891a5 2006-06-25 devnull #include <u.h>
  2 324891a5 2006-06-25 devnull #include <libc.h>
  3 324891a5 2006-06-25 devnull #include <draw.h>
  4 324891a5 2006-06-25 devnull #include <memdraw.h>
  5 324891a5 2006-06-25 devnull 
  6 324891a5 2006-06-25 devnull typedef struct Seg	Seg;
  7 324891a5 2006-06-25 devnull 
  8 324891a5 2006-06-25 devnull struct Seg
  9 324891a5 2006-06-25 devnull {
 10 324891a5 2006-06-25 devnull 	Point	p0;
 11 324891a5 2006-06-25 devnull 	Point	p1;
 12 324891a5 2006-06-25 devnull 	long	num;
 13 324891a5 2006-06-25 devnull 	long	den;
 14 324891a5 2006-06-25 devnull 	long	dz;
 15 324891a5 2006-06-25 devnull 	long	dzrem;
 16 324891a5 2006-06-25 devnull 	long	z;
 17 324891a5 2006-06-25 devnull 	long	zerr;
 18 324891a5 2006-06-25 devnull 	long	d;
 19 324891a5 2006-06-25 devnull };
 20 324891a5 2006-06-25 devnull 
 21 324891a5 2006-06-25 devnull static	void	zsort(Seg **seg, Seg **ep);
 22 324891a5 2006-06-25 devnull static	int	ycompare(const void*, const void*);
 23 324891a5 2006-06-25 devnull static	int	xcompare(const void*, const void*);
 24 324891a5 2006-06-25 devnull static	int	zcompare(const void*, const void*);
 25 324891a5 2006-06-25 devnull static	void	xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int, int, int);
 26 324891a5 2006-06-25 devnull static	void	yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int, int);
 27 324891a5 2006-06-25 devnull 
 28 324891a5 2006-06-25 devnull #if 0
 29 324891a5 2006-06-25 devnull static void
 30 324891a5 2006-06-25 devnull fillcolor(Memimage *dst, int left, int right, int y, Memimage *src, Point p)
 31 324891a5 2006-06-25 devnull {
 32 324891a5 2006-06-25 devnull 	int srcval;
 33 324891a5 2006-06-25 devnull 
 34 324891a5 2006-06-25 devnull 	USED(src);
 35 324891a5 2006-06-25 devnull 	srcval = p.x;
 36 324891a5 2006-06-25 devnull 	p.x = left;
 37 324891a5 2006-06-25 devnull 	p.y = y;
 38 324891a5 2006-06-25 devnull 	memset(byteaddr(dst, p), srcval, right-left);
 39 324891a5 2006-06-25 devnull }
 40 324891a5 2006-06-25 devnull #endif
 41 324891a5 2006-06-25 devnull 
 42 324891a5 2006-06-25 devnull static void
 43 324891a5 2006-06-25 devnull fillline(Memimage *dst, int left, int right, int y, Memimage *src, Point p, int op)
 44 324891a5 2006-06-25 devnull {
 45 324891a5 2006-06-25 devnull 	Rectangle r;
 46 324891a5 2006-06-25 devnull 
 47 324891a5 2006-06-25 devnull 	r.min.x = left;
 48 324891a5 2006-06-25 devnull 	r.min.y = y;
 49 324891a5 2006-06-25 devnull 	r.max.x = right;
 50 324891a5 2006-06-25 devnull 	r.max.y = y+1;
 51 324891a5 2006-06-25 devnull 	p.x += left;
 52 324891a5 2006-06-25 devnull 	p.y += y;
 53 324891a5 2006-06-25 devnull 	memdraw(dst, r, src, p, memopaque, p, op);
 54 324891a5 2006-06-25 devnull }
 55 324891a5 2006-06-25 devnull 
 56 324891a5 2006-06-25 devnull static void
 57 324891a5 2006-06-25 devnull fillpoint(Memimage *dst, int x, int y, Memimage *src, Point p, int op)
 58 324891a5 2006-06-25 devnull {
 59 324891a5 2006-06-25 devnull 	Rectangle r;
 60 324891a5 2006-06-25 devnull 
 61 324891a5 2006-06-25 devnull 	r.min.x = x;
 62 324891a5 2006-06-25 devnull 	r.min.y = y;
 63 324891a5 2006-06-25 devnull 	r.max.x = x+1;
 64 324891a5 2006-06-25 devnull 	r.max.y = y+1;
 65 324891a5 2006-06-25 devnull 	p.x += x;
 66 324891a5 2006-06-25 devnull 	p.y += y;
 67 324891a5 2006-06-25 devnull 	memdraw(dst, r, src, p, memopaque, p, op);
 68 324891a5 2006-06-25 devnull }
 69 324891a5 2006-06-25 devnull 
 70 324891a5 2006-06-25 devnull void
 71 324891a5 2006-06-25 devnull memfillpoly(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int op)
 72 324891a5 2006-06-25 devnull {
 73 324891a5 2006-06-25 devnull 	_memfillpolysc(dst, vert, nvert, w, src, sp, 0, 0, 0, op);
 74 324891a5 2006-06-25 devnull }
 75 324891a5 2006-06-25 devnull 
 76 324891a5 2006-06-25 devnull void
 77 324891a5 2006-06-25 devnull _memfillpolysc(Memimage *dst, Point *vert, int nvert, int w, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
 78 324891a5 2006-06-25 devnull {
 79 324891a5 2006-06-25 devnull 	Seg **seg, *segtab;
 80 324891a5 2006-06-25 devnull 	Point p0;
 81 324891a5 2006-06-25 devnull 	int i;
 82 324891a5 2006-06-25 devnull 
 83 324891a5 2006-06-25 devnull 	if(nvert == 0)
 84 324891a5 2006-06-25 devnull 		return;
 85 324891a5 2006-06-25 devnull 
 86 324891a5 2006-06-25 devnull 	seg = malloc((nvert+2)*sizeof(Seg*));
 87 324891a5 2006-06-25 devnull 	if(seg == nil)
 88 324891a5 2006-06-25 devnull 		return;
 89 324891a5 2006-06-25 devnull 	segtab = malloc((nvert+1)*sizeof(Seg));
 90 324891a5 2006-06-25 devnull 	if(segtab == nil) {
 91 324891a5 2006-06-25 devnull 		free(seg);
 92 324891a5 2006-06-25 devnull 		return;
 93 324891a5 2006-06-25 devnull 	}
 94 324891a5 2006-06-25 devnull 
 95 324891a5 2006-06-25 devnull 	sp.x = (sp.x - vert[0].x) >> fixshift;
 96 324891a5 2006-06-25 devnull 	sp.y = (sp.y - vert[0].y) >> fixshift;
 97 324891a5 2006-06-25 devnull 	p0 = vert[nvert-1];
 98 324891a5 2006-06-25 devnull 	if(!fixshift) {
 99 324891a5 2006-06-25 devnull 		p0.x <<= 1;
100 324891a5 2006-06-25 devnull 		p0.y <<= 1;
101 324891a5 2006-06-25 devnull 	}
102 324891a5 2006-06-25 devnull 	for(i = 0; i < nvert; i++) {
103 324891a5 2006-06-25 devnull 		segtab[i].p0 = p0;
104 324891a5 2006-06-25 devnull 		p0 = vert[i];
105 324891a5 2006-06-25 devnull 		if(!fixshift) {
106 324891a5 2006-06-25 devnull 			p0.x <<= 1;
107 324891a5 2006-06-25 devnull 			p0.y <<= 1;
108 324891a5 2006-06-25 devnull 		}
109 324891a5 2006-06-25 devnull 		segtab[i].p1 = p0;
110 324891a5 2006-06-25 devnull 		segtab[i].d = 1;
111 324891a5 2006-06-25 devnull 	}
112 324891a5 2006-06-25 devnull 	if(!fixshift)
113 324891a5 2006-06-25 devnull 		fixshift = 1;
114 324891a5 2006-06-25 devnull 
115 324891a5 2006-06-25 devnull 	xscan(dst, seg, segtab, nvert, w, src, sp, detail, fixshift, clipped, op);
116 324891a5 2006-06-25 devnull 	if(detail)
117 324891a5 2006-06-25 devnull 		yscan(dst, seg, segtab, nvert, w, src, sp, fixshift, op);
118 324891a5 2006-06-25 devnull 
119 324891a5 2006-06-25 devnull 	free(seg);
120 324891a5 2006-06-25 devnull 	free(segtab);
121 324891a5 2006-06-25 devnull }
122 324891a5 2006-06-25 devnull 
123 324891a5 2006-06-25 devnull static long
124 324891a5 2006-06-25 devnull mod(long x, long y)
125 324891a5 2006-06-25 devnull {
126 324891a5 2006-06-25 devnull 	long z;
127 324891a5 2006-06-25 devnull 
128 324891a5 2006-06-25 devnull 	z = x%y;
129 324891a5 2006-06-25 devnull 	if((long)(((ulong)z)^((ulong)y)) > 0 || z == 0)
130 324891a5 2006-06-25 devnull 		return z;
131 324891a5 2006-06-25 devnull 	return z + y;
132 324891a5 2006-06-25 devnull }
133 324891a5 2006-06-25 devnull 
134 324891a5 2006-06-25 devnull static long
135 324891a5 2006-06-25 devnull sdiv(long x, long y)
136 324891a5 2006-06-25 devnull {
137 324891a5 2006-06-25 devnull 	if((long)(((ulong)x)^((ulong)y)) >= 0 || x == 0)
138 324891a5 2006-06-25 devnull 		return x/y;
139 324891a5 2006-06-25 devnull 
140 324891a5 2006-06-25 devnull 	return (x+((y>>30)|1))/y-1;
141 324891a5 2006-06-25 devnull }
142 324891a5 2006-06-25 devnull 
143 324891a5 2006-06-25 devnull static long
144 324891a5 2006-06-25 devnull smuldivmod(long x, long y, long z, long *mod)
145 324891a5 2006-06-25 devnull {
146 324891a5 2006-06-25 devnull 	vlong vx;
147 324891a5 2006-06-25 devnull 
148 324891a5 2006-06-25 devnull 	if(x == 0 || y == 0){
149 324891a5 2006-06-25 devnull 		*mod = 0;
150 324891a5 2006-06-25 devnull 		return 0;
151 324891a5 2006-06-25 devnull 	}
152 324891a5 2006-06-25 devnull 	vx = x;
153 324891a5 2006-06-25 devnull 	vx *= y;
154 324891a5 2006-06-25 devnull 	*mod = vx % z;
155 324891a5 2006-06-25 devnull 	if(*mod < 0)
156 324891a5 2006-06-25 devnull 		*mod += z;	/* z is always >0 */
157 324891a5 2006-06-25 devnull 	if((vx < 0) == (z < 0))
158 324891a5 2006-06-25 devnull 		return vx/z;
159 324891a5 2006-06-25 devnull 	return -((-vx)/z);
160 324891a5 2006-06-25 devnull }
161 324891a5 2006-06-25 devnull 
162 324891a5 2006-06-25 devnull static void
163 324891a5 2006-06-25 devnull xscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int detail, int fixshift, int clipped, int op)
164 324891a5 2006-06-25 devnull {
165 324891a5 2006-06-25 devnull 	long y, maxy, x, x2, xerr, xden, onehalf;
166 324891a5 2006-06-25 devnull 	Seg **ep, **next, **p, **q, *s;
167 324891a5 2006-06-25 devnull 	long n, i, iy, cnt, ix, ix2, minx, maxx;
168 324891a5 2006-06-25 devnull 	Point pt;
169 324891a5 2006-06-25 devnull 	void	(*fill)(Memimage*, int, int, int, Memimage*, Point, int);
170 324891a5 2006-06-25 devnull 
171 324891a5 2006-06-25 devnull 	fill = fillline;
172 324891a5 2006-06-25 devnull /*
173 324891a5 2006-06-25 devnull  * This can only work on 8-bit destinations, since fillcolor is
174 324891a5 2006-06-25 devnull  * just using memset on sp.x.
175 324891a5 2006-06-25 devnull  *
176 324891a5 2006-06-25 devnull  * I'd rather not even enable it then, since then if the general
177 324891a5 2006-06-25 devnull  * code is too slow, someone will come up with a better improvement
178 324891a5 2006-06-25 devnull  * than this sleazy hack.	-rsc
179 324891a5 2006-06-25 devnull  *
180 324891a5 2006-06-25 devnull 	if(clipped && (src->flags&Frepl) && src->depth==8 && Dx(src->r)==1 && Dy(src->r)==1) {
181 324891a5 2006-06-25 devnull 		fill = fillcolor;
182 324891a5 2006-06-25 devnull 		sp.x = membyteval(src);
183 324891a5 2006-06-25 devnull 	}
184 324891a5 2006-06-25 devnull  *
185 324891a5 2006-06-25 devnull  */
186 324891a5 2006-06-25 devnull 	USED(clipped);
187 324891a5 2006-06-25 devnull 
188 324891a5 2006-06-25 devnull 
189 324891a5 2006-06-25 devnull 	for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
190 324891a5 2006-06-25 devnull 		*p = s;
191 324891a5 2006-06-25 devnull 		if(s->p0.y == s->p1.y)
192 324891a5 2006-06-25 devnull 			continue;
193 324891a5 2006-06-25 devnull 		if(s->p0.y > s->p1.y) {
194 324891a5 2006-06-25 devnull 			pt = s->p0;
195 324891a5 2006-06-25 devnull 			s->p0 = s->p1;
196 324891a5 2006-06-25 devnull 			s->p1 = pt;
197 324891a5 2006-06-25 devnull 			s->d = -s->d;
198 324891a5 2006-06-25 devnull 		}
199 324891a5 2006-06-25 devnull 		s->num = s->p1.x - s->p0.x;
200 324891a5 2006-06-25 devnull 		s->den = s->p1.y - s->p0.y;
201 324891a5 2006-06-25 devnull 		s->dz = sdiv(s->num, s->den) << fixshift;
202 324891a5 2006-06-25 devnull 		s->dzrem = mod(s->num, s->den) << fixshift;
203 324891a5 2006-06-25 devnull 		s->dz += sdiv(s->dzrem, s->den);
204 324891a5 2006-06-25 devnull 		s->dzrem = mod(s->dzrem, s->den);
205 324891a5 2006-06-25 devnull 		p++;
206 324891a5 2006-06-25 devnull 	}
207 324891a5 2006-06-25 devnull 	n = p-seg;
208 324891a5 2006-06-25 devnull 	if(n == 0)
209 324891a5 2006-06-25 devnull 		return;
210 324891a5 2006-06-25 devnull 	*p = 0;
211 324891a5 2006-06-25 devnull 	qsort(seg, p-seg , sizeof(Seg*), ycompare);
212 324891a5 2006-06-25 devnull 
213 324891a5 2006-06-25 devnull 	onehalf = 0;
214 324891a5 2006-06-25 devnull 	if(fixshift)
215 324891a5 2006-06-25 devnull 		onehalf = 1 << (fixshift-1);
216 324891a5 2006-06-25 devnull 
217 324891a5 2006-06-25 devnull 	minx = dst->clipr.min.x;
218 324891a5 2006-06-25 devnull 	maxx = dst->clipr.max.x;
219 324891a5 2006-06-25 devnull 
220 324891a5 2006-06-25 devnull 	y = seg[0]->p0.y;
221 324891a5 2006-06-25 devnull 	if(y < (dst->clipr.min.y << fixshift))
222 324891a5 2006-06-25 devnull 		y = dst->clipr.min.y << fixshift;
223 324891a5 2006-06-25 devnull 	iy = (y + onehalf) >> fixshift;
224 324891a5 2006-06-25 devnull 	y = (iy << fixshift) + onehalf;
225 324891a5 2006-06-25 devnull 	maxy = dst->clipr.max.y << fixshift;
226 324891a5 2006-06-25 devnull 
227 324891a5 2006-06-25 devnull 	ep = next = seg;
228 324891a5 2006-06-25 devnull 
229 324891a5 2006-06-25 devnull 	while(y<maxy) {
230 324891a5 2006-06-25 devnull 		for(q = p = seg; p < ep; p++) {
231 324891a5 2006-06-25 devnull 			s = *p;
232 324891a5 2006-06-25 devnull 			if(s->p1.y < y)
233 324891a5 2006-06-25 devnull 				continue;
234 324891a5 2006-06-25 devnull 			s->z += s->dz;
235 324891a5 2006-06-25 devnull 			s->zerr += s->dzrem;
236 324891a5 2006-06-25 devnull 			if(s->zerr >= s->den) {
237 324891a5 2006-06-25 devnull 				s->z++;
238 324891a5 2006-06-25 devnull 				s->zerr -= s->den;
239 324891a5 2006-06-25 devnull 				if(s->zerr < 0 || s->zerr >= s->den)
240 324891a5 2006-06-25 devnull 					print("bad ratzerr1: %ld den %ld dzrem %ld\n", s->zerr, s->den, s->dzrem);
241 324891a5 2006-06-25 devnull 			}
242 324891a5 2006-06-25 devnull 			*q++ = s;
243 324891a5 2006-06-25 devnull 		}
244 324891a5 2006-06-25 devnull 
245 324891a5 2006-06-25 devnull 		for(p = next; *p; p++) {
246 324891a5 2006-06-25 devnull 			s = *p;
247 324891a5 2006-06-25 devnull 			if(s->p0.y >= y)
248 324891a5 2006-06-25 devnull 				break;
249 324891a5 2006-06-25 devnull 			if(s->p1.y < y)
250 324891a5 2006-06-25 devnull 				continue;
251 324891a5 2006-06-25 devnull 			s->z = s->p0.x;
252 324891a5 2006-06-25 devnull 			s->z += smuldivmod(y - s->p0.y, s->num, s->den, &s->zerr);
253 324891a5 2006-06-25 devnull 			if(s->zerr < 0 || s->zerr >= s->den)
254 324891a5 2006-06-25 devnull 				print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
255 324891a5 2006-06-25 devnull 			*q++ = s;
256 324891a5 2006-06-25 devnull 		}
257 324891a5 2006-06-25 devnull 		ep = q;
258 324891a5 2006-06-25 devnull 		next = p;
259 324891a5 2006-06-25 devnull 
260 324891a5 2006-06-25 devnull 		if(ep == seg) {
261 324891a5 2006-06-25 devnull 			if(*next == 0)
262 324891a5 2006-06-25 devnull 				break;
263 324891a5 2006-06-25 devnull 			iy = (next[0]->p0.y + onehalf) >> fixshift;
264 324891a5 2006-06-25 devnull 			y = (iy << fixshift) + onehalf;
265 324891a5 2006-06-25 devnull 			continue;
266 324891a5 2006-06-25 devnull 		}
267 324891a5 2006-06-25 devnull 
268 324891a5 2006-06-25 devnull 		zsort(seg, ep);
269 324891a5 2006-06-25 devnull 
270 324891a5 2006-06-25 devnull 		for(p = seg; p < ep; p++) {
271 324891a5 2006-06-25 devnull 			cnt = 0;
272 324891a5 2006-06-25 devnull 			x = p[0]->z;
273 324891a5 2006-06-25 devnull 			xerr = p[0]->zerr;
274 324891a5 2006-06-25 devnull 			xden = p[0]->den;
275 324891a5 2006-06-25 devnull 			ix = (x + onehalf) >> fixshift;
276 324891a5 2006-06-25 devnull 			if(ix >= maxx)
277 324891a5 2006-06-25 devnull 				break;
278 324891a5 2006-06-25 devnull 			if(ix < minx)
279 324891a5 2006-06-25 devnull 				ix = minx;
280 324891a5 2006-06-25 devnull 			cnt += p[0]->d;
281 324891a5 2006-06-25 devnull 			p++;
282 324891a5 2006-06-25 devnull 			for(;;) {
283 324891a5 2006-06-25 devnull 				if(p == ep) {
284 324891a5 2006-06-25 devnull 					print("xscan: fill to infinity");
285 324891a5 2006-06-25 devnull 					return;
286 324891a5 2006-06-25 devnull 				}
287 324891a5 2006-06-25 devnull 				cnt += p[0]->d;
288 324891a5 2006-06-25 devnull 				if((cnt&wind) == 0)
289 324891a5 2006-06-25 devnull 					break;
290 324891a5 2006-06-25 devnull 				p++;
291 324891a5 2006-06-25 devnull 			}
292 324891a5 2006-06-25 devnull 			x2 = p[0]->z;
293 324891a5 2006-06-25 devnull 			ix2 = (x2 + onehalf) >> fixshift;
294 324891a5 2006-06-25 devnull 			if(ix2 <= minx)
295 324891a5 2006-06-25 devnull 				continue;
296 324891a5 2006-06-25 devnull 			if(ix2 > maxx)
297 324891a5 2006-06-25 devnull 				ix2 = maxx;
298 324891a5 2006-06-25 devnull 			if(ix == ix2 && detail) {
299 324891a5 2006-06-25 devnull 				if(xerr*p[0]->den + p[0]->zerr*xden > p[0]->den*xden)
300 324891a5 2006-06-25 devnull 					x++;
301 324891a5 2006-06-25 devnull 				ix = (x + x2) >> (fixshift+1);
302 324891a5 2006-06-25 devnull 				ix2 = ix+1;
303 324891a5 2006-06-25 devnull 			}
304 324891a5 2006-06-25 devnull 			(*fill)(dst, ix, ix2, iy, src, sp, op);
305 324891a5 2006-06-25 devnull 		}
306 324891a5 2006-06-25 devnull 		y += (1<<fixshift);
307 324891a5 2006-06-25 devnull 		iy++;
308 324891a5 2006-06-25 devnull 	}
309 324891a5 2006-06-25 devnull }
310 324891a5 2006-06-25 devnull 
311 324891a5 2006-06-25 devnull static void
312 324891a5 2006-06-25 devnull yscan(Memimage *dst, Seg **seg, Seg *segtab, int nseg, int wind, Memimage *src, Point sp, int fixshift, int op)
313 324891a5 2006-06-25 devnull {
314 324891a5 2006-06-25 devnull 	long x, maxx, y, y2, yerr, yden, onehalf;
315 324891a5 2006-06-25 devnull 	Seg **ep, **next, **p, **q, *s;
316 324891a5 2006-06-25 devnull 	int n, i, ix, cnt, iy, iy2, miny, maxy;
317 324891a5 2006-06-25 devnull 	Point pt;
318 324891a5 2006-06-25 devnull 
319 324891a5 2006-06-25 devnull 	for(i=0, s=segtab, p=seg; i<nseg; i++, s++) {
320 324891a5 2006-06-25 devnull 		*p = s;
321 324891a5 2006-06-25 devnull 		if(s->p0.x == s->p1.x)
322 324891a5 2006-06-25 devnull 			continue;
323 324891a5 2006-06-25 devnull 		if(s->p0.x > s->p1.x) {
324 324891a5 2006-06-25 devnull 			pt = s->p0;
325 324891a5 2006-06-25 devnull 			s->p0 = s->p1;
326 324891a5 2006-06-25 devnull 			s->p1 = pt;
327 324891a5 2006-06-25 devnull 			s->d = -s->d;
328 324891a5 2006-06-25 devnull 		}
329 324891a5 2006-06-25 devnull 		s->num = s->p1.y - s->p0.y;
330 324891a5 2006-06-25 devnull 		s->den = s->p1.x - s->p0.x;
331 324891a5 2006-06-25 devnull 		s->dz = sdiv(s->num, s->den) << fixshift;
332 324891a5 2006-06-25 devnull 		s->dzrem = mod(s->num, s->den) << fixshift;
333 324891a5 2006-06-25 devnull 		s->dz += sdiv(s->dzrem, s->den);
334 324891a5 2006-06-25 devnull 		s->dzrem = mod(s->dzrem, s->den);
335 324891a5 2006-06-25 devnull 		p++;
336 324891a5 2006-06-25 devnull 	}
337 324891a5 2006-06-25 devnull 	n = p-seg;
338 324891a5 2006-06-25 devnull 	if(n == 0)
339 324891a5 2006-06-25 devnull 		return;
340 324891a5 2006-06-25 devnull 	*p = 0;
341 324891a5 2006-06-25 devnull 	qsort(seg, n , sizeof(Seg*), xcompare);
342 324891a5 2006-06-25 devnull 
343 324891a5 2006-06-25 devnull 	onehalf = 0;
344 324891a5 2006-06-25 devnull 	if(fixshift)
345 324891a5 2006-06-25 devnull 		onehalf = 1 << (fixshift-1);
346 324891a5 2006-06-25 devnull 
347 324891a5 2006-06-25 devnull 	miny = dst->clipr.min.y;
348 324891a5 2006-06-25 devnull 	maxy = dst->clipr.max.y;
349 324891a5 2006-06-25 devnull 
350 324891a5 2006-06-25 devnull 	x = seg[0]->p0.x;
351 324891a5 2006-06-25 devnull 	if(x < (dst->clipr.min.x << fixshift))
352 324891a5 2006-06-25 devnull 		x = dst->clipr.min.x << fixshift;
353 324891a5 2006-06-25 devnull 	ix = (x + onehalf) >> fixshift;
354 324891a5 2006-06-25 devnull 	x = (ix << fixshift) + onehalf;
355 324891a5 2006-06-25 devnull 	maxx = dst->clipr.max.x << fixshift;
356 324891a5 2006-06-25 devnull 
357 324891a5 2006-06-25 devnull 	ep = next = seg;
358 324891a5 2006-06-25 devnull 
359 324891a5 2006-06-25 devnull 	while(x<maxx) {
360 324891a5 2006-06-25 devnull 		for(q = p = seg; p < ep; p++) {
361 324891a5 2006-06-25 devnull 			s = *p;
362 324891a5 2006-06-25 devnull 			if(s->p1.x < x)
363 324891a5 2006-06-25 devnull 				continue;
364 324891a5 2006-06-25 devnull 			s->z += s->dz;
365 324891a5 2006-06-25 devnull 			s->zerr += s->dzrem;
366 324891a5 2006-06-25 devnull 			if(s->zerr >= s->den) {
367 324891a5 2006-06-25 devnull 				s->z++;
368 324891a5 2006-06-25 devnull 				s->zerr -= s->den;
369 324891a5 2006-06-25 devnull 				if(s->zerr < 0 || s->zerr >= s->den)
370 324891a5 2006-06-25 devnull 					print("bad ratzerr1: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
371 324891a5 2006-06-25 devnull 			}
372 324891a5 2006-06-25 devnull 			*q++ = s;
373 324891a5 2006-06-25 devnull 		}
374 324891a5 2006-06-25 devnull 
375 324891a5 2006-06-25 devnull 		for(p = next; *p; p++) {
376 324891a5 2006-06-25 devnull 			s = *p;
377 324891a5 2006-06-25 devnull 			if(s->p0.x >= x)
378 324891a5 2006-06-25 devnull 				break;
379 324891a5 2006-06-25 devnull 			if(s->p1.x < x)
380 324891a5 2006-06-25 devnull 				continue;
381 324891a5 2006-06-25 devnull 			s->z = s->p0.y;
382 324891a5 2006-06-25 devnull 			s->z += smuldivmod(x - s->p0.x, s->num, s->den, &s->zerr);
383 324891a5 2006-06-25 devnull 			if(s->zerr < 0 || s->zerr >= s->den)
384 324891a5 2006-06-25 devnull 				print("bad ratzerr2: %ld den %ld ratdzrem %ld\n", s->zerr, s->den, s->dzrem);
385 324891a5 2006-06-25 devnull 			*q++ = s;
386 324891a5 2006-06-25 devnull 		}
387 324891a5 2006-06-25 devnull 		ep = q;
388 324891a5 2006-06-25 devnull 		next = p;
389 324891a5 2006-06-25 devnull 
390 324891a5 2006-06-25 devnull 		if(ep == seg) {
391 324891a5 2006-06-25 devnull 			if(*next == 0)
392 324891a5 2006-06-25 devnull 				break;
393 324891a5 2006-06-25 devnull 			ix = (next[0]->p0.x + onehalf) >> fixshift;
394 324891a5 2006-06-25 devnull 			x = (ix << fixshift) + onehalf;
395 324891a5 2006-06-25 devnull 			continue;
396 324891a5 2006-06-25 devnull 		}
397 324891a5 2006-06-25 devnull 
398 324891a5 2006-06-25 devnull 		zsort(seg, ep);
399 324891a5 2006-06-25 devnull 
400 324891a5 2006-06-25 devnull 		for(p = seg; p < ep; p++) {
401 324891a5 2006-06-25 devnull 			cnt = 0;
402 324891a5 2006-06-25 devnull 			y = p[0]->z;
403 324891a5 2006-06-25 devnull 			yerr = p[0]->zerr;
404 324891a5 2006-06-25 devnull 			yden = p[0]->den;
405 324891a5 2006-06-25 devnull 			iy = (y + onehalf) >> fixshift;
406 324891a5 2006-06-25 devnull 			if(iy >= maxy)
407 324891a5 2006-06-25 devnull 				break;
408 324891a5 2006-06-25 devnull 			if(iy < miny)
409 324891a5 2006-06-25 devnull 				iy = miny;
410 324891a5 2006-06-25 devnull 			cnt += p[0]->d;
411 324891a5 2006-06-25 devnull 			p++;
412 324891a5 2006-06-25 devnull 			for(;;) {
413 324891a5 2006-06-25 devnull 				if(p == ep) {
414 324891a5 2006-06-25 devnull 					print("yscan: fill to infinity");
415 324891a5 2006-06-25 devnull 					return;
416 324891a5 2006-06-25 devnull 				}
417 324891a5 2006-06-25 devnull 				cnt += p[0]->d;
418 324891a5 2006-06-25 devnull 				if((cnt&wind) == 0)
419 324891a5 2006-06-25 devnull 					break;
420 324891a5 2006-06-25 devnull 				p++;
421 324891a5 2006-06-25 devnull 			}
422 324891a5 2006-06-25 devnull 			y2 = p[0]->z;
423 324891a5 2006-06-25 devnull 			iy2 = (y2 + onehalf) >> fixshift;
424 324891a5 2006-06-25 devnull 			if(iy2 <= miny)
425 324891a5 2006-06-25 devnull 				continue;
426 324891a5 2006-06-25 devnull 			if(iy2 > maxy)
427 324891a5 2006-06-25 devnull 				iy2 = maxy;
428 324891a5 2006-06-25 devnull 			if(iy == iy2) {
429 324891a5 2006-06-25 devnull 				if(yerr*p[0]->den + p[0]->zerr*yden > p[0]->den*yden)
430 324891a5 2006-06-25 devnull 					y++;
431 324891a5 2006-06-25 devnull 				iy = (y + y2) >> (fixshift+1);
432 324891a5 2006-06-25 devnull 				fillpoint(dst, ix, iy, src, sp, op);
433 324891a5 2006-06-25 devnull 			}
434 324891a5 2006-06-25 devnull 		}
435 324891a5 2006-06-25 devnull 		x += (1<<fixshift);
436 324891a5 2006-06-25 devnull 		ix++;
437 324891a5 2006-06-25 devnull 	}
438 324891a5 2006-06-25 devnull }
439 324891a5 2006-06-25 devnull 
440 324891a5 2006-06-25 devnull static void
441 324891a5 2006-06-25 devnull zsort(Seg **seg, Seg **ep)
442 324891a5 2006-06-25 devnull {
443 324891a5 2006-06-25 devnull 	int done;
444 324891a5 2006-06-25 devnull 	Seg **q, **p, *s;
445 324891a5 2006-06-25 devnull 
446 324891a5 2006-06-25 devnull 	if(ep-seg < 20) {
447 324891a5 2006-06-25 devnull 		/* bubble sort by z - they should be almost sorted already */
448 324891a5 2006-06-25 devnull 		q = ep;
449 324891a5 2006-06-25 devnull 		do {
450 324891a5 2006-06-25 devnull 			done = 1;
451 324891a5 2006-06-25 devnull 			q--;
452 324891a5 2006-06-25 devnull 			for(p = seg; p < q; p++) {
453 324891a5 2006-06-25 devnull 				if(p[0]->z > p[1]->z) {
454 324891a5 2006-06-25 devnull 					s = p[0];
455 324891a5 2006-06-25 devnull 					p[0] = p[1];
456 324891a5 2006-06-25 devnull 					p[1] = s;
457 324891a5 2006-06-25 devnull 					done = 0;
458 324891a5 2006-06-25 devnull 				}
459 324891a5 2006-06-25 devnull 			}
460 324891a5 2006-06-25 devnull 		} while(!done);
461 324891a5 2006-06-25 devnull 	} else {
462 324891a5 2006-06-25 devnull 		q = ep-1;
463 324891a5 2006-06-25 devnull 		for(p = seg; p < q; p++) {
464 324891a5 2006-06-25 devnull 			if(p[0]->z > p[1]->z) {
465 324891a5 2006-06-25 devnull 				qsort(seg, ep-seg, sizeof(Seg*), zcompare);
466 324891a5 2006-06-25 devnull 				break;
467 324891a5 2006-06-25 devnull 			}
468 324891a5 2006-06-25 devnull 		}
469 324891a5 2006-06-25 devnull 	}
470 324891a5 2006-06-25 devnull }
471 324891a5 2006-06-25 devnull 
472 324891a5 2006-06-25 devnull static int
473 324891a5 2006-06-25 devnull ycompare(const void *a, const void *b)
474 324891a5 2006-06-25 devnull {
475 324891a5 2006-06-25 devnull 	Seg **s0, **s1;
476 324891a5 2006-06-25 devnull 	long y0, y1;
477 324891a5 2006-06-25 devnull 
478 324891a5 2006-06-25 devnull 	s0 = (Seg**)a;
479 324891a5 2006-06-25 devnull 	s1 = (Seg**)b;
480 324891a5 2006-06-25 devnull 	y0 = (*s0)->p0.y;
481 324891a5 2006-06-25 devnull 	y1 = (*s1)->p0.y;
482 324891a5 2006-06-25 devnull 
483 324891a5 2006-06-25 devnull 	if(y0 < y1)
484 324891a5 2006-06-25 devnull 		return -1;
485 324891a5 2006-06-25 devnull 	if(y0 == y1)
486 324891a5 2006-06-25 devnull 		return 0;
487 324891a5 2006-06-25 devnull 	return 1;
488 324891a5 2006-06-25 devnull }
489 324891a5 2006-06-25 devnull 
490 324891a5 2006-06-25 devnull static int
491 324891a5 2006-06-25 devnull xcompare(const void *a, const void *b)
492 324891a5 2006-06-25 devnull {
493 324891a5 2006-06-25 devnull 	Seg **s0, **s1;
494 324891a5 2006-06-25 devnull 	long x0, x1;
495 324891a5 2006-06-25 devnull 
496 324891a5 2006-06-25 devnull 	s0 = (Seg**)a;
497 324891a5 2006-06-25 devnull 	s1 = (Seg**)b;
498 324891a5 2006-06-25 devnull 	x0 = (*s0)->p0.x;
499 324891a5 2006-06-25 devnull 	x1 = (*s1)->p0.x;
500 324891a5 2006-06-25 devnull 
501 324891a5 2006-06-25 devnull 	if(x0 < x1)
502 324891a5 2006-06-25 devnull 		return -1;
503 324891a5 2006-06-25 devnull 	if(x0 == x1)
504 324891a5 2006-06-25 devnull 		return 0;
505 324891a5 2006-06-25 devnull 	return 1;
506 324891a5 2006-06-25 devnull }
507 324891a5 2006-06-25 devnull 
508 324891a5 2006-06-25 devnull static int
509 324891a5 2006-06-25 devnull zcompare(const void *a, const void *b)
510 324891a5 2006-06-25 devnull {
511 324891a5 2006-06-25 devnull 	Seg **s0, **s1;
512 324891a5 2006-06-25 devnull 	long z0, z1;
513 324891a5 2006-06-25 devnull 
514 324891a5 2006-06-25 devnull 	s0 = (Seg**)a;
515 324891a5 2006-06-25 devnull 	s1 = (Seg**)b;
516 324891a5 2006-06-25 devnull 	z0 = (*s0)->z;
517 324891a5 2006-06-25 devnull 	z1 = (*s1)->z;
518 324891a5 2006-06-25 devnull 
519 324891a5 2006-06-25 devnull 	if(z0 < z1)
520 324891a5 2006-06-25 devnull 		return -1;
521 324891a5 2006-06-25 devnull 	if(z0 == z1)
522 324891a5 2006-06-25 devnull 		return 0;
523 324891a5 2006-06-25 devnull 	return 1;
524 324891a5 2006-06-25 devnull }