op public repos

Blob

Date:: Mon Mar 26 20:55:26 2007 UTC
Message:: add page (Kris Maglione)
Actions:: History | Blame | Raw File
1 /*
2  * rotate an image 180° in O(log Dx + log Dy) /dev/draw writes,
3  * using an extra buffer same size as the image.
4  * 
5  * the basic concept is that you can invert an array by inverting
6  * the top half, inverting the bottom half, and then swapping them.
7  * the code does this slightly backwards to ensure O(log n) runtime.
8  * (If you do it wrong, you can get O(log² n) runtime.)
9  * 
10  * This is usually overkill, but it speeds up slow remote
11  * connections quite a bit.
12  */
13 
14 #include <u.h>
15 #include <libc.h>
16 #include <bio.h>
17 #include <draw.h>
18 #include <thread.h>
19 #include <cursor.h>
20 #include "page.h"
21 
22 int ndraw = 0;
23 enum {
24 	Xaxis = 0,
25 	Yaxis = 1,
26 };
27 
28 Image *mtmp;
29 
30 void
31 writefile(char *name, Image *im, int gran)
32 {
33 	static int c = 100;
34 	int fd;
35 	char buf[200];
36 
37 	snprint(buf, sizeof buf, "%d%s%d", c++, name, gran);
38 	fd = create(buf, OWRITE, 0666);
39 	if(fd < 0)
40 		return;	
41 	writeimage(fd, im, 0);
42 	close(fd);
43 }
44 
45 void
46 moveup(Image *im, Image *tmp, int a, int b, int c, int axis)
47 {
48 	Rectangle range;
49 	Rectangle dr0, dr1;
50 	Point p0, p1;
51 
52 	if(a == b || b == c)
53 		return;
54 
55 	drawop(tmp, tmp->r, im, nil, im->r.min, S);
56 
57 	switch(axis){
58 	case Xaxis:
59 		range = Rect(a, im->r.min.y,  c, im->r.max.y);
60 		dr0 = range;
61 		dr0.max.x = dr0.min.x+(c-b);
62 		p0 = Pt(b, im->r.min.y);
63 
64 		dr1 = range;
65 		dr1.min.x = dr1.max.x-(b-a);
66 		p1 = Pt(a, im->r.min.y);
67 		break;
68 	case Yaxis:
69 	default:
70 		range = Rect(im->r.min.x, a,  im->r.max.x, c);
71 		dr0 = range;
72 		dr0.max.y = dr0.min.y+(c-b);
73 		p0 = Pt(im->r.min.x, b);
74 
75 		dr1 = range;
76 		dr1.min.y = dr1.max.y-(b-a);
77 		p1 = Pt(im->r.min.x, a);
78 		break;
79 	}
80 	drawop(im, dr0, tmp, nil, p0, S);
81 	drawop(im, dr1, tmp, nil, p1, S);
82 }
83 
84 void
85 interlace(Image *im, Image *tmp, int axis, int n, Image *mask, int gran)
86 {
87 	Point p0, p1;
88 	Rectangle r0, r1;
89 
90 	r0 = im->r;
91 	r1 = im->r;
92 	switch(axis) {
93 	case Xaxis:
94 		r0.max.x = n;
95 		r1.min.x = n;
96 		p0 = (Point){gran, 0};
97 		p1 = (Point){-gran, 0};
98 		break;
99 	case Yaxis:
100 	default:
101 		r0.max.y = n;
102 		r1.min.y = n;
103 		p0 = (Point){0, gran};
104 		p1 = (Point){0, -gran};
105 		break;
106 	}
107 
108 	drawop(tmp, im->r, im, display->opaque, im->r.min, S);
109 	gendrawop(im, r0, tmp, p0, mask, mask->r.min, S);
110 	gendrawop(im, r0, tmp, p1, mask, p1, S);
111 }
112 
113 /*
114  * Halve the grating period in the mask.
115  * The grating currently looks like 
116  * ####____####____####____####____
117  * where #### is opacity.
118  *
119  * We want
120  * ##__##__##__##__##__##__##__##__
121  * which is achieved by shifting the mask
122  * and drawing on itself through itself.
123  * Draw doesn't actually allow this, so 
124  * we have to copy it first.
125  *
126  *     ####____####____####____####____ (dst)
127  * +   ____####____####____####____#### (src)
128  * in  __####____####____####____####__ (mask)
129  * ===========================================
130  *     ##__##__##__##__##__##__##__##__
131  */
132 int
133 nextmask(Image *mask, int axis, int maskdim)
134 {
135 	Point o;
136 
137 	o = axis==Xaxis ? Pt(maskdim,0) : Pt(0,maskdim);
138 	drawop(mtmp, mtmp->r, mask, nil, mask->r.min, S);
139 	gendrawop(mask, mask->r, mtmp, o, mtmp, divpt(o,-2), S);
140 //	writefile("mask", mask, maskdim/2);
141 	return maskdim/2;
142 }
143 
144 void
145 shuffle(Image *im, Image *tmp, int axis, int n, Image *mask, int gran,
146 	int lastnn)
147 {
148 	int nn, left;
149 
150 	if(gran == 0)
151 		return;
152 	left = n%(2*gran);
153 	nn = n - left;
154 
155 	interlace(im, tmp, axis, nn, mask, gran);
156 //	writefile("interlace", im, gran);
157 	
158 	gran = nextmask(mask, axis, gran);
159 	shuffle(im, tmp, axis, n, mask, gran, nn);
160 //	writefile("shuffle", im, gran);
161 	moveup(im, tmp, lastnn, nn, n, axis);
162 //	writefile("move", im, gran);
163 }
164 
165 void
166 rot180(Image *im)
167 {
168 	Image *tmp, *tmp0;
169 	Image *mask;
170 	Rectangle rmask;
171 	int gran;
172 
173 	if(chantodepth(im->chan) < 8){
174 		/* this speeds things up dramatically; draw is too slow on sub-byte pixel sizes */
175 		tmp0 = xallocimage(display, im->r, CMAP8, 0, DNofill);
176 		drawop(tmp0, tmp0->r, im, nil, im->r.min, S);
177 	}else
178 		tmp0 = im;
179 
180 	tmp = xallocimage(display, tmp0->r, tmp0->chan, 0, DNofill);
181 	if(tmp == nil){
182 		if(tmp0 != im)
183 			freeimage(tmp0);
184 		return;
185 	}
186 	for(gran=1; gran<Dx(im->r); gran *= 2)
187 		;
188 	gran /= 4;
189 
190 	rmask.min = ZP;
191 	rmask.max = (Point){2*gran, 100};
192 
193 	mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
194 	mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
195 	if(mask == nil || mtmp == nil) {
196 		fprint(2, "out of memory during rot180: %r\n");
197 		wexits("memory");
198 	}
199 	rmask.max.x = gran;
200 	drawop(mask, rmask, display->opaque, nil, ZP, S);
201 //	writefile("mask", mask, gran);
202 	shuffle(im, tmp, Xaxis, Dx(im->r), mask, gran, 0);
203 	freeimage(mask);
204 	freeimage(mtmp);
205 
206 	for(gran=1; gran<Dy(im->r); gran *= 2)
207 		;
208 	gran /= 4;
209 	rmask.max = (Point){100, 2*gran};
210 	mask = xallocimage(display, rmask, GREY1, 1, DTransparent);
211 	mtmp = xallocimage(display, rmask, GREY1, 1, DTransparent);
212 	if(mask == nil || mtmp == nil) {
213 		fprint(2, "out of memory during rot180: %r\n");
214 		wexits("memory");
215 	}
216 	rmask.max.y = gran;
217 	drawop(mask, rmask, display->opaque, nil, ZP, S);
218 	shuffle(im, tmp, Yaxis, Dy(im->r), mask, gran, 0);
219 	freeimage(mask);
220 	freeimage(mtmp);
221 	freeimage(tmp);
222 	if(tmp0 != im)
223 		freeimage(tmp0);
224 }
225 
226 /* rotates an image 90 degrees clockwise */
227 Image *
228 rot90(Image *im)
229 {
230 	Image *tmp;
231 	int i, j, dx, dy;
232 
233 	dx = Dx(im->r);
234 	dy = Dy(im->r);
235 	tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan);
236 	if(tmp == nil) {
237 		fprint(2, "out of memory during rot90: %r\n");
238 		wexits("memory");
239 	}
240 
241 	for(j = 0; j < dx; j++) {
242 		for(i = 0; i < dy; i++) {
243 			drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(j, dy-(i+1)), S);
244 		}
245 	}
246 	freeimage(im);
247 
248 	return(tmp);
249 }
250 
251 /* rotates an image 270 degrees clockwise */
252 Image *
253 rot270(Image *im)
254 {
255 	Image *tmp;
256 	int i, j, dx, dy;
257 
258 	dx = Dx(im->r);
259 	dy = Dy(im->r);
260 	tmp = xallocimage(display, Rect(0, 0, dy, dx), im->chan, 0, DCyan);
261 	if(tmp == nil) {
262 		fprint(2, "out of memory during rot270: %r\n");
263 		wexits("memory");
264 	}
265 
266 	for(i = 0; i < dy; i++) {
267 		for(j = 0; j < dx; j++) {
268 			drawop(tmp, Rect(i, j, i+1, j+1), im, nil, Pt(dx-(j+1), i), S);
269 		}
270 	}
271 	freeimage(im);
272 
273 	return(tmp);
274 }
275 
276 /* from resample.c -- resize from → to using interpolation */
277 
278 
279 #define K2 7	/* from -.7 to +.7 inclusive, meaning .2 into each adjacent pixel */
280 #define NK (2*K2+1)
281 double K[NK];
282 
283 double
284 fac(int L)
285 {
286 	int i, f;
287 
288 	f = 1;
289 	for(i=L; i>1; --i)
290 		f *= i;
291 	return f;
292 }
293 
294 /* 
295  * i0(x) is the modified Bessel function, Σ (x/2)^2L / (L!)²
296  * There are faster ways to calculate this, but we precompute
297  * into a table so let's keep it simple.
298  */
299 double
300 i0(double x)
301 {
302 	double v;
303 	int L;
304 
305 	v = 1.0;
306 	for(L=1; L<10; L++)
307 		v += pow(x/2., 2*L)/pow(fac(L), 2);
308 	return v;
309 }
310 
311 double
312 kaiser(double x, double t, double a)
313 {
314 	if(fabs(x) > t)
315 		return 0.;
316 	return i0(a*sqrt(1-(x*x/(t*t))))/i0(a);
317 }
318 
319 
320 void
321 resamplex(uchar *in, int off, int d, int inx, uchar *out, int outx)
322 {
323 	int i, x, k;
324 	double X, xx, v, rat;
325 
326 
327 	rat = (double)inx/(double)outx;
328 	for(x=0; x<outx; x++){
329 		if(inx == outx){
330 			/* don't resample if size unchanged */
331 			out[off+x*d] = in[off+x*d];
332 			continue;
333 		}
334 		v = 0.0;
335 		X = x*rat;
336 		for(k=-K2; k<=K2; k++){
337 			xx = X + rat*k/10.;
338 			i = xx;
339 			if(i < 0)
340 				i = 0;
341 			if(i >= inx)
342 				i = inx-1;
343 			v += in[off+i*d] * K[K2+k];
344 		}
345 		out[off+x*d] = v;
346 	}
347 }
348 
349 void
350 resampley(uchar **in, int off, int iny, uchar **out, int outy)
351 {
352 	int y, i, k;
353 	double Y, yy, v, rat;
354 
355 	rat = (double)iny/(double)outy;
356 	for(y=0; y<outy; y++){
357 		if(iny == outy){
358 			/* don't resample if size unchanged */
359 			out[y][off] = in[y][off];
360 			continue;
361 		}
362 		v = 0.0;
363 		Y = y*rat;
364 		for(k=-K2; k<=K2; k++){
365 			yy = Y + rat*k/10.;
366 			i = yy;
367 			if(i < 0)
368 				i = 0;
369 			if(i >= iny)
370 				i = iny-1;
371 			v += in[i][off] * K[K2+k];
372 		}
373 		out[y][off] = v;
374 	}
375 
376 }
377 
378 Image*
379 resample(Image *from, Image *to)
380 {
381 	int i, j, bpl, nchan;
382 	uchar **oscan, **nscan;
383 	char tmp[20];
384 	int xsize, ysize;
385 	double v;
386 	Image *t1, *t2;
387 	ulong tchan;
388 
389 	for(i=-K2; i<=K2; i++){
390 		K[K2+i] = kaiser(i/10., K2/10., 4.);
391 	}
392 
393 	/* normalize */
394 	v = 0.0;
395 	for(i=0; i<NK; i++)
396 		v += K[i];
397 	for(i=0; i<NK; i++)
398 		K[i] /= v;
399 
400 	switch(from->chan){
401 	case GREY8:
402 	case RGB24:
403 	case RGBA32:
404 	case ARGB32:
405 	case XRGB32:
406 		break;
407 
408 	case CMAP8:
409 	case RGB15:
410 	case RGB16:
411 		tchan = RGB24;
412 		goto Convert;
413 
414 	case GREY1:
415 	case GREY2:
416 	case GREY4:
417 		tchan = GREY8;
418 	Convert:
419 		/* use library to convert to byte-per-chan form, then convert back */
420 		t1 = xallocimage(display, Rect(0, 0, Dx(from->r), Dy(from->r)), tchan, 0, DNofill);
421 		if(t1 == nil) {
422 			fprint(2, "out of memory for temp image 1 in resample: %r\n");
423 			wexits("memory");
424 		}
425 		drawop(t1, t1->r, from, nil, ZP, S);
426 		t2 = xallocimage(display, to->r, tchan, 0, DNofill);
427 		if(t2 == nil) {
428 			fprint(2, "out of memory temp image 2 in resample: %r\n");
429 			wexits("memory");
430 		}
431 		resample(t1, t2);
432 		drawop(to, to->r, t2, nil, ZP, S);
433 		freeimage(t1);
434 		freeimage(t2);
435 		return to;
436 
437 	default:
438 		sysfatal("can't handle channel type %s", chantostr(tmp, from->chan));
439 	}
440 
441 	xsize = Dx(to->r);
442 	ysize = Dy(to->r);
443 	oscan = malloc(Dy(from->r)*sizeof(uchar*));
444 	nscan = malloc(max(ysize, Dy(from->r))*sizeof(uchar*));
445 	if(oscan == nil || nscan == nil)
446 		sysfatal("can't allocate: %r");
447 
448 	/* unload original image into scan lines */
449 	bpl = bytesperline(from->r, from->depth);
450 	for(i=0; i<Dy(from->r); i++){
451 		oscan[i] = malloc(bpl);
452 		if(oscan[i] == nil)
453 			sysfatal("can't allocate: %r");
454 		j = unloadimage(from, Rect(from->r.min.x, from->r.min.y+i, from->r.max.x, from->r.min.y+i+1), oscan[i], bpl);
455 		if(j != bpl)
456 			sysfatal("unloadimage");
457 	}
458 
459 	/* allocate scan lines for destination. we do y first, so need at least Dy(from->r) lines */
460 	bpl = bytesperline(Rect(0, 0, xsize, Dy(from->r)), from->depth);
461 	for(i=0; i<max(ysize, Dy(from->r)); i++){
462 		nscan[i] = malloc(bpl);
463 		if(nscan[i] == nil)
464 			sysfatal("can't allocate: %r");
465 	}
466 
467 	/* resample in X */
468 	nchan = from->depth/8;
469 	for(i=0; i<Dy(from->r); i++){
470 		for(j=0; j<nchan; j++){
471 			if(j==0 && from->chan==XRGB32)
472 				continue;
473 			resamplex(oscan[i], j, nchan, Dx(from->r), nscan[i], xsize);
474 		}
475 		free(oscan[i]);
476 		oscan[i] = nscan[i];
477 		nscan[i] = malloc(bpl);
478 		if(nscan[i] == nil)
479 			sysfatal("can't allocate: %r");
480 	}
481 
482 	/* resample in Y */
483 	for(i=0; i<xsize; i++)
484 		for(j=0; j<nchan; j++)
485 			resampley(oscan, nchan*i+j, Dy(from->r), nscan, ysize);
486 
487 	/* pack data into destination */
488 	bpl = bytesperline(to->r, from->depth);
489 	for(i=0; i<ysize; i++){
490 		j = loadimage(to, Rect(0, i, xsize, i+1), nscan[i], bpl);
491 		if(j != bpl)
492 			sysfatal("loadimage: %r");
493 	}
494 
495 	for(i=0; i<Dy(from->r); i++){
496 		free(oscan[i]);
497 		free(nscan[i]);
498 	}
499 	free(oscan);
500 	free(nscan);
501 
502 	return to;
503 }